Dominators

Let e denote the first block of a program. A node d dominates a node n iff every simple path from e to n passes through d .

For a given node n , its immediate dominator is the dominator closest to it. A tree structure is formed by immediate dominators, with e being the root of the tree.

A loop header h dominates all the nodes in the loop. A back edge is an edge n → h where h dominates n .

The dominator relation allows the program graph to be ordered in a topological sort, which helps in data flow analysis.