线性扫描寄存器分配

形式陈述

活跃范围和包住它的区间

输入是有限CFG、可达指令的固定排列和活跃集合。编号 $i=0,1,\ldots$ 的指令有读相位 $2i$ 和写相位 $2i+1$ 。右侧值在读相位取出，左侧在写相位写回；同一指令先读后写。

对名字x，收集它在LiveIn或Use出现的读点，以及在LiveOut或Def出现的写点。即使一个定义随后不再使用，也保留其写点。设这些点的最小/最大值为 $l_x,u_x$ ，分配用半开区间 $I_x=[l_x,u_x+1)$ 。区间中间可以含真实不活跃的洞；单段表示把这些洞也算占用，是安全的保守近似，不是精确路径事实。[1, §§3–4]

同一寄存器中的区间必须不重叠。两个区间一端恰好相接，如 $[1,3)$ 与 $[3,5)$ ，可以共用。本文与原论文的闭区间记号不同，因此到期条件也明确使用 $end\le start$ ，不能机械照搬原文严格小于的比较。

active中只放当前仍占寄存器的区间

按起点、再按名字排序。active保存已经处理、还没到期且确实获得寄存器的区间。处理当前区间x时：

删除所有 $end_y\le start_x$ 的active成员，释放它们的颜色
若有允许且空闲的颜色，把一个分给x，加入active
否则在active中找“颜色对x也允许”的最晚结束区间v。若 $end_v>end_x$ ，把v整段改为栈位置，x接过它的颜色；若没有这样的v，或v结束不更晚，就让x整段放栈

允许颜色集合全为同一 $K$ 色时，这就是基本最晚结束启发式。本单元加入一种保守调用限制：若区间横跨调用写点 $c$ ，即 $l_x<c<u_x+1$ ，删除调用会破坏的颜色。R0被double破坏，因此这样的区间只允许R1或栈；调用结果恰从 $c$ 开始，调用实参若读完即死则恰在 $c$ 结束，两者不因这个边界被误认成跨调用值。

选择候选后才做溢出重写。被后来挤出的v从其第一次定义起就按栈位置重写，不能保留前半段旧寄存器代码、只从挤出点突然开始读一个尚未写过的槽。最后依分配验证检查CFG真实干涉与调用约束；区间只是产生候选的工具。

直觉

把所有占用预约压在一条时间尺上

每个名字预约从首次需要到最后需要的一段位置。扫描到一个新预约，先退掉已经结束的；座位不够时，优先让占到最远处的那个去内存，给较早结束的新预约让位。

指令编号不是程序运行的墙上时间。分支两侧可能根本不会同时执行，但都出现在编号尺上；循环还会反复回到较小编号。区间安全性来自CFG活跃事实被包含在其中，不来自执行总是沿编号向右走。

主例八个半开区间，a在t2到来时整段改为栈；调用写点21约束跨过它的a — 读写相位与整段线性扫描

例子与边界

主例真正扫描出的顺序

使用终点菱形程序，块布局E、T、F、J。共有13条源指令，调用t5:=double(v)编号10、写点21。两个可分配寄存器R0/R1之外，S0/S1仍仅作显式保留暂存器。

名字	区间	允许寄存器	本次决定
a	[1,23)	R1	先给R1，之后整段被挤到slot0
flag	[3,9)	R0、R1	R0
t2	[5,15)	R0、R1	挤出结束于23的a，接R1
t3	[7,15)	R0、R1	整段slot1
t4	[11,19)	R0、R1	flag已到期，取R0
v	[19,21)	R0、R1	复用R0
t5	[21,23)	R0、R1	复用R0
y	[23,25)	R0、R1	复用R0

t3到来时active中的最晚结束者t2也在15结束，严格“更晚”不成立，所以牺牲当前t3。t4的区间包住两侧定义；虽然它与t2/t3在某条实际执行上能先读后写，跨块单区间近似仍更保守。该表给出合法结果，不保证和图分配器挑同两个spill名字。

a=3时，真/假分支仍分别返回21/1。线性扫描在所选路径上执行两次ST、四次LD，与本例图分配器的访存条数恰巧相同，但存的是a/t3，而非a/flag。其他程序没有这种相同保证。

最近使用、最后结束和实际代价不同

一个区间可能很长，却只在冷分支读取一次；另一段很短，却位于执行百万次的循环中。仅看end无法比较它们的动态访存成本。固定输入区间上的合法性与得到最少实际指令不是同一结论，本页不把“最晚结束”写成一般最优定理。

如果遗漏dead:=9的写点，区间表可能让仍需的x和dead共用位置；目标写入仍能破坏x。另一方面，如果把读点和写点混成一个不分先后的点，又会禁止y:=x+1在x最后一次读取后立即复用其寄存器。相位约定同时解决安全与不必要冲突。

推论与应用

所谓线性，是哪一段工作线性

设有V个区间，active长度至多K。已经按起点排好时，朴素active列表的每次筛除、颜色查找和牺牲者扫描花 $O(K+1)$ ，分配阶段总计 $O((V+1)(K+1))$ ；初始排序另需 $O(V\log(V+1))$ 。K固定才可把已排序的扫描称为线性。区间输出与位置表需要 $O(V+K)$ 空间，轨迹记录另为 $O(V)$ 。

构建区间前仍须计算CFG活跃信息；输入排列、活跃分析和实际load/store插入不藏在上述扫描界里。下载版用容易核对的集合不动点，而非声称整个编译过程都线性。

把洞和切点作为下一项决策

若需要利用活跃洞或同一值在不同位置换寄存器，先要明确每一段的接口和段间传值。活跃范围分裂给出一种按区域改名的可执行方案。成熟线性扫描可维护active/inactive和固定寄存器区间，还要在CFG边上解析位置差异；这不是只把一个区间画成两段就完成了重写。[2, §§2–3]

迁移任务：把主例a在调用后的使用删掉，重新算区间而不是只删禁止色；再将调用移到分支之前，看哪个区间真的横跨新写点。另取两个相接区间[0,2)、[2,3)，只给一种颜色，检查到期比较写成<后会增加一个不必要的spill。最后把一段后来被挤出的名字的早期store去掉，源/目标解释器应报告缺值，而不是默认该栈槽已经初始化。

参考资料

[1] Massimiliano Poletto、Vivek Sarkar，Linear Scan Register Allocation，ACM TOPLAS21(5)，1999，pp.895–913，§3 pp.897–898的程序/区间模型，§4 pp.898–900与图1的active、最晚结束及成本。原基本算法不做范围分裂。

[2] Christian Wimmer、Hanspeter Mössenböck，Optimized Interval Splitting in a Linear Scan Register Allocator，VEE2005，pp.132–141，§§2.2–2.4、3.1–3.3：活跃洞、固定区间、切分与边上resolution。本文允许颜色集合的整段版本是较小的教学扩展。

形式陈述 ​

活跃范围和包住它的区间 ​

active中只放当前仍占寄存器的区间 ​

把所有占用预约压在一条时间尺上 ​

主例真正扫描出的顺序 ​

最近使用、最后结束和实际代价不同 ​

所谓线性，是哪一段工作线性 ​

把洞和切点作为下一项决策 ​

反向链接