Cooper_Engineering_a_Compiler(Second Edition) (1157546), страница 6
Текст из файла (страница 6)
. .13.4.2 Estimating Global Spill Costs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13.4.3 Interferences and the Interference Graph . . . . . . . . . . . . . . . . . . .13.4.4 Top-Down Coloring . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .13.4.5 Bottom-Up Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13.4.6 Coalescing Copies to Reduce Degree . . . . . . . . . . . . . . . . . . . . . . .13.4.7 Comparing Top-Down and Bottom-UpGlobal Allocators . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13.4.8 Encoding Machine Constraints in theInterference Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13.5 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .13.5.1 Variations on Graph-Coloring Allocation . . . . . . . . . . . . . . . . . .13.5.2 Global Register Allocation over SSA Form . . . . . . . . . . . . . . . .13.6 Summary and Perspective . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .686689693696697699702704706708711713713717718719720APPENDIX A ILOC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725A.1 Introduction . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .A.2 Naming Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .A.3 Individual Operations . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .A.3.1 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .A.3.2 Shifts . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .A.3.3 Memory Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .A.3.4 Register-to-Register Copy Operations . . . . . . . . . . . . . .
. . . . . . . . . .A.4 Control-Flow Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .A.4.1 Alternate Comparison and Branch Syntax . . . . . . . . . . . . . . . . . . .A.4.2 Jumps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .A.5 Representing SSA Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .725727728728729729730731732732733APPENDIX B Data Structures . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737B.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .B.2 Representing Sets . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .B.2.1 Representing Sets as Ordered Lists . . . . . . . . . . . . . . . . . . . . . . . . . . .B.2.2 Representing Sets as Bit Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .B.2.3 Representing Sparse Sets . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .B.3 Implementing Intermediate Representations . . . . . . . . . . . . . . . . . . . . . . . . .B.3.1 Graphical Intermediate Representations . . . . . . . . . . . . . .
. . . . . . . .B.3.2 Linear Intermediate Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .737738739741741743743748xviii ContentsB.4 Implementing Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .B.4.1 Choosing a Hash Function . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .B.4.2 Open Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .B.4.3 Open Addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .B.4.4 Storing Symbol Records . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .B.4.5 Adding Nested Lexical Scopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .B.5 A Flexible Symbol-Table Design . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .750750752754756757760BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765INDEX . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787Preface to the Second EditionThe practice of compiler construction changes continually, in part because the designs ofprocessors and systems change. For example, when we began to write Engineering a Compiler (eac) in 1998, some of our colleagues questioned the wisdom of including a chapter oninstruction scheduling because out-of-order execution threatened to make scheduling largelyirrelevant. Today, as the second edition goes to press, the rise of multicore processors and thepush for more cores has made in-order execution pipelines attractive again because their smallerfootprints allow the designer to place more cores on a chip.
Instruction scheduling will remainimportant for the near-term future.At the same time, the compiler construction community continues to develop new insights andalgorithms, and to rediscover older techniques that were effective but largely forgotten. Recentresearch has created excitement surrounding the use of chordal graphs in register allocation(see Section 13.5.2). That work promises to simplify some aspects of graph-coloring allocators.Brzozowski’s algorithm is a dfa minimization technique that dates to the early 1960s but hasnot been taught in compiler courses for decades (see Section 2.6.2). It provides an easy pathfrom an implementation of the subset construction to one that minimizes dfas.
A modern coursein compiler construction might include both of these ideas.How, then, are we to structure a curriculum in compiler construction so that it prepares studentsto enter this ever changing field? We believe that the course should provide each student withthe set of base skills that they will need to build new compiler components and to modifyexisting ones. Students need to understand both sweeping concepts, such as the collaborationbetween the compiler, linker, loader, and operating system embodied in a linkage convention,and minute detail, such as how the compiler writer might reduce the aggregate code space usedby the register-save code at each procedure call.nCHANGES IN THE SECOND EDITIONThe second edition of Engineering a Compiler (eac2e) presents both perspectives: big-pictureviews of the problems in compiler construction and detailed discussions of algorithmic alternatives.
In preparing eac2e, we focused on the usability of the book, both as a textbook and as areference for professionals. Specifically, wennImproved the flow of ideas to help the student who reads the book sequentially. Chapterintroductions explain the purpose of the chapter, lay out the major concepts, and provide ahigh-level overview of the chapter’s subject matter. Examples have been reworked toprovide continuity across chapters. In addition, each chapter begins with a summary and aset of keywords to aid the user who treats eac2e as a reference book.Added section reviews and review questions at the end of each major section. The reviewquestions provide a quick check as to whether or not the reader has understood the majorpoints of the section.xixxx Preface to the Second EditionnnMoved definitions of key terms into the margin adjacent to the paragraph where they arefirst defined and discussed.Revised the material on optimization extensively so that it provides broader coverage ofthe possibilities for an optimizing compiler.Compiler development today focuses on optimization and on code generation.
A newly hiredcompiler writer is far more likely to port a code generator to a new processor or modify an optimization pass than to write a scanner or parser. The successful compiler writer must be familiarwith current best-practice techniques in optimization, such as the construction of static singleassignment form, and in code generation, such as software pipelining. They must also have thebackground and insight to understand new techniques as they appear during the coming years.Finally, they must understand the techniques of scanning, parsing, and semantic elaborationwell enough to build or modify a front end.Our goal for eac2e has been to create a text and a course that exposes students to the criticalissues in modern compilers and provides them with the background to tackle those problems.We have retained, from the first edition, the basic balance of material.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
