循环不变代码外提

循环把同一段代码执行很多次；如果其中的乘法每轮输入都相同，何必一遍遍重算？循环不变代码外提把这样的计算放到进入循环之前，只算一次，再让每轮读取保存的结果。真正需要证明的既有“不变”，也有“提前计算是安全的”。

从三轮乘法看出目标 ​

输入 a=2、b=3、n=3，执行：

i := 0
s := 0
while i < n:
    t := a*b
    s := s+t
    i := i+1
return s

每轮 t 都是6，循环头的 (i,s) 依次为 (0,0)、(1,6)、(2,12)、(3,18)，结果18。若 a、b 在循环中从不改变，可先计算新鲜 h=ab，再把循环内 t:=ab 改成 t:=h。三个循环后状态不变，乘法从3次变为1次。

这里刻意保留 t 的原赋值位置：外提的是表达式的计算，新鲜 h 保存结果。直接把对源变量 t 的赋值搬出去可能改变零次循环后的 t；用新鲜临时量能避开这一额外问题。

零次循环是必要测试 ​

令 n=0，源循环完全不执行，返回0。目标仍先做一次 a*b，随后返回0。乘法次数由0增为1，所以不能声称外提在每个输入上都减少工作；它是为多次执行时摊薄成本，并可能增加临时值存活范围。

若把乘法改成 t:=1/d，取 n=0、d=0，源返回0，错误的提前计算却除零 trap。“d 没被修改”只证明值不变，不证明提前求值合法。若 d=0、n>0，源稍后trap也不代表任意提前都合法，因为提前点与原点之间可能有可观察事件。

源变量赋值本身还有另一反例：循环前 t=99，循环体 t=ab，结束后 return t。n=0 时源返回99。若把整条 t:=ab 搬到 preheader，会返回6；正确的新鲜临时量版本先计算 h=6，却保留循环体内 t:=h，仍返回99。

从已知不变的输入逐层发现 ​

一个保守起点是：所有在 L 内从未被赋值、且进入 P 前已定义的变量，其值在一次循环进入期间不变。对本例，a、b、n 都满足，i、s 不满足。

随后扫描循环内纯总赋值。如果它的每个操作数都是常量、上述外部不变量，或已经确认并能提前取得的循环不变值，就标为候选。若一个候选依赖另一个候选，先移动被依赖的定义，再移动使用者。反复扫描直到没有新候选，可以发现 t:=a*b; q:=t+1 这样的两层计算。

非 SSA 中还要利用到达定义分析理路到达定义分析Reaching definitions analysis · 到达定值分析沿控制流保留每个变量可能最近执行的赋值，以入口定义、逐语句杀生与最小不动点建立定义到使用的可靠连接。核对操作数：若循环内定义提供这个操作数，该定义必须是到该使用处唯一的来源，并已被证明不变；还须排除旧值从循环入口或其他赋值到达。仅仅看到“源文件里只写了一行 t:=...”不够，因为同一行可能每轮用不同输入计算。

一个自循环依赖 t:=t+1 不会从上述种子被发现，因为 t 在循环中被写，且没有已经认证的不变定义供它使用。采用从空候选集合逐步生长的最小闭包，可以避免把一组互相依赖的循环定义当作无根的不变证据。

变化的值还可能有不变的增量。仿射归纳变量强度削弱理路仿射归纳变量强度削弱Affine induction strength reduction · Induction-variable strength reduction · 仿射归纳变量递推在规范整数循环中把每轮重算m乘i加c变成新鲜载体递推，证明非零起点、更新相位与零轮状态保持，并区分循环运算和新增初始化成本。对规范整数循环中的mi+c另建载体，先算正确初值，再紧跟i更新维护它；这不把整个变化表达式误判为不变。新载体与源赋值位置分开，因此零轮仍保留源变量旧值，新增初始化的运算成本则明确单列。

两个不同的正确性问题 ​

第一是值保持：每次到达原表达式位置时，操作数仍等于 preheader 中的对应值。对候选依赖顺序归纳，外部不变量在循环内没有写入；先前候选已经保存同值；纯确定运算便给出同一结果。因此 t:=h 与原 t:=a*b 对后续源变量状态的作用相同。

第二是新增执行安全：循环可能零次，某条条件分支也可能永远不走，而 preheader 仍会计算 h。这就是本页要求运算纯粹且总定义的原因。多做一次不会抛异常、不会发散，也不产生外部事件；h 又是新鲜内部变量，因此额外工作在观察中不可见。

二者合起来给出逐运行对应：进入循环时允许目标多一个 h，其他源变量一致；每到原计算点，用值保持恢复对应；其他指令同样执行，分支输入不变，退出结果相同。即使循环发散，每轮额外替换只改变有限内部工作，控制转移仍保持。

当重复的是不变条件的控制选择时，循环不变分支外提理路循环不变分支外提Loop unswitching · 循环选择外提对入口已定义且体内不写的条件生成两份完整计数循环，以一次运行时选择代替逐轮选择，并证明事件次序、零轮状态与次数捕获不变。给出独立接口：复制完整循环并在运行时选一份，保留每轮赋值与事件次序。条件须在入口有值且体内不写；零轮会多求值一次，仍依靠纯总与无事件条件。它改变代码体积，不能仅把条件算一次便当作完成全部控制改写。

代价、收益与迁移 ​

已知支配后，一条回边的自然循环可用反向搜索在 O(N+M) 时间内取得。朴素候选发现至多新增 K 条循环内指令，每轮扫描 K 条，故为 O(K²) 加到达定义查询与操作数扫描；有依赖计数和使用链时可以避免重复全扫。建 preheader 与重定向边的成本按边数计，SSA 修复另外计入。

若某表达式原本执行 m 次，外提后每次循环进入计算一次，再产生 m 次读取/复制。m=0 时多算一次，m=1时未省算术，m大时才可能有明显收益。数学整数乘法还要按位数计成本；延长活跃范围可能带来spill。本例只报告乘法计数和循环后状态。

迁移任务一：把 n 改为5，仍取 a=2、b=3，结果应为30，乘法5对1。任务二：循环每轮末尾再执行 a:=a+1，n=3、初始a=2、b=3；源各轮加6、9、12，结果27，错误外提仍得18。请定位哪条不变量前提失效。任务三：给乘积后加 q:=t+1，只使用q累加；在满足唯一来源与纯总条件时，先外提 h=a*b，再外提 k=h+1，三轮结果21。