如何对 llvm 生成的调用图进行 DFS

Question

我想在 llvm 生成的调用图上进行 DFS（深度优先搜索）遍历，即我正在使用以下代码，但卡在如何继续进行？

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

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

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

         return false;
    }

以上代码只是转储callGraph。但我想从 main 方法开始对其进行 DFS 遍历。我使用 clang 作为前端。怎么做？

Answer 1

学习使用 LLVM 图迭代器后，深度优先遍历将非常简单：

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

从df_iterator你可以使用getPathLength()和getPath(unsigned)成员函数来检查你在访问期间的位置，甚至可以使用skipChildren()跳过特定的子树（但要小心将其与 operator++).

混合使用

您还可以使用 post-order traversal or a strongly connected component iterator。

如何对 llvm 生成的调用图进行 DFS

How to do DFS on call graph generated by llvm

llvm

call-graph

llvm-clang