Index: include/llvm/MC/MCELFObjectWriter.h
===================================================================
--- include/llvm/MC/MCELFObjectWriter.h
+++ include/llvm/MC/MCELFObjectWriter.h
@@ -11,6 +11,7 @@
 #define LLVM_MC_MCELFOBJECTWRITER_H
 
 #include "llvm/ADT/Triple.h"
+#include "llvm/MC/MCValue.h"
 #include "llvm/Support/DataTypes.h"
 #include "llvm/Support/ELF.h"
 #include <vector>
@@ -31,10 +32,21 @@
   const MCSymbolELF *Symbol; // The symbol to relocate with.
   unsigned Type;   // The type of the relocation.
   uint64_t Addend; // The addend to use.
+  const MCSymbolELF *OriginalSymbol; // The original value of Symbol if we changed it.
+  uint64_t OriginalAddend; // The original value of addend.
 
   ELFRelocationEntry(uint64_t Offset, const MCSymbolELF *Symbol, unsigned Type,
-                     uint64_t Addend)
-      : Offset(Offset), Symbol(Symbol), Type(Type), Addend(Addend) {}
+                     uint64_t Addend, const MCSymbolELF *OriginalSymbol,
+                     uint64_t OriginalAddend)
+      : Offset(Offset), Symbol(Symbol), Type(Type), Addend(Addend),
+        OriginalSymbol(OriginalSymbol), OriginalAddend(OriginalAddend) {}
+
+  void print(raw_ostream &Out) const {
+    Out << "Off=" << Offset << ", Sym=" << Symbol << ", Type=" << Type
+        << ", Addend=" << Addend << ", OriginalSymbol=" << OriginalSymbol
+        << ", OriginalAddend=" << OriginalAddend;
+  }
+  void dump() const { print(errs()); }
 };
 
 class MCELFObjectTargetWriter {
Index: lib/MC/ELFObjectWriter.cpp
===================================================================
--- lib/MC/ELFObjectWriter.cpp
+++ lib/MC/ELFObjectWriter.cpp
@@ -690,6 +690,7 @@
   }
 
   unsigned Type = getRelocType(Ctx, Target, Fixup, IsPCRel);
+  uint64_t OriginalC = C;
   bool RelocateWithSymbol = shouldRelocateWithSymbol(Asm, RefA, SymA, C, Type);
   if (!RelocateWithSymbol && SymA && !SymA->isUndefined())
     C += Layout.getSymbolOffset(*SymA);
@@ -710,21 +711,24 @@
         ELFSec ? cast<MCSymbolELF>(ELFSec->getBeginSymbol()) : nullptr;
     if (SectionSymbol)
       SectionSymbol->setUsedInReloc();
-    ELFRelocationEntry Rec(FixupOffset, SectionSymbol, Type, Addend);
+    ELFRelocationEntry Rec(FixupOffset, SectionSymbol, Type, Addend, SymA,
+                           OriginalC);
     Relocations[&FixupSection].push_back(Rec);
     return;
   }
 
+  const auto *RenamedSymA = SymA;
   if (SymA) {
     if (const MCSymbolELF *R = Renames.lookup(SymA))
-      SymA = R;
+      RenamedSymA = R;
 
     if (ViaWeakRef)
-      SymA->setIsWeakrefUsedInReloc();
+      RenamedSymA->setIsWeakrefUsedInReloc();
     else
-      SymA->setUsedInReloc();
+      RenamedSymA->setUsedInReloc();
   }
-  ELFRelocationEntry Rec(FixupOffset, SymA, Type, Addend);
+  ELFRelocationEntry Rec(FixupOffset, RenamedSymA, Type, Addend, SymA,
+                         OriginalC);
   Relocations[&FixupSection].push_back(Rec);
 }
 
Index: lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp
===================================================================
--- lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp
+++ lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp
@@ -7,8 +7,11 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include <algorithm>
+#include <list>
 #include "MCTargetDesc/MipsBaseInfo.h"
 #include "MCTargetDesc/MipsFixupKinds.h"
+#include "MCTargetDesc/MipsMCExpr.h"
 #include "MCTargetDesc/MipsMCTargetDesc.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/MC/MCAssembler.h"
@@ -17,41 +20,187 @@
 #include "llvm/MC/MCSection.h"
 #include "llvm/MC/MCSymbolELF.h"
 #include "llvm/MC/MCValue.h"
+#include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 
+#define DEBUG_TYPE "mips-elf-object-writer"
+
 using namespace llvm;
 
 namespace {
-// A helper structure based on ELFRelocationEntry, used for sorting entries in
-// the relocation table.
+/// Holds additional information needed by the relocation ordering algorithm.
 struct MipsRelocationEntry {
-  MipsRelocationEntry(const ELFRelocationEntry &R)
-      : R(R), SortOffset(R.Offset), HasMatchingHi(false) {}
-  const ELFRelocationEntry R;
-  // SortOffset equals R.Offset except for the *HI16 relocations, for which it
-  // will be set based on the R.Offset of the matching *LO16 relocation.
-  int64_t SortOffset;
-  // True when this is a *LO16 relocation chosen as a match for a *HI16
-  // relocation.
-  bool HasMatchingHi;
+  const ELFRelocationEntry R; ///< The relocation.
+  bool Matched;               ///< Is this relocation part of a match.
+
+  MipsRelocationEntry(const ELFRelocationEntry &R) : R(R), Matched(false) {}
+
+  void print(raw_ostream &Out) const {
+    R.print(Out);
+    Out << ", Matched=" << Matched;
+  }
 };
 
-  class MipsELFObjectWriter : public MCELFObjectTargetWriter {
-  public:
-    MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI,
-                        bool _isN64, bool IsLittleEndian);
+raw_ostream &operator<<(raw_ostream &OS, const MipsRelocationEntry &RHS) {
+  RHS.print(OS);
+  return OS;
+}
+
+class MipsELFObjectWriter : public MCELFObjectTargetWriter {
+public:
+  MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI, bool _isN64,
+                      bool IsLittleEndian);
 
-    ~MipsELFObjectWriter() override;
+  ~MipsELFObjectWriter() override;
 
-    unsigned getRelocType(MCContext &Ctx, const MCValue &Target,
-                          const MCFixup &Fixup, bool IsPCRel) const override;
-    bool needsRelocateWithSymbol(const MCSymbol &Sym,
-                                 unsigned Type) const override;
-    virtual void sortRelocs(const MCAssembler &Asm,
-                            std::vector<ELFRelocationEntry> &Relocs) override;
-  };
+  unsigned getRelocType(MCContext &Ctx, const MCValue &Target,
+                        const MCFixup &Fixup, bool IsPCRel) const override;
+  bool needsRelocateWithSymbol(const MCSymbol &Sym,
+                               unsigned Type) const override;
+  virtual void sortRelocs(const MCAssembler &Asm,
+                          std::vector<ELFRelocationEntry> &Relocs) override;
+};
+
+/// Copy elements in the range [First, Last) to d1 when the predicate is true or
+/// d2 when the predicate is false. This is essentially both std::copy_if and
+/// std::remove_copy_if combined into a single pass.
+template <class InputIt, class OutputIt1, class OutputIt2, class UnaryPredicate>
+std::pair<OutputIt1, OutputIt2> copy_if_else(InputIt First, InputIt Last,
+                                             OutputIt1 d1, OutputIt2 d2,
+                                             UnaryPredicate Predicate) {
+  for (InputIt I = First; I != Last; ++I) {
+    if (Predicate(*I)) {
+      *d1 = *I;
+      d1++;
+    } else {
+      *d2 = *I;
+      d2++;
+    }
+  }
+
+  return std::make_pair(d1, d2);
 }
 
+/// The possible results of the Predicate function used by find_best.
+enum FindBestPredicateResult {
+  FindBest_NoMatch = 0, ///< The current element is not a match.
+  FindBest_Match,       ///< The current element is a match but better ones are possible.
+  FindBest_PerfectMatch, ///< The current element is an unbeatable match.
+};
+
+/// Find the best match in the range [First, Last).
+///
+/// An element matches when Predicate(X) returns FindBest_Match or
+/// FindBest_PerfectMatch. A value of FindBest_PerfectMatch also terminates
+/// the search. BetterThan(A, B) is a comparator that returns true when A is a
+/// better match than B. The return value is the position of the best match.
+///
+/// This is similar to std::find_if but finds the best of multiple possible
+/// matches.
+template <class InputIt, class UnaryPredicate, class Comparator>
+InputIt find_best(InputIt First, InputIt Last, UnaryPredicate Predicate,
+                  Comparator BetterThan) {
+  InputIt Best = Last;
+
+  for (InputIt I = First; I != Last; ++I) {
+    unsigned Matched = Predicate(*I);
+    if (Matched != FindBest_NoMatch) {
+      DEBUG(dbgs() << std::distance(First, I) << " is a match (";
+            I->print(dbgs()); dbgs() << ")\n");
+      if (Best == Last || BetterThan(*I, *Best)) {
+        DEBUG(dbgs() << ".. and it beats the last one\n");
+        Best = I;
+      }
+    }
+    if (Matched == FindBest_PerfectMatch) {
+      DEBUG(dbgs() << ".. and it is unbeatable\n");
+      break;
+    }
+  }
+
+  return Best;
+}
+
+/// Determine the low relocation that matches the given relocation.
+/// If the relocation does not need a low relocation then the return value
+/// is ELF::R_MIPS_NONE.
+///
+/// The relocations that need a matching low part are
+/// R_(MIPS|MICROMIPS|MIPS16)_HI16 for all symbols and
+/// R_(MIPS|MICROMIPS|MIPS16)_GOT16 for local symbols only.
+static unsigned getMatchingLoType(const ELFRelocationEntry &Reloc) {
+  unsigned Type = Reloc.Type;
+  if (Type == ELF::R_MIPS_HI16)
+    return ELF::R_MIPS_LO16;
+  if (Type == ELF::R_MICROMIPS_HI16)
+    return ELF::R_MICROMIPS_LO16;
+  if (Type == ELF::R_MIPS16_HI16)
+    return ELF::R_MIPS16_LO16;
+
+  if (Reloc.OriginalSymbol->getBinding() != ELF::STB_LOCAL)
+    return ELF::R_MIPS_NONE;
+
+  if (Type == ELF::R_MIPS_GOT16)
+    return ELF::R_MIPS_LO16;
+  if (Type == ELF::R_MICROMIPS_GOT16)
+    return ELF::R_MICROMIPS_LO16;
+  if (Type == ELF::R_MIPS16_GOT16)
+    return ELF::R_MIPS16_LO16;
+
+  return ELF::R_MIPS_NONE;
+}
+
+/// Determine whether a relocation (X) matches the one given in R.
+///
+/// A relocation matches if:
+/// - It's type that of a corresponding low part. This is provided in
+///   MatchingType for efficiency.
+/// - It's based on the same symbol.
+/// - It's offset of greater or equal to that of the one given in R.
+///   It should be noted that this rule assumes the programmer does not use
+///   offsets that exceed the alignment of the symbol. The carry-bit will be
+///   incorrect if this is not true.
+///
+/// A matching relocation is unbeatable if:
+/// - It is not already involved in a match.
+/// - It's offset is exactly that of the one given in R.
+static bool isMatchingReloc(const MipsRelocationEntry &X,
+                            const ELFRelocationEntry &R,
+                            unsigned MatchingType) {
+  if (X.R.Type == MatchingType && X.R.OriginalSymbol == R.OriginalSymbol) {
+    if (!X.Matched &&
+        X.R.OriginalAddend == R.OriginalAddend)
+      return FindBest_PerfectMatch;
+    else if (X.R.OriginalAddend >= R.OriginalAddend)
+      return FindBest_Match;
+  }
+  return FindBest_NoMatch;
+};
+
+/// Determine whether Candidate or PreviousBest is the better match.
+/// The return value is true if Candidate is the better match.
+///
+/// A matching relocation is a better match if:
+/// - It has a smaller addend.
+/// - It is not already involved in a match.
+static bool compareMatchingRelocs(const MipsRelocationEntry &Candidate,
+                                  const MipsRelocationEntry &PreviousBest) {
+  if (Candidate.R.OriginalAddend != PreviousBest.R.OriginalAddend)
+    return Candidate.R.OriginalAddend < PreviousBest.R.OriginalAddend;
+  return PreviousBest.Matched && !Candidate.Matched;
+}
+
+#ifndef NDEBUG
+/// Print all the relocations.
+template <class Container>
+static void dumpRelocs(const char *Prefix, const Container &Relocs) {
+  for (const auto &R : Relocs)
+    dbgs() << Prefix << R << "\n";
+}
+#endif
+
+} // end anonymous namespace
+
 MipsELFObjectWriter::MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI,
                                          bool _isN64, bool IsLittleEndian)
     : MCELFObjectTargetWriter(_is64Bit, OSABI, ELF::EM_MIPS,
@@ -216,177 +365,110 @@
   llvm_unreachable("invalid fixup kind!");
 }
 
-// Sort entries by SortOffset in descending order.
-// When there are more *HI16 relocs paired with one *LO16 reloc, the 2nd rule
-// sorts them in ascending order of R.Offset.
-static int cmpRelMips(const MipsRelocationEntry *AP,
-                      const MipsRelocationEntry *BP) {
-  const MipsRelocationEntry &A = *AP;
-  const MipsRelocationEntry &B = *BP;
-  if (A.SortOffset != B.SortOffset)
-    return B.SortOffset - A.SortOffset;
-  if (A.R.Offset != B.R.Offset)
-    return A.R.Offset - B.R.Offset;
-  if (B.R.Type != A.R.Type)
-    return B.R.Type - A.R.Type;
-  //llvm_unreachable("ELFRelocs might be unstable!");
-  return 0;
-}
-
-// For the given Reloc.Type, return the matching relocation type, as in the
-// table below.
-static unsigned getMatchingLoType(const MCAssembler &Asm,
-                                  const ELFRelocationEntry &Reloc) {
-  unsigned Type = Reloc.Type;
-  if (Type == ELF::R_MIPS_HI16)
-    return ELF::R_MIPS_LO16;
-  if (Type == ELF::R_MICROMIPS_HI16)
-    return ELF::R_MICROMIPS_LO16;
-  if (Type == ELF::R_MIPS16_HI16)
-    return ELF::R_MIPS16_LO16;
-
-  if (Reloc.Symbol->getBinding() != ELF::STB_LOCAL)
-    return ELF::R_MIPS_NONE;
-
-  if (Type == ELF::R_MIPS_GOT16)
-    return ELF::R_MIPS_LO16;
-  if (Type == ELF::R_MICROMIPS_GOT16)
-    return ELF::R_MICROMIPS_LO16;
-  if (Type == ELF::R_MIPS16_GOT16)
-    return ELF::R_MIPS16_LO16;
-
-  return ELF::R_MIPS_NONE;
-}
-
-// Return true if First needs a matching *LO16, its matching *LO16 type equals
-// Second's type and both relocations are against the same symbol.
-static bool areMatchingHiAndLo(const MCAssembler &Asm,
-                               const ELFRelocationEntry &First,
-                               const ELFRelocationEntry &Second) {
-  return getMatchingLoType(Asm, First) != ELF::R_MIPS_NONE &&
-         getMatchingLoType(Asm, First) == Second.Type &&
-         First.Symbol && First.Symbol == Second.Symbol;
-}
-
-// Return true if MipsRelocs[Index] is a *LO16 preceded by a matching *HI16.
-static bool
-isPrecededByMatchingHi(const MCAssembler &Asm, uint32_t Index,
-                       std::vector<MipsRelocationEntry> &MipsRelocs) {
-  return Index < MipsRelocs.size() - 1 &&
-         areMatchingHiAndLo(Asm, MipsRelocs[Index + 1].R, MipsRelocs[Index].R);
-}
-
-// Return true if MipsRelocs[Index] is a *LO16 not preceded by a matching *HI16
-// and not chosen by a *HI16 as a match.
-static bool isFreeLo(const MCAssembler &Asm, uint32_t Index,
-                     std::vector<MipsRelocationEntry> &MipsRelocs) {
-  return Index < MipsRelocs.size() && !MipsRelocs[Index].HasMatchingHi &&
-         !isPrecededByMatchingHi(Asm, Index, MipsRelocs);
-}
-
-// Lo is chosen as a match for Hi, set their fields accordingly.
-// Mips instructions have fixed length of at least two bytes (two for
-// micromips/mips16, four for mips32/64), so we can set HI's SortOffset to
-// matching LO's Offset minus one to simplify the sorting function.
-static void setMatch(MipsRelocationEntry &Hi, MipsRelocationEntry &Lo) {
-  Lo.HasMatchingHi = true;
-  Hi.SortOffset = Lo.R.Offset - 1;
-}
-
-// We sort relocation table entries by offset, except for one additional rule
-// required by MIPS ABI: every *HI16 relocation must be immediately followed by
-// the corresponding *LO16 relocation. We also support a GNU extension that
-// allows more *HI16s paired with one *LO16.
-//
-// *HI16 relocations and their matching *LO16 are:
-//
-// +---------------------------------------------+-------------------+
-// |               *HI16                         |  matching *LO16   |
-// |---------------------------------------------+-------------------|
-// |  R_MIPS_HI16, local R_MIPS_GOT16            |    R_MIPS_LO16    |
-// |  R_MICROMIPS_HI16, local R_MICROMIPS_GOT16  | R_MICROMIPS_LO16  |
-// |  R_MIPS16_HI16, local R_MIPS16_GOT16        |  R_MIPS16_LO16    |
-// +---------------------------------------------+-------------------+
-//
-// (local R_*_GOT16 meaning R_*_GOT16 against the local symbol.)
-//
-// To handle *HI16 and *LO16 relocations, the linker needs a combined addend
-// ("AHL") calculated from both *HI16 ("AHI") and *LO16 ("ALO") relocations:
-// AHL = (AHI << 16) + (short)ALO;
-//
-// We are reusing gnu as sorting algorithm so we are emitting the relocation
-// table sorted the same way as gnu as would sort it, for easier comparison of
-// the generated .o files.
-//
-// The logic is:
-// search the table (starting from the highest offset and going back to zero)
-// for all *HI16 relocations that don't have a matching *LO16.
-// For every such HI, find a matching LO with highest offset that isn't already
-// matched with another HI. If there are no free LOs, match it with the first
-// found (starting from lowest offset).
-// When there are more HIs matched with one LO, sort them in descending order by
-// offset.
-//
-// In other words, when searching for a matching LO:
-// - don't look for a 'better' match for the HIs that are already followed by a
-//   matching LO;
-// - prefer LOs without a pair;
-// - prefer LOs with higher offset;
-
-static int cmpRel(const ELFRelocationEntry *AP, const ELFRelocationEntry *BP) {
-  const ELFRelocationEntry &A = *AP;
-  const ELFRelocationEntry &B = *BP;
-  if (A.Offset < B.Offset)
-    return 1;
-  if (A.Offset > B.Offset)
-    return -1;
-  assert(B.Type != A.Type && "We don't have a total order");
-  return A.Type - B.Type;
-}
-
+/// Sort relocation table entries by offset except where another order is
+/// required by the MIPS ABI.
+///
+/// MIPS has a few relocations that have an AHL component in the expression used
+/// to evaluate them. This AHL component is an addend with the same number of
+/// bits as a symbol value but not all of our ABI's are able to supply a
+/// sufficiently sized addend in a single relocation.
+///
+/// The O32 ABI for example, uses REL relocations which store the addend in the
+/// section data. All the relocations with AHL components affect 16-bit fields
+/// so the addend for a single relocation is limited to 16-bit. This ABI
+/// resolves the limitation by linking relocations (e.g. R_MIPS_HI16 and
+/// R_MIPS_LO16) and distributing the addend between the linked relocations. The
+/// ABI mandates that such relocations must be next to each other in a
+/// particular order (e.g. R_MIPS_HI16 must be immediately followed by a
+/// matching R_MIPS_LO16) but the rule is less strict in practice.
+///
+/// The de facto standard is lenient in the following ways:
+/// - 'Immediately following' does not refer to the next relocation entry but
+///   the next matching relocation.
+/// - There may be multiple high parts relocations for one low part relocation.
+/// - There may be multiple low part relocations for one high part relocation.
+/// - The AHL addend in each part does not have to be exactly equal as long as
+///   the difference does not affect the carry bit from bit 15 into 16. This is
+///   to allow, for example, the use of %lo(foo) and %lo(foo+4) when loading
+///   both halves of a long long.
+///
+/// See getMatchingLoType() for a description of which high part relocations
+/// match which low part relocations. One particular thing to note is that
+/// R_MIPS_GOT16 and similar only have AHL addends if they refer to local
+/// symbols.
+///
+/// It should also be noted that this function is not affected by whether
+/// the symbol was kept or rewritten into a section-relative equivalent. We
+/// always match using the expressions from the source.
 void MipsELFObjectWriter::sortRelocs(const MCAssembler &Asm,
                                      std::vector<ELFRelocationEntry> &Relocs) {
   if (Relocs.size() < 2)
     return;
 
-  // Sorts entries by Offset in descending order.
-  array_pod_sort(Relocs.begin(), Relocs.end(), cmpRel);
-
-  // Init MipsRelocs from Relocs.
-  std::vector<MipsRelocationEntry> MipsRelocs;
-  for (unsigned I = 0, E = Relocs.size(); I != E; ++I)
-    MipsRelocs.push_back(MipsRelocationEntry(Relocs[I]));
-
-  // Find a matching LO for all HIs that need it.
-  for (int32_t I = 0, E = MipsRelocs.size(); I != E; ++I) {
-    if (getMatchingLoType(Asm, MipsRelocs[I].R) == ELF::R_MIPS_NONE ||
-        (I > 0 && isPrecededByMatchingHi(Asm, I - 1, MipsRelocs)))
-      continue;
-
-    int32_t MatchedLoIndex = -1;
-
-    // Search the list in the ascending order of Offset.
-    for (int32_t J = MipsRelocs.size() - 1, N = -1; J != N; --J) {
-      // check for a match
-      if (areMatchingHiAndLo(Asm, MipsRelocs[I].R, MipsRelocs[J].R) &&
-          (MatchedLoIndex == -1 || // first match
-           // or we already have a match,
-           // but this one is with higher offset and it's free
-           (MatchedLoIndex > J && isFreeLo(Asm, J, MipsRelocs))))
-        MatchedLoIndex = J;
-    }
-
-    if (MatchedLoIndex != -1)
-      // We have a match.
-      setMatch(MipsRelocs[I], MipsRelocs[MatchedLoIndex]);
+  // Sort relocations by the address they are applied to.
+  std::sort(Relocs.begin(), Relocs.end(),
+            [](const ELFRelocationEntry &A, const ELFRelocationEntry &B) {
+              return A.Offset < B.Offset;
+            });
+
+  std::list<MipsRelocationEntry> Sorted;
+  std::list<ELFRelocationEntry> Remainder;
+
+  DEBUG(dumpRelocs("R: ", Relocs));
+
+  // Separate the movable relocations (AHL relocations using the high bits) from
+  // the immobile relocations (everything else). This does not preserve high/low
+  // matches that already existed in the input.
+  copy_if_else(Relocs.begin(), Relocs.end(), std::back_inserter(Remainder),
+               std::back_inserter(Sorted), [](const ELFRelocationEntry &Reloc) {
+                 return getMatchingLoType(Reloc) != ELF::R_MIPS_NONE;
+               });
+
+  for (auto &R : Remainder) {
+    DEBUG(dbgs() << "Matching: " << R << "\n");
+
+    unsigned MatchingType = getMatchingLoType(R);
+    assert(MatchingType != ELF::R_MIPS_NONE &&
+           "Wrong list for reloc that doesn't need a match");
+
+    // Find the best matching relocation for the current high part.
+    // See isMatchingReloc for a description of a matching relocation and
+    // compareMatchingRelocs for a description of what 'best' means.
+    auto InsertionPoint =
+        find_best(Sorted.begin(), Sorted.end(),
+                  [&R, &MatchingType](const MipsRelocationEntry &X) {
+                    return isMatchingReloc(X, R, MatchingType);
+                  },
+                  compareMatchingRelocs);
+
+    // If we matched then insert the high part in front of the match and mark
+    // both relocations as being involved in a match. We only mark the high
+    // part for cosmetic reasons in the debug output.
+    //
+    // If we failed to find a match then the high part is orphaned. This is not
+    // permitted since the relocation cannot be evaluated without knowing the
+    // carry-in. We can sometimes handle this using a matching low part that is
+    // already used in a match but we already cover that case in
+    // isMatchingReloc and compareMatchingRelocs. For the remaining cases we
+    // should insert the high part at the end of the list. This will cause the
+    // linker to fail but the alternative is to cause the linker to bind the
+    // high part to a semi-matching low part and silently calculate the wrong
+    // value. Unfortunately we have no means to warn the user that we did this
+    // so leave it up to the linker to complain about it.
+    if (InsertionPoint != Sorted.end())
+      InsertionPoint->Matched = true;
+    Sorted.insert(InsertionPoint, R)->Matched = true;
   }
 
-  // SortOffsets are calculated, call the sorting function.
-  array_pod_sort(MipsRelocs.begin(), MipsRelocs.end(), cmpRelMips);
+  DEBUG(dumpRelocs("S: ", Sorted));
+
+  assert(Relocs.size() == Sorted.size() && "Some relocs were not consumed");
 
-  // Copy sorted MipsRelocs back to Relocs.
-  for (unsigned I = 0, E = MipsRelocs.size(); I != E; ++I)
-    Relocs[I] = MipsRelocs[I].R;
+  // Overwrite the original vector with the sorted elements. The caller expects
+  // them in reverse order.
+  unsigned CopyTo = 0;
+  for (const auto &R : reverse(Sorted))
+    Relocs[CopyTo++] = R.R;
 }
 
 bool MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbol &Sym,
Index: test/MC/Mips/sort-relocation-table.s
===================================================================
--- test/MC/Mips/sort-relocation-table.s
+++ test/MC/Mips/sort-relocation-table.s
@@ -1,125 +1,398 @@
 # RUN: llvm-mc -filetype=obj -arch mipsel %s | llvm-readobj -r | FileCheck %s
 
 # Test the order of records in the relocation table.
-# *HI16 and local *GOT16 relocations should be immediately followed by the
-# corresponding *LO16 relocation against the same symbol.
 #
-# We try to implement the same semantics as gas, ie. to order the relocation
-# table the same way as gas.
+# MIPS has a few relocations that have an AHL component in the expression used
+# to evaluate them. This AHL component is an addend with the same number of
+# bits as a symbol value but not all of our ABI's are able to supply a
+# sufficiently sized addend in a single relocation.
 #
-# gnu as command line:
-# mips-linux-gnu-as -EL sort-relocation-table.s -o sort-relocation-table.o
+# The O32 ABI for example, uses REL relocations which store the addend in the
+# section data. All the relocations with AHL components affect 16-bit fields
+# so the addend is limited to 16-bit. This ABI resolves the limitation by
+# linking relocations (e.g. R_MIPS_HI16 and R_MIPS_LO16) and distributing the
+# addend between the linked relocations. The ABI mandates that such relocations
+# must be next to each other in a particular order (e.g. R_MIPS_HI16 must be
+# followed by a matching R_MIPS_LO16) but the rule is less strict in practice.
+#
+# See MipsELFObjectWriter.cpp for a full description of the rules.
 #
 # TODO: Add mips16 and micromips tests.
-# Note: offsets are part of expected output, so it's simpler to add new test
-#       cases at the bottom of the file.
 
-# CHECK:       Relocations [
-# CHECK-NEXT:  {
+# HILO 1: HI/LO already match
+	.section .mips_hilo_1, "ax", @progbits
+	lui $2, %hi(sym1)
+	addiu $2, $2, %lo(sym1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_1 {
+# CHECK-NEXT:    0x0 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x4 R_MIPS_LO16 sym1
+# CHECK-NEXT:  }
 
-# Put HI before LO.
-addiu $2,$2,%lo(sym1)
-lui $2,%hi(sym1)
+# HILO 2: R_MIPS_HI16 must be followed by a matching R_MIPS_LO16.
+	.section .mips_hilo_2, "ax", @progbits
+	addiu $2, $2, %lo(sym1)
+	lui $2, %hi(sym1)
 
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_2 {
 # CHECK-NEXT:    0x4 R_MIPS_HI16 sym1
 # CHECK-NEXT:    0x0 R_MIPS_LO16 sym1
+# CHECK-NEXT:  }
+
+# HILO 3: R_MIPS_HI16 must be followed by a matching R_MIPS_LO16.
+#         The second relocation matches if the symbol is the same.
+	.section .mips_hilo_3, "ax", @progbits
+	addiu $2, $2, %lo(sym1)
+	lui $2, %hi(sym2)
+	addiu $2, $2, %lo(sym2)
+	lui $2, %hi(sym1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_3 {
+# CHECK-NEXT:    0xC R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 sym1
+# CHECK-NEXT:    0x4 R_MIPS_HI16 sym2
+# CHECK-NEXT:    0x8 R_MIPS_LO16 sym2
+# CHECK-NEXT:  }
 
-# When searching for a matching LO, ignore LOs against a different symbol.
-addiu $2,$2,%lo(sym2)
-lui $2,%hi(sym2)
-addiu $2,$2,%lo(sym2_d)
+# HILO 3b: Same as 3 but a different starting order.
+	.section .mips_hilo_3b, "ax", @progbits
+	addiu $2, $2, %lo(sym1)
+	lui $2, %hi(sym1)
+	addiu $2, $2, %lo(sym2)
+	lui $2, %hi(sym2)
 
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_3b {
+# CHECK-NEXT:    0x4 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 sym1
 # CHECK-NEXT:    0xC R_MIPS_HI16 sym2
 # CHECK-NEXT:    0x8 R_MIPS_LO16 sym2
-# CHECK-NEXT:    0x10 R_MIPS_LO16 sym2_d
-
-# Match HI with 2nd LO because it has higher offset (than the 1st LO).
-addiu $2,$2,%lo(sym3)
-addiu $2,$2,%lo(sym3)
-lui $2,%hi(sym3)
-
-# CHECK-NEXT:    0x14 R_MIPS_LO16 sym3
-# CHECK-NEXT:    0x1C R_MIPS_HI16 sym3
-# CHECK-NEXT:    0x18 R_MIPS_LO16 sym3
-
-# HI is already followed by a matching LO, so don't look further, ie. ignore the
-# "free" LO with higher offset.
-lui $2,%hi(sym4)
-addiu $2,$2,%lo(sym4)
-addiu $2,$2,%lo(sym4)
-
-# CHECK-NEXT:    0x20 R_MIPS_HI16 sym4
-# CHECK-NEXT:    0x24 R_MIPS_LO16 sym4
-# CHECK-NEXT:    0x28 R_MIPS_LO16 sym4
-
-# Match 2nd HI with 2nd LO, since it's the one with highest offset among the
-# "free" ones.
-addiu $2,$2,%lo(sym5)
-addiu $2,$2,%lo(sym5)
-lui $2,%hi(sym5)
-addiu $2,$2,%lo(sym5)
-lui $2,%hi(sym5)
-
-# CHECK-NEXT:    0x2C R_MIPS_LO16 sym5
-# CHECK-NEXT:    0x3C R_MIPS_HI16 sym5
-# CHECK-NEXT:    0x30 R_MIPS_LO16 sym5
-# CHECK-NEXT:    0x34 R_MIPS_HI16 sym5
-# CHECK-NEXT:    0x38 R_MIPS_LO16 sym5
-
-# When more HIs are matched with one LO, sort them in descending order of
-# offset.
-addiu $2,$2,%lo(sym6)
-lui $2,%hi(sym6)
-lui $2,%hi(sym6)
-
-# CHECK-NEXT:    0x48 R_MIPS_HI16 sym6
-# CHECK-NEXT:    0x44 R_MIPS_HI16 sym6
-# CHECK-NEXT:    0x40 R_MIPS_LO16 sym6
-
-#  sym7 is a local symbol, so GOT relocation against it needs a matching LO.
-sym7:
-addiu $2,$2,%lo(sym7)
-lui $2,%got(sym7)
-
-# CHECK-NEXT:    0x50 R_MIPS_GOT16 sym7
-# CHECK-NEXT:    0x4C R_MIPS_LO16 sym7
-
-# sym8 is not a local symbol, don't look for a matching LO for GOT.
-.global sym8
-addiu $2,$2,%lo(sym8)
-lui $2,%got(sym8)
-
-# CHECK-NEXT:    0x54 R_MIPS_LO16 sym8
-# CHECK-NEXT:    0x58 R_MIPS_GOT16 sym8
-
-# A small combination of previous checks.
-symc1:
-addiu $2,$2,%lo(symc1)
-addiu $2,$2,%lo(symc1)
-addiu $2,$2,%lo(symc1)
-lui $2,%hi(symc1)
-lui $2,%got(symc1)
-addiu $2,$2,%lo(symc2)
-lui $2,%hi(symc1)
-lui $2,%hi(symc1)
-lui $2,%got(symc2)
-lui $2,%hi(symc1)
-addiu $2,$2,%lo(symc1)
-addiu $2,$2,%lo(symc2)
-lui $2,%hi(symc1)
-lui $2,%hi(symc1)
-
-# CHECK-NEXT:    0x78 R_MIPS_HI16 symc1
-# CHECK-NEXT:    0x74 R_MIPS_HI16 symc1
-# CHECK-NEXT:    0x6C R_MIPS_GOT16 symc1
-# CHECK-NEXT:    0x68 R_MIPS_HI16 symc1
-# CHECK-NEXT:    0x5C R_MIPS_LO16 symc1
-# CHECK-NEXT:    0x8C R_MIPS_HI16 symc1
-# CHECK-NEXT:    0x60 R_MIPS_LO16 symc1
-# CHECK-NEXT:    0x90 R_MIPS_HI16 symc1
-# CHECK-NEXT:    0x64 R_MIPS_LO16 symc1
-# CHECK-NEXT:    0x70 R_MIPS_LO16 symc2
-# CHECK-NEXT:    0x7C R_MIPS_GOT16 symc2
-# CHECK-NEXT:    0x80 R_MIPS_HI16 symc1
-# CHECK-NEXT:    0x84 R_MIPS_LO16 symc1
-# CHECK-NEXT:    0x88 R_MIPS_LO16 symc2
+# CHECK-NEXT:  }
+
+# HILO 4: R_MIPS_HI16 must be followed by a matching R_MIPS_LO16.
+#         The second relocation matches if the symbol is the same and the
+#         offset is the same.
+	.section .mips_hilo_4, "ax", @progbits
+	addiu $2, $2, %lo(sym1)
+	addiu $2, $2, %lo(sym1+4)
+	lui $2, %hi(sym1+4)
+	lui $2, %hi(sym1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_4 {
+# CHECK-NEXT:    0xC R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 sym1
+# CHECK-NEXT:    0x8 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x4 R_MIPS_LO16 sym1
+# CHECK-NEXT:  }
+
+# HILO 5: R_MIPS_HI16 must be followed by a matching R_MIPS_LO16.
+#         The second relocation matches if the symbol is the same and the
+#         offset is greater or equal. Exact matches are preferred so both
+#         R_MIPS_HI16's match the same R_MIPS_LO16.
+	.section .mips_hilo_5, "ax", @progbits
+	lui $2, %hi(sym1)
+	lui $2, %hi(sym1)
+	addiu $2, $2, %lo(sym1+1)
+	addiu $2, $2, %lo(sym1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_5 {
+# CHECK-NEXT:    0x8 R_MIPS_LO16 sym1
+# CHECK-NEXT:    0x0 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x4 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0xC R_MIPS_LO16 sym1
+# CHECK-NEXT:  }
+
+# HILO 6: R_MIPS_HI16 must be followed by a matching R_MIPS_LO16.
+#         The second relocation matches if the symbol is the same and the
+#         offset is greater or equal. Smaller offsets are preferred so both
+#         R_MIPS_HI16's still match the same R_MIPS_LO16.
+	.section .mips_hilo_6, "ax", @progbits
+	lui $2, %hi(sym1)
+	lui $2, %hi(sym1)
+	addiu $2, $2, %lo(sym1+2)
+	addiu $2, $2, %lo(sym1+1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_6 {
+# CHECK-NEXT:    0x8 R_MIPS_LO16 sym1
+# CHECK-NEXT:    0x0 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x4 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0xC R_MIPS_LO16 sym1
+# CHECK-NEXT:  }
+
+# HILO 7: R_MIPS_HI16 must be followed by a matching R_MIPS_LO16.
+#         The second relocation matches if the symbol is the same and the
+#         offset is greater or equal so that the carry bit is correct. The two
+#         R_MIPS_HI16's therefore match different R_MIPS_LO16's.
+	.section .mips_hilo_7, "ax", @progbits
+	addiu $2, $2, %lo(sym1+1)
+	addiu $2, $2, %lo(sym1+6)
+	lui $2, %hi(sym1+4)
+	lui $2, %hi(sym1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_7 {
+# CHECK-NEXT:    0xC R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 sym1
+# CHECK-NEXT:    0x8 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x4 R_MIPS_LO16 sym1
+# CHECK-NEXT:  }
+
+# HILO 8: R_MIPS_LO16's may be orphaned.
+	.section .mips_hilo_8, "ax", @progbits
+	lw $2, %lo(sym1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_8 {
+# CHECK-NEXT:    0x0 R_MIPS_LO16 sym1
+# CHECK-NEXT:  }
+
+# HILO 8b: Another example of 8. The R_MIPS_LO16 at 0x4 is orphaned.
+	.section .mips_hilo_8b, "ax", @progbits
+	lw $2, %lo(sym1)
+	lw $2, %lo(sym1)
+	lui $2, %hi(sym1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_8b {
+# CHECK-NEXT:    0x8 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 sym1
+# CHECK-NEXT:    0x4 R_MIPS_LO16 sym1
+# CHECK-NEXT:  }
+
+# HILO 9: R_MIPS_HI16's don't need a matching R_MIPS_LO16 to immediately follow
+#         so long as there is one after the R_MIPS_HI16 somewhere. This isn't
+#         permitted by the ABI specification but has been allowed in practice
+#         for a very long time. The R_MIPS_HI16's should be ordered by the
+#         address they affect for purely cosmetic reasons.
+	.section .mips_hilo_9, "ax", @progbits
+	lw $2, %lo(sym1)
+	lui $2, %hi(sym1)
+	lui $2, %hi(sym1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_9 {
+# CHECK-NEXT:    0x4 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x8 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 sym1
+# CHECK-NEXT:  }
+
+# HILO 10: R_MIPS_HI16's must have a matching R_MIPS_LO16 somewhere though.
+#          When this is impossible we have two possible bad behaviours
+#          depending on the linker implementation:
+#          * The linker silently computes the wrong value using a partially
+#            matching R_MIPS_LO16.
+#          * The linker rejects the relocation table as invalid.
+#          The latter is preferable since it's far easier to detect and debug so
+#          check that we encourage this behaviour by putting invalid
+#          R_MIPS_HI16's at the end of the relocation table where the risk of a
+#          partial match is very low.
+	.section .mips_hilo_10, "ax", @progbits
+	lui $2, %hi(sym1)
+	lw $2, %lo(sym1)
+	lui $2, %hi(sym2)
+	lui $2, %hi(sym3)
+	lw $2, %lo(sym3)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_10 {
+# CHECK-NEXT:    0x0 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x4 R_MIPS_LO16 sym1
+# CHECK-NEXT:    0xC R_MIPS_HI16 sym3
+# CHECK-NEXT:    0x10 R_MIPS_LO16 sym3
+# CHECK-NEXT:    0x8 R_MIPS_HI16 sym2
+# CHECK-NEXT:  }
+
+# Now do the same tests for GOT/LO.
+# The rules only apply to R_MIPS_GOT16 on local symbols which are also
+# rewritten into section relative relocations.
+
+# GOTLO 1: GOT/LO already match
+	.section .mips_gotlo_1, "ax", @progbits
+	lui $2, %got(local1)
+	addiu $2, $2, %lo(local1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_1 {
+# CHECK-NEXT:    0x0 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x4 R_MIPS_LO16 local1
+# CHECK-NEXT:  }
+
+# GOTLO 2: R_MIPS_GOT16 must be followed by a matching R_MIPS_LO16.
+	.section .mips_gotlo_2, "ax", @progbits
+	addiu $2, $2, %lo(local1)
+	lui $2, %got(local1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_2 {
+# CHECK-NEXT:    0x4 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 local1
+# CHECK-NEXT:  }
+
+# GOTLO 3: R_MIPS_GOT16 must be followed by a matching R_MIPS_LO16.
+#          The second relocation matches if the symbol is the same.
+	.section .mips_gotlo_3, "ax", @progbits
+	addiu $2, $2, %lo(local1)
+	lui $2, %got(local2)
+	addiu $2, $2, %lo(local2)
+	lui $2, %got(local1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_3 {
+# CHECK-NEXT:    0xC R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 local1
+# CHECK-NEXT:    0x4 R_MIPS_GOT16 local2
+# CHECK-NEXT:    0x8 R_MIPS_LO16 local2
+# CHECK-NEXT:  }
+
+# GOTLO 3b: Same as 3 but a different starting order.
+	.section .mips_gotlo_3b, "ax", @progbits
+	addiu $2, $2, %lo(local1)
+	lui $2, %got(local1)
+	addiu $2, $2, %lo(local2)
+	lui $2, %got(local2)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_3b {
+# CHECK-NEXT:    0x4 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 local1
+# CHECK-NEXT:    0xC R_MIPS_GOT16 local2
+# CHECK-NEXT:    0x8 R_MIPS_LO16 local2
+# CHECK-NEXT:  }
+
+# GOTLO 4: R_MIPS_GOT16 must be followed by a matching R_MIPS_LO16.
+#          The second relocation matches if the symbol is the same and the
+#          offset is the same.
+	.section .mips_gotlo_4, "ax", @progbits
+	addiu $2, $2, %lo(local1)
+	addiu $2, $2, %lo(local1+4)
+	lui $2, %got(local1+4)
+	lui $2, %got(local1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_4 {
+# CHECK-NEXT:    0xC R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 local1
+# CHECK-NEXT:    0x8 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x4 R_MIPS_LO16 local1
+# CHECK-NEXT:  }
+
+# GOTLO 5: R_MIPS_GOT16 must be followed by a matching R_MIPS_LO16.
+#          The second relocation matches if the symbol is the same and the
+#          offset is greater or equal. Exact matches are preferred so both
+#          R_MIPS_GOT16's match the same R_MIPS_LO16.
+	.section .mips_gotlo_5, "ax", @progbits
+	lui $2, %got(local1)
+	lui $2, %got(local1)
+	addiu $2, $2, %lo(local1+1)
+	addiu $2, $2, %lo(local1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_5 {
+# CHECK-NEXT:    0x8 R_MIPS_LO16 local1
+# CHECK-NEXT:    0x0 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x4 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0xC R_MIPS_LO16 local1
+# CHECK-NEXT:  }
+
+# GOTLO 6: R_MIPS_GOT16 must be followed by a matching R_MIPS_LO16.
+#          The second relocation matches if the symbol is the same and the
+#          offset is greater or equal. Smaller offsets are preferred so both
+#          R_MIPS_GOT16's still match the same R_MIPS_LO16.
+	.section .mips_gotlo_6, "ax", @progbits
+	lui $2, %got(local1)
+	lui $2, %got(local1)
+	addiu $2, $2, %lo(local1+2)
+	addiu $2, $2, %lo(local1+1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_6 {
+# CHECK-NEXT:    0x8 R_MIPS_LO16 local1
+# CHECK-NEXT:    0x0 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x4 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0xC R_MIPS_LO16 local1
+# CHECK-NEXT:  }
+
+# GOTLO 7: R_MIPS_GOT16 must be followed by a matching R_MIPS_LO16.
+#          The second relocation matches if the symbol is the same and the
+#          offset is greater or equal so that the carry bit is correct. The two
+#          R_MIPS_GOT16's therefore match different R_MIPS_LO16's.
+	.section .mips_gotlo_7, "ax", @progbits
+	addiu $2, $2, %lo(local1+1)
+	addiu $2, $2, %lo(local1+6)
+	lui $2, %got(local1+4)
+	lui $2, %got(local1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_7 {
+# CHECK-NEXT:    0xC R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 local1
+# CHECK-NEXT:    0x8 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x4 R_MIPS_LO16 local1
+# CHECK-NEXT:  }
+
+# GOTLO 8: R_MIPS_LO16's may be orphaned.
+	.section .mips_gotlo_8, "ax", @progbits
+	lw $2, %lo(local1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_8 {
+# CHECK-NEXT:    0x0 R_MIPS_LO16 local1
+# CHECK-NEXT:  }
+
+# GOTLO 8b: Another example of 8. The R_MIPS_LO16 at 0x4 is orphaned.
+	.section .mips_gotlo_8b, "ax", @progbits
+	lw $2, %lo(local1)
+	lw $2, %lo(local1)
+	lui $2, %got(local1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_8b {
+# CHECK-NEXT:    0x8 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 local1
+# CHECK-NEXT:    0x4 R_MIPS_LO16 local1
+# CHECK-NEXT:  }
+
+# GOTLO 9: R_MIPS_GOT16's don't need a matching R_MIPS_LO16 to immediately
+#          follow so long as there is one after the R_MIPS_GOT16 somewhere.
+#          This isn't permitted by the ABI specification but has been allowed
+#          in practice for a very long time. The R_MIPS_GOT16's should be
+#          ordered by the address they affect for purely cosmetic reasons.
+	.section .mips_gotlo_9, "ax", @progbits
+	lw $2, %lo(local1)
+	lui $2, %got(local1)
+	lui $2, %got(local1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_9 {
+# CHECK-NEXT:    0x4 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x8 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 local1
+# CHECK-NEXT:  }
+
+# GOTLO 10: R_MIPS_GOT16's must have a matching R_MIPS_LO16 somewhere though.
+#           When this is impossible we have two possible bad behaviours
+#           depending on the linker implementation:
+#           * The linker silently computes the wrong value using a partially
+#             matching R_MIPS_LO16.
+#           * The linker rejects the relocation table as invalid.
+#           The latter is preferable since it's far easier to detect and debug
+#           so check that we encourage this behaviour by putting invalid
+#           R_MIPS_GOT16's at the end of the relocation table where the risk of
+#           a partial match is very low.
+	.section .mips_gotlo_10, "ax", @progbits
+	lui $2, %got(local1)
+	lw $2, %lo(local1)
+	lui $2, %got(local2)
+	lui $2, %got(local3)
+	lw $2, %lo(local3)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_10 {
+# CHECK-NEXT:    0x0 R_MIPS_GOT16 local1
+# CHECK-NEXT:    0x4 R_MIPS_LO16 local1
+# CHECK-NEXT:    0xC R_MIPS_GOT16 local3
+# CHECK-NEXT:    0x10 R_MIPS_LO16 local3
+# CHECK-NEXT:    0x8 R_MIPS_GOT16 local2
+# CHECK-NEXT:  }
+
+# Finally, do test 2 for R_MIPS_GOT16 on external symbols to prove they are
+# exempt from the rules for local symbols.
+
+# External GOTLO 2: R_MIPS_GOT16 must be followed by a matching R_MIPS_LO16.
+	.section .mips_ext_gotlo_2, "ax", @progbits
+	addiu $2, $2, %lo(sym1)
+	lui $2, %got(sym1)
+
+# CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_ext_gotlo_2 {
+# CHECK-NEXT:    0x0 R_MIPS_LO16 sym1
+# CHECK-NEXT:    0x4 R_MIPS_GOT16 sym1
+# CHECK-NEXT:  }
+
+# Define some local symbols.
+        .text
+        nop
+local1: nop
+local2: nop
+local3: nop