Finding Dominators in Practice [abstract] (PDF)
Loukas Georgiadis, Renato F. Werneck, Robert E. Tarjan, Spyridon Triantafyllis, and David I. August
Proceedings of the 12th European Symposium on Algorithms, September 2004.
The computation of dominators in a flowgraph has
applications in program optimization, circuit testing, and other
areas. Lengauer and Tarjan proposed two versions of a fast algorithm
for finding dominators and compared them experimentally with an
iterative bit vector algorithm. They concluded that both versions of
their algorithm were much faster than the bit-vector algorithm even on
graphs of moderate size. Recently Cooper et al. have proposed a new,
simple, tree-based iterative algorithm. Their experiments suggested
that it was faster than the simple version of the Lengauer-Tarjan
algorithm on graphs representing computer program control
flow. Motivated by the work of Cooper et al., we present an
experimental study comparing their algorithm (and some variants) with
careful implementations of both versions of the Lengauer-Tarjan
algorithm and with a new hybrid algorithm. Our results suggest that,
although the performance of all the algorithms is similar, the most
consistently fast are the simple Lengauer-Tarjan algorithm and the
hybrid algorithm, and their advantage increases as the graph gets
bigger or more complicated.