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)
}

Example:

Entry Set // Definitions reaching A at its entry.

Share this