Advanced Compiler Design ImplementationFrom the Foreword by Susan L. Graham: This book takes on the challenges of contemporary languages and architectures, and prepares the reader for the new compiling problems that will inevitably arise in the future. The definitive book on advanced compiler design This comprehensive, up-to-date work examines advanced issues in the design and implementation of compilers for modern processors. Written for professionals and graduate students, the book guides readers in designing and implementing efficient structures for highly optimizing compilers for real-world languages. Covering advanced issues in fundamental areas of compiler design, this book discusses a wide array of possible code optimizations, determining the relative importance of optimizations, and selecting the most effective methods of implementation. * Lays the foundation for understanding the major issues of advanced compiler design * Treats optimization in-depth * Uses four case studies of commercial compiling suites to illustrate different approaches to compiler structure, intermediate-code design, and optimization-these include Sun Microsystems's compiler for SPARC, IBM's for POWER and PowerPC, DEC's for Alpha, and Intel's for Pentium an related processors * Presents numerous clearly defined algorithms based on actual cases * Introduces Informal Compiler Algorithm Notation (ICAN), a language devised by the author to communicate algorithms effectively to people |
Contents
Introduction to Advanced Topics | 1 |
Informal Compiler Algorithm Notation ICAN | 19 |
SymbolTable Structure | 43 |
Intermediate Representations | 67 |
RunTime Support | 105 |
Producing Code Generators Automatically | 137 |
ControlFlow Analysis | 169 |
DataFlow Analysis | 217 |
Register Allocation | 481 |
Code Scheduling | 531 |
ControlFlow and LowLevel Optimizations | 579 |
Interprocedural Analysis and Optimization | 608 |
6 | 659 |
1 | 670 |
3 | 709 |
App A Guide to Assembly Languages Used in This Book | 747 |
Dependence Analysis and Dependence Graphs | 267 |
Alias Analysis | 293 |
Introduction to Optimization | 319 |
Early Optimizations | 329 |
Redundancy Elimination | 377 |
Loop Optimizations | 425 |
Procedure Optimizations | 461 |
A 5 | 753 |
Software Resources | 767 |
List of Illustrations | 773 |
List of Tables | 797 |
| 821 | |
Common terms and phrases
algorithm alias alias analysis aliasing approach architecture assignment basic block begin boolean branch bset cache call graph Chapter code in Figure common-subexpression elimination compiler compute conditional constant propagation constant folding constant propagation construct control-flow copy propagation data structures data-flow analysis dead-code elimination definition dependence depth-first determine discussed edges enddo endfor entry example execution exit expression false floating-point flow functions flowgraph in Figure follows formal parameters Fortran 77 global graph coloring ICAN implementations induction variables inst instruction scheduling integer interference graph intermediate code interprocedural iteration label language lattice loop body loop nest loop-invariant code motion low-level ninsts opd1 opd2 operand operations optimization PA-RISC performed pointer prefetching register allocation represent representation result routine scalar replacement Section sequence set of Node shown in Figure software pipelining SPARC Sparse conditional constant stack frame static Succ symbol table symbolic registers Tail-call optimization transformations tree unrolling value numbering worklist
Popular passages
Page 810 - Hummel, and A. Nicolau. A general data dependence test for dynamic, pointer-based data structures. In Proceedings of the SIGPLAN'94 Conference on Programming Language Design and Implementation, pages 218-229, June 1994.
Page 807 - Dhamdhere. Practical adaptation of the global optimization algorithm of Morel and Renvoise. ACM Transactions on Programming Languages and Systems, 13(2):291-294, April 1991.
Page 804 - 89 Conference on Programming Language Design and Implementation. [2] Preston Briggs. Register Allocation via Graph Coloring. PhD thesis, Rice University, April 1992. [3] Preston Briggs, Keith D. Cooper, Ken Kennedy, and Linda Torczon. Coloring heuristics for register allocation.
Page 802 - Proc. Symp. on Architectural Support for Programming Languages and Operating Systems (Palo Alto, Calif., March 1-3, 1982), ACM, New York, NY, 1982.
Page 808 - ... interface for ANSI C. Software — Practice and Experience, 21(9):963-988, September 1991. [FH91b] Christopher W. Fraser and Robert R. Henry. Hard-coding bottom-up code generation tables to save time and space. Software — Practice and Experience, 21(1):1-12, January 1991. [FHP91] Christopher W. Fraser, Robert R. Henry, and Todd A. Proebsting. BURG — fast optimal instruction selection and tree parsing. Technical Report 1066, University of Wisconsin, 1991. [Han90] David R. Hanson. Fast allocation...
Page 805 - Robert F. Cmelik and David Keppel. Shade: A Fast InstructionSet Simulator for Execution Profiling.
Page 805 - ASPLOS, 1992. [7] WY Chen, SA Mahlke, PP Chang, and WW Hwu, "Data Access Microarchitectures for Superscalar Processors with Compiler-Assisted Data Prefetching", Proc. of 25th MICRO, 1991. [8] C. Chi and H. Dietz, 'Unified Management of Registers and Cache Using Liveness and Cache Bypass", Proc.