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; @@ -1362,31 +1351,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!"); - return 0; -} - -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,22 @@ 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,20 @@ 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, @@ -33,6 +48,8 @@ bool IsPCRel) const override; bool needsRelocateWithSymbol(const MCSymbolData &SD, unsigned Type) const override; + virtual void sortRelocs(const MCAssembler &Asm, + std::vector &Relocs) override; }; } @@ -225,6 +242,167 @@ 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 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!"); +} + +// 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; + + const MCSymbolData &SD = Asm.getSymbolData(*Reloc.Symbol); + + if (MCELF::GetBinding(SD) != 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; +// +// There may be more ways to sort the table while respecting the ABI rule, and +// we match gnu as for easier comparison. +// +// 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]); + } + + // 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 { Index: test/MC/Mips/sort-relocation-table.s =================================================================== --- /dev/null +++ test/MC/Mips/sort-relocation-table.s @@ -0,0 +1,125 @@ +# 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. +# +# We try to implement the same semantics as gas, ie. to order the relocation +# table the same way as gas. +# +# gnu as command line: +# mips-linux-gnu-as -EL sort-relocation-table.s -o sort-relocation-table.o +# +# 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. +.global sym8 +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: ]