# 改进干涉图节点

首先需要说明，目前的框架中尚未做这个改进，不过做起来也不太难，也许未来框架中会加上。

课堂上，以及上一章中，我们都将干涉图节点定义为虚拟寄存器。这其实并不是最优的，考虑下面这个程序：

```c
void foo(int n) {
  int i;
  for (i = 0; i < n; i = i + 1) {
    // ...
  }
  for (i = 0; i < n; i = i + 1) {
    // ...
  }
}
```

虽然在两个循环中都使用`i`作为循环变量，但是这两个`i`其实是没有任何关系的。按照我们的翻译策略，自始至终都会以同一个虚拟寄存器来表示`i`，这样与`i`冲突的节点将包括两个循环中的虚拟寄存器。然而，如果这样改写程序：

```c
void foo(int n) {
  int i1, i2;
  for (i1 = 0; i1 < n; i1 = i1 + 1) {
    // ...
  }
  for (i2 = 0; i2 < n; i2 = i2 + 1) {
    // ...
  }
}
```

这样与分别`i1`和`i2`冲突的节点都只包括一个循环中的虚拟寄存器。不难想象，修改后的程序构造出来的干涉图将更加容易着色。如果我们要在不修改程序的情况下，让第一个程序达到和第二个程序一样的效果，就必须允许在不同的程序点上，同一个虚拟寄存器使用不同的物理寄存器，也就是说干涉图节点不应该定义为虚拟寄存器。

我们引入**生命周期**的概念，一个生命周期由一个变量的定值点，以及所有这个定值活跃的程序点的集合组成。一个定值在一点活跃定义为：这个定值可以到达这里，并且这一点处定值的变量活跃。根据这个定义，不难设想生命周期的计算方式：先进行到达-定值分析和活跃变量分析，然后对于每个定值点，寻找所有这个定值可以到达并且定值的变量活跃的程序点。

我们希望能够对于每个生命周期分配一个物理寄存器，而不是为每个虚拟寄存器分配一个物理寄存器。为了达成这一点还需要做一点修正，考虑这个程序片段：

```c
int a;
if (b) {
  a = ...;
} else {
  a = ...;
}
// use a
```

按照上面的定义，`a`的两次定值会形成两个生命周期，它们可以使用不同的物理寄存器。但是这是不对的，因为下面的`a`的使用点处只能使用一个确定的物理寄存器。为了避免这样的情况发生，需要进行生命周期的合并：如果同一个虚拟寄存器的两个生命周期发生了重叠，那么这两个生命周期需要被合并为一个，让它们只能使用同一个物理寄存器。

至此，干涉图的定义可以修改为：干涉图的节点是(合并后的)所有生命周期，如果两个生命周期有重叠，就在两个节点间连一条边。除了干涉图的定义之外，算法的其它部分不需要有任何变化。

对于修改前的例子，`i`总共有4个定值点(假设循环体内只使用`i`，没有给`i`定值)，两个`for`中的`i = 0`和`i = i + 1`对应的生命周期会被合并成一个(因为它们在循环体内有重叠)，从而总共有两个生命周期，它们在寄存器分配时作为两个独立的节点，这样就和修改后的例子效果完全一样了。