Interprocedural Data-Flow analysis - Compiler Design Video Lecture - Computer Science Engineering (CSE)

welcome to the lecture on
interprocedural dataflow analysis first
of all we need to understand why you
know interprocedural dataflow analysis
is needed so so far all the dataflow
analysis and optimizations that we have
studied were all interpret intra
procedural in nature so the point is all
these analysis were performed on one
procedure at a time we did not consider
a mix of procedures at any point in time
we always took one procedure analyze it
completely and then went to the other
and so on
so the interaction between the
procedures in you know when procedure
calls happen was not taken into account
so for example one of the procedures in
a processor parameter which is modified
by the other etcetera etcetera were not
taken into account and we assume that
procedures invoked may alter all the
visible variables this was essential
because once we ignore the interaction
between procedures and consider
procedures independently the side effect
of each procedure call must be assumed
to be reversed so the worst is that it
may alter all the variables visible you
know so except for the local variables
of the procedure all others were assumed
to be modified so such interprocedural
analysis is in general somewhat
imprecise so it is conservative but it's
very simple so in other words it happens
very quickly you know that I'm required
for
Alyce's is not much but at the same time
the effect of the other procedures
etcetera is not incorporated so results
are imprecise and conservative so
interprocedural analysis operates across
an entire program it considers the
effects of all the procedures so it
makes information flow from caller to
colleague and vice versa so parameters
flow from caller to you know from the
caller to Colley and then the results
flow back or the reference parameters
which are modified flow back from the
colleague to the caller
so procedure inlining is a very simple
method to enable such information flow
so what is inlining we have already
studied this so basically when you
consider a procedure call the procedure
corresponding to that particular call
you know the body of that could be reap
you know if I made to replace the call
itself so the what is involved here the
formal parameters would be assigned the
values of the actual parameters through
assignment statements and then the body
of the procedure follows finally the
result is also conveyed through similar
assignment statements so the call is
replaced by the body so that means there
is actually increase in core size so one
has to be very careful about such code
size increases so this is applicable
inlining is applicable only if it if the
target of a call is known so in other
words so if we say call test with some
parameters then it is possible to inline
the procedure test at that point but
suppose the same procedure test is
actually called by i a pointer okay so
we are calling the procedure by i
appoint
so in and we have no idea what the
pointer my point to so such a case in
lining is not possible otherwise if it's
a virtual call for example in the
object-oriented languages there are you
know methods which are called virtually
so we have no idea whether the virtual
call points to any one of the
possibilities had compiled them so in
such cases inlining is not possible
interprocedural analysis in
object-oriented languages can sometimes
determine if the target of even a
virtual call is actually a static call
in other words the call may be actually
virtual but the analysis may say that it
cannot point to anything but one
particular method so in such a case it
is a static call and we can replace the
virtual call by a static call but why
should we do this we know that virtual
calls happen using the dispatch tables
so it's there is some indirection and
therefore a cost attached to it so we
can make it cheaper by making it a
static call so either a static call or
inlining can be used at this point
however inlining should be applied with
care I already mentioned this because it
increases the memory footprint so what
are the applications of interprocedural
analysis so converting virtual method
calls to static method calls is one that
I already mentioned then the
interprocedural pointer analysis helps
in making points two sets more precise
so a pointer may be pointing to many
objects a b c d etcetera in the worst
case we will assume the largest set
possible at that point but with
interprocedural analysis we may be able
to cut down the size of such sets and
make the information more precise so
reaching definitions available
expressions etcetera can now be computed
with more precision so they're going to
be more accurate so that means the
effect of these are
EMAS Asians will also be right
interprocedural analysis eliminates
spurious data dependencies interpersonal
constant propagation makes loop bounds
known so these are all possibilities
so suppose we are doing Auto
parallelization the compiler is doing
the parallelization so then we compute
the data dependence graph so in the
absence of precise information you know
we may actually construct the graph with
many data dependences which are actually
spurious so this can be avoided and the
data dependence graph can be made more
accurate and precise similarly if there
are loops with hos bounds actually our
parameters of the procedure in which it
is being executed the bounds may not be
known
you know without an interpersonal
analysis but with such analysis if the
loop bounds become known and they become
constants then parallelization of such a
loop may be simpler
so exposes more parallelism during
parallelization so that's the general
idea
interposition glances helps in detecting
for example lock/unlock pattern of
critical regions so one may actually do
a talk but may forget to do an unlock on
a semaphore so such things can be
detected by an interpersonal analysis
disable enable law for interrupts so
every disable must be followed by an
enable of for an interrupt otherwise
interrupts will never happen again
so this can also be checked by interfere
analysis so you may wonder why
interprocedural it may also be intra but
in general there could be procedure
calls in between the lock and unlock or
disable enable etcetera so that's the
reason why we require such
interprocedural analysis then the SQL
injection attacks can be detected so
what is a skewer injection attack for
example in web applications the input
may not be validated properly so
the account number and the password may
not be validated properly so it is you
know it is well known that if the
account name or the number is some weird
set of characters such as percent hash
at etcetera etcetera some of the
mechanisms login mechanisms do not check
whether it's a valid name whether it
requires a password etcetera etcetera
they actually log in such user C with
some any-any password or without even a
password so then the user gets control
of the information and can create havoc
so this is through SQL injection and
software vulnerabilities due to buffer
overflows for example so in general C
C++ programs may not check the array
bounds at runtime so and definitely not
during compile time so if there is an
overflow and there is some area of the
buffer which is freely available for
writing some information the user may be
able to write extra information by
adding something and then he may he or
she may be able to access sensitive
areas so those are that's about the you
know application of interprocedural
analysis so let's start looking at the
analysis itself we need to understand
what exactly is a call graph so a call
graph for a program is a set of nodes
and edges as usual because it's a graph
so there is one node for each procedure
there is one node for each call site and
then if call side C may call procedure P
then there is an edge C to P so I will
show you an example very soon so C and
Fortran make procedure calls directly by
name so hence called target to such
invocation can be determined statically
otherwise as I already mentioned you
cannot do that
so if the program includes a procedure
parameter or a function pointer then the
target may not be known until runtime so
target may vary from one invocation to
another and the call site can link to
many or even all procedures in the call
graph so considering only return types
of functions so we have no other
information so we should we will
probably be forced to attach to anything
so this is the sorry the since we are
calling through a pointer and a pointer
my point to anything there is nothing
better we can do we will have to point
to every procedure that's available in
the graph so for example virtual method
invocations in C++ and Java are of this
kind calls through the base class
pointer cannot be resolved in runtime so
let's take a simple example so there is
a function called F 1 and F P is a you
know function pointer so f 1 takes an
integer parameter so it checks if X
greater than 0 then return star FP X
minus 1 or written X so here this is a
call through the function pointer so and
the F 2 is similar FP is assigned f1 so
FP now points to the function f1 and
then you return star fpy so again it is
a call through the function pointer so
main assigns say f2 to FP and calls
through FP so now let's understand how
the program works
so the first time FP is pointing to f2
so we have it it's really a call to F 2
with the parameter 200 so we come here
here FP is modified to point to F 1 and
then it calls through FP again so now we
are calling F 1 so when we go to F 1 we
check whether X greater than
and now AFP is pointing to f1 so there
is a recursion F P of X minus 1 as
returned X so this is a the call call
sequence so now in the absence of so at
this point in time we know that you know
this is a call to f2 and nothing else at
this point in time we know that this is
a call to a fun and nothing else
and here we definitely know that it is
nothing but a call to F 1 so that is if
we know the information that what FP
points to we can actually construct the
graph very accurately otherwise it
becomes conservative as we see now so
here is the call site 1 call site to
call site 3 f1 f2 and main so in the
absence of any pointer interprocedural
information we do not know what the
function pointer points to so for each
of the call sites it's actually pointing
to both f1 and f2 we cannot point to
main anyway because mine is a main
program from which to the protocol the
program starts and no calls can be made
to main so f1 and f2 are both pointed to
by call site 1 similarly call situ also
points to both F 1 and F 2 similarly
call site 3 also points to both f1 and
f2 this is in the absence of any
information that F P points through a
certain function but once we know that
you know call site 3 always points we
have to call site 2 always points to
your fun and call site 1 always points 3
of fun you can refine this particular
call graph 2 to be this this is an exact
call graph so this is an example of call
graph so what do we do with the call
graph presence of references or pointers
to functions or methods it helps us in
getting a static approximation of the
values of all procedure parameters
function pointers and receiver object
types so if we have any you know
assignments then to function pointers as
we saw in the example that's the
starting point of a static approximation
so we start from that point we do not
have any other edges that I already
added to the call graph we add only
those edges which are possible by the
static approximation then with
interprocedural analysis more targets
can be I discovered and new edges can be
inserted into the call graph this site
radio procedure is repeated until
convergence is reached so basically we
need to discover how the calls proceed
so in other words we need to trace the
call sequence and then construct the
calligraphic return there are many you
know aspects of this analysis and one of
them is context sensitivity so let us
understand what is sensitivity so here
is a small program I equal to 9 yr I
greater than or equal to 0 T 1 calls
tests with hundred rather T 1 is
assigned the value of function return of
this function with parameter hundred
second statement involves test call with
200 and a third one with the parameter
300 so and then we have Val I minus
minus equal to T 1 plus T 2 plus T 3 so
the loop continues until I greater than
or equal to 0
test itself just multiplies V by 2 and
returns so if we actually do a you know
analysis carefully let's see how we do a
careless or careful analysis function
test is invoked with a constant in each
of the call sets that's very clear 100
200 300 but the value of the constant is
context dependent in other words if we
discuss from call site 1 then the value
is 100 otherwise from 2 it is 200 and
from 3 it is 300 so it is not possible
to infer that T 1 T 2 and T 3 are HSN
car
values hence for val i as well unless we
recognize the context that is the call
site from which it is call is made so if
it is a very Navin Alice's it would
infer that the test can return 200 400
or 600 from any of the three calls so in
other words we have no information about
the call site so we are here in tests we
don't know whether the call comes from
fun 2 or 3 we know that there can be a
call from any one of these sites but we
don't know each one in such a case the
possible values of V are 100 200 or 300
because we do not know which call site
is involved so the values of the values
are done by test will be 200 400 and 600
any one of these or 600 whereas if the
call site information is available to us
it's a context sensitive analysis it
returns 200 400 and 600 for T 1 T 2 and
T 3 and 1200 for well I so if we know
the call site then we know exactly which
value is returned for which call site so
this is called context to context
sensitivity so because the value
returned is sensitive to the call side
call side is the context so let us do
let us understand what is context
insensitive analysis a little more so we
treat each call and each return as go to
operations it's as simple as that and we
create a super control flow graph so in
other words we now get rid of procedure
call we introduce a go-to operation for
both call and data so what does the
super control the control flow graph
contain it contains all the normal
interrupt additional control flow edges
as usual and then the edge connecting
each call side to the beginning of the
procedure it calls this is a go-to
operation now edge connecting return
statement back to the call side there's
another go-to operation and assignment
statements to assign the actual
parameter to its corresponding formal
parameter
the return value to the receiving
variable so these are all the extra
assignment statements that we need to
introduce so now the super control flow
graph I will show you an example very
soon is a simple flow graph there is no
procedure call inside so we can apply
standard analysis data flow analysis on
this super control flow graph so such a
method is very simple but it is very
imprecise because a function is now
analyzed as a common entity for all its
calls and only its input-output behavior
is abstracted out so we don't
distinguish between call sides so any
call site can make an entry into it so
we have we are going to be very
conservative so let us take an example
so the same previous example we started
off remember the equal to nine and the
loop for in just test of 100 200 and 300
so we start with a equal to nine then
this is the loop control if I less than
zero go to I'll quit the loop otherwise
we continue with the loop so now the
first call to test so the call to test
is here okay the test itself is here it
does nothing more than we start to so
return value is we start to that's the
body of the function test so we have e
equal to hundred so that is the call
site one we have assigned a parameter
then we make we have a jump to the body
of the function test
once the so let us say hundred so now it
computes 200 now possibly we would make
a jump to this okay
so T 1 equal to the trial so V equal to
200 this is a call to a call site 2 then
we jump here we compute V equal to 400
and then jump to this point possibly
then again T 2 equal to red 12 V equal
to 300 we jump here and then we go out
so you may wonder why we are going to
the appropriate place but when there are
many possibilities from here we can go
to this point or this point or this
point right any one of these is possible
here of course t3 equal to rate trial t4
equal to t1 plus t2 then t5 equal to t4
plus define as so so this is a t3 so
this is t3 sorry
t4 plus t3 and Vala equal to 45 so I
equal to I minus 1 and then you know you
go back to this in the loop continues
but now the value of V at b6 it could be
hundred it could be 200 it or it could
be 300 we don't know what the value is
because you could come from three places
t1 at before you know here for example
so if we had come here and then gone
there you know it would have been 200 if
we had actually come to this from here
to this point and then gone back it
would have been 400 otherwise it would
be 600 the same is true for t2 and t3 as
well each of those could be 200 400 or
600 so that means the value of Val I at
this point is a combination of any of
these so we have many possibilities for
Val I 600 800 thousand thousand 200 1400
1600 or 1800 so this is all that you can
infer from the context insensitive
analysis because we have no idea that
this call site you know a particular
call site gives this particular
parameter value and gets that particular
return value all that is kind of erased
now we have a super control flow graph
this is very conservative and therefore
imprecise so instead of saying well I
gets the value of t1 t2 t3 as 200 400
600 and the sum is the only value we
have an outside given so many
possibilities of 600 800 thousand
etcetera etcetera so Val I would have
got exactly one value if it is a contact
for the context-sensitive analysis but
now it gets four plus four eight values
as either 3 + 4 7 values
so that's the imprecise nature of this
context and insensitive analysis so what
exactly are call strings so we saw one
aspect that is the context sensitivity
so let's see what can't call strings are
so in the previous example we needed
just the call side to distinguish among
the contexts in general the entire call
stack defines a calling context so now
we are going to see why a complete stack
may be necessary to distinguish context
so the string of call sites in the call
stack is called as a call string so we
may choose to use only K entries just
below any call site in the stack to
distinguish between contexts so in which
case it is called as a K limiting
context analysis so we are not using the
entire call stack but at any point in
time just the K entries below a
particular value in the stack those are
the K president calls okay colles rather
collar scholars so those are the only
ones we are going to consider that
becomes a K limiting context analysis so
such a K limited context analysis
reduces precision and therefore makes
results even more conservative so we
take each such call string follow the
calls so start from let us say main
there is a call string attached to any
particular procedure to reach it may be
many call strings are possible for a
particular procedure so we consider all
such possible call strings do an
analysis of the and all the call strings
and then determine the various effects
of the procedure so we perform data flow
analysis replacing the parameters result
variables and as we go up and down the
call string so such an accurate you know
for each call string we are going to
make such an analysis and therefore it's
very accurate so let's see what the K
limiting call strings are
so the same program that we have here
now there are three call strings you
know only thing is there is a small
modification instead of test we have
another function f which is called here
and the F in turn calls test that's also
we always call F and F calls test so
there are three call strings now to test
so if you want to each test you have to
first call you know f and then call test
so it could be from c1 and then c4 our
c2 and c4 c3 and c4 so these are the
three call strings possible for the
procedure test so value of V in test
does not depend on the last call c4 so
this is the last call in the previous
case we did not have here so it
dependent on just the last call now
other is c4 as well so what it depends
on one call before that that is c3 or c2
or c1 so in this case two limiting
context analysis here now but one
limiting context analysis is not enough
to determine the accurate result so we
may require actually more than two in
general so let's see a demo of that so f
has been modified this part remains the
same so F says if we greater than one
not one call the F recursively we F of V
minus one otherwise called test so our
test remains as it is so now again let
us look at test so we start with F and
it is 100 so we actually is less than 1
not 1 so it just did a calls test so
that means c1 and c5 okay so this is the
call string for this particular one of
these c1 and c5 okay this is one call
string value returned is 200 then
suppose we start with C 2 in that case
you know it is 200 so we would have
actually called
F you know 100 times then the value
reduces
to one not one and finally we call test
so that means C 2 C 4 C 4 C 4 C 4 C 4
repeated hundred times is the call
string value returned is 202 similarly
for C 3 we would have C 3 C 4 C 4 C 4
etcetera so C 4 is repeated 200 times
and then we call test so the value
returned is again 202 because the value
come becomes 1 not 1 so the value of V
in test depends on the full call string
not the not either 1 or 2 or 3 limited
call strings so because if this instead
of this being 100 200 300 suppose this
was some other value then you know as
many times this recursion would have
been repeated as many times so the
costing would have become much longer so
this is an example to show that K
limited costing for any K is in general
not sufficient to analyze a program it
may require the full calls site
okay the entire cost ring so so now
suppose we want to do context sensitive
analysis we know that context
insensitive analysis is not very useful
so let us understand how to conduct
context sensitive analysis first
approach is what is known as turning
based context-sensitive analysis so this
is very simple but and context you know
what is cloning so we have this program
right so we have your fun and so for
each one of these call sites instead of
a single function you have calling it we
are going to introduce a specialized
function so T 1 has its own function f 1
so f 1 calls test1 so this is one set
similarly T 2 has F 2 and F 2 call
stress - so this is anger set T 3 has F
3 and F 3 calls test three so there are
three different functions F 1 F 2 F 3
and within that three different
functions test1 test2 and test3 are
called so there is a code explosion here
instead of just one function f and one
function test now we have three F
functions and three test functions so
there is chord explosion so once we have
such cloning we know that the F one
always calls test one right so there is
no other ambiguity here so simple
context insensitive analysis is enough
on the called cloned call graph but
recursive programs cannot be handled by
the scheme so there is code explosion
but there is accuracy but recursion
cannot be handled properly then the
second approach is called as the summary
based context two insensitive
context-sensitive approach so here each
procedure is represented by concise
description or summary that encapsulate
some observable behavior of the
procedure so for example in reaching
definitions or available expressions
analysis the appropriate out sets of the
procedure end blocks would serve the
purpose of this observable behavior so
our sets are available to the outside
world so this is what we want as the
observable behavior so for each of the
procedures using some assumptions we
compute the out sets and then they can
be appropriately used in order to
compute interprocedural information so
let us you know and then for each call
we are going to actually use this
summary information and derive some
result so let us look at one such method
in some detail here recursion can also
be handled because fixed point iteration
is possible in this approach so to
understand this properly we need to
understand the problem of what exactly
are aliases so look at this picture so
we have a equal to B plus X here then we
have y equal to C here and then D equal
to B plus X so control flows through
these
basic blocks so at this point you know
if suppose you know this is V Plus X so
if Y is not related to any of these
either be our X okay in such a case this
V plus X and this V Plus X are identical
there is no problem but if this Y is an
alias of either be re X that is the name
ye stands for either be our X it is
possible to have such julius's we will
know very soon how really accessorize so
just assume that the name Y is an alias
of either B or X so if Y is modified V
is modified or if Y is an alias of Y X
then if Y is modified X is modified so
because we have y equal to C here that
means it is a modification of the
expression V plus X so this B plus X and
this B plus X are not the same so if
such is the case then we cannot say that
B plus X is an available expression at
this point okay so that is why alias
analysis becomes important
how can a leonis arise so let's consider
a procedure so there is let us say a
procedure P X Y and then there is a call
to P such as p ZZ okay so the same
parameter that is passed twice in for
both x and y are it could be a call of p
u comma V from another procedure Q u
comma V but U is called as Q's it said
so one level of indirection q is called
as it said said said said then but P
would be called as within PU V itself
but since you and we are both said it is
the same as this in effect so
that's how aliases really arise so see
what happens is we have a X&Y here two
parameters but we have the same pair
actual parameter set here so both the X
and y stand for said okay so if you X is
modified that is modified if Y is
modified against it is modified and the
same is true here U and we both stand
for Z so this is how aliases arise in
programming so in reaching definitions
it is a conservative not to regard
variables as aliases when in doubt so we
do not kill definitions and in doubt so
it's okay to say one more definition
reaches even though it does not but in
the available expressions analysis it's
exactly the opposite so for example in
the previous you know program if B plus
X is to be available in v3 we must be
certain that both V and X are not
aliases of five so if they were then
since Y is modified then B plus X would
have been modified so we cannot you know
in available expression analysis it's
it's a must analysis so it is not enough
if V Plus X reaches along one path V
Plus X must reach along all paths so
even if there is a little bit of doubt
that V plus X is moving to be modified
we are not going to consider it as an
available expression so in very findout
we assuming that alias we assume
aliasing and we kill me plus X so the
point here is the application in the
reaching definitions are available
expressions etcetera etcetera will
determine whether aliasing is harmful or
is not harmful so we just compute alias
information and let the application use
it the way it really wants how is alias
analysis done actually with names it is
a fairly straightforward procedure let's
assume my language with recursive
procedures but no nesting of procedures
so if they are local parameters
aliases cannot happen so let us assume
that parameters are passed by reference
only number one step number one rename
the variables in procedures if necessary
so that all names are different so there
are no names which are being shared
across procedures all parameters dummy
and actual will have different names so
if there is a procedure P with
parameters x1 to xn and a call to P with
parameters actual parameters y1 to yn so
these are all call by reference
so there are only variables y1 - am
there are no expressions in place of
these variables now y1 and x1 are
aliases y2 and x2 are aliases yn and xn
are also aliases so we are going to set
the XA is an alias of Y a this is you
know a symmetric relation so if X a is
an alias of a a Y is also an alias ax X
I so we set this for all I this is an
equivalence relation really we take the
reflexive and transitive closure of this
alias relation and we get the aliases
for all the variables so let us take an
example so the G and H are global
variables procedure main has a local
variable I then we have assignment to G
we call one with H comma then there is
procedure one with two variables W comma
X X is assigned a value we call two with
W comma W and we call two with G comma X
so procedure 2 has a local variable K H
is assigned a value and then one is
called with K and Y so let's start doing
the earlier analysis on main so for a
Lea's analysis only procedure calls are
important so we go to the call 1 H comma
a H and I are local you know are
actually the parameter actual parameters
so let us take H in the procedure 1 it
corresponds W so H is alias of W let us
take I so I is
now alias effects so similarly if we
take this call W is an alias of Y and
again W is an alias of Zed as well right
so now in this case G's and Ilias of Y
and X is an alias of Z so that's also
correct now in this call K is an alias
of W and Y is an alias of X so these are
so now if you take the transitive
closure reflexive transitive closure we
see that all variables are aliases of
each other so you can dress that for
example H equal to W so W equal to Y so
H equal to Y and W equal to Z so H equal
to Z you know so then y equal to G so H
equal to G y equal to X so is equal to X
so H is related to all of them now so
one possible observable behavior is the
change set of a procedure so what
exactly is this change set so change of
P is a set of global variables and
formal parameters of the procedure P so
that might be changed during an
execution of P so we are going to look
at only reference parameters here not
local you know non called y-value
parameters are not considered and again
only global variables and formal
parameters can transmit effect outside
the function or procedure P so we are
interested only in the set of global
variables and formal parameters of the
procedure P so that might be change
during an execution of P so no aliasing
is considered at this point so this is
the set that we want to compute using
interprocedural analysis so when we are
computing P in this change of P we need
to consider the procedure calls within P
as well now this requires
three parameters so change of P will
require depth of P unless it called a of
P and the third one called G of P so let
us define them so change of P cannot be
computed once for all you know it has to
be done through an iterative process
what is def of P a set of formal
parameters of P and Global's
having explicit definitions within P so
not including those defined because of
procedure calls within P so we don't
worry about procedure calls within P
when we want def P we just take the
assignments to Global's assignments to
formals within P and that's the DEF P
okay so this can be computed it
statically once for all it doesn't
change because we are only looking at
concrete assignments to the Global's and
formal parameters so that's what I said
change B is def be Union ap using GP so
what is AFP so it's actually simpler to
show you a picture and then come back so
let's take a procedure P so in this body
it calls a procedure Q okay
so Q is here so when we call Q there is
a parameter a which is passed and this
is the actual parameter in this list
okay so now let us go to Q in Q there
are n parameters so VI is the ith formal
parameter you know so a and B a are the
corresponding parameters a is the a the
actual parameter bi is the eighth formal
parameter so now suppose VI is already
in change of Q okay so if bi is already
in change of Q then yeh will also be in
change of P so the reason is we are
calling Q B is definitely going to be
changed by VI is going to be changed by
this procedure Q so since VI and they
correspond to each other a will also be
changed when we call the sir Q so the
effect of procedure Q is
to change a so a goes into the change
set of P so yeah is a global variable or
formal parameter of P such that for some
procedure Q and integer I P calls Q with
a as the eighth actual parameter and the
eighth formal parameter of Q is in
change of Q so this is what I was
explaining now so we take the procedure
call take a particular parameter look at
the corresponding formal parameter of
that particular call if that formal
parameter is in the change of the called
procedure then we put this particular
parameter a also into the change set of
P another a set of P a goes into change
certainiy what is G of P so G is a
global in change of Q and P calls Q so P
calls procedure Q and Q we are now
looking at only global variables and Q
changes you know this G so it's in the
change set of Q therefore G will also
now be in the change set of P because P
is calling you if G changes in you it
changes in P as well so we use a
simplified calling graph whose nodes or
procedures we don't have call sites as
nodes there is an edge from P to you if
P calls Q somewhere in the program so we
don't have any node for the call site
okay so you all these are merged okay so
if there is some call from P to Q we
just say there is an arc from P to Q so
the input is a calling graph with a
collection of procedures P 1 P 2 P n if
the calling RUF is acyclic then we
assume that P I calls PJ only if J less
than I so some ordering is possible so
otherwise no assumptions so output is
change of P and it is assumed that def
of P is pre computed so we don't really
need this ordering it can be done as it
is also so what we really do is start
with change of P
FP that is the initialization then we do
a fixed point computation well changes
to any change P occur do so for I equal
to 1 to n for each procedure Q called by
P I so we are considering one procedure
P I at a time we look at all the
procedures Q called by API so now we add
G of PA eniac add any Global's in change
of Q to change of PA so this is adding J
of PA for each formal parameters now we
are looking at the computation of here
so say the jth parameter of Q if you X
is in change of Q then look at the call
Q by P if you a the Jets actual
parameter of the call is a global or
formal parameter of P I then add a to
change of PA so this is adding a of PA
so you look at the parameter look at the
the actual parameter and the
corresponding formal parameter if the
formal parameter is in change of some
you know change set add the actual
parameter also to the change set so this
is adding the a set to change okay so
this is a fairly straightforward
procedure so let us look at the same
example and trace it okay so we need to
worry about the assignment G is a global
there is an assignment in the main X is
a parameter so there is an assignment in
one and then H is another global with
there is an assignment in two and there
are a couple of fuzzier calls so here is
the calling graph main calls one one
calls to and two calls one so it's
recursive so we start with the DEF main
equal to GE change this is the same as
changement and similarly G main is Phi
and so on and so forth so suppose these
are the initializations so change to is
H change one is X okay so let us
consider that function to okay two calls
one so one is the call is one of K comma
Y these are the actual parameters K and
y1 of W comma X these are the formal
parameters of
the call the procedure one s'okay is a
local so we don't worry about the local
parameter at all local variable at all
so we are not going to worry about only
yn D X so X is in the change set of one
so see here so change set of one already
contain CX so Y will also be added to
the change set of two okay so now change
set of two already had you know H so now
we have added one as well that is
because of the asset so in this manner
we really consider one and then add the
appropriate parameters there is w w here
the y&z here so Y is already in the
change set of two so W is also added to
the change set of two and so on and so
forth so in this fashion we propagate
the change information from one color to
Cali in back to the color and finally we
go keep doing it because there is
recursion we keep doing it until there
is no further change so this is how the
change propagation happens so now let's
see how this change information is used
for the available expression analysis
there are two methods by which it can be
used so let's assume that each procedure
call is in a separate basic block so in
method 1 V is a block for the call to
procedure P so we assume that a gen of B
is 5 that means the procedure call does
not generate any expressions okay so for
all courses are called basic blocks so
what about kill if a variable B is in
the change set of P for this procedure
corresponding to this block then B kills
all expressions be involving B and it's
aliases so this is where the alias
information is becoming useful so how is
this possible
see you consider only those variables
which are changed by the procedure call
okay by that procedure call so only
those variables you know expressions
involving those variables will be killed
so that's very logical so a kill of B is
computed in this
fashion so here's an India kill for
other types of blocks of you know
computed as usual as we studied in the
available expression analysis so now we
know agent B and D ache will be for
procedure call blocks and now for all
other blocks as well computing in being
out B for all blocks in the whole
procedure no proceeds in the usual
manner so we had to know
so now agent is Phi of course but da
kill we could make a better guess look a
rather better estimate so hopefully our
available expression analysis would be
much better because now it incorporates
summary information from the procedure
calls so observed that we are using the
change information in computing a kill
and then we are right writing so this is
Method one in method to compute England
out for all basic blocks in all
procedures as usual after computing
agent and the AQL as in method one so
this is the starting point so after this
see we the previous method method one
gave us you know a slightly better
estimate for in and out of all the basic
blocks right now we use that as the
starting point now Soho a out at the
return point from a procedure P can be
taken as the agent P for a block with a
call to P so this is what I was saying
so what what is that that the procedure
can generate look at its return point or
the end point procedure end point and
you can now say that whatever was a out
at that end or return point is the is
the set of expressions generated for the
call block a you know and it is taken as
agent p for a block with a call to p no
aliases at this point again but we must
consider only those expressions in
layout with all their variables in
change of P obviously we should not
worry about expressions involving
low-calorie
and we also substitute actual parameters
for formal parameters and see what
expressions are generated by the column
so this is again necessary because we do
not want expressions with other
variables which are not in the formal
parameter list or you know in some other
variables involving locals etcetera
etcetera actual parameters are the only
ones which matter to us so we replace
actual parameters formal parameters by
actual parameters and then see see these
these are expressions involving actual
parameters and Global's
are the only ones which make sense in
the procedure after the procedure call
is over others don't matter to us so
that is why this is necessary so without
changing a kill for procedure call box
computations of in and out are now
repeated so now this procedure is
repeated until no changes occur it is
possible that by considering one
nitration you are feeding to some other
procedure okay so we go on doing this
until none of the values change in any
of the procedures so this is a little
more you know precise and gives you
better information than the previous
method and of course both of them give
much better information than you know
the one which uses no summary
information so this is the end of this
lecture thank you very much