llvm dev - Jan 2008 - [LLVMdev] Walking all the predecessors for a basic block

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

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

On Tue, 22 Jan 2008, Ted Kremenek wrote:
> 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;
Yep, that's perfect.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/

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
>