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

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. An expression, such as b + c or a - d, is redundant inB if and only if it has been previously computed in B and no intervening8.4 Local Optimization 421operation redefines one of its constituent arguments.

In B, the occurrence ofb + c in the third operation is not redundant because the second operationredefines b. The occurrence of a - d in the fourth operation is redundantbecause B does not redefine a or d between the second and fourth operations.The compiler can rewrite this block so that it computes a - d once, as shownin the margin. The second evaluation of a - d is replaced with a copy from b.An alternative strategy would replace subsequent uses of d with uses of b.However, that approach requires analysis to determine whether or not b isredefined before some use of d. In practice, it is simpler to have the optimizerinsert a copy and let a subsequent pass determine which copy operationsare, in fact, necessary and which ones can have their source and destinationnames combined.In general, replacing redundant evaluations with references to previouslycomputed values is profitable—that is, the resulting code runs more quicklythan the original.

However, profitability is not guaranteed. Replacingd ← a - d with d ← b has the potential to extend the lifetime of b and toshorten the lifetimes of either a or d or both—depending, in each case, onwhere the last use of the value lies. Depending on the precise details, eachrewrite can increase demand for registers, decrease demand for registers, orleave it unchanged. Replacing a redundant computation with a reference islikely to be unprofitable if the rewrite causes the register allocator to spill avalue in the block.abcd←←←←baba+++cdcdOriginal Blockabcd←←←←b + ca - db + cbRewritten BlockLifetimeThe lifetime of a name is the region of codebetween its definitions and its uses.

Here,definition means assignment.In practice, the optimizer cannot consistently predict the behavior of the register allocator, in part because the code will be further transformed before itreaches the allocator. Therefore, most algorithms for removing redundancyassume that rewriting to avoid redundancy is profitable.In the previous example, the redundant expression was textually identical tothe earlier instance. Assignment can, of course, produce a redundant expression that differs textually from its predecessor. Consider the block shown inthe margin. The assignment of b to d makes the expression d × c producethe same value as b × c.

To recognize this case, the compiler must track theflow of values through names. Techniques that rely on textual identity donot detect such cases.Programmers will protest that they do not write code that contains redundantexpressions like those in the example. In practice, redundancy elimination finds many opportunities. Translation from source code to ir elaborates many details, such as address calculations, and introduces redundantexpressions.Many techniques that find and eliminate redundancies have been developed.

Local value numbering is one of the oldest and most powerful ofa ← b × cd ← be ← d × cEffect of Assignment422 CHAPTER 8 Introduction to Optimizationthese transformations. It discovers such redundancies within a basic blockand rewrites the block to avoid them. It provides a simple and efficientframework for other local optimizations, such as constant folding andsimplification using algebraic identities.The AlgorithmThe idea behind value numbering is simple. The algorithm traverses a basicblock and assigns a distinct number to each value that the block computes. Itchooses the numbers so that two expressions, ei and e j , have the same valuenumber if and only ei and e j have provably equal values for all possibleoperands of the expressions.Figure 8.2 shows the basic local value numbering algorithm (lvn).

lvn takesas input a block with n binary operations, each of the form Ti ← Li Opi Ri .lvn examines each operation, in order. lvn uses a hash table to map names,constants, and expressions into distinct value numbers. The hash table isinitially empty.To process the i th operation, lvn obtains value numbers for Li and Ri bylooking for them in the hash table.

If it finds an entry, lvn uses the valuenumber of that entry. If not, it creates one and assigns a new value number.Given value numbers for Li and Ri , called VN(Li) and VN(Ri), lvn constructs a hash key from hVN(Li), Opi , VN(Ri)i and looks up that key in thetable. If an entry exists, the expression is redundant and can be replacedby a reference to the previously computed value. If not, operation i is thefirst computation of the expression in this block, so lvn creates an entryfor its hash key and assigns that entry a new value number. It also assignsthe hash key’s value number, whether new or pre-existing, to the table entryfor Ti . Because lvn uses value numbers to construct the expression’s hashfor i ← 0 to n - 1, where the block has n operations‘‘Ti ← Li Opi Ri ’’1. get the value numbers for Li and Ri2.

construct a hash key from Opi and the value numbers for Li and Ri3. if the hash key is already present in the table thenreplace operation i with a copy of the value into Ti andassociate the value number with Tielseinsert a new value number into the table at the hash key locationrecord that new value number for Tin FIGURE 8.2 Value Numbering a Single Block.8.4 Local Optimization 423THE IMPORTANCE OF ORDERThe specific order in which expressions are written has a direct impact onthe ability of optimizations to analyze and transform them. Consider thefollowing distinct encodings of v ← a × b × c:t0 ← a × bv ← t0 × ct0 ← b × cv ← a × t0The encoding on the left assigns value numbers to a × b, to (a × b) × cand to v, while the encoding on the right assigns value numbers to b × c,to a × (b × c) and to v. Depending on the surrounding context, one orthe other encoding may be preferable.

For example, if b × c occurs laterin the block but a × b does not, then the right-hand encoding producesredundancy while the left does not.In general, using commutativity, associativity, and distributivity to reorderexpressions can change the results of optimization. Similar effects can beseen with constant folding; if we replace a with 3 and c with 5, neitherordering produces the constant operation 3 × 5, which can be folded.Because the number of ways to reorder expressions is prohibitively large,compilers use heuristic techniques to find good orderings for expressions.For example, the IBM FORTRAN H compiler generated array-address computations in an order that tended to improve other optimizations. Othercompilers have sorted the operands of commutative and associative operations into an order that corresponds to the loop nesting level at which theyare defined.

Because so many solutions are possible, heuristic solutions forthis problem often require experimentation and tuning to discover what isappropriate for a specific language, compiler, and coding style.key, rather than names, it can effectively track the flow of values throughcopy and assignment operations, such as the small example labelled “Effectof Assignment” on the previous page. Extending lvn to expressions ofarbitrary arity is straightforward.To see how lvn works, consider our original example block, shown onpage 421. The version in the margin shows the value numbers that lvnassigns as superscripts. In the first operation, with an empty value table, band c get new value numbers, 0 and 1 respectively. lvn constructs the textualstring “0 + 1” as a hash key for the expression a + b and performs a lookup.