Static single-assignment form: Difference between revisions

Revision as of 19:07, 20 April 2005

Revision as of 16:10, 21 April 2005

Line 57:

First, we need the concept of a [[dominator|''dominator'']]: we say that a node A ''strictly dominates'' a different node B in the control flow graph if it's impossible to reach B without passing through A first. This is useful, because if we ever reach B we know that any code in A has run. We say that A ''dominates'' B if either A strictly dominates B or A = B.

Now we can define the [[dominator|''dominance frontier'']]: the dominance frontier of a node A is the set of nodes that A does ''not'' strictly dominate, but does dominate some immediate precessor of. From A's point of view, these are the nodes at which other control paths that don't go through A make their earliest appearance.

<!-- Need an example -->

Line 64:

<!-- Describe the algorithm for finding dominance frontiers in the future -->

One algorithm for computing the dominance frontier set is

for all nodes, b

if the number of predecessors of b >= 2

for all predecessors, p, of b

runner = p

while runner != doms(b)

add b to runner’s dominance frontier set

runner = doms(runner)

There is an efficient algorithm for finding dominance frontiers of each node. This algorithm was originally described in the paper "Efficiently computing static single assignment form and the

Line 71 ⟶ 81:

(Cambridge University Press, 2002). See the paper for more details.

Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy of [[Rice University]] describe an algorithm in their paper titled [http://www.hipersoft.rice.edu/grads/publications/dom14.pdf ''A Simple, Fast Dominance Algorithm'']. The algorithm achievesuses goodwell performanceengineered fordata typicalstructures controlto flowimprove graphs encountered in practiceperformance.

== Converting out of SSA form ==