LLVM Backend Practices - Part 1

PostEncoderMethod

Background

一般情况下我们对于指令encoding采取传统的在指令定义的tablegen文件里，设置好指令的field mapping即可，如果新一代指令集有新指令，则定义新的Inst和fieldmap类即可。

在实际项目中，我们遇到过这种情况：架构演进过程中，每代之间指令功能变动不大，但指令encoding变动频繁，此外encoding采取的并不是顺序编码，而是逐bit的映射，目的是为了获取一定的指令shrink机会，即可变长指令。这里先不展开讨论shrink，而是着重讨论我们是如何解决encoding问题的。

Solution

解决方案整体上可以一句话概括：自动代码生成 + LLVM基础设施中的PostencodeMethod hook

Code Auto-gen

  1. 针对每一代架构指令集，定义一张大表，可以是csv表格或其他便于非研发人员编辑与研发人员读取的格式均可，这个表格中定义每一个指令field对应encoding的比特位序列。

  2. 读取表格，针对每一类相同编码规则的指令，自动生成形似下述代码的encoder methods。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unsigned XXXInst1PostEncoder(const MCInst &MI, unsigned EncodedValue, const MCSubtargetInfo &STI) {
  
  ...

  return EncodedValue;
}

unsigned XXXInst2PostEncoder(const MCInst &MI, unsigned EncodedValue, const MCSubtargetInfo &STI) {
  
  ...

  return EncodedValue;
}


LLVM Infrastrcture - PostEncoderMethod

LLVM tablegen类Instruction中包含成员PostEncoderMethod，对需要使用postencoder的指令类绑定相应的method，即可完成绑定，例如ARM架构中的类似代码：

1
2
3
4
5
6
7
8
class NDataI<dag oops, dag iops, Format f, InstrItinClass itin,
             string opc, string dt, string asm, string cstr, list<dag> pattern>
  : NeonI<oops, iops, AddrModeNone, IndexModeNone, f, itin, opc, dt, asm, cstr,
          pattern> {
  let Inst{31-25} = 0b1111001;
  let PostEncoderMethod = "NEONThumb2DataIPostEncoder";
  let DecoderNamespace = "NEONData";
}

这里为NDataI这类指令，绑定了一个Post encoder method，用于在code emitting时对encoding进行修改。

Shrink

Shrink操作并不少见，很多可变长指令集都有对encoding的shrink操作，即在指令编码阶段，根据指令集编码的定义，允许按照一定规则将指令编码进一步缩短。根据指令集特点，会有不同的shrink策略。当然也有一些架构代码中定义了类似shrink的pass，会做一些target specific的指令替换或立即数优化，这与我们工作中遇到的shrink不相同，以下会称之为“某架构”。

某架构最长支持128bit，最短32bit编码，指令各个field根据一些经验和profiler数据，将编码的bit位分布在不同的dword上，并且会给这些域定义一个缺省值，这样就可以根据128bit中4个dword的u32值来判断某条指令实际是否会占据更高32bit的bit位，从而帮助编译器判断是否可以做shrink。

根据以上描述，编译器会根据某条指令初始编码中的4个u32值，是否为默认值，来判断最短可以shrink到几个dword，并且在实际占据的若干个dword的最后一个的最后一位上，设置一个endbit，即简单设为1，舍去后续的encoding，即可完成shrink。

Inlined ptx/asm Impl

llvm有支持inline对应架构的asm汇编的基础设施，具体是定义一个继承MCAsmInfo类，做一些简单的配置和注册即可初步使能inline asm，当然前提是指令定义是tablegen中要定义好每个指令对应的汇编格式。以AMDGPU为例：

  • 定义并配置
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31

    AMDGPUMCAsmInfo::AMDGPUMCAsmInfo(const Triple &TT,
                                     const MCTargetOptions &Options) {
      CodePointerSize = (TT.getArch() == Triple::amdgcn) ? 8 : 4;
      StackGrowsUp = true;
      HasSingleParameterDotFile = false;
      
      MinInstAlignment = 4;

      
      
      MaxInstLength = (TT.getArch() == Triple::amdgcn) ? 20 : 16;
      SeparatorString = "\n";
      CommentString = ";";
      InlineAsmStart = ";#ASMSTART";
      InlineAsmEnd = ";#ASMEND";

      
      UsesELFSectionDirectiveForBSS = true;

      
      HasAggressiveSymbolFolding = true;
      COMMDirectiveAlignmentIsInBytes = false;
      HasNoDeadStrip = true;
      
      SupportsDebugInformation = true;
      UsesCFIWithoutEH = true;
      DwarfRegNumForCFI = true;

      UseIntegratedAssembler = false;
    }
  • 注册
    1
    2
    3
    4
    5
    extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeAMDGPUTargetMC() {
    ...
      RegisterMCAsmInfo<AMDGPUMCAsmInfo> X(*T);
    ...
    }

那么inline ptx怎么做呢？其实也可以利用该机制，将ptx视为某个非ptx target所能识别的汇编，但要自定义ptx汇编语句的lexer、parser，并将inlined ptx codegen成llvm ir，所以这就要求将这个特殊的inlined asm处理的pass加在llvm ir阶段。

由于ptx其实功能非常繁多，直接generate成llvm ir，ir builder的开发量会比较大，并且有一些ptx指令功能其实是比较复杂的，因此我们也可以在llvm ir生成过程中，通过将ptx指令逻辑用c语言实现，放进libdevice库中，而在ir builder时直接生成libdevice function的call inst即可一定程度上提高实现的效率。同样，这也要求我们把pass加在llvm ir阶段，并且在always inliner之前，这样可以让libdevice function call自动inline。

这个实现方案有一个限制，就是编译器不太好区分是inline ptx还是inline native asm，此时需要牺牲掉inline ptx的语法检查功能，将无法解析的inline汇编语法认为是inline native asm，交给下一步inline native asm去处理。