全局指令选择

概述基于SelectionDAG 的指令选择方法可以生成质量较高的机器码但代价是开发难度和代码复杂度较高快速指令选择方法复杂度较低但代码质量较差。为了综合二者的优点取长补短LLVM在现有的架构上实现了全局指令选择并希望用全局指令选择取代基于SelectionDAG 的指令选择方法和快速指令选择方法全局指令选择提供了不同于其他两种指令选择方法的可重用pass和功能函数可以完成从LLVM IR到目标机器IR(Machine IR) 的指令选择功能全局指令选择没有引入新的DAG 中间表示而且全局指令选择工作在函数级别可以发掘更多的全局优化机会全局指令选择框架全局指令选择框架包括四个pass: IRTranslator、Legalizer、RegBankSelect、InstructionSelect上述四个pass的实现代码都在路径llvm_root/llvm/lib/CodeGen/GlobalSel/ 下。 LLVM 中的各目标后端没有实现全部的全局指令选择pass部分采用了LLVM 中已有的默认pass各目标后端如需添加全局指令选择pass需要重写后端TargetPassConfig派生类(如AMDPGU 后端的 GCNPassConfig 类) 中的 addIRTranslator()、ddRegBankSelect() 等虚函数并在后端目标机器描述文件TargetMachine.cpp 中通过 addPass() 向 pass管理器中添加全局指令pass例如AMDGPU 后端中添加全局指令选择 pass 的相关代码如下:bool GCNPassConfig::addIRTranslator () { addPass (new IRTranslator (getOptLevel ())); return false; } bool GCNPassConfig:: addLegalizeMachineIR () { addPass (new Legalizer ()) ; return false; } bool GCNPassConfig :: addRegBankSelect () { addPass (new RegBankSelect ()); return false; } bool GCNPassConfig:: addGlobalInstrunctionSelect() { addPass(new InstructionSelect()); return false; }IRTranslator passIRTranslator pass 的作用是将输入LLVM IR 转换为通用机器IR(Generic Machine IR, gMIR)gMIR 是一种与MIR共用相同数据结构的IR但其约束更宽松。随着编译过程向前递进这些约束逐渐收紧gMIR也由此变成MIRgMIR 和 MIR 的不同之处在于MIR主要处理目标指令只有一个小部分目标无关的操作码如COPY、PHI和REG_SEQUENCE 等。而gMIR定义了丰富的通用操作码集合(Generic Opcode)这些操作码虽然与目标无关但又是目标可以支持的操作。例如标量整数加法的通用操作码是G_ADD其用法如下%2:_(s32) G_ADD % 0: _(s32), %1:_(s32)Legalizer passLegalizer pass 的作用是将目标平台不支持的通用机器指令的操作数类型转换为目标机器指令的操作数类型以及转换目标平台不支持的操作Legalizer pass 与 SelectionDAG 的指令选择不同之处在于SelectionDAG的指令选择将操作和类型的合法化分两步完成而Legalizer pass 将其合并为一步Legalizer pass 会自下而上地在 gMIR上迭代地检查指令合法性当碰到非法指令时Legalizer pass 会对其做转换使当前指令在迭代过程中逐步变得合法经过Legalizer pass 处理后gMIR 中的指令操作仍以虚拟寄存器表示因而此时的指令不是纯粹的MIR而是混合机器指令许多处理器硬件中都存在多种类型的寄存器文件不同类型的寄存器文件在物理上是分开的。通常一条机器指令只能访问某一类型的寄存器文件若要在不同类型的寄存器文件之间执行数据操作则必须先将所有数据复制到同一类型的寄存器文件中。寄存器组(register bank)是一组由目标定义的寄存器类通过定义寄存器组可以寄存器分配器时限制某些虚拟寄存器只能使用特定类型的寄存器文件。而且划分寄存器组可减少高成本的跨寄存器组数据搬移操作例如AMDPGU 后端的寄存器按照其用途可分为SGPR(Scalar General Purpose Register) 和 VGPR(Vector General Purpose Register)AMDGPU 后端为不同类型的寄存器定义(llvm_root/llvm/lib/Target/AMDGPU/AMDGPURegisterBanks.td)了不同的寄存器组def SGPRRegBank : RegisterBank SGPR , [SReg_L016 , SReg_32 , SReg_64, SReg_96, SReg_128, SReg_160 , SReg_192 , SReg_256 , SReg_ 512 , SReg_1024]; def VGPRRegBank : RegisterBank VGPR , [ VGPR_L016 , VGPR_HI16, VGPR_32, VReg_64 , VReg_96 , VReg_128 , VReg_160 , VReg_192, VReg_ 256, VReg_512 , VReg_1024];RegBankSelect passRegBankSelect pass 会计算最优寄存器组分配方案并为每条混合机器指令的操作数分配寄存器组当遇到跨寄存器组搬移数据时RegBankSelect pass 还负责插入复制指令。RegisterBankInfo 类中保存了和寄存器组相关的信息并提供了指令与寄存器组映射的相关接口各LLVM后端可根据各自寄存器组定义和用法定义自己的ReigsterBankInfo类并实现copyCost()、getInstrMapping()等相关接口例如ADMGPU后端的 AMDGPURegisterBankInfo类定义如下:class AMDGPUGenRegisterBankinfo : public RegisterBankinfo { protected : fdefine GET TARGET REGBANK CLASS #include AMDGPUGenRegisterBank.inc }; class AMDGPURegisterBankinfo final : public AMDGPUGenRegisterBankinfo ( public: const GCNSubtarget Subtarget; ... unsigned copyCost (const RegisterBank A, const RegisterBank B, unsigned Size) const override; ... const InstructionMapping getInstrMapping (const MachineInstr MI) const override;经过RegBankSelect pass 处理后指令的操作和操作数的类型对于目标都是合法的。这降低了InstructionSelect pass 将混合机器指令转换为目标机器指令的难度但某些目标无关指令如COPY指令会在寄存器分配后才降级。各LLVM后端可根据目标相关的指令选择逻辑实现自己的InstructionSelector类。例如AMDGPU后端的AMDGPUInstructionSelector类定义如下:class AMDGPUinstructionSelector final : public InstructionSelector { private: MachineRegis terinfo *MRI; cons GCNSubtarget *Subtarget ; public : bool select (Machineinstr I) override;其中最重要的函数是select(),其作用是将通用机器指令转换为完全的机器指令。AMDGPU后端的select()函数实现(llvm_root/llvm/lib/Target/AMDGPU/AMDGPUInstructionSelector.cpp) 如下:bool AMDGPUinstructionSelector: :select (MachineInstr I) { ... switch (I.getOpcode()) { case TargetOpcode : : G_ADD : case TargetOpcode : : G_SUB : if (selectlmpl (I, *Coveragelnfo)) return true ; return selectG_ADD_SUB (I) ; default: return selectimpl(I , *Coverageinfo) ; return false ;由上述代码可以看到select()函数可以为某些通用机器指令进行定制化手动匹配并由selectImpl()函数完成大部分通用机器指令选择与SelectionDAG 指令选择手法中的GenDAGISel.inc文件类似TableGen也会根据全局指令选择相关的.td文件生成GenGloballISel.inc 文件 其中包含全局指令选择的匹配表(MatchTable0) 定义和 selectImpl()函数实现在InstructionSelector.cpp 文件中可通过 #include “ GenGloballSel.inc” 将全局指令选择匹配表定义和selectImpl()函数实现嵌入到InstrunctionSelct pass 实现中。 由此可见除了操作和类型的匹配方式外全局指令选择方法与当前的SelectionDAG 指令选择方法非常相似总结虽然LLVM 已经实现全局指令选择但若要在llc中启用全局指令选择还需在llc命令中增加-global-isel选项另一个和全局指令选择相关的llc命令行选项是-global-isel-abort. 当该选项值为0时llc会在全局指令选择方法失败时将SelectionDAG指令选择方法为回退方法。当该选项值为1时llc会在全局指令选择方法失败时直接报错