In the next two videos, we're going to be
looking at code generation for a language
that's higher level than a simple stack
machine language we've been talking about
so far. So here's a language with integers
and integer operation and this was the
grammar. So a program consists of a list
of declarations, and what's a declaration?
A declaration is a function definition so
it has a function name, the function takes
a list of arguments which are just
identifiers, and the function has an
expression, which is the body of the
function And what in function bodies look
like, well they expressions can be
integers identifiers if then else, and the
only predicate that we're going to allow
is an equality test between integers and
then sums of expressions, differences of
expressions, and function calls. Now we'll
just say that the first function
definition in the list is the entry point.
This will be the main routine, or the
function that gets run when the program
starts And this language is expressive
enough to write a [inaudible] function And
here it is And this is just a standard
definition, if X is one then the result is
zero. If X is two, the result is one.
Otherwise it's the sum of fib of X minus
one and fib of X minus two. Now, it's a
two code generation for this language. We
need to generate code for each expression
E; we need to produce MIPS code for each
expression E that accomplishes two things.
First of all, that code is going to
compute the value of E, and leave it in
the accumulator A zero. Right? So when the
code for E is done, the value of E will be
stored in the accumulator And furthermore,
E is going to, the code for E, excuse me,
the generated code for E is going to
preserve the stack pointer and the
contents of the stack. That means whatever
the stack is when we started executing E,
or the code for E, the stack will be
exactly the same after we're done,
executing the code for E And we're going
to write a code generation function C-gen
of E that produces code. Okay? So C-gen
would be something that produces a
program. It produces code that will
accomplish these two things. Now our
co-generation function is just going to
work by cases And to begin with let's
focus on the expressions, and we're just
going to have, different kind of code or a
certain kind of code that's generated for
each kind of expression in the language.
So to evaluate an expression, which is a
just an integral constant, all we have to
do is load that constant into the
accumulator. So, the code generation for
‘I', for the constant, ‘I', is the
instruction, load immediate into the
accumulator the value of ‘I' And it's
easy to see that this preserves the stack
as required, so this doesn't modify the
stack pointer or the contents of the stack
at all, so the stack is exactly the same
before and after the execution of this
instruction. >> And another thing I want
to point out or I want to emphasize here,
is I'm going to be following a convention
that things that are in red, are things
that are done at compile time And things
that are in blue are things that are going
to be done in run time. So in this case,
at compile time we execute the function C
gen of I And that produces code. Here that
will run at run time, okay. So, C gen of
I, something that would execute a compile
time, and it produces a program that will
be executed at run time And this is to
help you separate in your mind, and, and
to develop a very, firm grip on the idea
that we have a real division of time in
these programs, There's stuff that happens
inside the compiler, and then there's
computation that's deferred until the
program that we are producing, actually
executes. All right, now let's look at
another example. Let's, let's take on the
addition of two expressions and think
about the code that gets generated for
that. So, what are we going to do? Well
the first thing that happens when we
execute E1+E2 is that we have to compute
the values of the sum expressions, we have
to know what integers we're going to add.
So we better generate code for E1. And
that's going to happen at com pile time.
We're definitely going to generate that
code at compile time. And then, once we've
got the value of E1, well, remember we
only have one, register stack machine, so
we're going to have to save that value
somewhere until we also know the value of
E2 and where we're going to put it. We'll
do what we always do; we'll put it on a
stack. So, E1 The, the, the code for E1 is
guaranteed to leave the value of E1 and
the accumulator. So what we're going to
store the value of E1 onto the stack. And
we know how to do that. We store A0 onto
the stack, and then we have to bump the
stack pointer. >> And then we can generate
code for E2. Okay and again, this stuff in
blue is a part of the program that will be
executed at, at run time. These are calls
to the co-generator that are happening at
compile time. And so we generate the code
for E2, and then that goes here after this
code for pushing the value of E1 on the
stack And once we have the value for E2,
now we can perform the add, So how do we
do that? Well, first we retrieve the value
of E1. So we load the value of E1 Which is
on the stack. And notice that. This works
because E2 is guaranteed the code for E2
is guaranteed to preserve the stack. You
know this code for E2 here, and let me
digress for a moment; this code for E2 can
be arbitrarily complicated. This could be
a whole program. It could go call
functions. It could allocate data
structures. It could print things out. It
could do all kinds of complicated things
But because we have this invariant that
all code generation for all expressions
will preserve the stack, we know that no
matter how complicated this is and how
long it takes. When it's done executing,
the stack will be in the same state. And
that's what allows us to know. Where to
find the value of E1 that we stored away
It's going to be at the top of the stack,
Okay, so we load the value B one back into
a temporary register, now we can do the
add Okay, so we add T1 and A0 together,
and store that back in the accumulator And
now we have to pop the stack And now
notice that this is all the code, here,
for E1+E2, and when we're done, we've,
established our the value of E1+E2 is in
the accumulator. That was established by
this instruction. And this pop here
restores the state of the stacks. Now, the
state of the stacks here is exactly what
it was when we entered this block of code
up here. Now to be completely precise I
really should write this code generation
function out a slightly different way And
that would be like this. So what we're
really doing here is we are generating
code for E1 and then we're printing out
into a file or something like that the
code to do the push. Okay, and then we
generate the code for U2 And now, these
calls, the code generation, are also
printing in to the same file, okay. So,
here [inaudible], they just printed out
the instructions, whatever the
instructions are, like security one, this
is printing out the code to execute, to do
the push. You print out the code to do U2
And then, we print out the code to do the
ad and the pop Fence. Yes, The add and the
pop. Okay, and this is just a, this is
much more verbose over here, and so I'm
trying to go in and leave out the prints
and just indicate in blue the instructions
that are deferred, but I hope you
understand what this means. Everything in
red here, of course is being done in
compile time so you know, we're calling
these co-generation functions a compile
time. The print statements are being
executed in compile time and then we're
accumulating somewhere in some data
structure or in a file, all the
instructions that will be executed at run
time. So let's think about a possible
optimization to this code. Instead of
pushing the result of E1 on the stack,
what if we stored the result of E1 in a
temporary register T1. What would the code
for that look like? >> Well in that world,
to generate code for E1 plus E2, what
would we do? We'd generate code for E1 and
that would be followed now by instead of
pushing the result on the stack, we would
take the result of E1, which of course is
in the accumul ator A0, we would store it
in a temporary register And then we would
generate code for E2. Alright, that we
followed by the code for E2, and then we
could just do the add. We would, take the
result of E2, which is in the accumulator
A0, add it to the contents of T1, and
store that into the accumulator A0, and of
course there's no pushing and popping from
the stack here, so this code preserves the
stack, and it looks like, anyway, that it
actually puts the value of E1 plus E2,
into, the accumulator. Unfortunately, this
code is incorrect, so this is actually
wrong, and you don't want to do this And
to see why, let's consider what would
happen. If, E2 Was itself the actually,
let's do it for a concrete example. Let's
do the example one plus two Plus three
Parenthesize like that, okay. So what's
going to happen, so E1 here, so we're
doing one plus two plus three. So this
will be a load immediate, the first, the
code for E1 will be a load immediate into
A0 of the number one. Okay, and then we'll
have the move. We'll try to save that
value I, in, temporary register T1. And
now we're going to generate code for E2.
And what's E2? Well, E2 is itself, a plus
expression. So we're going to recursively
call the code generator to generate code
for two+3. So we generate code for the new
first, expression. So that will be a
[inaudible] immediate, into A0 of the
value two And now you should be able to
see what's going to go wrong, because. >>
Since this uses the same co-generation
strategy, it's also going to try to use
T-1 to hold the temporary value. So it's
going to move the accumulator into T-1,
thereby clobbering the value of the
previous self expression that we had
evaluated, the number one. Okay, so that
value's going to be overwritten and then
we're going to do and add And oops I may
have made a mistake, we're not going to do
an ad, let me erase that Forgot to
generate the code for the three, so now we
load the value of three. I, in to the
accumulator And now we can do the add, now
comes the add And so we do A0 T1 A0 and
when you execute this what do you get. You
get two + three which is five and that's
fine but now, Now we have the value of
this sub expression. In the accumulator
and now ready to do the outer add. So that
generates another add instruction. Which
is exactly the same But unfortunately, the
first value of T1, the first temporary we
tried to restore has been overwritten And
so what's in that, what's in T1 at this
point is the value two, instead of the
value one, and we get that one+2+3=7.
Which is not what we wanted And so the
problem here of course is that in the
presence of nested expressions, and
particularly nested expressions of the
same kind, if the expressions try to use a
fixed [inaudible] for their temporary
values, then if you try to generate a code
for two different expressions that are
[inaudible], sorry two expressions of the
same kind that are nested beside each
other, they will step on each other's
temporary intermediate results And so
that's why we have to use a stack to store
intermediate values. So this example
illustrates a couple of features of code
generation that I just want to emphasize.
First of all, notice that the code for
plus is really a template that has holes
in it for the code, for evaluating E1, E2,
that is there are some fixed instructions,
that we admit And then there are places
where we plug in the code for E one and
the code for E two, okay, so that's what I
mean by a template, so there's some fixed
stuff which are the instructions that
actually do the ad, and then there's a
place where we can just plug directly in,
arbitrary code, whatever it is for
implementing E one and E two, and we'll
see the same pattern with all the other
kinds of expressions. The other important
point is that stack machine code,
generation is recursive. That is you know
the code for E1 plus E2 is code for E1 and
E2 glued together and recursively
regenerate code E1 and E2 which will have
their own templates and may even be other
expressions of the same kind as we just
saw And what this means is that code
generation can be written as a recursive
descent of the abstract syntax tree, at
least for the expressions. Alright so
let's consider another new instruction.
Let's add the subtraction instruction And
this is just like addition instruction so
sub just subtraction to register instead
of adding them. And code generation then
for subtraction expression as you might
imagine look and awful like code
generation for a plus expression. So what
do we have first we have a place where we
plug in the code for E1. >> Then we have
to store the value of E1 on the stack. We
have to remember that intermediate result
And then we can go off and compute the
value of E2. So this is where the code for
E2 gets plugged in And then at the end, we
load the value of E1 back into a temporary
register. I actually do the operation, the
subtraction, and then pop the stack And
the thing to do note about this code is
that it's exactly the same as the code for
addition except for this instruction right
here where we do a subtraction instead of
an add. So next we're going to talk about
code generation for if then else
expressions And to do that we're going to
need some control flow instructions. So
we'll have, we'll need two in fact. So
here's the branch equal instruction, and
this jumps to a label if the contents of
two registers are equal And then we'll
also need an unconditional jump. So this
just does an unconditional branch, not
branch, an unconditional jump to a
particular assembly instruction. So let's
look at the code generation for the
expression if E1 is equal to E2 then
evaluate three otherwise evaluate four. So
first we have to evaluate the predicate
and in order to evaluate the predicate, we
first have to evaluate E1. And by now this
pattern for binary operation should be
familiar. So we evaluate the first
sub-expression we save the result on a
stack, so we push it on to the stack. It
takes two operations, one to save the
result of the cumulate on the stack and
the other cumulate stack later. Then we
evaluate E2. Now we have evaluate d both
of the arguments to the predicate. The
result of E2 is in the accumulator and the
result of E1 is at the top of the stack
because again, the evaluation of E2 will
preserve the stack. So now we load the
value of E One back into a temporary
register. And we pop the stack And then we
can actually do the comparison. So now we
do a branch equal. So if the value of E
One is equal. Sorry this is actually the
value of E Two and E Zero and if that's
equal to the value of E One. Then we
branch to the true branch. Otherwise we're
going to fall through if there not equal.
Okay And so we'll call that the false
branch And what are we going to do if we
fall through, if this test fails, well
then we want to evaluate E4. And that will
leave the value of E4 in the accumulator
and that will be the value of the entire
[inaudible] in the case where the
predacious falls. So when we're done,
we're going to branch now to some code
that we'll just clean up and end the if
statement. We'll see what that does in a
moment. Otherwise, we still need to
implement the true branch, so we'll stick
the label for the true branch here And
what do we do on the [inaudible]? We just
evaluate E3. Okay And then the and if,
Well, actually, there is no cleanup to do
Because, E3 and E4 both preserve the
stack, and they leave the result of their
expressions of the accumulator. So we
reach and if, from E3 if we executed the
true branch And then, in which case, the
value in the accumulator is the value of
E3 And we reach and if, through this
branch if we executed the false branch And
then the value in the accumulator is the
value of E4 And so this correctly
implements an if then else expression.