Introduction to Data Flow Analysis

hi i'm fernando pereira and today i shall introduce the notion of a data flow analysis this family of static analysis is perhaps the most used form of static analysis in compilers in general so i hope this class will be useful to you there are many kinds of static analysis that can be described as data flow and we will see some of them in this class something that's very important about them is that they are all flow sensitive do you know what that means well basically this family of data flow analysis consider the order in which

instructions exist in the program their relative order between them is important to the result of the analysis this importance comes from dependence relations that means that some instructions depend on others but what does it mean for instruction to depend on another to explain this notion of dependency let's consider two instructions the first two in this example this arrow on the right side indicates a dependency between them whenever we have two instructions so that the second uses some variable defined in the first then we say that the second instruction depends on the first in this particular

example the variable percent c and p is causing this dependency do you see why because these dependencies are so important data flow analysis are typically implemented in some data structure that is expressive enough to encode the program's control flow graph notice that we do not really need the cfg to run a data flow analysis we can do it just with the syntax of instructions yet having the cfg is useful because it gives us many ways to speed up the resolution of the analysis as we will see later in this course for instance we can run

analysis on the loops that form the cfg instead of running them on the entire program but that's enough with abstract concepts let me show you a concrete example of a data flow analysis and then everything will be clearer i hope as an example i would like to derive some data flow information from this program we will represent this program via its cfg here on the right is the cfg of our target program so i would like to answer the following question how many registers do i need to compile this program in other words i would

like to perform register location on this program to get the necessary information to the register location we will need to run a data flow analysis this analysis will give us the information to know when we can store two variables in the same register and when such is forbidden this data flow analysis that gives us this kind of information is called liveness analysis we say that a variable call it v is alive at a certain program point p if there is a path from p to a program point where v is used and along this path

we do not need any redefinition of v and a variable should be stored somewhere at every program point where this variable is alive in other words if a variable is alive at the program point p then this variable must reside in a register or a memory i mean any physical location at that program point that is to say that the variable needs a location now i wish you could stop the video for a moment and then think a bit about the second condition why is it really necessary what would happen if the variable were redefined

to understand a bit better the answer to that last question let's try to see where variables are alive in our original program can you try to fill up these sets on the edges with the question marks with the variables that you think are alive at those points you can stop the video to think about this problem if you want for instance which variables are alive at this point here in the red box it's hard to answer this question without looking at the entire program but let me simplify the question is there any variable that you

know for sure that's alive at that point well variable x must be alive there because it's used right after so there's a path from the program point until a use of x that does not process and definition of x same thing is true for y so all the variables used at the instruction are alive right before that instruction indeed this is true in general if i have an instruction that uses a variable v then visa live before that instruction i mean immediately before this adverb immediately is important because it means that there is no place

for a redefinition of v along the way this path is too short for this redefinition but what about other variables i mean which other variables are alive right before some instruction well we can try to think a bit a bit about this problem iteratively if a variable is alive after instruction and it's not redefined by that instruction then it's alive before the instruction in other words we have an information system in which information propagates backwardly along the directions of the edges in the program cfg we call this kind of analysis a backward analysis now what

do we do about the join point i mean what about program points that have multiple successors how do we compute the variables that are alive before a joint point we simply take the union of all the variables alive before the successors to solve a data flow analysis we need to store information somewhere this information is like a map that maps program points with sets of live variables for that we associate with every program point two sets we call them in and out so n is the set of variables alive before a program pointing out the

set of variables alive after that point this means that for every program point to have two sets and we consider in this case every instruction as a program point so we shall associate with every instruction to set in and out and when we solve the data flow analysis we will have the sets field with variables the variables alive at those points we can define the sets by millions of equations if we consider the equation for the inset it's saying that the inside of a given instruction that defines a variable v and uses variables in expression

e is built as follows any variable used in the instructions alive before it that's the first thing to know also every variable alive after the instruction is alive before it these of course unless the variable is defined by the instruction in other words an instruction kills variables that it defines and to compute the outsets we join the insets of all the successors that's what this equation is saying if you want you can stop the video and take a look into the equations to try to understand what they say anyways how do we solve these equations

we can solve them by simply evaluating them over and over until the in and out sets stop changing that of course poses many questions for instance how are the in and outsides initialized and how do we know that this algorithm would stop i mean our condition is iterate until the in and outside stop changing how do we know that eventually they really stop changing well let's take a look into some examples before we try to answer those questions so here you can see a program in the different equations that we have for this program notes

that each in and out set gives us an equation so we have twice as many equations as we have instructions in the program once we have the equations we can even throw away the program all that we need to solve the analysis the system of equations it's a very declarative way to describe an algorithm the equations are the instances of the data flow analysis and the solution to those equations is a solution to the data flow analysis this is so declarative that we can solve these equations using some declarative programming language very easily for instance

here on the right the same set of equations this time written in prolog a declarative programming language don't worry you don't have to know prologue to follow this course but perhaps just for the sake of it you want to stop the video and then see if you can find some correspondence between the equations on the left and the right sides of the figure just to help you out here's a correspondence between the original equations and its version written in prolog again don't worry you don't have to know prolog in this course this is just to

show you that the set of equations gives us indeed a true program if you want you can stop the video again and try to figure out why these two notations describe the same thing and mind it that i can even run the prologue equations we have four program points in our example i'm calling them one two three and four the integers one two three and four in prolog so i can check what are the in and outsides associated with each program point but if you check the solution of the prologue equations you will see that

they correspond to the expected solution of the liveness analysis and then we with all these new concepts that you've learned perhaps you want to take a look into the original example again could you try to solve liveness analysis for this example i'm sure you could but just in case here's a solution of life is analysis forbes example you can stop the video and check that the results are indeed correct and this discussion closes our first class about data flow analysis there is still much to see in the next classes we will talk about different kinds

of data flow analysis until there feel free to write me with questions or comments