Java Reference
In-Depth Information
procedure
simple
D
ominators
(
G
f
)
foreach
X
∈N
f
do
dom
(
X
)
←N
f
31
worklist
←
root
while
worklist
∅
32
do
Y
←
worklist
.
pickAndRemove()
33
newdom
←{
Y
}∪
dom
(
X
)
34
∈
E
f
(
X
,
Y
)
if
newdom
dom
(
Y
)
then
dom
(
Y
)
35
←
newdom
foreach
(
Y
,
Z
)
∈E
f
do
worklist
←
worklist
∪{
Z
}
36
end
Figure 14.17: Dominators algorithm.
This solution is a
fixed point
:
•
For each node
Z
under consideration, every node in
dom
(
Z
) does domi-
nate
Z
. For example, both
F
and
H
dominate node
H
.
•
Further application of Equation 14.4 at any node does not change the
solution at any node.
Although the system of equations is satisfied, we have obtained the
minimum
instead of
maximum fixed point
solution. In the above example, node
E
should dominate all nodes, but it appears only in
dom
(
E
). For each node
Z
,we
would like
dom
(
Z
)tobeas
large
as possible while satisfying Equation 14.4.
While establishing a fixed point solution of this system of equations, an
intermediate solution at node
Z
is obtained by applying Equation 14.4 to
the intermediate solutions at the predecessors of
Z
.Thedi
ff
erence between
successive solutions at node
Z
can only be attributed to the
intersection
(
)
operation in Equation 14.4 acting on changes in solutions at the predecessors
of
Z
.
If initially assuming
dom
(
Y
)
results in the minimum fixed point, then
we might (correctly) guess that initializing
dom
(
Y
)
=∅
= N
f
results in the max-
imum fixed point. Intuitively, the intersection operator whittles away at the
solution at each node in the flow graph, because set intersection can never pro-
duce a set larger than its inputs. To obtain the largest final solution at node
Z
,
we must trust (or, better yet,
prove
) that repeated applications of Equation 14.4
throughout the flow graph eventually stabilize to a safe fixed point.
Most data flow algorithms maintain a list of nodes or computations that
must be considered by the algorithm before it is done. The dominators algo-
rithm shown in Figure 14.17 maintains a
worklist
of nodes whose dominators
