[ELF] Relax R_RISCV_ALIGN

[MaskRay]

Summary

Alternative to D125036. Implement R_RISCV_ALIGN relaxation so that we can handle
-mrelax object files (i.e. -mno-relax is no longer needed) and creates a
framework for future relaxation.

relaxAux is placed in a union with InputSectionBase::jumpInstrMod, storing
auxiliary information for relaxation. In the first pass, relaxAux is allocated.
The main data structure is relocDeltas: when referencing relocations[i], the
actual offset is r_offset - (i ? relocDeltas[i-1] : 0).

relaxOnce performs one relaxation pass. It computes relocDeltas for all text
section. Then, adjust st_value/st_size for symbols relative to this section
based on SymbolAnchor. bytesDropped is set so that assignAddresses knows
that the size has changed.

Run relaxOnce in the finalizeAddressDependentContent loop to wait for
convergence of text sections and other address dependent sections (e.g.
SHT_RELR). Note: extrating relaxOnce into a separate loop works for many cases
but has issues in some linker script edge cases.

After convergence, compute section contents: shrink the NOP sequence of each
R_RISCV_ALIGN as appropriate. Instead of deleting bytes, we run a sequence of
memcpy on the content delimitered by relocation locations. For R_RISCV_ALIGN let
the next memcpy skip the desired number of bytes. Section content computation is
parallelizable, but let's ensure the implementation is mature before
optimizations. Technically we can save a copy if we interleave some code with
OutputSection::writeTo, but let's not pollute the generic code (we don't have
templated relocation resolving, so using conditions can impose overhead to
non-RISCV.)

Tested:
make ARCH=riscv CROSS_COMPILE=riscv64-linux-gnu- LLVM=1 defconfig all
built kernel is bootable.

[MaskRay]

x

[MaskRay]

R_RISCV_CALL patch will follow

[MaskRay]

simplify

[MaskRay]

adjust test. add more comments

[MaskRay]

Handle --gc-sections

[luismarques]

lld/ELF/LinkerScript.cpp

949–950 ↗

(On Diff #436867)

Document return

1326 ↗

(On Diff #436867)

We don't have test coverage for this.

[MaskRay]

Remove unneeded assignAddress change

[MaskRay]

lld/ELF/LinkerScript.cpp

949–950 ↗

(On Diff #436867)

I think assignOffsets does not need a change. Removed

1326 ↗

(On Diff #436867)

I removed this change.

If we exit the loop with

relaxOnce => true
assignAddresses   # address updated with correct section size information
relaxOnce => false   # instruction relaxation output does not change

It has converged.

[MaskRay]

(I intended to only bother Peter after some RISC-V folks made some verification, but I guess the two steps can be parallel. This works for some configurations I know, including @compnerd's usage.)
I have asked a distrubotr @felixonmars for testing as well.

[tschuett]

Do you really need a plain union? How about a PointerUnion or something llvmy std::variant?

[MaskRay]

In D127581#3594812, @tschuett wrote:

Do you really need a plain union? How about a PointerUnion or something llvmy std::variant?

The size is very important for memory usage. 8 or 16 bytes here may cost 1% maximum RSS.
Since PointerUnion abstraction seems unnecessary, I'd want to avoid it.

[tschuett]

In D127581#3595064, @MaskRay wrote:

In D127581#3594812, @tschuett wrote:

Do you really need a plain union? How about a PointerUnion or something llvmy std::variant?

The size is very important for memory usage. 8 or 16 bytes here may cost 1% maximum RSS.
Since PointerUnion abstraction seems unnecessary, I'd want to avoid it.

I would expect the size of the pointer union to be 8 bytes. My main motivation is that unions are odd.

[MaskRay]

In D127581#3595417, @tschuett wrote:

In D127581#3595064, @MaskRay wrote:

In D127581#3594812, @tschuett wrote:

Do you really need a plain union? How about a PointerUnion or something llvmy std::variant?

The size is very important for memory usage. 8 or 16 bytes here may cost 1% maximum RSS.
Since PointerUnion abstraction seems unnecessary, I'd want to avoid it.

I would expect the size of the pointer union to be 8 bytes. My main motivation is that unions are odd.

PointerUnion will not increase the size, but the additional abstraction is unnecessary. Both features are used in very specific context and there is no need to worry about misuse (and if there is a misuse, it will fail immediately). I'd also want to avoid the cost clearing the least significant bit.

[arichardson]

I haven't looked at the code yet, but I can confirm that I was able to build and boot FreeBSD for RISCV64 with this patch and the FreeBSD patch below to remove -mno-relax (I could have just defined the riscv-relaxations linker feature, but I wanted to make sure that the code is actually built with relaxations):

diff --git a/share/mk/bsd.lib.mk b/share/mk/bsd.lib.mk
index 36d91ea019f3..b37ebe39ecf4 100644
--- a/share/mk/bsd.lib.mk
+++ b/share/mk/bsd.lib.mk
@@ -123,8 +123,8 @@ CXXFLAGS+= ${DEBUG_FILES_CFLAGS}
 CTFFLAGS+= -g
 .endif
 
-.if ${MACHINE_CPUARCH} == "riscv" && ${LINKER_FEATURES:Mriscv-relaxations} == ""
-CFLAGS += -mno-relax
+.if ${MACHINE_CPUARCH} == "riscv"
+CFLAGS += -mrelax
 .endif
 
 .include <bsd.libnames.mk>
diff --git a/share/mk/bsd.prog.mk b/share/mk/bsd.prog.mk
index 6b8da09edaf0..3743250c2c87 100644
--- a/share/mk/bsd.prog.mk
+++ b/share/mk/bsd.prog.mk
@@ -84,8 +84,8 @@ CXXFLAGS+= -ftrivial-auto-var-init=pattern
 # bsd.sanitizer.mk is not installed, so don't require it (e.g. for ports).
 .sinclude "bsd.sanitizer.mk"
 
-.if ${MACHINE_CPUARCH} == "riscv" && ${LINKER_FEATURES:Mriscv-relaxations} == ""
-CFLAGS += -mno-relax
+.if ${MACHINE_CPUARCH} == "riscv"
+CFLAGS += -mrelax
 .endif
 
 .if defined(CRUNCH_CFLAGS)
diff --git a/share/mk/bsd.sys.mk b/share/mk/bsd.sys.mk
index 221e8b028479..f6266d7b991b 100644
--- a/share/mk/bsd.sys.mk
+++ b/share/mk/bsd.sys.mk
@@ -83,6 +83,13 @@ CWARNFLAGS.clang+=   -Wno-unused-const-variable
 .if ${COMPILER_TYPE} == "clang" && ${COMPILER_VERSION} >= 130000
 CWARNFLAGS.clang+=     -Wno-error=unused-but-set-variable
 .endif
+.if ${COMPILER_TYPE} == "clang" && ${COMPILER_VERSION} >= 150000
+CWARNFLAGS.clang+=     -Wno-deprecated-non-prototype
+CWARNFLAGS.clang+=     -Wno-unreachable-code-generic-assoc
+CWARNFLAGS.clang+=     -Wno-strict-prototypes
+CWARNFLAGS.clang+=     -Wno-error=unused-but-set-parameter
+CWARNFLAGS.clang+=     -Wno-error=implicit-function-declaration
+.endif
 .endif # WARNS <= 6
 .if ${WARNS} <= 3
 CWARNFLAGS.clang+=     -Wno-tautological-compare -Wno-unused-value\
diff --git a/stand/defs.mk b/stand/defs.mk
index e9c97f7720ab..753bf39ced31 100644
--- a/stand/defs.mk
+++ b/stand/defs.mk
@@ -175,9 +175,7 @@ CFLAGS+=    -fPIC
 
 # Some RISC-V linkers have support for relaxations, while some (lld) do not
 # yet. If this is the case we inhibit the compiler from emitting relaxations.
-.if ${LINKER_FEATURES:Mriscv-relaxations} == ""
-CFLAGS+=       -mno-relax
-.endif
+CFLAGS+=       -mrelax
 
 # The boot loader build uses dd status=none, where possible, for reproducible
 # build output (since performance varies from run to run). Trouble is that
diff --git a/sys/conf/kern.mk b/sys/conf/kern.mk
index b86149ab4618..2c82ff97b88e 100644
--- a/sys/conf/kern.mk
+++ b/sys/conf/kern.mk
@@ -34,6 +34,9 @@ NO_WUNUSED_BUT_SET_VARIABLE=  -Wno-unused-but-set-variable
 .if ${COMPILER_VERSION} >= 140000
 NO_WBITWISE_INSTEAD_OF_LOGICAL=        -Wno-bitwise-instead-of-logical
 .endif
+.if ${COMPILER_VERSION} >= 150000
+CWARNFLAGS+=   -Wno-strict-prototypes -Wno-error=unused-but-set-variable
+.endif
 # Several other warnings which might be useful in some cases, but not severe
 # enough to error out the whole kernel build.  Display them anyway, so there is
 # some incentive to fix them eventually.
@@ -151,9 +154,7 @@ CFLAGS.clang+=      -mcmodel=medium
 CFLAGS.gcc+=   -mcmodel=medany
 INLINE_LIMIT?= 8000
 
-.if ${LINKER_FEATURES:Mriscv-relaxations} == ""
-CFLAGS+=       -mno-relax
-.endif
+CFLAGS+=       -mrelax
 .endif
 
 #

[peter.smith]

I'll leave the RISCV details to the experts. General approach looks good to me.

lld/ELF/InputSection.h

102

It looks like the definitions are only used in RISCV.cpp as only a pointer is used in the union below. Could these be forward declared here?

I could be missing some use though.

223

update comment for relaxAux? I assume that the union is because we don't have relaxation and basic block sections simultaneously?

lld/ELF/Target.h

92

Will be worth a comment like needsThunk to describe what this does, just in case another architecture chooses to do RiscV like relaxations.

lld/ELF/Writer.cpp

1639

Although more source changes. Would it be cleaner to have the passes variable here, and pass it into createThunks as a parameter?

[gkm]

lld/ELF/Arch/RISCV.cpp

592

InputSectionBase::bytesDropped is merely uint8_t, and feels vulnerable to overflow. The comment on the decl says it is intended for basic-block sections, for which 8 bits is reasonable, but this new use, it might be inadequate. Perhaps uint16_t ?

[MaskRay]

comments

[kito-cheng]

lld/ELF/Arch/RISCV.cpp

609

I hit overflow here as @gkm concern, and the fixed by changing bytesDropped to uint16_t (yeah, I tested the uint8_t version), maybe we can put an assert (delta <= numeric_limits<uint16_t>::max()); here to make sure this could catch earlier?

I saw there are assertions for byteDropped in other place, so I think that should be reasonable?

[kitoc@xxxx llvm-project]$ grpe bytesDropped  * -R
...
lld/ELF/InputSection.h:  uint8_t bytesDropped = 0;
lld/ELF/InputSection.h:    assert(bytesDropped + num < 256);
lld/ELF/InputSection.h:    bytesDropped += num;
lld/ELF/InputSection.h:    assert(bytesDropped >= num);
lld/ELF/InputSection.h:    bytesDropped -= num;
...

Gonna run second round of testing.

[luismarques]

lld/ELF/Arch/RISCV.cpp

553–561

Can't we skip this for the first pass?

562–564

No test coverage for this?

[luismarques]

lld/ELF/Arch/RISCV.cpp

562–564

Nevermind. D127611.

[gkm]

lld/ELF/InputSection.h

161

[MaskRay]

add // namespace

lld/ELF/Arch/RISCV.cpp

553–561

This code takes nearly no time. I don't think we should special case the first pass.

592

Thanks!

609

push_back/drop_back is a code problem of the basic block sections feature. I don't intend to touch the functions for this patch.
Changed RISCV.cpp:611 instead.

lld/ELF/InputSection.h

161

push_back/drop_back is a code problem of the basic block sections feature. I don't intend to touch the functions for this patch.
Changed RISCV.cpp:611 instead.

lld/ELF/Writer.cpp

1639

ThunkCreator::pass needs to be retained, otherwise uint32_t pass needs to be threading though most of its member functions.

[peter.smith]

Thanks for the updates, I don't have any more comments. Happy for someone comfortable with RISCV to approve when they are happy with the details.

[VincentWu]

I have used this patch to compile and link to the software below. Generally, there are no obvious problems with this patch.

1. curl-7.82.0:
   • command: ./configure CC=/path/to/clang LDFLAGS="-fuse-ld=lld --ld-path=/path/to/ld.lld -mrelax" --without-ssl
   • result：The compiler and linker works fine and all the tests that are provided have passed. Simply running is fine.

2. bash-5.1:
   • command: ./configure CC_FOR_BUILD=/path/to/clang LDFLAGS_FOR_BUILD="-fuse-ld=lld --ld-path=/path/to/ld.lld -mrelax" CC=/path/to/clang LDFLAGS="-fuse-ld=lld --ld-path=/path/to/ld.lld -mrelax"
   • result：The compiler and linker works fine and part of the tests that are provided has passed. Failed test not related to this patch. Simply running is fine.

3. vim 8.2.5:
   • command: ./configure CC=/path/to/clang LDFLAGS="-fuse-ld=lld --ld-path=/path/to/ld.lld -mrelax
   • result：The compiler and linker works fine and part of the tests that are provided has passed. Failed test not related to this patch. Simply running is fine.

4. libevent:
   • command: ./configure CC=/path/to/clang LDFLAGS="-fuse-ld=lld --ld-path=/path/to/ld.lld -mrelax"
   • result: The compiler and linker works fine and all the tests that are provided have passed.

5. tmux:
   • command: ./configure CC=/path/to/clang LDFLAGS="-fuse-ld=lld --ld-path=/path/to/ld.lld -mrelax"
   • result: The compiler and linker works fine. run make check have no error. Simply running is fine.

[kito-cheng]

Tested with this patch with LLVM testsuite and internal testsuite, and no failure :)

[MaskRay]

Thanks for all the suggestions and testing! I think the approach implemented in this patch series is what we should use. I'll wait a week and push the two...

[felixonmars]

In D127581#3594793, @MaskRay wrote:

I have asked a distrubotr @felixonmars for testing as well.

Thanks for the patch. We (@Arch) have done some extended testing with for example the Firefox browser, and everything looks good so far.

[MaskRay]

Ping @jrtc27

[jrtc27]

lld/ELF/Arch/RISCV.cpp

276

ALIGN is not a hint, it's a requirement (as opposed to R_RISCV_RELAX, which is a true hint). I would suggest separating these two notions at the RelExpr level, then the config->relax check to skip R_RISCV_RELAX in the CALL(_PLT) patch can instead be done at the generic level rather than in the target.

490

Should this not be Elf_Sword or similar? ELFCLASS64 _can_ overflow this, even if you really really really shouldn't.

493

A getter that returns nothing is odd, saveSymbolAnchors/recordSymbolAnchors/initSymbolAnchors/similar?

499

Do you not just want an int32_t * (or smart pointer) given it's either 0 or relocations.size() elements? SmallVector adds overhead as it tracks both size and capacity, but we don't need any dynamic behaviour (beyond "does not exist" (null) and "exists with relocations.size() elements").

522

Does this not need to be stable_sort to guarantee the zero-sized symbols have their anchors in the right order? Also, does the order of A's end vs B's start matter for this implementation? That should be documented (and, ideally, why).

539

This seems like it belongs in generic code?

553

Is this actually the original st_value? If you interleave relaxation with other adjustment of st_value, won't delta stay the same but then the "unrelaxed" st_value will be different?

569

It might be nice to hoist this out to a separate function, it's quite nested here and this is the bit people care about editing to add new relaxations, so separating the "do the relaxations" part from all the tracking infrastructure would help there.

652

I don't know if it's a requirement that, say, 6 padding bytes be emitted as nop; c.nop rather than c.nop; nop. Does binutils make this assumption?

[MaskRay]

comments

lld/ELF/Arch/RISCV.cpp

276

The R_RISCV_ALIGN case label is specific to RISC-V. The pass is done after scanRelocations, so the code does not fit into the generic code. RelExpr can be split for ALIGN and RELAX but its necessity isn't that high. If just that HINT is a bit of misnomer I can rename it separately to R_RELAX or R_RELAX_OR_ALIGN.

490

There are precedents using int32_t in many places. Elf_Sword is not used. Since relocations aren't that many, just switched to int64_t.

499

changed to std::unique_ptr<int64_t[]>

522

llvm::sort is fine. The previous comment explains it. Improved the comment a bit.

539

This is RISC-V specific. Unless another supported architecture adds relaxation, this can stay here.

553

For most symbols, this is the original st_value.
Linker script symbol assignments may rewrite st_value (and does not care about the original value).
The code should be fine.

652

I vaguely remember that GNU ld seems to use nop; c.nop (prefer long to short). This code should match its behavior.

[MaskRay]

lld/ELF/Arch/RISCV.cpp

490

Hmm. I guess the original int32_t or uint32_t may be better.

[MaskRay]

Thank for the thorough comments.
I'll push this in few days if there is no further request.

Rebase after a getInputSections optimization

[nickdesaulniers]

Thanks for implementing this! Tested the kernel patch works well.
https://lore.kernel.org/llvm/[e-mail]/

[luismarques]

lld/ELF/Arch/RISCV.cpp

598

@MaskRay I ran into this error when building LLVM with LLD in a RISC-V host. I guess we actually need an int32?

[MaskRay]

lld/ELF/Arch/RISCV.cpp

598

This will increase the size of InputSection which we should try to avoid (memory usage increase). I am on a trip so cannot investigate it closely.

It will help if you can ask the author of --optimize-bb-jumps whether it is still used. Removing nopFiller will make room for delta.

[luismarques]

lld/ELF/Arch/RISCV.cpp

598

It will help if you can ask the author of --optimize-bb-jumps whether it is still used. Removing nopFiller will make room for delta.

@tmsriram any comments?

lld/ELF/Arch/RISCV.cpp

 //===- RISCV.cpp ----------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputFiles.h"
+#include "OutputSections.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 using namespace llvm::ELF;
public:
   void writePltHeader(uint8_t *buf) const override;
   void writePlt(uint8_t *buf, const Symbol &sym,
                 uint64_t pltEntryAddr) const override;
   RelType getDynRel(RelType type) const override;
   RelExpr getRelExpr(RelType type, const Symbol &s,
                      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
 
 const uint64_t dtpOffset = 0x800;
 
 enum Op {
   ADDI = 0x13,
RelExpr RISCV::getRelExpr(const RelType type, const Symbol &s,
   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:
-    // 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));
     return R_NONE;
   }
 }
 
 // Extract bits V[Begin:End], where range is inclusive, and Begin must be < 63.
void RISCV::relocate(uint8_t *loc, const Relocation &rel, uint64_t val) const {
   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());
+    }
+  }
+  // Store anchors (st_value and st_value+st_size) for symbols relatived to text
+  // sections.
+  for (InputFile *file : objectFiles)
+    for (Symbol *sym : file->getSymbols())
+      if (auto *d = dyn_cast<Defined>(sym))
+        if (auto *sec = dyn_cast_or_null<InputSection>(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 other displacements sufficiently to
+// become eligible for relaxation. Code shrinkage may increase displacement 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;
+    for (InputSection *sec : getInputSections(*osec)) {
+      auto &aux = *sec->relaxAux;
+      int32_t delta = 0;
+      for (auto &it : llvm::enumerate(sec->relocations)) {
+        const Relocation &r = it.value();
+        // r.offset is adjusted by delta as previous relocations may have
+        // removed content.
+        const uint64_t loc = sec->outSecOff + 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 needed_nops_bytes - nops_bytes.
+          delta += static_cast<int32_t>(((loc + align - 1) & -align) - nextLoc);
+          assert(delta <= 0 && "R_RISCV_ALIGN needs expanding the content");
+          break;
+        }
+        default:
+          // TODO: handle call/jump/load/store/addr-arithmetic relaxation
+          break;
+        }
+        if (delta != cur) {
+          cur = delta;
+          changed = true;
+        }
+      }
+    }
+  }
+  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<uint8_t> old = sec->rawData;
+      size_t newSize = old.size() + aux.relocDeltas.back();
+      uint8_t *p = context().bAlloc.Allocate<uint8_t>(newSize);
+      uint64_t offset = 0;
+      int32_t delta = 0;
+      sec->rawData = makeArrayRef(p, newSize);
+      for (size_t i = 0, e = sec->relocations.size(); i != e; ++i) {
+        int32_t inc = aux.relocDeltas[i] - delta;
+        delta = aux.relocDeltas[i];
+        if (inc == 0)
+          continue;
+        const Relocation &r = rels[i];
+        memcpy(p, old.data() + offset, r.offset - offset);
+        p += r.offset - offset;
+        offset = r.offset - inc;
+      }
+      memcpy(p, old.data() + offset, old.size() - offset);
+
+      // Decrease symbol values and relocation offsets.
+      size_t j = 0;
+      delta = 0;
+      for (SymbolAnchor &sa : aux.anchors) {
+        for (; j < rels.size() && rels[j].offset < sa.offset; ++j) {
+          rels[j].offset += delta;
+          delta = aux.relocDeltas[j];
+        }
+        if (sa.end)
+          sa.d->size = sa.offset + delta - sa.d->value;
+        else
+          sa.d->value += delta;
+      }
+      for (; j < rels.size(); ++j) {
+        rels[j].offset += delta;
+        delta = aux.relocDeltas[j];
+      }
+    }
+  }
+}
+
 TargetInfo *elf::getRISCVTargetInfo() {
   static RISCV target;
   return &target;
 }

lld/ELF/InputSection.h

 //===- InputSection.h -------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_INPUT_SECTION_H
 #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"
 #include "llvm/Object/ELF.h"
 
 namespace lld {
 namespace elf {
 
protected:
   constexpr SectionBase(Kind sectionKind, StringRef name, uint64_t flags,
                         uint32_t entsize, uint32_t alignment, uint32_t type,
                         uint32_t info, uint32_t link)
       : name(name), sectionKind(sectionKind), bss(false), keepUnique(false),
         alignment(alignment), flags(flags), entsize(entsize), type(type),
         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<SymbolAnchor, 0> anchors;
+  // For relocations[i], the actual offset is r_offset + relocDeltas[i-1].
+  SmallVector<int32_t, 0> relocDeltas;
+};
+
 // 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);
 
   InputSectionBase(InputFile *file, uint64_t flags, uint32_t type,
public:
   // and shrinking a section.
   uint8_t bytesDropped = 0;
 
   // Whether the section needs to be padded with a NOP filler due to
   // deleteFallThruJmpInsn.
   bool nopFiller = false;
 
   void drop_back(unsigned num) {
     assert(bytesDropped + num < 256);
     bytesDropped += num;
   }
 
   void push_back(uint64_t num) {
     assert(bytesDropped >= num);
     bytesDropped -= num;
   }
 
static uint64_t getRelocTargetVA(const InputFile *File, RelType Type,
                                    int64_t A, uint64_t P, const Symbol &Sym,
                                    RelExpr Expr);
 
   // The native ELF reloc data type is not very convenient to handle.
   // So we convert ELF reloc records to our own records in Relocations.cpp.
   // This vector contains such "cooked" relocations.
   SmallVector<Relocation, 0> relocations;
 
+  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
+    // 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
   // such functions and adjust their prologues.  This is very similar
   // to relocation. See https://gcc.gnu.org/wiki/SplitStacks for more
   // information.
   template <typename ELFT>
   void adjustSplitStackFunctionPrologues(uint8_t *buf, uint8_t *end);
 

lld/ELF/InputSection.cpp

uint64_t InputSectionBase::getRelocTargetVA(const InputFile *file, RelType type,
   case R_ABS:
   case R_DTPREL:
   case R_RELAX_TLS_LD_TO_LE_ABS:
   case R_RELAX_GOT_PC_NOPIC:
   case R_RISCV_ADD:
     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:
   case R_RELAX_TLS_GD_TO_IE_ABS:
     return sym.getGotVA() + a;
   case R_GOTONLY_PC:
     return in.got->getVA() + a - p;
   case R_GOTPLTONLY_PC:
for (size_t i = 0, size = relocations.size(); i != size; ++i) {
     if (auto *sec = dyn_cast<InputSection>(this))
       secAddr += sec->outSecOff;
     const uint64_t addrLoc = secAddr + offset;
     const uint64_t targetVA =
         SignExtend64(getRelocTargetVA(file, rel.type, rel.addend, addrLoc,
                                       *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);
       break;
     case R_AARCH64_GOT_PAGE_PC:
       if (i + 1 < size && aarch64relaxer.tryRelaxAdrpLdr(
                               rel, relocations[i + 1], secAddr, buf)) {
         ++i;

lld/ELF/Relocations.h

enum RelExpr {
   R_GOTPLT,
   R_GOTPLTREL,
   R_GOTREL,
   R_NONE,
   R_PC,
   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,
   R_RELAX_TLS_GD_TO_IE_ABS,
   R_RELAX_TLS_GD_TO_IE_GOT_OFF,
   R_RELAX_TLS_GD_TO_IE_GOTPLT,
   R_RELAX_TLS_GD_TO_LE,
   R_RELAX_TLS_GD_TO_LE_NEG,

lld/ELF/Relocations.cpp

 // will return true for such relocation.
 //
 // If this function returns false, that means we need to emit a
 // dynamic relocation so that the relocation will be fixed at load-time.
 bool RelocationScanner::isStaticLinkTimeConstant(RelExpr e, RelType type,
                                                  const Symbol &sym,
                                                  uint64_t relOff) const {
   // These expressions always compute a constant
-  if (oneof<R_GOTPLT, R_GOT_OFF, R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOTREL,
-            R_MIPS_GOT_OFF, R_MIPS_GOT_OFF32, R_MIPS_GOT_GP_PC,
+  if (oneof<R_GOTPLT, R_GOT_OFF, R_RELAX_HINT, R_MIPS_GOT_LOCAL_PAGE,
+            R_MIPS_GOTREL, R_MIPS_GOT_OFF, R_MIPS_GOT_OFF32, R_MIPS_GOT_GP_PC,
             R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTONLY_PC, R_GOTPLTONLY_PC,
             R_PLT_PC, R_PLT_GOTPLT, R_PPC32_PLTREL, R_PPC64_CALL_PLT,
             R_PPC64_RELAX_TOC, R_RISCV_ADD, R_AARCH64_GOT_PAGE>(e))
     return true;
 
   // These never do, except if the entire file is position dependent or if
   // only the low bits are used.
   if (e == R_GOT || e == R_PLT)

lld/ELF/Target.h

virtual bool inBranchRange(RelType type, uint64_t src,
                              uint64_t dst) const;
 
   virtual void relocate(uint8_t *loc, const Relocation &rel,
                         uint64_t val) const = 0;
   void relocateNoSym(uint8_t *loc, RelType type, uint64_t val) const {
     relocate(loc, Relocation{R_NONE, type, 0, 0, nullptr}, val);
   }
 
   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
   // the next section.  Further, if there is a conditional jump and a direct
   // jump consecutively, it tries to flip the conditional jump to convert the
   // direct jump into a fall thru and delete it.  Returns true if a jump
   // instruction can be deleted.
   virtual bool deleteFallThruJmpInsn(InputSection &is, InputFile *file,

lld/ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() {
   for (Partition &part : partitions)
     finalizeSynthetic(part.armExidx.get());
   resolveShfLinkOrder();
 
   // Converts call x@GDPLT to call __tls_get_addr
   if (config->emachine == EM_HEXAGON)
     hexagonTLSSymbolUpdate(outputSections);
 
+  target->relaxSections();
+
   int assignPasses = 0;
   for (;;) {
     bool changed = target->needsThunks && tc.createThunks(outputSections);
 
     // With Thunk Size much smaller than branch range we expect to
     // converge quickly; if we get to 15 something has gone wrong.
     if (changed && tc.pass >= 15) {
       error("thunk creation not converged");
       break;
     }
 
     if (config->fixCortexA53Errata843419) {
       if (changed)

lld/test/ELF/riscv-relax-align-rvc.s

+# 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: 00010000 g       .text  {{0*}}34 _start
+
+# CHECK:      <_start>:
+# CHECK-NEXT:           c.addi    a0, 1
+# CHECK-EMPTY:
+# CHECK-NEXT: <a>:
+# 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: <b>:
+# CHECK-NEXT:           c.addi  a0, 2
+# CHECK-EMPTY:
+# CHECK-NEXT: <c>:
+# CHECK-NEXT:           c.addi  a0, 3
+# CHECK-NEXT:           c.unimp
+# CHECK-NEXT:           addi    zero, zero, 0
+# CHECK-NEXT:           addi    zero, zero, 0
+# CHECK-NEXT:           c.nop
+# CHECK-NEXT:           c.addi  a0, 4
+# CHECK-NEXT:           c.addi  a0, 5
+# CHECK-NEXT:           c.unimp
+# CHECK-NEXT:           addi    zero, zero, 0
+# CHECK-NEXT:           addi    zero, zero, 0
+# CHECK-NEXT:           c.nop
+# CHECK-NEXT:           c.addi  a0, 6
+# CHECK-NEXT:           c.addi  a0, 7
+
+.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
+  c.addi a0, 4
+  c.addi a0, 5
+.balign 16
+.size c, . - c
+  c.addi a0, 6
+.size b, . - b
+  c.addi a0, 7
+.size _start, . - _start

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

+# 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
+
+# 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: <a>:
+# CHECK-NEXT:           addi    a0, a0, 2
+# CHECK-EMPTY:
+# CHECK-NEXT: <b>:
+# CHECK-NEXT:           addi    zero, zero, 0
+# CHECK-NEXT:           addi    zero, zero, 0
+# CHECK-NEXT:   10010:  addi    a0, a0, 3
+# CHECK-EMPTY:
+# CHECK-NEXT: <c>:
+# 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:      <e>:
+# CHECK-NEXT:           addi    a0, a0, 1
+# CHECK-EMPTY:
+# CHECK-NEXT: <f>:
+# 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
+
+.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:
+  addi a0, a0, 1
+f:
+  addi a0, a0, 2
+.balign 32
+.size d, . - d
+  addi a0, a0, 3
+.size e, . - e
+.size f, . - f
+
+.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)

lld/test/ELF/riscv-reloc-align.s

-# 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