Dominator (graph theory): Difference between revisions

Revision as of 17:01, 16 June 2005

Latest revision as of 03:28, 1 September 2025

(129 intermediate revisions by 89 users not shown)

Line 1:

{{Short description|When every path in a control-flow graph must go through one node to reach another}}

''For non-computer uses of '''dominate''', see [[domination and submission]], [[dominator culture]], [[The Dominator]] (Dominik Hasek) or [[global domination]].''

{{distinguish|dominating set}}

{| style="float:right"

| [[File:Dominator control flow graph.svg|thumb|200px|Example control-flow graph with entry node 1]]

|}

{| style="float:right" class=wikitable

|-

! 1

| dom     || {{color|#c0c0c0|1}} || {{color|#F00000|2}} || 3 || 4 || 5 || 6

|-

! 2

| dom || || {{color|#c0c0c0|2}} || {{color|#F00000|3}} || {{color|#F00000|4}} || {{color|#F00000|5}} ||{{color|#F00000|6}}

|-

! 3

| dom || || || {{color|#c0c0c0|3}} || || ||

|-

! 4

| dom || || || || {{color|#c0c0c0|4}} || ||

|-

! 5

| dom || || || || || {{color|#c0c0c0|5}} ||

|-

! 6

| dom || || || || || || {{color|#c0c0c0|6}}

|-

| colspan=8 | Corresponding domination relation:<br>{{color|#c0c0c0|Grey nodes}} are not strictly dominated<br>{{color|#F00000|Red nodes}} are immediately dominated

|}

[[File:Dominator tree.svg|thumb|200px|Corresponding ''dominator tree'' of the control flow graph]]

In [[computer science]], ina [[controlbasic flow graphblock|node]]s, {{mvar|d}} of a [[Nodecontrol-flow (computer science)|nodegraph]] '''ddominates''' ''dominates'' a node '''{{mvar|n'''}} if every path from the start''entry node'' to '''{{mvar|n'''}} must go through '''{{mvar|d'''}}. Notationally, this is written as '{{math|''d''' dom ''n'n'}} (or sometimes {{math|''d'' ≫ ''n''}}). By definition, every node dominates itself.

There are a number of related concepts:

* A node {{mvar|d}} ''strictly dominates'' a node {{mvar|n}} if {{mvar|d}} dominates {{mvar|n}} and {{mvar|d}} does not equal {{mvar|n}}.

* The ''immediate dominator'' or '''idom''' of a node ''{{mvar|n''}} is the unique node that strictly dominates ''{{mvar|n''}} but does not strictly dominate any other node that strictly dominates ''{{mvar|n''}}. Every node reachable from the entry node has an immediate dominator (except the entry node).<ref name="fastdom"/>

* The ''dominance frontier'' of a node n{{mvar|d}} is the set of all nodes w{{mvar|n{{sub|i}}}} such that n{{mvar|d}} dominates aan immediate predecessor of w{{mvar|n{{sub|i}}}}, but n{{mvar|d}} does not strictly dominate w{{mvar|n{{sub|i}}}}. It is the set of nodes where {{mvar|d}}'s dominance stops.

* A ''dominator tree'' is a [[tree (graph theory)|tree]] where each node's children are those nodes it immediately dominates. The start node is the root of the tree.

* 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.

== History ==

Dominance was first introduced by [[Reese Prosser|Reese T. Prosser]] in a 1959 paper on analysis of flow diagrams.<ref>{{cite book

|last=Prosser

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 in the interest in dominance in [[1989]] when he applied it to efficient computation of &phi; functions, which are used in [[static single assignment form]].

|first=Reese T.

|title=Papers presented at the December 1-3, 1959, eastern joint IRE-AIEE-ACM computer conference on - IRE-AIEE-ACM '59 (Eastern)

|chapter=Applications of Boolean matrices to the analysis of flow diagrams

|chapter-url=http://portal.acm.org/ft_gateway.cfm?id=1460314&type=pdf&coll=GUIDE&dl=GUIDE&CFID=79528182&CFTOKEN=33765747

|pages=133–138

|year=1959 |doi=10.1145/1460299.1460314

|s2cid=15546681

|author-link=Reese Prosser

}}</ref> Prosser did not present an algorithm for computing dominance, which had to wait ten years for Edward S. Lowry and C. W. Medlock.<ref>{{cite journal

|title=Object code optimization

|journal=Communications of the ACM

|volume=12

|issue=1

|date=January 1969

|pages=13–22

|first=Edward S.

|last=Lowry

|author2=Medlock, Cleburne W.

|doi=10.1145/362835.362838|s2cid=16768560

|doi-access=free

}}</ref> Ron Cytron ''et al.'' rekindled interest in dominance in 1989 when they applied it to the problem of efficiently computing the placement of φ functions, which are used in [[static single assignment form]].<ref>{{cite book

|first1=Ron

|last1=Cytron

|first2=Jeanne

|last2=Ferrante

|first3=Barry K.

|last3=Rosen

|first4=Mark N.

|last4=Wegman

|first5=F. Kenneth

|last5=Zadeck

|title=Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '89

|chapter=An efficient method of computing static single assignment form

|chapter-url = http://portal.acm.org/citation.cfm?doid=75277.75280

|doi = 10.1145/75277.75280

|isbn = 0897912942

|year=1989

|pages=25–35|s2cid=8301431

}}</ref>

== Applications ==

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

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.<ref>{{Cite journal |last1=Tamrawi |first1=Ahmed |last2=Kothari |first2=Suresh |date=2018-10-01 |title=Projected control graph for computing relevant program behaviors |url=https://www.sciencedirect.com/science/article/pii/S0167642318301497 |journal=Science of Computer Programming |volume=163 |pages=93–114 |doi=10.1016/j.scico.2018.04.003 |issn=0167-6423|url-access=subscription }}</ref>

Dominators, and dominance frontiers particularly, have applications in [[compiler]]s for computing [[static single assignment form]]. A number of compiler optimizations can also benefit from dominators. The flow graph in this case is comprised of [[basic block]]s.

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.<ref>{{cite web |url=http://help.eclipse.org/juno/index.jsp?topic=%2Forg.eclipse.mat.ui.help%2Fconcepts%2Fdominatortree.html |title=Dominator Tree |author=<!--Staff writer(s); no by-line.--> |orig-year=2008|year=2012 |website=eclipse.org |publisher=SAP AG and IBM Corporation |access-date=21 June 2013 }}</ref>

== Algorithms ==

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.<ref>{{cite book

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

|last=Teslenko

|first=Maxim

|author2=Dubrova, Elena

|title=Design, Automation and Test in Europe

|chapter=An Efficient Algorithm for Finding Double-Vertex Dominators in Circuit Graphs

|url=http://dl.acm.org/citation.cfm?id=1049138

|pages=406–411

|year=2005 |doi=10.1109/DATE.2005.53

|isbn=9780769522883

|citeseerx=10.1.1.598.3053

|s2cid=10305833

}}</ref>

In software systems, they are used for reducing the size of the test set in structural testing techniques such as statement and branch coverage.<ref>{{cite book

|last=Dubrova

|first=Elena

|title=Design, Automation and Test in Europe

|chapter=Structural Testing Based on Minimum Kernels

|chapter-url=http://dl.acm.org/citation.cfm?id=1049294

|pages=1168–1173

|year=2005 |doi=10.1109/DATE.2005.284

|isbn=9780769522883

|citeseerx=10.1.1.583.5547

|s2cid=11439732

}}</ref>

== Algorithms ==

<math>Dom(n_o) = \left \{ n_o \right \}</math>

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

: <math>\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 ) & \bigcup^mbox{} \leftif \{} n \rightneq n_0 \end{cases} </math>

The dominator of the start node is the start node itself. The set of dominators for any other node <math>n</math> is the intersection of the set of dominators for all predecessors <math>p</math> of <math>n</math>. The node <math>n</math> is also in the set of dominators for <math>n</math>.

Where <math>n_o</math> is the start node.

An algorithm for the direct solution is:

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(n_0n₀) = {n_0n₀}

// for all other nodes, set all nodes as the dominators

'''for each''' n '''in''' N - {n_0n₀}

Dom(n) = N;

// iteratively eliminate nodes that are not dominators

'''while''' changes in any Dom(n)

'''for each''' n '''in''' N - {n_0n₀}:

Dom(n) = {n} union with intersection over Dom(p) for all p in pred(n) of Dom(p)

DirectThe direct solution is [[quadratic growth|quadratic]] in the number of nodes, or <math>O(''n^''<sup>2)</mathsup>). [[Thomas Lengauer|Lengauer]] and [[Robert Endre Tarjan|Tarjan]] developed an algorithm which is almost linear,<ref butname="fastdom">{{cite itsjournal implementation tends to be complex and time consuming for graph of several hundred nodes or less.

|first1=Thomas |last1=Lengauer |author-link1=Thomas Lengauer

|first2=Robert Endre |last2=Tarjan |author-link2=Robert Tarjan

|date=July 1979

|title=A fast algorithm for finding dominators in a flowgraph

|journal=ACM Transactions on Programming Languages and Systems

|volume=1 |issue=1 |pages=121–141

|doi=10.1145/357062.357071

|citeseerx=10.1.1.117.8843

|s2cid=976012

}}</ref> and in practice, except for a few artificial graphs, the algorithm and a simplified version of it are as fast or faster than any other known algorithm for graphs of all sizes and its advantage increases with graph size.<ref>{{cite web |author1=Georgiadis, Loukas |author2=Tarjan, Robert E. |author-link2=Robert Tarjan |author3=Werneck, Renato F. |year=2006 |title=Finding Dominators in Practice |url=https://www.cs.uoi.gr/~loukas/index.files/dominators_esa04.pdf |archive-url=https://web.archive.org/web/20240415132509/https://www.cs.uoi.gr/~loukas/index.files/dominators_esa04.pdf |archive-date=15 Apr 2024}}</ref>

[[Keith D. Cooper]], Timothy J. Harvey, and [[Ken Kennedy (computer scientist)|Ken Kennedy]] of [[Rice University]] describe an algorithm in their paper titled [http://www.hipersoft.rice.edu/grads/publications/dom14.pdf ''A Simple, Fast Dominance Algorithm'']. Itthat essentially solves the above data flow equations but uses well engineered data structures to improve performance.<ref>{{cite web

|title=A Simple, Fast Dominance Algorithm

|url=http://www.hipersoft.rice.edu/grads/publications/dom14.pdf

|author1=Cooper, Keith D.

|author2=Harvey, Timothy J

|author3=Kennedy, Ken

|author-link1=Keith D. Cooper

|author-link3=Ken Kennedy (computer scientist)

|year=2001 }}</ref>

== Postdominance ==

See also:

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==

* [[Control flow graph]]

* [[Control-flow graph]]

* [[Interval (graph theory)]]

* [[Static single assignment form]]

==References==

<references />

==External links==

*[https://web.archive.org/web/20090714130243/http://www.eecs.harvard.edu/hube/software/nci/cfa.html The Machine-SUIF Control Flow Analysis Library]

*[https://sbaziotis.com/compilers/visualizing-dominators.html Algorithms for computing dominators visually explained]

{{DEFAULTSORT:Dominator (Graph Theory)}}

[[Category:Control-flow analysis]]

[[Category:Directed graphs]]