TweetFollow Us on Twitter

Jul 96 Factory Floor
Volume Number:12
Issue Number:7
Column Tag:From The Factory Floor

A Little CodeWarrior History

By Dave Mark

This month, we’re going to talk with John McEnerney, one of the compiler writers
at Metrowerks.

Dave: How did you first hook up with Metrowerks?

John: I first met Greg Galanos when I was the development manager at Symantec’s Language Products Group. Greg was trying to get me interested in doing some sort of deal with the fledgling Metrowerks, and I mostly ignored him because they were trying to compete aggressively with my first product, THINK Pascal. I would have never guessed that a few years later he would offer me the best opportunity of my career.

Dave: When did you leave Symantec?

John: I left Symantec in October ’92, taking about 6 months off to figure out what I wanted to do next. I didn’t have any real plans, but I figured I’d find some way to do PowerPC work. I didn’t relish the thought of trying to write an entire C++ compiler, so I considered doing a Pascal product on my own.

Around this time, Greg had heard from Rich Siegel (of BBEdit fame) that I was no longer at Symantec, and he called me right away. The first thing he said to me was, “describe your dream job,” and I told him I wanted to write a PowerPC code generator for the upcoming Power Macintoshes. I flew to Montreal to meet him and his partner, Jean Belanger. We had some Italian food, drank some wine, and they told me a little about their Pascal and Modula products. I was really hot to write a PowerPC backend, but I was not that impressed with their technology. We talked about various contracts, but I didn’t have a really solid feeling yet.

Dave: What finally convinced you to go with Metrowerks?

John: In February ’93, Greg asked me to meet with him in Palo Alto to get a look at a C compiler that they had just acquired; a guy named Andreas Hommel in Hamburg had been writing it as a hobby. It ran on the Macintosh, had a simple but nice IDE reminiscent of early versions of THINK C, and it was fast. I spent about an hour looking through the source code: it was well organized, the compiler front-end and back-end were cleanly separated, the code was easy to follow, and in addition to being a full ANSI C compiler, it had a lot of the C++ language implemented already.

It was clear that Greg had found a diamond in the rough, the perfect platform for a native PowerMacintosh product. A few hours later we had a contract - I had about 6-8 months to write a PowerPC back-end and linker. Andreas would finish the C++ language implementation, and a few guys in Montreal (Berardino Baratta, Marcel Achim) would work on the IDE and a new Pascal front-end. We immediately hired Greg Dow, who had written the THINK Class Library for Symantec when I was there, to write a new application framework: PowerPlant.

We must have hooked up with Jordan Mattson from Apple around this time, because a week or so later he sent me one of their RS/6000s to help me get started. Between him and Alan Lillich, who I had met at all the early PowerPC meetings that Apple had been holding for their key developers, I got pretty much everything I needed from Apple.

So, I now had a contract to do the most interesting work I could imagine; all I had to do was figure out where to start.

Dave: What was it like working with Andreas’ compiler?

John: Andreas’ compiler was pretty traditional in its organization. The front-end made a single pass over the source code, performing lexical analysis as it went, and generated an intermediate representation (IR) that consisted of expression trees, labels, and branches. It took about a week to totally remove the 68K code generator from the rest of the compiler, and put in stub routines where the front-end and the back-end connected so that everything would still link. If I could fill in all the stub routines in exactly the right way, we’d have a PowerPC compiler.

The first thing I did was write a routine that dumped the IR in human-readable form - I don’t know how Andreas got his 68K code generator to work without that, I guess he can keep more in his head than I can. Looking at the expression trees on the screen allowed me to visualize how the code generator would proceed.

Most CISC compilers spend a lot of time working on the IR trees themselves. Traditional global optimizations like loop-invariant code motion or common subexpression elimination are performed by rewriting the IR trees into optimized IR trees. The code generator gathers information about the shape of the trees, deciding how many registers will be needed, which addressing modes will be used, etc. After instructions are generated they are largely ignored except for small “peephole” optimizations. (A notable exception to this is the gcc compiler, which transforms the expressions into a simple algebraic representation called RTL and uses repeated “peephole” optimizations derived from a machine description to coalesce these RTL expressions into complex instructions and addressing modes.)

Most of the RISC compilers that I’d read about in the compiler literature used a different approach: immediately transform the IR trees into a low-level representation that was similar or identical to the actual RISC instructions of the target machine, and perform all optimizations at the machine instruction level. I decided to use this technique in my PowerPC code generator.

Dave: What was your basic approach to code generation?

John: Strange as it may seem, the first part of the code generator I actually wrote was the instruction scheduler - the phase that reorders instructions to minimize latencies caused by load delays, and to permit floating-point and integer instructions to execute in parallel. I needed to know if my low-level representation - I called it a “pcode” (no relation to the UCSD Pascal pcode) - had enough information for all the phases I would eventually write, and since the scheduler needed a lot of information, it would serve to prove the design of the pcode. Of course, I had to rewrite the scheduler twice more: the first time was to fix the original one, which had some design flaws, and the second time was to make it more general to support 601, 603 and 604 CPUs.

Once I finished the scheduler, I had my data structures organized and all the support routines in place, so I started writing the instruction selection phase - the “guts” of the code generator. This phase visits the IR tree and generates pcode. It does try to recognize certain tree patterns, like opportunities for FMADD and FMSUB routines, but since there are no complex addressing modes and very few complex instructions, it is mostly a straightforward translation to PowerPC instructions.

To get short-term results, I wrote a quick-and-dirty register allocator, and some code to display the generated pcode instructions, and was able to get most of the code generation debugged this way. I decided to use a proprietary object code format, derived from the one we were already using in our 68K compiler and linker, since I could get this working faster than trying to write an XCOFF linker. I spent a few weeks getting the linker working, finished the part of the code generator that wrote the object file, and I could actually compile and link small programs.

Dave: How did the debugger fit into all this?

John: Around August ’93 the project was falling into place, but we still didn’t have a source-level debugger. In a most serendipitous event, Dan Podwall, a friend of mine from Symantec, called and asked whether there were any opportunities at Metrowerks. Greg Galanos called him right away, hired him on the phone, and 4 weeks later he had written a debugger - in PowerPlant, no less - that could single-step and set breakpoints. This would be the first commercial PowerPlant program - in fact, the first PowerPlant program of any kind aside from Greg Dow’s demos.

Dave: How did you build the compiler?

John: By September ’93 we had some prototype PowerPC hardware, and I had a working code generator and linker which ran on the 68K Macintosh and generated PEF executables that ran on the prototypes. Since this compiler was already built using our own 68K compiler, it was pretty easy to rehost it on the Power Macintosh: we made the changes for the Universal Headers and routine descriptors and such, then compiled it with itself on the 68K machine, which gave us (after some debugging!) a working PowerPC-hosted PowerPC compiler. With a little bit of trickery, mandated by differences between PowerPC floating-point hardware and the 68K SANE software floating-point architecture, we were able to rehost the 68K compiler on the Power Macintosh as well. We now had the fastest compilers on the Macintosh.

Dave: What next?

John: I still had a lot of work to do on the PowerPC code generator. The biggest task was to replace the quick-and-dirty register allocator with a graph coloring-based allocator. This is one of the great algorithms in the history of compilers. For years people had been trying to come up with an accurate way to represent the lifetimes of variables, so that variables or temporaries that did not overlap could share a register. A lot of ad hoc techniques were developed, but this guy from IBM Watson Research Center named Greg Chaitin discovered a formal approach that solved the problem better than anything that had been previously attempted: build an “interference graph” which has an edge between any two variables whose values may be live at the same time, and then try to color this graph with N colors where N is the number of available registers.

So my code generator assumes it has an infinite number of “virtual” registers, and generates the most efficient code it can under that assumption; for example, it assumes that all local variables, arguments, and TOC pointers can be assigned to a register. After the code is all generated, the register allocator tries to rewrite the virtual registers using real PowerPC registers, and generates extra code to “spill” values that couldn’t get a real register. In most cases, everything gets a register since there are so many on the PowerPC. The smarter register allocator probably makes the overall largest contribution to code quality.

The algorithm has one drawback: it has O(N^2) complexity. There are actually programs which have so many intermediate expressions that the interference graph gets too large and it takes several minutes to color it. So I had to keep around the quick-and-dirty allocator as well, which is why you’ll sometimes get an annoying message that says the code generator ran out of registers if you’re compiling without global optimizations.

Dave: And so, CodeWarrior was born!

John: By December I had pretty much everything working. After a last-minute dash to get C++ language support working on the PowerPC, we were able to burn our first public release, DR/1, starting a long Metrowerks tradition of getting things in under the wire and never missing a ship date. We introduced the product at the San Francisco Macworld Expo with our huge 8-page MacWeek advertisement, and CodeWarrior™ was born.

There were plenty of things to be cleaned up between DR/1 and DR/3, which was our real “1.0” release. But by shipping DR/1 and DR/2 when we did, and by working closely with a lot of the major Macintosh software vendors, we were able to help a lot of companies get their software ported to the PowerMac that otherwise might not have.

For me, I had accomplished what I had wanted to when I was back at Symantec: building the PowerPC compiler that most users would use to port their code to the new Power Macintoshes. And Greg had kept his promise and given me my dream job.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

OmniOutliner Pro 5.4.1 - Pro version of...
OmniOutliner Pro is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
EarthDesk 7.3 - $24.99
EarthDesk replaces your static desktop picture with a rendered image of Earth showing correct sun, moon, and city illumination. With an Internet connection, EarthDesk displays near-real-time global... Read more
Monosnap 3.5.3 - Versatile screenshot ut...
Monosnap lets you capture screenshots, share files, and record video and .gifs! Features Capture Capture full screen, just part of the screen, or a selected window Make your crop area pixel... Read more
Monosnap 3.5.3 - Versatile screenshot ut...
Monosnap lets you capture screenshots, share files, and record video and .gifs! Features Capture Capture full screen, just part of the screen, or a selected window Make your crop area pixel... Read more
Spotify 1.0.93.244 - Stream music, creat...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
Evernote 7.6 - Create searchable notes a...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
Final Cut Pro X 10.4.4 - Professional vi...
Final Cut Pro X is a professional video editing solution. Completely redesigned from the ground up, Final Cut Pro adds extraordinary speed, quality, and flexibility to every part of the post-... Read more
Compressor 4.4.2 - Adds power and flexib...
Compressor adds power and flexibility to Final Cut Pro X export. Customize output settings, work faster with distributed encoding, and tap into a comprehensive set of delivery features. Features... Read more
Motion 5.4.2 - Create and customize Fina...
Motion is designed for video editors, Motion 5 lets you customize Final Cut Pro titles, transitions, and effects. Or create your own dazzling animations in 2D or 3D space, with real-time feedback as... Read more
Thunderbird 60.3.1 - Email client from M...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more

Latest Forum Discussions

See All

Slots Panther Vegas offers a social gamb...
New era of Online gambling Want to try your luck in online social gambling? More and more people are into online casinos as a risk-free amazing way to experience the excitement of a big game. Online casinos and slots machines are gaining popularity... | Read more »
3 features we think you'll love in...
Well known classic RPG “Shin Megami Tensei” franchise originally created by Atlus, can now be played throughout iOS and Android. Created by Sega, “Shin Megami Tensei” has spawned a mobile-centric installment in the shape of “Shin Megami Tensei:... | Read more »
These are the top 3 games for iPhone and...
The end of the week has rolled around again, which means it's time for us to look forward to the games you're going to be playing over the next seven days. We've got the return of a mobile gaming legend next week, as well as a couple of other... | Read more »
Time for you to pick which of these top...
Oh look, Thursday is upon us once more. And we all know what that means! You guessed it, it's time for you to vote for which of these five games you think deserves to win our game of the week award. And have we got a selection for y'all this week... | Read more »
Dragalia Lost - High Midgardsormr Prep G...
It might not seem like there's a ton to do between events in Dragalia Lost, but there is one high level piece of content that can keep you occupied for a long time. Defeating High Midgardsormr is currently the game's most difficult non-event... | Read more »
Get your friends, these are the top 5 be...
You can't be a lone wolf all the time, especially if you want to show off your gaming prowess. And that's where this list comes in - we're running down what we think are the top 5 multiplayer games for iPhone. There might be some controversial... | Read more »
SpitKiss is the worthy winner of last we...
It's been a rough and tumble battle this week, with all of the games managing to get a few hits in where it counts, but after checking with the independent adjudicators at ringside, we can now reveal that gloriously gross smooching sim SpitKiss has... | Read more »
The best games for iPhone - The definiti...
Hi there, and welcome to our ever-increasing list of the very best games for iPhone. We're going to be updating this regularly with new content, so make sure you check back often, because you're not going to want to miss out on even one of the... | Read more »
Dragalia Lost Guide - What You Need To K...
Another raid has come and gone in Dragalia Lost, but that doesn’t mean there’s not still lots to do. In fact, the game’s next event, A Wish to the Winds, has already been announced and will be coming to the game this Wednesday. Although details are... | Read more »
The top 5 best games like Star Wars: Gal...
One of the things we like to do here at 148Apps is broaden your horizons. Maybe you're a fan of Star Wars: Galaxy of Heroes and you're looking for something that's going to scratch similar itches? Well that's where we come, and more specifically... | Read more »

Price Scanner via MacPrices.net

Save on a new MacBook with these early Black...
B&H Photo has posted early Black Friday sale prices on Apple MacBooks, including up to $300 off MSRP on 15″ MacBook Pros, $100 off new 13″ MacBook Airs, and more. Most of these deals expire... Read more
T-Mobile Black Friday deal: Free iPhone Xr wi...
T-Mobile is offering the 64GB iPhone Xr for free as part of their Black Friday 2018 sale. Two new lines are required, as well as an eligible trade-in (iPhone 6s models or newer). $20.84 is applied to... Read more
Save up to $157 on a 10.5″ iPad Pro with thes...
Apple’s newest authorized reseller, Jet, has 10.5″ iPad Pros on sale for up to $157 off MSRP as part of their Black Friday week sale. Shipping is free. Note that some sale prices may be restricted to... Read more
US Cellular offers free iPhone Xr for new lin...
US Cellular is offering the 64GB iPhone Xr for free as part of their Black Friday 2018 sale. A new line is required, but there is no trade in requirement. Any of the iPhone Xr colors qualify. The... Read more
Roundup of Black Friday Week 2018 Sales &...
At MacPrices.net, we give you the most accurate Mac and Apple prices on the web. Choose one of our price trackers at the top of the page to see all the current sale prices on Apple’s products from... Read more
Details of Amazon’s 2018 Black Friday week di...
Amazon’s recent agreement with Apple has allowed the online store to add most of Apple’s most popular products to its inventory, including new 2018 iPad Pros, Mac minis, Apple Watch Series 4, and... Read more
Get A Job With Apple, The No. 3 ‘World’s Best...
FEATURE: 11.16.18- If you are a fan of Apple, Inc. and an avid user of any one of its vast array of tech gadgets, why not take it a step further and work for the company behind those products you... Read more
Sprint offers $100 discounts on Apple Watch S...
Sprint is offering customers $100 discounts on the purchase of a cellular Apple Watch Series 4 or Apple Watch Series 3. Their discount reduces the cost of a Series 4 watch to $399 (40mm) or $429 (... Read more
New 2018 11″ 64GB & 256GB iPad Pros in st...
MacMall has the new 2018 11″ 64GB and 256GB iPad Pros in stock today for $50 off Apple’s prices. They’re currently the lowest prices available for these new iPad Pros. – 11″ 64GB Space Gray WiFi iPad... Read more
New Mac minis in stock and available today at...
Apple Authorized Reseller Adorama has the new 2018 Mac minis in stock today today sales tax free for residents outside of NY & NJ. Shipping is also free. – 3.6GHz Quad-Core mini: $799 – 3.0GHz 6... Read more

Jobs Board

Best Buy *Apple* Computing Master - Best Bu...
**658102BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Location Number:** 000395-Pensacola-Store **Job Description:** **What does a Read more
*Apple* Mobile Master - Best Buy (United Sta...
**658022BR** **Job Title:** Apple Mobile Master **Job Category:** Store Associates **Location Number:** 000793-Dothan-Store **Job Description:** **What does a Best Read more
Geek Squad *Apple* Master Consultation Agen...
**657784BR** **Job Title:** Geek Squad Apple Master Consultation Agent **Job Category:** Services/Installation/Repair **Location Number:** 000597-Erie-Store **Job Read more
Best Buy *Apple* Computing Master - Best Bu...
**655276BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Location Number:** 000387-Randall Road-Store **Job Description:** **What does a Read more
Omni-Channel Associate - *Apple* Blossom Ma...
Omni-Channel Associate - Apple Blossom Mall Location:Winchester, VA, United States- Apple Blossom Mall 1850 Apple Blossom Dr Job ID:1074107 Date:November 12, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.