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)
“Only men of moral and mental force, of a patriotic regard for the relationship of the two races, can be of real service as ministers in the South. Less theology and more of human brotherhood, less declamation and more common sense and love for truth, must be the qualifications of the new ministry that shall yet save the race from the evils of false teaching.”
—Fannie Barrier Williams (1855–1944)