Algorithm to find the Control dependeny using PostDominator tree in llvm

undefined undefined


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


4:24 AM | |

 

0 comments:

Post a Comment

Subscribe to: Post Comments (Atom)