Code Generation in a Machine-Independent Compiler

RETROSPECTIVE: Code Generation in a Machine-Independent Compiler R. G. G. Cattell Sun Microsystems Santa Clara, CA 95054 cattell@sun.com Joseph M. Newcomer Joseph M. Newcomer Co. Pittsburgh, PA 15208 newcomer@flounder.com Bruce W. Leverett Spinnaker Networks Pittsburgh, PA 15238 bleverett@spinnakernet.com Our paper was one of several describing the work of the Production-Quality Compiler-Compiler (PQCC) research project at Carnegie-Mellon University. The paper focused on the code optimization and code generation phases of compilation. A later, broader paper on the PQCC project can be found in [Lev 80]. We left the compiler field a few years after that, so we apologize in advance that our retrospective is limited in its coverage of more recent work. Like most software projects at CMU, PQCC was entwined with many other projects in the Computer Science Department. These dependencies allowed us to stand on other’s shoulders and make progress on systems projects that required a lot of coordinated work to construct. PQCC built on the ISP machine description language [Bar 77], the Bliss-11 optimizing compiler [Wul 75], and heuristic search techniques from the AI work. Other members of the PQCC project included Steve Hobbs, Andy Reiner, Bruce Schatz, David Lamb, David Levine, Mathai Joseph, Peter Thiesen, and the project’s leader, Bill Wulf. We drew most heavily from the Bliss-11 optimizing compiler project. While we made some improvements in PQCC, the structure of our compiler was very similar to Bliss-11’s: the LEXSYN, FLOW, DELAY, TNBIND, CODE, and FINAL phases are illustrated in Figure 1 of the paper. Important Bliss- 11 compiler dissertations included [Ges 72], [Joh 75], and [Wei 76]. The PQCC compiler-compiler was unusual in its time because we focused on automatic generation of the back end of compiler; parser generators were already available to simplify the front end. The PQCC front end produced from the source programming language an intermediate tree representation we called TCOL (Tree Common Language) [New 79]. After that, various back end optimization phases “decorated” the TCOL as the compilation proceeded. Only the final peephole optimizer worked on the machine code representation. The motivation for the PQCC compiler-compiler was simple: with dozens of machine architectures and programming languages in common use, it was tedious to manually build a cross-product of compilers for all of the combinations, especially where good code quality was desired. Today compiler-compilers have assumed less importance. However, many of today’s compilers use techniques that were introduced at the time of Bliss-11 and PQCC, and today many compilers use a source-independent semantic tree for the back end of the compiler, use register allocation and code generation techniques similar to PQCC, and encode target machine dependencies in tables and rules. 20 Years of the ACM/SIGPLAN Conference on Programming Language Design and Implementation (1979-1999): A Selection, 2003. Copyright 2003 ACM 1-58113-623-4 $5.00 Other work in industry and academia took off on our work. Unfortunately, our knowledge of this work is now limited. Bill Wulf started a software company, Tartan Labs, based on the work of his students on PQCC. Tartan’s charter focus was on the generation of compilers. Our PhD dissertations [Cat 82, Lev 83] were published as books that were used in graduate compiler courses, along with other PQCC work and the Bliss-11 compiler book [Wul 77]. On the other hand, the compiler scene has changed dramatically in ways that make PQCC less applicable. Cheap memory makes space optimization less important. Processors are now much, much faster than memory. Pipelined architectures with L1 and L2 caches invalidate our simple assumption that instruction cycles and memory cycles are the only optimization measures. In a pipelined superscalar architecture, register-to-register transfers can often overlap because dynamic register renaming under the floor makes the cost close to zero. RISC added, in some cases, ordering constraints, and some cases (e.g., the Intel 960) the problem is that the floating point unit is a push-through unit, with an n-step delay pipe, where you have to force a result out, which gives a complex code ordering problem. Superscalar architectures and machines with multiple ALU/FPU concurrency also add complexity. Although vector machines already existed in the 1970s, we had specifically excluded them because the optimization strategies were more along the lines of algorithm transformations. Today, high-order multiprocessor systems with thousands of processors are available, and the algorithm issues are even more critical, yet PQCC did not focus in that direction at all. In most cases, we were performing optimizations that fit well in the classic single-stream, non-piped, single ALU/FPU, constant- time (for a given instruction with its specific addressing modes) model but would be somewhere between pointless and negative in some modern systems. Many of our key assumptions simply didn't even address these problems. Good results for their era, but today the problem is much harder. At the time the paper was written, not only were architectures different from those of today, but computers were much smaller and slower. Not only are clock speeds of modern machines faster than the machines of our research era, but the architectures accomplish more per clock cycle. Compare, for example, a .5GB, 2.0GHz Pentium IV processor, capable of doing a 32x32bit floating point multiply in one clock cycle, with a 256K 1-MIPS PDP-10/20 or the even smaller (64K, .3MIPS) minicomputers of the 1970's. Does this breathtaking advance in technology even call into question the motivation for code optimization? Surely the great majority of applications are not processor-bound or even memory-bound, and code optimization is the concern of a band of aficionados, rather than of compiler users everywhere. ACM SIGPLAN 1 Best of PLDI 1979-1999 Even 20 years ago that was true. But for those who push the envelope of the computer power available to them, code quality is still an issue, even though the terms of the definition have changed. References [Bar 77] Mario Barbacci, Gary Barnes, Rick Cattell, Dan Siewiorek. The ISPS Computer Description Language, Technical Report (revised as CMU-CS-79-137), Computer Science, Carnegie-Mellon University, August 1977. [Cat 82] R. G. G. Cattell, Formalization and Automatic Generation of Code Generators, UMI Research Press, Ann Arbor, 1982. [Ges 72] Charles M. Geschke. Global Program Optimizations, PhD dissertation, Computer Science Department, Carnegie- Mellon University, 1972. [Joh 75] Richard K. Johnsson. An Approach to Global Register Allocation, PhD dissertation, Computer Science Department, Carnegie-Mellon University, 1975. [Lev 80] Bruce W. Leverett, Roderic G. G. Cattell, Steven O. Hobbs, Joseph M. Newcomer, Andrew H. Reainer, Bruce R. Schatz, and William A. Wulf. An Overview of the Production- Quality Compiler-Compiler Project, IEEE Computer 13:8 (August 1980) p38. [Lev 83] Bruce W. Leverett, Register Allocation in Optimizing Compilers, UMI Research Press, Ann Arbor, 1983. [New 79] J.M. Newcomer, D.A. Lamb, B.W. Leverett, D. Levine, A.H. Reiner, M. Tighe, and W.A. Wulf. TCOL: Revised Report on An Intermediate Representation for the Ada DOD Standard Programming Language, Technical Report CMU-CS-79-128, June 1979. [Wei 76] Charles Weinstock. Analysis of Storage Allocation. PhD dissertation, Computer Science Department, Carnegie- Mellon University, 1976. [Wul 75] William Wulf, Richard K. Johnsson, Charles B. Weinstock, Steven O. Hobbs, and Charles M. Geschke. The Design of an Optimizing Compiler, American Elsevier, 1975. ACM SIGPLAN 2 Best of PLDI 1979-1999 ACM SIGPLAN 3 Best of PLDI 1979-1999 ACM SIGPLAN 4 Best of PLDI 1979-1999 ACM SIGPLAN 5 Best of PLDI 1979-1999 ACM SIGPLAN 6 Best of PLDI 1979-1999 ACM SIGPLAN 7 Best of PLDI 1979-1999 ACM SIGPLAN 8 Best of PLDI 1979-1999 ACM SIGPLAN 9 Best of PLDI 1979-1999 ACM SIGPLAN 10 Best of PLDI 1979-1999 ACM SIGPLAN 11 Best of PLDI 1979-1999 ACM SIGPLAN 12 Best of PLDI 1979-1999 ACM SIGPLAN 13 Best of PLDI 1979-1999