Question

Identify the define node, usage node, du-paths and dc-paths for all the variables.

int binsearch(int x,int v[],int n)
{
    int low,high,mid;

    low=0;
    high=n-1;

    while(low<high)
    {
        mid = ( low + high ) / 2;

        if( x < v[mid])
            high  = mid - 1;
        else if ( x > v[mid])
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

Answer 1

• Node: A node is a point, like a center or linking point, at which lines or paths converge or branch.
  • In this Program node Usage as follows: |_Low_|---> |_Mid_|--> |_High_|
• Du-paths: A definition-use path with respect to a variable v (denoted du-path) is a path in the set of all paths in P, PATHS(P), such that for some v ∈ V, there are define and usage nodes DEF(v, m) and USE(v, n) such that m and n are the initial and final nodes of the path.
  • Du-Paths in this program are int x, int v[], and int n.
  • Low Mid High( V, X ) and Usage Nodes: Low Mid High( V, N).
• Dc-paths: A definition-clear path with respect to a variable v (denoted dc-path) is a definition-use path in PATHS(P) with initial and final nodes DEF (v, m) and USE (v, n) such that no other node in the path is a defining node of v.
  • A du-path with no other defining node for v is a definition-clear path.
  • .