1
00:00:02,048 --> 00:00:07,075
We are now ready to begin our next major
topic, Program Optimization. In this

2
00:00:07,075 --> 00:00:12,067
video, we're just going to give overview
discussing why we want to perform

3
00:00:12,067 --> 00:00:18,043
optimization and what the trade-offs are
for compilers and deciding what kind of

4
00:00:18,043 --> 00:00:24,296
optimizations to implement. Optimization
is the last compiler phase that we're

5
00:00:24,296 --> 00:00:30,446
going to discuss. Let's just very briefly
review the compiler phases. First there is

6
00:00:30,446 --> 00:00:35,480
lexical analysis and then that's followed
by parsing. Then we have semantic

7
00:00:35,480 --> 00:00:46,522
analysis. And after that we talked about
code generation. And now we're going to

8
00:00:46,522 --> 00:00:51,321
talk about optimization, okay? So
optimization actually comes before code

9
00:00:51,321 --> 00:00:56,295
generation because we want to improve the
program before we commit it to machine

10
00:00:56,295 --> 00:01:01,068
code but it is of course the last one that
we've discussed. But, just point out here,

11
00:01:01,068 --> 00:01:06,061
optimization fits in between generally
semantic analysis and code generation and

12
00:01:06,061 --> 00:01:11,332
in modern compilers this is where most of
the action is. It's usually has by far the

13
00:01:11,332 --> 00:01:16,440
most code, and it's also the most complex
part of the compiler. Now, a very basic

14
00:01:16,440 --> 00:01:21,037
question is, when we should perform
optimizations? And we actually have some

15
00:01:21,037 --> 00:01:26,002
choices. We could perform them on the
abstract syntax tree and, a big advantage

16
00:01:26,002 --> 00:01:30,090
of that is that it's machine independent
but for many optimizations we want to do,

17
00:01:31,007 --> 00:01:35,202
this, it turns out that the abstract
syntax tree will be too high level that we

18
00:01:35,202 --> 00:01:39,079
can't actually even express the
optimizations we want to perform because

19
00:01:39,079 --> 00:01:44,089
those optimizations depend on lower level
details of the machine or of the kind of

20
00:01:44,089 --> 00:01:49,060
machine that we're generating code for
that aren't present in the abstract syntax

21
00:01:49,060 --> 00:01:53,646
tree. Another possibility would be to
perform optimizations directly on assembly

22
00:01:53,646 --> 00:01:58,763
language and the advantage here that all
the details of the machine are exposed. We

23
00:01:58,763 --> 00:02:03,767
can see everything that the machine is
doing. We can talk about all the resources

24
00:02:03,767 --> 00:02:08,031
of the machine and so, in principle, any
optimization we want to perform can be

25
00:02:08,031 --> 00:02:13,046
expressed at the assembly language level.
Now a disadvantage of doing optimizations

26
00:02:13,046 --> 00:02:17,359
on assembly language is that they are
machine-dependent. And then we would have

27
00:02:17,359 --> 00:02:21,800
to potentially re-implement our
optimizations for each new kind of

28
00:02:21,800 --> 00:02:27,042
architecture. And so, as we mentioned in
the previous video, another option is to

29
00:02:27,042 --> 00:02:32,647
use an intermediate language And the
intermediate language has the advantage

30
00:02:32,647 --> 00:02:37,533
potentially, if it's designed well, of
still being machine independent. Meaning

31
00:02:37,533 --> 00:02:42,408
it can, it can be a little bit above the
level of the concrete details of very,

32
00:02:42,408 --> 00:02:47,700
very specific architectures. I mean, it
can still represent a large family of

33
00:02:47,700 --> 00:02:52,947
machines but while, at the same time,
exposing enough optimization opportunities

34
00:02:52,947 --> 00:02:58,605
that the compiler can do a good job of
improving the program's performance. So,

35
00:02:58,605 --> 00:03:06,329
we will be looking at optimizations that
work on intermediate language that has

36
00:03:06,329 --> 00:03:11,954
operations given by this grammar. So, in
this case, a program is a sequence of

37
00:03:11,954 --> 00:03:17,785
statements and a statement consists of
either, an assignment Which could be a

38
00:03:17,785 --> 00:03:22,832
simple copy, or a unary, or binary
operation. We can push and pop things from

39
00:03:22,832 --> 00:03:27,520
a stack and then we have a couple of
different kinds of jumps. We have a

40
00:03:27,520 --> 00:03:32,097
comparison in jump where we compare the
value of two registers and then

41
00:03:32,097 --> 00:03:38,045
conditionally jump to a label. We have
unconditional jumps and finally there are

42
00:03:38,045 --> 00:03:43,026
labels, the targets of jumps. And the
identifiers here are the register names,

43
00:03:43,026 --> 00:03:48,045
and we could also use immediate values on
the right hand side of operations instead

44
00:03:48,045 --> 00:03:53,033
of registers and the typical operators,
we're just going to assume some typical

45
00:03:53,033 --> 00:03:59,829
family of operators like +,,, -,,, <i>,
etcetera. Now, optimizations typically</i>

46
00:03:59,829 --> 00:04:05,597
work on groups of statements and one of
the most important and useful statement

47
00:04:05,597 --> 00:04:10,185
groupings is the basic block. So a basic
block is a sequence of instructions and

48
00:04:10,185 --> 00:04:15,008
typically we want it to be the longest
possible sequence of instructions. So we

49
00:04:15,008 --> 00:04:19,511
want it to be maximal and this sequence
has two properties. First of all there are

50
00:04:19,511 --> 00:04:24,484
no labels except possibly for the very
first instruction. And there are no jumps

51
00:04:24,484 --> 00:04:29,627
anywhere in this sequence of instructions
except, possibly for the last instruction.

52
00:04:29,627 --> 00:04:35,077
And a basic block the ide a behind a basic
block, and the reason we require these two

53
00:04:35,077 --> 00:04:39,731
properties is that it's guaranteed to
flow, the execution is guaranteed to

54
00:04:39,731 --> 00:04:44,546
proceed from the first statement in the
block to the last statement in the block.

55
00:04:44,546 --> 00:04:49,163
So the flow of control within a basic
block is completely predictable. Once we

56
00:04:49,163 --> 00:04:53,891
enter the block, once we begin at the
first statement of the block which might

57
00:04:53,891 --> 00:04:58,540
have a label, there will be a sequence of
statements. That must all execute before

58
00:04:58,540 --> 00:05:03,054
we reach the last statement which could
potentially be a jump to some other part

59
00:05:03,054 --> 00:05:07,519
of the code. But once we get here, once we
get to this very first statement, then

60
00:05:07,519 --> 00:05:12,521
we're guaranteed to execute the entire
block without jumping out And furthermore,

61
00:05:12,521 --> 00:05:17,105
there's no way to jump into the block. You
couldn't just come from some other random

62
00:05:17,105 --> 00:05:21,445
part of the program and begin execution,
say, at the second or third instruction.

63
00:05:21,445 --> 00:05:27,062
The only way into the block is through the
first statement, and the only way out is

64
00:05:27,062 --> 00:05:33,086
through the last statement. Say here's a
example basic block and just to show you

65
00:05:33,086 --> 00:05:39,470
why basic blocks are useful. Let's observ
that we can actually optimize this piece

66
00:05:39,470 --> 00:05:45,121
of code. Okay because three always
executes after two. This instruction here

67
00:05:45,121 --> 00:05:50,722
always execute after this instruction. We
could change that third instruction to be

68
00:05:50,722 --> 00:05:55,213
w = three  x. Okay because we can see
here that t is getting two x + x or two

69
00:05:55,671 --> 00:06:01,709
x and here we're adding in another x and
so w is actually always equal to three

70
00:06:01,709 --> 00:06:08,529
x. And a question then, so that, that is
certainly a correct optimization and, and

71
00:06:08,529 --> 00:06:14,430
it's correct exactly because statement two
is always guaranteed to execute before

72
00:06:14,430 --> 00:06:20,164
statement three. Another question we might
be is whether we can eliminate this

73
00:06:20,164 --> 00:06:25,641
statement so once we replace this by three
 x, you know maybe we don't need this

74
00:06:25,641 --> 00:06:30,966
assignment anymore if this was the only
place that t was used if t was a temporary

75
00:06:30,966 --> 00:06:36,038
value that was computed only to compute
the, the value w. And then we can delete

76
00:06:36,038 --> 00:06:40,837
this statement and this depends on the
rest of the program. We have to know

77
00:06:40,837 --> 00:06:46,163
whether t has any other uses someplace
else in the program w hich we can't see

78
00:06:46,163 --> 00:06:52,653
just by looking at the single basic block.
The next important grouping of statements

79
00:06:52,653 --> 00:06:57,289
is a control flow graph. And a control
flow graph is a, just a graph of basic

80
00:06:57,289 --> 00:07:02,500
blocks. And so there's an edge from block
a to block b. If execution could pass from

81
00:07:02,500 --> 00:07:06,896
the last instruction in a to the first
instruction of b. So essentially the

82
00:07:06,896 --> 00:07:11,677
control flow graph just shows how control
flow can pass between the blocks and there

83
00:07:11,677 --> 00:07:16,063
isn't of course no interesting control
flow within the block. We know that the

84
00:07:16,063 --> 00:07:20,685
basic block will just execute from the
first instruction to the last instruction.

85
00:07:20,685 --> 00:07:25,623
So, the control flow graph is a way of
summarizing the interesting decision

86
00:07:25,623 --> 00:07:30,428
points in a, in a procedure or a other
piece of code showing where some

87
00:07:30,428 --> 00:07:36,111
interesting control flow decision is
actually made. So here's a simple control

88
00:07:36,111 --> 00:07:42,497
flow graph consists of two basic blocks.
The first basic block is outside of the

89
00:07:42,497 --> 00:07:47,440
loop, and consists of some initialization
code. And then we have one basic block

90
00:07:47,440 --> 00:07:52,748
here in the loop. The basic block consists
of these three instructions. And at the

91
00:07:52,748 --> 00:07:58,263
bottom of the block is a branch, a testing
branch where either we, exit and go

92
00:07:58,263 --> 00:08:03,335
someplace else or we loop around and
execute the loop body again, okay? And the

93
00:08:03,335 --> 00:08:08,328
body of a method can always be represented
as a control flow graph. The convention

94
00:08:08,328 --> 00:08:13,166
that we'll use is always a distinguished
entry node so a distinguished start node

95
00:08:13,166 --> 00:08:17,179
of the control flow graph and typically
it'll just be obvious it'll be the one

96
00:08:17,179 --> 00:08:21,839
listed at the top. And then there will be
some return nodes or one or some nodes of

97
00:08:21,839 --> 00:08:26,489
which you can return from and you know you
have a return statements in the procedure.

98
00:08:26,489 --> 00:08:31,520
And return nodes or places where you exit
the procedure will always be terminal.

99
00:08:31,520 --> 00:08:37,023
Meaning there will be no edges out of
those blocks. Now, the purpose of

100
00:08:37,023 --> 00:08:42,531
optimization is to improve a program's
resource utilization. And for the purposes

101
00:08:42,531 --> 00:08:46,523
of this classroom, when we talk about
optimization in, in our examples and in

102
00:08:46,523 --> 00:08:51,617
the videos we're gonna be talking about
execution time. And we're gonna be talking

103
00:08:51,617 --> 00:08:55,446
about, we're g onna be talking about
making the program run faster. And this is

104
00:08:55,446 --> 00:08:59,650
mostly what people are interested in. So
most compilers do spent quite a bit of

105
00:08:59,650 --> 00:09:03,809
effort on making programs run faster but
it's important to realize that there are

106
00:09:03,809 --> 00:09:07,362
many other resources that we could
optimize for. And, actually for any

107
00:09:07,362 --> 00:09:11,909
resource that you can imagine there
probably is a compiler out there that

108
00:09:11,909 --> 00:09:17,752
spend some effort optimizing for an insert
domain domains of application. So for

109
00:09:17,752 --> 00:09:23,717
example there are compilers we might care
about code size. We might care about the

110
00:09:23,717 --> 00:09:28,911
number of network messages sent, other
things that are commonly optimized for our

111
00:09:28,911 --> 00:09:33,502
memory usage, disk accesses so, so
databases, for example. Try to minimize

112
00:09:33,502 --> 00:09:38,995
the number of times you access the disk
and, and power for battery powered

113
00:09:38,995 --> 00:09:44,863
devices. And the important thing about
optimization is that it should not alter

114
00:09:44,863 --> 00:09:49,923
what the program computes. The answer
still must be the same, okay? So we're

115
00:09:49,923 --> 00:09:57,131
allowed to improve, the program's resource
utilization, but we can't change what the

116
00:09:57,131 --> 00:10:03,179
program will produce. Now, for languages
like C and Cool, and all of the languages

117
00:10:03,179 --> 00:10:07,663
that you're probably familiar with, there
are three granularities of optimization

118
00:10:07,663 --> 00:10:12,311
that people typically talk about. One is
called local optimization, and those are

119
00:10:12,311 --> 00:10:17,347
optimizations that apply to a basic block
in isolation. So these are optimizations

120
00:10:17,347 --> 00:10:21,683
that occur within a single basic block.
Then there are what are called global

121
00:10:21,683 --> 00:10:26,784
optimizations and this is really misnamed
because it's not global across the entire

122
00:10:26,784 --> 00:10:31,616
program. What people mean by global
optimization is that implies to a control

123
00:10:31,616 --> 00:10:36,066
flow graph. It's global across an entire
function alright so, so global

124
00:10:36,066 --> 00:10:40,898
optimizations would apply to a single
function and optimizer across all the

125
00:10:40,898 --> 00:10:45,584
basic blocks of that function. And finally
there are inter-procedural optimizations

126
00:10:45,584 --> 00:10:50,055
these are optimizations that work across
method boundaries. They take multiple

127
00:10:50,055 --> 00:10:55,457
functions and move things around to try to
optimize the collection of functions as a

128
00:10:55,457 --> 00:11:01,525
whole. Many compilers do one, in fact
almost all compilers do one. Many, many

129
00:11:01,525 --> 00:11:07,357
compilers today do two, but not very many
actually do three, okay? So you see

130
00:11:07,357 --> 00:11:14,439
decreasing numbers of compilers doing,
these optimizations as you move up in the

131
00:11:14,439 --> 00:11:20,352
granularity, and partly that's because the
optimization's are more difficult to

132
00:11:20,352 --> 00:11:24,479
implement so it's just more work to
implement the inter-procedural

133
00:11:24,479 --> 00:11:29,699
optimization's but also because a lot of
the payoff is in the more local

134
00:11:29,699 --> 00:11:34,951
optimizations. So, expanding on that last
point a little bit more. It turns out

135
00:11:34,951 --> 00:11:39,027
that, in practice, while we know how to do
many, many optimizations. Often a

136
00:11:39,027 --> 00:11:43,610
conscious decision is made not to
implement the fanciest optimization that

137
00:11:43,610 --> 00:11:48,661
is known in the research literature. And
that's kind of an unfortunate thing from

138
00:11:48,661 --> 00:11:53,555
my point of view being somebody who's
really likes compilers and spent a lot of

139
00:11:53,555 --> 00:11:58,400
time thinking about optimization. And
maybe it's a little bit hard to accept for

140
00:11:58,400 --> 00:12:03,547
the professional compiler researchers
that, that people don't always want to

141
00:12:03,547 --> 00:12:08,673
implement the latest and greatest
optimization. But it's worth understanding

142
00:12:08,673 --> 00:12:12,903
why that might not be the case and it
boils down essentially to software

143
00:12:12,903 --> 00:12:17,007
engineering. Some of these optimizations
are really hard to implement, I mean

144
00:12:17,007 --> 00:12:21,675
they're just complicated to implement.
Some of the optimizations are costly in

145
00:12:21,675 --> 00:12:26,585
compilation time. So even though the
compiling happens offline, it is not part

146
00:12:26,585 --> 00:12:31,715
of the running of the program, you know
the programmer still has to wait while the

147
00:12:31,715 --> 00:12:37,121
optimizing compiler compiles, does its
compilation and if it takes hours or in

148
00:12:37,121 --> 00:12:42,430
some cases days, to optimize a program,
you know, that's not necessarily great.

149
00:12:42,430 --> 00:12:47,508
And, some of these optimizations have low
pay off. They might, always improve the

150
00:12:47,508 --> 00:12:52,655
program, but they might only do it by a
very small amount and unfortunately, many

151
00:12:52,655 --> 00:12:56,885
of the fanciest optimizations in the
literature have all three of these

152
00:12:56,885 --> 00:13:01,624
properties. They're complicated, they take
a long time to run, and they don't do very

153
00:13:01,624 --> 00:13:06,434
much. And so it's not so surprising That
and not all of these to get implemented in

154
00:13:06,434 --> 00:13:11,481
production compilers. And this actually,
you kn ow points out what the real goal is

155
00:13:11,481 --> 00:13:16,976
in optimization. What we really want is
maximum benefit for minimum cost. We're

156
00:13:16,976 --> 00:13:22,123
really talking about a cost benefit ratio.
So, like optimization costs a certain

157
00:13:22,123 --> 00:13:27,119
amount, in code complexity, complexity of
the compiler In programmer time I mean

158
00:13:27,119 --> 00:13:32,666
waiting for the compiler to run and, and
the benefit, the amount that it improves

159
00:13:32,666 --> 00:13:36,062
the program has to be sufficient to
justify those costs.