[WIP][MC][RISCV] Allow targets to defer forcing relocations

[lewis-revill]

Summary

This patch modifies the process of recording relocations and applying fixups for a fragment to allow the target to remain undecided about whether or not to force a relocation until all fixups have been evaluated.

Only after the target has been allowed to re-evaluate fixups that have been marked as unknown can the process of recording relocations and applying fixups be run.

For RISC-V, this allows us to determine exactly which %pcrel_hi and %pcrel_lo fixups need relocations by ensuring all %pcrel_lo fixups and corresponding %pcrel_hi fixups are correctly matched in this regard.

Notable changes for review:

• Changed return type of shouldForceRelocation to Optional<bool> in MCAsmBackend
• Added handleUnknownFixups to MCAsmBackend
• Split up handleFixup and evaluateFixup to handleUnresolvedFixup, evaluateFixupPreTarget and evaluateFixup
• Split up fixup handling code into two distinct passes, one to attempt to evaluate and resolve fixups, and another to report errors, record relocations, and apply fixups, with the target being allowed to intervene for unknown fixups in between the two passes

This patch is work in progress, I'd appreciate feedback on the general approach and disruptiveness of this change.

[lewis-revill]

I have yet to add a RISC-V test for the behaviour we're trying to fix, but for now see the discussion on D57240.

[lewis-revill]

Remove dependency.

[rogfer01]

lib/Target/RISCV/MCTargetDesc/RISCVAsmBackend.cpp

133

Would this hold if the resolution of https://github.com/riscv/riscv-elf-psabi-doc/issues/90 is that a %pcrel_lo can cross sections?

Perhaps I got this wrong, but I understand that this process is currently section-wise, so we can't say much about a %pcrel_hi not being referenced by any %pcrel_lo in the same section, can we?

[palmer-dabbelt]

Thanks. It looks like everyone is on board with mandating in the RISC-V ELF psABI specification that pcrel_lo and pcrel_hi stay in the same section. Since this is nominally an ABI break (just one that we think nobody will notice) I proposed giving it a one week countdown to officially merge -- essentially if nobody can figure out a use case for doing this within a week then we'll adopt the ABI change. More information is on the github: https://github.com/riscv/riscv-elf-psabi-doc/issues/90

Thanks for finding this!

[lewis-revill]

lib/Target/RISCV/MCTargetDesc/RISCVAsmBackend.cpp

133

Sorry for the delay, yes this is a completely section-wise process. If the resolution allowed the pcrel to cross sections this patch would not be sufficient and the fix would require storing references to fixups between sections, which couldn't really be done in a neat way.

[bcain]

include/llvm/MC/MCAsmBackend.h

84–90

Could you make it explicit in the doc comments here that a returned value of 'None' indicates that it's indeterminate/unknown whether relocation is required.

[lewis-revill]

Rebased and added documentation comments

[lewis-revill]

Should the following case be considered for RISC-V? It's impossible to solve with this patch:

# pcrel_hi/pcrel_lo pair crossing a fragment boundary.

.Lpcrel_label0:
auipc  a0, %pcrel_hi(bar)

.p2align  2   # Cause a new fragment be emitted here

addi  a1, a0, %pcrel_lo(.Lpcrel_label0)

bar:
  # ...

I'm aware of the current clarification in the spec about crossing a section boundary, but this is less to do with specification and more about where LLVM decides to create fragments.

[rogfer01]

Hi @lewis-revill,

I've been looking into this and I have some observations, but not a satisfactory solution so far.

In the current form, this patch works fragment-wise. Which means that cross-fragment pcrel_hi / pcrel_lo can't really work because we eagerly solve pcrel_hi and later we can't relate pcrel_lo to its pcrel_hi because it is not in the current fragment. So we leave a dangling relocation for pcrel_lo which is problematic.

I moved the processing to be section-wise instead (i.e. delay all the handling until all the fragments of a section have been visited). This seems not to break anything but should be checked more thoroughly. The rest of the observations depend on this being possible.

Once we process section-wise what we see is that the offset between the pcrel_lo and the pcrel_hi is not correctly computed. This can be easily seen using .p2align 4 instead of 2 so a bunch of nops appear:

$ cat t.s
# pcrel_hi/pcrel_lo pair crossing a fragment boundary.

.Lpcrel_label0:
auipc  a0, %pcrel_hi(bar)

.p2align  4   # Cause a new fragment be emitted here

addi  a1, a0, %pcrel_lo(.Lpcrel_label0)

bar:
  ret

$ ./bin/llvm-mc -triple riscv64 -filetype obj -o t.o t.s && ./bin/llvm-objdump  -dr t.o

t.o:	file format ELF64-riscv


Disassembly of section .text:

0000000000000000 .text:
       0: 17 05 00 00                  	auipc	a0, 0
       4: 13 00 00 00                  	nop
       8: 13 00 00 00                  	nop
       c: 13 00 00 00                  	nop
      10: 93 05 45 01                  	addi	a1, a0, 4

0000000000000014 bar:
      14: 67 80 00 00                  	ret

The value computed in line 871, FixedValue has the wrong offset. The wrong offset is due to an interaction between RISCVMCExpr::evaluatePCRelLo computing a MCValue as stated in the comment (<real target> + <offset from this fixup to the auipc fixup>) and MCExpr::evaluateAsRelocatable removing the offset of the fixup within the section because this fixup is pc-relative. Thus, we compute 20 (the offset between the addi to bar, 4, and the offset from addi to auipc, 16) and then we remove 16 (the offset between the addi and auipc).

I'm unsure what we can do here, perhaps marking pcrel_lo fixups as not pc-relative would do? Maybe @jrtc27 or @asb have more insights whether this is feasible.

If we can't do this, then we need to make RISCVMCExpr::evaluatePCRelLo compensate the later subtraction (so it adds an extra Layout->getFragmentOffset(Fragment)). But to do this we need the Fragment of the current fixup (AFAIU it is not possible to get the MCFragment of a given MCFixup) and unfortunately this means we need to make it available to MCExpr::evaluateAsRelocatable (from MCAssembler::evaluateFixupPreTarget). This entails changing all the backends. I've gone this way and it seems to do the right thing for this case (i.e. the offset emitted is 20), but again needs some more testing.

I've also observed that in RISCVMCExpr::evaluatePCRelLo, the second check is tautological. Here this is %pcrel_lo(.Lpcrel_label0) and AUIPCSRE is .Lpcrel_label0 so I fail to see how their fragments would ever be different.

cpp
 // Don't try to evaluate %pcrel_hi/%pcrel_lo pairs that cross fragment
 // boundries.
 if (!AUIPCSRE ||
     findAssociatedFragment() != AUIPCSRE->findAssociatedFragment())

Hope these observations help!

Kind regards,

[lewis-revill]

In D58843#1486436, @rogfer01 wrote:

Hi @lewis-revill,

...

Hope these observations help!

Kind regards,

Hi @rogfer01,

Thanks for your thoughts, sorry for the delay.

I was worried that this would be the issue with this patch, in terms of not working section-wise. I would imagine that even if we did manage to make it work section-wise then that would not make a good generic patch... Thanks for the analysis on this approach though, I didn't realise that that would happen.

I'd like to know some more detail about the actual use cases for this pre-linker evaluation of fixups, it's becoming increasingly clear that a lot of difficulties could be/could have been avoided by letting the RISC-V shouldForceRelocation just return true for pcrel_hi/X_hi/pcrel_lo.

[lewis-revill]

Abandoned since this is no longer relevant to RISC-V; other individual fixes for issues relating to this problem have been merged since. I will keep D61907 around for discussion even though it's a similar 'big hammer' approach to the problem.

include/llvm/MC/MCAsmBackend.h

 //===- llvm/MC/MCAsmBackend.h - MC Asm Backend ------------------*- 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 LLVM_MC_MCASMBACKEND_H
 #define LLVM_MC_MCASMBACKEND_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/MC/MCDirectives.h"
 #include "llvm/MC/MCFixup.h"
 #include "llvm/MC/MCFragment.h"
 #include "llvm/Support/Endian.h"
 #include <cstdint>
 #include <memory>
public:
   virtual unsigned getNumFixupKinds() const = 0;
 
   /// Map a relocation name used in .reloc to a fixup kind.
   virtual Optional<MCFixupKind> getFixupKind(StringRef Name) const;
 
   /// Get information on a fixup kind.
   virtual const MCFixupKindInfo &getFixupKindInfo(MCFixupKind Kind) const;
 
   /// Hook to check if a relocation is needed for some target specific reason.
-  virtual bool shouldForceRelocation(const MCAssembler &Asm,
+  /// The target may return None when it is unknown whether or not to force a
+  /// relocation for the given fixup. Unknown fixups are revisited at the end of
+  /// the current section by handleUnknownFixups.
+  virtual Optional<bool> shouldForceRelocation(const MCAssembler &Asm,
                                                const MCFixup &Fixup,
                                                const MCValue &Target) {
     return false;
   }
 
+  /// Hook to revisit fixups for which shouldForceRelocation was unable to
+  /// determine whether to force a relocation. For each fixup the target should
+  /// indicate whether a relocation is needed in the EvaluatedFixups map.
+  virtual void
+  handleUnknownFixups(DenseSet<const MCFixup *> &UnknownFixups,
+                      DenseMap<const MCFixup *, bool> &EvaluatedFixups) {}
+
   /// Hook to check if extra nop bytes must be inserted for alignment directive.
   /// For some targets this may be necessary in order to support linker
   /// relaxation. The number of bytes to insert are returned in Size.
   virtual bool shouldInsertExtraNopBytesForCodeAlign(const MCAlignFragment &AF,
                                                      unsigned &Size) {
     return false;
   }
 

include/llvm/MC/MCAssembler.h

private:
   /// correct value if WasForced is true, even if evaluateFixup returns false.
   /// \return Whether the fixup value was fully resolved. This is true if the
   /// \p Value result is fixed, otherwise the value may change due to
   /// relocation.
   bool evaluateFixup(const MCAsmLayout &Layout, const MCFixup &Fixup,
                      const MCFragment *DF, MCValue &Target,
                      uint64_t &Value, bool &WasForced) const;
 
+  /// Evaluate a fixup to a relocatable expression and the value which should be
+  /// placed into the fixup. Same as evaluateFixup, but does not check if the
+  /// target needs to force the relocation.
+  ///
+  /// \param Layout The layout to use for evaluation.
+  /// \param Fixup The fixup to evaluate.
+  /// \param DF The fragment the fixup is inside.
+  /// \param Target [out] On return, the relocatable expression the fixup
+  /// evaluates to.
+  /// \param Value [out] On return, the value of the fixup as currently laid
+  /// out.
+  /// \param ErrorMsg [out] On return, stores the message related to any error
+  /// raised while evaluating this fixup.
+  /// \return Whether the fixup value was fully resolved. This is true if the
+  /// \p Value result is fixed, otherwise the value may change due to
+  /// relocation.
+  bool evaluateFixupPreTarget(const MCAsmLayout &Layout, const MCFixup &Fixup,
+                              const MCFragment *DF, MCValue &Target,
+                              uint64_t &Value, std::string &Error) const;
+
   /// Check whether a fixup can be satisfied, or whether it needs to be relaxed
   /// (increased in size, in order to hold its value correctly).
   bool fixupNeedsRelaxation(const MCFixup &Fixup, const MCRelaxableFragment *DF,
                             const MCAsmLayout &Layout) const;
 
   /// Check whether the given fragment needs relaxation.
   bool fragmentNeedsRelaxation(const MCRelaxableFragment *IF,
                                const MCAsmLayout &Layout) const;
bool relaxDwarfCallFrameFragment(MCAsmLayout &Layout,
                                    MCDwarfCallFrameFragment &DF);
   bool relaxCVInlineLineTable(MCAsmLayout &Layout,
                               MCCVInlineLineTableFragment &DF);
   bool relaxCVDefRange(MCAsmLayout &Layout, MCCVDefRangeFragment &DF);
 
   /// finishLayout - Finalize a layout, including fragment lowering.
   void finishLayout(MCAsmLayout &Layout);
 
-  std::tuple<MCValue, uint64_t, bool>
-  handleFixup(const MCAsmLayout &Layout, MCFragment &F, const MCFixup &Fixup);
+  void handleUnresolvedFixup(const MCAsmLayout &Layout, MCFragment &F,
+                             const MCFixup &Fixup, const MCValue &Target,
+                             uint64_t &FixedValue);
 
 public:
   std::vector<std::pair<StringRef, const MCSymbol *>> Symvers;
 
   /// Construct a new assembler instance.
   //
   // FIXME: How are we going to parameterize this? Two obvious options are stay
   // concrete and require clients to pass in a target like object. The other

lib/MC/MCAssembler.cpp

const MCSymbol *MCAssembler::getAtom(const MCSymbol &S) const {
   // Otherwise, return the atom for the containing fragment.
   return S.getFragment()->getAtom();
 }
 
 bool MCAssembler::evaluateFixup(const MCAsmLayout &Layout,
                                 const MCFixup &Fixup, const MCFragment *DF,
                                 MCValue &Target, uint64_t &Value,
                                 bool &WasForced) const {
+  WasForced = false;
+  std::string ErrorMsg;
+  bool IsResolved =
+      evaluateFixupPreTarget(Layout, Fixup, DF, Target, Value, ErrorMsg);
+  if (!ErrorMsg.empty()) {
+    getContext().reportError(Fixup.getLoc(), ErrorMsg);
+    return true;
+  }
+  // Let the backend force a relocation if needed.
+  if (IsResolved) {
+    auto ShouldForce = getBackend().shouldForceRelocation(*this, Fixup, Target);
+    if (!ShouldForce.hasValue() || ShouldForce.getValue()) {
+      IsResolved = false;
+      WasForced = true;
+    }
+  }
+
+  return IsResolved;
+}
+
+bool MCAssembler::evaluateFixupPreTarget(const MCAsmLayout &Layout,
+                                         const MCFixup &Fixup,
+                                         const MCFragment *DF, MCValue &Target,
+                                         uint64_t &Value,
+                                         std::string &ErrorMsg) const {
   ++stats::evaluateFixup;
 
   // FIXME: This code has some duplication with recordRelocation. We should
   // probably merge the two into a single callback that tries to evaluate a
   // fixup and records a relocation if one is needed.
 
   // On error claim to have completely evaluated the fixup, to prevent any
   // further processing from being done.
   const MCExpr *Expr = Fixup.getValue();
-  MCContext &Ctx = getContext();
   Value = 0;
-  WasForced = false;
+  ErrorMsg = "";
   if (!Expr->evaluateAsRelocatable(Target, &Layout, &Fixup)) {
-    Ctx.reportError(Fixup.getLoc(), "expected relocatable expression");
+    ErrorMsg = "expected relocatable expression";
     return true;
   }
   if (const MCSymbolRefExpr *RefB = Target.getSymB()) {
     if (RefB->getKind() != MCSymbolRefExpr::VK_None) {
-      Ctx.reportError(Fixup.getLoc(),
-                      "unsupported subtraction of qualified symbol");
+      ErrorMsg = "unsupported subtraction of qualified symbol";
       return true;
     }
   }
 
   assert(getBackendPtr() && "Expected assembler backend");
   bool IsPCRel = getBackendPtr()->getFixupKindInfo(Fixup.getKind()).Flags &
                  MCFixupKindInfo::FKF_IsPCRel;
 
if (IsPCRel) {
     uint32_t Offset = Layout.getFragmentOffset(DF) + Fixup.getOffset();
 
     // A number of ARM fixups in Thumb mode require that the effective PC
     // address be determined as the 32-bit aligned version of the actual offset.
     if (ShouldAlignPC) Offset &= ~0x3;
     Value -= Offset;
   }
 
-  // Let the backend force a relocation if needed.
-  if (IsResolved && getBackend().shouldForceRelocation(*this, Fixup, Target)) {
-    IsResolved = false;
-    WasForced = true;
-  }
-
   return IsResolved;
 }
 
 uint64_t MCAssembler::computeFragmentSize(const MCAsmLayout &Layout,
                                           const MCFragment &F) const {
   assert(getBackendPtr() && "Requires assembler backend");
   switch (F.getKind()) {
   case MCFragment::FT_Data:
void MCAssembler::writeSectionData(raw_ostream &OS, const MCSection *Sec,
   (void)Start;
 
   for (const MCFragment &F : *Sec)
     writeFragment(OS, *this, Layout, F);
 
   assert(OS.tell() - Start == Layout.getSectionAddressSize(Sec));
 }
 
-std::tuple<MCValue, uint64_t, bool>
-MCAssembler::handleFixup(const MCAsmLayout &Layout, MCFragment &F,
-                         const MCFixup &Fixup) {
-  // Evaluate the fixup.
-  MCValue Target;
-  uint64_t FixedValue;
-  bool WasForced;
-  bool IsResolved = evaluateFixup(Layout, Fixup, &F, Target, FixedValue,
-                                  WasForced);
-  if (!IsResolved) {
-    // The fixup was unresolved, we need a relocation. Inform the object
-    // writer of the relocation, and give it an opportunity to adjust the
-    // fixup value if need be.
-    if (Target.getSymA() && Target.getSymB() &&
-        getBackend().requiresDiffExpressionRelocations()) {
-      // The fixup represents the difference between two symbols, which the
-      // backend has indicated must be resolved at link time. Split up the fixup
-      // into two relocations, one for the add, and one for the sub, and emit
-      // both of these. The constant will be associated with the add half of the
-      // expression.
-      MCFixup FixupAdd = MCFixup::createAddFor(Fixup);
-      MCValue TargetAdd =
-          MCValue::get(Target.getSymA(), nullptr, Target.getConstant());
-      getWriter().recordRelocation(*this, Layout, &F, FixupAdd, TargetAdd,
-                                   FixedValue);
-      MCFixup FixupSub = MCFixup::createSubFor(Fixup);
-      MCValue TargetSub = MCValue::get(Target.getSymB());
-      getWriter().recordRelocation(*this, Layout, &F, FixupSub, TargetSub,
-                                   FixedValue);
-    } else {
-      getWriter().recordRelocation(*this, Layout, &F, Fixup, Target,
-                                   FixedValue);
-    }
-  }
-  return std::make_tuple(Target, FixedValue, IsResolved);
-}
+void MCAssembler::handleUnresolvedFixup(const MCAsmLayout &Layout,
+                                        MCFragment &F, const MCFixup &Fixup,
+                                        const MCValue &Target,
+                                        uint64_t &FixedValue) {
+    getWriter().recordRelocation(*this, Layout, &F, Fixup, Target, FixedValue);
 
 void MCAssembler::layout(MCAsmLayout &Layout) {
   assert(getBackendPtr() && "Expected assembler backend");
   DEBUG_WITH_TYPE("mc-dump", {
       errs() << "assembler backend - pre-layout\n--\n";
       dump(); });
 
   // Create dummy fragments and assign section ordinals.
for (MCFragment &Frag : Sec) {
         // Insert fixup type for code alignment if the target define
         // shouldInsertFixupForCodeAlign target hook.
         if (Sec.UseCodeAlign() && AF->hasEmitNops()) {
           getBackend().shouldInsertFixupForCodeAlign(*this, Layout, *AF);
         }
         continue;
       } else
         llvm_unreachable("Unknown fragment with fixups!");
+
+      // Unknown fixups are fixups for which the target does not yet know if a
+      // relocation should be forced or not. These should be re-evaluated after
+      // all fixups in this section have been processed.
+      DenseSet<const MCFixup *> UnknownFixups;
+      // Fixups that have been completely evaluated, along with whether or not
+      // they can been resolved without a relocation.
+      DenseMap<const MCFixup *, bool> EvaluatedFixups;
+      // Store data for all fixups to avoid re-evaluating on the second pass.
+      // Should be iterated over in the same order the fixups were originally
+      // encountered - hence the use of a MapVector.
+      MapVector<const MCFixup *, std::tuple<MCValue, uint64_t, std::string>>
+          FixupsData;
+
       for (const MCFixup &Fixup : Fixups) {
+        MCValue Target;
         uint64_t FixedValue;
-        bool IsResolved;
+        std::string ErrorMsg;
+        bool IsResolved = evaluateFixupPreTarget(Layout, Fixup, &Frag, Target,
+                                                 FixedValue, ErrorMsg);
+        if (IsResolved && ErrorMsg.empty()) {
+          auto WasForced =
+              getBackend().shouldForceRelocation(*this, Fixup, Target);
+          if (!WasForced.hasValue()) {
+            // The target indicated that it doesn't know whether to force a
+            // relocation for this fixup.
+            UnknownFixups.insert(&Fixup);
+            FixupsData[&Fixup] = {Target, FixedValue, ErrorMsg};
+            continue;
+          }
+          if (WasForced.getValue())
+            IsResolved = false;
+        }
+        EvaluatedFixups[&Fixup] = IsResolved;
+        FixupsData[&Fixup] = {Target, FixedValue, ErrorMsg};
+      }
+
+      // Allow the target to clear the unknown fixups.
+      getBackend().handleUnknownFixups(UnknownFixups, EvaluatedFixups);
+      assert(UnknownFixups.empty() && "Target failed to categorize all fixups");
+
+      // Now actions for all fixups are known, we can record relocations where
+      // necessary and apply fixups.
+      for (auto &FixupDataEntry : FixupsData) {
+        const MCFixup *Fixup = FixupDataEntry.first;
+        bool IsResolved = EvaluatedFixups[Fixup];
+
         MCValue Target;
-        std::tie(Target, FixedValue, IsResolved) =
-            handleFixup(Layout, Frag, Fixup);
-        getBackend().applyFixup(*this, Fixup, Target, Contents, FixedValue,
+        uint64_t FixedValue;
+        std::string ErrorMsg;
+        std::tie(Target, FixedValue, ErrorMsg) = FixupDataEntry.second;
+        if (!ErrorMsg.empty())
+          getContext().reportError(Fixup->getLoc(), ErrorMsg);
+        if (!IsResolved)
+          handleUnresolvedFixup(Layout, Frag, *Fixup, Target, FixedValue);
+        getBackend().applyFixup(*this, *Fixup, Target, Contents, FixedValue,
                                 IsResolved, STI);
       }
     }
   }
 }
 
 void MCAssembler::Finish() {
   // Create the layout object.

lib/Target/AArch64/MCTargetDesc/AArch64AsmBackend.cpp

public:
   bool writeNopData(raw_ostream &OS, uint64_t Count) const override;
 
   void HandleAssemblerFlag(MCAssemblerFlag Flag) {}
 
   unsigned getPointerSize() const { return 8; }
 
   unsigned getFixupKindContainereSizeInBytes(unsigned Kind) const;
 
-  bool shouldForceRelocation(const MCAssembler &Asm, const MCFixup &Fixup,
+  Optional<bool> shouldForceRelocation(const MCAssembler &Asm,
+                                       const MCFixup &Fixup,
                                        const MCValue &Target) override;
 };
 
 } // end anonymous namespace
 
 /// The number of bytes the fixup may change.
 static unsigned getFixupKindNumBytes(unsigned Kind) {
   switch (Kind) {
   default:
bool AArch64AsmBackend::writeNopData(raw_ostream &OS, uint64_t Count) const {
 
   // We are properly aligned, so write NOPs as requested.
   Count /= 4;
   for (uint64_t i = 0; i != Count; ++i)
     support::endian::write<uint32_t>(OS, 0xd503201f, Endian);
   return true;
 }
 
-bool AArch64AsmBackend::shouldForceRelocation(const MCAssembler &Asm,
+Optional<bool> AArch64AsmBackend::shouldForceRelocation(const MCAssembler &Asm,
                                                         const MCFixup &Fixup,
                                                         const MCValue &Target) {
   // The ADRP instruction adds some multiple of 0x1000 to the current PC &
   // ~0xfff. This means that the required offset to reach a symbol can vary by
   // up to one step depending on where the ADRP is in memory. For example:
   //
   //     ADRP x0, there
   //  there:
   //
   // If the ADRP occurs at address 0xffc then "there" will be at 0x1000 and

lib/Target/ARM/MCTargetDesc/ARMAsmBackend.h

public:
   }
 
   // FIXME: this should be calculated per fragment as the STI may be
   // different.
   bool hasNOP() const { return STI.getFeatureBits()[ARM::HasV6T2Ops]; }
 
   const MCFixupKindInfo &getFixupKindInfo(MCFixupKind Kind) const override;
 
-  bool shouldForceRelocation(const MCAssembler &Asm, const MCFixup &Fixup,
+  Optional<bool> shouldForceRelocation(const MCAssembler &Asm,
+                                       const MCFixup &Fixup,
                                        const MCValue &Target) override;
 
   unsigned adjustFixupValue(const MCAssembler &Asm, const MCFixup &Fixup,
                             const MCValue &Target, uint64_t Value,
                             bool IsResolved, MCContext &Ctx,
                             const MCSubtargetInfo *STI) const;
 
   void applyFixup(const MCAssembler &Asm, const MCFixup &Fixup,
                   const MCValue &Target, MutableArrayRef<char> Data,

lib/Target/ARM/MCTargetDesc/ARMAsmBackend.cpp

case ARM::fixup_t2_so_imm: {
     EncValue |= (Value & 0x800) << 15;
     EncValue |= (Value & 0x700) << 4;
     EncValue |= (Value & 0xff);
     return swapHalfWords(EncValue, Endian == support::little);
   }
   }
 }
 
-bool ARMAsmBackend::shouldForceRelocation(const MCAssembler &Asm,
+Optional<bool> ARMAsmBackend::shouldForceRelocation(const MCAssembler &Asm,
                                                     const MCFixup &Fixup,
                                                     const MCValue &Target) {
   const MCSymbolRefExpr *A = Target.getSymA();
   const MCSymbol *Sym = A ? &A->getSymbol() : nullptr;
   const unsigned FixupKind = Fixup.getKind() ;
   if ((unsigned)Fixup.getKind() == ARM::fixup_arm_thumb_bl) {
     assert(Sym && "How did we resolve this?");
 
     // If the symbol is external the linker will handle it.
     // FIXME: Should we handle it as an optimization?

lib/Target/Hexagon/MCTargetDesc/HexagonAsmBackend.cpp

const MCFixupKindInfo &getFixupKindInfo(MCFixupKind Kind) const override {
     if (Kind < FirstTargetFixupKind)
       return MCAsmBackend::getFixupKindInfo(Kind);
 
     assert(unsigned(Kind - FirstTargetFixupKind) < getNumFixupKinds() &&
            "Invalid kind!");
     return Infos[Kind - FirstTargetFixupKind];
   }
 
-  bool shouldForceRelocation(const MCAssembler &Asm, const MCFixup &Fixup,
+  Optional<bool> shouldForceRelocation(const MCAssembler &Asm,
+                                       const MCFixup &Fixup,
                                        const MCValue &Target) override {
     MCFixupKind Kind = Fixup.getKind();
 
     switch((unsigned)Kind) {
       default:
         llvm_unreachable("Unknown Fixup Kind!");
 
       case fixup_Hexagon_LO16:
       case fixup_Hexagon_HI16:

lib/Target/Mips/MCTargetDesc/MipsAsmBackend.h

public:
   /// \param [out] Res On return, the relaxed instruction.
   void relaxInstruction(const MCInst &Inst, const MCSubtargetInfo &STI,
                         MCInst &Res) const override {}
 
   /// @}
 
   bool writeNopData(raw_ostream &OS, uint64_t Count) const override;
 
-  bool shouldForceRelocation(const MCAssembler &Asm, const MCFixup &Fixup,
+  Optional<bool> shouldForceRelocation(const MCAssembler &Asm,
+                                       const MCFixup &Fixup,
                                        const MCValue &Target) override;
 
   bool isMicroMips(const MCSymbol *Sym) const override;
 }; // class MipsAsmBackend
 
 } // namespace
 
 #endif

lib/Target/Mips/MCTargetDesc/MipsAsmBackend.cpp

bool MipsAsmBackend::writeNopData(raw_ostream &OS, uint64_t Count) const {
 
   // If the count is not 4-byte aligned, we must be writing data into the text
   // section (otherwise we have unaligned instructions, and thus have far
   // bigger problems), so just write zeros instead.
   OS.write_zeros(Count);
   return true;
 }
 
-bool MipsAsmBackend::shouldForceRelocation(const MCAssembler &Asm,
+Optional<bool> MipsAsmBackend::shouldForceRelocation(const MCAssembler &Asm,
                                                      const MCFixup &Fixup,
                                                      const MCValue &Target) {
   const unsigned FixupKind = Fixup.getKind();
   switch (FixupKind) {
   default:
     return false;
   // All these relocations require special processing
   // at linking time. Delegate this work to a linker.
   case Mips::fixup_Mips_CALL_HI16:
   case Mips::fixup_Mips_CALL_LO16:

lib/Target/PowerPC/MCTargetDesc/PPCAsmBackend.cpp

void applyFixup(const MCAssembler &Asm, const MCFixup &Fixup,
     // from the fixup value. The Value has been "split up" into the appropriate
     // bitfields above.
     for (unsigned i = 0; i != NumBytes; ++i) {
       unsigned Idx = Endian == support::little ? i : (NumBytes - 1 - i);
       Data[Offset + i] |= uint8_t((Value >> (Idx * 8)) & 0xff);
     }
   }
 
-  bool shouldForceRelocation(const MCAssembler &Asm, const MCFixup &Fixup,
+  Optional<bool> shouldForceRelocation(const MCAssembler &Asm,
+                                       const MCFixup &Fixup,
                                        const MCValue &Target) override {
     switch ((PPC::Fixups)Fixup.getKind()) {
     default:
       return false;
     case PPC::fixup_ppc_br24:
     case PPC::fixup_ppc_br24abs:
       // If the target symbol has a local entry point we must not attempt
       // to resolve the fixup directly.  Emit a relocation and leave
       // resolution of the final target address to the linker.

lib/Target/RISCV/MCTargetDesc/RISCVAsmBackend.h

public:
   void applyFixup(const MCAssembler &Asm, const MCFixup &Fixup,
                   const MCValue &Target, MutableArrayRef<char> Data,
                   uint64_t Value, bool IsResolved,
                   const MCSubtargetInfo *STI) const override;
 
   std::unique_ptr<MCObjectTargetWriter>
   createObjectTargetWriter() const override;
 
-  bool shouldForceRelocation(const MCAssembler &Asm, const MCFixup &Fixup,
+  Optional<bool> shouldForceRelocation(const MCAssembler &Asm,
+                                       const MCFixup &Fixup,
                                        const MCValue &Target) override;
 
+  void handleUnknownFixups(
+      DenseSet<const MCFixup *> &UnknownFixups,
+      DenseMap<const MCFixup *, bool> &EvaluatedFixups) override;
+
   bool fixupNeedsRelaxation(const MCFixup &Fixup, uint64_t Value,
                             const MCRelaxableFragment *DF,
                             const MCAsmLayout &Layout) const override {
     llvm_unreachable("Handled by fixupNeedsRelaxationAdvanced");
   }
 
   bool fixupNeedsRelaxationAdvanced(const MCFixup &Fixup, bool Resolved,
                                     uint64_t Value,

lib/Target/RISCV/MCTargetDesc/RISCVAsmBackend.cpp

 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 // If linker relaxation is enabled, or the relax option had previously been
 // enabled, always emit relocations even if the fixup can be resolved. This is
 // necessary for correctness as offsets may change during relaxation.
-bool RISCVAsmBackend::shouldForceRelocation(const MCAssembler &Asm,
+Optional<bool> RISCVAsmBackend::shouldForceRelocation(const MCAssembler &Asm,
                                                       const MCFixup &Fixup,
                                                       const MCValue &Target) {
   bool ShouldForce = false;
+  bool Unknown = false;
 
   switch ((unsigned)Fixup.getKind()) {
   default:
     break;
   case RISCV::fixup_riscv_got_hi20:
   case RISCV::fixup_riscv_tls_got_hi20:
   case RISCV::fixup_riscv_tls_gd_hi20:
     return true;
+  case RISCV::fixup_riscv_pcrel_hi20:
+    Unknown = true;
+    break;
   case RISCV::fixup_riscv_pcrel_lo12_i:
   case RISCV::fixup_riscv_pcrel_lo12_s:
-    // For pcrel_lo12, force a relocation if the target of the corresponding
-    // pcrel_hi20 is not in the same fragment.
     const MCFixup *T = cast<RISCVMCExpr>(Fixup.getValue())->getPCRelHiFixup();
     if (!T) {
       Asm.getContext().reportError(Fixup.getLoc(),
                                    "could not find corresponding %pcrel_hi");
       return false;
     }
 
     switch ((unsigned)T->getKind()) {
     default:
       llvm_unreachable("Unexpected fixup kind for pcrel_lo12");
       break;
     case RISCV::fixup_riscv_got_hi20:
     case RISCV::fixup_riscv_tls_got_hi20:
     case RISCV::fixup_riscv_tls_gd_hi20:
+      // %pcrel_lo/%{got,tls_ie,tls_gd}_pcrel_hi pairs should always force
+      // relocations.
       ShouldForce = true;
       break;
     case RISCV::fixup_riscv_pcrel_hi20:
-      ShouldForce = T->getValue()->findAssociatedFragment() !=
-                    Fixup.getValue()->findAssociatedFragment();
+      // %pcrel_lo/%pcrel_hi pairs may not need relocations, but evaluate this
+      // later.
+      Unknown = true;
       break;
     }
     break;
   }
 
-  return ShouldForce || STI.getFeatureBits()[RISCV::FeatureRelax] ||
-         ForceRelocs;
+  if (ShouldForce || STI.getFeatureBits()[RISCV::FeatureRelax] || ForceRelocs)
+    return true;
+  if (Unknown)
+    return None;
+  return false;
+}
+
+void RISCVAsmBackend::handleUnknownFixups(
+    DenseSet<const MCFixup *> &UnknownFixups,
+    DenseMap<const MCFixup *, bool> &EvaluatedFixups) {
+
+  DenseMap<const MCFixup *, bool> EvaluatedPCRelLoFixups;
+  for (const MCFixup *Fixup : UnknownFixups) {
+    switch ((unsigned)Fixup->getKind()) {
+    default:
+      llvm_unreachable("Currently only %pcrel_lo and %pcrel_hi should be "
+                       "handled as 'unknown' fixups.");
+    case RISCV::fixup_riscv_pcrel_hi20:
+      // Leave %pcrel_hi fixups to be evaluated later.
+      break;
+    case RISCV::fixup_riscv_pcrel_lo12_i:
+    case RISCV::fixup_riscv_pcrel_lo12_s:
+      const MCFixup *T =
+          cast<RISCVMCExpr>(Fixup->getValue())->getPCRelHiFixup();
+      if (UnknownFixups.count(T)) {
+        // The corresponding %pcrel_hi is also 'unknown', therefore there is no
+        // need to force relocation and the fixup can be resolved. The %pcrel_hi
+        // will also be marked as resolved later.
+        EvaluatedFixups[Fixup] = true;
+        EvaluatedPCRelLoFixups[Fixup] = true;
+      } else {
+        // Otherwise the only other option is that the %pcrel_hi was unresolved.
+        EvaluatedFixups[Fixup] = false;
+        EvaluatedPCRelLoFixups[Fixup] = false;
+      }
+      UnknownFixups.erase(Fixup);
+      break;
+    }
+  }
+  // Find any unknown %pcrel_hi's through their corresponding %pcrel_lo.
+  for (const auto &EvaluatedFixup : EvaluatedPCRelLoFixups) {
+    const MCFixup *Fixup = EvaluatedFixup.first;
+    switch ((unsigned)Fixup->getKind()) {
+    default:
+      break;
+    case RISCV::fixup_riscv_pcrel_lo12_i:
+    case RISCV::fixup_riscv_pcrel_lo12_s:
+      const MCFixup *T =
+          cast<RISCVMCExpr>(Fixup->getValue())->getPCRelHiFixup();
+      if (UnknownFixups.count(T)) {
+        // We now know whether to resolve the %pcrel_hi based on this %pcrel_lo.
+        EvaluatedFixups[T] = EvaluatedFixup.second;
+        UnknownFixups.erase(T);
+      }
+      break;
+    }
+  }
+
+  // All remaining unknowns must be a %pcrel_hi without a corresponding
+  // %pcrel_lo, so they can be safely resolved.
+  for (const MCFixup *Fixup : UnknownFixups) {
+    EvaluatedFixups[Fixup] = true;
+    UnknownFixups.erase(Fixup);
+  }
 }
 
 bool RISCVAsmBackend::fixupNeedsRelaxationAdvanced(const MCFixup &Fixup,
                                                    bool Resolved,
                                                    uint64_t Value,
                                                    const MCRelaxableFragment *DF,
                                                    const MCAsmLayout &Layout,
                                                    const bool WasForced) const {

lib/Target/Sparc/MCTargetDesc/SparcAsmBackend.cpp

const MCFixupKindInfo &getFixupKindInfo(MCFixupKind Kind) const override {
       assert(unsigned(Kind - FirstTargetFixupKind) < getNumFixupKinds() &&
              "Invalid kind!");
       if (Endian == support::little)
         return InfosLE[Kind - FirstTargetFixupKind];
 
       return InfosBE[Kind - FirstTargetFixupKind];
     }
 
-    bool shouldForceRelocation(const MCAssembler &Asm, const MCFixup &Fixup,
+    Optional<bool> shouldForceRelocation(const MCAssembler &Asm,
+                                         const MCFixup &Fixup,
                                          const MCValue &Target) override {
       switch ((Sparc::Fixups)Fixup.getKind()) {
       default:
         return false;
       case Sparc::fixup_sparc_wplt30:
         if (Target.getSymA()->getSymbol().isTemporary())
           return false;
         LLVM_FALLTHROUGH;
       case Sparc::fixup_sparc_tls_gd_hi22: