LLVM 的 Pass 基础设施是整个编译器优化系统的核心骨架。与传统编译器将优化过程硬编码在固定流程中不同，LLVM 通过 Pass 机制实现了优化的模块化、可组合和可扩展。这种设计不仅使得新优化的添加变得简单，更重要的是建立了一套分析和转换相互协作的框架。本章将深入探讨 Pass 系统从早期 Legacy Pass Manager 到现代 New Pass Manager 的演化历程，理解其背后的设计权衡和工程挑战。
在 LLVM 中，Pass 是对 IR 进行分析或转换的基本单元。每个 Pass 都是一个独立的组件，具有明确定义的输入输出接口。这种设计源于编译器构造中的一个核心观察：大多数优化都可以被分解为对程序的遍历（pass over the program）。
Pass 在 LLVM 中主要分为两大类：
分析 Pass (Analysis Pass)：只读取 IR，不修改它，产生可供其他 Pass 使用的分析结果。例如：
DominatorTree：构建支配树LoopInfo：识别和分析循环结构ScalarEvolution：分析标量值的演化AliasAnalysis：判断内存访问是否可能指向同一位置转换 Pass (Transformation Pass)：修改 IR 以优化程序。例如：
InstCombine：组合和简化指令LICM：循环不变代码外提Inliner：函数内联DeadCodeElimination：死代码消除从粒度上，Pass 还可以分为：
Pass 的模块化设计带来了多重优势：
这种设计理念可以用以下 ASCII 图表示：
Input IR
|
v
+-----------+
| Pass A | <-- Analysis
+-----------+
|
v
+-----------+
| Pass B | <-- Transformation (uses A's result)
+-----------+
|
v
+-----------+
| Pass C | <-- Transformation
+-----------+
|
v
Output IR
Pass Manager 负责协调 Pass 的执行，其核心职责包括：
执行模型的核心是”懒惰求值”原则：分析结果只在需要时才计算，并尽可能长时间地保持有效。
Legacy Pass Manager 是 LLVM 项目早期（约 2003 年）由 Devang Patel 设计实现的。它基于继承的面向对象设计，所有 Pass 都继承自基类：
class Pass {
public:
virtual bool runOnModule(Module &M) { return false; }
virtual bool runOnFunction(Function &F) { return false; }
// ...
};
这种设计在项目初期运作良好，但随着 LLVM 的发展，逐渐暴露出严重问题：
AnalysisID（本质是 void*）表达，缺乏类型检查一个典型的 Legacy Pass 实现：
class MyFunctionPass : public FunctionPass {
static char ID;
public:
MyFunctionPass() : FunctionPass(ID) {}
bool runOnFunction(Function &F) override {
// 获取分析结果
DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
// 执行转换
// ...
return true; // IR 被修改
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<DominatorTreeWrapperPass>();
AU.addPreserved<LoopInfoWrapperPass>();
}
};
2014 年，Chandler Carruth 在 LLVM 开发者会议上提出了 New Pass Manager 的设计方案。主要动机包括：
New PM 的核心设计是基于模板的静态多态：
struct MyFunctionPass {
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM) {
// 获取分析结果
auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
// 执行转换
// ...
// 声明保留的分析
PreservedAnalyses PA;
PA.preserve<DominatorTreeAnalysis>();
return PA;
}
};
从 Legacy PM 到 New PM 的迁移是一个长达数年的过程（2014-2021），主要挑战包括：
迁移策略采用了渐进式方法：
Pass 之间存在复杂的依赖关系，主要包括：
在 New PM 中，这些关系通过 PreservedAnalyses 类精确表达：
PreservedAnalyses PA;
PA.preserve<DominatorTreeAnalysis>(); // 保留支配树
PA.preserveSet<CFGAnalyses>(); // 保留所有 CFG 分析
PA.abandon<LoopAnalysis>(); // 显式废弃循环分析
依赖图可以表示为：
┌──────────────┐
│ LoopAnalysis │
└──────┬───────┘
│ requires
v
┌──────────────┐
│ DomTreeAnalysis │
└──────┬───────┘
│ required by
v
┌──────────────┐
│ LICM Pass │ ──preserves──> DomTreeAnalysis
└──────────────┘
Pass Manager 的调度算法经历了多次演进：
Legacy PM 时代：
New PM 的改进：
调度算法的核心是解决优化顺序问题（Phase Ordering Problem）。不同的执行顺序可能导致不同的优化效果：
Scenario A: Inline → DeadCode → Simplify
Scenario B: DeadCode → Inline → Simplify
Scenario A 可能暴露更多死代码消除机会，而 Scenario B 可能减少内联的代码量。
为了找到最优的 Pass 顺序，LLVM 采用了多种策略：
一个典型的优化序列示例：
EarlyCSE → SimplifyCFG → SROA → EarlyCSE →
InstCombine → SimplifyCFG → Reassociate →
LoopRotate → LICM → LoopUnroll → InstCombine
分析结果的生命周期管理是 Pass Manager 的核心功能之一。一个分析结果从创建到销毁经历以下阶段：
生命周期可以用状态机表示：
[Not Computed]
|
| request
v
[Computing]
|
| complete
v
[Valid] <──────┐
| │
| invalidate│ recompute
v │
[Invalid] ───────┘
|
| cleanup
v
[Destroyed]
New PM 采用了分层缓存架构：
class FunctionAnalysisManager {
// 每个函数的分析结果缓存
DenseMap<pair<Function*, AnalysisKey*>, unique_ptr<AnalysisResult>> Cache;
template<typename AnalysisT>
typename AnalysisT::Result& getResult(Function &F) {
auto Key = make_pair(&F, AnalysisT::ID());
auto It = Cache.find(Key);
if (It != Cache.end())
return *static_cast<AnalysisT::Result*>(It->second.get());
// 运行分析并缓存结果
auto Result = AnalysisT().run(F, *this);
Cache[Key] = make_unique<...>(move(Result));
return *Cache[Key];
}
};
缓存策略的关键设计决策：
当 IR 被修改后，相关的分析结果需要失效。New PM 使用 PreservedAnalyses 实现细粒度的失效控制：
PreservedAnalyses InstCombinePass::run(Function &F, FunctionAnalysisManager &FAM) {
// 执行指令组合优化
bool Changed = combineInstructions(F);
if (!Changed)
return PreservedAnalyses::all(); // 没有修改，保留所有分析
PreservedAnalyses PA;
PA.preserveSet<CFGAnalyses>(); // 保留 CFG 相关分析
PA.abandon<ScalarEvolutionAnalysis>(); // SCEV 需要重算
return PA;
}
失效传播的规则：
失效传播示例：
Pass 修改了 CFG
→ BasicBlock 结构改变
→ DominatorTree 失效
→ LoopInfo 失效（依赖 DomTree）
→ ScalarEvolution 失效（依赖 LoopInfo）
LLVM 的优化级别继承了 GCC 的传统，但在实现上有自己的理解：
-O0（无优化）：
-O1（基础优化）：
-O2（平衡优化）：
-O3（激进优化）：
-Os（大小优化）：
-Oz（极限大小优化）：
优化 Pipeline 的构建遵循以下原则：
典型的 -O2 Pipeline 结构：
Module Pipeline:
├── Force Function Attrs
├── Infer Function Attrs
├── [CGSCC Pipeline]
│ ├── Function Simplification Pipeline (iteration 1)
│ │ ├── SROA
│ │ ├── Early CSE
│ │ ├── SimplifyCFG
│ │ ├── InstCombine
│ │ └── ...
│ ├── Inline
│ └── Function Simplification Pipeline (iteration 2)
└── Module Optimization Pipeline
├── Global DCE
├── Global Optimizer
└── ...
优化级别的选择本质上是性能提升与编译时间的权衡：
性能提升 (%)
^
│ ╭────── -O3
│ ╱
│ ╱╱───── -O2
│ ╱╱
│ ╱╱──── -O1
│╱
└────────────────> 编译时间 (x)
关键的权衡点：
实际案例：Sanjoy Das 在 2018 年的 Pipeline 调优将 Chrome 的某些关键路径性能提升了 5%，同时编译时间仅增加 2%。
C++20 引入的 Coroutine 给 LLVM 的 Pass 系统带来了独特挑战。Coroutine 的实现需要将看似连续的函数体转换为可以暂停和恢复的状态机，这涉及复杂的 IR 转换。
Coroutine 转换的核心步骤：
Frame Allocation：创建 coroutine frame 保存局部状态
转换示例：
// 原始 Coroutine
generator<int> range(int n) {
for (int i = 0; i < n; ++i)
co_yield i;
}
// 转换后的伪代码结构
struct range_frame {
int n, i;
int suspend_index;
promise_type promise;
};
void range_resume(range_frame* frame) {
switch(frame->suspend_index) {
case 0: goto resume_point_0;
case 1: goto resume_point_1;
}
resume_point_0:
// for loop body
frame->promise.yield_value(frame->i);
frame->suspend_index = 1;
return;
resume_point_1:
// continue loop
// ...
}
LLVM 的 Coroutine 转换通过一系列专门的 Pass 实现：
CoroEarly
↓
[Regular Optimization Passes]
↓
CoroSplit
├── CoroElide (优化：消除堆分配)
└── CoroFrame (构建 coroutine frame)
↓
CoroCleanup
关键的设计挑战：
CO-RE 是 BPF（Berkeley Packet Filter）生态系统中的一项关键技术，它允许编译一次的 BPF 程序在不同内核版本上运行。虽然不直接属于 Coroutine，但 CO-RE 展示了 LLVM 如何支持特殊的编译需求。
CO-RE 的核心机制：
// CO-RE 示例
struct task_struct {
// 不同内核版本字段偏移可能不同
int pid;
// ...
};
// 使用 CO-RE
int get_pid(struct task_struct *task) {
return BPF_CORE_READ(task, pid); // 运行时解析正确偏移
}
__builtin_preserve_* intrinsicsCO-RE 在 Pass 系统中的处理：
Source Code
↓
Clang (生成 CO-RE relocations)
↓
LLVM IR (带 preserve intrinsics)
↓
BPF Backend (保留 relocation 信息)
↓
BPF Object (带 BTF 和 relocations)
↓
Kernel Loader (运行时 relocation)
Coroutine 和 CO-RE 技术的发展趋势：
Devang Patel 在 Apple 工作期间主导了 Legacy Pass Manager 的设计和实现。他的主要贡献包括：
AnalysisUsage 机制关键设计决策：
char* 地址作为唯一标识Chandler Carruth 在 Google 工作期间推动了 New Pass Manager 的开发。他在 2014 年 LLVM 开发者会议上的演讲 “The New Pass Manager” 成为转折点。
主要改进：
他的名言：”The old pass manager is where performance goes to die”（旧的 Pass 管理器是性能的坟墓）深刻影响了社区。
Sanjoy Das 在 Azul Systems 和后来的 Google 工作期间，对 Pass Pipeline 进行了系统性优化：
2003: Legacy Pass Manager 初版发布
2005: Pass Manager 支持 Loop Pass
2008: 引入 CallGraphSCCPass
2010: 开始讨论 Pass Manager 重构
2014: Chandler Carruth 提出 New PM 设计
2015: New PM 基础设施开发开始
2016: 第一批 Pass 迁移到 New PM
2017: Clang 开始实验性支持 New PM
2018: New PM 在 -O3 下默认启用
2019: 大规模 A/B 测试验证 New PM
2020: New PM 成为默认选项
2021: Legacy PM 标记为废弃
2022: 开始移除 Legacy PM 代码
Pass 基础设施是 LLVM 成功的关键因素之一。从 Legacy Pass Manager 到 New Pass Manager 的演进，体现了软件工程中的重要原则：模块化、类型安全、性能优化和渐进式重构。
核心要点回顾：
模块化设计：Pass 机制将复杂的编译优化分解为可组合的单元，提高了代码的可维护性和可扩展性。
依赖管理：精确的依赖表达和缓存机制确保了分析结果的正确性和效率。
架构演进：从 Legacy PM 到 New PM 的迁移展示了大型系统重构的最佳实践。
优化策略：不同优化级别（-O0 到 -O3）的设计平衡了编译时间和运行时性能。
新技术挑战：Coroutine 和 CO-RE 等新技术要求 Pass 系统不断演进。
关键公式和概念：
练习 3.1：解释 Analysis Pass 和 Transformation Pass 的区别，并各举两个例子。
练习 3.2：为什么 New Pass Manager 使用模板而不是虚函数？列出至少三个优势。
练习 3.3：描述 -O2 和 -O3 优化级别的主要区别。
练习 3.4：设计一个简单的 Pass 依赖图，包含至少 4 个 Pass，其中 2 个是 Analysis Pass，2 个是 Transformation Pass。标注它们的 required 和 preserved 关系。
练习 3.5：假设你要从 Legacy PM 迁移一个自定义 Pass 到 New PM，列出需要修改的主要部分。