[lld-macho] Emit REBASE_OPCODE_ADD_ADDR_IMM_SCALED if possible

[BertalanD]

Summary

An ADD_ADDR rebase opcode's argument can be encoded as an immediate if
the offset is less than 15 * word size. This change reduces the size of
chromium_framework by 100+ KiB.

[int3]

can we have a test for this? obj2yaml dumps out the exact opcodes used, so we can check using that. See e.g. bind-opcodes.s

[BertalanD]

Added a test.

[int3]

Thanks!

lld/MachO/SyntheticSections.cpp

209–210

micro-opt suggestion: div/mod instructions are relatively expensive, so writing this in terms of target->p2WordSize would probably be more efficient. just a suggestion for a future diff, I think we have a bunch of other places in the code that could be similarly changed

lld/test/MachO/rebase-opcodes.s

4 ↗

(On Diff #441098)

just wondering, any reason you pick arm64? nothing wrong with that of course, but %lld defaults to -arch x86_64, so this is an extra flag that you're having to pass

[BertalanD]

lld/test/MachO/rebase-opcodes.s

4 ↗

(On Diff #441098)

There wasn't any particular reason other than the fact I'm developing on an ARM Mac. I'll push the commit with the arch changed to x86.

lld/MachO/SyntheticSections.cpp

if (lastRebase.segment != seg || lastRebase.offset != offset) {
     if (lastRebase.segment != seg) {
       os << static_cast<uint8_t>(REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
                                  seg->index);
       encodeULEB128(offset, os);
       lastRebase.segment = seg;
       lastRebase.offset = offset;
     } else {
       assert(lastRebase.offset != offset);
+      uint64_t delta = offset - lastRebase.offset;
+      // For unknown reasons, ld64 checks if the scaled offset is strictly less
+      // than REBASE_IMMEDIATE_MASK instead of allowing equality. We match this
+      // behavior as a precaution.
+      if ((delta % target->wordSize == 0) &&
+          (delta / target->wordSize < REBASE_IMMEDIATE_MASK)) {
+        os << static_cast<uint8_t>(REBASE_OPCODE_ADD_ADDR_IMM_SCALED |
+                                   (delta / target->wordSize));
+      } else {
         os << static_cast<uint8_t>(REBASE_OPCODE_ADD_ADDR_ULEB);
-      encodeULEB128(offset - lastRebase.offset, os);
+        encodeULEB128(delta, os);
+      }
       lastRebase.offset = offset;
     }
   }
   ++lastRebase.consecutiveCount;
   // DO_REBASE causes dyld to both perform the binding and increment the offset
   lastRebase.offset += target->wordSize;
 }