LLVM Pass开发：从返回基本块出发的逆CFG深度遍历报错求助

你遇到的类型错误主要来自两个关键点：LLVM的深度优先迭代器默认针对正向CFG（遍历后继节点），而你需要的是逆CFG（遍历前驱节点），必须用Inverse包装器明确指定；另外参数的const性和传递方式也需要调整。

错误根源拆解 #

从报错信息可以看到，inverse_depth_first和idf_begin的模板参数需要适配逆图的遍历规则，而默认的BasicBlock引用/指针对应的是正向CFG的GraphTraits，同时函数要求接受const T&类型参数，直接传非const的BasicBlock&会导致类型推导失败。

修正方案 #

我们需要用LLVM提供的Inverse<BasicBlock*>包装器来告诉迭代器使用逆CFG的遍历逻辑（即遍历每个节点的前驱），同时调整参数传递方式：

1. 确保包含必要头文件

首先确认代码里包含了GraphTraits.h（DepthFirstIterator.h可能间接包含，但显式添加更稳妥）：

#include "llvm/ADT/GraphTraits.h"

2. 修正两种遍历方式

方式一：Range-based for循环

把原来的*returnBB替换为Inverse<BasicBlock*>(returnBB)：

// 修正后的第一种循环
for (BasicBlock *BB : inverse_depth_first(Inverse<BasicBlock*>(returnBB))) {
    errs() << "Visited BB (range): " << BB->getName() << '\n';
    // 这里添加你的节点处理逻辑
}

方式二：显式迭代器循环

同样用Inverse<BasicBlock*>包装returnBB，注意迭代器访问节点时需要解引用一次（因为idf_iterator返回的是指针的包装）：

// 修正后的第二种循环
for (auto BB = idf_begin(Inverse<BasicBlock*>(returnBB)); BB != idf_end(Inverse<BasicBlock*>(returnBB)); ++BB) {
    errs() << "Visited BB (iterator): " << (*BB)->getName() << '\n';
    // 这里添加你的节点处理逻辑
}

为什么这样有效？ #

• Inverse<BasicBlock*>是LLVM的ADT工具，它会重载GraphTraits的接口，让迭代器从目标节点开始，反向遍历CFG（即访问前驱节点），这正是你需要的逆DFS逻辑。
• 直接传递returnBB指针给Inverse，而不是解引用，既满足了函数对const T&的参数要求，又让模板正确推导为逆图的迭代器类型。

完整修正后的代码片段 #

#include "llvm/Pass.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Function.h"
#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h" // 显式添加这个头文件
using namespace llvm;

namespace {
struct Exploration : public llvm::FunctionPass {
    static char ID;
    Exploration() : FunctionPass(ID) {}

    void getAnalysisUsage(llvm::AnalysisUsage &au) const {
        au.setPreservesAll();
        au.addRequiredTransitive<UnifyFunctionExitNodes>();
    }

    virtual bool runOnFunction(llvm::Function &F) override {
        UnifyFunctionExitNodes *UFEN = &getAnalysis<UnifyFunctionExitNodes>();
        BasicBlock *returnBB = UFEN->getReturnBlock();

        if (returnBB != nullptr) {
            errs() << "Return Block : ";
            errs().write_escaped(returnBB->getName()) << '\n';

            // 修正后的range-based for循环
            for (BasicBlock *BB : inverse_depth_first(Inverse<BasicBlock*>(returnBB))) {
                errs() << "Visited (range): " << BB->getName() << '\n';
            }

            // 修正后的显式迭代器循环
            for (auto BB = idf_begin(Inverse<BasicBlock*>(returnBB)); BB != idf_end(Inverse<BasicBlock*>(returnBB)); ++BB) {
                errs() << "Visited (iterator): " << (*BB)->getName() << '\n';
            }
        } else {
            errs() << "There is no return block\n";
        }

        return false; // 未修改IR
    }
};
}

char Exploration::ID = 0;
static RegisterPass<Exploration> X("Exploration", "Exploration Pass", false /* Only looks at CFG */, false /* Analysis Pass */);

内容的提问来源于stack exchange，提问作者Firmin Martin