diff options
Diffstat (limited to 'content/notes/register-allocation/liveness')
| -rw-r--r-- | content/notes/register-allocation/liveness/index.md | 257 |
1 files changed, 257 insertions, 0 deletions
diff --git a/content/notes/register-allocation/liveness/index.md b/content/notes/register-allocation/liveness/index.md new file mode 100644 index 0000000..e88dba4 --- /dev/null +++ b/content/notes/register-allocation/liveness/index.md @@ -0,0 +1,257 @@ +--- +title: "第二部分: 活跃性分析与生命周期" +slug: "liveness" +lang: zh-Hans +series: register-allocation +weight: 30 +created: 2026-08-17 +updated: 2026-09-09 +license: CC-BY-SA-4.0 +--- + +寄存器分配面对的是一种随程序位置变化的资源需求. 一个函数里可能出现几百个 virtual registers, 但 allocator 并不需要同时为它们全部准备物理寄存器. 某个 value 在完成最后一次有意义的 use 之后, 保存它的寄存器就可以重新利用. 因此, 在开始讨论 interference graph 或 Linear Scan 之前, 首先需要确定每个 value 在程序的哪些位置仍然必须保持有效. 这就是 liveness analysis. + +## 1 一个 value 在什么时候是 live 的 + +考虑一段简单的直线代码: + +```text +1: v1 = load a +2: v2 = v1 + 1 +3: v3 = v2 * 2 +4: return v3 +``` + +第 1 条指令产生 `v1`. 在第 1 条和第 2 条之间, `v1` 必须被保存, 因为第 2 条指令还要读取它. 第 2 条执行完以后, 后续已经没有 `v1` 的 use, 因而 `v1` 可以死亡. 从这个位置开始, 覆盖 `v1` 所使用的物理寄存器不会再改变程序结果. + +更严格地说, 对某个程序位置 $p$ 和 value $v$, 如果从 $p$ 出发存在一条可执行的控制流路径, 路径后面会读取当前的 $v$, 并且在这次读取之前没有新的 definition 取代它, 那么 $v$ 在 $p$ 处是 live 的. 这个定义包含 "存在一条路径" 这一条件, 所以 liveness 属于 may analysis. 编译器不能因为某条路径执行概率很低就忽略它, 只要该路径在语义上可能发生, 对应的 value 就必须得到保留. + +这也解释了为什么 liveness 是 backward dataflow analysis. 判断某个 value 当前是否 live, 要看它未来是否还有 use. 信息传播方向因此和程序执行方向相反. 如果 CFG 中有 `B1 -> B2 -> B3`, 程序沿箭头向前执行, liveness 则从后继 block 向前驱 block 传播. + +对一条机器指令来说, operand 通常可以分成 def 和 use. 例如: + +```text +v3 = ADD v1, v2 +``` + +`v1` 和 `v2` 是 uses, `v3` 是 def. `v1` 和 `v2` 必须在指令读取它们时仍然 live, `v3` 则从这次 definition 开始产生新的值. 如果这条 ADD 是 `v1` 的最后一次 use, 那么这个 use 可以带有 kill 的含义. Kill 描述 value 生命周期在这里结束, 并不对应一条真实的 "删除寄存器" 指令. + +反过来, 一个 definition 也可能产生从来没有被使用过的 value. 例如: + +```text +v1 = ADD v2, v3 +v4 = MUL v2, v3 +``` + +如果之后没有任何指令读取 `v1`, 那么第一条指令对 `v1` 的 definition 是 dead def. 在较早的优化阶段, 这种代码通常会被 DCE 删除, 但机器级变换仍然可能临时产生 dead definitions, 所以后端的 liveness 表示也需要能够处理它们. + +这里最好始终把 liveness 理解成 value 的性质, 不要和源语言变量的作用域混在一起. 例如: + +```text +x = 1 +use x +x = 2 +use x +``` + +两次 assignment 虽然都写着 `x`, 对数据流来说却产生两个不同 values. SSA 会把它们直接写成 `x1` 和 `x2`. 即使 IR 当前没有处于 SSA form, liveness 分析真正关心的也仍然是哪一个 definition 产生的值在后面还会被读取. + +## 2 从 Basic Block 到数据流方程 + +在没有分支的代码中, 从函数尾部向前逐条扫描就能得到 liveness. 有了 CFG 以后, 一个 block 的出口可能通向多个 successors, 这时通常先在 basic block 粒度求出边界信息, 再把结果展开到 block 内部. + +对 basic block $B$, 先定义 $\mathrm{USE}(B)$ 和 $\mathrm{DEF}(B)$. $\mathrm{DEF}(B)$ 包含 block 内产生的 definitions. $\mathrm{USE}(B)$ 包含那些在 block 内第一次使用时还没有在本 block 中被定义的 values, 也就是 upward-exposed uses. + +例如: + +```text +B: + v3 = v1 + v2 + v4 = v3 * v5 +``` + +这里 `v1`, `v2`, `v5` 都需要从 block 外部带进来, 所以它们属于 $\mathrm{USE}(B)$. `v3` 虽然在第二条指令里被使用, 但它已经在第一条指令中定义, 因此不属于 $\mathrm{USE}(B)$. 对这个 block 有 $\mathrm{USE}(B)={v1,v2,v5}$, $\mathrm{DEF}(B)={v3,v4}$. + +随后定义 $\mathrm{LIVE\_IN}(B)$ 和 $\mathrm{LIVE\_OUT}(B)$. 前者表示进入 $B$ 时必须仍然有效的 values, 后者表示离开 $B$ 时仍然必须有效的 values. 对普通 CFG, 经典 liveness 方程是: + +$$ +\begin{aligned} +\mathrm{LIVE\_IN}(B) &= \mathrm{USE}(B)\cup\left(\mathrm{LIVE\_OUT}(B)-\mathrm{DEF}(B)\right), \ +\mathrm{LIVE\_OUT}(B) &= \bigcup_{S\in\mathrm{succ}(B)}\mathrm{LIVE\_IN}(S). +\end{aligned} +$$ + +第一条方程可以直接按程序语义理解. 进入一个 block 时需要保留的 value 有两种来源. 一种是 block 自己马上会读取, 且在读取之前没有本地 definition 的 value. 另一种是 block 后面的代码还会使用, 同时当前 block 没有重新定义它的 value. 如果一个 value 在 $\mathrm{LIVE\_OUT}(B)$ 中, 但 $B$ 自己会重新定义它, 那么从 $B$ 入口带入的旧值就不需要为了后续 use 继续保留. + +第二条方程来自控制流分叉. 如果 $B$ 有两个 successors $S_1$ 和 $S_2$, 某个 value 只要在其中任意一个 successor 入口需要保持, 离开 $B$ 时就必须保存. 假设 $\mathrm{LIVE\_IN}(S_1)={a,b}$, $\mathrm{LIVE\_IN}(S_2)={b,c}$, 那么 $\mathrm{LIVE\_OUT}(B)={a,b,c}$. + +用一个 CFG 走一遍会更清楚: + +```text + B1 + / \ + v v + B2 B3 + \ / + v v + B4 +``` + +对应代码为: + +```text +B1: + v1 = load a + v2 = load b + if cond goto B2 else B3 + +B2: + v3 = v1 + v2 + goto B4 + +B3: + v3 = v1 - v2 + goto B4 + +B4: + v4 = v3 * 2 + return v4 +``` + +暂时假设 `cond` 是进入 `B1` 之前已经存在的 value. 对 `B4`, 返回以后没有继续需要保留的 virtual register, 所以 $\mathrm{LIVE\_OUT}(B4)=\varnothing$. `B4` 在定义 `v4` 之前需要 `v3`, 因而 $\mathrm{LIVE\_IN}(B4)={v3}$. + +`B2` 和 `B3` 的唯一 successor 都是 `B4`, 所以它们的 live-out 都是 `{v3}`. 两个 blocks 都会在内部重新定义 `v3`, 同时读取 `v1` 和 `v2`, 因而它们的 live-in 都是 `{v1,v2}`. `B1` 的两个 successors 入口都需要 `v1` 和 `v2`, 所以离开 `B1` 时这两个 values 都必须保留. `B1` 本身定义 `v1` 和 `v2`, 因而进入 `B1` 之前只需要 `cond`. + +如果 CFG 没有环, 按适当顺序传播这些集合通常很快就能得到结果. Loop 会形成循环依赖. 一个 loop header 的 live-in 可能影响 back edge predecessor 的 live-out, 后者又继续影响 loop header. 因此编译器通常从空集开始反复应用数据流方程, 直到所有集合都不再变化. + +```text +initialize LIVE_IN and LIVE_OUT to empty sets + +repeat: + for each block B: + new_out = union of LIVE_IN of B's successors + new_in = USE[B] union (new_out - DEF[B]) + + update LIVE_IN[B] and LIVE_OUT[B] + +until no set changes +``` + +这个过程会达到 fixed point. 函数中的 relevant values 数量有限, 每个 live set 也只是这个有限集合的子集. 在标准 liveness analysis 中, 信息从空集开始单调传播, 一个 value 加入某个集合以后, 只有有限种状态可供继续扩展, 所以迭代最终会稳定. + +工业实现通常使用 worklist 避免反复扫描完全不受影响的 blocks. 对 backward analysis 来说, 如果某个 block 的 `LIVE_IN` 改变, 真正可能因此需要重新计算的是它的 predecessors. 选择合适的遍历顺序也会影响收敛速度, 但不会改变 fixed point 的语义结果. + +## 3 Instruction-level Liveness 与 Live Range + +Basic block 边界上的 liveness 只是第一步. 寄存器分配通常还需要知道一条具体机器指令前后有哪些 values live. 得到 $\mathrm{LIVE\_OUT}(B)$ 后, 可以从 block 尾部向前逐条扫描. 对普通指令 $I$, 有 $LiveBefore(I)=Use(I)\cup(LiveAfter(I)-Def(I))$. + +考虑: + +```text +1: v1 = load a +2: v2 = load b +3: v3 = v1 + v2 +4: v4 = v3 * v1 +5: store v4 +``` + +从末尾开始, 第 5 条指令之前需要 `{v4}`. 穿过第 4 条指令以后, `v4` 的旧值不需要保留, 但这条指令需要 `v3` 和 `v1`, 所以第 4 条之前是 `{v1,v3}`. 再穿过第 3 条, `v3` 被该指令定义, 而 `v1`, `v2` 是 operands, 所以第 3 条之前是 `{v1,v2}`. 继续向前可以得到完整结果: + +```text + live before + +1: v1 = load a {} + | + | {v1} + v + +2: v2 = load b {v1} + | + | {v1, v2} + v + +3: v3 = v1 + v2 {v1, v2} + | + | {v1, v3} + v + +4: v4 = v3 * v1 {v1, v3} + | + | {v4} + v + +5: store v4 {v4} + | + | {} +``` + +这里可以直接看到物理寄存器复用发生在哪里. `v2` 在第 3 条指令完成以后已经死亡, 所以它占据的寄存器随后可以交给 `v3`. `v3` 在第 4 条指令读取以后也不再需要, 如果目标指令允许 result 覆盖某个已经死亡的 operand, 还可以进一步复用同一个 physical register. + +真实 machine instruction 内部有时还需要更细的位置划分. 普通三地址指令可以粗略看成先读取 uses, 再产生 defs, 但 two-address instruction, tied operand 和 early-clobber 会让 def/use 边界更加敏感. 例如: + +```text +R0 = ADD R0, R1 +``` + +旧 `R0` 是 input, 新 `R0` 是 output. Allocator 必须知道旧值什么时候读完, 新值什么时候可以开始覆盖同一个物理存储. LLVM 的 `SlotIndex` 就是用更细的 machine positions 表示这种关系, 后面讨论 LLVM LiveIntervals 时会再看它的具体设计. + +把一个 value 所有 live 的程序位置收集起来, 就得到它的 live range. 在直线代码中可以简单画成: + +```text +instruction: +1 2 3 4 5 6 + +v1: + |----------------| +``` + +CFG 中的 live range 则是一组控制流位置, 不一定适合看成一根连续的横线. 某个 value 可能只在一个分支上需要保持: + +```text + B1 + / \ + / \ + B2 B3 + | | + live dead + \ / + \ / + B4 +``` + +因此 live range 首先是控制流语义上的对象. 只有把机器程序的 positions 线性编号之后, 才会得到便于 Linear Scan 或其他 allocator 使用的 interval representation. + +## 4 Live Interval, Segment 与 Lifetime Hole + +假设机器程序已经建立线性位置编号, 某个 value 在 `[4,12)` 和 `[20,28)` 两段位置 live. 可以表示成: + +```text +v1: +[4, 12) [20, 28) +``` + +这两个连续区域通常称为 segments. 中间不 live 的部分是 lifetime hole. 一个现代 `LiveInterval` 因而可以包含多个 segments, "interval" 这个名字并不意味着它只能表示一个单独的数学区间. + +Live range 和 live interval 可以从抽象层次上区分. Live range 表示 value 在 CFG 上所有需要保持的程序位置. Live interval 是 allocator 为这些位置建立的线性化数据结构. 如果算法只保留最早 definition 和最后 use, 把整个生命周期粗略表示成一个 `[start,end)`, 实现会很简单, 但也会丢掉 holes. + +例如: + +```text +v1: |--------| |--------| + +v2: |--------| +``` + +`v2` 正好位于 `v1` 的 lifetime hole 中. 两个 values 在这些位置上可以共享物理寄存器. 如果把 `v1` 粗略表示成: + +```text +v1: |----------------------------| +``` + +allocator 就会认为 `v1` 和 `v2` 发生了整段 overlap, 从而产生不必要的资源冲突. + +Linear Scan 的高级版本因此会维护 multiple segments 和 inactive intervals. LLVM Greedy 同样依赖精细的 live interval information 来判断物理寄存器冲突和选择 splitting points. 与之相对, 经典 Chaitin-style allocator 会进一步把这些位置信息压缩成 interference graph, 只保留两个 allocation objects 是否曾经发生过冲突. + +Liveness 也直接决定 register pressure. 如果某个位置同时 live 的 values 是 `{a,b,c,d}`, 并且四个 values 都竞争同一个 register class, 那么这一位置至少产生 4 个寄存器单位的需求. 如果 target 只有三个可用寄存器, allocator 就需要通过 spilling, splitting, rematerialization 或其他变换降低实际寄存器占用. Instruction scheduling 改变 definitions 和 uses 之间的距离时, live ranges 也会随之伸长或缩短, 因而 register pressure 和 RA 从来没有完全脱离代码调度. + +下一步把 liveness 转换成 interference relation时, allocator关心的就是哪些 values 曾经在同一个程序位置同时需要相同物理资源. Graph coloring 会把这种关系记录成边, Linear Scan 和 LLVM Greedy 则更直接地利用 live interval overlap. 两种路线的数据结构不同, 但它们都建立在这一部分得到的生命周期信息上. |