1
00:00:03,050 --> 00:00:08,029
In this video, we're gonna continue our
discussion of analysis of controlled flow

2
00:00:08,029 --> 00:00:13,020
graphs by focusing on what is undoubtedly
the most interesting aspect of the whole

3
00:00:13,020 --> 00:00:19,044
problem, the analysis of loops. Here's an
example of control flow graph with a loop

4
00:00:19,044 --> 00:00:25,006
in it. And it turns out that the need for
the special element bottom in our analysis

5
00:00:25,212 --> 00:00:30,048
is intimately tied to the analysis of
loops. And so, let's just think about how

6
00:00:30,048 --> 00:00:35,070
we would do our constant propagation
example analysis with this particular

7
00:00:35,311 --> 00:00:41,006
control flow graph, all right. So, what do
we know about x? Okay. So, initially, we

8
00:00:41,006 --> 00:00:46,042
don't know anything so before we enter the
control flow graph, its value, its top

9
00:00:46,042 --> 00:00:52,032
and, and after the assignment of three,
we'll know that x has the value three. The

10
00:00:52,032 --> 00:00:58,009
conditional branch here, the predicate
won't affect the value of x. So, it'll be

11
00:00:58,009 --> 00:01:03,093
three on both branches. The assignment to
y won't affect it so it'll be three here

12
00:01:03,093 --> 00:01:09,056
as well. And now we come here okay, and
let's focus on this statement right here.

13
00:01:09,056 --> 00:01:18,006
So, the rule is that the analysis of x at
y equals zero. Okay, So with a value of x

14
00:01:18,006 --> 00:01:23,045
right here before, before the assignment
to y. Is a function of all the

15
00:01:23,045 --> 00:01:28,000
predecessors. So, we need to know what the
value of x is on both of the incoming

16
00:01:28,000 --> 00:01:32,032
edges. Okay. Well, we don't have a value
down here yet. So, the question is, you

17
00:01:32,032 --> 00:01:35,837
know, what is the value of x here on this
edge? And in order to figure that out,

18
00:01:35,837 --> 00:01:39,659
we'd have to look at its predecessors.
Okay, what are its predecessors? Well,

19
00:01:39,659 --> 00:01:43,662
there's this point here after the
predicate there's this point here between

20
00:01:43,662 --> 00:01:47,815
the two statements, and then there's this
point here after the execution of y. We're

21
00:01:47,815 --> 00:01:52,038
just following the edges backwards here.
Looking at, you know, where we need to

22
00:01:52,038 --> 00:01:56,062
know information for x. We need to know it
here, we need to know it here, and we know

23
00:01:56,062 --> 00:02:03,478
it here, alright? And then because of this
edge, that means we again need to know it

24
00:02:03,478 --> 00:02:08,029
at both of the predecessors of y = zero.
So, now we're in the loop and this isn't

25
00:02:08,029 --> 00:02:12,507
too surprising. I mean, if you have, if
information about x depends on t he

26
00:02:12,507 --> 00:02:17,466
predecessors of a statement and you do
follow that recursively then you're gonna

27
00:02:17,466 --> 00:02:22,845
wind up going around loops like this. And,
and there's no good way at least there's

28
00:02:22,845 --> 00:02:27,875
no, no particularly immediately obvious
way to solve this problem. So, how do we I

29
00:02:27,875 --> 00:02:33,653
get information about the predecessor the
predecessors of y = zero when they depend

30
00:02:33,653 --> 00:02:39,686
on themselves? So, to be more precise
looking at that particular statement again

31
00:02:39,686 --> 00:02:45,872
in order to compute whether x is constant
at the point right before the statement y

32
00:02:45,872 --> 00:02:51,303
= zero, we need to know whether x is
constant as the two predecessor and that

33
00:02:51,303 --> 00:02:56,701
information depends on his predecessors,
which include y = zero. Okay, so this is

34
00:02:56,701 --> 00:03:03,125
the conundrum. So, how are we to solve
this recursive problem. And there's a

35
00:03:03,125 --> 00:03:09,222
standard solution that, that is actually
used in many areas of Mathematics and not

36
00:03:09,222 --> 00:03:13,908
just in the analysis of, of loops. When
you have these kinds of recurrence

37
00:03:13,908 --> 00:03:19,672
relationships or recursive equations. And
the standard solution is to break the

38
00:03:19,672 --> 00:03:24,895
cycle by starting with some initial guess.
So, you have some initial approximation

39
00:03:24,895 --> 00:03:30,130
that is really not perhaps even expected
to be the final result but allows you to

40
00:03:30,130 --> 00:03:35,888
get going. So, and so, what we're going to
do is that because of the cycles, all of

41
00:03:35,888 --> 00:03:40,837
the points, all the program points have to
have values at all times. And so we're

42
00:03:40,837 --> 00:03:45,607
going to assign an initial value and that
is what bottom is for. And the initial

43
00:03:45,607 --> 00:03:49,602
value bottom means, so far as we know,
control never reaches this point. Remember

44
00:03:49,602 --> 00:03:54,703
this, we've said this quite a while ago on
several videos ago. And this will allow us

45
00:03:54,918 --> 00:04:01,408
to make progress. And to see that let's go
ahead and analyze this control flow graph

46
00:04:01,408 --> 00:04:07,538
now where we assume that all points, and
at all points, initially, x has the value

47
00:04:07,538 --> 00:04:13,043
bottom except at the entry point. So, the
entry point is special. Here, we assume

48
00:04:13,043 --> 00:04:17,940
that we don't know anything about x
because we know the control reaches the

49
00:04:17,940 --> 00:04:23,243
initial point. But, initially, we're going
to just say, well, x is bottom everywhere

50
00:04:23,243 --> 00:04:30,830
else. Okay, so, [inaudible] the bottom
there, [inaudible] bottom there, okay, I'm

51
00:04:30,830 --> 00:04:38,268
gonna just fill in all the values. And I'm
just writing it everywhere here. And

52
00:04:38,268 --> 00:04:43,050
there's really another one right here
after the merge of these two paths. So, I

53
00:04:43,050 --> 00:04:47,779
indicate that. All right, so there, now we
have our initial setup and now remember

54
00:04:47,779 --> 00:04:52,623
what the procedure is, we go and look
where the information is inconsistent and

55
00:04:52,623 --> 00:04:57,485
we update it. So where is the place where
the information is inconsistent? Well,

56
00:04:57,485 --> 00:05:02,480
clearly it's not correct here, all right,
because we know that after if, if control

57
00:05:02,480 --> 00:05:07,227
reaches the point before x = three, then
after the assignment, x will be equal to

58
00:05:07,227 --> 00:05:12,610
three. Again the predicate will not change
the value of x, so we have to update the

59
00:05:12,610 --> 00:05:17,536
results of the two branches after the
predicate, and after it's assignment, that

60
00:05:17,536 --> 00:05:22,449
doesn't affect x to make that information
consistent that we have that. Now, let's

61
00:05:22,449 --> 00:05:28,148
go back to our interesting case. Here we
know that x = three on this branch coming

62
00:05:28,148 --> 00:05:32,979
in to y = zero. And, so far as we know,
control never reaches the other

63
00:05:32,979 --> 00:05:37,030
predecessor. So, we're gonna start out by
assuming that, that, that part, that path

64
00:05:37,030 --> 00:05:41,286
is never taken. And if that path is never
taken, then it won't contribute anything.

65
00:05:41,286 --> 00:05:45,489
And s, at this point in the program, we
will know that x = three. So, assuming

66
00:05:45,489 --> 00:05:49,574
that all this information is correct we
will be able to conclude that x = three at

67
00:05:49,574 --> 00:05:54,448
this point. And notice how we've been able
to break the cycle here and get started.

68
00:05:54,448 --> 00:05:58,824
So, we just assume that the, you know,
this last edge in the cycle never executes

69
00:05:58,824 --> 00:06:03,105
and if that's not correct, we'll find out
later and this value down here will become

70
00:06:03,105 --> 00:06:07,293
something other than bottom and then we'll
update the assignment again. Alright, so

71
00:06:07,293 --> 00:06:12,933
let's continue on. So, we have x = three
before y is assigned zero. So the

72
00:06:12,933 --> 00:06:18,483
assignment of y will not affect the value
of x. So, make the information afterward

73
00:06:18,483 --> 00:06:23,313
consistent we'll have to make x=3 there.
Now, we have a merge of two paths. Okay.

74
00:06:23,313 --> 00:06:28,533
So, the, at this point here before the
execution of this assignment we will also

75
00:06:28,533 --> 00:06:33,271
know that x = three. The assignment a will
not affect x. We'll update that point

76
00:06:33,271 --> 00:06:37,627
there and the predicate will not affect
the value of x. So, we'll know that x =

77
00:06:37,627 --> 00:06:42,654
three on the back edge. And now this
information has changed. We now know the

78
00:06:42,654 --> 00:06:46,514
control can reach this edge cuz we
followed the control path all the way

79
00:06:46,514 --> 00:06:51,320
here. We have some new information about x
and so now we have to double check that

80
00:06:51,320 --> 00:06:55,975
everything is still okay. So, here we have
x = three on this edge, x = three on this

81
00:06:55,975 --> 00:07:01,141
edge and our previous conclusion that x =
three on the entry to the statement y =

82
00:07:01,141 --> 00:07:05,863
zero. Well, that is also consistent. There
are no places left in the control flow

83
00:07:05,863 --> 00:07:10,190
graph that are inconsistent. So, all the
information is consistent with all the

84
00:07:10,190 --> 00:07:14,036
rules And so we're done, and this is the
final analysis. We're able to conclude

85
00:07:14,190 --> 00:07:18,582
that all, at all of these points here,
like I say, every point except the entry

86
00:07:18,582 --> 00:00:00,000
point, that x is in fact, the constant
three.