In this video, we're going to look at
another global analysis called liveness
analysis. So, in the past several videos
we've looked at a procedure for globally
propagating constants through a control
flow graph And let's, here's, here's one
of the control flow graphs we've been
looking at and recall that this algorithm
that we discussed would be sufficient to
show that we could replace this use of x
here by the constant three. And once we do
that. This assignment x might no longer be
useful. It might not be used anywhere And
so we could potentially delete this
statement from the program And that would
be a real optimization, an important
optimization to do. However, we can only
do that if x is not used elsewhere in the
program. So let's be a little more careful
about what we mean by saying that x is not
used. So down here is a use of x, a
reference to x, in a statement. And,
clearly this particular reference to x,
is, use, picking up the value that's
defined by this right x here. So, we say
that the right of x here, is live. This
one is live. Okay, And what that means is
that the value may be used in the future.
So, live, equals, may be used. In the
future, Okay? So the value written to x at
this line of code maybe used by some
subsequent instruction And here it's not
just that it may be used. It's actually
guaranteed to be used because there's only
one path. And that one path has a
reference to x on it before there's
another assignment to x. Okay? So this
particular value of x as written here is
guaranteed to be used. But in general we
don't require that. We just mean there has
to be a possibility that it will be used.
Now in contrast let's take a look at this.
Other statement in this example, Here, we
assign x a value three but this assignment
x, this value of x is never used. This
one, is dead. Alright? Because the value
three here is overwritten by the value
four before there's any use of, the
variable x, Okay? So this particular right
to x will never see the light of day.
It'll never get used by any part of the
program. And we say that it is dead. So,
to summarize a variable x is live as a
statement S if, there exist some statement
that uses x. Okay. So, some other
statement S prime that uses x, and there
is some path from S to S prime and there
is no intervening assignments on that path
to x. Alright? So, there needs to be an
assignment to x, at some statement S there
is some path through the program that
reaches a read of x. Add sum statement to
S prime, and along that path, there is no
right to x, Okay? And if this situation
arises, then we say that this value
written in this first statement s is live.
Now if a value is not live, then it is
dead. And a statement that assigns to x is
going to be dead code if x is dead after
the assignment. So, if we know that
immediately after the assignment,
immediately after this assignment to x,
there is no possibility that a value of x
will be used in the future. Well then the
assignment was useless, and the entire
statement can be removed. Alright, So dead
assignments can be deleted from the
program, But notice that in order to do
that we have to have the liveness
information. We need to know whether x is
dead at this point. So, once again, what
we want to do is to have global
information about the control flow graph.
In this case, the property is whether x
will be used in the future. We want to
make that information local to a specific
point in the program, so we can make a
local optimization decision. Alright, And
just like for constant propagation, we're
going to define in a, an algorithm for
performing liveness analysis And it's
going to follow the same framework. If
we're going to express liveness in terms
of information transferred between
adjacent statements, just as we did for
copy of constant propagation And it's
gonna turn out that liveness is actually
quite, If it's simpler, or somewhat
simpler, than constant propagation, since
it's just a Boolean property. Eh, you
know, it's either true of false. Alright
So let's take a look at some of the rules
for liveness. So here, we're defining what
it means for x to be live at this point
here. So we're immediately after p is x
live And it's going to be live. Remember
what the intuition is. The intuition is
that a, the variable x is live right after
p if the value of x is used on some path.
On one of the paths that begin at p.
Alright, And so, in order to know whether
it's live, we're going to take the
liveness information at each of the input
points. So that would be here, here, here,
and here. So each of the successor
statements after p And we're gonna ask, is
x live at any of those points? So it's
just a big or over the liveness of x and
all of the successors of p And that's the
liveness of x at the out of p. Next, let's
consider the effect of individual
statements on the liveness of x. So, the
first rule is, that if we have a
statement, and it reads the value of x,
Okay? So here, we have an assignment
statement, and on the right hand side, it
refers to x, so its reading x Then, x is
live Before that statement. Clearly, x is
just about to be used on the end of this
statement, and so x is live at that point.
Alright? So if a statement, or if,
[inaudible], if a statement reads the
value of x, then the in of that statement,
x, is true. Sorry, the liveness of x is
true. A second case is when a statement
writes the value of x So here we have an
assignment to x And the rest of the
statement does not refer x Does not read
the value of x. So there's no x in E. Okay
So in this situation x is not live before
the statement. X is not live or we can say
that x is dead Before the statement And
why is that? Well, we're overriding the
value of x, so whatever value, x had
before this statement is never gonna be
read. Okay, Because the ee here, the
right-hand side of the assignment, doesn't
refer to x And, so, immediately before the
statement, the current value of x is never
gonna be used in the future. And so x is
dead at that point. And finally, the last
case is what if we have a statement that
does not refer to x? Okay, So it neither
reads no r writes x. Well, then whatever
the line this is of x after the statement,
it has the same liveness, before this
statement. So if x is live here. Then x
will be live here. Okay, and similarly, if
x is dead After the statement. Then x must
be dead before the statement. And that's
because x if x is not use in the future
after the statement S then it still want
be use in the future before the statement
S. Since the statement S neither reads nor
write x. So those are the only four rules
and now I can give the algorithm. So
initially we left the liveness information
for x be false at all program points And
then we repeat the following until all the
statements satisfy the rules one through
four, and just has it's the same algorithm
that we used for constant propagation. We
pick some statement where the information
is inconsistent and then up, update the
information at that statement with the
appropriate rule. So let's do a simple
example, something with a loop. So let's
begin, say by initializing x to zero, and
then what should our loop body do? Well,
we can check whether x is equal to ten,
and if it is, we'll, we'll exit, the loop
And let's assume that x is dead on exit.
So x is not refer to outside of the loop.
In other wise if x is not ten Then we will
increment x and we'll branch back to the
top of the loop. So this is a very, very
silly little program. It just counts to
ten and then exits. Well let's do the
lightness now to see where x is life. So
since x is dead here on exit it's clearly
gonna be dead on the out Of, of this,
conditional on this branch, Okay? So I
should say that x is not live. So we're
using [inaudible] here, so that's x's,
liveness would be false And we're assuming
And x is also, not live everyplace else,
initially. Okay And so, there's a program
point in there, also Where the liveness of
x is false. Okay, So now, let's propagate
the information. Well, so here we have
read of x. And let me switch colors here.
So here we have a read of x. So in fact
the information's inconsistent here
because ri ght before this statement since
we have a read of x, x must be live. So in
fact, x is live at this point. Now notice
that this statement both reads and writes
x. Okay? But the rule that says x is live
before, when we do a read, takes priority
here Because, the read happens before the
write. So we'll read the old value of x,
before we write the new value of x, Okay.
So the old value of x does get used, and
that's why x is live immediately before
this statement. Okay, so then here's
another, read of x. Okay, so on the, so
the point immediately before this when I
left out one program point here, x is also
Y. Okay, And then following edges
backwards, well, that means x is gonna be
live on the back edge of the loop And it's
also gonna be live by going into the
initialization block. Alright? Now we come
back around here and we see that we're
done 'cause x is already known to be, live
within the loop body. And now, live, x is
also live here And then the question is,
you know, what about this point on, the
entrance, at the entrance to the control
flow graph? Well, there's a right of x And
with no read of x on the right-hand side.
So, in fact, x, is not live on entry to
this control flow graph. So in fact, x is
dead at this point. So whatever value x
has when we enter the control flow graph,
it will never be used in the future.
Alright, and so that is The correct
[inaudible] in this information for every
program point in this example. Now another
thing you can see from our little example
is that values change from false to true,
but not the other way around. So every
value starts at false, and it can change
at most once. To say that the value is
actually live, the property becomes true,
and then it won't ever change back to
false again. So, going back to orderings,
We only have two values in this analysis,
false and true And the ordering is that
false is less than true. Okay, And we
know, so everything starts at the lowest
possible element of the ordering and they
only move up, and so they can be promoted
to true, but no t vice versa And so since
each value can only change once,
termination is guaranteed. That eventually
we're guaranteed to have consistent
information throughout the control flow
graph, and the analysis will terminate. To
wrap up and summarize our discussion of
the global analysis of control flow
graphs, we've talked about two kinds of
analysis in the past several videos.
Constant propagation is what is called a
forwards analysis Because information is
pushed from the inputs to the outputs. So
if you think about a control flow graph.
What happens in control flow analysis is
that information flows in this direction.
It flows in the same direction as
computation. If I have a constant up here
x is assigned constant down here, and x is
used later on and that constant will flow
forward to the uses. Okay So information
flows in the same direction as
computation. Liveness on the other hand is
a backwards analysis. Information is
pushed from outputs back towards inputs.
So here in this example and let me change
colors. Here we see that x is live before
the statement. And that liveness gets
propagated in the other direction. It gets
propagated [inaudible] against the
control, against the flow, of execution,
backwards towards the beginning of the
program. So they're many other kinds of
global flow analysis in the literature.
The constant propagation analysis and the
liveness analysis are two of the most
important. There is a number of others
that are also very important and many,
many more that people have investigated.
Almost all these analyses can be
classified as either forward or backward.
There are some analyses and some important
ones that are neither forward nor
backward. That information is basically
pushed in both directions. And the other
thing is that the, almost all the analyses
in the literature that do global flow
analysis anyway also follow this
methodology of local Rules that relay
information between adjacent program
points. So it, it's the local rules part
that's important. So we break down the
complicate d problem of analyzing an
entire control flow graph into a
collection of rules that only do ver,
propagate information very, very locally.