.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.