全局指令选择

概述

基于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 pass

IRTranslator pass 的作用是将输入LLVM IR 转换为通用机器IR(Generic Machine IR, gMIR)

gMIR 是一种与MIR共用相同数据结构的IR，但其约束更宽松。随着编译过程向前递进，这些约束逐渐收紧，gMIR也由此变成MIR

gMIR 和 MIR 的不同之处在于，MIR主要处理目标指令，只有一个小部分目标无关的操作码，如COPY、PHI和REG_SEQUENCE 等。

而gMIR定义了丰富的通用操作码集合(Generic Opcode)，这些操作码虽然与目标无关，但又是目标可以支持的操作。例如，标量整数加法的通用操作码是G_ADD，其用法如下

%2:_(s32) = G_ADD % 0: _(s32), %1:_(s32)

Legalizer pass

Legalizer 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 pass

RegBankSelect 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 指令选择方法非常相似