从虚拟名字交付一份可执行代码 ​

回到寄存器分配学习路线。这项练习把“得到颜色”继续推进到目标程序：同一份带分支和调用的IR，分别经过图分配、线性扫描、复制合并、区域分裂与物理溢出重写。每次改变都要交出实际块表，并说明哪个位置装着下一步需要的值。

下载纯Python核验器与完整参考输出。Python 3.10+运行python foundations-register-allocation-checker.py即可得到JSON；所有必要检查是显式检查，python -O应得到相同输出。使用importlib加载文件后，compile_all、split_regions、lower和两个解释器可分别调用。源码中的main_program()给出下列完整输入。

先固定机器和可观察结果 ​

物理寄存器共有四个：R0、R1可分配；S0、S1只作重载暂存器，不能跨原IR指令保存逻辑值。私有栈槽互不别名。二元指令先读取两个操作数，再写结果，采用数学整数。没有堆、I/O、异常、整数溢出或有限内存耗尽。

纯函数double由R0收参并返回两倍值，破坏R0、S0、S1，保留R1和私有槽。运行对象是顶层过程；若编入真实ABI中的被调用函数，还须另履行保存寄存器和栈布局约定。

比较的观察是返回整数和源分支真假序列。目标load、store和跳转是内部步骤，可以比源程序多。循环的每条源指令仍展开为有限条目标指令；解释器的步数上限只表示本次检查未完成，不把超限认作发散证明。

任务一：从活跃值建立约束 ​

E:
  a := input(a)
  flag := input(flag)
  t2 := a + 1
  t3 := a + 2
  if flag then T else F
T:
  t4 := t2 + t3
  goto J
F:
  t4 := t2 - t3
  goto J
J:
  v := t4
  t5 := double(v)
  y := a + t5
  return y

先不看候选位置，写出逐指令活跃集合理路活跃变量分析Live-variable analysis · Liveness analysis从未来使用逆向传播仍需保存的变量，计算逐指令和块边界活跃集，并把phi的使用限定在相应进入边。。调用结束后仍需a，因此a必须与固定R0节点干涉。v若调用读完即死，不属于跨调用值；t5是调用新结果，也不能被误加同一条禁止边。

用图着色分配理路图着色寄存器分配Graph-coloring register allocation · Chaitin–Briggs register allocation从活跃性和调用破坏集合建立干涉图，执行简化与乐观选色，再把失败节点交给真实溢出重写。逐步简化。参考候选把a放slot0、flag放slot1，t2放R1，t3/t4/v/t5/y放R0。应核的普通干涉包括a与flag、t2、t3、t4、v、t5；flag与t2、t3；以及t2与t3。move的偏好不是另一条强制相等约束。

提交每次出栈选色及所有原边的最终位置检查。再对两色四环和三角形运行同一算法：四环虽没有初始低度节点，却可在反向选色时不spill；三角形至少要让一个名字离开寄存器。潜在spill不能提前算成一次必然的内存访问。

任务二：交出物理IR，不停在位置字典 ​

上面图候选经物理溢出重写理路寄存器溢出与重物化Register spilling · Rematerialization · 溢出重写把栈位置真正改写为显式LOAD/STORE，核算暂存器和调用破坏，再以可证明的常量配方消除不必要访存。后得到以下代码。逗号分隔操作数；ST的顺序为“槽、源寄存器”，LD的顺序为“目标寄存器、槽”。

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

a=3、flag=1时返回21；flag=0时返回1。更一般地，真分支为5a+6，假分支为a−2。两条路径都运行2次ST、4次LD；真路径执行16条目标指令，而源路径为11条。v:=t4的物理自复制已被删掉，CALL2前R0确实装着实参。

故意把a改分到R0并保留其他决定，先让干涉检查拒绝候选。再考察x:=7; dead:=9; return x：若错误地把二者都放R0而仍保留死写，目标会返回9。这个失败和“x与dead是否同时活跃”不同，检查必须考虑实际保留的定义写入。

任务三：让另一种启发式处理同一压力 ​

线性扫描理路线性扫描寄存器分配Linear scan register allocation · 线性扫描分配将CFG活跃事实包成半开区间，按起点扫描并处理到期、整段牺牲和跨调用禁用颜色。按E、T、F、J布局，使用读点2i、写点2i+1。请核a=[1,23)、flag=[3,9)、t2=[5,15)、t3=[7,15)，调用写点为21。

a先获得R1；t2到来时无空闲颜色，a结束更晚，于是a整段改到slot0。t3和当前最晚结束的t2都结束于15，严格更晚条件不成立，所以t3整段放slot1。最终flag在R0，其余短段复用R0；访存条数在本例恰与图候选相同，存取的逻辑名字不同。

把J末尾的y:=a+t5改成y:=t5+1，重新执行活跃分析、区间构造和扫描。a不再因为调用后的读取被保活，不能沿用旧区间后只手工放宽颜色。另把单色区间[0,2)与[2,3)交给扫描器，验证“到期”使用≤而不是<。

交错合并理路迭代寄存器合并Iterated register coalescing · IRC register allocation把复制偏好与干涉约束分开，交错简化、保守合并和冻结，以实际图说明安全合并为何可能被早期度数遮住。另有自己的输入任务：五节点路径a—e—c—b—d偏好a/c。删d后b从度数2降到1，高度邻居数已经从2降到1，允许安全合并；实现优先继续简化b，然后才实际合并a/c。把偏好换成a/b时，两者隔3条边，强合并会闭成奇环；实际轨迹应先删d，再冻结a/b，最后a与b异色。提交别名表和原边检查，不能只数被删move。

任务四：区域分裂必须交付每条边上的值 ​

调用split_regions得到按块分裂理路活跃范围分裂Live-range splitting · Live interval splitting按区域为同一逻辑值改名并补齐每条边的传值，输出可执行虚拟IR，再比较分段位置和额外移动。后的完整虚拟IR，再分配和lower。原块内名字改成x@块名，四个边适配块应具有下列同时赋值：

a在T、F都只路过，没有当地使用，却仍要进入对应传值集合。分裂版本图分配把a@J放R1，a@E、a@T、a@F分别放私有槽；a的逻辑身份通过边复制连接。

a=3的真分支仍返回21，但本次分裂候选执行3次ST、5次LD、3次JMP、1次MOV，总计21条目标指令。对照任务二，它变慢了。全块切分让区域可独立选择位置，同时增加传值；这一结果不能隐藏在“分裂通常减少压力”的笼统说法后面。

删掉F→J上的a传递，假分支应暴露缺值；只运行真分支无法验收这个变换。再迁移到循环：初值a=1、b=2，每轮同时交换a/b并把n减1，结束返回a−b。n为偶数时应返回−1，奇数时返回1。先按虚拟同时赋值解释，再把R0/R1交换顺序化；用私有临时槽断环，不能把两条普通MOV顺序执行后宣称交换成功。原SSA消解理路SSA 消解SSA destruction · Out-of-SSA translation · SSA deconstruction把 φ 的按边并行赋值降为普通复制，通过拆分关键边、打破复制环和安全合并名字保持语义。中的并行复制不变量正是这里的工具。

任务五：用配方替代哪一份内存值 ​

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

固定c在slot0，x/u/y在R0。普通重写包含一次ST、两次LD；允许常量重物化后，在两次使用前各执行IMM S1,7，不再保存或重载c，x=3仍返回17。动态指令从7条变为6条；两种指令的真实机器延迟不在本教学计数里。

将配方换成c:=x+1，随后把x改成9，再使用c。若原x=3，保存值应为4，在使用处按当前x重算会得到10。要扩展常量配方，必须同时保存原操作数身份或证明未改写，并满足纯性和异常条件。另检查被合并别名共享一个spill槽的情形：没有证明整个值族都可重建时，不能只删某个常量名字的定义store。

完成时应有的文件和解释 ​

交付源IR、活跃/干涉或区间事实、位置与别名表、区域改名和四条传值边、可直接解释的目标块表，以及逐输入返回/分支对照。下载JSON同时包含未分裂和已分裂的全部物理代码，可逐条核对，不需要猜测被省略的load/store。

参考主入口检查a从−20到20、flag取0/1，三种分配器在原版与分裂版上共492次源/目标对照；另核四环、三角形、保留死写与常量重物化。有限样例能发现实现错误，不能代替逐指令、逐边、调用边界的保持论证。最后报告实际ST/LD/分支/调用条数，再讨论质量；合法候选与较好候选各有自己的证据。