In this video we're going to generate code
for a small example program. The program
we'll take a look at takes a positive
imaginary X and sums all the numbers from
O up to X. So if X is O then the result is
O. Otherwise it is X plus the sum of all
the numbers up to X minus one. So this
isn't a interesting program but it does
illustration all of the features that we
discuss in the previous couple of videos.
So let's dive right in and talk about how
we're going to generate code for sum two.
So we begin by giving it a label for the
entry point to the function, so that'll be
the sum two entries. Alright and now we
have to generate code for the caller's
side, call, callee side excuse me, of the
calling sequence. So what was that? So the
first thing we have to do is we have to
set up the frame pointer, which would just
be the value of the stack pointer. So
that's the frame pointer for this
activation, and. Then we're going to have
to store the return address at the current
value of the stack pointer. And then we're
going to move the stack pointer
[inaudible]. Whenever we store something
on the stack we have to. >> The Seg
pointer is the next unused location. >>
Alright. Okay And so now we have to
generate code, for this if then else All
right? And the very first thing if you go
back and look at the code for if then else
is to generate code for the first sub
expression of the predicate. So we're
going to generate code for X, and that's
really easy And we're generating code for
a variable, just looks up the variable in
the current position of the frame. Sorry,
at the correct offset from the frame
pointer, alright? Alright so once we do
that now we are generating code for the
predicate And how do we do that? Well we
generate code for this first sub
expression, and now we have to save that
sub expression somewhere Because we are
going to generate code for another sub
expression. So the equality there is a
binary operator, so we have to save the
value we just computed somewhere on the
stack Alright? So we'll do that, so we'll
st ore the value of a zero on the stack.
And that will involve, as always, moving
the side pointer. Okay and now we generate
code for the second sub-expression of the
predicate. All right, that's also easy.
That's just load the immediate of the
immediate value into the accumulator,
alright. And now I'm going to load the
value that we said, the first or we move
the predicate back into a temporary
register and actually do the comparison.
So this is more code, as actually part of
the conditional, alright, so we do a load
word Entity one Of the value that we saved
before. Okay and now we need to pop the
stack okay. We'll do that here because
we're done with that value. Alright, and
now we're going to do the branch. So now
we test whether. The two sub-expressions
of the predicate are equal or not, and if
they are, then we jump to the true branch.
And here I'm going to give the true branch
a unique label, because this might be part
of a larger program where there are many
if-then-else's, and so I'm going to append
some identifying number on the end.
Instead of writing out true branch, I'll
call this true one Alright? Okay, and then
if we fall through, then we're on the
false branch, we'll call that false one
And now we're generating code for the
false branch, which is this summation here
Alright? And how are we going to do that?
Well this, whole thing is a plus
expression, which means we have the
generic code first. For the first
sub-expression which is just X. Alright?
So what do we do? Well we load. To
generate code for x we look up x at its
current offset. And [inaudible] that is
appropriate offset in the frame, using the
frame pointer. Okay? It is the only
argument, and so it's at four from the
frame pointer. I'm sorry the only argument
to the procedure, and so that's stored at
the first position for arguments, which is
always four from the frame pointer in our
scheme. All right, and now that we've
loaded it we have to save it because it is
part of a binary operation so we're going
to save that value on the stack. Kay. And
now we will. Adjust the [inaudible]. Okay.
And what are we going to do next? Well,
now we've, we've, we computed this
sub-expression, this X. We can't do the
plus yet until we compute the second
sub-expression which is the function call
Alright? So now we have the generate code
for the function call and I'm going to
move up here to the other side of the
screen here to, to show the rest of the
code. Okay And the first thing we do, to
generate code, for the function call Is to
start setting up our activation record
Alright? This is even setting up the new
activation record for the function, call
that we're about to make Alright? So what
do we do there? We store The frame
pointer. 'Kay, use this to our old frame
pointer. Add the stack on the stack.
[sound] Alright, and now, we have to
compute the argument All right? We have to
compute the x-1. So that code gets
inserted here in the template for our
function call. So, what's going to happen
there? Well, we're completing subtraction,
so the template for subtraction is to
first generate code for the first
sub-expression, then generate code for the
second sube-xpression, and then subtract
them. All right, so let's do that. So,
first we generate code for x again. Okay,
and now, since it's the first argument of
a binary operation, we're going to save it
on stack. Alright now we generate code for
the second argument of the subtraction.
Okay, and now we perform the subtractions
so we have to load the first argument back
into a temporary register. Have to
actually do the subtraction. Excuse me
here. Alright, and then we can pop the
temporary value off the stack. Okay, now
we have actually done subtraction. Let me
see that. There is everything, from about
here to down there is computing x minus y.
Okay... So this is computing x And this
was computing one And then this whole
thing is computing the subtraction
Alright? So now we compute the argument.
What are we going to do? Well we save it
on the stack. So now we save the result on
the stack. We're saving it into the new
activat ion record that we're building
Alright? And then we have to advance this,
or move the stack pointers as always And
now we're ready, we have to do the
function calls And now we do the jump in
the link to the entry point of sum two
Okay? And now when this returns, what it's
going to return with, it's going to return
what the result of computing the sum to in
the accumulator, all right? And so then,
we're ready to perform the addition And
now we've computed the second argument to
the addition and how do we do that? Well,
look back at the template for addition the
next thing what happens is we reload the
temporary value that we saved on the
stack. Alright and now we got actually
perform the edition. Okay? And then we
could pop the temporary value of the stack
Alright And that actually ends the, the
else branch, the false branch of the
entire if and else And there's now a
branch around the rest of the if and else
code And we'll call that label if and one
And now comes the code for the true
branch. And what we are going to put
there, well, it's not very complicated
because all we're doing true branch is
loading or generating codes for zero which
is a single load immediate, load immediate
Alright And that's the entire true branch
is [inaudible] where it is there
[inaudible] excuse me, and in fact I can
just raise that a little bit Alright And
now we're at and actually I see it notice
in the wrong place so let's fix that so
this is a branch at the end of the false
branch, at the end of the else, part of
the if and we're going to, to branch
around per quote for the two branch which
is only one instruction. And so the very
next instruction is the label end if. So
now what's left [inaudible] if and else so
now it goes here is the rest of the
template for the function definition so
now we have to generate the code returns
back to the caller and how do we do well
we have to load. The return address The on
the stack, okay? And now we pop the stacks
so we pop the entire activation record off
the stack and now because of the
activation reco rd well remember, there's
always two words. One for the return
address and one for the frame pointer and
then a number of words equals to the
number of arguments where there's only one
argument here, so we have three words, so
it's twelve bytes. So we increment the
stack pointer by twelve, all right? And
then we load the old frame pointer, we
store the frame pointer. Okay, and then we
return. So, one more instruction, we'll do
a jump register to the return address And
that is the entire code for this simple
functions sum2 And there's a couple of
things to point out. So, first of all the,
the code is constructed as a bunch of
templates pasted together and I try to
point out as we go [inaudible] how that
works But we do lined up with one linear
sequence of code. Alright and if, if
you're all confused as we work as to go
back and look at those templates and look
at this example and understand how the
code all fits together and how it works.
And the other thing I would point out is
just that this is your extremely
inefficient code so later here where we
were generating code to check whether x=0.
Notice here that we, we load x so this is
a load Of x And then we immediately store
the x again into the stacks, we just
loaded it now from the frame then we
immediately store it back in the memory
and then we and load the immediate value
then we reload the value of x here. So,
you know, moving the value of x we you
know, all around. So we load it, we store
it, we load it again and this was a lot of
wasted motion here and that's a result of
this very simple cogeneration strategy
where we want to be able to compose code
together. We will be able to compose these
templates in a way that it will work
properly. This code does not have to be
this inefficient in a lot of the
techniques of what we discussed in
sub-sequential lectures we talked about in
a smarter code generation techniques and
also optimizations like even improve the
code further.