[RISCV] Alignment relaxation

[gkm]

Summary

This is the first in a stack of diffs that repackages and revises D100835 for RISC-V linker relaxation.

This diff implements machinery to elide unwanted instruction bytes, and to rewrite NOP sequences that are optimal for code-alignment padding.

Caveat: this has not been tested with option --emit-relocs.

[arichardson]

lld/ELF/InputSection.cpp

198

Missing test coverage, you should add some symbols to your test cases.

lld/ELF/InputSection.h

258

Moving this after the other bool above should avoid the size change.

[gkm]

Revise according to review feedback:

• place new bool member adjacent to another bool to avoid size change of lld/ELF/InputSection.cpp
• add test case for symbol-size

[reames]

Minor style comments. Not really my area, so I can't really comment on how this fits within the existing structure.

lld/ELF/Arch/RISCV.cpp

498

the name nopBytes is slightly ambiguous here. Maybe requiredNopBytes? To distinguish it on first glance from the number available.

519

Extend this comment to indicate why this is required - i.e. split a 4 byte into a 2-byte remainder case + not wanting to assume the compiler emitted nops at all.

526

The rvc part of this check is redundant with the checks above. Maybe drop it from the else if clause, and turn it into an assert within the block?

lld/ELF/InputSection.cpp

179

This code seems to assume that ranges appear in order of increasing start address. I believe that is true in the code, but could easily be asserted more heavily to prevent future subtle mistakes.

183

You should probably assert that no range contains the symbol address.

lld/ELF/InputSection.h

154

Having variables defined between functions looks odd to my eye, but I see this already exists in the class. Maybe do a pre-nfc to group all the data together, and then add your new ones there?

[gkm]

• Revise according to review feedback
• Rewrite InputSectionBase::deleteRanges() to use a compact single pass that unifies handling of symbol addresses and sizes
• expand lld/test/ELF/riscv-relax-syms.s

[gkm]

lld/ELF/InputSection.cpp

179

The relaxation algorithm processes relocations by ascending address, and thus delete ranges are pushed to the vector by ascending address. I added an assertion.

179

[gkm]

Refactor ...

• s/DeleteRanges/AdjustRanges/: these can now handle deletion and insertion, supporting multiple-pass relaxation where alignment padding can expand, and/or relaxations can be undone
• Build framework for adding more relaxation types in later diffs
• Add comments

[gkm]

• Fix indentation caught by clang-format

[MaskRay]

Clone https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git , apply this patch:

--- i/arch/riscv/Makefile
+++ w/arch/riscv/Makefile
@@ -38,9 +38,9 @@ endif
 
 ifeq ($(CONFIG_LD_IS_LLD),y)
-       KBUILD_CFLAGS += -mno-relax
-       KBUILD_AFLAGS += -mno-relax
+       #KBUILD_CFLAGS += -mno-relax
+       #KBUILD_AFLAGS += -mno-relax
 ifndef CONFIG_AS_IS_LLVM
-       KBUILD_CFLAGS += -Wa,-mno-relax
-       KBUILD_AFLAGS += -Wa,-mno-relax
+       #KBUILD_CFLAGS += -Wa,-mno-relax
+       #KBUILD_AFLAGS += -Wa,-mno-relax
 endif
 endif

(My llvm build directory is /tmp/RelA)

ninja -C /tmp/RelA clang lld llvm-{nm,size,strings,objcopy,objdump,readelf,ar,strip}

cd ~/Dev/linux
PATH=/tmp/RelA/bin:$PATH make O=/tmp/linux/riscv64 ARCH=riscv CROSS_COMPILE=riscv64-linux-gnu- LLVM=1 -j60 defconfig all
...

I see a segfault

  LD      .tmp_vmlinux.kallsyms1
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: ld.lld -melf64lriscv --build-id=sha1 --script=./arch/riscv/kernel/vmlinux.lds --strip-debug -o .tmp_vmlinux.kallsyms1 --whole-archive arch/riscv/kernel/head.o init/built-in.a usr/built-in.a arch/riscv/built-in.a arch/riscv/errata/built-in.a kernel/built-in.a certs/built-in.a mm/built-in.a fs/built-in.a ipc/built-in.a security/built-in.a crypto/built-in.a block/built-in.a lib/built-in.a arch/riscv/lib/built-in.a lib/lib.a arch/riscv/lib/lib.a drivers/built-in.a sound/built-in.a net/built-in.a virt/built-in.a --no-whole-archive --start-group ./drivers/firmware/efi/libstub/lib.a --end-group
 #0 0x000056142291b4d3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/tmp/RelA/bin/lld+0x387c4d3)
 #1 0x000056142291940e llvm::sys::RunSignalHandlers() (/tmp/RelA/bin/lld+0x387a40e)
 #2 0x000056142291bada SignalHandler(int) Signals.cpp:0:0
 #3 0x00007f8197d53200 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12200)
 #4 0x0000561422a7ad01 void std::__introsort_loop<SymbolAddr*, long, __gnu_cxx::__ops::_Iter_comp_iter<lld::elf::InputSectionBase::adjustRanges(llvm::ArrayRef<lld::elf::InputSectionBase::AdjustRange>)::$_0>>(SymbolAddr*, SymbolAddr*, long, __gnu_cxx::__ops::_Iter_comp_iter<lld::elf::InputSectionBase::adjustRanges(llvm::ArrayRef<lld::elf::InputSectionBase::AdjustRange>)::$_0>) InputSection.cpp:0:0
 #5 0x0000561422a6d458 lld::elf::InputSectionBase::adjustRanges(llvm::ArrayRef<lld::elf::InputSectionBase::AdjustRange>) (/tmp/RelA/bin/lld+0x39ce458)
 #6 0x0000561422b61a7c (anonymous namespace)::RISCV::finalizeSections() const RISCV.cpp:0:0
 #7 0x0000561422ba4223 (anonymous namespace)::Writer<llvm::object::ELFType<(llvm::support::endianness)1, true>>::finalizeSections() Writer.cpp:0:0
 #8 0x0000561422b827dc void lld::elf::writeResult<llvm::object::ELFType<(llvm::support::endianness)1, true>>() (/tmp/RelA/bin/lld+0x3ae37dc)
 #9 0x00005614229f170f lld::elf::LinkerDriver::link(llvm::opt::InputArgList&) (/tmp/RelA/bin/lld+0x395270f)
#10 0x00005614229e3ab4 lld::elf::LinkerDriver::linkerMain(llvm::ArrayRef<char const*>) (/tmp/RelA/bin/lld+0x3944ab4)
#11 0x00005614229e242d lld::elf::link(llvm::ArrayRef<char const*>, llvm::raw_ostream&, llvm::raw_ostream&, bool, bool) (/tmp/RelA/bin/lld+0x394342d)
#12 0x000056142286f488 lldMain(int, char const**, llvm::raw_ostream&, llvm::raw_ostream&, bool) lld.cpp:0:0
#13 0x000056142286ec62 main (/tmp/RelA/bin/lld+0x37cfc62)
#14 0x00007f81975fa7fd __libc_start_main ./csu/../csu/libc-start.c:332:16
#15 0x000056142286e7aa _start (/tmp/RelA/bin/lld+0x37cf7aa)

lld/ELF/Arch/RISCV.cpp

476

Consider SmallVector<InputSectionBase::AdjustRange, 0>

488

constexpr

491

static

496

static

Actually, avoid defining such a short function.

501

avoid defining such a short function.

514

Newer code uses osec instead of os. os is usually for raw_ostream.

519

+2 needs a comment.

525

Add some const

548

550

Use

if (!(is->flags & SHF_EXECINSTR))
  continue;

to decrease indentation.

lld/ELF/InputSection.cpp

189

Use sym for Symbol *.

Avoid Symbol *b from some old code.

1099

Prefer moving R_RELAX_HINT to the switch below to not penalize other architectures. They don't want to take a comparison overhead here.

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

12

Avoid a temporary file for FIleCheck input.

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

40

Add a few more text sections to demonstrate that multiple sections can be handled.

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

3

Avoid -p if the directory is known to not exist. Use cd %t if you need to refer to %t/ many times.

5

##

18

CHECK-DAG:

30

Add a comment somewhere to explain what the notation [0..4) means.

[MaskRay]

lld/ELF/Arch/RISCV.cpp

508

A NOTE does not need a username.

lld/ELF/InputSection.h

154

The mutable can be avoided.

[gkm]

In D125036#3513877, @MaskRay wrote:

Clone https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git , apply this patch:

. . .

I see a segfault

Yes, I see it also. Will debug.
Meanwhile, I responded to other feedback and asked you some follow-up questions.
Thanks for reviewing!

lld/ELF/Arch/RISCV.cpp

496

What do you propose as an alternative? Open-code the shift?

501

What do you propose as an alternative? Open-code the bitwise ops? The idea is to abstract access to subfields of addend. Ideally, I could access alignNopBytes and alignBoundary as distinct struct members, but I am hijacking the existing Relocation interface that I can't change.

lld/ELF/InputSection.h

154

Say more. How?

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

12

I find that the temporary files are very useful for debugging tests. I can see the output of llvm-objdump without the effort of extracting the command from the log and running it manually.

Although I wish it were standard practice to retain temp files, I can revert back to a pipeline prior to pushing upstream.

[gkm]

• Revise according to review feedback

[gkm]

• Handle case R_RELAX_HINT in InputSectionBase::getRelocTargetVA()

[gkm]

lld/ELF/InputSection.cpp

1099

I am unconvinced:

1. The extra comparison overhead will be lost in the noise, though I will measure to be certain
2. Delaying R_RELAX_HINT means we run the block of code between here and the switch, which requires handling R_RELAX_HINT in InputSectionBase::getRelocTargetVA() to return a fake value 0.

[MaskRay]

lld/ELF/Arch/RISCV.cpp

496

Yes, open-code it.

501

Open code it since it's only called once. A comment is sufficient to express the intent.

lld/ELF/InputSection.cpp

1099

R_NONE is also not nice here. It would be better be placed in the switch cases but I haven't got time to refine the basic-block-section usage.

R_RELAX_HINT is risc-v specific. I don't want it to penalize other code. The cost is certainly small but every a little makes a mickle.

[gkm]

• Rework class SymbolAddr. The broken version's comparison function confused llvm::sort by returning true when given the same object for args a and b. This violates the API because comparisions should return a < b, which is false when a and b are the same object.

[gkm]

• open code the trivial getter/setter functions atop R_RISCV_ALIGN's Relocation::addend for align boundary & nop byte count.

[gkm]

LLD no longer crashes when linking Linux.

[MaskRay]

On lld/ELF/Relocations.cpp:1439, R_RELAX_HINT should not trigger sym.hasDirectReloc = true;, otherwise an ifunc may unnecessarily be converted to a canonical PLT. You may read *-ifunc-nonpreemptible*.s tests for what they do. I have some notes on https://maskray.me/blog/2021-01-18-gnu-indirect-function#address-significance

lld/ELF/Arch/RISCV.cpp

40

The name is unnecessarily the same as Writer::finalizeSections. relaxSections may be a better name.

488

520

522

emplace_back

573

The variable and the member function have the same name. Rename the variable to ranges?

Move it outside the outer loop and use a ranges.clear() here. Try avoiding constructing/destructing a vector in a loop.

576

r.addend is guaranteed to be non-zero

591

Don't perform relaxation for a relocatable link.

lld/ELF/InputSection.cpp

156

struct

188

If a file compiled with -ffunction-sections has N text sections/function symbols, this takes O(N^2). I think we should build a map to decrease the time complexity. You can add a map to InputFile. It's unfortunate to increase the size of InputFile which it is acceptable.

191

emplace_back

194

stable_sort

Two symbols may be defined at the same offset.

223

238

The condition isn't correct. It may trigger the undefined behavior src0 < dest+length < srcN.

---

We should avoid std::copy when

The behavior is undefined if d_first is within the range [first, last)

Otherwise we should use std::copy.

---

I am not sure the code works with adding bytes. In that case we need to get the NOP pattern.

lld/ELF/InputSection.h

170

Then remove mutable from copiedData

172

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

39

The test needs many .balign {8,16} directives to test InputSectionBase::adjustRanges.

The current InputSectionBase::adjustRanges is flawed but the tests aren't able to detect that.

[MaskRay]

lld/ELF/Arch/RISCV.cpp

582

This is inefficient. relaxOnce should call script->assignAddresses() at most once. The call should be moved just before return.

[MaskRay]

While I think there are still significant problems needing to address, it may work with quite a few application. It'd be nice if folks can check how this patch works without -mno-relax.

[gkm]

lld/ELF/Arch/RISCV.cpp

40

This is an override of target-independent virtual void TargetInfo::finalizeSections(), which is meant to be a generic hook for targets to do target-specific things. For RISC-V, that target-specific thing happens to be relaxation.

522

/scratch/llvm-project/lld/ELF/Arch/RISCV.cpp:523:18: error: no matching member function for call to 'emplace_back'
    adjustRanges.emplace_back({r.offset, incr});
    ~~~~~~~~~~~~~^~~~~~~~~~~~
/scratch/llvm-project/llvm/include/llvm/ADT/SmallVector.h:927:45: note: candidate template ignored: substitution failure: deduced incomplete pack <(no value)> for template parameter 'ArgTypes'
  template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
                        ~~~~~~~~            ^

The only way I have found to code this without complaint from clang is this:

AdjustRange range {r.offset, incr};
adjustRanges.push_back(range);

Godbolt reveals that the generated code is substantially the same at -O2 for push_back() and emplace_back().

591

The comment is redundant and provides no insight, so I removed it.

lld/ELF/InputSection.cpp

188

Adding a map to InputFile is unnecessary, especially for something specific to one target.

194

For this algorithm, retaining the original sequence for symbols at the same offset is irrelevant.

238

You are correct that the condition was wrong. This is an arch-independent loop that is responsible only for moving code that falls outside the adjust ranges. Arch-dependent code is responsible for filling contents of expanded adjust ranges. See fillAlignNops() in Arch/RISCV.cpp.

It is not yet possible to test expanding adjust ranges. The first pass of relaxOnce() will only shrink ranges. Only on a subsequent pass will we ever grow an alignment pad, or undo a call/jump/load/store/arithmetic relaxation. Alignment alone without other relaxations will always complete in one pass.

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

39

How many .balign directives do you think are necessary? I think the important case is where moved bytes overlap. Since ranges can only shrink in this diff, we can only test for src0 < dest+length < srcN, but not for src0 < dest < srcN.

Note that in libc++, the implementations of std::copy() and std::copy_backward() both call __builtin_memmove(), which is bidirectionally safe and works no matter how the regions overlap.

[gkm]

• revise according to review feedback

[luismarques]

In D125036#3526818, @MaskRay wrote:

While I think there are still significant problems needing to address, it may work with quite a few application. It'd be nice if folks can check how this patch works without -mno-relax.

My testing hasn't revealed any problems so far. I have looked at the code but I haven't yet evaluated it as carefully as I would like.

lld/ELF/Arch/RISCV.cpp

533–535

Please describe in the comment what you mean by a corrupted NOP sequence.

542

add static?

571–573

What expectations should we have about the convergence? Let's write some of that down. Either in this comment or in some place that provides a more global overview.

585

Nit: remove the user from the TODO.

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

11

Typo: "the after".

[gkm]

• revise according to review feedback

[gkm]

• restructure NOP-rewriter loop in fillAdjustGaps()

[gkm]

Expand comments before relaxOnce() and fillAdjustGaps()

[gkm]

• Cleanup & improve commentary in lld/test/ELF/riscv-relax-syms.s

[gkm]

• fix indentation, as caught by clang-format

[luismarques]

lld/ELF/Arch/RISCV.cpp

539–540

Sorry, where is this done?

lld/ELF/InputSection.cpp

178

This was changed but the tests didn't change. Sounds like an opportunity to improve test coverage?

[gkm]

lld/ELF/Arch/RISCV.cpp

539–540

I should modify the comment because it pertains to non-alignment relaxation types that are implemented in subsequent diffs.

571–573

I will elaborate on that in later diffs. Alignment alone finishes in one pass.

lld/ELF/InputSection.cpp

178

The change is an optimization, and does not alter behavior, so no new test is necessary. Before, I was doing unnecessary work to store symbol boundaries for non-executable sections which would never be relaxed.

[gkm]

• revise comments according to review feedback

[gkm]

• rework AlignAddend as a union

[MaskRay]

lld/ELF/Arch/RISCV.cpp

40

My point is that I don't think other ports will do similar things. Rename this to relaxSections to make debugging easier. We can rename to finalizeSections if there is ever a need.

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

40

Not done? As mentioned, this test only has 12-byte nops in one place. This is not strong enough to catch issues.
We need multiple .blign in this section and .blign in other text sections.

[MaskRay]

lld/ELF/Arch/RISCV.cpp

511

This accesses an inactive member of the union and is UB. https://en.cppreference.com/w/cpp/language/union
You can drop union, replace u64 with a member function which returns a uint64_t instead.

[MaskRay]

Using just one buffer with the copy_backward usage is unsafe.

Consider a case when all AdjustRange::delta values are positive (inflating), I feel that one iteration may overwrite some bytes which will be used later.

Currently the content move is done in InputSectionBase::adjustRanges MutableArrayRef<uint8_t> buf = this->mutableData();. So every relax iteration shuffles the content.
I think a better way is to do the shuffle only once, after the relaxation finishes.

lld/ELF/InputSection.cpp

166

185

stable_sort

199

Delete since the caller has checked emptiness.

211

The invariant on ranges is checked by symbolAddrs. Ranges after the end of symbolAddrs is not tested.
I'd remove all assert in the for loop.

if (i > 0)
  // An AdjustRange should not span a symbol start/end offset.
  assert(!ranges[i - 1].contains(sa.offset));

below is sufficient.

If there is a need to check

are all disjoint, i.e., do not overlap; and ...

Use a separate loop which calls fatal and do this after the ranges object is constructed.

236

247

Using just one buffer with the copy_backward usage is unsafe.

Consider a case when all AdjustRange::delta values are positive (inflating), I feel that one iteration may overwrite some bytes which will be used later.

[MaskRay]

I will try to rewrite R_RISCV_ALIGN, but I will probably not spend too much time on other relocation types (you can add them :) )

[MaskRay]

I feel uneasy with this patch series mainly for two things (a) intrusive changes to generic code (this could be fixed) (b) deleting bytes and undo seem hacky.
There is a minor issue that st_size computation is incorrect for the Linux kernel which can be fixed.
Another issue is with

while (relaxOnce(sectionSymbolAddrs))
   ;

being separate from the finalizeAddressDependentContent loop. Some linker scripts can cause the relax to be re-done. I think the only waterproof approach is to place relaxation into finalizeAddressDependentContent.

I created D127611/D127581 as an alternative implementation for alignment and call relaxation. It only performs "deleting bytes" after convergence.

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 finalizeSections() 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");
   }
 }
 
+using AdjustRanges = SmallVector<InputSectionBase::AdjustRange, 0>;
+
+// As input, the addend of R_RISCV_ALIGN holds the number of NOP bytes emitted
+// by the compiler. We derive the desired alignment boundary by rounding this up
+// to the nearest power of two. The multi-pass relaxation algorithm needs two
+// quantities per R_RISCV_ALIGN: current NOP byte count, and alignment
+// boundary. Once we alter the NOP byte count, we lose the capacity to correctly
+// derive the alignment boundary. Therefore, we must derive the boundary from
+// the initial value of NOP byte count and then store it. The 64-bit addend
+// member is more than wide enough to keep both the NOP byte count and alignment
+// boundary.
+
+constexpr int alignNopBytesWidth = 16;
+constexpr int alignNopBytesMask = ((1 << alignNopBytesWidth) - 1);
+
+static void setAlignBoundary(Relocation &r, unsigned n) {
+  assert((r.addend & ~alignNopBytesMask) == 0);
+  r.addend = (n << alignNopBytesWidth) | (r.addend & alignNopBytesMask);
+}
+
+static unsigned getAlignBoundary(Relocation &r) {
+  return r.addend >> alignNopBytesWidth;
+}
+
+static void setAlignNopBytes(Relocation &r, unsigned n) {
+  r.addend = (r.addend & ~alignNopBytesMask) | n;
+}
+
+static unsigned getAlignNopBytes(Relocation &r) {
+  return r.addend & alignNopBytesMask;
+}
+
+// NOTE: The code structure is more complex than necessary
+// for handling R_RISCV_ALIGN alone. It is designed to accommodate
+// call/jump/load/store/addr-arithmetic relocs in later diffs.
+
+// Derive & store alignment boundaries for all R_RISCV_ALIGN relocs
+static void setAlignBoundaries() {
+  for (OutputSection *osec : outputSections)
+    for (InputSection *isec : getInputSections(*osec))
+      if (isec->flags & SHF_EXECINSTR)
+        for (Relocation &r : isec->relocations)
+          if (r.type == R_RISCV_ALIGN)
+            setAlignBoundary(r, PowerOf2Ceil(r.addend + 2));
+}
+
+// Adjust the NOP byte count of one R_RISCV_ALIGN to maintain alignment
+static void relaxAlign(InputSection *isec, Relocation &r, int64_t &delta,
+                       AdjustRanges &adjustRanges) {
+  const uint64_t pc = isec->getVA(r.offset) + delta;
+  const uint64_t oldNopBytes = getAlignNopBytes(r);
+  const uint64_t newNopBytes = alignTo(pc, getAlignBoundary(r)) - pc;
+  const uint64_t minNopWidth = config->eflags & EF_RISCV_RVC ? 2 : 4;
+  if (newNopBytes % minNopWidth != 0) {
+    errorOrWarn(isec->getObjMsg(r.offset) + ": alignment NOP bytes " +
+                Twine(newNopBytes) + " must be a multiple of " +
+                Twine(minNopWidth));
+    return;
+  }
+
+  setAlignNopBytes(r, newNopBytes);
+  int incr = newNopBytes - oldNopBytes;
+  if (incr) {
+    adjustRanges.push_back({r.offset, incr});
+    delta += incr;
+  }
+}
+
+// After one or more contractions and/or expansions of the address range that
+// rounds-up to the alignment boundary, the sequence of NOPs emitted by the
+// compiler could be corrupted. Repair by rewriting an optimal sequence of NOPs.
+// When compressed (2-byte) instructions are disabled, the NOP sequence length
+// will be a multiple of 4, and all NOPs can use the 4-byte encoding. When
+// compressed instructions are enabled, the NOP sequence length will be a
+// multiple of 2, and we can mix 4-byte NOPs with 2-byte C.NOPs. In order to
+// reduce instruction count, we emit as many 4-byte NOPs as possible, then
+// if necessary, use a single 2-byte C.NOP to finish.
+void fillAlignNops() {
+  for (OutputSection *osec : outputSections)
+    for (InputSection *isec : getInputSections(*osec)) {
+      if (!(isec->flags & SHF_EXECINSTR))
+        continue;
+      for (Relocation &r : isec->relocations)
+        if (r.type == R_RISCV_ALIGN) {
+          uint8_t *buf = isec->mutableData().data() + r.offset;
+          int keepNopBytes = getAlignNopBytes(r);
+          while (keepNopBytes > 0) {
+            if (keepNopBytes >= 4) {
+              write32le(buf, 0x00000013); // nop
+              keepNopBytes -= 4;
+              buf += 4;
+            } else if (keepNopBytes == 2) {
+              assert(config->eflags & EF_RISCV_RVC &&
+                     "expected RVC for 2-byte NOP");
+              write16le(buf, 0x0001); // c.nop
+              keepNopBytes -= 2;
+              buf += 2;
+            }
+          }
+          assert(keepNopBytes == 0);
+        }
+    }
+}
+
+// Execute a single relaxation pass. Return TRUE if we did something.  The
+// caller will repeatedly call this until the algorithm converges, as indicated
+// by a pass where nothing happens.
+static bool relaxOnce() {
+  bool changed = false;
+  for (OutputSection *osec : outputSections) {
+    for (InputSection *isec : getInputSections(*osec)) {
+      if (!(isec->flags & SHF_EXECINSTR))
+        continue;
+
+      AdjustRanges adjustRanges;
+      int64_t delta = 0;
+      for (Relocation &r : isec->relocations)
+        if (r.type == R_RISCV_ALIGN && r.addend)
+          relaxAlign(isec, r, delta, adjustRanges);
+
+      // TODO(gkm): handle call/jump/load/store/addr-arithmetic relocs here
+
+      if (isec->adjustRanges(adjustRanges)) {
+        script->assignAddresses();
+        changed = true;
+      }
+    }
+  }
+  return changed;
+}
+
+void RISCV::finalizeSections() const {
+  // Can't perform relaxation if it is not a final link.
+  if (config->relocatable)
+    return;
+
+  setAlignBoundaries();
+  while (relaxOnce())
+    ;
+  fillAlignNops();
+}
+
 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 {
 
void drop_back(unsigned num) {
     bytesDropped += num;
   }
 
   void push_back(uint64_t num) {
     assert(bytesDropped >= num);
     bytesDropped -= num;
   }
 
+  mutable bool copiedData = false;
   mutable ArrayRef<uint8_t> rawData;
 
   void trim() {
     if (bytesDropped) {
       rawData = rawData.drop_back(bytesDropped);
       bytesDropped = 0;
     }
   }
 
   ArrayRef<uint8_t> data() const {
     if (uncompressedSize >= 0)
       uncompress();
     return rawData;
   }
 
+  MutableArrayRef<uint8_t> mutableData() const {
+    if (!copiedData) {
+      size_t size = data().size();
+      uint8_t *mutData = context().bAlloc.Allocate<uint8_t>(size);
+      memcpy(mutData, data().data(), size);
+      rawData = llvm::makeArrayRef(mutData, size);
+      copiedData = true;
+    }
+
+    return llvm::makeMutableArrayRef(const_cast<uint8_t *>(rawData.data()),
+                                     rawData.size());
+  }
+
+  // Add or delete DELTA bytes. Positive (expand) DELTA pertains to
+  // R_RELAX_ALIGN during multi-pass relaxation. The first relaxation pass will
+  // always delete excess NOPs generated by the compiler, but subsequent
+  // relaxation passes might require expansion of NOP padding in order to
+  // round-up to the alignment boundary.
+  class AdjustRange {
+  public:
+    uint64_t offset;
+    int64_t delta;
+    bool contains(uint64_t a) const { return offset < a && a < offset - delta; }
+  };
+
+  // Adjust (delete or expand) a range of input-section content, symbols, and
+  // relocations.  The adjustRanges must be sorted by offset and must not
+  // overlap.
+  bool adjustRanges(ArrayRef<AdjustRange> adjustRanges);
+
   // The next member in the section group if this section is in a group. This is
   // used by --gc-sections.
   InputSectionBase *nextInSectionGroup = nullptr;
 
   template <class ELFT> RelsOrRelas<ELFT> relsOrRelas() const;
 
   // InputSections that are dependent on us (reverse dependency for GC)
   llvm::TinyPtrVector<InputSection *> dependentSections;
public:
 
 
   template <typename T> llvm::ArrayRef<T> getDataAs() const {
     size_t s = rawData.size();
     assert(s % sizeof(T) == 0);
     return llvm::makeArrayRef<T>((const T *)rawData.data(), s / sizeof(T));
   }
 
 protected:
   template <typename ELFT>
   void parseCompressedHeader();
   void uncompress() const;
 
   // This field stores the uncompressed size of the compressed data in rawData,
   // or -1 if rawData is not compressed (either because the section wasn't
   // compressed in the first place, or because we ended up uncompressing it).
   // Since the feature is not used often, this is usually -1.

lld/ELF/InputSection.cpp

if (shdr.sh_type == SHT_REL) {
     assert(shdr.sh_type == SHT_RELA);
     ret.relas = makeArrayRef(reinterpret_cast<const typename ELFT::Rela *>(
                                  file->mb.getBufferStart() + shdr.sh_offset),
                              shdr.sh_size / sizeof(typename ELFT::Rela));
   }
   return ret;
 }
 
+// Wrap a defined symbol with two of these, allowing uniform access to its start
+// and end offsets, supporting a unified vector of symbol starts and ends which
+// we can inspect and adjust individually.
+class SymbolAddr {
+public:
+  uint64_t offset;
+  Defined *d;
+
+  void bump(int64_t delta) {
+    if (offset == d->value) { // symbol-start
+      // Extend size as much as we reduce value, thereby preserving original
+      // value+size. We will fix size later when we bump symbol-end.
+      d->value += delta;
+      d->size -= delta;
+    } else { // symbol-end
+      d->size += delta;
+    }
+  }
+};
+
+// The relaxation pass queued a vector of adjustments for this input
+// section. Most often these remove excess bytes from shortened instructions for
+// calls/jumps/loads/stores/address-arithmentic/alignments. Sometimes, these add
+// bytes for alignments and undoing relaxations. We process everything in
+// ascending address order, adjusting section contents, reloc offsets, symbol
+// values, and function-symbol sizes. Function symbol sizes must be adjusted
+// when code size changes within the function.
+bool InputSectionBase::adjustRanges(ArrayRef<AdjustRange> ranges) {
+  if (ranges.empty())
+    return false;
+
+  // Make a unified vector of start & end offsets for all defined symbols within
+  // this section. Each symbol gets two entries in the vector, distinguished by
+  // the `isStart` member.
+  SmallVector<SymbolAddr, 0> symbolAddrs;
+  for (Symbol *sym : file->getSymbols())
+    if (Defined *d = dyn_cast<Defined>(sym))
+      if (d->section == this) {
+        symbolAddrs.push_back({d->value, d});
+        symbolAddrs.push_back({d->value + d->size, d});
+      }
+  llvm::sort(symbolAddrs, [](const SymbolAddr &a, const SymbolAddr &b) {
+    return a.offset < b.offset;
+  });
+
+  // Adjust symbol offsets and sizes.
+  int64_t delta = 0;
+  size_t i = 0;
+  for (SymbolAddr &sa : symbolAddrs) {
+    // The assertions below check that AdjustRanges ...
+    // (a) are all disjoint, i.e., do not overlap; and ...
+    // (b) do not have symbol boundaries within their interior, i.e., an
+    //     AdjustRange is entirely inside or entirely outside a symbol's range.
+    for (; i < ranges.size() && ranges[i].offset < sa.offset; i++) {
+      // An AdjustRange should not span a symbol start/end offset
+      assert(!ranges[i].contains(sa.offset));
+      if (i > 0)
+        // AdjustRanges should increase monotonically and never overlap.
+        assert(!ranges[i - 1].contains(ranges[i].offset));
+      delta += ranges[i].delta;
+    }
+    if (i > 0)
+      // An AdjustRange should not span a symbol start/end offset.
+      assert(!ranges[i - 1].contains(sa.offset));
+    sa.bump(delta);
+  }
+
+  // Adjust relocation offsets within the section.
+  delta = 0;
+  const auto *ar = ranges.begin();
+  for (auto &r : relocations) {
+    for (; ar != ranges.end() && ar->offset < r.offset; ++ar)
+      delta += ar->delta;
+    r.offset += delta;
+  }
+
+  // Remove or add bytes to the section piece-wise.
+  MutableArrayRef<uint8_t> buf = this->mutableData();
+  auto *dest = buf.begin() + ranges.begin()->offset;
+  for (size_t i = 0; i < ranges.size(); i++) {
+    const AdjustRange &ar = ranges[i];
+    auto *src0 = buf.begin() + ar.offset - ar.delta;
+    auto *srcN = (i + 1 < ranges.size()) ? (buf.begin() + ranges[i + 1].offset)
+                                         : buf.end();
+    size_t length = srcN - src0;
+    if (dest < src0)
+      std::copy_backward(src0, srcN, dest + length);
+    else
+      std::copy(src0, srcN, dest);
+    dest += length;
+  }
+
+  // Resize the section contents.
+  rawData = makeArrayRef(data().data(), dest);
+  return true;
+}
+
 uint64_t SectionBase::getOffset(uint64_t offset) const {
   switch (kind()) {
   case Output: {
     auto *os = cast<OutputSection>(this);
     // For output sections we treat offset -1 as the end of the section.
     return offset == uint64_t(-1) ? os->size : offset;
   }
   case Regular:
uint64_t InputSectionBase::getRelocTargetVA(const InputFile *file, RelType type,
   case R_TLSGD_PC:
     return in.got->getGlobalDynAddr(sym) + a - p;
   case R_TLSLD_GOTPLT:
     return in.got->getVA() + in.got->getTlsIndexOff() + a - in.gotPlt->getVA();
   case R_TLSLD_GOT:
     return in.got->getTlsIndexOff() + a;
   case R_TLSLD_PC:
     return in.got->getTlsIndexVA() + a - p;
+  case R_RELAX_HINT:
+    return 0;
   default:
     llvm_unreachable("invalid expression");
   }
 }
 
 // This function applies relocations to sections without SHF_ALLOC bit.
 // Such sections are never mapped to memory at runtime. Debug sections are
 // an example. Relocations in non-alloc sections are much easier to

 void InputSectionBase::relocateAlloc(uint8_t *buf, uint8_t *bufEnd) {
   assert(flags & SHF_ALLOC);
   const unsigned bits = config->wordsize * 8;
   const TargetInfo &target = *elf::target;
   uint64_t lastPPCRelaxedRelocOff = UINT64_C(-1);
   AArch64Relaxer aarch64relaxer(relocations);
   for (size_t i = 0, size = relocations.size(); i != size; ++i) {
     const Relocation &rel = relocations[i];
     if (rel.expr == R_NONE)
       continue;
     uint64_t offset = rel.offset;
     uint8_t *bufLoc = buf + offset;
 
     uint64_t secAddr = getOutputSection()->addr;
     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

 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,
             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))
+            R_PPC64_RELAX_TOC, R_RISCV_ADD, R_RELAX_HINT, 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)
     return target.usesOnlyLowPageBits(type) || !config->isPic;
 
   if (sym.isPreemptible)

lld/ELF/Target.h

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 finalizeSections() 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->finalizeSections();
+
   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");

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-unknown-elf -mattr=+c,+relax %s -o rv32.o
+# RUN: llvm-mc -filetype=obj -triple=riscv64-unknown-elf -mattr=+c,+relax %s -o rv64.o
+
+# Check that alignment is always handled, regardless of --relax option
+
+# RUN: ld.lld rv32.o -o relax.rv32
+# RUN: ld.lld rv64.o -o relax.rv64
+# RUN: llvm-objdump -d -M no-aliases relax.rv32 > relax.rv32.dis
+# RUN: llvm-objdump -d -M no-aliases relax.rv64 > relax.rv64.dis
+# RUN: FileCheck %s < relax.rv32.dis
+# RUN: FileCheck %s < relax.rv64.dis
+
+# RUN: ld.lld --no-relax rv32.o -o no-relax.rv32
+# RUN: ld.lld --no-relax rv64.o -o no-relax.rv64
+# RUN: llvm-objdump -d -M no-aliases no-relax.rv32 > no-relax.rv32.dis
+# RUN: llvm-objdump -d -M no-aliases no-relax.rv64 > no-relax.rv64.dis
+# RUN: FileCheck %s < no-relax.rv32.dis
+# RUN: FileCheck %s < no-relax.rv64.dis
+
+# CHECK:      c.add   a0, a1
+# CHECK-NEXT: addi    zero, zero, 0
+# CHECK-NEXT: addi    zero, zero, 0
+# CHECK-NEXT: addi    zero, zero, 0
+# CHECK-NEXT: c.nop
+# CHECK-NEXT: c.add   s0, s1
+# CHECK-NEXT: c.add   s2, s3
+# CHECK-NEXT: c.add   s4, s5
+# CHECK-NEXT: c.nop
+# CHECK-NEXT: c.add   t0, t1
+
+.global _start
+_start:
+.balign 4
+  c.add a0, a1
+.balign 16
+  c.add s0, s1
+  c.add s2, s3
+  c.add s4, s5
+.balign 8
+  c.add t0, t1

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

+# REQUIRES: riscv
+# RUN: rm -rf %t && mkdir %t && cd %t
+
+# RUN: llvm-mc -filetype=obj -triple=riscv32-unknown-elf -mattr=+relax %s -o rv32.o
+# RUN: llvm-mc -filetype=obj -triple=riscv64-unknown-elf -mattr=+relax %s -o rv64.o
+
+# Check that alignment is always handled regardless of --relax option
+
+# RUN: ld.lld rv32.o -o relax.rv32
+# RUN: ld.lld rv64.o -o relax.rv64
+# RUN: llvm-objdump -d -M no-aliases relax.rv32 > relax.rv32.dis
+# RUN: llvm-objdump -d -M no-aliases relax.rv64 > relax.rv64.dis
+# RUN: FileCheck %s < relax.rv32.dis
+# RUN: FileCheck %s < relax.rv64.dis
+
+# RUN: ld.lld --no-relax rv32.o -o no-relax.rv32
+# RUN: ld.lld --no-relax rv64.o -o no-relax.rv64
+# RUN: llvm-objdump -d -M no-aliases no-relax.rv32 > no-relax.rv32.dis
+# RUN: llvm-objdump -d -M no-aliases no-relax.rv64 > no-relax.rv64.dis
+# RUN: FileCheck %s < no-relax.rv32.dis
+# RUN: FileCheck %s < no-relax.rv64.dis
+
+# CHECK:      add     a0, a1, a2
+# CHECK-NEXT: add     a3, a4, a5
+# CHECK-NEXT: addi    zero, zero, 0
+# CHECK-NEXT: addi    zero, zero, 0
+# CHECK-NEXT: add     s0, s1, s2
+# CHECK-NEXT: add     t0, t1, t2
+
+.global _start
+_start:
+.balign 4
+  add a0, a1, a2
+  add a3, a4, a5
+.balign 16
+  add s0, s1, s2
+.balign 4
+.balign 4
+  add t0, t1, t2

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

+# REQUIRES: riscv
+# RUN: rm -rf %t && mkdir %t && cd %t
+
+## Check that relaxation correctly adjusts symbol addresses and sizes.
+
+# RUN: llvm-mc -filetype=obj -triple=riscv32-unknown-elf %s -o rv32.o
+# RUN: llvm-mc -filetype=obj -triple=riscv64-unknown-elf %s -o rv64.o
+# RUN: ld.lld -Ttext=0x100000 rv32.o -o rv32
+# RUN: ld.lld -Ttext=0x100000 rv64.o -o rv64
+
+# RUN: llvm-readelf -s rv32 > rv32.dis
+# RUN: llvm-readelf -s rv64 > rv64.dis
+# RUN: FileCheck %s < rv32.dis
+# RUN: FileCheck %s < rv64.dis
+
+# CHECK-DAG: 100000     4 NOTYPE  LOCAL  DEFAULT     1 a
+# CHECK-DAG: 100000    12 NOTYPE  LOCAL  DEFAULT     1 b
+# CHECK-DAG: 100004     8 NOTYPE  LOCAL  DEFAULT     1 c
+# CHECK-DAG: 100008    12 NOTYPE  LOCAL  DEFAULT     1 d
+# CHECK-DAG: 10000c     8 NOTYPE  LOCAL  DEFAULT     1 e
+# CHECK-DAG: 100010     4 NOTYPE  LOCAL  DEFAULT     1 f
+# CHECK-DAG: 100000    20 NOTYPE  GLOBAL DEFAULT     1 _start
+
+.global _start
+.balign 4
+_start:                         # 0
+a:
+b:
+    add  a0, a1, a2             # [0..4) = the semi-open interval 0,1,2,3
+.size a, .-a                    # 4
+c:
+    add s0, s1, s2              # [4..8)
+d:
+    add t0, t1, t2              # [8..12)
+.size b, .-b                    # 12
+.size c, .-c
+e:
+.balign 16
+f:                             # 16
+    add x0, x1, x2             # [16..20)
+.size d, .-d                   # 20
+.size e, .-e                   # 20
+.size f, .-f                   # 20
+.size _start, .-_start

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