X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTarget%2FMips%2FMCTargetDesc%2FMipsELFObjectWriter.cpp;h=4df92d067ea659586a35e0ed99460fd9c9941cba;hp=d47a49bdd5fc438ac61a54dcd9f2b1d517fadf34;hb=872808e946f3f8be1b30a6672697c2ba8e12f9e1;hpb=b284d4ae3175aadd81445ec2712277397172aca5 diff --git a/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp b/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp index d47a49bdd5f..4df92d067ea 100644 --- a/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp +++ b/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp @@ -10,7 +10,9 @@ #include "MCTargetDesc/MipsBaseInfo.h" #include "MCTargetDesc/MipsFixupKinds.h" #include "MCTargetDesc/MipsMCTargetDesc.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/MC/MCAssembler.h" +#include "llvm/MC/MCELF.h" #include "llvm/MC/MCELFObjectWriter.h" #include "llvm/MC/MCExpr.h" #include "llvm/MC/MCSection.h" @@ -21,25 +23,41 @@ using namespace llvm; namespace { +// A helper structure based on ELFRelocationEntry, used for sorting entries in +// the relocation table. +struct MipsRelocationEntry { + MipsRelocationEntry(const ELFRelocationEntry &R) + : R(R), SortOffset(R.Offset), HasMatchingHi(false) {} + const ELFRelocationEntry R; + // SortOffset equals R.Offset except for the *HI16 relocations, for which it + // will be set based on the R.Offset of the matching *LO16 relocation. + int64_t SortOffset; + // True when this is a *LO16 relocation chosen as a match for a *HI16 + // relocation. + bool HasMatchingHi; +}; + class MipsELFObjectWriter : public MCELFObjectTargetWriter { public: MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI, bool _isN64, bool IsLittleEndian); - virtual ~MipsELFObjectWriter(); + ~MipsELFObjectWriter() override; unsigned GetRelocType(const MCValue &Target, const MCFixup &Fixup, bool IsPCRel) const override; - bool needsRelocateWithSymbol(const MCSymbolData &SD, + bool needsRelocateWithSymbol(const MCSymbol &Sym, unsigned Type) const override; + virtual void sortRelocs(const MCAssembler &Asm, + std::vector &Relocs) override; }; } MipsELFObjectWriter::MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI, bool _isN64, bool IsLittleEndian) - : MCELFObjectTargetWriter(_is64Bit, OSABI, ELF::EM_MIPS, - /*HasRelocationAddend*/ (_isN64) ? true : false, - /*IsN64*/ _isN64) {} + : MCELFObjectTargetWriter(_is64Bit, OSABI, ELF::EM_MIPS, + /*HasRelocationAddend*/ _isN64, + /*IsN64*/ _isN64) {} MipsELFObjectWriter::~MipsELFObjectWriter() {} @@ -47,178 +65,299 @@ unsigned MipsELFObjectWriter::GetRelocType(const MCValue &Target, const MCFixup &Fixup, bool IsPCRel) const { // determine the type of the relocation - unsigned Type = (unsigned)ELF::R_MIPS_NONE; unsigned Kind = (unsigned)Fixup.getKind(); switch (Kind) { - default: - llvm_unreachable("invalid fixup kind!"); + case Mips::fixup_Mips_32: case FK_Data_4: - Type = ELF::R_MIPS_32; - break; + return IsPCRel ? ELF::R_MIPS_PC32 : ELF::R_MIPS_32; + case Mips::fixup_Mips_64: case FK_Data_8: - Type = ELF::R_MIPS_64; - break; + return ELF::R_MIPS_64; case FK_GPRel_4: if (isN64()) { + unsigned Type = (unsigned)ELF::R_MIPS_NONE; Type = setRType((unsigned)ELF::R_MIPS_GPREL32, Type); Type = setRType2((unsigned)ELF::R_MIPS_64, Type); Type = setRType3((unsigned)ELF::R_MIPS_NONE, Type); + return Type; } - else - Type = ELF::R_MIPS_GPREL32; - break; + return ELF::R_MIPS_GPREL32; case Mips::fixup_Mips_GPREL16: - Type = ELF::R_MIPS_GPREL16; - break; + return ELF::R_MIPS_GPREL16; case Mips::fixup_Mips_26: - Type = ELF::R_MIPS_26; - break; + return ELF::R_MIPS_26; case Mips::fixup_Mips_CALL16: - Type = ELF::R_MIPS_CALL16; - break; + return ELF::R_MIPS_CALL16; case Mips::fixup_Mips_GOT_Global: case Mips::fixup_Mips_GOT_Local: - Type = ELF::R_MIPS_GOT16; - break; + return ELF::R_MIPS_GOT16; case Mips::fixup_Mips_HI16: - Type = ELF::R_MIPS_HI16; - break; + return ELF::R_MIPS_HI16; case Mips::fixup_Mips_LO16: - Type = ELF::R_MIPS_LO16; - break; + return ELF::R_MIPS_LO16; case Mips::fixup_Mips_TLSGD: - Type = ELF::R_MIPS_TLS_GD; - break; + return ELF::R_MIPS_TLS_GD; case Mips::fixup_Mips_GOTTPREL: - Type = ELF::R_MIPS_TLS_GOTTPREL; - break; + return ELF::R_MIPS_TLS_GOTTPREL; case Mips::fixup_Mips_TPREL_HI: - Type = ELF::R_MIPS_TLS_TPREL_HI16; - break; + return ELF::R_MIPS_TLS_TPREL_HI16; case Mips::fixup_Mips_TPREL_LO: - Type = ELF::R_MIPS_TLS_TPREL_LO16; - break; + return ELF::R_MIPS_TLS_TPREL_LO16; case Mips::fixup_Mips_TLSLDM: - Type = ELF::R_MIPS_TLS_LDM; - break; + return ELF::R_MIPS_TLS_LDM; case Mips::fixup_Mips_DTPREL_HI: - Type = ELF::R_MIPS_TLS_DTPREL_HI16; - break; + return ELF::R_MIPS_TLS_DTPREL_HI16; case Mips::fixup_Mips_DTPREL_LO: - Type = ELF::R_MIPS_TLS_DTPREL_LO16; - break; + return ELF::R_MIPS_TLS_DTPREL_LO16; case Mips::fixup_Mips_Branch_PCRel: case Mips::fixup_Mips_PC16: - Type = ELF::R_MIPS_PC16; - break; + return ELF::R_MIPS_PC16; case Mips::fixup_Mips_GOT_PAGE: - Type = ELF::R_MIPS_GOT_PAGE; - break; + return ELF::R_MIPS_GOT_PAGE; case Mips::fixup_Mips_GOT_OFST: - Type = ELF::R_MIPS_GOT_OFST; - break; + return ELF::R_MIPS_GOT_OFST; case Mips::fixup_Mips_GOT_DISP: - Type = ELF::R_MIPS_GOT_DISP; - break; - case Mips::fixup_Mips_GPOFF_HI: + return ELF::R_MIPS_GOT_DISP; + case Mips::fixup_Mips_GPOFF_HI: { + unsigned Type = (unsigned)ELF::R_MIPS_NONE; Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type); Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type); Type = setRType3((unsigned)ELF::R_MIPS_HI16, Type); - break; - case Mips::fixup_Mips_GPOFF_LO: + return Type; + } + case Mips::fixup_Mips_GPOFF_LO: { + unsigned Type = (unsigned)ELF::R_MIPS_NONE; Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type); Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type); Type = setRType3((unsigned)ELF::R_MIPS_LO16, Type); - break; + return Type; + } case Mips::fixup_Mips_HIGHER: - Type = ELF::R_MIPS_HIGHER; - break; + return ELF::R_MIPS_HIGHER; case Mips::fixup_Mips_HIGHEST: - Type = ELF::R_MIPS_HIGHEST; - break; + return ELF::R_MIPS_HIGHEST; case Mips::fixup_Mips_GOT_HI16: - Type = ELF::R_MIPS_GOT_HI16; - break; + return ELF::R_MIPS_GOT_HI16; case Mips::fixup_Mips_GOT_LO16: - Type = ELF::R_MIPS_GOT_LO16; - break; + return ELF::R_MIPS_GOT_LO16; case Mips::fixup_Mips_CALL_HI16: - Type = ELF::R_MIPS_CALL_HI16; - break; + return ELF::R_MIPS_CALL_HI16; case Mips::fixup_Mips_CALL_LO16: - Type = ELF::R_MIPS_CALL_LO16; - break; + return ELF::R_MIPS_CALL_LO16; case Mips::fixup_MICROMIPS_26_S1: - Type = ELF::R_MICROMIPS_26_S1; - break; + return ELF::R_MICROMIPS_26_S1; case Mips::fixup_MICROMIPS_HI16: - Type = ELF::R_MICROMIPS_HI16; - break; + return ELF::R_MICROMIPS_HI16; case Mips::fixup_MICROMIPS_LO16: - Type = ELF::R_MICROMIPS_LO16; - break; + return ELF::R_MICROMIPS_LO16; case Mips::fixup_MICROMIPS_GOT16: - Type = ELF::R_MICROMIPS_GOT16; - break; + return ELF::R_MICROMIPS_GOT16; + case Mips::fixup_MICROMIPS_PC7_S1: + return ELF::R_MICROMIPS_PC7_S1; + case Mips::fixup_MICROMIPS_PC10_S1: + return ELF::R_MICROMIPS_PC10_S1; case Mips::fixup_MICROMIPS_PC16_S1: - Type = ELF::R_MICROMIPS_PC16_S1; - break; + return ELF::R_MICROMIPS_PC16_S1; case Mips::fixup_MICROMIPS_CALL16: - Type = ELF::R_MICROMIPS_CALL16; - break; + return ELF::R_MICROMIPS_CALL16; case Mips::fixup_MICROMIPS_GOT_DISP: - Type = ELF::R_MICROMIPS_GOT_DISP; - break; + return ELF::R_MICROMIPS_GOT_DISP; case Mips::fixup_MICROMIPS_GOT_PAGE: - Type = ELF::R_MICROMIPS_GOT_PAGE; - break; + return ELF::R_MICROMIPS_GOT_PAGE; case Mips::fixup_MICROMIPS_GOT_OFST: - Type = ELF::R_MICROMIPS_GOT_OFST; - break; + return ELF::R_MICROMIPS_GOT_OFST; case Mips::fixup_MICROMIPS_TLS_GD: - Type = ELF::R_MICROMIPS_TLS_GD; - break; + return ELF::R_MICROMIPS_TLS_GD; case Mips::fixup_MICROMIPS_TLS_LDM: - Type = ELF::R_MICROMIPS_TLS_LDM; - break; + return ELF::R_MICROMIPS_TLS_LDM; case Mips::fixup_MICROMIPS_TLS_DTPREL_HI16: - Type = ELF::R_MICROMIPS_TLS_DTPREL_HI16; - break; + return ELF::R_MICROMIPS_TLS_DTPREL_HI16; case Mips::fixup_MICROMIPS_TLS_DTPREL_LO16: - Type = ELF::R_MICROMIPS_TLS_DTPREL_LO16; - break; + return ELF::R_MICROMIPS_TLS_DTPREL_LO16; case Mips::fixup_MICROMIPS_TLS_TPREL_HI16: - Type = ELF::R_MICROMIPS_TLS_TPREL_HI16; - break; + return ELF::R_MICROMIPS_TLS_TPREL_HI16; case Mips::fixup_MICROMIPS_TLS_TPREL_LO16: - Type = ELF::R_MICROMIPS_TLS_TPREL_LO16; - break; + return ELF::R_MICROMIPS_TLS_TPREL_LO16; case Mips::fixup_MIPS_PC19_S2: - Type = ELF::R_MIPS_PC19_S2; - break; + return ELF::R_MIPS_PC19_S2; case Mips::fixup_MIPS_PC18_S3: - Type = ELF::R_MIPS_PC18_S3; - break; + return ELF::R_MIPS_PC18_S3; case Mips::fixup_MIPS_PC21_S2: - Type = ELF::R_MIPS_PC21_S2; - break; + return ELF::R_MIPS_PC21_S2; case Mips::fixup_MIPS_PC26_S2: - Type = ELF::R_MIPS_PC26_S2; - break; + return ELF::R_MIPS_PC26_S2; case Mips::fixup_MIPS_PCHI16: - Type = ELF::R_MIPS_PCHI16; - break; + return ELF::R_MIPS_PCHI16; case Mips::fixup_MIPS_PCLO16: - Type = ELF::R_MIPS_PCLO16; - break; + return ELF::R_MIPS_PCLO16; + } + llvm_unreachable("invalid fixup kind!"); +} + +// Sort entries by SortOffset in descending order. +// When there are more *HI16 relocs paired with one *LO16 reloc, the 2nd rule +// sorts them in ascending order of R.Offset. +static int cmpRelMips(const MipsRelocationEntry *AP, + const MipsRelocationEntry *BP) { + const MipsRelocationEntry &A = *AP; + const MipsRelocationEntry &B = *BP; + if (A.SortOffset != B.SortOffset) + return B.SortOffset - A.SortOffset; + if (A.R.Offset != B.R.Offset) + return A.R.Offset - B.R.Offset; + if (B.R.Type != A.R.Type) + return B.R.Type - A.R.Type; + //llvm_unreachable("ELFRelocs might be unstable!"); + return 0; +} + +// For the given Reloc.Type, return the matching relocation type, as in the +// table below. +static unsigned getMatchingLoType(const MCAssembler &Asm, + const ELFRelocationEntry &Reloc) { + unsigned Type = Reloc.Type; + if (Type == ELF::R_MIPS_HI16) + return ELF::R_MIPS_LO16; + if (Type == ELF::R_MICROMIPS_HI16) + return ELF::R_MICROMIPS_LO16; + if (Type == ELF::R_MIPS16_HI16) + return ELF::R_MIPS16_LO16; + + if (MCELF::GetBinding(*Reloc.Symbol) != ELF::STB_LOCAL) + return ELF::R_MIPS_NONE; + + if (Type == ELF::R_MIPS_GOT16) + return ELF::R_MIPS_LO16; + if (Type == ELF::R_MICROMIPS_GOT16) + return ELF::R_MICROMIPS_LO16; + if (Type == ELF::R_MIPS16_GOT16) + return ELF::R_MIPS16_LO16; + + return ELF::R_MIPS_NONE; +} + +// Return true if First needs a matching *LO16, its matching *LO16 type equals +// Second's type and both relocations are against the same symbol. +static bool areMatchingHiAndLo(const MCAssembler &Asm, + const ELFRelocationEntry &First, + const ELFRelocationEntry &Second) { + return getMatchingLoType(Asm, First) != ELF::R_MIPS_NONE && + getMatchingLoType(Asm, First) == Second.Type && + First.Symbol && First.Symbol == Second.Symbol; +} + +// Return true if MipsRelocs[Index] is a *LO16 preceded by a matching *HI16. +static bool +isPrecededByMatchingHi(const MCAssembler &Asm, uint32_t Index, + std::vector &MipsRelocs) { + return Index < MipsRelocs.size() - 1 && + areMatchingHiAndLo(Asm, MipsRelocs[Index + 1].R, MipsRelocs[Index].R); +} + +// Return true if MipsRelocs[Index] is a *LO16 not preceded by a matching *HI16 +// and not chosen by a *HI16 as a match. +static bool isFreeLo(const MCAssembler &Asm, uint32_t Index, + std::vector &MipsRelocs) { + return Index < MipsRelocs.size() && !MipsRelocs[Index].HasMatchingHi && + !isPrecededByMatchingHi(Asm, Index, MipsRelocs); +} + +// Lo is chosen as a match for Hi, set their fields accordingly. +// Mips instructions have fixed length of at least two bytes (two for +// micromips/mips16, four for mips32/64), so we can set HI's SortOffset to +// matching LO's Offset minus one to simplify the sorting function. +static void setMatch(MipsRelocationEntry &Hi, MipsRelocationEntry &Lo) { + Lo.HasMatchingHi = true; + Hi.SortOffset = Lo.R.Offset - 1; +} + +// We sort relocation table entries by offset, except for one additional rule +// required by MIPS ABI: every *HI16 relocation must be immediately followed by +// the corresponding *LO16 relocation. We also support a GNU extension that +// allows more *HI16s paired with one *LO16. +// +// *HI16 relocations and their matching *LO16 are: +// +// +---------------------------------------------+-------------------+ +// | *HI16 | matching *LO16 | +// |---------------------------------------------+-------------------| +// | R_MIPS_HI16, local R_MIPS_GOT16 | R_MIPS_LO16 | +// | R_MICROMIPS_HI16, local R_MICROMIPS_GOT16 | R_MICROMIPS_LO16 | +// | R_MIPS16_HI16, local R_MIPS16_GOT16 | R_MIPS16_LO16 | +// +---------------------------------------------+-------------------+ +// +// (local R_*_GOT16 meaning R_*_GOT16 against the local symbol.) +// +// To handle *HI16 and *LO16 relocations, the linker needs a combined addend +// ("AHL") calculated from both *HI16 ("AHI") and *LO16 ("ALO") relocations: +// AHL = (AHI << 16) + (short)ALO; +// +// We are reusing gnu as sorting algorithm so we are emitting the relocation +// table sorted the same way as gnu as would sort it, for easier comparison of +// the generated .o files. +// +// The logic is: +// search the table (starting from the highest offset and going back to zero) +// for all *HI16 relocations that don't have a matching *LO16. +// For every such HI, find a matching LO with highest offset that isn't already +// matched with another HI. If there are no free LOs, match it with the first +// found (starting from lowest offset). +// When there are more HIs matched with one LO, sort them in descending order by +// offset. +// +// In other words, when searching for a matching LO: +// - don't look for a 'better' match for the HIs that are already followed by a +// matching LO; +// - prefer LOs without a pair; +// - prefer LOs with higher offset; +void MipsELFObjectWriter::sortRelocs(const MCAssembler &Asm, + std::vector &Relocs) { + if (Relocs.size() < 2) + return; + + // The default function sorts entries by Offset in descending order. + MCELFObjectTargetWriter::sortRelocs(Asm, Relocs); + + // Init MipsRelocs from Relocs. + std::vector MipsRelocs; + for (unsigned I = 0, E = Relocs.size(); I != E; ++I) + MipsRelocs.push_back(MipsRelocationEntry(Relocs[I])); + + // Find a matching LO for all HIs that need it. + for (int32_t I = 0, E = MipsRelocs.size(); I != E; ++I) { + if (getMatchingLoType(Asm, MipsRelocs[I].R) == ELF::R_MIPS_NONE || + (I > 0 && isPrecededByMatchingHi(Asm, I - 1, MipsRelocs))) + continue; + + int32_t MatchedLoIndex = -1; + + // Search the list in the ascending order of Offset. + for (int32_t J = MipsRelocs.size() - 1, N = -1; J != N; --J) { + // check for a match + if (areMatchingHiAndLo(Asm, MipsRelocs[I].R, MipsRelocs[J].R) && + (MatchedLoIndex == -1 || // first match + // or we already have a match, + // but this one is with higher offset and it's free + (MatchedLoIndex > J && isFreeLo(Asm, J, MipsRelocs)))) + MatchedLoIndex = J; + } + + if (MatchedLoIndex != -1) + // We have a match. + setMatch(MipsRelocs[I], MipsRelocs[MatchedLoIndex]); } - return Type; + + // SortOffsets are calculated, call the sorting function. + array_pod_sort(MipsRelocs.begin(), MipsRelocs.end(), cmpRelMips); + + // Copy sorted MipsRelocs back to Relocs. + for (unsigned I = 0, E = MipsRelocs.size(); I != E; ++I) + Relocs[I] = MipsRelocs[I].R; } -bool -MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbolData &SD, - unsigned Type) const { +bool MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbol &Sym, + unsigned Type) const { // FIXME: This is extremely conservative. This really needs to use a // whitelist with a clear explanation for why each realocation needs to // point to the symbol, not to the section. @@ -244,20 +383,22 @@ MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbolData &SD, case ELF::R_MICROMIPS_LO16: return true; - case ELF::R_MIPS_26: case ELF::R_MIPS_32: + if (MCELF::getOther(Sym) & (ELF::STO_MIPS_MICROMIPS >> 2)) + return true; + // falltrough + case ELF::R_MIPS_26: case ELF::R_MIPS_64: case ELF::R_MIPS_GPREL16: return false; } } -MCObjectWriter *llvm::createMipsELFObjectWriter(raw_ostream &OS, +MCObjectWriter *llvm::createMipsELFObjectWriter(raw_pwrite_stream &OS, uint8_t OSABI, bool IsLittleEndian, bool Is64Bit) { - MCELFObjectTargetWriter *MOTW = new MipsELFObjectWriter(Is64Bit, OSABI, - (Is64Bit) ? true : false, - IsLittleEndian); + MCELFObjectTargetWriter *MOTW = + new MipsELFObjectWriter(Is64Bit, OSABI, Is64Bit, IsLittleEndian); return createELFObjectWriter(MOTW, OS, IsLittleEndian); }