概述基本寄存器分配器是四种寄存器分配器中最简单的寄存器分配pass实现(llvm_root/livm/lib/CodeGen/RegAllocBasic.cpp)但麻雀虽小，五脏俱全，基本寄存器分配器中实现了根据溢出权重确实虚拟寄存器优先级、按优先级分配物理寄存器，以及物理寄存器不足时将虚拟寄存器溢出到内存等功能。因此，基本寄存器分配器非常适合作为自定义寄存器分配器实现参考LLVM3.0 之前的默认寄存器分配器是线性扫描分配器。与线性扫描分配器不同，基本分配器不再以线性顺序访问生存期，而是采用优先队列，以溢出权重降序访问生存期，并通过一组生存期联合(live interval union) 完成干扰检查当无法为生存期分配其寄存器类中的任何物理寄存器时，生存期就会溢出。因为基本分配器以溢出权重递减的顺序为生存期分配物理寄存器，所以生存期联合中的所有干扰生存期(物理寄存器中已有的生存期被称为干扰生存期) 都具有更高溢出权重通过llc命令行选项 -regalloc = basic 可使能基本分配器快速寄存器分配器采用本地分配策略(llvm_root/llvm/lib/CodeGen/RegAllocFast.cpp) 对每个基本块从上往下扫描，当遇到虚拟寄存器时，便为其分配物理寄存器，便为其分配物理寄存器所有物理寄存器分配在基本块级别完成，并尽量长时间地将值保存在物理寄存器中，以便根据需要重用物理寄存器在这种分配方式下，基本块之间没有活跃寄存器。在每个基本块的结束位置，所有未分配物理寄存器的虚拟寄存器都溢出到内存。此策略适用于活跃范围较短的代码。通过llc命令行选项 regalloc = false 可使能快速分配器PBQP 全称 Partitoned Boolean Quadratic Programming, 即分区布尔二次规划，这是一个二次分配问题(Quadratic Assignment Problem, QAP)PBQP 寄存器分配器的工作原理是将PBQP 图视为干扰图的扩展，进而将不规则体系结构的寄存器分配问题映射为PBQP问题，然后使用PBQP求解器求解该问题llvm_root/llvm/lib/CodeGen/RegAllocPBQP.cppPBQP图中的节点和干扰图的节点都表示虚拟机寄存器，每个节点都有一个关联的代价向量，描述了该节点的每个分配选项的代价PBQP 图中的边表示对寄存器分配问题的约束。PBQP图中的边没有类型(这一点与干扰图不同)，而是与一个代价矩阵相关联，这个代价矩阵表示两个节点的成对分配代价，代价矩阵的值决定了与其关联的边对最终解决方案的影响通过llc 命令行选项 -regalloc = pbqp 可使能 PBQP分配器LLVM 3.0 之后新增了基本分配器和贪厌分配器是目前LLVM的默认分配器。因此，贪厌分配器是本节分析的重点。通过llc命令行选项-reglloc = greedy 可使能贪厌分配器和线性扫描分配器相比，贪厌分配器用一个优先级队列取代了线性扫描分配器的活跃性列表(ative list), 并按优先级访问队列的生存期，而不是像线性扫描分配器那样按先后顺序访问而且，贪厌分配器不像基本分配器那样优先为短生存期分配器，而是优先为为长生存期分配物理寄存器。有些函数中的长生存期太多，导致没有足够的物理寄存器容纳其他短生存期。但是将高溢出权重的短生存期溢出的代价太大，因此，可以从生存期联合中剔除已经分配的、低溢出权重的生存期，并将其重新放回优先队列，使用能有第二次被分配到其他寄存器的机会如果待分配的生存期无法找到可以被剔除的干扰生存期，也不会立即溢出，贪厌分配器在此处的另一个改进是在生存期溢出前增加切分步骤，将其切分为更短的生存期并放回优先级队列，这样可以增加生存期被分配到物理寄存器的可能性特别是当切分后的短生存器覆盖的是热点循环时，切分的收益更为明显。自定义寄存器分配pass可参照LLVM中基本寄存器分配pass或贪厌寄存器分配pass实现贪厌寄存器分配实现过程分析在寄存器分配之前，需要做很多准备工作，如指令序号标记、活跃性分析等。LLVM中的活跃性分析主要分为两个部分：在LiveVariable类中实现的活跃性变量分析(live variable analysis) 和 在LiveInterval 类中实现的生存期分配(live interval analyis)这些都是在寄存器分配pass之外的其他pass中完成。贪厌分配器分配pass可以进一步细分为不同步骤，包括:溢出权重计算(apill weight calculation)、生存期入队列(enqueue)、指定物理寄存器(assignment)、剔除生存期(eviction)、生存期切分(splitting)、和生存期溢出(spilling)生存期分析生存期分析不是寄存器分析过程的一部分，而是一个独立的pass。在此之前，SlotIndexes pass 已经为每条指令标记序号。通过检查变量的所有使用和定值，可以分析其生存期因此此时每一条指令都已经有序号，可以将分析得到的生存期用序号片段集合表示。例如，上图中变量x的定值在