概述
基本寄存器分配器是四种寄存器分配器中最简单的寄存器分配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.cpp>
PBQP图中的节点和干扰图的节点都表示虚拟机寄存器,每个节点都有一个关联的代价向量,描述了该节点的每个分配选项的代价
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的定值在基本块0(bb.0) 的指令序号01B处,基本块0在指令序号09B处结束,可得到x的第一段生存期为序号片段[01B, 09B)
x 在基本块2(bb.2) 的指令序号21B处被使用,因此x的第二段生存期为序号片段[20B, 21B)。同理可得到其他生存期分析结果
在LLVM 的 LiveInterval 类定义了寄存器(或值)的生存期,以及部分寄存器分配器状态.LiveInterval 类定义(llvm_root/llvm/include/llvm/CodeGen/LiveInterval.h)
class LiveInterval : public LiveRange {private:SubRange *SubRanges; ///< Single linked list of subregister live ranges.public:const unsigned reg; // the register or stack slot of this interval.float weight; // weight of this interval
其中,成员变量Reg是与生存期对应的寄存器或堆栈槽(stack slot), 成员变量Weight是生存期的溢出权重(spill weight)
溢出权重代表了对应生存期的溢出代价。物理寄存器数量不足的情况下,溢出权重越大的生存期,被从物理寄存器中剔除的可能性越小(因为生存期溢出的代价大)
反之,则越大。LiveInterval 类继承自LiveRange类,LiveRange类代表的变量活跃范围是变量保持活跃的所有程序点集合,而LiveInterval 类代表的变量生存期是从变量的第一次定义到最后一次使用之间的范围,包含变量所有活跃范围的最小子范围(sub-range )
即变量生存期中可以包含多个变量活跃范围。LLVM 中的虚拟寄存器或堆栈槽的活跃性通过LiveInterval 类表示,寄存器分配过程中回使用LiveInterval 类信息判定两个或多个虚拟寄存器在程序的某一个时间点是否会要求同一个物理寄存器
。当这种情况发生,有些虚拟器会被溢出
生存期分析pass实现类LiveIntervals 是 MachineFunctionPass类的子类,其入口函数是LiveIntervals.cpp 是 runOnMahcineFunction(), 代码如下:
bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {....if (!LRCalc)LRCalc = new LiveRangeCalc();// Allocate space for all virtual registers.VirtRegIntervals.resize(MRI->getNumVirtRegs());computeVirtRegs();computeRegMasks();computeLiveInRegUnits();...return true;
}
上述代码中的LiveIntervalCalc 类对象指针LICalc 是 LiveIntervals 类的成员变量
LiveIntervalCalc 类是LiveRangeCalc 类的子类,其作用是计算和修改LiveInterval 对象跟踪的虚拟寄存器活跃性
代码中的VirRegIntervals 也是 LiveIntervals 类的成员变量,其中包含了所有虚拟寄存器计算得到的生存期
生存期分析pass主要调用三个函数: computeVirtRegs() 、computeRegMasks() 和 computeLiveInRegUnits()
computeVirtRegs
computeVirtRegs() 函数遍历每一个虚拟寄存器,并对每个虚拟寄存器调用 createEmptyInterval() 函数,生成LiveInterval 对象引用,保存在VirtRegIntervals 中
如果该寄存器编号对应的是虚拟寄存器,则将LiveInterval 对象的 weight初始值设为0;如果该寄存器编号对应的是物理寄存器,则将LiveInterval 对象的weight 初始值设为 huge_valf,即无穷大
这意味着在后续的寄存器分配过程中,已经分配的物理寄存器不会被剔除。然后,computeVirtRegs() 函数调用computeVirtRegInterval 函数,通过LICalc 对象,基于使用和定值为LiveInterval 对象跟踪的虚拟寄存器计算活跃性
computeRegMasks
computeRegMask() 函数的作用是计算 RegMaskSlots 和 RegMaskBits. 某些指令,如函数调用指令,会篡改(clobber) 寄存器中的值,从而导致这些寄存器失效
寄存器掩码是长度等于寄存器总数的数组,其中的每一位指向一个寄存器。掩护码中值为1的位表示相应物理寄存器(包括其子寄存器)中的内容在函数调用过程中保持不变,值为0的位表示相应物理寄存器中的内容可能被指令篡改
在寄存器分配过程中,通过寄存器掩码能够帮助确定哪些寄存器可以在调用中处于活跃状态,从而优化寄存器在代码中使用。在MachineOperand.h 文件中的机器指令操作数枚举类型MachineOprandType 中定义了枚举常量 MO_RegisterMask , 表示寄存器掩码操作数类型
寄存器掩码操作数不拥有掩码所引用的内存的所有权,但掩护必须在操作数的生命周期内保持有效。LiveIntervals 类的成员变量RegMaskSlots 中保存了带有寄存器掩码操作数的指令列表
成员变量 RegMaskBits 可与 RegMaskSlots 配合使用,RegMaskBits中保存了指向对应寄存器掩码的指针。computeRegMasks() 函数遍历当前MachineFunction 中的所有机器指令及其操作数,并将指令的SlotIndex 和指令操作数的寄存器掩码分别保存在RegMaskSlots数组和RegMaskBits 数组中
computeLiveInRegUnits
computeLiveInRegUnits() 函数的作用的预先计算某个ABI块(ABI block)入口活跃寄存器单元(register unit) 的生存期
ABI块包括入口基本块的所谓的“着陆点”(landing pad)。着陆点是与异常处理相关概念。一般将异常后调用继续执行的位置称为着陆点
LLVM 中的着陆点在概念上可以替代函数入口点,在代码实现中,可以将异常结构引用和类型信息索引作为参数传入着陆点
着陆点保存异常结构引用,然后继续执行与异常对象的类型信息对应的catch块。computeLiveInRegUnits() 函数遍历当前 MachineFunction 中的所有基本块的入口活跃寄存器单元,并基于使用和定值计算这些寄存器单元的活跃范围
溢出权重计算
得到生存期分析结果后,接下来执行贪厌分配器pass,对应下去的寄存器分配步骤
LLVM的贪厌分配器实现类RAGreedy 在枚举类型 LiveRangeStage 中定义了 RS_New、RA_Assign、RS_Split、RS_Split2、RS_Spill、RS_Memory 和 RS_Done 七个枚举常量,分别表示寄存器分配 pass 的各个步骤
- 其中,RS_New 阶段生成生存期并放入优先级队列
- RS_Assign 阶段尝试为优先级队列中的生产期指定物理寄存器,如果不成功,则执行剔除操作,并在RS_Split 阶段将生存期重新放入优先级队列
- RS_Split 阶段尝试切分不能指定物理寄存器的生存期
- RS_Split2 阶段尝试对之前阶段不能指定物理寄存器的生存期做更激进的切分,确保最大限度地利用物理寄存器
- RS_Spill 阶段将始终无法指定寄存器的生存期溢出到存储器,不再尝试切分这些生存期
- RS_Memory 阶段的生存期位于存储器中,也可能因为其他剔除操作,生存期重新被移入物理寄存器
- RS_Done 阶段结束寄存器分配过程
上述某些阶段会对虚拟寄存器做切分,如块切分(Per-block splitting) 、区域切分(Region splitting)、本地切分(Local splitting) 等,并可能生成新的生存期。为了提高性能,在这些阶段生成的生存期在出队列时跳过干扰检查,因为这些生存期是经过切分后产生的,产生干扰的可能性较小
贪厌分配器的第一步骤是根据各个生存期的特点计算相应的溢出权重。溢出权重计算过程在calculateSpillWeightsAndHints() 函数中实现
该函数会被各寄存器分配pass的 runOnMachineFunction() 函数在初始化后调用。LLVM中各寄存器分配pass的工作流程都比较类似。首先,先调用init()函数完成初始化,包括获得用于寄存器分配的TargetRegisterInfo、MachineRegisterInfo等类对象
另外,在该函数中还会调用MachineRegisterInfo 类的 freezeReservedRegs() 函数,使预留寄存器在寄存器分配时不可访问
然后,runOnMachineFunction() 函数调用 calculateSpillWeigthsAndHints() 函数计算溢出权重。在此基础上,各寄存器分配pass 调用 allocatePhysRegs() 函数实现物理寄存器分配功能
最后,调用postOptimization() 函数完成寄存器选择和溢出后的优化。贪厌分配器的 runOnMachineFunction 代码实现如下
bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {initializeCSRCost();VRAI = std::make_unique<VirtRegAuxInfo>(*MF, *LIS, *VRM, *Loops, *MBFI);SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM, *VRAI));VRAI->calculateSpillWeightsAndHints();LLVM_DEBUG(LIS->dump());SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree, *MBFI, *VRAI));IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI);GlobalCand.resize(32); // This will grow as needed.SetOfBrokenHints.clear();allocatePhysRegs();tryHintsRecoloring();if (VerifyEnabled)MF->verify(this, "Before post optimization");postOptimization();reportStats();releaseMemory();return true;
}
其中,指针VRAI 指向 VirtRegAuxInfo 类。其功能是计算虚拟寄存器辅助信息,如溢出权重和分配提示等,其成员函数 calculateSpillWeightsAndHints() 遍历所有虚拟寄存器,并以生存期为参数调用函数 calculateSpillWeigthAndHint() ,为每个寄存器的生存期计算溢出权重。
calculateSpillWeightsAndHints() 和 calculateSpillWeightAndHint()
void VirtRegAuxInfo::calculateSpillWeightsAndHints() {LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"<< "********** Function: " << MF.getName() << '\n');MachineRegisterInfo &MRI = MF.getRegInfo();for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {Register Reg = Register::index2VirtReg(I);if (MRI.reg_nodbg_empty(Reg))continue;calculateSpillWeightAndHint(LIS.getInterval(Reg));}
}void VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &LI) {float Weight = weightCalcHelper(LI);// Check if unspillable.if (Weight < 0)return;LI.setWeight(Weight);
}
calculateSpillWeightAndHint() 函数的主要功能是在其辅助函数 weightCalcHelper() 中实现的
该函数遍历给定虚拟寄存器的所有使用和定值指令(不包含调试指令),针对每一条指令和给定虚拟寄存器,计算不同情况下虚拟寄存器生存期的溢出权重,并将在所有指令上计算得到的溢出权重求和,作为给定虚拟寄存器溢出权重(TotalWeight += Weight)
weightCalcHelper() 函数代码实现如下:
float VirtRegAuxInfo::weightCalcHelper(LiveInterval &LI, SlotIndex *Start,SlotIndex *End) {for (MachineRegisterInfo::reg_instr_nodbg_iteratorI = MRI.reg_instr_nodbg_begin(LI.reg()),E = MRI.reg_instr_nodbg_end();I != E;) {MachineInstr *MI = &*(I++);....float Weight = 1.0f;if (IsSpillable) {// Get loop info for mi.if (MI->getParent() != MBB) {MBB = MI->getParent();Loop = Loops.getLoopFor(MBB);IsExiting = Loop ? Loop->isLoopExiting(MBB) : false;}// Calculate instr weight.bool Reads, Writes;std::tie(Reads, Writes) = MI->readsWritesVirtualRegister(LI.reg());Weight = LiveIntervals::getSpillWeight(Writes, Reads, &MBFI, *MI);// Give extra weight to what looks like a loop induction variable update.if (Writes && IsExiting && LIS.isLiveOutOfMBB(LI, MBB))Weight *= 3;TotalWeight += Weight;}....}// Pass all the sorted copy hints to mri.if (ShouldUpdateLI && CopyHints.size()) {....TotalWeight *= 1.01F;}... // If all of the definitions of the interval are re-materializable,// it is a preferred candidate for spilling.// FIXME: this gets much more complicated once we support non-trivial// re-materialization.if (isRematerializable(LI, LIS, VRM, *MF.getSubtarget().getInstrInfo()))TotalWeight *= 0.5F;if (IsLocalSplitArtifact)return normalize(TotalWeight, Start->distance(*End), NumInstr);return normalize(TotalWeight, LI.getSize(), NumInstr);
}
其中, readsWritesVirtualRegister() 函数返回一对布尔值,表明指令是否为寄存器读写指令(即是否为寄存器使用或定值指令)
/// readsWritesVirtualRegister - Return a pair of bools (reads, writes)
/// indicating if this instruction reads or writes Reg. This also considers
/// partial defines.
std::pair<bool,bool>
MachineInstr::readsWritesVirtualRegister(Register Reg,SmallVectorImpl<unsigned> *Ops) const {bool PartDef = false; // Partial redefine.bool FullDef = false; // Full define.bool Use = false;for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {const MachineOperand &MO = getOperand(i);if (!MO.isReg() || MO.getReg() != Reg)continue;if (Ops)Ops->push_back(i);if (MO.isUse())Use |= !MO.isUndef();else if (MO.getSubReg() && !MO.isUndef())// A partial def undef doesn't count as reading the register.PartDef = true;elseFullDef = true;}// A partial redefine uses Reg unless there is also a full define.return std::make_pair(Use || (PartDef && !FullDef), PartDef || FullDef);
}
readsWritesVirtualRegister()函数后进一步调用 getSpillWeight() 函数,为寄存器读写指令计算基本块频率(block frequency) 与入口频率的相对值
基本块频率是指控制流图中基本块的执行次数。计算基本块频率与入口块频率的相对值目的是以入口块频率为基准,对控制流图中基本块频率做归一化处理,并以此作为指令所在基本块的执行频繁程序的指标
float LiveIntervals::getSpillWeight(bool isDef, bool isUse,const MachineBlockFrequencyInfo *MBFI,const MachineBasicBlock *MBB) {return (isDef + isUse) * MBFI->getBlockFreqRelativeToEntryBlock(MBB);
}
对溢出权重影响最大的是变量使用密度(use density)
。例如,循环中的归纳变量因被频繁使用,使用密度较大,这类变量应尽量不要溢出到内存中,否则严重影响程序效率
因此,对这类变量要额外提升变量。上述代码将循环归纳变量的溢出权重在原有基础增加了两倍(Weigth *= 3)
其他影响溢出权重的因素还包括:是否有提示寄存器(hinted register)、是否可再具体化(rematerializable) 生存期等
。在特定目标机构中,某些指令会有偏好的寄存器,这些寄存器称为提示寄存器
对于这类寄存器,对其溢出权重会做些微提升(totalWeight *= 1.01F)。对于可重物质化生存期,可以作为溢出候选,因为不将其指定给物理寄存器影响不大,值可以重新计算得到
因此,将其对应溢出权重减半(totalWeight *= 0.5F)。对于不能溢出的生存期,例如,已经指定固定物理寄存器的生存期,或者活跃范围非常短的生存期,则不为其计算溢出权重,保持原有权重不变