Code Generation - Compiler Design, Computer Science & Engineering Video Lecture - Computer Science Engineering (CSE)

welcome to the lecture on code
generation we covered a little bit of
this material in the last class we
looked at the main issues involved in
code generation for example
transformation what exactly is code
generation which instructions to
generate what are the consequences of
that in which order should we generate
the code and then which registers to use
should be optimized for memory time or
power etcetera so is the code generator
you know target retarget able to other
machines these are some of the issues
that we looked at we also saw some
samples of generated code for example
for the assignment V equal to AI a XJ
equal to Y X equal to star P star Q
equal to Y and then branch instruction
etcetera we will continue that
discussion today so let us look at the
generated code for you know function
calls etcetera first of all in the case
where we have static allocation and then
we look at the case where there is
dynamic allocation even with static
allocation let us assume that there is
no jump subroutine instruction to begin
with and then we will see the minor
modification needed when there is a jump
subroutine instruction available the
three address code for the function f 1
and function f 2 will probably look like
this so let us assume that function f 1
is the main program itself and function
f 2 is the subroutine so there is action
code segment 1 and then there is a call
to the function f 2 and then action code
segment 2
and then there is heart so these action
code segments are some code computations
within the function f1 to achieve the
meaningful length and result so in what
function f2 we just have action code
segment three and then there is a return
let us first look at the activation
record for the function f1 it size is 48
bytes so to begin with you know the
activation record will have for example
you know the static link dynamic link
information which we already have
studied discussed so I am omitting the
static link dynamic link information in
this particular activation record to
make the presentation simpler there is a
return address field then there are
local parameters function f1 you know
does not have any parameters within
local variables as I said sorry local
parameters function f 1 does not have
parameters passed to it whereas function
f 2 has a parameter passed to it so
there are local variables for example
data array a then there is a variable X
another variable Y so the total size of
this activation record is 48 bytes and
since this is static allocation the
activation record is allocated just once
and there is no recursion possible
activation record for the function f2 is
76 bytes in size to begin with there is
return address then there is space for
parameter 1 then there is an array B and
another variable M so what would be the
code that is generated for such a set of
functions so here is the code for
function f 1 then we have code for
function f 2 and finally we have the
activation record format for F 1 and
activation record format for f2 in the
activation record let us look at this
first for f1 it runs from 6 address 600
to address 647 and then the first
location as we saw previously contains
the return address and then the second
location onwards there is low K a space
for the local variable a which is an
array then at 640 we have the space for
variable X and at 6:44 we have the
variable Y the activation record for F 2
hazard is runs from 648 to 723 it is
address 648 we have the return address
stored in it at 6:52 we have the
parameter 1 and then at 6:56 onwards you
know we have the array B and set 720 we
have the variable M so this is the
layout of f1 and if the activation
records of f1 and f2 code for function
f1 it starts at 200 and the code for
function f2 starts at 400 so action code
segment 1 starts at 200 you know it runs
till 240 some computation which is
meaningful now at the address 240 we
have a move instruction move hash 264 to
address 648 this instruction achieves
storing the return address on to this
particular slot so the reason we are
doing it is there is no jump subroutine
instruction so we need to return the
store the return address explicitly and
then jump to it
once the function f2 is over so there is
a parameter to the call f2
so at 252 we have a move param one 652
which moves the some parameter you know
variable let us say 1 2 652 and then
it's 256 we have jump 4
which is actually a jump to the address
400 so note that this hash 264 is
nothing but the address of action code
segment to 264 is the address of this so
that is the return address which is
being stored at 6:48 so at location 400
which corresponds to function f2 we have
action code segment 3 and then you know
a tag at it the code is regulating 440
and then jump at 648 is an indirect jump
instruction which takes the contents of
648 and treats that as an address and
jumps to that particular address
so the 648 correctly current contains
this 264 and therefore once the jump is
completed the action code segment 2
continues and then finally function f1
halts so this is the way the code would
be for function call with the parameter
and no jump subroutine is function here
is the slight change in the activation
record format when we do not have we do
have a jump subroutine instruction and
for simplicity since we have already
studied how to pass parameters I have
omitted the parameter here as well
to say please observe that there is no
return address here ok and here you do
not have that we had it in the previous
activation record format rest of it
remains the same so the size of the
activation record has slightly you know
reduced okay so let us see what happens
in the code so the activation record for
F 1 now runs from 600 to 643 so we do
not have the return address otherwise
everything else remains the same okay we
do not have the parameter either in this
particular case so there is no space for
the parameter either here we execute the
action code segment 1 in function f 1
now there is a jump subroutine
instruction the jump subroutine
instruction uses
great hardware stack to store the
address the return address so there is
no need to store you know the return
address explicitly so jsr 400
automatically stores the return address
on its stack hardware stack and jumps to
that is 400 here we execute the function
of action for segment 3 in function f2
and a return instruction automatically
takes the return address from the
hardware stack and returns to the
address 248 which is the return address
then it continues so this is the minor
difference we would have when there is a
jump subroutine instruction so let us
see how the code changes when we have
dynamic allocation and again with no jsr
in this case again we have omitted the
parameter because there is not too much
difference when we have parameters we
have seen what happens already but here
the allocation is dynamic so we can have
recursion so function f1 has action code
segment 1 then a call to the function f2
action code segment 2 and then let us
say a return so we have called this from
the main program code for function f to
contains action code segment 3 then a
recursive call to function f1 C call f2
f2 and call to f1 again action code
segment 4 and then a recursive call to
f2 itself again and action code segment
5 finally return so let us see here
there is a return address and then local
data and other information return
address and local returned information
please observe that the size of the
activation record is 68 bytes here and
96 bytes here there is no jump
subroutine instruction so there is some
initialization for the stack pointer
saying that from 800 onwards the stack
begins ok and then let us look at the
code for the function f1 so there is
action code segment 1 till from 200 to
230 and then we have you know we have to
create the
activation record so which is done
actually we are assuming that the
activation record is created on the
stack itself so it is a stack managed
activation record not a heap managed
activation record 96 the size of the
stack the activation record is added to
SP thereby allocating the space for this
particular activation record for the
call to the function so function f2 that
is then we move the return address which
is 2 5 4 right at SP indirectly so the
first location of the activation record
now contains you know a return address
after this instruction is executed once
and then jump 300 so we come here this
is the code for f2 so within this we
execute action code segment 3 now there
is a recursive call so two function f1
so we add the size of the activation
record to SP thereby creating another
activation record for the function call
f1 and then the return address is moved
to the first location of this particular
activation record and finally you know
we jump to 200 so we come here
so this executes again and again it
keeps going finally once we return from
the you know function so let us see how
it that is done so we subtract 68 from
the stack pointer thereby the activation
record is destroyed action code 4 is
executed now there is another recursive
call so we add 96 to SP return address
store and jump to 300 so this is another
recursive call once that recursive call
is completed we come out and we subtract
the size of the activation record
thereby destroying it and execute the
action code segment 5 and jump at SP
automatically
returns by taking the return address
from the first location of the stack in
activation record on the stack the same
thing happens here once we return here
we come here
we say you know subtract 96 which is the
size of the activation record execute
the action code segment 2 and jump wait
SP takes the return address and returns
to the main program with jump subroutine
instruction the only change is there is
no return address here so the activation
records are smaller the code is also
much simpler the initialization remains
and then you know the activation record
is created we move there is a there is a
parameter which is permitted here in the
jump with along with jump subroutine so
we move the parameter to that particular
location and execute a jsr which stores
the return address on the hardware stack
then you know once it is completed we
come out deduct the size of the
activation record so this destroys the
activation record execute the code
segment 2 and return this is very
similar there is not much change every
time we add the size of the activation
record and jump subroutine once you come
out of the subroutine we subtract the
size of the activation record thereby we
added a you know destroy the activation
record and so on and so forth so this is
a fairly straightforward job so now we
have seen many examples of what type of
code is generated for function calls and
other statements so now it is time to
discuss how exactly code is generated so
what this says is it says treat each
quadruple as a macro so this is the
first scheme an example is here let us
say the quadruple is a equal to B plus C
ok so we generate extremely simple code
so we load this b2r one let us this is
one possible core sequence the other
possible code sequence load C to the
register r2 and r2 to r1 and finally
store r1 to a otherwise we say load B to
R 1 and R add r1 to this Robin I had C
comma r1 and then finally store r1 to a
this is add C comma r1 the purpose of
for such a macro is to make the code
generation macros self-contained
complete so observe that the registers
which are used for storing B and C here
will be released at the end of this
particular macro they are not going to
contain any meaningful values later on
that is the assumption so if we do this
load store sequence you know for every
quadruple automatically the code will be
very inefficient but it is very easy to
implement it for each type of
instruction we write a macro and you
know expand that macro for the sequence
of quadruples that is all nothing more
than that is needed so repeated load
store of registers takes place here so
for example we are not going to we are
going storing r1 in a and we are not
using the value of a which is in r1
later on we will load a into r1 all over
again if even if the next instruction is
like X equal to a plus y so this is very
simple to implement but definitely there
is a lot more chance to improve it
scheme B scheme be slightly more
complicated so it tries to track values
which are available in registers and
then it tries to reuse them so if any
operand is already in a register then
take advantage of it
is the basic idea but how to take
advantage of it it is done using two
data structures called register
descriptors and address descriptors so
two of them the register descriptor
tracks register variable name pairs so
in other words for each register it
tells you which are the variables which
correspond to that value in the register
but then the question will be how can I
register hold the values of many names
this is possible because a single
register can contain multiple names if
they are all copies of each other so let
us say you know we have computed a equal
to X plus 5 so the value of a is now
available in some register r1 then we
write B equal to you know B equal to a
or C equal to a or m equal to a and so
on so BC indium all these variables now
contain the same value of a but we do
not have to allocate different registers
for them so we just track that they all
contain they are all corresponding to
the same value using this register
descriptor what is an address descriptor
it tracks variable name and location
pairs so for each variable name it
stores the locations where that value is
present for example a single name may
have its value in multiple locations
such as memory register and say if it is
stack machine then on the stack also so
in such a case depending on the occasion
we may actually want to avoid storing
rather loading a particular value from
memory to a register if it is available
both in memory and register so we will
see this a little later
and then the computed result is left in
a register as long as possible so unless
the register is useful for some other
work we are not going to
the register so thereby we probably
avoid repeated loads we store only at
the end of a basic block unless we are
compelled to do otherwise
or when that register is needed for
another computation so on exit from a
basic block store only live variables
which are not in their memory locations
already so this as I said can be found
out very easily using the address
descriptor so live variables are those
which will be useful even after the
basic block is completed so in the next
basic block normally programmer defined
variables are normally live even after
the basic block is completed
whereas temporary variables have their
scope within the basic block if live
this information is for example not
available at all what do we do we cannot
stop code generation so we assume that
all the variables are live at all times
so thereby at the end of a basic block
we need to store a very variable into
their home memory location so let us
look at an example and understand how
this scheme B works and then go on to
the scheme itself say the quadruple is
equal to B plus C if B and C are in
registers r1 and r2 then generated r2
kamar 1 the cost of this is 1 and the
result is in r1 but this is legal only
if B is not live after the statement
because we are destroying B so B is in
r1 and after this instruction is
executed
we will not contain we will not be nor 1
it is the value B plus C that is y a
which will be in R 1 this is one
possible alternative the other
alternative is if for one contains B but
C is in memory so then generate add C
comma r1 cost is 2 because we need to
fetch from the memory location C also
and the result is in r1
one more possibility is you load C into
R 2 and then add R 2 to R 1 this cost is
3 because you are loading this also into
R 2 and then adding it so the result is
in R 1 this is legal only if B is not
right after the statement again the same
issue both these are the same you know B
is destroyed and it is attractive if the
value of C is subsequently used so in
both cases if we are going to use C
later on then we can take it from R 2
and we do not have to load it into R 2
all over again
so that is how there are there many
options available during code generation
regarding availability or otherwise of a
variable in memory or in register is
tackled to do that and then to usefully
retain only those values which are used
later in registers we use some
information called next use information
it is used in code generation and also
resist location in scheme B what is next
use so for example consider quadruple I
and quadruple J the control flows from
my 2j with no assignments to the
variable a which is defined here there
is an assignment to a and then there is
a usage of a in between there are no
other assignments to a so the value of a
here is valid here also so the next use
of this a inquire I is J if this is true
so in computing the next use we assume
that on exit from the basic block all
temporaries are considered non-life so
they are not useful anymore all
programmer defined variables and non
temporaries are live this is the
assumption that we make if this is not
true then you know we will have
to assume that all temporaries are all
variables are non line each procedure
function call is assumed to start a new
basic block so there are no interactions
from the procedure call inside the basic
block itself it is a PI it becomes a
separate basic block and it can be
handled in a much better fashion next
use is computed on a backward scan from
on the quadruples in a basic block
starting from the end so we will see an
example of this now and excuse
information is stored in the symbol
table itself here is an example of how
to compute next use so here nlv means
not life LV means live Lu means last use
a new means next use so let us start
from the bottom and see how the
algorithm computes an excuse information
this is the last quadruple of the basic
block so there is no more usage of the
variable I or any other variable for
that matter after this basic block so
for I it is a programmer defined
variable so it is recorded as live and
then the current quadruple number in
which it is used is recorded as last use
so that is 11 and there is no an excuse
because this is the last quadruple after
which there are no usages of any
variables with this information we go to
quadruple 10 so here is I equal to I
plus 1 again so I is live always so
remember that I and prod are programmer
defined variables so they are always
live last use of this I is 10 because I
is used here and this is the quadruple
so and then next use of I is in 11
because the value defined here is used
in 11 so what we really have done is use
this last use information to be recorded
as next
information for the previous quadruple
that is how the last use is used prod is
a different variable so none of this
holds now it is always live its next
last use is 9 the current quadruple
number and there is no next use because
there is no usage of prod anywhere after
this and this was the initialization to
the variable and determines as it is t6
is a temporary so it is always not live
after the basic block its last use is 9
and there is known excuse for it because
it is not referred to anywhere here as
far as the initialization is concerned
it would have been initialized to n nu
and it continues to be in nu when we
come to quadruple number 843 and t5
there is known excuse because this is
the first time that we have used it and
the current quadruple numbers are
recorded as 8 in 846 it is the last use
is recorded as 0 indicating that this is
a definition so a definition always
terminates that live range so even if
there were to be any usages of 46 here
all those are not going to be the same
t6 it is redefined here so it is apt to
say that the there is no last use that
is last use is 0 so once we go up to t5
this information about t5 which is
already in the symbol table for example
it had recorded not live like use last
use 8 and in the new so this lu8 is
copied to you know so this nu for
example t5 becomes next use 8 right so
whatever was here is copied here lu is 0
because it is a definition and as far as
t4 is concerned it is not used again so
we still do not have anything here which
is useful 44 in quadruple number 6 we
are copying lu 7 to nu and this
continues you know 43 4 at t2 t1 for
example t2 and t1
nothing whereas once we have t1 let us
look at this t1 itself so we had T 1
here which recorded in U as 7 and then
you know so the last use has 5 so Lu 5
here is copied to next use 5 here and I
is always recorded as live finally the
last use is 3 and nu is 10 from this
quadruple we had recorded Lu as 10 now
this is recorded as 10 so in the
backward scan we can compute this next
use information using the last use
information how do we use this
so we now begin the discussion of the
algorithm itself with this algorithm
deals with one basic block at one time
and we assume that there is no global
register location in this there is a
local register location which is the
gate reg okay function which we are
going to discuss very soon for each
quadruple EA equal to V of C we do the
following find a location L to perform
the computation v op C so that is it is
not necessarily always a register but
most often a register is returned by
gate right so this L is obtained by our
gate wreck we will see very soon how but
it could be a memory location normally
it is not where is B so let us say the
location of B prime B of V is V prime
and it is found using the address
descriptor for B that is what it is went
for address descriptor stelu for each
variable where exactly it is located so
if it is available in register and
memory
let us prefer the register say B prime
is a register now if it is not a
register ok generate lower B prime comma
L so sorry if L does not contain the you
know B Prime and L are not the same then
we generate an instruction called load B
prime comma
l to move the value from B prime to L if
B Prime and L are the same there is no
need for this particular instruction
very C located it is in C Prime and
again we find it using the address L
scripta now generate the instruction of
c prime comma L so once all this is done
you know we have to update the
descriptors for lnj so you know now L
contains the result so we have to you
know and it actually stands for the
value top supposed to be contained in a
so the L is a register we need to modify
the register descriptor for L and
similarly if it is whatever a is that s
descriptor for ei will have to be
modified to mention where exactly its
value is contained by the register or a
memory location etcetera if B and C have
known excuses then update the
descriptors to reflect this information
so this is one place where next use is
used so that means from now onwards B
and C need not be in the registers their
registers can be used for some other
purpose that is what this really means
what does the function get right do it
finds a locational for computing the B
of C so in other words computing a there
are four steps here first one says if B
is in the register say R and R holds no
other names okay so the address acceptor
tells you what are the other names
corresponding to this R and then B also
has no next use so it is not useful
anymore this is the last place where B
is used B is not live after the block so
we do not have to bother to storing C if
it is live then we have to store it into
its memory location we cannot destroy
the value now then return R so if all
these conditions are satisfied B is in a
register it corresponds to only one name
it has no next use and it is not live
after the basic block then return our if
this is not possible failing one return
an empty register if it is available
so if empty registers are also not
available then if a has an excuse in the
block so that is a is useful later on or
if B op C needs a register compulsorily
for example in indexing operations a
register is essential so if R P is an
indexing operator then somehow we will
have to free a register so how do we
free registers so we must use a
heuristic to find an occupied register
and then empty the contents of that
register into its home location and
release that register so how do you find
an occupied register there are many
heuristics possible so for example the
register whose contents for reference
farthest in future so if it is used
immediately in the next instruction it
is not a good idea to empty that
register and release it but if it is
used five or six instructions of a
perhaps by the time we reach there some
other register would be free and
therefore we can load that into the
register you know the value can be
loaded into a register all over again on
the number of next uses is the smallest
so look at the next uses of you know
each register the value in the register
so take one which is used very few times
that may be cost wise the best because
if it is used very small number of times
we do not we have to really load that
value into a register only a few times
but if you choose a register which is
used very large number of times or the
value is used very large number of times
we will have to load it into a register
every time so this is the issue behind
the heuristic so now we have a register
you have to spill it by generating an
instruction move
, mem so mem is the memory location for
the variable in the register R so we can
get this information you know from the
register descriptor and that variable is
not already in mem so this address crip
descriptor will tell you whether mem
already contains the updated value or it
does not once it is done you know we
probably generate the instruction and
update the register and descriptor
address descriptors because now the
situation has changed the registers do
not hold the value they are supposed to
hold they have been released so if a is
not used in the block or no suitable
register can be found only then return a
memory location for L so this is what I
was saying it is not compulsory for L to
be a register it can be a memory
location but that is the last resort so
let us look at a simple example to
understand the code generation process T
U and V are temporaries they are not
live at the end of the block so there is
no need to store them at the end of the
block W is a non temporary and it is
live at the end of the block so we have
to store it into its home location after
the block is completed and let us assume
there are two registers first this
statement is T equal to a star B to
begin with the basic block the first
instruction is this so all the registers
are free none of them contain any values
so gate rec will return r0 for a so we
load a into r0 get req will similarly
get you know we do not need another
register for B because we do not call
get reg a second time Eric would have
returned the location for a which is our
zero so now up become R 0 is multicom
our zeros when the result now goes into
R 0 so R 0 now contains T that is the
register descriptor content and a desk
says T is in r0 so now you equal to a
plus C so remember that the r0 which is
actually the value of a is now destroyed
it now contains the value of T that is a
star B so this is because our generation
scheme is a very simple scheme it does
not see whether there are many uses of
the same variable a on the right-hand
side it only checks if this T is used
later okay so u equal to a plus C we
load a into another register r1 which is
free add C to it so now r0 contains T r1
contains you are the contents of the
register descriptor T in r0 you in r1
are the contents of address descriptor
so when we look at V equal to t minus u
immediately the you know get rec
function knows that T is contained in
the register using this descriptors so
it is in R 0 U is in r1 this is
immediately found out and it also sees
that T is not used later on so it is
okay to destroy it so it simply emits a
single instruction sub r1 comma r0 from
now on r0 contains V in r1 contains you
for the instruction W equal to V Star
you it emits the instruction mult
r1 comma r0 because it is okay to
destroy V after this instruction and
finally once the basic block is
completed the value of W which is in r0
is stored back into its memory location
W this is a memory is restored and code
generation is complete for this
particular block now we start looking at
another scheme of code generation so far
we saw a model in which code generation
is not guaranteed to be optimal or
otherwise there was no result which said
anything about
code generation strategy set human
algorithm is one of the algorithms which
is guaranteed to generate optimal code
for a certain type of machine model so
for example look at you know the cost
model the cost model says it generates
the shortest sequence of instructions so
cost is the sequence the length of that
particular sequence itself and it is
possible to prove that this you know
with respect to the length of the
sequence that this is an optimal
algorithm in other words the code which
is generated by this algorithm is the
shortest in length no other code can be
shorter than this no scheme can give you
shorter than this and it is useful for
only expression trees so this is a
slight disadvantage because you cannot
generate optimal code for directed
acyclic graphs
unfortunately that problem is
np-complete so there is nothing we can
do so we have to actually represent
basic blocks as trees instead of
directed acyclic graphs and that is
possible we will see that later the
machine model which is used here it
assumes that all computations are
carried out and registers okay there is
no computation which is directly carried
out in memory and instructions are of
the form of R comma R or up m comma R so
register and register ID does not mean
the same register it could be up our i
comma r j and RP M comma R okay so
whatever is the operation it takes one
of the operands as M but the result is
always in R it always computes the left
subtree into a register and reuses it
immediately so this is a very important
feature of this particular algorithm so
the left subtree is computed into a
register
and the result of that left subtree is
used immediately there are two phases in
this particular algorithm the first
phase is the labeling phase and the
second phase is the code generation
phase the labeling phase labels each
node of the registry with an integer so
the number that we compute tells you
what exactly is the fewest number of
registers required to evaluate the tree
with no intermediate stores to memory so
this is what the number tells you how do
we compute such a number we will see
that very soon and we are going to
consider only binary trees because all
our operators are either unary or binary
suppose the node is a leaf node in that
case if n is the leftmost child of its
parent okay
then label of n is 1 otherwise label of
n is 0 very simple left Michelle 1
otherwise 0 and for internal nodes label
is computed as the maximum of L 1 and L
2 if L 1 not equal to L 2 and it is L 1
plus 1 if u L 1 equal to L 2 so let us
look at an example and understand this
process better so we start with the
leaves this is the leftmost child of its
parent so this is 1 this is the second
one the right one so this is a 0
similarly this is a 1 and this is a 0
this is a 1 and this is a 0 for the
interval node N 1 this value and this
value are not the same L 1 not equal to
L 2 so the maximum is taken and that is
1 here so here also the maximum is 1
here also the maximum is 1 now all these
three for and on all these 3 nodes have
1 so let us look at this node it has 2
children and it's numbering has
being one and one so these two values
are equal so this is numbered as 1 plus
1 that is 2 L 1 plus 1 so now n 2 n 3
and n 4 are the children of n 5 this is
true and this is 1 so they are unequal
we just take the maximum which is 2 what
does this really mean this means that
this entire expression tree can be
evaluated with no stores into memory ok
with just two registers the same is true
for this it requires two registers this
requires one registers this requires one
register and this also requires one
register so let us see how this is done
how do you use if you have just one
register then load the value of a into
that register and perform this operation
with V as the other operand the result
is also going to be in the same register
so one register is sufficient for us now
if we do not have another register this
cannot be evaluated that is the reason
what to compute this particular tree we
require two registers so we evaluate
this tree into one register we already
saw how to do that and then we are
evaluate this tree into another register
r1 so this is very similar to that
so now r0 and r1 contain the two values
of the two children and now this can be
computed into the same you know register
r0 which is the register of its left
child and now our one becomes free r0 is
held it holds the entire tree value but
r1 is free so that r1 is used for the
computation here so this is just loading
it into r1 and this does the operation
with R one and another operand from here
so now r1 contains the result of n for
r0 contains the result of this entire
tree and finally we can perform this
operation with r0 store the result also
in
our zero and release the result is a the
register r1 that is the reason why this
entire tree can be evaluated in two
registers if we had actually performed
this and then this end of suppose we had
performed this particular operation
first we had loaded into r1 then we
performed n4 so now the result is
available in r1 okay so we just have one
more register left and that is not
sufficient for the evaluation of this
particular tree so our code generation
strategy is going to be straightforward
it always sees first we compute the
numbers these main track values and then
we see which subtree at every point at
every step we see which subtree requires
more registers then generate code for
that particular subtree and then go to
the other subtree so when we co generate
code for a particular subtree say K
registers are needed for that we use you
know all the K registers compute the
result hold it in one of the registers
and release the other K minus registers
so this is our strategy so procedure
gencode with a node n which is the root
of that particular tree here we use two
data structures one is called
the register stack which is a stack of
registers r0 to our R minus 1 so there
are a little R number of registers the
stack of temporaries guy is called T
stack and this is you know there is no
limit on its length as many temporaries
as we need are available in this
particular stack so when we call gencode
n it generates code to evaluate a treaty
rotated node n into the register which
is on the top of our stack so that is a
very important thing so whenever we call
the function gencode we give it a stack
of registers and a stack of temporaries
so the stack of registers will contain
the result of this particular
three in the top most registers and all
other registers are supposed to be free
the rest of our stack remains in the
same state as the one before the call
that is free we also require a slap
operation of the top two registers of
our stack sometimes to ensure that a
node is evaluated into the same register
as its left child so these are some of
the features this last feature is needed
to prove the optimality of the code so
that is why this is also employee
important so let us look at the various
cases of this particular algorithm case
0 the there is a node n which is a leaf
node so this is case 0 so if n is a leaf
representing an operand n and is the
leftmost child of its parents so right
now we generate the code load n comma
top of our stack so so this will be some
register at runtime you know it may be
some R 0 or R 1 or whatever it is the
instruction which would be emitted would
be load n gamma that particular register
so this is the case 0 case 1 is the
right side is the right operand is a
leaf and the left operand is a subtree
so n is an interior node with operator
op left child N 1 and right child n 2 so
right child is a leaf node so so that is
if level n 2 equal to 0 that is it is a
leaf node let n be the operand for n 2
so now we generate code for n1 by
calling the routine gencode recursively
on this particular subtree once this is
completed the top of our stack will
contain the result of n1 so we generate
code op n gamma top our stripe so now
again the top of our stack will contain
the result of this entire
as well so we have restored the stack
the way it was this is case two so you
have a subtree n1 you have another
subtree and two for this particular node
n this subtree n1 requires less than R
number of registers this subtree n2
requires more than what n1 requires so
one less than label n 1 less than level
into ok so that is the order the other
order is considered in the next slide
and label n1 is less than or in other
words we require less than R number of
registers to evaluate n1 this requires a
little more than what this requires so
let us say R is 10 this requires five
this could require eight or it could
require 11 ok that does not matter in
this case we do what is known as a swap
operation on the our stack why the swap
function ensures that a node is
evaluated into the same register as its
left child this will become very clear
now so start our stack so if let us say
the top 2 or r0 and r1 now it becomes R
1 and R 0 gencode n 2 so R 1 is at the
top of stack so the result of this
entire thing you know because this
requires more registers the recursive
routine is called on n2 first this I
explained already so this 3 will
evaluate into the top of our stack which
is R 1 after the swap now pop that R 1
into the variable R at compile time
variable R now R 0 on these on the top
of stack below that is r 2 etcetera
etcetera call this routine on n1 so when
we do that r0 will now contain the
result of this particular subtree n1 now
generate the code for this entire thing
up R which is this and top of our stack
which is r0 which is corresponding to
this so this Center tree is now
available in top of our stack which is R
0
but our is outside the stack so we push
the stack into we push the are into the
our stack but then the now that is the
order is reversed our origin is at the
top and our zero is below it so we swap
the our stack the top two entries so our
zero comes to the top and it also now
holds the value of this entire tree so
thereby we have restored the
configuration the way it was now the
case number three this right child
requires less than R and this requires
more than what n2 requires okay so the
other case 1 less than or equal to label
n 2 less than or equal to level n1 and
level into less than R so obviously in
this case we do not require any swap
okay so we just generate code for n1 and
pop it so it is already r0 now is in the
variable R right it is removed from the
our stack now call gencode on n2 so that
will be evaluated into the present top
of stack say r1 now issue the
instruction up top of our stack comma R
and finally push so this should have
been a power gamma top of our stack this
is a slight error here so the assumption
is the result is the second operand so
then we push the removed register into
the stack again there by r0 now is at
the top of the stack and the
configuration is restored the last you
know case is case for both require more
than R number of registers more than or
equal to R number of registers now we
need a temporary in order to hold this
particular result so let us say
arbitrarily we gencode 4 in to take a
temporary from the stack push that
result from top of our stack to T the
temporary now you know all the registers
are available for n1 generate code for
n1 print the instruction op T comma top
of our stack thereby you know
the result of this entire tree is now
available in the top of our stack and
replace the temporary into the temporary
stack so thereby we have actually used
the entire stack of registers which is
available to us but because both these
children the sub trees require more than
our number of registers it is not
possible to generate code without
storing this particular result tea you
know gencode into generates result in
the top of our stack it cannot be
retained there you know we have to place
it in a temporary and then continue with
the operation so we will stop here this
lecture we will stop here and then next
time we will continue with examples of
the set human algorithm and also the
dynamic programming algorithm thank you
you