1
00:00:03,220 --> 00:00:09,350
Now we are ready to begin talking about
actual program optimizations and we begin
2
00:00:09,350 --> 00:00:15,277
with local optimizations. Local
optimization is the simplest form of
3
00:00:15,277 --> 00:00:20,562
program optimization because it focuses on
optimizing just a single basic block, so
4
00:00:20,562 --> 00:00:25,655
just one basic block and, in particular,
there is no need worry about complicated
5
00:00:25,655 --> 00:00:30,621
control flow, we are not going to be
looking at the entire method or procedure
6
00:00:30,621 --> 00:00:35,686
body. Let's dive right in and take a look
at a couple of simple local optimizations.
7
00:00:35,686 --> 00:00:40,311
If x is an integer valued variable And
from here on, we'll assume that x has
8
00:00:40,311 --> 00:00:45,300
type-ins. So let me just write that down.
We're going to assume that x has type-ins
9
00:00:45,300 --> 00:00:50,107
in all of our examples on this slide. Then
the statement x=x+0, well that doesn't
10
00:00:50,107 --> 00:00:54,793
change the value of x. Zero is the
additive identity for +. We're just going
11
00:00:54,793 --> 00:00:59,722
to assign x the value it currently has.
And so this statement is actually useless.
12
00:00:59,722 --> 00:01:04,222
It can just be deleted from the program.
Similarly, for x=x1. Multiplying by one
13
00:01:04,222 --> 00:01:08,823
will not change the value of X, and so
that statement can also be removed. And in
14
00:01:08,823 --> 00:01:13,309
this case these are great optimizations
because we actually save an entire
15
00:01:13,309 --> 00:01:19,136
instruction. Now, some statements can't be
deleted, but they can be simplified. A
16
00:01:19,136 --> 00:01:23,596
simple example of that is if we have
x=x0. So that can be replaced by the
17
00:01:23,596 --> 00:01:28,629
assignment, x=0, And again, we have, we
still have a statement here. We still have
18
00:01:28,629 --> 00:01:33,515
to execute a statement. But This statement
may execute more quickly because it
19
00:01:33,515 --> 00:01:38,499
doesn't involve actually running the, the,
the times operator. It doesn't involve
20
00:01:38,675 --> 00:01:43,658
referencing the value of X. Presumably X
is registered, that doesn't really cost
21
00:01:43,658 --> 00:01:48,407
anything. But you know, it's possible that
this instruction over here will execute
22
00:01:48,407 --> 00:01:53,097
faster than this instruction over here.
Now, on many machines that's not the case.
23
00:01:53,097 --> 00:01:57,963
In fact, this assignment of this, this
assignment on the right will take the same
24
00:01:57,963 --> 00:02:02,720
amount of time as the multiplication on
the left, but as we will see. Having a
25
00:02:02,720 --> 00:02:07,793
assignment of a constant to a variable
will actually enable other optimization,
26
00:02:07,793 --> 00:02:12,990
so this is still a very worthwhile
transformation to do. An example that's
27
00:02:12,990 --> 00:02:18,858
almost certainly an optimization is
replacing, the exponentiation operator,
28
00:02:19,087 --> 00:02:24,727
Raising a value to the power of two by an
explicit multiply. So here, we're
29
00:02:24,727 --> 00:02:29,849
computing y^2, And over here, we just
replace that by yy. Why is this a good
30
00:02:29,849 --> 00:02:34,915
idea? Well this explanation operator here
is almost certain not a built in machine
31
00:02:34,915 --> 00:02:40,041
instructions. Probably this is gonna wind
in our generated code being a call into to
32
00:02:40,041 --> 00:02:45,046
some built in math library. And there will
involve a functioning call overhead. And
33
00:02:45,046 --> 00:02:49,928
then there will be some kind of general
loop in there to do the right number of
34
00:02:49,928 --> 00:02:55,420
multiplies. Depending on what the exponent
is. So in the special case where we know
35
00:02:55,420 --> 00:03:00,697
that the exponent is two. It's much, much
more efficient. To just replace that, call
36
00:03:00,697 --> 00:03:06,104
to [inaudible] by an explicit multiply.
Another example of, substituting one kind
37
00:03:06,104 --> 00:03:10,598
of operation for another, In a in a
special situation, Is if we have, a
38
00:03:10,598 --> 00:03:15,875
multiplication by a power of two. We can
replace that by a left bit shift, So here,
39
00:03:15,875 --> 00:03:21,282
multiplying by eight. That's the same as
shifting the, binary representation of x
40
00:03:21,282 --> 00:03:27,532
over by three bits, And, I and, That will,
you know, in fact compute the same thing.
41
00:03:27,532 --> 00:03:32,361
And it doesn't even have to be a power of
two. If we had a [inaudible] location by
42
00:03:32,361 --> 00:03:36,973
some other number that is not a power of
two, that can be replaced by some
43
00:03:36,973 --> 00:03:41,461
combination of shifting and, and
subtractions. Okay? So we can replace the
44
00:03:41,461 --> 00:03:46,448
multiply by some combination of shifts
and, and arithmetic operations, Simpler
45
00:03:46,448 --> 00:03:51,038
arithmetic operations. Now these last two
here I should point out, you know, these
46
00:03:51,038 --> 00:03:55,921
are interesting transformations. On modern
machines generally this will not result in
47
00:03:55,921 --> 00:04:00,472
any kind of speed-up because on modern
machines the integer multiply operation is
48
00:04:00,472 --> 00:04:04,467
just as fast as any other single
instruction. Now, on historical machines
49
00:04:04,467 --> 00:04:08,293
these were actually significant
optimizations. So all of these,
50
00:04:08,531 --> 00:04:14,897
instructions together are examples of
algebraic simplifications. So, that just
51
00:04:14,897 --> 00:04:21,160
means exploiting properties of the
mathematical operators, to replace more
52
00:04:21,160 --> 00:04:28,213
complex, instruc tions or more complex
operations by simpler ones. One of the
53
00:04:28,213 --> 00:04:33,078
most important and useful local
optimizations is to compute the results of
54
00:04:33,078 --> 00:04:38,331
operations at compile time rather than at
run time if the arguments are known at
55
00:04:38,331 --> 00:04:43,780
compile time. So for example, let's say we
have a three-address instruction x=y op z.
56
00:04:43,780 --> 00:04:48,556
And it happens that y and z are both
constants. These are both immediate
57
00:04:48,556 --> 00:04:53,532
values. These are, you know, literals in
the instruction. Then we can actually
58
00:04:53,532 --> 00:04:58,972
compute the results of the right hand side
at compile time, and replace this by an
59
00:04:58,972 --> 00:05:04,147
assignment to a constant. So, for example,
if we have the instruction x=2+2, that can
60
00:05:04,147 --> 00:05:09,288
be replaced by the assignment x=4, And
another example which is a very common and
61
00:05:09,288 --> 00:05:14,178
important one, is if the predicate of a
conditional consists only of immediate
62
00:05:14,178 --> 00:05:19,310
values. Then we can pre-compute the result
of that conditional, And, and decide what
63
00:05:19,310 --> 00:05:23,838
the target of the conditional will be.
What the next instruction will be at
64
00:05:23,838 --> 00:05:28,426
compile time. So, in this case, we have a
predicate, which is going to be false,
65
00:05:28,426 --> 00:05:33,196
because two is not less than zero And so
we will not take the jump And so this
66
00:05:33,196 --> 00:05:38,409
instruction can just be deleted from the
program. If we had the, Otherwise if two
67
00:05:38,409 --> 00:05:44,880
is greater than zero, so if this is some
predicate to valuate true Then we would
68
00:05:44,880 --> 00:05:50,383
replace this conditional by the jump.
Okay, this would become an unconditional
69
00:05:50,383 --> 00:05:55,600
jump. Alright, And this class of
optimization's is called constant folding,
70
00:05:55,600 --> 00:06:02,118
And as I said this is one of the most
common and most important optimizations
71
00:06:02,118 --> 00:06:09,546
that compilers perform. Now, there is one
situation that you should be aware of and
72
00:06:09,546 --> 00:06:15,286
which can be very dangerous, and this
situation is actually very instructive as
73
00:06:15,286 --> 00:06:20,953
well. And so while it isn't that common,
I, I wanted to mention it, because it
74
00:06:20,953 --> 00:06:26,911
really illustrates some of the subtleties
of program optimization and programming
75
00:06:26,911 --> 00:06:32,941
language semantics. So what is this
dangerous situation? So let's consider the
76
00:06:32,941 --> 00:06:39,286
scenario where we have two machines. We
have a machine X And we have a machine.
77
00:06:39,286 --> 00:06:49,340
Why? Okay and now the compiler is being
run on machine X. And the compiler is
78
00:06:49,340 --> 00:06:55,814
producing code. Generated code this is the
generated code produced as the output of
79
00:06:55,814 --> 00:07:00,947
the compiler over here. That's gonna be
run on machine Y. So this is a cross
80
00:07:00,947 --> 00:07:07,005
compiler. Okay, So you are running the
compiler On one machine, but you're
81
00:07:07,005 --> 00:07:11,700
generating code for a different machine,
and why would you want to do that? Well.
82
00:07:11,700 --> 00:07:16,674
The, the common situation in which you
want to do this is that this machine Y
83
00:07:16,674 --> 00:07:22,360
over here is a very weak machine. So weak
in the sense that it's very slow and has
84
00:07:22,360 --> 00:07:28,045
very limited memory. Maybe very limited
power then it's beneficial to develop your
85
00:07:28,045 --> 00:07:33,755
program and even compile it on a much more
powerful machine. So many embedded Systems
86
00:07:33,755 --> 00:07:38,970
codes are developed in exactly this way.
Code is developed on some powerful
87
00:07:38,970 --> 00:07:44,520
workstations that are actually compiling
it for some small embedded device that
88
00:07:44,520 --> 00:07:49,817
well, executes the code. Now, the problem
comes If x and y are different. So
89
00:07:49,817 --> 00:07:54,532
consider the situation where x and y are
different machines, different
90
00:07:54,532 --> 00:07:59,516
architectures. Alright, And I've been
implying that they are, but they don't
91
00:07:59,516 --> 00:08:04,770
have to be. I mean, I mean, you could
compile on, one kind of architecture and
92
00:08:04,770 --> 00:08:09,013
run the same code on the same
architecture. But the interesting
93
00:08:09,013 --> 00:08:14,132
situation is when x and y are different
architectures. And so let's consider
94
00:08:14,132 --> 00:08:18,914
something like, you know, in, in, you
know, machine X, let's say we have the
95
00:08:18,914 --> 00:08:26,194
instruction, A=1.5+3.7. Mm-kay, And you
would like to constant fold that down to
96
00:08:26,523 --> 00:08:32,292
a=5.2 Alright? Now the problem is that if
you simply execute this as a floating
97
00:08:32,292 --> 00:08:38,186
point operation, on, architecture x, the
round off and you know the floating point
98
00:08:38,186 --> 00:08:43,463
semantics in architecture x maybe slightly
different, from these semantics on
99
00:08:43,463 --> 00:08:49,356
architecture y. It could be that if you do
that in architecture y, directly, that you
100
00:08:49,356 --> 00:08:54,428
might get something like a.5, you know,
a=5.19. There might be a small difference
101
00:08:54,428 --> 00:09:00,321
in the floating point result, depending on
whether you execute the instruction here
102
00:09:00,321 --> 00:09:04,720
or here. And this becomes significant in
the case of constant folding and, and
103
00:09:04,720 --> 00:09:08,906
cross compilation. Because some al
gorithms really depend on the floating
104
00:09:08,906 --> 00:09:13,315
point numbers being treated very, very
consistently. So if you're going to round
105
00:09:13,315 --> 00:09:17,780
off the operation one way, you need to do
it that way for every time you do that
106
00:09:17,780 --> 00:09:22,356
particular operation, And by shifting the
computation from comp, from run time when
107
00:09:22,356 --> 00:09:26,988
it would have executed an architecture y,
back into the compiler winds of executing
108
00:09:26,988 --> 00:09:31,596
architecture x. You can change the results
of the program. So how do cross compilers
109
00:09:31,596 --> 00:09:36,152
actually deal with this? So, so compilers
that want to be careful about this kind of
110
00:09:36,152 --> 00:09:40,378
thing, what they will do is, they will
represent the floating point numbers as
111
00:09:40,378 --> 00:09:45,098
strings inside the compiler and they will,
do the obvious, long form addition, and
112
00:09:45,098 --> 00:09:49,433
multiplication, division operations are
the floating operations directly on the
113
00:09:49,433 --> 00:09:53,912
strings. Keep the full precision Inside
the compiler And then, in the generated
114
00:09:53,912 --> 00:09:58,580
code, produced the literal, that is the
full precision flowing point number And
115
00:09:58,580 --> 00:10:02,858
then let the architecture, of the
architecture y decide how it wants to
116
00:10:02,858 --> 00:10:07,248
round that off, okay? So that's the really
careful way to do constant folding of
117
00:10:07,248 --> 00:10:12,356
floating point numbers if you're worried
about cross compilation. Continuing on
118
00:10:12,356 --> 00:10:16,624
with local optimizations, another
important one is to eliminate unreachable
119
00:10:16,624 --> 00:10:21,062
basic blocks. So what's an unreachable
basic block? That is one that is not the
120
00:10:21,062 --> 00:10:25,557
target of any jump or fall through. So if
I have a piece of code, that can never
121
00:10:25,557 --> 00:10:29,938
execute, and it might never execute
because there's no jump that jumps to the
122
00:10:29,938 --> 00:10:34,320
beginning of that piece of code and it's
not, it doesn't follow after another
123
00:10:34,320 --> 00:10:38,872
instruction that can fall through to it.
Well than that piece of code, that basic
124
00:10:38,872 --> 00:10:43,594
block is just not gonna be used, it's
unreachable and it can be deleted from the
125
00:10:43,594 --> 00:10:48,497
program. This has the advantage of making
the code smaller. So obviously, since the
126
00:10:48,497 --> 00:10:53,120
basic block is unreachable, it's not
contributing to the execution costs of the
127
00:10:53,120 --> 00:10:58,036
program in terms of the instruction count.
So the code is never executed. So it's not
128
00:10:58,036 --> 00:11:02,425
really slowing down the code because, you
know, extra instructions are being
129
00:11:02,425 --> 00:11:07,458
executed, But making the program smaller
can actually make it run faster because of
130
00:11:07,458 --> 00:11:12,257
cache effects. So the instructions have to
fit into memory just like, just like the
131
00:11:12,257 --> 00:11:16,524
data. And if you make the program smaller,
it makes it easier to fit the program in
132
00:11:16,524 --> 00:11:20,912
memory, and you may increase the spacial
locality of the program. Instructions that
133
00:11:20,912 --> 00:11:25,042
are used together may now be closer to
each other. And that can make the program
134
00:11:25,042 --> 00:11:31,289
run more quickly. Before continuing on I
want to say a word or two about why
135
00:11:31,289 --> 00:11:35,453
unreachable basic blocks occur. So why
would a programmer, in their right mind,
136
00:11:35,453 --> 00:11:39,670
ever write a program that had code in it
that wasn't going to be executed? And
137
00:11:39,670 --> 00:11:43,725
there's several actually ways in which
unreachable code can arise, and it's
138
00:11:43,725 --> 00:11:47,942
actually quite common. So this is an
important optimization, getting rid of the
139
00:11:47,942 --> 00:11:51,889
unreachable code is actually fairly
important. Perhaps the most common
140
00:11:51,889 --> 00:11:57,625
situation Is that the code is actually
parameterized with, code that is only
141
00:11:57,625 --> 00:12:03,543
compiled and used in certain situations.
So, for example, in C, It would be sorta
142
00:12:03,543 --> 00:12:09,765
typical to see some code that looks like
this. If debug, then, you know, executes
143
00:12:09,765 --> 00:12:15,617
something, where debug is a pound defying
constant. So in C, you can define names
144
00:12:15,617 --> 00:12:21,485
for literals. So you say something like
this. You might define debug. To be zero,
145
00:12:21,485 --> 00:12:26,596
and so you might see a program that had
this piece of code in it, and what this
146
00:12:26,596 --> 00:12:31,966
literally means is that this piece of code
is equivalent to if zero, then blah, blah,
147
00:12:31,966 --> 00:12:36,560
blah. Alright, so, so when you're
compiling without debugging, you have
148
00:12:36,560 --> 00:12:41,541
debug to find the zero, when you're
compiling with debugging, you would change
149
00:12:41,541 --> 00:12:46,320
this line to define debug to be some non
zero constant. So in this case we are
150
00:12:46,320 --> 00:12:50,724
compiling without debugging. What will
happen? Well we'll see that this predicate
151
00:12:50,724 --> 00:12:54,863
is guaranteed to be zero the constant
folding will take care of that. And that
152
00:12:54,863 --> 00:12:59,214
will result in an unreachable basic block
on the [inaudible] branch and then that
153
00:12:59,214 --> 00:13:03,671
code can be deleted And so essentially the
compiler is able to go through using the
154
00:13:03,671 --> 00:13:07,703
optimizer and strip out all o f the
debugging code. That isn't going to be
155
00:13:07,703 --> 00:13:11,895
used since your compiler [inaudible].
Another case where unreachable code comes
156
00:13:11,895 --> 00:13:16,535
up is with libraries. So, very frequently,
programs are written, to use generic
157
00:13:16,535 --> 00:13:21,100
libraries. But the program might only use
a very small part of the interface. So,
158
00:13:21,100 --> 00:13:25,781
the library might supply 100 methods, to
cover all the situations that various
159
00:13:25,781 --> 00:13:30,115
programmers are interested in. But for
your program, you might only be using
160
00:13:30,115 --> 00:13:34,391
three of those methods. And the rest of
those methods could potentially be
161
00:13:34,391 --> 00:13:39,130
removed, from the final binary, to make
the code smaller. And, finally another way
162
00:13:39,130 --> 00:13:44,063
that unreachable basic blocks occur, is as
the results of other optimizations. So as
163
00:13:44,063 --> 00:13:50,443
we will see optimizations frequently lead
to other to more optimizations. And it
164
00:13:50,443 --> 00:13:55,403
could be that just through other
rearrangements of the code that the
165
00:13:55,403 --> 00:14:04,065
compiler makes some basic block redundant
and, and able to be deleted. Now some
166
00:14:04,065 --> 00:14:08,878
optimizations are simpler to express if
each register occurs only once on the
167
00:14:08,878 --> 00:14:13,691
left-hand side of an assignment. So that
means if each register is assigned, at
168
00:14:13,691 --> 00:14:18,072
most, once then some of these
optimizations are easier to talk about. So
169
00:14:18,072 --> 00:14:22,886
we're gonna rewrite our intermediate code,
always to so that it's in single
170
00:14:22,886 --> 00:14:27,760
assignment form. So this is called single
assignment form. And all that means is
171
00:14:27,760 --> 00:14:32,944
that if we see a register being reused,
like over here, we have two assignments to
172
00:14:32,944 --> 00:14:38,684
the register X. Okay. We're just going to
introduce another register name, for one
173
00:14:38,684 --> 00:14:44,420
of those assignments. So in this case I'm
just gonna rename the first, use of X
174
00:14:44,420 --> 00:14:50,226
here, definition of X here to be some new
register B. I'll replace the uses of that
175
00:14:50,226 --> 00:14:55,679
X, by the name B, and now I have an
equivalent piece of code that satisfies
176
00:14:55,679 --> 00:15:02,836
single assignment form. Every register is
assigned at most, once. Let's take a look
177
00:15:02,836 --> 00:15:07,153
at an optimization that depends on single
assignment form. So we're going to assume
178
00:15:07,153 --> 00:15:11,469
the basic blocks are in single assignment
form, and if they are, then we're going to
179
00:15:11,469 --> 00:15:16,065
know That a definition of a register is
the first use of that register in th e
180
00:15:16,065 --> 00:15:20,520
block, And so, in particular, we're also
ruling out things like this. So there
181
00:15:20,520 --> 00:15:25,153
could be something like this, where X is
read. And then later on, X is used. Okay.
182
00:15:25,153 --> 00:15:29,905
Sorry, X is read and then later on, X is
defined. So we're not going to allow this.
183
00:15:30,083 --> 00:15:34,657
This register here would have to be
renamed to something else, say Y, And then
184
00:15:34,657 --> 00:15:39,468
uses of X later on here, are renamed to Y.
Alright, so we're going to insist that
185
00:15:39,468 --> 00:15:44,151
whenever we have a definition Of a
register in a basic block. That is the
186
00:15:44,151 --> 00:15:48,591
first use of that register in the block.
Alright, and if, if that's true, if we
187
00:15:48,591 --> 00:15:52,365
main, if we put things in that form, and
that's, that's easy to do as we've seen.
188
00:15:52,365 --> 00:15:56,139
Then when two assignments have the same
right hand side, they're guaranteed to
189
00:15:56,139 --> 00:16:00,714
compute the same value. So, take a look
here, This example. So let's say we have
190
00:16:00,714 --> 00:16:05,435
an assignment, x=y+z. And then later on we
have another assignment, w=y+z. And we
191
00:16:05,435 --> 00:16:10,560
said that there could only be one
assignment to x in any basic blocks. So,
192
00:16:10,560 --> 00:16:15,684
all of these instructions that are
[inaudible] here, they can't be assigning
193
00:16:15,684 --> 00:16:20,809
to X. And they also can't be assigning to
y and z. Y and z already have their
194
00:16:20,809 --> 00:16:26,339
definitions. So, y and z can't be changed.
And that means that x and w here actually
195
00:16:26,339 --> 00:16:32,190
compute the same value. And so we can
replace the second computation Y plus C by
196
00:16:32,190 --> 00:16:37,916
just the name that we already have for it
X. Okay, and this saves us having to
197
00:16:37,916 --> 00:16:44,416
recompute values. Alright so this is
called common sub expression elimination.
198
00:16:44,416 --> 00:16:51,495
Common it's a rather long name. Sub
expression. The elimination. And this is
199
00:16:51,495 --> 00:16:57,967
another one of the, more important
compiler optimizations. This is actually
200
00:16:57,967 --> 00:17:04,354
something that comes up surprisingly
often. And saves quite a bit of work if,
201
00:17:04,606 --> 00:17:11,655
if you perform this optimization. So,
another use of single assignment form is
202
00:17:11,655 --> 00:17:18,347
that if we see the assignment w equals x
in a block. So here, the register w is
203
00:17:18,347 --> 00:17:24,543
being just copied from the register x.
Then all subsequent uses of w can be
204
00:17:24,543 --> 00:17:30,979
replaced by uses of x. So, for example,
Here we have an assignment to b And then
205
00:17:30,979 --> 00:17:37,162
we have a copy, a, is=to b. And then, down
here, w e have a use of a in the last
206
00:17:37,162 --> 00:17:43,757
instruction. Well, that use of a in the
last instruction can be replaced by a use
207
00:17:43,757 --> 00:17:49,883
of B. And this is called copy propagation,
okay? Propagating copies through the code
208
00:17:49,883 --> 00:17:55,133
And by itself, notice, that this makes
absolute no improvement in the code it's
209
00:17:55,133 --> 00:18:00,254
only useful in conjunction with some of
the other optimizations. So, for example,
210
00:18:00,254 --> 00:18:05,115
in this case after we do the copy
propagation, it might be the case that
211
00:18:05,115 --> 00:18:10,365
this instruction can be deleted. If A is
not used any place else in the code, then
212
00:18:10,365 --> 00:18:14,964
this instruction can be removed. Now let's
do a little more complex example and use
213
00:18:14,964 --> 00:18:18,676
some of the optimizations that we've
discussed so far On a slightly bigger
214
00:18:18,676 --> 00:18:22,833
piece of code. So we are starting with
this piece of code here on the left and we
215
00:18:22,833 --> 00:18:26,842
are going to wind up with this piece of
code here on the right. And how does that
216
00:18:26,842 --> 00:18:31,015
work? Well, first we have a copy
propagation, so we have A is assigned the
217
00:18:31,015 --> 00:18:36,256
value five. And, so we can propagate that
value forward. And replace the use of a
218
00:18:36,256 --> 00:18:41,835
later on by five, and I should say. That
when the value is propagated is a constant
219
00:18:41,835 --> 00:18:45,995
rather than a registered name is called
Constant propagation instead of Copy
220
00:18:45,995 --> 00:18:49,939
propagation, but it's exactly the same
thing. We, we, we have a single value
221
00:18:49,939 --> 00:18:54,154
assigned on the right hand side, either a
register name or constant and we are
222
00:18:54,154 --> 00:18:57,936
replacing uses of that in later
instructions by that register name or
223
00:18:57,936 --> 00:19:02,096
constant. Okay? So once we have replaced a
here by five now we can do constant
224
00:19:02,096 --> 00:19:06,364
folding, and now we have two constant
arguments for this instruction. So this
225
00:19:06,364 --> 00:19:10,809
two times five can be replaced by the
constant ten. Now notice we have another
226
00:19:10,809 --> 00:19:16,315
assignment of a constant to a register and
so we can propagate that constant forward.
227
00:19:16,315 --> 00:19:21,257
We can replace the subsequent uses of X by
the number ten. And now we have more
228
00:19:21,257 --> 00:19:26,075
opportunities for constant folding ten
plus six can be replaced by the value
229
00:19:26,075 --> 00:19:31,080
sixteen. Alright now we have another,
another value here which is a, a constant
230
00:19:31,080 --> 00:19:36,086
assignment so another instruction here
which is just an assignment of a constant
231
00:19:36,086 --> 00:19:41,317
to a register so we can p ropagate that
constant forward. Alright then we wind up
232
00:19:41,317 --> 00:19:47,725
down here with ten times sixteen And I see
over here in my final example here I
233
00:19:47,725 --> 00:19:53,989
didn't bother to propagate the ten to x.
But we can do that, and this So we can
234
00:19:53,989 --> 00:19:59,676
either do this optimization. So x times
sixteen if we didn't do the propagation,
235
00:19:59,676 --> 00:20:05,580
would be equivalent to x left shift four.
Or we can just replace this by ten times
236
00:20:05,580 --> 00:20:12,538
sixteen. That'd be even better. We wind up
achieving the value 160. Returning to an
237
00:20:12,538 --> 00:20:17,150
idea I mentioned a couple of slides ago.
Let's say there is an assignment in a
238
00:20:17,150 --> 00:20:22,062
basic block. Some registered W is assigned
some value that's computed on the right
239
00:20:22,062 --> 00:20:26,374
hand side. Let's say that W, the
registered name is not used anywhere else
240
00:20:26,374 --> 00:20:31,046
in the program. It doesn't appear
anywhere, not only in this basic block but
241
00:20:31,046 --> 00:20:35,708
in any other part of the procedure in
which this statement appears. Well then,
242
00:20:35,903 --> 00:20:40,900
the statement is dead and can be just
deleted from the program And dead here
243
00:20:40,900 --> 00:20:45,831
means it does not contribute to the
programs result. Since the value that we
244
00:20:45,831 --> 00:20:51,606
write into W is never referenced anywhere,
W is never used, doing the computation, of
245
00:20:51,606 --> 00:20:56,797
W in the first place was a waste of time,
so we can just delete that computation.
246
00:20:56,992 --> 00:21:02,371
Here's a simple example. Let's assume that
the register a is not used any place else,
247
00:21:02,562 --> 00:21:07,658
in the program. And, the first thing we
have to do, so here's our initial piece of
248
00:21:07,658 --> 00:21:12,626
code. The first thing we do is we put it
in single assignment form. And so I've
249
00:21:12,626 --> 00:21:18,206
renamed here, this register x, to be,
register b. Okay, and once we do that, let
250
00:21:18,206 --> 00:21:23,360
me do that, so we'll say that B=Z+Y and
A=B, and then we propagate this forward.
251
00:21:23,360 --> 00:21:29,087
Alright, so we've now replaced this use of
A by B, so this takes us to this state
252
00:21:29,087 --> 00:21:34,957
where we have this piece of code. Now we
can see that we have an assignment to A. A
253
00:21:34,957 --> 00:21:40,469
is not used in the subsequent instruction.
We already said that A is not used
254
00:21:40,469 --> 00:21:46,124
anywhere outside of the basic block, and
so the assignment a=b can be deleted, and
255
00:21:46,124 --> 00:21:51,758
we wind up with this shorter basic block.
Now each local optimization actually does
256
00:21:51,758 --> 00:21:55,673
very little by itself. And some of these
optim izations, some of these
257
00:21:55,673 --> 00:22:00,165
transformations that are presented
actually don't make the program run faster
258
00:22:00,165 --> 00:22:04,368
at all. They don't make it run slower
either but by themselves they don't
259
00:22:04,368 --> 00:22:08,847
actually make any improvement to the
program. But, Typically, the optimizations
260
00:22:08,847 --> 00:22:13,109
will interact. So performing one
optimization will enable another. And we
261
00:22:13,109 --> 00:22:18,008
saw this in the little example that I did,
a few slides ago. So the way to think
262
00:22:18,008 --> 00:22:22,920
about an optimizing compiler is that it
has a big bag of tricks. It has a lot of.
263
00:22:22,920 --> 00:22:27,298
Individual program transformations that it
knows And what it is going to do when
264
00:22:27,298 --> 00:22:31,676
faced with a program's optimize, it's
going to rummage around in its bag looking
265
00:22:31,676 --> 00:22:36,108
for an optimization, that applies to some
part of the code. If it finds one, it will
266
00:22:36,108 --> 00:22:40,107
do the optimization, it will do the
transformation and then it will repeat.
267
00:22:40,107 --> 00:22:43,945
It'll go back and look at the program
again, and see if there's another
268
00:22:43,945 --> 00:22:48,323
optimization that reapplies. Then it will
just keep doing this until it reaches a
269
00:22:48,323 --> 00:22:52,431
point where none of the optimization's it
knows about can be applied to the
270
00:22:52,431 --> 00:22:59,329
programming. Next, we'll take a look at a
bigger example and try applying some of
271
00:22:59,329 --> 00:23:04,888
the optimizations that we've discussed, to
it, and see how far we get. And of course
272
00:23:04,888 --> 00:23:10,244
this example has been constructed to
illustrate, many of the optimizations that
273
00:23:10,244 --> 00:23:15,599
we discussed. So, the first thing we can
do. There are a couple of opportunities
274
00:23:15,599 --> 00:23:20,819
for algebraic simplifications. So, we can
replace the squaring up here, by a
275
00:23:20,819 --> 00:23:26,378
multiply. And down here we had a multiply
by two, which we can replace by a left
276
00:23:26,378 --> 00:23:31,843
shift of one. Next we can observe that we
have some copies and constants. So we have
277
00:23:31,843 --> 00:23:36,492
a constant assignment to b and a copy
assignment to c And those can be
278
00:23:36,492 --> 00:23:41,861
propagated forward to the uses of b and c.
Once we've done that, we can do constant
279
00:23:41,861 --> 00:23:47,230
folding. So here, the assignment to e, The
opera-, the arguments to the shift are all
280
00:23:47,230 --> 00:23:52,730
constants, And so that can be replaced by
an assignment, that e gets the value six.
281
00:23:52,730 --> 00:23:57,742
Next we could observe that we have a
common sub expression that we could
282
00:23:57,742 --> 00:24:03,659
eliminate that both a and d have the value
x times x. So the assignment to d could be
283
00:24:03,659 --> 00:24:09,308
replaced by a copy that d now gets the
value of a. Now we have two opportunities
284
00:24:09,308 --> 00:24:14,144
again for copying constant propagation the
assignment to D and the assignment to E
285
00:24:14,144 --> 00:24:19,642
can be propagated forward. And finally we
can do a bunch of dead code elimination.
286
00:24:19,642 --> 00:24:24,779
So, assuming that, none of these values,
B, C, D, or E is used anyplace else in the
287
00:24:24,779 --> 00:24:29,792
program, all four of these statements can
be deleted. And this is where we actually
288
00:24:29,792 --> 00:24:34,684
get some real performance improvement. So
here we actually are now saving entire
289
00:24:34,684 --> 00:24:40,591
instructions, and that's the best kind of
savings that we can have And so we wind up
290
00:24:40,591 --> 00:24:46,394
with this as our final form. So notice
that a is assigned the value xx. F is
291
00:24:46,394 --> 00:24:52,510
then assigned, the value a+a, And then g
is assigned the value sixf. Now, this is
292
00:24:52,510 --> 00:24:58,548
not quite as fast as it could be, alright?
There's actually one more algebraic
293
00:24:58,548 --> 00:25:04,351
optimization that could be done. We can
notice here that f is actually=to twoa,
294
00:25:04,351 --> 00:25:12,185
And then we could do some rearrangement
here to discover that g=12f. Sorry, sorry
295
00:25:12,185 --> 00:25:17,883
twelve x a. Alright, And then this
statement assignment to F might become
296
00:25:17,883 --> 00:25:23,465
dead code, and we could delete it from the
program. I think some compilers would
297
00:25:23,465 --> 00:25:28,785
actually find this, but I believe that
even current state of the art compilers,
298
00:25:28,785 --> 00:25:34,040
many of them, would not discover this last
rearrangement to the program.