Data-flow Analysis - Part 3 Control Flow Analysis - Compiler Design Video Lecture - Computer Science Engineering (CSE)

welcome to part three of the lecture on
data flow analysis so briefly you know
reviewing what we did in the last two
lectures a data for value for a program
point represents an abstraction of the
set of all program states that can be
observed for that point and then you
know the we studied the reaching
definitions available expressions
problems in the previous lectures so in
both the problems we computed the in and
out sets you know which are the data for
values before and after each statement
the general problem of dataflow analysis
is to find a solution to the set of
constraints on in n dias for all state
machines
so there is a dataflow schema that we
have been describing for the dataflow
analysis problems so the schema consists
of a control flow graph a direction of
dataflow either forward or backward a
set of all data flow values a confluence
operator and some transfer functions for
each block so for the reaching
definitions problem you know the
direction of data flow was forward the
set of data flow values or the domain of
data flow values was actually the set of
for you know sets of reaching
definitions each set of reaching
definitions for the data flow value the
confluence operator was Union for the
reaching definitions problem so the
transfer functions really describe how
the out and in change so that's
precisely however we describe the
reaching definitions
similarly we describe the available
expressions problem as well
and the other important point is we
always compute safe estimates of data
flow values so what are these safe
estimates that really depends on the
application so it's a conservative
estimate so for example in the reaching
definitions case we may include more
definitions in the set of for reaching
definitions it says okay something may
not reach but we still want to include
it because we have not very sure where
as for the available expressions unless
and unless we are certain that the
expression is available at a point we
are not going to include it in the set
so in that process we may actually lose
some of the expressions which may
actually be available but a safe
estimate is always like that we were
discussing the live variable analysis
problem so what is the live variable
analysis problem so if if we say that
the variable X is live at a point P then
you know the value of that particular
variable at that point is going to be
used along some path in the flow graph
starting at P so if this does not happen
then we say that X is dead at P so the
sets of you know variables constitute
the domain of for dataflow values here
each data flow value is a set of
variables this is actually a backward
dataflow analysis problem and the
confluence operator is Union so when we
say it is a backward analysis problem
for example if you look at the control
flow graph here it does not mean that
the traversal of the flow graph is in
reverse order that's not the point
forward or backward flow does not mean
does not have anything to do with the
traversal of the basic blocks in a
particular order
in fact I must add here that the order
in which we traverse the data flow you
know our travels the basic blocks of the
control flow graph is immaterial the
same solution will be obtained
irrespective of the order of energy
basic blocks are traversed it is just
that there are some orders which give
the solution the solution very quickly
whereas some other orders may not give
the solution very quickly this is true
for both forward analysis problems and
also backward analysis problems so in
the case of live variable analysis in B
is the set of variables live at the
beginning of for B and out B is the set
of variables live just after the basic
block B the gen and kill correspond to
to the su 2 sets use and def so use B is
the gen set it is the set of variables
whose values may be used in B prior to
any definition of the variable and so in
the example here so use of B 1 is M in
and new one why because M and nu 1 are
used on the right hand side of the three
assignment statements before they are
assigned any values in fact they are not
assigned any values at all whereas in
the case of B 2 I and J are used before
they are assigned a value so you must
observe that even in the assignment
statement this is true ie is accessed
first and then the side in this case it
is just u 2 and in before it CN j def is
the set of variables definitely assigned
values in B prior to any use of that
variable in B so again very quickly I J
and J are assigned values and they are
not at all used so def be one contains
AJ and here in the case of for b2 there
are no variables assigned values before
they are
you realize for example this I is the
old I and this is the old J as I
mentioned before so this sceptred F of B
2 is null a is assigned here if and
therefore it is you to a it is yet and I
either sign here so def of before is I
so this is how the values are really
computed so only this is an exception
IND are already used before they are
assigned any value so f of mu 2 is fine
the equations are here out B is the
union of the in values of the successors
of the basic block B and in B is as
usual you know it has the gen part and
then the heel part here so use B well
you know an Union out B - def B so let
us understand why these are really
correct this is easy to understand how
would be equal to Union of in yes see
you are really looking at the backward
flow analysis problem so when we compute
the out of a basic block B we are
looking at the successes of B for
example here we want to compute the out
of B - we are going to look at the in
sets of B 3 and B 4 so the idea is if
any variable is live here or here it
will be live here because what we want
is just a path any path will do there is
a path along this direction and there is
another path along this direction so we
take the union of these two sets that's
the reason for the Union and what about
the inside so here let's again take the
case of B 2 it says whatever is
generated within the we are given out
and we want to compute in
he want we are given out and we are
computing in that's why this is a
backward flow analysis problem so
whatever you know is used before
definition is definitely alive at this
point in other words because there is
going to be a use inj whatever values of
I and J are defined here are being used
in these two right that's why I and J
arrived at this point that is the used
component and then there may be other
variables which are live at this point
but the may or may not be killed that is
if they are defined then you know there
is no way we can really use them so if
you look at the out of B - it is you - E
and J so nothing is you know Def of B 2
is 5 so these 3 are not really killed so
i Ju - and they are all included in the
inset of B - lets verify it and see
whether it is correct I ain't here of
course correct because I value of I here
is used here and J is used here value of
u 2 is used here there is no definition
of u2 along this path and value of EI is
used here right so and value of J this J
is different okay J is defined here but
there's already a J here so we are only
considered a ball considering a the
variables and not the statements at
which it is used
so you - i Ju - and they are all live at
this point so if you look at the inset
of b3 for example you know u2 is
definitely alive at the entry point of
b3 at this point because it's visible
straight away from the top and let us
take the out of b3 at this point right a
and you - AJ into - so now you know the
DEF contains here so a is defined before
any use so we
removing a is not live at this point
whereas J you know and you too
okay so that that's the J and you two
are included in the inset okay so that's
how the Lyle the in sets for the live
variables are computed so I hope this
gives a flavor of how the backward flow
analysis happens it really does not
matter I can do B one first then V 2
then V 3 then B 4 and I keep doing these
computations of in and out use and
Deffer computed only once we keep doing
these computations of in and out until
all the values of in and out stabilize
so the iterative analysis algorithm for
backward flow analysis is very similar
to what we had given for live variable
analysis and I'm not going to show that
again the same loop with change etcetera
is used the equations are computed
inside the and then you know
stabilization is achieved by changing
the variable change so that's as far as
live variable analysis goes now there is
another information that's very useful
these are the do chains or the
definition use chains
so for each what is the what is the D
you chain for each definition we should
consider all the users of that
particular obsession what do you mean by
the users of a definition each
definition actually defines a variable
and then we are looking at the uses of
for the variable involved in that
definition but then you know that
particular variable should not be
redefined before usage so that's what we
really mean by uses of that particular
definition such information is very
useful in implementing register location
loop invariant code motion etcetera
etcetera because we want to you look at
the uses of a definition you just have
to go down the chain from starting from
the definition
and then you get all the uses so this is
a very useful piece of information we
have seen that the do chain information
is very useful in creating webs and then
doing register location via coloring
this problem cannot be solved using live
variable analysis the reason is simple
live variable analysis actually computes
sets of variables only it does not worry
about the statement numbers where the
variable is used whereas in the case of
definition use chains we want to use the
statement numbers also so the problem of
computing do chains can be transformed
to the ever to a new data for analysis
problem which is very similar to that of
live variable analysis so this problem
is that of computing for a point P the
set of uses of a variable say X such
that there is a path from P to the use
of X that does not redefine X so it's
similar to the live variable definition
it is just that we are computing at the
statement numbers also so that's why the
sets of users come into picture so we
are associating with each X you know a
statement yes also so the information is
represented as sets of Axios pairs where
X is the variable used in statement yes
so the dataflow equations are very
similar to the tough Elvia analysis I am
going to show you those and once the in
and out sets are computed new chains can
be computed quite easily like the URI
chains so in this problem the sets of
pairs X comma s constitute the domain of
dataflow values whereas in the library
bananas's it was just the sets of
variables this is also a backward flow
analysis problem and the confluence
operator is Union exactly like in the
live variable analysis problem
what about the gen and kill that is the
use and f so it there is a slight
modification USB is the set of pairs XS
such that there is a statement of envy
which uses variable X and such and such
that no prior definition of X occurs in
B so here as I said we are tagging along
the statement number of the use also
there we only worried about the use will
before the definition def is similar def
B is the set of pairs x comma s such
that yes is a statement which uses X but
yes is not in B and V contains a
definition of X so V contains a
definition and it obviously kills all
other users which are outside the basic
block B you know remember recall
reaching definitions so that's the way
we are doing it here look at all users
of 4x and the S should not be the
statement in which it is used is not in
B and B contains the definition of X so
let's see a small example here the same
live variable analysis problem we have
numbered the statements as s1 s2 s3 s4
s5 s6 s7 so use of b1 right so we are
looking at use before definition so M
comma s 1 n comma s 2 and u 1 comma s3
very simple here it is I comma s4 and J
comma s5 here it is
u2 comma s6 and finally here it is a
comma s7 and J comma s7 the DEF part I
is defined here so it is deemed to kill
all others in these blocks so I comma s4
so that's a statement which is outside
the block which uses I J comma s5
another one J comma s7
third wave SH and a comma is 7/4 usage
so these are the four usages of the
variables here so they are all which are
defined here so they are all killed
that's the DEF part whereas here
therefore B 2 is J comma s7 so J is
being defined here right and J is the
usage here so that's why the DEF part
come is here now the eye part does not
enter this def because for this
particular definition you know there is
no other usage that is going to be
killed
okay so that's why you know this is not
being considered okay and then def for
for B 3 we are assigning ya here right
so yes seven uses a so that's why a
comma s7 is here okay so that's the
difference and then def of before is I
comma s4 so yes 4 is here so IE is
defined here so I comma s4 is this
particular thing okay so that's how so
this is the usage of I okay this is the
definition of I so if you look at this I
there is no other usage of I you know
these are all definitions this usage is
not considered because it's within
that's why I comma something was not
included in def of me too
so this is how we compute the deficits
and new sets so now let's look at the
equations out B is union of the in sets
of the successors of me and in V is used
B Union out B - def mean these are
identical to the live variable analysis
problem so in B and out B are the set
software's X comma is such that
statement yes uses the variable X and
the value of x set in B or out B has not
been modified so it's very similar to
the definition of this
thing okay so here's let's look at this
so let's see let's look at the out of B
1 so I comma s4 J comma I comma s4 is
here so this is a usage let us say the
value of I that's away you know that's
live at this point is that of s1 so I
comma s4 uses this and then the value of
J that is relevant here is that of s2 so
that's being used here and then you know
u2 comma s6 whatever was the initial
value of u 2 is used here and then a
comma s7 so whatever is defined here is
used here okay so there is another part
which is the redefine but there is also
one path through which it is defined so
that's why the would be contends b1
contains all these sets enough b1 you
know is here right so obviously M comma
s 1 mu is used in s 1 the N comma s 2
and u 1 comma s 3 are in this particular
set in and then the a comma s 1 s 7 is
here so that's also actually sorry you
to come is six I was looking at the
wrong set u 2 comma s6 is here so
whatever was the initial value of u 2 is
used here so these are the only sets
which which actually get into enough
pairs which you get into enough V 1
similarly we will take just one example
say out of before so out of before will
contain a comma s7 I comma s4 J comma s5
and u 2 comma s6 why because of this arc
so a comma s7 so the a comes back
through this path I comma s4 so it goes
there J comma s5 so thats again goes
here and u 2 comma s6 which again
travels here so these are all in the out
set in set again contains a comma s7 J
comma s7 and u2 comma yes
six it does not contain you know I
because I is actually defined here
therefore there is no way it can this
old value of Phi which is relevant here
can go back okay so this is how the in
and out sets are computed so I also have
to show you how the new chains are
computed so this is a very simple job so
let's take each definition I come eyes
when Jacob minus 2 etcetera the
information of out sets that is computed
is used in computing the D u chain so
take I come is one that is here right so
for this the what is the deal chain it
should actually be s4 because that value
is used in s4 but how do we actually get
it you know look at the outer for out
set of v1 okay that's at this point it's
the only definition here is I comma s4
and then along this path okay so
whatever is here there are no other
definitions of I here
so we attach I comma s4 to this
particular s1 so that is s for how about
J comma s 2 so the C it is very similar
J comma s5 is in the outset so that's
the only one which is possibly a usage
there are no other definitions of J
after this particular statement J equal
to n so s5 is attached
similarly s7 is attached to a comma s3
let's look at I comma s4 so I comma s4
has I many of them but it has no pair
corresponding to I that is because the
variable value which is here you know is
redefined at this point and this is not
the same well as that defined in s4 so
whatever is defined in s7 is used here
and not what is used in and defined in
s4 that's why the do chain of Phi I
comma is 4 is 5 what about J comma s5 if
this is different see there is no other
definition of J so look at
the outset of b2 it contains J comma s5
and J comma s7 so J comma s7 is here so
it's included into the D you chain from
this particular thing and because of
this path the value of J here is what is
computed here so J comma s5 also gets in
so S 5 and s 7 are both on the D you
chain for a comma s6 which is here right
so the S at the outset contains C a
comma s7 so that's the only one which is
attached to this a comma s7 contains S 4
so that is here so that's the one which
is included which is in the outset so
this is formalized in this particular
figure here if there is a definition of
B that is def d1 and there are no
unambiguous definitions of be here till
the end of the basic block then attach
to do chain of this d1 all the
statements yes of all the used space B
comma s I in out B so all the statements
here say for all the pairs become is a
in out of me that's what we did here we
took all of them corresponding the to
the variable B and attach them to the
definition do you so if you take the
second case then there is a definition
of B here and then the usage of me here
right and there are no other unambiguous
definitions of V inside so this
definition now gets only this use so
attach use u1 to do chain of d1 this is
the definition B and there is another
ambiguous definition of B which is let
us say D 2 and then there are no other
unambiguous definitions of B here so
here is the use of B so because this is
ambiguous we have no idea whether it is
correct you know it is going to happen
or it is not going to happen so we don't
want to miss out on the information we
are going to attach the use u one to
both these d1 and d2 that's what is said
here
so very busy expressions or anticipated
expressions so this is the next dataflow
analysis problem that we are going to
tackle so for example consider this
picture there is a point P then you know
from along every path starting from P we
have ax equal to B op C y equal to B op
C and Z equal to B op C B op C is being
computed along every path starting from
P so such an expression B op C is said
to be very busy if there are no
definitions of B or C along any of these
paths so an expression B op C is very
busy or anticipated at a point P if
along every path from P we come to a
computation of B op C before any
computation VRC so this is you know very
busy expression is useful both in code
hoisting transformations and also in
partial redundancy elimination
transformation so what is code hoisting
so it says if you know B op C is very
busy at P white should we really compute
it here you might as well compute it
here so this is the code hoisting that
takes place for B of C so we compute T
equal to B op C right here into a
temporary T and then just assign X equal
to D by equal to T and Z equal to T
there is no saving in time here in this
code hoisting because B op C is computed
exactly once but there is saving in
space there is the cour for B op C need
not appear in three places so we but we
must make sure that you know the there
is no redefinition of either B or C
along any of these paths you know
with that's the only thing that and
secondly we must make sure that no more
definition of BRC reaches any of these
things without passing through B's so
that in other words if there is another
definition of B which comes here and one
comes through this path then the B op C
here will be very different from any of
these so that should not happen so how
do we really define a dataflow analysis
problem for very busy expressions as
usual the sets of expressions constitute
the domain of dataflow values here so we
have seen that already and this is a
backward analysis problem why look at
the equation in is defined in terms of
out the confluence operator is in you
know sorry the intersection so out n is
intersection of in es various is a
successor of n why are we using n here
just that B op C is the expression we
are looking at so using B here would be
confusing there's only reason what about
we use an Vida we use corresponds to the
gen set and we def corresponds to the
kill set so we use is the set of
expressions B of C computed in the N
with no prior definition of V or C in
the N so this is very similar to the
live variable analysis problem where we
had a usage before any definition so
this is a computation of V of C before
any definition of me or C and what about
we def the set of expressions B op C in
the universal set u of expressions for
which either B or C is defined in Ian's
prior to any computation of V op C so we
are see one of them is given a value
okay and then B op C is computed so that
constitutes you know the kill set
because
what happens is once BRC is defined in
the basic block then you know the
previous value of B op C is not very
useful to us anymore
so that is why when we look at this
equation computing in videos we include
in the inset because these are visible
expressions so B op C computed in yen
without prior definition of PR C so
whereas out n minus V Def make sure that
all those expressions whose variables
were defined first and then the
expression computed are kind of killed
they are removed from the outset so and
then as in any problem with intersection
as the confluence operator the in is
always initialized to the Universal set
for initialization purposes this way
gives us a much bigger set for in and
out rather than you know compared to
when we use Phi here is a very simple
example love for anticipated expressions
or very busy expressions so if you
consider the expression A plus B there's
only one here so at the point 1 and also
the point for a plus B is anticipated
because a plus B is inside the basic
block it is being computed and we are
not we have not defined a or b here
if there had been a definition of a or b
just before this computation then this
would not have been anticipated at this
point ok so that's how it is and at any
other point a plus b is not anticipated
why let's take say three along this path
a plus B is computed no problem
but along this path a plus B is not
computed that's the reason when the it
is not anticipated either at this point
or this point or any of these points for
that matter the situation is very
different here you start you know you
take a plus B look at any point there is
a computation of a plus
follow along all paths so here of course
a plus B is already computed inside and
it is not killed so it is anticipated at
this point if you take this point there
is only one part leading out so and
along that path a plus B is computed
again right so along this path there is
anticipation of a plus B and at any
point here this or this or this we can
take this we can of course take only
that part and a plus B is computed at
this point so this makes it anticipable
at every point in the flow graph so we
will see how to use anticipated
expressions in partial redundancy
elimination in one of the later lectures
now let us summarize dataflow analysis
problems that we studied so far we first
studied the reaching definitions problem
the domain was sets of definitions
Direction was for words confluence
operator was Union initialization was in
B equal to 5 and equations were in B
equal to Union of out P where P is the
predecessor of B out B is gen B Union in
B minus kill B then we studied the
available expressions problem sets of
expressions for the domain of dataflow
values for word problem confluence
operator intersection initialization in
B equal to U and equations were in B
equal to intersection of out P P being a
predecessor of B and out B is a gen B
Union in B - equal B in B one was always
Phi ok and the initialization for all
other blocks is U the live variable
analysis problem is a you know in one in
which the dataflow values are all sets
of variables and Direction is backwards
confluence operator is Union the
initialization is in B equal to 5
equations are out B equal to Union of
Indians yes being a successor in B equal
to use B Union out view - def be the
last one in the matrix the fourth
combination
I anticipated expressions which we just
now studied sets of expressions
constitute genuine of data flow values
backward problem intersection confluence
operator in V equal to u being
initialization now to be is intersection
of any s s being a successor and in we
use we use Union or P minus V definitely
so this constitutes a summary of the
data flow problems now we will move on
to control flow analysis so welcome to
the lecture on control flow analysis in
this lecture we will see why control
flow analysis is required and then we
are going to study dominators and
natural loops intervals and reducibility
t1 t2 transformations and graph
reduction and then the concept of what
are known as regions see the dataflow
analysis that we studied you know in the
last lecture tells us how the values
flow through the control flow graph the
control flow graph was given to us but
then we only talked about loops branches
and things like that in the control flow
graph but there was no structure of the
control flow graph such as loops and
branches that we understood formally
control flow analysis really helps us to
understand the structure of the control
flow graphs so for example we want to
formally define what exactly are the
loops in a control flow graph and if we
don't do this we will not be able to do
the optimizations which are meant for
loops so formulation of the you know
conditions for
code motion these use the concept of
autonomous dominators so Dominator
information is computed by control flow
analysis then I mentioned about the
intermediate form called static single
assignment form so the static single
assignment form requires information
known as dominance frontier so control
flow analysis is going to build this
information compute this information we
will study dominus frontiers along with
the static single assignment forms then
control flow analysis also tells us how
to determine the interval structure of a
control flow graph and use this interval
structure for carrying out dataflow
analysis the data flow analysis we did
so far is called I'd rate is called
iterative dataflow analysis whereas
there is under school of thought which
uses interval based dataflow analysis so
interval structure enables such interval
based dataflow analysis and then control
dependences which are essential for
parallelization and concurrentization
they require control flow analysis
dominance frontier a Dominator
information etcetera so these are the
reasons why we must understand control
for analysis thoroughly so let us begin
with the most important concept of
dominators so what exactly is a
Dominator so a node en node D in a flow
graph dominates a node N and we write it
as d da Mian if every part from the
initial node of the flow graph to n goes
through D so let me show an example and
explain
question let us say to be asked is does
v1 dominate v6 so the answer is yes the
reason is we are going to look at the
paths from the initial node that is B
naught and then to the node v6 so and
make sure that every path through to
from B naught to be six passes through B
1 so from here we go like that and reach
music's so we must compulsorily pass
through v1
in fact b2 also dominates b6 we will be
not also dominates b6
but before definitely does not dominate
basics because there is no path to
basics itself actually b7 is very
interesting
neither of b5 and b6 dominate b7 why
let's take the definition again it says
starting from the initial node going to
be seven every path must pass through b5
well now if I say B Phi dominates b6 I
will take the path from B not pass
through b1 b2 b3 b6 and Beach reach b7
so I bypassed by b5 but if I say b6
dominates b7 I will take the path
starting from B not pass through b1 b2
b3 b5 and then reach b7 I have bypassed
v6 but b3 definitely dominates b7
because no matter what I always have to
pass through B 3 and then go to b5 r b6
and reach b7 so b3 definitely dominates
b7 the initial node is the root and each
node dominates only its descendants in
the tree so we are out there we are
going to represent the Dominator
information in the form of a Dominator
tree so this is the root of the tree
this is the initial node which always
dominates all the nodes in the tree and
the way the tree information is
maintained
each no dominance only its descendants
so for example beaver b1 dominates all
these notes but it does not dominate be
not so you can easily see that b3
dominates b5 b6 and b7 so all these
three are children of b3 and therefore
you know this Dominator information is
very compactly represented in the tree
the node X strictly dominates way if we
X dominates y and X is not equal to Y so
self dominance is eliminated then it
becomes a strict domination X is the
immediate Dominator of fight denoted I
Dom Y if X is the closest closest strict
Dominator of Phi so in other words you
know if you look at the this year so
Beto immediately dominates b3 b2
immediately dominates before but Beto
does not immediately dominate v6 whereas
b3 immediately dominates b5 b6 and b7 so
this is so the tree actually shows only
the immediate Dominator relationship so
that's what is said here and what is the
principle of the nominator algorithm so
if P 1 2 PK are all predecessors of a
node n and d is not equal to n then
determine if and only if so note that
this is a necessary and sufficient
condition D Dom PA for each I so if
these are all the predecessors then the
node D must dominate all the
predecessors otherwise D will not
dominate n so let us check that out so
this b7 has two predecessors all of all
the others we will see later
b2 also has two predecessors so there
are two nodes b5 and b6 which are
predecessors of b7 right so now if some
node has to dominate b7 the result says
it they must eat the same node must
dominate both b5 and b6 well this is
true so look at the tree here
so B 3 B 2 B 1 and B is not all of them
dominate b7 so so here for example if B
3 you know so b3 b5 and b6 okay they do
not dominate b7 that's why this
information is not true so if you know
if one of them actually were dominating
this then in that would have been
dominated by these ok so let's take B to
its predecessors are B 1 and B seven so
let us take B to hear only be one
dominates B - okay so because b1
dominates both you know they all both
the predecessors of b2 that is b1 itself
and also b7 so this is how we use this
Dominator information rather the theorem
in order to construct dominators so let
us look at the algorithm for
constructing dominators it is actually
an algorithmic form of the same theorem
so the notation is DN equal to o TN for
all the N Union okay so we compute the N
and that is the out you know rather we
compute out yen and that is the
Dominator information of yen if not is
the initial known and n is the set of
all nodes so initialization and
permanent assignment OT n naught is en
not okay and in for the N in n minus n
not out n equal to and this is
initialization right so then see the set
of dominators of n is what is given by
DN so the set of dominators are for
naught is just your not n naught is the
initial node and it can never be
nominated by any other node so will
changes to any out in or Indian occur so
this is very similar to dataflow
analysis
recall that for all the nodes in the n
minus you not do so
Indian is this is that from the theorem
intersection of out PPA processor of P
again and then out n is n Union in the N
so it's a very simple data flow analysis
let us apply it on this particular
example initialization out of b12 b8 is
V not to V 8 that is capital n all the
nodes in the graph out of B naught is V
naught so they're just for this
particular node and then interaction one
enough B 1 okay so this is in it has
only one predecessor so it becomes out
of B naught that is B naught itself
right so then you know out of B 1 is V
naught comma V 1 okay so there is no
other possibility so so the then we have
see this is initialization is very
important here because out of B naught
has been initialized to B naught that is
why enough p1 gets out of B naught and
that's only one element if this had also
been initialized to capital n we would
not have reached the solution at all
enough V 2 that is here it has two
predecessors one is b7 otherwise B 1 so
we take the intersection so out of B 1
is B naught b1 out of b7 is B naught to
be 8 of course the intersection gives us
B naught b1 itself and the out of b2 is
including this node now V naught V 1 and
V 2 so they call that oh 10 is in the N
Union in Yin similarly we go on with
iteration 2 enough B 2 is over enough B
3 right iteration 3 enough b3 there's
only one more coming here so it's very
simple it's out of b2 that is B naught V
1 V 2 out of B 3 is including this into
the set V naught b1 b2 b3 right now
enough before and on this side is again
the same V naught V 1 V 2 and out of
before you improve before into the
so B naught b1 b2 before iteration for
enough b5 again it has only one element
one edge coming from B 3 so we get out
of b3 and that is same as enough b6
along this direction also and out of b5
you include b5 into it out of b6 we
include b6 into it and on this side you
know out of b8 is just B naught b1 b2 b4
+ b8 right along this direction this is
interesting enough b7 must take the
intersection of these two so these two
automatically got out of we were in Phi
intersection out of b6 so one of them
contains b5 the other one contains b6 so
out of b5 contains B 5 out of b6
contains b6 but both of them do not
contain b5 basic so it goes out the only
ones which remain are B naught b1 b2 b3
and finally out of b7 is B naught b1 b2
b3 and itself b7 now for the second
iteration now b7 has out of p7 has
changed so enough for B to B comes out
of b1 intersection out of visa and it is
the same as B naught b1 so there is no
change it so happens that the order in
which we have visited everything has
stabilized as we went along okay so but
only thing is we still have made 5
iterations if we had carried out you
know from bottom marcin if we had not
used this we would have actually done
even is one more number of rotations
possibly okay so we did this first then
this then this then this then this and
so on so we have done in you know what I
am assuming is we did this and then any
other so all of us should not change
then we did this and any all of this
none of them really change and so on and
so forth okay now
so we now that we have computed the
Dominator information let me show you
another bigger example this has been
adopted from my Jose Tillman's book
which is called as the dragon book a
huge graph here and this is a start node
ok so now if you look at it one
dominates all nodes that is a by
definition now why does one dominate six
for example one dominates six it says so
obviously since one is the route every
path must start from one but let us look
at something more interesting for
dominates 10 so four dominates ten so
that means starting from one all paths
to ten must go through four which is
very obvious it you know if we go like
this and then branch this way or this
way we go like this end like this
so that's very simple
so the Dominator tree is mentioned here
so four dominates nine and so on and so
forth we just look at the path starting
from the start node and then we go on to
that particular node if it is traversed
in every path then it is dominated by
that particular node
here we have changed the structure of
the flow graph see here we have this
edge here we change it to the other one
the this the rest of that just did not
change so the Dominator relationship
also has not really been affected okay
so minor changes in the graph do not
affect the Dominator information now now
that we have defined dominators we are
ready to define what exactly are called
back edges and natural loops edges host
dominate her head staminate their tails
are called back edges so let me show you
a simple example so for example in this
tree we know that for dominates seven
so there is an edge from 7 to 4 so
that's called as a package the packages
are all listed here 7 to 4 is a back
edge that is because four dominate 7 10
to 7 is a back edge because 7 dominates
10 4 to 3 is a back edge because 3
dominates 4 10 to 3 is a back edge 10 to
you know 3 right so then from here to
here right because 3 dominates 10 11 to
1 is a back edge because 1 dominates 11
all that is clear from the diagram so
given such a back edge n2d now we are
ready to define the natural loop of a
package so remember we do not know
anything about the loop structure of the
control flow graph we are now trying to
discover such a loop structure and loop
structure is defined with respect to
packages for every package there is said
to be a natural loop the natural loop of
the edge that is n to D is the node D
plus the set of nodes that can reach n
without going through D so in other
words you know n to D is the back edge
it was the backwards so starting from D
which is supposed to be the header of
the loop we want to travel to n so you
look at all the nodes through which
meaning we can travel to n but those
nodes cannot include D again ok so
that's what this is really saying so if
you look at this so let's say we are
looking at this particular 10 2 3 all
right so we start from 3 we want to go
to 10 we look at all the nodes through
which we can reach 10 ok and include
those nodes so 3 4 5 6 7 8 10 so they
are all included 3 4 5 6 7 8 and these
are all the nodes which we travel but
what is not intuitive is the
natural loop of the edge for two-three
okay so that must be studied only with
respect to this particular algorithm so
these the header of the loop the
properties of such a loop are there is a
single entry point to the loop that
dominates all nodes in the loop and at
least one path back to the header exists
that is along the n2d okay so that's D
is the Dominator and n to D is the path
back to the header so at this point we
will stop for this lecture and in the
next lecture part of the lecture we will
study an algorithm to find the natural
loop of a back edge and then go on to
the other users of Dominator information
thank you
you