Java Reference
In-Depth Information
Node
Preds
(
Y
)
IN
Y
Soln
(
Y
)
Change?
Y
Marker
87
Marker
88
Marker
89
2
{
1
,
5
}
5
{
4
}
4
{
3
}
⊥
true
3
{
1
}
1
{}
2
{
1
,
5
}
5
{
4
}
⊥
⊥
true
4
{
3
}
⊥
3
{
1
}
1
{}
2
{
1
,
5
}
⊥
⊥
true
5
{
4
}
⊥
⊥
4
{
3
}
⊥
3
{
1
}
1
{}
2
{
1
,
5
}
⊥
⊥
5
{
4
}
⊥
⊥
4
{
3
}
⊥
3
{
1
}
1
{}
Figure 14.50: Iterative evaluation using the node order [2
,
5
,
4
,
3
,
1].
2. In the prior pass, node 4's value changed. Node 5's transfer function
copies its input to its output, so node 5's output changes from
to
⊥
during this pass. Thus, another pass is required.
3. When node 2 is considered in this pass, its input (formed by the
meet
of
the output of nodes 1 and 5) is
. Node 2's transfer function copies its
input to its output, so the output of node 5 changes from
⊥
to
⊥
.
4. Nothing changes in this pass, so iterative evaluation is finished.
The following observations can help to improve the performance of itera-
tive evaluation:
•
The change in solution at a given node
Y
need not require another round
of evaluation of
all
nodes in
N
eg
. The output of a transfer function can
change only if its input changes. Thus, the loop at Marker
86
need
only consider those nodes whose predecessors have a di
erent solution.
The set of nodes requiring evaluation can be maintained by a
worklist
,
initialized to
ff
N
eg
, and updated to include all successors of a node
Y
whose solution has changed. Elements can be taken from the
worklist
for
processing until the
worklist
is empty.
