Editing Dominator (graph theory) (section)

== Algorithms ==
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 ) & \mbox{ if } n \neq 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>.

An algorithm for the direct solution is:

  // dominator of the start node is the start itself
  Dom(n<sub>0</sub>) = {n<sub>0</sub>}
  // for all other nodes, set all nodes as the dominators
  '''for each''' n '''in''' N - {n<sub>0</sub>}
      Dom(n) = N;
  // iteratively eliminate nodes that are not dominators
  '''while''' changes in any Dom(n)
      '''for each''' n '''in''' N - {n<sub>0</sub>}:
          Dom(n) = {n} union with intersection over Dom(p) for all p in pred(n)

The direct solution is [[quadratic growth|quadratic]] in the number of nodes, or O(''n''<sup>2</sup>). [[Thomas Lengauer|Lengauer]] and [[Robert Endre Tarjan|Tarjan]] developed an algorithm which is almost linear,<ref name="fastdom">{{cite journal 
|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 that 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>