After numerous videos on run time
organization and stack machines, we are
finally ready to begin our discussion of
code generation. So as I mentioned in the
previous video we're going to focus on
generating code for stack machines. This
is probably the simplest code generation
strategy. It doesn't generally yield
extremely efficient code. It's an
interesting strategy and certainly not,
totally not an unrealistic one. It's more
than complex enough for our purposes. We
want to run a real machine and we're going
to the mix processor. In particular we're
going to use a simulator from it which
runs on about any kind of hardware so that
will be very convenient for the course
project And the basic idea, the basic
strategy, is going to be to simulate a
stack machine using Mipp's instructions
and registers. So the first decision in,
designing our simulation, is deciding
where to put the accumulator in. We'll
keep that, in this register, A0. Any
register would have done but we'll just
use A0 always for the accumulator And then
the stack is going to be kept in memory
And I should point out here that when we
talk about a one register stack machine
nominally that register in this case A0,
is the top of the logical stack of the
stack machine But just to avoid confusion
in the terminology, I'm going to refer to
A0 as the accumulator and the stack as all
of the other data that's kept in a memory
stack on the MISC processor, so we'll just
consider A0 the accumulator to be distinct
from the stack, which lives in memory And
the stack on the MIPS will grow towards
the lower addresses which is the standard
convention on MIPS. The address of the
next location on the stack is going to be
kept in the [inaudible] SP And this
register actually has a mnemonic name that
stand for stack pointer. So, normally on
the MIPS machine, compilers use SP to,
point to, their stack, and the top of the
stack will always be at the address, SP
plus four. So, remember the stack is
growing towards low addresses, and the
address, in the stack pointer is the ne xt
unallocated location on the stack. So the
stack pointer actually points to unused
memory, and the top of the stack,
therefore, is at the next higher word
address which would be SP plus four, Now
the MIPS architecture is quite an old
architecture. It was designed in the
1980's and it was, or is, the prototypical
reduced instruction set computer, or risk
machine. And the idea behind RISC machines
was to have a relatively simple
instruction set. Most of the operations
used registers for operands and results.
And then load and store instructions are
used to move values to and from memory. So
primarily all the computation takes place
in registers, and the memory operations
are primarily are just loading and storing
data. There are 32 purp-, there are 32
general-purpose registers on the MITS,
it's a 32 bit machine. We're only going to
use three of those registers. We already
talked about SP, the stack pointer. A0 the
accumulator, and we'll need one more
register for temporary values. So some
operations that take two arguments like
plus and times will have to have two
registers to hold the arguments to the
operation. So we'll use the accumulator
for one of those and a temporary register
for the other. And there is a lot more
information on the MIPS architecture in
the SPIM documentation. Spim is the
simulator that we, we'll use to execute
MIPS code. Now of course, to, generate
code for the mix. We'll also need some mix
instructions. And we'll be able to get
away, with just a very small number of
instructions. Five in fact, for our first
example And here they are. So the first
instruction we need, is load, or load word
And the way this works is it takes the
value of register two, takes the contents
that are in register two Adds a fixed
offset. So this is a number that's,
directly in the code Adds a fixed offset
to that to the contents of register two.
That's a memory address. It loads the
value of that memory address into register
one. The add instruction adds the contents
of register two and register three
together and stores the results in
register one again. The store operation,
or store word operation takes the value in
register one and stores it into memory. So
that's stored at a memory address, and
with the memory address is the contents of
register two, plus a fixed offset that's
in the code. And an add immediate
unsigned, takes, is an unsigned add, and
it takes a value in register two, an
immediate value. So, this is just a
number, that's a constant that's directly
embedded in the code. It adds that to the
value register two and stores the result
in register one. And the unsigned aspect
here just means that the overflow is not
checked, we're not, we're not checking
whether we generate a number that's
beyond, beyond what we could represent if
we had sine numbers. Finally, load
immediate just takes a constant that's in
the code, and puts it into, the register
that's named as the first argument
Alright? So those are the five
instructions that we need, to do a, one
very simple example. So now we're ready to
do our first program, and not surprisingly
it's the same program that we looked at in
previous videos when we were talking about
stack machine code. So let's look, here's
the program for adding seven plus five,
written out in our little abstract stack
machine language. Now our goal is to
implement this program using MIPS
instructions. So over here on the right,
I'm going to layout the instructions we
would use to simulate this program or
implement this program on the MIPS machine
Alright? So the first instruction is to
load seven into the accumulator. And we
can do that with a load immediate. We're
going to load immediate the value seven.
A0 is our accumulator register, and so
this instruction puts seven in the
accumulator. Next instruction, we want to
push the value of the accumulator onto the
stack. How do we do that? Well we have to
store the value onto the stack, and
remember the stack pointer points to the
next unused memory location. And so we're
just storing directly at what the stack
pointer points to, so that's at zero
offset from the stack pointer. The value
of the accumulator pushes the value onto
the stack, and now to restore the
invariant. That the stack pointer points
to the next unused location, we have to
subtract four from the stack pointer.
Okay. So, these two instructions together,
implement a push, they push the data value
onto the stack, and they move the stack
pointer to the next unused address.
Alright, now I'm ready to do the next
instruction, loading five into the
accumulator. Well, we already know how to
do that. We'll be a load immediate into
the accumulator register A0, the immediate
value five Are now ready to do the add And
how does that work? Well, first, we have
to load the value of that's on the top of
the stack, alright. Because it's like an
argument is taken from the top of the
stack. And since [inaudible] can only do
operations out of registers, that value
has to go somewhere into a register. And
this is where we use our temporary
register. So now, this value is now at
offset four from the stack pointer,
because we subtracted four from the stack
pointer And we load it into register T1.
Okay, And then we can actually perform the
add. And so we add the accumulator to the
value of T1 and we store the result back
into the accumulator And finally we're
going to pop the stack so we're done with
the value that's on the stack, And how do
we pop? Well, we just add four to the
stack pointer, and that moves the stack
pointer back popping that value off of the
stack.