[RISCV][MC] Relax conditional branches to unresolved symbols

[jobnoorman]

Summary

D108961 introduced relaxation for out-of-range conditional branches.
However, relaxation was only performed when the branch target could be
resolved. I believe this has two undesired consequences:

• b<cc> ... foo, where foo is undefined, would not be relaxed although there is no guarantee the offset to foo will fit;
• Conditional branches are never relaxed with -mattr=+relax because MC considers fixups where shouldForceRelocation returns true (which will be the case with +relax) to be unresolved.

Note that binutils performs conditional branch relaxation in both cases.

This patch proposes to perform conditional branch relaxation even when
the target cannot be resolved.

Note on llvm/test/MC/RISCV/long-conditional-jump.s: I've removed the
.p2align because this causes alignment nops to be inserted for the
+relax tests. This in turn causes all the branch targets to change
compared to the non-+relax tests. Since +relax shouldn't change
these offsets, I found this confusing and hence chose to remove the
alignment.

Depends on D155953

[asb]

Just to note that @jobnoorman and I spent some time discussing this earlier in the week and I was pretty convinced the current behaviour isn't what is desired (especially for the second bullet point in the patch description). In D108961, @reames made a good argument for supporting this relaxation from the perspective of improving toolchain resilience (in particular, where we fail to accurately estimate the upper bounds of of instruction sizes). I think that applies here just as well.

Flagging as putting the code review aspect aside, it would be useful to figure out early if people feel strongly that the intent of this patch is wrong.

[jobnoorman]

Ping

[reames]

This makes perfect sense to me. LGTM, but please wait a few days before landing in case anyone else wants to chime in.

[jobnoorman]

Rebase on D155953 and use that to fix LLD tests.

[MaskRay]

LGTM.

[asb]

LGTM.

[jobnoorman]

Rebase

[hiraditya]

Should we back port this to llvm-17 branch cut?

[MaskRay]

In D154958#4550778, @hiraditya wrote:

Should we back port this to llvm-17 branch cut?

The previous behavior has been quite a while and I don't know who is actively requiring this behavior, so probably not a best candidate for release/17.x.

lld/test/ELF/riscv-branch.s

 # REQUIRES: riscv
 
-# RUN: llvm-mc -filetype=obj -triple=riscv32-unknown-elf -mattr=-relax %s -o %t.rv32.o
-# RUN: llvm-mc -filetype=obj -triple=riscv64-unknown-elf -mattr=-relax %s -o %t.rv64.o
+# RUN: llvm-mc -filetype=obj -triple=riscv32-unknown-elf -mattr=-relax -riscv-asm-relax-branches=0 %s -o %t.rv32.o
+# RUN: llvm-mc -filetype=obj -triple=riscv64-unknown-elf -mattr=-relax -riscv-asm-relax-branches=0 %s -o %t.rv64.o
 
 # RUN: ld.lld %t.rv32.o --defsym foo=_start+4 --defsym bar=_start -o %t.rv32
 # RUN: ld.lld %t.rv64.o --defsym foo=_start+4 --defsym bar=_start -o %t.rv64
 # RUN: llvm-objdump -d %t.rv32 | FileCheck %s --check-prefix=CHECK-32
 # RUN: llvm-objdump -d %t.rv64 | FileCheck %s --check-prefix=CHECK-64
 # CHECK-32: 63 02 00 00     beqz    zero, 0x110b8
 # CHECK-32: e3 1e 00 fe     bnez    zero, 0x110b4
 # CHECK-64: 63 02 00 00     beqz    zero, 0x11124

lld/test/ELF/riscv-undefined-weak.s

 # REQUIRES: riscv
-# RUN: llvm-mc -filetype=obj -triple=riscv64 %s -o %t.o
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -riscv-asm-relax-branches=0 %s -o %t.o
 # RUN: llvm-readobj -r %t.o | FileCheck --check-prefix=RELOC %s
 
 # RUN: ld.lld -e absolute %t.o -o %t
 # RUN: llvm-objdump -d --no-show-raw-insn %t | FileCheck --check-prefixes=CHECK,PC %s
 # RUN: llvm-readelf -x .data %t | FileCheck --check-prefixes=HEX,HEX-WITHOUT-PLT %s
 
 # RUN: ld.lld -e absolute %t.o -o %t --export-dynamic
 # RUN: llvm-objdump -d --no-show-raw-insn %t | FileCheck --check-prefixes=CHECK,PLT %s

llvm/lib/Target/RISCV/MCTargetDesc/RISCVAsmBackend.cpp

bool RISCVAsmBackend::fixupNeedsRelaxationAdvanced(const MCFixup &Fixup,
                                                    const MCAsmLayout &Layout,
                                                    const bool WasForced) const {
   if (!RelaxBranches)
     return false;
 
   int64_t Offset = int64_t(Value);
   unsigned Kind = Fixup.getTargetKind();
 
-  // We only do conditional branch relaxation when the symbol is resolved.
-  // For conditional branch, the immediate must be in the range
-  // [-4096, 4094].
-  if (Kind == RISCV::fixup_riscv_branch)
-    return Resolved && !isInt<13>(Offset);
-
   // Return true if the symbol is actually unresolved.
   // Resolved could be always false when shouldForceRelocation return true.
   // We use !WasForced to indicate that the symbol is unresolved and not forced
   // by shouldForceRelocation.
   if (!Resolved && !WasForced)
     return true;
 
   switch (Kind) {
   default:
     return false;
   case RISCV::fixup_riscv_rvc_branch:
     // For compressed branch instructions the immediate must be
     // in the range [-256, 254].
     return Offset > 254 || Offset < -256;
   case RISCV::fixup_riscv_rvc_jump:
     // For compressed jump instructions the immediate must be
     // in the range [-2048, 2046].
     return Offset > 2046 || Offset < -2048;
+  case RISCV::fixup_riscv_branch:
+    // For conditional branch instructions the immediate must be
+    // in the range [-4096, 4095].
+    return !isInt<13>(Offset);
   }
 }
 
 void RISCVAsmBackend::relaxInstruction(MCInst &Inst,
                                        const MCSubtargetInfo &STI) const {
   MCInst Res;
   switch (Inst.getOpcode()) {
   default:

llvm/test/MC/RISCV/compressed-relocations.s

 c.jal foo
 # A compressed jump (c.j) to an unresolved symbol will be relaxed to a (jal).
 # RELOC: R_RISCV_JAL
 # INSTR: c.jal foo
 # FIXUP: fixup A - offset: 0, value: foo, kind: fixup_riscv_rvc_jump
 
 c.bnez a0, foo
 # A compressed branch (c.bnez) to an unresolved symbol will be relaxed to a (bnez).
-# RELOC: R_RISCV_BRANCH
+# The (bnez) to an unresolved symbol will in turn be relaxed to (beqz; jal)
+# RELOC: R_RISCV_JAL
 # INSTR: c.bnez a0, foo
 # FIXUP: fixup A - offset: 0, value: foo, kind: fixup_riscv_rvc_branch

llvm/test/MC/RISCV/long-conditional-jump.s

 # RUN: llvm-mc -filetype=obj -triple=riscv64 %s \
 # RUN:     | llvm-objdump -d -M no-aliases - \
 # RUN:     | FileCheck --check-prefix=CHECK-INST %s
 # RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+c %s \
 # RUN:     | llvm-objdump -d -M no-aliases - \
 # RUN:     | FileCheck --check-prefix=CHECK-INST-C %s
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+relax %s \
+# RUN:     | llvm-objdump -dr -M no-aliases - \
+# RUN:     | FileCheck --check-prefix=CHECK-INST-RELAX %s
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+c,+relax %s \
+# RUN:     | llvm-objdump -dr -M no-aliases - \
+# RUN:     | FileCheck --check-prefix=CHECK-INST-C-RELAX %s
 
        .text
-       .p2align        3
        .type   test,@function
 test:
 # CHECK-INST:         beq     a0, a1, 0x8
 # CHECK-INST-NEXT:    jal     zero, 0x1458
 # CHECK-INST-C:       beq     a0, a1, 0x8
 # CHECK-INST-C-NEXT:  jal     zero, 0x1458
+# CHECK-INST-RELAX:         beq     a0, a1, 0x8
+# CHECK-INST-RELAX-NEXT:    jal     zero, {{.*}}
+# CHECK-INST-RELAX-NEXT:    R_RISCV_JAL .L1
+# CHECK-INST-C-RELAX:       beq     a0, a1, 0x8
+# CHECK-INST-C-RELAX-NEXT:  jal     zero, {{.*}}
+# CHECK-INST-C-RELAX-NEXT:  R_RISCV_JAL .L1
    bne a0, a1, .L1
 .fill 1300, 4, 0
 .L1:
    ret
 # CHECK-INST:         bne     a0, a1, 0x1464
 # CHECK-INST-NEXT:    jal     zero, 0x28b4
 # CHECK-INST-C:       bne     a0, a1, 0x1462
 # CHECK-INST-C-NEXT:  jal     zero, 0x28b2
+# CHECK-INST-RELAX:         bne     a0, a1, 0x1464
+# CHECK-INST-RELAX-NEXT:    jal     zero, {{.*}}
+# CHECK-INST-RELAX-NEXT:    R_RISCV_JAL .L2
+# CHECK-INST-C-RELAX:       bne     a0, a1, 0x1462
+# CHECK-INST-C-RELAX-NEXT:  jal     zero, {{.*}}
+# CHECK-INST-C-RELAX-NEXT:  R_RISCV_JAL .L2
    beq a0, a1, .L2
 .fill 1300, 4, 0
 .L2:
    ret
 # CHECK-INST:         bge     a0, a1, 0x28c0
 # CHECK-INST-NEXT:    jal     zero, 0x3d10
 # CHECK-INST-C:       bge     a0, a1, 0x28bc
 # CHECK-INST-C-NEXT:  jal     zero, 0x3d0c
+# CHECK-INST-RELAX:         bge     a0, a1, 0x28c0
+# CHECK-INST-RELAX-NEXT:    jal     zero, {{.*}}
+# CHECK-INST-RELAX-NEXT:    R_RISCV_JAL .L3
+# CHECK-INST-C-RELAX:       bge     a0, a1, 0x28bc
+# CHECK-INST-C-RELAX-NEXT:  jal     zero, {{.*}}
+# CHECK-INST-C-RELAX-NEXT:  R_RISCV_JAL .L3
    blt a0, a1, .L3
 .fill 1300, 4, 0
 .L3:
    ret
 # CHECK-INST:         blt     a0, a1, 0x3d1c
 # CHECK-INST-NEXT:    jal     zero, 0x516c
 # CHECK-INST-C:       blt     a0, a1, 0x3d16
 # CHECK-INST-C-NEXT:  jal     zero, 0x5166
+# CHECK-INST-RELAX:         blt     a0, a1, 0x3d1c
+# CHECK-INST-RELAX-NEXT:    jal     zero, {{.*}}
+# CHECK-INST-RELAX-NEXT:    R_RISCV_JAL .L4
+# CHECK-INST-C-RELAX:       blt     a0, a1, 0x3d16
+# CHECK-INST-C-RELAX-NEXT:  jal     zero, {{.*}}
+# CHECK-INST-C-RELAX-NEXT:  R_RISCV_JAL .L4
    bge a0, a1, .L4
 .fill 1300, 4, 0
 .L4:
    ret
 # CHECK-INST:         bgeu    a0, a1, 0x5178
 # CHECK-INST-NEXT:    jal     zero, 0x65c8
 # CHECK-INST-C:       bgeu    a0, a1, 0x5170
 # CHECK-INST-C-NEXT:  jal     zero, 0x65c0
+# CHECK-INST-RELAX:         bgeu    a0, a1, 0x5178
+# CHECK-INST-RELAX-NEXT:    jal     zero, {{.*}}
+# CHECK-INST-RELAX-NEXT:    R_RISCV_JAL .L5
+# CHECK-INST-C-RELAX:       bgeu    a0, a1, 0x5170
+# CHECK-INST-C-RELAX-NEXT:  jal     zero, {{.*}}
+# CHECK-INST-C-RELAX-NEXT:  R_RISCV_JAL .L5
    bltu a0, a1, .L5
 .fill 1300, 4, 0
 .L5:
    ret
 # CHECK-INST:         bltu    a0, a1, 0x65d4
 # CHECK-INST-NEXT:    jal     zero, 0x7a24
 # CHECK-INST-C:       bltu    a0, a1, 0x65ca
 # CHECK-INST-C-NEXT:  jal     zero, 0x7a1a
+# CHECK-INST-RELAX:         bltu    a0, a1, 0x65d4
+# CHECK-INST-RELAX-NEXT:    jal     zero, {{.*}}
+# CHECK-INST-RELAX-NEXT:    R_RISCV_JAL .L6
+# CHECK-INST-C-RELAX:       bltu    a0, a1, 0x65ca
+# CHECK-INST-C-RELAX-NEXT:  jal     zero, {{.*}}
+# CHECK-INST-C-RELAX-NEXT:  R_RISCV_JAL .L6
    bgeu a0, a1, .L6
 .fill 1300, 4, 0
 .L6:
    ret
 # CHECK-INST:         bne     a0, zero, 0x7a30
 # CHECK-INST-NEXT:    jal     zero, 0x8e80
 # CHECK-INST-C:       c.bnez  a0, 0x7a22
 # CHECK-INST-C-NEXT:  jal     zero, 0x8e72
+# CHECK-INST-RELAX:         bne     a0, zero, 0x7a30
+# CHECK-INST-RELAX-NEXT:    jal     zero, {{.*}}
+# CHECK-INST-RELAX-NEXT:    R_RISCV_JAL .L7
+# CHECK-INST-C-RELAX:       c.bnez  a0, 0x7a22
+# CHECK-INST-C-RELAX-NEXT:  jal     zero, {{.*}}
+# CHECK-INST-C-RELAX-NEXT:  R_RISCV_JAL .L7
    beqz a0, .L7
 .fill 1300, 4, 0
 .L7:
    ret
 # CHECK-INST:         bne     zero, a0, 0x8e8c
 # CHECK-INST-NEXT:    jal     zero, 0xa2dc
 # CHECK-INST-C:       c.bnez  a0, 0x8e7a
 # CHECK-INST-C-NEXT:  jal     zero, 0xa2ca
+# CHECK-INST-RELAX:         bne     zero, a0, 0x8e8c
+# CHECK-INST-RELAX-NEXT:    jal     zero, {{.*}}
+# CHECK-INST-RELAX-NEXT:    R_RISCV_JAL .L8
+# CHECK-INST-C-RELAX:       c.bnez  a0, 0x8e7a
+# CHECK-INST-C-RELAX-NEXT:  jal     zero, {{.*}}
+# CHECK-INST-C-RELAX-NEXT:  R_RISCV_JAL .L8
    beq x0, a0, .L8
 .fill 1300, 4, 0
 .L8:
    ret
 # CHECK-INST:         beq     a0, zero, 0xa2e8
 # CHECK-INST-NEXT:    jal     zero, 0xb738
 # CHECK-INST-C:       c.beqz  a0, 0xa2d2
 # CHECK-INST-C-NEXT:  jal     zero, 0xb722
+# CHECK-INST-RELAX:         beq     a0, zero, 0xa2e8
+# CHECK-INST-RELAX-NEXT:    jal     zero, {{.*}}
+# CHECK-INST-RELAX-NEXT:    R_RISCV_JAL .L9
+# CHECK-INST-C-RELAX:       c.beqz  a0, 0xa2d2
+# CHECK-INST-C-RELAX-NEXT:  jal     zero, {{.*}}
+# CHECK-INST-C-RELAX-NEXT:  R_RISCV_JAL .L9
    bnez a0, .L9
 .fill 1300, 4, 0
 .L9:
    ret
 # CHECK-INST:         beq     a6, zero, 0xb744
 # CHECK-INST-NEXT:    jal     zero, 0xcb94
 # CHECK-INST-C:       beq     a6, zero, 0xb72c
 # CHECK-INST-C-NEXT:  jal     zero, 0xcb7c
+# CHECK-INST-RELAX:         beq     a6, zero, 0xb744
+# CHECK-INST-RELAX-NEXT:    jal     zero, {{.*}}
+# CHECK-INST-RELAX-NEXT:    R_RISCV_JAL .L10
+# CHECK-INST-C-RELAX:       beq     a6, zero, 0xb72c
+# CHECK-INST-C-RELAX-NEXT:  jal     zero, {{.*}}
+# CHECK-INST-C-RELAX-NEXT:  R_RISCV_JAL .L10
    bnez x16, .L10
 .fill 1300, 4, 0
 .L10:
    ret
 .Lfunc_end0:
        .size   test, .Lfunc_end0-test

llvm/test/MC/RISCV/relocations.s

 # INSTR: add t1, t1, tp, %tprel_add(foo)
 # FIXUP: fixup A - offset: 0, value: %tprel_add(foo), kind: fixup_riscv_tprel_add
 
 jal zero, foo
 # RELOC: R_RISCV_JAL
 # INSTR: jal zero, foo
 # FIXUP: fixup A - offset: 0, value: foo, kind: fixup_riscv_jal
 
+# Since foo is undefined, this will be relaxed to (bltu; jal)
 bgeu a0, a1, foo
-# RELOC: R_RISCV_BRANCH
+# RELOC: R_RISCV_JAL
 # INSTR: bgeu a0, a1, foo
 # FIXUP: fixup A - offset: 0, value: foo, kind: fixup_riscv_branch