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

The compiler can use asecond, smaller table to map base names tosubscripts.While this sounds drastic, it shows the true impact of an ambiguous indirectassignment on the set of facts that the compiler can derive. The compiler canperform analysis to disambiguate pointer references—that is, to narrow theAmbiguous referenceA reference is ambiguous if the compiler cannotisolate it to a single memory location.428 CHAPTER 8 Introduction to Optimizationset of variables that the compiler believes a pointer can address.

Similarly, itcan use a variety of techniques to understand the patterns of element accessin an array—again, to shrink the set of locations that it must assume aremodified by an assignment to one element.8.4.2 Tree-Height BalancingAs we saw in Chapter 7, the specific details of how the compiler encodes acomputation can affect the compiler’s ability to optimize that computation.Many modern processors have multiple functional units so that they canexecute multiple independent operations in each cycle.

If the compiler canarrange the instruction stream so that it contains independent operations,encoded in the appropriate, machine-specific way, then the application willrun more quickly.t1t2t3t4t5t6t7←←←←←←←Consider the code for a + b + c + d + e + f + g + h shown in the margin. A leftto-right evaluation would produce the left-associative tree in Figure 8.5a.Other permissible trees include those in Figure 8.5b and c. Each distincttree implies constraints on the execution order that are not required by therules of addition. The left-associative tree implies that the program mustevaluate a + b before it can perform the additions involving either g or h.

Thecorresponding right-associative tree, created by a right-recursive grammar,implies that g + h must precede additions involving a or b. The balanced treeimposes fewer constraints, but it still implies an evaluation order with moreconstraints than the actual arithmetic.a + bt1 + ct2 + dt3 + et4 + ft5 + gt6 + hIf the processor can perform more than one addition at a time, then thebalanced tree should let the compiler produce a shorter schedule for the computation.

Figure 8.6 shows possible schedules for the balanced tree and theleft-associative tree on a computer with two single-cycle adders. The balanced tree can execute in four cycles, with one unit idle in the fourth cycle.++++++++aa@h@f@d+@c(a) Left-Associative Tree!!!, l,laaa+, l,l++ Jab Jcd J J(b) Balanced Treeg+@e+f@+d+e@+c!+a@e@b@+b@g+@f+@gh@(c) Right-Associative Treen FIGURE 8.5 Potential Tree Shapes for a + b + c + d + e + f + g + h.h8.4 Local Optimization 429Balanced TreeUnit 01234567Left-Associative TreeUnit 1t1 ← a + bt2 ← c + dt3 ← e + ft4 ← g + ht5 ← t1 + t2t7 ← t5 + t6t6 ← t3 + t4———————1234567Unit 0Unit 1t1 ← a + b———————t2 ← t1 + ct3 ← t2 + dt4 ← t3 + et5 ← t4 + ft6 ← t5 + gt7 ← t6 + hn FIGURE 8.6 Schedules from Different Tree Shapes for a + b + c + d + e + f + g + h.In contrast, the left-associative tree requires seven cycles, leaving the secondadder idle throughout the computation.

The shape of the left-associative treeforces the compiler to serialize the additions. The right-associative tree willproduce a similar effect.This small example suggests an important optimization: using the commutative and associative laws of<b>Текст обрезан, так как является слишком большим</b>.