LLVM中四种寄存器分配算法及开启选项

在LLVM编译器中，一共有四种寄存器分配算法：Basic Register Allocator、Fast Register Allocator、PBQP Register Allocator、Greedy Register Allocator。

Fast Register Allocator

这种分配器是局部的，作用于各个基本块，它尽量地将值保持在寄存器中并重用它们。

Basic Register Allocator

核心算法是线性扫描算法的变种，而 basic 分配器可以理解为一个简化版的 greedy 分配器。

PBQP Register Allocator

这种方法将寄存器分配映射为分区布尔二次规划（PBQP: Partitioned Boolean Quadratic Programming）问题。一个PBQP解决方法用于将这个问题的结果映射回寄存器

Greedy Register Allocator

核心算法是线性扫描算法的变种，并且Greedy是新版本 LLVM 默认的寄存器分配器，如果编译选项没有额外设置，在-O2以上会使用greedy，在其他情况会使用fast。

开启选项：

-regalloc=<regalloc_name>选项。可选的<regalloc_name>有：pbqp，greedy，basic，和fast。

示例：

clang   -regalloc=greedy test.c  -o test

但是要注意的是，如果用clang -regalloc=pbqp时，会报错说不存在pbqp寄存器分配算法，所以要使用pbqp算法可以采用下面的方法

clang -S  -emit-llvm test.c  -o test.ll
llc -filetype=obj  -regalloc=pbqp test.ll  -o test.o
clang test.o -o test_pbqp

另外，图着色法也是我们熟知的一种寄存器分配算法，但是LLVM 至始至终就没有考虑过图着色法。虽然图着色生成的代码质量很高，关注的是尽量减少溢出，但是对于大型程序中，由于寄存器有限，大量溢出是不可避免的，所以llvm认为关注如何高效地溢出比如何尽量减少溢出更有意义。