GCC Scheduler

Table of Contents

1. GCC Scheduler

https://en.wikipedia.org/wiki/Instruction_scheduling

https://gcc.gnu.org/wiki/InstructionScheduling

https://gcc.gnu.org/onlinedocs/gccint/Scheduling.html

指令调度有几个作用：

  1. 减少流水线 stall, 例如: 

    ## before
lw a0, 0(sp)
addi a0, a0, 1
addi a1, a1, 1
addi a2, a2, 1
## after
lw a0, 0(sp)
addi a1, a1, 1
addi a2, a2, 1
addi a0, a0, 1

    由于 cpu 本身支持 out-of-order 和 register renaming, 所以 gcc 的 scheduler 针对流水线 stall 的作用可能并不是特别重要

  2. 降低寄存器分配的压力, 例如: 

    # before
lw a0, 0(sp)
lw a1, 4(sp)
addi a0, a0, 1
addi a1, a1, 1
sw a0, 0(sp)
sw a1, 4(sp)
# after
lw a0, 0(sp)
addi a0, a0, 1
sw a0, 0(sp)
lw a0, 4(sp)
addi a0, a0, 1
sw a0, 4(sp)

scheduler 算法包括 haifa-sched, modulo-sched, sel-sched, 默认应该使用的是 haifa, scheduler 的入口是 pass_sched

scheduler 工作时和硬件的 pipeline, issue_rate 是紧密相关的, 需要 backend 去定义, 例如 target hook 中的 TARGET_SCHED_ISSUE_RATE 以及 riscv_tune_info 中 microarchitecture.

1.1. example

void foo(int k) {
    int x = 0;
    int y = 0;
    int z = 0;
    x = 1;
    y = 1;
    z = 1;
}

使用了 scheduler: 

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc  test.c -O0  -c -fenable-rtl-sched1
$> /opt/riscv/bin/riscv64-unknown-linux-gnu-objdump -d ./test.o

0000000000000000 <foo>:
   0:   7179                    addi    sp,sp,-48
   2:   f422                    sd      s0,40(sp)
   4:   1800                    addi    s0,sp,48
   6:   87aa                    mv      a5,a0
   8:   863e                    mv      a2,a5
   a:   fe042623                sw      zero,-20(s0)
   e:   fe042423                sw      zero,-24(s0)
  12:   fe042223                sw      zero,-28(s0)
  16:   4685                    li      a3,1
  18:   4705                    li      a4,1
  1a:   4785                    li      a5,1
  1c:   fcc42e23                sw      a2,-36(s0)
  20:   fed42623                sw      a3,-20(s0)
  24:   fee42423                sw      a4,-24(s0)
  28:   fef42223                sw      a5,-28(s0)
  2c:   0001                    nop
  2e:   7422                    ld      s0,40(sp)
  30:   6145                    addi    sp,sp,48
  32:   8082                    ret

没使用 scheduler: 

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc  test.c -O0  -c
$> /opt/riscv/bin/riscv64-unknown-linux-gnu-objdump -d ./test.o

0000000000000000 <foo>:
   0:   7179                    addi    sp,sp,-48
   2:   f422                    sd      s0,40(sp)
   4:   1800                    addi    s0,sp,48
   6:   87aa                    mv      a5,a0
   8:   fcf42e23                sw      a5,-36(s0)
   c:   fe042623                sw      zero,-20(s0)
  10:   fe042423                sw      zero,-24(s0)
  14:   fe042223                sw      zero,-28(s0)
  18:   4785                    li      a5,1
  1a:   fef42623                sw      a5,-20(s0)
  1e:   4785                    li      a5,1
  20:   fef42423                sw      a5,-24(s0)
  24:   4785                    li      a5,1
  26:   fef42223                sw      a5,-28(s0)
  2a:   0001                    nop
  2c:   7422                    ld      s0,40(sp)
  2e:   6145                    addi    sp,sp,48
  30:   8082                    ret

1.2. TARGET_SCHED_ISSUE_RATE

单个 cycle 可以发射的指令数量, 默认为 1

TODO 找一个能显示 issue_rate 区别的例子

Backlinks

GCC Target Hook (GCC Target Hook > schedule 相关 > TARGET_SCHED_ISSUE_RATE): TARGET_SCHED_ISSUE_RATE

mtune (mtune > riscv_tune_param > issue_rate): TARGET_SCHED_ISSUE_RATE 会使用这个 tune_param

1.3. microarchitecture

scheduler 工作时需要一个关键信息是指令的 latency, 例如 `sqrtsf2` 的 latency 在 sifive-3 是 25, 在 sifive-7 是 27, 这个值看起来和 GCC Cost 有点类似?

gcc 定义 microarchitecture 的机制称为 automaton

以 adddf3 为例:

riscv.md: 

(define_insn "adddf3"
  [(set (match_operand:ANYF            0 "register_operand" "=f")
    (plus:ANYF (match_operand:ANYF 1 "register_operand" " f")
           (match_operand:ANYF 2 "register_operand" " f")))]
  "TARGET_HARD_FLOAT"
  "fadd.<fmt>\t%0,%1,%2"
  [(set_attr "type" "fadd")
   (set_attr "mode" "DF")])

sifive-7.md:

通过 `fadd` type, `DF` mode 匹配到下面一条: 

(define_insn_reservation "sifive_7_dfma" 7
  (and (eq_attr "tune" "sifive_7")
       (and (eq_attr "type" "fadd,fmul,fmadd")
        (eq_attr "mode" "DF")))
  "sifive_7_B")

最后通过 genattrtab 生成 insn-latencytab.c: 

int insn_default_latency(rtx_insn *insn ATTRIBUTE_UNUSED) {
    enum attr_type cached_type ATTRIBUTE_UNUSED;
    enum attr_mode cached_mode ATTRIBUTE_UNUSED;

    switch (recog_memoized(insn)) {
        /* ... */
        case 2: /* adddf3 */
            if (((enum attr_tune)riscv_microarchitecture) == (TUNE_SIFIVE_7)) {
                return 7;
            }
        /* ... */
    }
}

1.3.1. example

以上面的 example 为例, 但把 generic.md 中 `li` 的 latency 从 1 修改为 10: 

(define_insn_reservation "generic_alu" 10
  (and (eq_attr "tune" "generic")
       (eq_attr "type" "unknown,const,arith,shift,slt,multi,auipc,nop,logical,move"))
  "alu")

scheduler 产生的代码变成: 

0000000000000000 <foo>:
   0:   7179                    addi    sp,sp,-48
   2:   f422                    sd      s0,40(sp)
   4:   1800                    addi    s0,sp,48
   6:   862a                    mv      a2,a0
   8:   4685                    li      a3,1
   a:   4705                    li      a4,1
   c:   4785                    li      a5,1
   e:   fe042623                sw      zero,-20(s0)
  12:   fe042423                sw      zero,-24(s0)
  16:   fe042223                sw      zero,-28(s0)
  1a:   fed42623                sw      a3,-20(s0)
  1e:   fee42423                sw      a4,-24(s0)
  22:   fef42223                sw      a5,-28(s0)
  26:   fcc42e23                sw      a2,-36(s0)
  2a:   0001                    nop
  2c:   7422                    ld      s0,40(sp)
  2e:   6145                    addi    sp,sp,48
  30:   8082                    ret

由于 li 的 latency 很大, 所以 `li a3,1` 与 `sw a3, -20(s0)` 之间被插入了多条 `sw zero, …`

1.3.2. define_insn_reservation

(define_insn_reservation insn-name default_latency
     condition regexp)

例如: 

(define_insn_reservation "sifive_7_dfma" 7
  (and (eq_attr "tune" "sifive_7")
       (and (eq_attr "type" "fadd,fmul,fmadd")
        (eq_attr "mode" "DF")))
  "sifive_7_B")

表示:

  1. condtion 为:
    • mtune 使用 `sifive_7` 的 microarchitecture
    • define_insn 的 type 是 `fadd, fmul 或 fmadd`
    • define_insn 的 mode 是 `DF`
  2. default_latency 为 7

  3. regexp 为 sifive_7_B, 表示使用 `sifive_7_B` 这个 cpu unit, 利用它可以分析 insn 之间的 structural hazard (data hazard 则需要分析 insn 本身对数据的使用情况)

    sifive_7_B 是通过 define_cpu_unit 定义的 functional unit, 例如流水线, fpu 等

    regexp 可以使用 `,+*|` 等符号表示各种复杂的 functional unit 占用需求:

    • `先使用 a 再使用 b`
    • `a, b 同时使用`
    • `前 3 个 cycle 用 a, 后 10 个 cycle 用 b`
    • …
Backlinks

machine desc (GCC Backend > insn selection > machine desc > md 语法 > define_insn_reservation): define_insn_reservation

1.3.3. define_bypass

https://gcc.gnu.org/legacy-ml/gcc/2004-05/msg01189.html

通过定义下面的 define_bypass, 可以使 generic_store 前面的 generic_alu 的 latency 变成 10, 达到和前面的 microarchitecture example 相同的效果. 

(define_bypass 10 "generic_alu" "generic_store")

TODO 为什么 a 后面接着 b 会导致 a 的 latency 变化?

Backlinks

mtune (mtune > microarchitecture): microarchitecture 主要是在 md 中定义 insn-latency 供 scheduler 使用

Backlinks

machine desc (GCC Backend > insn selection > machine desc > md 语法 > define_bypass): define_bypass

Backlinks

GCC (GCC > Scheduler): Scheduler

GCC Backend (GCC Backend > insn schedule): pass_sched

GCC Target Hook (GCC Target Hook > schedule 相关): schedule 相关

rtl pass (GCC Pass > rtl pass > pass_sched): pass_sched

Author: [email protected]
Date: 2022-04-25 Mon 17:56
Last updated: 2023-09-22 Fri 17:42

知识共享许可协议