寄存器溢出与重物化

存一张结果，还是带一张能重做的纸条 ​

内存可以保存已经算好的数，之后读取即可。若结果是一个固定的小常量，现场重新装入可能更便宜；若它依赖一个已经被覆盖的输入，纸条只写“再加一”就不够了。

两者都要付实际费用：保存方案付store和load，重算方案付IMM或计算指令。重物化只在指定目标成本模型下有利；昂贵运算被反复重算，可能比一次保存更慢。

主例的完整物理代码 ​

图分配给a/flag两个槽，t2在R1，其余运算结果顺序复用R0。下面是实际可执行目标，不再含a、t2等虚拟操作数；IN的最后一个字段只是外部输入键。

E: IN S0,a;       ST slot0,S0
   IN S0,flag;    ST slot1,S0
   LD S0,slot0;   ADD R1,S0,1
   LD S0,slot0;   ADD R0,S0,2
   LD S0,slot1;   BR S0,T,F
T: ADD R0,R1,R0; JMP J
F: SUB R0,R1,R0; JMP J
J: CALL2
   LD S0,slot0;   ADD R0,S0,R0
   RET R0

t4→v的复制和把v送R0的参数复制都成为同位置动作，可以省略；它们的值没有凭空消失。CALL2返回后R1虽然保留，其旧t2已不再需要；真正要用的a从slot0重载。输入a=3、flag=0执行F，R0从5变成−1，再被CALL2变成−2，最后加a返回1；flag=1返回21。

每条实际分支路径都有2次ST和4次LD，总共6次私有槽访存。静态代码同时含T和F，不能把两侧都加进一次执行成本。槽中没有未初始化读取：两个IN之后立即ST，后面的每次LD都由这份存储或保持它的路径覆盖。

两次使用常量，少了哪三次访存 ​

c := 7; x := input(x)
u := x + c; y := u + c; return y

给c独立slot0，x/u/y按顺序共用R0。普通方案先ST slot0,7，两次加法前各LD S1,slot0。重物化方案删掉store，两次使用分别IMM S1,7。x=3时两者都返回17；普通路径7条目标指令、3次访存，重物化6条指令、0次访存。

这个账本采用一次ST/LD/IMM各计一条目标指令，不宣称真实处理器延迟相同。若常量编码需要多条机器指令，应换成真实展开成本；本文的立即数是数学模型的输入能力。

原输入已经改变的反例 ​

令x:=3; saved:=x+1; x:=9; return saved。正确返回4。若把saved当作“随时重新算x+1”而删除保存，最后会得到10。可用原x的不可变版本作为配方输入，但这份旧版本也需要自己的保值位置；重物化不能把它的成本隐藏起来。

另有c:=7; d:=c; return d，若分配器合并c/d到同一溢出槽，直接删c的store、再把c→d当物理自复制删掉，d就会读取未初始化槽。当前实现看到共享home会保留普通保存方案。更积极的实现可以给整个别名族证明相同常量配方，再统一改写所有使用。

用指令边界关系证明重写 ​

在每条源指令入口，要求所有当前活跃名字的值存在其分配位置；获准重物化的独立常量则由配方给出相同值。LD/IMM先建立两个操作数，ADD/SUB/MOV按照同一全定义运算产生结果，ST把需要保留的结果交回home。干涉检查保证目标写入不会覆盖另一个仍需的不同值；CALL2的破坏集合另由调用边保护。到下一条源指令边界，关系重新成立。

一条源指令被有限目标序列匹配，分支读取同一个整数，所以选择同一条源边，返回值也相同。循环中逐边归纳同样成立；有限额外动作没有新增独立循环。证明依赖明示的目标资源和无别名私有槽，不能由“随机输入都相等”代替。

成本与终点迁移 ​

固定元数普通指令至多插常数条重载/保存，故给定位置后普通lowering按源IR大小L花$O(1+L)$工作和输出。并行复制含k个动作时，另计本单元朴素断环排序$O((k+1{)}^2)$；每次原边仍只展开有限长度。动态成本要沿实际执行路径累加，循环次数、调用次数与每次是否访问溢出值都会影响总量。

先在主例目标上逐条解释得到21/1和6次访存，再把a误放R0而不保存，检查调用前后的值在哪一步丢掉。随后比较常量重物化与共享home反例；最后把double改为连R1也破坏，给分配器增加约束后重新生成目标，不能只修改目标CALL2的破坏行为却继续沿用旧候选。