[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

494

RelType

506

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

551

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

666

R_RISCV_NONE

725

RelType (and maybe check != R_RISCV_NONE explicitly?)

754

(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.

 
 struct elf::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).
   std::unique_ptr<uint32_t[]> relocDeltas;
+  // For relocations[i], the actual type is relocTypes[i].
+  std::unique_ptr<RelType[]> relocTypes;
+  SmallVector<uint32_t, 0> writes;
 };
 
 static void initSymbolAnchors() {
   SmallVector<InputSection *, 0> storage;
   for (OutputSection *osec : outputSections) {
     if (!(osec->flags & SHF_EXECINSTR))
       continue;
     for (InputSection *sec : getInputSections(*osec, storage)) {
       sec->relaxAux = make<RISCVRelaxAux>();
-      if (sec->relocations.size())
+      if (sec->relocations.size()) {
         sec->relaxAux->relocDeltas =
             std::make_unique<uint32_t[]>(sec->relocations.size());
+        sec->relaxAux->relocTypes =
+            std::make_unique<RelType[]>(sec->relocations.size());
+      }
     }
   }
   // Store anchors (st_value and st_value+st_size) for symbols relative to text
   // sections.
   for (InputFile *file : ctx->objectFiles)
     for (Symbol *sym : file->getSymbols()) {
       auto *d = dyn_cast<Defined>(sym);
       if (!d || d->file != file)
for (InputSection *sec : getInputSections(*osec, storage)) {
       llvm::sort(sec->relaxAux->anchors, [](auto &a, auto &b) {
         return std::make_pair(a.offset, a.end) <
                std::make_pair(b.offset, b.end);
       });
     }
   }
 }
 
+// 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, uint32_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 =
+      (r.expr == R_PLT_PC ? sym.getPltVA() : sym.getVA()) + 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;
+  }
+}
+
 static bool relax(InputSection &sec) {
   const uint64_t secAddr = sec.getVA();
   auto &aux = *sec.relaxAux;
   bool changed = false;
 
   // Restore original st_value for symbols relative to this section.
   ArrayRef<SymbolAnchor> sa = makeArrayRef(aux.anchors);
   uint32_t delta = 0;
   for (auto it : llvm::enumerate(sec.relocations)) {
     for (; sa.size() && sa[0].offset <= it.value().offset; sa = sa.slice(1))
       if (!sa[0].end)
         sa[0].d->value += delta;
     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_n(aux.relocTypes.get(), sec.relocations.size(), R_RISCV_NONE);
+  aux.writes.clear();
   for (auto it : llvm::enumerate(sec.relocations)) {
     Relocation &r = it.value();
     const size_t i = it.index();
     const uint64_t loc = secAddr + r.offset - delta;
     uint32_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 = nextLoc - ((loc + align - 1) & -align);
       assert(static_cast<int32_t>(remove) >= 0 &&
              "R_RISCV_ALIGN needs expanding the content");
       break;
     }
+    case R_RISCV_CALL:
+    case R_RISCV_CALL_PLT:
+      if (i + 1 != sec.relocations.size() &&
+          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 previous relocation whose `relocDeltas` value equals `delta`.
     // Decrease their st_value and update their st_size.
     if (remove) {
       for (; sa.size() && sa[0].offset <= r.offset; sa = sa.slice(1)) {
         if (sa[0].end)
bool RISCV::relaxOnce(int pass) const {
   if (pass == 0)
     initSymbolAnchors();
 
   SmallVector<InputSection *, 0> storage;
   bool changed = false;
   for (OutputSection *osec : outputSections) {
     if (!(osec->flags & SHF_EXECINSTR))
       continue;
     for (InputSection *sec : getInputSections(*osec, storage))
       changed |= relax(*sec);
   }
   return changed;
 }
 
 void elf::riscvFinalizeRelax(int passes) {
   llvm::TimeTraceScope timeScope("Finalize RISC-V relaxation");
   log("relaxation passes: " + Twine(passes));
   SmallVector<InputSection *, 0> storage;
   for (OutputSection *osec : outputSections) {
     if (!(osec->flags & SHF_EXECINSTR))
       continue;
     for (InputSection *sec : getInputSections(*osec, storage)) {
       RISCVRelaxAux &aux = *sec->relaxAux;
       if (!aux.relocDeltas)
         continue;
 
       auto &rels = sec->relocations;
       ArrayRef<uint8_t> old = sec->rawData;
       size_t newSize =
           old.size() - aux.relocDeltas[sec->relocations.size() - 1];
+      size_t writesIdx = 0;
       uint8_t *p = context().bAlloc.Allocate<uint8_t>(newSize);
       uint64_t offset = 0;
       int64_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, storage)) {
             int64_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 (RelType 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);
 
       // Substract the previous relocDeltas value from the relocation offset.
       // For a pair of R_RISCV_CALL/R_RISCV_RELAX with the same offset, decrease
       // their r_offset by the same delta.
       delta = 0;
       for (size_t i = 0, e = rels.size(); i != e;) {
         uint64_t cur = rels[i].offset;
         do {
           rels[i].offset -= delta;
+          if (aux.relocTypes[i] != R_RISCV_NONE)
+            rels[i].type = aux.relocTypes[i];
         } while (++i != e && rels[i].offset == cur);
         delta = aux.relocDeltas[i - 1];
       }
     }
   }
 }
 
 TargetInfo *elf::getRISCVTargetInfo() {
   static RISCV target;
   return &target;
 }

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:       0001001c g       .text  {{0*}}00000000 _start_end
+# NORVC:       00010808 g       .mid   {{0*}}00000000 mid_end
+# NORVC:       00110016 g       .high  {{0*}}00000000 high_end
+
+# 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: <.mid2>:
+# NORVC-NEXT:    1080c:  jal    ra, {{.*}} <_start>
+# NORVC-EMPTY:
+
+# NORVC-LABEL: <.high>:
+# NORVC-NEXT:   110006:  auipc  ra, 1048320
+# NORVC-NEXT:            jalr   ra, -6(ra)
+# NORVC-NEXT:            auipc  ra, 1048320
+# NORVC-NEXT:            jalr   ra, -14(ra)
+# NORVC-EMPTY:
+
+# RVC32:       00010000 g       .text  00000016 _start
+# RVC32:       00010016 g       .text  00000000 _start_end
+# RVC32:       00010806 g       .mid   00000000 mid_end
+# RVC32:       0011000c g       .high  00000000 high_end
+# RVC64:       0000000000010000 g       .text  000000000000001a _start
+# RVC64:       000000000001001a g       .text  0000000000000000 _start_end
+# RVC64:       0000000000010808 g       .mid   0000000000000000 mid_end
+# RVC64:       0000000000110014 g       .high  0000000000000000 high_end
+
+# 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:   <.mid2>:
+# RVC32-NEXT:    1080a:  jal    ra, {{.*}} <_start>
+# RVC64-NEXT:    1080c:  jal    ra, {{.*}} <_start>
+# RVC-EMPTY:
+
+# RVC-LABEL:   <.high>:
+# RVC32-NEXT:   110000:  jal    ra, 0x10000 <_start>
+# RVC32-NEXT:            auipc  ra, 1048320
+# RVC32-NEXT:            jalr   ra, -4(ra)
+# RVC64-NEXT:   110004:  auipc  ra, 1048320
+# RVC64-NEXT:            jalr   ra, -4(ra)
+# RVC64-NEXT:            auipc  ra, 1048320
+# RVC64-NEXT:            jalr   ra, -12(ra)
+# 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_end
+_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
+_start_end:
+
+.section .mid,"ax",@progbits
+  call _start@plt # rv32c: c.jal; rv64c: jal
+  call _start@plt
+
+.section .mid2,"ax",@progbits
+  call _start@plt
+
+.section .high,"ax",@progbits
+  call _start@plt # relaxable for %t/32c
+  call _start@plt # not relaxed
+
+#--- b.s
+.globl bar
+bar:
+  ret
+
+#--- lds
+SECTIONS {
+  .text 0x10000 : { *(.text) }
+  .plt 0x10400 : { *(.plt) }
+  .mid 0x10800 : { *(.mid); mid_end = .; }
+  .mid2 mid_end+4 : { *(.mid2) }
+  # 22 is the size of _start in %t/32c (RVC32).
+  .high 0x110000+(_start_end-_start)-22 : { *(.high); high_end = .; }
+}

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

+# REQUIRES: riscv
+# RUN: rm -rf %t && split-file %s %t && cd %t
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+c,+relax a.s -o a.o
+
+# RUN: ld.lld -T lds a.o -o a
+# RUN: llvm-objdump -d --no-show-raw-insn -M no-aliases a | FileCheck %s
+
+## Unsure whether this needs a diagnostic. GNU ld allows this.
+# RUN: ld.lld -T lds -pie a.o -o a.pie
+# RUN: llvm-objdump -d --no-show-raw-insn -M no-aliases a.pie | FileCheck %s
+
+# RUN: ld.lld -T lds -pie -z notext -z ifunc-noplt a.o -o a.ifunc-noplt
+# RUN: llvm-objdump -d --no-show-raw-insn -M no-aliases a.ifunc-noplt | FileCheck %s --check-prefix=CHECK2
+
+# 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)
+# CHECK-EMPTY:
+
+# CHECK-LABEL:  <.mid>:
+# CHECK-NEXT:             jal    zero, 0x101000
+# CHECK-NEXT:             c.j    0x101000
+# CHECK-EMPTY:
+
+# CHECK2-LABEL: <.mid>:
+# CHECK2-NEXT:            auipc  t1, 0
+# CHECK2-NEXT:            jalr   zero, 0(t1)
+# CHECK2-NEXT:            auipc  t1, 0
+# CHECK2-NEXT:            jalr   zero, 0(t1)
+# CHECK2-EMPTY:
+
+#--- a.s
+.global _start, ifunc
+_start:
+  jump abs, t2
+  jump abs, t3
+  call abs
+  tail abs       # not relaxed
+
+.section .mid,"ax",@progbits
+.balign 16
+  tail ifunc@plt # not relaxed
+  tail ifunc@plt
+
+.type ifunc, @gnu_indirect_function
+ifunc:
+  ret
+
+#--- lds
+SECTIONS {
+  .text 0x100000 : { *(.text) }
+  .mid 0x100800 : { *(.mid) }
+  .iplt 0x101000 : { *(.iplt) }
+}
+abs = 8;