Editing Control-flow graph (section)

==Domination relationship==
{{Main|Dominator (graph theory)}}

A block M ''[[dominator (graph theory)|dominates]]'' a block N if every path from the entry that reaches block N has to pass through block M. The entry block dominates all blocks.

In the reverse direction, block M ''postdominates'' block N if every path from N to the exit has to pass through block M. The exit block postdominates all blocks.

It is said that a block M ''immediately dominates'' block N if M dominates N, and there is no intervening block P such that M dominates P and P dominates N. In other words, M is the last dominator on all paths from entry to N. Each block has a unique immediate dominator.

Similarly, there is a notion of ''immediate postdominator'', analogous to ''immediate dominator''.

The [[dominator (graph theory)|''dominator tree'']] is an ancillary data structure depicting the dominator relationships. There is an arc from Block M to Block N if M is an immediate dominator of N. This graph is a tree, since each block has a unique immediate dominator. This tree is rooted at the entry block. The dominator tree can be calculated efficiently using [[Lengauer–Tarjan's algorithm]].

A ''postdominator tree'' is analogous to the ''dominator tree''. This tree is rooted at the exit block.