A new, simpler linear-time dominators algorithm

We present a new linear-time algorithm to find the immediate dominators of all vertices in a flowgraph. Our algorithm is simpler than previous linear- time algorithms: rather than employ complicated data structures, we combine the use of microtrees and memoization with new observations on a restricte d class of path compressions. We have implemented our algorithm, and we rep ort experimental results that-show that the constant factors are low. Compa red to the standard, slightly superlinear algorithm of Lengauer and Tarjan, which has much less overhead, our algorithm runs 10-20% slower on real flo wgraphs of reasonable size and only a few percent slower on very large flow graphs.