[mips] Correct the ordering of HI/LO pairs in the relocation table.

[dsanders]

Summary

There seems to have been a misunderstanding as to the meaning of 'offset' in
the rules laid down by our ABI. The previous code believed that 'offset' meant
the offset within the section that the relocation is applied to. However, it
should have meant the offset from the symbol used in the relocation expression.

This patch adds two fields to ELFRelocationEntry and uses them to correct the
order of relocations for MIPS. These fields contain:

• The original symbol before shouldRelocateWithSymbol() is considered. This ensures that R_MIPS_GOT16 is able to correctly distinguish between local and external symbols, allowing us to tell whether %got() requires a matching %lo() or not (local symbols require one, external symbols don't). It also prevents confusing cases where the fuzzy matching rules cause things like %hi(foo)/%lo(foo+3) and %hi(bar)/%lo(bar+1) to swap their %lo()'s.
• The original offset before shouldRelocateWithSymbol() is considered. The existing Addend field is always zero when the object uses in place addends (because it's already moved it to the encoding) but MIPS needs to use the original offset to ensure that the linker correctly calculates the carry-in bit for %hi() and %got().

IAS ensures that unmatchable %hi()/%got() relocations are placed at the end of
the table to ensure that the linker rejects the table (we're unable to report
such errors directly). The alternatives to this risk accidental matching
against inappropriate relocations which may silently compute incorrect values
due to an incorrect carry bit between the %lo() and %hi()/%got().

Depends on D19716 and fixes the bug revealed by D19016.

[dsanders]

Include a last minute correction.

[sdardis]

LGTM with nits addressed.

lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp

86–88

Nit: Align the top two comments lines with the bottom line.

156

Nit: The first sentence here is a somewhat fragmented. I assume you're saying "It's type matches that of a corresponding low part".

178

warning: extra ';' [-Wpendantic]

include/llvm/MC/MCELFObjectWriter.h

 //===-- llvm/MC/MCELFObjectWriter.h - ELF Object Writer ---------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_MC_MCELFOBJECTWRITER_H
 #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>
 
 namespace llvm {
 class MCAssembler;
 class MCContext;
 class MCFixup;
 class MCFragment;
 class MCObjectWriter;
 class MCSymbol;
 class MCSymbolELF;
 class MCValue;
 class raw_pwrite_stream;
 
 struct ELFRelocationEntry {
   uint64_t Offset; // Where is the relocation.
   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 {
   const uint8_t OSABI;
   const uint16_t EMachine;
   const unsigned HasRelocationAddend : 1;
   const unsigned Is64Bit : 1;
   const unsigned IsN64 : 1;

lib/MC/ELFObjectWriter.cpp

if (const auto *Inner = dyn_cast<MCSymbolRefExpr>(Expr)) {
       if (Inner->getKind() == MCSymbolRefExpr::VK_WEAKREF) {
         SymA = cast<MCSymbolELF>(&Inner->getSymbol());
         ViaWeakRef = true;
       }
     }
   }
 
   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);
 
   uint64_t Addend = 0;
   if (hasRelocationAddend()) {
     Addend = C;
     C = 0;
   }
 
   FixedValue = C;
 
   if (!RelocateWithSymbol) {
     const MCSection *SecA =
         (SymA && !SymA->isUndefined()) ? &SymA->getSection() : nullptr;
     auto *ELFSec = cast_or_null<MCSectionELF>(SecA);
     const auto *SectionSymbol =
         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);
 }
 
 bool ELFObjectWriter::isInSymtab(const MCAsmLayout &Layout,
                                  const MCSymbolELF &Symbol, bool Used,
                                  bool Renamed) {
   if (Symbol.isVariable()) {
     const MCExpr *Expr = Symbol.getVariableValue();

lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp

 //===-- MipsELFObjectWriter.cpp - Mips ELF Writer -------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
+#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"
 #include "llvm/MC/MCELFObjectWriter.h"
 #include "llvm/MC/MCExpr.h"
 #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;
+}
+
+  MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI, bool _isN64,
+                      bool IsLittleEndian);
 
-    ~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;
-  };
+
+/// 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,
                               /*HasRelocationAddend*/ _isN64,
                               /*IsN64*/ _isN64) {}
 
 MipsELFObjectWriter::~MipsELFObjectWriter() {}
case Mips::fixup_MICROMIPS_TLS_TPREL_HI16:
     return ELF::R_MICROMIPS_TLS_TPREL_HI16;
   case Mips::fixup_MICROMIPS_TLS_TPREL_LO16:
     return ELF::R_MICROMIPS_TLS_TPREL_LO16;
   }
 
   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]);
-  }
-
-  // SortOffsets are calculated, call the sorting function.
-  array_pod_sort(MipsRelocs.begin(), MipsRelocs.end(), cmpRelMips);
-
-  // Copy sorted MipsRelocs back to Relocs.
-  for (unsigned I = 0, E = MipsRelocs.size(); I != E; ++I)
-    Relocs[I] = MipsRelocs[I].R;
+  // 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;
+  }
+
+  DEBUG(dumpRelocs("S: ", Sorted));
+
+  assert(Relocs.size() == Sorted.size() && "Some relocs were not consumed");
+
+  // 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,
                                                   unsigned Type) const {
   // FIXME: This is extremely conservative. This really needs to use a
   // whitelist with a clear explanation for why each realocation needs to
   // point to the symbol, not to the section.
   switch (Type) {

test/MC/Mips/sort-relocation-table.s

 # 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
+# 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)
 
-# 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-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:  }
 
-# 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
+# Define some local symbols.
+        .text
+        nop
+local1: nop
+local2: nop
+local3: nop