[LLVMdev] Walking all the predecessors for a basic block

Ted Kremenek kremenek at apple.com
Tue Jan 22 08:39:38 PST 2008

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  

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

More information about the llvm-dev mailing list