[LLVMdev] Walking all the predecessors for a basic block

[Prabhat Kumar Saraswat]

Hi,
    I managed to solve the problem. It was stupid of me to use the
iterator object directly as basic block. I managed to dyn_cast to
BasicBlock and it works just fine.
 And it works perfect, prints all the predecessors for the basic block.

Thanks alot again.

Regards
Prabhat

PS : The working code is below:


 #include "llvm/Support/CFG.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"

     virtual bool runOnFunction(Function& F) {
         //for each function iterating over the basic blocks
       for (Function::iterator b = F.begin(); b != F.end(); ++b) {

BasicBlock* BB = dyn_cast<BasicBlock>(&*b);

       for (idf_iterator<BasicBlock*> I=idf_begin(b); I!=idf_end(b);
++I) {   // for each basic block walking over the predecessors in the
 graph
   BasicBlock* B = *I;
   }
>  }
> }


On Jan 23, 2008 10:35 AM, Prabhat Kumar Saraswat
<prabhat.saraswat at gmail.com> wrote:
> Hi,
>  Well, yes i did try your suggestion but i keep on running into a
> compilation problem.
>
> The error is:
>
> llvm[0]: Compiling Hello.cpp for Release build  (PIC)
> /home/saraswat/llvm/llvm-2.1/include/llvm/ADT/GraphTraits.h: In
> instantiation of
> `llvm::GraphTraits<llvm::ilist_iterator<llvm::BasicBlock> >':
> Hello.cpp:59:   instantiated from here
> /home/saraswat/llvm/llvm-2.1/include/llvm/ADT/GraphTraits.h:57: error:
> no type named `UnknownGraphTypeError' in `class
> llvm::ilist_iterator<llvm::BasicBlock>'
> Hello.cpp: In member function `virtual bool
> <unnamed>::Hello::runOnFunction(llvm::Function&)':
> Hello.cpp:59: error: no matching function for call to
> `idf_begin(llvm::ilist_iterator<llvm::BasicBlock>&)'
> Hello.cpp:59: error: no matching function for call to
> `idf_end(llvm::ilist_iterator<llvm::BasicBlock>&)'
>
>
> My source code for this pass is below:
>
> #include "llvm/Support/CFG.h"
> #include "llvm/ADT/DepthFirstIterator.h"
> #include "llvm/ADT/GraphTraits.h"
>
>     virtual bool runOnFunction(Function& F) {
>         //for each function iterating over the basic blocks
>       for (Function::iterator b = F.begin(); b != F.end(); ++b) {
>
>       for (idf_iterator<BasicBlock*> I=idf_begin(b); I!=idf_end(b);
> ++I) {   // for each basic block walking over the predecessors in the
> graph
>   BasicBlock* B = *I;
>   }
>  }
> }
>
>
>
> Am i doing something wrong ?,   I did verify template specialisation
> of the GraphTrait class for the BasicBlock class from the CFG.h file.
> Why this UnknownGraphTypeError ?
>
> Thanks again for the help.
>
> Regards
> Prabhat
>
>
>
> On Jan 22, 2008 5:39 PM, Ted Kremenek <kremenek at apple.com> wrote:
> > Hi Pabhat,
> >
> > Have you checked out DepthFirstIterator?  (include/llvm/ADT/
> > DepthFirstIterator.h).  It provides an iterator abstraction to perform
> > a forward/reverse DFS traversal of a graph.
> >
> > Many of the LLVM datatypes that represent graphs have a template
> > specialization of the GraphTraits<> class which allows separate
> > algorithms to treat them as graphs, walk them, etc.  (Both BasicBlock
> > and MachineBlock have such template specializations; e.g. include/llvm/
> > Support/CFG.h for the specialization for BasicBlock).
> > DepthFirstIterator works on any datatype that has a specialization of
> > GraphTrait.
> >
> > For your particular task, I *think* you would do the following
> > (someone else please correct me if I am wrong):
> >
> > #include "llvm/Support/CFG.h"
> > #include "llvm/ADT/DepthFirstIterator.h"
> >
> > for (idf_iterator<BasicBlock*> I=idf_begin(BB), E=idf_end(BB); I != E;
> > ++I) {
> >    BasicBlock* B = *I;
> >
> >
> >
> > On Jan 22, 2008, at 6:11 AM, Prabhat Kumar Saraswat wrote:
> >
> > > Hi all,
> > >
> > > Is there a way to walk through ALL the predecessors of a basic block
> > > in a CFG. I tried to iterate over the preds using this method
> > >
> > > for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; +
> > > +I) {
> > > BasicBlock *PredBB = *PI;
> > > }
> > >
> > > but this only gives the immediate predecessors for a basic block.
> > >
> > > For example, in this sample control flow graph.
> > >
> > > entry -> bb1 -> bb2 -> bb4 -> return
> > >                   |        |
> > >                   bb3 <-|
> > >
> > >
> > > walking over the predecessors for bb2 only gives bb3 and bb1.. while i
> > > need something like bb3 bb1 and return (i.e. walking till the root of
> > > the CFG)
> > >
> > > Any Ideas ?
> > >
> > >
> > > Regards
> > > Prabhat
> > > _______________________________________________
> > > LLVM Developers mailing list
> > > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
>