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 <algorithm> 11 #include <list> 12 #include "MCTargetDesc/MipsBaseInfo.h" 13 #include "MCTargetDesc/MipsFixupKinds.h" 14 #include "MCTargetDesc/MipsMCExpr.h" 15 #include "MCTargetDesc/MipsMCTargetDesc.h" 16 #include "llvm/ADT/STLExtras.h" 17 #include "llvm/MC/MCAssembler.h" 18 #include "llvm/MC/MCELFObjectWriter.h" 19 #include "llvm/MC/MCExpr.h" 20 #include "llvm/MC/MCSection.h" 21 #include "llvm/MC/MCSymbolELF.h" 22 #include "llvm/MC/MCValue.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/ErrorHandling.h" 25 26 #define DEBUG_TYPE "mips-elf-object-writer" 27 28 using namespace llvm; 29 30 namespace { 31 /// Holds additional information needed by the relocation ordering algorithm. 32 struct MipsRelocationEntry { 33 const ELFRelocationEntry R; ///< The relocation. 34 bool Matched; ///< Is this relocation part of a match. 35 36 MipsRelocationEntry(const ELFRelocationEntry &R) : R(R), Matched(false) {} 37 38 void print(raw_ostream &Out) const { 39 R.print(Out); 40 Out << ", Matched=" << Matched; 41 } 42 }; 43 44 raw_ostream &operator<<(raw_ostream &OS, const MipsRelocationEntry &RHS) { 45 RHS.print(OS); 46 return OS; 47 } 48 49 class MipsELFObjectWriter : public MCELFObjectTargetWriter { 50 public: 51 MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI, bool _isN64, 52 bool IsLittleEndian); 53 54 ~MipsELFObjectWriter() override; 55 56 unsigned getRelocType(MCContext &Ctx, const MCValue &Target, 57 const MCFixup &Fixup, bool IsPCRel) const override; 58 bool needsRelocateWithSymbol(const MCSymbol &Sym, 59 unsigned Type) const override; 60 virtual void sortRelocs(const MCAssembler &Asm, 61 std::vector<ELFRelocationEntry> &Relocs) override; 62 }; 63 64 /// Copy elements in the range [First, Last) to d1 when the predicate is true or 65 /// d2 when the predicate is false. This is essentially both std::copy_if and 66 /// std::remove_copy_if combined into a single pass. 67 template <class InputIt, class OutputIt1, class OutputIt2, class UnaryPredicate> 68 std::pair<OutputIt1, OutputIt2> copy_if_else(InputIt First, InputIt Last, 69 OutputIt1 d1, OutputIt2 d2, 70 UnaryPredicate Predicate) { 71 for (InputIt I = First; I != Last; ++I) { 72 if (Predicate(*I)) { 73 *d1 = *I; 74 d1++; 75 } else { 76 *d2 = *I; 77 d2++; 78 } 79 } 80 81 return std::make_pair(d1, d2); 82 } 83 84 /// The possible results of the Predicate function used by find_best. 85 enum FindBestPredicateResult { 86 FindBest_NoMatch = 0, ///< The current element is not a match. 87 FindBest_Match, ///< The current element is a match but better ones are 88 /// possible. 89 FindBest_PerfectMatch, ///< The current element is an unbeatable match. 90 }; 91 92 /// Find the best match in the range [First, Last). 93 /// 94 /// An element matches when Predicate(X) returns FindBest_Match or 95 /// FindBest_PerfectMatch. A value of FindBest_PerfectMatch also terminates 96 /// the search. BetterThan(A, B) is a comparator that returns true when A is a 97 /// better match than B. The return value is the position of the best match. 98 /// 99 /// This is similar to std::find_if but finds the best of multiple possible 100 /// matches. 101 template <class InputIt, class UnaryPredicate, class Comparator> 102 InputIt find_best(InputIt First, InputIt Last, UnaryPredicate Predicate, 103 Comparator BetterThan) { 104 InputIt Best = Last; 105 106 for (InputIt I = First; I != Last; ++I) { 107 unsigned Matched = Predicate(*I); 108 if (Matched != FindBest_NoMatch) { 109 DEBUG(dbgs() << std::distance(First, I) << " is a match ("; 110 I->print(dbgs()); dbgs() << ")\n"); 111 if (Best == Last || BetterThan(*I, *Best)) { 112 DEBUG(dbgs() << ".. and it beats the last one\n"); 113 Best = I; 114 } 115 } 116 if (Matched == FindBest_PerfectMatch) { 117 DEBUG(dbgs() << ".. and it is unbeatable\n"); 118 break; 119 } 120 } 121 122 return Best; 123 } 124 125 /// Determine the low relocation that matches the given relocation. 126 /// If the relocation does not need a low relocation then the return value 127 /// is ELF::R_MIPS_NONE. 128 /// 129 /// The relocations that need a matching low part are 130 /// R_(MIPS|MICROMIPS|MIPS16)_HI16 for all symbols and 131 /// R_(MIPS|MICROMIPS|MIPS16)_GOT16 for local symbols only. 132 static unsigned getMatchingLoType(const ELFRelocationEntry &Reloc) { 133 unsigned Type = Reloc.Type; 134 if (Type == ELF::R_MIPS_HI16) 135 return ELF::R_MIPS_LO16; 136 if (Type == ELF::R_MICROMIPS_HI16) 137 return ELF::R_MICROMIPS_LO16; 138 if (Type == ELF::R_MIPS16_HI16) 139 return ELF::R_MIPS16_LO16; 140 141 if (Reloc.OriginalSymbol->getBinding() != ELF::STB_LOCAL) 142 return ELF::R_MIPS_NONE; 143 144 if (Type == ELF::R_MIPS_GOT16) 145 return ELF::R_MIPS_LO16; 146 if (Type == ELF::R_MICROMIPS_GOT16) 147 return ELF::R_MICROMIPS_LO16; 148 if (Type == ELF::R_MIPS16_GOT16) 149 return ELF::R_MIPS16_LO16; 150 151 return ELF::R_MIPS_NONE; 152 } 153 154 /// Determine whether a relocation (X) matches the one given in R. 155 /// 156 /// A relocation matches if: 157 /// - It's type matches that of a corresponding low part. This is provided in 158 /// MatchingType for efficiency. 159 /// - It's based on the same symbol. 160 /// - It's offset of greater or equal to that of the one given in R. 161 /// It should be noted that this rule assumes the programmer does not use 162 /// offsets that exceed the alignment of the symbol. The carry-bit will be 163 /// incorrect if this is not true. 164 /// 165 /// A matching relocation is unbeatable if: 166 /// - It is not already involved in a match. 167 /// - It's offset is exactly that of the one given in R. 168 static bool isMatchingReloc(const MipsRelocationEntry &X, 169 const ELFRelocationEntry &R, 170 unsigned MatchingType) { 171 if (X.R.Type == MatchingType && X.R.OriginalSymbol == R.OriginalSymbol) { 172 if (!X.Matched && 173 X.R.OriginalAddend == R.OriginalAddend) 174 return FindBest_PerfectMatch; 175 else if (X.R.OriginalAddend >= R.OriginalAddend) 176 return FindBest_Match; 177 } 178 return FindBest_NoMatch; 179 } 180 181 /// Determine whether Candidate or PreviousBest is the better match. 182 /// The return value is true if Candidate is the better match. 183 /// 184 /// A matching relocation is a better match if: 185 /// - It has a smaller addend. 186 /// - It is not already involved in a match. 187 static bool compareMatchingRelocs(const MipsRelocationEntry &Candidate, 188 const MipsRelocationEntry &PreviousBest) { 189 if (Candidate.R.OriginalAddend != PreviousBest.R.OriginalAddend) 190 return Candidate.R.OriginalAddend < PreviousBest.R.OriginalAddend; 191 return PreviousBest.Matched && !Candidate.Matched; 192 } 193 194 #ifndef NDEBUG 195 /// Print all the relocations. 196 template <class Container> 197 static void dumpRelocs(const char *Prefix, const Container &Relocs) { 198 for (const auto &R : Relocs) 199 dbgs() << Prefix << R << "\n"; 200 } 201 #endif 202 203 } // end anonymous namespace 204 205 MipsELFObjectWriter::MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI, 206 bool _isN64, bool IsLittleEndian) 207 : MCELFObjectTargetWriter(_is64Bit, OSABI, ELF::EM_MIPS, 208 /*HasRelocationAddend*/ _isN64, 209 /*IsN64*/ _isN64) {} 210 211 MipsELFObjectWriter::~MipsELFObjectWriter() {} 212 213 unsigned MipsELFObjectWriter::getRelocType(MCContext &Ctx, 214 const MCValue &Target, 215 const MCFixup &Fixup, 216 bool IsPCRel) const { 217 // Determine the type of the relocation. 218 unsigned Kind = (unsigned)Fixup.getKind(); 219 220 switch (Kind) { 221 case Mips::fixup_Mips_NONE: 222 return ELF::R_MIPS_NONE; 223 case Mips::fixup_Mips_16: 224 case FK_Data_2: 225 return IsPCRel ? ELF::R_MIPS_PC16 : ELF::R_MIPS_16; 226 case Mips::fixup_Mips_32: 227 case FK_Data_4: 228 return IsPCRel ? ELF::R_MIPS_PC32 : ELF::R_MIPS_32; 229 } 230 231 if (IsPCRel) { 232 switch (Kind) { 233 case Mips::fixup_Mips_Branch_PCRel: 234 case Mips::fixup_Mips_PC16: 235 return ELF::R_MIPS_PC16; 236 case Mips::fixup_MICROMIPS_PC7_S1: 237 return ELF::R_MICROMIPS_PC7_S1; 238 case Mips::fixup_MICROMIPS_PC10_S1: 239 return ELF::R_MICROMIPS_PC10_S1; 240 case Mips::fixup_MICROMIPS_PC16_S1: 241 return ELF::R_MICROMIPS_PC16_S1; 242 case Mips::fixup_MICROMIPS_PC26_S1: 243 return ELF::R_MICROMIPS_PC26_S1; 244 case Mips::fixup_MICROMIPS_PC19_S2: 245 return ELF::R_MICROMIPS_PC19_S2; 246 case Mips::fixup_MICROMIPS_PC18_S3: 247 return ELF::R_MICROMIPS_PC18_S3; 248 case Mips::fixup_MIPS_PC19_S2: 249 return ELF::R_MIPS_PC19_S2; 250 case Mips::fixup_MIPS_PC18_S3: 251 return ELF::R_MIPS_PC18_S3; 252 case Mips::fixup_MIPS_PC21_S2: 253 return ELF::R_MIPS_PC21_S2; 254 case Mips::fixup_MIPS_PC26_S2: 255 return ELF::R_MIPS_PC26_S2; 256 case Mips::fixup_MIPS_PCHI16: 257 return ELF::R_MIPS_PCHI16; 258 case Mips::fixup_MIPS_PCLO16: 259 return ELF::R_MIPS_PCLO16; 260 } 261 262 llvm_unreachable("invalid PC-relative fixup kind!"); 263 } 264 265 switch (Kind) { 266 case Mips::fixup_Mips_64: 267 case FK_Data_8: 268 return ELF::R_MIPS_64; 269 case FK_GPRel_4: 270 if (isN64()) { 271 unsigned Type = (unsigned)ELF::R_MIPS_NONE; 272 Type = setRType((unsigned)ELF::R_MIPS_GPREL32, Type); 273 Type = setRType2((unsigned)ELF::R_MIPS_64, Type); 274 Type = setRType3((unsigned)ELF::R_MIPS_NONE, Type); 275 return Type; 276 } 277 return ELF::R_MIPS_GPREL32; 278 case Mips::fixup_Mips_GPREL16: 279 return ELF::R_MIPS_GPREL16; 280 case Mips::fixup_Mips_26: 281 return ELF::R_MIPS_26; 282 case Mips::fixup_Mips_CALL16: 283 return ELF::R_MIPS_CALL16; 284 case Mips::fixup_Mips_GOT: 285 return ELF::R_MIPS_GOT16; 286 case Mips::fixup_Mips_HI16: 287 return ELF::R_MIPS_HI16; 288 case Mips::fixup_Mips_LO16: 289 return ELF::R_MIPS_LO16; 290 case Mips::fixup_Mips_TLSGD: 291 return ELF::R_MIPS_TLS_GD; 292 case Mips::fixup_Mips_GOTTPREL: 293 return ELF::R_MIPS_TLS_GOTTPREL; 294 case Mips::fixup_Mips_TPREL_HI: 295 return ELF::R_MIPS_TLS_TPREL_HI16; 296 case Mips::fixup_Mips_TPREL_LO: 297 return ELF::R_MIPS_TLS_TPREL_LO16; 298 case Mips::fixup_Mips_TLSLDM: 299 return ELF::R_MIPS_TLS_LDM; 300 case Mips::fixup_Mips_DTPREL_HI: 301 return ELF::R_MIPS_TLS_DTPREL_HI16; 302 case Mips::fixup_Mips_DTPREL_LO: 303 return ELF::R_MIPS_TLS_DTPREL_LO16; 304 case Mips::fixup_Mips_GOT_PAGE: 305 return ELF::R_MIPS_GOT_PAGE; 306 case Mips::fixup_Mips_GOT_OFST: 307 return ELF::R_MIPS_GOT_OFST; 308 case Mips::fixup_Mips_GOT_DISP: 309 return ELF::R_MIPS_GOT_DISP; 310 case Mips::fixup_Mips_GPOFF_HI: { 311 unsigned Type = (unsigned)ELF::R_MIPS_NONE; 312 Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type); 313 Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type); 314 Type = setRType3((unsigned)ELF::R_MIPS_HI16, Type); 315 return Type; 316 } 317 case Mips::fixup_Mips_GPOFF_LO: { 318 unsigned Type = (unsigned)ELF::R_MIPS_NONE; 319 Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type); 320 Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type); 321 Type = setRType3((unsigned)ELF::R_MIPS_LO16, Type); 322 return Type; 323 } 324 case Mips::fixup_Mips_HIGHER: 325 return ELF::R_MIPS_HIGHER; 326 case Mips::fixup_Mips_HIGHEST: 327 return ELF::R_MIPS_HIGHEST; 328 case Mips::fixup_Mips_GOT_HI16: 329 return ELF::R_MIPS_GOT_HI16; 330 case Mips::fixup_Mips_GOT_LO16: 331 return ELF::R_MIPS_GOT_LO16; 332 case Mips::fixup_Mips_CALL_HI16: 333 return ELF::R_MIPS_CALL_HI16; 334 case Mips::fixup_Mips_CALL_LO16: 335 return ELF::R_MIPS_CALL_LO16; 336 case Mips::fixup_MICROMIPS_26_S1: 337 return ELF::R_MICROMIPS_26_S1; 338 case Mips::fixup_MICROMIPS_HI16: 339 return ELF::R_MICROMIPS_HI16; 340 case Mips::fixup_MICROMIPS_LO16: 341 return ELF::R_MICROMIPS_LO16; 342 case Mips::fixup_MICROMIPS_GOT16: 343 return ELF::R_MICROMIPS_GOT16; 344 case Mips::fixup_MICROMIPS_CALL16: 345 return ELF::R_MICROMIPS_CALL16; 346 case Mips::fixup_MICROMIPS_GOT_DISP: 347 return ELF::R_MICROMIPS_GOT_DISP; 348 case Mips::fixup_MICROMIPS_GOT_PAGE: 349 return ELF::R_MICROMIPS_GOT_PAGE; 350 case Mips::fixup_MICROMIPS_GOT_OFST: 351 return ELF::R_MICROMIPS_GOT_OFST; 352 case Mips::fixup_MICROMIPS_TLS_GD: 353 return ELF::R_MICROMIPS_TLS_GD; 354 case Mips::fixup_MICROMIPS_TLS_LDM: 355 return ELF::R_MICROMIPS_TLS_LDM; 356 case Mips::fixup_MICROMIPS_TLS_DTPREL_HI16: 357 return ELF::R_MICROMIPS_TLS_DTPREL_HI16; 358 case Mips::fixup_MICROMIPS_TLS_DTPREL_LO16: 359 return ELF::R_MICROMIPS_TLS_DTPREL_LO16; 360 case Mips::fixup_MICROMIPS_TLS_TPREL_HI16: 361 return ELF::R_MICROMIPS_TLS_TPREL_HI16; 362 case Mips::fixup_MICROMIPS_TLS_TPREL_LO16: 363 return ELF::R_MICROMIPS_TLS_TPREL_LO16; 364 } 365 366 llvm_unreachable("invalid fixup kind!"); 367 } 368 369 /// Sort relocation table entries by offset except where another order is 370 /// required by the MIPS ABI. 371 /// 372 /// MIPS has a few relocations that have an AHL component in the expression used 373 /// to evaluate them. This AHL component is an addend with the same number of 374 /// bits as a symbol value but not all of our ABI's are able to supply a 375 /// sufficiently sized addend in a single relocation. 376 /// 377 /// The O32 ABI for example, uses REL relocations which store the addend in the 378 /// section data. All the relocations with AHL components affect 16-bit fields 379 /// so the addend for a single relocation is limited to 16-bit. This ABI 380 /// resolves the limitation by linking relocations (e.g. R_MIPS_HI16 and 381 /// R_MIPS_LO16) and distributing the addend between the linked relocations. The 382 /// ABI mandates that such relocations must be next to each other in a 383 /// particular order (e.g. R_MIPS_HI16 must be immediately followed by a 384 /// matching R_MIPS_LO16) but the rule is less strict in practice. 385 /// 386 /// The de facto standard is lenient in the following ways: 387 /// - 'Immediately following' does not refer to the next relocation entry but 388 /// the next matching relocation. 389 /// - There may be multiple high parts relocations for one low part relocation. 390 /// - There may be multiple low part relocations for one high part relocation. 391 /// - The AHL addend in each part does not have to be exactly equal as long as 392 /// the difference does not affect the carry bit from bit 15 into 16. This is 393 /// to allow, for example, the use of %lo(foo) and %lo(foo+4) when loading 394 /// both halves of a long long. 395 /// 396 /// See getMatchingLoType() for a description of which high part relocations 397 /// match which low part relocations. One particular thing to note is that 398 /// R_MIPS_GOT16 and similar only have AHL addends if they refer to local 399 /// symbols. 400 /// 401 /// It should also be noted that this function is not affected by whether 402 /// the symbol was kept or rewritten into a section-relative equivalent. We 403 /// always match using the expressions from the source. 404 void MipsELFObjectWriter::sortRelocs(const MCAssembler &Asm, 405 std::vector<ELFRelocationEntry> &Relocs) { 406 if (Relocs.size() < 2) 407 return; 408 409 // Sort relocations by the address they are applied to. 410 std::sort(Relocs.begin(), Relocs.end(), 411 [](const ELFRelocationEntry &A, const ELFRelocationEntry &B) { 412 return A.Offset < B.Offset; 413 }); 414 415 std::list<MipsRelocationEntry> Sorted; 416 std::list<ELFRelocationEntry> Remainder; 417 418 DEBUG(dumpRelocs("R: ", Relocs)); 419 420 // Separate the movable relocations (AHL relocations using the high bits) from 421 // the immobile relocations (everything else). This does not preserve high/low 422 // matches that already existed in the input. 423 copy_if_else(Relocs.begin(), Relocs.end(), std::back_inserter(Remainder), 424 std::back_inserter(Sorted), [](const ELFRelocationEntry &Reloc) { 425 return getMatchingLoType(Reloc) != ELF::R_MIPS_NONE; 426 }); 427 428 for (auto &R : Remainder) { 429 DEBUG(dbgs() << "Matching: " << R << "\n"); 430 431 unsigned MatchingType = getMatchingLoType(R); 432 assert(MatchingType != ELF::R_MIPS_NONE && 433 "Wrong list for reloc that doesn't need a match"); 434 435 // Find the best matching relocation for the current high part. 436 // See isMatchingReloc for a description of a matching relocation and 437 // compareMatchingRelocs for a description of what 'best' means. 438 auto InsertionPoint = 439 find_best(Sorted.begin(), Sorted.end(), 440 [&R, &MatchingType](const MipsRelocationEntry &X) { 441 return isMatchingReloc(X, R, MatchingType); 442 }, 443 compareMatchingRelocs); 444 445 // If we matched then insert the high part in front of the match and mark 446 // both relocations as being involved in a match. We only mark the high 447 // part for cosmetic reasons in the debug output. 448 // 449 // If we failed to find a match then the high part is orphaned. This is not 450 // permitted since the relocation cannot be evaluated without knowing the 451 // carry-in. We can sometimes handle this using a matching low part that is 452 // already used in a match but we already cover that case in 453 // isMatchingReloc and compareMatchingRelocs. For the remaining cases we 454 // should insert the high part at the end of the list. This will cause the 455 // linker to fail but the alternative is to cause the linker to bind the 456 // high part to a semi-matching low part and silently calculate the wrong 457 // value. Unfortunately we have no means to warn the user that we did this 458 // so leave it up to the linker to complain about it. 459 if (InsertionPoint != Sorted.end()) 460 InsertionPoint->Matched = true; 461 Sorted.insert(InsertionPoint, R)->Matched = true; 462 } 463 464 DEBUG(dumpRelocs("S: ", Sorted)); 465 466 assert(Relocs.size() == Sorted.size() && "Some relocs were not consumed"); 467 468 // Overwrite the original vector with the sorted elements. The caller expects 469 // them in reverse order. 470 unsigned CopyTo = 0; 471 for (const auto &R : reverse(Sorted)) 472 Relocs[CopyTo++] = R.R; 473 } 474 475 bool MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbol &Sym, 476 unsigned Type) const { 477 // FIXME: This is extremely conservative. This really needs to use a 478 // whitelist with a clear explanation for why each realocation needs to 479 // point to the symbol, not to the section. 480 switch (Type) { 481 default: 482 return true; 483 484 case ELF::R_MIPS_GOT16: 485 case ELF::R_MIPS16_GOT16: 486 case ELF::R_MICROMIPS_GOT16: 487 return true; 488 489 // These relocations might be paired with another relocation. The pairing is 490 // done by the static linker by matching the symbol. Since we only see one 491 // relocation at a time, we have to force them to relocate with a symbol to 492 // avoid ending up with a pair where one points to a section and another 493 // points to a symbol. 494 case ELF::R_MIPS_HI16: 495 case ELF::R_MIPS16_HI16: 496 case ELF::R_MICROMIPS_HI16: 497 case ELF::R_MIPS_LO16: 498 case ELF::R_MIPS16_LO16: 499 case ELF::R_MICROMIPS_LO16: 500 return true; 501 502 case ELF::R_MIPS_16: 503 case ELF::R_MIPS_32: 504 if (cast<MCSymbolELF>(Sym).getOther() & ELF::STO_MIPS_MICROMIPS) 505 return true; 506 // falltrough 507 case ELF::R_MIPS_26: 508 case ELF::R_MIPS_64: 509 case ELF::R_MIPS_GPREL16: 510 return false; 511 } 512 } 513 514 MCObjectWriter *llvm::createMipsELFObjectWriter(raw_pwrite_stream &OS, 515 uint8_t OSABI, 516 bool IsLittleEndian, 517 bool Is64Bit) { 518 MCELFObjectTargetWriter *MOTW = 519 new MipsELFObjectWriter(Is64Bit, OSABI, Is64Bit, IsLittleEndian); 520 return createELFObjectWriter(MOTW, OS, IsLittleEndian); 521 } 522