Content deleted Content added
Define dominance frontiers and why they're important and stuff |
|||
Line 55:
==== Computing minimal SSA using dominance frontiers ====
First, we need the concept of a ''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 ''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 -->
Dominance frontiers capture the precise places at which we need φ functions: if the node A defines a certain variable, then that definition and that definition alone will reach every node A dominates. Only when we leave these nodes and enter the dominance frontier must be account for other flows bringing in other definitions of the same variable. Moreover, no other φ functions are needed in the control flow graph to deal with A's definitions; in this sense, the set of nodes we add φ functions to is minimal.
<!-- Describe the algorithm for finding dominance frontiers in the future -->
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
control dependence graph", by R. Cryton, J. Ferrante, B. Rosen, M. Wegman and F. Zadek,
<i>ACM Trans. on Programming Languages and Systems</i> 13(4) 1991
chapter 19 of the book "Modern compiler implementation in Java" by Andrew Appel
(Cambridge University Press, 2002). See the paper for more details.
=== Converting out of SSA form ===
| |||