Josh BeckmanThe 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 relationis defined on vertices of a CFG (and thus basic blocks of the underlying program). A vertex adominatesb (a <= b) if every path from the start node s to b passes through a. A vertex aproperly dominatesb (a < b) if a dominates and is not equal to b. A vertex adirectly/immediately dominatesb (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.nick-black.comCompiler Design