Linker Relaxation

1. Linker Relaxation
- 1.1. example
- 1.2. impls

1. Linker Relaxation

https://www.sifive.com/blog/all-aboard-part-3-linker-relaxation-in-riscv-toolchain (local archive)

https://riscv.org/wp-content/uploads/2019/03/11.15-Shiva-Chen-Compiler-Support-For-Linker-Relaxation-in-RISC-V-2019-03-13.pdf (local archive)

gcc 编译和优化是以单个 object file 为单位, 导致两个问题:

symbol 的地址在 object file 中无法确定, gcc 必须通过 `auipc/lui` + `add/load/store/jalr` 多条指令的方式确保 symbol 在最 `远` 的情况下也能访问.

即使考虑可以使用 pc 相对地址的函数调用, 由于被调用函数的最终可能会因为 LinkerScript 被放在其它的地址, 所以编译 object 时是无法确定被调用函数的 pc 相对地址的.

另外, 如果代码中有 .align, 由于 object file 各个 section 的起始地址都是 0, 且指令有可能被 linker 修改, 导致编译时并不能确定 align 应该产生多少个 nop.
跨 object file 的优化无法实现

为了解决这两个问题, 需要 Static Linker 去优化/修改, 前者是 linker relaxation, 后者是 LTO

riscv 中的 linker relaxation 主要有几种方式:

lui+(addi,ld,sw…) 替换为 gp/tp+addi,ld,sw…
auipc+(addi,ld,sw…) 替换为 gp/tp+addi,ld,sw…
auipc+jalr 替换为 jal
根据 reloc 中的 align 信息重新调整 align
把一些指令替换成 c 指令, 例如把 jal 替换为 c.jal

另外, 是否能使用 gp/tp 也取决于符号的位置, 例如:

如果 symbol 在 .tdata 中, 使用 tp 做基址寄存器, 以支持 elf_tls
如果 symbol 在 __global_pointer$ 附近, 则可以用 gp 做为基址寄存器

1.1. example

1.1.1. lui relaxation

test.S:

    .global _start
    .section .text

_start:
    lui a1,%hi(here)
    addi a1, a1, %lo(here)

    .section .data
    .rept   (1<<10)
    .byte   0
    .endr

here:
    ret

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.S  -O0  -nostdlib
$> /opt/riscv/bin/riscv64-unknown-linux-gnu-objdump -D a.out

Disassembly of section .text:

00000000000100b0 <_start>:
   100b0:       c0018593                addi    a1,gp,-1024 # 114b4 <here>

Disassembly of section .data:

00000000000110b4 <__DATA_BEGIN__>:
        ...

00000000000114b4 <here>:
   114b4:       8082                    ret

1.1.2. jalr relaxation

test.S:

    .global _start
    .section .text

_start:
    call near
    call far

    .rept   (1<<18)-8
    .word   0
    .endr

near:
    ret
    .rept 10
    .word   0
    .endr
far:
    ret

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

Disassembly of section .text:

0000000000000000 <_start>:
       0:       00000097                auipc   ra,0x0
       4:       000080e7                jalr    ra # 0 <_start>
       8:       00000097                auipc   ra,0x0
       c:       000080e7                jalr    ra # 8 <_start+0x8>
        ...

00000000000ffff0 <near>:
   ffff0:       8082                    ret
        ...

000000000010001a <far>:
  10001a:       8082                    ret

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.S  -O0  -nostdlib -march=rv64g
$> /opt/riscv/bin/riscv64-unknown-linux-gnu-objdump -D a.out

Disassembly of section .text:

0000000000010078 <_start>:
   10078:       7edff0ef                jal     ra,110064 <near>
   1007c:       00100097                auipc   ra,0x100
   10080:       014080e7                jalr    20(ra) # 110090 <far>
        ...

0000000000110064 <near>:
  110064:       00008067                ret
        ...

0000000000110090 <far>:
  110090:       00008067                ret

1.1.3. gp relaxation

test.S:

    .global _start
    .section .text

_start:
    la a1,here

    .section .data
    .rept   (1<<19)+1
    .byte   0
    .endr

    .section .sdata
here:
    ret

test.lds:

SECTIONS
{
.text : { *(.text) }
.data : { *(.data) }
.bss : { *(.bss) }
.sdata : { *(.sdata);   __global_pointer$ = .;}
}

没有经过 linker relaxation 的 obj 文件:

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

Disassembly of section .text:

0000000000000000 <_start>:
   # NOTE: 这里显示 0x0 及 mv a1, a1 是因为相关操作数是 0
   # mv a1, a1 实际上是 addi a1, a1, 0
   0:   00000597                auipc   a1,0x0
   4:   00058593                mv      a1,a1

Disassembly of section .data:

0000000000000000 <.data>:
        ...

Disassembly of section .sdata:

0000000000000000 <here>:
   0:   8082                    ret

# 通过 objdump -r 可以显示 reloc 信息
$> /opt/riscv/bin/riscv64-unknown-linux-gnu-objdump -D -r ./test.o

Disassembly of section .text:

0000000000000000 <_start>:
   0:   00000597                auipc   a1,0x0
                        0: R_RISCV_PCREL_HI20   here
                        0: R_RISCV_RELAX        *ABS*
   4:   00058593                mv      a1,a1
                        4: R_RISCV_PCREL_LO12_I .L0
                        4: R_RISCV_RELAX        *ABS*

Disassembly of section .data:

0000000000000000 <.data>:
        ...

Disassembly of section .sdata:

0000000000000000 <here>:
   0:   8082                    ret

linker relaxation 的结果:

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.S  -O0  -nostdlib -T test.lds
$> /opt/riscv/bin/riscv64-unknown-linux-gnu-objdump -D ./a.out

Disassembly of section .text:

0000000000000000 <_start>:
   0:   ffe18593                addi    a1,gp,-2 # 80005 <here>

Disassembly of section .data:

0000000000000004 <.data>:
        ...

Disassembly of section .sdata:

0000000000080005 <here>:
   80005:       8082                    ret

lds 中必须有定义 __global_pointer$ 才可以使用基于 gp 的 relaxation. gcc 自带的 linker script 里 __global_pointer$ 定义为:

__global_pointer$ = MIN(__SDATA_BEGIN__ + 0x800,
                         MAX(__DATA_BEGIN__ + 0x800, __BSS_END__ - 0x800));

其中的 0x800 使得通过 gp 可以访问 SDATA_BEGIN 开始的 13-bit 地址范围 (因为 riscv 中 imm 是有符号数)

另外, 基于 gp 的 relaxation 不适用于 call 指令.

还有一点要注意, gp 的值需要程序初始化为 `__global_pointer$`, 例如 crt0.s 的的代码:

_start:
  # Initialize global pointer
.option push
.option norelax
1:auipc gp, %pcrel_hi(__global_pointer$)
  addi  gp, gp, %pcrel_lo(1b)
.option pop

如果使用了 nostdlib 或 nostartfiles , 则需要手写这段代码

Backlinks

Linker Relocation (Linker Relocation): 和 gp relaxation 有关

1.1.4. align relaxation

test.S:

    .global _start
    .section .text

_start:
    call here
    .balign 16
    move a0,a0
here:
    ret

没有经过 linker relaxation 的 obj:

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.S  -O0   -march=rv64g -c
$> /opt/riscv/bin/riscv64-unknown-linux-gnu-objdump -D test.o -r

Disassembly of section .text:

0000000000000000 <_start>:
   0:   00000097                auipc   ra,0x0
                        0: R_RISCV_CALL here
                        0: R_RISCV_RELAX        *ABS*
   4:   000080e7                jalr    ra # 0 <_start>
   8:   00000013                nop
                        8: R_RISCV_ALIGN        *ABS*+0xc
   c:   00000013                nop
  10:   00000013                nop
  14:   00050513                mv      a0,a0

0000000000000018 <here>:
  18:   00008067                ret
  1c:   0000                    unimp

gcc 编译时针对 align 插入了 3 个 nop, 且 reloc 中有一项 `R_RISCV_ALIGN=0xc`, 表示插入了 12 个 byte. 之所以是 3 个 nop, 是因为虽然 link 时到底多少个 nop 取决于 _start 的起始地址以及前面 R_RISCV_CALL 的 relaxation 的结果, 但是由于 linker relaxation 只能删除和替换指令(而不能增加指令), 所以这里会插入理论上最多的 nop. 对于 n 个 word 的 align, 需要插入的最多的 nop 是 n-1

relaxation 的结果:

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.S  -O0   -march=rv64g  -nostdlib
$> /opt/riscv/bin/riscv64-unknown-linux-gnu-objdump -D a.out

Disassembly of section .text:

0000000000010080 <_start>:
   10080:       014000ef                jal     ra,10094 <here>
   10084:       00000013                nop
   10088:       00000013                nop
   1008c:       00000013                nop
   # mv a0,a0 确实是 16 bytes 对齐
   10090:       00050513                mv      a0,a0

0000000000010094 <here>:
   10094:       00008067                ret
   10098:       0000                    unimp
        ...

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.S  -O0   -march=rv64g  -nostdlib -mno-relax
$> /opt/riscv/bin/riscv64-unknown-linux-gnu-objdump -D a.out

Disassembly of section .text:

0000000000010080 <_start>:
   10080:       00000097                auipc   ra,0x0
   10084:       014080e7                jalr    20(ra) # 10094 <here>
   10088:       00000013                nop
   1008c:       00000013                nop
   # -mno-relax 时针对 align 的 relaxation 还是会工作
   10090:       00050513                mv      a0,a0

0000000000010094 <here>:
   10094:       00008067                ret
   10098:       0000                    unimp
        ...

1.1.5. tls relaxation

tls relaxation 是为了支持 elf_tls

    .global _start
    .section .text

_start:
    lui  a5,%tprel_hi(here)           # R_RISCV_TPREL_HI20 (symbol)
    lw   t0,%tprel_lo(here)(a5)       # R_RISCV_TPREL_LO12_I (symbol)

    addi t0,t0,1
    sw   t0,%tprel_lo(here)(a5)

    .section .tdata
here:
    .word 0

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

0000000000000000 <_start>:
   0:   000007b7                lui     a5,0x0
   4:   0007a283                lw      t0,0(a5) # 0 <_start>
   8:   00128293                addi    t0,t0,1
   c:   0057a023                sw      t0,0(a5)

$> /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc test.S  -O0   -march=rv64g  -nostdlib
$> /opt/riscv/bin/riscv64-unknown-linux-gnu-objdump -d ./a.out

0000000000010120 <_start>:
   10120:       00022283                lw      t0,0(tp) # 0 <here>
   10124:       00128293                addi    t0,t0,1
   10128:       00522023                sw      t0,0(tp) # 0 <here>

Backlinks

Linker Relocation (Linker Relocation): 和 tls relaxation 有关

1.2. impls

linker relaxation 的实现在 BFD 中, 以 riscv 为例, 在 elfnn-riscv.c 中, 具体的:

_bfd_riscv_relax_call, 对应 `auipc+jalr -> jal`
_bfd_riscv_relax_lui, 对应 `lui+addi… -> addi…`
_bfd_riscv_relax_pc, 对应 `auipc+addi… -> addi…`
_bfd_riscv_relax_tls_le
_bfd_riscv_relax_align, 对应 `align`

linker relaxation 的实现非常复杂, 它会修改和删除指令, 从而导致:

其它指令的 branch offset 需要调整
DWARF 的 debug 信息需要调整
align 需要调整

1.2.1. _bfd_riscv_relax_call

1.2.2. _bfd_riscv_relax_lui

1.2.3. _bfd_riscv_relax_pc

1.2.4. _bfd_riscv_relax_align

Backlinks

AArch64 Tutorial (AArch64 Tutorial > AArch64 Assembly > instructions > Branch > BR/BLR): RISC-V 中针对函数调用会生成 auipc+jalr, 依赖 Relaxation 把它转换为 jal, AArch64 针对函数调用则会生成 bl (而不是 adrp+blr), 靠 linker 生成 veneer 来处理过远的函数调用

Linker Relocation (Linker Relocation > riscv relocation > R_RISCV_RELAX): 这个和 Linker Relaxation 有关

Static Linker (Static Linker > Linker Relaxation): Linker Relaxation

binutils (binutils > as > macro): riscv_call 生成了 `auipc+jalr`, 因为 assembler 无法知道跳转的范围有多大, 用 auipc+jalr 是最保险的做法, 在 link 阶段通过 linker relaxation 有可能会把它换成 jal

relax branch (binutils > as > relax branch): relax branch 的作用与 Linker Relaxation 类似, 但 linker relaxation 并没有处理 relax branch. 一种可能的 linker relaxation 中实现方法是: 让 blt 默认生成 `bge+jal`, 然后由 linker_relaxation 尝试把它替换回 `blt`

Linker Relaxation

Table of Contents

1. Linker Relaxation

1.1. example

1.1.1. lui relaxation

1.1.2. jalr relaxation

1.1.3. gp relaxation

Backlinks

1.1.4. align relaxation

1.1.5. tls relaxation

Backlinks

1.2. impls

1.2.1. _bfd_riscv_relax_call

1.2.2. _bfd_riscv_relax_lui

1.2.3. _bfd_riscv_relax_pc

1.2.4. _bfd_riscv_relax_align

Backlinks