TweetFollow Us on Twitter

Sep 96 Factory Floor
Volume Number:12
Issue Number:9
Column Tag:From The Factory Floor

Andreas Hommel, Compiler Architect

By Dave Mark

This month’s interview is with Andreas Hommel, one of the original minds behind Metrowerks’ compiler architecture. (See “A Little CodeWarrior History”, MacTech Magazine 12.7 [July 1996] 61-64, where John McEnerney recalls being shown Metrowerks’ newly acquired C compiler which “a guy named Andreas Hommel in Hamburg had been writing as a hobby”.) You’ll meet a pretty interesting person and, at the same time, learn a thing or two about the compilation process.

Dave: How did you hook up with Metrowerks?

Andreas: I got interested in compiler construction while I was still in University. I was writing computer games, and most C compilers didn’t really produce very good code. Also, I liked ANSI C a lot, but back then, Mac compilers didn’t really conform to this standard. So at one point, I decided that it would be fun to write my own compiler in my spare time. Two or three years later, I had my own little IDE and an ANSI C compiler with some C++ extensions.

I was about to finish my CS degree, and I had a good desktop publishing job offer in Hamburg, but I really liked working on my compiler project, so I decided to give it a try. I sent out a bunch of demo disks to some Macintosh compiler-related companies. A few months later, Greg Galanos called me and we started talking about technical details of the compiler and how we could come together. After a couple of Transatlantic phone calls, Greg invited me to come to Montreal to meet with him and Jean Belanger. They spoke about the incredible opportunities for a compiler company, given Apple’s pending transition to the PowerPC chip. We also talked a lot about all the technical aspects of the compiler and how it could be changed to support another code generator and a Pascal front-end. A week later, we had signed a contract.

The next 6 months were pretty busy. I still had some work to do for my old job, I had to finish and defend my thesis, and I had to start moving the compiler towards C++ for Metrowerks.

Dave: For folks who’ve never written a compiler, can you describe the compilation/link process?

Andreas: The compiler transforms each individual source file (or “translation unit”, to be technically correct) into an object file. The functions, procedures, and variables in a source file are transformed into code and data in the object file. The code in an object file is not executable because it usually contains references to code or data in other object files; these references have yet to be resolved by the linker. The unresolved references are also stored in the object file. The CodeWarrior IDE actually hides much of this process, because it stores all the object files in the project file, so you don’t see them on your hard drive (if you use the CW MPW tools, you will actually generate individual object files). The object file also stores symbolic information that is used by the Source Debugger to map source code to executable code and to find variables and their types. If you are interested in this, and you know a little bit of Assembly Language, you can use the Disassemble command (in the Project menu), which will generate a pretty complete object file dump for a particular source file.

The linker then takes all the object files (a library file is basically just an object file), resolves the external code and data references, and generates an executable file from that. On the Macintosh, the linker also merges your application with the resource data and generates a SYM file that is used by the debugger.

Dave: What about the actual compilation process?

Andreas: The compiler itself can be grouped into several phases. A user typically doesn’t notice these individual phases, and in fact most compilers do not strictly execute one phase after the other, but this logical grouping really makes it a lot easier to implement a compiler.

The first phase is the Lexical Analyzer or Scanner. This part of the compiler “looks” at your source code and splits it into individual tokens. A token is a small lexical element. For example, in C, operators such as '+', '--', '->', and keywords such as for and while are individual tokens. Identifiers, numbers and strings are also considered as tokens with attributes. For example, "123" is a numerical token with the attribute/value 123. A lexical analyzer for C and C++ is quite complicated, because it usually also implements the preprocessor, so it has to take care of source file inclusion (#include), macro expansions (#define) and conditional compilation (#if). All this is hidden from the remaining parts of the compiler, and the CodeWarrior lexical analyzer transforms a source file into a uniform stream of tokens.

The next phase is the Syntax Analyzer or Parser. Most computer languages (including C, C++, Pascal and Java) have a grammar which is a set of rules that describes which token sequences form a legal program. The parser makes sure that the stream of tokens conforms to these rules. For example, the rule for a while statement is:

<iteration-statement>: while ( <expression> ) <statement>

<iteration-statement> is the name of this grammar rule. while, '(' and ')' are tokens; <expression> and <statement> are called non-terminal tokens, which means they have to be replaced by other tokens or rules. The parser transforms the stream of individual tokens into another data structure (usually a syntax tree) that is used by the remaining phases.

The next phase is the Semantic Analyzer. The parser makes sure that a program conforms to the grammar, but it doesn’t catch any other types of error. For example, “1=2;” is a syntactically correct C assignment expression statement that is semantically incorrect, because you cannot assign 2 to 1. So this phase makes sure that types in a program match, that all identifiers (or variables) have been defined, and that operand types in expressions match.

Now we have a legal program and all we have to do is generate code from it. One could generate code directly from a syntax tree, but usually a compiler generates an intermediate code representation. For example, CodeWarrior uses a tree-based intermediate code (IR tree) that is very close to a syntax tree but has a lot of additional information about types. In fact, the CodeWarrior compiler folds the syntactic, semantic and intermediate code generation together, so basically the parser also checks the semantics and it generates an IR tree. This really speeds up the whole process. This IR tree is really the key to our compiler technology. All code generation is based on this tree. So this makes our front-ends (C/C++/Pascal) and back-ends (68K, MIPS, PPC, x86) interchangeable.

This IR tree is then passed to the individual back-ends where it is used to generate the actual 68K, PPC, MIPS, or x86 code. The back-ends are all pretty different, but they all transform the IR tree into machine instruction sequences, allocate memory and registers for variables, and generate an object file. All back-ends also do some machine-level optimizations (peephole optimizations) that replace instructions with better ones or remove redundant instructions.

We have an IR-level optimizer that removes redundant parts from this tree and does some other basic things to optimize branches. We also have a high-level IR optimizer that is currently used in the x86 compiler, but this optimizer will eventually also be used in the MIPS or 68K compilers. The PPC back-end is a little special because most of its optimization is done in the back-end. This makes sense, because the PPC’s RISC instructions are very simple, so you can do a lot of high-level optimizations (such as loop optimizations and common subexpressions) with more fine control on the actual machine level and get better results. This would be very hard to do for a CISC processor like the 68K with all its complex instructions and addressing modes.

Dave: With that in mind, what did your original development environment look like, from a technical perspective?

Andreas: It had pretty much all the basic functionality you need to write programs in C. It had a project window, a multi-window text editor, find and replace, and some simple Preference dialogs. It even had some nice little features such as function popups and multiple access paths, but a lot of major features such as multi-language support, plug-in compiler support, collapsible project views, syntax coloring, split-pane editing, multiple-pane Preference dialogs, a tool bar, and tool-server support, have been added to it since then.

Dave: How would you compare your original compiler architecture with the current CodeWarrior architecture?

Andreas: The original compiler and linker didn’t support a plug-in interface, and everything had to be linked into the IDE. I always had multiple back-end support in mind, and I was always using the IR tree. However, when John McEnerney started writing the PPC back-end, I had to clean up the front-end/back-end interface, and we had to change a few other minor things. There were also some changes in the 68K back-end, to support some Pascal-specific features such as sets and nested local variables.

There have been a lot of changes in the front-end. The original compiler had some basic support for C++ classes and function overloading, so a lot of stuff had to be added since then. I also had to change quite a few things to support multiple platforms (Mac OS, x86, MIPS). Recently, I had to make some additions to the IR to support zero runtime overhead exception handling. This also required changes in the back-ends.

Dave: What special work do you have to do in the front-end to enable multiple platform support? For example, what did you have to do to CodeWarrior to make sure it would support x86, MIPS, and 680x0 code generation?

Andreas: There are a number of areas where a front-end needs to be aware of back-end requirements. For example a C struct’s member layout is done in the front-end, so you have to be aware of the data-member alignment of the target architecture. Another problem has to do with integral and floating-point type differences. For example, a long double is an 80-bit type on 68K but a 64-bit type on the PPC. In the same vein, the x86 uses a different byte ordering (little-endian) than the 68K (big-endian). Most of the functions that deal with these issues have been isolated into target-specific front-end files.

There are also some language-specific issues. For example, both Apple and Microsoft have their own C and C++ language extensions, and the front-end needs to support all of them. One of the biggest problems is C++. There are many very powerful features in C++ like multiple inheritance, polymorphism, exception handling and runtime type identification. The ANSI C++ Standard defines how all these features work, but it does not define how they should be implemented, so every compiler vendor has their own implementation. For example, there are many ways to implement virtual function calls or to allocate base classes in a derived class hierarchy. We always had our own implementation for this, but now, with the x86 compiler, we also have to conform to Microsoft’s standard class layout. We’re still targeting full compatibility, and this requires more work in the front-end as we go forward.

Dave: Beginning with CW8, CodeWarrior offered support for zero runtime overhead. First, what is zero runtime overhead? Second, what advantages does it offer?

Andreas: C++ exception handling requires that all local class variables that have been constructed between a try and a throw be destroyed before an exception is handled in a catch block. This process is called stack unwinding. Our first exception implementation was based on a pseudo-setjmp/longjmp, and a linked list of all active local stack objects needing destruction. This was relatively easy to implement in the front-end, and it required no changes in any of the back-ends. So we were able to support exceptions in all our back-ends at the same time.

However, this implementation requires some runtime overhead. For example, each local class object that needs destruction has to be registered when it is constructed and unregistered when it is destroyed. Also, the setjmp call that was required for every try block was very expensive on the PPC, because it had to save all processor registers in a local buffer, and this implementation had to modify a global variable, so it did not work very well with threads.

Our zero runtime overhead implementation is no longer using setjmp or a linked list. Instead, the stack unwinding process is done by examining the processor’s stack and using a pretty complex exception table that tells the exception handler how to locate local variables and how to destroy them. So there is no runtime overhead required for saving registers or registering local objects. Throwing an exception is actually a little bit slower because the stack unwinder is a lot more complicated, but usually exceptions are really exceptional so your application runs much faster. Another advantage is that this exception model doesn’t have to modify any global variables, so it is really thread-safe.

The only disadvantage is that the stack unwinder can only unwind functions that do have an entry in the exception table. The current Mac OS doesn’t have any exception tables, so you can no longer throw an exception in an OS callback function and catch it in your main program, which was possible (but not recommended) in the previous implementation.

Dave: ANSI C and ANSI C++ are two different languages, yet there is a single front-end to handle both. How does this work?

Andreas: ANSI C++ was derived from ANSI C, and most of its new features are really add-ons. Almost all ANSI C features are also supported in C++, so I was able to support both languages from the same front-end by disabling C++ features depending on the state of a global variable. There are some syntactic and semantic differences, but I was able to code around those with some “if-else” statements. This really makes adding features or fixing bugs a lot easier, because everything will only have to be done once. What’s also really interesting is that our compiler architecture allows us to treat both C and C++ with the same front-end, making the transition from C to C++ much easier because it’s the same compiler. Just flip a switch and write your code.

Dave: When you first started on your compiler, work on a C++ standard had just begun (with the publication of the Annotated C++ Reference Manual, or ARM). How has this process evolved?

Andreas: The ARM was the only real useful C++ language reference when I started. This book was used as the base document for the ANSI C++ standard. It has a lot of gray areas, and the template chapter is really vague, but it has some useful sections that explain how certain C++ features like virtual functions can be implemented. Unfortunately, those sections have been removed from the standard.

The current ANSI C++ draft is the size of a phone book. Many features (namespaces, RTTI, bool/true/false, a complete C++ library) have been added to the original definition, and there are three or four revisions every year. It is very hard to keep track of all these changes, and I think it will take another two years until there will be a final ANSI C++ standard.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Skype 8.52.0.138 - Voice-over-internet p...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more
Bookends 13.2.6 - Reference management a...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Bookends uses the cloud to sync reference libraries on all the Macs you use.... Read more
BusyContacts 1.4.0 - Fast, efficient con...
BusyContacts is a contact manager for OS X that makes creating, finding, and managing contacts faster and more efficient. It brings to contact management the same power, flexibility, and sharing... Read more
Chromium 77.0.3865.75 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. Version 77.0.3865.75: A list of changes is available... Read more
DiskCatalogMaker 7.5.5 - Catalog your di...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast Finder-like intuitive look and feel Super-fast search algorithm Can compress catalog data for... Read more
Alfred 4.0.4 - Quick launcher for apps a...
Alfred is an award-winning productivity application for OS X. Alfred saves you time when you search for files online or on your Mac. Be more productive with hotkeys, keywords, and file actions at... Read more
A Better Finder Rename 10.45 - File, pho...
A Better Finder Rename is the most complete renaming solution available on the market today. That's why, since 1996, tens of thousands of hobbyists, professionals and businesses depend on A Better... Read more
iFinance 4.5.11 - Comprehensively manage...
iFinance allows you to keep track of your income and spending -- from your lunchbreak coffee to your new car -- in the most convenient and fastest way. Clearly arranged transaction lists of all your... Read more
OmniGraffle Pro 7.11.3 - Create diagrams...
OmniGraffle Pro helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use... Read more
BBEdit 12.6.7 - Powerful text and HTML e...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more

Latest Forum Discussions

See All

Five Nights at Freddy's AR: Special...
Five Nights at Freddy's AR: Special Delivery is a terrifying new nightmare from developer Illumix. Last week, FNAF fans were sent into a frenzy by a short teaser for what we now know to be Special Delivery. Those in the comments were quick to... | Read more »
Rush Rally 3's new live events are...
Last week, Rush Rally 3 got updated with live events, and it’s one of the best things to happen to racing games on mobile. Prior to this update, the game already had multiplayer, but live events are more convenient in the sense that it’s somewhat... | Read more »
Why your free-to-play racer sucks
It’s been this way for a while now, but playing Hot Wheels Infinite Loop really highlights a big issue with free-to-play mobile racing games: They suck. It doesn’t matter if you’re trying going for realism, cart racing, or arcade nonsense, they’re... | Read more »
Steam Link Spotlight - The Banner Saga 3
Steam Link Spotlight is a new feature where we take a look at PC games that play exceptionally well using the Steam Link app. Our last entry talked about Terry Cavanaugh’s incredible Dicey Dungeons. Read about how it’s a great mobile experience... | Read more »
PSA: GRIS has some issues
You may or may not have seen that Devolver Digital just released GRIS on the App Store, but we wanted to do a quick public service announcement to say that you might not want to hop on buying it just yet. The puzzle platformer has come to small... | Read more »
Explore the world around you in new matc...
Got a hankering for a fresh-feeling Match-3 puzzle game that offers a unique twist? You might find exactly what you’re looking for with What a Wonderful World, a new spin on the classic mobile genre which merges entertaining puzzles with global... | Read more »
Combo Quest (Games)
Combo Quest 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: Combo Quest is an epic, time tap role-playing adventure. In this unique masterpiece, you are a knight on a heroic quest to retrieve... | Read more »
Hero Emblems (Games)
Hero Emblems 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: ** 25% OFF for a limited time to celebrate the release ** ** Note for iPhone 6 user: If it doesn't run fullscreen on your device... | Read more »
Puzzle Blitz (Games)
Puzzle Blitz 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Puzzle Blitz is a frantic puzzle solving race against the clock! Solve as many puzzles as you can, before time runs out! You have... | Read more »
Sky Patrol (Games)
Sky Patrol 1.0.1 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.1 (iTunes) Description: 'Strategic Twist On The Classic Shooter Genre' - Indie Game Mag... | Read more »

Price Scanner via MacPrices.net

Save $150-$250 on 10.2″ WiFi + Cellular iPads...
Verizon is offering $150-$250 discounts on Apple’s new 10.2″ WiFi + Cellular iPad with service. Buy the iPad itself and save $150. Save $250 on the purchase of an iPad along with an iPhone. The fine... Read more
Apple continues to offer 13″ 2.3GHz Dual-Core...
Apple has Certified Refurbished 2017 13″ 2.3GHz Dual-Core non-Touch Bar MacBook Pros available starting at $1019. An standard Apple one-year warranty is included with each model, outer cases are new... Read more
Apple restocks 2018 MacBook Airs, Certified R...
Apple has restocked Certified Refurbished 2018 13″ MacBook Airs starting at only $849. Each MacBook features a new outer case, comes with a standard Apple one-year warranty, and is shipped free. The... Read more
Sunday Sale! 2019 27″ 5K 6-Core iMacs for $20...
B&H Photo has the new 2019 27″ 5K 6-Core iMacs on stock today and on sale for up to $250 off Apple’s MSRP. Overnight shipping is free to many locations in the US. These are the same iMacs sold by... Read more
Weekend Sale! 2019 13″ MacBook Airs for $200...
Amazon has new 2019 13″ MacBook Airs on sale for $200 off Apple’s MSRP, with prices starting at $899, each including free shipping. Be sure to select Amazon as the seller during checkout, rather than... Read more
2019 15″ MacBook Pros now on sale for $350-$4...
B&H Photo has Apple’s 2019 15″ 6-Core and 8-Core MacBook Pros on sale today for $350-$400 off MSRP, starting at $2049, with free overnight shipping available to many addresses in the US: – 2019... Read more
Buy one Apple Watch Series 5 at Verizon, get...
Buy one Apple Watch Series 5 at Verizon, and get a second Watch for 50% off. Plus save $10 on your first month of service. The fine print: “Buy Apple Watch, get another up to 50% off on us. Plus $10... Read more
Sprint offers 64GB iPhone 11 for free to new...
Sprint will include the 64GB iPhone 11 for free for new customers with an eligible trade-in in of the iPhone 7 or newer through September 19, 2019. The fine print: “iPhone 11 64GB $0/mo. iPhone 11... Read more
Verizon offers new iPhone 11 models for up to...
Verizon is offering Apple’s new iPhone 11 models for $500 off MSRP to new customers with an eligible trade-in (see list below). Discount is applied via monthly bill credits over 24 months. Verizon is... Read more
AT&T offers free $300 reward card + free...
AT&T Wireless will include a second free 64GB iPhone 11 with the purchase of one eligible iPhone at full price. They will also include a free $300 rewards card. The fine print: “Buy an elig.... Read more

Jobs Board

Student Employment (Blue *Apple* Cafe) Spri...
Student Employment (Blue Apple Cafe) Spring 2019 Penn State University Campus/Location: Penn State Brandywine Campus City: Media, PA Date Announced: 12/20/2018 Date Read more
Best Buy *Apple* Computing Master - Best Bu...
**732359BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Location Number:** 000171-Winchester Road-Store **Job Description:** Read more
*Apple* Mobile Master - Best Buy (United Sta...
**732324BR** **Job Title:** Apple Mobile Master **Job Category:** Store Associates **Location Number:** 000013-Fargo-Store **Job Description:** **What does a Best Read more
Best Buy *Apple* Computing Master - Best Bu...
**732455BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Location Number:** 000449-Auburn Hills-Store **Job Description:** **What does a Read more
*Apple* Mobility Pro - Best Buy (United Stat...
**732490BR** **Job Title:** Apple Mobility Pro **Job Category:** Store Associates **Location Number:** 000449-Auburn Hills-Store **Job Description:** At Best Buy, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.