[LLVMdev] Walking all the predecessors for a basic block

[Ted Kremenek]

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