LLVM编译器后端比较功能的添加

LLVM编译器后端的主要工作是将LLVM中间端表达式（IR）转换成汇编文件，Cpu0 是一个非常简单的 RISC 架构处理器，本文以Cpu0作为硬件的例子，来构建能适配它的编译器后端。

兴智开发者社区小助理

23人浏览 · 2023-07-20 16:03:52

兴智开发者社区小助理 · 2023-07-20 16:03:52 发布

1.动机

从机器层面上来看，控制流类的跳转指令分为无条件跳转和有条件跳转，无条件跳转 JMP，有条件跳转 JEQ、JNE、JLT、JGT、JLE、JGE，这部分指令是需要通过检查 condition code （SW 寄存器）来决定跳转条件；J 类型指令依赖的 condition code 是通过比较指令（比如 CMP）的结果来设置的。如下图所示，JNE跳转指令通过检查SW寄存器的状态以决定是否发生跳转。因此，为了支持控制流功能，首先要打通比较功能。

2.LLVM IR 中的比较指令

LLVM IR提供的 int 类型比较指令为 icmp。其接受三个参数：比较方案以及两个比较参数。

  %result = icmp ule i32 %a, %b

ule是比较方案，其中 u 为 unsigned int，le 为 lower than or equal，%a和%b就是用来比较的两个数，而icmp则返回一个i1类型的值，用来表示结果是否为真。

与ule类似的比较方案有多种，如：

等于与不等于：eq、ne；
无符号比较：ugt、uge、ult、ule，分别对应无符号的大于、大于等于、小于、小于等于；
有符号比较：sgt、sge、slt、sle，分别对应有符号的大于、大于等于、小于、小于等于。

3.实现比较功能的添加

3.1 定义format

class FA<bits<8> op, dag outs, dag ins, string asmStr,
         list<dag> pattern, InstrItinClass itin>
  : Cpu0Inst<outs, ins, asmStr, pattern, itin, FrmA>
{
  bits<4>  ra;
  bits<4>  rb;
  bits<4>  rc;
  bits<12> shamt;

  let Opcode = op;

  let Inst{23-20} = ra;
  let Inst{19-16} = rb;
  let Inst{15-12} = rc;
  let Inst{11-0}  = shamt;
}

rb、rc为两个寄存器类型源操作数，用于存放比较的数据，ra为寄存器类型目的操作数，用来存放比较的结果。

class FL<bits<8> op, dag outs, dag ins, string asmStr,
         list<dag> pattern, InstrItinClass itin>
  : Cpu0Inst<outs, ins, asmStr, pattern, itin, FrmL>
{
  bits<4>  ra;
  bits<4>  rb;
  bits<16> imm16;

  let Opcode = op;

  let Inst{23-20} = ra;
  let Inst{19-16} = rb;
  let Inst{15-0}  = imm16;
}

rb为寄存器类型源操作数，用于存放比较的数据，imm16是用于比较的16位立即数，ra为寄存器类型目的操作数，用来存放比较的结果。

3.2 定义指令

class SetCC_R<bits<8> op, string instrAsm, PatFrag condOp,
              RegisterClass RC>
  : FA<op, (outs GPROut:$ra), (ins RC:$rb, RC:$rc),
       !strconcat(instrAsm, "\t$ra, $rb, $rc"),
       [(set GPROut:$ra, (condOp RC:$rb, RC:$rc))],
       IIAlu>, Requires<[HasSlt]> {
  let shamt = 0;
}
def SLT      : SetCC_R<0x28, "slt", setlt, CPURegs>;
def SLTu     : SetCC_R<0x29, "sltu", setult, CPURegs>;

SetCC_R继承自上面定义的FA 。SLT、SLTu对应着小于、无符号小于两种比较方案

class SetCC_I<bits<8> op, string instrAsm, PatFrag condOp, Operand Od,
              PatLeaf immType, RegisterClass RC>
  : FL<op, (outs GPROut:$ra), (ins RC:$rb, Od:$imm16),
       !strconcat(instrAsm, "\t$ra, $rb, $imm16"),
       [(set GPROut:$ra, (condOp RC:$rb, immType:$imm16))],
       IIAlu>, Requires<[HasSlt]>;

class FMem<bits<8> op, dag outs, dag ins, string asmStr, list<dag> pattern,
           InstrItinClass itin>
  : FL<op, outs, ins, asmStr, pattern, itin> {
  bits<20> addr;
  let Inst{19-16}   = addr{19-16};
  let Inst{15-0}    = addr{15-0};
  let DecoderMethod = "DecodeMem";
}
def SLTi     : SetCC_I<0x26, "slti", setlt, simm16, immSExt16, CPURegs>;
def SLTiu    : SetCC_I<0x27, "sltiu", setult, simm16, immSExt16, CPURegs>;

SetCC_I继承自上面定义的FL 。SLTi、SLTiu对应着立即数小于、立即数无符号小于两种比较方案。

3.3 定义Pattern

上述四条指令只提到了小于、无符号小于两种比较方案，另外的比较方案没有定义。针对这种指令集中没有定义的比较方案需要借助Pattern定义。

指令选择过程就是DAG的模式匹配过程，模式的定义其主要在td文件中进行描述。当一个匹配找到后，将其DAG中的Node替换为具体的机器指令或伪指令。所以td文件中的Pattern的定义对于指令选择起到至关重要的作用。

每一个Pattern记录继承自 Pat class，其有两个参数，第一个参数DAG图中待匹配的模式，第二个参数是一个由机器指令组成DAG，当一个 Pattern 匹配后，将使用第二个参数替换第一个参数。以大于和大于等于为例，比较方案的模式定义如下：

大于(setgt、setugt)

multiclass SetgtPatsSlt<RegisterClass RC, Instruction SLTOp, Instruction SLTuOp> {
  def : Pat<(setgt RC:$lhs, RC:$rhs),
  // a > b is equal to b < a is equal to setlt(b, a)
            (SLTOp RC:$rhs, RC:$lhs)>;
  def : Pat<(setugt RC:$lhs, RC:$rhs),
            (SLTuOp RC:$rhs, RC:$lhs)>;
}

defm : SetgtPatsSlt<CPURegs, SLT, SLTu>;

大于等于(setge、setuge)

multiclass SetgePatsSlt<RegisterClass RC, Instruction SLTOp, Instruction SLTuOp> {
  def : Pat<(setge RC:$lhs, RC:$rhs),
  // a >= b is equal to b <= a
            (XORi (SLTOp RC:$lhs, RC:$rhs), 1)>;
  def : Pat<(setuge RC:$lhs, RC:$rhs),
            (XORi (SLTuOp RC:$lhs, RC:$rhs), 1)>;
}

defm : SetgePatsSlt<CPURegs, SLT, SLTu>;

4.测试 (以大于为例)

测试用例

int test_setxx()
{
  int a = 5;
  int b = 3;
  int c;

  c = (a > b);   // sgt, c = 1

  return (c);
}

LLVM IR

 %a = alloca i32, align 4
  %b = alloca i32, align 4
  %c = alloca i32, align 4
  store i32 5, i32* %a, align 4
  store i32 3, i32* %b, align 4
  %0 = load i32, i32* %a, align 4
  %1 = load i32, i32* %b, align 4
  %cmp = icmp sgt i32 %0, %1
  %conv = zext i1 %cmp to i32
  store i32 %conv, i32* %c, align 4
  %2 = load i32, i32* %c, align 4
  ret i32 %2
}

指令选择前后的DAG

汇编

test_setxx:
 .frame $fp,16,$lr
 .mask  0x00000000,0
 .set noreorder
 .set nomacro
# %bb.0:                                # %entry
 addiu $sp, $sp, -16
 addiu $2, $zero, 5
 st $2, 12($sp)
 addiu $2, $zero, 3
 st $2, 8($sp)
 ld $2, 12($sp)
 ld $3, 8($sp)
 cmp $sw, $3, $2
 andi $2, $sw, 1
 st $2, 4($sp)
 ld $2, 4($sp)
 addiu $sp, $sp, 16
 ret $lr
 nop
 .set macro
 .set reorder
 .end test_setxx
$func_end0:
 .size test_setxx, ($func_end0)-test_setxx
                                        # -- End function

5.总结

LLVM编译器后端的主要工作是将LLVM中间端表达式（IR）转换成汇编文件，Cpu0 是一个非常简单的 RISC 架构处理器，本文以Cpu0作为硬件的例子，来构建能适配它的编译器后端，主要讲述了比较指令在整个控制流当中的作用并梳理了在LLVM后端中添加比较功能的过程。在编译器后端的开发过程中有一定的参考作用。可能存在认知上的偏差，也请大佬多多指教，笔者也会在学习中一步步改正错误，欢迎交流技术心得。