Linear-Time Algorithms for Dominators and Related Problems (thesis)

Abstract:

This dissertation deals with several topics related to the problem

of finding dominators in flowgraphs. The concept of dominators has

applications in various fields, including program optimization,

circuit testing and theoretical biology. We are interested both in

asymptotically fast algorithms and in algorithms that are

practical.

We begin with an experimental study of various algorithms that

compute dominators efficiently in practice. We describe two

practical algorithms that have been proposed in the related

literature: an iterative algorithm initially presented by Allen

and Cocke and later refined by Cooper, Harvey and Kennedy, and the

well-known algorithm of Lengauer and Tarjan. We discuss how to

achieve efficient implementations, and furthermore, introduce a

new practical algorithm. We present a thorough empirical analysis

using real as well as artificial data.

Then we present a linear-time algorithm for dominators

implementable on the pointer machine model of computation.

Previously, Alstrup, Harel, Lauridsen and Thorup gave a

complicated linear-time algorithm for the random-access model.

Buchsbaum, Kaplan, Rogers and Westbrook presented a simpler

dominators algorithm, implementable on a pointer machine and

claimed linear running time. However, as we show, one of their

techniques cannot be applied to the dominators problem and,

consequently, their algorithm does not run in linear time.

Nonetheless, based on this algorithm, we show how to achieve

linear running time on a pointer machine.

Next we address the question of how to verify dominators. We

derive a linear-time verification algorithm, which is much simpler

than the known algorithms that compute dominators in linear time.

Still, this algorithm is non-trivial and we believe it provides

some new intuition and ideas towards a simpler dominators

algorithm.

Finally we study the relation of dominators to spanning trees. Our

central result is a linear-time algorithm that constructs two

spanning trees of any input flowgraph, such that corresponding

paths in the two trees satisfy a vertex-disjointness property we

call ancestor-dominance. This result is related to the concepts of

independent spanning trees and directed st-numberings, previously

studied by various authors, and implies linear-time algorithms for

these constructions.