K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 10
Текст из файла (страница 10)
They are appearing in many new places. Javacompilers take partially compiled programs (in Java "bytecode" format)and translate them into native code for the target machine. In this environment, success requires that the sum of compile time plus runtime must beless than the cost of interpretation. Techniques to analyze whole programsare moving from compile time to link time, where the linker can analyzethe assembly code for the entire application and use that knowledge toimprove the program.
Finally, compilers are being invoked at runtime togenerate customized code that capitalizes on facts that cannot be knownany earlier. If the compilation time can be kept small and the benefits arelarge, this strategy can produce noticeable improvements.the ir program into the instruction set and the finite resources of the targetmachine. Because the back end only processes ir created by the front end, itcan assume that the ir contains no syntactic or semantic errors.The compiler can make multiple passes over the ir form of the code beforeemitting the target program. This should lead to better code, as the compilercan, in effect, study the code in one phase and record relevant details.
Then,in later phases, it can use these recorded facts to improve the quality oftranslation. This strategy requires that knowledge derived in the first pass berecorded in the ir, where later passes can find and use it.Finally, the two-phase structure may simplify the process of retargetingthe compiler. We can easily envision constructing multiple back ends for asingle front end to produce compilers that accept the same language but target different machines. Similarly, we can envision front ends for differentRetargetingThe task of changing the compiler to generatecode for a new processor is often calledretargeting the compiler.8 CHAPTER 1 Overview of Compilationlanguages producing the same ir and using a common back end.
Bothscenarios assume that one ir can serve for several combinations of sourceand target; in practice, both language-specific and machine-specific detailsusually find their way into the ir.OptimizerThe middle section of a compiler, called anoptimizer, analyzes and transforms the IR toimprove it.Introducing an ir makes it possible to add more phases to compilation. Thecompiler writer can insert a third phase between the front end and the backend. This middle section, or optimizer, takes an ir program as its input andproduces a semantically equivalent ir program as its output. By using the iras an interface, the compiler writer can insert this third phase with minimaldisruption to the front end and back end.
This leads to the following compilerstructure, termed a three-phase compiler.SourceProgramFront EndIROptimizerIRBack EndTargetProgramCompilerThe optimizer is an ir-to-ir transformer that tries to improve the ir programin some way. (Notice that these transformers are, themselves, compilersaccording to our definition in Section 1.1.) The optimizer can make one ormore passes over the ir, analyze the ir, and rewrite the ir. The optimizermay rewrite the ir in a way that is likely to produce a faster target programfrom the back end or a smaller target program from the back end. It mayhave other objectives, such as a program that produces fewer page faults oruses less energy.Conceptually, the three-phase structure represents the classic optimizingcompiler.
In practice, each phase is divided internally into a series of passes.The front end consists of two or three passes that handle the details ofrecognizing valid source-language programs and producing the initial irform of the program. The middle section contains passes that perform different optimizations. The number and purpose of these passes vary fromcompiler to compiler. The back end consists of a series of passes, each ofwhich takes the ir program one step closer to the target machine’s instruction set. The three phases and their individual passes share a commoninfrastructure. This structure is shown in Figure 1.1.In practice, the conceptual division of a compiler into three phases, a frontend, a middle section or optimizer, and a back end, is useful. The problemsaddressed by these phases are different.
The front end is concerned withunderstanding the source program and recording the results of its analysis into ir form. The optimizer section focuses on improving the ir form.1.3 Overview of Translation 9--Reg Allocation-Inst Scheduling...Inst Selection-Optimization n-Optimization 2-Optimization 1 Optimizer Back End Elaboration-Parser-ScannerFront End- 666666666?????????Infrastructuren FIGURE 1.1 Structure of a Typical Compiler.The back end must map the transformed ir program onto the boundedresources of the target machine in a way that leads to efficient use of thoseresources.Of these three phases, the optimizer has the murkiest description.
The termoptimization implies that the compiler discovers an optimal solution to someproblem. The issues and problems that arise in optimization are so complex and so interrelated that they cannot, in practice, be solved optimally.Furthermore, the actual behavior of the compiled code depends on interactions among all of the techniques applied in the optimizer and the back end.Thus, even if a single technique can be proved optimal, its interactions withother techniques may produce less than optimal results. As a result, a goodoptimizing compiler can improve the quality of the code, relative to an unoptimized version. However, an optimizing compiler will almost always fail toproduce optimal code.The middle section can be a single monolithic pass that applies one or moreoptimizations to improve the code, or it can be structured as a series ofsmaller passes with each pass reading and writing ir.
The monolithic structure may be more efficient. The multipass structure may lend itself to a lesscomplex implementation and a simpler approach to debugging the compiler.It also creates the flexibility to employ different sets of optimization in different situations. The choice between these two approaches depends on theconstraints under which the compiler is built and operates.1.3 OVERVIEW OF TRANSLATIONTo translate code written in a programming language into code suitable forexecution on some target machine, a compiler runs through many steps.10 CHAPTER 1 Overview of CompilationNOTATIONCompiler books are, in essence, about notation. After all, a compiler translates a program written in one notation into an equivalent program writtenin another notation.
A number of notational issues will arise in yourreading of this book. In some cases, these issues will directly affect yourunderstanding of the material.Expressing Algorithms We have tried to keep the algorithms concise.Algorithms are written at a relatively high level, assuming that the readercan supply implementation details. They are written in a slanted, sansserif font.
Indentation is both deliberate and significant; it matters mostin an if-then-else construct. Indented code after a then or an elseforms a block. In the following code fragmentif Action [s,word] = ‘‘shift si ’’ thenpush wordpush siword ← NextWord()else if · · ·all the statements between the then and the else are part of the thenclause of the if-then-else construct. When a clause in an if-thenelse construct contains just one statement, we write the keyword thenor else on the same line as the statement.Writing Code In some examples, we show actual program text written insome language chosen to demonstrate a particular point.
Actual programtext is written in a monospace font.Arithmetic Operators Finally, we have forsaken the traditional useof * for × and of / for ÷, except in actual program text. The meaningshould be clear to the reader.To make this abstract process more concrete, consider the steps needed togenerate executable code for the following expression:a ← a × 2 × b × c × dwhere a, b, c, and d are variables, ← indicates an assignment, and × is theoperator for multiplication. In the following subsections, we will trace thepath that a compiler takes to turn this simple expression into executable code.1.3.1 The Front EndBefore the compiler can translate an expression into executable targetmachine code, it must understand both its form, or syntax, and its meaning,1.3 Overview of Translation 11or semantics. The front end determines if the input code is well formed, interms of both syntax and semantics.
If it finds that the code is valid, it createsa representation of the code in the compiler’s intermediate representation; ifnot, it reports back to the user with diagnostic error messages to identify theproblems with the code.Checking SyntaxTo check the syntax of the input program, the compiler must compare theprogram’s structure against a definition for the language.
This requires anappropriate formal definition, an efficient mechanism for testing whether ornot the input meets that definition, and a plan for how to proceed on anillegal input.Mathematically, the source language is a set, usually infinite, of stringsdefined by some finite set of rules, called a grammar. Two separate passesin the front end, called the scanner and the parser, determine whether or notthe input code is, in fact, a member of the set of valid programs defined bythe grammar.Programming language grammars usually refer to words based on their partsof speech, sometimes called syntactic categories. Basing the grammar ruleson parts of speech lets a single rule describe many sentences. For example,in English, many sentences have the formSentence → Subject verb Object endmarkwhere verb and endmark are parts of speech, and Sentence, Subject, andObject are syntactic variables. Sentence represents any string with the formdescribed by this rule.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
