Dominator (graph theory)

There are a number of related concepts: Dominance was first introduced by Reese T. Prosser in a 1959 paper on analysis of flow diagrams.

[2] Prosser did not present an algorithm for computing dominance, which had to wait ten years for Edward S. Lowry and C. W.

[3] 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.

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.

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.

[6] 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.

[9] 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.