Editing Static single-assignment form (section)

===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.