K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 106
Текст из файла (страница 106)
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>.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
