9
Oct

Compilers Lecture 26: Code Generation for Conditionals and Loops (2)

>>Let’s look at this example. So I have statement one, why some condition let’s
say R1 is greater than R2. Then do statement two,
then another while loop and this is R3 is
less than or equal R4. And inside of this I have
statement number three. And then I have statement four,
and then I have statement five. Now how can we generate
code for this? Remember those instructions
that compare so we need to use compare here, it’s
going to be compare greater than for the first loop and
for the other loop we are going to use compare less
than or equal. And this compare is going to
compare R1 and R2 and it’s going to put the result into some
register, let’s call it RX. And then we’re going
to generate code, we’re going to conditional
branch based on RX to N1 or N2. Okay so now let’s see. Okay so let’s now, so we
generate code for statement one, whatever that statement is. Then we have this while
loop, so we will need to generate a conditional
compare. Compare R1 and R2
and put the result. And now suppose that we have
these registers allocated already, R1, R2,
R3, R4 and you have that get next register function
so it’s going to give you R5. Okay so it’s going to give
you register R5 for this. And R5 is going to have
the result, so we are going to do conditional branch on
R5 to conditional branching to if it’s correct,
then we will go to the let’s call it L1
underscore B. So B stands for the body of the loop. By the way this is the format
that I want you to use. So if it’s correct we’ll go
to L1 or let’s do it L1 B, otherwise we go to L1 out. So L1 B loop by L1 O out
of the loop, loop out. And L1 C the checking
our loop condition. So in fact we need to introduce
a label for the compare because inside the loop
we want to jump to this. So we’re going to jump
to L1 C for compare, so this is the label and
this is the loop body. The loop body is going
to have in it what? Statement two. And this is the loop one out. So what should we put here?>>Statement five.>>Statement five yeah, statement five is the first
instruction after the loop. So loop out is the first
instruction after the loop. Okay so this is statement
two, then what should we do? Generate code for this. So you will code that same
function, recursively call that function that
generates code for a while. And the code for the while is
going to be conditional branch, sorry compare R3 and R4. Put the result in the
next register which is R6. And conditional branch
based on R6 to L1 B or L1 O. So B for body, O for out. The same thing I will have.>>Isn’t it supposed to be L2?>>Yeah, sorry. Thank you, yes L2 because
this a different loop, thank you very much. Yes. Now we will have to do
the same thing right for — well maybe we should have
completed the generation for the outer loop. So what remains in the
generation of the outer loop, in the code generation
for the outer loop? What are we missing in
the code generation, forget about the loop body? So this is the body of the
outer loop, what are we missing in the code generation
for the outer loop?>>Right before L1 out we have to have it jump to
go back to L1 C.>>Yeah, exactly, exactly. So we need this jump immediate
to L1 C because this is the end of the outer loop,
one is the outer loop and two is the inner loop. So we’ll do the same
thing for the inner loop. Now the out for this
loop is going to be — what will be the
out for this loop? Which statement will
be the out for the — out for the inner loop?>>Statement four.>>Yeah, exactly. So it’s going to be.>>Yeah, statement four
right before the jump.>>Oh okay so now I discovered
something else that I missed. Yeah, it’s statement
four that’s true. So it’s statement four
is going to be L2 out, this is statement four. I just missed what kind of compare this is,
so this is compare.>>Greater than.>>This is compare greater than
and this is compare less than or equal, I missed this. Okay so now this is and similarly we need
a jump immediate. Jump immediate L2 C. Okay so this is basically the
body of the inner loop. Now the body of the
inner loop starts with, in fact it has only one
statement in it so it’s going to be L2 body, L2 body
will have statement three. And then jump immediate
to the condition okay. What are we missing? What are — there’s
something missing, I can see at least
one thing missing?>>We do need the label
for the inner loop compare.>>Okay yes.>>That should be right
there with the [inaudible].>>Yeah, so here we
have L2 condition. Okay so each loop will
have three labels, one label for the condition,
one label for the body, and one label for the out, the first instruction
after the loop. Okay so are we missing
anything here? Okay so let’s make sure that
we are not missing anything. So statement one is there,
outside all the loops. Inside the loop we
have statement two. And then the while loop and inside the inner while
loop we have the body of the loop consists of this. And then jump immediate, let
me put the jump immediate here. And then statement four
is the output or the out of the inner loop. Then I need a jump
immediate for the outer loop. And then I will need the — yeah, the out statement
for the outer. Okay so how many people
have already written this? How many people have
already implemented this, implemented the code
that generates this?>>Not yet.>>Okay so this is an important
part of the assignment. And remember that this
is recursive so you have to have this function for generating you
know systematically for each loop generating
these three labels. And remember this is based on the abstract syntax
three, so you have a while. And the while will be
in a statement list, so this while will be
in a statement list. So in this case, [inaudible]
like this let’s put it this way. Statement one while and then
what comes after the while in the statement list?>>Statement five.>>Statement five exactly. So in the statement list if you have a next
pointer for every node. Okay the next of the while is
going to be statement five. But where are you
going to have this? So where will you
have the inner loop?>>It will be hanging
off that while there.>>Yeah.>>It’ll be.>>Exactly. So the while will have, it
will have an [inaudible]. So let’s make it a funny node. [ Laughter ] Okay so there is a next,
the next point to ST5. And then there is the —
it will have that condition and it will have the body. So each while loop, so this
is the abstract syntax there, there is a condition and
there is a body of the loop. And the condition
may have a whole in the assignment it’s not
going to be as simple as this, in the assignment it can
be an arbitrarily long and complex logical expression. So again this can have
a whole tree below it because this can be
an arbitrarily long and complex logical expression. And this body is what?>>Another statement list.>>Yeah, a list of statements. So this is going to be
another statement list and this statement list is
going to have statement two. And in the list after statement
you’ll have another while and after the while you
have statement four. So this is the other list. And this while will have a next
and it will have a condition. And it will have a body. And then the body of this inner
while will have only statement in it which is statement three. Okay so basically you know
these are two conceptually, the next pointer is a
conceptually different pointer than these pointers to what
constitutes the while loop. So these two pointers are the
pointers to the two components that constitute the while loop. A while loop consists of
a condition and a body. This is not — this is
a different concept; this is important to what
comes after it in the list of statements that
it belongs to. And you know it depends
on how you program it but if you are programming this
in an object-oriented language, for example in C++ then
this next pointer — well logically in fact
conceptually this next pointer should not belong to the
while node, it should belong to the you know while
node in particular. It should belong to any
node, any list element. So for every list element, so while as a list
element it will have to have a next —
have a list element. But while as a while it
has a condition and a body. How you implement this? Well the easiest
way is to put all of these possible pointers
instead inside of the AST node. So you can make this AST
node [inaudible] or structure and you can put everything
in it. This would be the easiest but it will not be the most
elegant way of structuring this. So the ST node you just put
into it a condition, a body, a [inaudible] for the
if statement and else if this node isn’t, and a next. From and you don’t have to do,
you know, an elegant object or [inaudible] design
in this assignment, but ideally you would like to — an AST node should
have only the elements that belong to all nodes. And you derive from the ST
node, you derive a while node. So you derive a base you
derive a derived class for a while node. And the while node will have in
it you know body and condition. And an if node will have
whatever is specific to the if node, which is a condition
and a list of statements for the [inaudible] part. And the list of statements
for the else part. And an add node will have
its different structure, the different fields. So for the add you will have to have the left-hand
side expression or expression one
and expression two. Whatever. So yeah,
so ideally you would like to have a derived
class for each node type that has the fields that
are specific to this type. But if you put everything
in one you know generic code that will work, it’s
fine, it will work fine. Even though I want you to
understand that this is not, you know, the best
way of designing this. This want to be elegant
design but it will still work and may simplify things. And we are writing
this in C anyway.