GCC Backend

1. GCC Backend

1. GCC Backend

https://github.com/sunwayforever/gcc-toy/

GNU Compiler Collection (GCC) Internals

GCC RISC-V backend 的最初提交

gcc backend 的功能主要包括:

instruction (insn) selection
rtl optimization
insn schedule
register allocation
code emission

其中 backend 开发的工作主要有:

完成 machine desc 文件, 用来声明:
1. backend 支持的 optab
2. optab 对应的 rtl (Register TransferLanguage)
3. optab 对应的汇编模板
md 文件主要用来支持 insn selection 和 code emission
实现一些 rtl 优化, 例如 combine 和 peephole
实现一些 target hook 和 target macro, 给通用算法 (register allocation, optimization 等) 提供必要的 backend 相关信息
如果有需要, 再实现一些 intrinsic

1.1. insn selection

insn selection 通过 `pass_expand` 完成, 目的是生成 gimple 对应的 rtl, 基本过程是:

根据 gimple 的 tree code (例如 PLUS_EXPR) 找到 optab (例如 add_optab)
根据 optab 找到 insn_code (例如 CODE_FOR_addsf3)
根据 insn_code 找到对应的 rtl

1.1.1. gimple tree code

gimple 定义的 tree code 在 `tree.def` 中, 例如:

DEFTREECODE (PLUS_EXPR, "plus_expr", tcc_binary, 2)
DEFTREECODE (MINUS_EXPR, "minus_expr", tcc_binary, 2)
DEFTREECODE (MULT_EXPR, "mult_expr", tcc_binary, 2)
DEFTREECODE (LSHIFT_EXPR, "lshift_expr", tcc_binary, 2)
DEFTREECODE (ABS_EXPR, "abs_expr", tcc_unary, 1)

有些 tree code 并没有直接对应的 C 语法 (例如 ABS_EXPR, MAX_EXPR), 这些 tree code 要么通过 gimple 的 `Match-and-simplify patterns` 或其它一些 gimple optimization 来生成的, 要么通过 builtin 来使用, 例如:

MAX_EXPR

MAX_EXPR 可以通过优化 `a>b?a:b` 或 `if (a>b) {return a; } return b;` 得到:

#define A(a, b) ((a) > (b) ? (a) : (b))

int main(int argc, char *argv[]) {
    int x = argc;
    int y = -argc;
    int z = A(x, y);
    return z;
}

生成的 gimple 为:

main (int argc, char * * argv)
{
  int D.1506;

  {
    int x;
    int y;
    int z;

    x = argc;
    y = -argc;
    z = MAX_EXPR <y, x>;
    D.1506 = z;
    return D.1506;
  }
  D.1506 = 0;
  return D.1506;
}

ABS_EXPR

abs 可以通过 `__builtin_fabs` 生成, 也可以通过优化 max(a,-a) 来生成:

match.pd:

/* max(a,-a) -> abs(a).  */
(simplify
 (max:c @0 (negate @0))
 (if (TREE_CODE (type) != COMPLEX_TYPE
      && (! ANY_INTEGRAL_TYPE_P (type)
      || TYPE_OVERFLOW_UNDEFINED (type)))
  (abs @0)))

以前面的代码为例, 优化后的 gimple 会变成:

main (int argc, char * * argv)
{
  int z;

  <bb 2> [local count: 1073741824]:
  z_2 = ABS_EXPR <argc_1(D)>;
  return z_2;

}

1.1.2. optab

optab 的定义在 optabs.def, 它是 gimple 与 rtl 之间的桥梁:

gimple 的 tree code (例如 PLUS_EXPR) 通过 `optab_for_tree_code` 映射到 optab (例如 add_optab)
optabl 通过 optab_handler 映射到 rtl 的 insn_code (例如 CODE_FOR_addsf3)

optabs.def 的部分内容:

OPTAB_NL(add_optab, "add$P$a3", PLUS, "add", '3', gen_int_fp_fixed_libfunc)
OPTAB_NL(sub_optab, "sub$P$a3", MINUS, "sub", '3', gen_int_fp_fixed_libfunc)
OPTAB_NL(smul_optab, "mul$Q$a3", MULT, "mul", '3', gen_int_fp_fixed_libfunc)
OPTAB_NL(sdiv_optab, "div$a3", DIV, "div", '3', gen_int_fp_signed_fixed_libfunc)

OPTAB_NL(and_optab, "and$a3", AND, "and", '3', gen_int_libfunc)
OPTAB_NL(xor_optab, "xor$a3", XOR, "xor", '3', gen_int_libfunc)

OPTAB_NL(ashl_optab, "ashl$a3", ASHIFT, "ashl", '3', gen_int_fixed_libfunc)

OPTAB_NL(eq_optab, NULL, EQ, "eq", '2', gen_fp_libfunc)
OPTAB_DC(cbranch_optab, "cbranch$a4", COMPARE)

OPTAB_NL(neg_optab, "neg$P$a2", NEG, "neg", '2', gen_int_fp_fixed_libfunc)
OPTAB_NC(abs_optab, "abs$P$a2", ABS)

OPTAB_NL(clz_optab, "clz$a2", CLZ, "clz", '2', gen_int_libfunc)
OPTAB_NC(sqrt_optab, "sqrt$a2", SQRT)

OPTAB_DC(mov_optab, "mov$a", SET)
OPTAB_D (atomic_add_fetch_optab, "atomic_add_fetch$I$a")

有些 optab 与 gimple 的 tree code 是对应的 (例如 add, sub, mul, shift 等), 另一些 optab (例如 clz, sqrt) 在 C 的语法中并不存在对应的东西, 这些 optab 主要是给 builtin (intrinsic) 或 tree optimizer 使用.

以 sqrt_optab 为例, 如果 backend 支持 sqrt_optab (通过 TARGET_OPTAB_SUPPORTED_P), 则 gimple 优化阶段会把 `pow (x, 0.5)` 替换成对 `__builtin_sqrt` 的调用, 后者在 insn selection 阶段会找到 sqrt_optab.

1.1.2.1. 构造 optab_handler

optab_handler 相当于一个注册表, 保存着 optab 与 insn_code 的对应关系

out/gcc/insn-opinit.c:

inline enum insn_code optab_handler(optab op, machine_mode mode) {
    unsigned scode = (op << 16) | mode;
    return raw_optab_handler(scode);
}

enum insn_code raw_optab_handler(unsigned scode) {
    int i = lookup_handler(scode);
    return (
        i >= 0 && this_fn_optabs->pat_enable[i] ? pats[i].icode
                                                : CODE_FOR_nothing);
}

static const struct optab_pat pats[NUM_OPTAB_PATTERNS] = {
  { 0x010405, CODE_FOR_extendqihi2 },
  { 0x010406, CODE_FOR_extendqisi2 },
  { 0x010407, CODE_FOR_extendqidi2 },
  { 0x010505, CODE_FOR_extendhihi2 },
  { 0x010506, CODE_FOR_extendhisi2 },
  { 0x010507, CODE_FOR_extendhidi2 },
  /* ... */
}

这个 insn-opinit.c 是 genopinit.c 通过扫描 optab.def 和 md 生成的

1.1.2.1.1. genopinit

genopinit.c:

/* read_md_rtx 是从 md 中依次读入 rtx, 例如
 * addsf3, adddf3, addsi3, ...
 * 需要注意的是 md 中通过 define_mode_iterator 定义的 insn (例如 add<mode>3)
 * 会被展开成多个 rtx: addsf3 和 adddf3
 * */
while (read_md_rtx(&info)):
    switch (GET_CODE(info.def)):
        case DEFINE_INSN:
        case DEFINE_EXPAND:
            gen_insn(&info);
            break;

static void gen_insn (md_rtx_info *info) {
  optab_pattern p;
  if (find_optab (&p, XSTR (info->def, 0))) {
      patterns.safe_push (p);
  }
}

1.1.2.1.2. find_optab

find_optab 是针对每一个 rtx 去查找 optab.def 中是否有对应的 optab, 目的是为了给 optab 找到底层的 rtx 实现.

例如:

addsf3 这个 rtx 会找到它对应 add_optab 且 mode 为 sf (single float) fadddf3 这个 rtx 会找到它也对应 add_optab 且 mode 为 df (double float)

bool find_optab(optab_pattern *p, const char *name) {
    if (*name == 0 || *name == '*') return false;

    /* 针对 name 遍历所有的 optab */
    for (unsigned int pindex = 0; pindex < ARRAY_SIZE(optabs); pindex++) {
        p->m1 = 0;
        /* 所谓的 match_pattern, 是指 rtx 能否满足 optab pattern 的要求
         * 例如 add_optab 有一个 patten 是 `add$F$a3`, 表示三个操作数的浮点加法,
         * 则 addsf3 和 adddf3 都会和 add_optab match. 即 add_optab 针对浮点模式 sf/df 找到了 rtx 实现
         * 实际上, 上层代码例如生成 gimple 时也会通过 optab_handler 去确认相应的 optab 在底层是否支持.
         * */
        if (match_pattern(p, name, optabs[pindex].pattern)) {
            p->name = name;
            p->op = optabs[pindex].op;
            p->sort_num = (p->op << 16) | p->m1;
            /* p->sort_num 即是 pats 中前面的数:
             * { 0x010405, CODE_FOR_extendqihi2 },
             * */
            return true;
        }
    }
    return false;
}

1.1.2.1.3. match_pattern

optabs.def 中的 add$P$a3 是一个 pattern, genopinit 的 match_pattern 函数会根据这个 pattern 来决定 md 中的哪些 insn 对应这个 optab. pattern 中的 $, P, I, a 等都有特定的含义

static bool match_pattern(optab_pattern *p, const char *name, const char *pat) {
    bool force_float = false;
    bool force_int = false;
    bool force_partial_int = false;
    bool force_fixed = false;

    if (pat == NULL) return false;
    for (;; ++pat) {
        if (*pat != '$') {
            if (*pat != *name++) return false;
            if (*pat == '\0') return true;
            continue;
        }
        /* IPFQ 是 optab.def 中表示格式的特殊字符
         * I 表示 int
         * F 表示 float
         * ...
         * */
        switch (*++pat) {
            case 'I':
                force_int = 1;
                break;
            case 'P':
                force_partial_int = 1;
                break;
            case 'F':
                force_float = 1;
                break;
            case 'Q':
                force_fixed = 1;
                break;

            case 'a':
            case 'b': {
                int i;
                /* NOTE: 遍历 target 支持的所有的 machine_mode: sf, df, si, di,
                 * ... */
                for (i = (MAX_MACHINE_MODE)-1; i >= 0; i--) {
                    const char *p, *q;
                    for (p = GET_MODE_NAME(i), q = name; *p; p++, q++)
                        if (TOLOWER(*p) != *q) break;
                    if (*p == 0 &&
                        (!force_int || mode_class[i] == MODE_INT ||
                         mode_class[i] == MODE_VECTOR_INT) &&
                        (!force_float || mode_class[i] == MODE_FLOAT ||
                         mode_class[i] == MODE_DECIMAL_FLOAT ||
                         mode_class[i] == MODE_COMPLEX_FLOAT ||
                         mode_class[i] == MODE_VECTOR_FLOAT) &&
                        ) || (...);
                        break;
                }

                if (i < 0) return false;

                /* 以 optab.def 中的 OPTAB_NX(add_optab, "add$F$a3") 为例
                 * addsf3 会 match 到 "add$F$a3" 这个 pat
                 */
                name += strlen(GET_MODE_NAME(i));
                p->m1 = i;
            } break;
        }
    }
}

1.1.2.2. optab_libfunc

gcc 通过 optab_handler 查找 optab 对应的 insn_code, 当它找不到 `optab+machmode` 对应的 insn 时, 对于某些简单的 optab (例如 smax_optab), 会在代码中直接生成 rtl 来代替 (例如 cbranch), 例如:

expand_binop:
  case MAX_EXPR:
  case MIN_EXPR:
    expand_operands (treeop0, treeop1,
             target, &op0, &op1, EXPAND_NORMAL);

    /* First try to do it with a special MIN or MAX instruction.
   If that does not win, use a conditional jump to select the proper
   value.  */
    this_optab = optab_for_tree_code (code, type, optab_default);
    temp = expand_binop (mode, this_optab, op0, op1, target, unsignedp,
             OPTAB_WIDEN);

对于复杂的功能, 会通过 optab_libfunc 生成对某个外部函数的调用, 例如 __divsf3. 这些函数是在 libgcc 中实现的.

rtx optab_libfunc(optab optab, machine_mode mode) {
    struct libfunc_entry e;
    struct libfunc_entry **slot;

    e.op = optab;
    e.mode1 = mode;
    e.mode2 = VOIDmode;
    slot = libfunc_hash->find_slot(&e, NO_INSERT);
    if (!slot) {
        const struct optab_libcall_d *d =
            &normlib_def[optab - FIRST_NORM_OPTAB];

        if (d->libcall_gen == NULL) return NULL;

        /* d->libcall_gen 中信息来自 optabs.def, 例如
         * OPTAB_NL(add_optab, "add$P$a3", PLUS, "add", '3', gen_int_fp_fixed_libfunc)
         * 表示 add_optab 的 libcall_basename 为 "add", libcall_gen 为 gen_int_fp_fixed_libfunc,
         * 后者会根据 libcall_basename(add) 和 mode (sf) 生成一个名为 __addsf3 的 libfunc_entry
         * 后通过 set_optab_libfunc 设置到 libfunc_hash, 后续就可以生成对 __addsf3 的调用
         * */

        d->libcall_gen(optab, d->libcall_basename, d->libcall_suffix, mode);
        slot = libfunc_hash->find_slot(&e, NO_INSERT);
        if (!slot) return NULL;
    }
    return (*slot)->libfunc;
}

实际上 soft-float 与 hard-float 的区别就是是通过 optab_libfunc 机制来体现的:

(define_insn "div<mode>3"
  [(set (match_operand:ANYF           0 "register_operand" "=f")
    (div:ANYF (match_operand:ANYF 1 "register_operand" " f")
          (match_operand:ANYF 2 "register_operand" " f")))]
  "TARGET_HARD_FLOAT && TARGET_FDIV"
  "fdiv.<fmt>\t%0,%1,%2"
  [(set_attr "type" "fdiv")
   (set_attr "mode" "<UNITMODE>")])

当 TARGET_HARD_FLOAT 时, optab_handler 会找到这里会产生的 divsf3/divdf3 两条 insn. 否则就会通过 optab_libfunc 产生对 __divsf3/__divdf3 的调用

Backlinks

LLVM Backend (LLVM Backend > instruction selection > SelectionDAG): 其中 DAG 中 node 的类型例如 fadd 定义在 ISDOpcodes.h, 和 gcc 的 optab 有些类似

Backlinks

LLVM Backend (LLVM Backend > instruction selection > legalize > libcall): 类似于 gcc optab_libfunc

1.1.3. machine desc

https://www.cse.iitb.ac.in/grc/slides/cgotut-gcc/topic5-md-intro.pdf

https://gcc.gnu.org/onlinedocs/gccint/Machine-Desc.html#Machine-Desc

optab 要找到 insn_code 和 rtl 需要 machine desc 文件.

写 machine desc(md) 文件是开发 backend 的第一步: 它指明了前端的操作 (例如 PLUS) 需要映射到 backend 的什么操作 (例如 fadd.s), 但它并不是直接由前端的 gimple 翻译成汇编, 而是先翻译成 rtl 代码再翻译成汇编.

md 有两个作用:

生成 rtl

insn selection 阶段找到 gimple 对应的 rtl
匹配 rtl

code emission 阶段找到 rtl 对应的汇编

1.1.3.1. md 语法

1.1.3.1.1. define_insn

md (例如 riscv.md) 是 backend 最核心的部分, 其中最重要的部分是 define_insn, 例如:

(define_insn "add<mode>3"
  [
  ;; -----------------------------
  ;; rtl 模板
  ;; 这个模板会匹配 (set rd (plus rs1 rs2) 形式的 rtl expression
  ;; 其中 register_operand 是指参数需要是一个寄存器, 在
  ;; predicates.md 中有定义
  (set (match_operand:ANYF 0 "register_operand" "=f")
    (plus:ANYF (match_operand:ANYF 1 "register_operand" "f")
           (match_operand:ANYF 2 "register_operand" "f")))]

  ;; -----------------------------
  ;; 匹配该模板需要的额外条件, 这里要求支持 hard float
  "TARGET_HARD_FLOAT"

  ;; -----------------------------
  ;; 汇编模板
  ;; 表示 rtl 模板匹配后输出的汇编, 可以是一个汇编的 string,
  ;; 也可以是一段产生 string 的 C 代码
  "fadd.<fmt>\t%0,%1,%2"

  ;; -----------------------------
  ;; 这些 attr 和 insn schedule 有关
  [(set_attr "type" "fadd")
   (set_attr "mode" "<UNITMODE>")])

ANYF 是一个包含 [SF, DF] 的 mode_iterator, 所以上面的模板实际上会被展开成两个: addsf3, adddf3

define_insn 有两个用法:

从 gimple 生成 rtl 时会根据 insn code (例如 CODE_FOR_addsf3) 选择对应的 rtl 模板来生成 rtl. addsf3 这个名字是 gcc 提前定义好的标准名字, 表示一个标准的操作 (更多的标准操作: https://gcc.gnu.org/onlinedocs/gccint/Standard-Names.html#Standard-Names)
经过各种 rtl pass 之后, 最后 code emission 会通过与 rtl 模板匹配确定对应的汇编

例如 test.c 中的 `float y = x + x` 会先通过 addsf3 转换为下面的 rtl 代码:

(insn# 0 0 (set (reg:SF 48 f16)
        (plus:SF (reg:SF 48 f16)
            (reg:SF 49 f17))) test.c:5# {addsf3}
     (nil))

假设这段代码没有被优化修改, 最终在 final 阶段会匹配前面的 `addsf3` 模板, 最终输出汇编 `fadd.s f16,f16,f17`

1.1.3.1.2. define_expand

与 define_insn 不同, 有些 insn 的功能是通过组合其它 insn 来完成的.

define_expand 的 templte 部分可以只声明 operand, 后面嵌入的 c 代码 (preparation statement) 负责通过 rtx 的 api (例如 emit_insn, gen_xxx) 生成 rtx. define_expand 也可以在 template 中写上完整的 template, 然后 c 代码可以对这个 template 做一些修改, 例如修改某个 operand.

以 gcc toy 中的 `mov` 为例:

(define_expand "mov<ANYI:mode>"
    [(set (match_operand:ANYI 0 "general_operand")
          (match_operand:ANYI 1 "general_operand"))]
  ""
  {
    if (toy_legitimize_move(operands[0], operands[1]))
        DONE;
  }
  )

由于 mov 可以有多种形式的 operand, 但大部分都是不合法的, 例如 `(set (mem ..) (const_int …))` 无法对应任何 riscv 指令, 因为 store 指令不接受 imm operand.

因此需要通过 expand 生成 rtx, 把 const_int 用 `(set (reg …) (const_int …))` load 到一个寄存器, 后续在 code emission 阶段可以匹配到下面这一条合法的 mov pattern:

(define_insn "*mov<mode>"
    [(set (match_operand:ANYI 0 "register_operand" "=r,r")
          (match_operand:ANYI 1 "arith_operand" "r,I"))]
  ""
  "@
   mv\t%0, %1
   li\t%0, %1"
  )

这个过程和 llvm 的 legalize 有点类似

1.1.3.1.3. define_split

define_split 和 define_expand 功能类似，都是生成 rtl. 但与 define_expand 不同的是, define_split 的 rtl 模板部分负责匹配而不是生成 rtl. define_split 的功能是匹配 rtl, 把它们替换成新的 rtl. 如果某个 optab 的实现比较复杂, 可以用 split 来实现, 例如:

(define_insn "ashlsi3"
   [(set (match_operand:SI 0 "register_operand" "=r")
         (ashift:SI (match_operand:SI 1 "register_operand" "r")
                    (match_operand:SI 2 "arith_operand" "i")))]
   ""
   "#"
)
(define_split
   [(set (match_operand:SI 0 "register_operand" "=r")
         (ashift:SI (match_operand:SI 1 "register_operand" "r")
                    (match_operand:SI 2 "arith_operand" "i")))]
   ""
   [(set (match_dup 0)
         (mult:SI (match_dup 1) (match_dup 2)))]
   {
   operands[2]=force_reg(SImode, GEN_INT (1<<(INTVAL (operands[2]))));
   })

define_insn asm 模板中的 `#` 表示它需要由 split 来处理. 可以把 define_insn 和 define_split 写在一起:

(define_insn_and_split "ashlsi3"
  [(set (match_operand:SI 0 "register_operand")
        (ashift:SI (match_operand:SI 1 "register_operand" "=r,r")
                   (match_operand:SI 2 "arith_operand" "r,i")))]
  ""
  "@
   sll\t%0,%1,%2
   #"
  ""
  [(set (match_dup 0)
        (mult:SI (match_dup 1) (match_dup 2)))]
  {
  operands[2]=force_reg(SImode, GEN_INT (1<<(INTVAL (operands[2]))));
  })

对于 operand 为 `r r`, 它相当于 `define_insn`, 对于 operand 为 `r i`, 它与 `define_expand` 基本相同, 只是不需要在代码中通过 emit_insn 生成的 rtl , 而是直接写在 split 的 new-insn-pattern 中

1.1.3.1.4. define_mode_iterator

某个指令针对不同的 mode (SI, DI, SF, DF,. …) 可能会定义类似的 insn, 例如 gcc-toy 中的:

(define_insn "*mov<mode>"
    [(set (match_operand:ANYI 0 "register_operand" "=r,r")
          (match_operand:ANYI 1 "arith_operand" "r,I"))]
  ""
  "@
   mv\t%0, %1
   li\t%0, %1"
  )

其中 ANYI 是一个包含了 [SI, DI, QI, HI] 的 mode iterator.

1.1.3.1.5. define_mode_attr

以前面的 `*mov<mode>` 为例, 使用 ANYI 这个 mode iterator 时, 当 mode 为 SI 时, insn 的名字应该为 "*movsi", 当 mode 为 DI 时, 相应的 insn 的名字应该为 "*movdi", 这里的 "si", "di" 是由 `mode` 这个 mode attri 定义的, 这个内容大约是:

(define_mode_attr mode [(SI "si") (DI "di") (QI "qi") (HI "hi")])

1.1.3.1.6. define_code_iterator

code iterator 中的 `code` 是指 rtl code. 有许多 rtl code 用起来类似, 例如 `plus`, `and`, `ior`, …

以 gcc-toy 为例:

(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 iteator:

(define_code_iterator arith [minus mult div])

这三个 code 对应的指令在 riscv 中有相同的 template

1.1.3.1.7. define_code_attr

上面的例子中, `optab` 和 `insn` 都是 code attr, 它们保存着 code 对应的 optab 和 insn:

(define_code_attr optab [
  (minus "sub")
  (mult "mul")
  (div "div")
  ])

(define_code_attr insn [
  (minus "sub")
  (mult "mul")
  (div "div")
  ])

1.1.3.1.8. define_c_enum

1.1.3.1.9. define_constants

1.1.3.1.10. define_attr

1.1.3.1.11. define_predicate

predicate 是指 match_operand/match_operator 时可以指定的条件, 例如

(define_insn "adddi3"
  [(set (match_operand:DI 0 "register_operand" "=r,r")
    (plus:DI (match_operand:DI 1 "register_operand" " r,r")
         (match_operand:DI 2 "arith_operand"    " r,I")))]
  ...
)

arith_operand 就是通过 define_predicate 指定的 predicate:

(define_predicate "arith_operand"
  (ior (match_operand 0 "const_arith_operand")
       (match_operand 0 "register_operand")))

另外, register_operand 是 gcc 自带的 predicate, 定义在 recog.c 中, 除了 register_operand, gcc 还定义了:

address_operand
immediate_operand
scratch_operand
const_int_operand
const_double_operand
memory_operand
…

1.1.3.1.12. define_peephole2

1.1.3.1.13. match

rtl 生成汇编时需要通过 recog 来找到 rtl 匹配的 insn_code, genrecog 通过扫描 match_xxx 生成各种 pattern 函数, 用来检测 rtl 是否 define_insn 匹配

https://gcc.gnu.org/onlinedocs/gccint/Predicates.html#Predicates

match_operand
match_operand 用来 match operand, 例如:
```
(match_operand:SI      0           "register_operand"    "r")
----------------------------------------------------------------------
               <mode>  <operand>   <predicate>           <constraints>
```
其中 constraints 是针对 predicate 的补充, 例如 r 表示寄存器, m 表示 memory, …

https://gcc.gnu.org/onlinedocs/gccint/Constraints.html#Constraints
match_operator
match_scratch
match_scratch 在生成 rtl 时可以用来分配一个 scratch 寄存器, 在匹配 rtl 时和 `(match_operand … "register_operand")` 差不多.

match_scratch 的典型用法类似这样:
```
(define_insn "swapsi3"
[
 (swap (match_operand:si 1 "register_operand")
   (match_operand:si 2 "register_operand"))
 (clobber (match_scratch:si 0 "=r")
]
""
mov %0, %1\nmov %1, %2\nmov %2, %0
""
)
```
即通过 match_scratch 给 swap 分配一个临时寄存器
match_code
match_test

1.1.3.1.14. define_insn_reservation

1.1.3.1.15. define_bypass

Backlinks

LLVM TableGen (LLVM TableGen): target description 和 gcc machine description 基本是类似, 它们都包含:

1.1.4. rtl

https://www.cse.iitb.ac.in/grc/gcc-workshop-13/downloads/slides/Day3/gccw13-rtl-intro.pdf

https://gcc.gnu.org/onlinedocs/gccint/index.html#toc-RTL-Representation

https://github.com/sunwayforever/hello_world/tree/main/hello_gcc_plugin/trace_with_rtl

rtl (Register Transfer Language) 相当于 gcc LIR, 主要涉及到寄存器分配, 汇编代码生成和底层优化.

例如下面的 rtl:

(insn/f 40 39 41 (set (mem/c:DI (plus:DI (reg/f:DI 2 sp)
                    (const_int 24 [0x18])) [2  S8 A64])
            (reg/f:DI 8 s0)) "test.c":1:21)

表示 `把 24(sp) 的值为 s0`

1.1.4.1. rtl.def

和 optab 一样, rtl 也定义了一些基本操作, rtl.def 相当于 rtl 语言的词汇表, 前面提到的 `set`, `const_int`, `reg` 等都定义在 rtl.def 中.

例如:

DEF_RTL_EXPR(PLUS, "plus", "ee", RTX_COMM_ARITH)

表示:

rtx_code 为 PLUS
name 为 "plus"
format 为 "ee", 表示两个 operand 都是 `expression`
class 为 RTX_COMM_ARITH

多个 rtx 可嵌套, 例如 `(set x (plus a b))`, 其中:

`set`, `plus` 是 rtx_code
`(plus…)` 是 `(set …)` 的 operand, operand 类型可以是 expression, int, string 等, 通过 XEXP, XINT, XWINT 和 XSTR 宏可以访问, 例如XEXP(x, 2) 是获得 x 的 operand[2] (假设它是一个 expression)

可以使用两种方式来写 rtl:

直接在 md 中用纯文本来构造, 然后通过 genemit 生成 rtx, 例如 md 中 `define_insn` 的做法,
通过 gengenrtl 工具扫描 rtl.def 生成权举类型 (例如 PLUS) 和函数 (例如 gen_rtx_PLUS), 然后通过 c 代码来构造 rtx, 参考 md 中 `define_expand` 的做法

1.1.4.2. constant expression

const_int
const_string

label_ref

(define_insn "*branch<mode>"
  [(set (pc)
    (if_then_else
     (match_operator 1 "order_operator"
             [(match_operand:X 2 "register_operand" "r")
              (match_operand:X 3 "reg_or_0_operand" "rJ")])
     (label_ref (match_operand 0 "" ""))
     (pc)))]
  ""
  "b%C1\t%2,%z3,%0")

code_label
…

1.1.4.3. register memory expression

reg
scratch
pc
mem
…

1.1.4.4. arithmetic expression

plus/minus/mult/div/mod
compare
neg
not/and/or/xor/ior
ashift
ss_abs/sqrt
clz/ctz
eq/ne/gt/gtu/lt
if_then_else
cond
…

1.1.4.5. conversion expression

sign_extend/zero_extend
float_extend

float_truncate

把 df truncate 成 sf:

(define_insn "truncdfsf2"
  [(set (match_operand:SF     0 "register_operand" "=f")
    (float_truncate:SF
        (match_operand:DF 1 "register_operand" " f")))]
  "TARGET_DOUBLE_FLOAT"
  "fcvt.s.d\t%0,%1")

truncate
float
…

1.1.4.6. side effect expression

set
call

clobber

clobber 是指 rtl 会隐式的修改这个寄存器, 例如:

(define_insn "call_internal"
  [(call (mem:SI (match_operand 0 "call_insn_operand" "l,S,U"))
     (match_operand 1 "" ""))
   (clobber (reg:SI RETURN_ADDR_REGNUM))]
  ""
  "@
   jalr\t%0
   call\t%0
   call\t%0@plt"
)

call 会隐式给 ra 赋值, 所以用 `(clobber (reg:SI ra))`.

clobber 与 CALL_USED_REGISTERS 的意义类似.

use

use 是指 rtl 会隐式的读取这个寄存器, 防止前面针对这个寄存器的写操作被优化掉,例如:
```
(define_insn "simple_return_internal"
  [(simple_return)
   (use (match_operand 0 "pmode_register_operand" ""))]
  ""
  "jr\t%0"
)
```
表示 simple_return_internal 的第一个 operand 需要被隐式使用.
parallel
…

Backlinks

LLVM Backend (LLVM Backend > instruction selection > SelectionDAG): 可以把 SDAG 看做 gcc rtl, 但与 gcc 不同的是, 生成 SDAG 时并不需要 td, td 中定义的 pattern 只是用来 isel 时做匹配.

1.1.5. example

float foo(float x) {
    if (x > 0.0) {
        return x + 1.0;
    }
    return 0.0;
}

rtl 的 `pass_expand` 用来把 gimple 转换为 rtl, 以 `两个浮点数相加` 为例:

add 对应的 gimple subcode (tree code) 为 PLUS_EXPR, 定义在 tree.def 中
通过 `optab_for_tree_code` 查找 optab, PLUS_EXPR 对应的 optab 为 add_optab, 定义在 optabs.def. PLUS_EXPR 与 add_optab 的对应关系是预设好的. 除了 `optab_for_tree_code`, 有时也会直接在代码中指定 tree code 与 optab 的映射关系
通过 `optab_handler` 查找 (add_optab, E_SFmode) 对应的 insn_code 为 CODE_FOR_addsf3, 定义在 md 中. add_optab 与 CODE_FOR_addsf3 的对应关系由 genopinit 根据 optabs.def 生成 ([email protected])
用 insn_code 做索引在 insn_data 中查找到 `gen_addsf3` 函数. insn_data 由 genoutput 扫描 md 生成. gen_addsf3 由 genemit 生成
gen_addsf3 函数会返回 addsf3 对应的 rtl

1.1.5.1. backtrace

#0  gen_addsf3 (operand0=0x7fffffffb250, operand1=0x7ffff7786bb8,
    operand2=0xf8360d <maybe_legitimize_operands(insn_code, unsigned int, unsigned int, expand_operand*)+46>) at insn-emit.c:45
#1  0x0000000000ef17fa in insn_gen_fn::operator()<rtx_def*, rtx_def*, rtx_def*> (this=0x1ecacb8 <insn_data+56>) at ../.././riscv-gcc/gcc/recog.h:407
#2  0x0000000000f83a1e in maybe_gen_insn (icode=CODE_FOR_addsf3, nops=3, ops=0x7fffffffb250) at ../.././riscv-gcc/gcc/optabs.c:7787
#3  0x0000000000f6ef4a in expand_binop_directly (icode=CODE_FOR_addsf3, mode=E_SFmode, binoptab=add_optab, op0=0x7ffff7786be8, op1=0x7ffff7786c18,
    target=0x7ffff7786bb8, unsignedp=0, methods=OPTAB_LIB_WIDEN, last=0x7ffff7676540) at ../.././riscv-gcc/gcc/optabs.c:1409
#4  0x0000000000f6f417 in expand_binop (mode=E_SFmode, binoptab=add_optab, op0=0x7ffff7786be8, op1=0x7ffff7786c18, target=0x7ffff7786bb8, unsignedp=0,
    methods=OPTAB_LIB_WIDEN) at ../.././riscv-gcc/gcc/optabs.c:1496
#5  0x0000000000c9079a in expand_expr_real_2 (ops=0x7fffffffbb80, target=0x7ffff7786bb8, tmode=E_SFmode, modifier=EXPAND_NORMAL)
    at ../.././riscv-gcc/gcc/expr.c:10007
#6  0x0000000000b197f4 in expand_gimple_stmt_1 (stmt=0x7ffff7784000) at ../.././riscv-gcc/gcc/cfgexpand.c:3947
#7  0x0000000000b199f1 in expand_gimple_stmt (stmt=0x7ffff7784000) at ../.././riscv-gcc/gcc/cfgexpand.c:4008
#8  0x0000000000b20b17 in expand_gimple_basic_block (bb=0x7ffff7761138, disable_tail_calls=false) at ../.././riscv-gcc/gcc/cfgexpand.c:6045
#9  0x0000000000b223d3 in (anonymous namespace)::pass_expand::execute (this=0x23401c0, fun=0x7ffff777e000) at ../.././riscv-gcc/gcc/cfgexpand.c:6729
#10 0x0000000000fdd7d1 in execute_one_pass (pass=0x23401c0) at ../.././riscv-gcc/gcc/passes.c:2567
#11 0x0000000000fddb1e in execute_pass_list_1 (pass=0x23401c0) at ../.././riscv-gcc/gcc/passes.c:2656
#12 0x0000000000fddbab in execute_pass_list (fn=0x7ffff777e000, pass=0x233c270) at ../.././riscv-gcc/gcc/passes.c:2667
#13 0x0000000000b6f617 in cgraph_node::expand (this=0x7ffff7780000) at ../.././riscv-gcc/gcc/cgraphunit.c:1830
#14 0x0000000000b6fd15 in cgraph_order_sort::process (this=0x2333788) at ../.././riscv-gcc/gcc/cgraphunit.c:2069
#15 0x0000000000b6ffce in output_in_order () at ../.././riscv-gcc/gcc/cgraphunit.c:2137
#16 0x0000000000b705a6 in symbol_table::compile (this=0x7ffff7670000) at ../.././riscv-gcc/gcc/cgraphunit.c:2355
#17 0x0000000000b709d2 in symbol_table::finalize_compilation_unit (this=0x7ffff7670000) at ../.././riscv-gcc/gcc/cgraphunit.c:2539
#18 0x000000000110d05f in compile_file () at ../.././riscv-gcc/gcc/toplev.c:482
#19 0x00000000011100c6 in do_compile () at ../.././riscv-gcc/gcc/toplev.c:2201
#20 0x00000000011103e8 in toplev::main (this=0x7fffffffc176, argc=14, argv=0x7fffffffc288) at ../.././riscv-gcc/gcc/toplev.c:2340
#21 0x0000000001bf4bf5 in main (argc=14, argv=0x7fffffffc288) at ../.././riscv-gcc/gcc/main.c:39

1.1.5.2. gimple code

float foo (float x)
{
  float D.1491;
  float _1;
  float _3;
  float _4;

  <bb 2> :
  if (x_2(D) > 0.0)
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :
  _4 = x_2(D) + 1.0e+0;
  // predicted unlikely by early return (on trees) predictor.
  goto <bb 5>; [INV]

  <bb 4> :
  _3 = 0.0;

  <bb 5> :
  # _1 = PHI <_4(3), _3(4)>
<L2>:
  return _1;

1.1.5.3. cbranch_optab

bb2 的第一个 stmt `if (x_2(D) > 0.0)` 的处理过程:

expand_gimple_basic_block()
    if (gimple_code (stmt) == GIMPLE_COND):
        new_bb = expand_gimple_cond (bb, as_a <gcond *> (stmt));

expand_gimple_cond:
   /* tree code 为 GT_EXPR, 定义在 tree.def */
    code = gimple_cond_code (stmt);
    if (true_edge->dest == bb->next_bb):
        jumpifnot_1 (code, op0, op1, label_rtx_for_bb (false_edge->dest), false_edge->probability);

label_rtx_for_bb:
    rtx_code_label *l = gen_label_rtx ();
        /* gen_rtx_CODE_LABEL 生成一个 `code_label` rtx */
        return as_a <rtx_code_label *> (gen_rtx_CODE_LABEL (VOIDmode, NULL_RTX, NULL_RTX,NULL, label_num++, NULL));

jumpifnot_1:
    /* code 为 GT */
    do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode,((mode == BLKmode) ? expr_size (treeop0) : NULL_RTX),
               if_false_label, if_true_label, prob);
        emit_cmp_and_jump_insns (op0, op1, code, size, mode, unsignedp, if_true_label, prob);
            prepare_cmp_insn (op0, op1, comparison, size, unsignedp, OPTAB_LIB_WIDEN, &test, &mode);
                /* cbranchsf4 要求 3 个参数, operand0 是要 test 的条件, comparison 是 GT */
                test = gen_rtx_fmt_ee (comparison, VOIDmode, x, y);
                enum insn_code icode;
                /* NOTE: 映射到 cbranch_optab, 后者又映射为 CODE_FOR_cbranchsf4 */
                icode = optab_handler (cbranch_optab, cmp_mode);
                rtx op0 = prepare_operand (icode, x, 1, mode, cmp_mode, unsignedp);
                rtx op1 = prepare_operand (icode, y, 2, mode, cmp_mode, unsignedp);
                XEXP (test, 0) = op0;
                XEXP (test, 1) = op1;
                /* NOTE: test 是要返回的 rtx  */
                *ptest = test;
        emit_cmp_and_jump_insn_1
            /* NOTE: GEN_FCN(icode) 即 gen_cbranchsf4 */
            insn = emit_jump_insn (GEN_FCN (icode) (test, XEXP (test, 0), XEXP (test, 1), label));

1.1.5.4. add_optab

bb3 的第一个 stmt `_4 = x_2(D) + 1.0e+0` 的处理过程:

expand_gimple_basic_block:
    expand_gimple_stmt(stmt);
       /* stmt->code 为 GIMPLE_ASSIGN, stmt->subcode (tree code) 为 PLUS_EXPR */
       /* target 是需要被 assign 的 rtx (例如 reg) */
       temp = expand_expr_real_2 (&ops, target, GET_MODE (target), EXPAND_NORMAL);
           /* NOTE: code 为 PLUS_EXPR, 返回的 this_optab 为 add_optab */
           this_optab = optab_for_tree_code (code, type, optab_default);
           /* mode 为 E_SFmode */
           temp = expand_binop (mode, this_optab, op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
               /* NOTE: icode 为 CODE_FOR_addsf3 */
               icode = optab_handler (binoptab, mode);
               create_output_operand (&ops[0], target, tmp_mode);
               create_input_operand (&ops[1], xop0, mode0);
               create_input_operand (&ops[2], xop1, mode1);
               pat = maybe_gen_insn (icode, 3, ops);
                   /* NOTE: 生成 rtx */
                   gen_addsf3();

1.1.5.5. mov_optab

bb4 的第一个 stmt `_3 = 0.0` 的处理过程:

expand_gimple_stmt:
    /* stmt->code 为 GIMPLE_ASSIGN, stmt->subcode 为 REAL_CST (real constant) */
    expand_assignment (lhs, rhs, ...)
      result = store_expr (from, to_rtx, 0, nontemporal, false);
          emit_move_insn (target, temp);
              /* NOTE: mov_optab 对应 CODE_FOR_movsf */
              code = optab_handler (mov_optab, mode);
              /* NOTE: gen_movesf */
              emit_insn (GEN_FCN (code) (x, y));

1.2. rtl optimization

https://gcc.gnu.org/onlinedocs/gccint/RTL-passes.html

pass_combine
pass_peephole2
pass_cse
pass_fast_rtl_dce

1.3. insn schedule

pass_sched

1.4. register allocation

pass_ira 和 pass_reload

1.5. code emission

rtl 最终由 pass_final 生成 assembly

通过 recog 函数查找 rtl 对应的 insn_code. recog 由 genrecog 扫描 md 生成. 整个 recog 相当于一个根据 md 生成的巨大的 switch-case
通过 `get_insn_template` 从 insn_data 以 insn_code 为索引查找汇编模板

1.5.1. backtrace

#0  get_insn_template (code=0, insn=0x7fffffffbc00) at ../.././riscv-gcc/gcc/final.c:2063
#1  0x0000000000ca46cb in final_scan_insn_1 (insn=0x7ffff7676880, file=0x2352480, optimize_p=0, nopeepholes=0, seen=0x7fffffffbdbc)
    at ../.././riscv-gcc/gcc/final.c:3062
#2  0x0000000000ca4b06 in final_scan_insn (insn=0x7ffff7676880, file=0x2352480, optimize_p=0, nopeepholes=0, seen=0x7fffffffbdbc)
    at ../.././riscv-gcc/gcc/final.c:3175
#3  0x0000000000ca2a44 in final_1 (first=0x7ffff77870a8, file=0x2352480, seen=0, optimize_p=0) at ../.././riscv-gcc/gcc/final.c:2022
#4  0x0000000000ca76c5 in rest_of_handle_final () at ../.././riscv-gcc/gcc/final.c:4680
#5  0x0000000000ca792f in (anonymous namespace)::pass_final::execute (this=0x2342260) at ../.././riscv-gcc/gcc/final.c:4758
#6  0x0000000000fdd7d1 in execute_one_pass (pass=0x2342260) at ../.././riscv-gcc/gcc/passes.c:2567
#7  0x0000000000fddb1e in execute_pass_list_1 (pass=0x2342260) at ../.././riscv-gcc/gcc/passes.c:2656
#8  0x0000000000fddb4f in execute_pass_list_1 (pass=0x2341d80) at ../.././riscv-gcc/gcc/passes.c:2657
#9  0x0000000000fddb4f in execute_pass_list_1 (pass=0x2340220) at ../.././riscv-gcc/gcc/passes.c:2657
#10 0x0000000000fddbab in execute_pass_list (fn=0x7ffff777e000, pass=0x233c270) at ../.././riscv-gcc/gcc/passes.c:2667
#11 0x0000000000b6f617 in cgraph_node::expand (this=0x7ffff7780000) at ../.././riscv-gcc/gcc/cgraphunit.c:1830
#12 0x0000000000b6fd15 in cgraph_order_sort::process (this=0x2333788) at ../.././riscv-gcc/gcc/cgraphunit.c:2069
#13 0x0000000000b6ffce in output_in_order () at ../.././riscv-gcc/gcc/cgraphunit.c:2137
#14 0x0000000000b705a6 in symbol_table::compile (this=0x7ffff7670000) at ../.././riscv-gcc/gcc/cgraphunit.c:2355
#15 0x0000000000b709d2 in symbol_table::finalize_compilation_unit (this=0x7ffff7670000) at ../.././riscv-gcc/gcc/cgraphunit.c:2539
#16 0x000000000110d05f in compile_file () at ../.././riscv-gcc/gcc/toplev.c:482
#17 0x00000000011100c6 in do_compile () at ../.././riscv-gcc/gcc/toplev.c:2201
#18 0x00000000011103e8 in toplev::main (this=0x7fffffffc176, argc=14, argv=0x7fffffffc288) at ../.././riscv-gcc/gcc/toplev.c:2340
#19 0x0000000001bf4bf5 in main (argc=14, argv=0x7fffffffc288) at ../.././riscv-gcc/gcc/main.c:39

1.5.2. final_scan_insn_1

final_scan_insn_1:
    /* insn code 在 rtl.def 中定义 */
    switch (GET_CODE (insn)):
        case CODE_LABEL:
            /* internal_label 指向 default_internal_label, 产生 .L6: 形式的 label */
            targetm.asm_out.internal_label (file, "L", CODE_LABEL_NUMBER (insn));
                char *const buf = (char *) alloca (40 + strlen (prefix));
                ASM_GENERATE_INTERNAL_LABEL (buf, prefix, labelno);
                ASM_OUTPUT_INTERNAL_LABEL (stream, buf);

        default:
            insn_code_number = recog_memoized (insn);
            templ = get_insn_template (insn_code_number, insn);
            output_asm_insn (templ, recog_data.operand);

1.5.3. recog_memoized

recog_memoized 的作用是根据 rtl 查找它对应的 insn_code, 查找的依据是 md 中声明的 predicate.

最简单的 recog 实现可以这样:

针对一条 rtl, 与 md 中所有 insn 的 rtl 模板比较, 看哪一条 insn 匹配.

但实际实现上 recog 采用的是类似于字典树 (trie) 的方式:

genrecog 工具会扫描 md 中所有的 insn, 根据 insn 声明的 predicate 构造一棵树, 例如:

A 指令的 predicate 为 x, y, z
B 指令的 predicate 为 x, y, k

则 genrecog 会生成一棵这样的树:

x--->y--->z
     |
     +--->k

genrecog 生成的 recog 函数会在这棵树上遍历来匹配 insn

1.5.3.1. movdi_64bit

以 movdi_64bit 为例, 要匹配的 insn 为:

(insn/f 40 39 41
        (set (mem/c:DI (plus:DI (reg/f:DI 2 sp) (const_int 24 [0x18])) [2  S8 A64])
        (reg/f:DI 8 s0)) "test.c":1:21
)

recog 的过程为:

static inline int recog_memoized(rtx_insn *insn) {
    if (INSN_CODE(insn) < 0) INSN_CODE(insn) = recog(PATTERN(insn), insn, 0);
    return INSN_CODE(insn);
}

/* x1 为 PATTERN(insn):
 *
 * (set (mem/c:DI (plus:DI (reg/f:DI 2 sp)
 *             (const_int 24 [0x18])) [2  S8 A64])
 *     (reg/f:DI 8 s0))
 *
 */
recog(x1, insn):
    switch (GET_CODE (x1)):
        /* x1->code=SET */
        case SET:
            return recog_19 (x1, insn, pnum_clobbers);

static int recog_19(
    rtx x1 ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED,
    int *pnum_clobbers ATTRIBUTE_UNUSED) {
    rtx *const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];
    rtx x2, x3, x4, x5, x6, x7;
    int res ATTRIBUTE_UNUSED;
    x2 = XEXP(x1, 1);
    /* NOTE: x2 为 (reg/f:DI 8 s0) */
    switch (GET_CODE(x2)) {
        case REG:
        case SUBREG:
        case MEM:
        case LABEL_REF:
        case SYMBOL_REF:
        case HIGH:
            return recog_7(x1, insn, pnum_clobbers);

    }


static int recog_7 (rtx x1 ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED, int *pnum_clobbers ATTRIBUTE_UNUSED):
    /* NOTE: x2 为
     *  (mem/c:DI (plus:DI (reg/f:DI 2 sp)
     *   (const_int 24 [0x18])) [2  S8 A64])
     * */
    x2 = XEXP (x1, 0);
    switch (GET_CODE (x2)) {
        case MEM:
            res = recog_2 (x1, insn, pnum_clobbers);
    }

static int recog_2 (rtx x1 ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED, int *pnum_clobbers ATTRIBUTE_UNUSED):
    x2 = XEXP (x1, 0);
    operands[0] = x2;
    x3 = XEXP (x1, 1);
    operands[1] = x3;
    switch (GET_MODE (operands[0])):
        case E_DImode:
            if ((TARGET_64BIT
                   && (register_operand (operands[0], DImode)
                      || reg_or_0_operand (operands[1], DImode))))
                return 135; /* *movdi_64bit */
            break;

最终匹配的 insn_code 为 135, 对应 riscv.md 中的:

(define_insn "*movdi_64bit"
  [(set (match_operand:DI 0 "nonimmediate_operand" "=r,r,r, m,  *f,*f,*r,*f,*m")
    (match_operand:DI 1 "move_operand"         " r,T,m,rJ,*r*J,*m,*f,*f,*f"))]
  "TARGET_64BIT
   && (register_operand (operands[0], DImode)
       || reg_or_0_operand (operands[1], DImode))"
  { return riscv_output_move (operands[0], operands[1]); }
  [(set_attr "move_type" "move,const,load,store,mtc,fpload,mfc,fmove,fpstore")
   (set_attr "mode" "DI")])

1.5.3.2. addsf3 vs. adddi3

recog 可以看做是一棵决策树, 以 addsf3 和addi3 为例:

(define_insn "addsf3"
  [(set (match_operand:SF            0 "register_operand" "=f")
    (plus:SF (match_operand:SF 1 "register_operand" " f")
           (match_operand:SF 2 "register_operand" " f")))]
  "TARGET_HARD_FLOAT"
  "fadd.s\t%0,%1,%2"
)

(define_insn "addsi3"
  [(set (match_operand:SI          0 "register_operand" "=r,r")
    (plus:SI (match_operand:SI 1 "register_operand" " r,r")
         (match_operand:SI 2 "arith_operand"    " r,I")))]
  ""
  { return TARGET_64BIT ? "add%i2w\t%0,%1,%2" : "add%i2\t%0,%1,%2"; }
)

recog 针对 addsf3 的决策树是: set->plus->GET_MODE(operand[0])==SF recog 针对 adddi3 的决策树是: set->plus->GET_MODE(operand[0])==DI

int recog(
    rtx x1 ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED,
    int *pnum_clobbers ATTRIBUTE_UNUSED) {
    switch (GET_CODE(x1)):
        case SET:
            /* NOTE: set */
            return recog_19(x1, insn, pnum_clobbers);

static int recog_19(
    rtx x1 ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED,
    int *pnum_clobbers ATTRIBUTE_UNUSED) {
    x2 = XEXP(x1, 1);
    switch (GET_CODE(x2)) {
        /* NOTE: plus */
        case PLUS:
            x3 = XEXP(x1, 0);
            operands[0] = x3;

            /* 虽然 addsf3 通过 match_oprand 给 plus 的 src 和 target 都指定了
             * mode, 但这里只使用了 target 的 mode, 后续会通过
             * pattern0/pattern10 等检查所有的 mode 都匹配, 这里的 switch mode 相当于一个 */
            switch (GET_MODE(operands[0])) {
                case E_SFmode:
                    if (pattern0(x2, E_SFmode) != 0 || !(TARGET_HARD_FLOAT))
                        return -1;
                    return 1; /* addsf3 */

                case E_DImode:
                    if (pattern10(x2, E_DImode) != 0 || !(TARGET_64BIT))
                        return -1;
                    return 4; /* adddi3 */

static int pattern0 (rtx x1, machine_mode i1) {
  rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];
  int res ATTRIBUTE_UNUSED;
  if (!register_operand (operands[0], i1)
      || GET_MODE (x1) != i1
      || !register_operand (operands[1], i1)
      || !register_operand (operands[2], i1))
    return -1;
  return 0;
}

1.5.4. get_insn_template

const char *get_insn_template(int code, rtx_insn *insn) {
    const char *ret;
    switch (insn_data[code].output_format) {
        case INSN_OUTPUT_FORMAT_SINGLE:
            ret = insn_data[code].output.single;
            break;
        case INSN_OUTPUT_FORMAT_MULTI:
            ret = insn_data[code].output.multi[which_alternative];
            break;
        /* NOTE: 135 对应的 insn_data 的 output_format 为 INSN_OUTPUT_FORMAT_FUNCTION, 因为 md 文件中指定了
         *   { return riscv_output_move (operands[0], operands[1]); }
         * */
        case INSN_OUTPUT_FORMAT_FUNCTION:
            gcc_assert(insn);
            /* NOTE: 这里的 output.function 就是  riscv_output_move */
            ret = (*insn_data[code].output.function)(recog_data.operand, insn);
            break;
    }
    return ret;
}

riscv_output_move:
    /* dest_code 为 MEM */
    dest_code = GET_CODE (dest);
    /* src_code 为 REG */
    src_code = GET_CODE (src);
    if ((src_code == REG && GP_REG_P (REGNO (src))) || (src == CONST0_RTX (mode))):
        if (dest_code == MEM):
            switch (GET_MODE_SIZE (mode))
            {
                case 1: return "sb\t%z1,%0";
                case 2: return "sh\t%z1,%0";
                case 4: return "sw\t%z1,%0";
                /* NOTE: 最后 match 的是这一句: */
                case 8: return "sd\t%z1,%0";
            }

1.5.5. output_asm_insn

void output_asm_insn (const char *templ, rtx *operands):
    /* NOTE: templ 为 sd\t%z1,%0 */
    /* output_asm_insn 会遍历并打印出 templ, 碰到 % 会特殊处理,
     * % 后面的特殊字符例如 z 决定了 operand 例如 1 如何处理
     * gcc 本身支持的特殊字符包括:
     * a : address
     * c : const address
     * l : label
     * n : int
     * 除此以外, target 可以实现自己的 TARGET_PRINT_OPERAND 来定义
     * 自己的特殊字符, 例如这里的 c 就是 riscv 自己定义的字符
     * %0 这种没有指定特殊字符的 operand 会使用默认的方式处理
     * */

     /* %z1 通过 riscv_print_operand 来处理, 返回 s0 */
     /* %0 通过 output_operand 处理*/
     output_operand (operands[opnum], letter);
         /* x 是 (mem (plus ...)) 这个 rtx, code 为 0, 因为没有 format letter*/
         targetm.asm_out.print_operand (asm_out_file, x, code);

static void riscv_print_operand (FILE *file, rtx op, int letter):
    machine_mode mode = GET_MODE (op);
    enum rtx_code code = GET_CODE (op);

    switch (letter):
        /*
         * ...
         */
        default:

        switch (code):
          case MEM:
            /* XEXP(op,0) 为
             * (plus:DI (reg/f:DI 2 sp)
             *   (const_int 24 [0x18]))
             * */
            output_address (mode, XEXP (op, 0));
          break;

void output_address (machine_mode mode, rtx x) {
  bool changed = false;
  walk_alter_subreg (&x, &changed);
  /* TARGET_PRINT_OPERAND_ADDRESS */
  targetm.asm_out.print_operand_address (asm_out_file, mode, x);
}

static void riscv_print_operand_address (FILE *file, machine_mode mode, rtx x):
    struct riscv_address_info addr;
    if (riscv_classify_address (&addr, x, word_mode, true))
        switch (addr.type) {
            case ADDRESS_REG:
                /* NOTE: 这里会输出 24 */
                riscv_print_operand (file, addr.offset, 0);
                /* NOTE: 这里会接着输出 (sp), 所以 (mem ...) 最终打印出 `24(sp)` */
                fprintf (file, "(%s)", reg_names[REGNO (addr.reg)]);
                return;

所以下面的 rtl:

(insn/f 40 39 41 (set (mem/c:DI (plus:DI (reg/f:DI 2 sp)
                (const_int 24 [0x18])) [2  S8 A64])
        (reg/f:DI 8 s0)) "test.c":1:21)

对应的汇编为:

sd  s0,24(sp)

1.6. misc

1.6.1. target hook

理想情况下 backend 相关代码会依赖 md 文件获得需要的信息, 但实际情况是有些信息无法放在 md 中, 这些信息会放在 target hook 和 target macro 中.

另外, 虽然理论上编译器的前中后端应该是独立的, 但实际上有时前中端也需要 target hook 和 target macro 提供的信息才能工作, 例如:

后端是否支持某种指令 (例如 pass_loop_prefetch 优化依赖 TARGET_HAVE_PREFETCH 这个 target macro 决定是否进行 prefetch)
后端是否支持某个 optab (例如 pass_cse_sincos 优化会依赖 TARGET_OPTAB_SUPPORTED_P 把 pow(x,0.5) 优化成 sqrt(x), 或者 pass_lower_vector 需要根据后端是否支持向量指令决定是否在 gimple 优化阶段把向量操作转换为标量操作)

1.6.2. intrinsic

通过 intrinsic 可以扩展 gcc 以支持 backend 自定义指令. 例如, 假设 backend 包含许多 dsp 指令 (例如 RISC-V P Extension), 那么支持它有两种方式:

使用 pass_combine 和 pass_peephole2 等让 gcc 自动生成 dsp 指令
定义 intrinsic 让用户直接调用这些指令

参考 P Extension 的提交:

https://github.com/riscv-collab/riscv-gcc/pull/258

1.6.3. mcpu/mtune/march/mabi

1.6.3.1. mcpu

`-mcpu` 参数是 mtune 和 march 的结合体, 例如

RISCV_CORE("sifive-e31",      "rv32imac",   "sifive-3-series")

表示 `-mcpu=sifive-e31` 等价于 `-march=rv32imac -mtune=sifive-3-series`

1.6.3.2. march

解析 march 的函数主要是 riscv_parse_arch_string, 通过一些宏可以访问解析的结果:

static const riscv_ext_flag_table_t riscv_ext_flag_table[] = {
    {"e", &gcc_options::x_target_flags, MASK_RVE},
    {"m", &gcc_options::x_target_flags, MASK_MUL},
    {"a", &gcc_options::x_target_flags, MASK_ATOMIC},
    {"f", &gcc_options::x_target_flags, MASK_HARD_FLOAT},
    {"d", &gcc_options::x_target_flags, MASK_DOUBLE_FLOAT},
    {"c", &gcc_options::x_target_flags, MASK_RVC},

    {"zicsr", &gcc_options::x_riscv_zi_subext, MASK_ZICSR},
    {"zifencei", &gcc_options::x_riscv_zi_subext, MASK_ZIFENCEI},

    {NULL, NULL, 0}};

/*
 * target_flags 为 global_options.x_target_flags
 */
#define TARGET_64BIT ((target_flags & MASK_64BIT) != 0)
#define TARGET_ATOMIC ((target_flags & MASK_ATOMIC) != 0)
#define TARGET_DOUBLE_FLOAT ((target_flags & MASK_DOUBLE_FLOAT) != 0)
#define TARGET_HARD_FLOAT ((target_flags & MASK_HARD_FLOAT) != 0)
#define TARGET_MUL ((target_flags & MASK_MUL) != 0)
#define TARGET_RVC ((target_flags & MASK_RVC) != 0)
#define TARGET_RVE ((target_flags & MASK_RVE) != 0)

/* 应用 march 设置的主要途径是 md 中会大量使用这些宏做为 match 的 predicate */

(define_insn "mul<mode>3"
  [(set (match_operand:ANYF               0 "register_operand" "=f")
    (mult:ANYF (match_operand:ANYF    1 "register_operand" " f")
              (match_operand:ANYF 2 "register_operand" " f")))]
  "TARGET_HARD_FLOAT"
  "fmul.<fmt>\t%0,%1,%2"
 )

(define_insn "mulsi3"
  [(set (match_operand:SI          0 "register_operand" "=r")
    (mult:SI (match_operand:SI 1 "register_operand" " r")
         (match_operand:SI 2 "register_operand" " r")))]
  "TARGET_MUL"
  { return TARGET_64BIT ? "mulw\t%0,%1,%2" : "mul\t%0,%1,%2"; }
 )

/* 其中在代码中也会有一些针对 TARGET_XXX 的设置, 例如 soft-float 时无法使用 fpr */
static void riscv_conditional_register_usage (void) {
    /* ... */
    if (!TARGET_HARD_FLOAT) {
        for (int regno = FP_REG_FIRST; regno <= FP_REG_LAST; regno++)
            fixed_regs[regno] = call_used_regs[regno] = 1;
    }
    /* ... */
}

Backlinks

TARGET_CPU_CPP_BUILTINS (GCC Target Hook > runtime target 相关 > TARGET_CPU_CPP_BUILTINS): gcc 通过 march 定义了 TARGET_MUL 等 macro, 但它们是给 gcc 使用的. 应用代码如果要得到 TARGET_MUL 类似的功能, 需要使用 TARGET_CPU_CPP_BUILTINS 通过 builtin_define 定义的 __riscv_mul

1.6.3.3. mtune

1.6.3.4. mabi

static const struct cl_enum_arg cl_enum_abi_type_data[] = {
    {"ilp32", ABI_ILP32, 0},   {"ilp32d", ABI_ILP32D, 0},
    {"ilp32e", ABI_ILP32E, 0}, {"ilp32f", ABI_ILP32F, 0},
    {"lp64", ABI_LP64, 0},     {"lp64d", ABI_LP64D, 0},
    {"lp64f", ABI_LP64F, 0},   {NULL, 0, 0}};

/* 通过这个 define 限制 ILP32/LP64 无法使用 fpr 传递参数 */
#define UNITS_PER_FP_ARG                                                \
  ((riscv_abi == ABI_ILP32 || riscv_abi == ABI_ILP32E                   \
    || riscv_abi == ABI_LP64)                                           \
   ? 0                                                                  \
   : ((riscv_abi == ABI_ILP32F || riscv_abi == ABI_LP64F) ? 4 : 8))

1.6.3.4.1. example

$> cat test.c

extern float hello(float x);

float foo(float x) {
    return x + hello(x);
}

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.c -c -O0 -march=rv64i -mabi=lp64 -S -o-

foo:
        addi    sp,sp,-32
        sd      ra,24(sp)
        sd      s0,16(sp)
        addi    s0,sp,32
        sw      a0,-20(s0)
        lw      a0,-20(s0)
        # hello 的参数和返回值通过 gpr (a0)
        call    hello
        mv      a5,a0
        lw      a1,-20(s0)
        mv      a0,a5
        # 使用软浮点
        call    __addsf3
        mv      a5,a0
        mv      a0,a5
        ld      ra,24(sp)
        ld      s0,16(sp)
        addi    sp,sp,32
        jr      ra

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.c -c -O0 -march=rv64if -mabi=lp64 -S -o-

foo:
        addi    sp,sp,-32
        sd      ra,24(sp)
        sd      s0,16(sp)
        addi    s0,sp,32
        sw      a0,-20(s0)
        lw      a0,-20(s0)
        # hello 的参数还是用的 gpr
        call    hello
        mv      a4,a0
        lw      a5,-20(s0)
        # 使用 hard float
        fadd.s  a5,a4,a5
        fmv.w.x fa5,a5
        fmv.x.w a0,fa5
        ld      ra,24(sp)
        ld      s0,16(sp)
        addi    sp,sp,32
        jr      ra

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.c -c -O0 -march=rv64if -mabi=lp64f -S -o-

foo:
        addi    sp,sp,-32
        sd      ra,24(sp)
        sd      s0,16(sp)
        addi    s0,sp,32
        fsw     fa0,-20(s0)
        flw     fa0,-20(s0)
        # heloo 的参数和返回值使用 fpr (fa0)
        call    hello
        fmv.x.w a4,fa0
        lw      a5,-20(s0)
        # 使用 hard float
        fadd.s  a5,a4,a5
        fmv.w.x fa5,a5
        fmv.s   fa0,fa5
        ld      ra,24(sp)
        ld      s0,16(sp)
        addi    sp,sp,32
        jr      ra

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.c -c -O0 -march=rv64i -mabi=lp64f -S -o-
cc1: error: requested ABI requires '-march' to subsume the 'F' extension

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.c -c -O0 -march=rv32i -mabi=lp64 -S -o-
cc1: error: ABI requires '-march=rv64'

1.6.3.5. march vs. mabi

https://www.sifive.com/blog/all-aboard-part-1-compiler-args

riscv 的 march 可以指定 rv{32,64}{i,f,d,m,a,g,v,c}, 用来指定产生什么样的硬件指令, 例如 `gcc -march=rv32ifd`
riscv 的 mabi 是指在与 march 不冲突的基础上, 函数调用时使用什么样的指令/寄存器. riscv mabi 包括:
1. ilp32{"",f,d}
  
  ilp32 指 int, long, pointer 是 32 bit, f 指支持 hard single float, d 指支持 hard double float
2. lp64{"",f,d}

Backlinks

GCC (GCC > Backend): Backend

GCC Target Hook (GCC Target Hook): GCC Backend 的 example 里看到的

Retargeting GCC To RISC-V (Retargeting GCC To RISC-V > gcc > gcc backend): gcc backend

GCC Backend

Table of Contents

1. GCC Backend

1.1. insn selection

1.1.1. gimple tree code

1.1.2. optab

1.1.2.1. 构造 optab_handler

1.1.2.1.1. genopinit

1.1.2.1.2. find_optab

1.1.2.1.3. match_pattern

1.1.2.2. optab_libfunc

Backlinks

Backlinks

1.1.3. machine desc

1.1.3.1. md 语法

1.1.3.1.1. define_insn

1.1.3.1.2. define_expand

1.1.3.1.3. define_split

1.1.3.1.4. define_mode_iterator

1.1.3.1.5. define_mode_attr

1.1.3.1.6. define_code_iterator

1.1.3.1.7. define_code_attr

1.1.3.1.8. define_c_enum

1.1.3.1.9. define_constants

1.1.3.1.10. define_attr

1.1.3.1.11. define_predicate

1.1.3.1.12. define_peephole2

1.1.3.1.13. match

1.1.3.1.14. define_insn_reservation

1.1.3.1.15. define_bypass

Backlinks

1.1.4. rtl

1.1.4.1. rtl.def

1.1.4.2. constant expression

1.1.4.3. register memory expression

1.1.4.4. arithmetic expression

1.1.4.5. conversion expression

1.1.4.6. side effect expression

Backlinks

1.1.5. example

1.1.5.1. backtrace

1.1.5.2. gimple code

1.1.5.3. cbranch_optab

1.1.5.4. add_optab

1.1.5.5. mov_optab

1.2. rtl optimization

1.3. insn schedule

1.4. register allocation

1.5. code emission

1.5.1. backtrace

1.5.2. final_scan_insn_1

1.5.3. recog_memoized

1.5.3.1. movdi_64bit

1.5.3.2. addsf3 vs. adddi3

1.5.4. get_insn_template

1.5.5. output_asm_insn

1.6. misc

1.6.1. target hook

1.6.2. intrinsic

1.6.3. mcpu/mtune/march/mabi

1.6.3.1. mcpu

1.6.3.2. march

Backlinks

1.6.3.3. mtune

1.6.3.4. mabi

1.6.3.4.1. example

1.6.3.5. march vs. mabi

Backlinks