[lld-macho] Only emit one BIND_OPCODE_SET_SYMBOL per symbol

[int3]

Summary

Size-wise, BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM is the most
expensive opcode, since it comes with an associated symbol string. We
were previously emitting it once per binding, instead of once per
symbol. This diff groups all bindings for a given symbol together and
ensures we only emit one such opcode per symbol. This matches ld64's
behavior.

While this is a relatively small win on chromium_framework (-72KiB), for
programs that have more dynamic bindings, the difference can be quite
large.

This change is perf-neutral when linking chromium_framework.

[thakis]

lld/MachO/SyntheticSections.cpp

358

Is it guaranteed that we have filtered out separate symbols pointing at the same address by now? If not, this has nondeterminism issues (here and in the sort below)

[int3]

lld/MachO/SyntheticSections.cpp

358

These are binding address, not symbol addresses, and I don't think any well-formed program will have two bindings pointing to the same address. I'm not even sure how you would generate that; I suppose you could use obj2yaml to hand-craft two relocations pointing at the same address, but I don't think it's possible if you're writing assembly.

Also FWIW I double-checked with -DLLVM_ENABLE_EXPENSIVE_CHECKS, and our test cases don't find any issues with this

[int3]

lld/MachO/SyntheticSections.cpp

358

ICF could cause two binds to point to the same dedup'ed address, but that gets fixed by D105044: [lld-macho] Move ICF earlier to avoid emitting redundant binds :)

[int3]

bump

[thakis]

lgtm

lld/MachO/SyntheticSections.h

 
 #include "Config.h"
 #include "ExportTrie.h"
 #include "InputSection.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "Target.h"
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/MC/StringTableBuilder.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <unordered_map>
 
public:
   }
 
 private:
   std::vector<Location> locations;
   SmallVector<char, 128> contents;
 };
 
 struct BindingEntry {
-  const DylibSymbol *dysym;
   int64_t addend;
   Location target;
-  BindingEntry(const DylibSymbol *dysym, int64_t addend, Location target)
-      : dysym(dysym), addend(addend), target(std::move(target)) {}
+  BindingEntry(int64_t addend, Location target)
+      : addend(addend), target(std::move(target)) {}
 };
 
+template <class Sym>
+using BindingsMap = llvm::DenseMap<Sym, std::vector<BindingEntry>>;
+
 // Stores bind opcodes for telling dyld which symbols to load non-lazily.
 class BindingSection final : public LinkEditSection {
 public:
   BindingSection();
   void finalizeContents() override;
   uint64_t getRawSize() const override { return contents.size(); }
-  bool isNeeded() const override { return !bindings.empty(); }
+  bool isNeeded() const override { return !bindingsMap.empty(); }
   void writeTo(uint8_t *buf) const override;
 
   void addEntry(const DylibSymbol *dysym, const InputSection *isec,
                 uint64_t offset, int64_t addend = 0) {
-    bindings.emplace_back(dysym, addend, Location(isec, offset));
+    bindingsMap[dysym].emplace_back(addend, Location(isec, offset));
   }
 
 private:
-  std::vector<BindingEntry> bindings;
+  BindingsMap<const DylibSymbol *> bindingsMap;
   SmallVector<char, 128> contents;
 };
 
-struct WeakBindingEntry {
-  const Symbol *symbol;
-  int64_t addend;
-  Location target;
-  WeakBindingEntry(const Symbol *symbol, int64_t addend, Location target)
-      : symbol(symbol), addend(addend), target(std::move(target)) {}
-};
-
 // Stores bind opcodes for telling dyld which weak symbols need coalescing.
 // There are two types of entries in this section:
 //
 //   1) Non-weak definitions: This is a symbol definition that weak symbols in
 //   other dylibs should coalesce to.
 //
 //   2) Weak bindings: These tell dyld that a given symbol reference should
 //   coalesce to a non-weak definition if one is found. Note that unlike the
 //   entries in the BindingSection, the bindings here only refer to these
 //   symbols by name, but do not specify which dylib to load them from.
 class WeakBindingSection final : public LinkEditSection {
 public:
   WeakBindingSection();
   void finalizeContents() override;
   uint64_t getRawSize() const override { return contents.size(); }
   bool isNeeded() const override {
-    return !bindings.empty() || !definitions.empty();
+    return !bindingsMap.empty() || !definitions.empty();
   }
 
   void writeTo(uint8_t *buf) const override;
 
   void addEntry(const Symbol *symbol, const InputSection *isec, uint64_t offset,
                 int64_t addend = 0) {
-    bindings.emplace_back(symbol, addend, Location(isec, offset));
+    bindingsMap[symbol].emplace_back(addend, Location(isec, offset));
   }
 
-  bool hasEntry() const { return !bindings.empty(); }
+  bool hasEntry() const { return !bindingsMap.empty(); }
 
   void addNonWeakDefinition(const Defined *defined) {
     definitions.emplace_back(defined);
   }
 
   bool hasNonWeakDefinition() const { return !definitions.empty(); }
 
 private:
-  std::vector<WeakBindingEntry> bindings;
+  BindingsMap<const Symbol *> bindingsMap;
   std::vector<const Defined *> definitions;
   SmallVector<char, 128> contents;
 };
 
 // The following sections implement lazy symbol binding -- very similar to the
 // PLT mechanism in ELF.
 //
 // ELF's .plt section is broken up into two sections in Mach-O: StubsSection

lld/MachO/SyntheticSections.cpp

 BindingSection::BindingSection()
     : LinkEditSection(segment_names::linkEdit, section_names::binding) {}
 
 namespace {
 struct Binding {
   OutputSegment *segment = nullptr;
   uint64_t offset = 0;
   int64_t addend = 0;
-  int16_t ordinal = 0;
 };
 } // namespace
 
 // Encode a sequence of opcodes that tell dyld to write the address of symbol +
 // addend at osec->addr + outSecOff.
 //
 // The bind opcode "interpreter" remembers the values of each binding field, so
 // we only need to encode the differences between bindings. Hence the use of
 // lastBinding.
-static void encodeBinding(const Symbol *sym, const OutputSection *osec,
-                          uint64_t outSecOff, int64_t addend,
-                          bool isWeakBinding, Binding &lastBinding,
+static void encodeBinding(const OutputSection *osec, uint64_t outSecOff,
+                          int64_t addend, Binding &lastBinding,
                           raw_svector_ostream &os) {
   OutputSegment *seg = osec->parent;
   uint64_t offset = osec->getSegmentOffset() + outSecOff;
   if (lastBinding.segment != seg) {
     os << static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
                                seg->index);
     encodeULEB128(offset, os);
     lastBinding.segment = seg;
     lastBinding.offset = offset;
   } else if (lastBinding.offset != offset) {
     os << static_cast<uint8_t>(BIND_OPCODE_ADD_ADDR_ULEB);
     encodeULEB128(offset - lastBinding.offset, os);
     lastBinding.offset = offset;
   }
 
   if (lastBinding.addend != addend) {
     os << static_cast<uint8_t>(BIND_OPCODE_SET_ADDEND_SLEB);
     encodeSLEB128(addend, os);
     lastBinding.addend = addend;
   }
 
-  uint8_t flags = BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
-  if (!isWeakBinding && sym->isWeakRef())
-    flags |= BIND_SYMBOL_FLAGS_WEAK_IMPORT;
-
-  os << flags << sym->getName() << '\0'
-     << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER)
-     << static_cast<uint8_t>(BIND_OPCODE_DO_BIND);
+  os << static_cast<uint8_t>(BIND_OPCODE_DO_BIND);
   // DO_BIND causes dyld to both perform the binding and increment the offset
   lastBinding.offset += target->wordSize;
 }
 
 // Non-weak bindings need to have their dylib ordinal encoded as well.
 static int16_t ordinalForDylibSymbol(const DylibSymbol &dysym) {
   if (config->namespaceKind == NamespaceKind::flat || dysym.isDynamicLookup())
     return static_cast<int16_t>(BIND_SPECIAL_DYLIB_FLAT_LOOKUP);

 
 static void encodeWeakOverride(const Defined *defined,
                                raw_svector_ostream &os) {
   os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM |
                              BIND_SYMBOL_FLAGS_NON_WEAK_DEFINITION)
      << defined->getName() << '\0';
 }
 
+// Organize the bindings so we can encoded them with fewer opcodes.
+//
+// First, all bindings for a given symbol should be grouped together.
+// BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM is the largest opcode (since it
+// has an associated symbol string), so we only want to emit it once per symbol.
+//
+// Within each group, we sort the bindings by address. Since bindings are
+// delta-encoded, sorting them allows for a more compact result. Note that
+// sorting by address alone ensures that bindings for the same segment / section
+// are located together, minimizing the number of times we have to emit
+// BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB.
+//
+// Finally, we sort the symbols by the address of their first binding, again
+// to facilitate the delta-encoding process.
+template <class Sym>
+std::vector<std::pair<const Sym *, std::vector<BindingEntry>>>
+sortBindings(const BindingsMap<const Sym *> &bindingsMap) {
+  std::vector<std::pair<const Sym *, std::vector<BindingEntry>>> bindingsVec(
+      bindingsMap.begin(), bindingsMap.end());
+  for (auto &p : bindingsVec) {
+    std::vector<BindingEntry> &bindings = p.second;
+    llvm::sort(bindings, [](const BindingEntry &a, const BindingEntry &b) {
+      return a.target.getVA() < b.target.getVA();
+    });
+  }
+  llvm::sort(bindingsVec, [](const auto &a, const auto &b) {
+    return a.second[0].target.getVA() < b.second[0].target.getVA();
+  });
+  return bindingsVec;
+}
+
 // Emit bind opcodes, which are a stream of byte-sized opcodes that dyld
 // interprets to update a record with the following fields:
 //  * segment index (of the segment to write the symbol addresses to, typically
 //    the __DATA_CONST segment which contains the GOT)
 //  * offset within the segment, indicating the next location to write a binding
 //  * symbol type
 //  * symbol library ordinal (the index of its library's LC_LOAD_DYLIB command)
 //  * symbol name
 //  * addend
 // When dyld sees BIND_OPCODE_DO_BIND, it uses the current record state to bind
 // a symbol in the GOT, and increments the segment offset to point to the next
 // entry. It does *not* clear the record state after doing the bind, so
 // subsequent opcodes only need to encode the differences between bindings.
 void BindingSection::finalizeContents() {
   raw_svector_ostream os{contents};
   Binding lastBinding;
+  int16_t lastOrdinal = 0;
 
-  // Since bindings are delta-encoded, sorting them allows for a more compact
-  // result. Note that sorting by address alone ensures that bindings for the
-  // same segment / section are located together.
+  for (auto &p : sortBindings(bindingsMap)) {
+    const DylibSymbol *sym = p.first;
+    std::vector<BindingEntry> &bindings = p.second;
     llvm::sort(bindings, [](const BindingEntry &a, const BindingEntry &b) {
       return a.target.getVA() < b.target.getVA();
     });
-  for (const BindingEntry &b : bindings) {
-    int16_t ordinal = ordinalForDylibSymbol(*b.dysym);
-    if (ordinal != lastBinding.ordinal) {
+    uint8_t flags = BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
+    if (sym->isWeakRef())
+      flags |= BIND_SYMBOL_FLAGS_WEAK_IMPORT;
+    os << flags << sym->getName() << '\0'
+       << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
+    int16_t ordinal = ordinalForDylibSymbol(*sym);
+    if (ordinal != lastOrdinal) {
       encodeDylibOrdinal(ordinal, os);
-      lastBinding.ordinal = ordinal;
+      lastOrdinal = ordinal;
     }
-    encodeBinding(b.dysym, b.target.isec->parent,
+    for (const BindingEntry &b : bindings)
+      encodeBinding(b.target.isec->parent,
                     b.target.isec->getOffset(b.target.offset), b.addend,
-                  /*isWeakBinding=*/false, lastBinding, os);
+                    lastBinding, os);
   }
-  if (!bindings.empty())
+  if (!bindingsMap.empty())
     os << static_cast<uint8_t>(BIND_OPCODE_DONE);
 }
 
 void BindingSection::writeTo(uint8_t *buf) const {
   memcpy(buf, contents.data(), contents.size());
 }
 
 WeakBindingSection::WeakBindingSection()
     : LinkEditSection(segment_names::linkEdit, section_names::weakBinding) {}
 
 void WeakBindingSection::finalizeContents() {
   raw_svector_ostream os{contents};
   Binding lastBinding;
 
   for (const Defined *defined : definitions)
     encodeWeakOverride(defined, os);
 
-  // Since bindings are delta-encoded, sorting them allows for a more compact
-  // result.
-  llvm::sort(bindings,
-             [](const WeakBindingEntry &a, const WeakBindingEntry &b) {
-               return a.target.getVA() < b.target.getVA();
-             });
-  for (const WeakBindingEntry &b : bindings)
-    encodeBinding(b.symbol, b.target.isec->parent,
+  for (auto &p : sortBindings(bindingsMap)) {
+    const Symbol *sym = p.first;
+    std::vector<BindingEntry> &bindings = p.second;
+    os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM)
+       << sym->getName() << '\0'
+       << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
+    for (const BindingEntry &b : bindings)
+      encodeBinding(b.target.isec->parent,
                     b.target.isec->getOffset(b.target.offset), b.addend,
-                  /*isWeakBinding=*/true, lastBinding, os);
-  if (!bindings.empty() || !definitions.empty())
+                    lastBinding, os);
+  }
+  if (!bindingsMap.empty() || !definitions.empty())
     os << static_cast<uint8_t>(BIND_OPCODE_DONE);
 }
 
 void WeakBindingSection::writeTo(uint8_t *buf) const {
   memcpy(buf, contents.data(), contents.size());
 }
 
 StubsSection::StubsSection()

lld/test/MachO/bind-opcodes.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/foo.s -o %t/foo.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
+# RUN: %lld -dylib %t/foo.o -o %t/libfoo.dylib
+# RUN: %lld -lSystem %t/test.o %t/libfoo.dylib -o %t/test
+
+## Make sure we emit exactly one BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM per
+## symbol.
+# RUN: obj2yaml %t/test | FileCheck %s --implicit-check-not BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM
+
+# CHECK:      Opcode:          BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM
+# CHECK-NEXT: Imm:             0
+# CHECK-NEXT: Symbol:          _foo
+
+# CHECK:      Opcode:          BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM
+# CHECK-NEXT: Imm:             0
+# CHECK-NEXT: Symbol:          _bar
+
+# RUN: llvm-objdump --macho --bind %t/test | FileCheck %s --check-prefix=BIND
+# BIND:       Bind table:
+# BIND-NEXT:  segment  section address type    addend dylib   symbol
+# BIND-NEXT:  __DATA   __data  {{.*}}  pointer      0 libfoo  _foo
+# BIND-NEXT:  __DATA   __data  {{.*}}  pointer      0 libfoo  _foo
+# BIND-NEXT:  __DATA   __data  {{.*}}  pointer      0 libfoo  _bar
+# BIND-NEXT:  __DATA   __data  {{.*}}  pointer      0 libfoo  _bar
+# BIND-EMPTY:
+
+#--- foo.s
+.globl _foo, _bar
+_foo:
+  .space 4
+_bar:
+  .space 4
+
+#--- test.s
+.data
+.quad _foo
+.quad _bar
+.quad _foo
+.quad _bar
+
+.globl _main
+.text
+_main: