Algorithm to find the Control dependeny using PostDominator tree in llvm
The given function finds whether there exist a control dependency between the given two basic blocks. The function returns true if there exist a direct or transitive control dependency between the blocks otherwise it returns false. Given function finds whether block Y is control dependent on block X or not. Initially we will call isControlDependent(X,Y,Y)
set controlStack;
bool isControlDependent (basicblock X, basicblock Y, basicblock Z)
{
controlStack.insert(Z);
if( (Z==entry) && (X!=entry) ) // entry is the entry block
{
controlStack.erase(Z);
return false;
}
if ( (isPostDominated(Y,Z) || (Y==Z) )
{
if(X==Y)
{
controlStack.erase(Z);
return false;
}
for( i=0 ; i < numpredecessor(z); i++ )
{
if not exists ( controlStack.find( Z.predecessor(i) ) )
{
flag = isControlDependent( X, Y, Z.predecessor(i) );
if(flag==true)
{
return true
}
}
}
}
else if(Z==X)
{
return true;
}
else
{
flag = isControlDependent( X,Z,Z );
if(flag==true)
{
return true;
}
}
controlStack.erase(Z);
return false;
}
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment