本书是经典的编译器著作，与”龙书”齐名。书中针对现代语言和体系结构全面介绍了编译器设计与实现的高级论题，从编译器的基础领域中的高级问题开始，然后深入讨论了各种重要的代码优化。本书专为编译器专业人士和计、算机专业本科生、研究生编写，在设计和实现高度优化的编译器以及确定优化的重要性和实现优化的最有效的方法等方面，为读者提供了非常有价值的指导。
本书的主要特点：
为理解高级编译器设计的主要问题奠定了基础。
深入阐述了优化问题。
使用四个商业编译器(包括Sun的SPARC，IBM的POWER和PowerPC。DEC的Alpha以及Intel的Pentium 和相关处理器上的编译器)的实例分析说明了编译器结构。中间代码设计和优化的各种方法。
给出了大量的定义明确的代码生成。优化和其他方面的算法。用Informal Compiler Algorthm Notation(ICAN)(一种由作者设计的语言)来以清晰。
简洁的方式表达算法。
This book concerns advanced issues in the design and implementation of compilers, for uniprocessors, with its major emphasis (over 60% of the text) on optimization. While it does consider machines with instruction-level parallelism, we ignore almost completely the issues of large-scale parallelization and vectorization.
It begins with material on compiler structure, symbol-table management (includ-ing languages that allow scopes to be imported and exported), intermediate code structure, run-time support issues (including shared objects that can be linked to at run time), and automatic generation of code generators from machine descrip- tions. Next it explores methods for intraprocedural (conventionally called global)control-flow, data-flow, dependence, and alias analyses. Then a series of groups of global optimizations are described, including ones that apply to program compo-nents from simple expressions to whole procedures. Next, interprocedural analyses of control flow, data flow, and aliases are described, followed by interprocedural optimizations and use of interprocedural information to improve global optimiza-tions. We then discuss optimizations designed to make effective use of the memory hierarchy. Finally, we describe four commercial compiler systems in detail, namely,ones from Digital Equipment Corporation, IBM, Intel, and Sun Microsysytems, to provide specific examples of approaches to compiler structure, intermediate-code de-sign, optimization choices, and effectiveness. As we shall see, these compiler systems represent a wide range of approaches and often achieve similar results in different ways.
How This Book Came to Be Written
In June 1990 and 1991, while a Distinguished Engineer at Sun Microsystems,I presented a half-day tutorial entitled "Advanced Compiling Techniques for aisc Systems" at the annual ACM SlGPLAN Conference on Programming Language De-sign and Implementation. The tutorial was based on approximately 130 transparen-cies on aisc architectures and relevant issues in compilers, particularly optimization.
I left that experience with the idea that somewhere within the material covered there was a seed (the mental image was, in fact, of an acorn) yearning for sun, soil, and water to help it grow into the mature oak tree of a book you have before you. Over a year later I discussed this idea with Wayne Rosing, then President of Sun Microsys-tems Laboratories, and within a few weeks he decided to nurture this project with a year-and-a-half's worth of partial funding.
The first draft that resulted included quite a lot of material on Risc architectures,as well as material on advanced compilation issues. Before long (with the help of three reviewers) I had decided that there was little point in including the architecture material in the book. New Risc architectures are being developed quite frequently,the kind of coverage of them that is needed is provided in architecture courses at most universities, and the real strengths of the text were in the compiler material.
This resulted in a major change of direction. Most of the architecture material was dropped, keeping just those parts that support decisions on how to proceed in compilation; the focus of the compiler material was broadened to provide equal coverage of ciscs; and it was decided to focus entirely on uniprocessors and to leave it to other texts to discuss parallelization and vectorization. The focus of the compilation material was deepened and, in some respects narrowed and in others broadened (for example, material on hand-crafted code generation was dropped almost entirely, while advanced methods of scheduling, such as trace and percolation scheduling, were added). The result is what you see before you.
About the Cover
The design on the cover is of a Chilkat blanket from the author's collection of Northwest Coast native art. The blanket was woven of fine strands of red-cedar inner bark and mountain-goat wool in the late 19th century by a Tlingit woman from southeastern Alaska. It generally took six to nine months of work to complete such a blanket. The blanket design is divided into three panels, and the center panel depicts a diving whale. The head is the split image at the bottom; the body is the panel with the face in the center (a panel that looks like a face never represents the face in this iconography); the lateral fins are at the sides of the body; and the tail flukes are at the top. Each part of the design is, in itself, functional but meaningless;assembled together in the right way, the elements combine to depict a diving whale and proclaim the rights and prerogatives of the village chief who owned the blanket.
In a similar way, each component of a compiler is functional, but it is only when the components are put together in the proper way that they serve their overall purpose. Designing and weaving such a blanket requires skills that are akin to those involved in constructing industrial-strength compilers--each discipline has a set of required tools, materials, design elements, and overall patterns that must be combined in a way that meets the prospective users' needs and desires.
Audience for This Book
This book is intended for computer professionals, graduate students, and advanced undergraduates who need to understand the issues involved in designing and con-structing advanced compilers for uniprocessors. The reader is assumed to have had introductory courses in data structures, algorithms, compiler design and implemen-tation, computer architecture, and assembly-language programming, or equivalent work experience.
Overview of the Book's Contents
This volume is divided into 21 chapters and three appendices as follows:
Chapter 1. Introduction to Advanced Topics This chapter introduces the subject of the book, namely, advanced topics in the de-sign and construction of compilers, and discusses compiler structure, the importance of optimization, and how the rest of the material in the book works together.
Chapter 2. Informal Compiler Algorithm Notation (ICAN)
Chapter 2 describes and gives examples of an informal programming notation called ICAN that is used to present algorithms in the text. After describing the notation used to express the language's syntax, it gives a brief overview of ICAN, followed by a detailed description of the language. The brief description should be sufficient for reading most of the algorithms presented and the full description should need to be referred to only rarely.
Chapter 3. Symbol-Table Structure
Chapter 3 first discusses the attributes of variables, such as storage class, visibility,volatility, scope, size, type, alignment, structure, addressing method, and so on.Then it describes effective methods for structuring and managing local and global symbol tables, including importation and exportation of scopes (as found, e.g., in Ada, Mesa, and Modula-2); storage binding; and approaches to generating load and store instructions that take the above characteristics into account.
Chapter 4. Intermediate Representations
This chapter focuses on intermediate language design, three specific intermediate lan-guages used in the remainder of the book, and other basic forms of intermediate code that might be used in a compiler. We use three closely related intermediate forms,one high-level, one medium-level, and one low-level, to allow us to demonstrate vir-tually all the optimizations discussed. We also discuss the relative importance and usefulness of our chosen forms and the others.
Two other more elaborate forms of intermediate code, namely, static single-assignment (SSA) form and program dependence graphs, are discussed in Sec-tions 8.11 and 9.5, respectively.
Chapter 5. Run-Time Support
Chapter 5 concerns the issues involved in supporting programs written in high-level languages at run time. It discusses data representation, register usage, design of the stack frame and overall run-time stack, parameter passing, procedure structure and linkage, procedure-valued variables, code sharing, position-independent code, and issues involved in supporting symbolic and polymorphic languages.
Chapter 6. Producing Code Generators Automatically
Chapter 6 discusses automatic approaches for producing code generators from ma-chine descriptions. We present the Graham-Glanville syntax-directed technique in detail and introduce two other approaches, namely, semantics-directed parsing and tree pattern matching.
Chapter 7. Control-Flow Analysis
This and the following three chapters discuss four types of analyses that apply to procedures and that are vital to doing correct and ambitious optimization.
Chapter 7 concentrates on approaches to determining the control flow within a procedure and to constructing a control-flow graph (CFG). It begins with an overview of the possible approaches and then discusses three of them in detail. The first is the classic approach of using depth-first search and dominators. In this area we also discuss flowgraph traversals, such as preorder and postorder, of the CFG and finding the strongly connected components of a CFG. The other two approaches depend on the concept of reducibility, which allows the control flow of a procedure to be composed hierarchically. One of the two is called interval analysis and the other is called structural analysis, and the two differ in ,what types of structural units they
distinguish. We also discuss the representation of a procedure's hierarchical structure by a so-called control tree.
Chapter 8. Data-Flow Analysis
Chapter 8 discusses approaches to determining the flow of data in a procedure. It begins with an example and next discusses the basic mathematical concepts un-derlying data-flow analysis, namely, lattices, flow functions, and fixed points. It continues with a taxonomy of data-flow problems and solution methods and then proceeds to discuss in detail three techniques for solving data-flow problems that correspond to the three approaches to control-flow analysis presented in the preced-ing chapter. The first approach is iterative data-flow analysis, which corresponds to
the use of depth-first search and dominators. The other two approaches correspond to the control-tree-based approaches to control-flow analysis and are known by the same names as those analyses: interval analysis and structural analysis. This is fol-lowed by an overview of a new sparse technique known as slotwise analysis, and descriptions of methods of representing data-flow information, namely, du-chains,ud-chains, webs, and static single-assignment (or SSA) form. The chapter concludes with thoughts on how to deal with arrays, structures, and pointers and with a dis-cussion of a method for automating construction of data-flow analyzers.
Chapter 9. Dependence Analysis and Dependence Graphs
Chapter 9 concerns dependence analysis, which is a poor-man's version of data-flow analysis for arrays and low-level storage references, and a closely related intermedi-ate code form known as the program dependence graph. It first discusses dependence relations and then how to compute dependence relations within a basic block, which is vital to the code-scheduling techniques discussed in Chapter 17. Next it discusses dependence in loops and methods of doing dependence testing, which are essential to the data-storage optimizations discussed in Chapter 20. Finally, it discusses the pro-gram dependence graph, which is an intermediate-code form that represents control and data dependences directly, and that can be used to perform a series of optimiza-
tions more effectively than on an intermediate code that leaves such information implicit.
Chapter 10. Alias Analysis
Chapter 10 discusses alias analysis, which determines whether a storage location may be accessible by more than one access path, such as by name and through a pointer. It discusses how aliases may impact programs in specific languages, such as Fortran 77, Pascal, C, and Fortran 90. Next it discusses a very general approach to determining the aliases present in a procedure that consists of a language-specific alias gatherer and a language-independent alias propagator. The alias gatherer and propagator can be tailored to provide information that depends or not on the control flow of the procedure and that also provides information in a variety of other ways,making it a general approach that can be suited to the needs and time constraints of a particular programming language and compiler.
Chapter 11. Introduction to Optimization
Chapter 11 introduces the subject of code optimization, discusses the fact that the applicability and effectiveness of most optimizations are recursively undecidable but still worthwhile for programs for which they are determinable, and provides a quick survey of the intraprocedural optimizations covered in Chapters 12 through 18. It then discusses flow sensitivity and may vs. must information and how they apply to optimization, the relative importance of particular optimizations, and the order in which they should be performed.
Chapter 12. Early Optimizations
Chapter 12 discusses optimizations that are usually performed early in the opti-mization process, namely, scalar replacement of aggregates, local and global value numbering (performed on SSA-form code), local and global copy propagation, and sparse conditional constant propagation (also performed on SSA-form code). It also discusses constant expression evaluation (or constant folding) and algebraic simpli-fication and how they are best included in an optimizer as subroutines that can be called from wherever they are needed.
Chapter 13. Redundancy Elimination
Chapter 13 concerns several types of redundancy elimination, which, in essence,delete computations that are performed more than once on a path through a pro-cedure. It describes local and global common-subexpression elimination, forward substitution, loop-invariant code motion, partial-redundancy elimination, and code hoisting.
Chapter 14. Loop Optimizations
Chapter 14 deals with optimizations that apply to loops, including identificanon of induction variables, strength reduction, removal of mduction variables, linear- function test replacement, elimination of unnecessary bounds checking.
Chapter 15. Procedure Optimizations
Chapter 15 presents optimizations that apply to procedures as units of code. It discusses tail-call optimization (including tail-recursion elimination), procedure in-tegration, in-line expansion, leaf-routine optimization, and shrink wrapping.
Chapter 16. Register Allocation
Chapter 16 concerns intraprocedural register allocation and assignment. First it discusses local, cost-based methods and then an approach that uses graph coloring.
We discuss webs as the allocatable objects, the interference graph, coloring the interference graph, and generating spill code. This is followed by a brief presentation of approaches to register allocation that use a procedure's control tree.
Chapter 17. Code Scheduling
Chapter 17 concerns local and global instruction scheduling, which reorders instruc-tions to take best advantage of the pipelines built into modern processors. There are two issues in local scheduling, namely, list scheduling, which deals with the sequence of instructions within a basic block, and branch scheduling, which deals with connections between blocks. We next consider approaches to scheduling across basic-block boundaries, including speculative loads and boosting. Next we discuss two approaches to software pipelining, called window scheduling and unroll and compact. Next we discuss loop unrolling, variable expansion, and register renaming,all of which increase the freedom available to scheduling, and hierarchical reduc-tion, which deals with control structures embedded in loops. We finish the chapter with two global approaches to scheduling, namely, trace scheduling and percolation scheduling.
Chapter 18. Control-Flow and Low-Level 0ptimizations
Chapter 18 deals with control-flow optimizations and ones that are generally per-formed on a low-level form of intermediate code or on an assembly-language-like representation. These include unreachable-code elimination,, straightening, if sim-plification, loop simplifications, loop inversion, unswitching, branch optimizations,tail merging (also called cross jumping), use of conditional move instructions, dead-code elimination, in-line expansion, branch prediction, machine idioms, instruction combining, and register coalescing or subsumption.
Chapter 19. Interprocedural Analysis and Optimization
Chapter 19 concerns extending analysis and optimization to deal with whole pro-grams. It discusses interprocedural control-flow analysis, data-flow analysis, alias analysis, and transformations. It presents two approaches each to flow-insensitive side effect and alias analysis, along with approaches to computing flow-sensitive side effects and doing interprocedural constant propagation. Next it discusses inter-procedural optimizations and applying interprocedural information to optimization within procedures, followed by interprocedural register allocation and aggregation of global references. It concludes with a discussion of how to integrate interproce-dural analysis and optimization into the order of optimizations.
Chapter 20. Optimization for the Memory Hierarchy
Chapter 20 discusses optimization to take better advantage of the memory hierar-chy found in most systems and specifically of cache memories. We first discuss the impact of data and instruction caches on program performance. We next consider instruction-cache optimization, including instruction prefetching, procedure sorting, procedure and block placement, intraprocedural code positioning, procedure split- ting, and combining intra- and interprocedural methods.
Next we discuss data-cache optimization, focusing mostly on loop transforma- tions. Rather than providing a full treatment of this topic, we cover some parts of it in detail, such as scalar replacement of array elements and data prefetching, and for others give only an outline of the definitions, terminology, and techniques, and issues involved and examples of the techniques. The latter topics include data reuse, locality, tiling, and the interaction of scalar and memory-oriented optimizations. We take this approach because the research on this subject is still too new to warrant selection of a definitive method.
Chapter 21. Case Studies of Compilers and Future Trends
Chapter 21 presents four case studies of commercial compiling systems that include a wide range of target architectures, compiler designs, intermediate-code representa- tions, and optimizations. The four architectures are Sun Microsystems' SPARC, IBM's VOWER (and PowerPC), the Digital Equipment Alpha, and the Intel 386 family. For each, we first discuss the architecture briefly and then present the hardware vendor's compilers for it.
Appendix A. Guide to Assembly Languages .Used in This Book
Appendix A presents a short description of each of the assembly languages used in the text, so as to make the code examples more easily accessible. This includes discussion of the SPARC, POWER (and PowerPC), Alpha, Intel 386 architecture family,and PA-RISC assembly languages.
Appendix B. Representation of Sets, Sequences, Trees, DAGs, and Functions
Appendix B provides a quick review of concrete representations for most of the ab-stract data structures in the text. It is not a substitute for a course in data structures,but a ready reference to some of the issues and approaches.
Appendix C. Software Resources
Appendix C is concerned with software accessible via anonymous FTP or on the World Wide Web that can be used as a basis for compiler implementation projects in the classroom and, in some cases, in industrial settings also.
Bibliography
Finally, the bibliography presents a wide range of sources for further reading in the topics covered in the text.
Indexes
The book ends with two indexes, one of which lists mathematical formulas, ICAN functions, and major ICAN data structures.
Supplements, Resources, and Web Extensions Several exercises appear at the end of each chapter. Advanced exercises are marked ADV in the left margin, and research exercises are marked RSCH. Solu-tions for selected exercises are available electronically from the publisher. Book-related materials can be found on the World Wide Web at the URL for this book
http://www.mkp.com/books_catalog/1-55860-320-4.asp. Instructors should contact the publisher directly to obtain solutions to exercises.
Resources
Appendix C, as described above, concerns free software designed for student compiler-construction projects and how to obtain it electronically. The entire ap-pendix, with links to these addresses, can be accessed at the URL listed above.
Web Extension
Additional material concerned with object-code translation, an approach to produc-ing machine code for an architecture from code for another architecture, rather than from source code, is available from the publisher's World Wide Web site, at the URL listed above. The Web Extension discusses the principles of object-code compilation and then focuses on three examples, Hewlett-Packard's HP3000--tO--PA-RISC transla-tor OCT and Digital Equipment Corporation's VAX VMS-to-Alpha translator VEST and its MIPS-to-Alpha translator mx.
Acknowledgments
First and foremost, I would like to thank my former colleagues at Sun Microsystems without whose support and encouragement this book would not have been possible.Chief among them are Peter Deutsch, Dave Ditzel, Jon Kannegaard, Wayne Rosing,Eric Schmidt, Bob Sproull, Bert Sutherland, Ivan Sutherland, and the members of the Programming Languages departments, particularly Sharokh Mortazavi, PeterDamron, and Vinod Grover. I particularly thank Wayne Rosing for the faith to fund my time working on the book for its first one and a half years.
Second, I would like to thank the reviewers, all of whom have provided valuable comments on drafts of the book, namely, J. Randy Allen, Bill Appelbe,Preston Briggs, Fabian E. Bustamante, Siddhartha Chatterjee, Bob Colwell,Subhendu Raja Das, Amer Diwan, Krishna Kunchithapadam, Jim Larus, Ion Mandoiu, Allan Porterfield, Arch Robison, Francisco J. Torres-Rojas, and Michael Wolfe.
I am also indebted to colleagues in other companies and Organizations who have shared information about their compilers and other technical topics, whether they appear directly in the book or not, namely, Michael Tiemann, James Wilson,and Torbjorn Granlund of Cygnus Support; Richard Grove, Neil Faiman, Maurice Marks, and Anton Chernoff of Digital Equipment; Craig Franklin of Green Hills Software; Keith Keilman, Michael Mahon, James Miller, and Carol Thompson of Hewlett-Packard; Robert Colwell, Suresh Rao, William Savage, and Kevin J. Smith of Intel; Bill Hay, Kevin O'Brien, and F. Kenneth Zadeck of International Business Machines; Fred Chow, John Mashey, and Alex Wu of MIPS Technologies; Andrew Johnson of the Open Software Foundation; Keith Cooper and his colleagues at Rice University; John Hennessy, Monica Lam, and their colleagues at Stanford University;and Nic Peeling 9f the UK Defense Research Agency.
I am particularly indebted to my parents, Samuel and Dorothy Muchnick, who created a homelife for me that was filled with possibilities, that encouraged me to ask and to try to answer hard questions, and that stimulated an appreciation for the beauty to be found in both the gifts of simplicity and in complexity, be it natural or made by the hand of man.
The staff at Morgan Kaufmann have shepherded this project through the stages of the publishing process with skill and aplomb. They include Bruce Spatz, Doug Sery, Jennifer Mann, Denise Penrose, Yonie Overton, Cheri Palmer, Jane Elliott, and Lisa Schneider. I thank them all and look forward to working with them again.
The compositor, Paul Anagnostopoulos of Windfall Software, designed the spe-cial symbols used in ICAN and did a thorough and knowledgeable job of typesetting the book. He made my day one morning when he sent me email saying that he looked forward to reading the product of our joint labor.
Last, but by no means least, I would like to thank my long-time lover, Eric Milliren, for putting up with my spending so much time writing this book during the last five years, for providing a nourishing home life for me, and for deferring several of his own major projects until completion of the book was in sight.
(美)Steven S.Muchnick：Steven S.Muchnick: Steven S．Muchnick具有丰富而广博的经验。他曾经是计算机科学教授，‘后来他将自己的知识和经验应用于编译器设计，成为两种计算机体系结构(惠普的PA-RISC和Sun的SPARC)开发团队的核心成员，并担任这些系统的高级编译器设计与实现的领导人。他的研究和开发经验对于指导读者做出编译器设计决策极具价值。
Foreword by Susan Graham vii
Preface x
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 Frame 111
5.4 The Run-Time Stack 114
5.5 Parameter-Passing Disciplines 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
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
