[JITLink] Introduce virtual offsets for Symbol definitions in LinkGraph

[sgraenitz]

Summary

On AArch32 branch offsets explicitly encode the target instruction subset (Arm/Thumb) in their least significant bit. We want to store Thumb symbol definitions with the extra bit set, so that branch offset calculations account for instruction subset changes automatically.

However, we don't want to adjust the physical size of the symbol or the containing block, since this bit is not part of the symbol's physical location. Instead, we could consider it a virtual offset: Virtual offsets do affect branch offsets, but not physical memory size.

[sgraenitz]

This implementation is one option. Symbols don't know their target triple, but the link-graph does. My main concern is that splitArchVirtualOffset() would introduce target-specific behavior to LinkGraph. Not sure how we could avoid it without changing the interface.

The alternative I see would be to extend the LinkGraph::add<...>Symbol() interface and:
(1) either add VirtualOffset as another parameter -- currently affects around 80 individual calls
(2) or add respective overloads where necessary -- affects no-one but adds extra overall complexity to the interface

What do you think?

[lhames]

My gut reaction is to want to introduce a new "target flags" concept into Symbol, rather than using/abusing the address. On the other hand I think that using/abusing the address is the standard for thumb, and people might get thrown if this bit _isn't_ where they expect it to be.

If I'm right about that then the question is whether we want to privilege the generic LinkGraph assumptions over the thumb ones, or vice versa.

[sgraenitz]

Dropping this in favor of D146641

llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h

 #ifndef LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H
 #define LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ExecutionEngine/JITLink/JITLinkMemoryManager.h"
 #include "llvm/ExecutionEngine/JITSymbol.h"
+#include "llvm/ExecutionEngine/Orc/Shared/ExecutorAddress.h"
 #include "llvm/ExecutionEngine/Orc/Shared/MemoryFlags.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/BinaryStreamWriter.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MathExtras.h"
assert(!Base.isDefined() &&
            "Cannot create absolute symbol from a defined block");
     auto *Sym = Allocator.Allocate<Symbol>();
     new (Sym) Symbol(Base, 0, Name, Size, L, S, IsLive, false);
     return *Sym;
   }
 
   static Symbol &constructAnonDef(BumpPtrAllocator &Allocator, Block &Base,
                                   orc::ExecutorAddrDiff Offset,
+                                  orc::ExecutorAddrDiff VirtualOffset,
                                   orc::ExecutorAddrDiff Size, bool IsCallable,
                                   bool IsLive) {
     assert((Offset + Size) <= Base.getSize() &&
            "Symbol extends past end of block");
     auto *Sym = Allocator.Allocate<Symbol>();
-    new (Sym) Symbol(Base, Offset, StringRef(), Size, Linkage::Strong,
+    new (Sym) Symbol(Base, Offset + VirtualOffset, StringRef(), Size, Linkage::Strong,
                      Scope::Local, IsLive, IsCallable);
     return *Sym;
   }
 
   static Symbol &constructNamedDef(BumpPtrAllocator &Allocator, Block &Base,
-                                   orc::ExecutorAddrDiff Offset, StringRef Name,
-                                   orc::ExecutorAddrDiff Size, Linkage L,
-                                   Scope S, bool IsLive, bool IsCallable) {
+                                   orc::ExecutorAddrDiff Offset,
+                                   orc::ExecutorAddrDiff VirtualOffset,
+                                   StringRef Name, orc::ExecutorAddrDiff Size,
+                                   Linkage L, Scope S, bool IsLive,
+                                   bool IsCallable) {
     assert((Offset + Size) <= Base.getSize() &&
            "Symbol extends past end of block");
     assert(!Name.empty() && "Name cannot be empty");
     auto *Sym = Allocator.Allocate<Symbol>();
-    new (Sym) Symbol(Base, Offset, Name, Size, L, S, IsLive, IsCallable);
+    new (Sym) Symbol(Base, Offset + VirtualOffset, Name, Size, L, S, IsLive, IsCallable);
     return *Sym;
   }
 
 public:
   /// Create a null Symbol. This allows Symbols to be default initialized for
   /// use in containers (e.g. as map values). Null symbols are only useful for
   /// assigning to.
   Symbol() = default;
void destroyBlock(Block &B) {
     Allocator.Deallocate(&B);
   }
 
   void destroySymbol(Symbol &S) {
     S.~Symbol();
     Allocator.Deallocate(&S);
   }
 
+  std::pair<orc::ExecutorAddrDiff, orc::ExecutorAddrDiff>
+  splitArchVirtualOffset(orc::ExecutorAddrDiff Offset) const;
+
   static iterator_range<Section::block_iterator> getSectionBlocks(Section &S) {
     return S.blocks();
   }
 
   static iterator_range<Section::const_block_iterator>
   getSectionConstBlocks(Section &S) {
     return S.blocks();
   }
Symbol &addAbsoluteSymbol(StringRef Name, orc::ExecutorAddr Address,
     AbsoluteSymbols.insert(&Sym);
     return Sym;
   }
 
   /// Add an anonymous symbol.
   Symbol &addAnonymousSymbol(Block &Content, orc::ExecutorAddrDiff Offset,
                              orc::ExecutorAddrDiff Size, bool IsCallable,
                              bool IsLive) {
-    auto &Sym = Symbol::constructAnonDef(Allocator, Content, Offset, Size,
-                                         IsCallable, IsLive);
+    auto [PhysicalOffset, VirtualOffset] = splitArchVirtualOffset(Offset);
+    auto &Sym =
+        Symbol::constructAnonDef(Allocator, Content, PhysicalOffset,
+                                 VirtualOffset, Size, IsCallable, IsLive);
     Content.getSection().addSymbol(Sym);
     return Sym;
   }
 
   /// Add a named symbol.
   Symbol &addDefinedSymbol(Block &Content, orc::ExecutorAddrDiff Offset,
                            StringRef Name, orc::ExecutorAddrDiff Size,
                            Linkage L, Scope S, bool IsCallable, bool IsLive) {
     assert((S == Scope::Local || llvm::count_if(defined_symbols(),
                                                 [&](const Symbol *Sym) {
                                                   return Sym->getName() == Name;
                                                 }) == 0) &&
            "Duplicate defined symbol");
-    auto &Sym = Symbol::constructNamedDef(Allocator, Content, Offset, Name,
-                                          Size, L, S, IsLive, IsCallable);
+    auto [PhysicalOffset, VirtualOffset] = splitArchVirtualOffset(Offset);
+    auto &Sym = Symbol::constructNamedDef(Allocator, Content, PhysicalOffset,
+                                          VirtualOffset, Name, Size, L, S,
+                                          IsLive, IsCallable);
     Content.getSection().addSymbol(Sym);
     return Sym;
   }
 
   iterator_range<section_iterator> sections() {
     return make_range(section_iterator(Sections.begin()),
                       section_iterator(Sections.end()));
   }

llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

// Handle symbol transfer/update.
     // Update offsets for all remaining symbols in B.
     for (auto *Sym : BlockSymbols)
       Sym->setOffset(Sym->getOffset() - SplitIndex);
   }
 
   return NewBlock;
 }
 
+std::pair<orc::ExecutorAddrDiff, orc::ExecutorAddrDiff>
+LinkGraph::splitArchVirtualOffset(orc::ExecutorAddrDiff Offset) const {
+  switch (TT.getArch()) {
+  case Triple::arm:
+  case Triple::armeb:
+  case Triple::thumb:
+  case Triple::thumbeb:
+    // On AArch32 the least significant bit (LSB) in a branch offset tells
+    // between Arm (LSB=0) and Thumb (LSB=1) destinations. We consider it a
+    // virtual offset since it isn't part of the physical branch range.
+    return {Offset & ~0x01, Offset & 0x01};
+  default:
+    break;
+  }
+  return {Offset, 0};
+}
+
 void LinkGraph::dump(raw_ostream &OS) {
   DenseMap<Block *, std::vector<Symbol *>> BlockSymbols;
 
   // Map from blocks to the symbols pointing at them.
   for (auto *Sym : defined_symbols())
     BlockSymbols[&Sym->getBlock()].push_back(Sym);
 
   // For each block, sort its symbols by something approximating