Dominator (graph theory)

History

Dominance was first introduced by Reese T. Prosser in a 1959 paper on analysis of flow diagrams.{{cite book |chapter-url=http://portal.acm.org/ft_gateway.cfm?id=1460314&type=pdf&coll=GUIDE&dl=GUIDE&CFID=79528182&CFTOKEN=33765747 |author-link=Reese Prosser |doi-access=free |chapter-url = http://portal.acm.org/citation.cfm?doid=75277.75280

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.

Dominators play a crucial role in control flow analysis by identifying the program behaviors that are relevant to a specific statement or operation, which helps in optimizing and simplifying the control flow of programs for analysis.

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.

In hardware systems, dominators are used for computing signal probabilities for test generation, estimating switching activities for power and noise analysis, and selecting cut points in equivalence checking.{{cite book In software systems, they are used for reducing the size of the test set in structural testing techniques such as statement and branch coverage.{{cite book |chapter-url=http://dl.acm.org/citation.cfm?id=1049294

Algorithms

Let n_0 be the source node on the Control-flow graph. The dominators of a node n are given by the maximal solution to the following data-flow equations:

: \operatorname{Dom}(n) = \begin{cases} \left { n \right } & \mbox{ if } n = n_0 \ \left { n \right } \cup \left ( \bigcap_{p \in \text{preds}(n)}^{} \operatorname{Dom}(p) \right ) & \mbox{ if } n \neq n_0 \end{cases}

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 the 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 Dom(p) for all p in pred(n)

The direct solution is quadratic in the number of nodes, or O(n2). Lengauer and Tarjan developed an algorithm which is almost linear,{{cite journal

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.{{cite web |author-link1=Keith D. Cooper |author-link3=Ken Kennedy (computer scientist)

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.

References

References

1. (2018-10-01). "Projected control graph for computing relevant program behaviors". Science of Computer Programming.
2. . (2012). ["Dominator Tree"](http://help.eclipse.org/juno/index.jsp?topic=%2Forg.eclipse.mat.ui.help%2Fconcepts%2Fdominatortree.html). *SAP AG and IBM Corporation*.
3. (2006). "Finding Dominators in Practice".