K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 102
Текст из файла (страница 102)
(After all,if transformations need not preserve meaning, why not replace the entireprocedure with a single nop?)Two issues, safety and profitability, lie at the heart of every optimization.The compiler must have a mechanism to prove that each application ofthe transformation is safe—that is, it preserves the program’s meaning.
Thecompiler must have a reason to believe that applying the transformation isprofitable—that is, it improves the program’s performance. If either of theseis not true—that is, applying the transformation will change the program’smeaning or will make its performance worse—the compiler should not applythe transformation.SafetyHow did the programmer know that this transformation was safe? That is,why did the programmer believe that the transformed code would producethe same results as the original code? Close examination of the loop nest8.2 Background 413DEFINING SAFETYCorrectness is the single most important criterion that a compiler mustmeet—the code that the compiler produces must have the same meaningas the input program. Each time the optimizer applies a transformation,that action must preserve the correctness of the translation.Typically, meaning is defined as the observable behavior of the program.For a batch program, this is the memory state after it halts, along withany output it generates.
If the program terminates, the values of all visiblevariables immediately before it halts should be the same under any translation scheme. For an interactive program, behavior is more complex anddifficult to capture.Plotkin formalized this notion as observational equivalence.For two expressions, M and N, we say that M and N are observationallyequivalent if and only if, in any context C where both M and N are closed (thatis, have no free variables), evaluating C[M] and C[N] either produces identicalresults or neither terminates [286].Thus, two expressions are observationally equivalent if their impacts onthe visible, external environment are identical.In practice, compilers use a simpler and looser notion of equivalence thanPlotkin’s, namely, that if, in their actual program context, two differentexpressions e and e0 produce identical results, then the compiler can substitute e0 for e.
This standard deals only with contexts that actually arisein the program; tailoring code to context is the essence of optimization.It does not mention what happens when a computation goes awry, ordiverges.In practice, compilers take care not to introduce divergence—the originalcode would work correctly, but the optimized code tries to divide by zero,or loops indefinitely. The opposite case, where the original code woulddiverge, but the optimized code does not, is rarely mentioned.shows that the only interaction between successive iterations occurs throughthe elements of y.nnA value computed as y(i) is not reused until the next iteration of theouter loop. The iterations of the inner loop are independent of eachother, because each iteration defines precisely one value and no otheriteration references that value.
Thus, the iterations can execute in anyorder. (For example, if we run the inner loop from n1 to 1 it producesthe same results.)The interaction through y is limited in its effect. The ith element of yaccumulates the sum of all the ith iterations of the inner loop. Thispattern of accumulation is safely reproduced in the unrolled loop.414 CHAPTER 8 Introduction to OptimizationA large part of the analysis done in optimization goes toward proving thesafety of transformations.ProfitabilityWhy did the programmer think that loop unrolling would improveperformance? That is, why is the transformation profitable? Severaldifferent effects of unrolling might speed up the code.nnnMemory boundA loop where loads and stores take more cyclesthan does computation is considered memorybound.To determine if a loop is memory bound requiresdetailed knowledge about both the loop and thetarget machine.The total number of loop iterations is reduced by a factor of 16.
Thisreduces the overhead operations due to loop control: adds, compares,jumps, and branches. If the loop executes frequently, these savingsbecome significant.This effect might suggest unrolling by an even larger factor. Finiteresource limits probably dictated the choice of 16. For example, theinner loop uses the same 16 values of x for all the iterations of theinner loop. Many processors have only 32 registers that can hold afloating-point number.
Unrolling by 32, the next power of two, wouldcreate enough of these “loop-invariant” values that they could not fit inthe register set. Spilling them to memory would add loads and storesto the inner loop and undo the benefits of unrolling.The array-address computations contain duplicated work. Consider theuse of y(i). The original code computed y(i)’s address once permultiplication of x and m; the transformed code computes it once per116 multiplications. The unrolled code does 16as much work to addressy(i). The 16 references to m, and to a lesser extent x, should includecommon portions that the loop can compute once and reuse, as well.The transformed loop performs more work per memory operation,where “work” excludes the overhead of implementing the array andloop abstractions. The original loop performed two arithmeticoperations for three memory operations, while the unrolled loopperforms 32 arithmetic operations for 18 memory operations, assumingthat all the x values stay in registers.
Thus, the unrolled loop is lesslikely to be memory bound. It has enough independent arithmetic tooverlap the loads and hide some of their latencies.Unrolling can help with other machine-dependent effects. It increases theamount of code in the inner loop, which may provide the instruction scheduler with more opportunities to hide latencies. If the end-of-loop branchhas a long latency, the longer loop body may let the compiler fill more ofthat branch’s delay slots. On some processors, unused delay slots must befilled with nops, in which case loop unrolling can decrease the number ofnops fetched, reduce memory traffic and, perhaps, reduce the energy used toexecute the program.8.2 Background 415RiskIf transformations intended to improve performance make it harder for thecompiler to generate good code for the program, those potential problemsshould be considered as profitability issues.
The hand transformationsperformed on dmxpy create new challenges for a compiler, including thefollowing:nnDemand for registers The original loop needs only a handful ofregisters to hold its active values. Only x(j), some part of the addresscalculations for x, y, and m, and the loop index variables need registersacross loop iterations, while y(i) and m(i,j) need registers briefly. Incontrast, the transformed loop has 16 elements of x to keep in registersacross the loop, along with the 16 values of m and y(i) that needregisters briefly.Form of address calculation The original loop deals with threeaddresses, one each for y, x, and m. Because the transformed loopreferences many more distinct locations in each iteration, the compilermust shape the address calculations carefully to avoid repeatedcalculations and excessive demand for registers.
In the worst case, thecode might use independent calculations for all 16 elements of x, all 16elements of m, and the one element of y.If the compiler shapes the address calculations appropriately, it can usea single pointer for m and another for x, each with 16 constant-valuedoffsets. It can rewrite the loop to use that pointer in the end-of-loop test,obviating the need for another register and eliminating another update.Planning and optimization make the difference.Other problems of a machine-specific nature arise as well. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
