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