11. Limiting Resources

Previous

Table of Contents

Next

Chapter 10
Global Optimization

The compiler next performs a complete optimization phase. Most global optimizations have already been performed. The compiler has performed constant propagation, value propagation, most strength reduction and redundant expression elimination, and has restructured expressions to improve movement of instructions out of loops. All of the optimizations performed so far involved changing the operands used in instructions or the insertion of instructions. No instructions have been moved. Now the compiler will move instructions to less frequent execution points, perform a more complete redundant expression elimination, and perform a different strength-reduction algorithm.

Consider the flow graph in Figure 10.1. The temporary T is evaluated at three points. The modification of T in block B6 means that the previous algorithms will not have eliminated any of the three evaluations. However, the evaluation of T in B2 is redundant due to the other two evaluations of T. Previous redundant expression elimination only identified redundant evaluations when there was a single evaluation in a dominator block. The evaluation of S in block B2 can be moved out of the loop starting at B2 and placed in a new block between B1 and B2.

The algorithm operates on each temporary individually. There are five types of instructions in the flow graph. These instructions can be identified by the operation code for the instruction; however, they also play a role in viewing each expression as an expression tree. At this point the expression tree is implicit, having been translated into individual computations; however, it is useful in understanding the larger structure of this optimizer.

•  LOAD instructions are leaves of the expression trees. The LOAD instructions will be moved toward the Entry block to a point of less frequent execution. These instructions can be handled much like the normal computational instructions, except that LOAD instructions can be killed by STORE instructions and procedure calls. During the transformation, the LOAD instruction is represented by the destination temporary. This is a unique identification by the assumptions we have made about the form of the flow graph.

Figure 10.1  Opportunities for Global Optimization

•  COPY instructions play two roles in expression trees. They occur at the roots of the tree, copying the result into the destination temporary or setting up for a STORE instruction. COPY instructions are the most difficult to move in the flow graph because moving the copy operation depends on both the uses and evaluation points of the temporaries involved in the copy. The copy operations will be moved toward the Entry block to a point of less frequent execution. This optimization will happen rarely; however, it is important when it can happen. During this transformation, the copy operation is represented by a pair: the source temporary and the target temporary. This is a unique representation of the instruction since it completely represents the instruction.

•  STORE instructions will be moved either toward Entry or toward Exit. In effect, they do not occur in the expression trees. Rather, they occur after the copy operation at the root of the tree. During the transformation, the store operation is represented by the temporary being stored. This is a unique representation for all store operations; however, it conflicts with the use of the same temporary for load operations, so separate sets of global and local information are computed for store operations.

•  Computational instructions are pure functions that compute a value depending only on their operands. These instructions will be moved toward Entry to a point of less frequent execution. We will see that by using this form of partial redundancy elimination these computations can be moved independent of LOAD, STORE, and other computational instructions. During the transformation, the instruction is represented by the destination temporary, which uniquely represents the instruction by the conventions for the flow graph.

•  The final class of instructions are those that determine the structure of the flow graph, such as procedure calls and branching instructions. These instructions are left in place by these optimizations and are not moved.

The optimization algorithm computes points in the flow graph where the insertion of evaluations of T will make all present evaluations of T redundant. Then the algorithm eliminates all of the original evaluations. If the algorithm attempts to insert an evaluation into a block that already contains an evaluation, neither the insertion nor the deletion will be performed.

There are three different algorithms depending on the class of instructions to be optimized. The rest of this chapter will describe the algorithms and apply them to the running example.

Partial redundancy elimination (PRE): This transformation includes moving expressions out of loops and eliminating redundant expressions. The compiler determines new positions in the flow graph at which to insert evaluations of temporaries to make all of the original evaluations redundant. The particular form of partial redundancy used here is a derivative of lazy code motion, which ensures that computations are not moved unless there is some path that guarantees a decrease of computations.

Strength reduction (SR): Using a modification of the partial redundancy algorithm, the compiler can further optimize temporaries that are functions of induction temporaries. This handles some of the strength-reduction situations that were not handled earlier in the dominator-based transformation phases.

Load-store motion (LSM): Another generalization of partial redundancy elimination, this technique will move loads of data backward out of loops and move stores forward out of loops in some situations in which the data changes in the loop (that is, the data is not loop invariant).

Previous

Table of Contents

Next