1
00:00:02,720 --> 00:00:03,555
In this video we are going to continue our
discussion on global data flow analysis by

2
00:00:03,555 --> 00:00:03,555
taking a look at how global constant
propagation works in detail. To begin,

3
00:00:03,555 --> 00:00:03,555
let's review what the conditions are to do
global constant propagation. So to replace

4
00:00:03,555 --> 00:00:03,555
a use of a variable x by a constant K, we
have to know the following property. That

5
00:00:03,555 --> 00:00:03,555
on, that on every path to the use of x,
the last assignment to the variable x is x

6
00:00:03,555 --> 00:00:03,555
equals the constant K. Okay, And this has
to be true again, on every path to the use

7
00:00:03,555 --> 00:00:03,555
of x. Now global constant propagation can
be performed at any point where this

8
00:00:03,555 --> 00:00:04,449
property holds. What we're going to look
at in this video is the case of computing

9
00:00:04,449 --> 00:00:04,449
the property for a single variable x, at
all program points. So we're going to take

10
00:00:04,449 --> 00:00:04,449
one, we're going to focus on one variable
x, and we're going to compute whether it's

11
00:00:04,449 --> 00:00:04,449
a constant at every program point. It's
easy to extend the algorithm to compute

12
00:00:04,449 --> 00:00:04,449
this property for all variables. One
simple but very efficient way to do that

13
00:00:04,449 --> 00:00:04,449
is just to repeat the computation once for
each variable in the, method body. The way

14
00:00:04,449 --> 00:00:04,449
we are going to compute the information
that we want is to associate one of the

15
00:00:04,449 --> 00:00:04,449
following values with the variable x with
every point in the program. And, let's

16
00:00:04,449 --> 00:00:04,449
start with the last one here, we will
assign x this special value here, which is

17
00:00:04,449 --> 00:00:04,449
pronounced top. If x is not a constant, So
if we can't figure out whether x is a

18
00:00:04,449 --> 00:00:04,449
constant at a particular point in the
program, then we'll just say x is top at

19
00:00:04,449 --> 00:00:04,449
that point. And this is going to be our
safe situation, it's always okay to say we

20
00:00:04,449 --> 00:00:04,449
don't know what the value of x is, and
when we say that x has a value top, and we

21
00:00:04,449 --> 00:00:04,449
say, we're essentially saying we don't
know whether x is a constant or not at

22
00:00:04,449 --> 00:00:04,449
this point in the program, x could have
any value. Alright? Now, another

23
00:00:04,449 --> 00:00:04,449
possibility is that we will say that x is
some constant c, okay? So this is a

24
00:00:04,449 --> 00:00:04,449
particular constant And if we say that x
is a constant c at a program point, that

25
00:00:04,449 --> 00:00:04,449
means, in fact, at that program point, we
believe or we have proven that x is

26
00:00:04,449 --> 00:00:04,449
always, that con stant. Now, there is a
third possibility, Which is not

27
00:00:04,449 --> 00:00:04,449
immediately intuitive, perhaps. But, as we
will see, plays a very important role in

28
00:00:04,449 --> 00:00:04,449
algorithms for, for global constant
propagation And, in fact, in all global

29
00:00:04,449 --> 00:00:04,449
data flow analyses. And that is bottom.
Okay, this value is pronounced bottom and

30
00:00:04,449 --> 00:00:04,449
intuitively the idea anyway that is kind
of opposite of top. Alright, the

31
00:00:04,449 --> 00:00:04,449
interpretation of bottom is going to be
this statement never executes. Alright?

32
00:00:04,449 --> 00:00:04,449
So, when we don't know whether a statement
is even executed at all, we will say that

33
00:00:04,449 --> 00:00:04,449
x, at that point, has a value bottom,
Meaning that, as far as we know, that

34
00:00:04,449 --> 00:00:04,449
point in the program is never reached. It
doesn't matter what the value of x is at

35
00:00:04,449 --> 00:00:04,449
that point, because that statement never
executes. Alright? So we're going to

36
00:00:04,449 --> 00:00:04,449
assign x one of these three kinds of
values. Either bottom, some constant, or

37
00:00:04,449 --> 00:00:05,148
top. Let's begin by working through an
example by hand And our goal is going to

38
00:00:05,148 --> 00:00:05,616
be for every program point to decide
whether x could be a constant definitely

39
00:00:05,616 --> 00:00:06,102
not a constant, or whether we think that
statement might not ever execute. Okay, so

40
00:00:06,102 --> 00:00:06,570
executions will began at the top of this
control flip graph so this the enter

41
00:00:06,570 --> 00:00:07,032
point. And before executions begins we
don't anything about the value of x. So

42
00:00:07,032 --> 00:00:07,530
I'm not making any assumptions about what
code came before this basic block And so

43
00:00:07,530 --> 00:00:08,028
it would be safe to say x has some unknown
value. We don't know what the value of x

44
00:00:08,028 --> 00:00:08,526
is it could be anything. So x is equal to
top is the property that we want entry to

45
00:00:08,526 --> 00:00:08,946
the first basic block Now after the
assignment x=3. [inaudible] Indicate

46
00:00:08,946 --> 00:00:10,387
there, where, what point we're talking
about. So, after the assignment x=3, we'll

47
00:00:10,387 --> 00:00:10,467
definitely know that x is the constant
three. Alright, now there's something here

48
00:00:10,467 --> 00:00:10,548
that's worth pointing out Which is that
our program points, the points that we're

49
00:00:10,548 --> 00:00:10,619
attaching, this knowledge to, or these,
these facts to Are in between the

50
00:00:10,619 --> 00:00:10,694
statements. So, when I say x=3 at this
program point, what I mean is that after,

51
00:00:10,694 --> 00:00:10,765
after this assignment has executed. X=3,
but before this predicate of th e

52
00:00:10,765 --> 00:00:10,845
conditional has executed, I know that x is
equal to three, okay. So, program points

53
00:00:10,845 --> 00:00:10,922
are in between statements, and there's a
program point before and after every

54
00:00:10,922 --> 00:00:11,005
statement. Alright so the next thing that
happens is this conditional branch. Notice

55
00:00:11,005 --> 00:00:11,082
that the branch doesn't update x doesn't
even refer to x. So after the branch

56
00:00:11,082 --> 00:00:11,166
executes we'll definitely knows that x is
still equal to three on both branches. Now

57
00:00:11,166 --> 00:00:11,248
let's do the right hand branch. The next
thing that happens is the assignment to Y

58
00:00:11,248 --> 00:00:11,331
that would not affect the value of x. So
after the assignment to Y we'll still know

59
00:00:11,331 --> 00:00:11,411
that x=3 alright. Now let's take a look at
the left hand branch. So the first thing

60
00:00:11,411 --> 00:00:11,484
that happens over here is another
assignment to Y. Well that won't affect

61
00:00:11,484 --> 00:00:11,567
the value of x. After the assignment of Y
we'll know that x is still equal to three.

62
00:00:11,567 --> 00:00:11,645
And now comes to the assignment of x.
Alright. So after this assignment happens

63
00:00:11,645 --> 00:00:11,726
at this program point we're going to know
that the value of x is different. We're

64
00:00:11,726 --> 00:00:11,805
going to know that x=4. Alright so now
after this statement we know x is equal to

65
00:00:11,805 --> 00:00:11,888
four and after this statement over here we
know x=3 alright. Now what do we know then

66
00:00:11,888 --> 00:00:11,965
about what happens before, This statement,
okay? The a=2<i>x. And I just want to point</i>

67
00:00:11,965 --> 00:00:12,047
out here. I said that there's a program
point before and after every statement And

68
00:00:12,047 --> 00:00:12,124
so this program point, here, which is
before this assignment to a is different

69
00:00:12,124 --> 00:00:12,197
from the program points that are after x=4
and y=0. So intuitively, after x=4, we

70
00:00:12,197 --> 00:00:12,276
know that we're still on this path over
here on the left And so we know that X=4

71
00:00:12,276 --> 00:00:12,350
and over here after Y=0, we still know
that we're on this path is X=3. But. When

72
00:00:12,350 --> 00:00:12,428
we reach the point before A=2 times x, we
no longer know which path we're coming

73
00:00:12,428 --> 00:00:12,506
from. This is the point of the merge of
these two paths that both lead to this

74
00:00:12,506 --> 00:00:12,587
statement. And what can we say about the
value of x here? Well. There's no constant

75
00:00:12,587 --> 00:00:12,666
that we can assign to x. Because on one
path, x is three And on the other path, x

76
00:00:12,666 --> 00:00:00,000
is four. And so what we have to say here
is that before this assignment execut es,

77
00:00:00,000 --> 00:00:00,000
a=x, sorry, X is equal to top. We don't
know what the value of x is Another way of

78
00:00:00,000 --> 00:00:00,000
saying it is we know, we, we don't know
that x is a constant. So after the

79
00:00:00,000 --> 00:00:00,000
assignment executes, it doesn't affect the
value of x, we will also have that x is

80
00:00:00,000 --> 00:00:00,000
equal to tau Now notice that once we have
the global constant information, once we

81
00:00:00,000 --> 00:00:00,000
know for every program point, what the
state of x is, it's going to be very easy

82
00:00:00,000 --> 00:00:00,000
to perform the optimization. We simply
look at the information associated with

83
00:00:00,000 --> 00:00:00,000
the statement, and that will tell us
whether x is a constant when that

84
00:00:00,000 --> 00:00:00,000
statement executes, or not And if x is a
constant at that point, then we can

85
00:00:00,000 --> 00:00:00,000
replace that use of x by the constant And
crucial question of course is how do we

86
00:00:00,000 --> 00:00:00,000
compute these properties. So, we did this
example by hand that how, in a systematic

87
00:00:00,000 --> 00:00:00,000
fashion, an arbitrary control flow graph
do we actually compute these properties

88
00:00:00,000 --> 00:00:00,000
for x for every program point. Now we're
ready to talk about data-flow analysis

89
00:00:00,000 --> 00:00:00,000
algorithms and there's one basic principle
that you see in all of these algorithms

90
00:00:00,000 --> 00:00:00,000
that's worth mentioning right away. And
that's that the analysis of a complicated

91
00:00:00,000 --> 00:00:00,000
program can be expressed as a combination
of very simple rules that relate the

92
00:00:00,000 --> 00:00:00,000
change in information between adjacent
statements. So we're just going to focus

93
00:00:00,000 --> 00:00:00,000
on local rules. And the way we're going to
build our global data flow analysis is

94
00:00:00,000 --> 00:00:00,000
actually by a combination of rules that
look only at a single statement and its

95
00:00:00,000 --> 00:00:00,000
neighbors. The idea behind the rules is
going to be the push or transfer

96
00:00:00,000 --> 00:00:00,000
information from one statement to the next
And so for each statement S, we're going

97
00:00:00,000 --> 00:00:00,000
to compute information about the value of
x immediately before and after S. Remember

98
00:00:00,000 --> 00:00:00,000
that's where, those are the program points
that we want to attach information to. So

99
00:00:00,000 --> 00:00:00,000
in particular we're going to have a
function C. It stands for constant

100
00:00:00,000 --> 00:00:00,000
information And C will take three
arguments, takes the name of the variable,

101
00:00:00,000 --> 00:00:00,000
x. It takes the statement that we're
talking about The particular statement in

102
00:00:00,000 --> 00:00:00,000
the program that we're looking at And then
e ither in Or out and this is what

103
00:00:00,000 --> 00:00:00,000
distinguishes the value of x before S
executes versus the value of x after S

104
00:00:00,000 --> 00:00:00,000
executes. We're going to be defining a set
of transfer functions that push

105
00:00:00,000 --> 00:00:00,000
information, or transfer information from
one statement to another And in the rules

106
00:00:00,000 --> 00:00:00,000
for constant propagation we need to talk
about a statement and its predecessors. So

107
00:00:00,000 --> 00:00:00,000
we're going to say that every statement s
has some set of immediate predecessors p1

108
00:00:00,000 --> 00:00:00,000
through pn. Alright? [inaudible] either of
these statements that lead in one step to

109
00:00:00,000 --> 00:00:00,000
the statement s. Let's do our first rule.
So we have a statement S and it has some

110
00:00:00,000 --> 00:00:00,000
set of predecessor statements, P1, P2, P3,
P4 And the situation that we're interested

111
00:00:00,000 --> 00:00:00,000
in here is, let's assume that x is top. At
the program point after one of these

112
00:00:00,000 --> 00:00:00,000
predecessors. So, after some predecessor,
it doesn't matter which one, if it happens

113
00:00:00,000 --> 00:00:00,000
that x is top at the program point after
that predecessor, well, then x has to be

114
00:00:00,000 --> 00:00:00,000
top before the execution of s. Okay? So
that's what this rule says, it says if the

115
00:00:00,000 --> 00:00:00,000
out of any predecessor, for x is top, then
the in of s for x is also top. Alright,

116
00:00:00,000 --> 00:00:00,000
and this makes sense. It says that if we
don't know whether x is a constant on some

117
00:00:00,000 --> 00:00:00,000
path that leads to s, well then, we don't
know that x is a constant at s. Because

118
00:00:00,000 --> 00:00:00,000
for all we know, execution came down that
particular, came from that particular

119
00:00:00,000 --> 00:00:00,000
predecessor. And so, we can't make any
prediction about whether s is, whether x

120
00:00:00,000 --> 00:00:00,000
is a constant before s executes. Now let's
look at another situation. Let's say that

121
00:00:00,000 --> 00:00:00,000
x is some constant C. After the execution
of some predecessor And that on a, after

122
00:00:00,000 --> 00:00:00,000
another predecessor a distinct predecessor
x is a different constant D. So D is not

123
00:00:00,000 --> 00:00:00,000
equal to C. Well then what do we know
about x at the program point before s

124
00:00:00,000 --> 00:00:00,000
executes? Well, we don't know anything. X,
has to be top, because we don't know which

125
00:00:00,000 --> 00:00:00,000
constant, s will be, since we don't know
which path will reach s at run time. And

126
00:00:00,000 --> 00:00:00,000
this is the situation that we saw in the
example we did by hand. Another

127
00:00:00,000 --> 00:00:00,000
possibility is that the predecessors all
agree o n what the, the value of x could

128
00:00:00,000 --> 00:00:00,000
be. So let's say that we have, you know,
predecessor here and that after it

129
00:00:00,000 --> 00:00:00,000
executes x is known to be the constant c
and x is known to be the constant c after

130
00:00:00,000 --> 00:00:00,000
this predecessor And x is known to be the
constant c after this predecessor. There's

131
00:00:00,000 --> 00:00:00,000
one other possibility. Let's say that
after this predecessor over here, all we

132
00:00:00,000 --> 00:00:00,000
know is that x is bottom. Okay, and so
what the rule says is that if you have

133
00:00:00,000 --> 00:00:00,000
this situation where either. X has the
property bottom after a predecessor. Or,

134
00:00:00,000 --> 00:00:00,000
all the predecessors agree on the
particular constant that x could be. Then

135
00:00:00,000 --> 00:00:00,000
before, at the program point before s
executes, we know that x, is going to

136
00:00:00,000 --> 00:00:00,000
guar-, is guaranteed to be the constant c.
And if you think about it for a second,

137
00:00:00,000 --> 00:00:00,000
it's easy to see why this is correct.
First of all, clearly, if we come along

138
00:00:00,000 --> 00:00:00,000
one of the paths, where x is known to be
the constant c, since they all agree And

139
00:00:00,000 --> 00:00:00,000
then when we get to s, x will definitely
have the value c. What about the bottom

140
00:00:00,000 --> 00:00:00,000
case? Well, remember what that means. That
means that this statement is never

141
00:00:00,000 --> 00:00:00,000
reached. So there's some predecessor P
here, which never executes. Which means if

142
00:00:00,000 --> 00:00:00,000
P never executes, then we could never
reach S along this path from P. So the

143
00:00:00,000 --> 00:00:00,000
only paths that will reach S are the ones
where x is known to be a constant. Alright

144
00:00:00,000 --> 00:00:00,000
so that's why it's okay in this situation
say that x if x if control if execution

145
00:00:00,000 --> 00:00:00,000
reaches S at all its guaranteed to reach
it in a state where x is the constant C.

146
00:00:00,000 --> 00:00:00,000
One last possibility is let's say x is
bottom for all the predecessors. Okay? And

147
00:00:00,000 --> 00:00:00,000
what does that mean? Well, that means that
every predecessor of S never executes, so

148
00:00:00,000 --> 00:00:00,000
they're all unreachable. And therefore, if
every predecessor of x never executes, S

149
00:00:00,000 --> 00:00:00,000
itself can never execute, and so we can
conclude that entry to S, x is bottom. The

150
00:00:00,000 --> 00:00:00,000
first four rules that we just looked at
relate the out of one statement to the in

151
00:00:00,000 --> 00:00:00,000
of the next. We also have to have rules
that relate the in of a statement to the

152
00:00:00,000 --> 00:00:00,000
out of the same statement. So we have to
push information from the input o f a

153
00:00:00,000 --> 00:00:00,000
statement to the output of the same
statement. So, once again, there are

154
00:00:00,000 --> 00:00:00,000
several cases. And let's take a look at an
easy one first. If x is bottom, on

155
00:00:00,000 --> 00:00:00,000
[inaudible], if the program point before
s. Well that says that [inaudible], that s

156
00:00:00,000 --> 00:00:00,000
is never reached, that x never executes.
And therefore, x will be bottom, after, s,

157
00:00:00,000 --> 00:00:00,000
after s as well. So if the program point
before s is never reached, the program

158
00:00:00,000 --> 00:00:00,000
point after s definitely can't be reached
either. Another possibility is that we're

159
00:00:00,000 --> 00:00:00,000
assigning x to constant C in this
statement. In that case the out of the

160
00:00:00,000 --> 00:00:00,000
statement is going to be equal to C.
Alright, so it doesn't matter what the

161
00:00:00,000 --> 00:00:00,000
state of x was before the statement, after
we execute the statement, x will, be the

162
00:00:00,000 --> 00:00:00,000
constant C And I should say there is a
conflict with the previous rule. Okay, it

163
00:00:00,000 --> 00:00:00,000
could be that x is bottom, before the
statement. So rule six, has lower priority

164
00:00:00,000 --> 00:00:00,000
than rule five, so we, so if we could say
that x is bottom after the statement, we

165
00:00:00,000 --> 00:00:00,000
would prefer you to say that. So rule five
would be applied first, and then if rule

166
00:00:00,000 --> 00:00:00,000
five does not apply. So if x is some other
constant D, or x is equal to top. Then we

167
00:00:00,000 --> 00:00:00,000
would apply this rule and we would
conclude that x is the constancy

168
00:00:00,000 --> 00:00:00,000
afterwards. So that makes sense. If x is d
or x is the, is top that means that

169
00:00:00,000 --> 00:00:00,000
control, as far as we know, can reach this
statement. And then what we're saying here

170
00:00:00,000 --> 00:00:00,000
is, well, after the execution of this
statement, if control can reach this

171
00:00:00,000 --> 00:00:00,000
statement after the execution of it, x is
guaranteed to be the constancy. Another

172
00:00:00,000 --> 00:00:00,000
possibility is that we have an assignment
to x but the right hand side is more

173
00:00:00,000 --> 00:00:00,000
complicated than a constant. So this case
is for everything other than the constant

174
00:00:00,000 --> 00:00:00,000
assignment. Okay, so this F here just
stands for some More complicated

175
00:00:00,000 --> 00:00:00,000
expression than just a simple constant,
and in this case we, we're just going to

176
00:00:00,000 --> 00:00:00,000
say we don't know what the value is, we're
not going to try, to guess what the result

177
00:00:00,000 --> 00:00:00,000
of that computation is, and we'll just
say, that x is equal to top. X, we don't

178
00:00:00,000 --> 00:00:00,000
know what the value of x is after the exec
ution of this statement And once again,

179
00:00:00,000 --> 00:00:00,000
rule five takes precedence, so if rule
five applies, then we would apply, then,

180
00:00:00,000 --> 00:00:00,000
then we would use that rule instead of
rule seven. But, if control can reach this

181
00:00:00,000 --> 00:00:00,000
statement, so up here x is equal to some
constant c, or x is equal to top. We'll

182
00:00:00,000 --> 00:00:00,000
apply rule seven and conclude that x is
top after the statement and finally Rule

183
00:00:00,000 --> 00:00:00,000
eight, another possibility is that we're
assigning to some variable other than x.

184
00:00:00,000 --> 00:00:00,000
And in that case, if x was equal to, some
value, k, before the statement then we

185
00:00:00,000 --> 00:00:00,000
just keep that value. Okay, so whatever x
was before the statement bottom, a

186
00:00:00,000 --> 00:00:00,000
constant, or top, if the assignment is to
some other variable other than x then x

187
00:00:00,000 --> 00:00:00,000
will have the same property, after the
statement executes. Now, we can put these

188
00:00:00,000 --> 00:00:00,000
rules together into an algorithm. For
every entry point, for every, entry

189
00:00:00,000 --> 00:00:00,000
statement to the program, we're going to
say on entry that we don't know anything

190
00:00:00,000 --> 00:00:00,000
about the value of x. So the program point
before that entry point we're gonna say

191
00:00:00,000 --> 00:00:00,000
that x has an unknown value, top. And then
everywhere else we're going to say that

192
00:00:00,000 --> 00:00:00,000
the value of x, is bottom. Okay. And this
is actually important. So we're going,

193
00:00:00,000 --> 00:00:00,000
what this intuitively is doing, is its
saying, well, so far as we know. Except

194
00:00:00,000 --> 00:00:00,000
for the entry point to the program, which
can definitely be executed. We don't know

195
00:00:00,000 --> 00:00:00,000
whether any of the other statements in the
control flow graph are actually ever

196
00:00:00,000 --> 00:00:00,000
executed And so we're going to assume
initially, that they're not. And we're

197
00:00:00,000 --> 00:00:00,000
just going to say that x has the value
bottom everywhere except at an entry point

198
00:00:00,000 --> 00:00:00,000
And now what we're going to do is a kind
of constraint satisfaction algorithm.

199
00:00:00,000 --> 00:00:00,000
We're going to pick some statement that
doesn't satisfy one of the rules, one

200
00:00:00,000 --> 00:00:00,000
through eight. And then we're going to
update it using the appropriate rules. So

201
00:00:00,000 --> 00:00:00,000
we'll look for places in the control flow
graph where the information is

202
00:00:00,000 --> 00:00:00,000
inconsistent according to the rules And
then we'll update, the information, to

203
00:00:00,000 --> 00:00:00,000
make it consistent with the rules. Let's
take a look at our example again. So,

204
00:00:00,000 --> 00:00:00,000
we're going to start out by saying x is
equal to top, at the entry point, and then

205
00:00:00,000 --> 00:00:00,000
we're going to have all of our other
program points And let me indicate them

206
00:00:00,000 --> 00:00:00,000
here. Okay, so these are all the other
program points that we have to be

207
00:00:00,000 --> 00:00:00,000
concerned with. And there again, there's a
program point before and after every

208
00:00:00,000 --> 00:00:00,000
statement. And we are going to say the x
is equal to bottom for all of these. So,

209
00:00:00,000 --> 00:00:00,000
again what this means is, that so far as
we know, control doesn't reach any of

210
00:00:00,000 --> 00:00:00,000
these points. We have not yet proven to
ourselves that any of these statements can

211
00:00:00,000 --> 00:00:00,000
execute And now we just look around in the
program and try to find places, where the

212
00:00:00,000 --> 00:00:00,000
information is inconsistent according to
the rules, and then we update the

213
00:00:00,000 --> 00:00:00,000
information. Let me switch colors here.
So, as, when we begin, the information is

214
00:00:00,000 --> 00:00:00,000
consistent everywhere except at this first
statement, because if x is top. Before,

215
00:00:00,000 --> 00:00:00,000
and we're assigning x to value three.
Well, then we should not have x is equal

216
00:00:00,000 --> 00:00:00,000
to bottom as the result. In fact this
should be x is equal to three. Should be

217
00:00:00,000 --> 00:00:00,000
the appropriate information here And once
we update that, then we see that this next

218
00:00:00,000 --> 00:00:00,000
statement is inconsistent, because now we
know this statement is reachable. We have

219
00:00:00,000 --> 00:00:00,000
a statement here and we're concluding that
the point after is not reachable which is

220
00:00:00,000 --> 00:00:00,000
not, Not correct according to the rules.
So that I believe that this is an

221
00:00:00,000 --> 00:00:00,000
application of rule eight. We have a
statement here that doesn't refer to x as

222
00:00:00,000 --> 00:00:00,000
and so whatever the value of x was before
the statement becomes the value of x after

223
00:00:00,000 --> 00:00:00,000
the statement. So that becomes x is equal
to three And then, now we can see that

224
00:00:00,000 --> 00:00:00,000
this information is inconsistent. The out
of the statement here, is not consistent

225
00:00:00,000 --> 00:00:00,000
with the in of the statement here. In this
case, you know, it's just one predecessor.

226
00:00:00,000 --> 00:00:00,000
And so, the, the value should be the same.
So x should be three. At this point, and

227
00:00:00,000 --> 00:00:00,000
similarly, x should be three at this
point. Here we have an assignment to a

228
00:00:00,000 --> 00:00:00,000
variable other than x. That should,
information should be the same before and

229
00:00:00,000 --> 00:00:00,000
after the statements. Same thing here, Now
we have an assignment x. The point before

230
00:00:00,000 --> 00:00:00,000
that assignment is reachable And so since
this is a constant assignment we should

231
00:00:00,000 --> 00:00:00,000
know that x is that constant after the
assignment. So here again we have an in

232
00:00:00,000 --> 00:00:00,000
and out issue, so the out of this
statement is not consistent with the in of

233
00:00:00,000 --> 00:00:00,000
this statement. So this is gonna have to
be updated. But now, what should this be?

234
00:00:00,000 --> 00:00:00,000
Well, we have two inconsistent
predecessors And so this has to be top And

235
00:00:00,000 --> 00:00:00,000
then finally, an assignment to x, sorry,
an assignment to a state, To a variable

236
00:00:00,000 --> 00:00:00,000
other than x. So the information should
just propagate across And that,

237
00:00:00,000 --> 00:00:00,000
[inaudible] is updated like this. So now x
is known to be top afterwards And now, if

238
00:00:00,000 --> 00:00:00,000
we look around at all. The program points,
we'd see that all the information is

239
00:00:00,000 --> 00:00:00,000
consistent. All the rules, if you, if you,
if you check whether the information

240
00:00:00,000 --> 00:00:00,000
before and after a statement or across a
statement. I'm sorry, or between

241
00:00:00,000 --> 00:00:00,000
predecessors and successors is correct,
it's correct everywhere according to the

242
00:00:00,000 --> 00:00:00,000
rules, and so we're done.