Index: include/llvm/MC/MCELFObjectWriter.h =================================================================== --- include/llvm/MC/MCELFObjectWriter.h +++ include/llvm/MC/MCELFObjectWriter.h @@ -25,6 +25,17 @@ class MCSymbolData; class MCValue; +struct ELFRelocationEntry { + uint64_t Offset; // Where is the relocation. + const MCSymbol *Symbol; // The symbol to relocate with. + unsigned Type; // The type of the relocation. + uint64_t Addend; // The addend to use. + + ELFRelocationEntry(uint64_t Offset, const MCSymbol *Symbol, unsigned Type, + uint64_t Addend) + : Offset(Offset), Symbol(Symbol), Type(Type), Addend(Addend) {} +}; + class MCELFObjectTargetWriter { const uint8_t OSABI; const uint16_t EMachine; @@ -61,6 +72,9 @@ virtual bool needsRelocateWithSymbol(const MCSymbolData &SD, unsigned Type) const; + virtual void sortRelocs(const MCAssembler &Asm, + std::vector &Relocs); + /// @name Accessors /// @{ uint8_t getOSABI() const { return OSABI; } Index: lib/MC/ELFObjectWriter.cpp =================================================================== --- lib/MC/ELFObjectWriter.cpp +++ lib/MC/ELFObjectWriter.cpp @@ -79,17 +79,6 @@ uint8_t other, uint32_t shndx, bool Reserved); }; -struct ELFRelocationEntry { - uint64_t Offset; // Where is the relocation. - const MCSymbol *Symbol; // The symbol to relocate with. - unsigned Type; // The type of the relocation. - uint64_t Addend; // The addend to use. - - ELFRelocationEntry(uint64_t Offset, const MCSymbol *Symbol, unsigned Type, - uint64_t Addend) - : Offset(Offset), Symbol(Symbol), Type(Type), Addend(Addend) {} -}; - class ELFObjectWriter : public MCObjectWriter { FragmentWriter FWriter; @@ -1338,30 +1327,14 @@ WriteWord(EntrySize); // sh_entsize } -// ELF doesn't require relocations to be in any order. We sort by the r_offset, -// just to match gnu as for easier comparison. The use type is an arbitrary way -// of making the sort deterministic. -static int cmpRel(const ELFRelocationEntry *AP, const ELFRelocationEntry *BP) { - const ELFRelocationEntry &A = *AP; - const ELFRelocationEntry &B = *BP; - if (A.Offset != B.Offset) - return B.Offset - A.Offset; - if (B.Type != A.Type) - return A.Type - B.Type; - llvm_unreachable("ELFRelocs might be unstable!"); -} - -static void sortRelocs(const MCAssembler &Asm, - std::vector &Relocs) { - array_pod_sort(Relocs.begin(), Relocs.end(), cmpRel); -} - void ELFObjectWriter::WriteRelocationsFragment(const MCAssembler &Asm, MCDataFragment *F, const MCSectionData *SD) { std::vector &Relocs = Relocations[SD]; - sortRelocs(Asm, Relocs); + // Sort the relocation entries. Most targets just sort by Offset, but some + // (e.g., MIPS) have additional constraints. + TargetObjectWriter->sortRelocs(Asm, Relocs); for (unsigned i = 0, e = Relocs.size(); i != e; ++i) { const ELFRelocationEntry &Entry = Relocs[e - i - 1]; Index: lib/MC/MCELFObjectTargetWriter.cpp =================================================================== --- lib/MC/MCELFObjectTargetWriter.cpp +++ lib/MC/MCELFObjectTargetWriter.cpp @@ -28,3 +28,23 @@ unsigned Type) const { return false; } + + +// ELF doesn't require relocations to be in any order. We sort by the Offset, +// just to match gnu as for easier comparison. The use type is an arbitrary way +// of making the sort deterministic. +static int cmpRel(const ELFRelocationEntry *AP, const ELFRelocationEntry *BP) { + const ELFRelocationEntry &A = *AP; + const ELFRelocationEntry &B = *BP; + if (A.Offset != B.Offset) + return B.Offset - A.Offset; + if (B.Type != A.Type) + return A.Type - B.Type; + llvm_unreachable("ELFRelocs might be unstable!"); +} + +void +MCELFObjectTargetWriter::sortRelocs(const MCAssembler &Asm, + std::vector &Relocs) { + array_pod_sort(Relocs.begin(), Relocs.end(), cmpRel); +} Index: lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp =================================================================== --- lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp +++ 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,6 +23,31 @@ using namespace llvm; namespace { +// A helper structure based on ELFRelocationEntry, used for sorting entries in +// the relocation table. +struct MipsRelocationEntry { + MipsRelocationEntry(ELFRelocationEntry &R, unsigned MatchingLo): + Reloc(R), SortOffset(R.Offset), MatchingLoType(MatchingLo), + IsPrevMatchingHi(false), IsNextMatchingLo(false), MatchedLoIndex(-1) {} + + ELFRelocationEntry Reloc; + // SortOffset equals Reloc.Offset except for the *HI16 relocations, for which + // it will be set based on the Reloc.Offset of the corresponding *LO16 + // relocation. + int64_t SortOffset; + // For *HI16 relocations, a matching relocation type for Reloc.Type. + int64_t MatchingLoType; + // True when this is a *LO16 relocation preceded with a matching *HI16 + // relocation in the relocation table. + bool IsPrevMatchingHi; + // True when this is a *HI16 relocation followed by a matching *LO16 in the + // relocation table. + bool IsNextMatchingLo; + // For *HI16 relocations, index of the matching *LO16 in the MipsRelocs + // vector. + int32_t MatchedLoIndex; +}; + class MipsELFObjectWriter : public MCELFObjectTargetWriter { public: MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI, @@ -33,6 +59,8 @@ bool IsPCRel) const override; bool needsRelocateWithSymbol(const MCSymbolData &SD, unsigned Type) const override; + virtual void sortRelocs(const MCAssembler &Asm, + std::vector &Relocs) override; }; } @@ -223,6 +251,152 @@ return Type; } +// 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 Reloc.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.Reloc.Offset != B.Reloc.Offset) + return A.Reloc.Offset - B.Reloc.Offset; + if (B.Reloc.Type != A.Reloc.Type) + return B.Reloc.Type - A.Reloc.Type; + llvm_unreachable("ELFRelocs might be unstable!"); +} + +// For the given Reloc.Type, return the matching relocation type, as in the +// table below. +static unsigned getMatchingLoType(const MCAssembler &Asm, + ELFRelocationEntry &Reloc) { + if (Reloc.Type == ELF::R_MIPS_HI16) return ELF::R_MIPS_LO16; + if (Reloc.Type == ELF::R_MICROMIPS_HI16) return ELF::R_MICROMIPS_LO16; + if (Reloc.Type == ELF::R_MIPS16_HI16) return ELF::R_MIPS16_LO16; + + // Don't check if symbol is local for non-*GOT16 relocations. + if (!(Reloc.Type == ELF::R_MIPS_GOT16 + || Reloc.Type == ELF::R_MICROMIPS_GOT16 + || Reloc.Type == ELF::R_MIPS16_GOT16)) + return ELF::R_MIPS_NONE; + + const MCSymbolData &SD = Asm.getSymbolData(*Reloc.Symbol); + if (MCELF::GetBinding(SD) == ELF::STB_LOCAL) { + if (Reloc.Type == ELF::R_MIPS_GOT16) return ELF::R_MIPS_LO16; + if (Reloc.Type == ELF::R_MICROMIPS_GOT16) return ELF::R_MICROMIPS_LO16; + if (Reloc.Type == ELF::R_MIPS16_GOT16) return ELF::R_MIPS16_LO16; + } + + return ELF::R_MIPS_NONE; +} + +// Return true if first needs a matching LO, its matching LO type equals +// second's type and both relocations are against the same symbol. +static bool areMatchingHiAndLo(MipsRelocationEntry &first, + MipsRelocationEntry &second) { + return first.MatchingLoType != ELF::R_MIPS_NONE + && first.MatchingLoType == second.Reloc.Type + && first.Reloc.Symbol + && first.Reloc.Symbol == second.Reloc.Symbol; +} + +// lo is chosen as a match for hi, set their fields accordingly. +static void setMatch(MipsRelocationEntry &Hi, + MipsRelocationEntry &Lo) { + Lo.IsPrevMatchingHi = true; + Hi.IsNextMatchingLo = true; + Hi.SortOffset = Lo.Reloc.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; +// +// When there is more than one way to sort the table while respecting the ABI +// rule, we try to replicate binutils' behaviour, for no other reason than +// consistency with what gnu as produces. +// +// 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 a matching LO: +// - don't look for a 'better' match for the HIs that are already followed with +// 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) { + unsigned MatchingLoType = getMatchingLoType(Asm, Relocs[I]); + MipsRelocs.push_back(MipsRelocationEntry(Relocs[I], MatchingLoType)); + + // Find HIs that need a matching LO. + // Also find HIs and LOs that are already matched. + if (I > 0 && areMatchingHiAndLo(MipsRelocs[I], MipsRelocs[I-1])) + setMatch(MipsRelocs[I], MipsRelocs[I-1]); + } + + // Find a matching LO for all HIs that need it. + for (int32_t I = 0, E = MipsRelocs.size(); I != E; ++I) { + if (MipsRelocs[I].MatchingLoType == ELF::R_MIPS_NONE // not HI + || MipsRelocs[I].IsNextMatchingLo) // already followed by LO + continue; + + // Search the list in the ascending order of Offset. + for (int32_t J = MipsRelocs.size() -1, N = -1; J != N; --J) { + if (areMatchingHiAndLo(MipsRelocs[I], MipsRelocs[J]) // check for a match + && (MipsRelocs[I].MatchedLoIndex == -1 // first match + // or we already have a match, + // but this one is with higher offset and it's free + || (MipsRelocs[I].MatchedLoIndex > J + && !MipsRelocs[J].IsPrevMatchingHi))) + MipsRelocs[I].MatchedLoIndex = J; + } + + if(MipsRelocs[I].MatchedLoIndex != -1) + // We have a match. + setMatch(MipsRelocs[I], MipsRelocs[MipsRelocs[I].MatchedLoIndex]); + } + + // 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].Reloc; +} + bool MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbolData &SD, unsigned Type) const { Index: test/MC/Mips/sort-relocation-table.s =================================================================== --- /dev/null +++ test/MC/Mips/sort-relocation-table.s @@ -0,0 +1,118 @@ +# RUN: llvm-mc -filetype=obj -arch mipsel %s | llvm-readobj -r | FileCheck %s + +# Test the order of records in the relocation table. +# *HI16 and local *GOT16 relocations should be immediately followed by the +# corresponding *LO16 relocation against the same symbol. + +# TODO: Add mips16 and micromips tests. +# Note: offsets are part of expected output, so it's simpler to add new test +# cases at the bottom of the file. + +# CHECK: Relocations [ +# CHECK-NEXT: { + +# Put HI before LO. +addiu $2,$2,%lo(sym1) +lui $2,%hi(sym1) + +# CHECK-NEXT: 0x4 R_MIPS_HI16 sym1 +# CHECK-NEXT: 0x0 R_MIPS_LO16 sym1 + +# When searching for a matching LO, ignore LOs against a different symbol. +addiu $2,$2,%lo(sym2) +lui $2,%hi(sym2) +addiu $2,$2,%lo(sym2_d) + +# CHECK-NEXT: 0xC R_MIPS_HI16 sym2 +# CHECK-NEXT: 0x8 R_MIPS_LO16 sym2 +# CHECK-NEXT: 0x10 R_MIPS_LO16 sym2_d + +# Match HI with 2nd LO because it has higher offset (than the 1st LO). +addiu $2,$2,%lo(sym3) +addiu $2,$2,%lo(sym3) +lui $2,%hi(sym3) + +# CHECK-NEXT: 0x14 R_MIPS_LO16 sym3 +# CHECK-NEXT: 0x1C R_MIPS_HI16 sym3 +# CHECK-NEXT: 0x18 R_MIPS_LO16 sym3 + +# HI is already followed by a matching LO, so don't look further, ie. ignore the +# "free" LO with higher offset. +lui $2,%hi(sym4) +addiu $2,$2,%lo(sym4) +addiu $2,$2,%lo(sym4) + +# CHECK-NEXT: 0x20 R_MIPS_HI16 sym4 +# CHECK-NEXT: 0x24 R_MIPS_LO16 sym4 +# CHECK-NEXT: 0x28 R_MIPS_LO16 sym4 + +# Match 2nd HI with 2nd LO, since it's the one with highest offset among the +# "free" ones. +addiu $2,$2,%lo(sym5) +addiu $2,$2,%lo(sym5) +lui $2,%hi(sym5) +addiu $2,$2,%lo(sym5) +lui $2,%hi(sym5) + +# CHECK-NEXT: 0x2C R_MIPS_LO16 sym5 +# CHECK-NEXT: 0x3C R_MIPS_HI16 sym5 +# CHECK-NEXT: 0x30 R_MIPS_LO16 sym5 +# CHECK-NEXT: 0x34 R_MIPS_HI16 sym5 +# CHECK-NEXT: 0x38 R_MIPS_LO16 sym5 + +# When more HIs are matched with one LO, sort them in descending order of +# offset. +addiu $2,$2,%lo(sym6) +lui $2,%hi(sym6) +lui $2,%hi(sym6) + +# CHECK-NEXT: 0x48 R_MIPS_HI16 sym6 +# CHECK-NEXT: 0x44 R_MIPS_HI16 sym6 +# CHECK-NEXT: 0x40 R_MIPS_LO16 sym6 + +# sym7 is a local symbol, so GOT relocation against it needs a matching LO. +sym7: +addiu $2,$2,%lo(sym7) +lui $2,%got(sym7) + +# CHECK-NEXT: 0x50 R_MIPS_GOT16 sym7 +# CHECK-NEXT: 0x4C R_MIPS_LO16 sym7 + +# sym8 is not a local symbol, don't look for a matching LO for GOT. +addiu $2,$2,%lo(sym8) +lui $2,%got(sym8) + +# CHECK-NEXT: 0x54 R_MIPS_LO16 sym8 +# CHECK-NEXT: 0x58 R_MIPS_GOT16 sym8 + +# A small combination of previous checks. +symc1: +addiu $2,$2,%lo(symc1) +addiu $2,$2,%lo(symc1) +addiu $2,$2,%lo(symc1) +lui $2,%hi(symc1) +lui $2,%got(symc1) +addiu $2,$2,%lo(symc2) +lui $2,%hi(symc1) +lui $2,%hi(symc1) +lui $2,%got(symc2) +lui $2,%hi(symc1) +addiu $2,$2,%lo(symc1) +addiu $2,$2,%lo(symc2) +lui $2,%hi(symc1) +lui $2,%hi(symc1) + +# CHECK-NEXT: 0x78 R_MIPS_HI16 symc1 +# CHECK-NEXT: 0x74 R_MIPS_HI16 symc1 +# CHECK-NEXT: 0x6C R_MIPS_GOT16 symc1 +# CHECK-NEXT: 0x68 R_MIPS_HI16 symc1 +# CHECK-NEXT: 0x5C R_MIPS_LO16 symc1 +# CHECK-NEXT: 0x8C R_MIPS_HI16 symc1 +# CHECK-NEXT: 0x60 R_MIPS_LO16 symc1 +# CHECK-NEXT: 0x90 R_MIPS_HI16 symc1 +# CHECK-NEXT: 0x64 R_MIPS_LO16 symc1 +# CHECK-NEXT: 0x70 R_MIPS_LO16 symc2 +# CHECK-NEXT: 0x7C R_MIPS_GOT16 symc2 +# CHECK-NEXT: 0x80 R_MIPS_HI16 symc1 +# CHECK-NEXT: 0x84 R_MIPS_LO16 symc1 +# CHECK-NEXT: 0x88 R_MIPS_LO16 symc2 Index: test/MC/Mips/xgot.s =================================================================== --- test/MC/Mips/xgot.s +++ test/MC/Mips/xgot.s @@ -9,8 +9,8 @@ // CHECK: 0x14 R_MIPS_GOT_HI16 ext_1 // CHECK: 0x1C R_MIPS_GOT_LO16 ext_1 // CHECK: 0x24 R_MIPS_CALL_HI16 printf -// CHECK: 0x2C R_MIPS_GOT16 $.str // CHECK: 0x30 R_MIPS_CALL_LO16 printf +// CHECK: 0x2C R_MIPS_GOT16 $.str // CHECK: 0x38 R_MIPS_LO16 $.str // CHECK: ]