编译器优化教程：寄存器分配 2

线性扫描接下来介绍一种不同思路的算法：线性扫描。算法描述如下[4]：
linearscanregisterallocation: active := {} for i in live interval in order of increasing start point expireoldintervals(i) if length(avtive) == r spillatinterval(i) else register[i] := a regsiter removed from pool of free registers add i to active, sorted by increasing end pointexpireoldinterval(i) for interval j in active, in order of increaing end point if endpoint[j] >= startpoint[i] return remove j from active add register[j] to pool of free registersspillatinterval(i) spill := last interval in active if endpoint[spill] > endpoint[i] register[i] := register[spill] location[spill] := new stack location remove spill from active add i to active, sorted by increasing end point else location[i] := new stack locationlive interval其实就是变量的生命期，用活跃变量分析可以算出来。不过需要标识第一次出现和最后一次出现的时间点。
举个例子：
图10
变量名live interval
a 1,2
d 2,3,4,5
e 3,4,5,6
llvm中实现在上文中介绍的算法都是作用在最普通的四元式上，但llvm-ir是ssa形式，有phi节点，但phi节点没有机器指令表示，所以在寄存器分配前需要把phi节点干掉，消除phi节点的算法限于篇幅不展开，如感兴趣的话请后台留言。
llvm作为工业级编译器，有多种分配算法，可以通过llc的命令行选项-regalloc=pbqp|greedy|basic|fast来手动控制分配算法。
不同优化等级默认使用算法也不同：o2和o3默认使用greedy，其他默认使用fast。
fast算法的策略很简单，扫描代码并为出现的变量分配寄存器，寄存器不够用就溢出到内存。用途主要是调试。
basic算法以linearscan为基础并对life interval设置了溢出权重而且用优先队列来存储life interval。
greedy算法也使用优先队列，但特点是先为生命期长的变量分配寄存器，而短生命期的变量可以放在间隙中，详情可以参考[5]。
pbqp算法全称是partitioned boolean quadratic programming，限于篇幅，感兴趣的读者请查阅[6]。
至于具体实现，自顶向下依次是：
targetpassconfig::addmachinepasses含有寄存器分配和其他优化addoptimizedregalloc中是与寄存器分配密切相关的pass，比如上文提到的消除phi节点addregassignandrewriteoptimized是实际的寄存器分配算法寄存器分配相关文件在lib/codegen下的regallocbase.cpp、regallocgreedy.cpp、regallocfast.cpp、regallocbasic.cpp和regallocpbqp.cpp等。regallocbase类定义了一系列接口，重点是selectorsplit和enqueue/dequeue方法，数据结构的重点是priority queue。selectorsplit方法可以类比上文中提到的spillatinterval。priority queue类比active list。简要代码如下：void regallocbase::allocatephysregs() { // 1. virtual reg其实就是变量 while (liveinterval *virtreg = dequeue()) { // 2.selectorsplit 会返回一个可用的物理寄存器然后返回新的live intervals列表 using virtregvec = smallvector; virtregvec splitvregs; mcregister availablephysreg = selectorsplit(*virtreg, splitvregs); // 3.分配失败检查 if (availablephysreg == ~0u) { ... } // 4.正式分配 if (availablephysreg) matrix->assign(*virtreg, availablephysreg); for (register reg : splitvregs) { // 5.入队分割后的liver interval liveinterval *splitvirtreg = &lis->getinterval(reg); enqueue(splitvirtreg); } }}至于这四种算法的性能对比，我们主要考虑三个指标：运行时间、编译时间和溢出次数。
图11 各算法的运行时间，图源[6]
横坐标是测试集，纵坐标是以秒为单位的运行时间
图12 各算法的编译时间，图源[6]
横坐标是测试集，纵坐标是编译时间
图13 各算法的溢出次数，图源[6]
从这三幅图可以看出greedy算法在大多数测试集上都优于其他算法，因此greedy作为默认分配器是可行的。
小结我们通过一个例子介绍了活跃变量分析和图着色算法。借助活跃变量分析，我们知道了变量的生命期，有了变量生命期建立干涉图，对干涉图进行着色。如果着色失败，可以选择某个变量溢出到内存中。之后在rig的基础上介绍了寄存器合并这一变换。
然后我们简单介绍了不同思路的寄存器分配算法：linearscan。最后介绍了llvm12中算法的实现并对比了llvm中四种算法的性能差异。
参考http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15745-s18/www/lectures/l5-intro-to-dataflow-pre-class.pdfhttp://web.cecs.pdx.edu/~mperkows/temp/register-allocation.pdfhttp://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15745-s18/www/lectures/l12-register-allocation.pdf http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15745-s18/www/lectures/l13-register-coalescing.pdfhttp://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdfhttp://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.htmlt. c. d. s. xavier, g. s. oliveira, e. d. d. lima and a. f. d. silva, a detailed analysis of the llvm's register allocators, 2012 31st international conference of the chilean computer science society, 2012, pp. 190-198, doi: 10.1109/sccc.2012.29.