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
}
.
14.2.7 Fast Dominance Algorithm
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).
 
 
Search WWH ::




Custom Search