Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Engineering and Applications Track of the 12th Annual European Symposium on Algorithms (ESA 2004)
DOI: 10.7155/jgaa.00119
Finding Dominators in Practice
Vol. 10, no. 1, pp. 69-94, 2006. Regular paper.
Abstract The computation of dominators in a flowgraph has applications in
several areas, including program optimization, circuit testing,
and theoretical biology. 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 even on graphs of moderate size. Recently Cooper
et al. [] have proposed a new, simple, tree-based
implementation of an iterative algorithm. Their experiments suggested
that it was faster than the simple version of the Lengauer-Tarjan algorithm on
graphs representing computer program control flows. 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.
|
Journal Supporters
|