In this video we are going to continue our
discussion on global data flow analysis by
taking a look at how global constant
propagation works in detail. To begin,
let's review what the conditions are to do
global constant propagation. So to replace
a use of a variable x by a constant K, we
have to know the following property. That
on, that on every path to the use of x,
the last assignment to the variable x is x
equals the constant K. Okay, And this has
to be true again, on every path to the use
of x. Now global constant propagation can
be performed at any point where this
property holds. What we're going to look
at in this video is the case of computing
the property for a single variable x, at
all program points. So we're going to take
one, we're going to focus on one variable
x, and we're going to compute whether it's
a constant at every program point. It's
easy to extend the algorithm to compute
this property for all variables. One
simple but very efficient way to do that
is just to repeat the computation once for
each variable in the, method body. The way
we are going to compute the information
that we want is to associate one of the
following values with the variable x with
every point in the program. And, let's
start with the last one here, we will
assign x this special value here, which is
pronounced top. If x is not a constant, So
if we can't figure out whether x is a
constant at a particular point in the
program, then we'll just say x is top at
that point. And this is going to be our
safe situation, it's always okay to say we
don't know what the value of x is, and
when we say that x has a value top, and we
say, we're essentially saying we don't
know whether x is a constant or not at
this point in the program, x could have
any value. Alright? Now, another
possibility is that we will say that x is
some constant c, okay? So this is a
particular constant And if we say that x
is a constant c at a program point, that
means, in fact, at that program point, we
believe or we have proven that x is
always, that con stant. Now, there is a
third possibility, Which is not
immediately intuitive, perhaps. But, as we
will see, plays a very important role in
algorithms for, for global constant
propagation And, in fact, in all global
data flow analyses. And that is bottom.
Okay, this value is pronounced bottom and
intuitively the idea anyway that is kind
of opposite of top. Alright, the
interpretation of bottom is going to be
this statement never executes. Alright?
So, when we don't know whether a statement
is even executed at all, we will say that
x, at that point, has a value bottom,
Meaning that, as far as we know, that
point in the program is never reached. It
doesn't matter what the value of x is at
that point, because that statement never
executes. Alright? So we're going to
assign x one of these three kinds of
values. Either bottom, some constant, or
top. Let's begin by working through an
example by hand And our goal is going to
be for every program point to decide
whether x could be a constant definitely
not a constant, or whether we think that
statement might not ever execute. Okay, so
executions will began at the top of this
control flip graph so this the enter
point. And before executions begins we
don't anything about the value of x. So
I'm not making any assumptions about what
code came before this basic block And so
it would be safe to say x has some unknown
value. We don't know what the value of x
is it could be anything. So x is equal to
top is the property that we want entry to
the first basic block Now after the
assignment x=3. [inaudible] Indicate
there, where, what point we're talking
about. So, after the assignment x=3, we'll
definitely know that x is the constant
three. Alright, now there's something here
that's worth pointing out Which is that
our program points, the points that we're
attaching, this knowledge to, or these,
these facts to Are in between the
statements. So, when I say x=3 at this
program point, what I mean is that after,
after this assignment has executed. X=3,
but before this predicate of th e
conditional has executed, I know that x is
equal to three, okay. So, program points
are in between statements, and there's a
program point before and after every
statement. Alright so the next thing that
happens is this conditional branch. Notice
that the branch doesn't update x doesn't
even refer to x. So after the branch
executes we'll definitely knows that x is
still equal to three on both branches. Now
let's do the right hand branch. The next
thing that happens is the assignment to Y
that would not affect the value of x. So
after the assignment to Y we'll still know
that x=3 alright. Now let's take a look at
the left hand branch. So the first thing
that happens over here is another
assignment to Y. Well that won't affect
the value of x. After the assignment of Y
we'll know that x is still equal to three.
And now comes to the assignment of x.
Alright. So after this assignment happens
at this program point we're going to know
that the value of x is different. We're
going to know that x=4. Alright so now
after this statement we know x is equal to
four and after this statement over here we
know x=3 alright. Now what do we know then
about what happens before, This statement,
okay? The a=2<i>x. And I just want to point</i>
out here. I said that there's a program
point before and after every statement And
so this program point, here, which is
before this assignment to a is different
from the program points that are after x=4
and y=0. So intuitively, after x=4, we
know that we're still on this path over
here on the left And so we know that X=4
and over here after Y=0, we still know
that we're on this path is X=3. But. When
we reach the point before A=2 times x, we
no longer know which path we're coming
from. This is the point of the merge of
these two paths that both lead to this
statement. And what can we say about the
value of x here? Well. There's no constant
that we can assign to x. Because on one
path, x is three And on the other path, x
is four. And so what we have to say here
is that before this assignment execut es,
a=x, sorry, X is equal to top. We don't
know what the value of x is Another way of
saying it is we know, we, we don't know
that x is a constant. So after the
assignment executes, it doesn't affect the
value of x, we will also have that x is
equal to tau Now notice that once we have
the global constant information, once we
know for every program point, what the
state of x is, it's going to be very easy
to perform the optimization. We simply
look at the information associated with
the statement, and that will tell us
whether x is a constant when that
statement executes, or not And if x is a
constant at that point, then we can
replace that use of x by the constant And
crucial question of course is how do we
compute these properties. So, we did this
example by hand that how, in a systematic
fashion, an arbitrary control flow graph
do we actually compute these properties
for x for every program point. Now we're
ready to talk about data-flow analysis
algorithms and there's one basic principle
that you see in all of these algorithms
that's worth mentioning right away. And
that's that the analysis of a complicated
program can be expressed as a combination
of very simple rules that relate the
change in information between adjacent
statements. So we're just going to focus
on local rules. And the way we're going to
build our global data flow analysis is
actually by a combination of rules that
look only at a single statement and its
neighbors. The idea behind the rules is
going to be the push or transfer
information from one statement to the next
And so for each statement S, we're going
to compute information about the value of
x immediately before and after S. Remember
that's where, those are the program points
that we want to attach information to. So
in particular we're going to have a
function C. It stands for constant
information And C will take three
arguments, takes the name of the variable,
x. It takes the statement that we're
talking about The particular statement in
the program that we're looking at And then
e ither in Or out and this is what
distinguishes the value of x before S
executes versus the value of x after S
executes. We're going to be defining a set
of transfer functions that push
information, or transfer information from
one statement to another And in the rules
for constant propagation we need to talk
about a statement and its predecessors. So
we're going to say that every statement s
has some set of immediate predecessors p1
through pn. Alright? [inaudible] either of
these statements that lead in one step to
the statement s. Let's do our first rule.
So we have a statement S and it has some
set of predecessor statements, P1, P2, P3,
P4 And the situation that we're interested
in here is, let's assume that x is top. At
the program point after one of these
predecessors. So, after some predecessor,
it doesn't matter which one, if it happens
that x is top at the program point after
that predecessor, well, then x has to be
top before the execution of s. Okay? So
that's what this rule says, it says if the
out of any predecessor, for x is top, then
the in of s for x is also top. Alright,
and this makes sense. It says that if we
don't know whether x is a constant on some
path that leads to s, well then, we don't
know that x is a constant at s. Because
for all we know, execution came down that
particular, came from that particular
predecessor. And so, we can't make any
prediction about whether s is, whether x
is a constant before s executes. Now let's
look at another situation. Let's say that
x is some constant C. After the execution
of some predecessor And that on a, after
another predecessor a distinct predecessor
x is a different constant D. So D is not
equal to C. Well then what do we know
about x at the program point before s
executes? Well, we don't know anything. X,
has to be top, because we don't know which
constant, s will be, since we don't know
which path will reach s at run time. And
this is the situation that we saw in the
example we did by hand. Another
possibility is that the predecessors all
agree o n what the, the value of x could
be. So let's say that we have, you know,
predecessor here and that after it
executes x is known to be the constant c
and x is known to be the constant c after
this predecessor And x is known to be the
constant c after this predecessor. There's
one other possibility. Let's say that
after this predecessor over here, all we
know is that x is bottom. Okay, and so
what the rule says is that if you have
this situation where either. X has the
property bottom after a predecessor. Or,
all the predecessors agree on the
particular constant that x could be. Then
before, at the program point before s
executes, we know that x, is going to
guar-, is guaranteed to be the constant c.
And if you think about it for a second,
it's easy to see why this is correct.
First of all, clearly, if we come along
one of the paths, where x is known to be
the constant c, since they all agree And
then when we get to s, x will definitely
have the value c. What about the bottom
case? Well, remember what that means. That
means that this statement is never
reached. So there's some predecessor P
here, which never executes. Which means if
P never executes, then we could never
reach S along this path from P. So the
only paths that will reach S are the ones
where x is known to be a constant. Alright
so that's why it's okay in this situation
say that x if x if control if execution
reaches S at all its guaranteed to reach
it in a state where x is the constant C.
One last possibility is let's say x is
bottom for all the predecessors. Okay? And
what does that mean? Well, that means that
every predecessor of S never executes, so
they're all unreachable. And therefore, if
every predecessor of x never executes, S
itself can never execute, and so we can
conclude that entry to S, x is bottom. The
first four rules that we just looked at
relate the out of one statement to the in
of the next. We also have to have rules
that relate the in of a statement to the
out of the same statement. So we have to
push information from the input o f a
statement to the output of the same
statement. So, once again, there are
several cases. And let's take a look at an
easy one first. If x is bottom, on
[inaudible], if the program point before
s. Well that says that [inaudible], that s
is never reached, that x never executes.
And therefore, x will be bottom, after, s,
after s as well. So if the program point
before s is never reached, the program
point after s definitely can't be reached
either. Another possibility is that we're
assigning x to constant C in this
statement. In that case the out of the
statement is going to be equal to C.
Alright, so it doesn't matter what the
state of x was before the statement, after
we execute the statement, x will, be the
constant C And I should say there is a
conflict with the previous rule. Okay, it
could be that x is bottom, before the
statement. So rule six, has lower priority
than rule five, so we, so if we could say
that x is bottom after the statement, we
would prefer you to say that. So rule five
would be applied first, and then if rule
five does not apply. So if x is some other
constant D, or x is equal to top. Then we
would apply this rule and we would
conclude that x is the constancy
afterwards. So that makes sense. If x is d
or x is the, is top that means that
control, as far as we know, can reach this
statement. And then what we're saying here
is, well, after the execution of this
statement, if control can reach this
statement after the execution of it, x is
guaranteed to be the constancy. Another
possibility is that we have an assignment
to x but the right hand side is more
complicated than a constant. So this case
is for everything other than the constant
assignment. Okay, so this F here just
stands for some More complicated
expression than just a simple constant,
and in this case we, we're just going to
say we don't know what the value is, we're
not going to try, to guess what the result
of that computation is, and we'll just
say, that x is equal to top. X, we don't
know what the value of x is after the exec
ution of this statement And once again,
rule five takes precedence, so if rule
five applies, then we would apply, then,
then we would use that rule instead of
rule seven. But, if control can reach this
statement, so up here x is equal to some
constant c, or x is equal to top. We'll
apply rule seven and conclude that x is
top after the statement and finally Rule
eight, another possibility is that we're
assigning to some variable other than x.
And in that case, if x was equal to, some
value, k, before the statement then we
just keep that value. Okay, so whatever x
was before the statement bottom, a
constant, or top, if the assignment is to
some other variable other than x then x
will have the same property, after the
statement executes. Now, we can put these
rules together into an algorithm. For
every entry point, for every, entry
statement to the program, we're going to
say on entry that we don't know anything
about the value of x. So the program point
before that entry point we're gonna say
that x has an unknown value, top. And then
everywhere else we're going to say that
the value of x, is bottom. Okay. And this
is actually important. So we're going,
what this intuitively is doing, is its
saying, well, so far as we know. Except
for the entry point to the program, which
can definitely be executed. We don't know
whether any of the other statements in the
control flow graph are actually ever
executed And so we're going to assume
initially, that they're not. And we're
just going to say that x has the value
bottom everywhere except at an entry point
And now what we're going to do is a kind
of constraint satisfaction algorithm.
We're going to pick some statement that
doesn't satisfy one of the rules, one
through eight. And then we're going to
update it using the appropriate rules. So
we'll look for places in the control flow
graph where the information is
inconsistent according to the rules And
then we'll update, the information, to
make it consistent with the rules. Let's
take a look at our example again. So,
we're going to start out by saying x is
equal to top, at the entry point, and then
we're going to have all of our other
program points And let me indicate them
here. Okay, so these are all the other
program points that we have to be
concerned with. And there again, there's a
program point before and after every
statement. And we are going to say the x
is equal to bottom for all of these. So,
again what this means is, that so far as
we know, control doesn't reach any of
these points. We have not yet proven to
ourselves that any of these statements can
execute And now we just look around in the
program and try to find places, where the
information is inconsistent according to
the rules, and then we update the
information. Let me switch colors here.
So, as, when we begin, the information is
consistent everywhere except at this first
statement, because if x is top. Before,
and we're assigning x to value three.
Well, then we should not have x is equal
to bottom as the result. In fact this
should be x is equal to three. Should be
the appropriate information here And once
we update that, then we see that this next
statement is inconsistent, because now we
know this statement is reachable. We have
a statement here and we're concluding that
the point after is not reachable which is
not, Not correct according to the rules.
So that I believe that this is an
application of rule eight. We have a
statement here that doesn't refer to x as
and so whatever the value of x was before
the statement becomes the value of x after
the statement. So that becomes x is equal
to three And then, now we can see that
this information is inconsistent. The out
of the statement here, is not consistent
with the in of the statement here. In this
case, you know, it's just one predecessor.
And so, the, the value should be the same.
So x should be three. At this point, and
similarly, x should be three at this
point. Here we have an assignment to a
variable other than x. That should,
information should be the same before and
after the statements. Same thing here, Now
we have an assignment x. The point before
that assignment is reachable And so since
this is a constant assignment we should
know that x is that constant after the
assignment. So here again we have an in
and out issue, so the out of this
statement is not consistent with the in of
this statement. So this is gonna have to
be updated. But now, what should this be?
Well, we have two inconsistent
predecessors And so this has to be top And
then finally, an assignment to x, sorry,
an assignment to a state, To a variable
other than x. So the information should
just propagate across And that,
[inaudible] is updated like this. So now x
is known to be top afterwards And now, if
we look around at all. The program points,
we'd see that all the information is
consistent. All the rules, if you, if you,
if you check whether the information
before and after a statement or across a
statement. I'm sorry, or between
predecessors and successors is correct,
it's correct everywhere according to the
rules, and so we're done.