「现代优化 Pass 管线」

1. 优化管线结构

一句话总结： 优化管线是多个 pass 的有序组合，每个 pass 把 IR 做一次保持语义的变换，整体呈「由浅入深、再由深回浅」的节奏。

编译器优化很少是一个 pass 搞定，而是一条精心排队的流水线。-O2 对应几十个 pass，每个 pass 负责一类变换：清理简化（SimplifyCFG、InstCombine）、内联与函数属性、循环优化（LICM、unroll）、全局数据流（GVN、SCCP）、以及最后的死代码清理。Pass 之间顺序很重要：常量折叠清理掉冗余指令后，内联才更精准；内联创造了新的内联场景，往往需要再跑一轮清理。

典型 O2 管线节奏 (概念示意):
  早期清理: SimplifyCFG → InstCombine → EarlyCSE
  ↗ 函数层面: FunctionAttrs → Inline → SROA
  → 循环层面: LoopRotate → LICM → LoopUnroll → LoopVectorize
  → 全局层面: GVN → SCCP → JumpThreading
  ↘ 收尾清理: InstCombine → DCE → SimplifyCFG

# 概念: pass 是无副作用的纯函数 IR -> IR
def run_pipeline(ir, passes):
    for name, fn in passes:
        before = ir.checksum()
        ir = fn(ir)
        after = ir.checksum()
        print(f"{name}: {before} instrs -> {after} instrs")
    return ir

优化的核心不变量是「语义保持」（preserve semantics）：任何 pass 都不允许改变程序的可观察行为。每个 pass 都要处理「合法变换的条件」，例如常量折叠只有在不会改变溢出行为时合法。现代编译器用测试套件与差分测试（把原程序与优化后程序随机喂相同输入对比结果）来维护这个不变量，任何 pass 引入的回归都会被这类测试捕获。

2. 函数内联

一句话总结： 内联把调用点替换为函数体副本，消除调用开销并打开后续优化的场景，但代码膨胀让内联必须谨慎定价。

函数内联（inlining）是最重要的函数级优化：把 x = f(3) 替换成 f 的函数体（形参替换为实参）。它一举消除调用、传参、返回与寄存器保存的开销，更重要的是让调用点上下文可见——f 里对常量参数的操作因此能被常量传播捕捉。代价是代码膨胀：函数体被复制到每个调用点，内联过度会让指令缓存压力上升、编译变慢。

# 概念: 简单内联的代价模型
def inline_cost(fn, call_site):
    body_size = len(fn.body)
    call_overhead = 10            # 调用/返回的折算代价
    constant_args = sum(1 for a in call_site.args if is_const(a))
    saved = constant_args * 5     # 常量参数带来的优化收益
    return body_size - call_overhead - saved

def should_inline(fn, call_site, threshold=75):
    return inline_cost(fn, call_site) < threshold

; 内联前
define i32 @caller() {
  %r = call i32 @square(i32 5)
  ret i32 %r
}
; 内联后 (实参代入)
define i32 @caller() {
  %t = mul i32 5, 5        ; 后续常折叠成 25
  ret i32 %t
}

现代编译器在内联上投入巨大工程：代价模型要估算函数体大小、调用点收益、调用频率（PGO 下调用点有执行计数）、递归函数的深度限制、以及跨模块内联（LTO）。内联还引入了「内联缓存」概念——即便不修改源码，编译优化层也实现了类似虚拟缓存的函数分派。过度内联导致崩溃性的编译内存增长时，编译器会用「内联总是内联，但超过深度就放弃」的硬阈值兜底。

语言层面的内联提示（inline 关键字、#[inline] 属性）本质是给代价模型的建议权重：程序员对自己函数的调用频率与收益有额外知识，编译器据此调整阈值。但编译器保留最终裁决权——声明 inline 只是「希望内联」，真正是否内联仍由代价模型决定。递归函数不能直接内联自身，编译器靠「部分内联」把递归体展开一层（fib(n) 内联出 fib(n-1) 的调用），把单层开销摊平，配合尾递归优化减少栈帧。

def inline_recursion_depth(fn, call_site, depth=3):
    if fn.is_recursive and call_site.depth >= depth:
        return False                 # 递归超深, 放弃
    return inline_cost(fn, call_site) < 75

3. 循环优化

一句话总结： 循环占据程序运行时的大部分，循环不变量外提、强度削减、展开与向量化共同把循环压到最低成本。

循环优化是优化器的「利润中心」。循环不变量外提（LICM）把循环体内不变的计算移到循环前；强度削减（strength reduction）把乘法换成加法（i*4 变成累加步长 4）；循环展开（unrolling）复制多份循环体减少分支判断与跳转；循环旋转（rotation）把 while 改成 do-while 让回边更可预测。这些变换在 SSA 与支配树上都有成熟算法。

# LICM 概念实现: 找到不随迭代变化的计算并外提
def licm(loop_body, loop_headers):
    hoisted = []
    for instr in loop_body:
        if not depends_on_loop_vars(instr, loop_headers):
            hoisted.append(instr)      # 移到循环前
            loop_body.remove(instr)
    return hoisted

# 强度削减: i*4 -> 累加步长
def strength_reduce(loop):
    if loop.has_induction("i") and loop.has_mul("i", 4):
        loop.replace_mul_with_accumulator("i", 4)

识别归纳变量是循环优化的基础设施：归纳变量是每轮迭代按固定增量变化的变量（for i in range(0, N, 2) 的 i），围绕它编译器能推导出每轮迭代的表达式、判断循环是否可展开、可向量化、可交换。下面的代码示意了归纳变量的识别与据此生成展开后的循环体。

def detect_induction_vars(loop):
    # 形如 i = i + step 的循环内赋值
    inductions = []
    for instr in loop.body:
        if (instr.op == "add" and instr.left == instr.var
                and is_const(instr.right)):
            inductions.append((instr.var, instr.right))
    return inductions

def unroll(loop, factor=4):
    ivs = detect_induction_vars(loop)
    if not ivs:
        return loop                     # 非规整循环不展开
    step = ivs[0][1]
    # 生成 factor 份循环体副本, 步长乘 factor
    new_step = step * factor
    return loop.rewrite(step=new_step,
                        body=loop.body * factor)

循环展开还有个关键权衡：展开 4 份减少 3/4 的分支与回跳，但增加指令缓存压力；配合 PGO 的执行计数可以决定哪些热循环值得展开。循环还有更高级的变换：循环交换（loop interchange）以改善缓存局部性、循环分块（blocking/tiling）用于矩阵类代码、循环融合与分裂。所有这些变换都以循环不变量与归纳变量（induction variable）分析为基础，因此先把「识别归纳变量」做好再谈其他。循环分块的经典场景是矩阵乘法：把大矩阵切成适配 L1/L2 缓存的小块，让内层循环的重用全部命中缓存，三层循环加一个分块维度后性能常可提升数倍。

4. 向量化

一句话总结： 向量化把标量循环改写成 SIMD 指令一次处理多个元素，是吞吐型代码最大的性能来源之一。

现代 CPU 有 SIMD 指令（x86 的 SSE/AVX、ARM 的 NEON/SVE）能一次处理 4/8/16 个元素。向量化（vectorization）分析循环的迭代之间是否有数据依赖，若无依赖则把标量操作改写成向量操作。例如 for i: a[i] = b[i] * c[i] 可改成一次 _mm256_mul_ps 处理 8 个 float。自动向量化依赖别名分析证明内存访问不冲突，否则必须保持串行语义。

# 概念: 检测可向量化循环 (无跨迭代依赖)
def is_vectorizable(loop):
    writes = {stmt.target for stmt in loop.body}
    reads = {src for stmt in loop.body for src in stmt.sources}
    # 每次迭代只写自己的槽位, 且不读未来槽位
    return writes.isdisjoint(reads) and \
           all(is_affine_index(w) for w in writes)

# 循环改写为宽操作
def vectorize(loop, width=8):
    if is_vectorizable(loop):
        return loop.rewrite(f"for chunk in range(0, N, {width}): "
                            f"  wide_op(chunk)")

; 向量化前后对比 (x86-64 AVX, 示意)
; 标量
loop:
  vmovss (%rsi,%rcx,4), %xmm0
  vmulss (%rdx,%rcx,4), %xmm0, %xmm0
  vmovss %xmm0, (%rdi,%rcx,4)
  addq $1, %rcx
; 向量化后 (一次 8 个 float)
  vmovups (%rsi,%rcx,4), %ymm0
  vmulps (%rdx,%rcx,4), %ymm0, %ymm0
  vmovups %ymm0, (%rdi,%rcx,4)

自动向量化的难点在依赖分析：指针别名（a 与 b 是否重叠）、归约操作（sum += a[i] 可向量化但需特殊处理）、条件分支与 gather/scatter 非连续访问。编译器常用「版本化」策略：运行时检查指针是否重叠，若安全则走向量化版本，否则回退标量版本。SVE 等可变宽向量架构还引入了向量长度无关（VL-dependent）的循环形式，进一步放宽了对固定宽度的依赖。

5. 常量传播与 SSA

一句话总结： SSA 让常量传播变成图上的数据流问题，稀疏条件常量传播在分支上同时推理可达性，配合 phi 实现精确传播。

常量传播（constant propagation）把已知常量的变量在后续使用处替换成字面量，常与常量折叠（constant folding）配合：x = 3 之后 x + 1 变成 3 + 1 再折叠成 4。SSA 让这个问题优雅起来——每个使用点只有一个定义，传播就是沿 def-use 链把常量值前向传播。稀疏条件常量传播（SCCP）更进一步：它还跟踪基本块可达性，把「未被执行的块」里的定义也考虑进去，得到更精确的常量集。

# 概念: SSA 上的常量传播 (简化)
def sccp(ir):
    value = {}                     # 变量 -> 常量或 TOP/BOTTOM
    for instr in ir:
        if is_const_def(instr):
            value[instr.name] = instr.const
        else:
            # 所有操作数都是常量才折叠
            if all(is_const(value.get(use))
                   for use in instr.uses):
                value[instr.name] = fold(instr, value)
            else:
                value[instr.name] = BOTTOM
    return {v: c for v, c in value.items() if is_const(c)}

; 传播前
%a = 5
%b = add i32 %a, 2
; 传播 + 折叠后
%b = 7

格（lattice）分析把每个变量映射到 TOP（未知）、常量、BOTTOM（不可常量）三态，迭代至不动点。SCCP 之所以是编译器教科书常客，是因为它把「可达性」与「常量性」两个问题放进同一个不动点循环里，能同时消除不可达代码。工程实现里 SCCP 常与 GVN（全局值编号）共享分析基础设施，两者都依赖支配树与 SSA 边的高效遍历。

GVN（全局值编号）与常量传播互补：它识别「计算相同值的不同指令」，把重复计算合并成一条。例如两条独立的指令分别计算 a + b，只要中间没有任何对 a 或 b 的修改，编译器就让第二条直接复用第一条的结果。在 SSA 形式下，值编号可以做到相当彻底，配合内存 SSA（memory SSA）还能追踪存储之间的冗余。

def gvn(ir):
    value_table = {}                  # (op, operands) -> result
    for instr in ir:
        key = (instr.op, tuple(instr.uses))
        if key in value_table:
            instr.replace_all_uses(value_table[key])
        else:
            value_table[key] = instr.name
    return ir

常量传播与值编号联动的经典效果：x = 4; y = x + 1 先传播成 y = 4 + 1，再折叠成 y = 5，若随后 z = y 还能被值编号识别为同一常量。这类「传播-折叠-复用」的级联正是优化器里收益最直观的部分，也是为什么流水线总把清理 pass 放在最后——把前面所有 pass 制造出的冗余一次性收干净。

6. Profile-Guided 优化 (PGO)

一句话总结： PGO 用真实运行数据标注分支频率与热函数，让优化器把力气花在最常执行的路径上。

静态优化无法知道「哪个分支常走、哪个函数热」。Profile-Guided Optimization（PGO，也叫 FDO）解决这个问题：先用插桩版本的程序跑代表性负载，收集执行计数（哪个基本块执行了多少次、哪条边被走多少次、哪个函数被调用多少回），再用这些计数指导优化决策。内联只内联热函数、循环按热程度展开、分支按概率重排以提高取指与分支预测命中。

# clang PGO 三阶段流程
clang -fprofile-instr-generate prog.c -o prog.prof
./prog.prof < representative_inputs     # 收集 profile
llvm-profdata merge -output=prog.profdata default.profraw
clang -fprofile-instr-use=prog.profdata prog.c -O2 -o prog

# 概念: 用 profile 计数指导内联
def pgo_inline_decision(fn, call_site, profile):
    call_count = profile.calls[call_site.id]
    body_size = len(fn.body)
    # 热调用点即使函数稍大也内联
    return body_size < 80 or call_count > 100_000

PGO 的工程难点是数据代表性：如果训练负载与真实负载不符，优化方向会错。编译器界因此演进出多种补充：AutoFDO 用硬件采样事件（如分支采样）免插桩、BOLT 对二进制直接做 PGO 化后处理、以及增量 PGO 与薄插桩。PGO 与 LTO 叠加是现代分发构建（如 Chrome、服务器二进制）的标配，但也要注意构建矩阵膨胀——每套优化目标需要一套对应的 profile。

7. Pass 调度与收敛

一句话总结： Pass 之间相互创造新优化机会，编译器需要迭代运行与收敛检测，Pass Manager 负责调度、缓存分析并保证终止。

一个 pass 的输出可能开启另一个 pass 的新机会：内联后产生常量参数，常量传播折叠出新的冗余，死代码消除清掉后又有新的简化机会。因此优化管线要「迭代到收敛」：同一批 pass 反复运行直到不再产生变换，或者达到最大轮数。收敛检测靠「IR 是否发生变化」的标记，LLVM 里 PassManager 会在一次 pass 报告修改后安排后续依赖 pass 重跑。

class ConvergentPipeline:
    def __init__(self, passes, max_rounds=8):
        self.passes = passes
        self.max_rounds = max_rounds

    def run(self, ir):
        for round_no in range(self.max_rounds):
            changed = False
            for name, fn in self.passes:
                ir, did = fn(ir)
                changed = changed or did
            if not changed:
                break                # 收敛
        return ir

Pass 调度与收敛的平衡点是编译时间：迭代太多会拖慢构建，太少会漏掉优化。现代编译器用分层策略——-O1 一轮清理、-O2 中循环与全局优化各几轮、-O3 再开向量化与更多循环变换；-Oz 牺牲速度换体积。Pass Manager 的可缓存分析（支配树、loop info）与 invalidation 追踪让调度在正确的前提下尽量快，这也是新 Pass Manager 相比旧实现的重要工程进步。

8. 总结

一句话总结： 现代优化管线靠有序、迭代的 pass 组合把 IR 不断变好，内联、循环、向量化、常量传播与 PGO 各司其职，收敛与调度则约束编译时间。

优化器的本质是在「代码大小、编译时间、运行速度」三个目标之间寻找平衡，而 PGO 与 LTO 把这种平衡从「静态猜测」升级为「实测数据驱动」。理解 pass 管线不是要求亲手实现每个算法，而是建立对变换之间相互作用的直觉：为什么内联要在常量传播前、为什么循环优化要依赖支配树、为什么向量化要证明无别名。这份直觉是读任何编译器日志、调任何构建优化参数的基础。

延伸阅读

• 词法分析器实现
• 语义分析与中间表示
• 中间代码优化
• 目标代码生成
• 解释器与 JIT 编译