LLVM Toy RISC-V Backend

实现 LLVMInitializeToyTarget.

RegisterTargetMachine 会设置 TheTarget 的 TargetMachineCtorFn, 使得 TheTarget->createTargetMachine 返回 ToyTargetMachine 实例.

LLVMInitializeToyTargetMC 会设置一个回调函数, 这些回调会由 initAsm 时通过 TheTargt 的 createXXX 调用以初始化 TheTarget 的 MRI, MII, STI, AsmInfo 等.

• MRI

  MCRegisterInfo

  寄存器的编号, 名字等, 主要信息由 td 生成

• MII

  MCInstrInfo

  指令的编码, 名字等, 主要信息由 td 生成

• STI

  MCSubtargetInfo

  subtarget 对应调用 llc 时指定的 `-mcpu`, `-mattr` 等信息. llc 会用这些信息调用 STI 对应的回调函数以初始化 STI.

  subtarget 的信息是由 td 生成的

• AsmInfo

  MCAsmInfo

  需要包含一些 asm 文件的格式信息, 例如 comment 对应的 `#` 符号

在定义 STI 时使用了 td 文件, td 文件需要在 cmake 中指定 tablegen 命令的参数以及生成头文件的名字, 例如

set(LLVM_TARGET_DEFINITIONS Toy.td)
tablegen(LLVM ToyGenSubtargetInfo.inc -gen-subtarget)
add_public_tablegen_target(ToyCommonTableGen)

表示 td 的入口是 Toy.td, 使用 `-gen-subtarget` 生成 ToyGenSubtargetInfo.inc

通过 ToyTargetMachine 的 createPassConfig 函数, 注册一个 ToyDAGToDAGISel pass, 后者继承自 SelectionDAGISel, 需要实现一个 `Select` 函数做为 isel 的入口. 这里的 Select 函数直接调用了 td 根据 patten 生成的 SelectCode 函数. tablegen 的 `gen-dag-isel` 需要 td 中定义一个 RegisterClass

ToyInstPrinter 继承自 MCInstPrinter, 需要实现 printInst, printRegName, printOperand 等函数. 它会使用 tablegen 的 `-gen-asm-writer` 生成的函数例如 printInstruction, getRegisterName 等

ToyAsmPrinter 操作的是 MachineInstr, 它需要实现 emitStartOfAsmFile, emitFunctionBodyStart, emitInstruction 等, 其中 emitInstruction 需要转换 MachineInstr 到 MCInstr, 然后通过 MC 调用到 ToyInstPrinter

AsmPrinter 会使用 TargetLoweringObjectFile 决定各种数据所在的 section

ToyTargetMachine 需要实现 getSubtargetImpl 返回一个 ToySubtaget, 后续 isel 相关的功能例如 getRegisterInfo, getInstrInfo, getFrameLowering, getTargetLowering 都需要由 subtarget 提供

TargetLowering 在 SelectionDAGBuilder 阶段会被调用, 用来生成最初的 SelectionDAG. 虽然最初的 SelectionDAG 基本是 target 无关, 但涉及到函数调用及其参数, 返回值的处理时需要 target 提供 TargetLowering 类, 并实现 LowerReturn 等函数

ToyFrameLowering 需要实现 emitPrologue 和 emitEpilogue, 它们由 PEI (prologue epilogue insertion) 这个 pass 调用.

emitPrologue 会获取 stack size, 然后通过 BuildMI 生成 MachineInstr 来调整 sp. 另外它还会生成 dwarf cfi directive.

PEI 操作的是 MachineInstr, 它发生成 scheduling 和 RA 之后, 因为 RA 之后才知道 stack size

写一个最简单的 ToyInstrInfo.td, 它会把 immediate 这个 pattern 转换为 Toy::ADDI, 并且把用于访问局部变量的 frameindex 转换为 Toy::STORE

===== Instruction selection begins: %bb.0 ''

ISEL: Starting selection on root node: t5: ch = store<(store (s32) into %ir.1)> t0, Constant:i32<255>, FrameIndex:i32<0>, undef:i32
ISEL: Starting pattern match
Creating constant: t7: i32 = TargetConstant<0>
  Morphed node: t5: ch = STORE<Mem:(store (s32) into %ir.1)> Constant:i32<255>, TargetFrameIndex:i32<0>, TargetConstant:i32<0>, t0
ISEL: Match complete!

ISEL: Starting selection on root node: t1: i32 = Constant<255>
ISEL: Starting pattern match
  Initial Opcode index to 51
Creating constant: t9: i32 = TargetConstant<255>
  Morphed node: t1: i32 = ADDI Register:i32 $physreg1, TargetConstant:i32<255>
ISEL: Match complete!

ISEL: Starting selection on root node: t0: ch,glue = EntryToken

===== Instruction selection ends:
Selected selection DAG: %bb.0 'foo:'
SelectionDAG has 7 nodes:
    t1: i32 = ADDI Register:i32 $physreg1, TargetConstant:i32<255>
    t0: ch,glue = EntryToken
  t5: ch = STORE<Mem:(store (s32) into %ir.1)> t1, TargetFrameIndex:i32<0>, TargetConstant:i32<0>, t0

ToyRegisterInfo 需要实现 `getCalleeSavedRegs` 等函数, 后续 RA, PEI 等会使用它

storeRegToStackSlot 需要生成 MachineInstr, 把 reg (例如 RA) 保存到栈上

PEI 会调用 eliminateFrameIndex 把使用了 frameindex 的 MachineInstr (例如 `STORE ra, addr, 0`) 修改成 `STORE ra, sp, N`.

eliminateFrameIndex 需要根据 frameindex 的值以及 stack_size 计算出正确的偏移量, 然后修改 MI 的 operand, 把原来的 (addr, 0)替换成 (sp, offset)

AsmPrinter 可以重写许多 emit 函数, 例如 emitFunctionBodyStart 等, 但这些都为默认的实现. 但 emitInstruction 是 target 必需实现的.

emitInstruction 的功能是把 MachineInstr 转换为 MCInst, 然后交给 MCStream, 后者会调用到 MCInstPrinter 中的接口, 例如 printInst

ToyInstPrinter 需要使用 td 生成的信息来实现 printInst, printRegName 等

添加 store/add/and/or/andi/ori 指令. 由于目前不涉及到 object 文件的生成, 所以去掉了 td 中关于指令格式的内容.

添加指令时 patten 可以有两种写法:

1. 写在 Instruct 的 patten 中, 例如:

   def LOAD : ToyInst<(outs GPR:$ra), (ins mem:$addr), "lw \t$ra, $addr",
             [(set GPR:$ra, (load AddrFI:$addr))],
             IIAlu>;
   

2. 使用 Pat, 例如:

   def LOAD : ToyInst<(outs GPR:$ra), (ins mem:$addr), "lw \t$ra, $addr", [], IIAlu>;
   
   def : Pat<(load AddrFI:$addr),
             (LOAD  AddrFI:$addr)>;
   

定义 ADD, DIV, REM, … 时有许多重复的内容, 可以使用 td 的 class 简化这些指令的定义

目前 toy 还不支持 global address, 所以编译下面的程序会报错:

$> cat toy_test/test.c
int x = 0;
void foo() {
    int l = x;
}

$> ./toy_test.sh

LLVM ERROR: Cannot select: t4: i32,ch = load<(dereferenceable load (s32) from
@x)> t0, GlobalAddress:i32<ptr @x> 0, undef:i32

对于 global address 的处理发生成 legalize 阶段, ToyTargetLower 需要通过 `setOperationAction` 标记 ISD::GlobalAddress 的 action 为 custom, 同时实现 LowerOperation 来处理这个 node: 生成 `add (lui %hi(x)) %lo(x))` 对应的 node

前面的 LowerOperation 把 global address lower 成了 ISD:ADD, 实际上可以直接 lower 成 Toy::ADDI, 省略后续 isel 时 ISD::ADD 到 Toy::ADDI 的过程. 由于 isel 的输入可能是 machine code, 所以 ToyDAGToDAGISel 的 Select 需要忽略掉 SDNode 已经是 machine code 的情况

前面 LUI 转换成 MacineInstr 后它的 MachineOperand 是 MO_GlobalAddress. ToyMCInstLower 的 LowerOperand 需要把它 lower 成 MCOperand.

这个 MCOperand 的 kind 既不是 register, 也不是 immediate, 因此需要定义ToyMCExpr, 做为 MCOperand 的 expr.

ToyMCExpr 保存着原始的 imm 和 kind (hi/lo) 信息. ToyInstPrinter 会调用到 ToyMCExpr::printImpl 最终根据它保存的 kind 打印出 `%hi` 和 `%lo`

前面的代码不支持全局变量的赋值, 因为缺少 `store $rs1, $rs2` 这个 pattern

return 语句需要通过 ToyISelLowering::LowerReturn 处理. 这个过程发生在最初的 SelectionDAGBuilder 阶段.

LowerReturn 需要分析需要 return 的值, 生成一些指令把这些值按调用约定处理 (放在寄存器, 放在栈上), 最后还生成一个 ToyISD::Ret.

目前的 LowerReturn 只处理了 return void 的情况

ToyISD::Ret 使用了自带的 PseudoInstExpansion 机制, 后者会使用 tablegen 生成和 ToyMCInstLower 类似的代码, 把 Toy::Ret lower 成 JALR 对应的 MCInst.

如果不考虑生成 obj, 也可以直接 def RET : InstI<(outs),(ins), "jalr zero,0(ra)", [(ToyRET)], IIAlu>;, 这样使用默认的 ToyMCInstLower 就可以处理.

当前生成的代码是错误的, 例如:

$> cat test.c
void foo() {
    int x = 1;
    int y = x;
    int z = y;
}

$> ./toy_test.sh
foo:                                    # @foo
# %bb.0:
        addi    t0, zero, 1
        sw      t0, 8(sp)
        lw      t0, 8(sp)
        sw      t0, 4(sp)
        lw      t0, 4(sp)
        sw      t0, 0(sp)
        jalr zero, 0(ra)

foo 的入口需要有 `addi sp, sp, -12`, 称为 prologue foo 的返回前需要有 `addi sp, sp, 12`, 称为 epilogue

其中 `8` 是 stack size, 取决于:

1. 是否保存 fp, 如果有 fp 且没有使用 omit-frame-pointer 则需要保存
2. 是否保存 ra, 如果函数不是 leaf function 则需要保存
3. 是否保存 callee saved reg (CSR), 如果函数使用了它们, 则需要保存和恢复
4. 局部变量占用的栈空间
5. …

emitPrologue 本身并不负责 CSR 的 spill 和 restore, 它们由 PEI 负责 (spillCalleeSavedRegs)

emitPrologue 发生在 schedule 及 RA 之后, 所以它们操作的是 MachineInstr 和物理寄存器

epilogue 与 prologue 对应, 但如果函数不需要返回, 则不需要 epilogue (参考 ToyInstrInfo.td 中的 `isReturn = 1`)

call 需要 ToyISelLowering::LowerCall 来处理, 它负责按调用约定处理函数调用的参数 (例如放在特定物理寄存器或放在栈上), 然后生成跳转指令, 并处理函数返回的结果 (例如从特定物理寄存器或栈上获得结果)

当前的实现只生成了跳转指令, 所以只能支持 `void foo()` 类型的函数调用

CSR 需要保存的前提是函数不是 leaf function, 通过设置 td 中 CALL 指令 `isCall = 1` 让 llvm 知道函数 `hasCalls()`

由于 RA 寄存器 并非由 register allocator 分配, 所以需要重写 determineCalleeSaves, 把 RA 加到 SavedRegs 里

最后需要实现 loadRegFromStackSlot, 以便生成 restore ra 的指令

LowerFormalArguments 负责按调用约定从物理寄存器或栈上获得函数的参数, ToyCallingConv.td 中的

def ToyCC : CallingConv<[
    CCIfType<[i32], CCAssignToReg<[A0, A1]>>
]>;

会生成一个 ToyCC 函数, LowerFormalArguments 调用它获得参数使用的物理寄存器或栈上的位置, 然后生成一些 SDNode (例如 getCopyFromReg) 获得这些参数

目前的实现只支持通过寄存器传递最多两个 i32 类型的参数

LowerCall 时除了生成跳转指令, 还需要按调用约定把参数放在物理寄存器或栈上, 它使用了和前面 LowerFormalArguments 类似的代码.

目前的实现只支持通过寄存器传递最多两个 i32 类型的参数

LowerReturn 不仅要生成跳转指令, 还需要按调用用约定把返回值放在物理寄存器或栈上.

目前的实现只支持通过寄存器返回一个 i32 类型的返回值

LowerCall 最后还需要根据调用约定从物理寄存器或栈上获得函数的返回值

访问栈上的 `a[1]` 时会使用带 offset 的 frameindex

访问全局的 `a[1]` 时会使用带 offset 的 global address

riscv 只支持 slt, 但 slt, sgt, seq, sne 都可以用 slt 实现

br_cc 是条件跳转. br_cc 先通过 expand 转换成 brcond, 然后再用 blt 等指令匹配 brcond

目前的实现里 add 指令只支持 32 位, 为了支持 8/16 位的加法, llvm 的 DAGTypeLegalizer 会在 load/store 时进行 type promotion, 例如 store 时通过 truncate 把 i32 变成 i8, 或 load 时通过 sext 把 i8 变成 i32.

这里的 truncate, sext 信息包含在 load/store 中, 后端需要匹配这些 patten 生成 lb/sb 等指令.

LowerCall 需要按约定把多余的参数放在栈上, LowerFormalArguments 需要从栈上取这些参数

caller 与 callee 的栈布局为:

caller:                  callee:

local_1                  local_1
local_2                  local_2
...                      ...
arg1
arg2 <-- [sp]

即 caller 把参数放在栈顶, callee 直接从 caller 的栈帧取参数, 对应的代码为:

bar:
    addi    sp, sp, -12                 # NOTE: bar 的 stack size 为 12, 但它访问了 sp+12 和 sp+16, 即 foo 的栈帧
    lw      t0, 16(sp)
    lw      t0, 12(sp)
    sw      a0, 8(sp)
    ...
foo:                                    # @foo
    addi    sp, sp, -16
    sw      ra, 12(sp)
    addi    a0, zero, 1
    addi    a1, zero, 2
    addi    a2, zero, 3
    addi    t0, zero, 4
    sw      t0, 0(sp)           # NOTE: foo 的 stack size 原来为 8, 由于参数会使
                                # 用 sp+0, sp+4, ..., 导致需要在
                                # emitPrologue/emitEpilogue 时调整 stack
                                # size. 另外为了避免与原有 local 变量冲突, 会在
                                # eliminateFrameIndex 加上一个 offset
    addi    t0, zero, 5
    sw      t0, 4(sp)
    call    bar
    sw      a0, 8(sp)
    lw      a0, 8(sp)
    lw      ra, 12(sp)
    addi    sp, sp, 16
    ret

由于 call, ret 隐含着使用 a0, a1 等寄存器, 为了避免寄存器分配时对这些寄存器的错误的优化, 需要把它们也放在指令中, 同时使用 glue 把这些寄存器 glue 在一起, 防止 scheduler 错误的优化. 例如:

测试代码为:

void bar(int a, int b, int c) {}
int foo(int a, int b) {
  bar(1, 2, 3);
  return 1;
}

若 LowerReturn 时没有标记 ret 需要使用 a0, 则会生成下面的代码:

foo:                                    # @foo
# %bb.0:
        addi    sp, sp, -16
        sw      ra, 12(sp)
        sw      s0, 8(sp)
        sw      a0, 4(sp)
        sw      a1, 0(sp)
        addi    s0, zero, 1
        addi    a1, zero, 2
        addi    a2, zero, 3
        add     a0, zero, s0
        call    bar
        # NOTE: ret 前对 a0 的赋值消失了
        lw      s0, 8(sp)
        lw      ra, 12(sp)
        addi    sp, sp, 16
        ret

若 LowerCall 时没有记录 call 使用了 a0, 则生成下面的代码:

foo:
    addi    sp, sp, -12
    sw      ra, 8(sp)
    sw      a0, 4(sp)
    sw      a1, 0(sp)
    # NOTE: a2 的赋值消失了
    call    bar
    addi    a0, zero, 1
    lw      ra, 8(sp)
    addi    sp, sp, 12
    ret

只记录寄存器的使用并不能完全正常工作, 还需要 glue 把 ret 和 a0 glue 在一起, 没有 glue 时, 可能会生成这样的代码:

foo:
    # ...
    addi    a0, zero, 1
    lw      ra, 8(sp)
    addi    sp, sp, 12
    # NOTE: call 应该在 addi 之前, 但 ret 和 a0 间没有 glue 可能导致这种错误的结
    # 果
    call    bar
    ret

toy 当前不支持 hard float, 导致 legalize 时会通过 libcall 的形式调用到 libgcc 中的函数

参考 calling convention, 返回结构体时有两种做法:

1. 当结构体较小时使用一个或多个寄存器返回
2. 当结构体较大时会传入一个隐式的指向结构体的指针, 即 named return value 优化

clang 在生成 llir 时就会根据传入的 target 信息决定用哪种方法.

当使用第二种方法时, caller 需要实现 `set rd, frameindex` 这个 patten, 用来传递结构体指针 (而不是之前实现的 `set rd, (load frameindex)`

支持硬浮点需要:

1. 通过 `addRegisterClass(MVT::f32, &Toy::FPRRegClass)` 告诉 llvm 在 legalize type (LegalizeTypes.cpp) 时不要使用软浮点
2. 添加浮点寄存器
3. 在 isel lowering 时处理 constant pool, 因为浮点数常量是使用的 constant pool, 而不是像整数常量那样直接 encode 在指令中
4. 添加指令及其 pattern, 当前的 `float.c` 中需要实现 fadd, load, store, brcond 及 setune. 由于 RISC-V 缺少 f32 br_cc (blt, beq, …) 指令, 所以 f32 br_cc 会使用 f32 setcc 和 i32 br_cc 实现

加入基本的 f64 寄存器和指令.

当处理 `float x=0.1` 时, 后端需要支持 truncstoref32. truncstoref32 实际做了两件事:

1. 把 f64 truncate 成 f32
2. 保存 f32 到内存

riscv 中没有对应的指令, 需要用到 `setTruncStoreAction(MVT::f64, MVT::f32, Expand)`, 让 llvm 把它 expand 成 fround 和 store 两个指令, 分别对应 riscv 的 fcvt.s.d 和 fsw 指令

以 fma 和 fmaxf 为例

https://blog.llvm.org/2010/04/intro-to-llvm-mc-project.html

MCInst 在整个 MC 层处于中心的位置:

MCInstPrinter: 把 MCInst 转换为 asm MCCodeEmitter: 把 MCInst 转换为 binary MCTargetAsmParser: 把 asm 转换为 MCInst MCDisassembler: 把 binary 转换为 MCInst

目前的实现都是 stub, `make xxx.o` 可以生成一个空的 obj 文件

支持 I 指令 (addi, lw…), S 指令 (sw, …) 和 R 指令 (add, sub, …) 的 encoding

去掉了针对 AddrFI 的 mem operand. 由于 I 指令中关于 imm 编码的特殊性, 目前无法实现其 EncoderMethod. 对于通过 ComplexPattern 匹配的 operand, 实际上可以通过 `[(load GPR:$rs2, (AddrFI GPR:$rs1, imm12:$imm))]` 的形式使用, 无需使用 mem 这种 operand

`make arith.o` 产生的 object 除了伪指令 ret, 其它都是正确的.

目前使用伪指令实现 RET 和 CALL, 在输出 asm 比较容易, 但没有考虑 encoding 的问题.

RET 转换成 jalr 比较容易, 它直接对应了 `jalr zero, 0(ra)`.

CALL 转换 jalr 时由于涉及到 symbol 的问题, 需要转换为 `lui t0, %hi(addr); addi t0, %lo(addr); jarl ra, 0(t0)`, 其中 hi/lo 需要转换为 fixup 信息 (类型, 原指令需要被 patch 的 offset 和长度) 保存在 object 中 Linker Relocation

`make run_arith BINARY=1` 可以正常运行, 但还剩几个伪指令 (j, lea, …) 和 branch 没有处理

j 指令需要使用 jal 实现, 并使用 jal 类型的 fixup

branch 指令和 jal 类似, 但使用 branch 的 fixup

`make run BINARY=1` 现在都能正常运行.

li 伪指令用来把 imm 赋值给 gpr, 如果 imm 为 imm12, 可以用 `addi` 实现, 否则需要用 `lui` 和 `addi` 来实现.

需要注意的是针对 imm 获得 lui 需要的高 20 位并不能直接取高 20 位, 因为低 12 位送给 addi 时有可能被当做负数.

例如 imm = 0x1fff, RISCV_CONST_HIGH_PART(imm) 宏返回 0x2000, 而不是 0x1000, 因为低 12 位 0xfff 在 addi 时会 sext 成负数

为了添加一个 intrinsic, 需要同时修改 clang 和 llvm

1. clang

   clang 需要把 c 代码中的 `__builtin_xxx` 转换成 llir 中的 `@llvm.xxx`

   intrinsic 定义在 BUiltins{xxx}.def 中.

   clang 的 CGBuiltin.cpp 在处理 intrinsic 时需要决定是否生成 @llvm.<target>.xxx 形式的 intrinsic 调用. c 代码中的 __builtin_xxx 并不一定都会转换为 llvm instrinsic, 有的会转换为 libcall. 例如

   # clang/Basic/Builtins.def
   LIBBUILTIN(sqrt, "dd", "fne", MATH_H, ALL_LANGUAGES)
   

   中通过 `e` 表示 sqrt 可能会出错, 需要返回 errno (例如输入为负数), 这时只能交给 libcall 处理. 所以 c 代码中的 `__builtin_sqrtf` 或 `sqrtf` 不会转换为 `@llvm.sqrt.f32` (除非使用了 -fno-math-error 等 flag, 参考 CGBuiltin.cpp::ConstWithoutErrnoAndExceptions)

2. llvm

   llvm 需要把 `@llvm.xxx` 形式的 llvm intrinsic lower 成最终的指令.

   llvm 需要修改 Instrinsics.td, intrinsic 的名字有特定的要求, 例如 td 中定义的 intrinsic 为 int_<target>_xxx, llir 中对应的是 `@llvm.<target>.xxx`.

   另外, intrinsic 可以重载, 例如:

   def int_fabs : DefaultAttrsIntrinsic<[llvm_anyfloat_ty], [LLVMMatchType<0>]>;
   

   其中的 anyfloat 会导致 llir 中可以使用 `@llvm.fabs.f32`, `@llvm.fabs.f64`

   最后需要添加 intrinsic 对应的 lowering, 可以直接在 td 中匹配 `int_toy_getsp`这种 patten, 也可以参考 LowerINTRINSIC_WO_CHAIN 使用 custom 的 lowering