[RISCV] GP relaxation broken if accesses straddle the boundary

[nemanjai]

If we have more than one memory access (with a R_RISCV_LO12_I relocation on it) that depends on the same LUI with a R_RISCV_HI20 relocation and one of them can be reached from the GP while the other(s) can't, the linker will relax and get rid of the LUI. The memory access that is reachable will be fine, but the one(s) that aren't will be relocated off of an undefined register.
To illustrate the issue:

$ cat a.s
.global _start
_start:
        lui     a1, %hi(Var0)
        lw      a0, %lo(Var0)(a1)
        lw      a1, %lo(Var0+4)(a1)

.section .sdata,"aw"
foo:
  .word 0
  .space 4091
Var0:
  .quad 0
  .size   Var0, 8

Produce object file:
llvm-mc -filetype=obj -triple=riscv32-unknown-elf -mattr=+relax a.s -o a.o

Link it:
ld.lld --relax-gp --undefined=__global_pointer$ a.o

Disassemble:

llvm-objdump -dr a.out

a.out:  file format elf32-littleriscv

Disassembly of section .text:

000110d4 <_start>:
   110d4: 03 a5 f1 7f   lw      a0, 2047(gp)
   110d8: 83 a5 f5 0d   lw      a1, 223(a1)

[llvmbot]

@llvm/issue-subscribers-backend-risc-v

Author: Nemanja Ivanovic (nemanjai)

If we have more than one memory access (with a `R_RISCV_LO12_I` relocation on it) that depends on the same `LUI` with a `R_RISCV_HI20` relocation and one of them can be reached from the GP while the other(s) can't, the linker will relax and get rid of the `LUI`. The memory access that is reachable will be fine, but the one(s) that aren't will be relocated off of an undefined register. To illustrate the issue: ``` $ cat a.s .global _start _start: lui a1, %hi(Var0) lw a0, %lo(Var0)(a1) lw a1, %lo(Var0+4)(a1)

.section .sdata,"aw"
foo:
.word 0
.space 4091
Var0:
.quad 0
.size Var0, 8

Produce object file:
`llvm-mc -filetype=obj -triple=riscv32-unknown-elf -mattr=+relax a.s -o a.o`

Link it:
`ld.lld --relax-gp --undefined=__global_pointer$ a.o`

Disassemble:

llvm-objdump -dr a.out

a.out: file format elf32-littleriscv

Disassembly of section .text:

000110d4 <_start>:
110d4: 03 a5 f1 7f lw a0, 2047(gp)
110d8: 83 a5 f5 0d lw a1, 223(a1)

</details>

[llvmbot]

@llvm/issue-subscribers-lld-elf

Author: Nemanja Ivanovic (nemanjai)

If we have more than one memory access (with a `R_RISCV_LO12_I` relocation on it) that depends on the same `LUI` with a `R_RISCV_HI20` relocation and one of them can be reached from the GP while the other(s) can't, the linker will relax and get rid of the `LUI`. The memory access that is reachable will be fine, but the one(s) that aren't will be relocated off of an undefined register. To illustrate the issue: ``` $ cat a.s .global _start _start: lui a1, %hi(Var0) lw a0, %lo(Var0)(a1) lw a1, %lo(Var0+4)(a1)

.section .sdata,"aw"
foo:
.word 0
.space 4091
Var0:
.quad 0
.size Var0, 8

Produce object file:
`llvm-mc -filetype=obj -triple=riscv32-unknown-elf -mattr=+relax a.s -o a.o`

Link it:
`ld.lld --relax-gp --undefined=__global_pointer$ a.o`

Disassemble:

llvm-objdump -dr a.out

a.out: file format elf32-littleriscv

Disassembly of section .text:

000110d4 <_start>:
110d4: 03 a5 f1 7f lw a0, 2047(gp)
110d8: 83 a5 f5 0d lw a1, 223(a1)

</details>

[nemanjai]

I imagine that fixing this in LLD wouldn't be desired since it would require that we re-scan relocations to find the corresponding R_RISCV_HI20 to the R_RISCV_LO12_I that can't be relaxed. And even if we are willing to do the work, I imagine that the relocation isn't guaranteed to be the right one in every case.

A few possibilities as far as I can tell:

1. [Compiler] Don't add the R_RISCV_RELAX relocations on the HI20 that has multiple uses. The disadvantage would be that we lose at least some of the code size reduction that comes with relaxation.
2. [Compiler] Duplicate the instruction with the HI20 relocation for every user (with some instruction marked with sideeffects so it doesn't get CSE'd). The disadvantage would be that we actually increase code size when relaxation isn't possible on multiple users.
3. [Linker + Compiler] Add information to the R_RISCV_RELAX relocation that is on the R_RISCV_LO12_I to provide the offset to the corresponding R_RISCV_HI20. It's a bit more involved wrt. implementation, but it allows the linker to only get rid of the LUI if all of its users are relaxed. Correctness without the loss of benefits of the relaxation (admittedly, with an increase in linker run-time).

@topperc @MaskRay @asb Please let me know if you guys think one of the 3 suggestions would be desirable or propose another solution to this.

[jrtc27]

The linker has all the information it needs, it's just an oversight that this isn't handled.

[nemanjai]

The linker has all the information it needs, it's just an oversight that this isn't handled.

I don't quite follow. Can you please elaborate? How does the linker know the relationship between the HI20 and LO12 relocations?
In fact, I believe it is entirely possible that multiple accesses of an object that is less than naturally aligned cannot even share the same LUI at all. This is of course orthogonal to the relaxation issue that I outlined above.

For example, if we are trying to load an 8-byte item aligned at 4 bytes (i.e. like a double):

.global _start
_start:
        lui     a1, %hi(Var0)
        lw      a0, %lo(Var0)(a1)
        lw      a1, %lo(Var0+4)(a1)

.section .sdata,"aw"
foo:
  .word 0
  .space 5912
Var0:
  .quad 0
  .size   Var0, 8

This test case cannot actually load the two halves of the double.

[jrtc27]

Oh this is for HI20/LO12, not PCREL_HI20/LO12. That code is invalid unless Var0 is aligned to 8 bytes. It can break even without GP relaxation (when the +4 causes Var0+4 to carry into high bits such that the LUI needs to change).

[topperc]

The code in the compiler that would create %lo(Var0+4)(a1) already checks alignment. It's here in RISCVISelDAGToDAG.cpp

        if (auto *GA = dyn_cast<GlobalAddressSDNode>(LoOperand)) {               
          // If the Lo in (ADD_LO hi, lo) is a global variable's address         
          // (its low part, really), then we can rely on the alignment of that   
          // variable to provide a margin of safety before low part can overflow 
          // the 12 bits of the load/store offset. Check if CVal falls within    
          // that margin; if so (low part + CVal) can't overflow.                
          const DataLayout &DL = CurDAG->getDataLayout();                        
          Align Alignment = commonAlignment(                                     
              GA->getGlobal()->getPointerAlignment(DL), GA->getOffset());        
          if (CVal == 0 || Alignment > CVal) {                                   
            int64_t CombinedOffset = CVal + GA->getOffset();                     
            Base = Base.getOperand(0);                                           
            Offset = CurDAG->getTargetGlobalAddress(                             
                GA->getGlobal(), SDLoc(LoOperand), LoOperand.getValueType(),     
                CombinedOffset, GA->getTargetFlags());                           
            return true;                                                         
          }                                                                      
        }                                                                        
      }

[nemanjai]

Thank you for the info. The secondary issue I mentioned isn't a concern as the compiler won't do that.
However, the original issue is definitely an issue.
Here's a perfectly valid set of accesses that the compiler can produce (along with a linker script) that illustrates the problem:

.global _start
_start:
        lui     a1, %hi(Var0)
        lw      a0, %lo(Var0)(a1)
        lw      a1, %lo(Var0+4)(a1)
        lui     a1, %hi(Var1)
        lw      a0, %lo(Var1)(a1)
        lw      a1, %lo(Var1+124)(a1)

.section .rodata
foo:
  .space 1
.section .sdata,"aw"
  .space 1
.section .data,"aw"
  .p2align 3
Var0:
  .quad 0
  .size   Var0, 8
  .space 3960
  .p2align 7
Var1:
  .quad 0
  .zero 120
  .size   Var1, 128

Linker script:

    SECTIONS {
        .text : { }
        .rodata : { }
        .sdata : { }
        .sbss : { }
        .data : { }
    }

[nemanjai]

My proposal for the fix to the issue:

diff --git a/lld/ELF/Arch/RISCV.cpp b/lld/ELF/Arch/RISCV.cpp
index 6413dcd..15f819b 100644
--- a/lld/ELF/Arch/RISCV.cpp
+++ b/lld/ELF/Arch/RISCV.cpp
@@ -651,6 +651,22 @@ static void relaxHi20Lo12(const InputSection &sec, size_t i, uint64_t loc,
   if (!isInt<12>(r.sym->getVA(r.addend) - gp->getVA()))
     return;

+  // The symbol may be accessed in multiple pieces. We need to make sure that
+  // all of the possible accesses are relaxed or none are. This prevents
+  // relaxing the hi relocation and being unable to relax one of the low
+  // relocations. The compiler will only access multiple pieces of an object
+  // with low relocations on the memory op if the alignment allows it.
+  // Therefore it should suffice to check that the smaller of the alignment
+  // and size can be reached from GP.
+  uint32_t alignAdjust = r.sym->getOutputSection() ?
+    r.sym->getOutputSection()->addralign : 0;
+  alignAdjust = std::min<uint32_t>(alignAdjust, r.sym->getSize());
+
+  if (!isInt<12>(r.sym->getVA() + alignAdjust - gp->getVA()))
+    return;
+
   switch (r.type) {
   case R_RISCV_HI20:
     // Remove lui rd, %hi20(x).

[jrtc27]

The lack of linking between hi and lo does unfortunately make that case fragile. However, one can still take a conservative approach and look at the set of relocations against the given symbol in that input section to determine whether there might be problems, I guess.