[JITLink][RISCV] Implement linker relaxation

[jobnoorman]

Summary

This patch is essentially an adaption of LLD's algorithm to JITLink.
Currently, only relaxing R_RISCV_CALL(_PLT) and R_RISCV_ALIGN is
implemented, other relocations can follow later.

From a high level, the algorithm works as follows. In the first phase
(relaxBlock), we iteratively try to relax all instructions that have a
R_RISCV_RELAX relocation:

• If, based on the current symbol values, an instruction sequence can be relaxed (i.e., replaced by a shorter instruction), we record how many bytes would be removed, the new instruction (Writes), and the new relocation type (EdgeKinds).
• We keep track of the total number of bytes that got removed up to each relocation in the RelocDeltas array. This is the cumulative sum of the number of bytes removed for each relocation.
• Symbol values and sizes are updated based on the number of removed bytes.
• If for any relocation, the current RelocDeltas value doesn't match the one from the previous iteration, something changed and we need to run another iteration as some symbols might now have different values.

In the second phase (finalizeBlockRelax), all code is moved based on
RelocDeltas, the relaxed instructions are rewritten using Writes, and
R_RISCV_ALIGN is handled (moving instructions to ensure alignment and
inserting the correct NOP-sequence if needed). Finally, edge kinds and
offsets are updated and all R_RISCV_RELAX and R_RISCV_ALIGN edges are
removed (they are not needed anymore for the fixup linking stage).

Linker relaxation is implemented as a pass and added to PreFixupPasses
in the default configuration on RISC-V.

Since linker relaxation removes instructions, the memory for blocks
should ideally be reallocated. However, I believe this is currently not
possible in JITLink. Therefore, relaxation directly modifies the memory
of blocks, reducing the number of instructions but not the size of
blocks. I'm not very familiar with JITLink's memory allocators so I
might be overlooking something here, though.

Note on testing: some of the tests rely on the debug output of
llvm-jitlink. The main reason for this is the verification of symbol
sizes (which may change due to relaxation). I don't believe this can be
done using jitlink-check checks alone.

Note that there is a slightly unrelated change that makes
Symbol::setOffset public to be able to update symbol offsets during
relaxation. I felt this change didn't warrant a separate patch but I can
split it off if necessary.

@MaskRay: I've added you as a reviewer since you're the original author
of the LLD algorithm. The algorithm in this patch is mostly the same as
yours but I made some minor modifications. The main one is that I got
rid of the valueDelta map you use in relax() to keep track of of the
deltas of symbols in the previous iteration in order to correctly update
symbol values. I believe this is unnecessary and the same can be
accomplished by using the original symbol value stored in offset field
in its anchor. When making the same change in LLD, all tests still pass.

Depends on D149522 and D149523 and D149525 and D149541

[jobnoorman]

Rebase on new dependency.

[tschuett]

It took me a moment to find where the new code is actually used.

You go a bit to far with the anonymous namespace:
https://llvm.org/docs/CodingStandards.html#anonymous-namespaces

[Hahnfeld]

llvm/include/llvm/ExecutionEngine/JITLink/riscv.h

205–211

Please keep this sorted based on the enum values (see comment at the top)

llvm/lib/ExecutionEngine/JITLink/ELF_riscv.cpp

523

Should this error more gracefully than asserting, also in Release builds?

589–592

I'm probably missing something here: Why is this only possible in RV32?

823–826

same here, please keep this sorted

llvm/lib/ExecutionEngine/JITLink/riscv.cpp

81–84

same

[jrtc27]

llvm/lib/ExecutionEngine/JITLink/ELF_riscv.cpp

589–592

C.JAL’s encoding means something else for RV64 (I think C.ADDIW but don’t remember for sure)

[jobnoorman]

Only use anonymous namespace for classes, make functions static.

[jobnoorman]

llvm/include/llvm/ExecutionEngine/JITLink/riscv.h

205–211

These edge kinds will be removed in the next version of this patch.

llvm/lib/ExecutionEngine/JITLink/ELF_riscv.cpp

523

It should indeed.

I'm going to make a small modification to the implementation based on a comment in another review:

In D149524#4308261, @lhames wrote:

For R_RISCV_RELAX we should add relaxable edge kinds to the RISCV edge kinds enum (along the same lines as the x86-64 relaxable edges, and we should take this opportunity to rename the RISCV edges to bring them in line with the other architectures). When the ELF/RISCV LinkGraphBuilder sees an R_RISCV_RELAX relocation it should choose the relaxable variant for the corresponding edge.

This will also move the detection of this kind of error to a different location so I will implement your suggestion there.

[jobnoorman]

Implement the following suggestion:

In D149524#4308261, @lhames wrote:

For R_RISCV_RELAX we should add relaxable edge kinds to the RISCV edge kinds enum (along the same lines as the x86-64 relaxable edges, and we should take this opportunity to rename the RISCV edges to bring them in line with the other architectures). When the ELF/RISCV LinkGraphBuilder sees an R_RISCV_RELAX relocation it should choose the relaxable variant for the corresponding edge.

The new edge kinds are called CallRelaxable and AlignRelaxable.

Note that I think we should do the renaming of other edges in a different patch.

[MaskRay]

@MaskRay: I've added you as a reviewer since you're the original author of the LLD algorithm. The algorithm in this patch is mostly the same as yours but I made some minor modifications. The main one is that I got rid of the valueDelta map you use in relax() to keep track of of the deltas of symbols in the previous iteration in order to correctly update symbol values. I believe this is unnecessary and the same can be accomplished by using the original symbol value stored in offset field in its anchor. When making the same change in LLD, all tests still pass.

See 6b1d151fe3dc530195d8802f1ecc247c8235dd3a for lld/ELF/Arch/RISCV.cpp:valueDelta.
lld/test/ELF/riscv-relax-call-intra-sec.s (use ninja check-lld-elf) will fail if you reset a symbol value to the original value.

[jobnoorman]

In D149526#4313436, @MaskRay wrote:

@MaskRay: I've added you as a reviewer since you're the original author of the LLD algorithm. The algorithm in this patch is mostly the same as yours but I made some minor modifications. The main one is that I got rid of the valueDelta map you use in relax() to keep track of of the deltas of symbols in the previous iteration in order to correctly update symbol values. I believe this is unnecessary and the same can be accomplished by using the original symbol value stored in offset field in its anchor. When making the same change in LLD, all tests still pass.

See 6b1d151fe3dc530195d8802f1ecc247c8235dd3a for lld/ELF/Arch/RISCV.cpp:valueDelta.
lld/test/ELF/riscv-relax-call-intra-sec.s (use ninja check-lld-elf) will fail if you reset a symbol value to the original value.

I don't reset symbol values to their original but I use the original value to simply the calculation. I've opened D149735 to try to explain this a bit better :)

[MaskRay]

In D149526#4314992, @jobnoorman wrote:

In D149526#4313436, @MaskRay wrote:

@MaskRay: I've added you as a reviewer since you're the original author of the LLD algorithm. The algorithm in this patch is mostly the same as yours but I made some minor modifications. The main one is that I got rid of the valueDelta map you use in relax() to keep track of of the deltas of symbols in the previous iteration in order to correctly update symbol values. I believe this is unnecessary and the same can be accomplished by using the original symbol value stored in offset field in its anchor. When making the same change in LLD, all tests still pass.

See 6b1d151fe3dc530195d8802f1ecc247c8235dd3a for lld/ELF/Arch/RISCV.cpp:valueDelta.
lld/test/ELF/riscv-relax-call-intra-sec.s (use ninja check-lld-elf) will fail if you reset a symbol value to the original value.

I don't reset symbol values to their original but I use the original value to simply the calculation. I've opened D149735 to try to explain this a bit better :)

Thanks. I think D149735 is good.

[lhames]

I believe that this is blocked by the subtarget features patch, but otherwise LGTM.

llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h

645–648

This could be moved to just below Symbol::getOffset to improve readability.

All defined symbols have blocks, so you could change the assert to:

assert(NewOffset < getBlock().getSize() && "Offset out of range");

to get a stricter bounds check.

[jobnoorman]

• Move setOffset() to a better location;
• Add stricter bounds check in setOffset().

[jobnoorman]

In D149526#4328661, @lhames wrote:

I believe that this is blocked by the subtarget features patch, but otherwise LGTM.

Thanks for the review @lhames!

Note that besides that patch, this is also still blocked by D149523 (for testing).

[jobnoorman]

Rebase on update of D149522.

[Hahnfeld]

Hi @jobnoorman, unfortunately this doesn't seem to work for me in practice with the whole machinery of LLJIT, launching even the most basic program via lli -mattr=+relax:

define i32 @main() {
  ret i32 0
}

results in:

JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.run_atexits_helper" at address 0x2ae0d3969e is out of range of R_RISCV_CALL_PLT fixup at 0x3f8e8ac018 (__lljit_run_atexits, 0x3f8e8ac000 + 0x18)
JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.run_atexits_helper" at address 0x2ae0d3969e is out of range of R_RISCV_CALL_PLT fixup at 0x3f8e8ac018 (__lljit_run_atexits, 0x3f8e8ac000 + 0x18)
./install/bin/lli: Failed to materialize symbols: { (<Platform>, { __dso_handle, atexit, __lljit_run_atexits }) }
Failed to materialize symbols: { (main, { __dso_handle, atexit, __lljit_run_atexits }) }

Could this have to do with copying the buffer? Could you take a look?

[jobnoorman]

Thanks for reporting this, @Hahnfeld. Was this working before? I don't seem to be able to run your test file even without relaxation enabled. I'm getting slightly different errors though:

$ lli -jit-linker=jitlink test.ll
JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.platform_support_instance" at address 0x40054e0cd0 is out of range of R_RISCV_HI20 fixup at 0x4008266008 (__lljit_run_atexits, 0x4008266000 + 0x8)
JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.platform_support_instance" at address 0x40054e0cd0 is out of range of R_RISCV_HI20 fixup at 0x4008268008 (__lljit_run_atexits, 0x4008268000 + 0x8)
./lli: Failed to materialize symbols: { (<Platform>, { __lljit_run_atexits, atexit, __dso_handle }) }
Failed to materialize symbols: { (main, { __lljit_run_atexits, atexit, __dso_handle }) }

[jobnoorman]

@Hahnfeld: the issue seems to be that by default, non-PIC code is generated. Adding --relocation-model=pic to the lli command line solves the issue for me.

[Hahnfeld]

In D149526#4353336, @jobnoorman wrote:

Thanks for reporting this, @Hahnfeld. Was this working before?

Yes, it was working before, and still is working for me without -mattr=+relax.

$ lli -jit-linker=jitlink test.ll
JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.platform_support_instance" at address 0x40054e0cd0 is out of range of R_RISCV_HI20 fixup at 0x4008266008 (__lljit_run_atexits, 0x4008266000 + 0x8)
JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.platform_support_instance" at address 0x40054e0cd0 is out of range of R_RISCV_HI20 fixup at 0x4008268008 (__lljit_run_atexits, 0x4008268000 + 0x8)
./lli: Failed to materialize symbols: { (<Platform>, { __lljit_run_atexits, atexit, __dso_handle }) }
Failed to materialize symbols: { (main, { __lljit_run_atexits, atexit, __dso_handle }) }

In D149526#4353688, @jobnoorman wrote:

@Hahnfeld: the issue seems to be that by default, non-PIC code is generated. Adding --relocation-model=pic to the lli command line solves the issue for me.

This is because you're explicitly specifying -jit-linker=jitlink, then it doesn't default to PIC. If you don't specify anything, you'll still get JITLink (there is nothing else for RISC-V) and PIC by default. Then the test case works without linker relaxation, but you should see the error I posted above with -mattr=+relax.

[jobnoorman]

Thanks for the explanation! I'll look into this more tomorrow but I just wanted to mention now that it does work for me, with and without relaxation.

[jobnoorman]

I managed to reproduce this on qemu-system (was using qemu-user before and the addresses just happened to be close enough together to fit R_RISCV_CALL_PLT there).

Should be fixed by D150957.

Thanks again for reporting this @Hahnfeld!

llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h

public:
 
   /// Set the WeaklyReferenced value for this symbol.
   /// This method may only be called on external symbols.
   void setWeaklyReferenced(bool WeakRef) {
     assert(isExternal() && "setWeaklyReferenced called on non-external");
     this->WeakRef = WeakRef;
   }
 
+  void setOffset(orc::ExecutorAddrDiff NewOffset) {
+    assert(NewOffset <= MaxOffset && "Offset out of range");
+    Offset = NewOffset;
+  }
+
 private:
   void makeExternal(Addressable &A) {
     assert(!A.isDefined() && !A.isAbsolute() &&
            "Attempting to make external with defined or absolute block");
     Base = &A;
     Offset = 0;
     setScope(Scope::Default);
     IsLive = 0;
     // note: Size, Linkage and IsCallable fields left unchanged.
   }
 
   void makeAbsolute(Addressable &A) {
     assert(!A.isDefined() && A.isAbsolute() &&
            "Attempting to make absolute with defined or external block");
     Base = &A;
     Offset = 0;
   }
 
   void setBlock(Block &B) { Base = &B; }
 
-  void setOffset(orc::ExecutorAddrDiff NewOffset) {
-    assert(NewOffset <= MaxOffset && "Offset out of range");
-    Offset = NewOffset;
-  }
-
   static constexpr uint64_t MaxOffset = (1ULL << 59) - 1;
 
   // FIXME: A char* or SymbolStringPtr may pack better.
   StringRef Name;
   Addressable *Base = nullptr;
   uint64_t Offset : 57;
   uint64_t L : 1;
   uint64_t S : 2;

llvm/include/llvm/ExecutionEngine/JITLink/riscv.h

enum EdgeKind_riscv : Edge::Kind {
   ///   Fixup <- (Target + Addend)
   R_RISCV_SET32,
 
   /// 32 bits PC relative relocation
   ///
   /// Fixup expression:
   ///   Fixup <- (Target - Fixup + Addend)
   R_RISCV_32_PCREL,
+
+  /// Marks another relocation at the same offset as eligible for linker
+  /// relaxation.
+  R_RISCV_RELAX,
+
+  /// Encodes alignment requirement of the instruction at Fixup + Addend
+  R_RISCV_ALIGN,
 };
 
 /// Returns a string name for the given riscv edge. For debugging purposes
 /// only
 const char *getEdgeKindName(Edge::Kind K);
 } // namespace riscv
 } // namespace jitlink
 } // namespace llvm
 
 #endif

llvm/lib/ExecutionEngine/JITLink/ELF_riscv.cpp

case R_RISCV_32_PCREL: {
       *(little32_t *)FixupPtr = Word32;
       break;
     }
     }
     return Error::success();
   }
 };
 
+namespace {
+
+struct SymbolAnchor {
+  uint64_t Offset;
+  Symbol *Sym;
+  bool End; // true for the anchor of getOffset() + getSize()
+};
+
+struct BlockRelaxAux {
+  // This records symbol start and end offsets which will be adjusted according
+  // to the nearest RelocDeltas element.
+  SmallVector<SymbolAnchor, 0> Anchors;
+  // All edges that either 1) are R_RISCV_ALIGN or 2) have a R_RISCV_RELAX edge
+  // at the same offset.
+  SmallVector<Edge *, 0> RelaxEdges;
+  // For RelaxEdges[I], the actual offset is RelaxEdges[I]->getOffset() - (I ?
+  // RelocDeltas[I - 1] : 0).
+  SmallVector<uint32_t, 0> RelocDeltas;
+  // For RelaxEdges[I], the actual type is EdgeKinds[I].
+  SmallVector<Edge::Kind, 0> EdgeKinds;
+  // List of rewritten instructions. Contains one raw encoded instruction per
+  // element in EdgeKinds that isn't Invalid or R_RISCV_ALIGN.
+  SmallVector<uint32_t, 0> Writes;
+};
+
+struct RelaxConfig {
+  bool IsRV32;
+  bool HasRVC;
+};
+
+struct RelaxAux {
+  RelaxConfig Config;
+  DenseMap<Block *, BlockRelaxAux> Blocks;
+};
+
+bool shouldRelax(const Section &S) {
+  return (S.getMemProt() & orc::MemProt::Exec) != orc::MemProt::None;
+}
+
+RelaxAux initRelaxAux(LinkGraph &G) {
+  RelaxAux Aux;
+  Aux.Config.IsRV32 = G.getTargetTriple().isRISCV32();
+  const auto &Features = G.getFeatures().getFeatures();
+  Aux.Config.HasRVC =
+      std::find(Features.begin(), Features.end(), "+c") != Features.end();
+
+  for (auto &S : G.sections()) {
+    if (!shouldRelax(S))
+      continue;
+    for (auto *B : S.blocks()) {
+      auto BlockEmplaceResult = Aux.Blocks.try_emplace(B);
+      assert(BlockEmplaceResult.second && "Block encountered twice");
+
+      auto &BlockAux = BlockEmplaceResult.first->second;
+      Edge *PrevEdge = nullptr;
+
+      for (auto &E : B->edges()) {
+        if (E.getKind() == R_RISCV_ALIGN) {
+          BlockAux.RelaxEdges.push_back(&E);
+          continue;
+        }
+
+        if (E.getKind() != R_RISCV_RELAX) {
+          PrevEdge = &E;
+          continue;
+        }
+
+        assert(PrevEdge && "R_RISCV_RELAX without previous edge");
+        BlockAux.RelaxEdges.push_back(PrevEdge);
+        PrevEdge = nullptr;
+      }
+
+      if (BlockAux.RelaxEdges.empty()) {
+        Aux.Blocks.erase(BlockEmplaceResult.first);
+        continue;
+      }
+
+      const auto NumEdges = BlockAux.RelaxEdges.size();
+      BlockAux.RelocDeltas.resize(NumEdges, 0);
+      BlockAux.EdgeKinds.resize_for_overwrite(NumEdges);
+
+      // Store anchors (offset and offset+size) for symbols.
+      for (auto *Sym : S.symbols()) {
+        if (!Sym->isDefined() || &Sym->getBlock() != B)
+          continue;
+
+        BlockAux.Anchors.push_back({Sym->getOffset(), Sym, false});
+        BlockAux.Anchors.push_back(
+            {Sym->getOffset() + Sym->getSize(), Sym, true});
+      }
+    }
+  }
+
+  // Sort anchors by offset so that we can find the closest relocation
+  // efficiently. For a zero size symbol, ensure that its start anchor precedes
+  // its end anchor. For two symbols with anchors at the same offset, their
+  // order does not matter.
+  for (auto &BlockAuxIter : Aux.Blocks) {
+    llvm::sort(BlockAuxIter.second.Anchors, [](auto &A, auto &B) {
+      return std::make_pair(A.Offset, A.End) < std::make_pair(B.Offset, B.End);
+    });
+  }
+
+  return Aux;
+}
+
+void relaxAlign(orc::ExecutorAddr Loc, const Edge &E, uint32_t &Remove,
+                Edge::Kind &NewEdgeKind) {
+  // E points to the start of the padding bytes.
+  // E + Addend points to the instruction to be aligned by removing padding.
+  // Alignment is the smallest power of 2 strictly greater than Addend.
+  const auto Align = NextPowerOf2(E.getAddend());
+  const auto DestLoc = alignTo(Loc.getValue(), Align);
+  const auto SrcLoc = Loc.getValue() + E.getAddend();
+  Remove = SrcLoc - DestLoc;
+  assert(static_cast<int32_t>(Remove) >= 0 &&
+         "R_RISCV_ALIGN needs expanding the content");
+  NewEdgeKind = R_RISCV_ALIGN;
+}
+
+void relaxCall(const Block &B, BlockRelaxAux &Aux, const RelaxConfig &Config,
+               orc::ExecutorAddr Loc, const Edge &E, uint32_t &Remove,
+               Edge::Kind &NewEdgeKind) {
+  const auto JALR =
+      support::endian::read32le(B.getContent().data() + E.getOffset() + 4);
+  const auto RD = extractBits(JALR, 7, 5);
+  const auto Dest = E.getTarget().getAddress() + E.getAddend();
+  const auto Displace = Dest - Loc;
+
+  if (Config.HasRVC && isInt<12>(Displace) && RD == 0) {
+    NewEdgeKind = R_RISCV_RVC_JUMP;
+    Aux.Writes.push_back(0xa001); // c.j
+    Remove = 6;
+  } else if (Config.HasRVC && Config.IsRV32 && isInt<12>(Displace) && RD == 1) {
+    NewEdgeKind = R_RISCV_RVC_JUMP;
+    Aux.Writes.push_back(0x2001); // c.jal
+    Remove = 6;
+  } else if (isInt<21>(Displace)) {
+    NewEdgeKind = R_RISCV_JAL;
+    Aux.Writes.push_back(0x6f | RD << 7); // jal
+    Remove = 4;
+  }
+}
+
+bool relaxBlock(LinkGraph &G, Block &Block, BlockRelaxAux &Aux,
+                const RelaxConfig &Config) {
+  const auto BlockAddr = Block.getAddress();
+  bool Changed = false;
+  ArrayRef<SymbolAnchor> SA = ArrayRef(Aux.Anchors);
+  uint32_t Delta = 0;
+
+  Aux.EdgeKinds.assign(Aux.EdgeKinds.size(), Edge::Invalid);
+  Aux.Writes.clear();
+
+  for (auto [I, E] : llvm::enumerate(Aux.RelaxEdges)) {
+    const auto Loc = BlockAddr + E->getOffset() - Delta;
+    auto &Cur = Aux.RelocDeltas[I];
+    uint32_t Remove = 0;
+    switch (E->getKind()) {
+    case R_RISCV_ALIGN: {
+      relaxAlign(Loc, *E, Remove, Aux.EdgeKinds[I]);
+      break;
+    }
+    case R_RISCV_CALL:
+    case R_RISCV_CALL_PLT:
+      relaxCall(Block, Aux, Config, Loc, *E, Remove, Aux.EdgeKinds[I]);
+      break;
+    }
+
+    // For all anchors whose offsets are <= E->getOffset(), they are preceded by
+    // the previous relocation whose RelocDeltas value equals Delta.
+    // Decrease their offset and update their size.
+    for (; SA.size() && SA[0].Offset <= E->getOffset(); SA = SA.slice(1)) {
+      if (SA[0].End)
+        SA[0].Sym->setSize(SA[0].Offset - Delta - SA[0].Sym->getOffset());
+      else
+        SA[0].Sym->setOffset(SA[0].Offset - Delta);
+    }
+
+    Delta += Remove;
+    if (Delta != Cur) {
+      Cur = Delta;
+      Changed = true;
+    }
+  }
+
+  for (const SymbolAnchor &A : SA) {
+    if (A.End)
+      A.Sym->setSize(A.Offset - Delta - A.Sym->getOffset());
+    else
+      A.Sym->setOffset(A.Offset - Delta);
+  }
+
+  return Changed;
+}
+
+bool relaxOnce(LinkGraph &G, RelaxAux &Aux) {
+  bool Changed = false;
+
+  for (auto &[B, BlockAux] : Aux.Blocks)
+    Changed |= relaxBlock(G, *B, BlockAux, Aux.Config);
+
+  return Changed;
+}
+
+void finalizeBlockRelax(LinkGraph &G, Block &Block, BlockRelaxAux &Aux) {
+  auto Contents = Block.getAlreadyMutableContent();
+  auto *Dest = Contents.data();
+  auto NextWrite = Aux.Writes.begin();
+  uint32_t Offset = 0;
+  uint32_t Delta = 0;
+
+  // Update section content: remove NOPs for R_RISCV_ALIGN and rewrite
+  // instructions for relaxed relocations.
+  for (auto [I, E] : llvm::enumerate(Aux.RelaxEdges)) {
+    uint32_t Remove = Aux.RelocDeltas[I] - Delta;
+    Delta = Aux.RelocDeltas[I];
+    if (Remove == 0 && Aux.EdgeKinds[I] == Edge::Invalid)
+      continue;
+
+    // Copy from last location to the current relocated location.
+    const auto Size = E->getOffset() - Offset;
+    std::memmove(Dest, Contents.data() + Offset, Size);
+    Dest += Size;
+
+    uint32_t Skip = 0;
+    switch (Aux.EdgeKinds[I]) {
+    case Edge::Invalid:
+      break;
+    case R_RISCV_ALIGN:
+      // For R_RISCV_ALIGN, we will place Offset in a location (among NOPs) to
+      // satisfy the alignment requirement. If both Remove and E->getAddend()
+      // are multiples of 4, it is as if we have skipped some NOPs. Otherwise we
+      // are in the middle of a 4-byte NOP, and we need to rewrite the NOP
+      // sequence.
+      if (Remove % 4 || E->getAddend() % 4) {
+        Skip = E->getAddend() - Remove;
+        uint32_t J = 0;
+        for (; J + 4 <= Skip; J += 4)
+          support::endian::write32le(Dest + J, 0x00000013); // nop
+        if (J != Skip) {
+          assert(J + 2 == Skip);
+          support::endian::write16le(Dest + J, 0x0001); // c.nop
+        }
+      }
+      break;
+    case R_RISCV_RVC_JUMP:
+      Skip = 2;
+      support::endian::write16le(Dest, *NextWrite++);
+      break;
+    case R_RISCV_JAL:
+      Skip = 4;
+      support::endian::write32le(Dest, *NextWrite++);
+      break;
+    default:
+      llvm_unreachable("unsupported type");
+    }
+
+    Dest += Skip;
+    Offset = E->getOffset() + Skip + Remove;
+  }
+
+  std::memmove(Dest, Contents.data() + Offset, Contents.size() - Offset);
+
+  // Fixup edge offsets and kinds.
+  Delta = 0;
+  for (auto [I, E] : llvm::enumerate(Aux.RelaxEdges)) {
+    E->setOffset(E->getOffset() - Delta);
+
+    if (Aux.EdgeKinds[I] != Edge::Invalid)
+      E->setKind(Aux.EdgeKinds[I]);
+
+    Delta = Aux.RelocDeltas[I];
+  }
+
+  // Remove R_RISCV_ALIGN and R_RISCV_RELAX edges.
+  for (auto *B : G.blocks()) {
+    for (auto IE = B->edges().begin(); IE != B->edges().end();) {
+      auto Kind = IE->getKind();
+      if (Kind == R_RISCV_RELAX || Kind == R_RISCV_ALIGN)
+        IE = B->removeEdge(IE);
+      else
+        ++IE;
+    }
+  }
+}
+
+void finalizeRelax(LinkGraph &G, RelaxAux &Aux) {
+  for (auto &[B, BlockAux] : Aux.Blocks)
+    finalizeBlockRelax(G, *B, BlockAux);
+}
+
+Error relax(LinkGraph &G) {
+  auto Aux = initRelaxAux(G);
+  while (relaxOnce(G, Aux)) {
+  }
+  finalizeRelax(G, Aux);
+  return Error::success();
+}
+
+} // namespace
+
 template <typename ELFT>
 class ELFLinkGraphBuilder_riscv : public ELFLinkGraphBuilder<ELFT> {
 private:
   static Expected<riscv::EdgeKind_riscv>
   getRelocationKind(const uint32_t Type) {
     using namespace riscv;
     switch (Type) {
     case ELF::R_RISCV_32:
getRelocationKind(const uint32_t Type) {
     case ELF::R_RISCV_SET8:
       return EdgeKind_riscv::R_RISCV_SET8;
     case ELF::R_RISCV_SET16:
       return EdgeKind_riscv::R_RISCV_SET16;
     case ELF::R_RISCV_SET32:
       return EdgeKind_riscv::R_RISCV_SET32;
     case ELF::R_RISCV_32_PCREL:
       return EdgeKind_riscv::R_RISCV_32_PCREL;
+    case ELF::R_RISCV_RELAX:
+      return EdgeKind_riscv::R_RISCV_RELAX;
+    case ELF::R_RISCV_ALIGN:
+      return EdgeKind_riscv::R_RISCV_ALIGN;
     }
 
     return make_error<JITLinkError>(
         "Unsupported riscv relocation:" + formatv("{0:d}: ", Type) +
         object::getELFRelocationTypeName(ELF::EM_RISCV, Type));
   }
 
   Error addRelocations() override {
private:
   }
 
   Error addSingleRelocation(const typename ELFT::Rela &Rel,
                             const typename ELFT::Shdr &FixupSect,
                             Block &BlockToFix) {
     using Base = ELFLinkGraphBuilder<ELFT>;
 
     uint32_t Type = Rel.getType(false);
-    // We do not implement linker relaxation, except what is required for
-    // alignment (see below).
-    if (Type == llvm::ELF::R_RISCV_RELAX)
-      return Error::success();
-
     int64_t Addend = Rel.r_addend;
-    if (Type == llvm::ELF::R_RISCV_ALIGN) {
-      uint64_t Alignment = PowerOf2Ceil(Addend);
-      // FIXME: Implement support for ensuring alignment together with linker
-      // relaxation; 2 bytes are guaranteed by the length of compressed
-      // instructions, so this does not need any action from our side.
-      if (Alignment > 2)
-        return make_error<JITLinkError>(
-            formatv("Unsupported relocation R_RISCV_ALIGN with alignment {0} "
-                    "larger than 2 (addend: {1})",
-                    Alignment, Addend));
-      return Error::success();
-    }
-
     Expected<riscv::EdgeKind_riscv> Kind = getRelocationKind(Type);
     if (!Kind)
       return Kind.takeError();
 
     uint32_t SymbolIndex = Rel.getSymbol(false);
     auto ObjSymbol = Base::Obj.getRelocationSymbol(Rel, Base::SymTabSec);
     if (!ObjSymbol)
       return ObjSymbol.takeError();
void link_ELF_riscv(std::unique_ptr<LinkGraph> G,
   const Triple &TT = G->getTargetTriple();
   if (Ctx->shouldAddDefaultTargetPasses(TT)) {
     if (auto MarkLive = Ctx->getMarkLivePass(TT))
       Config.PrePrunePasses.push_back(std::move(MarkLive));
     else
       Config.PrePrunePasses.push_back(markAllSymbolsLive);
     Config.PostPrunePasses.push_back(
         PerGraphGOTAndPLTStubsBuilder_ELF_riscv::asPass);
+    Config.PreFixupPasses.push_back(relax);
   }
   if (auto Err = Ctx->modifyPassConfig(*G, Config))
     return Ctx->notifyFailed(std::move(Err));
 
   ELFJITLinker_riscv::link(std::move(Ctx), std::move(G), std::move(Config));
 }
 
 } // namespace jitlink
 } // namespace llvm

llvm/lib/ExecutionEngine/JITLink/riscv.cpp

const char *getEdgeKindName(Edge::Kind K) {
   case R_RISCV_SET8:
     return "R_RISCV_SET8";
   case R_RISCV_SET16:
     return "R_RISCV_SET16";
   case R_RISCV_SET32:
     return "R_RISCV_SET32";
   case R_RISCV_32_PCREL:
     return "R_RISCV_32_PCREL";
+  case R_RISCV_RELAX:
+    return "R_RISCV_RELAX";
+  case R_RISCV_ALIGN:
+    return "R_RISCV_ALIGN";
   }
   return getGenericEdgeKindName(K);
 }
 } // namespace riscv
 } // namespace jitlink
 } // namespace llvm

llvm/test/ExecutionEngine/JITLink/RISCV/ELF_relax_align.s

+## 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 %t.rv32
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x0 -slab-page-size 4096 \
+# RUN:     -check %s %t.rv32
+
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+relax %s -o %t.rv64
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x0 -slab-page-size 4096 \
+# RUN:     -check %s %t.rv64
+
+    .globl main,align4,align8,align16,align32
+    .size align4, 1
+    .size align8, 1
+    .size align16, 1
+    .size align32, 1
+main:
+    call f
+    .balign 4
+align4:
+    call f
+    .balign 8
+align8:
+    call f
+    .balign 16
+align16:
+    call f
+    .balign 32
+align32:
+    call f
+    .size main, .-main
+
+    .globl f
+f:
+    ret
+    .size f, .-f
+
+# jitlink-check: main = 0x0
+# jitlink-check: align4 = 0x4
+# jitlink-check: align8 = 0x8
+# jitlink-check: align16 = 0x10
+# jitlink-check: align32 = 0x20
+
+## main: jal f
+# jitlink-check: (*{4}(main))[11:0] = 0xef
+# jitlink-check: decode_operand(main, 1) = (f - main)
+
+## align 4: jal f
+# jitlink-check: (*{4}(align4))[11:0] = 0xef
+# jitlink-check: decode_operand(align4, 1) = (f - align4)
+
+## align8: jal f; nop
+# jitlink-check: (*{4}(align8))[11:0] = 0xef
+# jitlink-check: decode_operand(align8, 1) = (f - align8)
+# jitlink-check: (*{4}(align8+4)) = 0x13
+
+## align16: jal f; nop; nop; nop
+# jitlink-check: (*{4}(align16))[11:0] = 0xef
+# jitlink-check: decode_operand(align16, 1) = (f - align16)
+# jitlink-check: (*{4}(align16+4)) = 0x13
+# jitlink-check: (*{4}(align16+8)) = 0x13
+# jitlink-check: (*{4}(align16+12)) = 0x13
+
+## align32: jal f
+# jitlink-check: (*{4}(align32))[11:0] = 0xef
+# jitlink-check: decode_operand(align32, 1) = (f - align32)

llvm/test/ExecutionEngine/JITLink/RISCV/ELF_relax_align_rvc.s

+## Test that we can handle R_RISCV_ALIGN.
+
+# RUN: llvm-mc -filetype=obj -triple=riscv32 -mattr=+relax,+c %s -o %t.rv32
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x0 -slab-page-size 4096 \
+# RUN:     -check %s %t.rv32
+
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+relax,+c %s -o %t.rv64
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x0 -slab-page-size 4096 \
+# RUN:     -check %s %t.rv64
+
+    .globl main,align2,align4,align8,align16,align32
+    .type  main,@function
+main:
+    jump f, t0
+    .balign 2
+align2:
+    jump f, t0
+    .size align2,.-align2
+    .balign 4
+align4:
+    jump f, t0
+    .size align4,.-align4
+    .balign 8
+align8:
+    jump f, t0
+    .size align8,.-align8
+    .balign 16
+align16:
+    jump f, t0
+    .size align16,.-align16
+    .size main, .-main
+
+    .globl f
+f:
+    ret
+    .size f, .-f
+
+# jitlink-check: main = 0x0
+# jitlink-check: align2 = 0x2
+# jitlink-check: align4 = 0x4
+# jitlink-check: align8 = 0x8
+# jitlink-check: align16 = 0x10
+
+## main: c.j f
+# jitlink-check: (*{2}(main))[1:0] = 0x1
+# jitlink-check: (*{2}(main))[15:13] = 0x5
+# jitlink-check: decode_operand(main, 0)[11:0] = (f - main)[11:0]
+
+## align2: c.j f
+# jitlink-check: (*{2}(align2))[1:0] = 0x1
+# jitlink-check: (*{2}(align2))[15:13] = 0x5
+# jitlink-check: decode_operand(align2, 0)[11:0] = (f - align2)[11:0]
+
+## align4: c.j f; c.nop
+# jitlink-check: (*{2}(align4))[1:0] = 0x1
+# jitlink-check: (*{2}(align4))[15:13] = 0x5
+# jitlink-check: decode_operand(align4, 0)[11:0] = (f - align4)[11:0]
+# jitlink-check: (*{2}(align4+2)) = 0x1
+
+## align8: c.j f; nop; c.nop
+# jitlink-check: (*{2}(align8))[1:0] = 0x1
+# jitlink-check: (*{2}(align8))[15:13] = 0x5
+# jitlink-check: decode_operand(align8, 0)[11:0] = (f - align8)[11:0]
+# jitlink-check: (*{4}(align8+2)) = 0x13
+# jitlink-check: (*{2}(align8+6)) = 0x1
+
+## align16: c.j f
+# jitlink-check: (*{2}(align16))[1:0] = 0x1
+# jitlink-check: (*{2}(align16))[15:13] = 0x5
+# jitlink-check: decode_operand(align16, 0)[11:0] = (f - align16)[11:0]

llvm/test/ExecutionEngine/JITLink/RISCV/ELF_relax_call.s

+# RUN: llvm-mc -triple=riscv32 -mattr=+relax -filetype=obj -o %t.rv32 %s
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x1000 -slab-page-size 4096 \
+# RUN:     -debug-only=jitlink -check %s %t.rv32 \
+# RUN:    2>&1 | FileCheck %s
+
+# RUN: llvm-mc -triple=riscv64 -mattr=+relax -filetype=obj -o %t.rv64 %s
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x1000 -slab-page-size 4096 \
+# RUN:     -debug-only=jitlink -check %s %t.rv64 \
+# RUN:    2>&1 | FileCheck %s
+
+        .text
+
+## Successful relaxation: call -> jal
+        .globl  main
+        .type   main,@function
+main:
+        call f
+        .size   main, .-main
+
+        .skip  (1 << 20) - (. - main) - 2
+
+        .globl f
+        .type   f,@function
+f:
+        call main
+        .size f, .-f
+
+## Failed relaxation: call -> auipc, jalr
+        .globl g
+g:
+        call h
+        .size g, .-g
+
+        .skip  (1 << 20) - (. - g) + 2
+
+        .globl h
+        .type   h,@function
+h:
+        call g
+        .size h, .-h
+
+## Successful relaxation: jump -> jal (not c.j as RVC is disabled)
+        .globl i
+        .type   i,@function
+i:
+        jump j, t0
+        .size i, .-i
+
+        .skip  (1 << 11) - (. - i) - 2
+
+        .globl j
+        .type   j,@function
+j:
+        jump i, t1
+        .size j, .-j
+
+## Successful relaxation: jump -> jal
+        .globl k
+        .type   k,@function
+k:
+        jump l, t2
+        .size k, .-k
+
+        .skip  (1 << 20) - (. - k) - 2
+
+        .globl l
+        .type   l,@function
+l:
+        jump k, t3
+        .size l, .-l
+
+## Failed relaxation: jump -> auipc, jalr
+        .globl m
+        .type   m,@function
+m:
+        jump n, t2
+        .size m, .-m
+
+        .skip  (1 << 20) - (. - m) + 2
+
+        .globl n
+        .type   n,@function
+n:
+        jump m, t3
+        .size n, .-n
+
+## Successful relaxation: call -> jal
+        .globl o
+        .type   o,@function
+o:
+        call p
+        .size o, .-o
+
+        .skip  (1 << 11) - (. - o) - 2
+
+        .globl p
+        .type   p,@function
+p:
+        call o
+        .size p, .-p
+
+# CHECK: Link graph "{{.*}}" before copy-and-fixup:
+# CHECK: section .text:
+# CHECK:   block 0x1000
+# CHECK:     symbols:
+# CHECK:       {{.*}} (block + 0x00000000): size: 0x00000004, linkage: strong, scope: default, live  -   main
+# CHECK:       {{.*}} (block + 0x000ffffa): size: 0x00000004, linkage: strong, scope: default, live  -   f
+# CHECK:       {{.*}} (block + 0x000ffffe): size: 0x00000008, linkage: strong, scope: default, live  -   g
+# CHECK:       {{.*}} (block + 0x00200000): size: 0x00000008, linkage: strong, scope: default, live  -   h
+# CHECK:       {{.*}} (block + 0x00200008): size: 0x00000004, linkage: strong, scope: default, live  -   i
+# CHECK:       {{.*}} (block + 0x00200802): size: 0x00000004, linkage: strong, scope: default, live  -   j
+# CHECK:       {{.*}} (block + 0x00200806): size: 0x00000004, linkage: strong, scope: default, live  -   k
+# CHECK:       {{.*}} (block + 0x00300800): size: 0x00000004, linkage: strong, scope: default, live  -   l
+# CHECK:       {{.*}} (block + 0x00300804): size: 0x00000008, linkage: strong, scope: default, live  -   m
+# CHECK:       {{.*}} (block + 0x00400806): size: 0x00000008, linkage: strong, scope: default, live  -   n
+# CHECK:       {{.*}} (block + 0x0040080e): size: 0x00000004, linkage: strong, scope: default, live  -   o
+# CHECK:       {{.*}} (block + 0x00401008): size: 0x00000004, linkage: strong, scope: default, live  -   p
+# CHECK:     edges:
+# CHECK:       {{.*}} (block + 0x00000000), addend = +0x00000000, kind = R_RISCV_JAL, target = f
+# CHECK:       {{.*}} (block + 0x000ffffa), addend = +0x00000000, kind = R_RISCV_JAL, target = main
+# CHECK:       {{.*}} (block + 0x000ffffe), addend = +0x00000000, kind = R_RISCV_CALL_PLT, target = h
+# CHECK:       {{.*}} (block + 0x00200000), addend = +0x00000000, kind = R_RISCV_CALL_PLT, target = g
+# CHECK:       {{.*}} (block + 0x00200008), addend = +0x00000000, kind = R_RISCV_JAL, target = j
+# CHECK:       {{.*}} (block + 0x00200802), addend = +0x00000000, kind = R_RISCV_JAL, target = i
+# CHECK:       {{.*}} (block + 0x00200806), addend = +0x00000000, kind = R_RISCV_JAL, target = l
+# CHECK:       {{.*}} (block + 0x00300800), addend = +0x00000000, kind = R_RISCV_JAL, target = k
+# CHECK:       {{.*}} (block + 0x00300804), addend = +0x00000000, kind = R_RISCV_CALL_PLT, target = n
+# CHECK:       {{.*}} (block + 0x00400806), addend = +0x00000000, kind = R_RISCV_CALL_PLT, target = m
+# CHECK:       {{.*}} (block + 0x0040080e), addend = +0x00000000, kind = R_RISCV_JAL, target = p
+# CHECK:       {{.*}} (block + 0x00401008), addend = +0x00000000, kind = R_RISCV_JAL, target = o
+
+## main: jal f
+# jitlink-check: (*{4}(main))[11:0] = 0xef
+# jitlink-check: decode_operand(main, 1) = (f - main)
+
+## f: jal main
+# jitlink-check: (*{4}(f))[11:0] = 0xef
+# jitlink-check: decode_operand(f, 1) = (main - f)
+
+## g:
+## - auipc ra, %pcrel_hi(h)
+# jitlink-check: (*{4}(g))[11:0] = 0x97
+# jitlink-check: decode_operand(g, 1) = (h - g + 0x800)[31:12]
+## - jalr ra, %pcrel_lo(g)
+# jitlink-check: (*{4}(g+4))[19:0] = 0x80e7
+# jitlink-check: decode_operand(g+4, 2)[11:0] = (h - g)[11:0]
+
+## h:
+## - auipc ra, %pcrel_hi(g)
+# jitlink-check: (*{4}(h))[11:0] = 0x97
+# jitlink-check: decode_operand(h, 1) = (g - h + 0x800)[31:12]
+## - jalr ra, %pcrel_lo(h)
+# jitlink-check: (*{4}(h+4))[19:0] = 0x80e7
+# jitlink-check: decode_operand(h+4, 2)[11:0] = (g - h)[11:0]
+
+## i: jal x0, j
+# jitlink-check: (*{4}(i))[11:0] = 0x6f
+# jitlink-check: decode_operand(i, 1)[11:0] = (j - i)[11:0]
+
+## j: jal x0, i
+# jitlink-check: (*{4}(j))[11:0] = 0x6f
+# jitlink-check: decode_operand(j, 1)[11:0] = (i - j)[11:0]
+
+## k: jal x0, l
+# jitlink-check: (*{4}(k))[11:0] = 0x6f
+# jitlink-check: decode_operand(k, 1) = (l - k)
+
+## l: jal x0, k
+# jitlink-check: (*{4}(l))[11:0] = 0x6f
+# jitlink-check: decode_operand(l, 1) = (k - l)
+
+## m:
+## - auipc t2, %pcrel_hi(n)
+# jitlink-check: (*{4}(m))[11:0] = 0x397
+# jitlink-check: decode_operand(m, 1) = (n - m + 0x800)[31:12]
+## - jalr t2, %pcrel_lo(m)
+# jitlink-check: (*{4}(m+4))[19:0] = 0x38067
+# jitlink-check: decode_operand(m+4, 2)[11:0] = (n - m)[11:0]
+
+## n:
+## - auipc t3, %pcrel_hi(m)
+# jitlink-check: (*{4}(n))[11:0] = 0xe17
+# jitlink-check: decode_operand(n, 1) = (m - n + 0x800)[31:12]
+## - jalr t3, %pcrel_lo(n)
+# jitlink-check: (*{4}(n+4))[19:0] = 0xe0067
+# jitlink-check: decode_operand(n+4, 2)[11:0] = (m - n)[11:0]
+
+## o: jal p
+# jitlink-check: (*{4}(o))[11:0] = 0xef
+# jitlink-check: decode_operand(o, 1) = (p - o)
+
+## p: jal o
+# jitlink-check: (*{4}(p))[11:0] = 0xef
+# jitlink-check: decode_operand(p, 1) = (o - p)

llvm/test/ExecutionEngine/JITLink/RISCV/ELF_relax_call_boundary.s

+## Test R_RISCV_CALL relaxation for some boundary situations that need multiple
+## iterations before symbols fit in a c.j immediate.
+
+# RUN: llvm-mc -filetype=obj -triple=riscv32 -mattr=+relax,+c %s -o %t.rv32
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x1000 -slab-page-size 4096 \
+# RUN:     -check %s %t.rv32
+
+# RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+relax,+c %s -o %t.rv64
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x1000 -slab-page-size 4096 \
+# RUN:     -check %s %t.rv64
+
+        .globl main
+        .type main,@function
+main:
+## Relaxed to c.j. This needs 2 iterations: c.j only fits after first relaxing
+## to jal
+        tail f
+        .space 2042
+        .size main, .-main
+
+        .globl f
+        .type f,@function
+f:
+## Relaxed to c.j in the same way as above.
+        tail main
+        .size f, .-f
+
+        .globl g
+        .type g,@function
+g:
+## Relaxed to c.j. This needs 3 iterations: c.j only fits after first relaxing
+## both itself and the call to g to jal, and then relaxing the call to g to c.j
+        tail h
+        tail g
+        .space 2040
+        .size g, .-g
+
+        .globl h
+        .type h,@function
+h:
+## Relaxed to c.j in the same way as above.
+        tail g
+        .size h, .-h
+
+## main: c.j f
+# jitlink-check: (*{2}(main))[1:0] = 0x1
+# jitlink-check: (*{2}(main))[15:13] = 0x5
+# jitlink-check: decode_operand(main, 0)[11:0] = (f - main)[11:0]
+
+## f: c.j main
+# jitlink-check: (*{2}(f))[1:0] = 0x1
+# jitlink-check: (*{2}(f))[15:13] = 0x5
+# jitlink-check: decode_operand(f, 0)[11:0] = (main - f)[11:0]
+
+## g: c.j h; c.j g
+# jitlink-check: (*{2}(g))[1:0] = 0x1
+# jitlink-check: (*{2}(g))[15:13] = 0x5
+# jitlink-check: decode_operand(g, 0)[11:0] = (h - g)[11:0]
+# jitlink-check: (*{2}(g+2))[1:0] = 0x1
+# jitlink-check: (*{2}(g+2))[15:13] = 0x5
+# jitlink-check: decode_operand(g+2, 0)[11:0] = (g - (g + 2))[11:0]
+
+## h: c.j g
+# jitlink-check: (*{2}(h))[1:0] = 0x1
+# jitlink-check: (*{2}(h))[15:13] = 0x5
+# jitlink-check: decode_operand(h, 0)[11:0] = (g - h)[11:0]

llvm/test/ExecutionEngine/JITLink/RISCV/ELF_relax_call_rvc.s

+# RUN: llvm-mc -triple=riscv32 -mattr=+relax,+c -filetype=obj -o %t.rv32 %s
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x1000 -slab-page-size 4096 \
+# RUN:     -debug-only=jitlink -check %s %t.rv32 \
+# RUN:    2>&1 | FileCheck %s
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x1000 -slab-page-size 4096 \
+# RUN:     -debug-only=jitlink -check %s -check-name=jitlink-check-rv32 %t.rv32 \
+# RUN:     2>&1 | FileCheck -check-prefix=CHECK-RV32 %s
+
+# RUN: llvm-mc -triple=riscv64 -mattr=+relax,+c -filetype=obj -o %t.rv64 %s
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x1000 -slab-page-size 4096 \
+# RUN:     -debug-only=jitlink -check %s %t.rv64 \
+# RUN:     2>&1 | FileCheck %s
+# RUN: llvm-jitlink -noexec \
+# RUN:     -slab-allocate 100Kb -slab-address 0x1000 -slab-page-size 4096 \
+# RUN:     -debug-only=jitlink -check %s -check-name=jitlink-check-rv64 %t.rv64 \
+# RUN:     2>&1 | FileCheck -check-prefix=CHECK-RV64 %s
+
+        .text
+
+## Successful relaxation: call -> jal
+        .globl  main
+        .type   main,@function
+main:
+        call f # rv64+c: jal (size 4)
+        .size   main, .-main
+
+        .skip  (1 << 20) - (. - main) - 2
+
+        .globl f
+        .type   f,@function
+f:
+        call main
+        .size f, .-f
+
+## Failed relaxation: call -> auipc, jalr
+        .globl g
+g:
+        call h
+        .size g, .-g
+
+        .skip  (1 << 20) - (. - g) + 2
+
+        .globl h
+        .type   h,@function
+h:
+        call g
+        .size h, .-h
+
+## Successful relaxation: jump -> c.j
+        .globl i
+        .type   i,@function
+i:
+        jump j, t0
+        .size i, .-i
+
+        .skip  (1 << 11) - (. - i) - 2
+
+        .globl j
+        .type   j,@function
+j:
+        jump i, t1
+        .size j, .-j
+
+## Successful relaxation: jump -> jal
+        .globl k
+        .type   k,@function
+k:
+        jump l, t2
+        .size k, .-k
+
+        .skip  (1 << 20) - (. - k) - 2
+
+        .globl l
+        .type   l,@function
+l:
+        jump k, t3
+        .size l, .-l
+
+## Failed relaxation: jump -> auipc, jalr
+        .globl m
+        .type   m,@function
+m:
+        jump n, t2
+        .size m, .-m
+
+        .skip  (1 << 20) - (. - m) + 2
+
+        .globl n
+        .type   n,@function
+n:
+        jump m, t3
+        .size n, .-n
+
+## RV32: Successful relaxation: call -> c.jal
+## RV64: Successful relaxation: call -> jal
+        .globl o
+        .type   o,@function
+o:
+        call p
+        .size o, .-o
+
+        .skip  (1 << 11) - (. - o) - 2
+
+        .globl p
+        .type   p,@function
+p:
+        call o
+        .size p, .-p
+
+# CHECK:      Link graph "{{.*}}" before copy-and-fixup:
+# CHECK:      section .text:
+# CHECK:        block 0x1000
+# CHECK:          symbols:
+# CHECK:            {{.*}} (block + 0x00000000): size: 0x00000004, linkage: strong, scope: default, live  -   main
+# CHECK:            {{.*}} (block + 0x000ffffa): size: 0x00000004, linkage: strong, scope: default, live  -   f
+# CHECK:            {{.*}} (block + 0x000ffffe): size: 0x00000008, linkage: strong, scope: default, live  -   g
+# CHECK:            {{.*}} (block + 0x00200000): size: 0x00000008, linkage: strong, scope: default, live  -   h
+# CHECK:            {{.*}} (block + 0x00200008): size: 0x00000002, linkage: strong, scope: default, live  -   i
+# CHECK:            {{.*}} (block + 0x00200800): size: 0x00000002, linkage: strong, scope: default, live  -   j
+# CHECK:            {{.*}} (block + 0x00200802): size: 0x00000004, linkage: strong, scope: default, live  -   k
+# CHECK:            {{.*}} (block + 0x003007fc): size: 0x00000004, linkage: strong, scope: default, live  -   l
+# CHECK:            {{.*}} (block + 0x00300800): size: 0x00000008, linkage: strong, scope: default, live  -   m
+# CHECK:            {{.*}} (block + 0x00400802): size: 0x00000008, linkage: strong, scope: default, live  -   n
+# CHECK-RV32:       {{.*}} (block + 0x0040080a): size: 0x00000002, linkage: strong, scope: default, live  -   o
+# CHECK-RV64:       {{.*}} (block + 0x0040080a): size: 0x00000004, linkage: strong, scope: default, live  -   o
+# CHECK-RV32:       {{.*}} (block + 0x00401002): size: 0x00000002, linkage: strong, scope: default, live  -   p
+# CHECK-RV64:       {{.*}} (block + 0x00401004): size: 0x00000004, linkage: strong, scope: default, live  -   p
+# CHECK:          edges:
+# CHECK:            {{.*}} (block + 0x00000000), addend = +0x00000000, kind = R_RISCV_JAL, target = f
+# CHECK:            {{.*}} (block + 0x000ffffa), addend = +0x00000000, kind = R_RISCV_JAL, target = main
+# CHECK:            {{.*}} (block + 0x000ffffe), addend = +0x00000000, kind = R_RISCV_CALL_PLT, target = h
+# CHECK:            {{.*}} (block + 0x00200000), addend = +0x00000000, kind = R_RISCV_CALL_PLT, target = g
+# CHECK:            {{.*}} (block + 0x00200008), addend = +0x00000000, kind = R_RISCV_RVC_JUMP, target = j
+# CHECK:            {{.*}} (block + 0x00200800), addend = +0x00000000, kind = R_RISCV_RVC_JUMP, target = i
+# CHECK:            {{.*}} (block + 0x00200802), addend = +0x00000000, kind = R_RISCV_JAL, target = l
+# CHECK:            {{.*}} (block + 0x003007fc), addend = +0x00000000, kind = R_RISCV_JAL, target = k
+# CHECK:            {{.*}} (block + 0x00300800), addend = +0x00000000, kind = R_RISCV_CALL_PLT, target = n
+# CHECK:            {{.*}} (block + 0x00400802), addend = +0x00000000, kind = R_RISCV_CALL_PLT, target = m
+# CHECK-RV32:       {{.*}} (block + 0x0040080a), addend = +0x00000000, kind = R_RISCV_RVC_JUMP, target = p
+# CHECK-RV64:       {{.*}} (block + 0x0040080a), addend = +0x00000000, kind = R_RISCV_JAL, target = p
+# CHECK-RV32:       {{.*}} (block + 0x00401002), addend = +0x00000000, kind = R_RISCV_RVC_JUMP, target = o
+# CHECK-RV64:       {{.*}} (block + 0x00401004), addend = +0x00000000, kind = R_RISCV_JAL, target = o
+
+## main: jal f
+# jitlink-check: (*{4}(main))[11:0] = 0xef
+# jitlink-check: decode_operand(main, 1) = (f - main)
+
+## f: jal main
+# jitlink-check: (*{4}(f))[11:0] = 0xef
+# jitlink-check: decode_operand(f, 1) = (main - f)
+
+## g:
+## - auipc ra, %pcrel_hi(h)
+# jitlink-check: (*{4}(g))[11:0] = 0x97
+# jitlink-check: decode_operand(g, 1) = (h - g + 0x800)[31:12]
+## - jalr ra, %pcrel_lo(g)
+# jitlink-check: (*{4}(g+4))[19:0] = 0x80e7
+# jitlink-check: decode_operand(g+4, 2)[11:0] = (h - g)[11:0]
+
+## h:
+## - auipc ra, %pcrel_hi(g)
+# jitlink-check: (*{4}(h))[11:0] = 0x97
+# jitlink-check: decode_operand(h, 1) = (g - h + 0x800)[31:12]
+## - jalr ra, %pcrel_lo(h)
+# jitlink-check: (*{4}(h+4))[19:0] = 0x80e7
+# jitlink-check: decode_operand(h+4, 2)[11:0] = (g - h)[11:0]
+
+## i: c.j j
+# jitlink-check: (*{2}(i))[1:0] = 0x1
+# jitlink-check: (*{2}(i))[15:13] = 0x5
+# jitlink-check: decode_operand(i, 0)[11:0] = (j - i)[11:0]
+
+## j: c.j i
+# jitlink-check: (*{2}(j))[1:0] = 0x1
+# jitlink-check: (*{2}(j))[15:13] = 0x5
+# jitlink-check: decode_operand(j, 0)[11:0] = (i - j)[11:0]
+
+## k: jal x0, l
+# jitlink-check: (*{4}(k))[11:0] = 0x6f
+# jitlink-check: decode_operand(k, 1) = (l - k)
+
+## l: jal x0, k
+# jitlink-check: (*{4}(l))[11:0] = 0x6f
+# jitlink-check: decode_operand(l, 1) = (k - l)
+
+## m:
+## - auipc t2, %pcrel_hi(n)
+# jitlink-check: (*{4}(m))[11:0] = 0x397
+# jitlink-check: decode_operand(m, 1) = (n - m + 0x800)[31:12]
+## - jalr t2, %pcrel_lo(m)
+# jitlink-check: (*{4}(m+4))[19:0] = 0x38067
+# jitlink-check: decode_operand(m+4, 2)[11:0] = (n - m)[11:0]
+
+## n:
+## - auipc t3, %pcrel_hi(m)
+# jitlink-check: (*{4}(n))[11:0] = 0xe17
+# jitlink-check: decode_operand(n, 1) = (m - n + 0x800)[31:12]
+## - jalr t3, %pcrel_lo(n)
+# jitlink-check: (*{4}(n+4))[19:0] = 0xe0067
+# jitlink-check: decode_operand(n+4, 2)[11:0] = (m - n)[11:0]
+
+## RV32: o: c.jal p
+# jitlink-check-rv32: (*{2}(o))[1:0] = 0x1
+# jitlink-check-rv32: (*{2}(o))[15:13] = 0x1
+# jitlink-check-rv32: decode_operand(o, 0) = (p - o)
+
+## RV64: o: jal p
+# jitlink-check-rv64: (*{4}(o))[11:0] = 0xef
+# jitlink-check-rv64: decode_operand(o, 1) = (p - o)
+
+## RV32: p: c.jal o
+# jitlink-check-rv32: (*{2}(p))[1:0] = 0x1
+# jitlink-check-rv32: (*{2}(p))[15:13] = 0x1
+# jitlink-check-rv32: decode_operand(p, 0) = (o - p)
+
+## RV64: p: jal o
+# jitlink-check-rv64: (*{4}(p))[11:0] = 0xef
+# jitlink-check-rv64: decode_operand(p, 1) = (o - p)