Finding the dominators of a node is an important first step for numerous algorithms in program analysis. Dominators are used for building an SSA form of a program, eliminating re-computations of expressions, and determining control dependencies between basic blocks.

Background

Node A dominates node B if all paths from the entry node to node B must pass through node A.

For example, in the above graph, node A dominates node B but does not dominate nodes C or D. All paths to B must go through A: entry, A, B or entry, D, C, A, B. However, there exist paths to C and D that do not go through A: entry, D and entry, D, C.