7. Static Single Assignment

Previous

Table of Contents

Next

Chapter 6
Alias Analysis

What does it mean for one instruction to affect another? Remember how the proofs of the theorems about available or anticipated expressions developed. During the proofs a walk is performed backward (or forward) from a point in the flow graph to a point where the desired computation occurs. There must be no instructions on that path that change the computation of the desired expression. In other words, one instruction affects another if interchanging the order of the instructions would change the values in the target temporaries (or memory) after the instruction pair.

This section describes the computation of two attributes for each temporary: modifies(T), which is the set of temporaries that are affected by the modification of T, and store_modifies(T), which is the set of temporaries whose store operations are affected by a modification of T.

Remember, temporaries are divided into two classes: expression and variable temporaries. Each expression temporary occurs as the target of an instruction that is a pure function of its operands. There may be multiple points where the expression temporary is evaluated. In each case the same instruction occurs, which means the same operator and the same operand temporaries or memory location. Each expression temporary represents an expression tree in which the node representing the temporary is labeled with the operator and the children are the operands. The root and internal nodes of this tree are all expression temporaries. The leaf nodes represent LOAD instructions from memory or variable temporaries. An expression temporary is not considered modified by the reevaluation of one of its operands that is an expression temporary. It is modified if one of the variable temporaries at the leaves of the tree is assigned a new value with a copy operation or if the memory location corresponding to one of the load operations is modified.

Similarly, a store operation can be modified by another store operation. If both store operations may reference the same memory location, then they cannot be reordered.

Definition	Modifies: A temporary T modifies temporary U if interchanging the order of the instructions that compute the two temporaries will result in different values stored in U.

Consider the fragment of source code in Figure 6.1. Unless there is some unstated relation between A and B, such as the Fortran EQUIVALENCE statement or C language rules for formal parameters, the store into B(I) does not affect the load of A(I) or A(N). Similarly, the store into A(I) does not affect the load of B(I+1). Since the compiler can prove that B(I) and B(I+1) reference different memory locations at each point in the program, the store into B(I) does not modify the value of the load operation B(I+1).

The variable I will be held in a temporary in the flow graph. The increment of I changes the address referenced by each of these STORE and LOAD instructions, so the store into I modifies each of these instructions.

This compiler implements dependence analysis, therefore it can notice that A(N) in Figure 6.1 is not modified by the store into A(I) since the value of I is always less than N in the loop. However, that is not done in this section. Using the techniques in this section, the compiler will be unable to differentiate A(I) from A(N). Compilers without dependence analysis cannot notice this. However, the compiler will identify the following situations:

•  When the compiler knows that two addresses are distinct, then no modifies relationship will exist between a store and a load. For example, B(I) and B(I+1) are not related by the modifies relation. When the compiler is not sure, it must assume that there is a modifies relationship, so A(I) and A(J) must be assumed to be related unless the compiler knows something about the ranges of values that I and J can take.

Figure 6.1  Example for Describing Aliasing

•  The compiler knows that two fields of a nonoverlaid structure cannot be related by the modifies relation because they are different offsets from the same address.

•  The compiler knows that the modifies relation is not transitive. A store into A(I) indicates that the whole array A is modified. The modification of A indicates that A(I+1) is potentially modified. However, the transitive relation “modification of A(I) indicates that A(I+1) is modified” is false.

•  Source language restrictions must be taken into account. In C, pointers are typed. Except for pointers to characters (which can point to anything for historical reasons), a storage modification using a pointer can only modify locations of the same type and data structures containing locations of the same type.

Previous

Table of Contents

Next