Domination Relationship
A block M 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 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. 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.
Read more about this topic: Control Flow Graph
Famous quotes containing the words domination and/or relationship:
“All personal, psychological, social, and institutionalized domination on this earth can be traced back to its source: the phallic identities of men.”
—Andrea Dworkin (b. 1946)
“It was a real treat when he’d read me Daisy Miller out loud. But we’d reached the point in our relationship when, in a straight choice between him and Henry James, I’d have taken Henry James any day even if Henry James were dead and not much of a one for the girls when living, either.”
—Angela Carter (1940–1992)