[lld-macho] Use intermediate arrays to store opcodes

[thevinster]

Summary

We want to incorporate some of the optimization passes in bind opcodes from ld64.
This revision makes no functional changes but to start storing opcodes in intermediate
containers in preparation for implementing the optimization passes in a follow-up revision.

[thevinster]

Fix clang-format, rename variables

[thevinster]

Fix clang-tidy

[thevinster]

lld/MachO/SyntheticSections.cpp

395

@int3 - sortBindings already sorts the bindings. Is there any reason to have to re-sort again?

[int3]

lld/MachO/SyntheticSections.cpp

395

nope, it's leftover code from before I added sortBindings. good catch :)

[int3]

lld/MachO/SyntheticSections.cpp

280

how about BindIR?

282

how about renaming it to data so that there's less confusion about why we're using delta to refer to an offset or an addend?

(alternatively we could use a union here)

301–302

cast shouldn't be necessary any more I think. I used it for writing to the stream because we would otherwise call the integer overload of the stream operator. But here there's no overload to worry about

305

336

I don't think there's anything to mask here, since we are explicitly setting op.opcode to one of the opcode values minus any extra data. But we could do an assert to be on the safe side :)

[int3]

commit title nit: should mention *bind* opcodes for clarity

[oontvoo]

lld/MachO/SyntheticSections.cpp

335

Can this be const & instead? op isn't being modified by this.

449

const auto& ?

481

const auto& ?

[thevinster]

lld/MachO/SyntheticSections.cpp

336

Doesn't this operation BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | seg->index mean it's possible that extra data could be embedded in an opcode value? Otherwise, why perform seg->index in the first place?

[thevinster]

Address feedback

[int3]

lgtm with minor changes. Do you have commit rights or should I commit it for you?

lld/MachO/SyntheticSections.cpp

281–282

do we need these default values?

300–306

ah I guess we need the cast

336

derp yeah I forgot about that one

[thevinster]

lld/MachO/SyntheticSections.cpp

281–282

Probably not, since we always construct these values explicitly. But, the reason for having it as default is 1/ follow the convention of Binding struct and 2/ in the event that something goes awry, 0xF0 is not valid opcode and should make the program scream instead of accidentally writing "valid" values.

Plus, I think it'll debugging easier if we see these specific values when debugging.

300–306

Fwiw, the tests did pass. I'll revert to the old implementation.

[int3]

lld/MachO/SyntheticSections.cpp

281–282

0xF0 is not valid opcode and should make the program scream instead of accidentally writing "valid" values.

Can you add that as a comment? Otherwise it looks a bit like a magic number :)

[thevinster]

Add comments on default values, revert to cast

[int3]

lld/MachO/SyntheticSections.cpp

300–306

I get why we added the cast back, but the temporary seems unnecessary... we can construct it inline as part of the push_back statement.

Also, the cast is only needed for BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | seg->index as | returns an int (regardless of the size of its operands). We don't need the cast for the other opcodes below

(I thought you meant 'revert' as in 'partial revert', didn't realize you were going to do a full one)

[thevinster]

lld/MachO/SyntheticSections.cpp

300–306

My bad. I completely misunderstood. I'll make a forward fix of this on D105867 and make sure things are still running smoothly.

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;
 };
+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;
+};
 } // 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,
-                          raw_svector_ostream &os) {
+                          std::vector<BindIR> &opcodes) {
   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);
+    BindIR op = {
+        static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
+                             seg->index), // opcode
+        offset                            // data
+    };
+    opcodes.push_back(op);
     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);
+    BindIR op = {
+        static_cast<uint8_t>(BIND_OPCODE_ADD_ADDR_ULEB), // opcode
+        offset - lastBinding.offset                      // data
+    };
+    opcodes.push_back(op);
     lastBinding.offset = offset;
   }
 
   if (lastBinding.addend != addend) {
-    os << static_cast<uint8_t>(BIND_OPCODE_SET_ADDEND_SLEB);
-    encodeSLEB128(addend, os);
+    BindIR op = {
+        static_cast<uint8_t>(BIND_OPCODE_SET_ADDEND_SLEB), // opcode
+        static_cast<uint64_t>(addend)                      // data
+    };
+    opcodes.push_back(op);
     lastBinding.addend = addend;
   }
 
-  os << static_cast<uint8_t>(BIND_OPCODE_DO_BIND);
+  BindIR op = {
+      static_cast<uint8_t>(BIND_OPCODE_DO_BIND), // opcode
+      0                                          // data
+  };
+  opcodes.push_back(op);
   // DO_BIND causes dyld to both perform the binding and increment the offset
   lastBinding.offset += target->wordSize;
 }
 
+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:
+    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;
+  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;
 }
 

 void BindingSection::finalizeContents() {
   raw_svector_ostream os{contents};
   Binding lastBinding;
   int16_t lastOrdinal = 0;
 
   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();
-    });
     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);
       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, os);
+                    lastBinding, 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 {
   memcpy(buf, contents.data(), contents.size());
 }
for (const Defined *defined : definitions)
     encodeWeakOverride(defined, os);
 
   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);
+    std::vector<BindIR> opcodes;
     for (const BindingEntry &b : bindings)
       encodeBinding(b.target.isec->parent,
                     b.target.isec->getOffset(b.target.offset), b.addend,
-                    lastBinding, os);
+                    lastBinding, 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 {
   memcpy(buf, contents.data(), contents.size());
 }