Corresponding domination relation: Grey nodes are not strictly dominated Red nodes are immediately dominated
In computer science, a noded of a control-flow graphdominates a node n if every path from the entry node to n must go through d. Notationally, this is written as d dom n (or sometimes d ≫ n). By definition, every node dominates itself.
There are a number of related concepts:
A node dstrictly dominates a node n if d dominates n and d does not equal n.
The immediate dominator or idom of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly dominates n. Every node, except the entry node, has an immediate dominator.[1]
The dominance frontier of a node d is the set of all nodes ni such that d dominates an immediate predecessor of ni, but d does not strictly dominate ni. It is the set of nodes where d's dominance stops.
A dominator tree is a tree where each node's children are those nodes it immediately dominates. The start node is the root of the tree.
^Cite error: The named reference fastdom was invoked but never defined (see the help page).