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)
“Harvey: Oh, you kids these days, I’m telling you. You think the only relationship a man and a woman can have is a romantic one.
Gil: That sure is what we think. You got something better?
Harvey: Oh, romance is very nice. A good thing for youngsters like you, but Helene and I have found something we think is more appropriate to our stage of life—companionship.
Gil: Companionship? I’ve got a flea-bitten old hound at home who’ll give me that.”
—Tom Waldman (d. 1985)