K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 103
Текст из файла (страница 103)
The different scopes of these optimizations presented differentopportunities to the optimizer. Reformulating the array reference improvedperformance for the execution of that array reference. Rewriting the loopimproved performance across a larger region. In general, transformationsand the analyses that support them operate on one of four distinct scopes:local, regional, global, or whole program.Scope of optimizationThe region of code where an optimizationoperates is its scope of optimization.Local MethodsLocal methods operate over a single basic block: a maximal-length sequenceof branch-free code.
In an iloc program, a basic block begins with a labelledoperation and ends with a branch or a jump. In iloc, the operation after abranch or jump must be labelled or else it cannot be reached; other notationsallow a “fall-through” branch so that the operation after a branch or jumpneed not be labelled.
The behavior of straight-line code is easier to analyzeand understand than is code that contains branches and cycles.Inside a basic block, two important properties hold. First, statements areexecuted sequentially. Second, if any statement executes, the entire blockexecutes, unless a runtime exception occurs.
These two properties let thecompiler prove, with relatively simple analyses, facts that may be strongerthan those provable for larger scopes. Thus, local methods sometimes makeimprovements that simply cannot be obtained for larger scopes. At the sametime, local methods are limited to improvements that involve operations thatall occur in the same block.Regional MethodsRegional methods operate over scopes larger than a single block but smallerthan a full procedure. In the example control-flow graph (cfg) in the margin, the compiler might consider the entire loop, {B0 , B1 , B2 , B3 , B4 , B5 , B6 },as a single region. In some cases, considering a subset of the code for thefull procedure produces sharper analysis and better transformation results??B0B1BR@B2R@B4B B3B @R B5BBN B6?418 CHAPTER 8 Introduction to Optimizationthan would occur with information from the full procedure.
For example,inside a loop nest, the compiler may be able to prove that a heavily usedpointer is invariant (single-valued), even though it is modified elsewhere inthe procedure. Such knowledge can enable optimizations such as keeping ina register the value referenced through that pointer.Extended basic blocka set of blocks β1 , β2 , . . . , βn where β1 hasmultiple CFG predecessors and each other βi hasjust one, which is some βj in the setDominatorIn a CFG, x dominates y if and only if every pathfrom the root to y includes x.The compiler can choose regions in many different ways. A region might bedefined by some source-code control structure, such as a loop nest.
The compiler might look at the subset of blocks in the region that form an extendedbasic block (ebb). The example cfg contains three ebbs: {B0 , B1 , B2 , B3 , B4 },{B5 }, and {B6 }. While the two single-block ebbs provide no advantage overa purely local view, the large ebb may offer opportunities for optimization(see Section 8.5.1).
Finally, the compiler might consider a subset of the cfgdefined by some graph-theoretic property, such as a dominator relation orone of the strongly connected components in the cfg.Regional methods have several strengths. Limiting the scope of a transformation to a region smaller than the entire procedure allows the compiler tofocus its efforts on heavily executed regions—for example, the body of aloop typically executes much more frequently than the surrounding code.The compiler can apply different optimization strategies to distinct regions.Finally, the focus on a limited area in the code often allows the compiler toderive sharper information about program behavior which, in turn, exposesopportunities for improvement.Global MethodsThese methods, also called intraprocedural methods, use an entire procedure as context.
The motivation for global methods is simple: decisions thatare locally optimal may have bad consequences in some larger context. Theprocedure provides the compiler with a natural boundary for both analysisand transformation. Procedures are abstractions that encapsulate and insulate runtime environments. At the same time, they serve as units of separatecompilation in many systems.Global methods typically operate by building a representation of the procedure, such as a cfg, analyzing that representation, and transforming theunderlying code. If the cfg can have cycles, the compiler must analyze theentire procedure before it understands what facts hold on entrance to anyspecific block.
Thus, most global transformations have separate analysis andtransformation phases. The analytical phase gathers facts and reasons aboutthem. The transformation phase uses those facts to determine the safety andprofitability of a specific transformation. By virtue of their global view,8.3 Scope of Optimization 419INTRAPROCEDURAL VERSUS INTERPROCEDURALFew terms in compilation create as much confusion as the word global.Global analysis and optimization operate on an entire procedure. The modern English connotation, however, suggests an all-encompassing scope, asdoes the use of global in discussions of lexical scoping rules. In analysis andoptimization, however, global means pertaining to a single procedure.Interest in analysis and optimization across procedure boundaries necessitated terminology to differentiate between global analysis and analysisover larger scopes.
The term interprocedural was introduced to describeanalysis that ranged from two procedures to a whole program. Accordingly, authors began to use the term intraprocedural for single-proceduretechniques. Since these words are so close in spelling and pronunciation,they are easy to confuse and awkward to use.Perkin-Elmer Corporation tried to remedy this confusion when it introduced its "universal" FORTRAN VIIZ optimizing compiler for the PE 3200; thesystem performed extensive inlining followed by aggressive global optimization on the resulting code.
Universal did not stick. We prefer the termwhole program and use it whenever possible. It conveys the right distinction and reminds the reader and listener that "global" is not "universal."these methods can discover opportunities that neither local nor regionalmethods can.Interprocedural MethodsThese methods, sometimes called whole-program methods, consider scopeslarger than a single procedure. We consider any transformation that involvesmore than one procedure to be an interprocedural transformation.
Just asmoving from a local scope to a global scope exposes new opportunities,so moving from single procedures to the multiple procedures can expose newopportunities. It also raises new challenges. For example, parameter-bindingrules introduce significant complications into the analysis that supportsoptimization.Interprocedural analysis and optimization occurs, at least conceptually, onthe program’s call graph.
In some cases, these techniques analyze the entireprogram; in other cases the compiler may examine just a subset of the sourcecode. Two classic examples of interprocedural optimizations are inline substitution, which replaces a procedure call with a copy of the body of thecallee, and interprocedural constant propagation, which propagates and foldsinformation about constants throughout the entireprogram.420 CHAPTER 8 Introduction to OptimizationSECTION REVIEWCompilers perform both analysis and transformation over a varietyof scopes, ranging from single basic blocks (local methods) to entireprograms (whole-program methods). In general, the number of opportunities for improvement grows with the scope of optimization.
However,analyzing larger scopes often results in less precise knowledge aboutthe code’s behavior. Thus, no simple relationship exits between scope ofoptimization and quality of the resulting code. It would be intellectuallypleasing if a larger scope of optimization led, in general, to better codequality. Unfortunately, that relationship does not necessarily hold true.??B0B1BR@B2R@B4B B3B R@ B5BBN B6?Review Questions1. Basic blocks have the property that if one instruction executes, everyinstruction in the block executes, in a specified order (unless an exception occurs). State the weaker property that holds for a block in anextended basic block, other than the entry block, such as block B2 in theEBB {B0 , B1 , B2 , B3 , B4 }, for the control-flow graph shown in the margin.2.
What kinds of improvement might the compiler find with wholeprogram compilation? Name several inefficiencies that can only beaddressed by examining code across procedure boundaries. Howdoes interprocedural optimization interact with the desire to compileprocedures separately?8.4 LOCAL OPTIMIZATIONOptimizations that operate over a local scope—a single basic block—areamong the simplest techniques that the compiler can use. The simple execution model of a basic block leads to reasonably precise analysis in supportof optimization. Thus, these methods are surprisingly effective.RedundantAn expression e is redundant at p if it has alreadybeen evaluated on every path that leads to p.This section presents two local methods as examples.
The first, valuenumbering, finds redundant expressions in a basic block and replaces theredundant evaluations with reuse of a previously computed value. The second, tree-height balancing, reorganizes expression trees to expose moreinstruction-level parallelism.8.4.1 Local Value NumberingConsider the four-statement basic block shown in the margin. We will referto the block as B.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
