活跃变量分析

复习

　　寄存器是有限的，而我们想尽量把值放在寄存器里（因为快）。要决定哪些值能共用同一个寄存器，得先知道：每个值在程序的哪些位置还“活着”。 这就是活跃变量分析（liveness analysis）。

　　一个变量在某点是活跃的，意思是：从这一点往后，它的值还会被用到（在被重新赋值覆盖之前）。反过来，如果往后都不会再用它当前的值，它就是“死的”。

　　看个例子：

x = 1
y = 2
用 x        ← 这里 x 活跃；y 从没被用过，一直不活跃
x = 3

　　y = 2 之后，y 再没被用过，所以这段里 y 一点都不“活跃”——它其实是死代码。

　　注意：要判断“现在这个值以后还会不会用”，得看后面的代码。所以活跃变量分析是反向的数据流分析：从程序的出口往回推，一路传播“哪些变量此刻是活跃的”。

　　这和前面“可达定义”那种从前向后传播的方向相反，但套路一样：在控制流图上迭代，直到稳定。 方向换一下，工具还是那套工具。

　　活跃信息把“谁能共用寄存器”这件事说清楚了：

　　于是，“怎样分配寄存器”就转化成了“怎样安排这些活跃区间”。下一章会用一张图，把这个问题画得清清楚楚。

思考题 1

　　“活跃”是什么意思？为什么这个分析是反向的？

思考题 2

　　活跃变量分析为什么是寄存器分配的基础？

　　活跃指某个变量在某点之后、被重新赋值之前，它的值还会被使用。因为要判断“以后还会不会用”，必须看后面的代码，所以分析方向是从出口往入口的反向传播。

　　因为只有知道每个变量在哪些位置“活着”，才能判断哪些变量会同时存活。同时存活的变量不能共用寄存器，只有活跃区间不重叠的才能共享。确定这些之后，才能正确地分配有限的寄存器。

设计师 | 南国微雪