K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 13
Текст из файла (страница 13)
As long as the results of a longlatency operation are not referenced until the operation completes, executionproceeds normally. If, however, some intervening operation tries to read theresult of the long-latency operation prematurely, the processor delays theoperation that needs the value until the long-latency operation completes.An operation cannot begin to execute until its operands are ready, and itsresults are not ready until the operation terminates.The instruction scheduler reorders the operations in the code.
It attempts tominimize the number of cycles wasted waiting for operands. Of course, thescheduler must ensure that the new sequence produces the same result as theoriginal. In many cases, the scheduler can drastically improve the performance of “naive” code. For our example, a good scheduler might producethe following sequence:StartEnd123456791134546881013loadAIrarp , @a ⇒ r1loadAIloadAIaddmultloadAImultrarp , @b ⇒ r2rarp , @c ⇒ r3r1 , r1 ⇒ r1r1 , r2 ⇒ r1rarp , @d ⇒ r2r1 , r3 ⇒ r1multstoreAIr1 , r 2r1⇒ r1⇒ rarp , @a// load ‘a’// load ‘b’// load ‘c’// r1 ← a × 2// r1 ← (a × 2) × b// load ‘d’// r1 ← (a × 2 × b) × c// r1 ← (a × 2 × b × c) × d// write ra back to ‘a’20 CHAPTER 1 Overview of CompilationCOMPILER CONSTRUCTION IS ENGINEERINGA typical compiler has a series of passes that, together, translate codefrom some source language into some target language.
Along the way,the compiler uses dozens of algorithms and data structures. The compilerwriter must select, for each step in the process, an appropriate solution.A successful compiler executes an unimaginable number of times. Consider the total number of times that GCC compiler has run. Over GCC’slifetime, even small inefficiencies add up to a significant amount of time.The savings from good design and implementation accumulate over time.Thus, the compiler writer must pay attention to compile time costs, suchas the asymptotic complexity of algorithms, the actual running time ofthe implementation, and the space used by data structures. The compilerwriter should have in mind a budget for how much time the compiler willspend on its various tasks.For example, scanning and parsing are two problems for which efficientalgorithms abound.
Scanners recognize and classify words in time proportional to the number of characters in the input program. For a typicalprogramming language, a parser can build derivations in time proportionalto the length of the derivation. (The restricted structure of programminglanguages makes efficient parsing possible.) Because efficient and effective techniques exist for scanning and parsing, the compiler writer shouldexpect to spend just a small fraction of compile time on these tasks.By contrast, optimization and code generation contain several problemsthat require more time.
Many of the algorithms that we will examine forprogram analysis and optimization will have complexities greater thanO(n). Thus, algorithm choice in the optimizer and code generator has alarger impact on compile time than it does in the compiler’s front end. Thecompiler writer may need to trade precision of analysis and effectivenessof optimization against increases in compile time. He or she should makesuch decisions consciously and carefully.This version of the code requires just 13 cycles to execute.
The code usesone more register than the minimal number. It starts an operation in everycycle except 8, 10, and 12. Other equivalent schedules are possible, as areequal-length schedules that use more registers. Chapter 12 presents severalscheduling techniques that are in widespread use.Interactions Among Code-Generation ComponentsMost of the truly hard problems that occur in compilation arise during codegeneration. To make matters more complex, these problems interact. For1.4 Summary and Perspective 21example, instruction scheduling moves load operations away from the arithmetic operations that depend on them.
This can increase the period overwhich the values are needed and, correspondingly, increase the number ofregisters needed during that period. Similarly, the assignment of particularvalues to specific registers can constrain instruction scheduling by creatinga “false” dependence between two operations. (The second operation cannot be scheduled until the first completes, even though the values in thecommon register are independent. Renaming the values can eliminate thisfalse dependence, at the cost of using more registers.)1.4 SUMMARY AND PERSPECTIVECompiler construction is a complex task.
A good compiler combines ideasfrom formal language theory, from the study of algorithms, from artificialintelligence, from systems design, from computer architecture, and from thetheory of programming languages and applies them to the problem of translating a program. A compiler brings together greedy algorithms, heuristictechniques, graph algorithms, dynamic programming, dfas and nfas, fixedpoint algorithms, synchronization and locality, allocation and naming, andpipeline management.
Many of the problems that confront the compiler aretoo hard for it to solve optimally; thus, compilers use approximations, heuristics, and rules of thumb. This produces complex interactions that can lead tosurprising results—both good and bad.To place this activity in an orderly framework, most compilers are organizedinto three major phases: a front end, an optimizer, and a back end. Eachphase has a different set of problems to tackle, and the approaches used tosolve those problems differ, too. The front end focuses on translating sourcecode into some ir.
Front ends rely on results from formal language theoryand type theory, with a healthy dose of algorithms and data structures. Themiddle section, or optimizer, translates one ir program into another, withthe goal of producing an ir program that executes efficiently. Optimizersanalyze programs to derive knowledge about their runtime behavior and thenuse that knowledge to transform the code and improve its behavior. The backend maps an ir program to the instruction set of a specific processor. A backend approximates the answers to hard problems in allocation and scheduling,and the quality of its approximation has a direct impact on the speed and sizeof the compiled code.This book explores each of these phases. Chapters 2 through 4 deal withthe algorithms used in a compiler’s front end. Chapters 5 through 7 describebackground material for the discussion of optimization and code generation.Chapter 8 provides an introduction to code optimization.
Chapters 9 and 1022 CHAPTER 1 Overview of Compilationprovide more detailed treatment of analysis and optimization for the interested reader. Finally, Chapters 11 through 13 cover the techniques used byback ends for instruction selection, scheduling, and register allocation.nCHAPTER NOTESThe first compilers appeared in the 1950s. These early systems showedsurprising sophistication.
The original fortran compiler was a multipasssystem that included a distinct scanner, parser, and register allocator, alongwith some optimizations [26, 27]. The Alpha system, built by Ershov andhis colleagues, performed local optimization [139] and used graph coloringto reduce the amount of memory needed for data items [140, 141].Knuth provides some interesting recollections of compiler construction inthe early 1960s [227]. Randell and Russell describe early implementation efforts for Algol 60 [293]. Allen describes the history of compilerdevelopment inside ibm with an emphasis on the interplay of theory andpractice [14].Many influential compilers were built in the 1960s and 1970s.
These includethe classic optimizing compiler fortran H [252, 307], the Bliss-11 andBliss-32 compilers [72, 356], and the portable bcpl compiler [300]. Thesecompilers produced high-quality code for a variety of cisc machines. Compilers for students, on the other hand, focused on rapid compilation, gooddiagnostic messages, and error correction [97, 146].The advent of risc architecture in the 1980s led to another generation ofcompilers; these focused on strong optimization and code generation [24,81, 89, 204]. These compilers featured full-blown optimizers structured asshown in Figure 1.1.
Modern risc compilers still follow this model.During the 1990s, compiler-construction research focused on reacting tothe rapid changes taking place in microprocessor architecture. The decadebegan with Intel’s i860 processor challenging compiler writers to managepipelines and memory latencies directly.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
