Values

A computer program calculates a number of values. One way to improve its performance is to reduce the number of values it calculates. This is done primarily by avoiding repeated calculation of the same value. The problem for the compiler is then to determine when two computations yield the same value.

Redundant computations

A programmer generally does not knowingly write the code to compute the same value several times. The programming language may, however, conceal such recomputations in such a way that the programmer has no choice in the matter. Address calculations are the primary culprit.

Suppose that the array a has bounds l1, u1, l2, u2, l3, u3. Assuming that the array is stored by rows starting at address A, and that the size of each element is e, the address of a[i,j,k] can be expressed as:

A + e * ( (i-l1) +
          (j-l2) * (u1-l1) +
          (k-l3) * (u1-l1) * (u2-l2)
        )
Let di = (ui-li), and after a little algebra:
A - e * (l1 + l2*d1 + l3*d1*d2)
  + i*e + j*e*d1 + k*e*d1*d2)

[Discuss-

]

Example

Consider the following expression that is part of a typical scientific computation:
a[i,j,k] := ( a[i-1,j,k] + a[i+1,j,k] +
              a[i,j-1,k] + a[i,j+1,k] +
              a[i,j,k-1] + a[i,j,k+1] ) / 6.0;
The address of a[i,j,k] was given above. The address of a[i-1,j,k] is:
A - C0 + (i-1)*C1 + j*C2 + k*C3
= A - C0 - C1 + i*C1 + j*C2 + k*C3
= A - C01 + i*C1 + j*C2 + k*C3

[Discuss-

]

How are values determined?

The normal code generator transforms the expression tree into a sequence of instructions. Considering the MIPS R2000, each instruction does one of the following things:

[Discuss-

]

Optimizer conventions

The optimizer represents the program as a sequence of actions that are basically identical to RISC instructions.

[Discuss-

]

When are values identical?

It is important to note that, for the optimizer, two values are identical if and only if they are obtained from the same values by use of the same operator. Consider the following sequence:
pi: Vj:=Vm+Vm
pi+1: Vk:=Vm*2
pi+2: Vj:=Vm+Vm
Vj and Vk are not identical, even though they represent the same numerical result. The computations at program points i and i+2, on the other hand, involve identical operations on identical values and thus lead to identical values.

[Discuss-

]

Variables

A value is a specific value that gets computed at a particular program point and never changes. A variable, on the other hand, can be changed by writing to it.

[Discuss-

]

Example

The first part of the tuple sequence for the array assignment mentioned above might be:
p1: V1:=i
p2: V2:=V1*C1
p3: V3:=j
p4: V4:=V3*C2
p5: V5:=V2+V4
p6: V6:=k
p7: V7:=V6*C3
p8: V8:=V5+V7
p9: V9:=V8-C01
p10: V10:=a[V9]
If we didn't know that the variables i, j and k were unchanged by this tuple sequence, then we would continue with a sequence having the same form but different values. Actually, however, the next 8 tuples will be identical to those at program points 1-8 and can therefore be omitted.

[Discuss-

]

Basic blocks

A basic block is a sequence of tuples containing no transfers of control: All of the tuples are executed, in order, if any of them are executed.

This technique for tracking the values of variables works within a single basic block. It also enables us to implement an arbitrarily complex basic block as one multiple assignment:

[Discuss-

]

Regions larger than a basic block

It is possible to identify several regions larger than a basic block that have useful properties for optimization:
Extended basic block
A maximal tree of code sequences
Strongly-connected region
A collection of program points in which there is a path from every program point to every other program point
Procedure
A collection of program points constituting a unit of abstraction

[Discuss-

]

Tracking variables outside of extended basic blocks

The cornerstone of our analysis of values is our ability to track the values stored in variables. Let's look at the desired result in an extended basic block and then a region that is neither a basic block nor an extended basic block.

Here the source language statements are to the right of the box representing a basic block. The top three boxes, enclosed by the dotted line, form an extended basic block. With the addtion of the fourth basic block, the structure no longer satisfies the definition of an extended basic block.

[Discuss-

]

Static single assignment (SSA)

Use a new symbol for a variable whenever it is assigned or its value becomes unknown because of a join. Here's our example, with the source code altered so that it is SSA form. The phi function expresses the fact that any of the possible values reaching the beginning of the join box could be the value of the new variable. It permits some higher-level analysis of value propagation.

[Discuss-

]

Converting a program to SSA form

Of course the program is not originally written in SSA form, so the compiler must transform it. There are two tasks that must be carried out: For a complete description of the process, see Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM Transactions on Programming Languages and Systems, 13 (1991) 451-490. (Their treatment does not use the standard consistent renaming technique.)

[Discuss-

]

Control flow graph

Here is an example of a control flow graph for complete procedure that illustrates most of the issues. It is slightly modifed from the cited SSA paper.

The numbered nodes represent the code of the procedure. Entry and Exit represent the entry and exit operations of the procedure.

[Discuss-

]

Dominator trees

A node X in the control flow graph dominates a node Y if X lies on all paths from the entry node to Y. The dominance relation is reflexive and transitive. We say that X strictly dominates Y when X dominates Y and the two are different nodes. Strict dominance can be described by a tree. For our example:

See A Fast Algorithm for Finding Dominators in a Flowgraph (ACM Transactions on Programming Languages and Systems 1 (1979) 121-141).

[Discuss-

]

Expansion of basic blocks

We've already seen that all of the assignments made within a basic block can be collected at the end. Also, if there is an assignment due to a phi function, it occurs at the beginning of the basic block. Thus we can regard each node of the dominator tree as consisting of three nodes:

[Discuss-

]

The scope of an assignment

In order to use standard consistent renaming algorithms (see Modularity and Reusability in Attribute Grammars, Acta Informatica, 31(1994) 601-627), we need to identify three roles: An assignment (either in the original program or as the result of a phi function) is a defining occurrence. If a variable is not assigned, its defining occurrence is its first use. If a variable use is not a defining occurrence, it's an applied occurrence. The scope of a defining occurrence is the subtree of the dominator tree rooted in the node containing that defining occurrence, less any subtrees rooted in nodes containing defining occurrences of the same variable.

[Discuss-

]

Example

Let's return to the simple example we used earlier:

Here's the expanded dominator tree:

The dotted box on the right encloses the expansion of the basic block at the bottom of the previous figure to include the assignment to x via the phi function. (Only the non-empty elements of each expansion are shown.)

[Discuss-

]

Dominance frontiers

The dominance frontier DF(X) of a control flow graph node X is the set of all nodes Y such that X dominates a predecessor of Y but does not strictly dominate Y.

If there is an assignment to a variable in node X, then there must be an assignment to that variable via a phi function at every node in DF(X).

Consider a node Y in DF(X)

There is a linear algorithm for computing all dominance frontiers. (See Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM Transactions on Programming Languages and Systems, 13(1991) 451-490.)

[Discuss-

]

Example

The dominance frontier for each node of our sample control flow graph is given next to that node, enclosed in square brackets:

[Discuss-

]

Global value numbering

We can now determine which tuples result in identical values over the entire procedure:

[Discuss-

]


waite@isa.informatik.th-darmstadt.de
Revision $Revision: 1.4 $