Java Reference
In-Depth Information
35. The
bit-vectoring data flow problems
earn their name from a common
representation for finite sets—the
bit vector
. In this representation, a slot
is reserved for each element in the set. If
e
∈
S
,then
e
's slot is
true
in the
bit vector that represents set
S
.
Describe how bit vectors can be applied to the available expressions
problem for a set of
n
expressions.
In particular, describe how a bit
vector is a
ff
ected by
(a) the transfer function at a node.
(b) the application of the meet operator.
36. The livevariablesproblem for a set of
n
variables can be solved as a data
flow problem.
(a) Define the formal framework, using the components given in Sec-
tion 14.4. The transfer function at node
Y
is defined by the following
formula (from Section 14.4.3):
f
Y
(
in
)
=
(
in
−
Kill
Y
)
∪
Gen
Y
Figure 14.47 shows how transfer functions model a node's behavior
for availableexpressions.O
er a similar set of diagrams and trans-
fer functions for livevariables. In particular, explain how
Kill
Y
and
Gen
Y
are determined for livevariables for a node
Y
.
(b) Now consider the use of bit vectors to solve live variables.The
transfer function can be implemented as described in Exercise 35.
How is the meet operation performed? What are
ff
and
⊥
?
37. Some optimization problems, such as constant propagation,arecon-
cerned with the flow of values in a program. One way to track such
values is to distinguish each definition of a given variable (e.g., x)by
giving each definition a unique name (as with SSA form).
Each assignment to x is called a
definition site
(
def
for short) of x.If
there are multiple defs of x, then these are suitably renamed so that they
are distinct. For example, the def of x at node 3 might be renamed as an
assignment to x
3
. Unlike SSA form, the renaming of x to x
3
is still a def
of x and not a def of a completely new variable name.
The reachingdefinitions problem can be stated as follows:
•
The only nodes of interest are those that assign to a variable. The
transfer function for all other nodes is simply
f
(
in
)
=
in
.
