Dominance relation (control flow graph)

Control flow graph ${\displaystyle G\langle V,E,1\rangle }$

Dominator tree of the control flow graph ${\displaystyle G\langle V,E,1\rangle }$

The dominance relation is a relation that is defined on the nodes of a control flow graph .

Let be a control flow graph and be two of its nodes. ${\displaystyle G\langle V,E,r\rangle }$ ${\displaystyle u,v\in V}$

Now, if every path in that starts in and ends in includes the node , then the node is said to dominate the node . One also writes . ${\displaystyle G}$ ${\displaystyle r}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u\ dom\ v}$

For example, in the control flow graph shown above , node 2 dominates node 5, but node 3 does not dominate node 5 because there is a path that does not include node 3. ${\displaystyle G\langle V,E,1\rangle }$ ${\displaystyle 1\to 2\to 4\to 5}$

Clearly, each node dominates itself. Therefore, the dominance relation is reflexive .

Since it also follows for from and that the node dominates, the dominance relation is also transitive . ${\displaystyle u,v,w\in V}$ ${\displaystyle u\ dom\ v}$ ${\displaystyle v\ dom\ w}$ ${\displaystyle u}$ ${\displaystyle w}$

If the knot dominates the knot and , then it is also said that the knot strictly dominates . You then also write . The strict dominance relation can be represented as a tree . This tree is also Dominator Tree (Engl. Dominator tree called). The example graph above has the following dominator tree: ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u\neq v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u\ stdom\ v}$

See also

• Reducible and irreducible control flow graph