llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-mc Author: Alex Rønne Petersen (alexrp) <details> <summary>Changes</summary> Manual backport of #<!-- -->104723. --- Full diff: https://github.com/llvm/llvm-project/pull/106008.diff 4 Files Affected: - (modified) llvm/include/llvm/MC/MCELFObjectWriter.h (+3-8) - (modified) llvm/lib/MC/ELFObjectWriter.cpp (+6-11) - (modified) llvm/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp (+43-117) - (modified) llvm/test/MC/Mips/sort-relocation-table.s (+3-3) ``````````diff diff --git a/llvm/include/llvm/MC/MCELFObjectWriter.h b/llvm/include/llvm/MC/MCELFObjectWriter.h index 9b74cbc3d3a520..cbb010fa2fd802 100644 --- a/llvm/include/llvm/MC/MCELFObjectWriter.h +++ b/llvm/include/llvm/MC/MCELFObjectWriter.h @@ -37,19 +37,14 @@ struct ELFRelocationEntry { const MCSymbolELF *Symbol; // The symbol to relocate with. unsigned Type; // The type of the relocation. uint64_t Addend; // The addend to use. - const MCSymbolELF *OriginalSymbol; // The original value of Symbol if we changed it. - uint64_t OriginalAddend; // The original value of addend. ELFRelocationEntry(uint64_t Offset, const MCSymbolELF *Symbol, unsigned Type, - uint64_t Addend, const MCSymbolELF *OriginalSymbol, - uint64_t OriginalAddend) - : Offset(Offset), Symbol(Symbol), Type(Type), Addend(Addend), - OriginalSymbol(OriginalSymbol), OriginalAddend(OriginalAddend) {} + uint64_t Addend) + : Offset(Offset), Symbol(Symbol), Type(Type), Addend(Addend) {} void print(raw_ostream &Out) const { Out << "Off=" << Offset << ", Sym=" << Symbol << ", Type=" << Type - << ", Addend=" << Addend << ", OriginalSymbol=" << OriginalSymbol - << ", OriginalAddend=" << OriginalAddend; + << ", Addend=" << Addend; } LLVM_DUMP_METHOD void dump() const { print(errs()); } diff --git a/llvm/lib/MC/ELFObjectWriter.cpp b/llvm/lib/MC/ELFObjectWriter.cpp index f958905a26aa42..8e8705500126e7 100644 --- a/llvm/lib/MC/ELFObjectWriter.cpp +++ b/llvm/lib/MC/ELFObjectWriter.cpp @@ -1393,22 +1393,17 @@ void ELFObjectWriter::recordRelocation(MCAssembler &Asm, bool RelocateWithSymbol = shouldRelocateWithSymbol(Asm, Target, SymA, C, Type) || (Parent->getType() == ELF::SHT_LLVM_CALL_GRAPH_PROFILE); - uint64_t Addend = 0; - - FixedValue = !RelocateWithSymbol && SymA && !SymA->isUndefined() - ? C + Asm.getSymbolOffset(*SymA) - : C; - if (usesRela(TO, FixupSection)) { - Addend = FixedValue; - FixedValue = 0; - } + uint64_t Addend = !RelocateWithSymbol && SymA && !SymA->isUndefined() + ? C + Asm.getSymbolOffset(*SymA) + : C; + FixedValue = usesRela(TO, FixupSection) ? 0 : Addend; if (!RelocateWithSymbol) { const auto *SectionSymbol = SecA ? cast<MCSymbolELF>(SecA->getBeginSymbol()) : nullptr; if (SectionSymbol) SectionSymbol->setUsedInReloc(); - ELFRelocationEntry Rec(FixupOffset, SectionSymbol, Type, Addend, SymA, C); + ELFRelocationEntry Rec(FixupOffset, SectionSymbol, Type, Addend); Relocations[&FixupSection].push_back(Rec); return; } @@ -1423,7 +1418,7 @@ void ELFObjectWriter::recordRelocation(MCAssembler &Asm, else RenamedSymA->setUsedInReloc(); } - ELFRelocationEntry Rec(FixupOffset, RenamedSymA, Type, Addend, SymA, C); + ELFRelocationEntry Rec(FixupOffset, RenamedSymA, Type, Addend); Relocations[&FixupSection].push_back(Rec); } diff --git a/llvm/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp b/llvm/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp index 4d6a00c14a3575..faf9772ab75756 100644 --- a/llvm/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp +++ b/llvm/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp @@ -40,20 +40,8 @@ struct MipsRelocationEntry { bool Matched = false; ///< Is this relocation part of a match. MipsRelocationEntry(const ELFRelocationEntry &R) : R(R) {} - - void print(raw_ostream &Out) const { - R.print(Out); - Out << ", Matched=" << Matched; - } }; -#ifndef NDEBUG -raw_ostream &operator<<(raw_ostream &OS, const MipsRelocationEntry &RHS) { - RHS.print(OS); - return OS; -} -#endif - class MipsELFObjectWriter : public MCELFObjectTargetWriter { public: MipsELFObjectWriter(uint8_t OSABI, bool HasRelocationAddend, bool Is64); @@ -115,17 +103,11 @@ static InputIt find_best(InputIt First, InputIt Last, UnaryPredicate Predicate, for (InputIt I = First; I != Last; ++I) { unsigned Matched = Predicate(*I); if (Matched != FindBest_NoMatch) { - LLVM_DEBUG(dbgs() << std::distance(First, I) << " is a match ("; - I->print(dbgs()); dbgs() << ")\n"); - if (Best == Last || BetterThan(*I, *Best)) { - LLVM_DEBUG(dbgs() << ".. and it beats the last one\n"); + if (Best == Last || BetterThan(*I, *Best)) Best = I; - } } - if (Matched == FindBest_PerfectMatch) { - LLVM_DEBUG(dbgs() << ".. and it is unbeatable\n"); + if (Matched == FindBest_PerfectMatch) break; - } } return Best; @@ -147,8 +129,7 @@ static unsigned getMatchingLoType(const ELFRelocationEntry &Reloc) { if (Type == ELF::R_MIPS16_HI16) return ELF::R_MIPS16_LO16; - if (Reloc.OriginalSymbol && - Reloc.OriginalSymbol->getBinding() != ELF::STB_LOCAL) + if (Reloc.Symbol && Reloc.Symbol->getBinding() != ELF::STB_LOCAL) return ELF::R_MIPS_NONE; if (Type == ELF::R_MIPS_GOT16) @@ -161,54 +142,12 @@ static unsigned getMatchingLoType(const ELFRelocationEntry &Reloc) { return ELF::R_MIPS_NONE; } -/// Determine whether a relocation (X) matches the one given in R. -/// -/// A relocation matches if: -/// - It's type matches that of a corresponding low part. This is provided in -/// MatchingType for efficiency. -/// - It's based on the same symbol. -/// - It's offset of greater or equal to that of the one given in R. -/// It should be noted that this rule assumes the programmer does not use -/// offsets that exceed the alignment of the symbol. The carry-bit will be -/// incorrect if this is not true. -/// -/// A matching relocation is unbeatable if: -/// - It is not already involved in a match. -/// - It's offset is exactly that of the one given in R. -static FindBestPredicateResult isMatchingReloc(const MipsRelocationEntry &X, - const ELFRelocationEntry &R, - unsigned MatchingType) { - if (X.R.Type == MatchingType && X.R.OriginalSymbol == R.OriginalSymbol) { - if (!X.Matched && - X.R.OriginalAddend == R.OriginalAddend) - return FindBest_PerfectMatch; - else if (X.R.OriginalAddend >= R.OriginalAddend) - return FindBest_Match; - } - return FindBest_NoMatch; -} - -/// Determine whether Candidate or PreviousBest is the better match. -/// The return value is true if Candidate is the better match. -/// -/// A matching relocation is a better match if: -/// - It has a smaller addend. -/// - It is not already involved in a match. -static bool compareMatchingRelocs(const MipsRelocationEntry &Candidate, - const MipsRelocationEntry &PreviousBest) { - if (Candidate.R.OriginalAddend != PreviousBest.R.OriginalAddend) - return Candidate.R.OriginalAddend < PreviousBest.R.OriginalAddend; - return PreviousBest.Matched && !Candidate.Matched; -} - -#ifndef NDEBUG -/// Print all the relocations. -template <class Container> -static void dumpRelocs(const char *Prefix, const Container &Relocs) { - for (const auto &R : Relocs) - dbgs() << Prefix << R << "\n"; +// Determine whether a relocation X is a low-part and matches the high-part R +// perfectly by symbol and addend. +static bool isMatchingReloc(unsigned MatchingType, const ELFRelocationEntry &R, + const ELFRelocationEntry &X) { + return X.Type == MatchingType && X.Symbol == R.Symbol && X.Addend == R.Addend; } -#endif MipsELFObjectWriter::MipsELFObjectWriter(uint8_t OSABI, bool HasRelocationAddend, bool Is64) @@ -436,65 +375,52 @@ void MipsELFObjectWriter::sortRelocs(const MCAssembler &Asm, if (hasRelocationAddend()) return; - if (Relocs.size() < 2) - return; - // Sort relocations by the address they are applied to. llvm::sort(Relocs, [](const ELFRelocationEntry &A, const ELFRelocationEntry &B) { return A.Offset < B.Offset; }); + // Place relocations in a list for reorder convenience. Hi16 contains the + // iterators of high-part relocations. std::list<MipsRelocationEntry> Sorted; - std::list<ELFRelocationEntry> Remainder; - - LLVM_DEBUG(dumpRelocs("R: ", Relocs)); - - // Separate the movable relocations (AHL relocations using the high bits) from - // the immobile relocations (everything else). This does not preserve high/low - // matches that already existed in the input. - copy_if_else(Relocs.begin(), Relocs.end(), std::back_inserter(Remainder), - std::back_inserter(Sorted), [](const ELFRelocationEntry &Reloc) { - return getMatchingLoType(Reloc) != ELF::R_MIPS_NONE; - }); - - for (auto &R : Remainder) { - LLVM_DEBUG(dbgs() << "Matching: " << R << "\n"); + SmallVector<std::list<MipsRelocationEntry>::iterator, 0> Hi16; + for (auto &R : Relocs) { + Sorted.push_back(R); + if (getMatchingLoType(R) != ELF::R_MIPS_NONE) + Hi16.push_back(std::prev(Sorted.end())); + } + for (auto I : Hi16) { + auto &R = I->R; unsigned MatchingType = getMatchingLoType(R); - assert(MatchingType != ELF::R_MIPS_NONE && - "Wrong list for reloc that doesn't need a match"); - - // Find the best matching relocation for the current high part. - // See isMatchingReloc for a description of a matching relocation and - // compareMatchingRelocs for a description of what 'best' means. - auto InsertionPoint = - find_best(Sorted.begin(), Sorted.end(), - [&R, &MatchingType](const MipsRelocationEntry &X) { - return isMatchingReloc(X, R, MatchingType); - }, - compareMatchingRelocs); - - // If we matched then insert the high part in front of the match and mark - // both relocations as being involved in a match. We only mark the high - // part for cosmetic reasons in the debug output. + // If the next relocation is a perfect match, continue; + if (std::next(I) != Sorted.end() && + isMatchingReloc(MatchingType, R, std::next(I)->R)) + continue; + // Otherwise, find the best matching low-part relocation with the following + // criteria. It must have the same symbol and its addend is no lower than + // that of the current high-part. // - // If we failed to find a match then the high part is orphaned. This is not - // permitted since the relocation cannot be evaluated without knowing the - // carry-in. We can sometimes handle this using a matching low part that is - // already used in a match but we already cover that case in - // isMatchingReloc and compareMatchingRelocs. For the remaining cases we - // should insert the high part at the end of the list. This will cause the - // linker to fail but the alternative is to cause the linker to bind the - // high part to a semi-matching low part and silently calculate the wrong - // value. Unfortunately we have no means to warn the user that we did this - // so leave it up to the linker to complain about it. - if (InsertionPoint != Sorted.end()) - InsertionPoint->Matched = true; - Sorted.insert(InsertionPoint, R)->Matched = true; - } + // (1) %lo with a smaller offset is preferred. + // (2) %lo with the same offset that is unmatched is preferred. + // (3) later %lo is preferred. + auto Best = Sorted.end(); + for (auto J = Sorted.begin(); J != Sorted.end(); ++J) { + auto &R1 = J->R; + if (R1.Type == MatchingType && R.Symbol == R1.Symbol && + R.Addend <= R1.Addend && + (Best == Sorted.end() || R1.Addend < Best->R.Addend || + (!Best->Matched && R1.Addend == Best->R.Addend))) + Best = J; + } + if (Best != Sorted.end() && R.Addend == Best->R.Addend) + Best->Matched = true; - LLVM_DEBUG(dumpRelocs("S: ", Sorted)); + // Move the high-part before the low-part, or if not found, the end of the + // list. The unmatched high-part will lead to a linker warning/error. + Sorted.splice(Best, Sorted, I); + } assert(Relocs.size() == Sorted.size() && "Some relocs were not consumed"); diff --git a/llvm/test/MC/Mips/sort-relocation-table.s b/llvm/test/MC/Mips/sort-relocation-table.s index cc951956fd24a0..7d126ba9f049d8 100644 --- a/llvm/test/MC/Mips/sort-relocation-table.s +++ b/llvm/test/MC/Mips/sort-relocation-table.s @@ -150,8 +150,8 @@ lui $2, %hi(sym1) # CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_hilo_8b { -# CHECK-NEXT: 0x8 R_MIPS_HI16 sym1 # CHECK-NEXT: 0x0 R_MIPS_LO16 sym1 +# CHECK-NEXT: 0x8 R_MIPS_HI16 sym1 # CHECK-NEXT: 0x4 R_MIPS_LO16 sym1 # CHECK-NEXT: } @@ -331,8 +331,8 @@ lui $2, %got(local1) # CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_8b { -# CHECK-NEXT: 0x8 R_MIPS_GOT16 .text # CHECK-NEXT: 0x0 R_MIPS_LO16 .text +# CHECK-NEXT: 0x8 R_MIPS_GOT16 .text # CHECK-NEXT: 0x4 R_MIPS_LO16 .text # CHECK-NEXT: } @@ -372,9 +372,9 @@ # CHECK-LABEL: Section ({{[0-9]+}}) .rel.mips_gotlo_10 { # CHECK-NEXT: 0x0 R_MIPS_GOT16 .text # CHECK-NEXT: 0x4 R_MIPS_LO16 .text +# CHECK-NEXT: 0x8 R_MIPS_GOT16 .text # CHECK-NEXT: 0xC R_MIPS_GOT16 .text # CHECK-NEXT: 0x10 R_MIPS_LO16 .text -# CHECK-NEXT: 0x8 R_MIPS_GOT16 .text # CHECK-NEXT: } # Finally, do test 2 for R_MIPS_GOT16 on external symbols to prove they are `````````` </details> https://github.com/llvm/llvm-project/pull/106008 _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits