Java Reference
In-Depth Information
...
...
−2 −1 0
1
2
Figure 14.59: Lattice for constant propagation of a single value.
can be taken. This solution is called the MOP solution. Thus, for distributive
frameworks, MOP
MFP. Examples of distributive frameworks include the
available expressions and live variables problems. Exercises 44, 46, and 49
explore the distributive nature of data flow frameworks in greater detail.
=
The last data flow problem we study in detail is constantpropagation,which
determines values that are constant over all executions of a program. Most
programmers do not intentionally introduce constant expressions. However,
such expressions often arise as artifacts of program translation. Interproce-
durally, constants can develop when a general method is specialized with
arguments that are constant.
We begin by considering the lattice that models a single constant value,
as shown in Figure 14.59. The lattice is conceptually infinite in width, unless
some bound is placed on constant values. No one constant is related (
)toany
other, so the constants are all at the same level in the lattice. The distinguished
element
⊥
represents that a value is
not
constant. The lattice reflects that if two
di
ff
erent constants meet (
∧
), then the result is
⊥
.
The distinguished element
requires some explanation. Lattice axioms
require that
∀
a
∈
A
,
a
∧=
a
.Thus,
cannot be any particular constant.
Instead,
represents a value that could be chosen by the compiler to suit its
purposes. Recalling that
is the initialized value for data flow evaluation, an
uninitialized variable can take on any value of interest without contradiction.
More generally, consider the programwhose control flow graph is shown
in Figure 14.60. Some nodes assign constant values to variables. In other
nodes, constant values may combine to create other constant values. We can
describe constant propagation as a data flow problem as follows:
