Added to Favorites

Related Searches

Nearby Words

In computer science, in control flow graphs, a node d dominates a node n if every path from the start node to n must go through d. Notationally, this is written as d dom n (or sometimes d $gg$ n). By definition, every node dominates itself.

There are a number of related concepts:

- 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.
- 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 where each node's children are those nodes it immediately dominates. Because the immediate dominator is unique, it is a tree. The start node is the top of the tree.

Dominance was first introduced by Prosser in a 1959 paper on analysis of flow diagrams. Prosser did not present an algorithm for computing dominance, which had to wait ten years for Lowry and Medlock. Ron Cytron rekindled interest in dominance in 1989 when he applied it to efficient computation of φ functions, which are used in static single assignment form.

Dominators, and dominance frontiers particularly, have applications in compilers for computing static single assignment form. A number of compiler optimizations can also benefit from dominators. The flow graph in this case comprises basic blocks.

Automatic parallelization benefits from postdominance frontiers. This is an efficient method of computing control dependence, which is critical to the analysis.

The dominators of a node n are given by the maximal solution to the following data-flow equations:

- $operatorname\{Dom\}(n\_o)\; =\; left\; \{\; n\_o\; right\; \}$

- $operatorname\{Dom\}(n)\; =\; left\; (bigcap\_\{p\; in\; preds(n)\}^\{\}\; operatorname\{Dom\}(p)\; right\; )\; bigcup^\{\}\; left\; \{\; n\; right\; \}$

where $n\_o$ is the start node.

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.

An algorithm for direct solution is:

// dominator of the start node is the start itselfDom(n

// for all other nodes, set all nodes as the dominatorsfor each n in N - {n

Dom(n) = N;

// iteratively eliminate nodes that are not dominators

` while changes in any Dom(n)`

for each n in N - {nDirect solution is quadratic in the number of nodes, or $O(n^2)$. Lengauer and Tarjan developed an algorithm which is almost linear, but its implementation tends to be complex and time consuming for a graph of several hundred nodes or less.

Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy of Rice University describe an algorithm in their paper titled A Simple, Fast Dominance Algorithm It essentially solves the above data flow equations but uses well engineered data structures to improve performance.

See also:

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday September 28, 2008 at 20:53:24 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday September 28, 2008 at 20:53:24 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.