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