The directed multigraph defined by interpreting basic blocks as vertices, and flow relationships as edges, yields its control flow graph (CFG). A start node exists for each CFG, corresponding to the basic block whose header is the first instruction of the program.

The antisymmetric, transitive, reflexive *domination relation* is defined on vertices of a CFG (and thus basic blocks of the underlying program). A vertex a *dominates* b (a <= b) if every path from the start node s to b passes through a. A vertex a *properly dominates* b (a < b) if a dominates and is not equal to b. A vertex a *directly/immediately dominates* b (a <d b) if a properly dominates b, and a dominates no vertex c that dominates b. This relation induces the dominator tree, where nodes dominate all descendents in the tree. The start node s dominates all nodes, properly dominates all nodes but itself, and roots the dominator tree.

*Compiler Design* *from* nick-black.com

#### Filed under:

### Same Source

### Related Notes