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=a68bf16ee4f72b2a34fce94d180f4b2c429f9032;hb=872808e946f3f8be1b30a6672697c2ba8e12f9e1;hpb=a1bcd75ddd2df8ee6b85b3930ddd571f4cfb0e9c diff --git a/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp b/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp index a68bf16ee4f..4df92d067ea 100644 --- a/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp +++ b/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp @@ -10,6 +10,7 @@ #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" @@ -22,17 +23,33 @@ 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; }; } @@ -48,186 +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: - Type = ELF::R_MICROMIPS_PC7_S1; - break; + return ELF::R_MICROMIPS_PC7_S1; case Mips::fixup_MICROMIPS_PC10_S1: - Type = ELF::R_MICROMIPS_PC10_S1; - break; + 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. @@ -254,7 +384,7 @@ MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbolData &SD, return true; case ELF::R_MIPS_32: - if (MCELF::getOther(SD) & (ELF::STO_MIPS_MICROMIPS >> 2)) + if (MCELF::getOther(Sym) & (ELF::STO_MIPS_MICROMIPS >> 2)) return true; // falltrough case ELF::R_MIPS_26: @@ -264,7 +394,8 @@ MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbolData &SD, } } -MCObjectWriter *llvm::createMipsELFObjectWriter(raw_ostream &OS, uint8_t OSABI, +MCObjectWriter *llvm::createMipsELFObjectWriter(raw_pwrite_stream &OS, + uint8_t OSABI, bool IsLittleEndian, bool Is64Bit) { MCELFObjectTargetWriter *MOTW =