[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

5

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

5

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;
 }
 

lld/test/MachO/rebase-opcodes.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
+# RUN: %lld -dylib %t.o -o %t.dylib
+# RUN: obj2yaml %t.dylib | FileCheck %s
+
+## Test that:
+## 1/ Consecutive rebases are encoded as REBASE_OPCODE_DO_REBASE_IMM_TIMES.
+## 2/ Gaps smaller than 15 words are encoded as REBASE_OPCODE_ADD_ADDR_IMM_SCALED.
+## 3/ Gaps larger than that become REBASE_OPCODE_ADD_ADDR_ULEB.
+## FIXME: The last rebase could be transformed into a REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB.
+
+# CHECK: RebaseOpcodes:
+# CHECK-NEXT: Opcode:          REBASE_OPCODE_SET_TYPE_IMM
+# CHECK-NEXT: Imm:             1
+# CHECK-NEXT: Opcode:          REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB
+# CHECK-NEXT: Imm:             1
+# CHECK-NEXT: ExtraData:       [ 0x0 ]
+# CHECK-NEXT: Opcode:          REBASE_OPCODE_DO_REBASE_IMM_TIMES
+# CHECK-NEXT: Imm:             1
+# CHECK-NEXT: Opcode:          REBASE_OPCODE_ADD_ADDR_IMM_SCALED
+# CHECK-NEXT: Imm:             14
+# CHECK-NEXT: Opcode:          REBASE_OPCODE_DO_REBASE_IMM_TIMES
+# CHECK-NEXT: Imm:             3
+# CHECK-NEXT: Opcode:          REBASE_OPCODE_ADD_ADDR_ULEB
+# CHECK-NEXT: Imm:             0
+# CHECK-NEXT: ExtraData:       [ 0x78 ]
+# CHECK-NEXT: Opcode:          REBASE_OPCODE_DO_REBASE_IMM_TIMES
+# CHECK-NEXT: Imm:             1
+# CHECK-NEXT: Opcode:          REBASE_OPCODE_DONE
+# CHECK-NEXT: Imm:             0
+
+
+.text
+.globl _foo
+_foo:
+
+.data
+.quad _foo
+.space 112
+.quad _foo
+.quad _foo
+.quad _foo
+.space 120
+.quad _foo