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)
“Some [adolescent] girls are depressed because they have lost their warm, open relationship with their parents. They have loved and been loved by people whom they now must betray to fit into peer culture. Furthermore, they are discouraged by peers from expressing sadness at the loss of family relationships—even to say they are sad is to admit weakness and dependency.”
—Mary Pipher (20th century)