[lld-macho] Optimize bind opcodes with multiple passes

[thevinster]

Summary

In D105866, we used an intermediate container to store a list of opcodes. Here,
we use that data structure to help us perform optimization passes that would allow
a more efficient encoding of bind opcodes. Currently, the functionality mirrors the
optimization pass {1,2} done in ld64 for bind opcodes under optimization gate
to prevent slight regressions.

[tschuett]

There is twice a 15 in your code. Are these magic numbers or could they be named constants?

[thevinster]

In D105867#2873885, @tschuett wrote:

There is twice a 15 in your code. Are these magic numbers or could they be named constants?

15 is the limit for data to be compacted within a single byte; otherwise it needs to be expanded. It turns out there is already a constant BIND_IMMEDIATE_MASK that already defines these values. I plan to separate pass 3 in a separate diff since that might involve some more changes.

[thevinster]

Separate out pass 3 and fix up tests

[thevinster]

Implement optimization gating since multiple passes showed regressions, clang-format

[tschuett]

Really stupid question: Are you tied to the order of entries in the vector or could changing the order allow further optimizations?

[int3]

@tschuett we already sort the bindings (in sortBindings) so the order should be pretty amenable to optimization

lld/MachO/Driver.cpp

1144 ↗

(On Diff #358841)

LLD-ELF defaults this to 1; I think we should follow suit (and gate the bind opcode optimization to > 1)

lld/MachO/SyntheticSections.cpp

370–372

nit: LLVM convention is to omit braces for one-liners

lld/test/MachO/lit.local.cfg

19 ↗

(On Diff #358841)

The -O flag should be in the bind-opcodes.s test file, instead of being turned on for all tests

[thevinster]

Will fix the rest.

lld/MachO/Driver.cpp

1144 ↗

(On Diff #358841)

I was considering that, but when I looked at the definitions of how clang (https://clang.llvm.org/docs/CommandGuide/clang.html#cmdoption-o0) uses the -O flag, they define -O0 as no optimizations which seemed fitting since we don't do any of it right now. That said, this does deviate from the LLD-ELF conventions and I'm happy to take either approaches if you feel strongly that it should be 1.

[int3]

lld/MachO/Driver.cpp

1144 ↗

(On Diff #358841)

yeah I think we should follow LLD-ELF more closely than we follow clang

[thevinster]

Address comments

[int3]

Thanks!

[thevinster]

Address minor refactor from D105866

lld/MachO/SyntheticSections.cpp

 namespace {
 struct Binding {
   OutputSegment *segment = nullptr;
   uint64_t offset = 0;
   int64_t addend = 0;
 };
 struct OpcodeTmp {
   uint8_t opcode = 0xF0;
-  uint64_t spread = 0; // Placeholder for offset or addend
+  uint64_t delta = 0; // Placeholder for offset or addend
+  uint64_t consecutiveCount = 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 OutputSection *osec, uint64_t outSecOff,
                           int64_t addend, Binding &lastBinding,
                           std::vector<OpcodeTmp> &opcodes) {
   OutputSegment *seg = osec->parent;
   uint64_t offset = osec->getSegmentOffset() + outSecOff;
   if (lastBinding.segment != seg) {
     OpcodeTmp op = {
       static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
                            seg->index), /* opcode */
-      offset /* spread */
+      offset /* delta */
     };
     opcodes.push_back(op);
     lastBinding.segment = seg;
     lastBinding.offset = offset;
   } else if (lastBinding.offset != offset) {
     OpcodeTmp op = {
       static_cast<uint8_t>(BIND_OPCODE_ADD_ADDR_ULEB), /* opcode */
-      offset - lastBinding.offset /* spread */
+      offset - lastBinding.offset /* delta */
     };
     opcodes.push_back(op);
     lastBinding.offset = offset;
   }
 
   if (lastBinding.addend != addend) {
     OpcodeTmp op = {
       static_cast<uint8_t>(BIND_OPCODE_SET_ADDEND_SLEB), /* opcode */
-      static_cast<uint64_t>(addend) /* spread */
+      static_cast<uint64_t>(addend) /* delta */
     };
     opcodes.push_back(op);
     lastBinding.addend = addend;
   }
 
   OpcodeTmp op = {
     static_cast<uint8_t>(BIND_OPCODE_DO_BIND), /* opcode */
-    0 /* spread */
+    0 /* delta */
   };
   opcodes.push_back(op);
   // DO_BIND causes dyld to both perform the binding and increment the offset
   lastBinding.offset += target->wordSize;
 }
 
+static void optimizeOpcodes(std::vector<OpcodeTmp> &opcodes) {
+  // Pass 1: Combine bind/add pairs
+  size_t i;
+  int pWrite = 0;
+  for (i = 1; i < opcodes.size(); ++i, ++pWrite) {
+    if ((opcodes[i].opcode == BIND_OPCODE_ADD_ADDR_ULEB)
+          && (opcodes[i-1].opcode == BIND_OPCODE_DO_BIND)) {
+      opcodes[pWrite].opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB;
+      opcodes[pWrite].delta = opcodes[i].delta;
+      ++i;
+    } else {
+      opcodes[pWrite] = opcodes[i-1];
+    }
+  }
+  if (i == opcodes.size()) {
+    opcodes[pWrite] = opcodes[i-1];
+  }
+  opcodes.resize(pWrite+1);
+
+  // Pass 2: Compress two or more bind_add opcodes
+  pWrite = 0;
+  for (i = 1; i < opcodes.size(); ++i, ++pWrite) {
+    if ((opcodes[i].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
+          && (opcodes[i-1].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
+          && (opcodes[i].delta == opcodes[i-1].delta)) {
+      opcodes[pWrite].opcode = BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB;
+      opcodes[pWrite].consecutiveCount = 2;
+      opcodes[pWrite].delta = opcodes[i].delta;
+      ++i;
+      while (i < opcodes.size() && (opcodes[i].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
+              && (opcodes[i].delta == opcodes[i-1].delta)) {
+        opcodes[pWrite].consecutiveCount++;
+        ++i;
+      }
+    } else {
+      opcodes[pWrite] = opcodes[i-1];
+    }
+  }
+  if (i == opcodes.size()) {
+    opcodes[pWrite] = opcodes[i-1];
+  }
+  opcodes.resize(pWrite+1);
+
+  // Pass 3: Use immediate encodings
+  for (OpcodeTmp* p = &opcodes[0]; p->opcode != REBASE_OPCODE_DONE; ++p) {
+    if ((p->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
+          && (p->delta < (15*sizeof(uint64_t)))
+          && ((p->delta % sizeof(uint64_t)) == 0)) {
+      p->opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED;
+      p->delta = p->delta/sizeof(uint64_t);
+    }
+  }
+}
+
 static void flushOpcodes(OpcodeTmp &op, raw_svector_ostream &os) {
   uint8_t opcode = op.opcode & 0xF0;
   switch (opcode) {
     case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
     case BIND_OPCODE_ADD_ADDR_ULEB:
+    case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
       os << op.opcode;
-      encodeULEB128(op.spread, os);
+      encodeULEB128(op.delta, os);
       break;
     case BIND_OPCODE_SET_ADDEND_SLEB:
       os << op.opcode;
-      encodeSLEB128(static_cast<int64_t>(op.spread), os);
+      encodeSLEB128(static_cast<int64_t>(op.delta), os);
       break;
     case BIND_OPCODE_DO_BIND:
       os << op.opcode;
       break;
+    case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
+      os << op.opcode;
+      encodeULEB128(op.consecutiveCount, os);
+      encodeULEB128(op.delta, os);
+      break;
+    case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
+      os << static_cast<uint8_t>(op.opcode | op.delta);
+      break;
     default:
       llvm_unreachable("cannot bind to an unrecognized symbol");
   }
 }
 
 // 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);
   assert(dysym.getFile()->isReferenced());
   return dysym.getFile()->ordinal;
 }
 
 static void encodeDylibOrdinal(int16_t ordinal, raw_svector_ostream &os) {
   if (ordinal <= 0) {
     os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM |
                                (ordinal & BIND_IMMEDIATE_MASK));
   } else if (ordinal <= BIND_IMMEDIATE_MASK) {
     os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | ordinal);
   } else {
-    os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
+    BindOpcode opcode = BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB;
+    if (ordinal <= 15) {
+      opcode = BIND_OPCODE_SET_DYLIB_ORDINAL_IMM;
+    }
+    os << static_cast<uint8_t>(opcode);
     encodeULEB128(ordinal, os);
   }
 }
 
 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)
if (ordinal != lastOrdinal) {
       encodeDylibOrdinal(ordinal, os);
       lastOrdinal = ordinal;
     }
     std::vector<OpcodeTmp> opcodes;
     for (const BindingEntry &b : bindings)
       encodeBinding(b.target.isec->parent,
                     b.target.isec->getOffset(b.target.offset), b.addend,
                     lastBinding, opcodes);
+    optimizeOpcodes(opcodes);
     for(auto &op : opcodes)
       flushOpcodes(op, os);
   }
   if (!bindingsMap.empty())
     os << static_cast<uint8_t>(BIND_OPCODE_DONE);
 }
 
 void BindingSection::writeTo(uint8_t *buf) const {

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
+## Test:
+## 1/ We emit exactly one BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM per symbol.
+## 2/ Combine BIND_OPCODE_DO_BIND and BIND_OPCODE_ADD_ADDR_ULEB pairs.
+## 3/ Compact BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB
+## 4/ Use BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED if possible.
+# RUN: obj2yaml %t/test | FileCheck %s --implicit-check-not BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM --implicit-check-not BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB --implicit-check-not BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB --implicit-check-not BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED
 
 # CHECK:      Opcode:          BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM
 # CHECK-NEXT: Imm:             0
 # CHECK-NEXT: Symbol:          _foo
 
+# CHECK:      Opcode:          BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB
+# CHECK-NEXT: Imm:             0
+# CHECK-NEXT: ULEBExtraData:   [ 0x2, 0x8 ]
+# CHECK-NEXT: Symbol:          ''
+
+# CHECK:      Opcode:          BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB
+# CHECK-NEXT: Imm:             0
+# CHECK-NEXT: ULEBExtraData:   [ 0x1008 ]
+# CHECK-NEXT: Symbol:          ''
+
 # CHECK:      Opcode:          BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM
 # CHECK-NEXT: Imm:             0
 # CHECK-NEXT: Symbol:          _bar
 
+# CHECK:      Opcode:          BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED
+# CHECK-NEXT: Imm:             1
+# CHECK-NEXT: Symbol:          ''
+
+# CHECK:      Opcode:          BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB
+# CHECK-NEXT: Imm:             0
+# CHECK-NEXT: ULEBExtraData:   [ 0x1008 ]
+# CHECK-NEXT: Symbol:          ''
+
 # 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-NEXT:  segment  section   address      type       addend dylib     symbol
+# BIND-NEXT:  __DATA   __data    0x100001000  pointer         0 libfoo    _foo
+# BIND-NEXT:  __DATA   __data    0x100001010  pointer         0 libfoo    _foo
+# BIND-NEXT:  __DATA   __data    0x100001020  pointer         1 libfoo    _foo
+# BIND-NEXT:  __DATA   __data    0x100002030  pointer         0 libfoo    _foo
+# BIND-NEXT:  __DATA   __data    0x100001008  pointer         0 libfoo    _bar
+# BIND-NEXT:  __DATA   __data    0x100001018  pointer         0 libfoo    _bar
+# BIND-NEXT:  __DATA   __data    0x100002028  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
+.quad _foo+1
+.zero 0x1000
+.quad _bar
+.quad _foo
 
 .globl _main
 .text
 _main: