CONVERTING TO SSA FORM

The algorithm for converting a program to SSA form first adds φ-functions for the variables, then renames all the definitions and uses of variables using subscripts. The sequence of steps is illustrated in Image 19.4.

CRITERIA FOR INSERTING φ-FUNCTIONS

We could add a φ-function for every variable at each join point (that is, each node in the control-flow graph with more than one predecessor). But this is wasteful and unnecessary. For example, block 4 in Image 19.2b is reached by the same definition of b along each incoming edge, so it does not need a φ-function for b. The following criterion characterizes the nodes where a variable's dataflow paths merge: Path-convergence criterion There should be a φ-function for variable a at node z of the flow graph exactly when all of the following are true:

1. There is a block x containing a definition of a,

2. There is a block y (with y ≠ x) containing a definition of a,
3. There is a nonempty path P_xz of edges from x to z,
4. There is a nonempty path Pyz of edges from y to z,
5. Paths P_xz and Pyz do not have any node in common other than z, and
6. The node z does not appear within both P_xz and P_yz prior to the end, though it may appear in one or the other.

We consider the start node to contain an implicit definition of every variable, either because the variable may be a formal parameter or to represent the notion of a ← uninitialized without special cases. Note, however, that a φ-function itself counts as a definition of a, so the path-convergence criterion must be considered as a set of equations to be satisfied. As usual, we can solve them by iteration. Iterated path-convergence criterion:

while there are nodes x, y, z satisfying conditions 1-5
 and z does not contain a φ-function for a
 do insert a ← φ(a, a,..., a) at node Z

where the φ-function has as many a arguments as there are predecessors of node z. Dominance property of SSA form An essential property of static single assignment form is that definitions dominate uses; more specifically,

1. If x is the ith argument of a φ-function in block n, then the definition of x dominates the ith predecessor of n.

2. If x is used in a non-φ statement in block n, then the definition of x dominates node n.

defines the dominance relation: d dominates n if every path from the start node to n goes through d.

THE DOMINANCE FRONTIER

The iterated path-convergence algorithm for placing φ-functions is not practical, since it would be very costly to examine every triple of nodes x, y, z and every path leading from x and y. A much more efficient algorithm uses the dominator tree of the flow graph. Definitions x strictly dominates w if x dominates w and x ≠ w. In this chapter we use successor and predecessor to refer to graph edges, and parent and child to refer to tree edges. Node x is an ancestor of y if there is a path x → y of tree edges, and is a proper ancestor if that path is nonempty. The dominance frontier of a node x is the set of all nodes w such that x dominates a predecessor of w, but does not strictly dominate w. Image 19.5a illustrates the dominance frontier of a node; in essence, it is the "border" between dominated and undominated nodes.

Dominance frontier criterion Whenever node x contains a definition of some variable a, then any node z in the dominance frontier of x needs a φ-function for a. Iterated dominance frontier. Since a φ-function itself is a kind of definition, we must iterate the dominance-frontier criterion until there are no nodes that need φ-functions. Theorem The iterated dominance frontier criterion and the iterated pathconvergence criterion specify exactly the same set of nodes at which to put φ-functions. The end-of-chapter bibliographic notes refer to a proof of this theorem. We will sketch one half of the proof, showing that if w is in the dominance frontier of a definition, then it must be a point of convergence. Suppose there is a definition of variable a at some node n (such as node 5 in Image 19.5b), and node w (such as node 12 in Image 19.5b) is in the dominance frontier of n. The root node implicitly contains a definition of every variable, including a. There is a path P_rw from the root node (node 1 in Image 19.5) to w that does not go through n or through any node that n dominates; and there is a path P_nw from n to w that goes only through dominated nodes. These paths have w as their first point of convergence. Computing the dominance frontier To insert all the necessary φ-functions, for every node n in the flowgraph we need DF[n], its dominance frontier. Given the dominator tree, we can efficiently compute the dominance frontiers of all the nodes of the flowgraph in one pass. We define two auxiliary sets DF_local[n]: The successors of n that are not strictly dominated by n; DF_up[n]: Nodes in the dominance frontier of n that are not strictly dominated by n's immediate dominator. The dominance frontier of n can be computed from DF_local and DF_up:

where children[n] are the nodes whose immediate dominator (idom)is n. To compute DF_local[n] more easily (using immediate dominators instead of dominators), we use the following theorem: DFlocal[n] = the set of those successors of n whose immediate dominator is not n. The following computeDF function should be called on the root of the dominator tree (the start node of the flowgraph). It walks the tree computing DF[n] for every node n: It computes DF_local[n] by examining the successors of n, then combines DF_local[n] and (for each child c) DF_up[c].

computeDF[n] =
 S ← {}
 for each node y in succ[n] This loop computes DFlocal[n]
 if idom(y) ≠ n
 S ← S ∪ {y}
 for each child c of n in the dominator tree
 computeDF[c]
 for each element w of DF[c] This loop computes DFup[c]
 if n does not dominate w, or if n = w
 S ← S ∪ {w}
 DF[n] S

This algorithm is quite efficient. It does work proportional to the size (number of edges) of the original graph, plus the size of the dominance frontiers it computes. Although there are pathological graphs in which most of the nodes have very large dominance frontiers, in most cases the total size of all the DFs is approximately linear in the size of the graph, so this algorithm runs in "practically" linear time.

INSERTING φ-FUNCTIONS

Starting with a program not in SSA form, we need to insert just enough φ-functions to satisfy the iterated dominance frontier criterion. To avoid reexamining nodes where no φ-function has been inserted, we use a work-list algorithm. Algorithm 19.6 starts with a set V of variables, a graph G of control-flow nodes - each node is a basic block of statements - and for each node n aset A_orig[n] of variables defined in node n. The algorithm computes A_φ[a], the set of nodes that must have φ-functions for variable a. Sometimes a node may contain both an ordinary definition and a φ-function for the same variable; for example, in Image 19.3b, a∉ A_orig[2] and 2∉ A_φ[a].

Place-φ-Functions =
 for each node n
 for each variable a in Aorig[n]
 defsites[a] ← defsites[a] ∪{n}
 for each variable a
 W ← defsites[a]
 while W not empty
 remove some node n from W
 for each y in DF[n]
 if a ∉ Aφ[y]
 insert the statement a ← φ(a, a,..., a) at the top
 of block y, where the φ-function has as many
 arguments as y has predecessors
 Aφ[Y] ← Aφ[Y] ∪ {a}
 if a∉ Aorig[y]
 W ← W ∪ {y}

The outer loop is performed once for each variable a. There is a work list W of nodes that might violate the dominance-frontier criterion. The representation for W must allow quick testing of membership and quick extraction of an element. Work-list algorithms (in general) do not care which element of the list they remove, so an array or linked list of nodes suffices. To quickly test membership in W, we can use a mark bit in the representation of every node n which is set to true when n is put into the list, and false when n is removed. If it is undesirable to modify the node representation, a list plus a hash table will also work efficiently.

This algorithm does a constant amount of work (a) for each node and edge in the control-flow graph, (b) for each statement in the program, (c) for each element of every dominance frontier, and (d) for each inserted φ-function. For a program of size N, the amounts a and b are proportional to N, c is usually approximately linear in N. The number of inserted φ-functions (d)² in the worst case, but empirical measurement has shown that it is usually proportional to N. So in practice, Algorithm 19.6 runs in approximately linear time.

RENAMING THE VARIABLES

After the φ-functions are placed, we can walk the dominator tree, renaming the different definitions (including φ-functions) of variable a to a₁, a₂, a₃, and so on. In a straight-line program, we would rename all the definitions of a, and then each use of a is renamed to use the most recent definition of a. For a program with control-flow branches and joins whose graph satisfies the dominance-frontier criterion, we rename each use of a to use the closest definition d of a that is above a in the dominator tree. Algorithm 19.7 renames all uses and definitions of variables, after the φ-functions have been inserted by Algorithm 19.6. In traversing the dominator tree, the algorithm "remembers" for each variable the most recently defined version of each variable, on a separate stack for each variable.

Initialization:
 for each variable a
 Count[a] ← 0
 Stack[a] ← empty
 push 0 onto Stack[a]
Rename(n) =
 for each statement S in block n
 if S is not a φ-function
 for each use of some variable x in S
 i ← top(Stack[x])
 replace the use of x with xi in S
 for each definition of some variable a in S
 Count[a] ← Count[a] + 1
 i ← Count[a]
 push i onto Stack[a]
 replace definition of a with definition of ai in S
 for each successor Y of block n,
 Suppose n is the jth predecessor of Y
 for each φ-function in Y
 suppose the jth operand of the φ-function is a
 i ← top(Stack[a])
 replace the jth operand with ai
 for each child X of n
 Rename(X)
 for each statement S in block n
 for each definition of some variable a in S
 pop Stack[a]

Although the algorithm follows the structure of the dominator tree - not the flowgraph - at each node in the tree it examines all outgoing flow edges, to seeifthereareany φ-functions whose operands need to be properly numbered.

This algorithm takes time proportional to the size of the program (after φ-functions are inserted), so in practice it should be approximately linear in the size of the original program.

EDGE SPLITTING

Some analyses and transformations are simpler if there is never a control-flow edge that leads from a node with multiple successors to a node with multiple predecessors. To give the graph this unique successor or predecessor property, we perform the following transformation: For each control-flow edge a → b such that a has more than one successor and b has more than one predecessor, we create a new, empty control-flow node z, and replace the a → b edge with an a → z edge and a z → b edge.

An SSA graph with this property is in edge-split SSA form. Image 19.2 illustrates edge splitting. Edge splitting may be done before or after insertion of φ-functions.

JaVa	Previous    Next