Walking all the predecessors for a basic block

Project Infrastructure LLVM Dev List Archives
1

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

2

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;

3

Yep, that's perfect.

-Chris

4

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

5

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;
   }