[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

1173

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

lld/MachO/SyntheticSections.cpp

362–364

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

1173

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

1173

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/Config.h

struct Configuration {
   bool emitEncryptionInfo = false;
   bool timeTraceEnabled = false;
   bool dataConst = false;
   bool dedupLiterals = true;
   uint32_t headerPad;
   uint32_t dylibCompatibilityVersion = 0;
   uint32_t dylibCurrentVersion = 0;
   uint32_t timeTraceGranularity = 500;
+  unsigned optimize;
   std::string progName;
 
   // For `clang -arch arm64 -arch x86_64`, clang will:
   // 1. invoke the linker twice, to write one temporary output per arch
   // 2. invoke `lipo` to merge the two outputs into a single file
   // `outputFile` is the name of the temporary file the linker writes to.
   // `finalOutput `is the name of the file lipo writes to after the link.
   llvm::StringRef outputFile;

lld/MachO/Driver.cpp

for (const Arg *arg : args.filtered(OPT_u)) {
     config->explicitUndefineds.push_back(symtab->addUndefined(
         arg->getValue(), /*file=*/nullptr, /*isWeakRef=*/false));
   }
 
   for (const Arg *arg : args.filtered(OPT_U))
     symtab->addDynamicLookup(arg->getValue());
 
   config->mapFile = args.getLastArgValue(OPT_map);
+  config->optimize = args::getInteger(args, OPT_O, 1);
   config->outputFile = args.getLastArgValue(OPT_o, "a.out");
   config->finalOutput =
       args.getLastArgValue(OPT_final_output, config->outputFile);
   config->astPaths = args.getAllArgValues(OPT_add_ast_path);
   config->headerPad = args::getHex(args, OPT_headerpad, /*Default=*/32);
   config->headerPadMaxInstallNames =
       args.hasArg(OPT_headerpad_max_install_names);
   config->printDylibSearch =

lld/MachO/Options.td

def icf_eq: Joined<["--"], "icf=">,
     Group<grp_lld>;
 def lto_O: Joined<["--"], "lto-O">,
     HelpText<"Set optimization level for LTO (default: 2)">,
     MetaVarName<"<opt-level>">,
     Group<grp_lld>;
 def thinlto_cache_policy: Joined<["--"], "thinlto-cache-policy=">,
     HelpText<"Pruning policy for the ThinLTO cache">,
     Group<grp_lld>;
+def O : JoinedOrSeparate<["-"], "O">,
+    HelpText<"Optimize output file size">;
 
 // This is a complete Options.td compiled from Apple's ld(1) manpage
 // dated 2018-03-07 and cross checked with ld64 source code in repo
 // https://github.com/apple-opensource/ld64 at git tag "512.4" dated
 // 2018-03-18.
 
 // Flags<[HelpHidden]> marks options that are not yet ported to lld,
 // and serve as a scoreboard for annotating our progress toward

lld/MachO/SyntheticSections.cpp

struct Binding {
   uint64_t offset = 0;
   int64_t addend = 0;
 };
 struct BindIR {
   // Default value of 0xF0 is not valid opcode and should make the program
   // scream instead of accidentally writing "valid" values.
   uint8_t opcode = 0xF0;
   uint64_t data = 0;
+  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<BindIR> &opcodes) {
   OutputSegment *seg = osec->parent;
   uint64_t offset = osec->getSegmentOffset() + outSecOff;
   if (lastBinding.segment != seg) {
-    BindIR op = {
-        static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
-                             seg->index), // opcode
-        offset                            // data
-    };
-    opcodes.push_back(op);
+    opcodes.push_back(
+        {static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
+                              seg->index),
+         offset});
     lastBinding.segment = seg;
     lastBinding.offset = offset;
   } else if (lastBinding.offset != offset) {
-    BindIR op = {
-        static_cast<uint8_t>(BIND_OPCODE_ADD_ADDR_ULEB), // opcode
-        offset - lastBinding.offset                      // data
-    };
-    opcodes.push_back(op);
+    opcodes.push_back({BIND_OPCODE_ADD_ADDR_ULEB, offset - lastBinding.offset});
     lastBinding.offset = offset;
   }
 
   if (lastBinding.addend != addend) {
-    BindIR op = {
-        static_cast<uint8_t>(BIND_OPCODE_SET_ADDEND_SLEB), // opcode
-        static_cast<uint64_t>(addend)                      // data
-    };
-    opcodes.push_back(op);
+    opcodes.push_back(
+        {BIND_OPCODE_SET_ADDEND_SLEB, static_cast<uint64_t>(addend)});
     lastBinding.addend = addend;
   }
 
-  BindIR op = {
-      static_cast<uint8_t>(BIND_OPCODE_DO_BIND), // opcode
-      0                                          // data
-  };
-  opcodes.push_back(op);
+  opcodes.push_back({BIND_OPCODE_DO_BIND, 0});
   // DO_BIND causes dyld to both perform the binding and increment the offset
   lastBinding.offset += target->wordSize;
 }
 
+static void optimizeOpcodes(std::vector<BindIR> &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].data = opcodes[i].data;
+      ++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].data == opcodes[i - 1].data)) {
+      opcodes[pWrite].opcode = BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB;
+      opcodes[pWrite].consecutiveCount = 2;
+      opcodes[pWrite].data = opcodes[i].data;
+      ++i;
+      while (i < opcodes.size() &&
+             (opcodes[i].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
+             (opcodes[i].data == opcodes[i - 1].data)) {
+        opcodes[pWrite].consecutiveCount++;
+        ++i;
+      }
+    } else {
+      opcodes[pWrite] = opcodes[i - 1];
+    }
+  }
+  if (i == opcodes.size())
+    opcodes[pWrite] = opcodes[i - 1];
+  opcodes.resize(pWrite + 1);
+}
+
 static void flushOpcodes(const BindIR &op, raw_svector_ostream &os) {
   uint8_t opcode = op.opcode & BIND_OPCODE_MASK;
   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.data, os);
     break;
   case BIND_OPCODE_SET_ADDEND_SLEB:
     os << op.opcode;
     encodeSLEB128(static_cast<int64_t>(op.data), 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.data, os);
+    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())
if (ordinal != lastOrdinal) {
       encodeDylibOrdinal(ordinal, os);
       lastOrdinal = ordinal;
     }
     std::vector<BindIR> opcodes;
     for (const BindingEntry &b : bindings)
       encodeBinding(b.target.isec->parent,
                     b.target.isec->getOffset(b.target.offset), b.addend,
                     lastBinding, opcodes);
+    if (config->optimize > 1)
+      optimizeOpcodes(opcodes);
     for (const auto &op : opcodes)
       flushOpcodes(op, os);
   }
   if (!bindingsMap.empty())
     os << static_cast<uint8_t>(BIND_OPCODE_DONE);
 }
 
 void BindingSection::writeTo(uint8_t *buf) const {
for (auto &p : sortBindings(bindingsMap)) {
     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);
     std::vector<BindIR> opcodes;
     for (const BindingEntry &b : bindings)
       encodeBinding(b.target.isec->parent,
                     b.target.isec->getOffset(b.target.offset), b.addend,
                     lastBinding, opcodes);
+    if (config->optimize > 1)
+      optimizeOpcodes(opcodes);
     for (const auto &op : opcodes)
       flushOpcodes(op, os);
   }
   if (!bindingsMap.empty() || !definitions.empty())
     os << static_cast<uint8_t>(BIND_OPCODE_DONE);
 }
 
 void WeakBindingSection::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
+# RUN: %lld -O2 -dylib %t/foo.o -o %t/libfoo.dylib
+# RUN: %lld -O2 -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
+# RUN: obj2yaml %t/test | FileCheck %s
 
-# 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
+# CHECK:      BindOpcodes:
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM
+# CHECK-NEXT:   Imm:             0
+# CHECK-NEXT:   Symbol:          _foo
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_SET_TYPE_IMM
+# CHECK-NEXT:   Imm:             1
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_SET_DYLIB_ORDINAL_IMM
+# CHECK-NEXT:   Imm:             2
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB
+# CHECK-NEXT:   Imm:             2
+# CHECK-NEXT:   ULEBExtraData:   [ 0x0 ]
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB
+# CHECK-NEXT:   Imm:             0
+# CHECK-NEXT:   ULEBExtraData:   [ 0x2, 0x8 ]
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_SET_ADDEND_SLEB
+# CHECK-NEXT:   Imm:             0
+# CHECK-NEXT:   SLEBExtraData:   [ 1 ]
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB
+# CHECK-NEXT:   Imm:             0
+# CHECK-NEXT:   ULEBExtraData:   [ 0x1008 ]
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_SET_ADDEND_SLEB
+# CHECK-NEXT:   Imm:             0
+# CHECK-NEXT:   SLEBExtraData:   [ 0 ]
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_DO_BIND
+# CHECK-NEXT:   Imm:             0
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM
+# CHECK-NEXT:   Imm:             0
+# CHECK-NEXT:   Symbol:          _bar
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_SET_TYPE_IMM
+# CHECK-NEXT:   Imm:             1
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_ADD_ADDR_ULEB
+# CHECK-NEXT:   Imm:             0
+# CHECK-NEXT:   ULEBExtraData:   [ 0xFFFFFFFFFFFFEFD0 ]
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB
+# CHECK-NEXT:   Imm:             0
+# CHECK-NEXT:   ULEBExtraData:   [ 0x8 ]
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB
+# CHECK-NEXT:   Imm:             0
+# CHECK-NEXT:   ULEBExtraData:   [ 0x1008 ]
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_DO_BIND
+# CHECK-NEXT:   Imm:             0
+# CHECK-NEXT:   Symbol:          ''
+# CHECK-NEXT:   Opcode:          BIND_OPCODE_DONE
+# CHECK-NEXT:   Imm:             0
+# 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: