Information Technology Reference
In-Depth Information
y=80
y = 80;
threshold = 100;
threshold=100
if (y > threshold) {
decrease = true;
} else {
decrease = false;
y>threshold
?
decrease=true
decrease=false
}
|y-threshold| > eps
?
while (|y-threshold| > eps) {
if (decrease) {
y-1;
} else {
y+1;
decrease
?
y=y-1
y=y+1
}
•
•
}
Fig. 2.
A simple control circuit
PL
program and its control flow graph
We can imagine to walk a partial evaluator through the control flow graph
(for the example on the right of Fig. 2) while maintaining a table of concrete
(i.e., constant) values for the program locations. In the example, that table is
empty at first. After processing the two initial assignments it contains
U
=
{
y
:=
80
(using the update notation of Section 2.2).
Whenever a new constant value becomes known, the partial evaluator attempts
to propagate it throughout the current control flow graph (CFG). For the example,
this
constant propagation
results in the CFG depicted in Fig. 3 on the left. Note
that the occurrences of
y
that are part of the loop have
not
been replaced. The
reason is that
y
might be updated in the loop so that these latter occurrences of
y
cannot be considered to be static. Likewise, the value of
decrease
after the first
conditional is not static either. The check whether the value of a given program
location can be considered to be static with respect to a given node in the CFG is
called
binding time analysis
(BTA) in partial evaluation.
Partial evaluation of our example proceeds now until the guard of the first
conditional. This guard became a
constant expression
which can be evaluated
to
false
. As a consequence, one can perform
dead code elimination
on the left
branch of the conditional. The result is depicted in Fig. 3 in the middle. Now
the value of
decrease
is static and can be propagated into the loop (note that
decrease
is not changed inside the loop). After further dead code elimination,
the final result of partial evaluation is the CFG on the right of Fig. 3.
Partial evaluators necessarily approximate the target programming language
semantics, because they are supposed to run fast and automatic. In the presence
of such programming language features as exceptions, inheritance with complex
localization rules (as in
||
threshold
:= 100
}
Java
), and aliasing (e.g., references, array entries) BTA
becomes very complex [14].
