Editing Static single-assignment form (section)

==Converting to SSA==
Converting ordinary code into SSA form is primarily a matter of replacing the target of each assignment with a new variable, and replacing each use of a variable with the "version" of the variable [[reaching definition|reaching]] that point. For example, consider the following [[control-flow graph]]:

[[Image:SSA example1.1.png|An example control-flow graph, before conversion to SSA|center]]

Changing the name on the left hand side of "x <math>\leftarrow</math> x - 3" and changing the following uses of <var>x</var> to that new name would leave the program unaltered. This can be exploited in SSA by creating two new variables: <var>x</var><sub>1</sub> and <var>x</var><sub>2</sub>, each of which is assigned only once. Likewise, giving distinguishing subscripts to all the other variables yields:

[[Image:SSA example1.2.png|An example control-flow graph, partially converted to SSA|center]]

It is clear which definition each use is referring to, except for one case: both uses of <var>y</var> in the bottom block could be referring to either <var>y</var><sub>1</sub> or <var>y</var><sub>2</sub>, depending on which path the control flow took.

To resolve this, a special statement is inserted in the last block, called a ''Φ (Phi) function''. This statement will generate a new definition of ''y'' called <var>y</var><sub>3</sub> by "choosing" either <var>y</var><sub>1</sub> or <var>y</var><sub>2</sub>, depending on the control flow in the past.

[[Image:SSA example1.3.png|An example control-flow graph, fully converted to SSA|center]]

Now, the last block can simply use <var>y</var><sub>3</sub>, and the correct value will be obtained either way. A Φ function for ''x'' is not needed: only one version of <var>x</var>, namely <var>x</var><sub>2</sub> is reaching this place, so there is no problem (in other words, Φ(<var>x</var><sub>2</sub>,<var>x</var><sub>2</sub>)=<var>x</var><sub>2</sub>).

Given an arbitrary control-flow graph, it can be difficult to tell where to insert Φ functions, and for which variables. This general question has an efficient solution that can be computed using a concept called ''dominance frontiers'' (see below).

Φ functions are not implemented as machine operations on most machines. A compiler can implement a Φ function by inserting "move" operations at the end of every predecessor block. In the example above, the compiler might insert a move from <var>y</var><sub>1</sub> to <var>y</var><sub>3</sub> at the end of the middle-left block and a move from <var>y</var><sub>2</sub> to <var>y</var><sub>3</sub> at the end of the middle-right block. These move operations might not end up in the final code based on the compiler's [[register allocation]] procedure. However, this approach may not work when simultaneous operations are speculatively producing inputs to a Φ function, as can happen on [[wide-issue]] machines. Typically, a wide-issue machine has a selection instruction used in such situations by the compiler to implement the Φ function.

===Computing minimal SSA using dominance frontiers===
In a control-flow graph, a node A is said to ''{{dfn|strictly [[dominator (graph theory)|dominate]]}}'' a different node B if it is impossible to reach B without passing through A first. In other words, if node B is reached, then it can be assumed that A has run. A is said to ''dominate'' B (or B to ''be dominated by'' A) if either A strictly dominates B or A = B.

A node which transfers control to a node A is called an ''{{dfn|immediate predecessor}}'' of A.

The ''{{dfn|dominance frontier}}'' of node A is the set of nodes B where A {{em|does not}} strictly dominate B, but does dominate some immediate predecessor of B. These are the points at which multiple control paths merge back together into a single path.

For example, in the following code:

<pre>
[1] x = random()
if x < 0.5
    [2] result = "heads"
else
    [3] result = "tails"
end
[4] print(result)
</pre>

Node 1 strictly dominates 2, 3, and 4 and the immediate predecessors of node 4 are nodes 2 and 3.

Dominance frontiers define the points at which Φ functions are needed. In the above example, when control is passed to node 4, the definition of <code>result</code> used depends on whether control was passed from node 2 or 3. Φ functions are not needed for variables defined in a dominator, as there is only one possible definition that can apply.

There is an efficient algorithm for finding dominance frontiers of each node. This algorithm was originally described in "Efficiently Computing Static Single Assignment Form and the Control Graph" by Ron Cytron, Jeanne Ferrante, et al. in 1991.<ref>{{cite journal |last1=Cytron |first1=Ron |last2=Ferrante |first2=Jeanne |last3=Rosen |first3=Barry K. |last4=Wegman |first4=Mark N. |last5=Zadeck |first5=F. Kenneth |title=Efficiently computing static single assignment form and the control dependence graph |journal=ACM Transactions on Programming Languages and Systems |date=1 October 1991 |volume=13 |issue=4 |pages=451–490 |doi=10.1145/115372.115320|s2cid=13243943 |doi-access=free }}</ref>

Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy of [[Rice University]] describe an algorithm in their paper titled ''A Simple, Fast Dominance Algorithm'':<ref name="Cooper_2001">{{cite tech report 
|title=A Simple, Fast Dominance Algorithm |id=Rice University, CS Technical Report 06-33870
|last1=Cooper |first1=Keith D. |last2=Harvey |first2=Timothy J. |last3=Kennedy |first3=Ken  |year=2001 |url=https://www.cs.rice.edu/~keith/EMBED/dom.pdf |archive-url=https://web.archive.org/web/20220326234549/https://www.cs.rice.edu/~keith/EMBED/dom.pdf |archive-date=2022-03-26 |url-status=dead}}</ref>

 '''for each''' node b
     dominance_frontier(b) := {}
 '''for each''' node b
     '''if''' the number of immediate predecessors of b ≥ 2
         '''for each''' p '''in''' immediate predecessors of b
             runner := p
             '''while''' runner ≠ idom(b)
                 dominance_frontier(runner) := dominance_frontier(runner) ∪ { b }
                 runner := idom(runner)

In the code above, <code>idom(b)</code> is the ''{{dfn|immediate dominator}}'' of b, the unique node that strictly dominates b but does not strictly dominate any other node that strictly dominates b.