[LLVMdev] Walking all the predecessors for a basic block

Prabhat Kumar Saraswat prabhat.saraswat at gmail.com
Wed Jan 23 01:35:16 PST 2008


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
>



More information about the llvm-dev mailing list