8. Dominator-Based Optimization

Previous

Table of Contents

Next

Chapter 7
Static Single Assignment

Many optimization algorithms need to know the relationships between uses of temporaries (or variables) and the points where they are evaluated. Each of the algorithms needs to know either the set of points in the flow graph where the value computed by an instruction is used or the set of evaluations whose values might be used at this point in the flow graph. The static single assignment (SSA) form is a compact representation of these facts.¹

---

¹An alternative technique called USE-DEF chains can also be used. It frequently requires more space and time to compute and is harder to incrementally update.

---

Definition	Static Single Assignment Form: The flow graph is in static single assignment form if each temporary is the target in a single instruction.

The definition of static single assignment is so restrictive that most programs cannot be translated into SSA form. Consider the left flow graph in Figure 7.1. There are two assignments to the variable X: one outside the loop and one incrementing X inside the loop. There is no way to put X into SSA form without the introduction of a new operator.

To ensure that all program flow graphs can be put in SSA form, another special instruction, called a φ-node, is added to the definition of static single assignment form.

Definition	φ-node: Consider a block B in the flow graph with predecessors {P1, P2, ..., Pn}, where n > 1.A φ-node T0 = φ(T1, T2, ..., Tn) in B is an instruction that gives T0 the value that Ti contains on entrance to B if the execution path leading to B traverses the block Pi as the predecessor of B on the path. The set of φ-nodes in B is denoted by Φ(B).

Figure 7.1  Graph (left) and SSA Graph Equivalent (right)

Consider the program flow on the right graph in Figure 7.1. This graph is equivalent to the one on the left (it computes the same values) and is in SSA form. The variable X has been replaced by four variables (X₀, X₁, X₂, X₃) and two φ-nodes that indicate the points in the program reached by multiple definitions of X. One of the φ-nodes is at the beginning of the loop because there is a modification of X inside the loop and it is initialized outside the loop. The other φ-node occurs at the merge of two paths through the loop, where only one path contains a definition of X.

A flow graph in SSA form is interpreted in the same way as a normal program flow graph, with the addition φ-nodes. Consider a path from Entry to exit:

•  Each normal instruction is evaluated in order, recording the results of each instruction so that these values can be used in the evaluation of later instructions on the path.

•  All φ-nodes at the beginning of a block are evaluated simultaneously on entrance to the block. The value of target temporary T₀ is T_i if the path came to the φ-node through the ith predecessor of the block.

The next two sections describe the fundamental operations of translating a flow graph into and out of static single assignment form. Two areas that are typically overlooked in the literature are emphasized: the simultaneous evaluation of φ-nodes at the beginning of a block, and the handling of abnormal edges in the flow graph.

7.1 Creating Static Single Assignment Form

The algorithm for translating the flow graph into static single assignment form treats each temporary independently. In fact, one could partially translate the flow graph leaving some temporaries in normal form and some in SSA form. This compiler does not. The translation takes place in two steps:

1.  Determine the points in the program where φ-nodes are inserted. In Figure 7.1, there are two points. Insert the φ-nodes with the left-hand operand and all right-hand operands being the same value. In Figure 7.1, there would be two insertions of the form X = φ(X,X).

2.  Rename the temporaries so that each instruction and φ-node having X as a target is given a new, unique name.

Where are φ-nodes needed? Consider a single temporary or variable T and a block B. A φ-node is needed at the beginning of B if B has multiple predecessors and different definitions of T occur on distinct paths going through at least two predecessors. This leads to the definition of converging paths.²

---

²Computing these points is not intuitive; thus, we now descend to a theoretical discussion. A more intuitive algorithm was used in an earlier form of static single assignment called p-graphs. P-graphs had all of the characteristics of static single assignment; however, computing the points for the insertion of the birth points was quadratic to the size of the graph, so was not practical in most compilers.

---

Definition	Converging Paths: Two non-null paths, p from B0 to Bn and q from to , converge at a block Z if and only if
	; in other words, the paths start at different points
	; in other words, both paths end at Z.
	If then either i = n or j = m; in other words, the only point on the paths that is in common is the end point. Note that one of the paths may loop through Z and come back to it.

Previous

Table of Contents

Next