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 restricted class of path compressions. We have implemented our algorithm, and we report experimental results that show that the constant factors are low. Compared to the standard, slightly superlinear algorithm of Lengauer and Tarjan, which has much less overhead, our algorithm runs 10-20% slower on real flowgraphs of reasonable size and only a few percent slower on very large flowgraphs.
INTRODUCTION
We consider the problem of nding the immediate dominators of vertices in a
graph. A
owgraph is a directed graph r) with a distinguished start
vertex , such that there is a path from r to each vertex in V . Vertex
w dominates vertex v if every path from r to v includes w; w is the immediate
dominator (idom) of v, denoted dominates v and (2) every
other vertex x that dominates v also dominates w. Every vertex in a
owgraph has
a unique immediate dominator [Aho and Ullman 1972; Lorry and Medlock 1969].
Finding immediate dominators in a
owgraph is an elegant problem in graph the-
ory, with applications in global
ow analysis and program optimization [Aho and
Ullman 1972; Cytron et al. 1991; Ferrante et al. 1987; Lorry and Medlock 1969].
Lorry and Medlock [1969] introduced an O(n 4 )-time algorithm, where
to nd all the immediate dominators in a
owgraph. Successive improve-
Some of this material was presented at the Thirtieth ACM Symposium on the Theory of Com-
puting, 1998.
Authors' address: AT&T Labs, Shannon Laboratory, 180 Park Ave., Florham Park, NJ 07932;
Permission to make digital/hard copy of all or part of this material without fee is granted
provided that the copies are not made or distributed for prot or commercial advantage, the
ACM copyright/server notice, the title of the publication, and its date appear, and notice is given
that copying is by permission of the Association for Computing Machinery, Inc. (ACM). To copy
otherwise, to republish, to post on servers, or to redistribute to lists requires prior specic
permission and/or a fee.
c
2  Adam L. Buchsbaum et al.
ments to this time bound were achieved [Aho and Ullman 1972; Purdom and Moore
1972; Tarjan 1974], culminating in Lengauer and Tarjan's [1979] O(m(m;n))-time
algorithm;  is the standard functional inverse of the Ackermann function and grows
extremely slowly with m and n [Tarjan and van Leeuwen 1984]. Lengauer and Tarjan
[1979] report experimental results showing that their algorithm outperforms all
previous dominators algorithms for
owgraph sizes that appear in practice.
Reducing the asymptotic time complexity of nding dominators to O(n +m) is
an interesting theoretical exercise. Furthermore, various results in compiler theory
rely on the existence of a linear-time dominators algorithm; Pingali and Bilardi
[1997] give an example and further references. Harel [1985] claimed a linear-time
dominators algorithm, but careful examination of his abstract reveals problems
with his arguments. Alstrup et al. [1997] detail some of the problems with Harel's
approach and oer a linear-time algorithm that employs powerful data structures
based on bit manipulation to resolve these problems. While they achieve a linear-time
dominators algorithm, their reliance on sophisticated data structures adds
su-cient overhead to make any implementation impractical.
We present a new linear-time dominators algorithm, which is simpler than that
of Alstrup et al. [1997]. Our algorithm requires no complicated data structures:
we use only depth-rst search, the fast union-nd data structure [Tarjan and van
Leeuwen 1984], topological sort, and memoization. We have implemented our al-
gorithm, and we report experimental results, which show that, even with the extra
overhead needed to achieve linear time, our constant factors are low. Ours is the
rst implementation of a linear-time dominators algorithm.
The rest of this article is organized as follows. Section 2 outlines Lengauer and
Tarjan's approach. Section 3 gives a broad overview of our algorithm and dieren-
tiates it from previous work. Section 4 presents our algorithm in detail, and Section
5 analyzes its running time. Section 6 presents our new path-compression result,
on which the analysis relies. Section 7 describes our implementation, and Section
8 reports experimental results. We conclude in Section 9.
2. THE LENGAUER-TARJAN ALGORITHM
Here we outline the Lengauer and Tarjan (LT) approach [Lengauer and Tarjan
1979] at a high level, to provide some details needed by our algorithm. Appel
[1998] provides a thorough description of the LT algorithm.
r) be an input
owgraph with n vertices and m arcs. Let D be a
depth-rst search (DFS) tree of G, rooted at r. We sometimes refer to a vertex x
by its DFS number; in particular, x < y means that x's DFS number is less than
y's. Let w
that w is an ancestor (not necessarily proper) of v in D;
can also denote the actual tree path. Similarly, w
that w is a
proper ancestor of v in D and can represent the corresponding path. For any tree
(v) be the parent of v in T , and let nca T (u; v) be the nearest common
ancestor of u and v in T . We will drop the subscripts and write p(v) and nca(u; v)
when the context resolves any ambiguity.
v) be a path in G. Lengauer and Tarjan
dene P to be a semidominator path (abbreviated sdom path) if x i > v; 1
1. An sdom path from u to v thus avoids all tree vertices between u and
A New, Simpler Linear-Time Dominators Algorithm  3
a,13
d,14
(a)
a,13
d,14
(b)
Fig. 1. (a) A
owgraph G with root r. Vertex labels are augmented with their DFS numbers.
(b) A DFS tree D of G. Solid arcs are tree arcs; dotted arcs are nontree arcs. Breaking D into
microtrees of size no more than 3 results in four nontrivial microtrees, rooted at k, j, g, and a;
the vertices of each nontrivial microtree are encircled.
v. The semidominator (semi) of vertex v is
there is an sdom path from u to vg:
For example, consider vertex g in DFS tree D in Figure 1(a). The DFS number of
g is 10. Paths (e; g), (f; g), (d; f; g), (a; d; f; g), (b; d; f; g), and (b; a; d; f; g) are all
the sdom paths to g. Since b has the least DFS number over the initial vertices on
these paths,
To compute semidominators, Lengauer and Tarjan use an auxiliary link-eval data
structure, which operates as follows. Let T be a tree with a real value associated
with each vertex. We wish to maintain a forest F contained in the tree, subject to
the following operations. (Initially F contains no arcs.)
to F .
Let r be the root of the tree containing u in F . If return r.
Otherwise, return any vertex x 6= r of minimum value on the path
r
u.
Tarjan [1979a] shows how to implement link and eval using the standard disjoint
set union data structure [Tarjan and van Leeuwen 1984]. Using linking by size and
path compression, n 1 links and m evals on an n-vertex tree T can be performed
in O(m(m;n) + n) time.
The LT algorithm traverses D in reverse DFS order, computing semidominators
as follows. (Initially, semi(v) v for all
For in reverse DFS order do
For (w; v) 2 A do
4  Adam L. Buchsbaum et al.
done
link(v)
done
It then computes the immediate dominator for each vertex, using semidominators
and the following facts, which we will also use to design our algorithm.
Lemma 2.1 (LT Lem. 1). If v  w then any path from v to w in G must
contain a common ancestor of v and w in D.
Lemma 2.2 (LT Lem. 4). For any vertex v 6= r, idom(v)
semi(v).
Lemma 2.3 (LT Lem. 5). Let vertices w; v satisfy w
v. Then w
or idom(v)
idom(w).
Lemma 2.4 (LT Thm. 2). Let w 6= r. Suppose every u for which semi(w)
Lemma 2.5 (LT Thm. 3). Let w 6= r, and let u be a vertex for which semi(u) is
minimum among vertices u satisfying semi(w)
and
3. OUTLINE OF A LINEAR-TIME ALGORITHM
The links and evals used by the LT algorithm make it run in O(m(m;n)) time.
We can eliminate the (m; n) term by exploiting the sensitivity of  to relative
dierences in m and n. In particular, when m is slightly superlinear in n, e.g.,
m=n
becomes a constant [Tarjan and van Leeuwen 1984]. 1
Our dominators algorithm proceeds roughly as follows:
(1) Compute a DFS tree D of G, and partition D into regions. We discuss the
partitioning in detail in Section 3.2. For now, it su-ces to consider that D is
partitioned into a collection of small, vertex-disjoint regions, called microtrees.
We consider separately the microtrees at the bottom of D|those that contain
the leaves of D|from the microtrees comprising the interior, D 0 , of D.
(2) For each vertex, determine whether its idom is in its microtree and, if so,
determine the actual idom.
(3) For each vertex v such that idom(v) is not in v's microtree
(a) compute idom(v) by applying the LT algorithm only to vertices in D 0 or
(b) nd an ancestor u of v such that and idom(u) can be
computed by applying the LT algorithm only to vertices in D 0 .
Partitioning D into microtrees serves two purposes. First, the subgraph induced
by the microtree roots will achieve the ratio m=n necessary to reduce (m; n) to
a constant. Second, when the microtrees are small enough, the number of distinct
microtrees will be small compared to n +m. We can thus perform simple computations
on each microtree in O(n using precomputed tables or
memoization to eliminate redundant computations.
log (i) n is the iterated log function: log (0)
A New, Simpler Linear-Time Dominators Algorithm  5
3.1 Comparison to Previous Approaches
We contrast our use of these facts to previous approaches. Harel [1985] and Alstrup
et al. [1997] apply the LT algorithm to all of D, using the microtree partitioning to
speed links and evals. Harel [1985] divides the entire tree D into microtrees, all of
which can contain more than one vertex, and performs links and evals as described
by Lengauer and Tarjan [1979] on the tree D 0 induced by the microtree roots.
Alstrup et al. [1997] simplify Harel's approach [Harel 1985] by restricting nonsin-
gleton microtrees to the bottom of D, leaving an upper subtree, D 0 , of singleton
microtrees as we do. They then perform links and evals on D 0 using two novel
data structures, as well as the Gabow-Tarjan linear-time disjoint set union result
[Gabow and Tarjan 1985] and transformations to D 0 . Both algorithms use pre-computed
tables to process evals on the internal microtree vertices. This approach
requires information regarding which vertices outside microtrees might dominate
vertices inside microtrees, to derive e-cient encodings needed by the table lookup
technique. Harel [1985] presents a method to restrict the set of such outside dominator
candidates. Alstrup et al. [1997] demonstrate deciencies in Harel's arguments
and correct these problems, using Fredman and Willard's Q-heaps [Fredman and
Willard 1994] to manage the microtrees.
We apply the LT algorithm just to the upper portion, D 0 , of D. We combine
our partitioning scheme with a new path compression result to show that the LT
algorithm runs in linear time on D 0 . Instead of processing links and evals on internal
microtree vertices, we determine, using any simple dominators algorithm, whether
the dominators of such vertices are internal to their microtrees, and if so we compute
them directly, using memoization to eliminate redundant computation. We process
those vertices with dominators outside their microtrees without performing evals on
internal microtree vertices. Our approach obviates the need to determine outside
dominator candidates for internal microtree vertices, eliminating the additional
complexity Alstrup et al. require to manage this information.
We can thus summarize the key dierences in the various approaches as follows.
Harel [1985] and Alstrup et al. [1997] partition D into microtrees and apply the
standard LT algorithm to all of D, using precomputed tables to speed the computation
of the link-eval data structure in the microtrees. We also partition D
into microtrees, but we apply the LT algorithm, with the link-eval data structure
unchanged, only to one, big region of D and use memoization to speed the computation
of dominators in the microtrees. In other words, Harel [1985] and Alstrup
et al. [1997] take a purely data structures approach, leaving the LT algorithm unchanged
but employing sophisticated new data structures to improve its running
time. We modify the LT algorithm so that, although it becomes slightly more
complicated, simple and standard data structures su-ce to implement it.
A minor dierence in the two approaches regards the use of tables. Harel [1985]
and Alstrup et al. [1997] precompute the answers to all possible queries on mi-
crotrees and then use table lookup to answer the queries during the actual dominators
computation. We build the corresponding table incrementally using memo-
ization, computing only the entries actually needed by the given instance. The two
approaches have identical asymptotic time complexities, but memoization tends to
outperform a priori tabulation in practice, because the former does not compute
6  Adam L. Buchsbaum et al.
answers to queries that will never be needed.
3.2 Microtrees
Consider the following procedure that marks certain vertices in D. The parameter
g is given, and initially all vertices are unmarked.
For x in D in reverse DFS order do
y child of x S(y)
If S(x) > g then
Mark all children of x
endif
done
Mark root(D)
For any vertex v, let nma(v) be the nearest marked ancestor (not necessarily
proper) of v. The nma function partitions the vertices of D into microtrees as
follows. Let v be a marked vertex; T vg is the microtree
containing all vertices x such that v is the nearest marked ancestor of x. We say
is the root of microtree T v . For any vertex x, micro(x) is the microtree
containing x. See Figure 1.
For any v, if v has more than g descendents, all children of v are marked. There-
fore, each microtree has size at most g. We call a microtree nontrivial if it contains
a leaf of D. Only nontrivial microtrees can contain more than one vertex; these
are the subtrees we process using memoization. The remaining microtrees, which
we call trivial, are each composed of singleton, internal vertices of D; these vertices
comprise the upper subtree, D 0 , of D. Additionally, all the children of a vertex that
forms a trivial microtree are themselves microtree roots. Call a vertex v that forms
a trivial microtree special if each child of v is the root of a nontrivial microtree.
(In

Figure

1(b), c and e are special vertices.) If we were to remove the nontrivial
microtrees from D, these special vertices would be the leaves of the resulting tree.
Since each special vertex has more than g descendents, and the descendents of any
two special vertices form disjoint sets, there are O(n=g) special vertices.
We note that Alstrup et al. [1997] dene microtrees only where they include
leaves of D (our nontrivial microtrees), whereas our denition makes every vertex
a member of some microtree. We could adopt the Alstrup et al. [1997] denition,
but dening a microtree for each vertex allows more uniformity in our discussion,
particularly in the statements and proofs of our lemmas and theorems.
Gabow and Tarjan [1985] pioneered the use of microtrees to produce a linear-time
disjoint set union algorithm for the special case when the unions are known in
advance. In that work, microtrees are combined into microsets, and precomputed
tables are generated for the microsets. Dixon and Tarjan [1997] introduce the idea
of processing microtrees only at the bottom of a tree.
3.3 Path Denitions
v) be a path in G. We dene P to be
an external dominator path (abbreviated xdom path) if P is an sdom path and
dominator path is simply a semidominator
A New, Simpler Linear-Time Dominators Algorithm  7
path that resides wholly outside the microtree of the target vertex (until it hits the
target vertex). The external dominator of vertex v is
there is an xdom path from u to vgg :
In particular, for any vertex v that forms a singleton microtree,
We dene P to be a pushed external dominator path (abbreviated pxdom path)
nontrivial microtrees occur only at the
bottom of D, a pxdom path to v cannot exit and reenter micro(v): to do so would
require traversing a back arc to a proper ancestor of root(micro(v)). Therefore, a
pxdom path to v is (a) an xdom path to some vertex x 2 micro(v) catenated with
(b) an x-to-v path inside micro(v). Either (a) or (b) may be the null path. The
pushed external dominator of vertex v is
there is a pxdom path from u to vg:
Note that pxdom(v) 62 micro(v): since the arc (p D (root(micro(v))); root(micro(v)))
catenated with the tree path root(micro(v))
pxdom path to v, we have
that pxdom(v)  pD (root(micro(v))).
For example, consider vertices l and h in DFS tree D in Figure 1(b). The DFS
number of l is 4. The path is an sdom path from r to l, and so
is not an xdom path. Path (c; j; l) is an xdom
path from c to l, and no xdom path exists from r to l, so 2. P is a
pxdom path, however: (r; b; e; n) is an xdom path from r to n 2 micro(l), and
(n; l) is a path internal to micro(l). Thus, semi(l). Continuing, the
DFS number of h is 12. The only sdom path to h is (g; h), and so
Path (b; d; f; g; h) is a pxdom path to h, however, so In
general, for any vertex, its semi, xdom, and pxdom values need not match.
We use the following lemmas. Note the similarity of Lemma 3.2 to Lemma 2.2.
Lemma 3.1. For any vertex v that forms a singleton microtree,
semi(v).
Proof. Let v) be a
pxdom path from u to v. If v forms a singleton microtree, then
and so, by denition of pxdom, x i  v for 1  i < k. Without loss of generality,
however, since u is the minimum vertex from which there is a pxdom path to v,
we can assume that x i 6= v for 1  i < k. Therefore P is a semidominator path,
so semi(v)  u. Any semidominator path, however, is a pxdom path, so in fact
Lemma 3.2. idom(v) 62 micro(v) =) idom(v)
pxdom(v).
Proof. Let As observed above, u 62 micro(v). By denition
of pxdom, there is a path from u to v that avoids all vertices (other than u) on
the tree path u
Therefore, if idom(v) 62 micro(v), idom(v)
cannot lie on that tree path.
In the next section, we give the details of our algorithm.
4. DETAILS OF OUR LINEAR-TIME ALGORITHM
At a high level, we can abstract our algorithm as follows:
8  Adam L. Buchsbaum et al.
a
d
f
(a)
a
d
f
(b)
Fig. 2. (a) The microtree T , consisting of vertices a, d, and f from Figure 1(b), as well as incident
arcs external to T . (b) The induced graph aug(T ).
(1) Using memoization to reduce running time, determine for each vertex v if
so, the actual value idom(v).
(2) Use the LT algorithm to compute idoms for all v such that idom(v) 62 micro(v).
The remainder of this section provides the details behind our approach. For clarity,
we describe as separate phases the resolution of the idom(v) 2 micro(v) question,
the computation of pxdom(v), and the overall algorithm to compute idom(v). We
discuss in Section 7 how to unite these phases into one traversal of D.
4.1 Computing Internal Dominators
We begin by showing how to determine whether idom(v) 2 micro(v) and, if it is, how
to nd the actual value idom(v). For vertex v that comprises a singleton microtree,
our decision is trivial: idom(v) 62 micro(v). For a nonsingleton microtree T , we
dene the following augmented graph. Let G(T ) be the subgraph of G induced by
vertices of T . Let aug(T ) be the graph G(T ) plus the following:
(1) A vertex t, which we call the root of aug(T ), or root(aug(T )).
(2) An arc (t; v) for each v 2 T such that there exists an arc (u; v) 2 A for some
We call these blue arcs.
Note that there is a blue arc (t; root(T )). Vertex t represents the contraction of
ignoring all arcs that exit T . See Figure 2. We use the augmented graphs
to capture the intuition that removing arcs that exit a microtree 2 does not change
the dominator relationship.
We dene the internal immediate dominator (iidom) of vertex x, iidom(x), to
be the immediate dominator of x in aug(micro(x)). We show that if iidom(x) 2
conversely, that if
Computing
iidoms using memoization on aug(micro(v)) thus yields a fast procedure to deter-
exits micro(u) if v 62 micro(u).
A New, Simpler Linear-Time Dominators Algorithm  9
y
x
(a)
y
z
x
(b)
Fig. 3. aug(micro(x)), plus incident external arcs/paths from G. Solid lines are arcs; dotted lines
are paths. (a) The case t, and z < y. If z 62 micro(x), e.g.,
in the gure, then there is a path from t to x in aug(T ), using blue arc (t; v), that avoids y. If
in the gure, then there is a path internal to micro(T ) from z to x that
avoids y. Either case contradicts the assumption that y = iidom(x). (b) Similar case, but y < z.
There is a path P in aug(T ) from y to x, avoiding z. P contains no blue arcs, so it is a path in
G, contradicting that z = idom(x).
mine whether or not idom(v) 2 micro(v) for any v. We give the details of the
memoization procedure below.
Lemma 4.1. iidom(x) 6= root(aug(micro(x))) =)
Proof. Let
idom(x) such that y 6= t and y 6= z. If z < y, then in the full graph G, there
exists a path P from z to x that avoids y. We use P to demonstrate a path P 0 in
aug(T ) from some z 0 2 ft; zg to x that avoids y, contradicting the assumption that
v) be the last arc on P such that u 62 aug(T ). If there is
no such arc then P yields an immediate contradiction. Otherwise, arc (u; v)
induces blue arc (t; v) 2 aug(T ). This arc together with a subpath of P from v to
x provides path P 0 . See Figure 3(a).
On the other hand, if y < z, then there is a path P in aug(T ) from y to x that
avoids z. By hypothesis, y 6= t, so P contains no blue arcs. (There are no arcs into
t, and so t 62 P .) Therefore, P is also a path in G, contradicting that z = idom(x).

Figure

3(b).
Lemma 4.2.
Proof. Let
t. Then there is a path P in aug(T ) from t to x that avoids
z. If P contains no blue arcs, then it is a path in the original graph, contradicting
the claim that z = idom(x). If P contains blue arc (t; v) for some v, then in G
there is an arc (u; v) for some u 62 T . The tree path root(G)
catenated with
the arc (u; v) and the subpath in P from v to x gives a path in G to x that avoids
a
z
x
Fig. 4. aug(micro(x)), plus incident external arcs/paths from G. Solid lines are arcs; dotted lines
are paths. Case in which t. There is a path P in aug(T )
from t to x, avoiding z. If P contains no blue arcs (follows the path from a to b around z), this
contradicts that z = idom(x), for P exists in G. If P contains blue arc (t; v), then there is a path
in G to x, using the arc (u; v), where u 62 T . Again, P avoids z, contradicting
z, again giving a contradiction. See Figure 4.
We memoize the computation of iidom(v) as follows. The rst time we compute
the internal immediate dominators for some augmented graph aug(T ), we store the
results in a table, I , indexed by graph aug(T ) and vertex v. We encode aug(T ) by
a bit string corresponding to its adjacency matrix represented in row-major order.
To compute this bit string, we traverse aug(T ) in DFS order, assigning DFS value
one to the root of aug(T ) and using the DFS values as vertex identiers; we refer
to this as the canonical encoding of aug(T ).
If a subsequent microtree T 0 has an augmented graph that is isomorphic to
encodings will be identical, so we can simply look up the
iidom values for aug(T 0 ) in table I . This obviates having to recompute the iidoms
for aug(T 0 simply map the iidom values stored in table I , which are relative to
the canonical encoding of aug(T 0 ), to the current instantiation of aug(T 0 ). (Vertex
x in aug(T 0 ) corresponds to vertex x root(aug(T in the canonical encoding
of aug(T 0 ).)
4.2 Computing Pushed External Dominators
We now prove that the following procedure labels vertices with their pxdoms. As
we will show, this process allows us to avoid performing links and evals within
nontrivial microtrees.
Initially, D, and we use a link-eval data structure with
label(v) as the value for vertex v. As we will see, by Theorem 4.4,
pxdom(v) when v becomes linked. The link-eval values are thus pxdoms.
micro(v)g, the external neighbors of v, be the
vertices outside micro(v) with arcs to v. The procedure processes the microtrees T
A New, Simpler Linear-Time Dominators Algorithm  11
in reverse DFS order.
(1) For
6
(c) label(v) min(fvg
Lemma 4.3 proves that this labels v with xdom(v).
(2) For (v) be the set of all vertices in T from which there is a path to
consisting only of arcs in G(T ). Set label(v) min y2Y (v) flabel(y)g. We call
this pushing to v. (Pushing can be done by computing the strongly connected
components of G(T ) and processing them in topological order.) Theorem 4.4
proves that pushing labels v with pxdom(v).
If T is a trivial microtree, then link(v).
Due to the pushing in Step (2), pxdom values are nonincreasing along paths from
the microtree root. This allows us to perform evals only on parents of microtree
roots: the pxdom pushing eectively substitutes for the evals on vertices inside the
microtrees.
To prove that the above procedure correctly labels vertices in a microtree T , we
assume by induction that the procedure has already labeled by their pxdoms all
vertices in all trees preceding T in reverse DFS order. The base case is vacuously
true.
Lemma 4.3. After Step (1),
Proof. Let We show that (1) label(x)  w and (2) label(x)  w.
(1) Consider the xdom path P from w to x. Let y 62 micro(x) be the last vertex
on P before x. Let z be the least vertex excluding w that P touches on the
tree path w
else P is not an xdom path. The prex P 0
of P from w to z is a semidominator path. Otherwise, there exists some u 6= w
on P 0 such that u < z; by Lemma 2.1, P 0 contains a common ancestor of u and
z, contradicting the assertion that z is the least vertex in P on the tree path
y. Therefore, pxdom(z)  semi(z)  w. By induction, label(z)  w. If
z 2 micro(y), then label(z) got pushed to y, and thus label(y)  w. (Note that
in Step (1).) If z 62 micro(y), then C in Step (1) contains some
value no greater than label(z), due to the previous links via Step (3). In either
case the label considered for x via the (y; x) arc is no greater than label(z)  w.

Figure

5.
(2) Consider arc (y; x) such that y 62 micro(x). Let
so there is a pxdom path P from w 0 to y. P catenated with
the arc (y; x) is an xdom path. Similarly, for
there is a pxdom path P from w label(z) to z. P catenated with the tree
path z
y and arc (y; x) forms an xdom path from w 0 to x. In either case,

Figure

5 again demonstrates the potential paths.
Theorem 4.4. After Step (2),
12  Adam L. Buchsbaum et al.
y
x
Fig. 5. Microtrees containing x and y, with incident external paths. Solid lines are arcs; dotted
lines are paths. There is an sdom path from w to some z > nca(y; x); thus
in the gure), then label(y)  w. If z 62 micro(y)
in the gure), then label(eval(root(micro(y))))  w.
Proof. We argue analogously to the proof of Lemma 4.3. Let
we show that (1) w is considered as a label for x via an internal pushing path and
(2) for any w 0 so considered, there is a valid pxdom path from w 0 to x.
(1) Consider the pxdom path P from w to x. Let v be the rst vertex on P inside
During Step (2),
w is pushed to x via the path from v to x.
(2) Consider any w 0 pushed to x. w 0 is an xdom or pxdom for some vertex y 2 T .
there is a valid pxdom path from w 0 to x.
4.3 Computing Dominators
Using the information we computed in Sections 4.1 and 4.2, we now give an algorithm
to compute immediate dominators. The algorithm proceeds like the LT
algorithm; in fact, on the subtree of D induced by the trivial microtrees, it is exactly
the LT algorithm. The algorithm relies on the following two lemmas:
Lemma 4.5. For any v, there exists a w 2 micro(v) such that
(3
(4
Proof. The proof proceeds as follows. We rst nd an appropriate vertex w
on the tree path root(micro(v))
v. We show that
A New, Simpler Linear-Time Dominators Algorithm  13
x
(a)
x
(b)
Fig. 6. The graph induced by micro(v), plus incident external arcs/paths from G. Solid lines are
arcs; dotted lines are paths. be the pxdom path from x to v. w is the least
vertex in P on the path from root(micro(v)) to v. (a) The prex P 0 of P from x to w includes
only vertices that are greater than v (except w). (b) P 0 includes descendents of w that are less
than v and so must take a back arc to w. In either case, P 0 is an sdom path from x to w, since
w is the least vertex in P on the path from root(micro(v)) to v.
argue that This resolves postulates (1){(3). Finally, we
prove that idom(w) 62 micro(x), which implies postulate (4).
consider the pxdom path P from x to v. Let w be
the least vertex in P on the tree path root(micro(v))
v. We argue that the
prex P 0 of P from x to w is a semidominator path. If not, then there is some
vertex y 6= x on P 0 such that y < w. Since w  v, it must be that y 2 micro(v);
otherwise, y violates the pxdom path denition, since we only allow a y < v on P
if y 2 micro(v). By Lemma 2.1, the subpath of P 0 from y to w contains a common
ancestor z of y and w. Since y < w, it must be that z < w. As with y, it must also
be that z 2 micro(v), or else z violates the pxdom path denition. This implies
that z is on the tree path root(micro(v))
v, contradicting the assertion that w is
the least such vertex on P . Therefore semi(w)  x. See Figure 6.
Now we argue that semi(w)  x. If not, there is a semidominator path P from
some y < x to w. P catenated with the tree path from w to v, however, forms a
pxdom path from y to v, contradicting the assumption that
Similarly, we argue that any semidominator path is also
a pxdom path, pxdom(w)  x. If there is a pxdom path P from some y < x
to however, P catenated with the tree path from w to v is a pxdom path
that contradicts the assumption that x. Thus we have shown that
By denition of pxdom, pxdom(w) < root(micro(w)). Therefore,
semi(w) implies that semi(w) 62 micro(w). By Lemma 2.2, therefore, idom(w) 62
micro(w), and thus by Lemma 4.1,
Lemma 4.6. Let w; v be vertices in a microtree T such that
14  Adam L. Buchsbaum et al.
y
Fig. 7. The graph induced by micro(v), plus incident external arcs/paths from G. Dotted lines
are paths. If idom(v) < idom(w), then there is an sdom path from some y < idom(w) to some
x > idom(w) such that there is a tree path from x to v. If x lies on the tree path from idom(w)
to w in the gure), however, this contradicts the denition of idom(w), and if x lies on
the tree path from w to v in the gure), this contradicts that
(3
Proof. Condition (3) and Lemma 4.2 imply that idom(v); idom(w) 62 T . In
particular, idom(v) < w, so Lemma 2.3 implies that idom(v)  idom(w). If
idom(v) < idom(w), then there is a path P from idom(v) to v that avoids idom(w).
must contain a semidominator subpath P 0 from some y < idom(w) to some
x > idom(w) such that x
v. x cannot lie on tree path idom(w)
would contradict the denition of idom(w). x cannot lie on tree path w
v, for this
would imply pxdom(v)  y < pxdom(w). (By Lemma 3.2, idom(w)  pxdom(w).)
So no such P 0 can exist. See Figure 7.
Lemmas 4.5 and 4.6 imply the following, which is formalized in the proof of Theorem
4.7. Consider a path in a microtree, from root to leaf. The vertices on the
path are partitioned by pxdom, with pxdom values monotonically nonincreasing.
Each vertex w at the top of a partition is such that
thermore, idom(w) 62 micro(w). For another vertex v in the same partition as w,
either idom(v) is actually in the partition, or else outside the
microtree. See Figure 8. That implies that our algorithm
devolves into the LT algorithm on the upper subtree, D 0 , of D consisting of trivial
microtrees.
We can now compute immediate dominators by Algorithm IDOM, given in Figure
9. For each v 2 D, IDOM either computes idom(v) or determines a proper ancestor
A New, Simpler Linear-Time Dominators Algorithm  15
x
y
z
a
c
Fig. 8. A microtree with incident external paths. Dotted lines are paths. y, and
All vertices on the tree path from w to p(v) have pxdom y; the path from x
to b, a prex of which is an xdom path, does not aect the pxdom values on the w-p(v) part
of the partition. The vertices in the partition need not share idoms, however. In this picture,
y, but
u of v such that description of the straightforward
postprocessing phase that resolves the latter identities. IDOM uses a second link-eval
data structure, with pxdom(v) as the value for vertex v; at the beginning of IDOM,
no links have been done.
Theorem 4.7. Algorithm IDOM correctly assigns immediate dominators.
Proof. Lemma 4.1 shows that assigning idom(v) to be iidom(v) if iidom(v) 2
micro(v) is correct. Assume then that iidom(v) 62 micro(v), and thus idom(v) 62
micro(v) by Lemma 4.2.
Consider the processing of vertex v in bucket(u). Assume rst that
be the child of u on tree path u
v. We claim that z is
the vertex on tree path u 0
v with minimum semi and that
Assuming that this claim is true, if
Observe that for any w 2 micro(v) such that w
pxdom(w)  semi(w). Thus, if
v, and the claim holds. On the other hand, if
then is the vertex on the tree path
pD (root(micro(v))) of minimum pxdom. The claim holds, since (1) pxdom(u 0 )
Consider the remaining case, when pxdom(v) 6= semi(v). Lemma 4.5 shows that
there exists a w 2 micro(v) such that w
root(aug(micro(v))), and so
pxdom(w) and and w are both placed in the same bucket
Algorithm IDOM
For in reverse DFS order do
Process(v)
done
For such that fug is a trivial microtree, in reverse DFS order do
link(u)
done
Process(v)
If iidom(v) 2 micro(v) then
else
add v to bucket(pxdom(v))
endif
For do
If
z v
else
z eval(p D (root(micro(v))))
endif
idom(v) u
else
endif
done
Fig. 9. Algorithm IDOM.
by IDOM. Therefore, IDOM does compute the same value for idom(v) as for idom(w),
and by the previous argument, it computes the correct value for idom(w).
5. ANALYSIS
Here we analyze the running time of our algorithm. It should be clear that the
generation of the initial DFS tree D and the division of D into microtrees can be
performed in linear time, by the discussion in Section 3.2.
5.1 Computation of iidoms
Recall the memoized computation of iidoms described in Section 4.1. So that all
the iidom computations run in linear time overall, the augmented graphs must be
small enough so that (1) a unique description of each possible graph aug(T ) can be
computed in O(jaug(T )j) time and (2) all the immediate dominators for all possible
augmented graphs are computable in linear time. (After computing immediate
dominators for an augmented graph, future table lookups take constant time each.)
We require a description of aug(T ) to t in one computer word, which we assume
holds log n bits. Recall each microtree has no more than g vertices, for some
parameter g. Thus, each augmented graph has no more than g+1 vertices. Without
aecting the time bounds (we can use g 1 in place of g), we can assume that any
aug(T ) has no more than g vertices. Therefore, aug(T ) has no more than g 2 arcs
A New, Simpler Linear-Time Dominators Algorithm  17
and can be uniquely described by a string of at most g 2 bits. To t in one computer
word,
We can traverse aug(T ) and compute its bitstring identier in O(jaug(T )j) time,
assuming that we can (1) initialize a computer word to 0, and (2) set a bit in
a computer word, both in O(1) time. This further assumes that vertices in T are
numbered from 1 to jT j, where jT j is the number of vertices in T . As part of the DFS
of G, we can assign secondary DFS numbers to each v, relative to root(micro(v)),
satisfying this labeling constraint. The total time to generate bitstring identiers
is thus
O
microtree T
Since each vertex (respectively, arc) in G can be attributed to one vertex (respec-
tively, arc) in exactly one augmented graph, and there is one extra root vertex for
each augmented graph, Expression
When rst encountering a particular aug(T ), we can use any naive dominators
algorithm to compute its immediate dominators in poly(g) time. Then we can store
the values for iidom(v), for each v 2 aug(T ), in table I in time O(jaug(T )j). In the
worst case, we would have to memoize all the iidom values for all possible distinct
graphs on g or fewer vertices. There are about 2 g 2
such graphs, so the total time
is O(2
poly(g)), inducing the constraint
poly(g)  n:
A simple analysis shows that if using memoization, we can
compute all needed iidom values in O(n +m) time.
5.2 Computation of pxdoms
Step (1) in the computation, the initial labeling of a vertex v, processes each vertex
and arc in G once throughout the labelings of all vertices v. Additionally, Step (1)
performs at most one eval operation, on a trivial microtree root, per arc in G.
Step (2) can be implemented by computing the strongly connected components
(SCCs) of the subgraph of G induced by the microtree T , initially assigning each
vertex in each SCC the minimum label among all the vertices in the SCC, and then
pushing the labels through the SCCs in topological order. Computing SCCs can be
done in linear time [Tarjan 1972], as can the topological processing of the SCCs.
Step (3) links root(T ) once for each trivial microtree T .
Thus, the time to compute the pxdoms, summed over all the microtrees, is
n) plus the time to perform at most n 1 link and m eval operations. We
analyze the link-eval time in Section 6.
5.3 Computation of idoms
We implement the bucket associated with each vertex by a linked list. For each
takes constant time to look up iidom(v) and either assign idom(v)
or place v into bucket(pxdom(v)).
To process a vertex v in bucket(pxdom(v)) requires constant time plus the time
to perform eval on pD (root(micro(v))). Each vertex appears in at most one bucket,
so processing the buckets takes time O(n) plus the time to do at most n evals on
trivial microtree roots. (Since pxdom(v) 62 micro(v), only trivial microtree roots
have buckets.)
Again, we perform link(v) only on trivial microtree roots, so the total time taken
by IDOM is O(m n) plus the link-eval time.
5.4

Summary

By the above analysis, the total time required to compute immediate dominators in
a
owgraph G with n vertices and m arcs is O(m+n) plus the time to perform the
links and evals on D. We next prove that since we do links and evals only on trivial
microtree roots, the total link-eval time is O(m n) for an appropriate choice of
the parameter g.
6. DISJOINT SET UNION WITH BOTTOM-UP LINKING
Recall that link and eval are based on disjoint set union, yielding the (m; n) term
in the LT time bound. Here we show that restricting the tree to which we apply
links and evals to have few leaves results in the corresponding set union operations
requiring only linear time.
Let U be a set of n vertices, initially partitioned into singleton sets. The sets are
subject to the standard disjoint set union operations.
and C are the names of sets; the operation unites sets A
and B and names the result C.
nd(u). Returns the name of the set containing u.
It is well known [Tarjan and van Leeuwen 1984] that n 1 unions intermixed with
m nds can be performed in O(m(m;n) + n) time. The sets are represented by
trees in a forest. A union operation links the root of one tree to the root of another.
Operation nd(u) traces the path from u to the root of the tree containing u. By
linking the smaller tree as a child of the root of the larger tree during a union and
compressing the path from u to the root of the tree containing u during nd(u),
the above time bound is achieved.
We show that given su-cient restrictions on the order of the unions, we can
improve the above time bound. We know of no previous result based on this type
of restriction. Previously, Gabow and Tarjan [1985] used a priori knowledge of the
unordered set of unions to implement the union and nd operations in O(m
time. We do not require advance knowledge of the unions themselves, only that
their order be constrained. Other results on improved bounds for path compression
[Buchsbaum et al. 1995; Loebl and Nesetril 1997; Lucas 1990] generally restrict the
order in which nds, not unions, are performed.
Of the n vertices, designate l to be special and the remainder n l to be ordinary.
The following theorem shows that by requiring the unions to \favor" a small set of
vertices, the time bound becomes linear.
Theorem 6.1. Consider n vertices such that l are special and the remaining
n l are ordinary. Let  be a sequence of n 1 unions and m nds such that each
A New, Simpler Linear-Time Dominators Algorithm  19
union involves at least one set that contains at least one special vertex. Then the
operations can be performed in O(m(m; l)
Proof. The restriction on the unions ensures that at all times while the sequence
is being processed, each set either contains at least one special vertex or is
a singleton set containing an ordinary vertex. This observation can be proved by
an induction on the number of unions.
The following algorithm can be used to maintain the sets. A standard union-nd
data structure is created containing all the special vertices as singleton sets. Recall
that such a data structure consists of a forest of rooted trees built on the vertices,
one tree per set. The root of a tree contains the name of the set. There is also
an array, indexed by name, that maps a set name to the root of the corresponding
tree. We will call this smaller data structure U 0 and denote unions and nds on it
by union 0 and nd 0 .
The ordinary vertices are kept separate. Each ordinary vertex contains a pointer
that is initially null. The operations are performed as follows.
If each of x and y names a set that contains at least one special
vertex, perform union 0 (x; Suppose one of x and y, say y, is a singleton set
containing an ordinary vertex. Set the pointer of the ordinary vertex to point to
the root of set x. Relabel that root z.
nd(x). If x is a special vertex, execute nd 0 (x). If x is ordinary and has a null
pointer, return x. (It is in a singleton set.) If x is ordinary with a nonnull pointer
to special vertex y, return nd 0 (y).
The intuition is simple: unless an ordinary vertex x forms a singleton set, it can
be equated to a special vertex y such that
Each operation involves O(1) steps plus, possibly, an operation on a union-nd
data structure U 0 containing l vertices. Let k be the total number of operations done
on U 0 . Then the total running time is O(k(k; l)+m+n), which is O(m(m; l)+n)
It is convenient to implement the above algorithm completely within the frame-work
of a single standard union-nd forest data structure, using path compression
and union by size, as follows. Initially all special vertices are given weight one, and
all ordinary vertices are given weight zero. Recall that the size of a vertex is the
sum of the weights of its descendents, including itself.
To see that this implementation is essentially equivalent to that described in
Theorem 6.1, observe the following points. First, by induction on the number of
operations, an ordinary vertex is always a leaf in the union-nd forest. The union-
by-size rule ensures that whenever a singleton ordinary set is united with a set
containing special elements, the ordinary vertex is made a child of the root of the
other set. The standard nd operation is done by following parent pointers to the
root and then resetting all vertices on the path to point to the root. Hence any leaf
vertex, and in particular any ordinary vertex, remains a leaf in the forest.
Each ordinary vertex is thus either a singleton root or contains a pointer to a
special vertex, as in the proof of Theorem 6.1. Furthermore, since the ordinary
vertices have weight zero they do not aect the size decisions made when uniting
sets containing special vertices. A nd on an ordinary vertex is equivalent to a
20  Adam L. Buchsbaum et al.
nd on its parent, which is a special vertex, just as in the proof of Theorem 6.1.
The only dierence is that the pointer in the ordinary vertex is possibly changed
to point to a dierent special vertex, the root. This only adds O(1) to the running
time.
6.1 Bottom-Up linking
Let a sequence of unions on U be described by a rooted, undirected union tree, T ,
each vertex of which corresponds to an element of U . The edges in T are labeled
zero or one; initially, they are all labeled zero. Vertices connected by a path in T of
edges labeled one are in the same set. Labeling an edge fv; p(v)g one corresponds
to uniting the sets containing v and p(v). The union sequence has the bottom-up
linking property if no edge fv; p(v)g is labeled one until all edges in the subtree
rooted at v are labeled one.
Corollary 6.2. Let T be a union tree with l leaves and the bottom-up linking
property. Then n 1 unions and m nds can be performed in O(m(m; l)
time.
Proof. Let the leaves of T be classed as special and all internal vertices classed
as ordinary. When the union indicated by edge fx; p(x)g occurs, all descendants of
x, and in particular at least one leaf, are in the same set as x. Therefore the union
sequence has the property in the hypothesis of Theorem 6.1.
Alstrup et al. [1997] prove a variant of Corollary 6.2, with the m(m; l) term
replaced by (l log l +m), which su-ces for their purposes. They derive the weaker
result by processing long paths of unary vertices in T outside the standard set union
data structure. We apply the standard set union data structure directly to T ; we
need only weight the leaves of T one and the internal vertices of T zero.
6.2 Application to Dominators
Recall the denition of special vertices from Section 3.2: a vertex is special if all of
its children are roots of nontrivial microtrees.
Theorem 6.3. The (n) links and (m) evals performed during the computation
of pxdoms and by the algorithm IDOM require O(n +m) time.
Proof. Consider the subtree T of D induced by the trivial microtree roots. All
the links and evals are performed on vertices of T . The special vertices of D are
precisely the leaves of T . We can view T as the union tree induced by the links.
The links are performed bottom-up, due to the reverse DFS processing order.
As shown in Section 3.2, there are O(n=g) special vertices in D and thus O(n=g)
leaves of T . We choose log 1=3 n, which su-ces to compute iidoms in linear
time. By Corollary 6.2, the link-eval time is thus O(m(m; n= log 1=3 n) n). The
theorem follows, since m  n and (m;
Our algorithm is completely general: it runs in linear time for any input
owgraph
G. Corollary 6.2, however, implies that, implementing union-nd as described
above, the standard LT algorithm [Lengauer and Tarjan 1979] actually runs in
linear time for all classes of graphs in which the corresponding DFS trees D have
the following property: the number l of leaves of D is su-ciently sublinear in m so
that (m;
A New, Simpler Linear-Time Dominators Algorithm  21
7. IMPLEMENTATION
This section describes our implementation, which diers somewhat from our earlier
description of the algorithm for e-ciency reasons. The input is a
owgraph in
adjacency list format, i.e., each vertex v is associated with a list of its successors.

Figure

presents the top-level routines, which initialize the computation, perform
a depth-rst search and partition the DFS tree into microtrees, and compute
dominators. The initialization code creates and initializes the memoization tables.
The partitioning code assigns DFS numbers, initializes the vertices and stores
them in an array, vertices, in DFS order, computes the size of the subtree rooted at
each vertex, and identies microtrees using the subtree sizes. Each vertex is marked
Plain, MTRoot, or TrivMTRoot, depending on whether it is a nonroot vertex in a
microtree, the root of a nontrivial microtree, or the root of a trivial microtree.
Also, each vertex is assigned a weight to be used by the link-eval computation:
special vertices (recall that a vertex is special if all of its children are roots of
nontrivial microtrees) have weight one, and ordinary vertices have weight zero.
(See Lengauer and Tarjan [1979] for the implementation of link and eval.) Finally,
we initialize an array, pmtroot, to contain parent(v) for each v. This array will
eventually store parent(root(micro(v))) for each v. By initializing it to the vertex
parent, we only have to update it for vertices in nontrivial microtrees, which we
will do in ProcessMT below.
The code to compute dominators given the partitioned DFS tree diers from our
earlier presentation in two ways. First, we combine the processing of vertices and
buckets into a single pass, to eliminate a pass over the vertex set, as do Lengauer
and Tarjan [1979]. Second, we separate the code for processing trivial microtrees
from the code for processing nontrivial microtrees, which allows us to specialize
the algorithm to each situation, resulting in simpler and more e-cient code. These
changes, which are simple rearrangements of the code, do not alter the time complexity
of the algorithm.
Computedom calls ProcessV, to handle trivial microtrees, and ProcessMT, to
handle nontrivial microtrees. ProcessV, shown in Figure 11, computes the xdom
and pxdom of v, stores v in the appropriate bucket, links v to its parent, and then
processes the bucket of v's parent. This code exhibits both of our changes. First,
we follow the LT approach to combining the processing of vertices and buckets:
we link v to p, its parent, and then process p's bucket. Immediately following the
processing of v, only vertices from the subtree rooted at v are in p's bucket. Adding
the link from v to p completes the path from any such vertex to p, which allows us
to process the bucket. Second, we exploit that idom(v) is guaranteed to be outside
v's microtree, thereby eliminating a conditional expression.
ProcessMT (Figure 12) performs similar steps but is more complex, because it
processes an entire microtree at once. The rst step is to nd the microtree's root.
Since the vertices in a microtree have contiguous DFS numbers, we can nd the
root by searching backward from v in the vertices array for the rst vertex that is
marked as a nontrivial microtree root. Once we have the microtree root, we update
pmtroot(v) appropriately for each v in the microtree. Then we (1) compute the
xdom of each vertex in the microtree and an encoding for the augmented graph
that corresponds to the microtree, (2) compute iidoms, (3) compute pxdoms, and
22  Adam L. Buchsbaum et al.
Initialize computation
Partition(root)
status(root) TrivMTRoot
Computedom(root)
Partition(Vertex v)
Assign DFS number to v
Mark v as visited
bucket(v) NULL
link(v) NULL
label(v) dfsnum(v)
status(v) Plain
For s 2 successors(v) do
If s has not been visited then
endif
Add v to predecessors(s)
done
If size(v) > g then
If all v's children are Plain then
Mark the Plain children of v in DFS tree with MTRoot
status(v) TrivMTRoot
endif
Computedom(Vertex root)
For in reverse DFS order do
ProcessV(v)
elseif v has not been processed
ProcessMT(v)
endif
done
For in DFS order do
If samedom(v) 6= NULL then
endif
done
Fig. 10. Pseudocode for computing dominators.
A New, Simpler Linear-Time Dominators Algorithm  23
ProcessV(Vertex v)
label(v) dfsnum(v)
For do
If label(p) < label(v) then
label(v) label(p)
endif
If dfsnum(p) > dfsnum(v) then
evalnode
If label(evalnode) < label(v) then
label(v) label(evalnode)
endif
endif
done
Add v to bucket(vertices[label(v)])
For do
z
else
samedom(w) z
endif
delete w from bucket(parent(v))
done
Fig. 11. Pseudocode for processing trivial microtrees.
(4) process the bucket of the parent of the microtree root.
We compute xdoms and the microtree encoding together, because both computations
examine predecessor arcs. The microtree encoding is simple: two bits for
each pair of microtree vertices, plus one bit for each blue arc. During this computa-
tion, we also identify a special class of microtrees: a microtree is isolated if the only
target of a blue arc is the microtree root. We will use this information to speed the
computation of pxdoms.
The iidom computation uses memoization to maintain the linear time bound.
To increase its eectiveness, we remove unnecessary bits and eliminate unnecessary
information from the microtree encoding used to index the memoization tables.
First, we remove the bits for self-loops. Second, we exploit that a blue arc to
v implies that iidom(v) 62 micro(v) and that none of the information about v's
internal arcs is useful. In particular, since we know that the root of the microtree
is always the target of some blue arc, we eliminate from the encoding the bits for
arcs into the root. These changes reduce the size of the iidom encoding from g 2 +g
to bits (from 12 bits to six, for In addition to reducing the size
of the encoding, we can reduce the number of populated slots in the memoization
table, using the same observation. If there is a blue arc into a nonroot vertex, w,
we zero the remaining bits for arcs into it, because they are irrelevant. We do not
ProcessMT(Vertex v)
Find mtroot in vertices starting from v
initialize encoding
isolated true
For do
label(v) dfsnum(v)
For do
Include (p; v) in encoding
else
Include blue arc to v in encoding
If v 6= mtroot then
isolated false
endif
If label(p) < label(v) then
label(v) label(p)
endif
If dfsnum(p) > dfsnum(v) then
evalnode
If label(evalnode) < label(v) then
label(v) label(evalnode)
endif
endif
endif
done
done
iidomencoding reduced encoding
If iidommemo[iidomencoding] is not dened then
iidommemo[iidomencoding] Computeiidom(encoding)
endif
iidoms iidommemo[iidomencoding]
If (isolated) then
else
endif
For do
delete w from bucket(parent(mtroot))
done
Fig. 12. Pseudocode for processing nontrivial microtrees.
A New, Simpler Linear-Time Dominators Algorithm  25
IsolatedPush(microtree MT; int iidoms[ ])
mtroot MT [0]
for do
label(v) label(mtroot)
done
Add mtroot to bucket(label(mtroot))
Fig. 13. Pseudocode for pushing in isolated microtrees.
remove these bits, because we want a xed-length encoding. (The bits are extra
only when there is a blue arc into w.) Once we compute the reduced encoding, we
look it up in the memoization table to determine if futher computation is necessary
to determine the iidoms. We use the O(n 2 )-time bit-vector algorithm [Aho et al.
1986] augmented to exploit the blue arcs, when necessary.
The iidoms are expressed in terms of a DFS numbering of the augmented graph.
We translate the augmented graph vertex into the corresponding vertex in the
current microtree by adding its secondary DFS number to the primary DFS number
of the root of the microtree.
We have implemented two forms of Push. The rst, shown in Figure 13, is
a simplied form that can be used for isolated microtrees. The absence of blue
arcs into nonroot vertices implies that (1) the xdom of the microtree's root is
the pxdom of all vertices in the microtree and (2) the immediate dominators of
nonroot vertices will be local to the microtree (that is,
root(micro(v))). The root vertex has a nonlocal idom, so we simply add it to
the bucket of its pxdom.
The second, shown in Figure 14, handles the general case. First, we compute
strongly connected components (SCCs) using memoization. In this case, the memoization
is used only for e-ciency. As with the iidom calculation, we use a reduced
encoding for SCCs. The SCC encoding, which uses g 2 g bits, does not include
self-loops or blue arcs, since neither aects the computation. We compute SCCs
using the linear-time two-pass algorithm from Cormen et al. [1991]. Given the
SCCs (either from the memoization table or by computing them), we process them
in topological order: we nd the minimum of the xdoms of the vertices within
the SCC and the incoming pxdoms, and then assign this value to each vertex
as its pxdom. Given v's pxdom and iidom, we either assign idom(v) directly, if
or we put v into the appropriate bucket.
After pushing, we nish by processing the bucket of pmt, the parent of the mi-
crotree's root. Any vertex in the bucket must have pmt as its immediate dominator.
By denition, the pxdom of a vertex, v, in the microtree, is the minimum pxdom
along the path from pmt to v. As a result, we can skip the eval on any vertex in
pmt's bucket and assign pmt as the immediate dominator directly.
8. RESULTS
This section describes our experimental results. It would be interesting to compare
our algorithm (BKRW) with that of Alstrup et al. (AHLT) [1997], to judge relative
constant factors, but AHLT relies on the atomic heaps of Fredman and Willard.
26  Adam L. Buchsbaum et al.
mtroot MT [0]
sccencoding reduced encoding
If sccmemo[sccencoding] is not dened then
sccmemo[sccencoding] Computescc(mtroot; encoding)
endif
For in topological order do
For do
If iidoms[secdfsnum(v)] 62 MT then
Add v to bucket(label(v))
else
endif
done
done
Fig. 14. Pseudocode for pushing in the general case.
Atomic heaps, in turn, are composed of Q-heaps, which can store only log 1=4 n
elements given O(n) preprocessing time. The atomic heap construction requires
Q-heaps that store 12  log 1=5 n elements. For atomic heaps, and thus the AHLT
algorithm, to run in linear time, therefore, n must exceed 2 12 20
[Fredman and
(Alternatively, one can consider AHLT to run in linear time, but
with an impractically high additive constant term.) Alstrup et al. [1997] provide
variants of their algorithm that do not use atomic heaps, but none of these runs
in linear time. Ours is thus the only implementable linear-time algorithm, and we
therefore compare our implementation of BKRW with an implementation of the LT
algorithm derived from their paper [Lengauer and Tarjan 1979].
We performed two sets of experiments. The rst set used
owgraphs collected
from the SPEC 95 benchmark suite [SPEC 1995], using the CFG library from the
Machine SUIF compiler [Holloway and Young 1997] from Harvard. 3 (Six les from
the integer suite could not be compiled by Machine SUIF v. 1.1.2 and are omitted
from the data.) The second set used some large graphs collected from our Lab.
We performed our experiments on one processor of an eight-processor SGI Origin
2000 with 2048MB of memory. Each processing node has an R10000 processor
with 32KB data and instruction caches and a 4MB unied secondary cache. Both
implementations were compiled with the Mongoose C compiler version 7.0.
We report aggregate numbers for the SPEC test set, because it contains a large
number of
owgraphs. Table I reports the sizes of the
owgraphs, averaged by
benchmark. Table II contains average running times for LT and for BKRW with
microtree sizes of two and three. Figure 15 displays a scatter plot in which each
3 Machine SUIF is an extension of the SUIF compiler [Amarasinghe et al. 1995] from Stanford.
We used Machine SUIF version 1.1.2.
A New, Simpler Linear-Time Dominators Algorithm  27

Table

I. Graph Sizes, Averaged Over the Flowgraphs
in Each Benchmark, for the SPEC 95 Flowgraphs
Benchmark Number of Average Average
Flowgraphs Vertices Arcs
CINT95 Suite
129.compress
132.ijpeg 524 14 20
147.vortex 923 23 34
134.perl 215
CFP95 Suite
145.fpppp 37 19 26
103.su2cor 37
104.hydro2d 43 35 46
125.turb3d 24 52 71

Table

II. Running Times on the SPEC 95 Flowgraphs, Averaged Over the Flow-
graphs in Each Benchmark. The Numbers in Parentheses Measure the Dier-
ence Between the Two Algorithms, as Computed by the Following Formula:
LT  100:0. Positive Numbers Indicate That LT is Better; Negative Numbers
Indicate That BKRW is Better.
Benchmark LT BKRW
CINT95 Suite
130.li 20.01 us 33.91 us (69.49%) 36.99 us (84.90%)
129.compress 22.61 us 37.62 us (66.42%) 43.84 us (93.92%)
132.ijpeg 25.46 us 40.43 us (58.78%) 45.86 us (80.11%)
147.vortex 36.70 us 53.59 us (46.02%) 61.29 us (67.00%)
us 56.61 us (43.93%) 63.73 us (62.04%)
099.go 50.39 us 69.87 us (38.66%) 79.37 us (57.51%)
126.gcc 66.56 us 87.87 us (32.01%) 95.61 us (43.63%)
134.perl 89.54 us 112.23 us (25.34%) 121.13 us (35.28%)
CFP95 Suite
145.fpppp 32.75 us 46.63 us (42.37%) 49.33 us (50.61%)
us 53.14 us (37.93%) 59.90 us (55.47%)
107.mgrid 38.36 us 53.72 us (40.02%) 60.32 us (57.23%)
103.su2cor 46.74 us 62.06 us (32.78%) 67.28 us (43.95%)
104.hydro2d 49.99 us 66.71 us (33.45%) 72.82 us (45.68%)
146.wave5 51.71 us 68.45 us (32.38%) 74.46 us (44.00%)
125.turb3d 73.66 us 103.56 us (40.60%) 110.36 us (49.82%)
us 99.01 us (26.60%) 106.72 us (36.46%)
101.tomcatv 174.60 us 210.20 us (20.39%) 215.20 us (23.25%)
28  Adam L. Buchsbaum et al.
Number of vertices1.52.5
Number of vertices101000
Number
of
flowgraphs
Fig. 15. Relative dierences in running times of BKRW and LT (for 3). There is a
point in the top plot for each
owgraph generated from the SPEC 95 benchmarks. The bottom
plot displays the number of
owgraphs for each respective number of vertices. (Note that the
y-axis on the bottom plot represents a logarithmic scale.)
point represents the running time of BKRW (with microtrees of size two or three)
relative to LT on a single
owgraph. The plot shows that the overhead of BKRW is
larger than that of LT on small graphs, but that the dierence tails o to about 10%
quickly. For this gure, we combined the data from the integer and
oating-point
suites; separating the two, as in Table II, would yield two similar plots.

Table

III lists our large test graphs, which come from a variety of sources, along
A New, Simpler Linear-Time Dominators Algorithm  29

Table

III. Graph Sizes for the
Large Test Graphs
Graph Vertices Arcs
ATIS 4950 515080
Phone
2048 4095 7166
with their sizes. The ATIS, NAB, and PW graphs are derived from weighted
nite-state automata used in automatic speech recognition [Pereira and Riley 1997;
Pereira et al. 1994] by removing weights, labels, and multiple arcs. The Phone
graph represents telephone calling patterns. The augmented binary graphs (AB1
and AB2) were generated synthetically by building a binary tree of a given size
(shown in the table as the graph's label) and then replacing each leaf by a sub-
graph. See Figure 16. The AB1 graphs use the subgraph shown in Figure 16(b),
and the AB2 graphs use the subgraph shown in Figure 16(c). These graphs were
designed to distinguish BKRW from LT. The subgraphs will be treated as isolated
microtrees in BKRW, which means that all the nonroot vertices in a microtree will
have dominators within the microtree and that the back and cross arcs will be handled
cheaply (without evals) by BKRW. In particular, calls to eval related to these
arcs will be avoided by BKRW, and as a result, no links in the link-eval forest will
be compressed by BKRW.
We observed that, as expected, BKRW performs fewer links and evals than does
LT. Running time is a more telling metric, however, and we present the running
times for our experiments in Table IV. For the speech and Phone graphs, the
overhead of processing the microtrees, which includes initializing the memoization
tables, computing iidoms, computing microtree encodings, and pushing, outweighs
the savings on calls to link and eval. BKRW does outperform LT on the larger
augmented binary graphs. This is to be expected, since BKRW has substantially
fewer calls to eval and compresses zero links for these graphs. In addition, the
overhead of processing the microtrees is low, because they are all isolated. Note
that the improvement of BKRW over LT decreases as the graphs get larger. The
benet gained by our algorithm is small relative to the cost due to paging, which
increases as the graphs get larger.
(a)1(b)13
(c)
Fig. 16. (a) T k is a k-depth binary tree. Augmented binary graph AB1 (respectively, AB2) is
generated by replacing each leaf M i with the subgraph shown in (b) (respectively, (c)).

Table

IV. Running Times on the Large Test Graphs. The Numbers in Parentheses
Measure the Dierence Between the Two Algorithms, as Computed by the Following
LT  100:0. Positive Numbers Indicate That LT is Better; Negative
Numbers Indicate That BKRW is Better.
Graph LT BKRW
ATIS 384.50 ms 423.38 ms (10.11%) 427.25 ms (11.12%)
ms 2836.25 ms (3.55%) 2844.75 ms (3.86%)
ms 3195.98 ms (2.20%) 3189.15 ms (1.99%)
Phone 8313.62 ms 8594.75 ms (3.38%) 8616.38 ms (3.64%)
1024 2.00 ms 2.00 ms (0.00%) 2.50 ms (25.00%)
2048 5.00 ms 5.00 ms (0.00%) 5.00 ms (0.00%)
ms 10.00 ms (-9.09%) 12.00 ms (9.09%)
ms 22.00 ms (-9.74%) 23.00 ms (-5.64%)
ms 48.38 ms (-8.08%) 48.38 ms (-8.08%)
ms 117.50 ms (-7.75%) 117.88 ms (-7.46%)
2097152 20188.00 ms 19499.00 ms (-3.41%) 19498.38 ms (-3.42%)
1024 4.00 ms 3.12 ms (-21.88%) 4.00 ms (0.00%)
2048 8.00 ms 7.00 ms (-12.50%) 7.00 ms (-12.50%)
ms 15.62 ms (-2.34%) 16.00 ms (0.00%)
ms 34.25 ms (-4.86%) 32.75 ms (-9.03%)
ms 74.25 ms (-5.11%) 70.38 ms (-10.06%)
ms 182.12 ms (-4.14%) 175.38 ms (-7.70%)
2097152 51920.62 ms 51461.25 ms (-0.88%) 51029.88 ms (-1.72%)
A New, Simpler Linear-Time Dominators Algorithm  31
Given the overhead that BKRW pays for computing microtree encodings and
pushing and that  is very small, BKRW is surprisingly competitive, even for small
owgraphs, but these experiments suggest that LT is the algorithm of choice for
most current practical applications. LT is simpler than BKRW and performs better
on most graphs. BKRW performs better only on graphs that have a high percentage
of isolated microtrees.
9. CONCLUSION
We have presented a new linear-time dominators algorithm that is simpler than
previous such algorithms. We have implemented our algorithm, and experimental
results show that the constant factors are low.
Rather than decompose an entire graph into microtrees, as in Harel's approach
to dominators, our path-compression result allows microtree processing to be restricted
to the \bottom" of a tree traversal of the graph. We have applied this
technique [Buchsbaum et al. 1998] to simplify previous linear-time algorithms for
least common ancestors, minimum spanning tree (MST) verication, and randomized
MST construction. We also show [Buchsbaum et al. 1998] how to apply our
techniques on pointer machines [Tarjan 1979b], which allows them to be implemented
in pure functional languages.

ACKNOWLEDGMENTS

We thank Bob Tarjan, Mikkel Thorup, and Phong Vo for helpful discussions, Glenn
Holloway for his help with Machine SUIF, and James Abello for providing the phone
graph.



--R

Compilers: Principles

The Theory of Parsing

Dominators in linear time.
Manuscript available at ftp://ftp.
The SUIF compiler for scalable parallel machines.
Modern Compiler Implementation in C.


Introduction to Algorithms.

Optimal parallel veri

The program dependency graph and its uses in optimization.

A linear-time algorithm for a special case of disjoint set union
A linear time algorithm for
The ow analysis and transformation libraries of Machine SUIF.
A fast algorithm for


Linearity of strong postorder.
Object code optimization.
Postorder disjoint set union is linear.
Speech recognition by composition of weighted
In Finite-State Language Processing
Weighted rational transductions and their application to human language processing.
Optimal control dependence computation and the Roman chariots problem.
Algorithm 430: Immediate predominators in a directed graph.


Finding dominators in directed graphs.
Applications of path compression on balanced trees.
A class of algorithms which require nonlinear time to maintain disjoint sets.

accepted June
--TR
Worst-case Analysis of Set Union Algorithms
Compilers: principles, techniques, and tools
A linear algorithm for finding dominators in flow graphs and related problems
The program dependence graph and its use in optimization
Introduction to algorithms
Postorder disjoint set union is linear
Efficiently computing static single assignment form and the control dependence graph
Trans-dichotomous algorithms for minimum spanning trees and shortest paths
Data-Structural Bootstrapping, Linear Path Compression, and Catenable Heap-Ordered Double-Ended Queues
Linearity and unprovability of set union problem strategies I
Optimal control dependence computation and the Roman chariots problem
Modern compiler implementation in Java
Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators
Applications of Path Compression on Balanced Trees
A fast algorithm for finding dominators in a flowgraph
Immediate predominators in a directed graph [H]
Object code optimization
The Theory of Parsing, Translation, and Compiling

--CTR
Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, Corrigendum: a new, simpler linear-time dominators algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.383-387, May 2005
G. Ramalingam, On loops, dominators, and dominance frontier, ACM SIGPLAN Notices, v.35 n.5, p.233-241, May 2000
On loops, dominators, and dominance frontiers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.5, p.455-490, September 2002
Andrzej S. Murawski , C.-H. Luke Ong, Fast verification of MLL proof nets via IMLL, ACM Transactions on Computational Logic (TOCL), v.7 n.3, p.473-498, July 2006
Loukas Georgiadis , Robert E. Tarjan, Finding dominators revisited: extended abstract, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Loukas Georgiadis , Robert E. Tarjan, Dominator tree verification and vertex-disjoint paths, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Efficient Algorithm for Finding Double-Vertex Dominators in Circuit Graphs, Proceedings of the conference on Design, Automation and Test in Europe, p.406-411, March 07-11, 2005
Adam Buchsbaum , Yih-Farn Chen , Huale Huang , Eleftherios Koutsofios , John Mocenigo , Anne Rogers , Michael Jankowsky , Spiros Mancoridis, Visualizing and Analyzing Software Infrastructures, IEEE Software, v.18 n.5, p.62-70, September 2001
Ren Krenz , Elena Dubrova, A fast algorithm for finding common multiple-vertex dominators in circuit graphs, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
Elena Dubrova, Structural Testing Based on Minimum Kernels, Proceedings of the conference on Design, Automation and Test in Europe, p.1168-1173, March 07-11, 2005
compilers;dominators;microtrees;path compression;flowgraphs