编译器与 LLVM Pass

基于 C++17 和 LLVM 19 实现的两个 LLVM IR 分析 Pass：局部值编号（Local Value Numbering）Pass 用于基本块内冗余检测，以及活跃变量分析（Liveness Analysis）Pass，在含回边的控制流图（CFG）上计算 UEVar、VarKill、LiveIn、LiveOut。

在 GitHub 上查看

亮点

• 将 LocalValueNumbering 和 Liveness 构建为 LLVM 插件共享库，通过新 Pass 管理器注册
• LVN 使用值编号表和表达式表，在基本块内标记冗余二元计算
• Liveness 对 CFG 后继节点进行迭代不动点更新，正确处理回边和自用模式（如 a = a + 1）
• 直接使用 LLVM 19 C++ API 操作 IR 指令、基本块和 CFG 遍历

局部值编号（LVN）

LocalValueNumbering Pass 扫描每个函数内的 IR 指令，为操作数和表达式分配值编号以标记冗余计算。

核心数据结构：

• ValueNumberTable — 将字符串化操作数和指令映射到值编号
• ExpressionTable — 将 (opcode, VN1, VN2) 元组映射到值编号；重复元组表示冗余表达式

二元、load 和 store 指令在 LVN::generateLVNMap 中分别处理。该 Pass 在单个基本块内操作（局部分析）。

Pass 输出：每条指令分配的值编号；冗余表达式已标记

活跃变量分析（Liveness）

Liveness Pass 使用标准数据流方程，迭代计算每个基本块的活跃变量信息，直至收敛：

• LiveOut(BB) = ∪ LiveIn(Successors)
• LiveIn(BB) = UEVar(BB) ∪ (LiveOut(BB) − VarKill(BB))

CFG 遍历使用 LLVM 的后继迭代器。迭代循环在 LiveIn 和 LiveOut 集合不再变化时终止——正确处理回边。特殊情况处理自用模式（a = a + 1），即变量同时出现在赋值两侧。

迭代不动点循环：从后继传播 LiveOut，每次迭代重新计算 LiveIn

Pass 输出：含分支的 CFG 中每个基本块的 UEVar、VarKill、LiveOut

技术概览