diff --git a/bolt/include/bolt/Core/BinarySection.h b/bolt/include/bolt/Core/BinarySection.h --- a/bolt/include/bolt/Core/BinarySection.h +++ b/bolt/include/bolt/Core/BinarySection.h @@ -59,7 +59,7 @@ // Relocations associated with this section. Relocation offsets are // wrt. to the original section address and size. - using RelocationSetType = std::set>; + using RelocationSetType = std::multiset>; RelocationSetType Relocations; // Dynamic relocations associated with this section. Relocation offsets are @@ -345,7 +345,8 @@ bool removeRelocationAt(uint64_t Offset) { auto Itr = Relocations.find(Offset); if (Itr != Relocations.end()) { - Relocations.erase(Itr); + auto End = Relocations.upper_bound(Offset); + Relocations.erase(Itr, End); return true; } return false; diff --git a/bolt/include/bolt/Core/Relocation.h b/bolt/include/bolt/Core/Relocation.h --- a/bolt/include/bolt/Core/Relocation.h +++ b/bolt/include/bolt/Core/Relocation.h @@ -14,10 +14,11 @@ #ifndef BOLT_CORE_RELOCATION_H #define BOLT_CORE_RELOCATION_H +#include "llvm/MC/MCExpr.h" +#include "llvm/MC/MCStreamer.h" #include "llvm/TargetParser/Triple.h" namespace llvm { -class MCStreamer; class MCSymbol; class raw_ostream; @@ -122,8 +123,36 @@ /// responsible for setting the position correctly. size_t emit(MCStreamer *Streamer) const; + /// Emit a group of composed relocations. All relocations must have the same + /// offset. If std::distance(Begin, End) == 1, this is equivalent to + /// Begin->emit(Streamer). + template + static size_t emit(RelocIt Begin, RelocIt End, MCStreamer *Streamer) { + if (Begin == End) + return 0; + + const MCExpr *Value = nullptr; + + for (auto RI = Begin; RI != End; ++RI) { + assert(RI->Offset == Begin->Offset && + "emitting composed relocations with different offsets"); + Value = RI->createExpr(Streamer, Value); + } + + assert(Value && "failed to create relocation value"); + auto Size = std::prev(End)->getSize(); + Streamer->emitValue(Value, Size); + return Size; + } + /// Print a relocation to \p OS. void print(raw_ostream &OS) const; + +private: + const MCExpr *createExpr(MCStreamer *Streamer) const; + const MCExpr *createExpr(MCStreamer *Streamer, + const MCExpr *RetainedValue) const; + static MCBinaryExpr::Opcode getComposeOpcodeFor(uint64_t Type); }; /// Relocation ordering by offset. diff --git a/bolt/lib/Core/BinarySection.cpp b/bolt/lib/Core/BinarySection.cpp --- a/bolt/lib/Core/BinarySection.cpp +++ b/bolt/lib/Core/BinarySection.cpp @@ -90,23 +90,44 @@ Streamer.emitBytes(SectionContents); } else { uint64_t SectionOffset = 0; - for (const Relocation &Relocation : relocations()) { - assert(Relocation.Offset < SectionContents.size() && "overflow detected"); + for (auto RI = Relocations.begin(), RE = Relocations.end(); RI != RE;) { + auto RelocationOffset = RI->Offset; + assert(RelocationOffset < SectionContents.size() && "overflow detected"); + + if (SectionOffset < RelocationOffset) { + Streamer.emitBytes(SectionContents.substr( + SectionOffset, RelocationOffset - SectionOffset)); + SectionOffset = RelocationOffset; + } + + // Get iterators to all relocations with the same offset. Usually, there + // is only one such relocation but there can be more for composed + // relocations. + auto ROI = RI; + auto ROE = Relocations.upper_bound(RelocationOffset); + + // Start from the next offset on the next iteration. + RI = ROE; + // Skip undefined symbols. - if (BC.UndefinedSymbols.count(Relocation.Symbol)) + auto HasUndefSym = [this](const auto &Relocation) { + return BC.UndefinedSymbols.count(Relocation.Symbol); + }; + + if (std::any_of(ROI, ROE, HasUndefSym)) continue; - if (SectionOffset < Relocation.Offset) { - Streamer.emitBytes(SectionContents.substr( - SectionOffset, Relocation.Offset - SectionOffset)); - SectionOffset = Relocation.Offset; + + for (const auto &Relocation : make_range(ROI, ROE)) { + LLVM_DEBUG( + dbgs() << "BOLT-DEBUG: emitting relocation for symbol " + << (Relocation.Symbol ? Relocation.Symbol->getName() + : StringRef("")) + << " at offset 0x" << Twine::utohexstr(Relocation.Offset) + << " with size " + << Relocation::getSizeForType(Relocation.Type) << '\n'); } - LLVM_DEBUG(dbgs() << "BOLT-DEBUG: emitting relocation for symbol " - << (Relocation.Symbol ? Relocation.Symbol->getName() - : StringRef("")) - << " at offset 0x" - << Twine::utohexstr(Relocation.Offset) << " with size " - << Relocation::getSizeForType(Relocation.Type) << '\n'); - size_t RelocationSize = Relocation.emit(&Streamer); + + size_t RelocationSize = Relocation::emit(ROI, ROE, &Streamer); SectionOffset += RelocationSize; } assert(SectionOffset <= SectionContents.size() && "overflow error"); @@ -221,9 +242,7 @@ assert(NewRel.Offset < getSize()); LLVM_DEBUG(dbgs() << "BOLT-DEBUG: moving " << Rel << " -> " << NewRel << "\n"); - auto Res = NewRelocations.emplace(std::move(NewRel)); - (void)Res; - assert(Res.second && "Can't overwrite existing relocation"); + NewRelocations.emplace(std::move(NewRel)); } return NewRelocations; } diff --git a/bolt/lib/Core/Relocation.cpp b/bolt/lib/Core/Relocation.cpp --- a/bolt/lib/Core/Relocation.cpp +++ b/bolt/lib/Core/Relocation.cpp @@ -817,39 +817,48 @@ size_t Relocation::emit(MCStreamer *Streamer) const { const size_t Size = getSizeForType(Type); + const auto *Value = createExpr(Streamer); + Streamer->emitValue(Value, Size); + return Size; +} + +const MCExpr *Relocation::createExpr(MCStreamer *Streamer) const { MCContext &Ctx = Streamer->getContext(); + const MCExpr *Value = nullptr; + + if (Symbol && Addend) { + Value = MCBinaryExpr::createAdd(MCSymbolRefExpr::create(Symbol, Ctx), + MCConstantExpr::create(Addend, Ctx), Ctx); + } else if (Symbol) { + Value = MCSymbolRefExpr::create(Symbol, Ctx); + } else { + Value = MCConstantExpr::create(Addend, Ctx); + } + if (isPCRelative(Type)) { MCSymbol *TempLabel = Ctx.createNamedTempSymbol(); Streamer->emitLabel(TempLabel); - const MCExpr *Value = nullptr; - if (Symbol) { - Value = MCSymbolRefExpr::create(Symbol, Ctx); - if (Addend) { - Value = MCBinaryExpr::createAdd( - Value, MCConstantExpr::create(Addend, Ctx), Ctx); - } - } else { - Value = MCConstantExpr::create(Addend, Ctx); - } Value = MCBinaryExpr::createSub( Value, MCSymbolRefExpr::create(TempLabel, Ctx), Ctx); - Streamer->emitValue(Value, Size); - - return Size; } - if (Symbol && Addend) { - auto Value = - MCBinaryExpr::createAdd(MCSymbolRefExpr::create(Symbol, Ctx), - MCConstantExpr::create(Addend, Ctx), Ctx); - Streamer->emitValue(Value, Size); - } else if (Symbol) { - Streamer->emitSymbolValue(Symbol, Size); - } else { - Streamer->emitIntValue(Addend, Size); + return Value; +} + +const MCExpr *Relocation::createExpr(MCStreamer *Streamer, + const MCExpr *RetainedValue) const { + const auto *Value = createExpr(Streamer); + + if (RetainedValue) { + Value = MCBinaryExpr::create(getComposeOpcodeFor(Type), RetainedValue, + Value, Streamer->getContext()); } - return Size; + return Value; +} + +MCBinaryExpr::Opcode Relocation::getComposeOpcodeFor(uint64_t Type) { + llvm_unreachable("not implemented"); } #define ELF_RELOC(name, value) #name,