Chapter 10: Liveness Analysis
如果变量不同时活跃，可以把他们映射到同一个寄存器上，减少寄存器使用
How
- 在语句 n 之后有哪些 statements -> 画 control flow graph
- 变量 x 在这些是、 statements 中被使用了吗 -> 分析 statement
Example:
Flow Graph Terminology
Definitions
- out-edges: lead to successor nodes
- in-edges: come from predecessor nodes
- pred[n]: all the predecessors of node n（前序结点）
- succ[n]: the set of successors of node n（后序结点）
- def(variable) = 定义了该变量的结点集合
- def(node) = 该结点定义的变量的集合
- use(x) 同理
live-in 和 live-out
- live - 变量 x 在 边上活跃，意味着有直接路径到 use(x)，且不经过任何 def(x)
- live-in - 某个变量在一个结点的每条入边上都活跃，则称该变量在该节点上 live-in
- live-out - 每条出边上都活跃
- in[n] - 结点 n 入口活跃的变量集合
- out[n] - 结点 n 出口活跃的变量集合
Calculation of Liveness
Rules
- \(a\in in[m]\)，m 是 n 的后继结点，则 \(a\in out[n]\)
- \(a\in use[n]\)，\(a\in in[n]\)
- \(a\in out[n]\)，\(a\notin def[n]\)，则 \(a\in in[n]\)
每次迭代用上面的公式更新每个结点，直到不动点
从后往前，先算 out
Discussion
优化：
- Basic block 作为结点
- 串行计算
表示 in 和 out 集合
- Bit array - 适合变量稠密，每一时刻有大量变量活跃
- Sorted Lists - 适合稀疏集合
复杂度分析
- 每个集合操作 - O(N)
- 最坏情况 - O(N^4)
- 实际上 O(N) - O(N^2)
Conservative Approximation
停机问题的引理 - 我们不知道执行时一个标签是否能到达
- Dynamic liveness - a 在 node n Dynamic live 意味着有可能的执行路径经过 n 使用 a，且不经过 a 的定义
- Static liveness - a 在 node n Static live 意味着有控制流图的路径经过 n 使用 a，且不经过 a 的定义
Dynamic live 一定 static live
Interference Graphs
- interference：阻止临时变量 a，b 分配到同一寄存器的条件
- 生存范围重合
- a 的产生不能用寄存器 r1
- MOVE 不一定冲突
添加冲突边的规则
- 对于不是 MOVE 的结点 n，定义了 a，out[n] = {b1, ..., bj}，添加冲突边 (a, b1), ..., (a, bj)
- 对于 MOVE 结点 n，a:=c，out[n] = {b1, ..., bk}，如果 bi 不等于 c，添加冲突边 (a, b1), ..., (a, bk)
如果变量定义后从未使用，不需要放入寄存器，但是定义的语句会执行，副作用可能会产生冲突边