1
00:00:03,000 --> 00:00:07,087
In this video I'm going to give a very
brief introduction to Intermediate Code

2
00:00:07,087 --> 00:00:15,066
and its use in compilers. So the first
question to address is, what is

3
00:00:15,066 --> 00:00:19,081
Intermediate Code or an Intermediate
Language? And as the name suggests, an

4
00:00:19,081 --> 00:00:24,050
Intermediate Language is just that, it's a
language that's intermediate between the

5
00:00:24,050 --> 00:00:30,006
source language and the target language.
So, keep in mind what a compiler does. So

6
00:00:30,006 --> 00:00:36,023
a compiler takes a program written in some
source language. And, it provides a

7
00:00:36,023 --> 00:00:43,039
translation of that program into some
target language And so in this class, for

8
00:00:43,039 --> 00:00:47,097
example, where often our source language
is cool and our target language is mixed

9
00:00:47,097 --> 00:00:54,033
assembly code. Now, an Intermediate
Language actually lives in between these

10
00:00:54,033 --> 00:00:58,028
two and a compiler that uses an
Intermediate Language will first translate

11
00:00:58,028 --> 00:01:02,024
its source language into the Intermediate
Language and then later translate the

12
00:01:02,024 --> 00:01:08,023
intermediate the code in the Intermediate
Language into the target language. And you

13
00:01:08,023 --> 00:01:13,098
might wonder, well why make life so
difficult? Why when, why do something in

14
00:01:13,098 --> 00:01:19,084
two steps if you can do in one step? And
it turns out that for many purposes this

15
00:01:19,084 --> 00:01:25,054
intermediate level here is actually quite
useful precisely because it provides an

16
00:01:25,054 --> 00:01:30,680
intermediate level of abstraction. So, in
particular, the intermediate level may

17
00:01:30,680 --> 00:01:37,063
have more details in it than the source
language. So for example, if we want to

18
00:01:37,063 --> 00:01:42,408
optimize register usage you know, a source
language like Cool has no notion of

19
00:01:42,408 --> 00:01:47,041
registers at the source level, and so
there's no way to even express the kinds

20
00:01:47,041 --> 00:01:51,067
of optimizations you might want to do with
registers. So an Intermediate Language

21
00:01:51,067 --> 00:01:55,765
that exposes that at that amount of
detail, at least have registers in it will

22
00:01:55,765 --> 00:02:00,667
allow you to talk about and, and write
algorithms that could try to improve the

23
00:02:00,667 --> 00:02:05,661
use of registers in the program. On the
other hand, the Intermediate Language

24
00:02:05,661 --> 00:02:10,363
which will also have fewer details than
the target. And so it might be for

25
00:02:10,363 --> 00:02:14,706
example, if the Intermediate Language is a
little bit above the level of the parti

26
00:02:14,706 --> 00:02:18,752
cular instruction set of a particular
machine, and therefore it's easier to

27
00:02:18,752 --> 00:02:23,404
retarget that, that intermediate level of
code to lots of different kinds of

28
00:02:23,404 --> 00:02:28,426
machines. Precisely because doesn't have
all the grubby details in a, of a

29
00:02:28,426 --> 00:02:33,308
particular machine. And, experience has
shown, that this is actually a pretty good

30
00:02:33,308 --> 00:02:37,346
idea to have Intermediate Language. And,
almost all compilers have an Intermediate

31
00:02:37,346 --> 00:02:40,980
Language. I, In fact, in their
implementation and some compilers have

32
00:02:40,980 --> 00:02:45,403
more than one. Some compilers actually
translate through an entire the series of

33
00:02:45,403 --> 00:02:50,287
Intermediate Languages between the source
and target language. Now we're only going

34
00:02:50,287 --> 00:02:55,238
to consider one Intermediate Language for
the rest of this course. The kind of

35
00:02:55,238 --> 00:02:59,100
Intermediate Language which we're going to
look at is going to be a high level

36
00:02:59,100 --> 00:03:03,680
assembly. And so, as I suggested on the
previous slide, this language is going to

37
00:03:03,680 --> 00:03:08,806
use register names but it will have an
unlimited number, so we can use any number

38
00:03:08,806 --> 00:03:13,238
of registers that we like. We're not bound
to 32 or 64 registers. The control

39
00:03:13,238 --> 00:03:17,852
structures will look a lot like assembly
language. In particular, there will be

40
00:03:17,852 --> 00:03:23,082
explicit jumps and labels on instructions.
And the language will also have op codes

41
00:03:23,082 --> 00:03:26,783
in it so it'll look like assembly language
level op codes. But some of these op codes

42
00:03:26,783 --> 00:03:31,714
will be higher level. So for example, we
might have an op code called Push. And

43
00:03:31,714 --> 00:03:37,046
Push would end up translating into several
concrete assembly language instructions

44
00:03:37,046 --> 00:03:43,056
for a particular target machine. In the
intermediate code that we'll be looking

45
00:03:43,056 --> 00:03:47,084
at, every instruction will have one of two
forms. It will either be a binary

46
00:03:47,084 --> 00:03:53,176
operation, or it will be a unary
operation. And always the arguments on the

47
00:03:53,176 --> 00:03:57,294
right hand side, in this case the y and
the z, will be either registers or

48
00:03:57,294 --> 00:04:03,381
constants. They could also be immediate
values. And this is a very, very common

49
00:04:03,381 --> 00:04:08,935
form of Intermediate Code, so widely used,
and so widely used it actually has a name.

50
00:04:08,935 --> 00:04:15,334
It's called Three Address Code because
every instruction has at most three

51
00:04:15,334 --> 00:04:23,441
addresses in it. Two arguments, at most
two arguments and then a destination. Now,

52
00:04:23,441 --> 00:04:29,908
to see that this code is actually low
level notice that you know, higher level

53
00:04:29,908 --> 00:04:34,314
expressions that involve multiple
operations will have to be translated into

54
00:04:34,314 --> 00:04:39,972
a sequence of instructions that do only
one operation at a time. So, for example,

55
00:04:39,972 --> 00:04:45,816
if I have the expression, x = sorry, x + y
 z, and let me put in parens here to show

56
00:04:45,816 --> 00:04:50,570
the association. So the times binds more
tightly than the plus, we're going to have

57
00:04:50,570 --> 00:04:55,061
to, this can't be written directly in an
intermediate , language of this form.

58
00:04:55,061 --> 00:04:58,069
Instead, we would have to write it
something like the following. We have to

59
00:04:58,069 --> 00:05:04,497
first compute y  z and assign that to a
new register or a temporary or you know, a

60
00:05:04,497 --> 00:05:10,322
new register t1 to hold the intermediate
value. And then we would have to use t1 to

61
00:05:10,322 --> 00:05:14,986
compute x + t1, which of course is the
value of the entire expression and that

62
00:05:14,986 --> 00:05:19,242
would end up getting stored in another
register. I noticed that one effect of

63
00:05:19,242 --> 00:05:25,395
forcing you to use only one operation at a
time. You see, you do one primitive

64
00:05:25,395 --> 00:05:29,094
operation at time and then the result of
that has to be restored in a register. One

65
00:05:29,094 --> 00:05:34,628
effect of that is to give every
subexpression of the program a name. So,

66
00:05:34,628 --> 00:05:40,740
if I look back at this expression here, I
see you know, like y  z is anonymous.

67
00:05:40,740 --> 00:05:46,069
That in this expression x + y <i>z the
expression y </i> z itself doesn't have a

68
00:05:46,069 --> 00:05:51,842
name. And by rewriting it like this, I
actually name that intermediate result. So

69
00:05:52,062 --> 00:05:58,810
again just to summarize this point, one
consequence of having to write out

70
00:05:59,073 --> 00:06:04,083
compound expressions as a sequence of
instructions that do a single operation in

71
00:06:04,083 --> 00:06:12,000
time is that every intermediate value will
be given its own name. Generating

72
00:06:12,000 --> 00:06:16,011
Intermediate Code is very similar to
generating assembly code and we're not

73
00:06:16,011 --> 00:06:19,093
going to go into this in any detail
because it is so similar. But I will

74
00:06:19,093 --> 00:06:24,466
sketch it for you, you know, briefly. The
main difference between generating

75
00:06:24,466 --> 00:06:30,137
assembly code and generating intermediate
code is that we can use any number of

76
00:06:30,137 --> 00:06:38,006
registers in the Intermediate Language to
hold intermediate results. To generate

77
00:06:38,006 --> 00:06:41,325
intermediate code, we could write a
function called IGEN for Intermediate Code

78
00:06:41,325 --> 00:06:45,024
Generation that takes two arguments. It
takes the expression for which we're

79
00:06:45,024 --> 00:06:49,077
generating code and it takes the register
into which the results of that expression

80
00:06:49,077 --> 00:06:54,057
should be stored. And to give you just one
example, and this is the only example that

81
00:06:54,057 --> 00:06:59,091
I'll do. Let's take a look at generating
intermediate code for a+ expressions. I

82
00:06:59,091 --> 00:07:05,021
wanna generate code for e1 + e2 and I want
the results of that to be stored in the

83
00:07:05,021 --> 00:07:08,875
register t, okay? So the first thing I'm
going to do is I'm going to generate code

84
00:07:08,875 --> 00:07:12,089
for the subexpressions and I need some
place to store the results of the sub

85
00:07:12,089 --> 00:07:16,787
expressions so I'm just going to make up
new register names for those results. So

86
00:07:16,787 --> 00:07:21,697
I'll generate code for e1 and store that
in some register, t1 and I'll generate

87
00:07:21,697 --> 00:07:25,836
code for e2 and I'll store the results of
that in some register t2. And then, we can

88
00:07:25,836 --> 00:07:32,989
just compute the sum. So t = t1 + t2 and
notice that this is a Three Address

89
00:07:32,989 --> 00:07:37,793
Instruction. So we're sticking to the
rules here and only using three Address

90
00:07:37,793 --> 00:07:45,212
Instructions In our Intermediate Code
Generator. And also notice that because we

91
00:07:45,212 --> 00:07:49,076
have an unlimited number of registers,
this actually leads to very simple code

92
00:07:49,076 --> 00:07:53,050
generation of intermediate code. In fact,
it's even a little bit simpler than

93
00:07:53,050 --> 00:07:57,098
generating code for a stack machine.
Recall that, in a stack machine, we had to

94
00:07:57,098 --> 00:08:02,070
save the intermediate results here of e1
on the stack. And that involved, you know,

95
00:08:02,070 --> 00:08:07,659
more than one instruction to actually push
the result and adjust the stack pointer

96
00:08:07,659 --> 00:08:14,425
and things like that. And here we can just
save it in a register, and, and then just

97
00:08:14,425 --> 00:08:21,012
use that register name later on. So, that
is actually all I have to say about

98
00:08:21,012 --> 00:08:25,097
Intermediate Code for this course. You
should be able to use Intermediate Code at

99
00:08:25,097 --> 00:08:29,641
the level in which we are going to be
using it in, in lectures. The, in the

100
00:08:29,641 --> 00:08:34,179
future videos we'll actually be looking at
Intermediate Code quite a bit and using it

101
00:08:34,342 --> 00:08:39,008
especially to express certain kinds of
optimizations. You should also be able to

102
00:08:39,008 --> 00:08:42,674
write simple Intermediate Code programs
and you should be able to write algorithms

103
00:08:42,852 --> 00:08:47,382
that work on Intermediate Code. But I'm
not going to expect you to know how to

104
00:08:47,382 --> 00:08:51,209
generate Intermediate Code because we're
not going to discuss it any further. And

105
00:08:51,209 --> 00:08:55,041
quite frankly, it doesn't introduce any
new any idea. That's really just a

106
00:08:55,041 --> 00:09:02,402
variation on the cogeneration ideas that
we've already discussed in quite a bit of