Java Reference
In-Depth Information
1
2
6
4
5
3
7
8
11
9
12
13
10
Figure 14.27: Dominator tree for the flow graph in Figure 14.10.
is transmitted on its outgoing edges.
Definition 14.15
A node Y is in the
dominance frontier
of X, denoted DF
(
X
)
,
if Y is just outside of (i.e., one edge away from) the shadow cast by making node
Xopaque.
More formally, DF
(
X
)
is the set of nodes Z such that X dominates a predecessor
Y of Z but does not strictly dominate Z:
DF
(
X
)
={
Z
|
(
∃
(
Y
,
Z
)
∈E
f
)(
X
YandX
Z
)
}
In Figure 14.16, nodes 4, 8, and 6 are in
DF
(
X
). A node can be in its own
dominance frontier. For example, node 11 has a predecessor (node 12) that is
dominated by node 11, but node 11 cannot strictly dominate itself. Therefore,
11
∈
DF
(11).
Dominance frontiers are useful for computing
control dependence
(Ex-
ercise 11) and
static single assignment
(SSA) form (Section 14.7). Based on
the above definition, a simple algorithm for computing dominance frontiers is
given in Figure 14.28. A clue to the ine
ciency of this algorithm is its use of
the potentially quadratic
full
dominance information at Markers
56
and
58
.
A reasonable approach for improving this algorithm is to limit the search to
the
immediate
dominators computed in Figure 14.24. Another improvement
comes from visiting nodes in a favorable order as compared with Marker
57
.
