[BOLT][RFC] Implement composed relocations

[jobnoorman]

Summary

Note: I marked this patch as RFC since it implements a rather obscure
ELF feature at a relatively high cost in terms of code complexity.
Therefore, I would like some feedback on whether this approach is
desirable.

Second note: the implemented feature isn't used (afaict) by X86 or
AArch64 so this should in principle be NFC. It is used by RISC-V so this
patch is part of my efforts to bring BOLT support to that platform. The
patch itself doesn't contain any RISC-V-specific code though.

BOLT currently assumes (and asserts) that no two relocations can share
the same offset. Although this is true in most cases, ELF has a feature
called (not sure if this is an official term) composed relocations [1]
where multiple relocations at the same offset are combined to produce a
single value.

For example, to support label subtraction (a - b) on RISC-V, two
relocations are emitted at the same offset:

• R_RISCV_ADD32 a + 0
• R_RISCV_SUB32 b + 0

which, when combined, will produce the value of (a - b).

To support this in BOLT, first, RelocationSetType in BinarySection is
changed to be a multiset in order to allow it to store multiple
relocations at the same offset.

Next, Relocation::emit() is changed to receive an iterator pair of
relocations. In most cases, these will point to a single relocation in
which case its behavior is unaltered by this patch. For composed
relocations, they should point to all relocations at the same offset and
the following happens:

• A new method Relocation::createExpr() is called for every relocation. This method is essentially the same as the original emit() except that it returns the MCExpr without emitting it.
• The MCExprs of relocations i and i+1 are combined using the opcode returned by the new method Relocation::getComposeOpcodeFor().
• After combining all MCExprs, the last one is emitted.

Note that in the current patch, getComposeOpcodeFor() simply calls
llvm_unreachable() since none of the current targets use composed
relocations. This will change once the RISC-V target lands.

Finally, BinarySection::emitAsData() is updated to group relocations by
offset and emit them all at once.

Note that this means composed relocations are only supported in data
sections. Since this is the only place they seem to be used in RISC-V, I
believe it's reasonable to only support them there for now to avoid
further code complexity.

[1]: https://www.sco.com/developers/gabi/latest/ch4.reloc.html

[yota9]

Nice! I didn't know about this feature. May I ask you to create dependent review with getComposeOpcodeFor ? Thank you!

[jobnoorman]

In D146546#4210355, @yota9 wrote:

Nice! I didn't know about this feature. May I ask you to create dependent review with getComposeOpcodeFor ? Thank you!

Sure! D146554

Note that I still have to write tests for that patch; I will add them later.

[treapster]

The implemented feature isn't used (afaict) by X86 or AArch64 so this should in principle be NFC

In fact we need to have it for other targets because for example some golang structures contain offsets into .text which is ok if we know output .text address, but if we land https://reviews.llvm.org/D144560 it would be cumbersume to reserve .text address ahead of time, and i think other cases of symbol diffs or other expressions may emerge outside of golang. Last week i tried to merge golang with -rewrite and ended up creating bogus relocation type which can contain arbitrary symbol expression and has advantages of not using multiset and extra indirection at the cost of Relocation's PODness and privatizing Relocation::Symbol. However, in case of RISCV we'll need to collect composed relocations in a single expression while reading them and only then add them to BinarySection. Here's the patch, should i open a competing RFC with it?:)

0001-BOLT-Use-raw-MCExpr-to-express-symbol-differences.patch16 KBDownload

[jobnoorman]

In D146546#4212407, @treapster wrote:

The implemented feature isn't used (afaict) by X86 or AArch64 so this should in principle be NFC

In fact we need to have it for other targets because for example some golang structures contain offsets into .text which is ok if we know output .text address, but if we land https://reviews.llvm.org/D144560 it would be cumbersume to reserve .text address ahead of time, and i think other cases of symbol diffs or other expressions may emerge outside of golang. Last week i tried to merge golang with -rewrite and ended up creating bogus relocation type which can contain arbitrary symbol expression and has advantages of not using multiset and extra indirection at the cost of Relocation's PODness and privatizing Relocation::Symbol. However, in case of RISCV we'll need to collect composed relocations in a single expression while reading them and only then add them to BinarySection. Here's the patch, should i open a competing RFC with it?:)

0001-BOLT-Use-raw-MCExpr-to-express-symbol-differences.patch16 KBDownload

Thanks, this is an interesting alternative approach! I believe it could indeed be used to implement composed relocations on RISC-V, at least for the ones I currently care about.

I do think there is some information loss, though: since the relocation type is replaced by a "bogus" one, we won't know what the original type was. For composed relocations, the type of the last one determines how the value is written. Since we lost that type, this could be an issue. Now, for the relocations on RISC-V that are used in a composed way (ADD32/SUB32), this doesn't matter since their size corresponds to the "bogus" ones so this might just be a mere theoretical issue.

In any case, since this heavily changes one of the core data structures in BOLT, I'll leave it for others to decide which approach is preferable :)

[treapster]

In D146546#4212632, @jobnoorman wrote:

I do think there is some information loss, though: since the relocation type is replaced by a "bogus" one, we won't know what the original type was. For composed relocations, the type of the last one determines how the value is written. Since we lost that type, this could be an issue. Now, for the relocations on RISC-V that are used in a composed way (ADD32/SUB32), this doesn't matter since their size corresponds to the "bogus" ones so this might just be a mere theoretical issue.

In any case, since this heavily changes one of the core data structures in BOLT, I'll leave it for others to decide which approach is preferable :)

We do lose the original type, but on the other hand MCStreamer doesn't get original type anyway since it only knows about expressions and size(which we save in type), and it's just a matter of whether we convert to MCExpr in Relocation::emit or earlier when creating the relocation instance. But since i mix Relocation with MCExpr and explicitly delegate handling of composed relocations to external code, i'd also wait for others to decide whether they like it.

[yota9]

From my standpoint this patch seems to be more solid and universal. We don't have to change structure, don't have to create pseudo relocation types on BOLT level and can compose relocations with more then 2 symbols easily if needed (although I'm, not sure if there are such cases). Indeed I was interested in this patch since the first thought was that might be re-used in golang support in couple of places and it seems to be a solution that might help with it. But the only major downside of this solution - we don't have special label relocations for aarch64/x86. But it seems to be reasonable addon and probably worth to speak with community about adding such types to other platforms too.

[treapster]

In D146546#4212848, @yota9 wrote:

From my standpoint this patch seems to be more solid and universal. We don't have to change structure, don't have to create pseudo relocation types on BOLT level and can compose relocations with more then 2 symbols easily if needed (although I'm, not sure if there are such cases). Indeed I was interested in this patch since the first thought was that might be re-used in golang support in couple of places and it seems to be a solution that might help with it. But the only major downside of this solution - we don't have special label relocations for aarch64/x86. But it seems to be reasonable addon and probably worth to speak with community about adding such types to other platforms too.

IMO if we can create some expressions in opaque way regardless of architecture, it's simpler than stacking up proper arch-specific relocations only to convert them to the same expression later. While this patch is more solid for incoming RISC-V relocs, having an internal opaque type is also useful, not necessarily implemented in the way it's done in my patch. It's definitely easier to implement internal hack than to force other platforms to introduce new relocation types. And since now we don't have the needed types for AArch64/X86, i guess we have to invent our own anyway.

[jobnoorman]

So it feels to me (please correct me if I'm wrong) that there is some agreement that the current patch is the preferred approach for dealing with the composed relocations in RISC-V. There might be a need though for supporting custom MCExprs in relocations for features found in golang. I think it should be possible to implement that *in addition to* the current patch so maybe it would make sense to move that discussion to another RFC?

[jobnoorman]

Friendly ping.

[rafauler]

LGTM

[jobnoorman]

@yota9 Are you ok with landing this?

bolt/include/bolt/Core/BinarySection.h

class BinarySection {
   const uint64_t Size;         // Input section size
   uint64_t InputFileOffset{0}; // Offset in the input binary
   unsigned Alignment;          // alignment in bytes (must be > 0)
   unsigned ELFType;            // ELF section type
   unsigned ELFFlags;           // ELF section flags
 
   // Relocations associated with this section. Relocation offsets are
   // wrt. to the original section address and size.
-  using RelocationSetType = std::set<Relocation, std::less<>>;
+  using RelocationSetType = std::multiset<Relocation, std::less<>>;
   RelocationSetType Relocations;
 
   // Dynamic relocations associated with this section. Relocation offsets are
   // from the original section address.
   RelocationSetType DynamicRelocations;
 
   // Pending relocations for this section.
   std::vector<Relocation> PendingRelocations;
public:
 
   /// Does this section have any pending relocations?
   bool hasPendingRelocations() const { return !PendingRelocations.empty(); }
 
   /// Remove non-pending relocation with the given /p Offset.
   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;
   }
 
   void clearRelocations();
 
   /// Add a new relocation at the given /p Offset.

bolt/include/bolt/Core/Relocation.h

 //===- bolt/Core/Relocation.h - Object file relocations ---------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains the declaration of Relocation class, which represents a
 // relocation in an object or a binary file.
 //
 //===----------------------------------------------------------------------===//
 
 #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;
 
 namespace ELF {
 /// Relocation type mask that was accidentally output by bfd 2.30 linker.
 enum { R_X86_64_converted_reloc_bit = 0x80 };
 } // namespace ELF
 
struct Relocation {
   /// Return true if this relocation is R_*_RELATIVE type. Return false
   /// otherwise.
   bool isRelative() const { return isRelative(Type); }
 
   /// Emit relocation at a current \p Streamer' position. The caller is
   /// 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 <typename RelocIt>
+  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.
 inline bool operator<(const Relocation &A, const Relocation &B) {
   return A.Offset < B.Offset;
 }
 
 inline bool operator<(const Relocation &A, uint64_t B) { return A.Offset < B; }

bolt/lib/Core/BinarySection.cpp

void BinarySection::emitAsData(MCStreamer &Streamer,
   LLVM_DEBUG(dbgs() << "BOLT-DEBUG: emitting "
                     << (isAllocatable() ? "" : "non-")
                     << "allocatable data section " << SectionName << '\n');
 
   if (!hasRelocations()) {
     Streamer.emitBytes(SectionContents);
   } else {
     uint64_t SectionOffset = 0;
-    for (const Relocation &Relocation : relocations()) {
-      assert(Relocation.Offset < SectionContents.size() && "overflow detected");
-      // Skip undefined symbols.
-      if (BC.UndefinedSymbols.count(Relocation.Symbol))
-        continue;
-      if (SectionOffset < Relocation.Offset) {
+    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, Relocation.Offset - SectionOffset));
-        SectionOffset = Relocation.Offset;
+            SectionOffset, RelocationOffset - SectionOffset));
+        SectionOffset = RelocationOffset;
       }
-      LLVM_DEBUG(dbgs() << "BOLT-DEBUG: emitting relocation for symbol "
-                        << (Relocation.Symbol ? Relocation.Symbol->getName()
-                                              : StringRef("<none>"))
-                        << " at offset 0x"
-                        << Twine::utohexstr(Relocation.Offset) << " with size "
-                        << Relocation::getSizeForType(Relocation.Type) << '\n');
-      size_t RelocationSize = Relocation.emit(&Streamer);
+
+      // 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.
+      auto HasUndefSym = [this](const auto &Relocation) {
+        return BC.UndefinedSymbols.count(Relocation.Symbol);
+      };
+
+      if (std::any_of(ROI, ROE, HasUndefSym))
+        continue;
+
+      for (const auto &Relocation : make_range(ROI, ROE)) {
+        LLVM_DEBUG(
+            dbgs() << "BOLT-DEBUG: emitting relocation for symbol "
+                   << " at offset 0x" << Twine::utohexstr(Relocation.Offset)
+                   << " with size "
+      }
+
+      size_t RelocationSize = Relocation::emit(ROI, ROE, &Streamer);
       SectionOffset += RelocationSize;
     }
     assert(SectionOffset <= SectionContents.size() && "overflow error");
     if (SectionOffset < SectionContents.size())
       Streamer.emitBytes(SectionContents.substr(SectionOffset));
   }
 
   if (BC.HasRelocations && opts::HotData && isReordered())
if ((!BD->isMoved() && !Inplace) || BD->isJumpTable())
       continue;
 
     Relocation NewRel(Rel);
     uint64_t RelOffset = RelAddr - BD->getAddress();
     NewRel.Offset = BD->getOutputOffset() + RelOffset;
     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;
 }
 
 void BinarySection::reorderContents(const std::vector<BinaryData *> &Order,
                                     bool Inplace) {
   IsReordered = true;
 

bolt/lib/Core/Relocation.cpp

 uint64_t Relocation::getRelative() {
   if (Arch == Triple::aarch64)
     return ELF::R_AARCH64_RELATIVE;
   return ELF::R_X86_64_RELATIVE;
 }
 
 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();
-  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);
-    }
+
+  if (Symbol && Addend) {
+    Value = MCBinaryExpr::createAdd(MCSymbolRefExpr::create(Symbol, Ctx),
+                                    MCConstantExpr::create(Addend, Ctx), Ctx);
+  } else if (Symbol) {
+
+  if (isPCRelative(Type)) {
+    MCSymbol *TempLabel = Ctx.createNamedTempSymbol();
+    Streamer->emitLabel(TempLabel);
     Value = MCBinaryExpr::createSub(
         Value, MCSymbolRefExpr::create(TempLabel, Ctx), Ctx);
-    Streamer->emitValue(Value, Size);
+  }
 
-    return Size;
-  }
+  return Value;
 
-  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);
+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,
 
 void Relocation::print(raw_ostream &OS) const {
   static const char *X86RelocNames[] = {
 #include "llvm/BinaryFormat/ELFRelocs/x86_64.def"
   };