GCC Toy RISC-V Backend

configure 时指定 target 为 `toy-elf` 后, gcc 默认会使用如下的文件:

• gcc/config/toy/toy.cc

  包含所有的代码及 target hook, gcc 会链接这个文件

• gcc/config/toy/toy.h

  gcc 会 include 这个文件

• gcc/config/toy/toy.md

• gcc/config/toy/toy-protos.h

  md 使用 genxxx 生成的代码会 include 这个文件

为了支持各种算术运算, 需要查找 optabs.def, 以及查找 standard names 文档, 确定要实现的 insn 的名字.

另外, 生成 rtl 时若某个 optab 没有匹配的 insn, gcc 会隐式的用其它 optab. 例如计算 `a%b` 时若 `smod_optab` 没有匹配的 insn, 则会转换成 `a-(a/b)*b`, 这一点与 llvm 不同, 后者碰到不支持的 insn 会直接报错, 除非显式的通过 setOperationAction 指定其 action 为 expand.

为了知道 md 中到底要定义哪些 insn, 可以在 optabs.cc 中相应的地方加上 log, 打印出编译时查找过的 optab, 从而确定哪些 insn 需要实现.

code iterator 中的 code 是指 rtl code, 在前面实现算术运算时, 发现大部分运算都符合相同的模板, 例如:

(define_insn "mulsi3"
    [(set (match_operand:SI          0 "register_operand")
          (mult:SI (match_operand:SI 1 "register_operand")
                   (match_operand:SI 2 "register_operand")))]
  ""
  "mul\t%0,%1,%2"
  [])

(define_insn "addsi3"
    [(set (match_operand:SI          0 "register_operand")
          (plus:SI (match_operand:SI 1 "register_operand")
                   (match_operand:SI 2 "register_operand")))]
  ""
  "add\t%0,%1,%2"
  [])

把 `mult`, `plus` 这些 rtl code 写在一个 code iterator 中, 再把它们对应的 optab (mulsi3, addsi3 中的 mul, add) 和 insn (汇编模板中的 mul, add) 写在 code attribute 中, 最可以用一个模板简化多个 insn 的定义:

(define_insn "<optab>si3"
     [(set (match_operand:SI          0 "register_operand")
          (arith:SI (match_operand:SI 1 "register_operand")
                   (match_operand:SI 2 "register_operand")))]
   ""
  "<insn>\t%0,%1,%2"
  []
)

• arith 是一个 code iterator: `(define_code_iterator arith [mult div])`,
• optab 是一个 code attribute: `(define_code_attr optab [(mult "mul") (div "div")])`
• insn 也是一个 code attribute: `(define_code_attr insn [(mult "mul") (div "div")])`

通过 `(mem (symbol_ref xxx))` 的形式访问全局变量, 但 riscv 在寻址时需要先把符号的地址加载到寄存器, 然后再使用 load/store 指令, 因为在 toy_legitimize_move中需要完成这种变换:

if (GET_CODE(symbol) == SYMBOL_REF) {
    dst = gen_reg_rtx(SImode);
    /* 对应 la 指令 */
    emit_move_insn(dst, symbol);
    /* 对应 load/store 指令 */
    dst = gen_rtx_MEM(SImode, dst);
    legitimize = true;
}

通过常量的索引访问全局数组 (例如 x[2]) 时, 会生成类似下面的 rtl:

`(mem (const (plus (symbol_ref xxx) 8)))`

因此需要改进一下前面的 toy_legitimize_move, 让这支持这个 pattern:

if (GET_CODE(symbol) == CONST) {
    rtx plus = XEXP(symbol, 0);
    if (GET_CODE(XEXP(plus, 0)) == SYMBOL_REF) {
        rtx tmp = gen_reg_rtx(SImode);
        emit_move_insn(tmp, XEXP(plus, 0));
        XEXP(plus, 0) = tmp;
        XEXP(dst, 0) = plus;
        legitimize = true;
    }
}

从而把 rtl 变成

`(set reg (symbol_ref xxx)) (set yyy (mem (const (plus reg 8))))`

setcc 类指令是为了支持 `int x=(a>b)` 这种代码, 对应 riscv 中的 slt (set less than) 指令, 但 riscv 只支持 slt, 并不支持 sle, sgt, seq 等, 需要通过 define_expand 把它们转换成使用 slt 的形式, 例如 (sgt x y) <=> (slt y x)

setcc 对应的 optab 为 cstore, 所以需要 `define_expand cstoresi4`, 主要的代码是 expand 的过程:

void toy_expand_int_scc(rtx target, int code, rtx op0, rtx op1) {
    switch (code) {
        case LT:
            emit_insn(gen_rtx_SET(
                target, gen_rtx_fmt_ee(LT, GET_MODE(target), op0, op1)));
            break;
        case GT:
            /* NOTE: (GT X Y) <=> (LT Y X) */
            emit_insn(gen_rtx_SET(
                target, gen_rtx_fmt_ee(LT, GET_MODE(target), op1, op0)));
            break;
        case GE:
            /* NOTE: (GE X Y) <=> (XOR (LT X Y) 1), 因为 a >= b 等价于 !(a<b) */
            emit_insn(gen_rtx_SET(
                target, gen_rtx_fmt_ee(LT, GET_MODE(target), op0, op1)));
            emit_insn(gen_rtx_SET(
                target,
                gen_rtx_fmt_ee(XOR, GET_MODE(target), target, const1_rtx)));
            break;
        /* ... */
    }
}

brcc 类指令用来支持 `if (a>b) {}` 这种代码, riscv 中对应的指令为 blt, bge, beq, bne, 但缺少 ble, bgt. 这里并没有像 setcc 那样通过 expand 来支持它, 因为 assember 已经提供了对应 ble, bgt 的伪指令.

(define_insn "cbranchsi4"
  [(set (pc)
    (if_then_else (match_operator 0 "comparison_operator"
              [(match_operand:SI 1 "register_operand")
               (match_operand:SI 2 "register_operand")])
              (label_ref (match_operand 3 ""))
              (pc)))]
  ""
  "b%C0\t%1,%2,%3"
  )

其中汇编模板中的 `C` 符号由 `toy_print_operand` 处理, 直接在输出汇编时打印出 `lt`, `ge` 等字符串

目前为止生成的汇编还无法执行, 因为:

1. 没有保存和恢复 csr, 尤其是函数返回时需要的 ra 寄存器
2. INITIAL_ELIMINATION_OFFSET 只有 stub 实现, 因为没有处理 csr, 还不知道 stack 大小

生成 prologue 和 epilogue 的代码会负责完成这两项任务.

prologue 是函数开头由编译器自动插入的一些指令, 例如:

addi    sp,sp,-32
sw      ra,28(sp)
sw      s0,24(sp)
addi    s0, sp, 32

它的任务包括:

1. 预留栈空间
2. 保存 csr, 包括 ra, fp 及其它 csr
3. 设置 fp

为了预留栈空间需要先计算 stack frame size. 通过 gcc 的 get_frame_size 可以获得包含局部变量和 outgoing argument 的 stack frame size, backend 需要自己计算 csr 需要的大小以获得最终的 size

epilogue 是函数结尾由编译器插入的指令, 用来恢复 sp 和 csr

目前的实现只支持 `void f()` 形式的函数, 需要实现 `TARGET_FUNCTION_ARG` target hook 以支持函数参数. 按 riscv 的调用约定, 函数调用时前 8 个参数放在 a0~a7, 其它放在栈上.

toy_function_arg 函数会返回对应 a0~a7 的 rtx, 若返回 NULL_RTX, 则由 gcc 分配在栈上.

当前的实现只支持 8 个及以内的 int 参数

`TARGET_FUNCTION_VALUE` hook 决定了函数的返回值如何访问, 当前只支持通过 a0 返回 int 值

riscv 并没有单独的针对 QI/HI 的算术运算, gcc 会把 QI/HI 转换成 SI, 计算完再转换回 QI/HI, 这个和 llvm legalize 时的 promote 类似. gcc 通过 subreg 来表示这种转换, 例如:

`(set reg:QI (subreg:QI (reg:SI)))` 表示把 SI 转换为 QI, 通过 zext, sext 这类 optab 可以实现这种转换.

另外, match_register 这个 predicate 可以匹配 subreg (即 subreg 也是 reg), 实际上 reload 阶段会把 subreg 转换成 zext 类指令, 并不需要 backend 自己处理.

支持浮点对应 optab, 包括算术运算, 类型转换, load/store 等.

另外, 由于浮点立即数无法编码到指令中, 所以通过 TARGET_LEGITIMATE_CONSTANT_P 要求 gcc 不要生成 `(const_double 1.00)` 这种形式的 rtl, 而是使用 load/store constant pool 的形式来读写浮点数

实现浮点数的 setcc 和 brcc.

setcc 与 SI 基本相同, 但 riscv 不支持针对浮点数的 blt 指令, 因此 brcc 是通过 setcc 来实现的, 例如把 `(blt x y xxx )` 转换为 `(bne (slt x y) 0 xxx)`

处理了以下需要考虑浮点数的场景:

1. 计算 stack 大小
2. 生成 prologue/epilogue
3. 函数参数
4. 函数返回值

测试 qsort 时, 发现一个问题: 使用变量访问数组时, 会生成如下的 rtl:

`(mem (plus (symbol_ref xxx) (mult x y)))`

因为对于 `int a[]`, 访问 a[n] 相当于访问 a+n*4. toy_legitimize_memory_address 需要处理这种情况

通常 backend 实现 instrinsics 时显得有些复杂, 因为它们需要考虑如何方便的, 以可配置的方式添加 instrinsic, 因此对整个过程做了一些抽象, 实际上添加 intrinsics 实现只需要两步:

1. 实现 TARGET_INIT_BUILTINS, 告诉前端哪个函数是 intrinsics
2. 实现 TARGET_EXPAND_BUILTIN, 在 expand_builtin 时生成对应的 rtl

当前实现 arch 为 rv32imfd, 所以原生不支持 DI 类型. gcc 会用 SI 来实现 DI 的运算, 例如, gcc 会这样实现 adddi3:

1. 各使用两个寄存器保存输入和输出
2. 计算低 32 位加法
3. 通过 LTU 看是否有进位
4. 计算高 32 位加法, 再加上进位

在此过程中 gcc 会使用 `(subreg:SI (reg:DI) 0))` 的形式表示要操作 DI 的低 32 位, 最终 reload 会负责去掉 subreg, 并分配合适的寄存器

所以 backend 并不需要太多额外代码即可支持 long long

前面的代码函数调用只支持 8 个参数, 通过 toy_function_arg 返回 NULL_RTX, 表示该参数需要用栈传递. 这些参数在 reload 之前是通过 ARG_POINTER_REGNUM (toy backend 中的 varg) 表示的, 其栈布局为:

        arg1
fp  ->  arg0 <-- varg
        csr
        ...
        local N
        local ...
vfp ->  local 0

因此需要实现 toy_initial_elimination_offset, 当 from 为 ARG_POINTER_REGNUM 时返回 0, 因为 toy backend 使用 fp 索引局部变量

通过 TARGET_HARD_REGNO_MODE_OK, 可以控制 reload 针对 machine mode 分配什么寄存器, 当前代码要求 MODE_FLOAT 必须使用 FPR.

默认情况下, SF mode 也可能分配到 GPR, 因为 GPR 宽度足够保存 int, 通过 riscv 的 fmv 指令访问 FPR 中保存的定点值或 GPR 保存的浮点值 (注意 fmv 和 fcvt 指令的差别)

backend 可以在汇编中插入 cfi (call frame info) directive, 然后 assembler 可以根据这些 directive 生成 dwarf 的信息 (gas cfi directives). gcc 编译时是否生成 cfi directive 取决于当前使用的 assember 是否支持这些 directive, 所以需要通过 DEFAULT_ASSEMBLER 指定 as 后才能生成 directive.

以 arith.s 为例, 针对 foo 生成的 directive 为:

foo:
.LFB0:
.LM1:
    .cfi_startproc
    addi        sp,sp,-32
    # NOTE: 设置 cfa 为 sp+32
    .cfi_def_cfa_offset 32
    sw  ra, 28(sp)
    # NOTE: ra (reg 1) 保存在 cfa-4
    .cfi_offset 1, -4
    sw  s0, 24(sp)
    # NOTE: s0 (reg 0) 保存在 cfa-8
    .cfi_offset 8, -8
    addi        s0,sp,32
    # ...
    lw  ra, 28(sp)
    .cfi_restore 1
    lw  s0, 24(sp)
    .cfi_restore 8
    addi        sp,sp,32
    # NOTE: 设置 cfa 为 sp+0
    .cfi_def_cfa_offset 0
    ret
    .cfi_endproc

cfa (canonical frame address) 相当于虚拟的 fp, dwarf 会使用一个寄存器(例如 sp, fp) 和 一个 offset 来计算 cfa. cfa 可以用来做 stack unwinding 和访问 csr

stack unwinding 的大致过程:

loop {
     // current frame
     fde=get_fde(pc)
     cfa=get_cfa(sp, def_cfa_offset)
     ra=get_csr(cfa, cfi_offset)
     // prepare next frame
     pc=ra
     sp=cfa
}

alloca 会在运行时修改 sp, 导致 dwarf 不能用 sp 做 cfa 的 base register. backend 需要在 prologue中添加 `.cfi_def_cfa 8, 0`, 使它使用 fp (x8) 做 cfa.

另外, 需要设置 STACK_GROWS_DOWNWARD 以便 `expand_builtin_alloca` 在扩展 stack 时正确生成 `addi sp, sp, -xxx`, 而不是 `addi sp, sp, xxx`. 同时, STACK_GROWS_DOWNWARD 还会导致局部变量会由 vfp+n 的形式变成 vfp-n, 所以 INITIAL_ELIMINATION_OFFSET 也需要相应的修改, 因为设置 STACK_GROWS_DOWNWARD 后栈的布局会变成:

        arg1
 fp ->  arg0 <-- varg
        csr
        ...
vfp ->  local 0
        local ...
        local N

# fp - vfp = csr_size

gcc 中支持 SIMD 有几种方式:

1. intrinsic
2. auto vectorization
3. omp simd
4. vector extension

其中 vector extension 是指类似下面的代码:

v4si x = {1, 2, 3, 4};
v4si y = {1, 2, 3, 4};
v4si z = x + y;

为了支持 vector extension, backend 需要:

1. 声明支持 vector mode, 例如 V4SI, V8HI 等
2. 定义 vector 寄存器
3. 定义 vector 相关指令

如果前两点没有正确设置, 则 veclower pass 在 gimple 阶段就会把 vector lower 成 scaler 操作.

rvv 指令不支持 `imm(reg)` 的寻址方式, 因此 legitimize_memory_address 需特殊处理.

由于 rvv 的限制, 生成的每条汇编前都添加了 vsetvl 指令.

通过 toy.opt 可以方便的添加 command-line option, 并且在 c 代码和 md 中可以使用这些 option.

定义 TARGET_HARD_FLOAT 选项, 禁用浮点指令和浮点寄存器, gcc 会自动通过 libcall 调用 libgcc 中的 soft float 函数.

在测试时碰到三个问题:

1. 测试 float.c 的 clobber_ra 函数时, 发现 libcall 时 ra 因为没有标记为 clobber 而被错误的使用, 需要在 md 中相应的 insn 中标记 ra 为 clobber
2. 通过 toy_function_arg 分配寄存器时, 针对 DF mode 需要分配索引为偶数的寄存器. 以 float.c 中的 `__adddf3` 为例, 它有两个 DF 类型的参数, gcc 需要使用两个GPR 表示一个 DF. 当 toy_function_arg 分配的寄存器为 r0, r2 时, gcc 会把它们转换为 (r0, r1), (r2, r3). 如果分配的寄存器为 r0, r1, 则 gcc 会它们转换为 (r0, r1), (r1, r2), 导致出错.
3. gcc 会生成 cbranchsi4 指令, 但 operand 2 有时会为 (const_int 0) (而不是一个寄存器), 需要后端处理这种情况