Dominators
- A flowgraph G = (V, A, r) is a directed graph with |V| = n vertices and |A| = m edges such that every vertex is reachable from a distinguished root vertex r from V . A vertex w dominates a vertex v if every path from r to v includes w. Our goal is to find the set Dom(v) of all vertices that dominate v for each vertex v from V. Certain applications require computing of the postdominators for G, defined as the dominators in the graph obtained from G by reversing the orientation of each edge.
- A node d strictly dominates a node n if d dominates n and d does not equal n.
- The immediate dominator or idom of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly dominates n.
- The dominance frontier of a node n is the set of all nodes w such that n dominates a predecessor of w, but n does not strictly dominate w.
(DF(S) = sum( x from S) of DF(x)
- A node z post-dominates node n if after going through n, you're always going to go through z.
- A dominator tree is a tree in which each node's children are those nodes that it immediately dominates. As the immediate dominator is unique, it is a tree. The start node is the top of the tree.
- The dominator of the start node is the start node itself. The set of dominators for any other node n is the intersection of the set of dominators for all predecessors p of n. The node n is also in the set of dominators for n.
- Iterated dominance frontier:
( DF+(S) = lim( i->iternity) of DFi(S)) where
DF1(S) = DF(S) DFi+1(S) = DF(S logic+ DFi(S))
EXAMPLES:
