如果变量在后面的代码中不再被引用, 在生存期内, 它的寄存器可以被编译器挪为他用吗?

当然可以。寄存器分配器就是干这活儿的。

呃，

大大先回答了那我写点啥好…

卧槽，码着码着字

大神也先回答了。算了先写了多少发多少占了坑再说。

他们俩的答案都说得很对：寄存器不是绑在变量上的，而且物理寄存器经常不够用所以有可能会spill。

下面我想写写有一定优化的编译器中，寄存器分配器的初步知识。

各种各样的编译器取舍都不同，

最偷懒的根本就没有寄存器分配器，所有局部变量直接映射到栈上；

稍微不那么偷懒的可能会用一些局部信息挑几个局部变量映射到寄存器上，其它的映射到栈上，而且全部都是固定映射（一个寄存器或栈槽只用于映射一个变量）；

再多做一点可能会分析一下变量的生存期再分配寄存器；

再更多做一点可能会拆分变量、合并变量啥的再分配寄存器…

我就说说“普通”的做法吧，不太偷懒也不太复杂的。

=========================================================

首先要把题主的问题拆成几部分：

• 虚拟寄存器？物理寄存器？
• 变量的生存期有多长？
• 源语言层面的变量？IR层面的变量？
• 变量是否有被分配到寄存器？有的话，是作为一个整体被分配到一个寄存器，还是分段被分配到多个寄存器？
• 已经分配给一个变量的寄存器，能否在后面再被分配给别的寄存器。

然后分别回答：

1、虚拟寄存器与物理寄存器

编译器IR有可能分为多层：

• 其中较高层（比较抽象）的IR可能没有虚拟寄存器的概念，只有变量的概念；
  
• 而较底层（比较具体、更贴近目标机器）的IR可能没有变量的概念，只有虚拟与物理寄存器的概念。此时“虚拟寄存器”可以有无限多个，但最终得要被映射到目标机器上有限多个物理寄存器上。
  

虚拟寄存器跟变量的概念其实还是很相似，只不过前者更侧重于跟目标机器相关的属性（例如目标机器层面的类型，是分配到物理寄存器上还是分配到栈上了，等），而后者更侧重于跟源语言相关的属性（例如语言层面的类型）。

那么从较高层IR转换为较底层IR的过程中，“变量”的概念就会先被映射为“虚拟寄存器”的概念，然后再由寄存器分配器将虚拟寄存器映射到物理寄存器上。

（所谓“物理寄存器”就是目标机器的ISA所支持的寄存器，倒不一定真的是硬件里底层实现的真的寄存器——中间可能还有

、

之类的有趣的事情，这里不用关心那么细节，只看ISA层面就好。）

假设题主关心的是如果变量分配到了物理寄存器上，这个寄存器能否被复用于别的变量。

2、变量的生存期

一个变量的作用域（scope）是这个变量可以被使用的范围。对拥有静态/词法作用域的编程语言来说，这个范围可以从源码看出来，例如说使用块作用域的C++粗略的看：

//          Scopes for variables:  a  b  c  d  e  f
int foo(int a, int b, int c) { //  x  x  x
  int d = a + 1;               //  x  x  x  x
  {                            //  x  x  x  x
    int e = 2;                 //  x  x  x  x  x
  }                            //  x  x  x  x
  {                            //  x  x  x  x
    int f = 3;                 //  x  x  x  x     x
  }                            //  x  x  x  x
  return b + d;                //  x  x  x  x
}

（“粗略”是因为我只标记到行的粒度；实际的作用域在行内也有分割，例如d的作用域从声明的赋值符号左边开始，而不包括赋值符号右边——不能写 int d = d + 1;）

注释里右边的x表示变量在作用域内。很明显e和f的作用域不重叠。

有编译器通过作用域信息来决定寄存器分配的。

例如说Java的源码编译器javac。如果把JVM看作目标机器，它的“局部变量区”其实就跟寄存器类似，可以通过名字/标号随机访问。javac在把Java源码编译到字节码时，可以让同一个local variable slot复用给多个局部变量，只要这些局部变量的作用域没有重叠。请参考我之前一个演示稿的例子：

，第82-91页的例子。

同样的思路当然也可以应用在针对有真实硬件的目标机器来分配寄存器。

对编译器来说，还有另外一个跟“作用域”有点相关但是不一样的概念，叫做“生存期”（live range），或者更正统的译法是“活跃期”；也可称为“生命区间”（lifetime interval）。

作用域关注的是一个变量允许被使用的合法范围，而生存期关注的是一个变量实际被使用的范围。

继续用前面的例子，

//     Live ranges for variables:  a  b  c  d  e  f
int foo(int a, int b, int c) { //  x  x  x
  int d = a + 1;               //  x  x     x
  {                            //     x     x
    int e = 2;                 //     x     x  x
  }                            //     x     x
  {                            //     x     x
    int f = 3;                 //     x     x     x
  }                            //     x     x
  return b + d;                //     x     x
}

可以看到例中变量的生存期普遍有比作用域小的倾向。这是根据定义能推导出来的：变量的生存期必然是其作用域的子集，或者说作用域是生存期的上限。

那这“生存期”要咋定义呢？一种定义是：一个变量的生存期从它第一次被定义（赋值）开始，到它最后一次被使用为止。

（这是为了简化说明而特别用不太准确的定义方式，为了避开对控制流相关的讨论。

更准确的定义方式是：

一个变量v在程序中某个位置P是存活的，如果变量v的某次定义有一条路径能到达P而且路径上v没有被重新定义，并且从P有一条路径能到达v的一个使用。这里的路径是控制流图意义上的路径，本文偷懒避开讨论控制流。）

根据这个定义再重新看看上面的例子：

//     Live ranges for variables:   a   b   c   d   e   f
int foo(int a, int b, int c) { //   d   d  d/e
  int d = a + 1;               //  u/e  |       d
  {                            //       |       |
    int e = 2;                 //       |       |  d/e
  }                            //       |       |
  {                            //       |       |
    int f = 3;                 //       |       |      d/e
  }                            //       |       |
  return b + d;                //      u/e     u/e
}

这里d表示定义（Definition），u表示使用（Use），/e表示生存期结束（end），|表示变量活着但此处没有被使用。

这样可以明确的看到，

参数c与局部变量e、f都在刚定义之后生存期就结束了，这是因为它们的定义都没有被使用过。这些就是典型的“无用变量”（dead variable）；

参数a在函数入口出得到定义，进来之后被用了一次生存期就结束了；

参数b和局部变量d的生存期一直坚持到函数临返回的地方，但中间有一大块范围是没有被使用的，也就是说生存期有“空洞”。

要计算出生存期，涉及的动作叫做活跃分析（liveness analysis）。

写到这里题主可能也发现了：这种“生存期”的定义保证了一个变量最后一次使用位置就是其生存期的结束位置，不多不少。所以题主的原始问题看起来就会有点奇怪。要进一步拆分为两种角度猜测题主真正想问的问题：

• 变量的生存期内，其分配的寄存器有没有可能被挪为它用；
• 变量的生存期后，其分配的寄存器有没有可能被复用。

还好，无论是哪个角度，答案都是：可能。具体看后文的例子。

通常的做法，编译器的寄存器分配不是对源语言上的“变量”分配寄存器，而是对变量的“生存期”来分配寄存器。

3、源语言层面的变量与IR层面的变量

上面的例子都只讨论了变量只被赋值了一次的情况。那变量被赋值了多次要怎么处理呢？

有两种常见办法：

• 编译器IR层面的“变量”允许被多次赋值。此时IR里的“变量”跟源语言层面的变量大致还是一回事；
• 编译器IR层面的“变量”只允许单次赋值。这种IR称为“静态单赋值形式”（SSA，Static Single Assignment）此时IR里的“变量”就跟源语言层面的变量不太一样了。

举个新的例子，如果IR层面的变量允许多次赋值的话，

// Live ranges for variables:  a   b
int foo(int a, bool b) {  //  d/e  d
  a = 2;                  //  d/e  |
  if (b) {                //      u/e
    a = 3;                //   d
  } else {                //   |
    a = 4;                //   d
  }                       //   |
  return a;               //  u/e
}

留意到此处变量a的生存期并不是完整的一条，而是分段的：每次定义（赋值）产生一段生存期，到该定义被最后一次使用为止；每当变量被重新定义，之前的定义就死掉了，所以每个新定义都会导致生存期被分段。

如果IR是SSA形式的，IR层面的变量不允许多次赋值，源码在转换为IR时就要做变量重命名，变成：

// Live ranges for variables:  a0   a1   a2   a3   a4   b
int foo(int a0, bool b) {  //  d/e                      d
  a1 = 2;                  //       d/e                 |
  if (b) {                 //                          u/e
    a2 = 3;                //            d
  } else {                 //            |
    a3 = 4;                //            |    d
  }                        //            |    |
  a4 = phi(a2, a3);        //            u/e  u/e  d
  return a4;               //                      u/e
}

可以看到源语言中的参数a被拆分成了多个变量，拆分后的变量每个只有一次赋值，并且各自有独立的生存期。分支中的赋值，在分支合并（控制流合并）的地方用phi函数把多个可能的定义聚合为一个新定义。

放个传送门：

这两种形式的IR可以直接交给寄存器分配器去处理，也可以做进一步处理之后再给寄存器分配器。

一种可能的处理是：SSA形式的IR，先退出SSA回到普通形式再交给寄存器分配器，这样会消除所有phi函数；退出的同时可以尝试做“变量接并”（coalescing），尽量把多个由phi函数关联在一起的变量接并为一个。经过这种处理之后，上面SSA的例子就会变成：

// Live ranges for variables:  a0   a1   a2   b
int foo(int a0, bool b) {  //  d/e            d
  a1 = 2;                  //       d/e       |
  if (b) {                 //                 u/e
    a2 = 3;                //            d
  } else {                 //            |
    a2 = 4;                //            d
  }                        //            |
  return a2;               //            u/e
}

可以看到SSA形式里的a2、a3、a4被合并到了一个变量上，然后a4是phi函数的产物在合并后就不用要了。

a0和a1都是无用变量可以放一边不管。

总结一下这一段：寄存器分配器至少可能看到3种形式的变量/生存期：跟源语言一致的；SSA形式拆分过的；SSA形式拆分后又再接并起来的。

4、变量与寄存器分配

终于写到激动人心的寄存器分配了。好吧其实一点也不激动，前面废话了那么多，能读到这里的同学们辛苦了 >_<

至此读者应该已经习惯了看生存期的记法。为方便举例讨论，下面我们就只看抽象的生存期与寄存器分配，暂时其对应的具体代码放一边——反正寄存器分配器也只关心生存期而不关心变量、运算之类的概念；无论前面IR的形态是怎样的，这里都可以统一用抽象的生存期概念来讨论。

之前的例子都为了迁就代码竖着画生存期，下面为了更好利用空间改为横着画，大家请调整一下习惯再继续。横着画的例子里，每一列对应同一时间的状态。生存期的区间有重叠的被称为“相互干涉”（interfere）。

关键点在于：

• 同时存活（相互干涉）的生存期不能分配到同一寄存器；
• 不同时存活的生存期可以分配到同一寄存器；
  
• 寄存器不够用的话可以把变量的整个或部分生存期分配在栈上。

假如有下面三条生存期v0 - v3，但只有2个物理寄存器r0、r1可分配给它们的话：

v0  d-----------------u
v1    d----------u
v2               d---------u

v1的最后一个使用与v2的定义在同一位置，说明v2的定义与v1的使用是相关的；此时虽然v1的末尾看似与v2的开头重叠，但没关系，还是可以安全的分配到同一个寄存器上。于是可以做出这样的分配：

v0 (r0)  d-----------------u
v1 (r1)   d----------u
v2 (r1)              d---------u

这个例子大概就是题主原本期待的一方面：一个变量分配到得寄存器，后面再被分配给别的变量使用。

再看一例。如果有4条生存期，2个物理寄存器：

v0  d-----------------------u
v1    d--------u
v2             d---------u
v3        d-------u

这4条生存期无论如何也不可能只用两个寄存器就同时存好，所以得做点额外的处理。

寄存器分配器有许多种选择：

• 贪婪分配寄存器给生存期，先来先得，用光了寄存器之后就把剩余的生存期都扔到内存（栈）里。被扔到栈里的生存期既可以说是“分配”到了栈里，也可以说是“溢出”（spill）到了栈里。先来先得也得有个顺序，分配器可以按生存期的起始位置的顺序排序；也可以按生存期使用频度排序，用得多的优先分配；还可以随便挑个啥顺序。这种策略下，上面的例子可以得出：

  v0 (r0)      d-----------------------u
  v1 (r1)        d--------u
  v2 (r1)                 d---------u
  v3 (stack 0)       d-------u

  这样的分配。这就是现在很流行的“线性扫描寄存器分配器”（LSRA，Linear-Scan Register Allocation）的基本思路。
• 可以观察到v0生存期的使用离定义很远，中间一大块时间其实都没被用到，也就是说有空洞。利用这点，寄存器分配器可以进行“生存期拆分”（live-range splitting）。具体要如何拆分是现实种寄存器分配里非常影响性能的地方。下面举一个拆分v0的例子，策略还是跟前面一样贪婪分配，但当遇到有新的生存期分配不到寄存器时，从已经分配到寄存器的生存期种选一个最迟被使用的溢出到内存里；被溢出的生存期到临使用前再试图恢复到寄存器上：

  v0 (r0)      d----s                 ru
     (stack 0)      s*****************r
  v1 (r1)        d--------u
  v2 (r1)                 d---------u
  v3 (r0)            d-------u
  

  s表示“溢出”（spill），r表示“恢复”（restore）。这个例子的意思是v0生存期被新来的v3导致拆分为3段，其中头尾两段在寄存器里，中间一段被“溢出”到栈上暂时存着。这个例子大概就是题主原本期待的另一方面：一个分配到了寄存器的变量，该寄存器可以在该生存期以内被挪为分配给别的变量。
• 还有更激进的拆分策略，例如说先激进拆分再激进合并：先让所有生存期都在定义之后立即溢出到栈上，到临要使用时才恢复到寄存器，这样可以最大限度缩短生存期占用寄存器的时间，保证分配算法能有进展；等分配结束后，再用一趟冗余拷贝消除来把分配到同一个寄存器、中间该寄存器没有被别的生存期占用的生存期片段给固定在寄存器里，把对它的溢出/恢复代码消除掉。这是种比较悲观的做法。
• 还有各种可能性…

前文对“生存期”的描述其实还停留在比较粗的粒度，隐含了一个假设：忽略控制流关系，IR里代码有一个线性顺序，生存期的范围是在这个线性顺序上的范围。

当然可以用更细粒度的方式来考察生存期，例如说精确到控制流图上的每个基本块，或者甚至每条指令层面。那样可以得到更精确的信息，因而可以得出更好的分配，不过实现起来也更复杂。本文就不继续展开讲图着色寄存器分配（Graph-Coloring Register Allocation）相关的内容了。有兴趣的同学可以自己找资料读，或者另外开问题讨论。

大大说建议在回答里添加caller-save寄存器与callee-save寄存器的区别。呃这个回头有兴致再加，本来就已经够长了…

另外，关于简易寄存器分配的做法，请移步传送门：