3.2
活跃性分析

uncover_live编译遍执行 活跃性分析 ，即它发现在程序的不同区域中使用的变量。一个变量或寄存器，如果它的当前值在之后的某点处被使用，则在其当前程序点处是 活跃 的。我们将变量、栈单元和寄存器统称为 位置 。考虑下面的代码段，其中有两个对b的写入。变量a和b是否同时活跃？

答案是否定的，因为a从第1行到第3行是活跃的，而b从第4行到第5行是活跃的。第2行写入b的整数从未被使用，因为它在下一次读取（第5行）之前被覆盖（第4行）。

通过从后向前遍历指令序列（即按执行顺序向后遍历），可以计算每条指令的活跃位置。设 I ₁ , …, I _n 为指令序列。对于指令 I _k 之后的一组活动位置，写入 L _after （ k ），对于指令 I _k 之前的一组活动位置，写入 L _before （ k ）。建议使用图3.3中描述的Racket集合数据结构来表示这些集合。

一条指令之后的活跃位置构成其 live-after 集合，指令之前的活跃位置构成其live-before集合。一条指令的live-after集合始终与下一条指令的live-before集合相同。

首先，在最后一条指令之后没有活跃位置，因此

然后，我们重复应用以下规则，从后向前遍历指令序列。

其中 W （ k ）是指令 I _k 写入的位置， R （ k ）则是指令 I _k 读取的位置。

jmp指令有一种特殊情况。在jmp之前活跃的位置应该是 L _before 中跳转目标处的位置。因此，我们建议维护一个名为label->live的属性表，将每个标号映射到其块中第一条指令的 L _before 。目前，x86 _Var 程序中唯一的jmp是跳转到收尾部分（参见图3.1）。收尾部分读取rax和rsp，因此该属性表应该将标号conclusion映射到集合{rax, rsp}。

我们走一遍前面的例子，从代码段第5行的指令开始从后向前应用这些公式。我们收集了图3.4所示的答案。指令addq b, c的 L _after 是∅，因为它是最后一条指令（公式（3.2））。该指令的 L _before 是{b, c}，因为它读取变量b和c（公式（3.3））：

L _before （5）=（∅-{c}）∪{b, c}={b, c}

继续第4行的指令movq $10, b，我们将第5行指令的live-before集合复制为该指令的live-after集合（公式（3.1））：

L _after （4）={b, c}

该传送指令写变量b，但没有读取任何变量，因此有如下的live-before集合（公式（3.3））：

L _before （4）=（{b, c}-{b}）∪∅={c}

指令movq a, c的live-before集合是{a}，因为它写位置{c}，并且读位置{a}（公式（3.3））。指令movq$30, b的live-before集合是{a}，因为它写一个非活跃变量，并且没有读取变量。最终，指令movq$5, a的live-before集合是∅，因为它写变量a。

习题3.1 手工对图3.1中的运行示例进行活跃性分析，计算每条指令的live-before集合和live-after集合。将你的答案与图3.5所示的解答进行比较。

习题3.2 实现编译遍uncover_live。将live-after集合序列存储在Block结构的 info 字段中。建议创建一个辅助函数，该函数接受指令列表和初始的live-after集合（通常为空），并返回live-after集合列表。建议创建辅助函数来计算出现在 arg 中的位置集，计算指令读取的位置（ R 函数），以及指令写入的位置（ W 函数）。callq指令应该在其写入集 W 中包含所有调用者保存的寄存器，因为调用约定指出，在函数调用期间可以写这些寄存器。同样，callq指令应该在其读取集 R 中包含适当的参数传递寄存器，这取决于被调用函数的参数个数。（这就是callq的抽象语法包含参数个数的原因。）