lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp

   1 //===-- MipsELFObjectWriter.cpp - Mips ELF Writer -------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "MCTargetDesc/MipsBaseInfo.h"
  11 #include "MCTargetDesc/MipsFixupKinds.h"
  12 #include "MCTargetDesc/MipsMCTargetDesc.h"
  13 #include "llvm/ADT/STLExtras.h"
  14 #include "llvm/MC/MCAssembler.h"
  15 #include "llvm/MC/MCELF.h"
  16 #include "llvm/MC/MCELFObjectWriter.h"
  17 #include "llvm/MC/MCExpr.h"
  18 #include "llvm/MC/MCSection.h"
  19 #include "llvm/MC/MCValue.h"
  20 #include "llvm/Support/ErrorHandling.h"
  21 #include <list>
  22
  23 using namespace llvm;
  24
  25 namespace {
  26 // A helper structure based on ELFRelocationEntry, used for sorting entries in
  27 // the relocation table.
  28 struct MipsRelocationEntry {
  29   MipsRelocationEntry(const ELFRelocationEntry &R)
  30       : R(R), SortOffset(R.Offset), HasMatchingHi(false) {}
  31   const ELFRelocationEntry R;
  32   // SortOffset equals R.Offset except for the *HI16 relocations, for which it
  33   // will be set based on the R.Offset of the matching *LO16 relocation.
  34   int64_t SortOffset;
  35   // True when this is a *LO16 relocation chosen as a match for a *HI16
  36   // relocation.
  37   bool HasMatchingHi;
  38 };
  39
  40   class MipsELFObjectWriter : public MCELFObjectTargetWriter {
  41   public:
  42     MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI,
  43                         bool _isN64, bool IsLittleEndian);
  44
  45     ~MipsELFObjectWriter() override;
  46
  47     unsigned GetRelocType(const MCValue &Target, const MCFixup &Fixup,
  48                           bool IsPCRel) const override;
  49     bool needsRelocateWithSymbol(const MCSymbol &Sym,
  50                                  unsigned Type) const override;
  51     virtual void sortRelocs(const MCAssembler &Asm,
  52                             std::vector<ELFRelocationEntry> &Relocs) override;
  53   };
  54 }
  55
  56 MipsELFObjectWriter::MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI,
  57                                          bool _isN64, bool IsLittleEndian)
  58     : MCELFObjectTargetWriter(_is64Bit, OSABI, ELF::EM_MIPS,
  59                               /*HasRelocationAddend*/ _isN64,
  60                               /*IsN64*/ _isN64) {}
  61
  62 MipsELFObjectWriter::~MipsELFObjectWriter() {}
  63
  64 unsigned MipsELFObjectWriter::GetRelocType(const MCValue &Target,
  65                                            const MCFixup &Fixup,
  66                                            bool IsPCRel) const {
  67   // determine the type of the relocation
  68   unsigned Type = (unsigned)ELF::R_MIPS_NONE;
  69   unsigned Kind = (unsigned)Fixup.getKind();
  70
  71   switch (Kind) {
  72   default:
  73     llvm_unreachable("invalid fixup kind!");
  74   case Mips::fixup_Mips_32:
  75   case FK_Data_4:
  76     Type = ELF::R_MIPS_32;
  77     break;
  78   case Mips::fixup_Mips_64:
  79   case FK_Data_8:
  80     Type = ELF::R_MIPS_64;
  81     break;
  82   case FK_GPRel_4:
  83     if (isN64()) {
  84       Type = setRType((unsigned)ELF::R_MIPS_GPREL32, Type);
  85       Type = setRType2((unsigned)ELF::R_MIPS_64, Type);
  86       Type = setRType3((unsigned)ELF::R_MIPS_NONE, Type);
  87     }
  88     else
  89       Type = ELF::R_MIPS_GPREL32;
  90     break;
  91   case Mips::fixup_Mips_GPREL16:
  92     Type = ELF::R_MIPS_GPREL16;
  93     break;
  94   case Mips::fixup_Mips_26:
  95     Type = ELF::R_MIPS_26;
  96     break;
  97   case Mips::fixup_Mips_CALL16:
  98     Type = ELF::R_MIPS_CALL16;
  99     break;
 100   case Mips::fixup_Mips_GOT_Global:
 101   case Mips::fixup_Mips_GOT_Local:
 102     Type = ELF::R_MIPS_GOT16;
 103     break;
 104   case Mips::fixup_Mips_HI16:
 105     Type = ELF::R_MIPS_HI16;
 106     break;
 107   case Mips::fixup_Mips_LO16:
 108     Type = ELF::R_MIPS_LO16;
 109     break;
 110   case Mips::fixup_Mips_TLSGD:
 111     Type = ELF::R_MIPS_TLS_GD;
 112     break;
 113   case Mips::fixup_Mips_GOTTPREL:
 114     Type = ELF::R_MIPS_TLS_GOTTPREL;
 115     break;
 116   case Mips::fixup_Mips_TPREL_HI:
 117     Type = ELF::R_MIPS_TLS_TPREL_HI16;
 118     break;
 119   case Mips::fixup_Mips_TPREL_LO:
 120     Type = ELF::R_MIPS_TLS_TPREL_LO16;
 121     break;
 122   case Mips::fixup_Mips_TLSLDM:
 123     Type = ELF::R_MIPS_TLS_LDM;
 124     break;
 125   case Mips::fixup_Mips_DTPREL_HI:
 126     Type = ELF::R_MIPS_TLS_DTPREL_HI16;
 127     break;
 128   case Mips::fixup_Mips_DTPREL_LO:
 129     Type = ELF::R_MIPS_TLS_DTPREL_LO16;
 130     break;
 131   case Mips::fixup_Mips_Branch_PCRel:
 132   case Mips::fixup_Mips_PC16:
 133     Type = ELF::R_MIPS_PC16;
 134     break;
 135   case Mips::fixup_Mips_GOT_PAGE:
 136     Type = ELF::R_MIPS_GOT_PAGE;
 137     break;
 138   case Mips::fixup_Mips_GOT_OFST:
 139     Type = ELF::R_MIPS_GOT_OFST;
 140     break;
 141   case Mips::fixup_Mips_GOT_DISP:
 142     Type = ELF::R_MIPS_GOT_DISP;
 143     break;
 144   case Mips::fixup_Mips_GPOFF_HI:
 145     Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type);
 146     Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type);
 147     Type = setRType3((unsigned)ELF::R_MIPS_HI16, Type);
 148     break;
 149   case Mips::fixup_Mips_GPOFF_LO:
 150     Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type);
 151     Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type);
 152     Type = setRType3((unsigned)ELF::R_MIPS_LO16, Type);
 153     break;
 154   case Mips::fixup_Mips_HIGHER:
 155     Type = ELF::R_MIPS_HIGHER;
 156     break;
 157   case Mips::fixup_Mips_HIGHEST:
 158     Type = ELF::R_MIPS_HIGHEST;
 159     break;
 160   case Mips::fixup_Mips_GOT_HI16:
 161     Type = ELF::R_MIPS_GOT_HI16;
 162     break;
 163   case Mips::fixup_Mips_GOT_LO16:
 164     Type = ELF::R_MIPS_GOT_LO16;
 165     break;
 166   case Mips::fixup_Mips_CALL_HI16:
 167     Type = ELF::R_MIPS_CALL_HI16;
 168     break;
 169   case Mips::fixup_Mips_CALL_LO16:
 170     Type = ELF::R_MIPS_CALL_LO16;
 171     break;
 172   case Mips::fixup_MICROMIPS_26_S1:
 173     Type = ELF::R_MICROMIPS_26_S1;
 174     break;
 175   case Mips::fixup_MICROMIPS_HI16:
 176     Type = ELF::R_MICROMIPS_HI16;
 177     break;
 178   case Mips::fixup_MICROMIPS_LO16:
 179     Type = ELF::R_MICROMIPS_LO16;
 180     break;
 181   case Mips::fixup_MICROMIPS_GOT16:
 182     Type = ELF::R_MICROMIPS_GOT16;
 183     break;
 184   case Mips::fixup_MICROMIPS_PC7_S1:
 185     Type = ELF::R_MICROMIPS_PC7_S1;
 186     break;
 187   case Mips::fixup_MICROMIPS_PC10_S1:
 188     Type = ELF::R_MICROMIPS_PC10_S1;
 189     break;
 190   case Mips::fixup_MICROMIPS_PC16_S1:
 191     Type = ELF::R_MICROMIPS_PC16_S1;
 192     break;
 193   case Mips::fixup_MICROMIPS_CALL16:
 194     Type = ELF::R_MICROMIPS_CALL16;
 195     break;
 196   case Mips::fixup_MICROMIPS_GOT_DISP:
 197     Type = ELF::R_MICROMIPS_GOT_DISP;
 198     break;
 199   case Mips::fixup_MICROMIPS_GOT_PAGE:
 200     Type = ELF::R_MICROMIPS_GOT_PAGE;
 201     break;
 202   case Mips::fixup_MICROMIPS_GOT_OFST:
 203     Type = ELF::R_MICROMIPS_GOT_OFST;
 204     break;
 205   case Mips::fixup_MICROMIPS_TLS_GD:
 206     Type = ELF::R_MICROMIPS_TLS_GD;
 207     break;
 208   case Mips::fixup_MICROMIPS_TLS_LDM:
 209     Type = ELF::R_MICROMIPS_TLS_LDM;
 210     break;
 211   case Mips::fixup_MICROMIPS_TLS_DTPREL_HI16:
 212     Type = ELF::R_MICROMIPS_TLS_DTPREL_HI16;
 213     break;
 214   case Mips::fixup_MICROMIPS_TLS_DTPREL_LO16:
 215     Type = ELF::R_MICROMIPS_TLS_DTPREL_LO16;
 216     break;
 217   case Mips::fixup_MICROMIPS_TLS_TPREL_HI16:
 218     Type = ELF::R_MICROMIPS_TLS_TPREL_HI16;
 219     break;
 220   case Mips::fixup_MICROMIPS_TLS_TPREL_LO16:
 221     Type = ELF::R_MICROMIPS_TLS_TPREL_LO16;
 222     break;
 223   case Mips::fixup_MIPS_PC19_S2:
 224     Type = ELF::R_MIPS_PC19_S2;
 225     break;
 226   case Mips::fixup_MIPS_PC18_S3:
 227     Type = ELF::R_MIPS_PC18_S3;
 228     break;
 229   case Mips::fixup_MIPS_PC21_S2:
 230     Type = ELF::R_MIPS_PC21_S2;
 231     break;
 232   case Mips::fixup_MIPS_PC26_S2:
 233     Type = ELF::R_MIPS_PC26_S2;
 234     break;
 235   case Mips::fixup_MIPS_PCHI16:
 236     Type = ELF::R_MIPS_PCHI16;
 237     break;
 238   case Mips::fixup_MIPS_PCLO16:
 239     Type = ELF::R_MIPS_PCLO16;
 240     break;
 241   }
 242   return Type;
 243 }
 244
 245 // Sort entries by SortOffset in descending order.
 246 // When there are more *HI16 relocs paired with one *LO16 reloc, the 2nd rule
 247 // sorts them in ascending order of R.Offset.
 248 static int cmpRelMips(const MipsRelocationEntry *AP,
 249                       const MipsRelocationEntry *BP) {
 250   const MipsRelocationEntry &A = *AP;
 251   const MipsRelocationEntry &B = *BP;
 252   if (A.SortOffset != B.SortOffset)
 253     return B.SortOffset - A.SortOffset;
 254   if (A.R.Offset != B.R.Offset)
 255     return A.R.Offset - B.R.Offset;
 256   if (B.R.Type != A.R.Type)
 257     return B.R.Type - A.R.Type;
 258   //llvm_unreachable("ELFRelocs might be unstable!");
 259   return 0;
 260 }
 261
 262 // For the given Reloc.Type, return the matching relocation type, as in the
 263 // table below.
 264 static unsigned getMatchingLoType(const MCAssembler &Asm,
 265                                   const ELFRelocationEntry &Reloc) {
 266   unsigned Type = Reloc.Type;
 267   if (Type == ELF::R_MIPS_HI16)
 268     return ELF::R_MIPS_LO16;
 269   if (Type == ELF::R_MICROMIPS_HI16)
 270     return ELF::R_MICROMIPS_LO16;
 271   if (Type == ELF::R_MIPS16_HI16)
 272     return ELF::R_MIPS16_LO16;
 273
 274   const MCSymbolData &SD = Reloc.Symbol->getData();
 275
 276   if (MCELF::GetBinding(SD) != ELF::STB_LOCAL)
 277     return ELF::R_MIPS_NONE;
 278
 279   if (Type == ELF::R_MIPS_GOT16)
 280     return ELF::R_MIPS_LO16;
 281   if (Type == ELF::R_MICROMIPS_GOT16)
 282     return ELF::R_MICROMIPS_LO16;
 283   if (Type == ELF::R_MIPS16_GOT16)
 284     return ELF::R_MIPS16_LO16;
 285
 286   return ELF::R_MIPS_NONE;
 287 }
 288
 289 // Return true if First needs a matching *LO16, its matching *LO16 type equals
 290 // Second's type and both relocations are against the same symbol.
 291 static bool areMatchingHiAndLo(const MCAssembler &Asm,
 292                                const ELFRelocationEntry &First,
 293                                const ELFRelocationEntry &Second) {
 294   return getMatchingLoType(Asm, First) != ELF::R_MIPS_NONE &&
 295          getMatchingLoType(Asm, First) == Second.Type &&
 296          First.Symbol && First.Symbol == Second.Symbol;
 297 }
 298
 299 // Return true if MipsRelocs[Index] is a *LO16 preceded by a matching *HI16.
 300 static bool
 301 isPrecededByMatchingHi(const MCAssembler &Asm, uint32_t Index,
 302                        std::vector<MipsRelocationEntry> &MipsRelocs) {
 303   return Index < MipsRelocs.size() - 1 &&
 304          areMatchingHiAndLo(Asm, MipsRelocs[Index + 1].R, MipsRelocs[Index].R);
 305 }
 306
 307 // Return true if MipsRelocs[Index] is a *LO16 not preceded by a matching *HI16
 308 // and not chosen by a *HI16 as a match.
 309 static bool isFreeLo(const MCAssembler &Asm, uint32_t Index,
 310                      std::vector<MipsRelocationEntry> &MipsRelocs) {
 311   return Index < MipsRelocs.size() && !MipsRelocs[Index].HasMatchingHi &&
 312          !isPrecededByMatchingHi(Asm, Index, MipsRelocs);
 313 }
 314
 315 // Lo is chosen as a match for Hi, set their fields accordingly.
 316 // Mips instructions have fixed length of at least two bytes (two for
 317 // micromips/mips16, four for mips32/64), so we can set HI's SortOffset to
 318 // matching LO's Offset minus one to simplify the sorting function.
 319 static void setMatch(MipsRelocationEntry &Hi, MipsRelocationEntry &Lo) {
 320   Lo.HasMatchingHi = true;
 321   Hi.SortOffset = Lo.R.Offset - 1;
 322 }
 323
 324 // We sort relocation table entries by offset, except for one additional rule
 325 // required by MIPS ABI: every *HI16 relocation must be immediately followed by
 326 // the corresponding *LO16 relocation. We also support a GNU extension that
 327 // allows more *HI16s paired with one *LO16.
 328 //
 329 // *HI16 relocations and their matching *LO16 are:
 330 //
 331 // +---------------------------------------------+-------------------+
 332 // |               *HI16                         |  matching *LO16   |
 333 // |---------------------------------------------+-------------------|
 334 // |  R_MIPS_HI16, local R_MIPS_GOT16            |    R_MIPS_LO16    |
 335 // |  R_MICROMIPS_HI16, local R_MICROMIPS_GOT16  | R_MICROMIPS_LO16  |
 336 // |  R_MIPS16_HI16, local R_MIPS16_GOT16        |  R_MIPS16_LO16    |
 337 // +---------------------------------------------+-------------------+
 338 //
 339 // (local R_*_GOT16 meaning R_*_GOT16 against the local symbol.)
 340 //
 341 // To handle *HI16 and *LO16 relocations, the linker needs a combined addend
 342 // ("AHL") calculated from both *HI16 ("AHI") and *LO16 ("ALO") relocations:
 343 // AHL = (AHI << 16) + (short)ALO;
 344 //
 345 // We are reusing gnu as sorting algorithm so we are emitting the relocation
 346 // table sorted the same way as gnu as would sort it, for easier comparison of
 347 // the generated .o files.
 348 //
 349 // The logic is:
 350 // search the table (starting from the highest offset and going back to zero)
 351 // for all *HI16 relocations that don't have a matching *LO16.
 352 // For every such HI, find a matching LO with highest offset that isn't already
 353 // matched with another HI. If there are no free LOs, match it with the first
 354 // found (starting from lowest offset).
 355 // When there are more HIs matched with one LO, sort them in descending order by
 356 // offset.
 357 //
 358 // In other words, when searching for a matching LO:
 359 // - don't look for a 'better' match for the HIs that are already followed by a
 360 //   matching LO;
 361 // - prefer LOs without a pair;
 362 // - prefer LOs with higher offset;
 363 void MipsELFObjectWriter::sortRelocs(const MCAssembler &Asm,
 364                                      std::vector<ELFRelocationEntry> &Relocs) {
 365   if (Relocs.size() < 2)
 366     return;
 367
 368   // The default function sorts entries by Offset in descending order.
 369   MCELFObjectTargetWriter::sortRelocs(Asm, Relocs);
 370
 371   // Init MipsRelocs from Relocs.
 372   std::vector<MipsRelocationEntry> MipsRelocs;
 373   for (unsigned I = 0, E = Relocs.size(); I != E; ++I)
 374     MipsRelocs.push_back(MipsRelocationEntry(Relocs[I]));
 375
 376   // Find a matching LO for all HIs that need it.
 377   for (int32_t I = 0, E = MipsRelocs.size(); I != E; ++I) {
 378     if (getMatchingLoType(Asm, MipsRelocs[I].R) == ELF::R_MIPS_NONE ||
 379         (I > 0 && isPrecededByMatchingHi(Asm, I - 1, MipsRelocs)))
 380       continue;
 381
 382     int32_t MatchedLoIndex = -1;
 383
 384     // Search the list in the ascending order of Offset.
 385     for (int32_t J = MipsRelocs.size() - 1, N = -1; J != N; --J) {
 386       // check for a match
 387       if (areMatchingHiAndLo(Asm, MipsRelocs[I].R, MipsRelocs[J].R) &&
 388           (MatchedLoIndex == -1 || // first match
 389            // or we already have a match,
 390            // but this one is with higher offset and it's free
 391            (MatchedLoIndex > J && isFreeLo(Asm, J, MipsRelocs))))
 392         MatchedLoIndex = J;
 393     }
 394
 395     if (MatchedLoIndex != -1)
 396       // We have a match.
 397       setMatch(MipsRelocs[I], MipsRelocs[MatchedLoIndex]);
 398   }
 399
 400   // SortOffsets are calculated, call the sorting function.
 401   array_pod_sort(MipsRelocs.begin(), MipsRelocs.end(), cmpRelMips);
 402
 403   // Copy sorted MipsRelocs back to Relocs.
 404   for (unsigned I = 0, E = MipsRelocs.size(); I != E; ++I)
 405     Relocs[I] = MipsRelocs[I].R;
 406 }
 407
 408 bool MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbol &Sym,
 409                                                   unsigned Type) const {
 410   // FIXME: This is extremely conservative. This really needs to use a
 411   // whitelist with a clear explanation for why each realocation needs to
 412   // point to the symbol, not to the section.
 413   switch (Type) {
 414   default:
 415     return true;
 416
 417   case ELF::R_MIPS_GOT16:
 418   case ELF::R_MIPS16_GOT16:
 419   case ELF::R_MICROMIPS_GOT16:
 420     llvm_unreachable("Should have been handled already");
 421
 422   // These relocations might be paired with another relocation. The pairing is
 423   // done by the static linker by matching the symbol. Since we only see one
 424   // relocation at a time, we have to force them to relocate with a symbol to
 425   // avoid ending up with a pair where one points to a section and another
 426   // points to a symbol.
 427   case ELF::R_MIPS_HI16:
 428   case ELF::R_MIPS16_HI16:
 429   case ELF::R_MICROMIPS_HI16:
 430   case ELF::R_MIPS_LO16:
 431   case ELF::R_MIPS16_LO16:
 432   case ELF::R_MICROMIPS_LO16:
 433     return true;
 434
 435   case ELF::R_MIPS_32:
 436     if (MCELF::getOther(Sym.getData()) & (ELF::STO_MIPS_MICROMIPS >> 2))
 437       return true;
 438     // falltrough
 439   case ELF::R_MIPS_26:
 440   case ELF::R_MIPS_64:
 441   case ELF::R_MIPS_GPREL16:
 442     return false;
 443   }
 444 }
 445
 446 MCObjectWriter *llvm::createMipsELFObjectWriter(raw_pwrite_stream &OS,
 447                                                 uint8_t OSABI,
 448                                                 bool IsLittleEndian,
 449                                                 bool Is64Bit) {
 450   MCELFObjectTargetWriter *MOTW =
 451       new MipsELFObjectWriter(Is64Bit, OSABI, Is64Bit, IsLittleEndian);
 452   return createELFObjectWriter(MOTW, OS, IsLittleEndian);
 453 }