LLVM 中基本块的拓扑排序

Question

我希望能够按拓扑顺序获取函数中的基本块。有一个迭代器可以迭代函数中的基本块，但是我不确定它是否按拓扑顺序执行。我无法获得特定基本块的下一个基本块，也无法自己进行拓扑排序。

您可以假设 CFG 中没有循环。

Answer 1

在一般情况下，这是不可能的，因为 BB 不形成 DAG。拓扑顺序只为 DAG 定义——一个没有环的图；函数内的 BB 可能形成循环（循环等）。

恕我直言，您最好的近似方法是将 BB 图分解为 SCC（强连接组件）。LLVM 已经有工具可以做到这一点：参见include/llvm/ADT/SCCIterator.h，还有tools/opt/PrintSCC.cpp.

事实上，后者已经以反向拓扑顺序打印函数的 SCC ，调用方式如下：

$ opt -print-cfg-sccs <bitcode file>

更新（2013 年 9 月 16 日）：另请参阅此博客文章。