Reaching Definition Analysis

While debugging a program, determining the possible values of a variable can be very helpful. Reaching definition analysis can be leveraged for finding out these possible values. It is a May Analysis, which means there may exist a path from which a definition may reach the particular program point.

The Reaching Definition for some instruction or program statement A are all the previous definitions that may that instruction A. A definition can be written as:
[var=expr]A 
       Where var is a variable or expr is some expression, value or some other variable.


Example: 

 

Entry Set          // Definitions reaching A at its entry.


int reverse(int n)              // . is for unknown sources or the argument variables
{                                      //  ? is for uninitialized variables
int i;
[int rev=0;]1       //(n,.),(i,?)    
[while(n>0)     //(n,.),(i,?),(rev,1),(rev,4),(i,3),(n,5)
{
[i=n%10;]3         //(n,.),(i,?),(rev,1),(rev,4),(i,3),(n,5)
[rev=rev*10+i;]4      //(n,.),(i,?),(rev,1),(rev,4),(i,3),(n,5)
[n=n/10;]5            //(n,.),(i,?),(rev,1),(rev,4),(i,3),(n,5)
}]2            
}

                                                                                                                 Entry set                Exit Set              //Definitions reaching A at its exit

 

int reverse(int n)                                                                          
{
int i;                                                                                                        
[int rev=0;]1       //(n,.),(i,?),(rev,1)    
[while(n>0)     //(n,.),(i,?),(rev,1),(rev,4),(i,3),(n,5)                                     
{
[i=n%10;]3         //(n,.),(i,?),(rev,1),(rev,4),(i,3),(n,5)
[rev=rev*10+i;]4      //(n,.),(i,?),(rev,1),(rev,4),(i,3),(n,5)                              Exit set
[n=n/10;]5            //(n,.),(i,?),(rev,1),(rev,4),(i,3),(n,5)
}]2              //(n,.),(i,?),(rev,1),(rev,4),(i,3),(n,5)
}