Dominator (graph theory)

Dominator (graph theory)

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. Not all nodes have immediate dominators (e.g. entry nodes).
  • The dominance frontier of a node d is the set of all nodes n such that d dominates an immediate predecessor of n, but d does not strictly dominate n. It is the set of nodes where d's dominance stops.
  • 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 root of the tree.

Contents

History

Dominance was first introduced by Reese T. Prosser in a 1959 paper on analysis of flow diagrams.[1] Prosser did not present an algorithm for computing dominance, which had to wait ten years for Edward S. Lowry and C. W. Medlock.[2] Ron Cytron et al. rekindled interest in dominance in 1989 when they applied it to efficient computation of φ functions, which are used in static single assignment form.[3]

Applications

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.

Memory usage analysis can benefit from the dominator tree to easily find leaks and identify high memory usage (http://www.eclipse.org/mat/).

Algorithms

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 \text{preds}(n)}^{} \operatorname{Dom}(p) \right ) \bigcup^{} \left \{ n \right \}

where no 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 itself
 Dom(n0) = {n0}
 // for all other nodes, set all nodes as the dominators
 for each n in N - {n0}
     Dom(n) = N;
 // iteratively eliminate nodes that are not dominators
 while changes in any Dom(n)
     for each n in N - {n0}:
         Dom(n) = {n} union with intersection over all p in pred(n) of Dom(p)

Direct solution is quadratic in the number of nodes, or O(n2). 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 fewer.[4]

Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy of Rice University describe an algorithm that essentially solves the above data flow equations but uses well engineered data structures to improve performance.[5]

Postdominance

Analogous to the definition of dominance above, a node z is said to post-dominate a node n if all paths to the exit node of the graph starting at n must go through z. Similarly, the immediate post-dominator of a node n is the postdominator of n that doesn't strictly postdominate any other strict postdominators of n.

See also

References

  1. ^ Prosser, Reese T. (1959). "Applications of Boolean matrices to the analysis of flow diagrams". AFIPS Joint Computer Conferences: Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference (Boston, MA: ACM): 133–138. http://portal.acm.org/ft_gateway.cfm?id=1460314&type=pdf&coll=GUIDE&dl=GUIDE&CFID=79528182&CFTOKEN=33765747. 
  2. ^ Lowry, Edward S.; and Medlock, Cleburne W. (January 1969). "Object code optimization". Communications of the ACM 12 (1): 13–22. http://portal.acm.org/ft_gateway.cfm?id=362838&type=pdf&coll=GUIDE&dl=GUIDE&CFID=79528182&CFTOKEN=33765747. 
  3. ^ Cytron, Ron; Hind, Michael; and Hsieh, Wilson (1989). "Automatic Generation of DAG Parallelism". Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation: 54–68. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.9287&rep=rep1&type=pdf. 
  4. ^ Lengauer, Thomas; and Tarjan, Robert Endre (July 1979). "A fast algorithm for finding dominators in a flowgraph". ACM Transactions on Programming Languages and Systems (TOPLAS) 1 (1): 121–141. http://portal.acm.org/ft_gateway.cfm?id=357071&type=pdf&coll=GUIDE&dl=GUIDE&CFID=79528182&CFTOKEN=33765747. 
  5. ^ Cooper, Keith D.; Harvey, Timothy J; and Kennedy, Ken (2001). "A Simple, Fast Dominance Algorithm". http://www.hipersoft.rice.edu/grads/publications/dom14.pdf. 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Dominator — may refer to: People The Dominator, nickname for Mariusz Pudzianowski (Strongman and MMA fighter), a five times World s Strongest Man The Dominator, nickname for Wayne Johnston (footballer) (b. 1957), a Carlton footballer in Australia The… …   Wikipedia

  • Control flow graph — Simplified control flowgraphs[1] A control flow graph (CFG) in computer science is a representation, using graph notation, of all paths that might be traversed through a program during its execution …   Wikipedia

  • Dominating set — For Dominator in control flow graphs, see Dominator (graph theory). Dominating sets (red vertices). In graph theory, a dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is joined to at… …   Wikipedia

  • Domination — Contents 1 Entertainment 1.1 Books 1.2 Music 1.3 Games …   Wikipedia

  • Terence McKenna — Terence Kemp McKenna (November 16 1946 – April 3 2000) was a writer, philosopher, and ethnobotanist. He was noted for his many speculations on the use of psychedelic, plant based hallucinogens, and subjects ranging from shamanism, the development …   Wikipedia

  • Philosophy of education — The philosophy of education is the study of the purpose, process, nature and ideals of education. This can be within the context of education as a societal institution or more broadly as the process of human existential growth, i.e. how it is… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”