Local Optimizations-Part 2 and Code Generation - Compiler Design Video Lecture - Computer Science Engineering (CSE)

welcome to part two of the lecture on
local optimizations in the last lecture
we learned about basic blocks control
flow graphs a few of you know the
optimizations as examples and how to
build a flow graph today we will
continue in the same direction alone
what directed acyclic graphs are and
understand value numbering so just to
recapitulate from the last lecture here
is an example of a control flow graph so
these are the basic blocks each basic
block is a single entry single exit
structure and there are arcs between the
basic blocks to show the control flow
within the program the contents of for
each of these basic blocks are
quadruples that is a form of
intermediate code and these basic blocks
and you know are built by identifying
leaders and there are optimizations
which can be carried out on these basic
blocks which we are going to learn from
now on okay here is an example of a
directed acyclic graph dag as it is
called here is a set of ten quadruples a
small basic block and a basic block can
be represented in the form of a directed
acyclic graph here is the dag
representation of this particular basic
block so why are we studying this
representation of a basic block first of
all this is the conceptual structure
that we need to build in order to
perform local optimizations and it very
clearly tells us what are the
capabilities
of such an optimizer so let's go
quadruple by quadruple and see how this
particular bag structure is built the
first one is a equal to 10 so here is a
no da you know a node containing 10 and
it is labeled as EA so this is the way
we are going to do it whenever there is
a value or whenever there is an operator
star plus etcetera etcetera that's going
to be placed inside the node as text and
there is a label attached to each of
these nodes which will tell us what is
the name associated with that particular
value or operator so a equal to 10
corresponds to this particular node with
the value 10 inside and the label a
outside so the next one is B equal to 4
star a so here is a node containing
value for the node star connects 4 and a
and it is by itself named as be the next
one is 3 1 equal to I star J which is
very similar there is a node I and there
is a node J these the names are also put
inside because there is no value
attached to them as of now and then
there's a star which really shows that I
and J are connected and the value of the
label associated with the node star is
t1 to begin with t3 arrives later C
equal to t1 plus B is similar t1 is used
as one of the children of force a plus B
is used as angle child and it is labeled
as C this over striking of C has an
extra meaning which will be clear later
on t2 equal to 15 story is similar J is
reused 15 is created star is created and
a label t2 is attached to this
particular star D equal to t2 star C
again we take t2 we take C
and then you know these two are related
by star and that is actually labeled as
d there is another statement e equal to
I so there is a node already with a
value I or a label I and there is no
modification of that I which has been
carried out so the value of e will be
the same as value of I before you know
and it is all therefore we attach the
label e to this particular node I and
nothing else no other action is taken t3
equal to e star J so e star J is
actually discovered as I star J because
he is nothing but a label on the node I
and therefore I star J and E star J
identical it's the the I star J small
sub tree already has a label T 1 and
therefore T 3 is also attached to the
same list of labels so T 1 and T 3 are
both now corresponding to this
particular star there is no further nor
creation which is carried out so this is
an example of how common sub-expressions
are actually discovered so I star J was
an expression which was computed now
East RJ which is nothing but I star J
has also been discovered as a common
sub-expression so we don't have to
compute it again we just use the
previous expression and this is
indicated by attaching the label t3 to
this particular node star t4 equal to I
star a so this is a really at this part
of 4 in this part of the picture so
there is a and you know this is already
I is already here so now there is
something special which happens here
look at it the what is stated here is I
star a and what is taken here is a star
I so this is possible because we assume
at this point that the star operator is
commutative so by using commutativity we
checked whether
yes I if I sorry a was not present so we
checked whether yest our I was present
so we discovered that ta star I is
present and therefore you know we a and
I are present rather and we created a
node star and attached a level t4 to it
C equal to t3 plus t4 is very similar
there is t3 here t4 here and this is an
example where a new value has been
assigned to C and the old value in
quadruple number 4 is no longer going to
be used so this is overriding that
particular value so this old value is
killed the node level C is deleted and a
new level C is attached to this
particular plus so this dag hopefully
shows examples where there is a reuse of
nodes and that common sub-expressions
are discovered and so on so now let's
see how to implement this type of a
scheme to carry out some of the local
optimizations value numbering is a
simple way to represent you know DAGs
and while searching the directed acyclic
graphs if we represent them using
pointers etcetera
it's extremely inefficient for example
if you are searching for a node in the
dag it is not possible to search for the
node without exhaustively searching the
entire diet so it is so in practice when
we implement you know optimizations on
tags we use the value numbering scheme
rather than a linked representation of
tags now value numbering scheme uses
hash tables and therefore it is very
efficient in searching the graph itself
what is the central idea the central
idea of value numbering is to assign
numbers called these are called value
numbers so these are assigned to
expressions and of course they are also
assigned to single variables in such a
way that two expression
receive the same number if the compiler
can throw that they are equal for all
possible program inputs so we saw this
happen in the previous picture only
thing is we had not assigned any values
numbers so for example here you know I
star J was already present so he stars
discovered as a common sub-expression
we will soon see that this particular
expression you know I star J and another
expression e star J will both receive
the same values numbers so what we
assume are quadruples with binary or
unary operators we also permit copy
operations stay assignment of stay
constants and so on and so forth two
variables there are three tables which
are used by this particular algorithm
and you know they are all hash tables so
I will show you some pictures of these
data structures very soon the first one
here is called a hash table the other
one is called as a value number table
and the third one is called as a name
table so let's see some pictures so here
is a hash table entry it is indexed by
expression hash values in other words we
take an expression hash the expression
that will give us some particular value
index and go to that particular index in
this hash table if the expression which
is present there is the same as the one
we are searching then there is success
and if there is no success if necessary
we insert that particular expression
into that index so in each one of these
entries we store the actual expression
itself and the value number value number
is nothing but a counter so we
initialize it to 1 and then we go on
incrementing it whenever we need a new
value number so
this is so far as the expression hash
table as a hash table which is which is
storing expressions then the second one
is called a value number table a value
number table is shown here each entry
actually has a name and a value number
this is indexed by the hash value of the
name why do we have a separate valve
number table and why don't we store
names also in the hash table itself the
hashing function for expressions will
have the two variables of the expression
assuming that it's a binary expression
binary operator so it will have you know
as parameters the two operators
operations rather as a sorry the
operands and let's say in the a star b
we take a and b and then the operator
also the star has to be incorporated
into the hashing function so depending
on the three values a star and we the
index value produced is going to be
different if they are different
variables again it's going to be
different so the same expression hashing
function cannot be used for names where
you don't have any operator and you
don't have a second name so we use a
different table for storing names and
this is the value number table for each
name you hash it then you know you
produce what is that particular index
and pick up the value number if the name
is already present there the third one
is called as a name table so name tables
are shown here the entries are shown in
ten entries shown here there is a
nameless there is a constant value and
there is a constant flag so the name
which actually produces you know it's
indexed by the value number for example
okay so the names are put a given value
numbers and the value number is used to
index into this particular
table called the name table so inside
the name table we store the constant
value of that particular name if it is a
constant and then set the cons flat to
one if the name that is stored here is
not a constant then this is set to zero
and then you know this file this
particular field has no relevance but
what is this list here so in the field
name list first name in the list is
always the defining occurrence of that
particular name and it replaces all
other names with the same value number
with itself okay or it's constant value
so if there are many names which are
equivalent we saw this happen in this
particular figure t1 and t3 are
equivalent alright so here he and I are
equivalent and so on and so forth so in
such a case we are going to have a list
of such names here which are equivalent
and the first one is the defining
occurrence which will be used in place
of all other names in that particular
list and if it is a constant we are
going to use the value of that constant
in place of all these names the value
numbering scheme can be used to
eliminate common sub-expressions
constant folding can also be performed
and constant propagation can be carried
out in basic blocks so elimination of
common sub-expressions is something
which I already mentioned constant
folding is evaluation of expressions
involving only constants and constant
propagation is if there is a assignment
which say C equal to 4 then wherever you
a is used for is going to be propagated
to that point that is called constant
propagation you will see how to do these
things with value numbering value
numbering can also take care of or take
advantage of the commutativity of
operators which I briefly mentioned a
few minutes ago with respect to that
directed acyclic graph representation
addition of 0 because a plus 0 is a
itself multiplication by 1 a star one is
a and you know these are the 3 which
have a simple algebra class which can be
taken care of by Vera numbering in basic
blocks so let's take an example run
through that example in a step-by-step
fashion and see how it works out here is
a high level language program a equal to
10 B equal to 4 star a C equal to I star
J plus B D equal to 15 star a star C
equal to I and C equal to e star J plus
I star a so if you look at this here is
a a equal to 10 so this is actually the
if you observe it is the same program
that we saw here okay
there is no difference so only thing is
we have considered the quadruple version
directly here is the high-level language
version so i star j plus b is broken
into two quadruples 15 star a star c is
also broken into many quadruples
similarly this is also broken into many
quadruples so what is the set of
quadruples after the optimization so let
us understand that and then see how the
optimization itself is carried out so a
equal to ten remains in for star a B
equal to 4 star a J is 10 so we are
going to replace it by B equal to 40 T 1
equal to I star J remains as it is C
equal to t 1 plus B a B is replaced by
40 which is now being calculated as a
constant t 2 equal to 15 star a becomes
t 2 equal to 150 because a is a constant
value of 10 D equal to T 2 star C
becomes Vava D equal to 150 a star C
because T 2 is 150 equal to I remains as
equal to I and T 3 equal to e star J
becomes T 3 equal to I star J you know
it is really now we find that T 1 equal
to I star J and T 3 equal to I star J
actually are the same one and the same
so we can replay delete this particular
instruction number 8 and all
used even in its place so further t4
equal to I star a becomes t4 equal to I
star ten and C equal to t3 plus t4
becomes C equal to t1 plus t4 because t1
and t3 have the same value as I said it
can be deleted and t2 equal to 150 the
value of 150 has already been propagated
to all the other places for example t2
star C is the only place where t2 is
used so this quadruple is not needed
anymore five and eight but can both be
deleted and for did we have detected
that I star J is a common sub-expression
we have done constant folding by
evaluating these expressions constant
expressions and we have done constant
propagation by replacing these B's and s
by constants so let's see how all this
can be done so the first quadruple is a
equal to 10 now a is entered into the
valnum table let us say with the value
number of 1 this is the beginning so we
have set V and the counter value as 1
and it is also entered into the name
table with the constant value of 10 so
first J is hashed entered into a random
table the well number is set as 1 and
then using the trial number index into
the name table set the constant value as
10 and because they set the constant
flag as one second quadruple be equal to
4 star a so now when we search for a in
the valnum table which is a variable we
find that it's already present and its
value is 10 the trial you can be found
from the name table by using this value
number in the values on table so we have
performed now constant propagation
because we find that J is 10 and we can
replace it here for star a is evaluated
to 40 this already said and the quad is
rewritten this is the other action you
have know perform constant folding B is
entered into the valnum table with the
value number of 2 this is a different
value number now
and into the name table using the same
value number of two with a constant
value of 40 so far we have entered these
two into the appropriate tables t1 equal
to I star J similar I and J are not
present in the tables so they are
entered into the tables no new value
numbers are created okay and there is no
constant value attached to either a ERJ
because they are not constants Oistrakh
J is entered into the hash table with a
new value number so we hash this go to
that index store it and assign a new
value number because I star J was not
present before t1 is entered into the
valnum table with the same VN as that of
I star J so we assign some value number
to I star J the same value number is
assigned to t1 because these two always
carry the same value until put this
point in time equal to I I is already
present thanks to I star J I was
introduced into the table some time ago
so we get it actually from the table
find the value number and then assign
the same value number to e as well so
whenever we get e we can replace it with
I so what we do is this actually is
entered into that name table along with
I you know I is the first defining entry
and then e is going to be attached to
the same list in processing t3 equal to
e star J we find that Yi and I have the
same value number search and you get the
same value number e plus J is nothing
but I plus J sorry East RJ this plus is
a mistake so e star J is same as I star
J and since I star J is already in the
hash table we have found a common
sub-expression so please read this plus
s star from now on all users of 43 can
be replaced by t1 so t1 was already
present in the hash table right so there
is no need to cry
another sub expression called I star J
quad t3 equal to a star J which is
nothing but I star J can be deleted so
we found that you know I star J is
present its t1 is actually attached to
it with the same value number so now we
have the same value number attached to
t3 also and therefore t1 and t3 are two
occurrences of the same expression where
we have two occurrences with the same
value number so whenever we have t1 we
can replace you know whenever which he
is get t3 we can replace it by t1 so t1
and t3 will be entered into the name
table t1 as the defining occurrence and
t3 following it now C equal to t3 plus
t4 t3 and t4 are already there in the
table and they have a value number two
so t3 plus t4 is entered into the hash
table with a new value number so we hash
it and enter this is not in a common
sub-expression which is already present
this is a reassignment to see that is
what we need to be very careful about
you see so far we had you know this is
not the third quadruple this is really
the you know quadruple a little later on
okay so this is the sixth quadruple okay
so t3 plus t4 was not there so we have
entered it but this is an you see this
is not the same old si si was defined
earlier but now C is really defined so
si gets a different value number and it
is the same as that of t3 plus t4
so the old si actually it's kind of for
disabled its value number is not used
anymore it's rewritten with the new
value number so these quadruples are all
remembered after the deletions and we
get an optimized set of quadruples as we
saw here so 3 you know 5 & 8 go away 5
is gone it is gone so then we make
success 5 7 s 6 etcetera etcetera
etcetera
so here are the hash table and value
number table at you know finishing time
so see that I star J has value five even
plus 46 150 stars he has eight I started
in as 91 plus t4 has 11 so these are the
various expressions that we have found
with distinct values numbers value
number table is interesting ABI e JT 1
and C they were all given one two three
four five six then T to seven days 8e
did not get a new value number it got
the same value number as three then T
three did not get a new value number it
got the same value number as T 1 and
then T four what a new value number 10
the second time C got a value number six
11 and the six was overwritten here is
the the name table at the end so yeh
stored with constant value 10 and cons
flags to be stored with 40 and true ind
are not constant so there is nothing
here
j is not a constant t1 t3 are not
constants so please see that I and J I
and E are together here I is the
defining occurrence and replacement for
e will be that of I see was a t1 t3
replacement of T 3 will be t1 itself t2
is 150 and true D and C are not
constants so this is how we do simple
value numbering and create these tables
find common sub-expressions
and so on and so forth now let's see how
to handle commutativity so when i
already mentioned this commutativity in
the directed acyclic graph
representation so when we search for an
expression I plus J in the hash table
and this search let us say fails
so if plus is commutative on integers
for example commutativity holds on
floating point numbers it may not hold
so let us assume that competitivity
holds so now instead of Phi Phi plus J
is not available
h4j plus side so perhaps J + I is
present so we already saw this happen
before if there is a quadruple so this
is using commutativity exploiting
commutativity if there is a quadruple X
equal to I plus 0 then it is not
necessary to keep it as it is and do the
arithmetic with plus it can be replaced
with X equal to Y perhaps from now on
you know we can use ie in place of X and
finally even X can be deleted so here we
are using an algebraic law you know a
equal to a plus 0 any quadruple of the
form y equal to j star 1 can be replaced
with y equal to j this is again you know
a simple a you know a equal to b star 1
right the can be replaced by a equal to
b after we about 2 types of replacements
travel numbers of x and y become same as
those of I and J so that's a very simple
thing to see quadruple sociologists
variables are used later can be marked
as useful and all unmarked quadruples
can be deleted at the end so this is a
implementation detail there are more
complications which come in when there
are arrays so let us consider a simple
sequence of 3 assignments X equal to AI
y a AJ equal to y and z equal to AI so
if you look at this particular statement
a J equal to Y I and J are runtime
variables right they can take any value
so we have no idea of what their values
are so it is possible that I and J could
be the same if they are same by some
chance then you know I a I is not a
common sub-expression anymore
syntactically this a and you know this
year look the same so I could have all
he said that equal to X if we had only
looked at the syntax but this particular
statement a is equal to Y if I and J are
the same should be interpreted as AI
equal to Y in which case there is a
reassignment of value to AI and the
previous you know value which was
assigned to X cannot be used as the
value of AI anymore so we need to replay
retain these three statements as they
are so this is a problem how do we
handle it whenever there is an array
expression we actually do not try
reusing the value of the towei
expression at all so the above sequence
cannot be replaced by X equal to a AJ
equal to Y and set equal to X because of
the reasons I mentioned just now so this
is processed as it is you know here is a
an indexing assignment operator so we
hashed this particular expression a I
you know I enter it into the tables and
then you know X is taken as a defining
occurrence which gets the same value
number as ei but when we process CA J
equal to Y all references to array a so
far are searched in the tables we need
to search exhaustively there is no other
mechanism and they are marked rescued so
this kills the quadruple number one here
so there could have been others also all
such AI ei J aka X etcetera are all
deleted in our rather mark Roskilde so
that their value numbers are not reused
from this point onwards why this
particular J could have been any one of
those values we do not know which value
it is it could be it could have possibly
is not but we cannot take a chance when
processing Z equal to AI will quadruple
skill quadruples are not used for common
sub-expression elimination so fresh
table entries are created was that equal
to EI there is a new value number is
which is assigned to AI however if we
know a priori that I not equal to J
so that these two are never identical
then AI can be used as a common solution
in this particular case but this is very
rare it's very rare so we may have to
kill them pointers are very similar so
consider X equal to star P star Q equal
to Y & Z equal to star P so P and Q
could be pointing to the same object
you don't know at runtime this can
happen if if which has happened then Z
equal to star P okay he is not a common
sub-expression anymore because a new
assignment is being made to star Q it is
not X equal to you know X was pointing
to what P was pointing to X contains
star P so X contains the object if I he
was pointing to now a star Q contains a
new object Y so Q points to a new object
called Y and you know it is hue has a
value possibly P itself so this should
be read as star P equal to Y so now P
points through some other object and
therefore Zend equal to star P cannot
become you know X is equal to X this
would be wrong it's very similar to
array case before so if pointer analysis
has been carried out and P and Q never
point to the same object and that fact
is known then we can proceed with the
same CSC here but otherwise P and Q can
point to any object in the basic block
hence when star Q equal to Y is
processed during value numbering all
table entry is created so far our mark
Roskilde so this kills the quadruple
number one here and when we are
processing set equal to star P killed
quadruples are not used for CSE and
fresh tables entries are made for Z
equal to star P
something similar happens when we have
procedure calls so if we do not know a
priori which objects P and Q point to
then table entries corresponding to only
those objects need to be killed so this
I am n shinned already so what happens
in procedures with no dataflow analysis
that is analysis of the program we need
to assume that the procedure call can
modify any object in the basic block so
if the procedure is called it has side
effects
so it can assign to global variables you
know it can assign to parameters which
have been passed by reference so we have
to assume that any variable in the basic
block is modified because we have not
carried out any analysis and we have no
information about any variable hence
while processing a procedure call all
table entries created so far are not
killed everything goes nothing is
visible anymore nothing is a useful
useful anymore sometimes this problem is
avoided by making a procedure called a
separate basic block so we eliminate
this problem you know we avoid it by
making a separate basic block for a
procedure call so that it does not kill
any other variable and since the
procedure call is in its own basic block
and this is a fairly simple thing to do
so analysis becomes much simpler now we
looked at basic blocks
so sometimes basic blocks are small so
what happens is they are all the
techniques that we have applied may not
be so effective there is a way to extend
whatever we did so far with our value
numbering to a sequence of basic blocks
let's see what these are
a sequence of basic blocks B 1 to B K
such that bi is the unique predecessor
of bi plus 1 for 1 less than equal to I
less than K and B 1 is either the start
block or has no unique predecessor so
such a sequence of basic blocks is
called as an extended basic block so
extended basic blocks with shared blocks
can be represented as a tree so let's
look at some examples here is a control
flow graph right so start b1 b2 b3 b5 b7
this side is b6 b7 this side is before
b7 and then stop
so the extended basic blocks are start
and b1 okay and then you know when you
go to veto it has two predecessors it
doesn't have a unique predecessor so we
stop our extended basic block at b1
itself then you consider V 2 V 3 and B 5
B 2 B 3 and B 5 okay
so if you try adding you know something
else for example b7 then it has two
predecessors so we really cannot have
that in the same basic block right so B
2 B 3 and B 6 this is another extended
basic block this is a sequence we could
not have added b2 b3 b5 and b6 because
v5 and basics are not in the same
sequence
okay so b2 b3 b6 are all b5 is not the
predecessor of b6 or vice-versa so we
cannot add these two in the same
extended basic block so b2 b3 b6 forms
another extended basic block then b2 b4
forms one more extended basic block
finally b7 and stop form a basic block
or be extended basic block now these 3
b2 b3 b5 b2 b3 b6 and b2 b4 actually
share basic blocks so b2 b3 b3 shared
you know with b5 and b6 b2 is shared
between
III and v4 so there is a lot of sharing
that happens in these right so because
of this b2 is shared in all of them
actually B 2 B 3 and B 5 B 2 B 3 B 6
then B 2 B 4 so B 2 is shared in all of
them now such a tree representation can
be used you know gainfully to do our
value numbering and extend the benefits
of value numbering to such basic block
please so what we do is very simple we
really need to use a technique which was
used in the symbol table construction
for programming languages with nested
scopes so the new entries okay so shared
blocks in extended basic blocks required
scope reversions of our tables I will
explain what these are the new entries
must be purged and change entries must
be replaced by old entries as we go on
and a pre-order traversal of extended
basic block trees is used here so let's
see what happens so we start let us say
we let us consider this particular set
of extended basic blocks so we start our
value numbering with the basic block -
it is done as usually you know as is
usually done the expressions and
variables are entered into the various
tables and they are filled when we come
to then we take up b3 without destroying
any of the tables built in b2 it is easy
to see that we can use all the commas of
expressions and constants of b2 in v3
also there is no problem at all so we
can keep the you know entries of B 2 and
reuse them within b3
now when we go to b5 something similar
happens we can reduce the entries of B 2
and B 3 with no difficulty at all but
once b5 is completely processed
possibly we have discovered new common
sub-expressions and constant propagation
folding etcetera has been carried out
using v2 and v3 also b5 is completed so
now we have to get back to b3 and start
processing b6 this is the preorder
traversal but the entries that we
actually created during b5 cannot be
made available during the processing of
v6 we need to have only the entries of B
2 and B 3 and the interests of b5 must
be eliminated removed this is the reason
why we require scoped versions of for
these tables so we start a ask you know
a symbol table we use something similar
to scope symbol tables we have a set of
table set scope equal to 1 when we come
to a new level we actually establish you
know tables at scope equal to 2 and here
we established table set scope equal to
3 whenever we want to search these scope
row tables we actually search for the
current table such the current tables
first then in the enclosing scope and
then in the next enclosing scope and so
on and so forth up the tree
when we finish processing b5 all the
tables is scope equal to 3 are removed
and a new table with scope equal to 3 is
started for b6 so now we can use entries
of B 2 and B 3 in b6 also finally when
b6 is completed its entries are all
deleted we go to b3 when the and when we
need to now return to b2 so the entries
of B 3 which go peak hwal to 2 are also
removed and new set of entries it's Corp
equal to 2 corresponding to B for are
created and this is processed and
finally we return to be 2 after relating
the entries corresponding to B 4 so this
is how scope the you know hash tables
are used in order to do value numbering
on these extended basic blocks as you
can see because we reuse entries from B
2 and B 3 in B 5 and B say
there is a lot more scope for
discovering common sub-expressions and
finding constants doing cosmic
propagation and so on here is a simple
algorithm for doing value numbering so
when we visit extended basic block tree
and E is a node in the tree so it's to
begin with the root of the tree and from
now on the new names will be entered
into enter with the new scope into the
tables when searching the tables we
always search the beginning with the
current scope this is something I
already mentioned and more to enclosing
scopes so this is similar to the
processing involved in symbol tables
with lexically scoped languages value
number e comma B is the call to the
function value number to process the
basic block B and now so e dot B is the
basic block so e dot left not equal to
null then visit left subtree u dot right
not equal to null is it the right
subtree this corresponds to the
pre-order traversal then once the left
and right subtrees are completed remove
the entries for the new scope from all
the tables and undo the changes in the
table saw for the enclosing scopes so
this is the function called visit TVB
and which is actually called for each
tree representation of the extended
basic block so this brings us to the end
of the lecture on local optimizations so
welcome to the lecture on code
generation so in this set of lectures we
are going to look at the main issues in
machine code generation some samples of
generated code two schemes for
generating simple code so these are
simple code generators machine code
generation is
very fascinating area with several
optimal code generation algorithms we
are going to look at a couple of
algorithms of this kind one of them is
the historically famous set human
algorithm then there is a slightly more
complicated dynamic programming based
algorithm and we are also going to look
at a practical tool called I burg which
uses tree pattern matching and dynamic
programming in its implementation then
we are going to look at the method of
generating code from directed acyclic
graphs this problem is np-complete so we
need some heuristics to solve this
problem finally we will talk about
peephole optimizations which are machine
dependent optimizations what are the
main issues in machine code generation
machine code generation is a
transformation so it transforms
intermediate code to machine code and
machine code we can say is either binary
representation or assembly language
representation if it is a binary
representation all the machine code
which is generated for the program can
be sent to the linker and then the
loader whereas if the machine code is in
the form of assembly it has to be sent
to the assembler which in turn generates
binary then the binaries are sent to the
linker and the loader but the difficulty
of generating code is the same whether
we generate machine code in binary or
machine coding assembly it is just that
if we want to generate binary the job of
doing assembly is also in some way
incorporated into the machine code
generator itself
let us assume that we generate assembly
because it is easier to explain the
scheme in such a case let us assume
quadruples as our intermediate form and
let's also assume that the control flow
graph is available to us the first issue
is which instructions should we generate
so for example we let us say the
quadruple is a equal to a plus 1 a very
simple instruction such as increment a
can be generated or we can say load a
into the register r1
add the constant 1 to r1 and store the
register r1 in a so either one
instruction or three instructions well
obviously increment is much cheaper as
if everybody can realize but if there is
no increment instruction in the
instruction report or of the machine we
need to generate this particular
sequence the point here is every machine
is different its instruction set is
different therefore we cannot assume the
existence of a particular type of
instruction in every machine we will
have to our algorithms for code
generation will have to cater to every
type of machine what we know is that
every machine will have instructions to
perform any task that's all we really
know so here this increment of the
sequences may be faster than the other
in such a case we say that one of the
sequences is cheaper than the other
second issue in which order should we
generate code it is possible that some
of the orders use fewer registers and
some of the orders may
so be faster than the others so the code
simulator to some extent must evaluate
different orders and then choose the
best obviously it cannot enumerate all
orders and check them it uses other
mechanisms to check a few of these
orders and finally use the one choose
the one which is cheapest one more issue
is which registers should we use in code
generation some of the registers are
reserved for particular types of use for
example the program counter the stack
pointer so these are specific registers
which should not be used for any other
purpose this is the norm in programming
but there are many registers in there
but in machines and these registers can
be used to store any variables so which
registers to use which variables should
be put in those registers etcetera is
the problem of register allocation in
general so optimal assignment of
registers to variables is is very
difficult to achieve
there are heuristics which are used to
achieve this - some with some efficacy
one other issue is should we optimize
for memory should be optimized for time
or should we optimize to save power
each of these is actually very important
in the different context for example for
embedded systems of one kind okay it may
be necessary to save memory so we must
optimize for memory in another embedded
system such as sensor network the
programs which run may have to actually
save power because they all run on
batteries and in our servers it is
necessary to
optimize the programs to save time so
they must run as fast as possible power
and memory are not considerations here
so which the code generation strategy
for any type of optimization is going to
be different so the cost of the
instruction sequence is abstract so it
can be memory save a space or time or
power we will see how this system is the
core simulator easily there targetable
to other machines is a very important
problem writing code generators is a
difficult task it is no easy task there
are thousands of details which need to
be kept track off it is necessary
therefore that read code generators be
produced either automatically or parts
of code generators we used in writing
code generators for other machines so
can the code generator be produced
automatically from specifications of the
machine so as we will see later it's
possible to use what are known as tree
grammars for the specification of the
machine instructions and there is going
to be a code generator generator which
is very similar to yock yock accepts
context-free grammars and gives you a
parser this type of code generator
generators accept such specifications
and produce code generators as output so
let's look at some samples of generated
code to understand what the issues are
we have shown here are several types of
quadruples be equal to a a is actually
you know loading B from an array XJ
equal to Y is assigning a value to an
element of an array
yes equal to star P assigns a X the
value of using a pointer star Q equal to
Y assigns a value to
a location pointed to by cube and here
is a branch statement so let's see what
the code that is generated for each of
these be equal to AI so load I into r1
so now the value of I is available what
is I it is the offset within the array a
multiply our 1 by 4 and then put the
value in r1 itself why each of the
elements of the array is assumed to be 4
bytes long so if you look at the white
version of the array a each value is
stored in blocks of 4 bytes so to get to
the ice location of the abstract array a
we actually have to you know pass four
star I locations so that is what is done
by multiplication here so two
instructions already just for this
particular thing
finally load a of R 1 with r 2 so sorry
the other way
lower lower R 2 with EF R 1 R 2 equal to
a plus R 1 so what we really contents of
a plus R 1 so what we really did was
take the index which is R 1 you know go
into the array a get the contents of
that particular location now it is a Fi
and put that place that into our to
store the value of R 2 finally in B so
this four instructions actually require
are required to satisfy this one
quadruple instruction similarly XJ equal
to Y is simple we have load Y with R 1
so I saw a load Y into R 1 then loads a
into R 2 now we need to compute the
address of XJ so multiply R 2 with 4 and
place it in R 2 so now we have gone to
the place in X where we need to store
the value of y so r1 contains Y
so store r1 into X of R 2 this will
store the value Y into X of a so X equal
to star P is simple load P into R 1 and
now lower 0 r1 r2 comma R 2 takes the
contents of r1 as an address and goes to
that location fetches the value in that
particular location then puts it into r2
so an indirection here store R 2 into X
puts this entire value which is in R 2
into X star Q equal to Y is a very
similar load Y into r1 load Q into r2
store R 1 into 0 of r2 this is actually
indirection
if X less than Y go to L so load X into
r1
load Y into r1 now compare r1 and r2 if
branch on less than 0 to the label L so
these are the some of the example to
show what kind of code that we need to
generate so in the next lecture we are
going to look at samples of static
allocation dynamic allocation and then
see how to generate such code using
simple methods and also with optimal
results thank you
you