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

For example,the 17 loads and one store, the 16 multiplies, the 16 adds, plus the addresscalculations and loop-overhead operations in each iteration must be scheduled with care. The compiler may need to issue some of the load operationsin a previous iteration so that it can schedule the initial floating-pointoperations in a timely fashion.8.2.3 Opportunities for OptimizationAs we have seen, the task of optimizing a simple loop can involve complexconsiderations. In general, optimizing compilers capitalize on opportunitiesthat arise from several distinct sources.1.

Reducing the overhead of abstraction As we saw for the array-addresscalculation at the beginning of the chapter, the data structures and typesintroduced by programming languages require runtime support.Optimizers use analysis and transformation to reduce this overhead.416 CHAPTER 8 Introduction to Optimization2. Taking advantage of special cases Often, the compiler can useknowledge about the context in which an operation executes tospecialize that operation. As an example, a c++ compiler can sometimesdetermine that a call to a virtual function always uses the sameimplementation. In that case, it can remap the call and reduce the cost ofeach invocation.3.

Matching the code to system resources If the resource requirements of aprogram differ from the processor’s capacities, the compiler maytransform the program to align its needs more closely with availableresources. The transformations applied to dmxpy have this effect; theydecrease the number of memory accesses per floating-point operation.These are broad areas, described in sweeping generality. As we discuss specific analysis and transformation techniques, in Chapters 9 and 10, we willfill in these areas with more detailed examples.SECTION REVIEWMost compiler-based optimization works by specializing general purposecode to its specific context. For some code transformations, the benefitsaccrue from local effects, as with the improvements in the array-addresscalculations. Other transformations require broad knowledge of largerregions in the code and accrue their benefits from effects that occur overlarger swaths of the code.In considering any optimization, the compiler writer must worry aboutthe following:1.

Safety, for example, does the transformation not change the meaningof the code?2. Profitability, for example, how will the transformation improve thecode?3. Finding opportunities, for example, how can the compiler quicklylocate places in the code where applying the given transformation isboth safe and profitable?Review Questions1. In the code fragment from dmxpy in LINPACK, why did the programmerchoose to unroll the outer loop rather than the inner loop? How wouldyou expect the results to differ had she unrolled the inner loop?2. In the c fragment shown below, what facts would the compiler needto discover before it could improve the code beyond a simple byteoriented, load/store implementation?8.3 Scope of Optimization 417MemCopy(char *source, char *dest, int length) {int i;for (i=1; i≤length; i++){ *dest++ = *source++; }}8.3 SCOPE OF OPTIMIZATIONOptimizations operate at different granularities or scopes.

In the previoussection, we looked at optimization of a single array reference and of an entireloop nest. 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.