6. Alias Analysis

Previous

Table of Contents

Next

Chapter 5
Local Optimization

The most effective transformations in an optimizing compiler are the simplest. Consider the expression T * 0. The translation techniques that walk the abstract syntax tree creating the flow graph would naturally compute T, load 0 into a temporary, and perform the multiplication. Algebraic identities can tell the compiler that this expression is 0, so load the constant into a temporary instead.

This chapter discusses these local transformations. The transformations are used in three places in the compiler: during the building of the flow graph, during dominator-based optimization, and later during peephole optimization. The optimizations include the following techniques:

•  Apply algebraic transformations to decrease the number of instructions. As an example, the expression N < 1 discussed in Figure 5.1 can be replaced by the expression N ≤ 0, which can be encoded in a single instruction without the need of loading the constant. A large collection of algebraic identities is listed at the end of this chapter.

•  The compiler can trace the values stored in temporaries and record the temporaries that have already been evaluated. If the same temporary is evaluated again without an intervening instruction changing the operands, then the instruction may be eliminated. These two operations are combined in a technique called value numbering.

•  Instructions that are not executed or that generate a temporary that is not used can be eliminated. This is a limited form of dead-code elimination. A more complete form of dead-code elimination occurs later.

These simplifications apply to our running example. Consider the code fragment from the initialization of the outer loop in Figure 2.1 (see Figure 5.2). The left column is the set of instructions generated by translating the abstract syntax tree into the flow graph; the right column is the resulting set of instructions after local optimization.

Figure 5.1  Value Numbering and Identities

The compiler tracks the values in temporaries within the current block and applies algebraic identities. In this case the compiler knows that T5 has the value 1. The next computation asks whether T5 > T8, which the compiler knows is 1 > T8. The compiler knows that this is the same as 0 ≥ T8.

Figure 5.2  Value-Numbering Example

After building the program flow graph and performing the initial aliasing analysis, the compiler performs local optimizations and transformations to improve the structure of the program flow graph for the rest of the optimizer and decrease its size so that it takes less time and space. After cleaning up the program flow graph, this phase will perform global constant propagation and folding so that later phases have complete constant information.

Note that most of the algebraic simplifications are applied to integer arithmetic. It must also be applied to floating point arithmetic; however, the compiler must be careful on two points.

The arithmetic must be done at compile time exactly the same way it is done at runtime. Usually this is not a problem. It is a problem if the compiler is not running on the same machine as the machine which executes the program (a cross compiler). It is also a problem if the floating point rounding mode can change. If the rounding mode is not known, constant folding should be avoided.

Precise IEEE floating arithmetic can also be a problem. Full IEEE arithmetic includes the representation of infinities and NaN (Not a Number). The compiler must avoid the evaluation of expressions where one of the operands may be a NaN. It must even avoid replacing 0 * X by 0 if X might be a NaN.

5.1 Optimizations while Building the Flow Graph

Building the flow graph can be optimized to eliminate about half of the instructions generated. The idea is that the same computations frequently occur in the same block. This is not true of source code, but it is true of the addressing arithmetic generated by the compiler. These same instructions (and more) could be eliminated later. Eliminating them decreases the storage required for the flow graph and decreases the processing time required in the rest of the compiler. The following instructions can be eliminated from the generated block:

•  If a second instance of an instruction is about to be inserted in a block, then it can be eliminated if the arguments of the previous instruction have not been modified.

•  If an instruction has constant arguments, then the instruction can be replaced by a load constant instruction. The arithmetic must be done precisely as it would be done on the target machine. If there is any chance that an exception might be raised by the operation, the computation should be left as it is.

•  The list of algebraic identities at the end of this chapter should be applied to the instructions as they are generated. The simpler equivalent instruction sequence should be generated when possible.

The effect of these transformations is shown in the code in Figure 5.3 from the running example. The left column is the set of instructions that would be generated by the techniques that have been described in the previous section. The right column contains the instructions that are generated after value numbering and simplification of algebraic identities. Some statistics indicate that these techniques will eliminate about half of the instructions.

Value numbering divides the instructions in a block into equivalence classes: two instructions are equivalent if the compiler can determine that they have the same value. Only one instruction in each equivalence class needs to be generated. The code that generates the flow graph operates as described in Chapter 4, except the procedures that insert instructions into the flow graph maintain data structures to eliminate instructions that are unneeded.

•  If the instruction to be inserted is equivalent to an instruction already in the block, then the instruction is skipped and the target register from the equivalent instruction is returned as holding the value needed.

•  If the operands of the instruction are constants and the operator has no side effects, then a load constant for the precomputed result is generated instead.

Figure 5.3  Optimizations without Side Effects

•  If the instruction and its operands match a tree corresponding to an algebraic identity, then the simplified form of the tree is generated instead. Changing the instructions may cause some existing instructions to be unused. They will be eliminated later with dead-code elimination.

Previous

Table of Contents

Next