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

Itdoes not find an entry for that key, so the lookup fails. Accordingly, lvn creates a new entry for “0 + 1” and assigns it value number 2. lvn then createsan entry for a and assigns it the value number of the expression, namely 2.Repeating this process for each operation, in sequential order, produces therest of the value numbers shown in the margin.a2b4c5d4←←←←b0a2b4a2++-c1d3c1d3424 CHAPTER 8 Introduction to Optimizationabcd←←←←b + ca - db + cbThe value numbers reveal, correctly, that the two occurrences of b + c produce different values, due to the intervening redefinition of b. On the otherhand, the two occurrences of a - d produce the same value, since they havethe same input value numbers and the same operator.

lvn discovers thisand records it by assigning b and d the same value number, namely 4. Thatknowledge lets lvn rewrite the fourth operation with a d ← b as shown inthe margin. Subsequent passes may eliminate the copy.Extending the Algorithmlvn provides a natural framework to perform several other localoptimizations.nnnCommutative operations Commutative operations that differ only inthe order of their operands, such as a × b and b × a, should receive thesame value numbers. As lvn constructs a hash key for the right-handside of the current operation, it can sort the operands using someconvenient scheme, such as ordering them by value number.

Thissimple action will ensure that commutative variants receive the samevalue number.Constant folding If all the operands of an operation have knownconstant values, lvn can perform the operation and fold the answerdirectly into the code. lvn can store information about constants in thehash table, including their value. Before hash-key formation, it can testthe operands and, if possible, evaluate them. If lvn discovers aconstant expression, it can replace the operation with an immediateload of the result. Subsequent copy folding will clean up the code.Algebraic identities lvn can apply algebraic identities to simplify thecode. For example, x + 0 and x should receive the same value number.Unfortunately, lvn needs special-case code for each identity. A seriesof tests, one per identity, can easily become long enough to produce anunacceptable slowdown in the algorithm.

To ameliorate this problem,lvn should organize the tests into operator-specific decision trees.Since each operator has just a few identities, this approach keeps theoverhead low. Figure 8.3 shows some of the identities that can behandled in this way.a + 0 = aa - 0 = aa - a = 02 × a = a + aa × 1 = aa × 0 = 0a ÷ 1 = aa ÷ a = 1, a 6= 0a1 = aa2 = a × aa 0 = aa 0 = aa AND a = aa OR a = aMAX (a,a) = aMIN (a,a) = an FIGURE 8.3 Algebraic Identities for Value Numbering.8.4 Local Optimization 425for i ← 0 to n - 1, where the block has n operations‘‘Ti ← Li Opi Ri ’’1.get the value numbers for Li and Ri2.if Li and Ri are both constant then evaluate Li Opi Ri ,assign the result to Ti , and mark Ti as constant3.if Li Opi Ri matches an identity in Figure 8.3, then replace it witha copy operation or an assignment4.construct a hash key from Opi and the value numbers for Li and Ri ,using the value numbers in ascending order, if Opi commutes5.if the hash key is already present in the table thenreplace operation i with a copy 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.4 Local Value Numbering with Extensions.A clever implementor will discover other identities, including some thatare type specific.

The exclusive-or of two identical values should yielda zero of the appropriate type. Numbers in ieee floating-point formathave their own special cases introduced by the explicit representationsof ∞ and NaN; for example, ∞ − ∞ = NaN, ∞ − NaN = NaN, and∞ ÷ NaN = NaN.Figure 8.4 shows lvn with these extensions. Steps 1 and 5 appeared in theoriginal algorithm.

Step 2 evaluates and folds constant-valued operations.Step 3 checks for algebraic identities using the decision trees mentionedearlier. Step 4 reorders the operands of commutative operations. Even withthese extensions, the cost per ir operation remains extremely low. Each stephas an efficient implementation.NaNNot a Number, a defined constant that representsan invalid or meaningless result in the IEEEstandard for floating-point arithmeticThe Role of NamingThe choice of names for variables and values can limit the effectiveness ofvalue numbering. Consider what happens when lvn is applied to the blockshown in the margin.

Again, the superscripts indicate the value numbersassigned to each name and value.In the first operation, lvn assigns 1 to x, 2 to y and 3 to both x + y andto a. At the second operation, it discovers that x + y is redundant, with valuenumber 3. Accordingly, it rewrites b ← x + y with b ← a. The third operationa3 ← x1 + y2b3 ← x1 + y2a4 ← 17 4c3 ← x1 + y2426 CHAPTER 8 Introduction to Optimizationis both straightforward and nonredundant. At the fourth operation, it againdiscovers that x + y is redundant, with value number 3. It cannot, however,rewrite the operation as c ← a because a no longer has value number 3.We can cure this problem in two distinct ways.

We can modify lvn so thatit keeps a mapping from value numbers to names. At an assignment to somename, say a, it must remove a from the list for its old value number and adda to the list for its new value number. Then, at a replacement, it can use anyname that currently contains that value number. This approach adds somecost to the processing of each assignment and clutters up the code for thebasic algorithm.a3← x1+ y2000b3← x1+ y2000a4← 17 41c3← x1+ y2000As an alternative, the compiler can rewrite the code in a way that gives eachassignment a distinct name.

Adding a subscript to each name for uniqueness,as shown in the margin, is sufficient. With these new names, the code defineseach value exactly once. Thus, no value is ever redefined and lost, or killed.If we apply lvn to this block, it produces the desired result. It proves thatthe second and fourth operations are redundant; each can be replaced with acopy from a0 .However, the compiler must now reconcile these subscripted names withthe names in surrounding blocks to preserve the meaning of the originalcode. In our example, the original name a should refer to the value from thesubscripted name a1 in the rewritten code.

A clever implementation wouldmap the new a1 to the original a , b0 to the original b , c0 to the originalc , and rename a0 to a new temporary name. That solution reconciles thename space of the transformed block with the surrounding context withoutintroducing copies.This naming scheme approximates one property of the name space created for static single-assignment form, or ssa, introduced in Section 5.4.2.Section 9.3 explores translation from linear code into ssa form and from ssaform back into linear code. The algorithms that it presents for name-spacetranslation are more general than needed for a single block, but will certainly handle the single-block case and will attempt to minimize the numberof copy operations that must be inserted.The Impact of Indirect AssignmentsThe previous discussion assumes that assignments are direct and obvious,as in a ← b × c. Many programs contain indirect assignments, where thecompiler may not know which values or locations are modified.

Examplesinclude assignment through a pointer, such as *p = 0; in c, or assignmentto a structure element or an array element, such as a(i,j) = 0 in fortran.Indirect assignments complicate value numbering and other optimizations8.4 Local Optimization 427RUNTIME EXCEPTIONS AND OPTIMIZATIONSome abnormal runtime conditions can raise exceptions. Examples includeout-of-bounds memory references, undefined arithmetic operations suchas division by zero, and ill-formed operations. (One way for a debuggerto trigger a breakpoint is to replace the instruction with an ill-formed oneand to catch the exception.) Some languages include features for handlingexceptions, for both predefined and programmer-defined situations.Typically, a runtime exception causes a transfer of control to an exception handler.

The handler may cure the problem, re-execute the offendingoperation, and return control to the block. Alternatively, it may transfercontrol elsewhere or terminate execution.The optimizer must understand which operations can raise an exceptionand must consider the impact of an exception on program execution.Because an exception handler might modify the values of variables ortransfer control, the compiler must treat exception-raising operations conservatively.

For example, every exception-raising operation might forcetermination of the current basic block. Such treatment can severely limitthe optimizer’s ability to improve the code.To optimize exception-laden code, the compiler needs to understand andmodel the effects of exception handlers.

To do so, it needs access to thecode for the exception handlers and it needs a model of overall executionto understand which handlers might be in place when a specific exceptionraising operation executes.because they create imprecisions in the compiler’s understanding of the flowof values.Consider value numbering with the subscripted naming scheme presented inthe previous section. To manage the subscripts, the compiler maintains a mapfrom the base variable name, say a, to its current subscript. On an assignment, such as a ← b + c, the compiler simply increments the current subscriptfor a. Entries in the value table for the previous subscript remain intact. Onan indirect assignment, such as *p ← 0, the compiler may not know whichbase-name subscripts to increment.

Without specific knowledge of the memory locations to which p can refer, the compiler must increment the subscriptof every variable that the assignment could possibly modify—potentially,the set of all variables. Similarly, an assignment such as a(i,j) = 0, wherethe value of either i or j is unknown, must be treated as if it changes thevalue of every element of a.Hint: The hash table of value numbers mustreflect subscripted names.