How to do DFS on call graph generated by llvm

Question

I want to do the DFS(Depth First Search) traversal on the call graph generated by llvm i.e. I am using following code, but stuck at how to proceed further?

bool runOnModule(Module &M) override
    {
        CallGraph cg = CallGraph(M);
         cg.dump();

         CallGraph::iterator beg =  cg.begin();

         CallGraph::iterator end = cg.end();

         return false;
    }

The above code is only dumping the callGraph. But I want to do DFS traversal on it starting from main method. I am using clang as front end. How to do it?

Answer 1

The depth first traversal is very simple once you learn to use the LLVM graph iterators:

#include <llvm/ADT/DepthFirstIterator.h>

bool runOnModule(Module &M) override {
  CallGraph CG = CallGraph(M);

  for (auto IT = df_begin(&CG), EI = df_end(&CG); IT != EI; IT++) {
    if (Function *F = IT->getFunction()) {
      dbgs() << "Visiting function: " << F->getName() << "\n";
    }
  }

  return false;
}

From the df_iterator you can use getPathLength() and getPath(unsigned) member functions to check your position during the visitation or even skip a specific sub-tree withskipChildren() (but be careful with mixing this with the operator++).

You can also use the post-order traversal or a strongly connected component iterator.