lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp

   1 //===-- MipsELFObjectWriter.cpp - Mips ELF Writer -------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "MCTargetDesc/MipsFixupKinds.h"
  10 #include "MCTargetDesc/MipsMCTargetDesc.h"
  11 #include "llvm/ADT/STLExtras.h"
  12 #include "llvm/BinaryFormat/ELF.h"
  13 #include "llvm/MC/MCContext.h"
  14 #include "llvm/MC/MCELFObjectWriter.h"
  15 #include "llvm/MC/MCFixup.h"
  16 #include "llvm/MC/MCObjectWriter.h"
  17 #include "llvm/MC/MCSymbolELF.h"
  18 #include "llvm/Support/Casting.h"
  19 #include "llvm/Support/Compiler.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/ErrorHandling.h"
  22 #include "llvm/Support/MathExtras.h"
  23 #include "llvm/Support/raw_ostream.h"
  24 #include <algorithm>
  25 #include <cassert>
  26 #include <cstdint>
  27 #include <iterator>
  28 #include <list>
  29 #include <utility>
  30
  31 #define DEBUG_TYPE "mips-elf-object-writer"
  32
  33 using namespace llvm;
  34
  35 namespace {
  36
  37 /// Holds additional information needed by the relocation ordering algorithm.
  38 struct MipsRelocationEntry {
  39   const ELFRelocationEntry R; ///< The relocation.
  40   bool Matched = false;       ///< Is this relocation part of a match.
  41
  42   MipsRelocationEntry(const ELFRelocationEntry &R) : R(R) {}
  43
  44   void print(raw_ostream &Out) const {
  45     R.print(Out);
  46     Out << ", Matched=" << Matched;
  47   }
  48 };
  49
  50 #ifndef NDEBUG
  51 raw_ostream &operator<<(raw_ostream &OS, const MipsRelocationEntry &RHS) {
  52   RHS.print(OS);
  53   return OS;
  54 }
  55 #endif
  56
  57 class MipsELFObjectWriter : public MCELFObjectTargetWriter {
  58 public:
  59   MipsELFObjectWriter(uint8_t OSABI, bool HasRelocationAddend, bool Is64);
  60
  61   ~MipsELFObjectWriter() override = default;
  62
  63   unsigned getRelocType(MCContext &Ctx, const MCValue &Target,
  64                         const MCFixup &Fixup, bool IsPCRel) const override;
  65   bool needsRelocateWithSymbol(const MCSymbol &Sym,
  66                                unsigned Type) const override;
  67   void sortRelocs(const MCAssembler &Asm,
  68                   std::vector<ELFRelocationEntry> &Relocs) override;
  69 };
  70
  71 /// The possible results of the Predicate function used by find_best.
  72 enum FindBestPredicateResult {
  73   FindBest_NoMatch = 0,  ///< The current element is not a match.
  74   FindBest_Match,        ///< The current element is a match but better ones are
  75                          ///  possible.
  76   FindBest_PerfectMatch, ///< The current element is an unbeatable match.
  77 };
  78
  79 } // end anonymous namespace
  80
  81 /// Copy elements in the range [First, Last) to d1 when the predicate is true or
  82 /// d2 when the predicate is false. This is essentially both std::copy_if and
  83 /// std::remove_copy_if combined into a single pass.
  84 template <class InputIt, class OutputIt1, class OutputIt2, class UnaryPredicate>
  85 static std::pair<OutputIt1, OutputIt2> copy_if_else(InputIt First, InputIt Last,
  86                                                     OutputIt1 d1, OutputIt2 d2,
  87                                                     UnaryPredicate Predicate) {
  88   for (InputIt I = First; I != Last; ++I) {
  89     if (Predicate(*I)) {
  90       *d1 = *I;
  91       d1++;
  92     } else {
  93       *d2 = *I;
  94       d2++;
  95     }
  96   }
  97
  98   return std::make_pair(d1, d2);
  99 }
 100
 101 /// Find the best match in the range [First, Last).
 102 ///
 103 /// An element matches when Predicate(X) returns FindBest_Match or
 104 /// FindBest_PerfectMatch. A value of FindBest_PerfectMatch also terminates
 105 /// the search. BetterThan(A, B) is a comparator that returns true when A is a
 106 /// better match than B. The return value is the position of the best match.
 107 ///
 108 /// This is similar to std::find_if but finds the best of multiple possible
 109 /// matches.
 110 template <class InputIt, class UnaryPredicate, class Comparator>
 111 static InputIt find_best(InputIt First, InputIt Last, UnaryPredicate Predicate,
 112                          Comparator BetterThan) {
 113   InputIt Best = Last;
 114
 115   for (InputIt I = First; I != Last; ++I) {
 116     unsigned Matched = Predicate(*I);
 117     if (Matched != FindBest_NoMatch) {
 118       LLVM_DEBUG(dbgs() << std::distance(First, I) << " is a match (";
 119                  I->print(dbgs()); dbgs() << ")\n");
 120       if (Best == Last || BetterThan(*I, *Best)) {
 121         LLVM_DEBUG(dbgs() << ".. and it beats the last one\n");
 122         Best = I;
 123       }
 124     }
 125     if (Matched == FindBest_PerfectMatch) {
 126       LLVM_DEBUG(dbgs() << ".. and it is unbeatable\n");
 127       break;
 128     }
 129   }
 130
 131   return Best;
 132 }
 133
 134 /// Determine the low relocation that matches the given relocation.
 135 /// If the relocation does not need a low relocation then the return value
 136 /// is ELF::R_MIPS_NONE.
 137 ///
 138 /// The relocations that need a matching low part are
 139 /// R_(MIPS|MICROMIPS|MIPS16)_HI16 for all symbols and
 140 /// R_(MIPS|MICROMIPS|MIPS16)_GOT16 for local symbols only.
 141 static unsigned getMatchingLoType(const ELFRelocationEntry &Reloc) {
 142   unsigned Type = Reloc.Type;
 143   if (Type == ELF::R_MIPS_HI16)
 144     return ELF::R_MIPS_LO16;
 145   if (Type == ELF::R_MICROMIPS_HI16)
 146     return ELF::R_MICROMIPS_LO16;
 147   if (Type == ELF::R_MIPS16_HI16)
 148     return ELF::R_MIPS16_LO16;
 149
 150   if (Reloc.OriginalSymbol &&
 151       Reloc.OriginalSymbol->getBinding() != ELF::STB_LOCAL)
 152     return ELF::R_MIPS_NONE;
 153
 154   if (Type == ELF::R_MIPS_GOT16)
 155     return ELF::R_MIPS_LO16;
 156   if (Type == ELF::R_MICROMIPS_GOT16)
 157     return ELF::R_MICROMIPS_LO16;
 158   if (Type == ELF::R_MIPS16_GOT16)
 159     return ELF::R_MIPS16_LO16;
 160
 161   return ELF::R_MIPS_NONE;
 162 }
 163
 164 /// Determine whether a relocation (X) matches the one given in R.
 165 ///
 166 /// A relocation matches if:
 167 /// - It's type matches that of a corresponding low part. This is provided in
 168 ///   MatchingType for efficiency.
 169 /// - It's based on the same symbol.
 170 /// - It's offset of greater or equal to that of the one given in R.
 171 ///   It should be noted that this rule assumes the programmer does not use
 172 ///   offsets that exceed the alignment of the symbol. The carry-bit will be
 173 ///   incorrect if this is not true.
 174 ///
 175 /// A matching relocation is unbeatable if:
 176 /// - It is not already involved in a match.
 177 /// - It's offset is exactly that of the one given in R.
 178 static FindBestPredicateResult isMatchingReloc(const MipsRelocationEntry &X,
 179                                                const ELFRelocationEntry &R,
 180                                                unsigned MatchingType) {
 181   if (X.R.Type == MatchingType && X.R.OriginalSymbol == R.OriginalSymbol) {
 182     if (!X.Matched &&
 183         X.R.OriginalAddend == R.OriginalAddend)
 184       return FindBest_PerfectMatch;
 185     else if (X.R.OriginalAddend >= R.OriginalAddend)
 186       return FindBest_Match;
 187   }
 188   return FindBest_NoMatch;
 189 }
 190
 191 /// Determine whether Candidate or PreviousBest is the better match.
 192 /// The return value is true if Candidate is the better match.
 193 ///
 194 /// A matching relocation is a better match if:
 195 /// - It has a smaller addend.
 196 /// - It is not already involved in a match.
 197 static bool compareMatchingRelocs(const MipsRelocationEntry &Candidate,
 198                                   const MipsRelocationEntry &PreviousBest) {
 199   if (Candidate.R.OriginalAddend != PreviousBest.R.OriginalAddend)
 200     return Candidate.R.OriginalAddend < PreviousBest.R.OriginalAddend;
 201   return PreviousBest.Matched && !Candidate.Matched;
 202 }
 203
 204 #ifndef NDEBUG
 205 /// Print all the relocations.
 206 template <class Container>
 207 static void dumpRelocs(const char *Prefix, const Container &Relocs) {
 208   for (const auto &R : Relocs)
 209     dbgs() << Prefix << R << "\n";
 210 }
 211 #endif
 212
 213 MipsELFObjectWriter::MipsELFObjectWriter(uint8_t OSABI,
 214                                          bool HasRelocationAddend, bool Is64)
 215     : MCELFObjectTargetWriter(Is64, OSABI, ELF::EM_MIPS, HasRelocationAddend) {}
 216
 217 unsigned MipsELFObjectWriter::getRelocType(MCContext &Ctx,
 218                                            const MCValue &Target,
 219                                            const MCFixup &Fixup,
 220                                            bool IsPCRel) const {
 221   // Determine the type of the relocation.
 222   unsigned Kind = Fixup.getTargetKind();
 223
 224   switch (Kind) {
 225   case FK_NONE:
 226     return ELF::R_MIPS_NONE;
 227   case FK_Data_1:
 228     Ctx.reportError(Fixup.getLoc(),
 229                     "MIPS does not support one byte relocations");
 230     return ELF::R_MIPS_NONE;
 231   case Mips::fixup_Mips_16:
 232   case FK_Data_2:
 233     return IsPCRel ? ELF::R_MIPS_PC16 : ELF::R_MIPS_16;
 234   case Mips::fixup_Mips_32:
 235   case FK_Data_4:
 236     return IsPCRel ? ELF::R_MIPS_PC32 : ELF::R_MIPS_32;
 237   }
 238
 239   if (IsPCRel) {
 240     switch (Kind) {
 241     case FK_Data_8:
 242       Ctx.reportError(Fixup.getLoc(),
 243                       "MIPS does not support 64-bit PC-relative relocations");
 244       return ELF::R_MIPS_NONE;
 245     case Mips::fixup_Mips_Branch_PCRel:
 246     case Mips::fixup_Mips_PC16:
 247       return ELF::R_MIPS_PC16;
 248     case Mips::fixup_MICROMIPS_PC7_S1:
 249       return ELF::R_MICROMIPS_PC7_S1;
 250     case Mips::fixup_MICROMIPS_PC10_S1:
 251       return ELF::R_MICROMIPS_PC10_S1;
 252     case Mips::fixup_MICROMIPS_PC16_S1:
 253       return ELF::R_MICROMIPS_PC16_S1;
 254     case Mips::fixup_MICROMIPS_PC26_S1:
 255       return ELF::R_MICROMIPS_PC26_S1;
 256     case Mips::fixup_MICROMIPS_PC19_S2:
 257       return ELF::R_MICROMIPS_PC19_S2;
 258     case Mips::fixup_MICROMIPS_PC18_S3:
 259       return ELF::R_MICROMIPS_PC18_S3;
 260     case Mips::fixup_MICROMIPS_PC21_S1:
 261       return ELF::R_MICROMIPS_PC21_S1;
 262     case Mips::fixup_MIPS_PC19_S2:
 263       return ELF::R_MIPS_PC19_S2;
 264     case Mips::fixup_MIPS_PC18_S3:
 265       return ELF::R_MIPS_PC18_S3;
 266     case Mips::fixup_MIPS_PC21_S2:
 267       return ELF::R_MIPS_PC21_S2;
 268     case Mips::fixup_MIPS_PC26_S2:
 269       return ELF::R_MIPS_PC26_S2;
 270     case Mips::fixup_MIPS_PCHI16:
 271       return ELF::R_MIPS_PCHI16;
 272     case Mips::fixup_MIPS_PCLO16:
 273       return ELF::R_MIPS_PCLO16;
 274     }
 275
 276     llvm_unreachable("invalid PC-relative fixup kind!");
 277   }
 278
 279   switch (Kind) {
 280   case Mips::fixup_Mips_64:
 281   case FK_Data_8:
 282     return ELF::R_MIPS_64;
 283   case FK_DTPRel_4:
 284     return ELF::R_MIPS_TLS_DTPREL32;
 285   case FK_DTPRel_8:
 286     return ELF::R_MIPS_TLS_DTPREL64;
 287   case FK_TPRel_4:
 288     return ELF::R_MIPS_TLS_TPREL32;
 289   case FK_TPRel_8:
 290     return ELF::R_MIPS_TLS_TPREL64;
 291   case FK_GPRel_4:
 292     if (is64Bit()) {
 293       unsigned Type = (unsigned)ELF::R_MIPS_NONE;
 294       Type = setRType((unsigned)ELF::R_MIPS_GPREL32, Type);
 295       Type = setRType2((unsigned)ELF::R_MIPS_64, Type);
 296       Type = setRType3((unsigned)ELF::R_MIPS_NONE, Type);
 297       return Type;
 298     }
 299     return ELF::R_MIPS_GPREL32;
 300   case Mips::fixup_Mips_GPREL16:
 301     return ELF::R_MIPS_GPREL16;
 302   case Mips::fixup_Mips_26:
 303     return ELF::R_MIPS_26;
 304   case Mips::fixup_Mips_CALL16:
 305     return ELF::R_MIPS_CALL16;
 306   case Mips::fixup_Mips_GOT:
 307     return ELF::R_MIPS_GOT16;
 308   case Mips::fixup_Mips_HI16:
 309     return ELF::R_MIPS_HI16;
 310   case Mips::fixup_Mips_LO16:
 311     return ELF::R_MIPS_LO16;
 312   case Mips::fixup_Mips_TLSGD:
 313     return ELF::R_MIPS_TLS_GD;
 314   case Mips::fixup_Mips_GOTTPREL:
 315     return ELF::R_MIPS_TLS_GOTTPREL;
 316   case Mips::fixup_Mips_TPREL_HI:
 317     return ELF::R_MIPS_TLS_TPREL_HI16;
 318   case Mips::fixup_Mips_TPREL_LO:
 319     return ELF::R_MIPS_TLS_TPREL_LO16;
 320   case Mips::fixup_Mips_TLSLDM:
 321     return ELF::R_MIPS_TLS_LDM;
 322   case Mips::fixup_Mips_DTPREL_HI:
 323     return ELF::R_MIPS_TLS_DTPREL_HI16;
 324   case Mips::fixup_Mips_DTPREL_LO:
 325     return ELF::R_MIPS_TLS_DTPREL_LO16;
 326   case Mips::fixup_Mips_GOT_PAGE:
 327     return ELF::R_MIPS_GOT_PAGE;
 328   case Mips::fixup_Mips_GOT_OFST:
 329     return ELF::R_MIPS_GOT_OFST;
 330   case Mips::fixup_Mips_GOT_DISP:
 331     return ELF::R_MIPS_GOT_DISP;
 332   case Mips::fixup_Mips_GPOFF_HI: {
 333     unsigned Type = (unsigned)ELF::R_MIPS_NONE;
 334     Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type);
 335     Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type);
 336     Type = setRType3((unsigned)ELF::R_MIPS_HI16, Type);
 337     return Type;
 338   }
 339   case Mips::fixup_MICROMIPS_GPOFF_HI: {
 340     unsigned Type = (unsigned)ELF::R_MIPS_NONE;
 341     Type = setRType((unsigned)ELF::R_MICROMIPS_GPREL16, Type);
 342     Type = setRType2((unsigned)ELF::R_MICROMIPS_SUB, Type);
 343     Type = setRType3((unsigned)ELF::R_MICROMIPS_HI16, Type);
 344     return Type;
 345   }
 346   case Mips::fixup_Mips_GPOFF_LO: {
 347     unsigned Type = (unsigned)ELF::R_MIPS_NONE;
 348     Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type);
 349     Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type);
 350     Type = setRType3((unsigned)ELF::R_MIPS_LO16, Type);
 351     return Type;
 352   }
 353   case Mips::fixup_MICROMIPS_GPOFF_LO: {
 354     unsigned Type = (unsigned)ELF::R_MIPS_NONE;
 355     Type = setRType((unsigned)ELF::R_MICROMIPS_GPREL16, Type);
 356     Type = setRType2((unsigned)ELF::R_MICROMIPS_SUB, Type);
 357     Type = setRType3((unsigned)ELF::R_MICROMIPS_LO16, Type);
 358     return Type;
 359   }
 360   case Mips::fixup_Mips_HIGHER:
 361     return ELF::R_MIPS_HIGHER;
 362   case Mips::fixup_Mips_HIGHEST:
 363     return ELF::R_MIPS_HIGHEST;
 364   case Mips::fixup_Mips_SUB:
 365     return ELF::R_MIPS_SUB;
 366   case Mips::fixup_Mips_GOT_HI16:
 367     return ELF::R_MIPS_GOT_HI16;
 368   case Mips::fixup_Mips_GOT_LO16:
 369     return ELF::R_MIPS_GOT_LO16;
 370   case Mips::fixup_Mips_CALL_HI16:
 371     return ELF::R_MIPS_CALL_HI16;
 372   case Mips::fixup_Mips_CALL_LO16:
 373     return ELF::R_MIPS_CALL_LO16;
 374   case Mips::fixup_MICROMIPS_26_S1:
 375     return ELF::R_MICROMIPS_26_S1;
 376   case Mips::fixup_MICROMIPS_HI16:
 377     return ELF::R_MICROMIPS_HI16;
 378   case Mips::fixup_MICROMIPS_LO16:
 379     return ELF::R_MICROMIPS_LO16;
 380   case Mips::fixup_MICROMIPS_GOT16:
 381     return ELF::R_MICROMIPS_GOT16;
 382   case Mips::fixup_MICROMIPS_CALL16:
 383     return ELF::R_MICROMIPS_CALL16;
 384   case Mips::fixup_MICROMIPS_GOT_DISP:
 385     return ELF::R_MICROMIPS_GOT_DISP;
 386   case Mips::fixup_MICROMIPS_GOT_PAGE:
 387     return ELF::R_MICROMIPS_GOT_PAGE;
 388   case Mips::fixup_MICROMIPS_GOT_OFST:
 389     return ELF::R_MICROMIPS_GOT_OFST;
 390   case Mips::fixup_MICROMIPS_TLS_GD:
 391     return ELF::R_MICROMIPS_TLS_GD;
 392   case Mips::fixup_MICROMIPS_TLS_LDM:
 393     return ELF::R_MICROMIPS_TLS_LDM;
 394   case Mips::fixup_MICROMIPS_TLS_DTPREL_HI16:
 395     return ELF::R_MICROMIPS_TLS_DTPREL_HI16;
 396   case Mips::fixup_MICROMIPS_TLS_DTPREL_LO16:
 397     return ELF::R_MICROMIPS_TLS_DTPREL_LO16;
 398   case Mips::fixup_MICROMIPS_GOTTPREL:
 399     return ELF::R_MICROMIPS_TLS_GOTTPREL;
 400   case Mips::fixup_MICROMIPS_TLS_TPREL_HI16:
 401     return ELF::R_MICROMIPS_TLS_TPREL_HI16;
 402   case Mips::fixup_MICROMIPS_TLS_TPREL_LO16:
 403     return ELF::R_MICROMIPS_TLS_TPREL_LO16;
 404   case Mips::fixup_MICROMIPS_SUB:
 405     return ELF::R_MICROMIPS_SUB;
 406   case Mips::fixup_MICROMIPS_HIGHER:
 407     return ELF::R_MICROMIPS_HIGHER;
 408   case Mips::fixup_MICROMIPS_HIGHEST:
 409     return ELF::R_MICROMIPS_HIGHEST;
 410   case Mips::fixup_Mips_JALR:
 411     return ELF::R_MIPS_JALR;
 412   case Mips::fixup_MICROMIPS_JALR:
 413     return ELF::R_MICROMIPS_JALR;
 414   }
 415
 416   llvm_unreachable("invalid fixup kind!");
 417 }
 418
 419 /// Sort relocation table entries by offset except where another order is
 420 /// required by the MIPS ABI.
 421 ///
 422 /// MIPS has a few relocations that have an AHL component in the expression used
 423 /// to evaluate them. This AHL component is an addend with the same number of
 424 /// bits as a symbol value but not all of our ABI's are able to supply a
 425 /// sufficiently sized addend in a single relocation.
 426 ///
 427 /// The O32 ABI for example, uses REL relocations which store the addend in the
 428 /// section data. All the relocations with AHL components affect 16-bit fields
 429 /// so the addend for a single relocation is limited to 16-bit. This ABI
 430 /// resolves the limitation by linking relocations (e.g. R_MIPS_HI16 and
 431 /// R_MIPS_LO16) and distributing the addend between the linked relocations. The
 432 /// ABI mandates that such relocations must be next to each other in a
 433 /// particular order (e.g. R_MIPS_HI16 must be immediately followed by a
 434 /// matching R_MIPS_LO16) but the rule is less strict in practice.
 435 ///
 436 /// The de facto standard is lenient in the following ways:
 437 /// - 'Immediately following' does not refer to the next relocation entry but
 438 ///   the next matching relocation.
 439 /// - There may be multiple high parts relocations for one low part relocation.
 440 /// - There may be multiple low part relocations for one high part relocation.
 441 /// - The AHL addend in each part does not have to be exactly equal as long as
 442 ///   the difference does not affect the carry bit from bit 15 into 16. This is
 443 ///   to allow, for example, the use of %lo(foo) and %lo(foo+4) when loading
 444 ///   both halves of a long long.
 445 ///
 446 /// See getMatchingLoType() for a description of which high part relocations
 447 /// match which low part relocations. One particular thing to note is that
 448 /// R_MIPS_GOT16 and similar only have AHL addends if they refer to local
 449 /// symbols.
 450 ///
 451 /// It should also be noted that this function is not affected by whether
 452 /// the symbol was kept or rewritten into a section-relative equivalent. We
 453 /// always match using the expressions from the source.
 454 void MipsELFObjectWriter::sortRelocs(const MCAssembler &Asm,
 455                                      std::vector<ELFRelocationEntry> &Relocs) {
 456   // We do not need to sort the relocation table for RELA relocations which
 457   // N32/N64 uses as the relocation addend contains the value we require,
 458   // rather than it being split across a pair of relocations.
 459   if (hasRelocationAddend())
 460     return;
 461
 462   if (Relocs.size() < 2)
 463     return;
 464
 465   // Sort relocations by the address they are applied to.
 466   llvm::sort(Relocs,
 467              [](const ELFRelocationEntry &A, const ELFRelocationEntry &B) {
 468                return A.Offset < B.Offset;
 469              });
 470
 471   std::list<MipsRelocationEntry> Sorted;
 472   std::list<ELFRelocationEntry> Remainder;
 473
 474   LLVM_DEBUG(dumpRelocs("R: ", Relocs));
 475
 476   // Separate the movable relocations (AHL relocations using the high bits) from
 477   // the immobile relocations (everything else). This does not preserve high/low
 478   // matches that already existed in the input.
 479   copy_if_else(Relocs.begin(), Relocs.end(), std::back_inserter(Remainder),
 480                std::back_inserter(Sorted), [](const ELFRelocationEntry &Reloc) {
 481                  return getMatchingLoType(Reloc) != ELF::R_MIPS_NONE;
 482                });
 483
 484   for (auto &R : Remainder) {
 485     LLVM_DEBUG(dbgs() << "Matching: " << R << "\n");
 486
 487     unsigned MatchingType = getMatchingLoType(R);
 488     assert(MatchingType != ELF::R_MIPS_NONE &&
 489            "Wrong list for reloc that doesn't need a match");
 490
 491     // Find the best matching relocation for the current high part.
 492     // See isMatchingReloc for a description of a matching relocation and
 493     // compareMatchingRelocs for a description of what 'best' means.
 494     auto InsertionPoint =
 495         find_best(Sorted.begin(), Sorted.end(),
 496                   [&R, &MatchingType](const MipsRelocationEntry &X) {
 497                     return isMatchingReloc(X, R, MatchingType);
 498                   },
 499                   compareMatchingRelocs);
 500
 501     // If we matched then insert the high part in front of the match and mark
 502     // both relocations as being involved in a match. We only mark the high
 503     // part for cosmetic reasons in the debug output.
 504     //
 505     // If we failed to find a match then the high part is orphaned. This is not
 506     // permitted since the relocation cannot be evaluated without knowing the
 507     // carry-in. We can sometimes handle this using a matching low part that is
 508     // already used in a match but we already cover that case in
 509     // isMatchingReloc and compareMatchingRelocs. For the remaining cases we
 510     // should insert the high part at the end of the list. This will cause the
 511     // linker to fail but the alternative is to cause the linker to bind the
 512     // high part to a semi-matching low part and silently calculate the wrong
 513     // value. Unfortunately we have no means to warn the user that we did this
 514     // so leave it up to the linker to complain about it.
 515     if (InsertionPoint != Sorted.end())
 516       InsertionPoint->Matched = true;
 517     Sorted.insert(InsertionPoint, R)->Matched = true;
 518   }
 519
 520   LLVM_DEBUG(dumpRelocs("S: ", Sorted));
 521
 522   assert(Relocs.size() == Sorted.size() && "Some relocs were not consumed");
 523
 524   // Overwrite the original vector with the sorted elements. The caller expects
 525   // them in reverse order.
 526   unsigned CopyTo = 0;
 527   for (const auto &R : reverse(Sorted))
 528     Relocs[CopyTo++] = R.R;
 529 }
 530
 531 bool MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbol &Sym,
 532                                                   unsigned Type) const {
 533   // If it's a compound relocation for N64 then we need the relocation if any
 534   // sub-relocation needs it.
 535   if (!isUInt<8>(Type))
 536     return needsRelocateWithSymbol(Sym, Type & 0xff) ||
 537            needsRelocateWithSymbol(Sym, (Type >> 8) & 0xff) ||
 538            needsRelocateWithSymbol(Sym, (Type >> 16) & 0xff);
 539
 540   switch (Type) {
 541   default:
 542     errs() << Type << "\n";
 543     llvm_unreachable("Unexpected relocation");
 544     return true;
 545
 546   // This relocation doesn't affect the section data.
 547   case ELF::R_MIPS_NONE:
 548     return false;
 549
 550   // On REL ABI's (e.g. O32), these relocations form pairs. The pairing is done
 551   // by the static linker by matching the symbol and offset.
 552   // We only see one relocation at a time but it's still safe to relocate with
 553   // the section so long as both relocations make the same decision.
 554   //
 555   // Some older linkers may require the symbol for particular cases. Such cases
 556   // are not supported yet but can be added as required.
 557   case ELF::R_MIPS_GOT16:
 558   case ELF::R_MIPS16_GOT16:
 559   case ELF::R_MICROMIPS_GOT16:
 560   case ELF::R_MIPS_HIGHER:
 561   case ELF::R_MIPS_HIGHEST:
 562   case ELF::R_MIPS_HI16:
 563   case ELF::R_MIPS16_HI16:
 564   case ELF::R_MICROMIPS_HI16:
 565   case ELF::R_MIPS_LO16:
 566   case ELF::R_MIPS16_LO16:
 567   case ELF::R_MICROMIPS_LO16:
 568     // FIXME: It should be safe to return false for the STO_MIPS_MICROMIPS but
 569     //        we neglect to handle the adjustment to the LSB of the addend that
 570     //        it causes in applyFixup() and similar.
 571     if (cast<MCSymbolELF>(Sym).getOther() & ELF::STO_MIPS_MICROMIPS)
 572       return true;
 573     return false;
 574
 575   case ELF::R_MIPS_GOT_PAGE:
 576   case ELF::R_MICROMIPS_GOT_PAGE:
 577   case ELF::R_MIPS_GOT_OFST:
 578   case ELF::R_MICROMIPS_GOT_OFST:
 579   case ELF::R_MIPS_16:
 580   case ELF::R_MIPS_32:
 581   case ELF::R_MIPS_GPREL32:
 582     if (cast<MCSymbolELF>(Sym).getOther() & ELF::STO_MIPS_MICROMIPS)
 583       return true;
 584     LLVM_FALLTHROUGH;
 585   case ELF::R_MIPS_26:
 586   case ELF::R_MIPS_64:
 587   case ELF::R_MIPS_GPREL16:
 588   case ELF::R_MIPS_PC16:
 589   case ELF::R_MIPS_SUB:
 590     return false;
 591
 592   // FIXME: Many of these relocations should probably return false but this
 593   //        hasn't been confirmed to be safe yet.
 594   case ELF::R_MIPS_REL32:
 595   case ELF::R_MIPS_LITERAL:
 596   case ELF::R_MIPS_CALL16:
 597   case ELF::R_MIPS_SHIFT5:
 598   case ELF::R_MIPS_SHIFT6:
 599   case ELF::R_MIPS_GOT_DISP:
 600   case ELF::R_MIPS_GOT_HI16:
 601   case ELF::R_MIPS_GOT_LO16:
 602   case ELF::R_MIPS_INSERT_A:
 603   case ELF::R_MIPS_INSERT_B:
 604   case ELF::R_MIPS_DELETE:
 605   case ELF::R_MIPS_CALL_HI16:
 606   case ELF::R_MIPS_CALL_LO16:
 607   case ELF::R_MIPS_SCN_DISP:
 608   case ELF::R_MIPS_REL16:
 609   case ELF::R_MIPS_ADD_IMMEDIATE:
 610   case ELF::R_MIPS_PJUMP:
 611   case ELF::R_MIPS_RELGOT:
 612   case ELF::R_MIPS_JALR:
 613   case ELF::R_MIPS_TLS_DTPMOD32:
 614   case ELF::R_MIPS_TLS_DTPREL32:
 615   case ELF::R_MIPS_TLS_DTPMOD64:
 616   case ELF::R_MIPS_TLS_DTPREL64:
 617   case ELF::R_MIPS_TLS_GD:
 618   case ELF::R_MIPS_TLS_LDM:
 619   case ELF::R_MIPS_TLS_DTPREL_HI16:
 620   case ELF::R_MIPS_TLS_DTPREL_LO16:
 621   case ELF::R_MIPS_TLS_GOTTPREL:
 622   case ELF::R_MIPS_TLS_TPREL32:
 623   case ELF::R_MIPS_TLS_TPREL64:
 624   case ELF::R_MIPS_TLS_TPREL_HI16:
 625   case ELF::R_MIPS_TLS_TPREL_LO16:
 626   case ELF::R_MIPS_GLOB_DAT:
 627   case ELF::R_MIPS_PC21_S2:
 628   case ELF::R_MIPS_PC26_S2:
 629   case ELF::R_MIPS_PC18_S3:
 630   case ELF::R_MIPS_PC19_S2:
 631   case ELF::R_MIPS_PCHI16:
 632   case ELF::R_MIPS_PCLO16:
 633   case ELF::R_MIPS_COPY:
 634   case ELF::R_MIPS_JUMP_SLOT:
 635   case ELF::R_MIPS_NUM:
 636   case ELF::R_MIPS_PC32:
 637   case ELF::R_MIPS_EH:
 638   case ELF::R_MICROMIPS_26_S1:
 639   case ELF::R_MICROMIPS_GPREL16:
 640   case ELF::R_MICROMIPS_LITERAL:
 641   case ELF::R_MICROMIPS_PC7_S1:
 642   case ELF::R_MICROMIPS_PC10_S1:
 643   case ELF::R_MICROMIPS_PC16_S1:
 644   case ELF::R_MICROMIPS_CALL16:
 645   case ELF::R_MICROMIPS_GOT_DISP:
 646   case ELF::R_MICROMIPS_GOT_HI16:
 647   case ELF::R_MICROMIPS_GOT_LO16:
 648   case ELF::R_MICROMIPS_SUB:
 649   case ELF::R_MICROMIPS_HIGHER:
 650   case ELF::R_MICROMIPS_HIGHEST:
 651   case ELF::R_MICROMIPS_CALL_HI16:
 652   case ELF::R_MICROMIPS_CALL_LO16:
 653   case ELF::R_MICROMIPS_SCN_DISP:
 654   case ELF::R_MICROMIPS_JALR:
 655   case ELF::R_MICROMIPS_HI0_LO16:
 656   case ELF::R_MICROMIPS_TLS_GD:
 657   case ELF::R_MICROMIPS_TLS_LDM:
 658   case ELF::R_MICROMIPS_TLS_DTPREL_HI16:
 659   case ELF::R_MICROMIPS_TLS_DTPREL_LO16:
 660   case ELF::R_MICROMIPS_TLS_GOTTPREL:
 661   case ELF::R_MICROMIPS_TLS_TPREL_HI16:
 662   case ELF::R_MICROMIPS_TLS_TPREL_LO16:
 663   case ELF::R_MICROMIPS_GPREL7_S2:
 664   case ELF::R_MICROMIPS_PC23_S2:
 665   case ELF::R_MICROMIPS_PC21_S1:
 666   case ELF::R_MICROMIPS_PC26_S1:
 667   case ELF::R_MICROMIPS_PC18_S3:
 668   case ELF::R_MICROMIPS_PC19_S2:
 669     return true;
 670
 671   // FIXME: Many of these should probably return false but MIPS16 isn't
 672   //        supported by the integrated assembler.
 673   case ELF::R_MIPS16_26:
 674   case ELF::R_MIPS16_GPREL:
 675   case ELF::R_MIPS16_CALL16:
 676   case ELF::R_MIPS16_TLS_GD:
 677   case ELF::R_MIPS16_TLS_LDM:
 678   case ELF::R_MIPS16_TLS_DTPREL_HI16:
 679   case ELF::R_MIPS16_TLS_DTPREL_LO16:
 680   case ELF::R_MIPS16_TLS_GOTTPREL:
 681   case ELF::R_MIPS16_TLS_TPREL_HI16:
 682   case ELF::R_MIPS16_TLS_TPREL_LO16:
 683     llvm_unreachable("Unsupported MIPS16 relocation");
 684     return true;
 685   }
 686 }
 687
 688 std::unique_ptr<MCObjectTargetWriter>
 689 llvm::createMipsELFObjectWriter(const Triple &TT, bool IsN32) {
 690   uint8_t OSABI = MCELFObjectTargetWriter::getOSABI(TT.getOS());
 691   bool IsN64 = TT.isArch64Bit() && !IsN32;
 692   bool HasRelocationAddend = TT.isArch64Bit();
 693   return std::make_unique<MipsELFObjectWriter>(OSABI, HasRelocationAddend,
 694                                                 IsN64);
 695 }