📚 课程目录第4章基本块支配树计算

4. 基本块支配树计算

任务目标

编写一个LLVM FunctionPass，对每个函数计算基本块的支配树（Dominator Tree），并打印每个基本块与其直接支配者（IDom）的对应关系。通过该Pass验证对LLVM支配关系API的理解与使用。

环境与依赖

LLVM版本：10.x或更高（本案例代码基于LLVM 10+ API）
构建方式：使用llvm-config获取编译与链接参数
源码文件：DomTreePass.cpp

完整实现代码

#include "llvm/IR/Function.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/Pass.h"
#include "llvm/Passes/PassBuilder.h"
#include "llvm/Passes/PassPlugin.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Analysis/DominanceFrontier.h"
#include "llvm/IR/Dominators.h"

using namespace llvm;

namespace {
class DomTreePrinterPass : public FunctionPass {
public:
  static char ID;
  DomTreePrinterPass() : FunctionPass(ID) {}

  bool runOnFunction(Function &F) override {
    DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();

    errs() << "Function: " << F.getName() << "\n";

    // 遍历函数中的所有基本块
    for (BasicBlock &BB : F) {
      // 获取该基本块的直接支配者
      BasicBlock *IDom = DT.getNode(&BB)->getIDom()
                             ? DT.getNode(&BB)->getIDom()->getBlock()
                             : nullptr;

      errs() << "  BB \"" << BB.getName() << "\"";
      if (IDom) {
        errs() << " is dominated by BB \"" << IDom->getName() << "\"\n";
      } else {
        errs() << " has no immediate dominator (entry block)\n";
      }
    }
    errs() << "\n";
    return false; // 不修改函数
  }

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.addRequired<DominatorTreeWrapperPass>();
    AU.setPreservesAll();
  }
};
} // namespace

char DomTreePrinterPass::ID = 0;
static RegisterPass<DomTreePrinterPass> X("domtree-printer",
                                          "Print Dominator Tree for each function",
                                          false /* Only looks at CFG */,
                                          false /* Analysis Pass */);

注册为动态库（可选）

若需通过opt动态加载，添加以下插件注册代码：

extern "C" ::llvm::PassPluginLibraryInfo LLVM_ATTRIBUTE_WEAK llvmGetPassPluginInfo() {
  return {LLVM_PLUGIN_API_VERSION, "DomTreePrinter", LLVM_VERSION_STRING,
          [](PassBuilder &PB) {
            PB.registerPipelineParsingCallback(
                [](StringRef Name, FunctionPassManager &FPM,
                   ArrayRef<PassBuilder::PipelineElement>) {
                  if (Name == "domtree-printer") {
                    FPM.addPass(DomTreePrinterPass());
                    return true;
                  }
                  return false;
                });
          }};
}

编译与运行

编译Pass（静态链接方式）：

llvm-config --cxxflags --ldflags --libs core analysis --system-libs | xargs g++ -std=c++14 -fPIC -shared DomTreePrinterPass.cpp -o DomTreePrinterPass.so

准备测试IR：创建test.ll，内容包含分支结构（如if-else）：

define i32 @test(i32 %x) {
entry:
  %cmp = icmp sgt i32 %x, 0
  br i1 %cmp, label %then, label %else
then:
  ret i32 1
else:
  ret i32 0
}

运行Pass：

opt -load ./DomTreePrinterPass.so -domtree-printer test.ll -o /dev/null

验证方法与预期输出

运行后，标准错误输出应显示每个基本块的支配关系。对于上述test.ll，预期输出为：

Function: test
  BB "entry" has no immediate dominator (entry block)
  BB "then" is dominated by BB "entry"
  BB "else" is dominated by BB "entry"

通过条件：entry块无直接支配者（它是根节点），then和else块的直接支配者均为entry。若输出与此一致，则Pass实现正确。

常见问题

链接错误：确保编译命令包含-lLLVMCore -lLLVMAnalysis（通过llvm-config --libs core analysis获取）。
Pass未注册：若使用-domtree-printer报错，检查是否已用-load加载.so文件，且Pass名称与注册字符串一致。
空基本块名：若基本块无显式名称（如%1），输出会显示空字符串，可改用BB.getAddress(&BB)或编号方式区分，但本案例为清晰起见使用名称。