In this video, we are going to move beyond
our discussion of Run-time Organization
and begin talking about code generation
And in this first you know, it was
probably quite a long series of videos on
code generation, we are gonna talk about
the simplest model for code generation
which is called a stack machine. So, in a
stack machine, you might guess that the
primary storage is some kind of a stack
and you would be right. In fact, the only
storage that the stack machine has is the
stack And the way the stack machine works
is that it executed an instruction, and
all instruction have the form. There's
some function of some arguments and they
produce one result. And what that does is
it'll pop in upper hands for the stack so
the arguments a1 through an are stored at
the top of the stack. It will then compute
the function f using those operands and it
will push the result r back on top of the
stack. Okay, So, let's take a look at a
simple example. Let's see how we would
compute seven plus five using a stack
machine. So, we would have our stack And
initially the stack might have, already
have some stuff on it but we don't care
what that stuff is and so it will execute
seven plus five. What we would do, well
first we will have to get the seven and
the five out of the stack so as we get
pushed on stack and we'll see more about
how that happens in a minute. And let's
say that seven and five were both on the
stack. And so now we wanted to compute the
addition on seven and five so, addition
takes two arguments so we would pop the
two arguments off the stack. And we wined
up with the five and the seven Pop-up the
stack. We will perform the operation plus
and then the result will get push back
under the stack. So this would be good to
twelve and then twelve will get push back
on to our stack. Okay. And I noticed that
I did indicate that there might be some
other stuff on this stack already. Let me
give that stuff a name. And let me talk
about one very important property of the
stack machine. So, those we have evaluated
seve n+5, we round up in the situation
where the results of that operation was on
top of the stop of the stack. Okay, and
the initial stack contents was unchanged.
This stack, the stack that was below the
arguments that we are interested in didn't
get modified. Okay. So, we have survived
through all the operations unchanged. And
this is an important property of the stack
machine. That we will exploit and the
general to say what the general property
is when you evaluate an expression the
result of the expression will be on top of
the stack and the contents of the stack
prior to the beginning evaluation of the
expression will be preserved. So, now
let's take by how we could program a stack
machine. So, let's have a language with
just two instructions in it. We can push
an engine run to the stack and then we
have the operation add which will add the
two integers on the top of the stack. And
now, let's take a look at this program
which pushes seven and then pushes five
and then does an add. So, let's think
about how this program would work. Okay,
so we have our stack contents and now, and
the first instruction is to push seven. So
wined up with the seven on the stack,
added to the stack and now we push five.
Okay. And so the next step, we'll have
five and seven on top of the stack then
we'll perform the add and then we'll pop
these two elements off the stack and add
them and push the result back on. And
we'll wind up with twelve on the stack and
again the original stack contents are
preserved. Now, what interesting property
of stack machine code is that the location
of the upper hands and result is not
exquisitely stated in the instruction. And
that's because these instructions always
refer to the top of the stack. And this is
in contrast were register machine or
register instructions that explicitly name
where they take their upper hands from and
where they put the results. So for example
you might be familiar from seeing some
machine code or assembly code in the past
or and add instruction by typically take
three regis ters, two for the arguments
[inaudible] two for the registered
arguments are gonna be added together and
one for the destination for the result
where in the stack machine we just have. A
single word add and no explicit naming of
the arguments because it's fixed, where
the arguments will come from. The
arguments will always be popped from the
stack and the result will always be placed
back on top of the stack. And. The
interesting property here is that it leads
to more compact programs because we have
to say less in the instructions the
programs themselves are actually quite a
bit smaller than register machine
programs. And this is one of the reason,
reasons that Java bytecode uses a stack
evaluation model because it leads to more
compact programs and especially in the
early days of Java when it was very
expensive to ship these programs around
the Internet to download them, having very
small compact code was a good property.
And by we might wonder why would we prefer
register machine and the answer is that
register machine code is generally faster
because we can place the data exactly
where we wanted to be. We will generally
have fewer, you know, immediate operations
and less manipulation of the stack,
pushing and popping stuff to get to the
data that we want. And then it turns out
that there isn't inter-media point between
a pure stack machine and a pure register
machine, that's interesting. This is
called an N register stack machine. And
conceptually, the idea of the N register
stack machine is to keep the. Top end
locations of the stack in registers. And
the particular variant of the un-resourced
stack machine that we particularly
interested in is the one register stack
machine because the terms that you get
widely benefit by even having a single
register that's dedicated to the top of
the stack. This register is called the
accumulator so the dedicated registry here
is called the accumulator. It's called
that because intuitively it accumulates
the results of operations and then all the
other data lives on the stack. So, what is
the advantage of a one register stack
machine? Well, let's think about the add
instruction and how it works in a pure
stack machine? So, in the pure stack
machine, what is the add instruction going
to do it's going to pop two arguments from
the stacks, a five and seven. And it's
going to add them and then it's gonna put
the result back onto the stack. And let's
just name the rest of the stack contents
there. And that requires three memory
operations. After load, two arguments and
then store one result. But in the one
razor stack machine, the add operation
actually does a lot of its work out of the
one register. So, the one of the arguments
is already stored in the register because
that's the conceptually the top of the, of
the stack. And, the result will be pushed
back on the top of the stack which again
is just the accumulated register. So here,
one of the arguments in the right are both
taking from registers and there's only one
memory reference to get the second
argument from the portion of the stack
that's stored in the memory. So in
general, let's think about how we would
evaluate and arbitrary expression using a
stack machine. So now this isn't I should
say, you know, just stack machine called
like we're looking at it before. This is
not just a sequence of bytecode level
operations, this is actually a full
expression as you might find in Kuhl so
there are other complex expressions nested
inside of some operation. All right. And
so, forget the operation that takes N
arguments and those arguments are
expression that themselves needs to be
evaluated so here's a general strategy for
doing that with the stack machines. So,
for each of the sub-expression, each of
the arguments in order we're going to
evaluate it recursively using the same
stack machine strategy and that will end
up putting the result when we evaluate EI,
recursively the results will be in the
accumulator. And so the results is in the
accumulator, alright. And then we're going
to push that results onto the memory
stack. So we'r e going to take that
results and we're gonna free up the
accumulator and save it on the stack, the
portion of stack that's in memory, okay.
So we do this evaluating the
sub-expressions for the first and -one
arguments. So everything except the last
one, okay. We're gonna use the same
strategy, for the last one, for en. We
just evaluate. We don't push the result on
the stack. That just means that the result
is left in the accumulator okay so now we
have one of the arguments of the
accumulator. The last one we evaluated and
the other in line as one are o the top of
the portion of the stack that's in memory.
So that what we all have to do is we pop
in -one values from the stack and combine
any compute up using the -one values plus
the value of the accumulator and we store
the result back into the accumulator,
okay. So that's the general strategy for
evaluating an expression using a stack
machine. So let's do this now for a simple
example. Let's take our same example that
we've been using and let's evaluate the
expression seven plus five. So, how we're
gonna do that? Well, we're evaluating a
plus expression and that takes two
arguments, two expression as the way to
evaluate each of those. So first we
evaluate the expression seven. Let me
actually, let me draw our stack here.
Okay, so we have our initial content to
the stack, we have our initial
accumulator. And so now we're evaluating
seven, okay? And of course a constant
loose evaluate to itself and the result is
toward the accumulator, okay? So that's
the first step after evaluating seven. And
now because that's the first argument to
plus, it has to get pushed on to the
stack, the portion of the stack in main
memory. So. Now, we have a situation that
looks like this. All right, in the course
to seven is still in the accumulator but
we're now about to override it, we're not
gonna use that value again. Because the
next thing we're gonna do is evaluate the
second argument to plus and that happens
to be in this case also a constant
expression five and so that will get
evaluated and then stored in the
accumulator. Okay, so I will override the
seven. This will be five there, all right?
And now, we have evaluated both arguments.
Okay, remember in the case of just having
two arguments. The first argument gets
evaluated and saved on the stack so it
doesn't, so we don't lose the value when
we evaluate the second argument. And the
second argument we uses is the last one we
can just leave in the accumulator And that
way actually evaluates the plus. Okay, so
we do the accumulator gets the accumulator
plus the top of the memory stack. So in
this case, that results in adding seven
and five. And we line up and of course we
pop the argument from the memory stack,
right. So we have just the original
contents there and now the value twelve in
the accumulator. So, as I think you would
see from the example, the invariant that
we're gonna maintain with the stack
machine is that after we evaluate an
expression e, the accumulator holds the
value of e so the result of evaluating
[inaudible] accumulator and the stack is
unchanged. And so the stack, the memory
portion of the stack is whatever it was
before we start of evaluating e. And this
is a very, very important property,
expression evaluation preserves the stack.
So, now let's look at a more elaborated
example, just slightly more elaborate,
three+7+5. And the interesting thing about
this example. Is that now one of the
arguments to the other plus is itself a
compound expression. So it would have to
be, that would have to be evaluated
recursively as part of evaluating the
entire expression so let's see how this
works. So the first thing that's going to
happen or evaluating the outer plus, we're
gonna evaluate the first argument to that
plus that's just the constant three so
we're gonna load it into the accumulator.
And that's the result of evaluating three.
And now because it's the first argument to
the plus, we have to save it before we can
get around to evaluating the addition
itself. So that result is pushed on to the
stack. And now we're g onna evaluate the
second argument to the outer plus and that
itself has two arguments. And the first
argument to that, to the inner plus is
seven. And so that winds up getting stored
in the accumulator, that's the result of
evaluating seven. And then because the
inner plus has two arguments, we have to
evaluate the second, evaluate the second
argument to the inner plus, the seven has
to get saved to the stack. So now, the
stack has seven three and whenever it had
before we start it. Next, we're gonna
evaluate the second argument to the inner
plus And so evaluating a constant five
will result in five being loaded in the
accumulator and now, we have evaluated all
the arguments to the inner plus, okay. And
so we know from our stack discipline that
the last arguments is in the accumulator
and the first argument will be on top of
the stack. So the next thing that will
happen is that we'll pop that second
argument from the stack added to the
accumulator and store back into the
accumulator and so now we have the results
of the inner plus in the accumulator. We
also have the pop, the seven from the
stack, okay and finally now we've
evaluated the second argument to the outer
plus. So now we can perform the outer
edition. And what is that involve that
takes the stack contents then adds it to
the value that is currently on the top of
the stack which is the value three which
is what we saved a long time ago now to,
to remember it from what it was to do the
other addition and we wind up. After we
pop the stack with fifteen in the
accumulator, that's the results of the
entire expression, and notice it's the
same stack that we started with. Okay? So
evaluating this entire expression,
resulted in the, result in any accumulator
and the stack being unchanged And if you
looked at that the sub-expression, you can
see that the same things happened. So
let's take a look at the evaluation of
seven plus five. So where that take place
that started here. Okay. Started at this
instruction. And, it lasted down to here
and you can see that the evaluation of
seven + five which encompasses these five
expressions resulted in twelve being put
on top of the stack, that's the result of
seven + five and it didn't affect the
contents I'm sorry. It resulted in twelve
being placed in the accumulator and it
will left the stack unchanged to where it
was when the evaluation of seven plus five
began. So here is where it began and the
value we had saved three was on the top of
the stack and when we're done evaluating
seven plus five indeed again the value
three and. All the other stuff that was
there before are still on the stack.