★ FEATURED ARTICLE 做编译器后端优化的时候最让我头疼的一类问题不是算法本身多复杂而是明明寄存器分配器写得没问题出来的代码却总在一些很普通的局部变量上疯狂溢出。后来反复定位才发现真正卡住分配器的不是寄存器数量而是变量的“活跃范围”被表达得太长了。一个只在一个循环片段里用到的值硬是从循环入口活到函数返回把一整片寄存器堵得死死的。把这个范围重写掉代码性能立刻上了一个台阶。“活跃范围重写Live Range Rewriting”这个技术简单说就是改变变量在程序中的生存区间让它在寄存器分配、指令调度这些下游阶段里表现得更加友好。它不是一条具体的优化指令而是一整套关于“如何重新切分、合并、迁移变量生命周期”的思路。对于正在写编译器、做静态分析、或者研究程序优化的人来说它是理解寄存器分配和中间表示设计之间关系的关键一环。这篇文章我会从活跃范围的定义和数据流基础讲起再展开到寄存器分配里最常遇到的冲突与溢出然后落到实际工程中可以操作的切分流程与启发式策略最后把我踩过的坑和排查经验一并整理出来。尽量讲得接地气不绕弯子。1. 活跃范围到底是什么从变量生命周期说起1.1 活跃范围的定义与直观理解说得直白一点一个变量从被赋值def开始到它最后一次被读取use为止这段区间就是它的活跃范围。在这个区间内的任意一个程序点这个变量的值都可能在下游被用到所以它必须被保留下来至少要保证后续能读到正确值。举个例子函数里有一个循环for (i 0; i n; i) { sum a[i] * b[i]; }变量sum在循环之前初始化在循环体里被反复读取和更新。它的活跃范围几乎覆盖整个循环。如果这个函数还有其他变量在循环体里同时活跃那么sum就必须和它们在寄存器分配层面“抢地盘”。更麻烦的是如果sum在循环结束后还要用那它的活跃范围会一直延伸到函数末尾。有人可能会问这个范围是死的吗并不是。我们完全可以通过改写代码把一个逻辑变量拆成多个物理上不同的临时变量让它们在时间上错开。这样一来原本一个很长的活跃范围就变成了多段短范围每一段都可以用不同的寄存器交错使用同一个物理寄存器也没问题。这就是活跃范围重写最核心的动作之一把“一个长命变量”变成“多个短命变量”然后让寄存器分配器对这些短范围分别做决定。1.2 为什么活跃范围过长会成为优化瓶颈活跃范围过长带来的直接后果就是寄存器压力过高。现代处理器能用的通用寄存器通常也就十几个而程序里同时活跃的变量数量很容易超过这个数。当冲突程度超过物理寄存器数量时分配器只能选择把一部分变量放到内存栈上也就是“溢出”。溢出是有代价的每次读写这个变量都会产生一次访存。如果是循环体里高频使用的变量这个代价就非常感人。更重要的是一个长活跃范围会和其他变量形成大量冲突边。冲突图interference graph里的边越多着色分配的难度越大到最后几乎只能靠启发式硬推。与其事后这样硬推不如在寄存器分配之前主动对活跃范围做一次“修剪”和“重排”让冲突图变干净。我在实际项目里遇到过一种很典型的反例一个变量只在非常局部的计算里用到却因为代码生成阶段把它的存储位置和另一个长命变量的存储位置合并比如复用了同一个寄存器变量导致它不得不跟着一起在被占用期间溢出。这种情况如果不做活跃范围重写几乎无解。1.3 活跃范围的计算基础数据流分析里的活变量要重写活跃范围首先得知道原本的活跃范围长什么样。这个在编译原理里叫“活变量分析”live variable analysis属于后向数据流分析。基本规则是这样的入口处活跃变量 本条语句中引用的变量 ∪ 出口处活跃变量 − 本条语句中定义的变量出口处活跃变量 所有后继基本块入口处活跃变量的并集用伪代码表达对于每个基本块 Bin[B] use[B] ∪ (out[B] − def[B]) out[B] ∪_{S in succ[B]} in[S]然后从函数的最末端开始反复迭代直到收敛。use[B]是在 B 中被读取但未在 B 中定义的变量集合def[B]是在 B 中被定义的变量集合。这套计算得到的in[B]和out[B]就刻画了每个基本块边界上哪些变量是活跃的。寄存器分配器会进一步把这些边界信息转换成每个指令位置的活跃状态然后计算出完整冲突关系。我建议所有想做活跃范围优化的同学先把这一步做扎实。因为后面所有的重写方案不管是你自己设计还是依赖框架的能力都需要准确判断“这个变量在某个程序点上到底还活不活”。判断一错很容易引入错误。2. 活跃范围重写的目标寄存器分配的胜负手2.1 寄存器分配器里的冲突图与着色经典寄存器分配流程是把每个变量的活跃范围视为一个节点两个范围如果有重叠就在它们之间连一条干涉边。之后的问题变成了用 K 种颜色物理寄存器给所有节点染色使得相邻节点颜色不同。这就是图着色问题。K 通常是个固定值由目标机器的寄存器数量决定。如果图着色失败就说明某些节点的邻居太多超过了 K必须把其中一些节点溢出到内存。但这里有个容易被忽略的细节溢出选择的不是“变量”而是“活跃范围”。如果我们已经把变量拆分成多段范围那么溢出的粒度也会变细。可以在循环外保留一个变量在寄存器里而在循环内给另一个分段分配不同寄存器甚至让这段范围直接重新计算。这就是活跃范围重写给寄存器分配器带来的自由度它不是改变 K而是改变冲突图的结构让着色问题从“不可能”变成“可能”。2.2 Live Range Splitting把一段长命变量拆成多段最常见的重写形式是“活跃范围拆分”Live Range Splitting。做法是选定一个程序点 p把变量 v 的活跃范围在 p 点切开变成 v1 和 v2 两段。v1 在 p 点之前使用v2 在 p 点之后使用。为了保持语义正确需要在切分点把 v1 的值复制给 v2。听起来简单但切在哪里是关键。切分点选得不好不光不能解决冲突还会引入大量额外的复制指令得不偿失。我比较常用的启发式是“按循环边界切”。变量在循环内被高频使用却因为循环外某一段代码的干扰而不得不溢出时就在循环入口处切一刀原始活跃范围|----------- L -----------| 循环入口切分后|-- L1 --|复制|-- L2 --|L1 覆盖循环外的前段L2 覆盖循环内及后续范围。两者在循环入口处交接。这样做的好处是让高频的循环内范围没有跨循环溢出的额外负担而且循环外那段范围即便被分配到内存代价也比较小。2.3 Rematerialization比单纯拆分更聪明的重算除了拆分还有一个思路是让某些值“重新算出来”而不用在寄存器里保留。这叫“重新实例化”Rematerialization在活跃范围重写的语境下同样重要。比如变量被定义为一个常量或者一条简单的算术指令例如tmp addr 24。如果它溢出与其把结果保存到栈上再读回来不如在需要它的位置直接重新计算一次。因为“重算一条加法”比“做一次内存访问”便宜得多而且完全不影响寄存器的占用。实际操作中能可靠重算的通常有这些特征指令本身没有副作用操作数在目标位置依然活跃且容易获得计算成本低于一次访存这种做法从“活跃范围”的角度看是把原本横跨多个程序点的范围压缩成一小段。因为每次重新计算都会产生一个独立的、短暂存活的值不需要在整个区间内持续占用资源。2.4 重写之后腾出来的寄存器能干什么重写不只是为了减少溢出节省一点访存指令。更深一层的收益是它把稀缺的寄存器资源集中到了更值得的地方。试想一个函数里有热路径和冷路径。热路径上有一个变量需要频繁使用但冷路径上某个长命变量一直占着一个寄存器。如果不做重写分配器必须让两个寄存器同时存活。如果做了重写把冷路径那段的范围拆分让它在热路径执行期间根本不占用寄存器那热路径就能多获得一个物理寄存器。有了这个多余寄存器热路径上的变量就少了一次溢出循环体内少了几次访存。这种收益在嵌套循环、递归函数、大基本块中会叠加放大。另外拆分成短范围之后分配器还能更好地做“寄存器别名”和“寄存器重用”——同一个物理寄存器可以在相邻时间段被分给不同变量前提是它们的活跃范围在时间上没有重叠。3. 实操层面怎么把重写落地到编译器里3.1 常见编译框架里的活跃范围表示要在真实工程里做活跃范围重写第一步是选择一种合适的表示方式。不同编译架构不一样我自己更习惯用“区间列表”的方式每个变量对应一组互不重叠的区间每个区间用 [start, end) 表示在指令序列中的位置范围。变量 v: range1: [12, 45) range2: [88, 102)这种表示查询方便判断两个变量是否冲突也简单先按 start 排序然后线性扫描看有没有重叠。区间交叠的判定可以直接用if (a.start b.end b.start a.end) interfere true;如果是基于 SSA静态单赋值形式的中间表示活跃范围的表示会天然不同每个变量只有一个赋值点因此变量本身就是一段定义到使用的范围冲突关系可以直接用“定义支配使用”和“路径覆盖”来推导。这时候做活跃范围拆分本质上是把 SSA 变量替换成一个新变量在新的定义点补充复制指令。3.2 重写的基本流程切分点选择与数据流修正我把自己在某个模拟项目里用过的完整流程说一下它不依赖任何特定框架纯手工也能实现先对函数做一遍活变量分析拿到每个基本块入口和出口的活跃集合。为每个变量构造完整的活跃区间列表。根据启发式规则选出候选切分点。常见切分点包括基本块边界、循环头、循环退出点、调用指令位置、条件分支合并点。在切分点插入复制指令或移动指令。插入时要保证语义从旧变量读出值写入新变量。重新运行一遍数据流分析更新活跃集合如果用的是 SSA 中间表示还要插入新的 phi 节点来合并不同来源的值。重建冲突图重新做寄存器分配。第 4 步特别容易出错。举例说如果切分点在基本块边界而该基本块有多个前驱块那新变量必须在每个前驱的出口处都被赋值。如果不补全这些赋值路径就会出现“某个分支没有执行赋值就读取新变量”的经典错误。我在工作中解决这个问题的办法是在切分点统一用 copy 指令保证所有路径都经过复制点。如果复制点的代价过高就放弃这次切分。3.3 启发式与代价模型怎么决定切在哪里选切分点不是拍脑袋它背后有个代价模型。大致可以这样量化假设变量 v 原本需要溢出溢出代价是spillCost。如果我们在某个边界把 v 拆成 v1 和 v2使它们不再和某个难缠变量冲突那么 v1 和 v2 的溢出概率会下降这个收益记为saveSpill。代价是插入复制指令和执行这些复制指令的时间记为copyCost。当saveSpill copyCost时拆分才值得做。更精细一点还要考虑循环频率。循环体里的复制指令执行次数等于迭代次数乘以循环体代码体积。所以即使收益很大如果复制点落在超级热循环里也要谨慎。我自己的习惯是给不同位置设置经验权重函数入口/出口权重低复制几乎不执行循环外到循环内权重中等但是收益极高循环内到循环内权重高非必要不切调用指令附近权重低但能减少跨调用保存寄存器的压力3.4 我实操中的切点选择心得有一次做一个数组循环求和的函数某个临时变量因为函数开头一段初始化代码的存在活跃范围被拖得极长导致循环体内两个关键变量无法同时上寄存器。我一开始在函数入口切发现没效果后来把切点移到循环入口之前让临时变量的值在进入循环前就被复制到另一个变量上老变量彻底失去活跃状态整个循环体里的寄存器压力一下就下去了。这个经验给到大家一个非常实际的操作倾向“切分点尽量靠近使用密集区之前”。不要把范围切在中间最好直接让某一段范围在进入热区之前彻底“死掉”。这样即使是复制指令也发生在冷路径或者只执行一次的位置上。4. 常见问题与排查技巧实录4.1 活跃范围重写后代码体积膨胀这是我最早踩到的坑。原本想着拆分后能减少溢出结果编译产出不只是没有变小反而显著变大了。原因是切分点太多生成了大量复制指令而且每个复制指令还占用额外的寄存器最后得不偿失。排查后发现是我的启发式对“变量只在热路径使用、但范围覆盖冷路径”的情况过度敏感导致在冷路径上也不断切分。后来加了条件过滤只有切分点所在基本块的预估执行频率低于某个阈值并且确实能消除一条干涉边才执行拆分。我还要在拆分完成之后加一个收益核查器它把“新增复制指令的预计执行成本”和“节省下来的溢出访存成本”做比较。核查不通过就回滚这次重写。这个回滚机制在早期迭代里非常有价值。4.2 与 phi 节点、复制传播的复杂交互在 SSA 形式上做活跃范围拆分看起来最优雅因为每个变量只有一个定义点。一旦拆分就需要把原来变量忽略掉换成新变量这不可避免地要和 phi 节点、复制传播发生交互。常见问题是一个拆分变量在两个分支里被赋了不同的值汇聚点原本的 phi 节点会变得很难看。如果不对 phi 节点同步更新下游读取的可能是旧变量但旧变量在这个汇聚点之后已经停止更新了。我自己处理 phi 节点的方法是先对汇聚块生成新的 phi 节点让下一个临时变量接收所有前驱的合并值再把后续读取全部重定向到新 phi 的结果。这个过程必须配合死代码删除否则旧变量和旧 phi 会残留成死代码。记住一个原则重写活跃范围之后所有对旧变量的读取都必须严格确认它仍然落在旧变量还活跃的区间内。任何跨出区间的读操作都是 bug。4.3 调试时数据流不一致活跃范围重写之后调试数据流问题特别头疼。原来的变量可能被拆成三个临时变量三个的名字还全是编译器自动生成的根本分不清谁是谁。我养成了两个好习惯。第一每个新变量都保留原始的变量编号作为调试后缀类似v_orig3_split1、v_orig3_split2。这样在中间表示 dump 里能一眼看出是哪个变量的哪一段。第二在每个切分点插入复制指令之后立刻重新做一次活变量分析并且加一条断言被切分的旧变量在切分点之后一定不再活跃。如果断言失败说明切分点选错了或者复制路径有缺失。4.4 实测对比究竟在什么场景收益最大我把活跃范围重写用在一个模拟的循环规约程序和一个递归遍历程序上观察不同场景的实际收益。结果很有意思场景特征重写前行为重写后效果长循环 多分支合并点多处强制溢出循环体内访存频繁循环内冲突显著减少执行时间大约能缩短 20% 以上函数整体活跃变量少但个别变量跨越调用点跨调用需保存和恢复拆分到调用点两侧后省去不必要的保存变量在整个函数内都被高频使用拆分后复制指令成本大于收益基本没有提升有时还会变差从这个结果看活跃范围重写不是万金油。它最适合的场景是“变量的活跃范围比实际需要长得多”的情况也就是范围覆盖了大量实际不读取它的区间。对于本来就已经短命、高频的变量硬去拆分反而会破坏寄存器分配的局部性。所以说先分析再决定拆不拆比无条件拆分重要得多。我建议在实现阶段加一个开关默认只对“证据充分”的高冲突变量启动重写。等整个流程稳定了再慢慢放开启发式的激进程度。最后分享一个我在实践中反复验证的细节做活跃范围重写前先把循环不变量外提和公共子表达式消除这类优化跑完。因为这两类优化本身就会显著压缩变量的活跃范围很多看起来需要重写的长命变量在做完这些基础优化后已经自己变短了。先做常规优化再做范围重写收益排序会清晰很多。这个顺序是我踩了多次坑才定下来的大家可以直接照搬。
阅读完成 · 觉得有帮助？
