1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 |
- .NH 2
- Immediate dominators
- .PP
- A basic block B dominates a block C if every path
- in the control flow graph from the procedure entry block
- to C goes through B.
- The immediate dominator of C is the closest dominator
- of C on any path from the entry block.
- See also
- .[~[
- aho compiler design
- .], section 13.1.]
- .PP
- There are a number of algorithms to compute
- the immediate dominator relation.
- .IP 1.
- Purdom and Moore give an algorithm that is
- easy to program and easy to describe (although the
- description they give is unreadable;
- it is given in a very messy Algol60 program full of gotos).
- .[
- predominators
- .]
- .IP 2.
- Aho and Ullman present a bitvector algorithm, which is also
- easy to program and to understand.
- (See
- .[~[
- aho compiler design
- .], section 13.1.]).
- .IP 3
- Lengauer and Tarjan introduce a fast algorithm that is
- hard to understand, yet remarkably easy to implement.
- .[
- lengauer dominators
- .]
- .LP
- The Purdom-Moore algorithm is very slow if the
- number of basic blocks in the flow graph is large.
- The Aho-Ullman algorithm in fact computes the
- dominator relation,
- from which the immediate dominator relation can be computed
- in time quadratic to the number of basic blocks, worst case.
- The storage requirement is also quadratic to the number
- of blocks.
- The running time of the third algorithm is proportional
- to:
- .DS
- (number of edges in the graph) * log(number of blocks).
- .DE
- We have chosen this algorithm because it is fast
- (as shown by experiments done by Lengauer and Tarjan),
- it is easy to program and requires little data space.
|