Penrose Director o f Production and Manufacturing Senior Production Editor Cheri Palmer Editorial Coordinator Jane Elliott Cover Design Ross Carron Design Text Design, Composition, and Illustration Copyeditor Jeff Van Bueren Proofreader Jennifer McClain Indexer Ty Koontz Printer Courier CorporationĪ Harcourt Science and Technology Company 525 B Street, Suite 1900, San Diego, CA 92101-4495, USA http:/lAcademic Press Harcourt Place, 32 Jamestown Road, London, NW1 7BY, United Kingdom http:llMorgan Kaufmann Publishers 340 Pine Street, Sixth Floor, San Francisco, CA 94104-3205, USA © 1997 by Academic Press All rights reserved Printed in the United States of America 04 A version of this diagram appears in Chapters 1 and 11 through 20 to guide the reader in ordering optimizer components in a compiler.Īdvanced Compiler Design and Implementation Three optimizations, namely, constant folding, algebraic simplification, and reassociation, are in boxes connected to the other phases of the optimization process by dotted lines because they are best structured as subroutines that can be invoked whenever they are needed. These optimizations are performed at link time, so they operate on relocatable object code.
Compiler design textbook code#
These optimizations are almost always done on a low-level form of code-one that may be quite machine-dependent (e.g., a structured assembly language) or that may be somewhat more general, such as the low-level intermediate code used in this book- because they require that addresses have been turned into the form required by the target processor and because several of them require low-level control-flow code. They also represent a choice of the data-flow analyses used to perform the optimization. The branches from C l to C2 and C3 represent a choice of the method used to perform essentially the same optimization (namely, moving computations to places where they are per formed less frequently without changing the semantics of the program). If, on the other hand, some optimizations are performed on a medium-level, relatively machine-independent intermedi ate code and others are performed on low-level code after code generation (known as the “ mixed” model), then these optimizations are generally done on the medium-level interme diate code. If code selection is done before all optimizations other than those in box A (known as the “ low-level” model of optimizer struc ture), then these optimizations are performed on low-level code. These optimizations are typically performed on medium- or low-level intermediate code, depending on the overall organization of the compiler.
Interprocedural register allocation Aggregation of global references Interprocedural I-cache optimization
Compiler design textbook software#
In-line expansion Leaf-routine optimization Shrink wrapping Machine idioms Tail merging Branch optimizations and conditional moves Dead-code elimination Software pipelining, with loop unrolling, variable expansion, register renaming, and hierarchical reduction Basic-block and branch scheduling 1 Register allocation by graph coloring Basic-block and branch scheduling 2 Intraprocedural I-cache optimization Instruction prefetching Data prefetching Branch prediction (to constant folding, algebraic simplifications, and reassociation) Usually, these optimizations are done very early in the compilation process, since compilation tends to lower the level of the code as it proceeds from one phase to the next. These optim izations typically are applied either to source code or to a high-level intermediate code that preserves loop structure and the sequence in which operations are performed and that has array accesses in essentially their source-code form. The correspondence between letters and code levels is as follows: The letters at the left in the diagram correspond to the levels o f code appropriate for the corresponding optim izations. Other orders are possible, and the exam ples o f real-world compilers in Chapter 21 present several alternatives, though none o f them includes all o f the optim iza tions in this diagram. Order o f Optimizations This flowchart represents a recommended order for performing optim izations in an aggres sive optimizing compiler.