Translation to Static Single Assignment (SSA) Form

Dominance Frontiers

The first step of the SSA translation algorithm is to identify the minimal set of convergence points at which trivial phi nodes need to be placed. This is done by computing the dominance frontiers of the nodes in the CFG.

Strict dominance: X strictly dominates Y (written X sdom Y) if X dominates Y and X ≠ Y.

Recall that the dominator relation is reflexive (every node dominates itself), but the strict dominance relation is not reflexive.
We write X !sdom Y to say that X does not strictly dominate Y; this relation is the complement of sdom. For example, B !sdom B always holds; and if B does not dominate C, then B !sdom C.

Dominance Frontier: The dominance frontier of a node X, written DomF(X), is the set of all nodes Y such that:

X does not strictly dominate Y (X !sdom Y), but
X dominates some predecessor P of Y.

DomF(X) = { Y | X !sdom Y  and  X dom P for some P in pred(Y) }

Intuition: if X dominates P and P-->Y is an edge, then there exists a path X-->...-->P-->Y where all the nodes from X to P are dominated by X (because every path from entry to P must go through X, and this includes the paths that go through the intermediate nodes). Y is the first node on this path that is not strictly dominated by X. In other words, look at all outgoing paths from X; on each path, the first node that X does not strictly dominate belongs to the dominance frontier of X. This is why the word frontier is used: it is the boundary at which X's (strict) dominance ends.

A node Z further down the path that is also not strictly dominated by X is not in DomF(X) if none of Z's predecessors are dominated by X.
Y may be dominated by X and yet be in DomF(X), if Y = X. e.g., if X is a loop header, then X may be in its own dominance frontier.

Example

Consider the following CFG (with edges entry-->A):

A --> B, C
B --> D
C --> E
D --> B, F, G
E --> E, G
G --> F

Here, A dominates all nodes; B strictly dominates D; and C strictly dominates E. No other strict dominance relationships exist; e.g., F is not dominated by B because of the path A-->C-->E-->G-->F.

DomF(A) = {}: The only node not strictly dominated by A is A itself, but A's only predecessor is entry, which A does not dominate.
DomF(B) = {B, F, G}:
- D is strictly dominated by B, so D is not in DomF(B).
- F is not strictly dominated by B (path A-->C-->E-->G-->F), but F's predecessor D is dominated by B. Similarly for G.
- B does not strictly dominate itself, but B dominates D, which is a predecessor of B (through the back edge D-->B). So B is in its own dominance frontier.
DomF(C) = {G}: C strictly dominates E, so E is not in the frontier. C does not strictly dominate G, but C dominates E, which is a predecessor of G.
DomF(D) = {B, F, G}: D does not strictly dominate any of its successors B, F, G; and D (which dominates itself) is a predecessor of each of them.
DomF(E) = {E, G}: G is not strictly dominated by E, but its predecessor E is dominated by E. Also, E is not strictly dominated by E, but its predecessor E (through the self-loop E-->E) is dominated by E. Here, X, Y, and P (in the definition) are all the same node E.

Computing Dominance Frontiers

Recap: dominator tree and immediate dominators. In the dominator tree, X dominates Y iff there is a path from X to Y in the tree. X immediately dominates Y (written X idom Y) if X sdom Y and there is no node C such that X sdom C and C sdom Y.

The immediate dominator of a node is unique, as it can be shown that if a node X has two dominators D1 and D2, one of them must dominate the other (or else we will have a path from D1 to X that does not go through D2). Thus, we can treat idom as a function from nodes to nodes: idom(Y) is the parent of Y in the dominator tree. For the example above, the dominator tree is:

A --> B, C, F, G
B --> D
C --> E

i.e., idom(B) = idom(C) = idom(F) = idom(G) = A, idom(D) = B, and idom(E) = C.

We assume that we already have access to the idom relation that has been obtained in near-linear time. Recall that the DFA-based algorithm that we discussed had a quadratic time complexity (it computes all dominators, not just the immediate dominator, and so the output size itself can be quadratic). There exist more efficient algorithms, e.g., Lengauer-Tarjan algorithm.

Some properties follow directly from the tree representation:

If X dom Y, then idom(X) dom Y (if there is a path from X to Y in the tree, there is also one from X's parent to Y).
If X sdom Y, then idom(X) sdom Y.
If X !dom Y (or X !sdom Y), then nothing can be said about whether idom(X) dominates (strictly dominates) Y. e.g., C does not dominate F but idom(C) = A does; whereas E does not dominate F and neither does idom(E) = C.

Naive algorithm: For each node X, perform a depth-first search on the CFG starting at X; on each path, stop at the first node that is not strictly dominated by X and add it to DomF(X). Each DFS takes linear time, and we perform one for each of the N nodes, so the running time is quadratic.

The naive algorithm recomputes each dominance frontier from scratch, even though DomF(X) is related to the dominance frontiers of X's children in the dominator tree. Note that if Y in DomF(X), Y may or may not be in DomF(idom(X)): e.g., F in DomF(B) but F not in DomF(A) (idom(B) = A); whereas F in DomF(D) and also F in DomF(B) (idom(D) = B). We define two relations to capture this.

DomF_up: The nodes in DomF(X) that are "passed up" to DomF(idom(X)):

DomF_up(X) = { Y in DomF(X) | Y in DomF(idom(X)) }
           = { Y in DomF(X) | idom(X) !sdom Y }

To see why the two definitions are equivalent: if Y in DomF(X), then X dominates some predecessor P of Y, so idom(X) also dominates P. Thus, if idom(X) !sdom Y, then Y in DomF(idom(X)) by definition. (The converse is similar.) The second form is easy to check: given DomF(X), keep only the nodes not strictly dominated by X's parent.

DomF_up(E) = {G}: DomF(E) = {E, G}; idom(E) = C strictly dominates E but not G.
DomF_up(D) = {B, F, G}: DomF(D) = {B, F, G}; idom(D) = B strictly dominates none of these (B dominates B, but does not strictly dominate it).

DomF_local: The nodes in DomF(X) that are immediate successors of X in the CFG:

DomF_local(X) = { Y in succ(X) | Y in DomF(X) }
              = { Y in succ(X) | X !sdom Y }

To see why: if Y is a successor of X and X !sdom Y, then X dominates a predecessor of Y (namely X itself, as dominance is reflexive), so Y in DomF(X).

DomF_local(B) = {}: B's only successor D is strictly dominated by B. (Recall DomF(B) = {B, F, G}, but none of these are immediate successors of B.)
DomF_local(D) = {B, F, G}: all three successors are not strictly dominated by D.
DomF_local(E) = {E, G}.

Theorem:

DomF(X) = DomF_local(X)  ∪  ∪_{Z in children(X)} DomF_up(Z)

where children(X) are the children of X in the dominator tree (and succ(X) in DomF_local refers to successors in the CFG). Intuitively, a node in X's dominance frontier is either an immediate successor of X that X does not strictly dominate, or is passed up from the dominance frontier of a node immediately dominated by X. In terms of the naive algorithm: the DFS from X either stops at the very first step (an immediate successor), or proceeds through a node strictly dominated by X, and so through one of X's children in the dominator tree.

DomF(A): DomF_local(A) = {} as both successors B and C are strictly dominated by A. A's children in the dominator tree are B, C, F, G; nothing in their dominance frontiers is passed up, because A strictly dominates every node other than itself. So DomF(A) = {}.
DomF(B): DomF_local(B) = {}; B's only child in the dominator tree is D, and DomF_up(D) = {B, F, G}. So DomF(B) = {B, F, G}.

Algorithm: Compute the dominance frontiers in a single bottom-up traversal of the dominator tree, so that the dominance frontiers of X's children are available when computing DomF(X):

for each X in a bottom-up traversal of the dominator tree:
  DF(X) := {}
  for each Y in succ(X):              // DomF_local
    if idom(Y) ≠ X:
      DF(X) := DF(X) ∪ {Y}
  for each Z in children(X):          // DomF_up
    for each Y in DF(Z):
      if idom(Y) ≠ X:
        DF(X) := DF(X) ∪ {Y}

The check X !sdom Y reduces to idom(Y) ≠ X in both loops:

In the local loop, Y is a CFG successor of X, so if X strictly dominates Y, X must be Y's immediate dominator (any node strictly between X and Y in the dominator tree would have to lie on the edge X-->Y).
In the up loop, Y is in the dominance frontier of a child Z of X; if X strictly dominates Y, then (since Z does not strictly dominate Y) X must be Y's immediate dominator.
- If X is not Y's immediate dominator, there must exist another node L that is Y's immediate dominator. L must then be dominated by X. Also, L must dominate Z, but then that is a contradiction, as X was Z's immediate dominator. Thus, no such L can exist; and so X must be Y's immediate dominator, if X dominates Y.

For example, DF(D) and DF(E) are computed first; then DF(B) reuses DF(D), DF(C) reuses DF(E), and DF(A) reuses the dominance frontiers of B, C, F, and G.

Running time:

The local loop examines each outgoing edge of each node exactly once: O(E) in total.
The up loop iterates over each child Z of each node X (N children in total, as this is a tree), and for each child, over DF(Z): O(∑_X |DF(X)|) in total.

So the total running time is O(E + ∑_X |DF(X)|). If dominance frontiers are small (e.g., constant-sized), this is linear in the size of the CFG. However, a single dominance frontier can be as large as N, so in the worst case this can still be quadratic. However, if the output size is smaller (e.g., linear), then the running time is also smaller --- the running time is proportional to the output size (which is the best any algorithm can do any way). We characterize ∑_X |DF(X)| in more detail later.

Placing Phi Nodes

The second step of the SSA translation is the placement of trivial phi nodes. Consider an assignment v := ... at node X, and let Y in DomF(X). Because Y is not strictly dominated by X, there must be another path to Y on which a different definition of v potentially reaches Y; this other definition is either another assignment to v, or the initial value of v at program entry. In either case, a phi node for v is needed at Y.

We stage the placement of phi nodes in two steps:

Place a trivial phi node v := φ(v, v, ..., v) at Y, where the number of arguments is the number of incoming edges of Y. This is effectively a no-op instruction.
Later, rename the variables so that the program is in SSA form.

Placing phi nodes only at the dominance frontiers satisfies the requirement for minimal SSA.

Some observations:

Transitivity: A phi node placed at Y is itself an assignment to v. So if Z in DomF(Y), then a phi node for v must also be placed at Z, and so on, until all phi nodes required by this transitive dominance-frontier relationship have been placed.
At most one phi node per variable per node: A phi node sits at the beginning of a basic block, and a block needs at most one phi node for each variable. e.g., if Z is in both DomF(X) and DomF(Y), only one phi node for v is placed at Z.

Per-variable: Phi nodes are placed separately and independently for each variable:

placePhis(P):
  for each variable v in P:
    P := placePhisForVar(P, v)
  return P

Algorithm: placePhisForVar(P, v) maintains three sets (represented as maps from nodes to booleans):

W (worklist): nodes whose DomF needs to be examined. It may shrink (when a node is picked) and grow (when a phi node is added).
consideredAlready: nodes that have ever been in the worklist. It only grows. A node's DomF needs to be examined at most once.
hasAlready: nodes that already have a phi node for v, to avoid placing duplicate phi nodes.

placePhisForVar(P, v):
  W := nodes with assignments to v
  consideredAlready := W
  hasAlready := {}
  while W ≠ {}:
    take X from W                         // W[X] := false
    for each Y in DomF(X):
      if Y not in hasAlready:
        place trivial phi node v := φ(v, ..., v) at Y
        hasAlready := hasAlready ∪ {Y}
        if Y not in consideredAlready:    // transitive step
          W := W ∪ {Y}
          consideredAlready := consideredAlready ∪ {Y}

Pruned SSA: Recall that pruned SSA additionally requires that a phi node for v is placed at Y only if v is live at Y (i.e., v may be used downstream). The algorithm above can be adapted to pruned SSA by additionally checking whether v is live at Y before placing the phi node. The liveness analysis can be run a priori, and only needs to be conservative; the more precise the liveness analysis, the more phi nodes may be eliminated.

Example

Draw the CFG and convert to SSA for the following program.

i = 0
do {
  i++;
} while (i < n);
return i;

Running Time of Phi Placement

Define:

A_orig(X): the number of original assignments in basic block X; A_orig = ∑_X A_orig(X).
A_φ(X): the number of assignments added due to phi nodes in X.
A_final(X) = A_orig(X) + A_φ(X); A_final = ∑_X A_final(X).

The number of phi nodes added to a single basic block can be as large as A_orig (e.g., all assignments in all other blocks may need a phi node in this block). So A_orig(X) ≤ A_final(X) ≤ ~A_orig. Summing over all basic blocks (whose number is roughly proportional to A_orig):

A_orig  ≤  A_final  ≤  ~A_orig²

i.e., the total number of final assignments can be quadratic in the number of original assignments.

Across all variables, the statement take X from W executes (at most) A_final times, as nodes with phi nodes added by the algorithm are also added to the worklist. Each time, the inner loop executes |DomF(X)| times. So the total work is:

∑_X A_final(X) × |DomF(X)|  =  A_final × (weighted average DomF size)

where the average of |DomF(X)| is weighted by the number of assignments A_final(X) in X.

A_final is between linear and quadratic in the size of the original program.
The weighted average DomF size is between constant and linear (it can be as large as the number of basic blocks).

So the overall running time is between linear and cubic. We will characterize when this is linear (as is typical in practice) later.

Versioning Variables

The third (and final) step of the SSA translation is to rename the mentions of each variable, so that every variable version is assigned at most once in the static text of the program. At this point, the trivial phi nodes have already been placed; the user definitions (e.g., a := b + c) and the phi nodes are both processed in the same traversal.

Idea: Perform a depth-first search (DFS) traversal of the CFG. During the traversal, keep track of the current version of each variable in a map vmap:

If a variable is used in the current node, rename that use with the variable's current version.
If a variable is assigned in the current node, give the assigned variable a new version, which becomes the current version for the subsequent instructions.

Like any DFS, a visited set ensures that every node is visited at most once.

Algorithm:

vmap := { v → 0 for each variable v }     // every variable starts at version 0
DFS(entry, vmap)

DFS(n, vmap):
  visited := visited ∪ {n}
  rename n's variables using vmap:
    for each instruction in n (in order), e.g., a := b + c:
      rename the non-phi uses (b, c) with their current versions in vmap   // e.g., b0, c3
      for the assigned variable a (also for phi nodes at the start of n):
        give a a new version using a global map from variable to assignment-versions, e.g., a4, and set vmap[a] := 4
  vmap' := vmap after all the assignments in n   // copy of vmap with versions of
                                                  // variables modified in n incremented
  for each successor s of n:
    if s contains phi nodes:
      for each phi node v := φ(..., v, ...) in s:
        rename only the argument corresponding to the edge n-->s, using vmap'
    if s not in visited:
      DFS(s, vmap')

Note: vmap is passed by value, i.e., each DFS call gets its own copy of the current versions along its DFS path. However, the new versions must be fresh across the entire program, not just along the current path: e.g., if two sibling nodes B and C both assign to a and both start with vmap[a] = 0, simply incrementing vmap[a] would produce a1 in both B and C. So, in an implementation, the new version number is drawn from a global map (another per-variable counter) as shown in the algorithm, while vmap records which version is current on the path being traversed. Notice the slight twist for phi nodes: when visiting n, we do not rename the phi uses (arguments) in n itself; instead, we rename the phi arguments in n's successors that correspond to the incoming edge from n. Recall that a trivial phi node at s has one argument per incoming edge of s; exactly one of these corresponds to the edge n-->s, and the value flowing along this edge is given by vmap', the map after all the assignments in n have been completed. Because every edge n-->s is examined when n is visited (whether or not s has already been visited), all phi arguments are eventually renamed.

Notice that the version obtained from DFS is correct because we have already placed PHI nodes where there could have been a conflict. Consider a use of v at node Y without a phi node for v, and let the last definition of v on the DFS path to Y be at node Z. If Z did not dominate Y, then Y is reachable from Z without Z strictly dominating it, and so some node between Z and Y on this path would be in the (iterated) dominance frontier of Z, and would thus contain a phi node for v, which is a later definition on the path; a contradiction. So the last definition on the DFS path dominates Y, and is the unique definition that reaches Y along every path.

The DFS visits every node at most once, and examines every edge once, so the number of DFS steps is O(V + E), where V and E are the number of nodes and edges of the CFG.

Running Time of Versioning

Counting DFS steps is not enough, as each step may perform a non-constant amount of work (renaming all mentions in a basic block). So we count the number of mentions of variables, where a mention is either a use or a def of a variable.

M_orig(X): the number of mentions in basic block X in the original program; M_orig = ∑_X M_orig(X). Because the original program is in three-address code, each instruction has only a constant number (two or three) of mentions, so M_orig is proportional to the size of the program n.
M_φ(X): the number of mentions due to the newly-added phi nodes in X. For each new phi assignment a := φ(a, a, ..., a) added to X, M_φ(X) += indegree(X), as the phi function has one argument per incoming edge of X.
M_final(X) = M_orig(X) + M_φ(X); M_final = ∑_X M_final(X).

How large can M_final be?

As discussed earlier, the number of new phi assignments can be up to O(n²), where n is the number of assignments in the original program: up to O(n) different variables may reach a basic block with different versions on different incoming edges, each requiring a separate phi node; and there are O(n) basic blocks. Typically, however, the number of new assignments is linear in n.
The in-degree of a node is typically O(1) (e.g., two), but in the worst case can be O(n).

Multiplying the number of new assignments (n to n²) with the in-degree (1 to n), M_final is between O(n) (typical) and O(n³) (worst case). This blow-up is possible because a phi instruction, unlike a three-address instruction, can have more than a constant (up to O(n)) number of mentions.

The versioning step looks at each mention once and renames it, so its running time is O(M_final), i.e., between O(n) and O(n³).

Overall Running Time of Translation to SSA

Step	Running time	Typical	Worst case
1. Computing dominance frontiers	`O(E + ∑_X \|DomF(X)\|)`, i.e., (E + V) × average DomF size	`O(n)`	`O(n²)`
2. Placing phi nodes	`A_final` × (weighted average DomF size)	`O(n)`	`O(n³)`
3. Versioning variables	`O(M_final)`	`O(n)`	`O(n³)`

Here, E and V are O(n); the dominance frontier of a node can be between constant and O(n) in size; and A_final is between n and n².

When is the Translation Linear?

There is a large gap between the typical case (linear) and the worst case (cubic). To get a sense of when each occurs:

Theorem: If a program contains only if-then-else and while-do loops (i.e., while (cond) { body }), then |DomF(X)| ≤ 2 for every node X.

The proof is out of scope for our discussion (see the original paper: Cytron, Ferrante, Rosen, Wegman, and Zadeck, Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, TOPLAS 1991). Some examples:

if-then-else: A --> T, F; T --> J; F --> J. Here, DomF(T) = DomF(F) = {J} and DomF(A) = DomF(J) = {}.
while-do: H --> B, X; B --> H, where H is the loop header that evaluates the condition, B is the loop body, and X is the exit. Here, DomF(H) = DomF(B) = {H}.
A while-do loop inside the then-branch of an if-then-else: A --> H, F; H --> B, J; B --> H; F --> J. Here, DomF(H) = {H, J}: H dominates B, a predecessor of H; and H dominates itself, a predecessor of J, but does not strictly dominate J. This is the maximum size (two).

Thus, for such programs, the average dominance frontier size is at most two, and so the first step takes linear time; the second step also takes roughly linear time, and so on.

Repeat-until (do-while) loops: In the real world, programs also have repeat-until or do-while loops. Here, the loop header does not have two branches (it has a single successor); instead, the node at the end of the loop body (the source of the back edge) has two outgoing branches: the back edge and the loop exit. With such loops, the size of the dominance frontier of a node can be as high as O(n).

Example: three nested do-while loops with loop headers A (outermost), B, and C (innermost):

A --> B
B --> C
C --> D
D --> C, E     // innermost loop: back edge D-->C
E --> B, F     // middle loop: back edge E-->B
F --> A, G     // outer loop: back edge F-->A

Every node is dominated by all the nodes before it (the dominator tree is the chain A, B, C, D, E, F, G). Computing bottom-up:

DomF(F) = {A}: F does not strictly dominate A, and F is a predecessor of A. (G is strictly dominated by F.)
DomF(E) = DomF_local(E) ∪ DomF_up(F) = {B} ∪ {A} = {A, B}.
DomF(D) = DomF_local(D) ∪ DomF_up(E) = {C} ∪ {A, B} = {A, B, C}.

In general, for a loop nest of depth k, the dominance frontier of a node (here, the end of the innermost loop body) can be as large as k, which can in turn be as large as O(n). So, in pathological cases, translation to SSA can become quadratic, or in the worst case, cubic.

Why not simply disallow repeat-until and do-while loops in the language? That is not a solution, because compiler transformations themselves often convert while-do loops into do-while loops: e.g., loop inversion converts a while-do loop into a guarded repeat-until loop (other examples include loop unrolling and loop splitting). A typical compiler maintains the program in SSA form across such transformations, so even if the original program contains only while-do loops, the intermediate programs in the transformation pipeline will contain do-while loops, and the bound of two on the dominance frontier size no longer holds.

However, the pathological cases where the dominance frontiers are large arise only when loop nests are very deep, which is not typically the case. Hence, in practice, this is not a big problem, and the translation to SSA algorithm discussed here is commonly used.