Java Reference
In-Depth Information
Node
Y
Old
Pred
(
Y
)
New
New
picked by
dom
(
Y
)
dom
(
Y
)
worklist
Marker
33
Marker
34
Marker
36
⇒
1
N
f
{}
{
1
}
{
2
,
3
}
⇒
2
N
f
{
1
}
{
1
,
2
}
{
3
,
4
,
11
}
3
N
f
{
1
,
2
,
5
}
{
1
,
3
}
{
4
,
11
,
9
}
⇒
4
N
f
{
2
,
3
}
{
1
,
4
}
{
11
,
9
,
5
,
8
}
11
N
f
{
2
,
12
} {
1
,
2
,
11
}
{
9
,
5
,
8
,
12
,
13
}
⇒
9
N
f
{
3
}
{
1
,
3
,
9
}
{
5
,
8
,
12
,
13
,
10
}
5
N
f
{
4
,
6
}
{
1
,
4
,
5
} {
8
,
12
,
13
,
10
,
6
,
3
}
⇒
8
N
f
{
4
,
9
}
{
1
,
8
}
{
12
,
13
,
10
,
6
,
3
}
12
N
f
{
11
,
13
} {
1
,
2
,
11
,
12
} {
13
,
10
,
6
,
3
,
7
,
11
}
⇒
13
N
f
{
11
} {
1
,
2
,
11
,
13
} {
10
,
6
,
3
,
7
,
11
,
12
}
⇒
10
N
f
{
9
}
{
1
,
3
,
9
,
10
} {
6
,
3
,
7
,
11
,
12
}
6
N
f
{
5
,
8
,
10
}
{
1
,
6
}
{
3
,
7
,
11
,
12
,
5
}
⇒
3
{
1
,
3
}
{
1
,
2
}
same
{
7
,
11
,
12
,
5
}
⇒
7
N
f
{
6
,
12
}
{
1
,
7
}
{
11
,
12
,
5
}
⇒
11
{
1
,
2
,
11
} {
2
,
12
}
same
{
9
,
5
,
8
,
12
,
13
}
⇒
12
{
1
,
2
,
11
,
12
} {
11
,
13
}
same
{
5
}
⇒
5
{
1
,
4
,
5
}
{
4
,
6
}
{
1
,
5
}
{
6
}
⇒
6
{
1
,
6
}
{
5
,
8
,
10
}
same
{}
Figure 14.18: Dominators computation. An arrow before a node marks
that node's final computation of its dominators.
should be recomputed by applying Equation 14.4. The solution for all nodes
is initialized to
N
f
and the
worklist
is initialized to
root
by Marker
32
.The
call to
at Marker
33
picks
any
element to be removed from
the list and returned for assignment to
Y
. If the recomputation of a node
Y
's
dominators at Marker
34
produces a di
pick
A
nd
R
emove
erent solution at node
Y
, then the
successors of
Y
are placed on the
worklist
by Marker
36
because their solution
may consequently change.
We now apply the dominators algorithm to the flow graph of Figure 14.10.
The steps of the algorithm and the development of the dominator sets are
shown in Figure 14.18. Node 1 (the root) has no predecessors, so its solution
changes from
ff
N
f
to just itself, which causes its successors 2 and 3 to be placed
on the
worklist
. The first time 3 is taken from the
worklist
, its dominators
change from
, which causes nodes 4 and 9 to be added to the
worklist
. Node 4 was already on the
worklist
due to the change at node 2, so
the
worklist
expands only with node 9. The next time node 3 is taken from the
worklist
, no change results from recomputing
dom
(3), so the
worklist
does not
grow.
N
f
to
{
1
,
3
}
