diff --git a/lld/ELF/Arch/RISCV.cpp b/lld/ELF/Arch/RISCV.cpp --- a/lld/ELF/Arch/RISCV.cpp +++ b/lld/ELF/Arch/RISCV.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "InputFiles.h" +#include "OutputSections.h" #include "Symbols.h" #include "SyntheticSections.h" #include "Target.h" @@ -36,6 +37,7 @@ const uint8_t *loc) const override; void relocate(uint8_t *loc, const Relocation &rel, uint64_t val) const override; + void relaxSections() const override; }; } // end anonymous namespace @@ -271,12 +273,7 @@ case R_RISCV_TPREL_ADD: return R_NONE; case R_RISCV_ALIGN: - // Not just a hint; always padded to the worst-case number of NOPs, so may - // not currently be aligned, and without linker relaxation support we can't - // delete NOPs to realign. - errorOrWarn(getErrorLocation(loc) + "relocation R_RISCV_ALIGN requires " - "unimplemented linker relaxation; recompile with -mno-relax"); - return R_NONE; + return R_RELAX_HINT; default: error(getErrorLocation(loc) + "unknown relocation (" + Twine(type) + ") against symbol " + toString(s)); @@ -476,6 +473,185 @@ } } +static void getSymbolAnchors() { + for (OutputSection *osec : outputSections) { + if (!(osec->flags & SHF_EXECINSTR)) + continue; + for (InputSection *sec : getInputSections(*osec)) { + sec->relaxAux = make(); + sec->relaxAux->relocDeltas.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(sym); + if (!d || d->file != file) + continue; + if (auto *sec = dyn_cast_or_null(d->section)) + if (sec->flags & SHF_EXECINSTR) { + sec->relaxAux->anchors.push_back({d->value, d, false}); + sec->relaxAux->anchors.push_back({d->value + d->size, d, true}); + } + } + // Sort anchors by offset. + for (OutputSection *osec : outputSections) { + 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; }); + } + } +} + +// Do a relaxation pass and return true if we changed something. When relaxing +// just R_RISCV_ALIGN, relocDeltas is only changed once. For call and load/store +// R_RISCV_RELAX, code shrinkage may reduce distances and make some relocations +// eligible for relaxation. Code shrinkage may increase distance to a +// call/load/store target at a higher fixed address, invalidating an earlier +// relaxation which must now be undone. Any change in section sizes can have +// cascading effect and require another relaxation pass. +static bool relaxOnce() { + bool changed = false; + for (OutputSection *osec : outputSections) { + if (!(osec->flags & SHF_EXECINSTR)) + continue; + uint64_t dot = 0; + for (InputSection *sec : getInputSections(*osec)) { + auto &aux = *sec->relaxAux; + int32_t delta = 0; + // dot is like outSecOff, but taking into account of deleted bytes. + dot = alignTo(dot, sec->alignment); + for (auto &it : llvm::enumerate(sec->relocations)) { + const Relocation &r = it.value(); + const uint64_t loc = dot + r.offset - delta; + int32_t &cur = aux.relocDeltas[it.index()]; + switch (r.type) { + case R_RISCV_ALIGN: { + const uint64_t nextLoc = loc + r.addend; + const uint64_t align = PowerOf2Ceil(r.addend + 2); + // Adjust delta by nops_bytes - needed_nops_bytes. + delta += static_cast(nextLoc - ((loc + align - 1) & -align)); + assert(delta >= 0 && "R_RISCV_ALIGN needs expanding the content"); + break; + } + default: + // TODO: handle call/jump/load/store/addr-arithmetic relaxation + break; + } + // Update relocDeltas: r.offset-cur is the actual relocation offset. + if (delta != cur) { + cur = delta; + changed = true; + } + } + dot += sec->rawData.size() - delta; + } + } + return changed; +} + +void RISCV::relaxSections() const { + if (config->relocatable) + return; + + int pass = 1; + getSymbolAnchors(); + while (relaxOnce()) { + script->assignAddresses(); + if (++pass >= 10) { + errorOrWarn("relaxation does not converge"); + return; + } + } + log("relaxation passes: " + Twine(pass)); + if (pass == 1) + return; + + for (OutputSection *osec : outputSections) { + if (!(osec->flags & SHF_EXECINSTR)) + continue; + for (InputSection *sec : getInputSections(*osec)) { + RISCVRelaxAux &aux = *sec->relaxAux; + if (aux.relocDeltas.empty()) + continue; + + // Delete ranges. + auto &rels = sec->relocations; + ArrayRef old = sec->rawData; + size_t newSize = old.size() - aux.relocDeltas.back(); + uint8_t *p = context().bAlloc.Allocate(newSize); + uint64_t offset = 0; + int32_t delta = 0, nopBytes = 0; + sec->rawData = makeArrayRef(p, newSize); + auto writeNops = [&]() { + if (nopBytes) { + int32_t j = 0; + for (; j + 4 <= nopBytes; j += 4) + write32le(p + j, 0x00000013); // nop + if (j != nopBytes) { + assert(j + 2 == nopBytes); + write16le(p + j, 0x0001); // c.nop + } + } + }; + + for (size_t i = 0, e = sec->relocations.size(); i != e; ++i) { + // If this is a R_RISCV_ALIGN, -inc is the number of bytes which should + // be removed starting at r_offset. + int32_t inc = aux.relocDeltas[i] - delta; + delta = aux.relocDeltas[i]; + if (inc == 0) + continue; + assert(inc > 0); + + // Copy [offset, r.offset). If the previous relocation is R_RISCV_ALIGN, + // `offset` is placed in a location (among NOPs) to satisfy the + // alignment requirement. We use a non-zero `nopBytes` to indicate that + // `offset` is placed in the middle of a 4-byte NOP. We need to rewrite + // the NOP sequence. + const Relocation &r = rels[i]; + memcpy(p, old.data() + offset, r.offset - offset); + writeNops(); + p += r.offset - offset; + + // Place the cursor at or ahead of r.offset. + offset = r.offset + inc; + // As an optimization: if inc is a multiple 4, `offset` is at the start + // of a NOP or the next non-padding instruction. We don't need to + // rewrite the NOP sequence (nopBytes can be 0). + if (r.type == R_RISCV_ALIGN && inc % 4 != 0) + nopBytes = r.addend - inc; + else + nopBytes = 0; + } + // Copy [offset, old.size()). Then possibly rewrite the NOP sequence. + memcpy(p, old.data() + offset, old.size() - offset); + writeNops(); + + // Decrease symbol values and relocation offsets. + size_t i = 0; + delta = 0; + for (SymbolAnchor &sa : aux.anchors) { + for (; i < rels.size() && rels[i].offset < sa.offset; ++i) { + rels[i].offset -= delta; + delta = aux.relocDeltas[i]; + } + if (sa.end) + sa.d->size = sa.offset - delta - sa.d->value; + else + sa.d->value -= delta; + } + for (; i < rels.size(); ++i) { + rels[i].offset -= delta; + delta = aux.relocDeltas[i]; + } + } + } +} + TargetInfo *elf::getRISCVTargetInfo() { static RISCV target; return ⌖ diff --git a/lld/ELF/InputSection.h b/lld/ELF/InputSection.h --- a/lld/ELF/InputSection.h +++ b/lld/ELF/InputSection.h @@ -10,7 +10,9 @@ #define LLD_ELF_INPUT_SECTION_H #include "Relocations.h" +#include "lld/Common/CommonLinkerContext.h" #include "lld/Common/LLVM.h" +#include "lld/Common/Memory.h" #include "llvm/ADT/CachedHashString.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/TinyPtrVector.h" @@ -97,6 +99,23 @@ link(link), info(info) {} }; +struct SymbolAnchor { + uint64_t offset; + Defined *d; + bool end; // true for the anchor of st_value+st_size +}; + +// Auxiliary information for RISC-V linker relaxation, attached to an +// InputSection. +struct RISCVRelaxAux { + // This records symbol start and end offsets which will be adjusted according + // to the nearest relocDeltas element. + SmallVector anchors; + // For relocations[i], the actual offset is r_offset - (i ? relocDeltas[i-1] : + // 0). + SmallVector relocDeltas; +}; + // This corresponds to a section of an input file. class InputSectionBase : public SectionBase { public: @@ -201,11 +220,15 @@ // This vector contains such "cooked" relocations. SmallVector relocations; - // These are modifiers to jump instructions that are necessary when basic - // block sections are enabled. Basic block sections creates opportunities to - // relax jump instructions at basic block boundaries after reordering the - // basic blocks. - JumpInstrMod *jumpInstrMod = nullptr; + union { + // These are modifiers to jump instructions that are necessary when basic + // block sections are enabled. Basic block sections creates opportunities + // to relax jump instructions at basic block boundaries after reordering the + // basic blocks. + JumpInstrMod *jumpInstrMod = nullptr; + + RISCVRelaxAux *relaxAux; + }; // A function compiled with -fsplit-stack calling a function // compiled without -fsplit-stack needs its prologue adjusted. Find diff --git a/lld/ELF/InputSection.cpp b/lld/ELF/InputSection.cpp --- a/lld/ELF/InputSection.cpp +++ b/lld/ELF/InputSection.cpp @@ -621,6 +621,8 @@ return sym.getVA(a); case R_ADDEND: return a; + case R_RELAX_HINT: + return 0; case R_ARM_SBREL: return sym.getVA(a) - getARMStaticBase(sym); case R_GOT: @@ -986,6 +988,8 @@ *rel.sym, rel.expr), bits); switch (rel.expr) { + case R_RELAX_HINT: + continue; case R_RELAX_GOT_PC: case R_RELAX_GOT_PC_NOPIC: target.relaxGot(bufLoc, rel, targetVA); diff --git a/lld/ELF/Relocations.h b/lld/ELF/Relocations.h --- a/lld/ELF/Relocations.h +++ b/lld/ELF/Relocations.h @@ -46,6 +46,7 @@ R_PLT, R_PLT_PC, R_PLT_GOTPLT, + R_RELAX_HINT, R_RELAX_GOT_PC, R_RELAX_GOT_PC_NOPIC, R_RELAX_TLS_GD_TO_IE, diff --git a/lld/ELF/Relocations.cpp b/lld/ELF/Relocations.cpp --- a/lld/ELF/Relocations.cpp +++ b/lld/ELF/Relocations.cpp @@ -956,8 +956,8 @@ const Symbol &sym, uint64_t relOff) const { // These expressions always compute a constant - if (oneof(e)) diff --git a/lld/ELF/Target.h b/lld/ELF/Target.h --- a/lld/ELF/Target.h +++ b/lld/ELF/Target.h @@ -92,6 +92,8 @@ virtual void applyJumpInstrMod(uint8_t *loc, JumpModType type, JumpModType val) const {} + virtual void relaxSections() const {} + virtual ~TargetInfo(); // This deletes a jump insn at the end of the section if it is a fall thru to diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp --- a/lld/ELF/Writer.cpp +++ b/lld/ELF/Writer.cpp @@ -1630,6 +1630,8 @@ if (config->emachine == EM_HEXAGON) hexagonTLSSymbolUpdate(outputSections); + target->relaxSections(); + int assignPasses = 0; for (;;) { bool changed = target->needsThunks && tc.createThunks(outputSections); diff --git a/lld/test/ELF/riscv-relax-align-rvc.s b/lld/test/ELF/riscv-relax-align-rvc.s new file mode 100644 --- /dev/null +++ b/lld/test/ELF/riscv-relax-align-rvc.s @@ -0,0 +1,75 @@ +# REQUIRES: riscv + +# RUN: rm -rf %t && mkdir %t && cd %t + +# RUN: llvm-mc -filetype=obj -triple=riscv32 -mattr=+c,+relax %s -o 32.o +# RUN: ld.lld -Ttext=0x10000 32.o -o 32 +# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 32 | FileCheck %s +## R_RISCV_ALIGN is handled regarldess of --no-relax. +# RUN: ld.lld -Ttext=0x10000 --no-relax 32.o -o 32.norelax +# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 32.norelax | FileCheck %s + +# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+c,+relax %s -o 64.o +# RUN: ld.lld -Ttext=0x10000 64.o -o 64 +# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 64 | FileCheck %s +# RUN: ld.lld -Ttext=0x10000 --no-relax 64.o -o 64.norelax +# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 64.norelax | FileCheck %s + +# CHECK-DAG: 00010002 l .text {{0*}}1e a +# CHECK-DAG: 00010010 l .text {{0*}}22 b +# CHECK-DAG: 00010012 l .text {{0*}}1e c +# CHECK-DAG: 00010020 l .text {{0*}}16 d +# CHECK-DAG: 00010000 g .text {{0*}}36 _start + +# CHECK: <_start>: +# CHECK-NEXT: c.addi a0, 1 +# CHECK-EMPTY: +# CHECK-NEXT: : +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: c.nop +# CHECK-EMPTY: +# CHECK-NEXT: : +# CHECK-NEXT: 10010: c.addi a0, 2 +# CHECK-EMPTY: +# CHECK-NEXT: : +# CHECK-NEXT: c.addi a0, 3 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-EMPTY: +# CHECK-NEXT: : +# CHECK-NEXT: 10020: c.addi a0, 4 +# CHECK-NEXT: c.addi a0, 5 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: 10030: c.addi a0, 6 +# CHECK-NEXT: c.addi a0, 7 +# CHECK-NEXT: c.addi a0, 8 +# CHECK-EMPTY: + +.global _start +_start: + c.addi a0, 1 +a: +.balign 16 +b: + c.addi a0, 2 +c: + c.addi a0, 3 +.balign 32 +.size a, . - a +d: + c.addi a0, 4 + c.addi a0, 5 +.balign 16 +.size c, . - c + c.addi a0, 6 +.size b, . - b + c.addi a0, 7 +.balign 4 + c.addi a0, 8 +.size d, . - d +.size _start, . - _start diff --git a/lld/test/ELF/riscv-relax-align.s b/lld/test/ELF/riscv-relax-align.s new file mode 100644 --- /dev/null +++ b/lld/test/ELF/riscv-relax-align.s @@ -0,0 +1,124 @@ +# REQUIRES: riscv +## Test that we can handle R_RISCV_ALIGN. + +# RUN: rm -rf %t && mkdir %t && cd %t + +# RUN: llvm-mc -filetype=obj -triple=riscv32 -mattr=+relax %s -o 32.o +# RUN: ld.lld -Ttext=0x10000 32.o -o 32 +# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 32 | FileCheck %s +## R_RISCV_ALIGN is handled regarldess of --no-relax. +# RUN: ld.lld -Ttext=0x10000 --no-relax 32.o -o 32.norelax +# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 32.norelax | FileCheck %s + +# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+relax %s -o 64.o +# RUN: ld.lld -Ttext=0x10000 64.o -o 64 +# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 64 | FileCheck %s +# RUN: ld.lld -Ttext=0x10000 --no-relax 64.o -o 64.norelax +# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 64.norelax | FileCheck %s + +# RUN: ld.lld -Ttext=0x10000 --emit-relocs 64.o -o 64 +# RUN: llvm-objdump -td --no-show-raw-insn -M no-aliases 64 | FileCheck %s +# RUN: llvm-readelf -r 64 | FileCheck %s --check-prefix=EMIT + +# CHECK-DAG: 00010004 l .text {{0*}}1c a +# CHECK-DAG: 00010008 l .text {{0*}}28 b +# CHECK-DAG: 00010014 l .text {{0*}}20 c +# CHECK-DAG: 00010000 g .text {{0*}}38 _start + +# CHECK: <_start>: +# CHECK-NEXT: addi a0, a0, 1 +# CHECK-EMPTY: +# CHECK-NEXT: : +# CHECK-NEXT: addi a0, a0, 2 +# CHECK-EMPTY: +# CHECK-NEXT: : +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: 10010: addi a0, a0, 3 +# CHECK-EMPTY: +# CHECK-NEXT: : +# CHECK-NEXT: addi a0, a0, 4 +# CHECK-NEXT: addi a0, a0, 5 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: 10020: addi a0, a0, 6 +# CHECK-NEXT: addi a0, a0, 7 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: 10030: addi a0, a0, 8 +# CHECK-NEXT: addi a0, a0, 9 +# CHECK: : +# CHECK-NEXT: addi a0, a0, 1 +# CHECK-EMPTY: +# CHECK-NEXT: : +# CHECK-NEXT: 10044: addi a0, a0, 2 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: 10060: addi a0, a0, 3 + +## _start-0x10070 = 0x10000-0x10070 = -112 +# CHECK: <.L1>: +# CHECK-NEXT: 10070: auipc a0, 0 +# CHECK-NEXT: addi a0, a0, -112 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: addi zero, zero, 0 +# CHECK-NEXT: auipc a0, 0 +# CHECK-NEXT: addi a0, a0, -112 +# CHECK-EMPTY: + +# EMIT: Relocation section '.rela.text' at offset {{.*}} contains 3 entries: +# EMIT: 0000000000010008 {{.*}} R_RISCV_ALIGN c +# EMIT-NEXT: 0000000000010020 {{.*}} R_RISCV_ALIGN 1c +# EMIT-NEXT: 0000000000010044 {{.*}} R_RISCV_ALIGN c +# EMIT: Relocation section '.rela.text2' at offset {{.*}} contains 2 entries: +# EMIT: 0000000000010040 {{.*}} R_RISCV_ALIGN 4 +# EMIT-NEXT: 000000000001004c {{.*}} R_RISCV_ALIGN 1c + +.global _start +_start: + addi a0, a0, 1 +a: + addi a0, a0, 2 +b: +.balign 16 + addi a0, a0, 3 +c: + addi a0, a0, 4 + addi a0, a0, 5 +.balign 32 +.size a, . - a + addi a0, a0, 6 + addi a0, a0, 7 +.balign 16 +.size b, . - b + addi a0, a0, 8 +.size c, . - c + addi a0, a0, 9 +.size _start, . - _start + +## Test another text section. +.section .text2,"ax",@progbits +d: +e: +.balign 8 + addi a0, a0, 1 +f: + addi a0, a0, 2 +.balign 32 +.size d, . - d + addi a0, a0, 3 +.size e, . - e +.size f, . - f + +## Test that matching HI20 can be found despite deleted bytes. +.section .pcrel,"ax",@progbits +.L1: + auipc a0, %pcrel_hi(_start) + addi a0, a0, %pcrel_lo(.L1) +.balign 16 +.L2: + auipc a0, %pcrel_hi(_start) + addi a0, a0, %pcrel_lo(.L1) diff --git a/lld/test/ELF/riscv-reloc-align.s b/lld/test/ELF/riscv-reloc-align.s deleted file mode 100644 --- a/lld/test/ELF/riscv-reloc-align.s +++ /dev/null @@ -1,12 +0,0 @@ -# REQUIRES: riscv - -# RUN: llvm-mc -filetype=obj -triple=riscv32 -mattr=+relax %s -o %t.o -# RUN: not ld.lld %t.o -o /dev/null 2>&1 | FileCheck %s - -# CHECK: relocation R_RISCV_ALIGN requires unimplemented linker relaxation - -.global _start -_start: - nop - .balign 8 - nop