Java Reference
In-Depth Information
•
Some assignments to a variable completely and certainly redefine
the variable. In such cases, the node generates a new def of the
variable and
kills
all other defs of the same variable name. Nodes
E
and
F
in Figure 14.43 completely and certainly define the variable
v
.
All other defs of
v
that reach node
E
cannot reach any further, and
the node generates the def
v
E
that propagates out of node
E
.
•
Some assignments assign to a name without certainty. For example,
the call to f at node
J
in Figure 14.43 might modify
v
(assuming
v
is
passed by reference), but it is di
cult to saywith certainty that
v
will
be modified. Such an assignment is called a
wounding definition
.
Any defs of
v
that reach node
J
continue to propagate forward,
along with
v
J
defined at node
J
.
•
Some assignments assign to a name, but not completely. For ex-
ample, an assignment to the array element
A
[
i
] assigns to the name
A
but does not completely modify
A
. Such an assignment is also
treated as a
wounding definition
.
•
When multiple paths converge at a node, the set of defs that prop-
agates forward is the
union
of the defs that propagate on the edges
into the node.
(a) Is this a forward or backward problem?
(b) What is the value of
(the best solution)?
(c) Describe how to model a node's behavior with a transfer function,
using Figure 14.47 as a guide.
(d) How are solutions summarized at common control flow points?
(e) Formally define the components (Section 14.4) of the reachingdefi-
nitions data flow framework.
(f) Prove or disprove that your framework is
rapid
.
(g) Prove or disprove that your framework is
distributive
.
38. Liveness shows that a variable is potentially of future use in a program.
The verybusyexpressionsproblemdetermines if an expression's current
value is
certainly
of future use. An expression
e
is very busy at a point
P
in a control flow graph if every path after point
P
contains a use of the
current value of
e
at
P
.
(a) Is this a forward or backward problem?
(b) What is the value of
(the best solution)?
(c) Describe the e
ff
ects of a node on an expression, using Figure 14.47
as a guide.