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