LLVM IR 中端 Pass 的设计目标与运行原理

发表于 2026-09-15 更新于 2026-09-13 分类于笔记本文字数： 55k 阅读时长 ≈ 3:20

境界線の向こう側で　足掻く人々　嘆く人々　目にしながら，
境界线的那一边挣扎着的人们叹息着的人们如若将之收在眼里，
沈黙することを選択するならば　僕らは共犯者　人たりえたのか，
却还沉默着选择旁观的话那我们就是共犯何以称为人类，
存在価値はいつだって自分の中　個々に宿る銘々の色，
存在的价值一直都在自身之中在每个个体居宿若我们将各自的颜色，
胸に抱いたなら　微かに灯る火が　最後の星空と　どこか似ていたんだ，
抱在怀中无论是多么微渺的灯火那连缀的点点火光正似那最后的星辰满空。

—— 境界線 · amazarashi

clang -O2 的中端流水线上排着相当多的 pass，但其中真正独立的算法不多，真正独立的正确性依据更少：通用理论那一章立起的 T0–T7 支撑了后文每一段证明。本文的结论也在这里——中端的复杂度主要在次序，不在算法。

本文基于 llvm-project main 分支 026e3f3c，文中每一处 file.h:line 都链到该 commit 下的具体位置（绝大多数在 llvm/ 下；少数几处引 clang/lib/CodeGen/BackendUtil.cpp，用来说明 driver 如何设定流水线开关）。谈的是中端（IR 层）优化，前端语义与指令选择不涉及。

题图：pixiv 148848095（Tiarii《Hope》，《86—エイティシックス—》的シン与レーナ）

引子

clang -O2 的执行过程里，前端把 C++ 翻译成 LLVM IR，之后还有一长串优化 pass 依次作用在这份 IR 上。若按”一共有多少个优化”去理解这条流水线，容易走偏：真正独立的算法数量有限，清单上的大量条目是同一批规则在不同层次、不同时机被重复调用；更关键的是，真正独立的正确性依据更少。读下去会发现，它们的论证反复使用的只有以下几句：这个值只有一个定义，因此沿一条 use 边就能取到它；这个块支配那个块，因此把指令移过去不会减少执行次数；这条依赖的距离非负，因此交换执行顺序不会颠倒先后关系；这个结论是格上的不动点，因此它只会偏保守，不会偏错。其余部分都是同一批定理在不同 pass 上的实例化。

本文因此采用另一种组织方式：先把 T0–T7 这批被反复引用的工具逐条写清——每件给出形式化陈述、证明（或证明骨架）、以及真正使用它的 pass（每件列出若干个消费者，实际用到的远多于列出的）；再按 -O2 的真实次序逐个走 pass（变换与分析各成一章，一个条目里含几个 pass 的不再拆开计数），每个只回答三个问题——它对 IR 做了什么改写（算法）、改写后 IR 变成什么形态（效果）、这个形态为什么值得（意义），然后附一段证明，证明中只引用前面已经立过的定理。这样读下来会发现：中端流水线的复杂度主要不在算法，而在次序。算法本身大半是这些定理的直接推论，真正需要解释的是它们为什么按这个顺序排列。

我习惯从代码而不是从论文入手，所以本文不按”先框架、后算法”的教科书顺序讲：New Pass Manager 的机制全部放到最后一章。原因是它回答的问题为”次序如何被表达成数据”，要先知道次序为什么是这样，才看得出这套机制省掉了什么。

本文的目录就是 -O2 的骨架（PassBuilderPipelines.cpp:1753）：

buildPerModuleDefaultPipeline(O2)                        :1753
├─ 模块简化流水线 buildModuleSimplificationPipeline      :1113
│    前端清理 → IPSCCP → CalledValuePropagation → GlobalOpt(全局)
│    → always-inline → 内联器(沿call graph)
│    → 嵌套(逐函数)简化流水线 ─────────────────────────┐
└─ 模块优化流水线 buildModuleOptimizationPipeline        :1508
     再内联 → 循环再整形(rotate/deletion/interchange/fuse/distribute)  │
     → 向量化 → 收尾 → GlobalDCE                         │
                                                          │
  逐函数简化流水线 buildFunctionSimplificationPipeline   :620 ┘
    SROA → EarlyCSE → JumpThreading/CVP → SimplifyCFG
    → InstCombine/AggressiveInstCombine → Reassociate → ConstraintElim
    → LPM1(LICM/rotate/LICM/unswitch/flatten)
    → LPM2(idiom/indvars/deletion/full-unroll)
    → GVN → SCCP → BDCE → 第二轮 DFAJumpThreading/JT/CVP
    → ADCE/MemCpyOpt/DSE → LICM 再一轮 → 再清理

骨架里与后文反复出现的简称在这里一次给全（每个 pass 的完整说明在它自己那一节，此处只给一句话职责）：

简称	全称与它做什么
SROA	Scalar Replacement of Aggregates：把栈上的聚合体（结构体、数组）按访问区间拆开，能提升的提成 SSA 值
EarlyCSE	Early Common Subexpression Elimination：在昂贵分析就绪之前先消掉显然的重复计算
JT	JumpThreading：某条来路上分支结果已经确定时，把这条来路直接接到那个目标块
CVP	CorrelatedValuePropagation：把分支条件蕴含的值事实（非负、范围、非空）写进元数据与溢出标志
GVN	Global Value Numbering：给语义相同的表达式同一个编号，据此消除跨块重复计算
SCCP / IPSCCP	Sparse Conditional Constant Propagation：只在可达的边上稀疏地传播常量；IPSCCP 是它的跨过程版本
LICM	Loop-Invariant Code Motion：把循环内每次迭代都得到同一结果的计算提出循环
BDCE / ADCE / DSE	三种死代码判据：按位（Bit-tracking DCE）、按可观测行为（Aggressive DCE）、按内存写覆盖（Dead Store Elimination）
SCEV	Scalar Evolution：把循环里随迭代变化的值写成关于迭代次数的闭式
LAA / TLI / BFI / BPA	LoopAccessAnalysis（循环内访存对的依赖判定）、TargetLibraryInfo（平台库函数档案）、BlockFrequencyInfo / BranchProbabilityInfo（块频度与边概率）
NPM / LPM / CGSCC	New Pass Manager（LLVM 现行的 pass 调度框架，本文末章）、Loop Pass Manager（循环子流水线；正文的 LPM1/LPM2/LPM3 指逐函数简化流水线里依次出现的那三段）、Call Graph SCC（调用图按强连通分量分层遍历）
PGO / LTO / VF	Profile-Guided Optimization（用真实运行计数指导优化）、Link-Time Optimization（链接期优化）、vectorization factor（向量宽度）
ConstraintElim	ConstraintElimination：把全函数的线性比较约束联立求解，折掉可证恒真/恒假的检查。另注：CalledValuePropagation（给间接调用点挂上候选目标集合的元数据）在本文一律写全名——它的缩写会与上表的 CVP（CorrelatedValuePropagation）撞车

另有一批不属于某个 pass、而是全文通用的基础术语，同样在这里一次给全（每条都给”本文在哪一处正式使用它”，用到时可直接翻回）：

术语	一句话定义	正式使用处
IR	intermediate representation，中间表示：前端与后端之间那层与目标机器无关的程序表示，本文特指 LLVM IR	全文；语义契约见 T0
pass	流水线上的一道工序：读入一份 IR 或一份分析结论，产出改写后的 IR 或新的结论	全文；调度机制见末章
SSA / φ 节点 / select	static single assignment，静态单赋值：每个值只被赋值一次，多处赋值改名，汇合处用 φ 节点按”这次从哪个前驱块进来”选择入参；`select` 则是按条件在两个值里挑一个的指令（不分支，两个操作数都已求值）	定义 2.1a、定理 2.2；select 的惰性对比见 LibCallsShrinkWrap 一节
CFG / DAG	control flow graph，控制流图：基本块为节点、跳转为边；DAG 是有向无环图	定义 2.1；调用图缩点后是 DAG（引 3.3）
UB	undefined behavior，未定义行为：语言标准不为其规定任何结果的执行，本文记作 $\bot$	定义 0.1、引 0.5
poison	LLVM 的一种值：拿它做普通运算不立刻 UB，但送进分支条件、除数、访存地址一类位置即 UB；同一个 poison 允许对应多种取值	定义 0.1、引 0.4，LangRef §Poison Values
AA	alias analysis，别名分析：判定两个指针是否可能指向同一块内存，结论是 NoAlias / PartialAlias / MustAlias / MayAlias 四值之一	引 1.4、引 5.6、分析章 AAManager
mem2reg / RAUW	mem2reg 是 `PromoteMemoryToRegister`：把只被 load/store 触及的 `alloca` 提升为 SSA 值；RAUW 是 `replaceAllUsesWith`，把一个值的全部使用改指向另一个值	定义 2.1a、推论 2.3
alloca	在函数栈帧上分配一块内存的指令；它的地址不逃逸时，这块内存对外不可见	定义 0.1a、引 5.4
intrinsic	编译器内建函数：名字由 LLVM 保留、语义在 LangRef 里逐字定义的调用，如 `llvm.memset`、`llvm.assume`	引 0.5、定义 0.1b 及各消费者
GEP	`getelementptr`，LLVM 的地址计算指令：基址加一组”下标 × 元素大小”，本身不访存	定义 5.1 出处、分析章 AAManager
trip count / EC	trip count 是循环的迭代次数；exit count（EC）是退出前已经完成的迭代次数	引 2.6、引 4.2
hoist / sink	hoist 是把指令搬到必经的或执行次数更少的支配点；sink 是反向，搬到汇合点或低频块	引 0.7、引 2.4
lane / splat / reduction	lane 是向量里的一个元素位置；splat 是把同一个标量填满整个向量；reduction 是把一串值归约成一个值的运算（求和、求积）	引 4.7、VectorCombine 与 SLPVectorize 两节
vtable	虚函数表：C++ 虚调用在运行期查表取函数指针所用的那张表	分析章 LazyCallGraph、收尾章 WholeProgramDevirt
bitcode / fat LTO	bitcode 是 LLVM 的序列化 IR 文件；fat LTO 指把 bitcode 一并嵌进目标文件的做法	分析章 Verifier
Semi-NCA	求支配树的一种算法：先算半支配点（semi-dominator），再由最近公共祖先得到 idom	定义 2.1 出处、分析章 DominatorTree
clobbering access	MemorySSA 里”最近一次可能覆盖某位置的访存”，是判断一个 load 是否仍然有效的依据	引 5.3、分析章 MemorySSA

前置背景（IR 的语义契约、SSA 形式带来的性质、格与数据流、SCEV 的代数、别名分层）另有一篇整理（尚未发布，暂不附链接）。本文的通用理论一章与它有重叠，但视角不同：那篇讲”这些性质是什么”，本文讲”这些性质写成定理之后，每个 pass 各引用了哪一条”。图论工具的现成词条（支配树 / 拓扑排序 / 强连通分量 / DFS）本文按原样沿用、不另造说法：通用理论章开头有一张表，写清这四页各给了哪条定义、本文哪些条目建立在它之上，正文用到时直接引那张表。

通用理论：T0–T7，被反复引用的那批工具

每件工具一小节，格式统一：说什么（形式化陈述）、为什么成立（证明或证明骨架）、谁在用（列出若干消费者；后文每个 pass 的证明只往这一章引）。

这一章依赖四块外部定义，四块都是 oi-wiki 上现成的标准陈述，本文原样沿用、不另造说法：

外部定义	那一页给的定义	出处	本文建立在它之上的条目
DFS、DFS 序列与括号序列	深度优先搜索：递归下探、访问过的点打标记；DFS 序列 = 调用过程中访问到的节点编号序列，”每个子树都对应 DFS 序列中的连续一段”；括号序列 = 进入一个节点记一个左括号、退出时记一个右括号，于是每个节点出现两次、进出各一次	oi-wiki DFS（图论）	T3 全部（定义 3.0 的后序就是把”退出时记的那一次”排成序列）；引 2.7（子树 = 连续区间 → 支配查询降为区间比较）
支配关系与支配树	钦定入口 $s$ ；若从 $s$ 到 $u$ 的每条路径都经过 $v$ ，则 $v\ \mathrm{dom}\ u$ ；每个点的直接支配点（immediate dominator，该页的用法，本文写作 idom）连成支配树。支配集用不动点方程 $\mathrm{dom}(u)=\{u\}\cup\bigcap_{v\in pre(u)}\mathrm{dom}(v)$ “不断迭代直至答案不变”求得，而”为了提高效率，希望每轮迭代时当前结点的所有前驱尽可能都已算完，因此要利用深度优先排序得出这个图的逆后序，按这个顺序迭代”	oi-wiki 支配树	定义 2.1、引 2.4–2.7；定理 1.2 与引 1.3 的 worklist 与 RPO 就是这一页那两句话的抽象
DFS 生成树与四类边、SCC	树边、返祖边（back edge，”也称回边”：指向 DFS 栈上的祖先）、前向边、横叉边；强连通分量 SCC = 极大的强连通子图，Tarjan 求出后缩点得到 DAG	oi-wiki 强连通分量	引 3.1 的回边、定理 3.2 的自然循环、引 3.3 的缩点
拓扑排序	DAG 上排一个线性序，使任何边 $(u,v)$ 都满足 $u$ 在 $v$ 前；有环就排不出来	oi-wiki 拓扑排序	引 3.3/3.4 的逆拓扑序

这四块之外，本文自己约定的记号只有三组，且都在用到之前给出：事件序列（定义 0.1/0.1a/0.1b，T0 开头）、格上的 worklist 不动点（定义 1.1 + 定理 1.2，T1 开头）、自然循环 / 迭代空间（定理 3.2、定义 4.4a）。写作规则是一个记号只在被定义之后才使用；确有条目需要提前用到后面的定义（例如引 1.3 要用 T3 的 RPO），就地标注”（见 T3 引 3.1）”指明出处，不另造新词。

T0 精化：改写的合法性判据

所有改写共用的合法性判据只有一条，即定义 0.2 的精化关系。要说清它，得先把”事件序列”这四个字拆开：它指函数执行过程中对外可见的动作按发生次序排成的序列，不是执行结束时的内存终态。两者差别很大：终态相同但中间多了一次对外调用，仍然是不同的程序行为，而事件序列能区分这两种情形。

定义 0.1（可观测语义）。给一个 Function 一份输入 $\sigma$ （实参、可达全局的初值、内存内容、以及运行期才定的 load 结果），它的可观测行为集是

\mathcal{O}(P,\sigma)\;\subseteq\;\mathrm{Trace}\;\cup\;\{\bot\}\;\cup\;\{\uparrow\}

\bot

是"这次执行触发了 UB"，

\uparrow

是"不终止"（事件流无限，或停在一条不产生任何事件的循环里）。**

\mathcal{O}

是关系不是函数**：poison 让同一个

\sigma

允许多条合法 trace（引 0.4），而

\sigma

里那个"运行期才定的 load 结果"把环境的不确定性也一并收进来。正确性因此是个

\forall\sigma

的全称命题——这正是推论 1.6 那个方向性（结论过于保守只损失优化机会，结论过于精确就是错误结论）的源头。

出处：”可观测行为”的原始口径是 C++ 标准的 as-if rule（”最少要求”那段就是 $W/C/V/R$ 的来源）；IR 侧见 LangRef §Poison Values 与 §Undefined Values；工程编码是 MemoryEffects（:78 的 MemoryEffectsBase）与 Instruction.h:887 的 mayHaveSideEffects()。形式化先例：Vellvm（POPL’12）的操作语义、Alive2（PLDI’21）的 refinement 判定。定义 0.1/0.1a/0.1b 是本文的记账口径，不是 LLVM 的规范文本，只要求能把后文每条证明的合法性说清。

定义 0.1a（事件字母表与 trace）。 $\mathrm{Trace}=\mathcal{E}^{*}\cup\mathcal{E}^{\omega}$ ，即事件字母表 $\mathcal{E}$ 上的有限或无限序列，序列次序就是执行次序。 $\mathcal{E}$ 只有四类：

\mathcal{E}\;=\;\underbrace{\{\,W(a,v)\,\}}_{\text{对可观测地址的普通写}}\;\cup\;\underbrace{\{\,C(f,\bar{v})\,\}}_{\text{不透明 call}}\;\cup\;\underbrace{\{\,V(a,d)\,\}}_{\text{volatile/atomic 访存}}\;\cup\;\underbrace{\{\,R(v)\,\}}_{\text{对外的 return}}

依次是：对可观测地址的普通写；不透明 call（外部函数、inline asm、任何 callee 未知的调用——callee body 已知时这一对 call/ret 不是事件，它贡献的是自己 body 里的事件）；volatile/atomic 访存（读也算，每一次都是一个事件）；对外的 return（函数对外可见或地址逃逸时）。

什么不是事件，同样重要：

不是事件	为什么
普通 load	读只改变后续事件的因果链，自己不留痕迹；它的值由 $\sigma$ 给定
纯算术、比较、phi、`select`、地址计算	只影响后面事件的取值，不与外界交互
写未逃逸的 `alloca`、写地址不出模块的 `internal` 全局	地址不可观测（私有性见 T5 引 5.4）
控制流本身（跳转、块结构、迭代次数）	只有它导致的 $W/C/V/R$ 差异才可观测
模块内已知 body 的 call/ret 这一对	内联前后事件逐条对应（Inliner 那条证明）

次序在三种情形下有影响，影响范围依次扩大：同一地址的两次写——次序决定终值，一律要保；不同地址的两次写——只在中间存在观测点时才要保；两个不透明 call 之间——一律保序，因为无法排除 callee 读写同一个位置。第二条的精确化就是 0.1b。

出处： $W$ 与 $V$ 的区分见 LangRef §store、§load 的 volatile/atomic 语义与 MemoryLocation.h:217；”callee 已知则 call 透明”对应 LangRef §Function Attributes 的 memory(...) 属性族（按位置逐个声明可读可写，如 memory(none)、memory(read)、memory(argmem: read)；早期写作 readnone/readonly/argmemonly 的那组名字，现在主要留在参数属性上）与 AliasAnalysis.md 的 mod/ref 摘要；”不是事件”那张表的判定函数是 Instruction.h:827 mayReadOrWriteMemory() 与 :887 mayHaveSideEffects()。

定义 0.1b（写的可观测粒度）。对非 volatile、非 atomic 的普通写，事件不是”每一次写”，而是”该地址在观测点上呈现的值”。观测点三种：

(\mathrm{OP1})\ \text{任何可能读到该地址的读}\qquad (\mathrm{OP2})\ \text{任何不透明 call}\qquad (\mathrm{OP3})\ \text{函数返回 / 线程结束 / 程序终止}

于是判据是：两次写之间若不存在观测点，则前一次写不进任何 trace，可自由删除、合并、搬移。 $W(a,v)$ 被记进 trace 当且仅当存在一个观测点，在它之前 $a$ 的最近一次写就是这次。volatile/atomic 的每一次访存都是事件（ $V$ ），故 DSE 家族从不碰它们。

这套判据不是本文的发明，而是 C++ as-if rule 在 IR 上的对应版本：标准把可观测行为限定在 volatile 访问的严格求值、对文件的写、与交互设备的动态行为上；LangRef 继承它，并用 memory(...) 那套函数属性给”一个 call 能贡献哪些访存事件、作用于哪些位置”下了官方定义（它在源码里的类型是 MemoryEffects，常用的几档由工厂函数给出：unknown() 可读可写任意内存、none() 不访存、readOnly()/writeOnly()、argMemOnly() 只碰实参指向的内存）——那套属性就是 0.1a 在实现中的对应物，也是 InferFunctionAttrs 与 PostOrderFunctionAttrs 两节在标注的内容。

一个逐行标注的例子（ $\sigma$ 给定 @sink 的内容与 %out 的指向）：

@fmt = private constant [4 x i8] c"%d\0A\00"
@sink = global i32 0                 ; 外部可见 ⇒ 可观测地址
declare i32 @printf(ptr, ...)        ; callee body 不在本模块 ⇒ 不透明
define i32 @f(i32 %n, ptr %out) {    ; %out 由 caller 传入 ⇒ 逃逸 ⇒ 可观测
  %p = alloca i32
  store i32 7, ptr %out              ; ✗ W₀：被 W₁ 全覆盖，中间无观测点 ⇒ 0.1b 授权删除
  store i32 0, ptr %p                ; ✗ 私有存储，地址不可观测（见 T5 引 5.4）
  %g = load i32, ptr @sink           ; ✗ 读不是事件，值由 σ 给定
  %s = add nsw i32 %g, %n            ; ✗ 纯算术；溢出则该执行只有 ⊥（见下文引 0.6）
  store i32 %s, ptr %out             ; ✓ W₁ = W(%out, %s)
  %k = call i32 (ptr, ...) @printf(ptr @fmt, i32 %s)   ; ✓ C₁；同时是 W₁ 之后的观测点(OP2)
  store i32 1, ptr @sink             ; ✓ W₂ = W(@sink, 1)
  ret i32 %s                         ; ✓ R；同时是 OP3
}

trace 为 $\langle W_1,C_1,W_2,R\rangle$ 。 $W_0$ 不在里面；而 $C_1$ 之后的任何写都不能随便删—— $C_1$ 是观测点，printf 可能通过任何途径看见 %out（要严格删就得让 AA 证明这个 callee 不读 %out，这正是 DSE 必须依赖 AA 结论与函数属性的原因）。把 $C_1$ 换成一条纯算术， $W_1$ 与 $W_2$ 之间就没有观测点了吗？有—— $W_2$ 写的是另一个地址， $W_1$ 的观测点是 OP3（return 时 %out 的值可被 caller 看见），故 $W_1$ 仍在 trace 里。判定观测点的依据是”哪些位置可能被谁读到”，不是”哪些指令在两次写之间执行”。

出处：as-if rule 原文在 C++ [intro.execution]；IR 侧的消费者就是 DSE、MemCpyOpt 与 LICM 的 promote——DeadStoreElimination.cpp:9 沿 MemorySSA def 链找”下一次可能别名访问”就是 OP1 的实现，MemCpyOptimizer.cpp 的区间合并靠的也是”中间无观测点”；OP2 的判定靠函数属性（ModRef.h:78）。

定义 0.2（精化）。 $P'\sqsubseteq P$ 当且仅当

\forall\sigma:\quad \bot\in\mathcal{O}(P,\sigma)\ \ \vee\ \ \mathcal{O}(P',\sigma)\subseteq\mathcal{O}(P,\sigma)

一句话：在旧程序有定义的输入上，新程序的每种结局都必须是旧程序本来可能的结局。 $\bot$ 与 $\uparrow$ 都算结局，所以这一条同时管住下面三件事。后文按条款引用，展开写清（均在 $\bot\notin\mathcal{O}(P,\sigma)$ 时）：

(\mathrm{i})\ \tau\in\mathcal{O}(P',\sigma),\ \tau\neq\bot\ \Rightarrow\ \tau\in\mathcal{O}(P,\sigma)\qquad\text{不许造出新 trace（含"把不终止变成终止"）}

(\mathrm{ii})\ \bot\in\mathcal{O}(P',\sigma)\ \Rightarrow\ \text{假}\qquad\text{不许把不 UB 的输入变 UB}

(\mathrm{iii})\ \uparrow\in\mathcal{O}(P',\sigma)\ \Rightarrow\ \uparrow\in\mathcal{O}(P,\sigma)\qquad\text{不许把会停的输入变不停}

注意它没有要求旧程序的 $\bot$ 或 $\uparrow$ 被保留：UB 的执行没有行为需要保护（引 0.5），而 C++ 的前进保证已使”无副作用却不终止”本身 UB，定义开头那条前提（ $\bot\in\mathcal{O}(P,\sigma)$ 时整条义务解除）把它接住——LoopDeletion 删无副作用的循环，但默认不删可能不终止的循环（除非 mustprogress 属性明确授权，见 LoopDeletion 那一条），分界就在 (iii)。

出处：refinement 定义与”UB 输入上无义务”这条约定是 Alive（PLDI’15）与 Alive2（PLDI’21）的核心处理（它们把 UB 当成”实现可自由选择”），Vellvm（POPL’12）用的是等价的 refinement 关系； $\uparrow$ 那一支的语言依据是 C++ [intro.progress]（前进保证）。

引理 0.3（传递律）。 $\sqsubseteq$ 自反、传递。故流水线的正确性等价于每个 pass 各自满足 $\sqsubseteq$ ： $P_0\succeq P_1\succeq\cdots\succeq P_n\Rightarrow P_0\succeq P_n$ 。证明是关系包含的传递性，一行。这条说明 New Pass Manager 为什么只要求每个 pass 各自证明局部正确、不对整条流水线做全局验证：全局正确性是局部正确的复合；代价是任何一个 pass 的声明不成立，整条流水线的结论随之失效（末章的 preserve 契约会再次出现同一结构）。

出处：”逐改写单元验证再串起来”的工程实例就是 Alive2：它把 InstCombine 的每条规则当成一个独立的 refinement 子问题单独判，而流水线整体的正确性靠的就是引 0.3 的传递性。

引理 0.4（poison 可任意替换）。若 $v$ 在某执行中为 poison，把 $v$ 换成任意同类型值 $c$ 仍满足 0.2。证明：poison 的消费者只有两种下场——把它当普通值用（关系语义下 $\mathcal{O}$ 已包含 poison 的一切取值，故 $c$ 对应的那条 trace 本就在 $\mathcal{O}(P,\sigma)$ 里，(i) 成立），或把它送进 UB 位置（br 条件、除数、访存地址、noundef 参数），此时 $\bot\in\mathcal{O}(P,\sigma)$ ，0.2 的前提不成立、该输入上无任何义务。∎

出处：LangRef §Poison Values 原话 “It is correct to replace a poison value with an undef value or any value of the type”，同节给出 poison 升级为 UB 的位置清单；配套的指令是 §freeze（把 poison 冻结成一个确定值）。Alive2 把这条当作 refinement 的基本引理用（PLDI’21）。

引理 0.5（UB 分支可剪）。若块 $B$ 的一切执行都触发 UB（ $B$ 以 unreachable 终结，或 $B$ 只在 nsw 溢出时可达），则删掉所有进入 $B$ 的边保持 0.2。证明：分两种 $\sigma$ 。经 $B$ 的那些 $\sigma$ 上 $\bot\in\mathcal{O}(P,\sigma)$ ，义务解除；不经 $B$ 的 $\sigma$ 上删边不影响任何执行， $\mathcal{O}$ 逐点相同，(i)(ii)(iii) 空虚成立。∎ 这一条是多个 pass 的共同依据：SCCP 剪不可达边、JumpThreading 改道、CVP 折分支、LoopDeletion 删除迭代次数为零的循环，全部引它。

出处：边可达格的实现是 SCCPSolver.cpp:796 markEdgeExecutable 与 :1280；”删边前先查副作用”的实现是 JumpThreading.cpp:418；UB 路径可自由处置的理论论证见 Alive2 的 UB 语义一节。

引理 0.6（标志即可证明的前提）。add nsw 的语义是

\llbracket\texttt{add nsw }x,y\rrbracket_\sigma=\begin{cases}x_\sigma+y_\sigma & x_\sigma+y_\sigma\in[-2^{31},\,2^{31}-1]\\[2pt] \text{poison} & \text{否则}\end{cases}

于是它支持两个方向的推理：(a) 消费——带着 nsw 的改写免费拿到那条不等式；(b) 生产——想加 nsw 必须先证明该不等式。nuw、exact、nneg、fast-math flag 同理，方向都一样。消费者：CVP（把 nsw 证明出来再写进指令）、Reassociate（重排前先检查链上有没有标志）、IndVarSimplify（扩宽以避免回绕）、SCEV（hasNoUnsignedWrap 一族）、FullUnroll 与 Vectorize（复制 body 时不得凭空造标志）。

出处：nuw/nsw 的 poison 语义原文在 LangRef §add，fast-math 那一族在 §Fast-Math Flags；消费端见 ScalarEvolutionExpressions.h:217 的 hasNoUnsignedWrap()/hasNoSignedWrap()（:221），生产端见 CorrelatedValuePropagation.cpp。

引理 0.7（纯指令可推测）。若指令 $i$ 无副作用且在任何输入下都不会成为 $\bot$ 的源（不访存、不作除数与陷阱操作、不把 poison 送进 UB 位置），则把它搬到任何支配其全部 use 的位置执行，仍满足 0.2。证明：新程序至多在”本来不执行 $i$ “的路径上多算一个不被观测的值，事件集不变； $\bot$ 的产生能力未变。∎ 消费者：SpeculativeExecution、MergedLoadStoreMotion、GVNHoist、LICM 的 AllowSpeculation、LoopSink、SimplifyCFG 的 hoist。

出处：这条引理在源码里对应一个具体的函数：ValueTracking.cpp:7499 isSafeToSpeculativelyExecute()；主要调用方是 MergedLoadStoreMotion.cpp:11（文件头写的就是 diamond/hammock 上的 hoist/sink；diamond 与 hammock 这两种图形状的说明见后文 MergedLoadStoreMotion 一节）、SpeculativeExecution.cpp:9、LICM.cpp:192 的 AllowSpeculation。

T1 格与不动点：为什么算得完，为什么结论只会偏保守

定义 1.1。 $(L,\sqsubseteq)$ 为完备格， $f:L\to L$ 单调（ $x\sqsubseteq y\Rightarrow f(x)\sqsubseteq f(y)$ ）。约定 $\sqsubseteq$ 越大越保守（信息越少）： $\bot$ 是最精确、 $\top$ 是”我不知道”。

出处：LLVM 里现成的几个格——常数格 ValueLattice.h:27（:236 的 getOverdefined）、四值别名格 AliasAnalysis.cpp:126、位集合格 DemandedBits.h:41；定理本身是 Tarski 1955。

定理 1.2（Knaster–Tarski + Kleene）。 $\mathrm{lfp}(f)=\mathop{\sqcap}\limits\{x\mid f(x)\sqsubseteq x\}$ 存在；若 $L$ 高度有限（升链条件），则

\mathrm{lfp}(f)=\bigsqcup_{n\geq 0}f^{n}(\bot),\qquad f^{h}(\bot)=f^{h+1}(\bot),\ h=\mathrm{height}(L)

出处：不动点存在性是 Tarski 1955；编译器数据流里的经典陈述（Kleene 迭代 + 有限高度终止）见 Kildall, POPL 1973 与 Kam & Ullman, Acta Informatica 1977。

引理 1.3（终止与代价）。worklist（一个”待处理节点”的队列：取出一个、更新它的结论、若结论变了就把受影响的后继重新入队，直到队列空；oi-wiki 支配树页求支配集时”不断迭代直至答案不变”就是它最朴素的形式）实现下，每个节点被取出处理的次数以格的高度 $h$ 为上界（ $h$ 见定理 1.2），全部节点的处理次数因此以 $|V|\cdot h$ 为上界；按 RPO（逆后序，定义见 T3 的定义 3.0；oi-wiki 支配树页给的正是同一个理由——按逆后序迭代可以让每个节点的前驱尽可能先算完）处理时，每走完一趟，信息就沿着非回边向前推进一层循环嵌套的深度，故实际迭代轮数以”循环嵌套深度加一”为上界。

把这两个上界读成日常语言：结论只会朝一个方向变（越来越保守），而保守的方向上有尽头，所以队列一定会空——这是”分析 pass 必然终止”的统一理由；至于收敛得快不快，取决于循环嵌套有多深，与函数有多大关系不大。SCEV 之所以能在每轮循环改写之后放心重建，靠的也是这两个上界：重建的代价有界。

出处：迭代轮数与 RPO 的关系出自 Kam & Ullman 1977（单调框架的迭代算法）；实现侧的 worklist 见 SCCPSolver.h:66 与 SCCPSolver.cpp:796。

引理 1.4（保守合成 / join 聚合）。若干独立结论要合成一个时，取 join（并，最不确定者胜）： $\mathrm{AA}(p,q)=\bigsqcup_i \mathrm{AA}_i(p,q)$ ，其中 $\mathrm{NoAlias}\sqsubset\mathrm{Partial/Must}\sqsubset\mathrm{MayAlias}=\top$ 。推论：任何一层给出错误的强结论，整体就错，且错在语义不在形态，Verifier（只查形态，见分析章末位）看不见。消费者：AAManager（别名分析各层结论的聚合器，见分析章）的全部分层、ReversePostOrderFunctionAttrs（callee 声明上的属性必须是所有 caller 都能保证的 meet——取交、最保守者胜，与 join 方向相反）、LAA 的 loop-non-alias 结论回填、AssumptionCache（收集 llvm.assume 事实的缓存，见分析章）的事实合并。

这里要补充说明”错在语义不在形态”：一个分析给出错误的 NoAlias 之后，下游改写产出的 IR 在类型、SSA、支配关系上全部合法，所以 Verifier 不会报错；错的是改写后的程序与原程序不再等价（定义 0.2 的 (i)）。

出处：join 的实现就在 AA 主循环里——AliasAnalysis.cpp:126：for (const auto &AA : AAs) { Result = AA->alias(...); if (Result != AliasResult::MayAlias) break; }（任一层答 MayAlias 即停，正是 $\top$ 短路）；分层的官方说明见 AliasAnalysis.md；”任一层错就全盘错”的不可能性根源见 Landi, Undecidability of Static Analysis, LOPLAS 1992。

定理 1.5（MOP $\sqsubseteq$ MFP）。同一个单调框架有两种解法：MOP 把 entry 到目标点的每条可行路径各自执行一遍转移函数、再取 meet 合并（最精确的可得目标）；MFP 是引 1.3 那套 worklist 迭代得到的不动点。前者不会比后者更保守：

\mathrm{MOP}(b)=\mathop{\sqcap}\limits_{p\,:\,\mathrm{entry}\rightsquigarrow b}F_p(\bot)\ \sqsubseteq\ \mathrm{MFP}(b)

证明：对 RPO 归纳。设 $b$ 的前驱均已满足 $\mathrm{MOP}\sqsubseteq\mathrm{MFP}$ ； $\mathrm{MFP}(b)=\bigsqcup_{p\to b}F_{p\to b}(\mathrm{MFP}(p))\sqsupseteq \bigsqcup_{p\to b}F_{p\to b}(\mathrm{MOP}(p))\sqsupseteq\mathop{\sqcap}\limits_p F_{p\to b}(\mathrm{MOP}(p))=\mathrm{MOP}(b)$ ，第一步用归纳假设与单调性，第二步用 join 支配 meet。∎

两者的区别再说一次：MOP 先把每条可行路径执行完再合并，精确但路径数指数级；MFP 在块入口先把前驱的结论 join 起来再执行转移函数，多项式时间但会把不可行路径的信息混进来。定理 1.5 只保证 MFP 不比 MOP 精确，不保证相等；而”不更精确”在本章的约定（ $\sqsubseteq$ 越大越保守）下就是”只会偏保守”。

出处：Kam & Ullman 1977（MOP 与 MFP 的关系、单调 vs 可分配的区分）；起点是 Kildall, POPL 1973。

推论 1.6（SCCP 型保证）。若 MFP 在点 $b$ 给出常数 $c$ ，则 $b$ 在任何真实执行中要么不可达、要么取值恰为 $c$ 。证明： $\mathrm{MOP}(b)\sqsubseteq c$ 意味着路径合并的结果比 $c$ 更精确，而常数格中比 $c$ 更精确的只有 $\bot$ （不可达）与 $c$ 本身。∎ 这条把 SCCP、IPSCCP、CVP 取用值事实的那一步（源码里是 LazyValueInfo 的 getPredicateAt/getConstantRangeAtUse，调用例如 CorrelatedValuePropagation.cpp:297 与 :467）、GVN 的编号、ConstraintElimination 的不等式闭包、CalledValuePropagation 的候选集，全部归约为同一句话：只要转移函数单调，结论一定覆盖真实情形。换句话说，结论过于保守只损失优化机会，结论过于精确就是错误。

出处：Wegman & Zadeck, Constant Propagation with Conditional Branches, TOPLAS 1991（另有 POPL’85 版）——稀疏 + 条件传播这两个关键词都是他们立的；LLVM 侧 ValueLattice.h:27、SCCPSolver.h:87 markBlockExecutable、IPO/SCCP.cpp:9。

引理 1.7（细化即新的一次遍历）。把某个等价/依赖关系加细（refine：把原来的等价类切成更小的类、判据变严，例如把”有人用”加细成”有人用它的第 $k$ 位”），原关系下的不动点一般不再是新关系下的不动点，故需要新的一遍计算。消费者：BDCE（把 use 细化为 demanded bits）、ADCE（把”被引用”细化为”可达于可观测根”）、DSE（把”被读”细化为”被区间覆盖前读到”）、MemorySSA（把”整个堆”这一粒度细化到 MemoryLocation，见 T5）。这条是引理 7.5（表示盲区与对应的专门 pass）的形式化基础。

出处：三次加细各对应一处源码——位级：DemandedBits.h:41 + BDCE.cpp:1；堆→Location：MemorySSA.md；读→区间覆盖：DeadStoreElimination.cpp:9。

T2 支配与 SSA：phi 的位置与代码移动的落点

定义 2.1。CFG $G=(V,E)$ 有唯一入口 $\mathrm{entry}$ 。 $a$ 支配 $b$ （ $a\ \mathrm{dom}\ b$ ）指 entry 到 $b$ 的每条路径都经过 $a$ ；严格支配去掉 $a=b$ 。每个非入口块有唯一最深的严格支配者 $\mathrm{idom}(b)$ ，把 $\mathrm{idom}(b)\to b$ 连成边即支配树。后支配 $\mathrm{pdom}$ 在反向图上镜像定义。支配边界 $\mathrm{DF}(v)=\{w\mid \exists p\to w,\ v\ \mathrm{dom}\ p,\ w\not\!\mathrm{sdom}\ v\}$ ，迭代支配边界 $\mathrm{IDF}(S)=\mathrm{DF}^{+}(S)$ 的最小不动点（定理 1.2 保证存在）。

出处：支配的经典算法是 Lengauer & Tarjan, TOPLAS 1979；LLVM 实际用的是 Semi-NCA，出处就写在文件头 GenericDomTreeConstruction.h:12（引 Georgiadis 的博士论文 Linear-Time Algorithms for Dominators and Related Problems, Princeton 2005）与 :31（增量更新，arXiv:1604.02711）；对外接口 Dominators.h:241、PostDominators.h:48。

定义 2.1a（最小 SSA 形式）。SSA 形式要求每个变量只被赋值一次：同一个变量在多处被写时改名成不同的名字，汇合处用 φ 节点选择”这次进来的是哪条路径上的那个名字”。同一份程序可以写成许多种都合法的 SSA，区别就在 φ 放多少：放多了也对，只是多余。最小 SSA 指其中 φ 数最少的那一种——只在”确有两条以上路径带着 $x$ 的不同定义汇合到一起”的块上放 φ，其余块一个都不放。Cytron 等人证明了这个”最少的放法”有精确刻画：所需的块集合恰是赋值点集的迭代支配边界 $J^{+}(S)$ （定义 2.1 的 $\mathrm{IDF}$ ）。LLVM 的 mem2reg/SROA 提升出来的、以及 MemorySSA 对访存做的，都是这个最小形式；注意”最小”说的是 φ 的数量，不是 def 的数量——def 一个也不省。

出处：minimal SSA 的定义与” $J^{+}$ 恰为所需 φ 集”这一结论出自 Cytron et al. 1991（§4 dominance frontiers）；LLVM 侧的实现自述是 PromoteMemoryToRegister.cpp:11，文件头原话 “transformed by using iterated dominator frontiers to place PHI nodes”——按 $\mathrm{IDF}$ 放 φ；idom 与支配集的基础定义见 oi-wiki 支配树。

定理 2.2（SSA 构造定理，Cytron et al.）。对变量 $x$ 的赋值点集 $S$ ，最小 SSA 形式中 $x$ 需要 phi 的块集合恰为 $J^{+}(S)=\mathrm{IDF}(S\setminus\{\mathrm{entry}\})$ 。

证明骨架：必要性——设 $w\notin J^+(S)$ ，对支配树归纳： $w$ 的每个前驱 $p$ 处 $x$ 有唯一到达定义 $d_p$ （归纳假设 + $p$ 不在 IDF 里）；若诸 $d_p$ 互异，则存在两条从不同 def 出发、只在 $w$ 汇合的路径，按 DF 定义即 $w\in\mathrm{DF}(\{d_p\})\subseteq J^+(S)$ ，矛盾。充分性—— $w\in J^+(S)$ 时上述两条路径给出两个不可区分的候选值，phi 不可省。∎

出处：Cytron, Ferrante, Rosen, Wegman & Zuck, Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, TOPLAS 1991（ $J^{+}$ 与最小性）；phi 位置的线性时间算法是 Sreedhar & Gao, POPL 1995——GenericIteratedDominanceFrontier.h:13 的文件头原文引的就是它；mem2reg 的实现 PromoteMemoryToRegister.cpp:809、:888、:1259；不建支配树、按需构造的另一路是 Braun et al., CC 2013。

推论 2.3（单步取得定义 / DCE 即可达性）。SSA 下每条 Use 直接持有其 def 指针，”reaching definitions” 退化为一次解引用；”还有没有人用”退化为一次 use 计数。于是删除一条无 use 且无可观测副作用的指令是安全的：它的值从未进入 $\mathcal{O}$ （定义 0.1a 的字母表里没有它）。消费者：mem2reg/SROA（定理 2.2 的正命题 + 沿 DFS 重写 load 的逆命题）、GVN、InstCombine、一切 DCE、SCEV 的 def-use 归纳。

出处：LLVM Programmer’s Manual 的 Value/Use/User 与 RAUW 两节；源码入口 Value.h:75、Use.h:35、User.h:44、Value.h:300 replaceAllUsesWith。

引理 2.4（代码移动四条件 M1–M4）。把指令 $i$ 从块 $A$ 搬到块 $B$ 保持 0.2，只要

\begin{aligned} (\mathrm{M1})\ &\forall o\in\mathrm{ops}(i):\ \mathrm{def}(o)\ \mathrm{dom}\ B &&\text{操作数在落点可用}\\ (\mathrm{M2})\ &\forall u\in\mathrm{users}(i):\ B\ \mathrm{dom}\ u &&\text{落点支配全部使用点}\\ (\mathrm{M3})\ &f_B\geq f_A\ \ \vee\ \ i\text{ 满足引 0.7} &&\text{执行次数不减（$f$ 为块执行频度，见 T6 定义 6.1），或纯且不会 UB}\\ (\mathrm{M4})\ &i\text{ 访存}\Rightarrow A,B\text{ 之间无与之 may-alias 的访问} &&\text{内存可见性不变（见 T5 引 5.3）} \end{aligned}

证明：(M1) 保证搬过去不引用未定义值；(M2) 保证没有 use 落在 $i$ 之前；(M3) 两支分别覆盖”次数不变”与”多算但不被观测”；(M4) 覆盖 store→load 的顺序未被扰动。四者合起来使事件序列逐点相同。∎ 凡是在 IR 里移动指令的改写，都要分别满足这四条义务：LICM 的提升、LICM 的 promote、LoopSink 的下沉、GVNHoist、GVNSink、SpeculativeExecution、MergedLoadStoreMotion、SimplifyCFG 的 hoist、TailCallElim 的参数赋值搬移，全是 M1–M4 的实例，差别只在各自怎么证 (M3) 与 (M4)。

出处：四条清单是本文的归纳，源码里它们分散在四处：LICM.cpp:181 hoist / :185 sink、LoopSink.cpp:357；(M3) 的判据是 ValueTracking.cpp:7499，(M4) 的判据是 MemorySSA.md 的 clobbering access。

引理 2.5（后支配 ⇒ 必然执行）。 $B\ \mathrm{pdom}\ A$ 当且仅当从 $A$ 到函数出口的每条路径都过 $B$ ；故 $A$ 一旦执行， $B$ 必在其后执行恰一次。证明：路径定义的直接改写；”恰一次”由 $B$ 在路径上出现一次 + 无循环重入（有重入时改为”至少一次”，消费者需自查）。∎ 消费者：ADCE 用后支配树把控制依赖上的指令一并标记为活的（不可删除）、GVNSink/MergedLoadStoreMotion 的落点必须后支配分支两侧、LoopDeletion 的”零次进入”、SimplifyCFG 的 sink 与 unreachable 清理。

出处：”控制依赖 = 后支配”的原始出处是 Ferrante, Ottenstein & Warren, The Program Dependence Graph and Its Use in Optimization, TOPLAS 1987；实现见 ADCE.cpp:101（成员 PostDominatorTree &PDT）与 :216（从后支配树根的孩子里找 return）。

引理 2.6（支配 ⇒ 循环内恒定）。若 $v$ 的定义支配循环头 $h$ （header：循环的入口块。本文用到的循环术语 header / preheader / latch / exit 一律按 LoopTerminology.md 的官方定义：preheader 是 header 之前唯一的外部前驱块，latch 是循环体里跳回 header 的那个块，exit 是循环外的后继块），且 $v$ 在循环内无重定义（SSA 下即：循环内没有第二个 def），则 $v$ 在每次迭代取同一值。证明：SSA 唯一 def（推论 2.3）+ 支配保证循环内任意点都”看得见”该 def，循环内无竞争者。∎ 消费者：LICM 的不变性判定、SimpleLoopUnswitch 的不变条件、LoopFlatten/LoopFuse 的 trip count 一致性前提、LAA 的仿射下标系数、LoopIdiomRecognize 的常数写识别。

出处：不变性判定是 LoopInfo 上的成员函数——LoopInfo.h:62 声明、LoopInfo.cpp:67 的 Loop::isLoopInvariant（判据就一句：是指令且不在本循环内，否则视为不变）与 :73 的 hasLoopInvariantOperands（全部操作数都不在循环内）；LICM 的提升候选正是把这两条与安全性一起查（LICM.cpp:935）；循环术语与”循环不变”的官方定义见 LoopTerminology.md；SCEV 侧是 ScalarEvolution.h:621 的 enum LoopDisposition——每个 SCEV 按与循环的关系定性，entry 处定义的值归入 LoopInvariant。

引理 2.7（支配树的 O(1) 查询）。对 idom 树做一遍 DFS 预编号 $(\mathrm{tin},\mathrm{tout})$ 后， $a\ \mathrm{dom}\ b\iff \mathrm{tin}(a)\leq\mathrm{tin}(b)\ \wedge\ \mathrm{tout}(b)\leq\mathrm{tout}(a)$ ，即一次区间比较。证明：支配树的子树恰是编号连续区间，这正是 oi-wiki DFS 页那句”每个子树都对应 DFS 序列中的连续一段”在支配树上的应用；括号序列的”进入/退出各记一次”就是 $(\mathrm{tin},\mathrm{tout})$ 这一对编号。∎ 消费者：DominatorTree 本体、LICM/GVN/CVP 的高频支配查询、MemorySSA 沿支配树传播版本、IDFCalculator。

出处：子树与连续区间的对应见 oi-wiki DFS（图论）的”DFS 序列”与”括号序列”两节；GenericDomTree.h:148（getDFSNumIn/getDFSNumOut，即 $(\mathrm{tin},\mathrm{tout})$ 这一对编号）、:505（dominates，编号可用时直接走区间比较）与 :755（updateDFSNumbers：建树后补一遍 DFS 预编号；查询过密时也会自动重编号）。

T3 遍历序：顺序决定收敛速度，不决定正确性

定义 3.0（后序与逆后序）。从入口块对 CFG 做一遍 DFS（就是 oi-wiki DFS（图论）那套递归 + 访问标记），离开一个块时才把它记下，得到的序列叫后序（postorder）：递归返回时才输出，所以后继先于前驱、子树先于父节点。把后序倒过来就是逆后序 RPO（reverse postorder）。它好用的原因可以一句话说清：RPO 里”前驱排在后继前面”（只有回边例外），这正是数据流迭代需要的顺序——oi-wiki 支配树页求支配集时就是这么干的（”利用深度优先排序得出这个图的逆后序，根据这个顺序进行迭代”）。

定义 3.0a（四种遍历序：树上四个，图上有意义的三个）。树上前序 / 中序 / 后序是现成的，因为有”孩子”这个明确结构；搬到有向图上，中序直接失去定义（图没有左孩子右孩子），前序与后序虽然照抄 DFS 就能得到，但两者给出的保证差别很大：

序	什么时候记下这个节点	它保证什么	图上有用吗
前序 preorder	第一次访问到它时（进入即记）	只保证 DFS 树上的父先于子	✗ 不保证节点排在它所有后继之前
中序 inorder	左子树走完、右子树未走时	二叉搜索树上得到升序序列	✗ 图上定义不出来
后序 postorder	它的所有出边都走完时（离开才记）	若存在路径 $W\leadsto V$ ，则 $V$ 排在 $W$ 之前（无环时）	✓ 反向数据流要的顺序
逆后序 RPO	把后序倒过来	若存在路径 $V\leadsto W$ ，则 $V$ 排在 $W$ 之前（无环时）	✓ 正向数据流要的顺序

两个例子（后继按写出的顺序枚举，序列都用脚本重算过）。无环图 $A\to B,\ A\to C,\ B\to D,\ C\to D,\ D\to T$ ：

\text{前序}=A,B,D,T,C\qquad \text{后序}=T,D,B,C,A\qquad \text{RPO}=A,C,B,D,T

前序里 $C$ 排在最后，可 $C\to D$ 、而 $D$ 早在它前面就出现了——前序不保证”节点先于它的后继”；RPO 里每条边都从前往后，正是拓扑排序（oi-wiki 拓扑排序那个定义）。所以那句常见误解要纠正：RPO 不是前序。树上前序就够用的算法，搬到 DAG 上要的是 RPO。

带循环的 CFG $\text{entry}\to H,\ H\to\text{body},\ H\to\text{exit},\ \text{body}\to H$ （最后一条是回边）：

\text{前序}=\text{entry},H,\text{body},\text{exit}\qquad \text{后序}=\text{body},\text{exit},H,\text{entry}\qquad \text{RPO}=\text{entry},H,\text{exit},\text{body}

两个观察。其一，RPO 与前序在这里就不一样了（body 与 exit 互换）。其二，有环时”路径 ⇒ 前后”的保证必然失效：环上两点互相可达，谁排前面都违反保证。于是 RPO 退化成引 3.1 那句”除回边以外一切边都是前向的”；要让保证重新成立，只能先按 SCC 缩点、在缩点后的 DAG 上谈序（引 3.3）。

为什么数据流要挑这个序。数据流问题分两个方向：正向（用前驱的结论算自己、再传给后继；SCCP、GVN、常量传播都是）与反向（用后继的结论算自己；ADCE、DSE、BDCE 那一族）。正向问题在 RPO 下最省：无环时走到一个块之前它的所有前驱都算完了，一遍就够；有环时退化为迭代，但 RPO 仍是收敛最快的顺序——每轮尽可能多地让信息沿非回边向前推进，只有回边上的信息要等下一轮，这正是引 1.3 那句”每走完一趟就把信息向前推进一层循环嵌套的深度”。反向问题对偶地要后序。

前序为什么两个方向都不能用，把上面两组例子按”每条边是否满足该方向要求的先后”逐边检查一遍就清楚了（脚本实测，回边按引 3.1 豁免）：

序	无环 DAG 正向	无环 DAG 反向	带循环 CFG 正向	带循环 CFG 反向
前序	✗ 有边被颠倒（ $C\to D$ ）	✗ 绝大多数边被颠倒	✓（回边貁免后碰巧成立）	✗ 绝大多数边被颠倒
后序	✗ 绝大多数边被颠倒	✓ 逐边均满足	✗ 绝大多数边被颠倒	✓ 逐边均满足
RPO	✓ 逐边均满足	✗ 绝大多数边被颠倒	✓ 逐边均满足	✗ 绝大多数边被颠倒

读法：正向合法序只有 RPO，反向合法序只有后序，前序在两个方向上都不合法。它在带循环 CFG 的正向一栏满足要求，纯属巧合——那一栏唯一不满足的边就是回边 $\text{body}\to H$ ，而它按引 3.1 貁免（DFS 树本来就是”父先于子”）；换成 DAG 立即不成立（ $C\to D$ 被颠倒，因为 $C$ 排在最后）。这正是”树上前序够用、图上不够用”的分界。

还有一个容易弄错的细节：不少资料建议反向问题用反向 CFG 上的 RPO，而不是原图的后序（Bendersky 原文的对比就是这两个：post-order on the original graph vs RPO on the reverse CFG）。两者都是合法的反向序，差别在哪：无环时两者都满足”后继先于前驱”，只在互不可达的块之间次序可能不同（本例原图后序 $T,D,B,C,A$ 、反图 RPO $T,D,C,B,A$ ， $B$ 与 $C$ 互换，而它俩之间没有路径，谁先都不影响正确性）；有环时差别落在环内： $A\to B,\ A\to C,\ B\to C,\ B\to D,\ C\to B$ （ $B\leftrightarrow C$ 成环），原图从 $A$ 出发的后序是 $C,D,B,A$ ，把每条边掉头、以原图出口 $D$ 为入口，反图的 RPO 是 $D,B,C,A$ ——环内 $B$ 、 $C$ 的先后不同。为什么反图 RPO 反而更好，Bendersky 给的猜测（本文采纳）是：先访问 $B$ 时它的后继 $D$ 已经算过，而先访问 $C$ 时它唯一的后继 $B$ 还未计算，于是前者收敛更快。LLVM 里”反向图”是一个 marker class Inverse<>：同一套遍历器与建树器换个模板参数就能处理反向图，后支配树正是”同一套 Semi-NCA 在反向视图上跑一遍”。

最后还有一条更弱的保证，也是定理 1.2 的实际含义：数据流的值域是偏序集、转移函数单调，所以即使随机顺序访问也会收敛到同一个不动点；挑对遍历序影响的是收敛速度（也就是编译时间），不是正确性。

出处：四序对比、”RPO ≠ 前序”、正反两向如何选序、以及”反图 RPO 与原图后序不等价”这个例子，都出自 Eli Bendersky, Directed graph traversal, orderings and applications to data-flow analysis, 2015（本文的三组序列与那张逐边合法性对照表都按同一定义用脚本重算过：前序/后序/RPO 各跑一遍，再逐条边检查该方向要求的先后是否成立，回边豁免）；LLVM 侧，RPO 的实现就是”先 post_order 收集、再用反向迭代器输出”（PostOrderIterator.h:290 的 class ReversePostOrderTraversal，:306 注释原话 “Because we want a reverse post order, use reverse iterators from the vector”），消费者 NewGVN.cpp:3445、GVN.cpp:3102、GVNSink.cpp:514、Reassociate.cpp:2744；反向图的 marker class 见 GraphTraits.h:109（注释写明 “used as a little marker class to tell the graph iterator to iterate over the graph in a graph defined ‘Inverse’ ordering”）；后支配树复用同一套建树器、只把子节点类型换成反向视图，见 GenericDomTreeConstruction.h:130（std::conditional_t<Inversed, Inverse<NodePtr>, NodePtr>）；”乱序也收敛、只是更慢”的形式理由是定理 1.2 与 Kam & Ullman 1977。

引理 3.1（RPO 与回边）。DFS 把每条边分成四类（oi-wiki 强连通分量页的树边 / 返祖边 / 前向边 / 横叉边），其中回边（back edge，oi-wiki 叫返祖边）指 $u\to v$ 且 $v$ 此刻还在 $u$ 的 DFS 栈上（即 $v$ 是 $u$ 的祖先）。则： $u\to v$ 是回边 $\iff$ 后序里 $u$ 排在 $v$ 之前（倒过来，RPO 里就变成 $v$ 在前）；除回边以外的一切边在 RPO 中都是前向的（ $u$ 排在 $v$ 之前）。推论：沿 RPO 走一趟，信息顺着非回边总能从”已算好”流向”还没算”，只有回边上的信息要等下一轮，故一趟即可把信息推进”循环嵌套深度 + 1”层，worklist 轮数被嵌套深度而非图规模支配（与引 1.3 合流）。消费者：GVN/NewGVN 的编号序、ADCE、mem2reg 的重写序、DominatorTree 的迭代、Reassociate 的 rank 计算、LoopInfo 的回边标记。

出处：Tarjan, Depth-First Search and Linear Graph Algorithms, SIAM J. Comput. 1972（三色与回边的原始论证）；LLVM 侧的现成迭代器 PostOrderIterator.h 与 DepthFirstIterator.h；rank 的实际用法见 Reassociate.cpp:209 BuildRankMap。

定理 3.2（自然循环与森林）。 $h$ 是循环头 $\iff$ 存在回边 $n\to h$ ；该回边的自然循环为 $\{h\}\cup\{x\mid x\text{ 可不经过 }h\text{ 到达 }n\}$ ，它单入口（ $h$ ）、可多 latch、任意两个自然循环或嵌套或不相交，故全体构成森林。证明：单入口由 $h\ \mathrm{dom}\ n$ 与支配的传递性给出；嵌套/不相交由”若 $x$ 同属两个循环则两头互相支配”导出。∎ 消费者：LoopInfo（一遍 DFS， $O(V+E)$ ）、LPM 的 worklist、SCEV 以 Loop 为索引、一切 loop pass 的”循环内/循环外”划分。

出处：LoopInfo.cpp:9 的文件头原话（”identify natural loops … may actually be several natural loops that share the same header node”）、LoopInfo.h:433；官方术语与图示见 LoopTerminology.md。

引理 3.3（缩点逆拓扑 = callee 先）。调用图按 SCC 缩点后是 DAG；逆拓扑序保证 callee 侧 SCC 先于 caller 侧被访问。消费者：Inliner/CGSCC 遍历、PostOrderFunctionAttrs、LazyCallGraph 的 SCC 维护（LazyCallGraph 本体见分析章）、GlobalOpt 的引用图遍历。

出处：LazyCallGraph.h:13（”NB: This is not a traditional call graph!”）与 :122（引用图是调用图的超集）；遍历序的设计说明 CGSCCPassManager.h:13、:29、:59；SCC 算法仍是 Tarjan 1972。

推论 3.4（单次传递即达不动点）。设属性 $A(f)$ 的转移函数只依赖 $f$ 自身体内结构与 $\{A(g)\mid f\text{ 调 }g\}$ 。沿缩点逆拓扑处理，则每个 SCC 只需内部解一次不动点（定理 1.2），SCC 之间单次传递即达全图不动点。证明：对缩点 DAG 的逆拓扑秩归纳——秩为 0 的 SCC（叶子）无出边依赖，直接收敛；秩 $k$ 的 SCC 依赖的全在秩 $<k$ 中且已定型。∎ 消费者：PostOrderFunctionAttrs（readnone 一类的结论从调用图的叶子逐层传到根）、nocapture 的参数图归纳、InlineCost 的 callee 体积测量、IPSCCP 的跨过程传播（加一条：调用边本身也在格上，故是”值格 × 边可达格”的联合不动点）。

出处：FunctionAttrs.cpp:271 的注释”Deduce readonly/readnone/writeonly attributes for the SCC”就是”SCC 内解一次不动点、SCC 间单次传递”的实现自述；属性作为格上 meet 的写法见 ModRef.h:78 与 LangRef §Function Attributes。

引理 3.5（循环森林逆后序 = 内层先）。LPM 的 worklist 按循环森林的逆后序取循环，故处理外层循环时内层循环已定型；循环被改写（unswitch 克隆、flatten 合并）时经 LPMUpdater 把新循环插回 worklist 且保持该序不变。证明：逆后序在森林上是”子先于父”，与引 3.1 同构；不变量的维持靠”新循环只可能出现在被改写循环的子树内”。∎ 消费者：FunctionToLoopPassAdaptor 的契约、LICM、unswitch、full unroll，以及”外层改写会破坏内层已处理完的状态”这个必须靠 LoopInstSimplify/LoopSimplifyCFG 进场时重建规范形的事实。

出处：LoopPassManager.h:13（文件头写明逆后序 + 强制补 LoopSimplify/LCSSA）与 :218（class LPMUpdater：改写方经它把新循环登记回 worklist、维持逆后序）；森林遍历序的数据结构在 LoopInfo.h:433。

T4 循环代数：闭式、正规形、依赖保持

定义 4.1（addrec：SCEV 的链式记法）。SCEV 要给”随循环推进而变化的表达式”一个名字，它用的记号是 $\{a,+,b\}_{L}$ ，读作”在循环 $L$ 里，从 $a$ 起，每转一次加 $b$ “——就是等差数列。下标 $L$ 说明这条递推是哪个循环的（嵌套时不能混），把它按迭代次数展开就是普通式子：

\{a,+,b\}_{L}(i)=a+b\cdot i,\qquad i=\text{进入循环 }L\text{ 后已经转过的次数（从 0 起）}

对照代码看三个例子：for (i = 0; i < n; ++i) 里的 i 是 $\{0,+,1\}_{L}$ ；指针递进 p = p + 4、初值 %p0 是 $\{\%p0,+,4\}_{L}$ ；数组元素地址 %A + i*4 是 $\{\%A,+,4\}_{L}$ ——这正是向量化能算出”第 $i$ 次访问哪个地址”的依据。 $a$ 与 $b$ 本身还可以是别的 SCEV 表达式，于是有两件常见的事：嵌套（ $b$ 又是外层循环的 addrec 时得到链套链，即嵌套递推，写法上把内层链当外层链的步长）、常数因子吸收（ $\{0,+,2\cdot k\}$ 与 $2\cdot\{0,+,k\}$ 是同一个节点）。还有一条硬约束：源码写明 “All operands of an AddRec are required to be loop invariant”—— $a$ 与 $b$ 必须是循环不变的，这就是引 2.6（支配 ⇒ 循环内恒定）在 SCEV 里的用处所在。

为什么不直接留着 SSA 的 φ 环：φ 环只说”下一轮的值由上一轮决定”，不告诉你第 $i$ 轮是多少；addrec 把它变成关于迭代次数的闭式，于是”循环结束后这个变量是多少””第 $i$ 轮的地址是多少””这个循环一共转几次”都成了可以代 $i$ 去算的代数问题（引 4.2/4.3、定理 4.5 全部建立在这一步上）。工程上这些节点被记在 FoldingSet（LLVM 用来做结构哈希的容器：形状相同的表达式被折叠成同一个节点）里，相同表达式共享同一个节点，所以 SCEV 的查询是查表而不是重算。

出处：ScalarEvolutionExpressions.h:332 class SCEVAddRecExpr（:324 的文件注释原话是 “a polynomial recurrence on the trip count of the specified loop”，并写明这是 SCEV 的主要对象、其余节点都是为它服务的基础设施；:330 是那条”所有操作数必须循环不变”的约束）；记号 $\{a,+,b\}$ 与 nuw/nsw 的写法见 ScalarEvolution.h:468（:473 拿 i32 {0,+,1} 举例）；算法路线的出处是 Wolfe, Beyond Induction Variables, PLDI 1992 与 Gerlek, Stoltz & Wolfe, TOPLAS 1995（demand-driven、沿 SSA 归纳并分类序列——正是 SCEV 的做法）。

引理 4.2（闭式与终值外提）。若出口计数 $\mathrm{EC}=n$ 静态已知，则归纳变量在出口处的值为 $a+b\cdot n$ ，可在循环外用一次乘加算出（SCEVExpander 物化）。证明：对 $i$ 归纳， $i=0$ 取 $a$ ， $i\to i+1$ 加 $b$ 。∎ 消费者：IndVarSimplify 的 final-value rewrite（循环外对终值的引用搬出循环）、FullUnroll 的常量代入、LoopFlatten 的合并计数、LoopDeletion 的 $\mathrm{EC}=0$ 证明。

出处：ScalarEvolution.cpp:8285 getTripCountFromExitCount、:8340 getSmallConstantTripCount；终值物化靠 SCEVExpander，消费方是 IndVarSimplify.cpp:9。

引理 4.3（溢出与扩宽）。 $\mathbb{Z}_{2^w}$ 中若 $a+nb$ 越出表示范围即回绕，nuw/nsw 事实随之失效（引 0.6）。把宽度扩到 $w'$ 使 $|a|+n|b|<2^{w'-1}$ ，则扩宽后的递推无回绕，推理合法，末尾截回原宽度无损。证明： $\mathbb{Z}\hookrightarrow\mathbb{Z}_{2^{w'}}$ 在该范围内是单射且运算保持，故截断是同构的逆。∎ 消费者：IndVarSimplify 的 widen、SCEV 的 wrap 事实传播、LoopVectorize 的指针递进、Float2Int 的可表示性检查。

出处：ScalarEvolutionExpressions.h:217 的 hasNoUnsignedWrap()/hasNoSignedWrap()，以及 ScalarEvolution.h:468 的 nusw/nssw 传播规则；溢出语义本身在 LangRef §add；扩宽实现在 IndVarSimplify 的 WidenIV（IndVarSimplify.cpp:9）。

定理 4.4（do-while 正规形）。while-do 与”preheader 里预检 + latch 尾测”的 do-while 在 (i) 首次条件求值结果相同、(ii) 条件表达式无副作用时等价。证明：对迭代次数归纳。 $n=0$ ：原版不进 body，新版预检失败直落 exit，事件集同为空； $n\geq 1$ ：两版执行同一段 body 序列，第 $n$ 次迭代后条件变假，原版在头部退出、新版在尾部退出，中间的判断值相同。∎ 代价：条件被求值两次（零次迭代的那条路径上多一次），故用权重 $\{1,127\}$ 计价（ $p_{\text{zero-trip}}=1/128$ ，见引 6.2）。消费者：LoopRotate、LICM 的推测授权（尾测形确立”至少执行一次迭代”⇒ (M3) 的 $f_B\geq f_A$ 成立）、SCEV 的 trip-count 推导、FullUnroll/Vectorize 的”body 是直线块可整体复制”前提、LoopDeletion。

出处：LoopRotationUtils.cpp:52（rotate 本体）与 :49（ZeroTripCountWeights[] = {1, 127} 就在这一行）；官方图示见 LoopTerminology.md 的 rotated loop 一节；推测授权翻转的实现见 LICM.cpp:192。

定义 4.4a（迭代空间）。给循环的每个迭代变量一个坐标，一组坐标就唯一确定”这一趟要执行循环体里的哪些语句”；把所有可能的坐标收集起来，就是迭代空间（iteration space）。单层 for (i = 0; i < n; ++i) 的迭代空间是 $\{0,1,\dots,n-1\}$ ，共 $n$ 个点；两层嵌套 for (i = 0; i < n; ++i) for (j = 0; j < m; ++j) 的是矩形 $\{(i,j)\mid 0\leq i<n,\ 0\leq j<m\}$ ，共 $n\cdot m$ 个点。空间里的一个点 $\vec i$ 就是一次具体的迭代（后文说”第 $i$ 次迭代”即指此），点与点之间的字典序就是原始的执行顺序。

引入坐标视角的理由是：循环变换（interchange / flatten / distribute / fuse）本质上都是对迭代空间做一个重排映射 $\sigma$ ，而合法性判据只有一句—— $\sigma$ 必须保持数据依赖的先后（定理 4.5）。有了坐标，”能不能换序”就从逐行读代码变成算一个映射。

出处：迭代空间与依赖向量的说法出自 Allen & Kennedy, Automatic Translation of Fortran Programs to Vector Form, TOPLAS 1987，以及 Wolfe, High Performance Compilers for Parallel Computing（Addison-Wesley, 1995；书无 DOI，迭代空间与依赖向量是它的标准内容）；LLVM 侧用到这个词的地方例如 LoopFlatten.cpp:941（”select the original version at runtime if the iteration space is too large”）。

定理 4.5（依赖保持 = 调度合法性）。设迭代空间 $I$ （定义 4.4a），依赖 $(s,t,\vec d)$ 表示 $s$ 在第 $\vec i$ 次迭代的执行与 $t$ 在第 $\vec i+\vec d$ 次迭代的执行之间有数据依赖（ $\vec d$ 即依赖向量：两次迭代的坐标差）。调度变换 $\sigma:I\to$ 执行序合法 $\iff$ 对一切依赖， $\sigma(\vec i+\vec d)$ 排在 $\sigma(\vec i)$ 之后。推论（同一定理的几个特例，逐个列出）：

\begin{aligned} \text{interchange:}\ &\sigma(i,j)=(j,i),\ \text{合法}\iff\text{一切 }\vec d\text{ 在新维序下字典序非负}\\ \text{flatten:}\ &\sigma(i,j)=i\cdot m+j,\ \text{双射且保序（}(i,j)\text{ 字典序}\leftrightarrow k\text{ 数值序）}\\ \text{distribute:}\ &\text{语句分组后不存在"后组}\to\text{前组"的依赖}\\ \text{vectorize:}\ &\sigma\text{ 把 VF 个连续迭代（VF = vectorization factor，向量宽度）压成一步}\Rightarrow \vec d=\vec 0\ \vee\ d\geq\mathrm{VF}\\ \text{LICM:}\ &\vec d\text{ 的循环不变分量为 }0\Rightarrow\text{该指令可移出循环} \end{aligned}

消费者：LoopInterchange、LoopFlatten、LoopFuse（引 4.6）、LoopDistribute、LoopVectorize、LICM、LAA（ $\vec d$ 的生产者，见分析章）。这一条是循环变换合法性的统一判据：后文所有循环变换的合法性证明都引用它。

出处：依赖向量的原始定义在 Allen & Kennedy, Automatic Translation of Fortran Programs to Vector Form, TOPLAS 1987；调度合法性的仿射版本见 Feautrier, IJPP 1992, Part I 与 Part II。LLVM 侧： $\vec d$ 的生产者 LoopAccessAnalysis.h:1049，消费者 LoopInterchange.cpp、LoopFlatten.cpp、LoopDistribute.cpp、LoopVectorize.cpp:1172（runtime checks）、LICM.cpp:935（提升候选的三重检查）与 :1294 canSinkOrHoistInst（访存类指令能不能搬的专项判定）。

引理 4.6（fuse 的精确条件）。两相邻循环 trip count 同为 $n$ ，融合合法 $\iff$ 不存在 $B_2\to B_1$ 的依赖，且一切 $B_1\to B_2$ 的依赖距离 $\geq 0$ 。证明：原执行序中 $B_1(i)$ 在时刻 $i$ 、 $B_2(j)$ 在时刻 $n+j$ ；融合后 $B_1(k)$ 在 $2k$ 、 $B_2(k)$ 在 $2k+1$ 。依赖 $B_1(i)\to B_2(j)$ 要求 $2i<2j+1\iff i\leq j$ ，即距离 $\geq 0$ ；依赖 $B_2(i)\to B_1(j)$ 要求 $n+i<j$ ，而 $j<n$ ，不可能。∎

出处：LoopFuse.cpp；fusion/distribution 的依赖判据最早系统写在 Allen, Callahan & Kennedy, Automatic Decomposition of Scientific Programs for Parallel Execution, POPL 1987。

引理 4.7（结合律的定义域）。整数加减在 $\mathbb{Z}_{2^w}$ 中结合且交换，故 reduction 重排无条件合法；浮点不结合（舍入误差），故向量化的 reduction 例外需要 reassoc/contract 一类 fast-math 授权，否则定理 4.5 的 vectorize 推论中 $\vec d=\vec 0$ 那一支不成立。证明： $\mathbb{Z}_{2^w}$ 是交换环； $\mathbb{R}$ 上的浮点子集在 $\oplus$ 下不是半群。∎ 消费者：LoopVectorize、SLPVectorize、Reassociate（同一环引理的另一面）、Float2Int（反向：证明浮点链实际上落在整数环里）。

出处：授权开关就是 LangRef §Fast-Math Flags 的 reassoc；整数侧的实现 Reassociate.cpp:436 LinearizeExprTree；向量化侧的 reduction 处理在 LoopVectorize.cpp。

引理 4.8（不变条件的循环外化）。若条件 $c$ 的操作数全部定义在循环外，则由引 2.6 得 $c$ 循环内恒定，于是

\texttt{loop}\{\,\texttt{if}(c)\,B_1\ \texttt{else}\ B_2\,\}\;\equiv\;\texttt{if}(c)\,\texttt{loop}\{B_1\}\ \texttt{else}\ \texttt{loop}\{B_2\}

证明：对迭代次数归纳，每次迭代内 $c$ 同值 ⇒ 每次迭代走同一支。∎ 消费者：SimpleLoopUnswitch、LICM 的分支外提、LoopFlatten 的前提检查、FullUnroll 后 guard 的常量折叠。

出处：SimpleLoopUnswitch.cpp:86 EnableNonTrivialUnswitch 与 :169 NonTrivialUnswitchCandidate（克隆预算就挂在这个结构上）；不变性判定用 LoopInfo.cpp:67 的 Loop::isLoopInvariant，SimpleLoopUnswitch 自己的调用点在 :577（if (L.isLoopInvariant(Cond))）。

T5 内存版本与别名：堆上的 SSA

定义 5.1。MemoryLocation $=(\text{基址},\text{偏移},\text{大小})$ 外加 TBAA 标签（type-based alias analysis：按类型元数据判别名）； $\mu_k$ 表示第 $k$ 次 may-write 之后的堆状态。两个 Location 的关系只有四种：不交、包含、部分重叠、全等，由偏移与大小的区间运算决定（引 5.5）。

出处：MemoryLocation.h:217 class MemoryLocation，同文件 :40 起的一段注释把”精确/不精确的 LocationSize”说得很清（就是区间代法的输入）；GEP 分解见 BasicAliasAnalysis.cpp:602 DecomposeGEPExpression。

定理 5.2（堆版本链 = 单地址 SSA）。把每次 may-write 视为对”整个堆”的一次定义，按定理 2.2 的 IDF 构造在汇合处插 MemoryPhi，即得堆状态的最小 SSA 形式（定义 2.1a：”最小”说的是 MemoryPhi 的数量，不是 Def 的数量）；再用 AA 把”整个堆”细化到 MemoryLocation 粒度，load 挂到最近的可能 def 上（MemoryUse）、store 生成 MemoryDef、call 保守地生成 Def。证明：这是定理 2.2 在”变量 = 堆”上的直接实例，细化那一步是引 1.7（关系加细 ⇒ 重算一遍）。∎ 消费者：MemorySSA 本体、DSE、EarlyCSE 的 mem 模式、LICM 的 promote、LoopIdiomRecognize、GVN 的 load 折叠、MemCpyOpt。

出处：官方设计文档 MemorySSA.md（”trivial heap versioning” 这个自称就在那里）、MemorySSA.h:9；MemoryPhi 复用的是同一个 IDF 计算器 GenericIteratedDominanceFrontier.h:58——这表明”堆也是 SSA”是实现事实，不是类比。

引理 5.3（最近覆盖 def）。load $\ell$ 的取值 = 支配 $\ell$ 的、最近一个与 $\ell$ 的 Location 非 NoAlias 的 def 所写的值。证明：对版本链归纳——中间被跳过的版本要么不支配 $\ell$ （引 2.7），要么 AA 判为 NoAlias（引 1.4 的合成结论），两者都不改变 $\ell$ 读到的字节。∎ 消费者：GVN（load→寄存器/常量）、EarlyCSE、DSE、LICM 提升 must-alias 访存、MemCpyOpt 的区间推理。

出处：MemorySSA.h:1035（MemorySSAWalker::getClobberingMemoryAccess 声明）；典型调用点 EarlyCSE.cpp:1043（注释直接点名）与 :1097。

引理 5.4（私有存储提升）。若地址 $a$ 从不逃逸（不被存入可观测位置、不作为实参传出、不被 volatile 访问、其 alloca 不出函数），则 $a$ 指向的存储是私有的，其内容完全由本函数内的 store 序列决定；于是 $(a,\text{off},\text{size})$ 这一”片”可替换为一个 SSA 值，phi 插入点按定理 2.2 计算。证明：私有性 ⇒ 该存储上不存在任何观测点（OP1/OP2/OP3 都碰不到它），由定义 0.1b 它的写一次也不进 trace ⇒ 用寄存器复现同一 store/load 序列即可让 $\mathcal{O}$ 不变；phi 位置由定理 2.2 给出最小构造。∎ 这一条被多个 pass 共用：SROA（聚合切片后逐片提升）、mem2reg（不切片的退化情形）、GlobalOpt（地址未逃逸的全局）、LICM 的 promote-to-register（把”循环内 must-alias 且循环内外无别名访问”的单元提升），以及 DSE 消除整块 alloca 的那一路。

出处：PromoteMemoryToRegister.cpp:1259 PromoteMemToReg（mem2reg）、SROA.cpp:9、GlobalOpt.cpp:9、LICM.cpp:526 promoteLoopAccessesToScalars；”从不逃逸”的判定（位枚举）在 ModRef.h:365 CaptureComponents 与 :414 CaptureInfo。

引理 5.5（区间代数）。设两次访问的区间为 $[o_1,o_1+s_1)$ 与 $[o_2,o_2+s_2)$ ，则

[o_1,o_1+s_1)\subseteq[o_2,o_2+s_2)\iff o_2\leq o_1\wedge o_1+s_1\leq o_2+s_2

包含即覆盖。推论三条：源区刚被常数写满的 memcpy 可换 memset；相邻同值 memset 可合并为一次；被后续全覆盖 store 吞掉且中间无 may-alias 读的 store 是死的。消费者：DSE、MemCpyOpt、BasicAA、LAA、LoopIdiomRecognize。

出处：BasicAliasAnalysis.cpp:1105 aliasGEP（区间比较的主体）、MemoryLocation.h:40（区间大小）、DeadStoreElimination.cpp:9（”覆盖即死”的消费方）。

引理 5.6（别名不可判定 ⇒ 只能分层）。指针的逃逸路径不可静态穷尽（可经任意次传递、存入任意容器、跨模块），故别名问题是不可判定的；工程解是引 1.4 的保守合成分层。消费者：AAManager 与它的全部层、LAA、内联的 mod-ref 剪枝、向量化合法性、LICM。这条同时说明安全性约定的来源：任何一层误答 NoAlias，产出的就是语义错误的程序，而且形态合法、Verifier 不报。

出处：不可判定性：Landi, Undecidability of Static Analysis, ACM LOPLAS 1992；分层的官方说明 AliasAnalysis.md；聚合实现 AliasAnalysis.cpp:126。

T6 频度与代价：收益判定的统一标尺

定义 6.1。边概率 $\Pr(p\to b)$ 由静态启发（cold/likely 属性、!prof 元数据、默认偏置）或 PGO 计数给出；块频度满足

f_b=\sum_{p\to b}f_p\cdot\Pr(p\to b),\qquad f_{\mathrm{entry}}=1

这是线性方程组 $(I-A^{\top})f=e$ 。循环使 $I-A^\top$ 奇异，故按 SCC 消元或迭代求解，最后整体缩放到不溢出的定点表示（循环带放大因子，饱和时统一压缩）。

出处：BlockFrequencyInfoImpl.h:724（文件头把算法分三步，第三步就是 computeMassInFunction）与 :1259；定点缩放 BlockFrequencyInfoImpl.cpp:462 convertFloatingToInteger；边概率 BranchProbabilityInfo.h:108。论文：Wu & Larus, Static Branch Frequency and Program Profile Analysis, MICRO 1994（静态启发式估频度）、Ball & Larus, TOPLAS 1994（路径频度与最优 profiling）。

引理 6.2（期望迭代次数）。出口概率为 $p$ 的自然循环，期望迭代次数是 $1/p$ 。证明： $\mathbb{E}=\sum_{k\geq1}k(1-p)^{k-1}p=1/p$ 。∎ 于是 LoopRotate 的权重 $\{1,127\}$ 读作”循环几乎总会进入，零次迭代被当成极小概率事件”——按这条权重算，多复制一次条件求值的期望代价，远小于循环体每转一圈少一条回边的收益；unswitch 的克隆预算、inline 的 hot-callsite 特判、full unroll 的 $n\times|B|$ 上限，用的都是同一套按频度加权的算法。

出处： $\{1,127\}$ 的字面值就在 LoopRotationUtils.cpp:49（static constexpr uint32_t ZeroTripCountWeights[] = {1, 127};）；用同一套期望值算法的其他消费方见 InlineCost.h:38 与 ProfileSummaryInfo.h:372。

定义 6.3（盈亏）。 $\Delta=\sum_b f_b\cdot(\#\text{改前}_b-\#\text{改后}_b)$ ，接受 $\iff\Delta>0$ 且静态体积增量在预算内。换句话说：把每个块的指令减少量按该块的执行频度加权求和，为正才做这个改写。消费者：SimplifyCFG 的 hoist/sink、SpeculativeExecution、LoopRotate、InlineCost、SimpleLoopUnswitch 预算、LoopFullUnroll 预算、LoopIdiomRecognize 的 size 档、LoopSink、SLPVectorize 的打包树核算、ProfileSummaryInfo 的 hot/cold 阈值（分位数聚合出的全局标尺）。

出处：InlineCost.h:38（各档阈值常量：OptSizeThreshold = 50 等）、LoopUnrollPass.cpp:149 与 :337（trip count 与体积预算）、ProfileSummaryInfo.h:372。

注记 6.4（贪心判定的局部性）。 $\Delta_i$ 是用当时的 $f$ 度量的，而改写会改 $f$ ，故 $\sum_i\Delta_i\geq 0$ 不成立。这就是 LoopSink 必须排在 LICM 之后（把 LICM 提升位置不当的指令再移回循环内；它只在函数带运行期 profile 数据时才动手，理由见 LoopSink 那一条）、二轮 JumpThreading/CVP 必须存在、SLP 必须排在 unroll 之后的代价模型理由——形式化见定理 7.4。

出处：LoopSink.cpp:357（它的存在本身就是对”上一轮 $\Delta$ 算得不准”的承认）、PassBuilderPipelines.cpp:799（”再来一轮”的硬编码位置）。

T7 规范化与机会图：次序本身承载信息

定义 7.1（规范形）。重写系统 $R$ 的规范形是 $R$ 的不动点。引理 7.2（Newman）：若 $R$ 终止且局部合流，则规范形唯一。现实是 InstCombine 的规则集既不终止也不合流（存在互相创造应用条件、彼此反转的规则对），故实现是”worklist + 迭代上限”，流水线的补偿手段是在不同时机重复安排同一批规则：SimplifyCFG、InstCombine、LICM 在一条 -O2 路径上各出现多回（具体位置见后文 MoveAutoInit 那一条）。消费者：InstCombine、InstSimplify、SimplifyCFG、Reassociate、以及”再来一轮”的全部位置。

出处：Newman 引理：Newman, On Theories with a Combinatorial Definition of “Equivalence”, Ann. of Math. 1942；”不终止也不合流”的实证就在源码里——InstructionCombining.cpp:6198 的 if (Iteration >= Opts.MaxIterations && !VerifyFixpoint)，以及 :120–:123 那四个按迭代次数分档的统计计数器（NumOneIteration / NumTwoIterations / NumThreeIterations / NumFourOrMoreIterations；紧挨着的 :118 是总数计数器 NumWorklistIterations）。

定义 7.3（机会算子）。对每个 pass $i$ 定义 $O_i(x)$ = IR $x$ 中 $i$ 能改写的机会集。连边 $i\to j$ 当且仅当存在 $x$ 使 $O_j(P_i(x))\supsetneq O_j(x)$ （ $i$ 为 $j$ 创造机会）。

定理 7.4（清单是机会图的拓扑序）。-O2 清单是这张”创造—消费”图的一个拓扑序。证明：对流水线位置编号归纳——设在第 $k$ 个位置之前，一切由更早位置创造、且被第 $k$ 个位置消费的机会均已物化（这正是拓扑序的定义），故第 $k$ 个位置的 $O_k$ 达到它在本清单下能达到的最大值；去掉节点 $i$ ，其直接后继 $j$ 的前提失效， $O_j$ 严格变小。∎ 消费者：全部——这是本文最后一节”次序即算法”的形式化，也是 PassBuilderPipelines.cpp 里那些看起来冗余的重排（例如 SimplifyCFG 把已 rotate 的循环转回原形之后再 rotate 一次）的合法性说明。

出处：本文的抽象，无外部出处——机会算子与”清单是它的拓扑序”这个提法是本文为了把散在各处的”前提—产物”配对收成一句话而造的。它对应的经验事实全在 PassBuilderPipelines.cpp 的重复排布与旁注里（:620、:759、:765、:799、:1609）。

引理 7.5（表示盲区与对应的专门 pass）。SSA 数据流用的等价关系是”操作数同形 $\Rightarrow$ 值同”（GVN/EarlyCSE 的同余），它看不见下表这几类东西，每类由一个专门的 pass 按引 1.7 把关系加细后重算：

盲区	加细成什么	负责的 pass
聚合体（结构体/数组字段）	按访问区间切片后的独立单元（引 5.4）	SROA / mem2reg
位级死代码	use → demanded bits 位掩码（引 1.7）	BDCE
内存搬运与覆盖	区间代数（引 5.5）	MemCpyOpt / DSE
非支配分支上的重复访存	图形态（菱形）而非支配关系（引 2.5）	MergedLoadStoreMotion / GVNSink
循环内互相引用的死代码	可观测根的反向可达（定义 0.1a + 引 2.5）	ADCE

出处：表中这几个 pass 的文件头各自说明了它处理的表示形式——SROA.cpp:9、BDCE.cpp:1（标题就写着 bit-tracking）、MemCpyOptimizer.cpp、MergedLoadStoreMotion.cpp:11（diamond/hammock）、ADCE.cpp:198（”Collect the set of ‘root’ instructions that are known live”）。

引理 7.6（代数等价 → 语法同形）。把加法链（含 sub 的取负展开）规约为系数向量后，

e\ \equiv\ \sum_i c_i x_i + k\quad(c_i,k\in\mathbb{Z}_{2^w})

\mathbb{Z}_{2^w}

是交换环，故链内可任意重排、合并同类项（

2x+3x=5x

），且该表示在给定项序下唯一。于是"代数等价"变成"语法同形"，正好落进 GVN/EarlyCSE 的同余关系。消费者：Reassociate（生产者）、GVN、EarlyCSE、InstCombine、ConstraintElimination（求解器只接受规范形输入）、SCCP。*证明中唯一需要注意的是溢出标志*：链上若带 `nsw/nuw`，重排会改变 poison 出现的位置，故必须按引 0.6(b) 重新证明，或干脆不动这条链。

出处：系数向量与重排的实现 Reassociate.cpp:436 LinearizeExprTree、:449（注释原话”the number of times that operand occurs in the linearized expression”就是系数）、:626 RewriteExprTree、:209 BuildRankMap（项序）；”同形才能认出等价”这一端的经典出处是 Alpern, Wegman & Zadeck, Detecting Equality of Variables in Programs, POPL 1988 与 Click, Global Code Motion / Global Value Numbering, PLDI 1995。

T0–T7 与消费者的对照见下表（后文每个 pass 的证明只往这张表里引）：

定理	一句话	消费者（列出的只是其中几个）
0.5 UB 可剪	必然 UB 的路径没有行为要保护	SCCP · JumpThreading · CVP · LoopDeletion · WholeProgramDevirt
0.6 标志即前提	nsw 是可消费的不等式，也是需证明的义务	CVP · Reassociate · IndVarSimplify · SCEV · FullUnroll · Vectorize
0.7 纯指令可推测	不会 UB 的纯指令搬到哪都对	SpeculativeExecution · MergedLoadStoreMotion · GVNHoist · LICM · LoopSink
1.5 MOP⊑MFP	单调框架的结论只会偏保守	SCCP · IPSCCP · GVN · CVP · ConstraintElim · CalledValuePropagation
1.4 join 聚合	多层结论取最不确定者	AAManager · ReversePostOrderFunctionAttrs · LAA 回填 · AssumptionCache
2.2 SSA 构造	phi 恰插在迭代支配边界	mem2reg · SROA · MemorySSA · LICM promote · GlobalOpt
2.4 M1–M4	代码搬迁的四条合法性	LICM · LoopSink · GVNHoist · GVNSink · SpeculativeExecution · MergedLoadStoreMotion · TailCallElim
2.5 后支配	必然执行 ⇒ 可当落点/可标活	ADCE · GVNSink · MergedLSM · LoopDeletion · SimplifyCFG
2.6 支配⇒循环内恒定	循环外定义 + 循环内无重定义 = 不变量	LICM · SimpleLoopUnswitch · LoopFlatten · LAA · LoopIdiom
3.4 单次传递即达不动点	缩点逆拓扑上单次传递即达不动点	PostOrderFunctionAttrs · Inliner · IPSCCP · nocapture 归纳
4.5 依赖保持	调度合法 ⟺ 依赖序不被颠倒	Interchange · Flatten · Fuse · Distribute · Vectorize · LICM · LAA
4.7 结合律的域	整数环随便重排，浮点不行	Vectorize · SLP · Reassociate · Float2Int
5.3 最近覆盖 def	load 的值来自支配它的最近别名 def	GVN · EarlyCSE · DSE · LICM · MemCpyOpt
5.4 私有存储提升	不逃逸的地址可换成寄存器	SROA · mem2reg · GlobalOpt · LICM promote · DSE
5.5 区间代数	包含即覆盖	DSE · MemCpyOpt · BasicAA · LAA · LoopIdiom
6.3 盈亏	一切收益判定都是频度加权的差值	SimplifyCFG · SpecExec · LoopRotate · InlineCost · Unswitch · FullUnroll · LoopSink · SLP
7.4 拓扑序	清单是机会图的拓扑序	全部（”再来一轮”的每一次都是它的实例）
7.6 规范化	代数等价先变成同形才好认	Reassociate · GVN · EarlyCSE · InstCombine · ConstraintElim · SCCP

分析 Pass：三类只读事实

变换 pass 是本文的主体，但它们每一步都依赖一组只读的分析。分析回答的都是”重算代价高、IR 一改就作废”的派生事实：支配关系是一次图上不动点，SCEV 是一次符号推导，MemorySSA 是一次全函数建链——建一次的开销常常高于消费它的那个变换本身。机制（懒算、缓存键、PreservedAnalyses——每个 pass 返回的”哪些分析结论在我之后仍然成立”的声明集合，manager 据此逐份判定哪份结论还活着）留在末章，这里只讲每个分析算的是什么、凭什么算得完、谁在消费。格式统一：概念 → 算法 → 产出 → 消费方 → 证明，证明一律往回引通用理论。

DominatorTree / PostDominatorTree（domtree/postdomtree，Dominators.h:241 / PostDominators.h:48）

概念：定义 2.1 的全部——单入口 CFG 上的支配偏序，压成 idom 树；后支配在反向图上镜像。算法：按不动点迭代 $\mathrm{idom}(b)=\mathop{\sqcap}\limits_{p\to b}\mathrm{idom}(p)$ （前驱 idom 的最近公共祖先）至收敛，再做一遍 DFS 预编号。产出：dominates/properlyDominates 谓词、树本体（子表、深度、块↔节点双射）、按需现算的支配边界与迭代支配边界（IDFCalculator 用的是 DJ 图（dominator joiner graph：在支配树上补进”祖先指向非后代”的辅助边所得到的图）上的线性时间算法，Sreedhar & Gao，GenericIteratedDominanceFrontier.h:99，而非朴素逐块枚举）。消费方：mem2reg 的 phi 插入点、GVN 折 load、LICM 的提升落点、ADCE 的控制依赖（用后支配树），以及一切引 2.4/2.5/2.6 的场合。由于查询频繁、重建代价又高，它对 preserve 声明的要求最严格——配套的 DomTreeUpdater 允许改写者批量登记删边/插边、延后一次合并重建，SimplifyCFG 合块、LoopRotate 造 preheader 走的都是这条路。

证明（定理 1.2、引 2.7、定理 2.2）。把”当前 idom 估计”排成格： $x\sqsubseteq y\iff \mathrm{depth}(x)\geq\mathrm{depth}(y)$ （越深越保守），格的高度由块数封顶（再深的估计也不会深过树本身），转移函数单调（前驱估计变浅只会让 LCA 变浅），故由定理 1.2 迭代必然收敛、轮数同样由块数封顶，收敛值即真 idom——真 idom 是满足 $f(x)\sqsubseteq x$ 的最小元，正是 $\mathrm{lfp}$ 。查询降为区间比较由引 2.7 给出。支配边界与 IDF 的存在性与最小性由定理 2.2 的 $J^+$ 构造保证，因此”φ 插在这些位置既足够又无多余”是定理而不是启发式。∎

出处：Lengauer & Tarjan, TOPLAS 1979；LLVM 实际用的 Semi-NCA 与增量更新见 GenericDomTreeConstruction.h:12、:31（arXiv:1604.02711）；IDF 的线性算法 Sreedhar & Gao, POPL 1995；SSA 构造 Cytron et al., TOPLAS 1991。

LoopInfo（loops，LoopInfo.h:433）

概念：自然循环与森林（定理 3.2）。算法：一遍 DFS 标记回边（当前栈上的前驱即头），沿前驱集回溯收块求极小集， $O(V+E)$ 。产出：每个 Loop 持块列表、header、parent/children、latch 与出口边集合，外加块→循环反向索引 getLoopFor 与 O(1) 包含判定。消费方：LPM 的逆后序 worklist（引 3.5）、SCEV 的每个 trip count 以 Loop 为索引、循环被改写后 LPMUpdater 同步森林并补新循环。

证明（引 3.1、定理 3.2）。回边判定” $v$ 在 $u$ 的 DFS 栈上”就是引 3.1 的回边定义本身（递归进行到 $u$ 时，栈里装着的正是尚未退出的一串祖先）；单入口由 $h\ \mathrm{dom}\ n$ 与支配传递性给出；森林性质由”若 $x$ 同属两个循环则两头互相支配，故二者可比”给出。于是 $\mathrm{Loop}$ 集合是良基偏序，逆后序遍历 = 子先于父（引 3.5）。∎

出处：LoopInfo.cpp:9 的文件头与 LoopInfo.h:433；术语与图示的官方版本 LoopTerminology.md；回边判定 Tarjan, SIAM J. Comput. 1972。

ScalarEvolution（scalar-evolution，ScalarEvolution.h:9）

概念：回答”这个值随迭代如何变化”，即循环上的闭式求解问题。算法：沿 def-use 把每条指令归纳成符号 SCEV 节点：常数、entry 处的循环不变量、加法链求解成 $\{a,+,b\}_{L}$ （等差/高阶套层，乘法吸收常数因子），溢出性质按环上语义传播；节点 memoize 在 FoldingSet，复合表达式共享子项；对出口条件与归纳变量的符号差解出精确/上界执行次数。产出：getSCEV 闭式、getTripCountFromExitCount/getSmallConstantTripCount、hasNoUnsignedWrap/hasNoSignedWrap 一族溢出事实；SCEVExpander 把闭式物化回指令序列——IndVarSimplify 那一步”在循环外重算终值”就是它做的。消费方：full unroll 与 vectorize 需要知道迭代次数是否静态可知、LoopDeletion 拿它出 $\mathrm{EC}=0$ 的证明、unswitch 拿它判 trip count、LAA 拿它做距离比较、IndVarSimplify 拿它做扩宽与终值外提。代价：结论是对当时 IR 的推导缓存，IR 改写后最容易失效——PreservedAnalyses 里那个显式丢弃某份结论的 abandon 用得最多的就是它（默认流水线里 ForgetAllSCEVInLoopUnroll 这个参数名直接说明了这一点），loop 流水线从内到外反复重建也是为此（重建有界，引 1.3）。

证明（引 4.2、引 4.3、引 2.6）。闭式正确性：对迭代次数 $i$ 归纳， $i=0$ 时值为 $a$ （entry 处定义或循环不变量，由引 2.6 保证每次迭代同值）， $i\to i+1$ 时 latch 上的 add 恰好加 $b$ ，故 $\{a,+,b\}(i)=a+bi$ 。出口计数：设出口条件为 $\{a,+,b\}<c$ 且 $b>0$ ，则首次不满足的迭代序号是

\mathrm{EC}=\max\!\left(0,\ \left\lceil\frac{c-a}{b}\right\rceil\right)

即最小的 $i$ 使 $a+bi\geq c$ ；这是引 4.2 的逆用。无回绕前提由引 4.3 保证： $|a|+n|b|<2^{w-1}$ 时环嵌入是单射，故上述整数推理与 $\mathbb{Z}_{2^w}$ 中的实际运算一致；不满足时 SCEV 只能给出 nuw/nsw 缺失的保守闭式，getSmallConstantTripCount 随之返回未知——结论保守是允许的（推论 1.6），结论超出真实情形是不允许的。∎

出处：ScalarEvolution.h:9、ScalarEvolutionExpressions.h:332；算法路线 Wolfe, PLDI 1992 与 Gerlek, Stoltz & Wolfe, TOPLAS 1995。

MemorySSA（memoryssa，MemorySSA.h:9）

概念：SSA 处理寄存器；内存没有现成的 SSA 形式，MemorySSA 用堆状态的版本链为它建立同样的性质——即定理 5.2（把定理 2.2 的构造用在”变量 = 整个堆”上），φ 的位置同样取最小形式（定义 2.1a）。算法：以 MemoryLocation 为粒度沿支配树传播当前 def，汇合处用 IDFCalculator 插 MemoryPhi；load 经 walker 沿 def 链跳过不可能影响其 Location 的版本、挂到最近可能 def 上记为 MemoryUse；store 生成 MemoryDef；call 对全堆保守生成 def（纯读/无副作用的由 AA 降级）。文件头的自称是 “a trivial form of ‘heap versioning’”（MemorySSA.h:15）。产出：叠在指令之上的 Use/Def/Phi 节点图，getWalker()->getClobberingMemoryAccess 与其反向 use 遍历；MemorySSAUpdater 保改写方的增量一致性，-verify-memoryssa 可整体校验。消费方：EarlyCSE 的 mem 模式、DSE 的写覆盖判定、LICM 的提升与 promote、LoopIdiomRecognize 的”整个循环都在写常数”匹配——都归结为沿 def 链走一步。也因此有流水线里一条精确到名字的失效声明：LPM1 进 loop 时 UseMemorySSA=true（:755），LPM2 则传 false（:763），理由是注释原话：”The loop passes in LPM2 (LoopIdiomRecognizePass, IndVarSimplifyPass, LoopDeletionPass and LoopFullUnrollPass) do not preserve MemorySSA. All loop passes must preserve it, in order to be able to use it.”（:759）。

证明（定理 5.2、引 5.3、引 1.7）。把”堆”当唯一变量，每次 may-write 当一次赋值，定理 2.2 直接给出 MemoryPhi 的最小插入点集，故版本链是 SSA 的实例而非新发明；随后按引 1.7 把”整堆”这一关系加细到 MemoryLocation 粒度，加细后 use 挂到最近可能 def 上正是引 5.3 的结论，跳过的那些版本由 AA 的 NoAlias（引 1.4 的合成结果）证明与本次读无关。∎

出处：官方设计文档 MemorySSA.md、MemorySSA.h:9；MemoryPhi 复用 IDF 计算器见 GenericIteratedDominanceFrontier.h:58。

AAManager（aa，AliasAnalysis.h:967）

概念：别名不可判定（引 5.6），工程上的答案是分层启发式的保守合成。算法：它不是一种分析，而是结论聚合器——一次查询走 AAResults::alias(LocA, LocB, AAQI, CtxI)（两个实参都是 MemoryLocation，即定义 5.1 的基址加大小），把 BasicAA（GEP 偏移与类型几何的区间推理，引 5.5）、ScopedNoAliasAA（!alias.scope 与 !noalias 两组元数据：前者声明本指令属于哪些作用域，后者声明与哪些作用域不别名）、TypeBasedAA（!tbaa 标签不同即不别名）、GlobalsAA（全局变量的 mod/ref 摘要）与各插件的局部答案保守合成，再过 noalias-metadata 链与 loop-non-alias 缓存（LAA 产出回填处）。产出：NoAlias/MayAlias/PartialAlias/MustAlias 四值判断（查询带着 MemoryLocation 的 size，使区间级而非点级判定成为可能）；各层分析由 addAAResult 逐个登记，因此分析家族可以按 IR 单元动态注册。消费方：LICM 提 load、GVN 折 load、DSE 判覆盖、向量化证距离、内联时 mod-ref 剪枝；模块优化阶段的 RecomputeGlobalsAAPass 重算全局摘要再写回（:1557）。

证明（引 1.4、引 5.5、引 5.6）。四值排成格 $\mathrm{NoAlias}\sqsubset\mathrm{Partial/Must}\sqsubset\mathrm{MayAlias}=\top$ ，聚合取 join，故整体结论不会比任何一层更精确；由引 1.4 的推论，整体健全性 = 每一层健全性的合取，任何一层误答 NoAlias 即产出错程序，且错在语义（定义 0.2 的 (i)）而非形态，Verifier 不报。区间级判定是引 5.5 的直接应用： $(o_1,s_1)$ 与 $(o_2,s_2)$ 不交 $\iff o_1+s_1\leq o_2\ \vee\ o_2+s_2\leq o_1$ ，这条不等式在 TBAA 标签相同的前提下就是 BasicAA 的全部推理。∎

出处：分层的官方说明 AliasAnalysis.md；接口 AliasAnalysis.h:967，聚合实现 AliasAnalysis.cpp:126，区间推理 BasicAliasAnalysis.cpp:1105；不可判定性 Landi, LOPLAS 1992。

LoopAccessAnalysis（access-info，LoopAccessAnalysis.h:1049）

概念：向量化的合法性 = 循环内访存对之间不存在”不安全”的跨迭代依赖。算法：把循环内的访存指令两两配对，把依赖判定归约为下标的符号比较——仿射下标交给 SCEV 解距离与方向，AA 结论剪掉不可能别名的对，非仿射访问归入 gather/scatter（按一组离散地址逐元素读/写的向量访存形式）档案；距离无法静态证明的降格为运行期两两比较（检查基址区间重叠与 stride），失败则整体回退标量版本。产出：可向量化访存集合、runtime check 清单、每依赖的静态/待证/不可向量化三分类、每访存的 stride 档案。消费方：LoopVectorize 的合法性判定基本是直接转发它的结论；loop-non-alias 结论回填 AA 缓存供 LICM/GVN 复用——这也是它身为 loop 分析却影响函数全局的原因。

证明（定理 4.5、引 4.3、引 1.4）。LAA 是定理 4.5 里 $\vec d$ 的生产者：对访问对 $(A[\alpha(i)],A[\beta(j)])$ ，若 $\alpha,\beta$ 均为仿射（SCEV 闭式，引 4.2）则依赖存在的必要条件是 $\alpha(i)=\beta(j)$ 有整数解，解出的 $j-i$ 即 $\vec d$ ；无回绕由引 4.3 保证。三分类对应三种证明状态： $\vec d$ 已知且满足定理 4.5 的调度约束（静态合法）、 $\vec d$ 依赖运行期基址（生成 check，把输入空间二分为”可证安全”与”回退”，两支各自合法）、AA 判 MayAlias 且非仿射（不可向量化）。runtime check 的健全性来自引 0.5 的镜像用法：check 失败即走标量版，两版在同一输入下的事件集相同。∎

出处：依赖与距离的框架见定理 4.5 的出处（Allen & Kennedy, TOPLAS 1987、Feautrier, IJPP 1992）。实现侧：单个循环的分析结果 LoopAccessAnalysis.h:726 class LoopAccessInfo，逐对分析的入口 :826 analyzeLoop(AAResults*, ...)；运行期检查的结构 :543 class RuntimePointerChecking，取出接口 :752 getRuntimePointerChecking；按循环缓存的管理器 :1015 LoopAccessInfoManager——它自己持有一份 AAResults &（:1021），这就是”loop 分析却影响函数全局”的实现形态；把检查变成代码的位置 LoopVectorize.cpp:1172。

LazyCallGraph（module 层 lcg，PassRegistry.def:31）

概念：优化器使用的调用关系不能只统计 call 指令——一个当前只被存进 vtable 的函数，可能在内联之后出现的新调用点上被调到；这类潜在调用边必须一并计入。文件头注释开门见山：”NB: This is not a traditional call graph!”。算法：边的定义是引用可达（直接调用、函数地址逃逸均建边）；扫描按需展开（只分析已经被访问到的函数，因此称为 lazy），图随优化增量更新。产出：函数节点 + 引用边的图，附带可由 CGSCCPassManager 维护的 SCC 结构。消费方：CGSCC 层遍历序的基础——逆拓扑保证 callee 先于 caller，这正是内联一节那个遍历次序（引 3.3、推论 3.4）成立的前提。

证明（引 3.3、推论 3.4）。健全性方向是过近似：设运行期实际发生的调用边集为 $E_r$ ，LCG 的边集 $E\supseteq E_r$ ——因为任何一次调用都要求被调函数的地址在该调用点引用可达，而 LCG 把全部引用可达关系都建了边。缩点后是 DAG（SCC 缩点的标准结论），逆拓扑序存在且唯一到同构；由推论 3.4，任何”只依赖 callee 结论”的属性推断在此序上单次传递即达不动点。过近似不影响健全性：多出来的边只会让属性推断更保守（引 1.4 的 join 更多项）。∎

出处：设计说明就写在文件头——:13–:16 的 “NB: This is not a traditional call graph! It is a graph which models both the current calls and potential calls”，:18–:23 接着说明它的用途正是”保证所有 callee 先于 caller 被访问，因此适合组织 CGSCC 类优化（内联、outlining（把重复的代码段抽成一个函数）、参数提升）”；引用图是调用图的超集 :122；遍历序的契约 CGSCCPassManager.h:13；SCC 与缩点 Tarjan, SIAM J. Comput. 1972。

频度、profile 摘要与 assume：三个元信息分析

概念：支配、循环、调用图那几个分析回答”是否允许改写”与”改写是否安全”，这一类回答”改写是否有收益”。BlockFrequencyAnalysis/BranchProbabilityAnalysis（block-freq/branch-prob）——BPA（BranchProbabilityInfo）先给每条边定概率（静态启发：cold/likely 属性、llvm.expect（经 LowerExpectIntrinsic 降级为 !prof 元数据）、默认偏置；PGO 则由加载 pass 写入真实计数再折算），BFI 再解定义 6.1 的线性方程组，最后整体缩放到定点。产出：每块一个可比较的相对执行次数，边频度随之可得。ProfileSummaryAnalysis（ProfileSummaryInfo.h:372 的分析壳，结论本体是 :42 的 class ProfileSummaryInfo）——从函数 entry count 聚合出全模块热分布摘要（hot/cold 阈值由分位数算出），对外回答 isHotCount 与 isFunctionEntryHot。AssumptionCache（AssumptionCache.h:44 的缓存本体，:189 是包它的分析壳 AssumptionAnalysis）——收集全函数 llvm.assume 并按被假设的值建索引，查询接口是”关于 %x 我被告知了什么”；消费链两条：LazyValueInfo 持有一份 AssumptionCache *（LazyValueInfo.cpp:401），求某个值的范围时遍历 assumptionsFor(Val)（:846）——CVP 的事实就是经这条链拿到的；ConstraintElimination 则直接扫 llvm.assume intrinsic（ConstraintElimination.cpp:1462）；用不上的 assume 由 DropUnnecessaryAssumes 反向清理（默认流水线在向量化之后就调它一次，:1350）。消费方：SimplifyCFG 折哪边、hoist/sink 的盈亏（定义 6.3）、内联的 hot-callsite 特判、LoopSink 的落点、unswitch 的克隆预算。

证明（定义 6.1、引 6.2、引 0.5）。频度方程组的可解性：每个循环都必有出口（否则函数不终止，无需计价），故循环内概率乘积 $<1$ ， $(I-A^\top)$ 在每个 SCC 上可逆，解唯一且非负；定点缩放不改相对量级，故定义 6.3 的 $\Delta$ 符号保持不变——这是”频度只用于比较、不用于绝对判断”的形式理由。assume 的可用性：llvm.assume(c) 的语义是 $c$ 为假时该执行触发 UB，故由引 0.5，把 $c$ 当作使用点处恒真的事实使用是合法的；索引按被假设值组织只是查询效率，不改变健全性。∎

出处：静态估频度 Wu & Larus, MICRO 1994，路径频度与 profiling Ball & Larus, TOPLAS 1994；实现 BlockFrequencyInfoImpl.h:724、BranchProbabilityInfo.h:108、ProfileSummaryInfo.h:372、AssumptionCache.h:189。

TargetLibraryAnalysis（target-lib-info，TargetLibraryInfo.h:625）

概念：优化器不能假定 libc 存在——平台不同，名字、签名、可用集都不同。算法：字典本身由 TableGen 生成：TargetLibraryInfo.td 逐条给出库函数的符号名与签名（例如 :440 的 def memcpy_chk : TargetLibCall<"__memcpy_chk", Ptr, [Ptr, Ptr, SizeT, SizeT]>;——_chk 变体与标准名同典收录），TargetLibraryInfoImpl.td 定义参数类型的抽象（SizeT、Int32 这一档）；TargetLibraryInfoImpl（TargetLibraryInfo.h:93）按 triple 决定这一档平台认哪些名字，对外的查询类是 TargetLibraryInfo（:283）：getLibFunc(StringRef)（:349）、getLibFunc(const Function&)（:353）、getLibFunc(const CallBase&)（:359）把符号名解析回 LibFunc 枚举，has(LibFunc)（:392）回答”本平台有没有它”。产出：LibFunc 枚举 + 该平台的可用集与签名校验（isValidProtoForLibFunc，:340）。分配/free 家族的判定不在 TLI 里，而在 MemoryBuiltins.h 那一组工具（:56 isAllocationFn、:77 isLibFreeFunction、:127 getAllocationFamily），而它们的实参里都要带一份 TLI——本文说”平台库函数档案”时指的就是这个分工。消费方：InferFunctionAttrs 的标注、LibCallsShrinkWrap 的错误域、MemCpyOpt 的区间代数、ExpandMemCmp 的字展开、AA 判断”这个未知调用读不读内存”。不同 target 之间的优化差异，相当一部分来自这张表的内容差异。

证明（引 0.6 的同类）。TLI 给出的属性是断言而非推导，其健全性依赖一条外部约定：符号名 memcpy 指的就是标准语义的那个 memcpy（用户自行定义同名函数即破坏约定，因此 LLVM 提供 -fno-builtin 一类的开关让用户退出这条约定）。形式上它等价于给每个已知库函数附加一组引 0.6 式的前提，下游 pass 消费这些前提时的义务与消费 nsw 完全相同。∎

出处：字典与 triple 相关行为 TargetLibraryInfo.td 与 TargetLibraryInfoImpl.td；接口 TargetLibraryInfo.h:93 与 :283；分析壳 :621–:625，那里的注释顺手给了末章 preserve 讨论一个现成的例子：”this pass’s result cannot be invalidated, it is immutable for the life of the module”——一份不会因 IR 改写而失效的结论，自然可以被所有 pass 无条件 preserve。

VerifierAnalysis（verify，Verifier.h:109）

概念：整条流水线的正确性依赖一条前提：每个 pass 的 run 之后 IR 仍是合法 IR。而合法性本身是一组形态谓词：phi 入数与前驱严格对齐、每条指令类型匹配、SSA 赋值唯一、entry 块无前驱、定义支配使用。算法/产出：全量校验这些不变量，违例时输出到足以定位的粒度；验证器自身不做任何改写。消费方：-passes=verify 可插进流水线任意两个 pass 之间，把”谁把 IR 改坏了”定位到具体 pass；fat-LTO 流水线在把 bitcode 嵌进产物之前也排了它一次（:1821 的 if (Verify) 之下、:1822 的 MPM.addPass(VerifierPass())，紧挨着下一行的 EmbedBitcodePass）。

证明（定理 2.2 的形态侧）。”phi 入数 = 前驱数”与”定义支配使用”两条正是定理 2.2 构造的可检验形式：前者保证 phi 的选择函数是全函数（每个前驱都有对应入参），后者保证 SSA 值在使用点已定义。故 Verifier 通过 $\Rightarrow$ IR 是良构的 SSA。但它对定义 0.2 的 (i) 一无所知——AA 答错的 NoAlias、SCEV 算错的 trip count，形态全部合法。这也是本文把”健全性”与”良构性”分开写的原因：前者靠每个 pass 自证，后者才靠工具查。∎

分类如下：domtree/loops/lcg 是图分析，定义单元边界与改写合法性（T2/T3）；SCEV/MemorySSA/AA/access-info 是数据流分析，决定每次改写是否安全（T1/T4/T5）；profile/assumptions/TLI 是元信息分析，决定改写是否有收益（T6）。后文每个变换的”意义”一段最终都落回这三类里的某几个；而每个变换返回的那份 PreservedAnalyses，本质上就是在向这三类分别交代：哪些结论在该 pass 之后仍然成立（机制见末章）。

模块级前奏：把前端输出整理成可分析的形式

（PassBuilderPipelines.cpp:1113 起）

进正题前先说明 T0 那两个定义在本章的用法。定义 0.1a 里的 $W(a,v)$ 要求 $a$ 可观测：逃逸到本翻译单元之外、被 volatile/atomic 触及、或取自外部可见的全局；未逃逸的 alloca 与 internal 全局不在此列——引 5.4 的”私有性”就是这句话的形式化。定义 0.1b 再补一层：即便地址可观测，两次写之间没有观测点时前一次也不进 trace。本章 GlobalOpt 的三种情形分别依赖这两条。

InferFunctionAttrs（IPO/InferFunctionAttrs.cpp）——算法：只对声明（F.isDeclaration()）且未标 optnone 的函数动手（:29），拿符号名查 TargetLibraryInfo，命中即按该库函数的语义标注属性；标注逻辑不在本文件，而在 BuildLibCalls.cpp:336 的 inferNonMandatoryLibFuncAttrs：readnone（:66）、readonly（:99）、nounwind（:162）、参数 nocapture（:187）、nosync（:200）、nofree（:276）、willreturn（:282）都在那里加；带 nobuiltin 的声明则跳过不标（:30 的 !F.hasFnAttribute(Attribute::NoBuiltin)）——这就是 TLI 那条证明里”用户可以退出命名约定”在 IR 侧的开关（driver 侧对应 -fno-builtin）。效果：call 从”效果未知的副作用”变成带明确效果档案的调用点。意义：LICM 能否提升一个调用、内联是否复制它，判断依据全是这些 attribute；不先标注，后续所有 pass 只能按最坏情形保守处理。

证明（TLI 契约、引 0.6 同构、引 1.4）。属性是断言不是推导：标注 readonly 等于声称该 call 无写事件，此后 LICM 依引 2.4(M4) 判定”提升不改变内存可见性”、依引 0.7 判定”可推测”。故健全性完全外包给 TLI 的命名约定（符号 memcpy 即标准 memcpy）；一旦约定被破坏（用户自定义同名函数），错误落在定义 0.2 的 (i) 上而形态合法。这也说明了它为什么排在最前：下游对一次调用的判断，取决于它拿得到多少已知事实；事实还没标上，聚合出来的结论就只能停在最保守的那一格（引 1.4），标注晚一轮，整条流水线就多保守一轮。∎

EarlyFPM（流水线里的变量名，:1162）——几件轻量 pass 的组合：EntryExitInstrumenter（按 instrument-function-entry／instrument-function-exit 属性，在函数入口与出口插入 mcount、__cyg_profile_func_enter 那类插桩调用；这里传 PostInlining=false，处理的是”内联之前”的那一档属性）、LowerExpectIntrinsic（把 llvm.expect 降级为分支权重元数据；源码注释给的理由是 “Lower llvm.expect to metadata before attempting transforms. Compare/branch metadata may alter the behavior of passes like SimplifyCFG”，:1164）、再 SimplifyCFG → SROA → EarlyCSE。效果：块数与 alloca 数先降一轮，重复计算收敛。意义：内联阈值按函数体积算（定义 6.3），前端留下的冗余不清理，代价模型（cost model：把”这样改划不划算”折算成可比较的数）量到的就是无关代码的体积。O3 在此追加 CallSiteSplitting：按到达路径复制调用点、各自代入该路径已知的实参形态。

证明（引 0.5、引 1.7、定义 6.1）。LowerExpectIntrinsic 是恒等式改写加事实换通道： $\llbracket\texttt{llvm.expect}(x,c)\rrbracket=x$ 对一切 $x$ 成立（intrinsic 的语义就是”返回值等于第一参数”），故删除它不改变任何事件； $c$ 被记为 !prof 元数据，而元数据是定义 6.1 的合法输入通道——后续 pass 读得懂元数据、读不懂 intrinsic，这正是引 1.7 的一次加细：把”事实”从值域搬到元数据域后，消费者集合扩大了。CallSiteSplitting 的正确性靠引 0.5：复制调用点时，每条路径上”已知为假的实参形态”对应的分支被剪掉，剪掉的部分本来必然 UB 或必不可达。∎

IPSCCP（IPO/SCCP.cpp:9）——算法：在”值格 × 调用边可达格”上做跨过程的稀疏条件常量传播：实参常量沿调用边与形参 meet，形参收敛为常量后代入被调函数体继续传播；不能整体特化但值得区分调用形态的，克隆特化版本并改接调用边。效果：callee 内分支条件常量化的部分被死代码消除整块带走，参数位成为立即数。意义：这是把模块级信息换成收益最集中的一处——foo(42) 一旦确定，foo 里不会执行的那半个函数整块消失，影响范围超过任何局部改写。

证明（推论 1.6、推论 3.4、引 0.5）。格取 $L_v=\{\bot\}\sqcup\mathrm{Const}\sqcup\{\top\}$ （常数之间互不比较，故每个值的结论只有”不可达 / 某个常量 / 未定”这几档）、 $L_e=\{\text{不可达}\sqsubset\text{可达}\}$ ，联合格高度有限，由定理 1.2 终止；引 1.3 进一步给出 worklist 入队次数的上界：与图的规模成线性，倍数就是格的高度。健全性：转移函数单调（可达边只增不减、常数只在所有前驱一致时保留），故定理 1.5 给出 $\mathrm{MOP}\sqsubseteq\mathrm{MFP}$ ，推论 1.6 立即得出”形参被判为 $c$ $\Rightarrow$ 一切可达调用中该实参确为 $c$ “，代入合法；边被判不可达 $\Rightarrow$ 该调用点在任何真实执行中不发生 $\Rightarrow$ 引 0.5 授权整块删除。克隆特化是上下文敏感化：把 callee 复制一份后，副本拥有独立的格坐标，故不同调用形态不再互相 meet 成 $\top$ ——健全性由副本与原件逐点同构（推论 2.3 的重命名双射）保证。跨过程的遍历序按推论 3.4：callee 侧 SCC 先定型，caller 的事实才有处可传。∎

出处：稀疏条件常量传播 Wegman & Zadeck, TOPLAS 1991；跨过程那一半的经典出处 Callahan, Cooper & Kennedy, Interprocedural Constant Propagation, 1986；实现 SCCPSolver.h:66 与 IPO/SCCP.cpp:9。

CalledValuePropagation（IPO/CalledValuePropagation.cpp:9）——算法：把”哪些函数地址可能被存入哪个全局/参数”做一遍不动点传播，给候选集足够小的间接调用点挂上 !callees 元数据。用的是通用稀疏传播 solver（文件头原话：”similar to constant propagation and makes uses of the generic sparse propagation solver”）——就是 SCCP 那台机器换了一个格。效果：间接调用的目标集合成为 IR 里的显式事实。意义：收尾章的 devirtualization（去虚拟化：把间接调用改成直接调用）用的就是它提供的候选集——本 pass 只枚举候选、不做改写，因为此刻调用图还会被内联大幅改动。

证明（定理 1.2、引 1.4 的镜像）。格取函数集合的幂集，序为反包含（ $\sqsubseteq$ = 更大集合 = 更保守），join = 交集，故 $\mathrm{lfp}$ 是满足传播方程的最小候选集，即最精确的过近似。健全性方向与 LCG 相同（引 3.3 的证明）：每一次运行期的间接调用，其目标地址必在某处被写入过某个位置，而传播方程覆盖了全部写入—读取路径，故真实目标 $\in$ 候选集。由此 devirt 的合法性立刻得到：候选集为单元素 $\Rightarrow$ 运行期目标唯一 $\Rightarrow$ 改直调是等价的（事件集只把”间接跳转”换成”直接跳转”，两者都不在定义 0.1a 的字母表里）。∎

GlobalOpt（IPO/GlobalOpt.cpp:9）——算法：对地址从未逃逸的全局变量分情形：只写不读的删；初始化后只读的升 constant；只被单个函数触及的做与 mem2reg 同构的提升——初值折叠、存写折成 SSA 值。效果：可变全局减少、常量增多、引用链变短。意义：这是在全局作用域上做的私有存储提升，做完后 GlobalDCE 才能顺着引用链把它们一起删掉，GVN/InstCombine 才拿得到这些新的立即数。

证明（引 5.4、定义 0.1a/0.1b）。三种情形是引 5.4 在模块作用域的三次实例化：
(i) 只写不读——该地址未逃逸故不可观测，其上不存在任何观测点（0.1b），故其写不进任何 trace，删掉全部 store 与全局本身不改变任何 $\mathcal{O}(P,\sigma)$ ；
(ii) 初始化后只读——模块内不存在对 $G$ 的 store，故对一切 $\sigma$ ， $\mu_k(G)=\mu_0(G)$ 恒成立（引 5.3 的版本链上没有 def），于是每个 load 的值等于初值，把 $G$ 升为 constant 并折叠 load 逐点相等；升 constant 还额外断言”外部也不能写”，这需要 $G$ 具有本地链接（源码里的门槛就是 hasLocalLinkage()，GlobalOpt.cpp:1665，通过才走到 :1540 的 setConstant(true)）——external linkage 的全局可能被别的翻译单元写，(ii) 的前提就不成立，pass 不做；
(iii) 单函数触及—— $G$ 退化为该函数的私有存储，引 5.4 直接适用，phi 插入点由定理 2.2 给出。∎

AlwaysInliner（:1316）——算法：只做一件无条件的内联：把带 alwaysinline 属性的调用点全部展开（带 flatten 属性的函数则展开它体内的一切调用点），不做任何代价核算；文件头写明它是 “a custom inliner that handles only functions that are marked as ‘always inline’”（AlwaysInliner.cpp:9；flatten 那一支在 :97，收集 alwaysinline 调用点的那段在 :108–:113）。流水线传进来的 InsertLifetimeIntrinsics=true 管的是内联机制里的另一步：被内联函数的静态 alloca 搬进 caller 之后，用 llvm.lifetime.start/end 把它们的生命周期区间标出来（InlineFunction.cpp:3134 的开关、:3151 与 :3161 的两次插入；已带 marker 的与大小为 0 的跳过，动态 alloca 则改用 llvm.stacksave/llvm.stackrestore 包住整段，:3168）。效果：这些必选内联体从此以展开形态存在于函数体内，调用点清零；callee 的栈对象变成 caller 里带生命周期标注的私有存储。意义：alwaysinline 是语义要求而不是收益判断，所以它排在一切代价模型之前；而生命周期标注必须在 alloca 刚搬进 caller 的那一刻就补上——晚了，SROA/DSE/AA 面对的就是”看起来在整个 caller 里都活着”的栈对象，判断只能更保守。

证明（内联的操作性等价，见下节 Inliner；引 5.4；定义 0.1b）。内联本体的等价性由 Inliner 那条证明给出（事件序列逐条对应，call/ret 这一对不在定义 0.1a 的字母表里）；本 pass 与它的差别只在于不做代价核算，故不需要定义 6.3，剩下的义务只有一条：属性要求必须展开。生命周期标注那一步是加信息而不改行为：llvm.lifetime.start(p, n) 的语义是给 $(p,n)$ 这段区间划定生命周期，区间外的访问视为无效（LangRef §’llvm.lifetime.start’ Intrinsic），消费者是 SROA/DSE 与 AA。插入它不会造出新 trace：新 marker 只是把”这块私有存储在哪个区间内可观测”说得更清楚，而定义 0.1b 本来就允许区间外的写不进 trace；引 5.4 的私有性论证因此变短而不是变长。反过来，若不插入，callee 的 alloca 在 caller 里就没有区间边界，任何提升与删除都只能按”整个函数都活着”这个最保守假设处理。插入位置本身的合法性走引 2.4(M1)：lifetime.start 插在内联体的第一个新块开头、lifetime.end 插在每个 return 之前（musttail/deoptimize 调用与 return 之间不插，InlineFunction.cpp:3153–:3160 的两个跳过条件），两者都支配/后支配全部对该 alloca 的访问，故 M1 与 M2 成立。∎

出处：实现 IPO/AlwaysInliner.cpp；生命周期插入的那一段 Utils/InlineFunction.cpp:3130–:3166（注释里还写了一条：即使 O0 也要插，因为多线程协程会因缺标注而出现非法访问）；llvm.lifetime.* 与 llvm.stacksave/llvm.stackrestore 的语义在 LangRef；官方摘要 Passes.md 的 always-inline 一节。

沿调用图内联：按 SCC 自底向上

Inliner / ModuleInlinerWrapperPass（:963，机制在 IPO/Inliner.cpp:9）——算法：以 LazyCallGraph 的 SCC 缩点图做逆拓扑遍历（callee 侧 SCC 先于 caller）；对每个调用点计算 InlineCost：被调函数体的指令预算，减去参数代入可折叠、条件变可判定等”简化学分”，与随 Level 的阈值（含 hot-callsite 特判）比较，通过则复制被调体、入参替换、ret 边界接回调用点，调用边从图中删除并更新图。效果：跨函数数据流全部变成函数内 def-use 链，call 开销消失。意义：它是跨过程优化的信息来源——常量进了新上下文才有 SCCP 可用，跨函数的重复表达式才有 GVN 可认；所以主流水线把”逐函数简化流水线”整个嵌进 CGSCC 遍历（:1037）：先减小自身体积，再被内联进其它函数。

证明（操作性等价 + 推论 2.3 + 定义 6.3）。设被调函数体为 $B_f$ 、形参 $p_1..p_k$ 、调用点实参 $a_1..a_k$ 、call 的定义为 $v$ 。内联做三件事：

\text{(1) 重命名 }B_f\text{ 中每个值为新鲜名（SSA 下这是 def-use 图的一个双射，推论 2.3）}

\text{(2) 绑定 }p_i\mapsto a_i\qquad \text{(3) } \texttt{ret }r\ \mapsto\ v:=r,\ \text{接回原调用点的后继}

alloca 随复制得到新鲜副本，故多次内联（含递归展开一层）之间不共享私有存储。等价性论证：一次 call 的语义就是”求值实参 → 绑定形参 → 执行 body → 返回值”，(1)–(3) 把这四步在调用点原地展开；body 产生的事件序列（定义 0.1a 意义下）逐条不变，而 call/ret 这一对不在 $\mathcal{E}$ 里（callee body 已知时调用是透明的；除非函数地址逃逸给栈观测，此时 pass 不做）。递归情形只展开一层，因为新复制的 body 里的自调用点仍在图上，等下一轮遍历再判——这保证终止。遍历序由引 3.3 给出，”先减小自身体积”由定义 6.3 的体积预算给出： $\mathrm{cost}(\text{callsite})=|B_f|-\text{简化学分}$ ，学分项恰是定理 7.4 的”上游产物”折算，故内联与逐函数简化必须交替嵌套而不是先后两轮。∎

出处：代价模型的常量档在 InlineCost.h:38（OptSizeThreshold = 50、OptAggressiveThreshold = 250 等）；遍历与 SCC 维护 CGSCCPassManager.h:13、LazyCallGraph.h:109；内联本身没有经典论文，机制全在 IPO/Inliner.cpp:9。

PostOrderFunctionAttrs（IPO/FunctionAttrs.cpp:271）——算法：沿同一棵缩点图逆拓扑，由”已定性的 callee 集合 + 自身体内的访存/递归/异常结构”归纳推断 norecurse/readnone/willreturn/nofree。效果：遍历收尾时每函数的 attribute 集达到当前调用图下的归纳闭包——readnone 这类结论从调用图的叶子逐层传播到根。意义：函数级的”无副作用”从孤立事实变成归纳事实——每个函数只需推一步，前提是它调用的都已证明；内联器的 mod-ref 剪枝与下游 LICM 直接消费这份闭包。

证明（推论 3.4、引 1.4）。转移函数写成

A(f)=\Bigl(\text{body}(f)\text{ 的本地事实}\Bigr)\sqcap \mathop{\sqcap}\limits_{g\,\in\,\mathrm{callees}(f)}A(g)

取 meet（最保守者胜，引 1.4）。 $A$ 在属性格上单调，故由定理 1.2 存在不动点；由推论 3.4，沿逆拓扑秩归纳：秩 0 的 SCC（不调用任何函数或只调已定性的）单次计算即达不动点；秩 $k$ 的 SCC 内部若有递归，则 $A$ 限制在该 SCC 上仍是单调自映射，格高度有限故收敛轮数以格高为上界（引 1.3）。收尾时全图达到 $A$ 的不动点，即”当前调用图下的归纳闭包”。∎

DeadArgumentElimination（:1325，紧跟在内联流水线之后）——算法：删掉函数体里从未被读取的形参与从未被使用的返回值，调用点的签名一并改窄。效果：跨过程的 def-use 链变短，签名变窄。意义：源码注释写明它收拾的是”被清理、全局常量折叠与参数提升暴露出来的死参数”（:1323）——内联把实参代进 callee 之后，才能看出哪些形参从未被读取，所以它只能排在内联之后。

证明（推论 2.3、引 1.4 的全称量化）。形参 $p$ 可删的条件是一条全称命题：模块内每个调用点传给 $p$ 的值都不被 $p$ 的任何 use 读取（推论 2.3 的 use 计数为零），且函数地址未逃逸——否则存在看不见的外部调用者，全称量化就不成立，这与 ReversePostOrderFunctionAttrs 那条证明的前提是同一句。返回值同理：所有调用点都不使用 call 的结果时才可删。∎

逐函数简化流水线（上半场）：建立 SSA 形式，消除显然的冗余

（PassBuilderPipelines.cpp:620）

SROA（Scalar/SROA.cpp:9）——算法：收集每个 alloca 上的全部访问区间，按访问模式切分成不交叉的”片”；只以标量身份被读的片提成独立的 SSA 值（mem2reg 式的 phi 合并），能被向量/位域标量整体重命名的，改写为 bitcast 后的向量或整数位运算；纯粹进出外部内存的整块搬运故意不切（注释原话：”minimal slicing of the alloca so that regions which are merely transferred in and out of external memory remain unchanged”，SROA.cpp:15）。效果：聚合内存对象转换为标量/向量 SSA 值。意义：排第一是因为它是 SSA 形式的前提而不是可选优化——文件头自己就这么定位：”Because this also performs alloca promotion, it can be thought of as also serving the purpose of SSA formation”（SROA.cpp:19）；mem2reg 只处理”仅有 load/store 访问的 alloca”，结构体不切开，后面所有值域分析就没有输入。

; SROA 前                             ; SROA 后（各字段成为 SSA 值，phi 合并）
%A = alloca { i32, i32 }              ; %x = phi i32 [ 1, %entry ], [ %x2, %loop ]
%0 = getelementptr ...                ; %y = phi i32 [ 0, %entry ], [ %y2, %loop ]
store i32 1, ptr ...                  ; ...内存对象彻底消失

证明（引 5.4、定理 2.2、定义 6.3）。设 alloca 大小为 $n$ ，其上的访问区间集为 $\mathcal{I}=\{[o_i,o_i+s_i)\}$ ，取端点集 $E=\bigcup_i\{o_i,\,o_i+s_i,\,n\}$ 排序后得到最小划分 $\{[e_j,e_{j+1})\}$ 。这个划分有两个性质：(a) 每次访问都是若干划分格的并（端点全在 $E$ 里）；(b) 划分是最细的满足 (a) 的划分。于是每个格子独立地满足引 5.4 的私有性（alloca 地址未逃逸）与”只被纯 load/store 触及”，可各自提升为一个 SSA 值，phi 插入点由定理 2.2 的 $J^{+}$ 给出且最小。不切的例外是盈利性判断而非合法性判断：整块 memcpy 进出的对象若切开，每格都要 extractelement/insertelement 重组，按定义 6.3 的 $\Delta$ 算下来为负——所以注释要求 minimal slicing（SROA.cpp:15）。∎

EarlyCSE（Scalar/EarlyCSE.cpp:9）——算法：沿支配树做一遍前序遍历（文件头原话 “a simple dominator tree walk”），每进入一个支配树节点开一层作用域哈希表、退出时关掉，表里存”操作数与标志 → 指令”；在同一条作用域链上命中即替换并删除。作用域的进出正好对应支配关系，所以”表里还在”等价于”那处的值仍然支配当前点”。访存那一档由构造开关打开，流水线里恰好开着：EarlyCSEPass(true /* Enable mem-ssa. */)（:639），它用 MemorySSA 的最近覆盖 def 判一个 load 是否仍然有效。效果：逐字重复的表达式与冗余内存访问就地消失。意义：”early” 指在昂贵分析就绪之前，先消除前端生成的廉价冗余，减少 InstCombine 的工作量与体积测量的噪声；它只做一遍支配树上的作用域遍历，不做值编号的不动点迭代，成本比 GVN 低得多，所以排在这个位置。

证明（同余关系 + 引 5.3）。同余关系定义为

(o,\mathrm{op},\langle v_1..v_k\rangle,\mathrm{flags})\ \sim\ (o',\mathrm{op}',\langle v'_1..v'_k\rangle,\mathrm{flags}')\iff \text{逐项相同}

纯运算（无副作用、无访存）在作用域可见的范围内操作数相同 $\Rightarrow$ 值相同，因为它的结果在定义 0.1a 下（纯算术不是事件）是操作数的确定函数；替换后事件集不变（被删的那份从未产生事件）。跨块的可用性由作用域哈希表在支配树上的进出给出：一个表达式在支配树节点 $d$ 的作用域里插入，只有 $d$ 支配的块才看得到它（引 2.7 的区间比较正是这一支配关系的判定），故替换点上的操作数一定已经定义、且值没有被改写过（引 2.4 的 M1 与 M2）。访存那档由引 5.3 判定： $\ell$ 与 $\ell'$ 同 Location 且 $\ell$ 是 $\ell'$ 的最近覆盖 def（MemorySSA 的 clobbering access 恰是 $\ell$ 自己） $\Rightarrow$ 二者同值。∎

GVNHoist / GVNSink（默认关闭）、SpeculativeExecution（Scalar/GVNHoist.cpp / GVNSink.cpp / SpeculativeExecution.cpp:9；前两件要 -enable-gvn-hoist／-enable-gvn-sink 才排进流水线，:253 与 :257 的选项描述里写着 default = off）——算法：三个方向的”把计算挪到只执行一次或根本不执行的位置”：hoist 把重复表达式移到必经支配点，sink 把分支两侧同构表达式沉到汇合块折成一条，SpecExe 把小 if-then-else 两侧的操作提到分支前无条件算、结果用 select 按条件挑选（要求目标分支昂贵且操作可安全推测）。效果：表达式计算次数趋近每路径一次，或分支直接变成 select。意义：SpeculativeExecution 的文件头明确提到 GPU——分支发散执行时，一次分支的代价高于多算一次；而它在流水线里带的是 OnlyIfDivergentTarget=true（:655，旁注写的就是 “if the target has divergent branches; otherwise nop”），即只在分支发散的 target 上生效，x86 上不做任何改写；GVNHoist/GVNSink 打开后在 x86 上也只是偶有收益。

证明（引 2.4 的 M1–M4、引 2.5、引 0.7）。三者是同一条引理的三个方向：
hoist——设 $n$ 份同构表达式分别在块 $B_1..B_n$ ，取 $d=\mathop{\sqcap}\limits_i B_i$ （支配树上的最近公共祖先 LCA）。M1 由操作数在 $B_i$ 处可用且 $d\ \mathrm{dom}\ B_i$ 得（支配传递）；M2 由全部 use 都在 $\bigcup B_i$ 的子树内得；M3 则因提到 LCA 后执行次数改变、 $f_d\geq\sum_i f_{B_i}$ 未必成立，改走引 0.7（纯且不会 UB）；M4 对访存版由引 5.3 判”中途无覆盖”。
sink——落点 $j$ 必须后支配 $B_1..B_n$ （引 2.5：分支两侧任一支执行则 $j$ 必执行恰一次），且两份表达式的操作数在 $j$ 处同值（GVN 同余 + 操作数定义支配 $j$ ），于是 $n$ 份折成 1 份，执行次数下降；纯运算的情形下事件集不变（定义 0.1a：纯算术不是事件），访存的情形另需 (M4)。
SpecExe——把 $i$ 提到分支前是无条件执行，M3 只能靠引 0.7；提到前面后两支的使用点用 select 接回，未被选中那支的 $i$ 结果不被观测，故 $\mathcal{O}$ 不变。盈利性由定义 6.3 判： $\Delta=f_{\text{then}}\cdot c_i-(1-f_{\text{then}})\cdot 0$ 与分支开销的差。∎

JumpThreading（Scalar/JumpThreading.cpp）——算法：对块 $X$ 的条件分支查每个前驱 $P$ ：若从 $P$ 到达时条件值已可判定（ $P$ 的 terminator 常量分支传播过来，或路径上的相等事实代入），就把 $P$ 的这条出边从 $X$ 改接到 $X$ 的目标分支， $X$ 中对应 phi 项随之折叠； $X$ 只有一个前驱时直接改写 $X$ 的 terminator。效果：CFG 的边数下降——一条运行时分支在特定路径上变成直通边。意义：把运行期的判定提前到编译期，且改道后的边成为新的事实来源，常常连续触发下一处 threading（定理 7.4 中机会图的自增强边）。

证明（引 0.5、推论 1.6、引 2.4(M2)）。设 $X$ 的终结指令为 $\texttt{br }c,T,F$ ，前驱 $P$ 。若在路径 $P\to X$ 上 $c$ 被判定为真——判定来源有二： $P$ 的终结指令本身是常量分支（则该事实沿这条唯一的边成立，推论 1.6 的条件格给出），或路径上的相等事实代入 $c$ 后化简为常量——则对一切经 $P$ 进入 $X$ 的执行， $X$ 的终结指令必跳 $T$ 。于是把边 $P\to X$ 改接为 $P\to T$ 后，事件序列不变，条件是 $X$ 中从入口到终结指令之间的指令无可观测副作用（否则跳过它们会少产生事件，违反定义 0.2(i)）——实现上正是这一步先查 mayHaveSideEffects。 $T$ 中的 phi 需要按” $P$ 经 $X$ 到达”这条新路径重算入参：若入参是 $X$ 里定义的 phi 结果，则沿 $X$ 的 $P$ -入项取值（SSA 下唯一，推论 2.3），必要时克隆该计算到 $P$ （合法性再走引 2.4 的 M1–M4）。 $X$ 只有一个前驱时， $X$ 的 phi 全部退化为单入项，直接折叠。∎

CorrelatedValuePropagation（Scalar/CorrelatedValuePropagation.cpp）——算法：对每条分支的真假两侧，沿支配树收集”由该分支条件可推出的值事实”（非零、范围、符号、nonnull；事实来自 LazyValueInfo 在每个使用点给出的 ConstantRange），把结论以 !range、!nonnull 元数据或 nsw 标志的形式写到该范围内每条用到它的指令上，能直接折的替成常量。效果：下游 pass 局部可见的事实集合扩大，不是本 pass 亲手改的指令也变便宜。意义：与 JumpThreading 分工——前者改写 CFG 的边（把路径上已确定的事实固化成图的形状），后者改写元数据（把值的属性写进指令），两者各自作废的下游分析结论都最少；add 指令上的 nsw 标志常常就是在这里被证明、再写上去的。

证明（引 2.6/2.7、引 0.6(b)、引 0.5）。设 $\texttt{br }(\texttt{icmp}_{\mathrm{pred}}\,x,y),A,B$ 。在 $A$ 的任意执行中 $\mathrm{pred}(x,y)$ 为真（路径条件），在 $B$ 中为假。要把事实写到指令 $i$ 上，健全性条件是

\mathrm{def}(c)\ \mathrm{dom}\ A\quad\wedge\quad A\ \mathrm{dom}\ \mathrm{block}(i)

前者由分支条件的定义支配给出，后者保证 $i$ 只在走了 $A$ 之后才执行（引 2.7 的区间查询）。于是”在 $i$ 处 $\mathrm{pred}(x,y)$ 恒真”是定理不是假设，把它的推论（ $x\neq 0$ 、 $x\in[a,b)$ 、 $x\geq 0$ ）写成 !nonnull/!range 或直接折叠，都满足定义 0.2。生产 nsw 那一路是引 0.6(b) 的义务履行：必须先在 ConstantRange 上证明 $x+y$ 不越界（实现上是 ConstantRange::makeGuaranteedNoWrapRegion，CorrelatedValuePropagation.cpp:472；例如由 $x\in[0,2^{30})$ 、 $y\in[0,2^{30})$ 得 $x+y<2^{31}$ ），证明失败就不加标志。顺带的两条折算是域引理： $\forall x,y\in[0,2^{31}),\ x\ \texttt{sdiv}\ y=x\ \texttt{udiv}\ y$ 且 $x\ \texttt{srem}\ y=x\ \texttt{urem}\ y$ （截断向零，位形相同），以及 $x\geq 0$ 时 $\texttt{sext}\to\texttt{zext}$ 。∎

SimplifyCFG（Scalar/SimplifyCFGPass.cpp，规则本体在 Utils/SimplifyCFG.cpp，流水线传的选项在 SimplifyCFGOptions.h）——算法：规则式 CFG 重写集：合并只有一个前驱/后继的平凡块、删无条件跳转中转、折叠可判定分支、把 switch 的连续 case 转成 icmp（流水线的 convertSwitchRangeToICmp(true)，激进档还有 convertSwitchToArithmetic）、合并同构分支、按需 hoist/sink 公共指令；迭代应用。效果：块数与边数下降，图更接近树，phi 数量减少。意义：几乎所有改图的 pass 都会留下单前驱单后继的冗余块，与其要求每个 pass 自己清理，不如定期集中做一次——所以它在清单上反复出现：逐函数简化流水线里，每在最可能产生冗余块的 pass 之后就排一次（:666/:681/:757/:822，另有 :651 那一处只在 GVN-sink 打开时才排），EarlyFPM 里也有一次（:1168）。

证明（引 0.5、引 2.4、定义 6.3，逐条给）。
折叠可判定分支： $c$ 为常量时 $\texttt{br }c,T,F$ 的一支必不可达，引 0.5 授权删边删块。
合并单前驱块：设 $B$ 的唯一前驱是 $P$ 且 $P$ 以 $\texttt{br }B$ 终结。合并后路径集与原图双射（每条经 $P\to B$ 的路径对应唯一一条经 $PB$ 的路径）， $B$ 中的 phi 因前驱唯一而退化为单入项（定理 2.2 的 $J^+$ 在此为空），故可直接用其入参替换。
switch 转 icmp：设 case 标签构成连续区间 $[a,b]$ 且共用目标 $T$ ，则

\texttt{switch }x\{a..b\to T,\ \mathrm{default}\to D\}\ \equiv\ \texttt{br}\bigl(\texttt{icmp ule }(x-a),\,(b-a)\bigr),T,D

证明： $\mathbb{Z}_{2^w}$ 中 $x\mapsto x-a$ 是双射，且区间长度 $b-a+1\leq 2^w$ ，故 $x$ 落在无回绕区间 $[a,b]$ 内 $\iff (x-a)\bmod 2^w\leq b-a$ （无符号比较恰是模意义下的区间判定）。∎
hoist/sink：引 2.4 的 M1–M4 加定义 6.3 的 $\Delta>0$ 判据——hoist 到必经点省重复执行，sink 到低频分支减少高频路径的指令数，两者用同一个频度度量比较，这也是注记 6.4 说的”贪心判定的局部性”最集中的地方。∎

InstCombine（InstCombine/InstructionCombining.cpp，按操作数分文件：InstCombineAddSub/AndOrXor/Casts/Compares/MulDivRem/Shifts/…）——算法：逐条指令过一大批重写规则（x+0→x、select(c,a,a)→a、移位/逻辑/比较的恒等式库），任何改写产物立即回灌 worklist，迭代到不动点。效果：表达式收敛到规范且最小的形态，常数折叠到底。意义：窥孔优化（peephole：只在局部几条指令的范围内做等价替换）的通用基础；与 SimplifyCFG 交替排布是因为一个管表达式树、一个管图，规则互相创造应用条件——CVP 标出 icmp ne %x, 0 之后，InstCombine 才能把对应的 select 换成 trunc（定理 7.4）。

证明（规则模板 + 引 0.4、引 0.6）。每条规则的证明义务是同一个模板：对一切 $\sigma$ ，作为关系证明 $\llbracket e\rrbracket_\sigma=\llbracket e'\rrbracket_\sigma$ ，即两侧取值集合相同（含 poison 行为），并检查标志义务（引 0.6）。三个样例：

\texttt{select}(c,a,a)\to a:\quad c\text{ 为真取 }a\text{、为假取 }a\text{、}c\text{ 为 poison 时两侧皆 poison（引 0.4）}

x+0\to x:\quad \mathbb{Z}_{2^w}\text{ 中 }x+0=x\text{；}x\text{ 为 poison 时两侧皆 poison；带 nsw 时 }x+0\text{ 不溢出，故标志可保留}

(x\ \&\ 1)\neq 0\ \to\ \texttt{trunc}(x\ \&\ 1):\quad x\&1\in\{0,1\}\Rightarrow\text{与 }0\text{ 的比较等于其唯一有效位}

终止性：引 7.2 的两条前提（终止 + 局部合流）在 InstCombine 的规则集上不成立——存在互相创造应用条件的规则对，故实现用 worklist 加迭代上限，”到不动点”是设计目标而非定理。这一点很重要：它解释了为什么 InstCombine 要在清单上反复出现而不是一次，也解释了定理 7.4 的机会图为什么会有环（环靠多次重排打破，不靠单遍收敛）。∎

出处：这批规则现在有机器验证：Alive2, PLDI 2021（前身 Alive, PLDI 2015，它把每条 peephole 规则当成一个 refinement 子问题判）；迭代上限 InstructionCombining.cpp:6198；规则清单的官方摘要 Passes.md。

AggressiveInstCombine（:668，AggressiveInstCombine/AggressiveInstCombine.cpp:9）——InstCombine 之后紧接的一个 pass：把多条指令组成的表达式模式折成更短的形式，当前主要处理 truncate 相关的模式（文件头自述 “Currently, it handles expression patterns for: * Truncate instruction”，另有 TruncInstCombine.cpp 专管截断）。效果：位宽转换链变短。意义：它处理的是 InstCombine 规范化之后剩下的多指令模式——单条规则看不见的形状（定理 7.4）。

证明（引 7.6 + 引 0.6）。每条模式改写的义务与 InstCombine 同模板：在 $\mathbb{Z}_{2^w}$ 上逐点相等 + 标志义务。以截断—扩展对为例，设 $w_x\leq w_t$ ，则 $\texttt{trunc}_{w_t}(\texttt{zext}_{w_t}(x))=x$ （高位全零，截断恰好切掉它们）；而 $\texttt{trunc}_{w_t}(\texttt{sext}_{w_t}(x))=x$ 也成立，但反向 $\texttt{sext}(\texttt{trunc}(x))=x$ 只在 $x$ 的高位确为符号扩展时成立——这个前提要么由引 0.6 的标志给出，要么由 CVP 写上去的 !range 元数据给出，两者都没有就不改。∎

LibCallsShrinkWrap（Utils/LibCallsShrinkWrap.cpp:9，位置在 :669）——算法：只对结果未被使用的 libcall（对标准库函数的调用）动手。这类调用不能直接删，因为它可能设 errno（一个可观测的写）；而错误条件往往只取决于入参，于是把调用包进一个 guard——文件头的例子就是 sqrt(val); 改成 if (val < 0) sqrt(val);。效果：常见路径上库调用整条消失，只在可能出错的路径上保留。意义：errno 是这类调用无法直接删除的唯一原因，把”无条件调用”改为”仅在错误域内调用”就避开了它。文件头还交代了这类代码的来源：”These partially dead calls are usually results of C++ abstraction penalty exposed by inlining”（:23–:24）——结果没被用的库调用，大多是内联把 C++ 的抽象代价暴露出来之后剩下的，这也解释了它为什么排在内联与一轮化简之后。分工需要说明：pow(x,2)→x*x、exp(log(x))→x 那类恒等式改写不在本 pass，而是 InstCombine 经 Utils/SimplifyLibCalls.cpp 按 TargetLibraryInfo 的语义档案做。

证明（定义 0.1a 的 $C$ / $W$ 事件 + TLI 档案 + 引 6.2）。设 libcall $f$ 的结果未被使用，则它对 trace 的贡献只有两项：一次调用 $C(f,\cdot)$ ，以及错误时对外部可观测对象 errno 的写 $W(\&\text{errno},e)$ 。令 $E\subseteq$ 入参域为”会设 errno 的错误条件”（由 TLI 的语义档案给出，例如 sqrt 的 $E=\{x<0\}$ ），改写为

f(x)\ \longrightarrow\ \texttt{if}(x\in E)\ f(x)

分两种输入： $x\in E$ 时两侧都调用，事件序列相同； $x\notin E$ 时新程序少了那一次 $C$ ——这一步成立的前提是 $f$ 此时已不是不透明 call：TLI 给了它的语义档案后，它唯一的可观测效果就是 $W(\&\text{errno},e)$ ，而 $x\notin E$ 时这个写也不发生，故两侧 trace 相同。因此本 pass 的正确性与 InferFunctionAttrs 相同：完全依赖 TLI 档案可信。guard 的实现细节：判定 $x\in E$ 是纯比较、不会 UB（引 0.7），且必须在 $f$ 之前执行，故用条件分支而不是 select（select 的两个操作数都已求值，不具备惰性）。盈利性由引 6.2： $p_E$ 极低，期望代价 $p_E\cdot c_f$ 远小于 $c_f$ 。∎

TailCallElim（Scalar/TailRecursionElimination.cpp:9，注册名 tailcallelim，位置在 :678）——算法：只处理自递归：函数体以”调用自身、结果直接被 return”终结时，把 call+ret 换成”参数按实参重写 + 跳回入口的 br“。文件头列了几条扩展，与本文相关的是三条：(1) call 与 ret 之间夹着死指令不影响判定；(2) 若阻止尾递归的是一个结合且交换的表达式，改用累加器变量——“the typical naive factorial or ‘fib’ implementation” 因此变成循环；(3) 返回 void、返回调用结果、或所有出口返回同一运行期常量时都能做。效果：自递归成为带参数重置的循环，栈深度变为常数。意义：这是 IR 层的改写——判定需要看全函数（所有 return 的形态、call/ret 之间有无活指令、有无 landing pad 检查栈），前端在语法层拿不到这些信息。

证明（定义 0.1a + 引 2.4）。设 $f(p)\{\,\beta;\ \texttt{ret }f(p')\,\}$ ，其中 $\beta$ 是 body 的其余部分，且尾调用之后无任何指令。原版的事件序列是 $\mathcal{E}(\beta_1)\,\mathcal{E}(\beta_2)\cdots$ （每次递归一层贡献自己 body 的事件），改写版是循环 $\texttt{entry}:\beta;\ p:=p';\ \texttt{br entry}$ ，其事件序列同样是 $\mathcal{E}(\beta_1)\mathcal{E}(\beta_2)\cdots$ ——因为参数绑定是私有寄存器（不产生事件），call/ret 对内部函数不在 $\mathcal{O}$ 中。等价所需的边界条件三条，逐条对应定义 0.1a 的事件类型：(i) 栈深度不可观测（没有 landing pad（异常处理入口块）检视栈、函数地址未逃逸给栈回溯）；(ii) 各层之间不共享可变存储（alloca 每次调用一份新鲜副本，改写后必须确认 $\beta$ 里没有跨层存活的 alloca 引用，否则把 alloca 提到循环外会改变可见性——引 2.4(M4)）；(iii) 参数赋值的搬移满足 M1（ $p'$ 在跳回点已定义）。扩展 (2)（累加器）另走引 4.7：把 $f(p,a)$ 的递归累积改成 $a:=a\oplus p$ 的循环累积， $\oplus$ 结合交换时两种求值次序在 $\mathbb{Z}_{2^w}$ 中同值——这也是它只限整数类 $\oplus$ 、不碰浮点的原因。∎

Reassociate（Scalar/Reassociate.cpp）——算法：把加法链（含 sub 的取负展开）规约为系数向量——每表达式写成 $\sum c_ix_i+k$ 后按项序重排、合并同类项（x*2 + x*3 → x*5），乘法树把常数与重复因子提到根部（流水线注释的原话：”this will form (nearly) minimal multiplication trees”，:684）。效果：代数等价 → 语法同形。意义：GVN 与 InstCombine 只能识别语法同形的表达式，规范化是”让值编号能识别代数等价”的前置代价；所以它必须排在它们之前。

证明（引 7.6、引 4.7、引 0.6(b)）。 $\mathbb{Z}_{2^w}$ 是交换环，故加法链中任意重排与结合律改写都保持值：

\Bigl(\sum_i c_ix_i\Bigr)+\Bigl(\sum_j d_jy_j\Bigr)=\sum_k (c_k+d_k)z_k\quad(\text{同类项合并，系数在 }\mathbb{Z}_{2^w}\text{ 中相加})

且给定项序（rank 由引 3.1 的 DFS 编号给出）后该表示唯一，于是”代数等价”与”语法同形”重合——这正是 GVN/EarlyCSE 的同余关系（EarlyCSE 那条证明）能识别它的前提。乘法树部分： $x\cdot x=x^2$ 、 $x^{2^k}=((x^2)^2)\cdots$ 由交换半群的幂定义给出，”nearly minimal” 是指常数因子被提到根部、重复因子被平方化，深度按 $\log$ 收敛。唯一需要注意的是标志（引 0.6）：链上若有 nsw/nuw，重排会改变 poison 的产生位置，故 Reassociate 要么证明重排后仍不溢出（保留标志），要么放弃标志/放弃这条链；对浮点则整条引理不适用（引 4.7： $\oplus$ 不结合），除非有 reassoc 授权。∎

出处：Reassociate.cpp:436 LinearizeExprTree、:449（系数即”操作数在线性化表达式里出现的次数”）、:626 RewriteExprTree；”为何必须先规范化”的另一面见 Alpern, Wegman & Zadeck, POPL 1988。

ConstraintElimination（Scalar/ConstraintElimination.cpp:279；流水线位置在 :688，紧跟 Reassociate 之后、LPM1 之前；开关 -enable-constraint-elimination 的 cl::init(true) 在 :283，即默认开着）——算法：把全函数的线性 icmp 假设编码为不等式矩阵，跑一个整数线性规划式的求解器推出新结论，把可证恒真/恒假的检查（越界判断、x>=0 时的 x<0 分支）折叠删除。效果：运行时检查整批消失。意义：覆盖 sanitizer 与数组边界检查这类代码——UBSan（UndefinedBehaviorSanitizer，用运行时插桩检查 UB 的工具）插入的检查大多是线性可判定的，但只有把全部约束联立才能推出结论；放在 reassociate 之后，正因为求解器的输入必须是规范形（引 7.6）。

证明（引 0.5、引 2.6、推论 1.6 的松弛版）。事实集来自三处：分支两侧的路径条件（引 2.6/2.7 的支配保证”该事实只在此子树内使用”）、AssumptionCache 的 llvm.assume（引 0.5：假设为假即 UB）、以及已折叠的常量。设事实集为 $\mathcal{F}=\{a_j^{\top}x\leq b_j\}$ ，待判分支为 $c^{\top}x\leq d$ 。求解器证

\mathcal{F}\cup\{c^{\top}x>d\}\ \text{在 }\mathbb{Q}^n\text{ 上不可行}\ \Rightarrow\ \text{在 }\mathbb{Z}^n\text{ 上不可行}\quad(\because\mathbb{Z}^n\subseteq\mathbb{Q}^n)

不可行即该分支在任何真实执行中不进入，引 0.5 授权删除。注意这是有理松弛：整数专属的可判情形（如 $2x=1$ 无整数解）会漏掉，故结论不完备——但由推论 1.6 的方向性，不完备只意味着少删几个 check，不意味着删错。规范形作为输入的必要性：求解器按项的语法身份对齐变量，未经引 7.6 规范化的 $2x+3x$ 与 $5x$ 会被当成两个不同变量，事实矩阵随之失效。∎

出处：整数线性可行性判定的工程经典是 Pugh, The Omega Test: A Fast and Practical Integer Programming Algorithm for Dependence Analysis, Supercomputing 1991——“有理松弛健全但不完备”在它那里就是常识；LLVM 侧用的不是 Omega 而是自己的约束系统：ConstraintElimination.cpp:279 class ConstraintInfo。

循环子流水线 LPM1：先整形，再把不变量移出循环

（LPM 的契约在此生效：LCSSA（Loop-Closed SSA：循环内定义、循环外使用的值一律经出口 phi 导出）、内层循环先处理、LoopInfo / DominatorTree / ScalarEvolution 常备——上一章的分析在这里全部被用到。契约本身的机制在末章，这里只用它的结论。）

LoopSimplify + LCSSA（由 adaptor 强制加上，LoopPassManager.h:402；实现分别在 LoopSimplify.cpp 与 LCSSA.cpp）——算法：LoopSimplify 补齐唯一 preheader、唯一 latch、规范 exit；LCSSA 对一切”循环内定义、循环外用”的值在出口块插入 phi 再导出。效果：循环边界从”散布全函数的 use”收拢为”几个出口 phi”。意义：loop pass 因此只需改写循环内部、不必追踪散布在循环外的引用——按单元重写能成立全靠这一步；代价（多余的 phi）在收尾阶段由 InstSimplify 清除（”clean up LCSSA form before generating code”，:1649）。

证明（定理 2.2、引 2.7、引 3.5）。把”规范循环形”写成四条结构不变量：

(\mathrm{C1})\ \exists!\ \text{preheader},\ \mathrm{pred}_{\text{外}}(h)=\{\text{preheader}\}\qquad (\mathrm{C2})\ \exists!\ \text{latch}\qquad (\mathrm{C3})\ \text{exit 块专用}\qquad (\mathrm{C4})\ \forall v:\ \mathrm{def}(v)\in L\wedge\exists u\notin L\Rightarrow u\text{ 只经 exit phi}

(C1)–(C3) 由定理 3.2 的森林性质可构造（补块不改变路径集，只在边上插一个单前驱单后继块，其等价性即 SimplifyCFG 合并规则的逆用）；(C4) 是定理 2.2 在”变量 = 循环内定义的值、赋值点 = latch”上的实例：exit phi 的插入点集恰是 $J^{+}(\{\text{latch}\})$ ，故最小且足够。(C4) 换来的性质是改写影响范围有界：loop pass 改动循环内定义 $v$ 后需要修的循环外引用数从 $|\mathrm{uses}_{\text{外}}(v)|$ （无上界）降为 $|\mathrm{incoming}(\varphi_{\text{exit}})|\leq|\mathrm{pred}_{\text{内}}(\text{exit})|$ （由 (C3) 有界）。噪音的清理是 trivial phi 折叠：exit 的循环内前驱唯一时 LCSSA phi 只有一个入项，而单入项 phi 的选择函数恒取该入项，故 $\varphi[v]\equiv v$ 。∎

LoopInstSimplify / LoopSimplifyCFG（Scalar/LoopInstSimplify.cpp / LoopSimplifyCFG.cpp）——概念：LPM1 的前两个 pass，处理契约的反向问题：进入循环流水线之前先把循环恢复到契约形。算法：LoopInstSimplify 对循环内指令做单遍化简（不新增重写规则，只代入已知的循环不变量与外层循环新折出的常量）；LoopSimplifyCFG 是 SimplifyCFG 的循环内受限版——改写范围不出当前 Loop，避免破坏外层已处理的状态。效果：被前序 pass 改动过的循环体回到局部最优。意义：外层的改写会波及内层已经处理完的状态，而 LPM 的”内层先、定了不再回头”次序（引 3.5）要求每次进入一个循环时它的形态已经是契约形——这两个 pass 就是该保证的实现处。

证明（引 3.5、引 7.2 的弱化）。引 3.5 的不变量是”处理外层循环时内层循环已定型”，但”定型”只对内层循环自己的 pass 成立：外层循环 pass（unswitch 克隆、LICM 提升到外层循环 preheader）会往内层循环的块里塞新指令或改新边，内层循环的规范形被破坏。LoopInstSimplify/LoopSimplifyCFG 的作用是把内层循环重新化简到它自己的不动点——注意这里只需单遍而非迭代到不动点：外层循环引入的指令数量有限（每次改写只引入常数量级的新指令），故一遍化简足以吸收，这与引 7.2 里 InstCombine 需要迭代上限的情形形成对比。∎

LICM（Scalar/LICM.cpp:9）——算法：对循环内每条指令问两个问题：”操作数的定义都在循环外吗”（不变）且”移出去安全吗”（可能触发异常的指令必须有可到达的出口，或获准推测执行）；文件头注释同时点名第二职责——提升 must-alias 的内存访问：指针不变、MemorySSA def 链上循环内外无可能别名的读写，则 load 提到 preheader、store 沉到 exit，中间改写用 SSA 值传递，等价于把这块内存提升为寄存器。效果：每次迭代一次的计算变成全程一次；循环携带内存变成循环携带 SSA 值。意义：除法、地址计算、全局读取这类”每次迭代重复计算同一结果”的开销被消除，且内存依赖消失之后，后续分析与向量化面对的才是纯寄存器数据流。

证明（引 2.6、引 2.4 的 M1–M4、定理 4.4、引 5.4）。
职责一（提升不变计算）：不变性由引 2.6 判定—— $i$ 的全部操作数定义支配 header 且循环内无重定义，故每次迭代取值相同。搬迁走 M1–M4：M1 由操作数定义在循环外、且支配 header 的循环外定义必支配 preheader（(C1)：preheader 是 header 的唯一外部前驱）；M2 由 preheader 支配循环内一切块、且循环外使用点已经过 LCSSA phi（(C4)）；M4 对纯指令空虚成立。M3 是关键： $f_{\text{preheader}}\leq f_{\text{body}}$ ，执行次数减少，故纯指令走引 0.7 无条件合法，而可能陷阱的指令（sdiv 除数在循环内才非零、访存可能段错误）需要”至少执行一次迭代”的保证——这正是定理 4.4 的 rotate 提供的：尾测形下 preheader 执行 $\Rightarrow$ body 至少执行一次，于是 preheader 里新引入的陷阱必然对应原第一次迭代的陷阱，定义 0.2(ii) 不被违反。流水线里 AllowSpeculation 确实是 rotate 前传 false（:714）、rotate 后传 true（:720）；不过源码给出的第一条理由比合法性更实际——注释原话：”do not perform speculative hoisting the first time as LICM will destroy metadata that may not need to be destroyed if run after loop rotation”（:708）：先推测提升会把本来不必丢的元数据丢掉。两个理由叠在一起才是这一对 LICM 的完整解释。
职责二（promote to register）：设位置 $\ell$ 在循环内 must-alias 不变（引 2.6 + AA 的 MustAlias），且 MemorySSA def 链上循环内外不存在与 $\ell$ may-alias 的其他访问（引 5.3 的”最近覆盖 def”就是被提升的那次写）。则 $\ell$ 在引 5.4 的意义下对这个循环是私有的：load 提到 preheader（M1–M4 同上，M4 由无别名访问给出）、store 沉到 exit（落点由引 2.5 的后支配保证”循环内每次写最终都对应 exit 处一次写”，前提是循环内无读该位置的其他点——即”先写后读”的中间值改由 SSA 传递），中间用 phi 在 exit 合并（定理 2.2）。于是循环携带的内存依赖变成循环携带的 SSA 值，循环内那 EC 次写合并为 exit 处 1 次。这是 LICM 唯一会改变 trace 里 $W$ 事件条数的改写，合法性由定义 0.1b 给出：循环内不存在观测点——OP1 由”循环内外无 may-alias 读”排除、OP2 由”循环内无不透明 call 触及 $\ell$ “排除（must-alias 不变 + AA 结论正是这两句的证明义务），故那 EC 次写本来就一次也不进 trace，任何 trace 只在 OP3（exit 之后）看见 $\ell$ 的值，而它被 exit 处那一次写原样保留。若 $\ell$ 根本未逃逸（引 5.4），连 OP3 都不存在，那最后 1 次写也可一并省掉。∎

出处：几个动作在源码里分得很清——LICM.cpp:181 hoist、:185 sink、:935（提升候选的三重检查：hasLoopInvariantOperands + canSinkOrHoistInst + isSafeToExecuteUnconditionally）、:1294 canSinkOrHoistInst、:1826 isSafeToExecuteUnconditionally（AllowSpeculation 就是它的最后一个实参，声明处 :188–:192）、:2008 promoteLoopAccessesToScalars（调用点 :526）；不变性本身由 LoopInfo.cpp:67 与 :73 回答；官方摘要 Passes.md 的 LICM 一节。

LoopRotate（LoopRotationUtils.cpp:52）——算法：把入口边的条件检查克隆进 preheader，循环体改为首指令直落、latch 尾测的 do-while；检查复制代价用分支权重对冲（ZeroTripCountWeights = {1, 127}）。效果：模块内的循环从此具有统一形态——preheader + 单 latch + 尾测出口。意义：SCEV 的 trip-count 推导、unroll/vectorize 的”整个 body 可当直线块复制”的合法性、LICM 的推测授权，全部以这个形态为前提；一次形态变换，三者各自要的前提同时满足。

证明（定理 4.4、引 6.2、引 0.7）。等价性即定理 4.4，两个前提逐条兑现：(i) 首次条件求值结果相同——克隆的是同一条比较指令，其操作数在 preheader 与 latch 处取值相同（引 2.6：操作数在循环内不变；若可变，rotate 会先把条件化简到只依赖循环不变量，否则放弃）；(ii) 条件无副作用——rotate 只克隆纯比较与分支，可能陷阱的操作数（如 load）需满足引 0.7 才允许复制。代价按引 6.2 计：权重 $\{1,127\}$ 读作 $p_{\text{zero-trip}}=1/128$ ，故多出来的那次求值期望代价为 $\frac{1}{128}\cdot c_{\text{cmp}}$ ，而收益是 body 内每次少一条跳回头部的边，按定义 6.3 的 $\Delta$ 恒正。∎

SimpleLoopUnswitch（Scalar/SimpleLoopUnswitch.cpp:86）——算法：对不变条件（入口一次判、循环内不碰）把循环体连同分支克隆成两份，分别前置真/假判定；trivial 情形（编译期常量条件）直接折掉一支；nontrivial 的 guard 克隆受体积预算约束，且只在 O3 打开——NonTrivial 实参写的就是 Level == OptimizationLevel::O3（:723），O2 只执行 trivial 的那一半。效果：if (flag) 从每次迭代执行一次变成循环外执行一次。意义：循环体内的分支密度下降之后，每次迭代的指令数与指令种类都更接近可展开、可向量化所要求的形态——紧接的 LPM2（惯用法识别、归纳变量规范化、展开）才有可用的输入。

证明（引 4.8、引 0.5、定义 6.3）。不变性由引 2.6 判定（条件 $c$ 的操作数全在循环外定义），故引 4.8 的分配律直接适用：

\texttt{loop}\{\texttt{if}(c)B_1\texttt{ else }B_2\}\equiv\texttt{if}(c)\texttt{loop}\{B_1\}\texttt{else}\texttt{loop}\{B_2\}

克隆后每份循环里 $c$ 已知为常量，其分支由引 0.5 折掉， $B_1$ / $B_2$ 成为直线块——这一步正是 LPM2 里 full unroll 与 vectorize 需要的”body 可整体复制”前提（定理 4.4 之后的第二次形态收敛）。trivial 情形（ $c$ 编译期常量）不产生克隆，只折一支，故不计预算；nontrivial 情形的体积增量是 $|B_1|+|B_2|-|B|$ ，按定义 6.3 与 Level 预算比较，超预算则放弃——放弃不影响正确性，只影响收益（推论 1.6 的方向性在此再次生效）。∎

LoopFlatten（默认关闭：-enable-loop-flatten 的 cl::init(false) 在 :226，开启后挂在 LPM1 末尾 :725；实现在 Scalar/LoopFlatten.cpp）——算法：证明内外层间无携带依赖后，两层 trip count 相乘合成单个循环（:763 的 CreateMul，新 trip count 写回外层出口条件 :781）。内层归纳变量不是”重建”出来的，而是要求它本来就以线性形式出现：两个归纳变量的全部用法都必须匹配 (OuterPHI * InnerTripCount) + InnerPHI 这个形状，匹配上的那些用法直接换成合并后的计数；不匹配就得用 div/mod 才能还原，pass 判定为不划算而放弃（:613–:619 的注释与 :620 checkIVUsers）；乘法会不会回绕另有专门一道检查（:644 checkOverflow，引 4.3），证不出来就生成运行期版本选择（:983）。效果：循环嵌套深度减一。意义：两层边界检查与两条 latch 合并为一，SCEV 面对单层仿射式推导能力更强，unroll 也只需处理一个循环。

证明（定理 4.5 的 flatten 推论、引 4.2、引 2.6）。迭代空间为 $\{(i,j):0\leq i<n,\ 0\leq j<m\}$ ，映射 $\sigma(i,j)=i\cdot m+j$ 是双射，且 $(i,j)$ 的字典序与 $\sigma$ 的数值序一致：

\sigma(i',j')-\sigma(i,j)=(i'-i)m+(j'-j)\ \begin{cases}>0 & i'>i\\ =0 & i'=i,\ j'=j\\ <0 & i'<i\end{cases}\quad(j,j'\in[0,m))

故按定理 4.5，只要一切依赖向量在字典序下非负（原本嵌套执行即保证这一点），flatten 保序合法。两个附加前提：内层 trip count $m$ 对外层循环不变（引 2.6），否则 $\sigma$ 不是双射；内层无 early exit（否则迭代空间不是矩形）。逆变换 $i=k/m,\ j=k\bmod m$ 在 $m>0$ 时是 $\sigma$ 的逆，且 $k<n\cdot m$ 时不溢出（引 4.3 检查宽度，实现里就是 :644 checkOverflow）。

还有一条实现上的限制值得单独说，因为它把上面那个”逆变换存在”的前提换成了更强的形式：pass 并不真的去算 div/mod，而是要求两个归纳变量的全部用法已经是线性形式 $(i\cdot m+j)$ （:613–:620）。也就是说，合法性由定理 4.5 保证，而盈利性由”不需重建下标”保证——两条判据分开，少一条就不做。∎

循环子流水线 LPM2：识别惯用法、规范归纳变量、展开

LoopIdiomRecognize（Scalar/LoopIdiomRecognize.cpp:9）——算法：用 MemorySSA 的 def/uses 链 + SCEV 的地址仿射性匹配整个循环的访存模式：常数写连续区→memset，逐元素搬运→memcpy/memmove，找零扫描→strlen 等；按代码体积编译时，它会先判断改写之后体积是否更大（文件头注释：”If compiling for code size we avoid idiom recognition if the resulting code could be larger than the code for the original loop”）。效果：整个循环替换为一条 intrinsic 调用。意义：收益有两处——memset 由 libc 或后端实现为带非临时存储（non-temporal store：提示硬件这块数据不必进缓存）的向量化例程，执行成本从”与元素个数成正比”降到”与向量步数成正比”；更重要的是循环结构消失，它带来的寄存器占用、依赖边与分析成本对下游全部归零。

证明（引 4.2、引 5.5、引 5.3、定义 6.3）。以 memset 模式为例：设循环内唯一的写是 $\texttt{store }c,\ \texttt{gep}(\text{base},\ i\cdot s)$ ， $i$ 遍历 $[0,n)$ ， $c$ 循环不变（引 2.6），地址由 SCEV 给出闭式 $\text{base}+i\cdot s$ （引 4.2，仿射）。对 $i$ 归纳：第 $i$ 次迭代写入字节区间 $[\text{base}+is,\ \text{base}+(i{+}1)s)$ ， $n$ 次迭代后

\bigcup_{i=0}^{n-1}[\text{base}+is,\ \text{base}+(i{+}1)s)=[\text{base},\ \text{base}+ns)

区间两两不交（引 5.5 的区间代数），每格内容均为 $c^{s}$ ，故最终内存状态与 $\texttt{memset}(\text{base},c,ns)$ 逐字节相同。trace 也相同： $n$ 次写之间不存在观测点（循环内无读该区的点、无不透明 call，由引 5.3 的最近覆盖 def 判定保证），故由定义 0.1b 这 $n$ 次写一次也不单独进 trace，任何 trace 只在 OP3 处看见 $[\text{base},\text{base}+ns)$ 的最终字节；而 llvm.memset 不是不透明 call，LangRef 逐字定义了它的效果就是产生同一份最终字节状态，故替换后 $W/C/V/R$ 四类事件逐条对应。memcpy/strlen 模式同构，只是把常数 $c$ 换成源区的读值/把写换成比较。盈利性走定义 6.3 的 size 档。∎

出处：各模式在源码里各有一个入口——常数写：LoopIdiomRecognize.cpp:900 processLoopMemSet（内部走 :1097 processLoopStridedStore）；逐元素搬运：:837 processLoopMemCpy 与 :1279 processLoopStoreOfLoopLoad；找零扫描（strlen/wcslen）的形状要求写在 :2178 的注释里，开关是 :137 的 -disable-loop-idiom-strlen，统计项 :104；按代码体积编译时的那条避讱规则在文件头 :13。替换目标 llvm.memset/llvm.memcpy 的效果逐字定义在 LangRef §’llvm.memset’ Intrinsic 与 §’llvm.memcpy’ Intrinsic——这是”替换后四类事件逐条对应”那一步的依据（本 pass 不把循环换成不透明 call，而是换成效果已定义的 intrinsic）。

IndVarSimplify（Scalar/IndVarSimplify.cpp:9）——算法两件事：其一，规范出口条件——for (i = 7; i*i < 1000; ++i) 改写成 for (i = 0; i != 25; ++i)（注释例），trip count 成为显式常数比较，循环外对循环终值的引用搬到循环外重算；其二，SCEV 扩宽——把 A[i] 的 mul+add 地址算式替换成围绕 getelementptr 的指针归纳变量，每迭代一次加法，宽度取足防止回绕。效果：地址表达式从”每次重算”变成”每次迭代一步”；循环出口值不再依赖循环终值。意义：向量化器按 VF 步进指针；地址若不是指针形态就退化为逐元素乘加，代价模型会直接否决；trip count 显式化之后，”循环能否删除、能展开多宽”的判定依据就交给 SCEV 与 unroll——循环本身甚至因终值外提而变成死代码，正好交给下一个 pass（LoopDeletion）处理。

证明（引 4.2、引 4.3、引 2.4(M1)）。
终值外提：设循环外使用点 $u$ 引用循环内归纳变量 $v=\{a,+,b\}_L$ ，出口计数 $\mathrm{EC}=n$ （引 4.2 已给出闭式）。则 $u$ 处 $v$ 的值为 $a+bn$ ，它只依赖循环外量与常数 $n$ ，故可在 exit 之前用一次乘加算出——这是引 2.4 的 M1 在”把定义搬到循环外”方向的应用（操作数 $a,b,n$ 全在循环外，落点支配全部 use）。搬完之后循环内 $v$ 若无其他 use，即成为死代码（推论 2.3 的 use 计数为零），交给 ADCE。
出口条件规范化：把 $\{7,+,1\}$ 与谓词 $i^2<1000$ 联立解出 $n=25$ ，改写为 $\{0,+,1\}$ 与 $i\neq 25$ ；健全性由引 4.2 的闭式唯一性给出——两个循环的迭代次数与每次迭代中”被使用的量”逐点对应（原 $i$ 用 $i'+7$ 替换）。
扩宽： $w$ 位下 $\{a,+,b\}$ 若 $a+nb$ 越界即回绕（引 4.3），扩到 $w'$ 使 $|a|+n|b|<2^{w'-1}$ ，则宽类型里的递推与数学整数一致，推理合法；末尾 trunc 回 $w$ 位是无损的，因为真实值本就在 $w$ 位范围内。指针递进 $q_{k+1}=q_k+s$ 与 $q_k=\text{base}+ks$ 的等价由引 4.2 归纳，且指针算术走 getelementptr 而非整数加法，从而绕开引 0.6 的溢出义务。∎

出处：归纳变量的识别与分类 Wolfe, Beyond Induction Variables, PLDI 1992、Gerlek, Stoltz & Wolfe, TOPLAS 1995（demand-driven 沿 SSA 归纳，正是 SCEV 的路线）；实现 IndVarSimplify.cpp:9 与 SCEVExpander。

LoopDeletion（Scalar/LoopDeletion.cpp）——算法：三条判定路，每条在源码里各对应一个函数：循环可证从不进入（preheader 的每个前驱都以常量条件分支绕过它）、回边可证一次也不走（SCEV 给出零回边计数，或对首次迭代做一次符号求值、证明第一轮就退出）、循环是死的（体内无可观测副作用、出口 phi 的值循环不变）。另有两条硬性前提：必须有 preheader 与专用出口，且出口不能是 EH pad。效果：preheader 直通 exit。意义：结构上是循环、迭代次数却为 0 的循环如果不删，会阻碍后面所有以”循环存在”为前提的 pass——删除它本身就是把”此处没有循环”这条事实交给下游（定理 7.4）。

证明（引 4.2、推论 1.6、定义 0.1a、引 0.5）。三条路各对应一种”事件集为空”的论证：
(i) 回边一次也不走（ $\mathrm{EC}=0$ ）：由引 4.2 的闭式解出 $n=0$ ，推论 1.6 保证这是真实执行次数，故 body 一次也不执行，删除循环后 preheader 直通 exit，路径集与原图在”跳过零次 body”意义下同构；
(ii) 循环是死的：body 无可观测副作用且无循环外活值： $\mathcal{O}$ 中不含 body 的任何事件（定义 0.1a 的四类 $W/C/V/R$ 一个都没有），且其结果无人消费（推论 2.3 的 use 计数），故执行 $n$ 次与执行 0 次的 $\mathcal{O}$ 相同；
(iii) 循环从不进入：preheader 的全部前驱都以常量条件分支把 preheader 放在 not-taken 一侧，故不存在进入 header 的可行路径（引 0.5 的逆向用法：那条边本来就不可达）；删除循环后，出口 phi 的入项改成 poison 也不会被观测——因为那些 phi 只在循环真的执行过时才有意义。
需要说清一条常见误解：本 pass 不拿 profile 计数当删除依据（这个 commit 的 LoopDeletion.cpp 里读不到任何 !prof），三条路全部是静态证明；profile 只提供”值不值得做”的信息，不提供”能不能做”的授权（定义 6.3 与引 0.5 的分工）。
边界情形：无副作用但不终止的循环不能走 (ii)——原程序的结局是 $\uparrow$ ，删除循环后变成有限 trace，正是定义 0.2(i) 明文禁止的那一类（”把不终止变成终止”）。C++ 的前进保证使”无副作用却不终止”本身 UB，即 $\bot\in\mathcal{O}(P,\sigma)$ ，0.2 的义务整体解除，引 0.5 适用；而在实现里，这条语言级授权不是 pass 默认拿走的，而是被编码成 IR 里的属性：函数上的 mustprogress，或循环元数据 llvm.loop.mustprogress。判据写得很直白：除了体内无副作用，还要满足”函数带 mustprogress“或”每个子循环要么带 mustprogress、要么迭代次数静态可知”，否则一律不删（:112–:117 的注释与紧随其后的 mustProgress() 检查）。也就是说，无限循环不是被 pass 私自删掉的，而是被那条属性显式授权删掉的。∎

出处：三条路各有一处实现——从不进入：:147 isLoopNeverExecuted（调用点 :462，删前先把出口 phi 的入项填成 poison）；回边不走：:398 breakBackedgeIfNotTaken（:407 的 getConstantMaxBackedgeTakenCount 与 :409 的 getBackedgeTakenCount；首次迭代的符号求值在 :216 canProveExitOnFirstIteration，由 -loop-deletion-enable-symbolic-execution 控制，:40 的 cl::init(true) 说明它默认开着）；循环是死的：:63 isLoopDead（:106–:110 逐条查 mayHaveSideEffects()，droppable 的 intrinsic 除外），pass 入口在 :516；preheader / 专用出口 / 非 EH pad 那三条前提在 :442–:460。”死循环”的官方定义就在 :422–:428 的文档注释里（原文：”does not impact the observable behavior of the program other than finite running time, or … required to make progress by an attribute such as ‘mustprogress’ or ‘llvm.loop.mustprogress’ and does not make any”）；属性本身的语义见 LangRef §Function Attributes 的 mustprogress 与 §’llvm.loop.mustprogress’ Metadata，语言侧依据是 C++ [intro.progress]；官方摘要见 Passes.md 的 loop-deletion 一节。

LoopFullUnroll（Scalar/LoopUnrollPass.cpp:1640）——算法：trip count 静态已知且展开后体积在 Level 预算内（构造式直接把 Level 传进 LoopFullUnrollPass(static_cast<int>(Level), ...)，O2 比 O3 紧），把循环体复制 $N$ 份：归纳变量与出口条件每份代入常数。效果：循环消失，成为直线代码；LCSSA phi 的入项全变常数、随后被折叠。意义：跨迭代的冗余从此成为普通 GVN 能识别的同形重复；数组访问 A[i] 下标变编译期常数——这正是随后 SROA 再执行一遍能”delete small array after loop unroll”（:765）的原因。它与 unswitch 的衔接同样直接：guard 分支被常数条件替掉之后，剩下的就是无分支直线段。一个 pass 在清单中的位置，本身取决于其它 pass 为它创造的前提。

证明（定理 4.4、引 4.2、引 4.7、定义 6.3）。前提三条：rotate 已把 body 变成单 latch 的直线块（定理 4.4，故”复制 body”是复制一段无内部回边的指令序列）； $\mathrm{EC}=n$ 静态已知（引 4.2）； $n\cdot|B|$ 在预算内（定义 6.3 的静态体积项）。构造：把 body 复制 $n$ 份串联，第 $k$ 份中归纳变量 $\{a,+,b\}$ 代入常数 $a+bk$ ，出口条件按 $k<n$ 折为真（引 0.5 删掉假支）。等价性对 $n$ 归纳： $n=0$ 时由 LoopDeletion 的 (i) 处理； $n\to n+1$ 时前 $n$ 份按归纳假设等价，第 $n+1$ 份对应原第 $n+1$ 次迭代，其执行前提是前 $n$ 份未触发 UB/未提前退出。UB 的次序问题：第 $k$ 份的 UB 对应原第 $k$ 次迭代的 UB，而迭代的执行是有序的，故”新程序在第 $k$ 份 UB”蕴含”原程序在第 $k$ 次迭代 UB”，定义 0.2(ii) 不被触犯。LCSSA phi 变成单入项常量后由 trivial phi 折叠（LoopSimplify 那条证明）消失。数组下标常量化后，若整个 alloca 的访问区间集有限且不重叠，SROA 的划分（那条证明里的最小划分）会把数组切成 $n$ 个独立标量片并各自提升——引 5.4 的第二次应用。∎

逐函数下半场：全局冗余、常量传播与存活判定

VectorCombine（early folds）/ MergedLoadStoreMotion（Vectorize/VectorCombine.cpp / Scalar/MergedLoadStoreMotion.cpp:11；位置在 :770 与 :773，夹在 SROA 第二次进场与 GVN 之间）——算法：前者按目标代价模型做”标量/向量交互”的模式重写：extract(extract(...)) 与 extract(insert(...)) 折叠（:662 foldExtractExtract）、insert/extract 与 shuffle 互换（:5940 foldInsExtVectorToShuffle、:1096 foldBitcastShuffle）、”先提取再比较”改成”先比较再提取”（:1362 foldExtractedCmps）、从向量 load 里只取一个元素时退化为标量 load（:2131 scalarizeLoad）；文件头（:9–:11）写明这一类变换”不适合放进基于循环或 SLP 的向量化 pass”，所以才单独成一件；后者把 if-then-else 两侧同地址的 load 提到分支前、两侧不同的使用点用 select 接回（store 反向可沉）。效果：重复访存合并，向量指令的形态更贴近后端能直接高效实现的样子。意义：跨控制流的重复 load 是数据流 pass 的盲区——GVN 折 load 要求支配，分支两侧互不支配；必须有 pass 按图形态而不是值等价来消除（引 7.5 表中对应的那一行）。

证明（向量语义 + 引 2.4 + 引 0.7 + 引 5.3）。
VectorCombine：shufflevector 的语义是索引置换

\texttt{shufflevector}(a,b,m)_k=\begin{cases}a_{m_k}&0\leq m_k<N\\ b_{m_k-N}&N\leq m_k<2N\\ \text{poison}&m_k=\text{undef}\end{cases}

于是 $\texttt{extractelement}(\texttt{insertelement}(v,x,i),i)=x$ （同索引抵消）、 $\texttt{insertelement}(\texttt{insertelement}(v,x,i),y,i)=\texttt{insertelement}(v,y,i)$ （后写覆盖前写，引 5.5 的单格版本）都是索引算术的恒等式，逐 lane 成立即整体成立。splat 消除靠 $\forall k:\ v_k=c\Rightarrow v=\texttt{broadcast}(c)$ 。
MergedLoadStoreMotion：设菱形（源码注释叫 diamond，也叫 hammock：入口与出口各一个、中间分成两支的形状） $d\to\{B_1,B_2\}\to j$ ， $B_1,B_2$ 各有一条对同一 Location 的 load $\ell_1,\ell_2$ 。提到 $d$ 的合法性不能只靠引 0.7——load 可能陷阱（解引用非法地址即 UB）。这里的论证更强： $d$ 的每条出边子树里都存在对该地址的读，故任何经过 $d$ 的执行原本都会读一次这个地址，提前到 $d$ 不可能引入原本不存在的陷阱，定义 0.2(ii) 不被违反。值相同由引 5.3 给出（ $B_1,B_2$ 之间无支配关系但也无 may-alias 写插入，二者的最近覆盖 def 都是 $d$ 之前那一个），故 $\ell_1=\ell_2$ ，两处的 use 用 $\texttt{select}$ 或直接替换接回。store 方向反过来：沉到 $j$ 需要 $j\ \mathrm{pdom}\ B_1,B_2$ （引 2.5：任一支执行则 $j$ 必执行恰一次），且 $B_1,B_2$ 与 $j$ 之间无 may-alias 读（引 5.3），且两侧写入的值与地址同余（GVN 意义下）。∎

GVN / NewGVN（Scalar/NewGVN.cpp:9）——算法：逆后序给每个表达式按”操作数编号相同⇒同余”分配值号（哈希合并），同余类只保留一次计算；附带支配可折的 load→寄存器/常量替换（load PRE），以及按已知相等事实折叠分支条件（:3113 propagateEquality，调用点 :3382 与 :3407；新建 load 时 !range 元数据原样带过去，:1663）。NewGVN 改用稀疏形式：除了”操作 → 值号”的正向映射，还维护”值号 → 操作集合”的反向映射，于是某个值号变化时只需重算受影响的那些指令，不必整函数重扫；它多做一步符号求值与前向传播，目标是补上 SSA 系 GVN 的已知不完备点——识别 phi(a+b, c+d) 与 phi(a,c)+phi(b,d) 等价（以上均为 NewGVN.cpp:11-45 文件头的自述）。默认流水线跑的是 GVN：:774–:777 写的是 if (RunNewGVN) NewGVNPass(); else GVNPass();，而 RunNewGVN 由 -enable-newgvn 控制、默认 false（:215）。效果：跨块、跨循环的重复计算合并为单点。意义：EarlyCSE 已经消除了显然的冗余，而循环阶段（rotate/unroll/LICM）刚刚产生大量新的重复——真正的跨循环、跨块冗余到此时才形成，这是它安排在循环阶段之后的全部理由（定理 7.4）。

证明（同余归纳 + 引 3.1 + 引 5.3 + 引 2.7）。定义同余关系 $\sim$ 为最小的满足下式的等价关系：

v\sim v'\iff \begin{cases}\text{同 opcode、同 flags，且操作数逐个 }\sim & v,v'\text{ 为纯运算}\\ \text{同 Location，且最近覆盖 def 相同} & v,v'\text{ 为 load（引 5.3）}\\ v=v' & \text{否则}\end{cases}

健全性对 RPO 归纳（引 3.1 保证编号时操作数已编号）：设 $v\sim v'$ 且二者操作数在真实执行中取值相同，则由纯运算的确定性（定义 0.1a：纯算术不是事件，结果由操作数唯一决定，poison 情形两侧同为 poison，引 0.4）得 $v,v'$ 同值；load 那一支由引 5.3 给出。替换的额外条件是支配：leader 必须支配被替换点（引 2.7 的区间查询），否则需要在汇合处插 phi（此时 $\sim$ 仍成立，但改写从”替换”升级为”phi 构造”，落回定理 2.2）。NewGVN 的差别在关系本身：GVN 的 $\sim$ 是”同 op + 同操作数”的最小不动点，NewGVN 额外维护值号→操作的反向映射并做符号求值，于是它的闭包条件里多了”phi of ops 与 op of phis 同值”这一类等式——这是引 1.7 的又一次加细（把”语法同余”加细到”符号求值闭包下的同余”），代价是不动点迭代更慢（引 1.3 的界变大）。∎

出处：值编号与同余的两条经典路线是 Alpern, Wegman & Zadeck, Detecting Equality of Variables in Programs, POPL 1988（SSA 上的等价类）与 Click, Global Code Motion / Global Value Numbering, PLDI 1995；实现见 GVN.cpp 与 NewGVN.cpp:9。NewGVN 的算法出处写在它自己的文件头（NewGVN.cpp:11-45）里，点了三篇：稀疏形式取自 Gargi, A Sparse Algorithm for Predicated Global Value Numbering, POPL 2002，对照的 RPO 算法是 Simpson 的 SCC-Based Value Numbering（文件头只给了标题与作者，无 DOI），phi-of-ops 的完备化技术取自 Pai, Detection of Redundant Expressions: A Complete and Polynomial-Time Algorithm in SSA, 2015。

SCCP（函数级，Scalar/SCCP.cpp，solver 与 IPSCCP 共用）——算法：值格（常量/未定/top）× CFG 边格（可达/不可达）的稀疏不动点：常量沿 def-use 传播，边按条件判定剪枝。效果：常量传播到底，不可达分支整块删除。意义：与 JumpThreading 的分工是”值的常量性”与”路径上已确定的事实”——%x = add i32 41, 1 一路折叠为常量时，这里删除的范围比 threading 更彻底。

证明（推论 1.6、引 0.5、引 3.1）。与 IPSCCP 完全同一套论证，只是格坐标限制在单函数内： $L_v=\{\bot\}\sqcup\mathrm{Const}\sqcup\{\top\}$ 、 $L_e=\{\text{不可达}\sqsubset\text{可达}\}$ ，转移函数单调，定理 1.5 给 $\mathrm{MOP}\sqsubseteq\mathrm{MFP}$ ，推论 1.6 得”判为常数即真为常数、判为不可达即真不可达”，后者由引 0.5 授权整块删除。稀疏性来自 SSA：沿 def-use 传播只在被影响的 use 上入队（推论 2.3），而边的处理沿 RPO（引 3.1），故遍历一趟就能把信息推进一层，迭代轮数被嵌套深度而非指令数支配（引 1.3）。与 JumpThreading 的分工是条件的形式：threading 用的是”某前驱路径上 $c$ 已可判定”（路径局部事实），SCCP 用的是” $c$ 的定义在所有可达路径上都是同一常数”（全局事实），两者互补而不重叠。∎

出处：Wegman & Zadeck, Constant Propagation with Conditional Branches, TOPLAS 1991——标题里的 “with Conditional Branches” 就是本文说的”边格”；格与 solver ValueLattice.h:27、SCCPSolver.cpp:796；官方摘要 Passes.md。

BDCE（Scalar/BDCE.cpp）——算法：以 DemandedBits 结果为依据：自每个 use 反推”实际消费的位掩码”回传，shl/and/xor 一类会丢弃高位的指令的产出若 demand 为空即删，多余扩展的 sext 顺带降为 zext（文件头注释原话）。效果：结果被使用但部分位不被需要的计算消失。意义：它处理指令级 DCE 的盲区——shl 的结果有使用者，但只有高 16 位被消费；按位粒度重新判定一遍，”新暴露的 DCE 机会留给稍后的 ADCE”（流水线注释:784）。

证明（引 1.7、定理 1.2、定义 0.1a）。位格 $L=2^{\{0..w-1\}}$ 按包含排序，join 为并集，格的高度由位宽封顶（位集每多一个元素只多一档），故反向不动点由定理 1.2 终止。转移函数按 opcode 给出，例如

D(\texttt{and }x,m)=D(r)\cap \mathrm{bits}(m),\quad D(\texttt{shl }x,k)=\{i-k\mid i\in D(r),\,i\geq k\},\quad D(\texttt{trunc}_{N}\,x)=D(r)\cap[0,N)

D(\texttt{or/xor/add})=D(r)\ \text{（两侧全传）},\quad D(\texttt{select}(c,a,b))=D(r)\ \text{且}\ c\ \text{全位被需求}

删除判据： $D(v)=\emptyset$ 且 $v$ 无副作用。健全性： $\mathcal{O}$ 中每个可观测位都是若干输入位的函数， $D$ 的反向闭包恰是”能影响某个可观测位”的位集，故 $D(v)=\emptyset$ 意味着 $v$ 的任何位都不出现在任何事件里，删掉它 $\mathcal{O}$ 不变（定义 0.1a：纯算术不是事件，它的位只在被某个 $W/C/V/R$ 消费时才可观测）。sext→zext 是同一判据的弱化版：符号扩展的高位若不被需求，扩展的种类就无关紧要，换成更便宜的 zext 逐点在被需求的位上相等。这是引 1.7 的典型实例——把”use 关系”加细成”位级 use 关系”后，指令级 DCE 的不动点不再是不动点，必须重算一遍。∎

出处：位级需求分析的接口是 DemandedBits.h:41 的 class DemandedBits，对外的三个查询是 :55 getDemandedBits(Instruction*)、:61 isInstructionDead、:64 isUseDead；改写本体 BDCE.cpp:205 BDCEPass::run，sext→zext 那一条写在文件头注释里（:9–:13）；流水线位置与”新暴露的 DCE 机会留给稍后的 ADCE”那句注释在 :784（Passes.md 没有收录这个 pass，摘要以文件头为准）。

DFAJumpThreading + JumpThreading/CVP 二轮（:797–:800，这一段的流水线注释是 “Re-consider control flow based optimizations after redundancy elimination, redo DCE, etc.”）——算法：DFAJumpThreading 处理 switch 驱动的状态机——沿每条 threading 路径克隆块，让克隆体无条件跳到分析认定的下一个 case（DFAJumpThreading.cpp:9 的文件头带 CFG 例子）；随后 JumpThreading 与 CVP 把 GVN/SCCP/BDCE 之后新暴露的边与值事实再消费一轮。效果：状态分派的跳转变成直接跳转，冗余分支再减少一批。意义：GVN/SCCP 刚把常量传播到底，状态值到此时才是编译期已知的——这是它排在这个位置的全部理由（定理 7.4）。

证明（引 0.5、推论 1.6、定义 6.3）。DFAJumpThreading 的每条克隆路径对应原图中一条确定的进入路径：路径上的状态值经推论 1.6 已知为常量，故克隆体里那条 switch 的目标是编译期确定的，引 0.5 授权剪掉其余分支；改写后每条执行走过的块序列与原图逐一对应，事件序列不变。克隆带来的体积增量按定义 6.3 预算。JT/CVP 二轮的正确性与第一轮是同一条证明，只是输入的事实集更大——定理 7.4 的直接实例。∎

ADCE（Scalar/ADCE.cpp:9）——算法：反向可达，分三步。收根：isAlwaysLive 判定的指令一律标活（:246–:259：EH pad、mayHaveSideEffects() 的指令、以及非 br/switch 的终结指令；给常量做值 profile 插桩的调用除外），收根的那一趟在 :198–:201。回溯：沿操作数把活性往回传（:273 markLiveInstructions），并把”决定活指令是否执行”的分支一并标活（markLiveBranchesFromControlDependences，就是沿后支配树把控制依赖也拉进来）。补边界：从后支配树根的孩子里挑出以 return 结束的那些（真正退出程序的出口），其余子树（例如无限循环）整棵标活（:216–:230）；回边的终结指令默认也标活（-adce-remove-loops 的 cl::init(false) 在 :69）。未被标记者全删。文件头注释即其判定原则：”optimistically assumes that all instructions are dead until proven otherwise”。效果：死计算成批删除；不终止的循环默认保留——这正是定义 0.2(iii) 那一支义务的实现处。意义：正向 DCE 沿 use 链判定存活，循环内互相引用的归纳变量总是”被使用”；ADCE 从可观测行为反向推导，把这类闭环的死代码整体删除——因此必须排在各轮清理之后，此时根集合最准确。

证明（定义 0.1a、引 2.5、定理 1.2、引 0.5）。活集定义为最小不动点

\mathrm{Live}=\mathrm{lfp}\Bigl(S\mapsto R\cup\{\mathrm{ops}(i)\mid i\in S\}\cup\{\mathrm{term}(B)\mid B\text{ 中有 }i\in S\}\cup\{\text{后支配树上的祖先块终结指令}\}\Bigr)

其中根集 $R$ = 产生定义 0.1a 四类事件的指令： $W$ （对可观测地址的 store）、 $C$ （不透明/非纯 call）、 $V$ （volatile/atomic）、 $R$ （return），外加 EH pad 这类结构上不能删的指令；实现里的判据就是 mayHaveSideEffects() 加 isEHPad()（:246），它与定义 0.1a 那张”什么不是事件”的表互为反面。另一件事必须单独处理：从某个块出发到不了 return 的子树（无限循环），删掉它会把 $\uparrow$ 变成有限 trace，正是定义 0.2(iii) 禁止的那一类——所以实现沿后支配树把这些子树整体标活（:216–:230），而不是靠频度去猜。格是 $2^{I}$ 按包含排序，转移单调，定理 1.2 给终止。健全性： $i\notin\mathrm{Live}$ 意味着 $i$ 的结果不在任何根的操作数传递闭包里，且 $i$ 所在块的执行与否不由任何根控制依赖（后支配树的祖先标活正是引 2.5 的用法：若 $i$ 活，则决定” $i$ 所在块是否执行”的那些分支也必须活，否则删掉分支会改变 $\mathcal{O}$ 中事件的发生与否）。故删除 $\mathrm{Live}$ 之外的指令既不改变事件内容也不改变事件是否发生， $\mathcal{O}$ 逐点相同。与前向 DCE 的差别形式化为判据不同：前向用 $\{i\mid \mathrm{uses}(i)\neq\emptyset\}$ 的不动点，循环内互相引用的归纳变量满足它（phi 与其 latch 上的 add 互相引用形成环），于是”被引用”被误当成”被观测”；ADCE 把判据换成可观测根的反向可达，环里没有根就整环删掉。∎

MemCpyOpt（Scalar/MemCpyOptimizer.cpp）——算法：对 memset/memcpy/memmove 序列做区间代数；能做哪几件事，源码开头的统计项列得最齐（:71–:77）：删掉多余的 memcpy/memmove（NumMemCpyInstr/NumMemMoveInstr）、把一串常量 store 推成一个 memset（NumMemSetInfer，区间合并的数据结构就是 :81 起的 MemSetRanges：它的注释举的例子就是四个乱序的常量 store 合成 [0,3) 一段）、memmove 降级成 memcpy（NumMoveToCpy）、源区刚被常数写满的 memcpy 改成 memset（NumCpyToSet）、以及 call slot 与 stack-move 两类把”拷进去再拷出来”消掉的重写（NumCallSlot/NumStackMove）。效果：调用条数减少、长度缩短。意义：流水线注释给足动机——“Specially optimize memory movement as it doesn’t look like dataflow in SSA”（:585 与 :807 各出现一次），def-use 链看不出”搬运的是什么内容”，必须由专门的 pass 按地址区间处理（引 7.5 表中对应的那一行）。

证明（引 5.5、引 5.3、定义 0.1b）。三条改写各对应一条区间恒等式，前提都是”中间无 may-alias 访问”（由引 5.3 的最近覆盖 def 判定；实现里就是 MemCpyOptimizer.cpp:299 accessedBetween 与 :323 writtenBetween）：

\texttt{memset}(p,c,n_1);\ \texttt{memset}(p{+}n_1,c,n_2)\ \equiv\ \texttt{memset}(p,c,n_1{+}n_2)\quad(\text{引 5.5 的区间并})

\texttt{memset}(s,c,n);\ \texttt{memcpy}(d,s,n)\ \equiv\ \texttt{memset}(s,c,n);\ \texttt{memset}(d,c,n)\quad(\because s[0,n)=c^n\Rightarrow\text{拷贝即写常数})

\texttt{memset}(d,c,n_1);\ \texttt{memcpy}(d,s,n_2)\ \equiv\ \texttt{memset}(d{+}n_2,c,n_1{-}n_2);\ \texttt{memcpy}(d,s,n_2)\quad(\text{前段被拷贝覆盖，引 5.5})

三条各自的实现入口：第一条 MemCpyOptimizer.cpp:827 processMemSet（它转给 tryMergingIntoMemset，邻居可以是另一个 memset 或一个 store）；第二条 :1442 performMemCpyToMemSetOptzn；第三条 :1298 processMemSetMemCpyDependence。第三条有两个实现上的限制值得记下，它们正是引 5.5 与定义 0.1b 的具体义务：两个目的地址必须 MustAlias（:1302），且 $n_2$ 必须可证非零（:1313，否则改写只是个复杂的 no-op）。方向反过来的那种截短——memcpy 在前、memset 在后——本 pass 不做，因为 memcpy 的两个操作数不允许部分重叠（:1317–:1319 的注释：”memcpy operands cannot partially overlap, exact equality is allowed”），只允许完全相等。

每条的健全性论证同构，走的都是定义 0.1b：被合并掉或被截短掉的那些写，与它的后继写之间不存在观测点（引 5.3 判”中间无 may-alias 读”排除 OP1，中间无不透明 call 排除 OP2），故它们不进任何 trace；trace 里留下的只是每个观测点上该地址呈现的值，而三条恒等式保证这些值逐字节相同。这也解释了 MemCpyOpt 为什么必须依赖 MemorySSA 与 AA：它要证的不是”最终状态相同”，而是”中间没有观测点”。∎

DSE（Scalar/DeadStoreElimination.cpp）——算法：沿 MemorySSA def 链找每个 store 之后下一次可能别名访问：被另一写覆盖则删旧写；对象不逃逸且后续无读，store 连同 alloca 整体消失。效果：写次数下降，临时对象不再占用存储。意义：前端为值语义大量生成”构造→覆盖→析构”的写序列，这是唯一从内存视角删除它们的 pass；排在 ADCE 之后——ADCE 刚删除一批看似有副作用的调用，”可能存在读”这一保守答案到此时已被推翻。

证明（引 5.5、引 5.3、引 5.4、引 1.4）。判据：store $s_1$ 写 $L_1$ 是死的 $\iff$ 存在后继 store $s_2$ 写 $L_2\supseteq L_1$ （引 5.5 的区间包含），且 $s_1,s_2$ 之间不存在与 $L_1$ may-alias 的读（引 5.3：若有这样的读，它取的就是 $s_1$ 的值，删 $s_1$ 会改变 $\mathcal{O}$ ）。充分性： $L_2\supseteq L_1$ 使 $s_1$ 写入的每个字节都被 $s_2$ 重写，故两次写之后的内存状态与只写 $s_2$ 相同；中间无读 ⇒ 无观测点（定义 0.1b 的 OP1 被排除；OP2 也须排除，故 $s_1,s_2$ 之间夹着不透明 call 时，还得靠 AA 或 callee 的内存效果属性（memory(none)、memory(argmem: write) 这一类，见定义 0.1b 的出处）证明那个 call 读不到 $L_1$ ）⇒ $s_1$ 不进任何 trace ⇒ $\mathcal{O}$ 不变。第二条路是引 5.4：对象地址未逃逸且无读 ⇒ 整块存储私有且从不被观测，store 与 alloca 一起消失。排在 ADCE 之后的理由是引 1.4 的 join 项数减少：ADCE 删掉的那些调用原本是 AA 查询里的保守项（”可能有读”），它们消失后 $\bigsqcup_i\mathrm{AA}_i$ 的结论变强，DSE 才能执行删除——这是定理 7.4 的机会图里一条方向明确的边：ADCE → DSE。∎

MoveAutoInit + 再一轮 LICM + CoroElide + SimplifyCFG(hoist/sink) + InstCombine（:811–:827）——算法：MoveAutoInit 把标记为 auto-init 的指令（栈槽的自动零初始化）挪近真正使用它的块，从而在某些控制路径上整个省掉（Utils/MoveAutoInit.cpp:9，注释原话 “moves instruction maked as auto-init closer to the basic block that use it, eventually removing it from some control path”）；接着是正文里叫 LPM3 的那段循环流水线，里面只装了一件 LICM（:813）；CoroElide 处理协程帧的分配与销毁；最后 SimplifyCFG 带 hoist/sink 再清一次图、InstCombine 再折一次表达式。效果：ADCE/DSE 之后新出现的不变量与冗余被再消费一轮，清零写被推迟或删除。意义：NPM 不追求全局不动点，补偿方式是把”再执行一遍”固定写在次序里——每个清理 pass 本身就是下一轮优化机会的来源。

证明（定理 7.4、引 7.2 的不成立）。用机会算子表述：设 $x_k$ 为第 $k$ 个位置之后的 IR。GVN/SCCP 之后

O_{\mathrm{LICM}}(x_{\mathrm{GVN}})\supsetneq O_{\mathrm{LICM}}(x_{\mathrm{LPM1}})

因为 GVN 把跨循环重复折成单点后，新的循环不变量出现了；SCCP 把常量传到底后，原本”循环内才可知”的条件变成编译期可判定，于是 CVP 的事实集与 JT 的可 threading 边都变多。由定理 7.4，重复执行不是冗余而是拓扑序的必要补边。为什么不迭代到全局不动点？因为引 7.2 的前提不成立（InstCombine 的规则集不终止，且各 pass 之间存在互相创造应用条件的环），全局不动点未必存在；工程做法是把环截断成有限次重排，次数由经验确定，位置则固定在清单里：逐函数简化流水线里 LICM 出现在 rotate 之前、之后与清理阶段各一次（:714/:720/:814），InstCombine 每在一批改写之后就排一次（:667/:758/:791/:827），SimplifyCFG 同样（:666/:681/:757/:822，另有 :651 那一处只在 GVN-sink 打开时才排）；EarlyFPM 与模块优化阶段另有若干次，这条流水线本身又被内联器逐个 SCC 嵌套调用——总共执行了多少遍，用 opt -passes='default<O2>' -print-pipeline-passes 打印一次即可看到。MoveAutoInit 那一件另走引 2.4：零初始化是一次纯写，把它挪近使用点满足 M1（操作数是 alloca 地址与常量）、M2（落点支配全部 use）、M4（中间不得有 may-alias 写，否则初值被覆盖）——省掉的那些路径上它本来也不被执行，故 $\mathcal{O}$ 不变。∎

模块优化流水线：向量化收尾，模块级再遍历一次

（PassBuilderPipelines.cpp:1508）

EliminateAvailableExternally / ReversePostOrderFunctionAttrs（:1527）——算法：删掉非 LTO 场景不再需要的 available_externally 定义（:1527）；属性那一件在这个 commit 里范围很窄，做的是自顶向下（caller 先于 callee）的两条推断：先把调用图按 RefSCC 后序收集、再反向走一遍得到这个次序（:2402 deduceFunctionAttributeInRPO），只对”内部链接、有定义、仍被使用”的单函数 SCC 动手（:2417–:2420），逐函数调 :2323 addNoRecurseAttrsTopDown（若 $F$ 的全部使用都是”已标 norecurse 的函数里的调用”，则 $F$ 也标 norecurse）与 :2353 addNoFPClassAttrsTopDown（把全部调用点上观察到的 nofpclass 事实按位取交，写回 $F$ 的参数与返回值）。效果：available_externally 的定义体退化为声明，不再被后续每轮逐函数流水线重复处理，也不再充当引用关系的材料；callee 声明上的 norecurse/nofpclass 变多。意义：与逆拓扑的 PostOrderFunctionAttrs 方向相反——归纳推断（由 callee 的已知属性推自身）与代入推断（caller 把已知事实写给 callee）互为反向，两者结合之后属性集才逼近完备。

证明（linkage 语义 + 引 1.4 的全称量化）。available_externally 的定义是”仅供优化参考、不会被发射”，故删除定义体不改变任何可观测行为（它从未出现在 $\mathcal{O}$ 里）；但它若留着，会继续充当 GlobalDCE 的引用材料，把本该删掉的全局留在图里——这是释放信息而不是收益优化（定理 7.4 的同一逻辑）。前向传播的健全性是一条全称量化，两条推断各自一个形式：

\text{给 }F\text{ 标 }\texttt{norecurse}\iff \forall\ \text{使用 }U:\ U\text{ 是一个调用且调用方已标 }\texttt{norecurse}

\text{给 }F\text{ 的参数 }i\text{ 标 }\texttt{nofpclass}=C\iff C=\bigcap_{\text{调用点 }cs}C_{cs}\quad(\text{全交，最保守者胜})

按引 1.4，第二条就是所有调用点结论的 meet；第一条是同一思路的全称形式（任何一个反例就否决）。两者的前提都是调用点集合完整，所以实现把范围限制在内部链接（:2331 的 assert(F.hasInternalLinkage() && "Can only do top-down deduction for internal linkage functions!")）；norecurse 那一条还额外要求使用必须真的是调用（:2342–:2347 的 CB->isCallee(&U)），否则函数地址可能被一个 norecurse 函数返回出去、再被别处递归调用。两个方向合起来把属性集夹到同一个不动点：逆拓扑那趟给出 $A(f)\sqsubseteq$ 本地事实与 callee 闭包，正拓扑这趟给出 $A(f)\sqsubseteq$ caller 侧事实，两次 meet 后属性集单调变小（信息单调变多），且都由定理 1.2 保证有限步收敛。∎

Float2Int（Scalar/Float2Int.cpp:9，文件头把算法写得很短：”demote floating point operations to work on integers, where that is losslessly possible”）——算法：从三类”离开浮点域”的指令出发（fptoui、fptosi、fcmp，:89 findRoots），沿 def-use 反向走，为链上每条浮点指令算一个 ConstantRange，说明它的值实际落在哪段整数区间里（:116 seen、:203 calcRange，三态判定在 :122–:129）；碰到 uitofp/sitofp 就停，那是链的入口。链上没有不可映射的指令、且区间落在可表示范围内时，整链改写为整数对应物（:314 validateAndTransform、:404 convert；opcode 映射 :78 mapBinOpcode，比较谓词映射 :51 mapFCmpPred），整数位宽上限由 -float2int-max-integer-bw 控制（:45 的 cl::init(64)）。效果：浮点指令序列 → 整数指令序列。意义：浮点单元的吞吐限制、依赖长度与舍入模式约束一并解除，而数值上无损；整数化之后的表达式重新落入 SCEV/GVN 的恒等式适用范围。

证明（引 4.3 的浮点对偶 + 引 4.7）。核心是一条单射性论证。设 $x$ 是 $w$ 位整数，浮点格式尾数 $p$ 位（binary32 的 $p=24$ ），则

|x|<2^{p}\ \Rightarrow\ \texttt{sitofp}(x)\text{ 精确}\ \Rightarrow\ \texttt{fptosi}(\texttt{sitofp}(x))=x

且在该范围内 $\texttt{sitofp}$ 保序（单射 + 单调），于是

\texttt{fcmp olt}(\texttt{sitofp}(i),\texttt{sitofp}(j))\ \equiv\ \texttt{icmp slt}(i,j)\quad(|i|,|j|<2^p)

范围前提由 Float2Int 自己的 ConstantRange 三态传播给出（Float2Int.cpp:116 seen() 与 :122–:128 的 badRange/unknownRange/validateRange），必要时由 SCEV 补——这是引 4.3 的同一套可表示性检查，只是从”整数扩宽避免回绕”换成”浮点尾数容纳整数”。往返段省略是上述单射性的直接推论。反过来，把浮点链整体换成整数链时，每一步都要证”该步的浮点结果落在目标宽度可精确表示的集合内”，逐点相等才成立；证明不出来的步骤不改写——保守方向又一次由推论 1.6 保证。∎

出处：实现 Float2Int.cpp；sitofp/fptosi 的语义与舍入规则在 LangRef §Conversion Operations；”尾数能容下多少整数”这一步用的是 IEEE-754 的二进制格式定义（binary32 的 $p=24$ ），无专门论文。

再整形（:1609-1641）——几个只改结构、不改算术的 pass：LoopRotate 重转（注释说明 SimplifyCFG 等 pass 会把已经转换好的循环又转回原形，:1598；这一次带 CheckExitCount=true，:1611）→ LoopDeletion 再删 → LoopInterchange（依赖证明合法后交换内外层，使最内层访存连续；排入条件是 PTO.LoopInterchange，:1618；该值在 opt 里默认取自 -enable-loopinterchange 的 cl::init(true)（:219；clang 里则由 -finterchange-loops 经 BackendUtil.cpp:901 覆盖））→ LoopFuse（trip count 一致的相邻循环合并，省掉一遍索引；排入条件是 PTO.LoopFusion，:1626；PTO 构造式里写死 :338 的 LoopFusion = false;，clang 侧对应 -ffuse-loops（BackendUtil.cpp:902））→ LoopDistribute（把阻碍向量化的依赖访存组剥离成独立循环，其余部分保住向量化资格；只对带 llvm.loop.distribute=true 元数据或开了 -enable-loop-distribute 的循环生效，:1629 的注释就是这么写的）。效果：嵌套深度、层序、依赖分布三项调整到位，指令数不变。意义：向量化器的代价模型只评估”当前形态”——向量化面对的形态就是在这一节确定的。

证明（定理 4.4、引 4.6、定理 4.5 的三个推论）。
重转：SimplifyCFG 的合块规则会把尾测形的 latch 与 header 合并，从而把 do-while 变回 while-do，定理 4.4 的前提（body 是直线块）失效；再转一次即恢复，等价性证明与第一次完全相同（定理 4.4 是双向的）。
interchange： $\sigma(i,j)=(j,i)$ ，按定理 4.5 合法 $\iff$ 一切依赖向量在新维序下字典序非负，即原 $\vec d=(d_1,d_2)$ 满足 $d_2>0\ \vee\ (d_2=0\wedge d_1\geq 0)$ 。收益是访存连续性：原内层按 $i$ 步进（stride $=m\cdot s$ ）变成按 $j$ 步进（stride $=s$ ），这正是 LoopVectorize 的连续访存前提。
fuse：引 4.6 的精确条件（无 $B_2\to B_1$ 依赖， $B_1\to B_2$ 距离 $\geq 0$ ）。
distribute：定理 4.5 的 distribute 推论——把 body 的语句分成 $G_1,G_2$ 后分别成为循环，合法 $\iff$ 不存在 $G_2\to G_1$ 的依赖（否则被剥出的那个循环会先于依赖源执行）。收益是把带依赖的访存组隔离，使 $G_1$ 保住向量资格。∎

出处：distribution/fusion 的依赖判据最早系统写在 Allen, Callahan & Kennedy, Automatic Decomposition of Scientific Programs for Parallel Execution, POPL 1987；实现 LoopInterchange.cpp、LoopFlatten.cpp、LoopFuse.cpp、LoopDistribute.cpp；官方摘要 Passes.md。

LoopVectorize（addVectorPasses，:1341；合法性单独成文件 Vectorize/LoopVectorizationLegality.cpp）——算法：LAA 给出依赖三分类，静态可证的循环按代价模型选出的向量宽度 VF 重写为向量体（候选宽度逐个估价，模型本体是 :764 起的 LoopVectorizationCostModel）；不确定的插运行期对齐/别名检查、生成检查失败的标量版本回退；无法向量化的依赖按 reduction/gather/scatter 特化。效果：每迭代 N 条标量运算合并为一条向量运算。意义：吞吐提升 VF 倍由硬件给出，但它必须最后做——它放大的是此刻已成形的 IR，LCSSA phi 与 unroll 留下的冗余都会进入代价模型；提前做等于把未整理的形态一起放大，而且未必能还原。

证明（定理 4.5 的 vectorize 推论、引 4.7、引 4.3、引 0.5）。调度 $\sigma(k)=(\lfloor k/\mathrm{VF}\rfloor,\ k\bmod\mathrm{VF})$ ：第 $\lfloor k/\mathrm{VF}\rfloor$ 个向量迭代的第 $k\bmod\mathrm{VF}$ 条 lane 承担原第 $k$ 次迭代。逐项验证定理 4.5 的约束：
(i) 依赖——距离 $d\geq\mathrm{VF}$ 的跨向量迭代依赖被 $\sigma$ 保序； $d=0$ 的循环内依赖由向量体内语句顺序保持（lane 内顺序即原语句顺序）； $0<d<\mathrm{VF}$ 的依赖非法，除非它是被识别的 reduction 或 induction。
(ii) reduction——把 $\bigoplus_{k=0}^{n-1}a_k$ 重排成 $\bigoplus_{l}\bigoplus_{q}a_{q\mathrm{VF}+l}$ 需要 $\oplus$ 结合交换：整数加减在 $\mathbb{Z}_{2^w}$ 中无条件成立（引 4.7），浮点需要 reassoc 授权，否则这条推论不可用——这就是”浮点 reduction 不向量化”的全部理由。
(iii) 访存——连续访问（stride $=$ 元素大小）映射为一条向量 load/store；非连续映射为 gather/scatter；may-alias 的指针对生成运行期检查，把输入空间二分为”可证安全”与”走标量回退版”，两支各自满足 (i)（引 0.5 的镜像用法，与 LAA 那条证明相同）。
(iv) 余数—— $\mathrm{EC}=\mathrm{VF}\cdot q+r$ 时生成 $q$ 个向量迭代加 $r$ 个标量迭代，迭代序列与原循环逐一对应（引 4.2 的闭式给出 $q,r$ ）。
(v) 指针递进——按 $\mathrm{VF}\cdot s$ 步进，宽度取足以避免回绕（引 4.3）。
排在最后的理由由定理 7.4 给出：代价模型度量的是当前形态，而形态在 LPM2 与再整形两节才定型；提前做会把 LCSSA phi 与 unroll 留下的冗余一起放大进向量体，且向量化后的 IR 很难被标量 pass 还原（机会图里这是一条几乎单向的边）。∎

出处：依赖判据 Allen & Kennedy, TOPLAS 1987，调度合法性的仿射框架 Feautrier, IJPP 1992 Part I；LLVM 侧文档 Vectorizers.md，实现 LoopAccessAnalysis.h:1049 与 LoopVectorize.cpp:1172（runtime check 的生成点）。

SLPVectorize（Vectorize/SLPVectorizer.cpp:9；排入条件是 PTO.SLPVectorization，:1444，clang 侧由 -fslp-vectorize 经 BackendUtil.cpp:907 设定）——算法：自底向上：以相邻的同构操作（通常是连续 store 或对向量操作数的逐元素运算）为起点，沿 use-def 链向上构造”打包树”，代价核算通过则整树向量化。效果：直线代码中的独立标量链合并为向量运算加 shuffle。意义：它利用的是不依赖循环的并行度——unroll 留下的多份直线副本正是它的输入，与 LoopVectorize 互补。

证明（lane 独立性 + 定义 6.3）。打包树的每个节点是一组同构标量操作 $\{o_1..o_{\mathrm{VF}}\}$ ，向量化为一条 $\mathrm{VF}$ 宽指令的健全性条件是 lane 独立： $\forall i\neq j$ ， $o_i$ 与 $o_j$ 之间无数据依赖（各自的 def-use 子图不交，访存则要求 AA 判 NoAlias 或区间不交，引 5.5）。在此条件下 SIMD 的逐 lane 语义与标量序列的语义逐点相同：

\texttt{vop}(a_1..a_{\mathrm{VF}},\,b_1..b_{\mathrm{VF}})_l=\texttt{op}(a_l,b_l)\quad\forall l

对树高归纳：叶子（操作数）由 pack/shuffle 重排到位（shufflevector 的索引恒等式，见 VectorCombine 那条证明），内部节点按上式逐 lane 成立。代价核算按定义 6.3：收益是 $\mathrm{VF}$ 条标量折成 1 条，成本是必要的 shuffle 与 pack——因此 SLP 经常出现”打包比不打包更贵”的负收益树，剪枝依据就是这个代价度量。∎

出处：SLP 的原始论文 Larsen & Amarasinghe, Exploiting Superword Level Parallelism with Multimedia Instruction Sets, PLDI 2000（”打包树”就是它的 superword）；实现 SLPVectorizer.cpp:9。

LoopSink / InstSimplify / DivRemPairs / MergeICmps→ExpandMemCmp——几件收尾的 pass：LoopSink 把 LICM 提到 preheader、但使用点频度更低的指令再沉回循环内（文件头自述是 “the inverse transformation of what LICM does”，用 alias set tracker 拿更准的别名信息、用 BFI 找最优落点，LoopSink.cpp:9；注意它开头就查一道门槛：函数带运行期 profile 数据才干活，:360 的 if (!F.hasProfileData()) return PreservedAnalyses::all(); 与它上面那两行注释写的理由——“With static profile, the sinking decision may be sub-optimal”，静态频度下下沉的判定可能更差，不如不做）；InstSimplify（Scalar/InstSimplifyPass.cpp）单遍折掉 LCSSA phi 残留与单引用 trivial；DivRemPairs 把同被除数/除数的 {x/d, x%d} 配对折成一次除法 + 一次乘法减法（Scalar/DivRemPairs.cpp:9，文件头自述是 “hoists and/or decomposes/recomposes integer division and remainder instructions”）；MergeICmps 把逐字节 icmp+and 链识别回 memcmp（Scalar/MergeICmps.cpp:9），ExpandMemCmp 再把 memcmp 展开成”对目标最优的 load + 比较”序列（文件头原话：”expand memcmp() calls into optimally-sized loads and compares for the target”，Scalar/ExpandMemCmp.cpp:9）。效果：数据搬运与比较类指令的形态全部贴近后端能直接高效实现的形式。意义：它们共同处理一类非算术 IR——SSA 数据流视角看不到的那部分。

证明（引 2.4、注记 6.4、trivial phi、整数除法定义、字典序）。
LoopSink 是 LICM 的逆运算，合法性同走引 2.4 的 M1–M4（方向相反：M2 要求落点支配全部 use，M3 由 $f_{\text{落点}}<f_{\text{preheader}}$ 给出收益）；存在的理由正是注记 6.4——LICM 当时的 $\Delta$ 是用当时的频度与寄存器压力算出的，可能不准，需要有 pass 回头修正；这也是它开头就要查 hasProfileData() 的原因——没有真实计数时， $f_{\text{落点}}<f_{\text{preheader}}$ 这条判据本身不可靠，源码注释写的就是静态 profile 下下沉决定可能更差，于是宁可不改。
InstSimplify 的主力是 trivial phi： $\varphi[v]$ 只有单一入项时，phi 的选择函数恒取 $v$ （定理 2.2 的构造在 $|J^+|=0$ 时退化），故 $\varphi[v]\equiv v$ 。
DivRemPairs：由整数除法的定义 $x=q\cdot d+r$ ，其中 $q=\texttt{x sdiv d}$ （截断向零）、 $r=\texttt{x srem d}$ ，故 $r=x-q\cdot d$ 逐点成立。唯一的溢出隐患是 $q\cdot d$ ： $q=\mathrm{INT\_MIN},\ d=-1$ 时乘法回绕——但该情形下 sdiv INT_MIN, -1 本身就是 UB，由引 0.5 这些执行不需要保护，故在非 UB 的全部执行中 $|q\cdot d|\leq|x|$ 不回绕。收益是省掉一次多周期除法。
MergeICmps/ExpandMemCmp： $n$ 字节 memcmp 的语义是字节串的字典序比较，而字典序等于把字节串按大端解释成整数后的数值序：

\mathrm{cmp}(a,b)=\mathrm{sgn}\Bigl(\textstyle\sum_{k=0}^{n-1}(a_k-b_k)2^{8(n-1-k)}\Bigr)

故在小端机上按字展开需要先 bswap 再做无符号比较，尾块单独处理 $n\bmod W$ 字节（ $W$ 是机器字长的字节数）；逐字节 icmp+and 链反向识别回 memcmp 用的是同一条等式的语法侧（模式匹配）。∎

再来一轮内联 + 逐函数简化（buildModuleInlinerPipeline，:1064）——算法与内联一节相同：把 callee 复制进来，就地再简化一轮。效果：LTO 导入与新直接边（devirt 前置、内联解锁）产生的调用点得到同等待遇。意义：”内联产物需要再简化”这条次序规则第二次出现——整条逐函数流水线作为模块级 pass 的附属部分再执行一遍。

证明（定理 7.4）。机会图上内联有两条出边：一条指向 SCCP/GVN（常量与重复表达式进了新上下文才可见），一条指向自己（内联出的新调用点又满足阈值）。第二条出边构成环，故必须截断成有限次重排——buildModuleInlinerPipeline 就是这次截断。每一轮之后 $O_{\text{逐函数简化}}$ 严格变大（新搬进来的代码从未被简化过），由定理 7.4，不再简化就等于放弃这一轮内联的全部收益。∎

GlobalDCE / ConstantMerge / MergeFunctions / WholeProgramDevirt（:1723；收尾段的真实次序是 :1701 GlobalDCE → :1702 ConstantMerge → :1707 MergeFunctions → 最后才是 devirt；后两件的默认开关在本条末尾交代）——算法：devirt 消费前奏 CalledValuePropagation 的 !callees 候选集：单实现点直接改直调（源码统计项 NumSingleImpl，WholeProgramDevirt.cpp:127），多目标插入”函数指针 == 常数？”的分支漏斗（branch funnel）接 direct call，只对用了 llvm.assume(llvm.type.test) 或 llvm.type.checked.load 的调用点动手（:30），另有不限 LTO 的 speculative 模式（-devirtualize-speculatively，:52）；GlobalDCE 沿引用图删失去引用的 internal 全局与 vtable 项（GlobalDCE.cpp:9）；ConstantMerge 合并重复常量；MergeFunctions 先算结构哈希、再对同哈希的函数对做逐指令全序比较，mergeTwoFunctions（:1122）在两者不能直接互调时（一方是 interposable——链接期可能被别的翻译单元里的同名定义替换——或双方都受 ODR（One Definition Rule：同一实体在各翻译单元里的定义必须相同）约束）新建一个 internal 函数，让两边都变成跳到它的 thunk（跳板函数，:1126）。效果：间接调用数趋近于零、全局表变小、代码体积下降。意义：调用目标从运行期查 BTB（branch target buffer：硬件用来预测间接跳转目标的表）变成编译期已知的常数目标，链接期还能得到更好的布局信息；这些判断只有在全部优化完成之后才稳定——任何后续内联都可能重新打开调用边集合，因此放在最后。

两个默认值必须先说清，否则清单会被读错：MergeFunctions 只在 PTO.MergeFunctions 为真时排入（:1706），而这个值默认取自 -enable-merge-functions 的 cl::init(false)（:191；clang 侧由 -fmerge-functions 经 BackendUtil.cpp:908 覆盖）；WholeProgramDevirt 在这一段只在 -enable-devirtualize-speculatively（:321 的 cl::init(false)）打开且不是 LTO 时才排入（:1718），LTO 流水线里则是无条件排的（ThinLTO post-link :1969、full LTO pre-link :2039、ThinLTO pre-link :2120）。换句话说，默认的 clang -O2（非 LTO）在这一段实际只跑 GlobalDCE 与 ConstantMerge；函数合并与去虚拟化要额外开关或走 LTO。

证明（引 1.4 的过近似、可达性、unnamed_addr、双模拟）。
devirt：候选集 $S$ 满足 $S\supseteq S_{\text{运行期}}$ （CalledValuePropagation 那条证明）。 $|S|=1$ 时改直调，事件集不变（间接/直接跳转都不在 $\mathcal{O}$ 中，被调函数的 body 执行序列相同）。 $|S|>1$ 时构造 guard 链 $\texttt{if}(fp=\&f_1)f_1()\ \texttt{else if}\cdots\texttt{else }fp()$ ：对 $S$ 做穷尽情形分析，每个运行期可能值都命中某一支，或被最后那条间接调用接住，故逐点等价。健全性前提是 $S$ 完备，而完备性要求全程序可见（LTO）——外部代码持有的函数指针不在传播范围内，故 pass 只处理 llvm.type.test/llvm.type.checked.load 覆盖的点（WholeProgramDevirt.cpp:30）。
GlobalDCE：从根（被发射的符号、活代码引用）在模块引用图上做可达性，不可达的全局其地址从不进入 $\mathcal{O}$ （定义 0.1a 的可观测性），删除不改变任何事件。
ConstantMerge：两个逐字节相同的常量合并为一个，需要 unnamed_addr——否则程序若比较两个常量的地址，合并会改变 icmp eq ptr 的结果（指针身份是可观测的）。带 unnamed_addr 时地址身份不可观测，故合并安全。
MergeFunctions：结构同构 = 存在值集合上的双射 $\phi$ ，使每条指令的 opcode、flags、类型一致且操作数经 $\phi$ 对应。 $\phi$ 是双模拟（bisimulation）：两侧的执行步一一对应且产生相同事件，故 $\mathcal{O}$ 相同，把其中一个换成跳到另一个的跳板合法。∎

New Pass Manager：把次序表达为数据

前面各章讲的是”次序为什么是这样”（定理 7.4 的机会图）与”每一步为什么合法”（T0–T7）。本章讲承载它们的框架：NPM 自身承担的职责很少，五条设计职责加一个主循环即可说完。原因在于次序不再由 C++ 的调用链表达，而是变成了数据——被省掉的正是”次序”这一层，它被移入 PassRegistry.def 与解析器。

五条设计职责

pass 与调度解耦：pass 是实现 run(Unit&, AnalysisManager&) 的普通对象；”对一层内每个成员各执行一次”由 manager/adaptor 负责，pass 对遍历无感知。
分析懒算 + 精确作废：结论缓存在 AnalysisManager，键为 (分析ID, IR对象地址)；每个 pass 返回 PreservedAnalyses 点名保住了哪些分析，manager 每执行完一个 pass 立刻 invalidate（PassManagerImpl.h:28 的主循环，逐 pass 的固定顺序：PI.runBeforePass 判定 :73 → Pass->run :76 → AM.invalidate :80 → PI.runAfterPass :84 → PA.intersect :88，收尾再对本层缓存整体声明 preserve :95）。
流水线是数据：PassRegistry.def 一张 X-macro 表（一个 .def 文件里只写宏调用列表，包含方各自定义宏体，就能展开成注册代码、解析代码等不同东西）登记了全部变换 pass 与分析的名字与构造式：变换按 MODULE / CGSCC / FUNCTION / LOOP 四个层次各有 *_PASS 与 *_PASS_WITH_PARAMS 两类宏，分析同样按四个层次各有 *_ANALYSIS 宏（:353-392 是 FUNCTION 那一段）；想知道确切有多少个，按宏名前缀 grep 这个文件数一遍即可；PassBuilder::parsePassPipeline（PassBuilder.cpp:2718）把 function(sroa,loop-mssa(licm)) 解析成 manager 树，首 pass 层次不够时自动向上补 adaptor。
无全局注册：pass 选项即构造函数参数，sroa<preserve-cfg> 的尖括号由解析器填入。
观测有钩子：PassInstrumentation 回调贯穿每个 pass 前后，runBeforePass 返回 false 即整体跳过；-print-before/-after 全部实现在这几个回调槽上。

第 1 条是本文能按”定理 → 引用”组织的前提：pass 不知道自己被调度在哪一层，故同一条引理（例如引 2.4 的 M1–M4）可以被 LICM 在 loop 层引用、被 LoopSink 在 function 层引用，而不需要两份实现。第 3 条是定理 7.4 能被验证的前提：次序若硬编码在 C++ 调用链里，就无法打印、无法做重排实验；它是数据，所以 opt -print-pipeline-passes 能把本文的目录原样输出。

跨层的两类衔接机制

变换用 adaptor（ModuleToFunctionPassAdaptor 逐函数驱动内层流水线并逐函数作废缓存，PassManager.cpp:107），分析缓存用 proxy（InnerAnalysisManagerProxy，PassManager.h:601，设计说明在 :588 起的注释；外层函数列表失效则内层缓存整体作废）。FunctionToLoopPassAdaptor 额外携带契约：进入 loop 流水线前强制补 LoopSimplify + LCSSA，循环按逆后序从最内层向外处理，结构被改写时经 LPMUpdater 维持次序不变量（LoopPassManager.h:13）。

证明（adaptor 与 proxy 各自的不变量）。adaptor 的义务是把”内层流水线的 preserve 声明”翻译成外层的声明，它按成员逐个作废：内层对函数 $f$ 执行完之后，只有 $f$ 的缓存可能失效，故外层保留其余函数的结论。这一翻译的正确性依赖一条前提——内层 pass 不得跨函数改写（IR 的分层容器结构保证 Module 层以下的 pass 拿不到别的 Function）；违反者（内联）必须放在 CGSCC/Module 层，这正是内联器不能写成 FunctionPass 的形式理由。proxy 的义务是闭包条件：内层结论的宿主是外层结构，外层函数列表一变（增删函数），内层缓存的地址键可能已指向被删对象，故整体作废。FunctionToLoopPassAdaptor 的契约则是引 3.5 与 (C1)–(C4) 的进场条件：内层先（引 3.5）、规范形（(C1)–(C4)），两者都是 loop pass 证明里被反复引用的前提，于是框架把它们做成不变量而不是让每个 pass 自己检查。∎

preserve 契约：整条流水线中最容易出错的一环

分析机制的其余部分（懒算、getResult<A> 缓存未命中才构建、requires 的子分析迭代到不动点后按序补齐、成环直接 assert、RequireAnalysisPass 预热 PassManager.h:913 / InvalidateAnalysisPass 丢弃 :940、文本名注册于 PassRegistry.def 的 *_ANALYSIS 节 :353-392）都是工程细节，只有一条值得单独证明：缓存健全性。

定义 N.1。分析缓存 $C\subseteq\mathcal{A}\times\mathrm{Addr}$ ， $(A,u)\in C$ 读作” $A$ 对 IR 单元 $u$ 的结论已算出并缓存”。不变量

(\mathrm{I})\quad \forall (A,u)\in C:\ A(u)\text{ 的缓存结论对当前 IR 仍成立}

引理 N.2（主循环维持 (I)）。设 pass $P$ 声明的 preserve 集合为 $S_P$ ，且 $P$ 的声明是真的：

S_P\subseteq\{A\in\mathcal{A}\mid A\text{ 的结论在 }P\text{ 之后仍成立}\}

则主循环”run $P$ → invalidate $C\setminus S_P$ “之后 (I) 保持。证明：对 pass 序号归纳。设 $P$ 之前 (I) 成立； $P$ 之后被删的是 $\neg S_P$ 中的条目，留在 $C$ 里的条目全在 $S_P$ 中，由”声明是真的”这一前提它们仍成立； $P$ 运行期间新算出的条目由构造成立（分析总是对当前 IR 计算）。故 (I) 在 $P$ 之后成立。∎

引理 N.3（方向的不对称）。整条流水线里，分析结论的聚合是保守的（引 1.4：多层结论取 join，任一层不确定则整体不确定），而 preserve 的声明是乐观的（引理 N.2 的前提无法被检查）。两者出错的后果也不同：聚合偏保守只是少优化；声明不成立（pass 说保住了某份结论、实际没保住）则 (I) 被破坏，下游 pass 会用针对旧 IR 的结论去改写新 IR，产出语义错误的程序——而且形态合法，Verifier 不报（见分析章 Verifier 一条），缓存层也无从检测（键还是那个地址）。这就是为什么 PreservedAnalyses 的默认值是 none()（什么都没保住），而 all() 必须显式书写、逐个 pass 审计；也是为什么流水线注释会精确到名字地写 “LPM2 的那几个 pass 不 preserve MemorySSA”，LPM2 进 loop 时直接传 UseMemorySSA=false（:763，注释在 :759）——宁可放弃一份代价高的分析，也不采信一份未经审计的声明。∎

顺带解释了本文分析章那句”abandon 用得最多的就是 SCEV”：SCEV 的结论是对当时 IR 的符号推导（引 4.2 的闭式依赖具体的 def-use 形状），任何循环内改写都可能使它失效，而”是否失效”没有代价低的判据，故它默认不被 preserve——引理 N.3 的乐观声明在这里被彻底放弃，改成每轮重建（重建有界，引 1.3）。

验证：让编译器自己打印这份目录

# 把 -O2 的完整清单打出来（本文目录的机器可读版）
opt -passes='default<O2>' -print-pipeline-passes -disable-output /dev/null

# 单看任何一个 pass 前后的 IR
opt -passes='default<O2>' -print-after=loop-rotate -print-before=loop-rotate t.ll

# 只执行到某一处：验证"去掉其中一环之后，后面某个 pass 的合法性前提就失去依据"
opt -passes='function(instcombine,loop-mssa(loop-instsimplify,loop-simplifycfg,licm))' t.ll

# 校验形态合法性（引理 N.3 说明它查不出语义错误，但形态错误一个不漏）
opt -passes='verify' -disable-output t.ll

四条命令对应本文的四类断言：清单（定理 7.4 的拓扑序）、前后 IR（每个 pass 的”效果”一栏）、局部重排（机会图的边）、verify（定义 0.2 的形态侧）。算法→效果→意义→证明，四列答案各有一条命令或一条定理对应。

总结 · 次序即算法

先按章复述一遍——每章一句结论，与正文标题一一对应；然后给出三条贯穿全文的共性。

章节	一句话结论
通用理论	T0–T7 这批工具（T0 精化：事件字母表 $W/C/V/R$ + 三类结局 $\tau/\bot/\uparrow$ / T1 格 / T2 支配 / T3 遍历序 / T4 循环代数 / T5 内存版本 / T6 频度 / T7 规范化）覆盖了后文全部证明；每件都有若干消费者。被引最多的是引 0.5（UB 可剪），覆盖面最宽的是引 2.4 的 M1–M4——凡是在 IR 里移动指令的改写都要满足这四条
分析 Pass	三类只读事实：图分析回答”是否允许改写”（支配/循环/调用图，T2/T3），数据流分析回答”改写是否安全”（SCEV/MemorySSA/AA/LAA，T1/T4/T5），元信息回答”改写是否有收益”（频度/assume/TLI，T6）
模块级前奏	把前端输出整理成可分析的形式：属性标注、expect 降级、全局常量化、必选内联展开——之后 profile 与内联阈值才度量得准（引 1.4 的项数越少越保守）
沿调用图内联	SCC 逆拓扑（推论 3.4）：先减小自身体积，再被内联进其它函数；复制进来之后立刻再简化一轮，因为内联产物需要再加工
函数简化上半场	SROA 建立 SSA 形式（引 5.4 + 定理 2.2）；JT 与 CVP、SimplifyCFG 与 InstCombine 分别负责图和表达式，交替排布、互相创造应用条件；Reassociate 先把式子规范化，GVN 才认得出同形（引 7.6）
循环 LPM1	先把循环整理成契约形（(C1)–(C4) + 定理 4.4 的 do-while 尾测），再把不变量移出循环（引 2.6 + 引 2.4）；”是否允许”由支配树回答，”是否安全”由 AA 回答
循环 LPM2	迭代次数可静态确定的循环展开成直线代码（引 4.2 + 定理 4.4），匹配模式的循环换成 libc intrinsic（引 5.5 的区间恒等式），归纳变量规范化成指针递进（引 4.3）——全部是为向量化准备输入
函数下半场	循环阶段产生的新冗余到此时才形成，GVN/SCCP 消除重复（同余 + 推论 1.6）；BDCE/ADCE/DSE 按位、按可观测行为、按堆版本三个判据重新计算存活集（引 1.7 的三次加细）
模块优化	整形的那几个 pass 按定理 4.5 与引 4.6 调整嵌套、层序与依赖分布，向量化放在最后、只放大最终形态；收尾先做 GlobalDCE 与 ConstantMerge，devirt 消费的正是前奏中 CalledValuePropagation 得到的候选集（默认的非 LTO `-O2` 里它要开关才排入，见该条）
New Pass Manager	框架只有三部分：`run(unit, AM)→PreservedAnalyses` 的契约、缓存 + 逐 pass 作废的主循环、`PassRegistry.def` + 解析器把流水线当数据；其中最容易出错的是 preserve 声明（引理 N.3 的方向不对称）

然后是三条贯穿全文的共性。

其一，证明的复用率极高。每个变换与分析条目后面都跟着一段”证明”，通用理论章的每一条也各自就地附证；独立的新论点只有通用理论那一章，剩下的都是引用加一步特化。按编号 grep 一遍就能看出哪几条被引用最多，出现最频繁的是这几条：引 0.5（UB 可剪）、定义 6.3（盈亏）、引 5.3（最近覆盖 def）、引 2.4（代码移动四条件）、引 1.4（join 聚合）、引 4.2（闭式与终值）、定义 0.1a（事件字母表）、推论 1.6（SCCP 型保证）、引 5.4（私有存储提升）——其中引 5.4 一条被 SROA、mem2reg、GlobalOpt、LICM 的 promote 与 DSE 共用；定理 7.4（机会图的拓扑序）字面上的引用不算多，但它的实质（”上游产物是下游前提”）几乎每章都要用一次。这解释了本文开头那个观察：真正独立的算法有限，真正独立的道理更少。

其二，每个 pass 的存在理由高度同构：它消除一个别的 pass 的表示盲区（引 7.5 那张表）。SSA 数据流看不见聚合（SROA 补）、看不见内存搬运（MemCpyOpt 补）、看不见位级死（BDCE 补）、看不见循环内互相引用的死代码（ADCE 补）、看不见分支两边的重复访存（MergedLoadStoreMotion 补）；而每个改写者的产物又成了别人的前提——SCEV 要 rotate 过的形，GVN 要 reassociate 过的式，向量化要 unroll 过的块，DSE 要 ADCE 先删掉那些保守的 call（引 1.4 的 join 项变少）。中端流水线就是这两组关系：盲区与对应的 pass，前提与对应的次序。

其三，各章不是并列的，而是一条流水线的先后段。把每一段的交接物写出来，散落各章的那些配对——rotate→LICM（LoopRotationUtils.cpp:52 旁注释）、unswitch→full unroll（:723）、full unroll→SROA（:765）、ADCE→DSE——就不再是孤立的配对，而是同一个事实（定理 7.4）的不同侧面：上游的产物是下游的前提。整条链：

① 前端 IR：alloca 遍布函数体、attrs 缺失、expect 未降级、间接调用目标未知
      │ 模块级前奏：整理形态 + 建立属性档案（attrs/expect/全局常量/必选内联/间接调用候选集）
②    ▼
 可分析的模块：属性齐备，潜在调用图就位，候选集元数据已挂
      │ 沿调用图内联：跨过程数据流折成函数内 def-use；
      │   每内联一批，嵌套调用一次逐函数简化（内联产物到此才完成加工）
③    ▼
 函数体：SSA 形式已建立（SROA），表达式已规范化（Reassociate），路径上已确定的事实已写成 CFG 形状与元数据（JT/CVP）
      │ LPM1：循环先整理成契约形（LCSSA + do-while 尾测），不变量再移出循环（LICM）
④    ▼
 规范化循环：trip count 静态可定、归纳变量为指针递进、guard 已外提
      │ LPM2：迭代次数可静态确定的循环展开成直线（full unroll）→ 下标成常量、数组可切分（SROA 再执行一遍）
      │        匹配模式的循环整体换成 libc intrinsic（idiom）；迭代次数为 0 的循环直接删除（deletion）
⑤    ▼
 冗余与死代码集中出现的函数（跨循环重复、位级死、循环内互相引用、写覆盖）
      │ 下半场：GVN/SCCP 消除重复，BDCE/ADCE/DSE 按可观测行为与堆版本重新计算存活集
⑥    ▼
 接近最终形态：少量直线块 + 结构规整的循环骨架
      │ 模块优化：整形的那几个 pass 调整嵌套与依赖分布 → 向量化放大（只放大最终形态）→ GlobalDCE/ConstantMerge 收尾，devirt（LTO 或开关打开时）消费前奏阶段得到的候选集
⑦    ▼
 产出：向量指令、趋近于零的间接调用（或只剩少量 guard 分支）、无内存对象的 IR

读这张链的方法是从任一环向两端各问一句：它消费的上游产物由谁产生（往前一个位置），它产生的下游前提由谁消费（往后一个位置）——-O2 的全部次序就是这一套衔接；去掉任何一环，后面至少一个 pass 的合法性前提失去依据。用本文的语言说：去掉一环，就是在定理 7.4 的拓扑序里删一个节点，其后继的前提失效， $O_j$ 严格变小。

Legacy PM（Legacy Pass Manager，NPM 之前的那套 pass 调度框架）时代，这些次序散落在各个 driver 的 addPass 调用序列里；NPM 把同一条清单变成可读、可打印、可用文本复现的数据结构——框架机制本身就只有这么多（本章那个主循环就是全部）。

拝啓　今は亡き過去を想う　望郷の詩，
敬启现在正在想念逝去的过去望乡之诗，
最低な日々が　最悪な夢が，
最烂的每天跟最糟糕的梦，
始まりだったと思えば　随分遠くだ，
觉得好像才刚开始但已经成为了很遥远的过去，
どうせ花は散り　輪廻の輪に還る命，
反正花一定会凋零轮回之轮会归还生命，
苦悩にまみれて　嘆き悲しみ，
被苦恼所弥漫哀叹悲伤，
それでも途絶えぬ歌に　陽は射さずとも，
就算这样也绝不中断歌声即使太阳无法照射到，
季節は次々生き返る，
季节一个接着一个逐渐回归生气~。

—— 季節は次々死んでいく · amazarashi

Reference

源码基线

llvm-project@026e3f3c：核心文件 llvm/lib/Passes/PassBuilderPipelines.cpp 与 llvm/lib/Transforms/{Scalar,Utils,IPO,Vectorize}；文中每一处 file:line 都指向该 commit（含本章新增的引用，行号全部对照该 commit 下的文件核对过；引用的英文注释也逐条在该 commit 的原文里比对过）。
clang/lib/CodeGen/BackendUtil.cpp：PipelineTuningOptions 在 clang 侧的赋值处（:900–:908）——本文说某个 pass “默认开/关”时，指的是 opt 里 cl::opt 的 cl::init 值；走 clang 时这些值由对应的 -f… 选项覆盖，两边已分开标注。

官方文档

LangRef——T0 的语义出处：§Poison Values、§Undefined Values、§Function Attributes、§add、§Fast-Math Flags、§store/§load、§freeze；本文另外引用的几节：memory(...) 属性族（定义 0.1b）、§’llvm.loop.mustprogress’ Metadata（LoopDeletion 的边界情形）、§’llvm.lifetime.start’ Intrinsic（AlwaysInliner）、§’llvm.memset’/§’llvm.memcpy’（LoopIdiomRecognize 的替换目标）、§Conversion Operations（Float2Int）
Passes.md（按注册名分段给出权威摘要，如 licm、sccp、loop-deletion、always-inline；但覆盖不全——bdce、loop-idiom-recognition、constraint-elimination、loop-sink 这些并不在里面，本文遇到时改引源码文件头）、NewPassManager.md、WritingAnLLVMNewPMPass.md
AliasAnalysis.md（T5 的分层）、MemorySSA.md（定理 5.2 的设计文档）、LoopTerminology.md（T4 的循环术语与图示）、Vectorizers.md、Programmer’s Manual（Value/Use/User 与 RAUW）
C++ 标准工作草案：[intro.execution]（as-if rule，定义 0.1/0.1a/0.1b 的原始口径）与 [intro.progress]（前进保证，即 $\uparrow$ 那一支）

定理出处（按本文编号）

本文的定理	出处
0.2 精化、0.4 poison 可替	Vellvm, POPL 2012、Alive, PLDI 2015、Alive2, PLDI 2021
1.2 不动点	Tarski, Pacific J. Math. 1955
1.3 终止与轮数、1.5 MOP⊑MFP	Kildall, POPL 1973、Kam & Ullman, Acta Informatica 1977
1.6 SCCP 型保证	Wegman & Zadeck, TOPLAS 1991（POPL’85 版）、Callahan, Cooper & Kennedy 1986
2.1/2.7 支配树与 O(1) 查询	Lengauer & Tarjan, TOPLAS 1979；LLVM 实用的 Semi-NCA 见 GenericDomTreeConstruction.h:12 引的 Georgiadis 博士论文，增量更新见 arXiv:1604.02711
2.2 SSA 构造定理	Cytron et al., TOPLAS 1991、Sreedhar & Gao, POPL 1995、Braun et al., CC 2013
2.5 后支配与控制依赖	Ferrante, Ottenstein & Warren, TOPLAS 1987
3.0/3.0a 后序、逆后序与四种遍历序	Eli Bendersky 2015, Directed graph traversal, orderings and applications to data-flow analysis（四序对比、RPO ≠ 前序、正向用 RPO / 反向用后序、反图 RPO 与原图后序有环时不等价）；LLVM 侧 PostOrderIterator.h:290 `ReversePostOrderTraversal` 与 GraphTraits.h:109 `Inverse`
3.1/3.3 DFS、回边、SCC	Tarjan, SIAM J. Comput. 1972
4.1–4.3 SCEV 与闭式	Wolfe, PLDI 1992、Gerlek, Stoltz & Wolfe, TOPLAS 1995
4.5/4.6 依赖保持与调度	Allen & Kennedy, TOPLAS 1987、Allen, Callahan & Kennedy, POPL 1987、Feautrier, IJPP 1992 I/II、Pugh, Omega test, Supercomputing 1991
4.7 / SLP 打包	Larsen & Amarasinghe, PLDI 2000
5.2/5.3 堆版本化	MemorySSA.md（无论文，只有设计文档）
5.6 别名不可判定	Landi, ACM LOPLAS 1992
6.1/6.2 频度与期望迭代次数	Wu & Larus, MICRO 1994、Ball & Larus, TOPLAS 1994
7.2 Newman 引理	Newman, Ann. of Math. 1942
7.6 同余与值编号	Alpern, Wegman & Zadeck, POPL 1988、Click, PLDI 1995
7.3/7.4 机会算子与拓扑序	本文的抽象，无外部出处；经验事实全在 PassBuilderPipelines.cpp 的重复排布与注释里
0.1/0.1a/0.1b 事件序列	也是本文的记账口径（不是 LLVM 规范文本），口径来源为上列 as-if rule + LangRef + ModRef.h 的 MemoryEffects

其他

前置词条：支配树 / 拓扑排序 / 强连通分量 / DFS
题头歌词：境界線 (边界线) — amazarashi
题尾歌词：季節は次々死んでいく (季节接连逝去) — amazarashi
前篇：Agent原理介绍——同样是”把职责收敛到少数契约上”的框架