[ELF] Relax R_RISCV_CALL and R_RISCV_CALL_PLT

[MaskRay]

Summary

A pair of auipc+jalr relocated by R_RISCV_CALL or R_RISCV_CALL_PLT can be
converted to c.j, c.jal, or jal.

• c.j: RVC and displacement is representable as an int12
• c.jal: RV32C and displacement is representable as an int12
• jal: displacement is representable as an int21

Use the D127581 relaxation framework to implement the relaxation. If a shorter
sequence is satisfied, we record the new relocation type in relocTypes and
saves the new instruction into writes. Finally let riscvFinalizeRelax rewrite the
instruction by setting skip.

[MaskRay]

rebase

[MaskRay]

rebase

[MaskRay]

rebase

[MaskRay]

improve tests

[MaskRay]

Will push this next week.

[luismarques]

My tests finally finished running. No issues detected. LGTM.

lld/test/ELF/riscv-relax-call.s

122

Nit: "32c" is confusing. "RV32C" is the usual name.

135

Nit: just write "RV32C" instead of "32c (RVC32)"?

[jrtc27]

lld/ELF/Arch/RISCV.cpp

478

RelType

484

Same comment as for relocDeltas in the other patch, really just want a pointer not a dynamically-resizable SmallVector

519

Shouldn't we know from the relocation's expr which we picked? Repeating a version of that logic seems fragile.

577

R_RISCV_NONE

680

RelType (and maybe check != R_RISCV_NONE explicitly?)

702

(maybe != R_RISCV_NONE?)

[luismarques]

Sorry, my previous approval comment was meant for D127581.

[MaskRay]

(in a trip, so i didn't spend too much time yet)
but all comments should be addressed

lld/test/ELF/riscv-relax-call.s

122

32c is the executable name.

[kito-cheng]

Run this patch with LLVM testsuite and internal testsuite, no regression.

[MaskRay]

rebase
improve test

lld/ELF/Arch/RISCV.cpp

case R_RISCV_TLS_GD_HI20:
     return R_TLSGD_PC;
   case R_RISCV_TLS_GOT_HI20:
     config->hasTlsIe = true;
     return R_GOT_PC;
   case R_RISCV_TPREL_HI20:
   case R_RISCV_TPREL_LO12_I:
   case R_RISCV_TPREL_LO12_S:
     return R_TPREL;
-  case R_RISCV_RELAX:
   case R_RISCV_TPREL_ADD:
     return R_NONE;
   case R_RISCV_ALIGN:
     return R_RELAX_HINT;
+  case R_RISCV_RELAX:
+    return config->relax ? R_RELAX_HINT : R_NONE;
   default:
     error(getErrorLocation(loc) + "unknown relocation (" + Twine(type) +
           ") against symbol " + toString(s));
     return R_NONE;
   }
 }
 
 // Extract bits V[Begin:End], where range is inclusive, and Begin must be < 63.
case R_RISCV_RELAX:
     return; // Ignored (for now)
 
   default:
     llvm_unreachable("unknown relocation");
   }
 }
 
 static void getSymbolAnchors() {
   for (OutputSection *osec : outputSections) {
     if (!(osec->flags & SHF_EXECINSTR))
       continue;
     for (InputSection *sec : getInputSections(*osec)) {
       sec->relaxAux = make<RISCVRelaxAux>();
       sec->relaxAux->relocDeltas.resize(sec->relocations.size());
+      sec->relaxAux->relocTypes.resize(sec->relocations.size());
     }
   }
   // Store anchors (st_value and st_value+st_size) for symbols relative to text
   // sections.
   for (InputFile *file : objectFiles)
     for (Symbol *sym : file->getSymbols()) {
       auto *d = dyn_cast<Defined>(sym);
       if (!d || d->file != file)
if (!(osec->flags & SHF_EXECINSTR))
       continue;
     for (InputSection *sec : getInputSections(*osec)) {
       llvm::stable_sort(sec->relaxAux->anchors,
                         [](auto &a, auto &b) { return a.offset < b.offset; });
     }
   }
 }
 
+// Relax R_RISCV_CALL/R_RISCV_CALL_PLT auipc+jalr to c.j, c.jal, or jal.
+static void relaxCall(const InputSection &sec, size_t i, uint64_t loc,
+                      Relocation &r, int32_t &remove) {
+  const bool rvc = config->eflags & EF_RISCV_RVC;
+  const Symbol &sym = *r.sym;
+  const uint64_t insnPair = read64le(sec.rawData.data() + r.offset);
+  const uint32_t rd = extractBits(insnPair, 32 + 11, 32 + 7);
+  const uint64_t dest =
+      (!sym.isPreemptible && (!sym.isGnuIFunc() || config->zIfuncNoplt)
+           ? sym.getVA()
+           : sym.getPltVA()) +
+      r.addend;
+  const int64_t displace = dest - loc;
+
+  if (rvc && isInt<12>(displace) && rd == 0) {
+    sec.relaxAux->relocTypes[i] = R_RISCV_RVC_JUMP;
+    sec.relaxAux->writes.push_back(0xa001); // c.j
+    remove = 6;
+  } else if (rvc && isInt<12>(displace) && rd == X_RA &&
+             !config->is64) { // RV32C only
+    sec.relaxAux->relocTypes[i] = R_RISCV_RVC_JUMP;
+    sec.relaxAux->writes.push_back(0x2001); // c.jal
+    remove = 6;
+  } else if (isInt<21>(displace)) {
+    sec.relaxAux->relocTypes[i] = R_RISCV_JAL;
+    sec.relaxAux->writes.push_back(0x6f | rd << 7); // jal
+    remove = 4;
+  }
+}
+
 // Do a relaxation pass and return true if we changed something. When relaxing
 // just R_RISCV_ALIGN, relocDeltas is usually changed only once in the absence
 // of a linker script. For call and load/store R_RISCV_RELAX, code shrinkage may
 // reduce displacement and make more relocations eligible for relaxation. Code
 // shrinkage may increase displacement to a call/load/store target at a higher
 // fixed address, invalidating an earlier relaxation. Any change in section
 // sizes can have cascading effect and require another relaxation pass.
 bool RISCV::relaxOnce(int pass) const {
for (InputSection *sec : getInputSections(*osec)) {
         delta = aux.relocDeltas[it.index()];
       }
       for (const SymbolAnchor &sa : sa)
         if (!sa.end)
           sa.d->value += delta;
       sa = makeArrayRef(aux.anchors);
       delta = 0;
 
+      std::fill(aux.relocTypes.begin(), aux.relocTypes.end(), 0);
+      aux.writes.clear();
       for (auto it : llvm::enumerate(sec->relocations)) {
         Relocation &r = it.value();
         size_t i = it.index();
         const uint64_t loc = secAddr + r.offset - delta;
         int32_t &cur = aux.relocDeltas[i], remove = 0;
         switch (r.type) {
         case R_RISCV_ALIGN: {
           const uint64_t nextLoc = loc + r.addend;
           const uint64_t align = PowerOf2Ceil(r.addend + 2);
           // All bytes beyond the alignment boundary should be removed.
           remove = static_cast<int32_t>(nextLoc - ((loc + align - 1) & -align));
           assert(remove >= 0 && "R_RISCV_ALIGN needs expanding the content");
           break;
         }
+        case R_RISCV_CALL:
+        case R_RISCV_CALL_PLT:
+          if (i != sec->relocations.size() - 1 &&
+              sec->relocations[i + 1].type == R_RISCV_RELAX)
+            relaxCall(*sec, i, loc, r, remove);
+          break;
         }
 
         // For all anchors whose offsets are <= r.offset, they are preceded by
         // the relocation with `relocDeltas` value `delta`. Decrease their
         // st_value.
         if (remove) {
           for (; sa.size() && sa[0].offset <= r.offset; sa = sa.slice(1)) {
             if (sa[0].end)
if (!(osec->flags & SHF_EXECINSTR))
       continue;
     for (InputSection *sec : getInputSections(*osec)) {
       RISCVRelaxAux &aux = *sec->relaxAux;
       if (aux.relocDeltas.empty())
         continue;
 
       auto &rels = sec->relocations;
       ArrayRef<uint8_t> old = sec->rawData;
-      size_t newSize = old.size() - aux.relocDeltas.back();
+      size_t newSize = old.size() - aux.relocDeltas.back(), writesIdx = 0;
       uint8_t *p = context().bAlloc.Allocate<uint8_t>(newSize);
       uint64_t offset = 0;
       int32_t delta = 0;
       sec->rawData = makeArrayRef(p, newSize);
       sec->bytesDropped = 0;
 
       // Update section content: remove NOPs for R_RISCV_ALIGN and rewrite
       // instructions for relaxed relocations.
for (InputSection *sec : getInputSections(*osec)) {
             int32_t j = 0;
             for (; j + 4 <= skip; j += 4)
               write32le(p + j, 0x00000013); // nop
             if (j != skip) {
               assert(j + 2 == skip);
               write16le(p + j, 0x0001); // c.nop
             }
           }
+        } else if (uint32_t newType = aux.relocTypes[i]) {
+          const uint32_t insn = aux.writes[writesIdx++];
+          switch (newType) {
+          case R_RISCV_RVC_JUMP:
+            skip = 2;
+            write16le(p, insn);
+            break;
+          case R_RISCV_JAL:
+            skip = 4;
+            write32le(p, insn);
+            break;
+          default:
+            llvm_unreachable("unsupported type");
+          }
         }
 
         p += skip;
         offset = r.offset + skip + remove;
       }
       memcpy(p, old.data() + offset, old.size() - offset);
 
       delta = 0;
       for (size_t i = 0, e = rels.size(); i != e; ++i) {
         // Substract the previous relocDeltas value from the relocation offset.
         rels[i].offset -= delta;
         delta = aux.relocDeltas[i];
+        if (aux.relocTypes[i])
+          rels[i].type = aux.relocTypes[i];
       }
     }
   }
 }
 
 TargetInfo *elf::getRISCVTargetInfo() {
   static RISCV target;
   return &target;
 }

lld/ELF/InputSection.h

 // InputSection.
 struct RISCVRelaxAux {
   // This records symbol start and end offsets which will be adjusted according
   // to the nearest relocDeltas element.
   SmallVector<SymbolAnchor, 0> anchors;
   // For relocations[i], the actual offset is r_offset - (i ? relocDeltas[i-1] :
   // 0).
   SmallVector<int32_t, 0> relocDeltas;
+  // For relocations[i], the actual type is relocTypes[i].
+  SmallVector<uint32_t, 0> relocTypes;
+  SmallVector<uint32_t, 0> writes;
 };
 
 // This corresponds to a section of an input file.
 class InputSectionBase : public SectionBase {
 public:
   template <class ELFT>
   InputSectionBase(ObjFile<ELFT> &file, const typename ELFT::Shdr &header,
                    StringRef name, Kind sectionKind);

lld/test/ELF/riscv-relax-call-abs.s

+# REQUIRES: riscv
+
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+c,+relax %s -o %t.o
+# RUN: ld.lld --defsym abs=0x8 -Ttext=0x100000 %t.o -o %t
+# RUN: llvm-objdump -d --no-show-raw-insn -M no-aliases %t | FileCheck %s
+
+## Unsure whether this needs a diagnostic. GNU ld supports this.
+# RUN: ld.lld --defsym abs=0x8 -Ttext=0x100000 -pie %t.o -o %t
+# RUN: llvm-objdump -d --no-show-raw-insn -M no-aliases %t | FileCheck %s
+
+# CHECK-LABEL: <_start>:
+# CHECK-NEXT:            jal    zero, 0x8 <abs>
+# CHECK-NEXT:            jal    zero, 0x8 <abs>
+# CHECK-NEXT:            jal    ra, 0x8 <abs>
+# CHECK-NEXT:            auipc  t1, 1048320
+# CHECK-NEXT:            jalr   zero, -4(t1)
+
+#--- a.s
+.global _start
+_start:
+  jump abs, t2
+  jump abs, t3
+  call abs      # last relaxable insn
+  tail abs

lld/test/ELF/riscv-relax-call.s

+# REQUIRES: riscv
+## Relax R_RISCV_CALL and R_RISCV_CALL_PLT.
+
+# RUN: rm -rf %t && split-file %s %t && cd %t
+
+## Without RVC
+# RUN: llvm-mc -filetype=obj -triple=riscv32 -mattr=+relax a.s -o a.32.o
+# RUN: llvm-mc -filetype=obj -triple=riscv32 -mattr=+relax b.s -o b.32.o
+# RUN: ld.lld -shared -soname=b.so b.32.o -o b.32.so
+# RUN: ld.lld -T lds a.32.o b.32.so -o 32
+# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 32 | FileCheck %s --check-prefix=NORVC
+
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+relax a.s -o a.64.o
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+relax b.s -o b.64.o
+# RUN: ld.lld -shared -soname=b.so b.64.o -o b.64.so
+# RUN: ld.lld -T lds a.64.o b.64.so -o 64
+# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 64 | FileCheck %s --check-prefix=NORVC
+
+## RVC
+# RUN: llvm-mc -filetype=obj -triple=riscv32 -mattr=+c,+relax a.s -o a.32c.o
+# RUN: llvm-mc -filetype=obj -triple=riscv32 -mattr=+c,+relax b.s -o b.32c.o
+# RUN: ld.lld -shared -soname=b.so b.32c.o -o b.32c.so
+# RUN: ld.lld -T lds a.32c.o b.32c.so -o 32c
+# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 32c | FileCheck %s --check-prefixes=RVC,RVC32
+
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+c,+relax a.s -o a.64c.o
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+c,+relax b.s -o b.64c.o
+# RUN: ld.lld -shared -soname=b.so b.64c.o -o b.64c.so
+# RUN: ld.lld -T lds a.64c.o b.64c.so -o 64c
+# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 64c | FileCheck %s --check-prefixes=RVC,RVC64
+
+## --no-relax disables relaxation.
+# RUN: ld.lld -T lds a.64.o b.64.so --no-relax -o 64.norelax
+# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 64.norelax | FileCheck %s --check-prefixes=NORELAX
+
+# NORVC:       00010000 g       .text  {{0*}}0000001c _start
+
+# NORVC-LABEL: <_start>:
+# NORVC-NEXT:    10000:  jal    zero, {{.*}} <a>
+# NORVC-NEXT:            jal    zero, {{.*}} <a>
+# NORVC-NEXT:            addi   zero, zero, 0
+# NORVC-NEXT:            addi   zero, zero, 0
+# NORVC-NEXT:    10010:  jal    ra, {{.*}} <a>
+# NORVC-NEXT:            jal    ra, 0x10420
+# NORVC-EMPTY:
+
+# NORVC-LABEL: <.mid>:
+# NORVC-NEXT:    10800:  jal    ra, {{.*}} <_start>
+# NORVC-NEXT:            jal    ra, {{.*}} <_start>
+# NORVC-EMPTY:
+
+# NORVC-LABEL: <.high>:
+# NORVC-NEXT:   110000:  jal    ra, {{.*}} <_start>
+# NORVC-NEXT:            auipc  ra, 1048320
+# NORVC-NEXT:            jalr   ra, -4(ra)
+# NORVC-NEXT:            addi   zero, zero, 0
+# NORVC-NEXT:   110010:  addi   a0, a0, 3
+# NORVC-NEXT:            addi   a0, a0, 3
+# NORVC-NEXT:            jal    ra, {{.*}} <a>
+# NORVC-EMPTY:
+
+# RVC32:       00010000 g       .text  00000016 _start
+# RVC64:       0000000000010000 g       .text  000000000000001a _start
+
+# RVC-LABEL:   <_start>:
+# RVC-NEXT:      10000:  c.j    {{.*}} <a>
+# RVC-NEXT:              c.j    {{.*}} <a>
+# RVC-NEXT:              addi   zero, zero, 0
+# RVC-NEXT:              addi   zero, zero, 0
+# RVC-NEXT:              addi   zero, zero, 0
+# RVC32-NEXT:    10010:  c.jal  {{.*}} <a>
+# RVC32-NEXT:            c.jal  0x10420
+# RVC64-NEXT:    10010:  jal    ra, {{.*}} <a>
+# RVC64-NEXT:            jal    ra, 0x10420
+# RVC-EMPTY:
+# RVC-NEXT:    <a>:
+# RVC-NEXT:              c.jr   ra
+# RVC-EMPTY:
+# RVC-LABEL:   <.mid>:
+# RVC32-NEXT:    10800:  c.jal  {{.*}} <_start>
+# RVC64-NEXT:    10800:  jal    ra, {{.*}} <_start>
+# RVC-NEXT:              jal    ra, {{.*}} <_start>
+# RVC-EMPTY:
+# RVC-LABEL:   <.high>:
+# RVC-NEXT:     110000:  jal    ra, {{.*}} <_start>
+# RVC-NEXT:              auipc  ra, 1048320
+# RVC-NEXT:              jalr   ra, -4(ra)
+# RVC-NEXT:              addi   zero, zero, 0
+# RVC-NEXT:     110010:  c.addi a0, 3
+# RVC-NEXT:              c.addi a0, 3
+# RVC-NEXT:              jal    ra, {{.*}} <a>
+# RVC-EMPTY:
+
+# NORELAX-LABEL: <_start>:
+# NORELAX-NEXT:    10000:  auipc  t1, 0
+# NORELAX-NEXT:            jalr   zero, 32(t1)
+# NORELAX-NEXT:            auipc  t0, 0
+# NORELAX-NEXT:            jalr   zero, 24(t0)
+# NORELAX-NEXT:    10010:  auipc  ra, 0
+# NORELAX-NEXT:            jalr   ra, 16(ra)
+# NORELAX-NEXT:            auipc  ra, 0
+# NORELAX-NEXT:            jalr   ra, 1032(ra)
+# NORELAX-EMPTY:
+
+#--- a.s
+.global _start
+_start:
+  tail a@plt
+  jump a, t0
+.balign 16
+  call a          # rv32c: c.jal; rv64c: jal
+  call bar        # PLT call can be relaxed. rv32c: c.jal; rv64c: jal
+
+a:
+  ret
+.size _start, . - _start
+
+.section .mid,"ax",@progbits
+  call _start@plt # rv32c: c.jal; rv64c: jal
+  call _start@plt
+
+.section .high,"ax",@progbits
+  call _start@plt
+  call _start@plt # not relaxed
+.balign 16
+  addi a0, a0, 3
+  addi a0, a0, 3
+  # Initially jal can reach a. After shrinkage, auipc+jalr should be restored.
+  # Then jal can be used again.
+  call a
+
+#--- b.s
+.globl bar
+bar:
+  ret
+
+#--- lds
+SECTIONS {
+  .text 0x10000 : { *(.text) }
+  .plt 0x10400 : { *(.plt) }
+  .mid 0x10800 : { *(.mid) }
+  .high 0x110000 : { *(.high) }
+}