LLVM基本块基线路径构建分析Pass运行崩溃问题求助

现有代码致命问题梳理 #

• 已访问集合未更新导致无限递归：代码中只判断基本块是否在Explored集合中，但从未将访问过的基本块插入集合，当CFG存在循环结构时会进入无限递归，最终栈溢出导致程序崩溃，这是程序卡住的核心原因。
• 容器参数全为值传递：set、list类型参数全部用值传递，每次递归都会完整拷贝所有容器内容，内存占用随递归深度指数级上涨，且递归中对容器的修改无法回传给上层调用，逻辑完全不生效。
• 终止指令判断逻辑完全错误：ret指令所在的基本块没有后继，判断后继块的终止指令是否为ret的分支是永远无法触发的死代码，递归没有正常终止条件。同时分支指令是当前基本块的终止指令，不是后继块的，判断逻辑完全错位。
• 多后继块处理逻辑错误：一个基本块存在多个后继时，处理完第一个后继就直接return，剩余后继永远不会被遍历，路径覆盖不完全。

修复后代码 #

#include "llvm/Support/raw_ostream.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Function.h"
#include <set>
#include <list>
using namespace llvm;
using namespace std;

// 容器改用引用传递，避免拷贝同时传递修改结果
void Build_Baseline_path(BasicBlock *Start, set<BasicBlock *> &Explored, list<BasicBlock *> &Decision_points, list<BasicBlock *> &Path) {
    // 先将当前块标记为已访问
    Explored.insert(Start);
    Path.push_back(Start);

    // 判断当前块的终止指令，而非后继块的
    Instruction *Terminator = Start->getTerminator();
    StringRef OpcodeName = Terminator->getOpcodeName();

    // 遇到ret直接终止当前路径遍历
    if (OpcodeName == "ret") {
        errs() << "Found complete baseline path: ";
        for (auto *BB : Path) {
            errs() << BB->getName() << " ";
        }
        errs() << "\n";
        Path.pop_back();
        return;
    }

    // 标记决策点
    if ((OpcodeName == "br" && Terminator->getNumSuccessors() > 1) || OpcodeName == "switch") {
        errs() << "Decision point found: " << Start->getName() << "\n";
        Decision_points.push_back(Start);
    }

    // 遍历所有后继
    for (BasicBlock *Successor : successors(Start)) {
        if (Explored.find(Successor) == Explored.end()) {
            Build_Baseline_path(Successor, Explored, Decision_points, Path);
        }
    }

    // 回溯，移出当前块，准备遍历其他分支
    Path.pop_back();
}

// Function Pass中调用示例
bool runOnFunction(Function &F) override {
    set<BasicBlock *> Explored;
    list<BasicBlock *> Decision_points;
    list<BasicBlock *> Path;
    Build_Baseline_path(&F.getEntryBlock(), Explored, Decision_points, Path);
    return false;
}

补充说明 #

如果要实现基线法的独立路径生成，可在上述遍历基础上，默认优先选择第一个后继作为基线路径，后续通过替换决策点的分支选择，生成其他与基线仅存在决策点差异的独立路径即可。

内容的提问来源于stack exchange，提问作者Andrea Nenna