1
00:00:02,008 --> 00:00:06,019
In the last several videos, we've been
talking about doing a kind of abstract

2
00:00:06,019 --> 00:00:10,073
computation. Computing with elements like
Bottom the Constants and Top. And, in this

3
00:00:10,073 --> 00:00:14,085
video, we're going to start to generalize
those ideas a little bit. And the first

4
00:00:14,085 --> 00:00:18,084
thing we're going to talk about, the first
step towards that generalization, is to

5
00:00:18,084 --> 00:00:24,041
talk about orderings of those values.
First, I'd like to introduce a technical

6
00:00:24,041 --> 00:00:28,091
term. These values that we compute within
program analysis, things like Bottom, the

7
00:00:28,091 --> 00:00:34,144
Constants and Top, these are called
Abstract Values. And that's just to

8
00:00:34,144 --> 00:00:37,539
distinguish them from the Concrete Values,
so the Concrete Values are the actual

9
00:00:37,539 --> 00:00:42,967
run-time values that a program computes
with. Things like actual objects, and

10
00:00:42,967 --> 00:00:48,147
numbers and things like that. And the
Abstract Values here the program analysis

11
00:00:48,147 --> 00:00:54,030
uses are in general, more abstract. Some
particular Abstract Values can stand for a

12
00:00:54,030 --> 00:01:00,166
set of possible Concrete Values. And in a
particular set of Abstract Values we're

13
00:01:00,166 --> 00:01:04,575
using for concept propagation, there's
only one very Abstract Value and that's

14
00:01:04,575 --> 00:01:09,548
the Top and it stands for any possible run
time value. So it stands for the entire

15
00:01:09,548 --> 00:01:14,091
set of run time values. Anyway, it turns
out that there is a way to simplify the

16
00:01:14,091 --> 00:01:17,868
presentation of, of the analysis that we
have been discussing by ordering the

17
00:01:17,868 --> 00:01:22,486
Abstract Values. So we're going to say is
that Bottom is less than all the constants

18
00:01:22,486 --> 00:01:27,585
and that, and all the Constants are less
than Top. And so if we draw a picture with

19
00:01:27,585 --> 00:01:32,662
the lower values drawn towards at the
bottom picture and the higher values drawn

20
00:01:32,662 --> 00:01:38,640
at the top. And, and edges between values
where there's a relationship, we get this

21
00:01:38,819 --> 00:01:42,961
diagram here. So you have bottom down
here, underneath all the other values,

22
00:01:42,961 --> 00:01:47,164
Bottom is less than every Constant. Okay.
So notice that all the constants are here

23
00:01:47,164 --> 00:01:50,848
on the middle level, alright? And also
notice that the constants are not

24
00:01:50,848 --> 00:01:55,224
comparable to each other, alright? So this
ordering is different than the numeric

25
00:01:55,224 --> 00:01:59,461
ordering. So zero is not less than one for
example. Zero and one are inco mparable,

26
00:01:59,464 --> 00:02:03,564
as are every other pair of Constants. So
you have, you know, Bottom at the Bottom.

27
00:02:03,564 --> 00:02:07,645
You have all the Constants in the middle
and they're incomparable, And then, bigger

28
00:02:07,645 --> 00:02:15,181
than everything else is Top. Now with the
ordering defined, there's a useful

29
00:02:15,181 --> 00:02:20,859
operation we can define on collections of
elements and that is the Least Upper

30
00:02:20,859 --> 00:02:25,966
Bound, or LUB, alright? And, and this
means is taking the smallest element that

31
00:02:25,966 --> 00:02:31,288
is bigger than everything in the Least
Upper Bound. So, for example, if I have

32
00:02:31,288 --> 00:02:38,742
the Least Upper Bound of Bottom and one,
that is equal to one, okay? If I had the

33
00:02:38,742 --> 00:02:44,979
Least Upper Bound of Top and Bottom, that
is equal to Top. And perhaps more

34
00:02:44,979 --> 00:02:50,648
interesting one, the Least Upper Bound of
one and two, so two incomparable Constants

35
00:02:50,648 --> 00:02:55,354
here. And remember, the meaning of the
Least Upper Bound, it's the smallest

36
00:02:55,354 --> 00:02:59,568
element in the ordering that's bigger than
everything over which we're taking the

37
00:02:59,568 --> 00:03:03,599
Least Upper Bound. So we just have two
things here in our Least Upper Bound. But

38
00:03:03,599 --> 00:03:07,124
the Least Upper Bound of one and two, the
smallest thing that's bigger than both of

39
00:03:07,124 --> 00:03:12,264
them, or greater than or equal I should
say, both of them is Top, okay? And so,

40
00:03:12,264 --> 00:03:18,155
the Least Upper Bound then, if you think
about it, if you draw, draw our picture

41
00:03:18,155 --> 00:03:22,597
again. So we had Bottom and we had Top,
and if you pick out some points here,

42
00:03:22,597 --> 00:03:26,404
let's say we want to take the Least Upper
Bound of Bottom and two, you're just

43
00:03:26,404 --> 00:03:30,273
picking the smallest thing that's bigger
than both. Well, that's going to be two

44
00:03:30,273 --> 00:03:34,217
itself, similarly two on Top, you will get
Top. And then if have anything that's

45
00:03:34,217 --> 00:03:37,470
incomparable, then you have to pick
something that's bigger than both of them

46
00:03:37,470 --> 00:03:41,451
and in this case that will always end up
being Top for this very simple ordering,

47
00:03:41,451 --> 00:03:46,682
alright? Then given this idea of the Least
Upper Bound, it turns out that rules one

48
00:03:46,682 --> 00:03:51,357
through four, all they're doing is
computing the Least Upper Bound. So the in

49
00:03:51,357 --> 00:03:57,198
of a statement is just equal to the Least
Upper Bound of the out of all the

50
00:03:57,198 --> 00:04:01,852
predecessors. Alright, and that's all that
rules one through four we're saying. And

51
00:04:01,852 --> 00:04:05,712
if you remember what we had there, we had,
you know, we had a bunch of predecessors

52
00:04:05,712 --> 00:04:10,031
and then there's some kind of statement s,
and all we're doing is whatever the

53
00:04:10,031 --> 00:04:16,393
information is on these predecessors,
we're just taking the Least Upper Bound

54
00:04:16,393 --> 00:04:24,068
over it, all right? And that is the
information on entry to, to s. The

55
00:04:24,068 --> 00:04:29,024
ordering on the Abstract Values also helps
to clarify another important aspect of our

56
00:04:29,024 --> 00:04:33,842
analysis algorithm which is why it
terminates. So remember the algorithm's

57
00:04:34,038 --> 00:04:39,084
termination condition is to repeat to
repeatedly apply the rules until nothing

58
00:04:39,084 --> 00:04:43,084
changes, until there are no more
inconsistencies in the control flow graph

59
00:04:43,084 --> 00:04:47,091
and there's no information left to update.
Well, just because we say we're going to

60
00:04:47,091 --> 00:04:52,319
repeat until nothing changes, that doesn't
guarantee that eventually nothing changes.

61
00:04:52,319 --> 00:04:55,084
It could be that, that goes on forever,
that we always introduce new

62
00:04:55,084 --> 00:05:01,005
inconsistencies with every update and we
never actually get to the point where all

63
00:05:01,005 --> 00:05:06,031
the information is consistent. So, the
ordering actually shows why that can't

64
00:05:06,031 --> 00:05:09,656
happen and the algorithm is guaranteed to
terminate. So remember that in every

65
00:05:09,656 --> 00:05:13,874
program point except the entry point, the
values start as Bottom. So, they start at

66
00:05:13,874 --> 00:05:18,768
the lowest place in the ordering. And then
if you look carefully at the rules, it's

67
00:05:18,768 --> 00:05:24,038
easy to see that the rules can only make
the values increase at a program point. So

68
00:05:24,038 --> 00:05:30,027
Bottom can be promoted, can be changed at
a given program point up to some Constant

69
00:05:30,027 --> 00:05:36,088
and, and, and another update could raise
that Constant to Top but of course, once

70
00:05:36,088 --> 00:05:40,075
we get the Top, there's no greater
element. And if the rules can only make

71
00:05:40,075 --> 00:05:45,069
the elements increase, then eventually we
have to run out of elements that could be

72
00:05:45,069 --> 00:05:51,042
increased, okay? So what that says is that
each piece of information we're computing,

73
00:05:51,042 --> 00:05:57,015
for every statement, for every variable,
and for either in or out, it can change at

74
00:05:57,015 --> 00:06:00,264
most twice, okay? So it can go from a
Bottom to a Constant, and from Constant to

75
00:06:00,264 --> 00:06:06,084
a Top but after that, it will never be
updated again. And what this means is that

76
00:06:06,084 --> 00:06:11,030
the constant propagation algorithm that
we've described is actually linear in

77
00:06:11,030 --> 00:06:15,420
program size. So the number of steps is
gonna be bounded by the number of c values

78
00:06:15,420 --> 00:06:19,333
that we're trying to compute times two,
cuz each one of those could change two

79
00:06:19,333 --> 00:06:25,048
times. And since there's one value for the
entry and exit over the in and out of

80
00:06:25,048 --> 00:06:29,676
every statement, the total number of steps
that the algorithm can possibly take is

81
00:06:29,676 --> 00:06:33,004
the number of program statements times
four.