Java Reference
In-Depth Information
1
Data Flow Framework
Specification
2
3
f
3
2
{
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
}
A
∅
⊥{
4
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
}
a
b
a
⊇
b
a
∧
b
a
∪
b
5
6
Node
Transfer Function
f
6
3
f
3
(
in
)
=
in
∪{
3
}
6
f
6
(
in
)
=
in
∪{
6
}
7
f
7
(
in
)
=
in
∪{
7
}
7
f
7
all others
f
(
in
)
=
in
8
(a)
(b)
Figure 14.53: (a) Flow graph; (b) Data flow framework.
Definition 14.23
A lattice has
finite descending chains
if
∀
a
∈
A, the path
from a to
⊥
in the lattice is finite.
The above requirement does not insist that
A
is finite, but it does require a
limit on the number of times a solution can move toward
⊥
without actually
reaching
. Iterative evaluation can continue only if the solution at some node
continues to change. For monotone frameworks (Definition 14.22), a solution
at any point in the flow graph progresses toward
⊥
if it changes at all. Thus,
termination is guaranteed for any data flow problem whose lattice has finite
descending chains.
Termination is clearly essential for the optimization phase of a compiler.
Because an optimization phase typically calls for the solution of multiple data
flow problems, some understanding of the computational cost of each problem
is necessary for crafting the optimization phase. In this section we study a class
of data flow problems that converge as quickly as can be expected.
A flow graph and data flow framework are given in Figure 14.53. The meet
lattice's domain
A
is the set of all subsets (
power set
)of
⊥
{
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
}
.Ifit-
