Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 7

Front ends are commoditycomponents; they can be purchased from a reliable vendor or adapted from one of the manyopen-source systems. At the same time, optimizers and code generators are custom-craftedfor particular processors and, sometimes, for individual models, because performance relies soheavily on specific low-level details of the generated code. These facts affect the way that webuild compilers today; they should also affect the way that we teach compiler construction.nORGANIZATIONeac2e divides the material into four roughly equal pieces:nnnnnThe first major section, Chapters 2 through 4, covers both the design of a compiler frontend and the design and construction of tools to build front ends.The second major section, Chapters 5 through 7, explores the mapping of source-code intothe compiler’s intermediate form—that is, these chapters examine the kind of code that thefront end generates for the optimizer and back end.The third major section, Chapters 8 through 10, introduces the subject of codeoptimization.

Chapter 8 provides an overview of optimization. Chapters 9 and 10 containdeeper treatments of analysis and transformation; these two chapters are often omittedfrom an undergraduate course.The final section, Chapters 11 through 13, focuses on algorithms used in the compiler’sback end.THE ART AND SCIENCE OF COMPILATIONThe lore of compiler construction includes both amazing success stories about the application oftheory to practice and humbling stories about the limits of what we can do. On the success side,modern scanners are built by applying the theory of regular languages to automatic constructionof recognizers.

lr parsers use the same techniques to perform the handle-recognition that drivesPreface to the Second Edition xxia shift-reduce parser. Data-flow analysis applies lattice theory to the analysis of programs inclever and useful ways. The approximation algorithms used in code generation produce goodsolutions to many instances of truly hard problems.On the other side, compiler construction exposes complex problems that defy good solutions.The back end of a compiler for a modern processor approximates the solution to two or moreinteracting np-complete problems (instruction scheduling, register allocation, and, perhaps,instruction and data placement). These np-complete problems, however, look easy next to problems such as algebraic reassociation of expressions (see, for example, Figure 7.1).

This problemadmits a huge number of solutions; to make matters worse, the desired solution depends on context in both the compiler and the application code. As the compiler approximates the solutionsto such problems, it faces constraints on compile time and available memory. A good compilerartfully blends theory, practical knowledge, engineering, and experience.Open up a modern optimizing compiler and you will find a wide variety of techniques.

Compilers use greedy heuristic searches that explore large solution spaces and deterministic finiteautomata that recognize words in the input. They employ fixed-point algorithms to reasonabout program behavior and simple theorem provers and algebraic simplifiers to predict thevalues of expressions. Compilers take advantage of fast pattern-matching algorithms to mapabstract computations to machine-level operations. They use linear diophantine equationsand Pressburger arithmetic to analyze array subscripts.

Finally, compilers use a large set ofclassic algorithms and data structures such as hash tables, graph algorithms, and sparse setimplementations.In eac2e, we have tried to convey both the art and the science of compiler construction. Thebook includes a sufficiently broad selection of material to show the reader that real tradeoffsexist and that the impact of design decisions can be both subtle and far-reaching. At the sametime, eac2e omits some techniques that have long been part of an undergraduate compilerconstruction course, but have been rendered less important by changes in the marketplace, inthe technology of languages and compilers, or in the availability of tools.nAPPROACHCompiler construction is an exercise in engineering design.

The compiler writer must choosea path through a design space that is filled with diverse alternatives, each with distinct costs,advantages, and complexity. Each decision has an impact on the resulting compiler. The qualityof the end product depends on informed decisions at each step along the way.Thus, there is no single right answer for many of the design decisions in a compiler. Evenwithin “well understood” and “solved” problems, nuances in design and implementation havean impact on both the behavior of the compiler and the quality of the code that it produces.Many considerations play into each decision.

As an example, the choice of an intermediaterepresentation for the compiler has a profound impact on the rest of the compiler, from timeand space requirements through the ease with which different algorithms can be applied. Thedecision, however, is often given short shrift. Chapter 5 examines the space of intermediatexxii Preface to the Second Editionrepresentations and some of the issues that should be considered in selecting one. We raise theissue again at several points in the book—both directly in the text and indirectly in the exercises.eac2e explores the design space and conveys both the depth of the problems and the breadthof the possible solutions.

It shows some ways that those problems have been solved, along withthe constraints that made those solutions attractive. Compiler writers need to understand boththe problems and their solutions, as well as the impact of those decisions on other facets of thecompiler’s design. Only then can they make informed and intelligent choices.nPHILOSOPHYThis text exposes our philosophy for building compilers, developed during more than twentyfive years each of research, teaching, and practice. For example, intermediate representationsshould expose those details that matter in the final code; this belief leads to a bias towardlow-level representations.

Values should reside in registers until the allocator discovers thatit cannot keep them there; this practice produces examples that use virtual registers and storevalues to memory only when it cannot be avoided. Every compiler should include optimization;it simplifies the rest of the compiler. Our experiences over the years have informed the selectionof material and its presentation.nA WORD ABOUT PROGRAMMING EXERCISESA class in compiler construction offers the opportunity to explore software design issues inthe context of a concrete application—one whose basic functions are well understood by anystudent with the background for a compiler construction course.

In most versions of this course,the programming exercises play a large role.We have taught this class in versions where the students build a simple compiler from start tofinish—beginning with a generated scanner and parser and ending with a code generator forsome simplified risc instruction set. We have taught this class in versions where the studentswrite programs that address well-contained individual problems, such as register allocation orinstruction scheduling. The choice of programming exercises depends heavily on the role thatthe course plays in the surrounding curriculum.In some schools, the compiler course serves as a capstone course for seniors, tying togetherconcepts from many other courses in a large, practical, design and implementation project.Students in such a class might write a complete compiler for a simple language or modify anopen-source compiler to add support for a new language feature or a new architectural feature.This class might present the material in a linear order that closely follows the text’s organization.In other schools, that capstone experience occurs in other courses or in other ways.

In sucha class, the teacher might focus the programming exercises more narrowly on algorithms andtheir implementation, using labs such as a local register allocator or a tree-height rebalancingpass. This course might skip around in the text and adjust the order of presentation to meet theneeds of the labs. For example, at Rice, we have often used a simple local register allocatorPreface to the Second Edition xxiiias the first lab; any student with assembly-language programming experience understands thebasics of the problem. That strategy, however, exposes the students to material from Chapter 13before they see Chapter 2.In either scenario, the course should draw material from other classes. Obvious connectionsexist to computer organization, assembly-language programming, operating systems, computerarchitecture, algorithms, and formal languages.

Although the connections from compiler construction to other courses may be less obvious, they are no less important. Character copying,as discussed in Chapter 7, plays a critical role in the performance of applications that includenetwork protocols, file servers, and web servers. The techniques developed in Chapter 2 forscanning have applications that range from text editing through url-filtering. The bottomup local register allocator in Chapter 13 is a cousin of the optimal offline page replacementalgorithm, min.nADDITIONAL MATERIALSAdditional resources are available that can help you adapt the material presented in eac2e toyour course.

These include a complete set of lectures from the authors’ version of the course atRice University and a set of solutions to the exercises. Your Elsevier representative can provideyou with access.AcknowledgmentsMany people were involved in the preparation of the first edition of eac. Their contributionshave carried forward into this second edition. Many people pointed out problems in the firstedition, including Amit Saha, Andrew Waters, Anna Youssefi, Ayal Zachs, Daniel Salce, DavidPeixotto, Fengmei Zhao, Greg Malecha, Hwansoo Han, Jason Eckhardt, Jeffrey Sandoval, JohnElliot, Kamal Sharma, Kim Hazelwood, Max Hailperin, Peter Froehlich, Ryan Stinnett, SachinRehki, Sağnak Taşırlar, Timothy Harvey, and Xipeng Shen. We also want to thank the reviewersof the second edition, who were Jeffery von Ronne, Carl Offner, David Orleans, K.

StuartSmith, John Mallozzi, Elizabeth White, and Paul C. Anagnostopoulos. The production teamat Elsevier, in particular, Alisa Andreola, Andre Cuello, and Megan Guiney, played a criticalrole in converting the a rough manuscript into its final form. All of these people improved thisvolume in significant ways with their insights and their help.Finally, many people have provided us with intellectual and emotional support over the lastfive years. First and foremost, our families and our colleagues at Rice have encouraged us atevery step of the way. Christine and Carolyn, in particular, tolerated myriad long discussions ontopics in compiler construction.