Java Reference
In-Depth Information
The only node that changes on second computation is node 5. When
dom
(5) was first computed, its predecessor node 6 had dominators
N
f
,sothat
dom
(5)
. After node 4 is removed from
dom
(6), node 5 is placed on
the
worklist
and its recomputation establishes its dominators as
= {
1
,
4
,
5
}
{
1
,
5
}
.
The simple dominance algorithm is easy to program and performs e
ciently
for most flow graphs. Nonetheless, most compilers use the “fast” algorithm,
due to Lengauer and Tarjan [LT79], for the following reasons:
•
The fast algorithm requires only
O
(
is a func-
tion with
very
slow growth. Experimentally, the algorithm presented in
this section is faster than the algorithm in Figure 14.17 on all but the
smallest of flow graphs.
E
f
α
(
E
f
,N
f
)) time, where
α
•
The algorithmin Figure 14.17 computes the set
dom
(
Y
)
,but
the optimization problems we study do not usually require computing
all
of
Y
's dominators. For example, the algorithms discussed in Section 14.7
require only immediate dominance—information found in a dominator
tree. The fast algorithm directly computes the dominator tree, from
which all dominators of a node can be easily obtained.
={
X
|
X
Y
}
2
) space, while the faster algorithm
•
The dominators algorithm uses
O
(
N
f
requires only
O
(
N
f
)space.
The fast dominance algorithm is also a useful exercise in applying depth-first
numbering and traversing the DFST. These structures will also be used in
computing the
interval
partition of a flow graph in Section 14.2.9.
The term
fast
applies here because of the following result [LT79]. If a
graph has
m
nodes and
n
edges, then the best implementation of the fast algo-
rithm runs in
O
(
m
α
(
m
,
n
)isanextremelyslow-growing
functional inverse of the
Ackermann function
. In other words, the algorithm
runs in
almost linear time
in the size of the flow graph. The implementation
discussed here is a simpler formulation, also found in [LT79], which runs in
O
(
m
log
n
) time. A faster algorithm has been developed that runs in linear
time [GT04], but that algorithm is more complex and it uses structures similar
to the algorithm described here.
(
m
,
n
)) time, where
α
Observe that the dominators of each node
Y
in Figure 14.18 are ancestors
of
Y
in the DFST shown in Figure 14.12: For example, the dominators of node
8 include all of its ancestors. However, not all of a node's ancestors dominate
that node. For example, the dominators of node 9 do not include its ancestor
(node 2).