很多年前第一次在编译实验里跑优化通道的时候我一个很直观的感受是真正让中间代码变“干净”的往往不是那些看起来高大上的循环变换和向量化而是最不起眼的复制传播、常数折叠、常数传播。这三个优化在教科书里挤在一节经常被一笔带过可到了工程里它们才是前期优化的主力。所谓“前期优化”就是编译器把源代码翻译成中间表示IR之后、进入指令选择之前的那一票优化。这个阶段的特点是IR足够低层、能暴露很多冗余信息但又足够高层、还能保留一些语义细节。这篇文章我打算按三条主线展开先讲清楚这三个优化到底在解决什么、为什么它们必须捆绑在一起做然后分别拆解每个优化的实现原理、触发条件和边界问题最后把我实际调试编译工具链时踩过的坑和排查思路整理出来。如果你是在做编译器课程设计或者自己撸一个玩具编译器又或者在给某个开源编译框架写优化通道这篇文章可以直接当参考手册用。1. 前期优化三件套它们到底在解决什么问题1.1 从一棵“很笨”的树到一个“好用”的图前端把源代码变成IR之后IR里最典型的特点就是冗余特别多。为什么因为前端是递归下降或语法分析驱动的它一条条翻译语句时根本不会去考虑“这个临时变量是不是多余的”“这个表达式是不是已经有确定值了”。举个例子源代码里写一段int b 5; int c b 3; int d c * 2;前端翻译成三地址码之后可能长成这样t1 5 b t1 t2 b 3 c t2 t3 c * 2 d t3中间出现了大量的临时变量t1、t2、t3而这些临时变量的存在并没有带来任何抽象价值纯粹是翻译过程的副产物。如果后端直接拿这份IR去生成汇编轻则生成一堆mov指令做毫无意义的搬运重则让寄存器分配策略被这些临时变量干扰导致原有的活跃变量分析、指令调度等后续优化全部变差。这里就引出了“优化”的核心思路与其等后端去处理这些垃圾不如在前期就把它们处理掉。复制传播能直接把b t1这种复制关系传递给所有用到b的地方常数传播能进一步把b替换为已知的5常数折叠则能把5 3直接算成8。1.2 为什么必须是“组合拳”很多初学者会问一个问题只做常数折叠不就行了吗把5 3算成8把8 * 2算成16问题不就解决了吗现实很简单折叠要触发前提是操作数已经是常量。在上述例子中b 3的操作数b虽然是由5赋值的但如果不先把5传播到b折叠引擎看到的只是一个“符号变量”b加上常量3它没办法直接下结论。这就是为什么三个优化必须来回迭代折叠产生新的常量常量通过传播流入新的使用点又触发更多折叠。打个比方这三者就像一个清洗流水线复制传播负责清除无效的搬运动作常数传播负责把常量身份带到所有“疑似非常量”的变量上常数折叠负责在拿到两个常量时立刻做算术、缩短表达式。少任何一个环节另外两个的效果都会大打折扣。1.3 在SSA形式下做这件事事半功倍想深入理解这些优化绕不开一个前提它们几乎都是在SSA静态单赋值形式下实现的。SSA的核心思想是每个变量只被赋值一次即一个变量名代表程序中一个唯一的定义点而具体的赋值路径靠phi指令合并。为什么SSA对此如此重要在没有SSA的IR里一个变量可能被多处赋值你看到一个x的使用点要去查“当前生效的定义是哪个”必须做经典的数据流分析考虑控制流路径比较麻烦。SSA把这事变成了一个局部事务x的定义是唯一的所有能到达这个定义的x使用点都在它的支配范围内。这样一来复制传播和常数传播都可以实现为非常轻量的“定义到使用的替换操作”算法复杂度大大降低正确性分析也简单得多。如果哪天你要给一个非SSA的IR写优化我会强烈建议你先想办法把IR转换成SSA或至少做个静态单次赋值否则下面是相当容易踩坑的。2. 复制传播把没意义的“中间手”直接砍掉2.1 基本规则与一个直觉例子复制传播针对的模式是t1 5 b t1后一条指令b t1俗称“拷贝指令”copy它做的事情就是把t1的值原封不动搬给b中间没有任何计算。复制传播要做的事情很简单遇到一条x y形式的指令在保证安全的前提下把所有后续用到x的地方替换成y然后删除这条拷贝指令。来看一个直观例子t1 5 b t1 t2 b 3复制传播之后变成t1 5 b t1 t2 t1 3 ; 将所有 b 替换为 t1随后常数传播发现t1 5又可以把t2 5 3传给折叠引擎最终变成t2 8。这里要注意一个细节复制传播本身不删除b t1这条拷贝指令。删不删取决于死代码消除DCE是否认为b已经不再被使用。实际工程里常见的组合是“复制传播–死代码消除”一起跑传播之后那种拷贝指令的右侧变量如果没有任何合法使用了DCE就会把它删掉。教材里常常把“复制传播”和“死代码消除”分成两章讲但工程上的心智模型应该是它们是天然的搭档。2.2 正确性条件什么时候不能传播复制传播看起来简单但踩坑点在于“什么时候不能传播”。核心原则是替换后不能改变程序的可观察行为。下面几种情况必须谨慎。第一种是volatile变量。如果一个变量被声明为 volatile它的读写都是有副作用的不能随便用一个普通变量替换它因为那会丢掉读取的原子语义或者I/O映射关系。这条在写编译实验时经常被忽略但在真实工具链里几乎每个优化通道开头都会做isVolatile()检查。第二种是指针别名场景。假设x y p x z *p如果x是某块内存的指针且此后有人通过指针修改了它指向的内存那x的值就未必还等于y了。所以复制传播在遇到可能被别名分析影响的内存操作时必须格外谨慎。在SSA形式下如果一个变量是“地址相关”的取了地址通常优化器会退缩或者只在别名分析确认安全时才传播。第三种是逃逸分析失败的场景。如果一个变量被传入函数调用且函数可能修改它你不能假定其在调用点之后仍然等于原先的拷贝源。我的建议是初版实现里宁可保守也不要激进。只对“显然不取址、非volatile、无调用穿越”的局部临时变量做复制传播命中率已经很高而且不会出恶性bug。等后续有精力再加别名分析来放宽限制。2.3 实现路径与算法骨架在SSA的IR里复制传播可以做得非常轻量常见方式有两种。第一种是“使用点替换法”遍历所有指令如果发现某条拷贝指令x y就维护一个映射map[x] y然后遍历x的所有使用点把参数从x替换成y。替换过程中需要注意到x可能又出现在另一条拷贝指令的右侧这时要传递替换比如a bb c则在处理a的使用点时要顺着链到达最终的源头c。链可能很长需要自己做路径压缩避免递归爆栈。第二种是“全局数据流法”把“到达赋值”看作一个数据流信息通过基本块之间的迭代传播在每条使用点找到当时的可达拷贝对集合。这个方法更全面但实现量更大。工程里如果目标是前期快速清一批冗余用第一种“SSA 使用点替换”就够了我实测在普通规模的IR上性能完全不是瓶颈。节点处理顺序上有一点经验先处理小块内的拷贝再进行跨块传播。块内处理简单、安全性高跨块传播需要判断路径活跃性否则容易引入“不该有的替换”。做跨块传播时最好结合“支配边界”的概念判断某条拷贝指令是否在目标使用点的支配路径上。2.4 复制传播为什么能“放长线”复制传播单独看收益似乎只是少了一条搬运指令但它在优化链中的价值不仅于此。一个典型的“放大效应”是它会为后续的强度削减、公共子表达式消除打开局面。比如数组访问计算arr[i]前端可能生成t1 i t2 t1 * 4 t3 base t2如果没有复制传播i和t1同时存在公共子表达式检测时可能因为名字不同而无法合并。一旦把t1的使用点替换成i后续的公共子表达式分析就会发现这两个表达式形式一致进一步合并计算。这就是为什么很多优化通道跑完一轮复制传播后再跑一轮公共子表达式消除IR的简化会突然“跃迁”一大步。3. 常数折叠干活最直接的“计算器”3.1 折叠的边界能算的和不能算的常数折叠的意义一句话就能概括在编译期把能够确定的算术结果算出来省掉运行期的一次计算。比如3 4直接变成72 * 2 * 2直接变成8数组下标a[CONST]里的计算也可以提前完成。但“能够确定”这四个字里藏着无数边界。最经典的边界是整型溢出。以C/C为例int x INT_MAX 1; // 未定义行为如果把INT_MAX 1折叠成一个很大的负数虽然在大多数机器上行为一致但严格来说这是在“把未定义行为合法化”。更麻烦的是有些编译器在-fwrapv下允许有符号整型环绕另一些则明确禁止。你的折叠逻辑必须和语言语义保持严格一致否则就是给用户埋雷。同样的问题还出现在除法模零1 / 01 % 0这类表达式不能折叠因为语义上它会触发异常而不是返回某个数。浮点运算0.1 0.2折叠后可能因为舍入产生微小的精度差异。你做折叠时最好遵循“按目标机器舍入语义”的约定通常通过roundToFloat之类的精度转换来控制。指针运算两个指针相减、非法对齐等如果折叠会破坏语义就不做。折叠面积的另一个边界是溢出检测的显式处理。某些语言比如带溢出检查的方言要求运行时捕获溢出异常那么INT_MAX 1就不能折叠成普通常量而是要保留为“可能触发异常”的运算。折叠器必须先询问后端“整型溢出是否允许静默环绕”再决定能不能折叠。3.2 折叠规则不仅仅是加减乘除教科书里常说的折叠规则包括交换律、结合律、分配律、吸收律等等工程实现里其实是一张大表。举几个常用但经常被忽略的例子0 x → x、x - 0 → x、x * 1 → xx 0需要检查浮点-0.0的特殊性按IEEE754-0.0 0.0的结果是0.0在某些依赖符号位语义的场合不能直接替换为x。真做全语义的折叠时连零元规则都要分情况讨论。x * 0 → 0同样如果x是浮点且是 NaN 或者无穷大NaN * 0会得到 NaN 而不是0所以这条规则在浮点上其实不永远成立。!(x false)之类的布尔折叠实际上发生在更高层的表达式树里但常数折叠器通常也会做。我不是在吓唬你而是想说折叠器不是单纯背个“简化表”就能做对的东西尾数、NaN、无穷大、符号零这些浮点边角在真实工具链里引发过无数轮bug。如果你只写课程实验建议把浮点折叠保守化只折叠那些所有舍入模式结果一致的场景即使丢一些优化机会也比搞出错误结果强。3.3 折叠何时触发不是所有常量表达式都可见很多初学者以为常数折叠就是把整个表达式树“拍扁”但IR是线性指令序列折叠面对的经常是分散的临时变量。比如t1 4 t2 5 t3 t1 * t2如果不先做常数传播折叠器在t3这条指令上看到的是t1 * t2而不是常量的*它根本无从折叠。除非你在同一条指令里做了谓词“如果操作数都是ConstantInt则计算结果”否则折叠永远依赖外部把常量身份“洗”出来。所以优化通道的调度顺序通常是这样先跑常数传播把常量值传播出去再跑常数折叠把所有常量表达式算掉再跑死代码消除把没用的赋值删掉。这种循环来回几轮后IR就慢慢变干净了。我在实际写优化通道时常常把这个循环做两次第一轮负责建立常量身份第二轮负责清掉那些第一轮才刚暴露出来的新机会。另外一个工程经验是折叠要做成“即时折叠”的形式。也就是说当优化器修改一条指令时马上尝试对它的操作数进行折叠能折就折。这样能在局部把所有新产生的常量组合立刻消耗掉避免留下“理论上该被折叠但没人去触发”的半成品IR。4. 常数传播把常量身份“洗白”到每一个角落4.1 最简单的形式单一赋值链上的传播常数传播的任务是当知道某变量一定是某个常量时把这个常量替换到它的所有使用点。它在SSA里有一个非常简洁的表述对于一条形如x CONSTANT的定义指令如果x的定义不会被任何 phi 或其他赋值覆盖那么x的使用点就可以直接替换为这个常量。在无SSA的IR里这条规则会很快崩塌因为两条不同的赋值路径可能给x带去不同的值。假设if (cond) x 1; else x 2; print(x);在非SSA形式下x在使用点有两种可能值你不能直接传播单个常量。但SSA会把x分叉成x1和x2并在汇聚点插入x3 phi(x1, x2)。常数传播看到的则是 phi 节点判断“phi 的两个入参是否都指向同一个常量”。如果都是常量且相等则 phi 也能折叠成常量如果一个入参非常量则 phi 不可传播。这个现象很重要常数传播的本质工作其实有一半是在处理phi节点。4.2 Sparse Conditional Constant Propagation稀疏条件常数传播LLVM优化家族里有个更高级的算法叫Sparse Conditional Constant Propagation简称SCCP。它的核心思想比普通常数传播多做一步把“分支条件为常量时不可达块”也纳入考虑。普通常数传播不管控制流它对所有基本块一视同仁地传播。而SCCP会先给每条边和每个块作“可达性”标记。举个例子if (x 1) { y x 1; if (y 3) { thing(); } } else { y x 2; }如果x 1则y 2第二层条件y 3恒为假那么thing()所在的整块代码根本是死代码。SCCP能发现这条死代码并把它标记掉后面的死代码消除再把这块物理删除。这是“常数传播”从“值替换”走向“控制流简化”的关键跃迁。教科书的经典伪代码是这样一张工作队列表每条指令有PUSH(工作队列)、visitPhi、visitInstruction等函数。每个变量有一个格值lattice valueUndef未定义、Constant已知常量、Overdefined非恒定。开始时大部分变量都是Undef当发现一个常量赋值时入队它的所有使用点。如果一个变量的定义者被赋了两个不同常量则格值升级为Overdefined并退役它的一切悲观传播。要注意Undef和Overdefined的区别是常数传播实现里最容易犯迷糊的地方。Undef不代表“未知”它代表“编译器还没有看到定义”这时传播者可以做乐观假设一旦确认有冲突定义立刻降级为Overdefined所有依赖它的结点都必须回退。实现上常用“格”这个偏序结构来显式表达这种升级/降级。4.3 一个多路径案例的完整推演我想用一个更复杂的例子来展示常数传播的完整过程。设中间IR为entry: x 1 if (cond) goto L1 else goto L2 L1: a 2 goto join L2: a 3 goto join join: b phi(a, a) // 这里两个入参的名字可能相同但语义不同 c x b第一步传播器发现x 1把x标为Constant(1)。第二步a在L1和L2分别被赋2和3所以phi节点入参不是同一个常量b : phi(a, a)保持Overdefined。第三步c x b因为b不可常数化c也保持Overdefined传播终止。如果改成两个分支都给a赋2那么phi的两个入参都是常量2phi折叠为2于是c 1 2折叠为3。这就是常数传播和折叠在跨块场景下的协同方式。4.4 传播的副作用问题越过函数调用怎么办在真实程序里变量很少从头到尾都没有函数调用。如果常数传播碰到一个调用x 5 foo() y x 1除非foo()不可能修改x否则不能假定y 6。这在经典SSA里会自动规避如果函数可能修改xSSA会产生一个新的变量xy的使用点引用的是x而不是原始的x。但前提是你做了内存SSA或在做别名分析。如果你只是做了“普通SSA”而x的地址曾逃逸foo()确实能通过指针改写那块内存那么x虽然存在但其值不一定为5。所以常数传播实现里一定有一道检查变量定义是否“可精确表示”。该检查通常结合了取址分析、别名分析和调用点分析。如果发现某个变量被取址且地址逃逸直接把它标记为Overdefined别传了。宁可损失优化机会也不能编造一个不存在的常量。5. 实操中常见的坑与排查技巧5.1 折叠后“常量库”里出现奇怪值有同学跑优化时发现折叠完之后IR里出现了i64的常数像18446744073709551615看起来莫名其妙。这通常不是bug而是因为-1被按无符号数存储了。IR层的常量通常有类型和宽度信息打印时可能用无符号格式。这时不要慌查一下原始类型和操作行为是否一致。真正的坑是如果上下文操作符是“逻辑右移”但你的折叠代码误用了“算术右移”的C运算符结果就会莫名其妙差出一个符号扩展开来。这类问题调试时很难察因为不是每个常量都会触发。我的习惯是给折叠器写一组基于已知输入的单元测试覆盖INT_MIN / -1、-1 1、0 - INT_MIN等边界案例每次改动之前先跑这组测试。5.2 传播过程中常量身份丢失常见表现是IR里明明有x 5后面也有y x 1但传播器没有把x传给y。排查思路依次是看看x是不是被取址了。如果是传播器会主动放弃。看看x的定义指令是否在另一个基本块里而y所在块不受该定义支配。看看x是否被phi合并过合并后格值已经变成Overdefined。看看是否有内联函数调用、异常路径等隐式控制流阻断了传播。有一个技巧把优化器内部打印Ctx-getValue(x)或LatticeVal的输出打开对照数据流表看变量状态。如果是跨块问题基本上一眼就能看出是哪个桥断了。5.3 顺序依赖问题为什么跑了两轮效果才好我第一次给某工具链写优化通道时只跑了一轮“复制传播→常数折叠→常数传播”结果优化完IR还是有很多冗余。后来发现问题是常数传播先把一个常量传到了拷贝指令的另一侧生成了新的拷贝模式但复制传播在第一轮已经跑完了触发不到这个新模式。第二轮复制传播才把它砍掉。这个现象在优化器里太常见了——所谓“优化是迭代式波浪前进的”几乎每一种优化都能为其他优化解锁新机会。实际工程里大部分编译器会跑多轮“简化”通道每轮内部按照同样的顺序执行一组小优化。如果你写的优化器优化效果不好别急着改算法先试试把整组优化循环个三次往往收益比你想的大。5.4 与“死代码消除”合作的坑复制传播和常数传播之后大量原本活跃的变量突然失去所有使用点。这时候如果DCE不跟上IR里就会留着一些无用的常量赋值和拷贝指令代码体积乖乖地没有变小。常见编排错误是先跑DCE再跑传播。跑完传播后DCE没有机会清理新增的死代码。正确做法是传播和折叠之后立刻接DCE一轮净化结束再评估要不要再来一轮。DCE本身也会反过来为传播创造条件死块没删掉时一些常量路径被伪装成“可能执行”的分支导致传播器不敢下结论。所以它们的先后顺序解释成“相辅相成”比“先后承接”更贴切。5.5 性能问题传播太慢常数传播如果实现成了“每条指令都反复扫描一遍所有使用点”的朴素版本稍微大一点的IR就会慢到让人怀疑人生。我见过一个实验版优化通道在中等规模的中间代码集上跑一次常数传播要好几秒。两种加速思路一用工作队列算法。只有定义发生变化时才把它的使用点加入队列每次只处理队列里的点。二对use-def链建立索引不要每次遍历全IR来查找使用点。在SSA下Use–Def链本身就是现成的利用那个列表即可把复杂度降到接近 O(边数)。如果传播过程中有大量的phi需要反复判断可以考虑给phi加一个上游状态缓存。工程上还有一套近似技巧先做一次局部块内的快速传播爆发机会最大的一部分直接被消化再做全局传播时工作集小很多。5.6 快速问题速查表现象常见原因优先排查方向折叠结果数值异常符号/无符号语义处理错误检查常量存储类型、溢出标志传播不触发变量被取址/逃逸检查别名分析和SSA变量替换传播后产生大量死代码DCE未及时运行调整优化通道调度顺序跨块传播出错误phi合并导致格值升级查看phi入参是否被正确合并浮点折叠后结果和运行时不符舍入模式/NaN/Inf边界保守化浮点折叠策略优化速度慢朴素全量扫描改用工作队列 use-def索引这个表是给调试期用的非常直白。实际工具链里可能遇到的是这六种问题的组合版本那就按顺序拆开排查把控制变量隔离掉再定位。6. 后面还能怎么玩这三个优化做完之后很多更进阶的优化机会其实已经暴露出来了常量数组的索引静态化简、基于常量的循环边界分析、分支条件的常量推断等等。我记得自己后来做的一个性能优化任务里先靠这三件套把函数内复制的元素个数传成了一个常量才让向量化的通道有机会生成一次拷16字节的紧致循环。那种“前面帮后面清路”的连锁反应是编译器优化里最有成就感的时刻。如果这篇文章对你有帮助建议你把示例IR亲手放进自己的优化实验里跑一遍看看每一轮传播之后打印出来的IR长什么样。亲手观察过一遍“冗余如何被逐步消除”比看十篇文章都管用。