1
00:00:02,980 --> 00:00:08,022
After numerous videos on run time
organization and stack machines, we are

2
00:00:08,022 --> 00:00:16,074
finally ready to begin our discussion of
code generation. So as I mentioned in the

3
00:00:16,074 --> 00:00:20,671
previous video we're going to focus on
generating code for stack machines. This

4
00:00:20,671 --> 00:00:25,152
is probably the simplest code generation
strategy. It doesn't generally yield

5
00:00:25,152 --> 00:00:29,342
extremely efficient code. It's an
interesting strategy and certainly not,

6
00:00:29,342 --> 00:00:34,055
totally not an unrealistic one. It's more
than complex enough for our purposes. We

7
00:00:34,055 --> 00:00:38,943
want to run a real machine and we're going
to the mix processor. In particular we're

8
00:00:38,943 --> 00:00:43,715
going to use a simulator from it which
runs on about any kind of hardware so that

9
00:00:43,715 --> 00:00:48,377
will be very convenient for the course
project And the basic idea, the basic

10
00:00:48,377 --> 00:00:53,759
strategy, is going to be to simulate a
stack machine using Mipp's instructions

11
00:00:53,759 --> 00:00:58,672
and registers. So the first decision in,
designing our simulation, is deciding

12
00:00:58,672 --> 00:01:03,296
where to put the accumulator in. We'll
keep that, in this register, A0. Any

13
00:01:03,296 --> 00:01:08,641
register would have done but we'll just
use A0 always for the accumulator And then

14
00:01:08,641 --> 00:01:14,161
the stack is going to be kept in memory
And I should point out here that when we

15
00:01:14,161 --> 00:01:19,812
talk about a one register stack machine
nominally that register in this case A0,

16
00:01:19,812 --> 00:01:25,135
is the top of the logical stack of the
stack machine But just to avoid confusion

17
00:01:25,332 --> 00:01:30,852
in the terminology, I'm going to refer to
A0 as the accumulator and the stack as all

18
00:01:30,852 --> 00:01:36,372
of the other data that's kept in a memory
stack on the MISC processor, so we'll just

19
00:01:36,372 --> 00:01:41,885
consider A0 the accumulator to be distinct
from the stack, which lives in memory And

20
00:01:41,885 --> 00:01:47,307
the stack on the MIPS will grow towards
the lower addresses which is the standard

21
00:01:47,307 --> 00:01:53,272
convention on MIPS. The address of the
next location on the stack is going to be

22
00:01:53,272 --> 00:01:58,917
kept in the [inaudible] SP And this
register actually has a mnemonic name that

23
00:01:58,917 --> 00:02:04,261
stand for stack pointer. So, normally on
the MIPS machine, compilers use SP to,

24
00:02:04,261 --> 00:02:09,764
point to, their stack, and the top of the
stack will always be at the address, SP

25
00:02:09,764 --> 00:02:14,663
plus four. So, remember the stack is
growing towards low addresses, and the

26
00:02:14,663 --> 00:02:20,368
address, in the stack pointer is the ne xt
unallocated location on the stack. So the

27
00:02:20,368 --> 00:02:25,200
stack pointer actually points to unused
memory, and the top of the stack,

28
00:02:25,200 --> 00:02:31,273
therefore, is at the next higher word
address which would be SP plus four, Now

29
00:02:31,273 --> 00:02:35,969
the MIPS architecture is quite an old
architecture. It was designed in the

30
00:02:35,969 --> 00:02:41,172
1980's and it was, or is, the prototypical
reduced instruction set computer, or risk

31
00:02:41,172 --> 00:02:45,394
machine. And the idea behind RISC machines
was to have a relatively simple

32
00:02:45,394 --> 00:02:50,009
instruction set. Most of the operations
used registers for operands and results.

33
00:02:50,009 --> 00:02:54,680
And then load and store instructions are
used to move values to and from memory. So

34
00:02:54,680 --> 00:02:59,238
primarily all the computation takes place
in registers, and the memory operations

35
00:02:59,238 --> 00:03:03,853
are primarily are just loading and storing
data. There are 32 purp-, there are 32

36
00:03:03,853 --> 00:03:08,355
general-purpose registers on the MITS,
it's a 32 bit machine. We're only going to

37
00:03:08,355 --> 00:03:12,959
use three of those registers. We already
talked about SP, the stack pointer. A0 the

38
00:03:12,959 --> 00:03:17,607
accumulator, and we'll need one more
register for temporary values. So some

39
00:03:17,607 --> 00:03:22,631
operations that take two arguments like
plus and times will have to have two

40
00:03:22,631 --> 00:03:27,530
registers to hold the arguments to the
operation. So we'll use the accumulator

41
00:03:27,530 --> 00:03:32,555
for one of those and a temporary register
for the other. And there is a lot more

42
00:03:32,555 --> 00:03:37,454
information on the MIPS architecture in
the SPIM documentation. Spim is the

43
00:03:37,454 --> 00:03:43,508
simulator that we, we'll use to execute
MIPS code. Now of course, to, generate

44
00:03:43,508 --> 00:03:48,641
code for the mix. We'll also need some mix
instructions. And we'll be able to get

45
00:03:48,641 --> 00:03:53,646
away, with just a very small number of
instructions. Five in fact, for our first

46
00:03:53,646 --> 00:03:58,780
example And here they are. So the first
instruction we need, is load, or load word

47
00:03:58,780 --> 00:04:03,617
And the way this works is it takes the
value of register two, takes the contents

48
00:04:03,617 --> 00:04:07,970
that are in register two Adds a fixed
offset. So this is a number that's,

49
00:04:08,151 --> 00:04:13,230
directly in the code Adds a fixed offset
to that to the contents of register two.

50
00:04:13,230 --> 00:04:18,068
That's a memory address. It loads the
value of that memory address into register

51
00:04:18,068 --> 00:04:23,248
one. The add instruction adds the contents
of register two and register three

52
00:04:23,248 --> 00:04:28,252
together and stores the results in
register one again. The store operation,

53
00:04:28,252 --> 00:04:33,776
or store word operation takes the value in
register one and stores it into memory. So

54
00:04:33,776 --> 00:04:39,040
that's stored at a memory address, and
with the memory address is the contents of

55
00:04:39,040 --> 00:04:43,930
register two, plus a fixed offset that's
in the code. And an add immediate

56
00:04:43,930 --> 00:04:49,254
unsigned, takes, is an unsigned add, and
it takes a value in register two, an

57
00:04:49,254 --> 00:04:54,651
immediate value. So, this is just a
number, that's a constant that's directly

58
00:04:54,651 --> 00:05:00,550
embedded in the code. It adds that to the
value register two and stores the result

59
00:05:00,550 --> 00:05:06,378
in register one. And the unsigned aspect
here just means that the overflow is not

60
00:05:06,378 --> 00:05:11,630
checked, we're not, we're not checking
whether we generate a number that's

61
00:05:11,630 --> 00:05:17,093
beyond, beyond what we could represent if
we had sine numbers. Finally, load

62
00:05:17,093 --> 00:05:22,552
immediate just takes a constant that's in
the code, and puts it into, the register

63
00:05:22,552 --> 00:05:26,776
that's named as the first argument
Alright? So those are the five

64
00:05:26,776 --> 00:05:32,040
instructions that we need, to do a, one
very simple example. So now we're ready to

65
00:05:32,040 --> 00:05:37,065
do our first program, and not surprisingly
it's the same program that we looked at in

66
00:05:37,065 --> 00:05:41,972
previous videos when we were talking about
stack machine code. So let's look, here's

67
00:05:41,972 --> 00:05:46,702
the program for adding seven plus five,
written out in our little abstract stack

68
00:05:46,702 --> 00:05:50,840
machine language. Now our goal is to
implement this program using MIPS

69
00:05:50,840 --> 00:05:55,511
instructions. So over here on the right,
I'm going to layout the instructions we

70
00:05:55,511 --> 00:06:00,300
would use to simulate this program or
implement this program on the MIPS machine

71
00:06:00,640 --> 00:06:05,054
Alright? So the first instruction is to
load seven into the accumulator. And we

72
00:06:05,054 --> 00:06:09,411
can do that with a load immediate. We're
going to load immediate the value seven.

73
00:06:09,411 --> 00:06:13,543
A0 is our accumulator register, and so
this instruction puts seven in the

74
00:06:13,543 --> 00:06:18,240
accumulator. Next instruction, we want to
push the value of the accumulator onto the

75
00:06:18,240 --> 00:06:22,159
stack. How do we do that? Well we have to
store the value onto the stack, and

76
00:06:22,159 --> 00:06:26,413
remember the stack pointer points to the
next unused memory location. And so we're

77
00:06:26,413 --> 00:06:30,356
just storing directly at what the stack
pointer points to, so that's at zero

78
00:06:30,356 --> 00:06:34,559
offset from the stack pointer. The value
of the accumulator pushes the value onto

79
00:06:34,559 --> 00:06:38,556
the stack, and now to restore the
invariant. That the stack pointer points

80
00:06:38,556 --> 00:06:43,029
to the next unused location, we have to
subtract four from the stack pointer.

81
00:06:43,029 --> 00:06:48,033
Okay. So, these two instructions together,
implement a push, they push the data value

82
00:06:48,033 --> 00:06:52,389
onto the stack, and they move the stack
pointer to the next unused address.

83
00:06:52,389 --> 00:06:56,569
Alright, now I'm ready to do the next
instruction, loading five into the

84
00:06:56,569 --> 00:07:01,220
accumulator. Well, we already know how to
do that. We'll be a load immediate into

85
00:07:01,220 --> 00:07:06,169
the accumulator register A0, the immediate
value five Are now ready to do the add And

86
00:07:06,169 --> 00:07:10,913
how does that work? Well, first, we have
to load the value of that's on the top of

87
00:07:10,913 --> 00:07:15,086
the stack, alright. Because it's like an
argument is taken from the top of the

88
00:07:15,086 --> 00:07:19,601
stack. And since [inaudible] can only do
operations out of registers, that value

89
00:07:19,601 --> 00:07:23,888
has to go somewhere into a register. And
this is where we use our temporary

90
00:07:23,888 --> 00:07:28,232
register. So now, this value is now at
offset four from the stack pointer,

91
00:07:28,232 --> 00:07:32,920
because we subtracted four from the stack
pointer And we load it into register T1.

92
00:07:33,220 --> 00:07:38,075
Okay, And then we can actually perform the
add. And so we add the accumulator to the

93
00:07:38,075 --> 00:07:42,755
value of T1 and we store the result back
into the accumulator And finally we're

94
00:07:42,755 --> 00:07:47,610
going to pop the stack so we're done with
the value that's on the stack, And how do

95
00:07:47,610 --> 00:07:51,998
we pop? Well, we just add four to the
stack pointer, and that moves the stack

96
00:07:51,998 --> 00:07:55,040
pointer back popping that value off of the
stack.