Introduction: We now examine carefully what it means to move an operation up a path. Suppose we wish to move an operation from block src up a control-flow path to block dst. We assume that such a move does not violate any data dependences and that it makes paths through dst and src run faster. If dst dominates src, and src post-dominates dst, then the operation moved is executed once and only once, when it should. If src does not postdominate dst

Then there exists a path that passes through dst that does not reach src. An extra operation would have been executed in this case. This code motion is illegal unless the operation moved has no unwanted side effects. If the moved operation executes "for free" (i.e., it uses only resources that otherwise would be idle), then this move has no cost. It is beneficial only if the control flow reaches src. If dst does not dominate src

Then there exists a path that reaches src without first going through dst. We need to insert copies of the moved operation along such paths. We know how to achieve exactly that from our discussion of partial redundancy elimination in Section 9.5- We place copies of the operation along basic blocks that form a cut set separating the entry block from src. At each place where the operation is inserted, the following constraints must be satisfied:

1.  The operands of t he operation must hold the same values as in the original,

2.  The result does not overwrite a value that is still needed, and

3.  It itself is not subsequently overwritten befpre reaching src. These copies render the original instruction in src fully redundant, and it thus can be eliminated.

We refer to the extra copies of the operation as compensation code. As discussed in Section 9.5, basic blocks can be inserted along critical edges to create places for holding such copies. The compensation code can potentially make some paths run slower. Thus, this code motion improves program execution only if the optimized paths are executed more frequently than the non-optimized ones.

Downward Code Motion

Suppose we are interested in moving an operation from block src down a controlflow path to block dst. We can reason about such code motion in the same way as above.

If src does not dominate dst

Then there exists a path that reaches dst without first visiting src. Again, an extra operation will be executed in this case. Unfortunately, downward code motion is often applied to writes, which have the side effects of overwriting old values. We can get around this problem by replicating the basic blocks along the paths from src to dst, and placing the operation only in the new copy of dst. Another approach, if available, is to use predicated instructions. We guard the operation moved with the predicate that guards the src block. Note that the predicated instruction must be scheduled only in a block dominated by the computation of the predicate, because the predicate would not be available otherwise.

If dst does not postdominate src

As in the discussion above, compensation code needs to be inserted so that the operation moved is executed on all paths not visiting dst. This transformation is again analogous to partial redundancy elimination, except that the copies are placed below the src block in a cut set that separates src from the exit.

Summary of Upward and Downward Code Motion: From this discussion, we see that there is a range of possible global code motions which vary in terms of benefit, cost, and implementation complexity. Figure 10.13 shows a summary of these various code motions; the lines correspond to the following four cases:

1. Moving instructions between control-equivalent blocks is simplest and most cost effective. No extra operations are ever executed and no compensation code is needed.

2. Extra operations may be executed if the source does not postdominate (dominate) the destination in upward (downward) code motion. This code motion is beneficial if the extra operations can be executed for free, and the path passing through the source block is executed.

3. Compensation code is needed if the destination does not dominate (postdominate) the source in upward (downward) code motion. The paths with the compensation code may be slowed down, so it is important that the optimized paths are more frequently executed.

4. The last case combines the disadvantages of the second and third case: extra operations may be executed and compensation code is needed.

Previous Next