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 } 454