2019-05-12

LLVM的指令映射机制分析

1. 什么是指令映射

本文介绍LLVM中的指令映射机制，以及AMDGPU backend如何为目标平台实现指令映射。本文中的指令映射不是指令选择过程中将IR指令匹配到td文件定义的机器指令，那应该称为指令匹配，匹配操作的中间媒介是MatcherTable。本文介绍的指令映射其目的是为了支持在不同的优化中切换不同指令格式，例如支持硬件架构演进过程中不同版本的ISA，或者不同格式指令之间的映射，映射操作的中间媒介是关系表。二者的对比如下图所示。LLVM开源后端代码中AMDGPU、PowerPC、X86、ARM等均用到指令映射。本文以AMDGPU后端为例，说明LLVM指令映射的用法。

AMDGPU 后端中（参考文献2）支持的产品型号定义在枚举变量Generation中，包括：

enum Generation {
	R600 = 0,
	R700 = 1,
	EVERGREEN = 2,
	NORTHERN_ISLANDS = 3,
	SOUTHERN_ISLANDS = 4,
	SEA_ISLANDS = 5,
	VOLCANIC_ISLANDS = 6,
	GFX9 = 7
};

支持的Subtarget定义在SIEncodingFamily中，

def SIEncodingFamily {
  int NONE = -1;
  int SI = 0;
  int VI = 1;
  int SDWA = 2;
  int SDWA9 = 3;
  int GFX80 = 4;
  int GFX9 = 5;
}

subtargetEncodingFamily函数定义了产品型号到Subtarget的映射：

static SIEncodingFamily subtargetEncodingFamily(const GCNSubtarget &ST)
{
  switch (ST.getGeneration()) {
    default: break;
    case AMDGPUSubtarget::SOUTHERN_ISLANDS:
    case AMDGPUSubtarget::SEA_ISLANDS:
    return SIEncodingFamily::SI;
    case AMDGPUSubtarget::VOLCANIC_ISLANDS:
    case AMDGPUSubtarget::GFX9:
    return SIEncodingFamily::VI;
    }
  llvm_unreachable("Unknown subtarget generation!");
}

由上述代码可见，目前AMDGPU后端支持的subtarget只有SI和VI，因此，AMDGPU后端并没有实现全部Subtarget的实际指令。

2. InstrMapping类

TableGen使用关系模型做指令之间的映射。这些模型以InstrMapping类为基础描述指令之间的映射。每个模型会根据需要指令的独特关系设置InstrMapping类的各个域。在编译过程中，TableGen会解析所有关系模型，使用模型中的信息构造关系表将指令相互联系起来。这些关系表和表的查询方法会被编译到XXXInstrInfo.inc文件中。

InstrMapping类定义在Target.td文件中，定义如下：

class InstrMapping {
  string FilterClass;
  list<string> RowFields = [];
  list<string> ColFields = [];
  list<string> KeyCol = [];
  list<list<string> > ValueCols = [];
}

其中，FilterClass域规定了各指令类的基类，可减少使用关系模型的指令的搜索空间。RowFields域规定了关系表中在同一行的所有指令必须保持相同的属性。ColFields域规定了关系表中在同一列的所有指令必须保持相同的属性，这里仅规定了属性名称。KeyCol域规定了关键指令的ColFields域的属性值，这个属性值实际上就是关系表的关键指令，关键指令会被关系表转换成其它指令，这些指令在ValueCols域中规定。

为了建立AMDGPU中伪指令和实际指令之间的映射关系，第一步是定义关系模型。AMDGPU后端中定义了多个关系模型，伪指令和实际指令之间的关系模型是getMCOpcodeGen（定义如下），并通过为InstrMapping中的各个域指令适当的值，将伪指令和实际指令格式关联起来。TableGen根据关系模型会生成对应的关系表。getMCOpcodeGen模型的关系表是getMCOpcodeGenTable。在这个关系表中，伪指令是关键指令，因为要用伪指令Opcode为关键字查询接口方法。

def getMCOpcodeGen : InstrMapping {
    let FilterClass = "SIMCInstr";
    let RowFields = ["PseudoInstr"];
    let ColFields = ["Subtarget"];
    let KeyCol = [!cast<string>(SIEncodingFamily.NONE)];
    let ValueCols = [[!cast<string>(SIEncodingFamily.SI)],
                      [!cast<string>(SIEncodingFamily.VI)],
                      [!cast<string>(SIEncodingFamily.SDWA)],
                      [!cast<string>(SIEncodingFamily.SDWA9)],
                      [!cast<string>(SIEncodingFamily.GFX80)],
                      [!cast<string>(SIEncodingFamily.GFX9)]];
}

其中，let FilterClass ="SIMCInstr";表示关系模型中的所有指令都以SIMCInstr类为基类，搜索空间只局限在这类指令中。let RowFields =["PseudoInstr"];表示对于关系表中的伪指令和实际指令，它们的PseudoInstr域必须相同。let ColFields =["Subtarget"];表示关系表中在同一列的所有指令的Subtarget必须相同。let KeyCol =[!cast<string>(SIEncodingFamily.NONE)];表示关系表的关键指令列（第一列）是伪指令。let ValueCols = [[!cast<string>(SIEncodingFamily.SI)],...表示关系表在关键指令列之后还有六列，第一列是SI 实际指令，第二列是VI实际指令，依次类推。

以下仅以AMDGPU 后端中的部分伪指令和实际指令为例说明。伪指令类定义如下：

class SM_Pseudo <string opName, dag outs, dag ins, string asmOps, list<dag> pattern=[]> : InstSI <outs, ins, "", pattern>, SIMCInstr<opName, SIEncodingFamily.NONE> {
  ...
  multiclass SM_Pseudo_Loads<string opName, RegisterClass baseClass, RegisterClass dstClass> {
  def _IMM : SM_Load_Pseudo <opName, (outs dstClass:$sdst), (ins baseClass:$sbase, i32imm:$offset, i1imm:$glc), $sdst, $sbase, $offset$glc, []> {
    let offset_is_imm = 1;
    let BaseClass = baseClass;
    let PseudoInstr = opName # "_IMM";
    let has_glc = 1;
  }

  def _SGPR : SM_Load_Pseudo <opName, (outs dstClass:$sdst), (ins baseClass:$sbase, SReg_32:$soff, i1imm:$glc), $sdst, $sbase, $offset$glc, []> {
    let BaseClass = baseClass;
    let PseudoInstr = opName # "_SGPR";
    let has_glc = 1;
  }
}

伪指令S_LOAD_DWORD定义如下：

defm S_LOAD_DWORD : SM_Pseudo_Loads <"s_load_dword", SReg_64, SReg_32_XM0_XEXEC>;

SI实际指令类定义如下：

class SMRD_Real_si <bits<5> op, SM_Pseudo ps> : SM_Real<ps>, SIMCInstr<ps.PseudoInstr, SIEncodingFamily.SI>, Enc32 {
  ...
  multiclass SM_Real_Loads_si<bits<5> op, string ps, SM_Load_Pseudo immPs = !cast<SM_Load_Pseudo>(ps#_IMM), SM_Load_Pseudo sgprPs = !cast<SM_Load_Pseudo>(ps#_SGPR)> {
    def _IMM_si : SMRD_Real_si <op, immPs> {
      let InOperandList = (ins immPs.BaseClass:$sbase, smrd_offset_8:$offset, GLC:$glc);
    }
    def _SGPR_si : SMRD_Real_si <op, sgprPs> {
      let InOperandList = (ins sgprPs.BaseClass:$sbase, SReg_32:$offset, GLC:$glc);
    }
  }
}

实际指令S_LOAD_DWORD_IMM_si和S_LOAD_DWORD_SGPR_si定义如下：

defm S_LOAD_DWORD : SM_Real_Loads_si <0x00, "S_LOAD_DWORD">;

上述各类之间的关系总结如下图所示：

注意到上述伪指令类（如SM_Pseudo ）或实际指令类（如SMRD_Real_vi和SMRD_Real_si）都是以SIMCInstr为基类。TableGen以SIMCInstr作为过滤标准为getMCOpcodeGen函数选择指令。不是派生自SIMCInstr类的指令在映射时都不会被getMCOpcodeGen函数考虑。RowFields的域值”PseudoInstr”在这里起到连接伪指令类和实际指令类的作用。也就是说，针对不同subtarget的伪指令类，必须和实际指令类具有相同的”PseudoInstr”。如果希望在关系表中增加新版本的指令，这些指令定义必须包含PseudoInstr等相关信息。

3. 关系表结构

TableGen使用关系模型产生关系表getMCOpcodeGenTable（如下所示）。getMCOpcodeGen的第一个输入参数Opcode是伪指令的Opcode，同时也是关系表getMCOpcodeGenTable的第一列。以指令”S_LOAD_DWORD”为例，其伪指令”S_LOAD_DWORD_IMM”的Opcode为AMDGPU::S_LOAD_DWORD_IMM，si和vi的实际指令分别为S_LOAD_DWORD_IMM_si和S_LOAD_DWORD_IMM_vi，各自位于关系表getMCOpcodeGenTable的第二列和第三列。简言之，getMCOpcodeGenTable的第一列是各Subtarget共用的伪指令Opcode，其后的每一列对应一个Subtarget的MCOpcode，这样就可以将伪指令定义与实际指令定义对应起来。因为AMDGPU后端没有为所有Subtarget实现实际指令，因此第三列之后的列数值都为”(uint16_t)-1U”，表示未实现。

查询函数getMCOpcodeGen在TableGen生成的AMDGPUGenInstrInfo.inc文件中，定义如下：

int getMCOpcodeGen(uint16_t Opcode, enum Subtarget inSubtarget) {
  static const uint16_t getMCOpcodeGenTable[][8] = {
  ...
  /*17946*/
  { AMDGPU::S_LOAD_DWORD_IMM, AMDGPU::S_LOAD_DWORD_IMM_si,AMDGPU::S_LOAD_DWORD_IMM_vi, (uint16_t)-1U, (uint16_t)-1U,(uint16_t)-1U, (uint16_t)-1U },
  ...
  /*41134*/
  { AMDGPU::V_XOR_B32_sdwa, (uint16_t)-1U, (uint16_t)-1U, AMDGPU::V_XOR_B32_sdwa_vi, AMDGPU::V_XOR_B32_sdwa_gfx9,(uint16_t)-1U, (uint16_t)-1U },
  }; // End of getMCOpcodeGenTable
  ...
}

关系表getMCOpcodeGenTable中共有3189（41134 – 17946 + 1）项，各项按伪指令Opcode从小到大排序。查询时以二分法查找Opcode对应的Subtarget实际指令MCOpcode，如下代码所示：

unsigned mid;
unsigned start = 0;
unsigned end = 3189;
while (start < end) {
  mid = start + (end - start)/2;
  if (Opcode == getMCOpcodeGenTable[mid][0]) {
    break;
  }
  if (Opcode < getMCOpcodeGenTable[mid][0])
    end = mid;
  else
    start = mid + 1;
}
if (start == end)
  return -1; // Instruction doesn't exist in this table.

按照输入参数Opcode找到对应的伪指令后，根据输入参数inSubtarget返回对应MCOpcode。

if (inSubtarget == Subtarget_0)
  return getMCOpcodeGenTable[mid][1];
if (inSubtarget == Subtarget_1)
  return getMCOpcodeGenTable[mid][2];
if (inSubtarget == Subtarget_2)
  return getMCOpcodeGenTable[mid][3];
if (inSubtarget == Subtarget_3)
  return getMCOpcodeGenTable[mid][4];
if (inSubtarget == Subtarget_4)
  return getMCOpcodeGenTable[mid][5];
if (inSubtarget == Subtarget_5)
  return getMCOpcodeGenTable[mid][6];
return -1;

作者: 汪岩

来源: zhuanlan.zhihu.com/p/55807207

LLVM的指令映射机制分析

1. 什么是指令映射

2. InstrMapping类

3. 关系表结构

最新文章

归档