“具体候选可由图着色分配或线性扫描产生，迭代合并再协调复制偏好与干涉。溢出与重物化给出带显式保留暂存器的可执行重写，并按实际路径计算访存；这些生成算法共同接受本页的位置与值保持合同，启发式质量…”
形式陈述
干涉边是禁令，复制边是偏好
在图分配的输入上，另记录每条复制
合并两个节点u、v，是用代表节点uv承接二者邻居并记录别名。如果u、v原本干涉，不能合并；两个固定不同颜色的节点也不能合并。若后来其他合并使一条原偏好的两端变成干涉邻居，就把该偏好标为constrained，不再用它阻止简化。已经归于同一代表的偏好则已满足。
两种保守测试
设有K种颜色，普通节点当前度数至少K称为高度节点；固定节点在本测试中始终视为高度，因为它们不会被低度简化删除。
Briggs测试用于两个普通节点：它们邻居并集中的高度节点数量严格小于K才允许合并。证明机制是先移除那些低度邻居；合并不会增加其他节点的度，因为两个旧邻居只替换成至多一个新邻居。此后合并节点剩下少于K个邻居，可以删除；剩余子图的着色再按逆序扩展，低度定理逐个恢复。[1, §3]
George测试用于普通v合并到固定u：v的每个邻居t都必须满足“t低度，或t是固定节点，或t已经与u相邻”。固定颜色两两相邻，因此固定t的颜色已由原固定图约束。低度t移除后可恢复；其余t本来已禁止使用u的颜色，合并不会额外限制它们。[1, §6]
这些是充分条件，不是“不能通过就一定不能同色”的必要条件。它们保护当前约简图的可着色性；若此前已经移走没有低度保证的潜在spill节点，不能进一步宣称整次乐观启发式的实际spill数量绝不会增加。
把简化和合并反复接起来
每轮先更新代表和偏好状态，然后：
- 简化一个低度、没有未解决复制偏好的普通节点
- 若没有，寻找通过保守测试的未解决偏好并合并；图一改变，重新检查原先暂时不合格的偏好
- 若仍没有，选一个低度但有偏好的节点，冻结它关联的偏好，再简化该节点。冻结只放弃“争取删这条复制”，不删除源程序里的复制
- 若全是高度节点，选择潜在spill，冻结其偏好并移走，最后乐观反向选色
下载版每次重扫来得到这四类集合，与增量维护worklist有相同判定接口，成本不同。代表别名必须一直追到最终代表；回填颜色时，过去保存的邻接节点也按最终别名解释。实际spill的合并族共用一个私有槽，仍须遵守全部原干涉边。
直觉
先腾出不相关的邻居，合并机会才会出现
想让两个名字共享寄存器时，不能只看它们之间有没有边，还要看合并后会把多少限制集中到一个节点。先完成一些不带复制关系的低度名字，可降低剩余节点的度，使原本保守拒绝的合并变得安全。
冻结则是让算法继续前进的出口：一条便宜的复制未必值得为了消掉它而制造更贵的访存。放弃这项偏好以后，仍可正常着色；若最后偶然给了同色，代码生成仍可删掉那条物理自复制。
例子与边界
一条五节点路径上的两次机会
令K=2，干涉图为路径a—e—c—b—d，唯一复制偏好是a与c。初态邻居并集为{e,b}，二者度数都是2，高度数量2不小于K，Briggs测试拒绝。
先简化没有复制偏好的d，其度数1。b随即降到度数1，a/c的邻居并集仍为{e,b}，但只有e属于高度节点；此时高度数量已经从2降为1，保守测试已经允许合并。
下载实现优先处理可简化的非复制相关节点，所以先继续删除b，再实际执行a/c合并；这时邻居并集只剩e。随后简化合并点和e，逆序着色得到e、b用R0，a、c、d用R1。应区分“删d后已可安全合并”和“实现删b后才选择执行合并”这两个时点。
这个例子说明“早期保守测试失败”可以随图约简改变；并不说明所有没有显式合并的分配器都一定留下复制，普通选色也可能碰巧让a、c同色。
不相邻也不能随意合并
改为四节点路径u—a—b—v，仍用两色，并希望u/v同色。原路径有合法两色着色，但合并两个端点后得到三角形uv—a—b—uv，需要三色。原来不存在边u—v，不足以证明合并保持可着色性。
在本算法中，a和b高度，端点偏好的Briggs测试失败；又没有非复制相关的低度节点。可以冻结u/v偏好后简化端点，保留复制，得到合法两色。若强行合并，就会至少产生一个实际spill。
预着色也会改变答案。跨调用值若已与固定R0干涉，不能借与另一个名字的复制偏好把它合并到R0；保守测试之前就应拒绝这条受约束偏好。复制的数值相等不取消调用对物理寄存器的破坏。
推论与应用
正确性和好不好分别验收
可靠输出首先要求固定颜色不变、每条原干涉边异色或位于不同私有槽，以及每个实际删掉的move两端位置相同。别名只改变表示，不能漏掉合并节点原先任何一方的邻居。这些是有限可检查条件。
“消掉多少move”“最后多少spill”属于另一份质量报告。George–Appel §5.1特别区分悲观与乐观spill：交错保守合并的保证不能直接改写成乐观选色下实际spill数总不增加。后续经过机械化验证的IRC工作也将合法性与启发式最优性分开。[2, §2]
本实现成本与终止
令N为包括固定节点在内的节点数，M为复制偏好数。每个外层动作至少移走一个普通节点，或合并两个节点；普通节点数量严格减小，所以至多N轮结构改变。冻结在同一轮接着移走其低度节点，不会反复冻结却不前进。
下载版使用未压缩别名链、重复扫描偏好和当前度数。按整数化标识、期望常数集合操作计，
终点任务：在五节点路径上写出d、b删除前后的高度邻居计数，再把偏好改成a/b。两者相隔3条边，强合并会把a—e—c—b闭成三角形；本实现先简化d，再冻结a/b偏好并简化a，最终a与b异色，复制保留。逐项复算这条轨迹，说明冻结为何使合法两色解仍可被找到。随后把c固定为R0，重新核每项George条件，不能仍使用“两个普通节点”的测试。
参考资料
[1] Lal George、Andrew W. Appel，Iterated Register Coalescing，ACM TOPLAS18(3)，1996，§3 pp.303–307保守合并，§5 pp.308–310交错/freeze及乐观边界，§6 p.311固定节点判定；附录A pp.317–322给工作表与别名不变量。
[2] Sandrine Blazy、Benoît Robillard、Andrew W. Appel，Formal Verification of Coalescing Graph-Coloring Register Allocation，ESOP2010作者稿，§§2–3：部分着色规格、四类工作表与终止/合法性目标。本页使用便于逐步复算的重扫实现与独立路径实例；论文的Coq证明针对其自身算法。