Foreword by Susan Graham vii
Preface x
1 Introduction to Advanced Topics   1
  1.1    Review of Compiler Structure  1
  1.2    Advanced Issues in Elementary Topics  3
  1.3    The Importance of Code Optimization  6
  1.4    Structure of Optimizing Compilers  7
  1.5    Placement of Optimizations in Aggressive Optimizing Compilers  11
  1.6    Reading Flow Among the Chapters  14
  1.7    Related Topics Not Covered in This Text  16
  1.8    Target Machines Used in Examples  16
  1.9    Number Notations and Data Sizes  16
  1.10   Wrap-Up  17
  1.11   Further Reading  18
  1.12   Exercises  18
2  Informal Compiler Algorithm Notation (ICAN)   19
  2.1    Extended Backus-Naur Form Syntax Notation  19
  2.2    Introduction to ICAN  20
  2.3    A Quick Overview of ICAN  23
  2.4    Whole Programs  25
  2.5    Type Definitions 25
  2.6    Declarations  26
  2.7    Data Types and Expressions  27
  2.8    Statements  36
  2.9    Wrap-Up  41
  2.10   Further Reading  41
  2.11   Exercises  41
3  Symbol-Table Structure   43
  3.1    Storage Classes, Visibility, and Lifetimes  43
  3.2    Symbol Attributes and Symbol-Table Entries  45
  3.3    Local Symbol-Table Management  47
  3.4    Global Symbol-Table Structure  49
  3.5    Storage Binding and Symbolic Registers  54
  3.6    Approaches to Generating Loads and Stores  59
  3.7    Wrap-Up  64
  3.8    Further Reading  64
  3.9    Exercises  64
4  Intermediate Representations   67
  4.1    Issues in Designing an Intermediate Language  67
  4.2    High-Level Intermediate Languages  69
  4.3    Medium-Level Intermediate Languages  71
  4.4    Low-Level Intermediate Languages  71
  4.5    Multi-Level Intermediate Languages  72
  4.6    Our Intermediate Languages: MIR, HIR, and LIR  73
  4.7    Representing MIR, HIR, and LIR in ICAN  81
  4.8    ICAN Naming of Data Structures and Routines that Manipulate Intermediate Code  92
  4.9    Other Intermediate-Language Forms  96
  4.10   Wrap-Up  101
  4.11   Further Reading  102
  4.12   Exercises  102
5  Run-Time Support   105
  5.1    Data Representations and Instructions  106 
  5.2    Register Usage  109
  5.3    The,Local Stack Fr ame  111
  5.4    The Run-Time Stack  114
  5.5    Parameter-PassingDisciplines  116
  5.6    Procedure Prologues, Epilogues, Calls, and Returns  119
  5.7    Code Sharing and Position-Independent Code  127
  5.8    Symbolic and Polymorphic Language Support 131
  5.9    Wrap-Up  133
  5.10   Further Reading  134
  5.11   Exercises  135
6 Producing Code Generators Automatically   137
  6.1    Introduction to Automatic Generation of Code Generators  138
  6.2    A Syntax-Directed Technique  139
  6.3    Introduction to Semantics-Directed Parsing  159
  6.4    Tree Pattern Matching and Dynamic Programming  160
  6.5    Wrap-Up  165
  6.6    Further Reading  166
  6.7    Exercises  166
7 Control-Flow Analysis   169
  7.1    Approaches to Control-Flow Analysis  172
  7.2    Depth-First Search, Preorder Traversal, Postorder Traversal, and Breadth-First Search  177
  7.3    Dominators and Postdominators  181
  7.4    Loops and Strongly Connected Components  191
  7.5    Reducibility  196
  7.6    Interval Analysis and Control Trees 197
  7.7    Structural Analysis  202
  7.8    Wrap-Up  214
  7.9    Further Reading  214
  7.10   Exercises  215
8  Data-Flow Analysis   217
  8.1    An Example: Reaching Definitions  218
  8.2    Basic Concepts: Lattices, Flow Functions, and Fixed Points  223
  8.3    Taxonomy of Data-Flow Problems and Solution Methods  228
  8.4    Iterative Data-Flow Analysis  231
  8.5    Lattices of Flow Functions  235
  8.6    Control-Tree-Based Data-Flow Analysis  236
  8.7    Structural Analysis  236
  8.8    Interval Analysis  249
  8.9    Other Approaches  250
  8.10   Du-Chains, Ud-Chains, and Webs  251
  8.11   Static Single-Assignment (SSA) Form  252
  8.12   Dealing with Arrays, Structures, and Pointers  258
  8.13   Automating Construction of Data-Flow Analyzers  259
  8.14   More Ambitious Analyses  261
  8.15   Wrap-Up  263
  8.16   Further Reading  264
  8.17   Exercises  265
9 Dependence Analysis and Dependence Graphs   267
  9.1    Dependence Relations  267
  9.2    Basic-Block Dependence DAGs  269
  9.3    Dependences in Loops  274
  9.4    Dependence Testing  279
  9.5    Program-Dependence Graphs  284
  9.6    Dependences Between Dynamically Allocated Objects  286
  9.7    Wrap-Up  288
  9.8    Further Reading  289
  9.9    Exercises  290
10 Alias Analysis   293
  10.1   Aliases in Various Real Programming Languages  297
  10.2   The Alias Gatherer  302
  10.3   The Alias Propagator  307
  10.4   Wrap-Up  314
  10.5   Further Reading  315
  10.6   Exercises  316
11  Introduction to Optimization   319
  11.1   Global Optimizations Discussed in Chapters 12 Through 18  321
  11.2   Flow Sensitivity and May vs. Must Information 323
  11.3   Importance of Individual Optimizations  323
  11.4   Order and Repetition of Optimizatious  325
  11.5   Further Reading  328
  11.6   Exercises  328
12  Early Optimizations   329
  12.1   Constant-Expression Evaluation (Constant Folding)  329
  12.2   Scalar Replacement of Aggregates  331
  12.3   Algebraic Simplifications and Reassociation  333
  12.4   Value Numbering  343
  12.5   Copy Propagation  356
  12.6   Sparse Conditional Constant Propagation  362
  12.7   Wrap-Up  371
  12.8   Further Reading  373
  12.9   Exercises  374
13 Redundancy Elimination   377
  13.1   Common-Subexpression Elimination  378
  13.2   Loop-Invariant Code Motion  397
  13.3   Partial-Redundancy Elimination  407
  13.4   Redundancy Elimination and Reassociation  415
  13.5   Code Hoisting  417
  13.6   Wrap-Up  420
  13.7   Further Reading  422
  13.8   Exercises  422
14 Loop Optimizations   425
  14.1   Induction-Variable Optimizations  425
  14.2   Unnecessary Bounds-Checking Elimination  454
  14.3   Wrap-Up  457
  14.4   Further Reading  459
  14.5   Exercises  460
15 Procedure Optimizations   461
  15.1   Tail-Call Optimization and Tail-Recursion Elimination  461
  15.2   Procedure Integration  465
  15.3   In-Line Expansion  470
  15.4   Leaf-Routine Optimization and Shrink Wrapping  472
  15.5   Wrap-Up  476
  15.6   Further Reading  478
  15.7   Exercises  478
16 Register Allocation   481
  16.1   Register Allocation and Assignment  482
  16.2   Local Methods  483
  16.3   Graph Coloring  485
  16.4   Priority-Based Graph Coloring  524
  16.5   Other Approaches to Register Allocation  525
  16.6   Wrap-Up  526
  16.7   Further Reading  528
  16.8   Exercises  529
17 Code Scheduling   531
  17.1   Instruction Scheduling  532
  17.2   Speculative Loads and Boosting  547
  17.3   Speculative Scheduling  548
  17.4   Software Pipelining  548
  17.5   Trace Scheduling  569
  17.6   Percolation Scheduling  571
  17.7   Wrap-Up  573
  17.8   Further Reading  575
  17.9   Exercises  576
18 Control-Flow and Low-Level Optimizations   579
  18.1   Unreachable-Code Elimination  580
  18.2   Straightening  583
  18.3   If Simplifications  585
  18.4   Loop Simplifications  586
  18.5   Loop Inversion  587
  18.6   Unswitching  588
  18.7   Branch Optimizations  589
  18.8   Tail Merging or Cross Jumping  590
  18.9   Conditional Moves  591
  18.10  Dead-Code Elimination  592
  18.11  Branch Prediction  597
  18.12 Machine Idioms and Instruction Combining  599
  18.13  Wrap-Up  602
  18.14  Further Reading  604
  18.15  Exercises  605
19 Interprocedural Analysis and Optimization   607
  19.1   Interprocedural Control-Flow Analysis: The Call Graph  609
  19.2   Interprocedural Data-Flow Analysis  619
  19.3   Interprocedural Constant Propagation  637
  19.4   Interprocedural Alias Analysis  641
  19.5   Interprocedural Optimizations  656
  19.6   Interprocedural Register Allocation  659
  19.7   Aggregation of Global References  663
  19.8   Other Issues in Interprocedural Program Management  663
  19.9   Wrap-Up  664
  19.10 Further Reading  666
  19.11  Exercises  667
20 Optimization for the Memory Hierarchy   669
  20.1   Impact of Data and Instruction Caches  670
  20.2   Instruction-Cache Optimization  672
  20.3   Scalar Replacement of Array Elements  682
  20.4   Data-Cache Optimization  687
  20.5   Scalar vs. Memory-Oriented Optimizations  700
  20.6   Wrap-Up  700
  20.7   Further Reading  703
  20.8   Exercises  704
21 Case Studies of Compilers and Future Trends   105
  21.1   The Sun Compilers for SPARC  707
  21.2   The IBM XL Compilers for the POWER and PowerPC Architectures  716
  21.3   Digital Equipment's Compilers for Alpha  726
  21.4   The Intel Reference Compilers for the Intel 386 Architecture Family  734
  21.5   Wrap-Up  744
  21.6   Future Trends in Compiler Design and Implementation  745
  21.7   Further Reading  746
App.A Guide to Assembly Languages Used in This Book   747
  A.1    Sun SPARC Versions 8 and 9 Assembly Language  747
  A.2   IBM POWER and PowerPC Assembly Language  749
  A.3   DEC Alpha Assembly Language  750
  A.4   Intel 386 Architecture Assembly Language  752
  A.5   Hewlett-Packard's PA~RISC Assembly Language  753
App.B Representation of Sets, Sequences, Trees, DAGs, and Functions   757
  B.1    Representation of Sets  759
  B.2    Representation of Sequences  763
  B.3    Representation of Trees and DAGs  763
  B.4    Representation of Functions  764
  B.5    Further Reading  765
App.C Software Resources   767
  C.1   Finding and Accessing Software on the Intemet  767
  C.2   Machine Simulators  767
  C.3   Compilers  768
  C.4   Code-Generator Generators: BURG and IBURG  769
  C.5   Profiling Tools  770
  List of Illustrations  773
  List of Tables  797
  Bibliography  801
  Technical Index of Mathematical Formulas and ICAN Procedures and Major Data Structures  821
  Subject Index  827