[lld-macho] Add support for objc_msgSend stubs

[keith]

Summary

[lld-macho] Add support for objc_msgSend stubs

Apple Clang in Xcode 14 introduced a new feature for reducing the
overhead of objc_msgSend calls by deduplicating the setup calls for each
individual selector. This works by clang adding undefined symbols for
each selector called in a translation unit, such as _objc_msgSend$foo
for calling the foo method on any NSObject. There are 2
different modes for this behavior, the default directly does the setup
for _objc_msgSend and calls it, and the smaller option does the
selector setup, and then calls the standard _objc_msgSend stub
function.

The general overview of how this works is:

• Undefined symbols with the given prefix are collected
• The suffix of each matching undefined symbol is added as a string to __objc_methname
• A pointer is added for every method name in the __objc_selrefs section
• A got entry is emitted for _objc_msgSend
• Stubs are emitting pointing to the synthesized locations

Notes:

• Both __objc_methname and __objc_selrefs can also exist from object files, so their contents are merged with our synthesized contents
• The compiler emits method names for defined methods, but not for undefined symbols you call, but stubs are used for both
• This only implements the default "fast" mode currently just to reduce the diff, I also doubt many folks will care to swap modes
• This only implements this for arm64 and x86_64, we don't need to implement this for 32 bit iOS archs, but we should implement it for watchOS archs in a later diff

[keith]

This is a WIP version of https://github.com/llvm/llvm-project/issues/56034 I wanted to submit it early to hopefully get some initial reactions from folks in case I'm going down a bad path here! FYI I'm out through 7/5th, so I won't get back to this until sometime after then.

There are quite a few things left to do mostly outlined by TODOs here. Right now this doesn't work with non-trivial programs because some (not sure the conditions here) object files contain a __objc_selrefs section that conflicts with the one I'm creating. I also have only been testing this on my M1 mac, which is why I've only done the arm64 support so far, and clearly I haven't added any tests yet.

But I'd love to get feedback on the overall approach here before I flesh out these TODOs!

[int3]

This looks like a reasonable approach. Re the section name conflict, do we just need to apply relocations + concatenate the output (i.e. what ConcatOutputSection is doing), or do we have to do something more complicated? Whether to make SyntheticSections subclasses of InputSections vs OutputSections has been something we've debated for a while... LLD-ELF makes them subclass InputSections but we don't, and maybe this use case should make us rethink that.

lld/MachO/SyntheticSections.cpp

730–732

maybe do something similar to what we have for StubHelperSection::setup()

755

I would just do an if check for 32/64 bit here, I don't think we should having ObjC implementation details exposed on the Target class

[int3]

lld/MachO/Writer.cpp

698–700

I think this should be part of treatSpecialUndefineds, which runs before scanSymbols -- I expect that we'd raise undef symbol errors otherwise

[int3]

lld/MachO/SyntheticSections.cpp

755

nvm, I realize this is in line with what we're already doing for the regular stubs code + arch dependency means that we'd need to check for more than word size

[int3]

lld/MachO/Writer.cpp

698–700

oh wait no we do the actual undef check in scanRelocations, so this is fine.

Sorry -- I've been away from the code for a while, should have paged in a bit more context before reviewing :)

[keith]

Thanks for doing a first pass!

In D128108#3631007, @int3 wrote:

Re the section name conflict, do we just need to apply relocations + concatenate the output (i.e. what ConcatOutputSection is doing), or do we have to do something more complicated?

This is a good question that still requires more investigation from me. I have found so far that these sections already exist in object files only in _some_ cases and I haven't yet figured out why that is, or how that needs to be handled. I didn't hit that case until I started testing on real world codebases, and even then only a small subset of object files have them.

[keith]

Implmenet much more robust version

[keith]

Minor todos

[keith]

Add more test coverage

[keith]

rebase to resolve conflicts

[keith]

@int3 ok can you take another look here? I haven't implemented non arm64, or the "small" mode yet, but otherwise this is more complete than before.

[int3]

lld/MachO/SyntheticSections.cpp

732

isn't the string already null-terminated? why do we have to add another \0?

781–782

I'm not sure I understand how InputSection ordering matters... also, which offset are you referring to here?

Plus inserting like this means that we are copying the entire vector, which is pretty large... would prefer if we didn't have to do this

1618

Why can't we just use stringMapOffset itself? Is it because it isn't available in the non-deduplicated CStringSection?

If that's the case, I wonder if we should just always have __objc_methname be deduplicated...

[keith]

Add selrefs to end of inputSections

lld/MachO/SyntheticSections.cpp

732

I didn't dig into this, but this is how I got here:

In CStringSection:

StringRef string = isec->getStringRef(i);
llvm::outs() << "'" << string << "'" << " len: " << string.size() << "\n";

This prints: 'foo' size 4.

In ObjCStubsSection::addEntry

llvm::outs() << "'" << sym->getName() << "' size " << sym->getName().size() << "\n";
std::string methname = sym->getName().drop_front(symbolPrefixLength).str();

This prints 'foo' size 3.

781–782

Sorry I didn't go back to check this. I originally added it before I started using getVA for the selrefs section, with that change this isn't required. Removed.

1618

Why can't we just use stringMapOffset itself? Is it because it isn't available in the non-deduplicated CStringSection?

Correct

If that's the case, I wonder if we should just always have __objc_methname be deduplicated...

Yea we could definitely do that if you think the performance downside wouldn't be a big deal. I didn't feel great adding this here either, but figured the time savings on larger codebases might be significant enough to warrant the complexity.

[keith]

Minor format

[int3]

lld/MachO/SyntheticSections.cpp

1618

yeah initially I wanted to keep the default output of LLD 100% unoptimized but I'm having second thoughts... firstly the behavior difference wrt ld64 is not ideal, secondly we haven't parallelized this yet, thirdly the extra data we have to write for __cstring probably offsets the perf savings we get from not dedup'ing (just as I've found some builds to be faster with -dead_strip), and fourthly, the code complexity...

would be nice to pick an objC-intensive app and run a benchmark here. but I don't think a minor regression here should block this, we can work on parallelizing this later instead

[keith]

Always deduplicate methnames

[keith]

Remove leftover members

[keith]

Handle arguments

[keith]

Add x86_64 support

[keith]

Small fixups

[keith]

Resolve more todos

[keith]

Minor cleanup

[keith]

@int3 ok I've updated this with all the major outstanding issues and updated the description with the current state. I believe this is ready for more serious review. Let me know if you think I should implement either of things I'm planning to defer here, the small mode and watchOS support, or if you're also ok with us doing those separately.

[int3]

file naming consistency nits:

x86_64-objcstubs.s -> x86-64-objc-stubs.s
arm64-objcstubs.s -> arm64-objc-stubs.s
methname.s -> objc-methname.s
selrefs.s -> objc-selrefs.s

lld/MachO/Arch/ARM64.cpp

114–116

What's the purpose of these brk #0 instructions? Also, any idea why they are rendered as brk #0x1 in the arm64-objcstubs.s test?

159

are you planning to implement this in the near future? otherwise I think it's cleaner to drop it for now

lld/MachO/Arch/X86_64.cpp

192

consistency nit

lld/MachO/Driver.cpp

789–798

the switch statement seems a bit overkill given that we know arg can only take two values... how about just if (arg->getOption().getID() == OPT_objc_stubs_small) { ... }?

1174

is this necessary? isn't marking the pieces as live above sufficient?

lld/MachO/InputSection.h

197

use member initialization list

lld/MachO/SyntheticSections.cpp

732

could you dig into this? I would really prefer we avoid copying the string if possible

lld/MachO/SyntheticSections.h

313

Could we have a block comment here explaining how ObjC stubs are laid out? (Similar to what we have for StubsSection.)

323

could make this a StringLiteral (then we wouldn't need a separate symbolPrefixLength either)

568

we should be returning a const ref instead of a copy... but I think it would be even cleaner to just expose a getStringOffset(StringRef) method instead of the whole map interface. I think having the 31-bit hashing logic encapsulated within DeduplicatedCStringSection is also cleaner

lld/MachO/Writer.cpp

1219–1221

nit: braces unnecessary

lld/test/MachO/arm64-objcstubs.s

36 ↗

(On Diff #450173)

Should we have a CHECK-EMPTY here just to verify that _objc_msgSend$bar isn't generated? Otherwise I'm not sure what the purposes of selref2 is :)

lld/test/MachO/methname.s

30–34 ↗

(On Diff #450173)

can we spell out "in" -> "internal"? I spent a while trying to figure out what "inc str" meant heh

also I don't think the _some_cstr and _some_methname symbols are needed

lld/test/MachO/x86_64-objcstubs.s

18 ↗

(On Diff #450173)

just curious -- does clang -S normally generate regular symbols for strings in __objc_methname? AFAIK it usually uses private LFoo symbols for __cstring

[keith]

Address feedback

lld/MachO/Arch/ARM64.cpp

114–116

The comment here was outdated, fixed to show 0x1. I'm not sure why there are extras here, maybe some alignment concern? I wasn't really sure if the right path is to copy ld64, or just ignore unless we hit an issue. I haven't tested without them.

lld/MachO/Driver.cpp

1174

Without it I hit this assert https://github.com/llvm/llvm-project/blob/1b349bdaaa540e97d90318c3706527f6ca084987/lld/MachO/InputSection.cpp#L221 when using -dead_strip, the entire section being alive or not doesn't include the strings being alive

lld/MachO/SyntheticSections.cpp

732

I pushed a new option here which I believe avoids the copies. The core issue is that here https://github.com/llvm/llvm-project/blob/1b349bdaaa540e97d90318c3706527f6ca084987/lld/MachO/InputSection.h#L206-L212 we manually construct a StringRef with the actual data, and with the length of the actual data + 1, since pieces[i + 1].inSecOff is after the null terminator. But any other StringRef initialization, like this one https://github.com/llvm/llvm-project/blob/1b349bdaaa540e97d90318c3706527f6ca084987/lld/MachO/InputFiles.cpp#L943 goes through an initializer that computes the length, which naturally excludes the null terminator https://github.com/llvm/llvm-project/blob/1b349bdaaa540e97d90318c3706527f6ca084987/llvm/include/llvm/ADT/StringRef.h#L83-L85

I'm now mirroring this StringRef initialization, but maybe we should correct that string length off by 1 instead?

lld/test/MachO/x86_64-objcstubs.s

18 ↗

(On Diff #450173)

Here's a snippet:

	.section	__TEXT,__objc_methname,cstring_literals
l_OBJC_METH_VAR_NAME_:                  ; @OBJC_METH_VAR_NAME_
	.asciz	"foo"

Then they reference this from __objc_const:

	.section	__DATA,__objc_const
	.p2align	3                               ; @"_OBJC_$_INSTANCE_METHODS_Foo"
__OBJC_$_INSTANCE_METHODS_Foo:
	.long	24                              ; 0x18
	.long	3                               ; 0x3
	.quad	l_OBJC_METH_VAR_NAME_
	.quad	l_OBJC_METH_VAR_TYPE_
	.quad	"-[Foo foo]"

I added a prefix to these to be more clear

[int3]

lgtm, thanks!

lld/MachO/Arch/ARM64.cpp

114–116

ah gotcha. yeah let's just emulate ld64

lld/MachO/SyntheticSections.cpp

726

how about asserting that the symbol name startswith() the symbol prefix here, just for clarity?

732

ooh. Yeah we should fix that off-by-one. I'm fine if you want to do it in a separate commit though

1638

lld/test/MachO/arm64-objc-stubs.s

41–44

make these symbols private lselref*s too?

[keith]

Small feedback improvements

[int3]

lld/MachO/SyntheticSections.cpp

732

fix is here: D133728: [lld-macho][nfci] Don't include null terminator in StringRefs

[int3]

lld/test/MachO/objc-selrefs.s

17

@keith I tried running this test using ld64 (ld64-764 from XCode 14) instead of LLD and it complained about _objc_msgSend$foo being undefined + it did not recognize -objc_stubs_fast. Am I using the wrong version or something?

[keith]

The version 764 is from Xcode 13:

% xcodebuild -version
Xcode 14.0
Build version 14A309
% ld -v
@(#)PROGRAM:ld  PROJECT:ld64-819.6
BUILD 14:58:44 Aug  5 2022
configured to support archs: armv6 armv7 armv7s arm64 arm64e arm64_32 i386 x86_64 x86_64h armv6m armv7k armv7m armv7em
LTO support using: LLVM version 14.0.0, (clang-1400.0.29.102) (static support for 29, runtime is 29)
TAPI support using: Apple TAPI version 14.0.0 (tapi-1400.0.11)

% DEVELOPER_DIR=/Applications/Xcode-13.4.0-RC1.app ld -v
@(#)PROGRAM:ld  PROJECT:ld64-764

lld/MachO/Arch/ARM.cpp

struct ARM : TargetInfo {
   void relocateOne(uint8_t *loc, const Reloc &, uint64_t va,
                    uint64_t pc) const override;
 
   void writeStub(uint8_t *buf, const Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const Symbol &,
                             uint64_t entryAddr) const override;
 
+  void writeObjCMsgSendStub(uint8_t *buf, Symbol *sym, uint64_t stubsAddr,
+                            uint64_t stubOffset, uint64_t selrefsVA,
+                            uint64_t selectorIndex, uint64_t gotAddr,
+                            uint64_t msgSendIndex) const override;
+
   void relaxGotLoad(uint8_t *loc, uint8_t type) const override;
   uint64_t getPageSize() const override { return 4 * 1024; }
 
   void handleDtraceReloc(const Symbol *sym, const Reloc &r,
                          uint8_t *loc) const override;
 };
 } // namespace
 
void ARM::writeStubHelperHeader(uint8_t *buf) const {
   fatal("TODO: implement this");
 }
 
 void ARM::writeStubHelperEntry(uint8_t *buf, const Symbol &sym,
                                uint64_t entryAddr) const {
   fatal("TODO: implement this");
 }
 
+void ARM::writeObjCMsgSendStub(uint8_t *buf, Symbol *sym, uint64_t stubsAddr,
+                               uint64_t stubOffset, uint64_t selrefsVA,
+                               uint64_t selectorIndex, uint64_t gotAddr,
+                               uint64_t msgSendIndex) const {
+  fatal("TODO: implement this");
+}
+
 void ARM::relaxGotLoad(uint8_t *loc, uint8_t type) const {
   fatal("TODO: implement this");
 }
 
 ARM::ARM(uint32_t cpuSubtype) : TargetInfo(ILP32()) {
   cpuType = CPU_TYPE_ARM;
   this->cpuSubtype = cpuSubtype;
 

lld/MachO/Arch/ARM64.cpp

 namespace {
 
 struct ARM64 : ARM64Common {
   ARM64();
   void writeStub(uint8_t *buf, const Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const Symbol &,
                             uint64_t entryAddr) const override;
+
+  void writeObjCMsgSendStub(uint8_t *buf, Symbol *sym, uint64_t stubsAddr,
+                            uint64_t stubOffset, uint64_t selrefsVA,
+                            uint64_t selectorIndex, uint64_t gotAddr,
+                            uint64_t msgSendIndex) const override;
   void populateThunk(InputSection *thunk, Symbol *funcSym) override;
   void applyOptimizationHints(uint8_t *, const ConcatInputSection *,
                               ArrayRef<uint64_t>) const override;
 };
 
 } // namespace
 
 // Random notes on reloc types:
static constexpr uint32_t stubHelperEntryCode[] = {
     0x00000000, // 08: l0: .long 0
 };
 
 void ARM64::writeStubHelperEntry(uint8_t *buf8, const Symbol &sym,
                                  uint64_t entryVA) const {
   ::writeStubHelperEntry(buf8, stubHelperEntryCode, sym, entryVA);
 }
 
+static constexpr uint32_t objcStubsFastCode[] = {
+    0x90000001, // adrp  x1, __objc_selrefs@page
+    0xf9400021, // ldr   x1, [x1, @selector("foo")@pageoff]
+    0x90000010, // adrp  x16, _got@page
+    0xf9400210, // ldr   x16, [x16, _objc_msgSend@pageoff]
+    0xd61f0200, // br    x16
+    0xd4200020, // brk   #0x1
+    0xd4200020, // brk   #0x1
+    0xd4200020, // brk   #0x1
+};
+
+void ARM64::writeObjCMsgSendStub(uint8_t *buf, Symbol *sym, uint64_t stubsAddr,
+                                 uint64_t stubOffset, uint64_t selrefsVA,
+                                 uint64_t selectorIndex, uint64_t gotAddr,
+                                 uint64_t msgSendIndex) const {
+  ::writeObjCMsgSendStub<LP64>(buf, objcStubsFastCode, sym, stubsAddr,
+                               stubOffset, selrefsVA, selectorIndex, gotAddr,
+                               msgSendIndex);
+}
+
 // A thunk is the relaxed variation of stubCode. We don't need the
 // extra indirection through a lazy pointer because the target address
 // is known at link time.
 static constexpr uint32_t thunkCode[] = {
     0x90000010, // 00: adrp  x16, <thunk.ptr>@page
     0x91000210, // 04: add   x16, [x16,<thunk.ptr>@pageoff]
     0xd61f0200, // 08: br    x16
 };

 
 ARM64::ARM64() : ARM64Common(LP64()) {
   cpuType = CPU_TYPE_ARM64;
   cpuSubtype = CPU_SUBTYPE_ARM64_ALL;
 
   stubSize = sizeof(stubCode);
   thunkSize = sizeof(thunkCode);
 
+  objcStubsFastSize = sizeof(objcStubsFastCode);
+  objcStubsAlignment = 32;
+
   // Branch immediate is two's complement 26 bits, which is implicitly
   // multiplied by 4 (since all functions are 4-aligned: The branch range
   // is -4*(2**(26-1))..4*(2**(26-1) - 1).
   backwardBranchRange = 128 * 1024 * 1024;
   forwardBranchRange = backwardBranchRange - 4;
 
   modeDwarfEncoding = UNWIND_ARM64_MODE_DWARF;
   subtractorRelocType = ARM64_RELOC_SUBTRACTOR;

lld/MachO/Arch/ARM64Common.h

inline void writeStubHelperEntry(uint8_t *buf8,
   auto pcVA = [entryVA](int i) { return entryVA + i * sizeof(uint32_t); };
   uint64_t stubHelperHeaderVA = in.stubHelper->addr;
   buf32[0] = stubHelperEntryCode[0];
   encodeBranch26(&buf32[1], {&sym, "stub helper"}, stubHelperEntryCode[1],
                  stubHelperHeaderVA - pcVA(1));
   buf32[2] = sym.lazyBindOffset;
 }
 
+template <class LP>
+inline void
+writeObjCMsgSendStub(uint8_t *buf, const uint32_t objcStubsFastCode[8],
+                     Symbol *sym, uint64_t stubsAddr, uint64_t stubOffset,
+                     uint64_t selrefsVA, uint64_t selectorIndex,
+                     uint64_t gotAddr, uint64_t msgSendIndex) {
+  SymbolDiagnostic d = {sym, sym->getName()};
+  auto *buf32 = reinterpret_cast<uint32_t *>(buf);
+
+  auto pcPageBits = [stubsAddr, stubOffset](int i) {
+    return pageBits(stubsAddr + stubOffset + i * sizeof(uint32_t));
+  };
+
+  uint64_t selectorOffset = selectorIndex * LP::wordSize;
+  encodePage21(&buf32[0], d, objcStubsFastCode[0],
+               pageBits(selrefsVA + selectorOffset) - pcPageBits(0));
+  encodePageOff12(&buf32[1], objcStubsFastCode[1], selrefsVA + selectorOffset);
+  encodePage21(&buf32[2], d, objcStubsFastCode[2],
+               pageBits(gotAddr) - pcPageBits(2));
+  encodePage21(&buf32[3], d, objcStubsFastCode[3], msgSendIndex * LP::wordSize);
+  buf32[4] = objcStubsFastCode[4];
+  buf32[5] = objcStubsFastCode[5];
+  buf32[6] = objcStubsFastCode[6];
+  buf32[7] = objcStubsFastCode[7];
+}
+
 } // namespace lld::macho
 
 #endif

lld/MachO/Arch/ARM64_32.cpp

 namespace {
 
 struct ARM64_32 : ARM64Common {
   ARM64_32();
   void writeStub(uint8_t *buf, const Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const Symbol &,
                             uint64_t entryAddr) const override;
+  void writeObjCMsgSendStub(uint8_t *buf, Symbol *sym, uint64_t stubsAddr,
+                            uint64_t stubOffset, uint64_t selrefsVA,
+                            uint64_t selectorIndex, uint64_t gotAddr,
+                            uint64_t msgSendIndex) const override;
 };
 
 } // namespace
 
 // These are very similar to ARM64's relocation attributes, except that we don't
 // have the BYTE8 flag set.
 static constexpr std::array<RelocAttrs, 11> relocAttrsArray{{
 #define B(x) RelocAttrBits::x
static constexpr uint32_t stubHelperEntryCode[] = {
     0x00000000, // 08: l0: .long 0
 };
 
 void ARM64_32::writeStubHelperEntry(uint8_t *buf8, const Symbol &sym,
                                     uint64_t entryVA) const {
   ::writeStubHelperEntry(buf8, stubHelperEntryCode, sym, entryVA);
 }
 
+void ARM64_32::writeObjCMsgSendStub(uint8_t *buf, Symbol *sym,
+                                    uint64_t stubsAddr, uint64_t stubOffset,
+                                    uint64_t selrefsVA, uint64_t selectorIndex,
+                                    uint64_t gotAddr,
+                                    uint64_t msgSendIndex) const {
+  fatal("TODO: implement this");
+}
+
 ARM64_32::ARM64_32() : ARM64Common(ILP32()) {
   cpuType = CPU_TYPE_ARM64_32;
   cpuSubtype = CPU_SUBTYPE_ARM64_V8;
 
   modeDwarfEncoding = 0x04000000;              // UNWIND_ARM_MODE_DWARF
   subtractorRelocType = GENERIC_RELOC_INVALID; // FIXME
   unsignedRelocType = GENERIC_RELOC_INVALID;   // FIXME
 

lld/MachO/Arch/X86_64.cpp

struct X86_64 : TargetInfo {
   void relocateOne(uint8_t *loc, const Reloc &, uint64_t va,
                    uint64_t relocVA) const override;
 
   void writeStub(uint8_t *buf, const Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const Symbol &,
                             uint64_t entryAddr) const override;
 
+  void writeObjCMsgSendStub(uint8_t *buf, Symbol *sym, uint64_t stubsAddr,
+                            uint64_t stubOffset, uint64_t selrefsVA,
+                            uint64_t selectorIndex, uint64_t gotAddr,
+                            uint64_t msgSendIndex) const override;
+
   void relaxGotLoad(uint8_t *loc, uint8_t type) const override;
   uint64_t getPageSize() const override { return 4 * 1024; }
 
   void handleDtraceReloc(const Symbol *sym, const Reloc &r,
                          uint8_t *loc) const override;
 };
 } // namespace
 

 void X86_64::writeStubHelperEntry(uint8_t *buf, const Symbol &sym,
                                   uint64_t entryAddr) const {
   memcpy(buf, stubHelperEntry, sizeof(stubHelperEntry));
   write32le(buf + 1, sym.lazyBindOffset);
   writeRipRelative({&sym, "stub helper"}, buf, entryAddr,
                    sizeof(stubHelperEntry), in.stubHelper->addr);
 }
 
+static constexpr uint8_t objcStubsFastCode[] = {
+    0x48, 0x8b, 0x35, 0, 0, 0, 0, // 0x0: movq selrefs@selector(%rip), %rsi
+    0xff, 0x25, 0,    0, 0, 0,    // 0x7: jmpq *_objc_msgSend@GOT(%rip)
+};
+
+void X86_64::writeObjCMsgSendStub(uint8_t *buf, Symbol *sym, uint64_t stubsAddr,
+                                  uint64_t stubOffset, uint64_t selrefsVA,
+                                  uint64_t selectorIndex, uint64_t gotAddr,
+                                  uint64_t msgSendIndex) const {
+  memcpy(buf, objcStubsFastCode, sizeof(objcStubsFastCode));
+  SymbolDiagnostic d = {sym, sym->getName()};
+  uint64_t stubAddr = stubsAddr + stubOffset;
+  writeRipRelative(d, buf, stubAddr, 7,
+                   selrefsVA + selectorIndex * LP64::wordSize);
+  writeRipRelative(d, buf, stubAddr, 0xd,
+                   gotAddr + msgSendIndex * LP64::wordSize);
+}
+
 void X86_64::relaxGotLoad(uint8_t *loc, uint8_t type) const {
   // Convert MOVQ to LEAQ
   if (loc[-2] != 0x8b)
     error(getRelocAttrs(type).name + " reloc requires MOVQ instruction");
   loc[-2] = 0x8d;
 }
 
 X86_64::X86_64() : TargetInfo(LP64()) {
   cpuType = CPU_TYPE_X86_64;
   cpuSubtype = CPU_SUBTYPE_X86_64_ALL;
 
   modeDwarfEncoding = UNWIND_X86_MODE_DWARF;
   subtractorRelocType = X86_64_RELOC_SUBTRACTOR;
   unsignedRelocType = X86_64_RELOC_UNSIGNED;
 
   stubSize = sizeof(stub);
   stubHelperHeaderSize = sizeof(stubHelperHeader);
   stubHelperEntrySize = sizeof(stubHelperEntry);
 
+  objcStubsFastSize = sizeof(objcStubsFastCode);
+  objcStubsAlignment = 1;
+
   relocAttrs = {relocAttrsArray.data(), relocAttrsArray.size()};
 }
 
 TargetInfo *macho::createX86_64TargetInfo() {
   static X86_64 t;
   return &t;
 }
 

lld/MachO/Config.h

 
 enum class ICFLevel {
   unknown,
   none,
   safe,
   all,
 };
 
+enum class ObjCStubsMode {
+  fast,
+  small,
+};
+
 struct SectionAlign {
   llvm::StringRef segName;
   llvm::StringRef sectName;
   uint32_t align;
 };
 
 struct SegmentProtection {
   llvm::StringRef name;
struct Configuration {
   bool deadStrip = false;
   bool errorForArchMismatch = false;
   PlatformInfo platformInfo;
   llvm::Optional<PlatformInfo> secondaryPlatformInfo;
   NamespaceKind namespaceKind = NamespaceKind::twolevel;
   UndefinedSymbolTreatment undefinedSymbolTreatment =
       UndefinedSymbolTreatment::error;
   ICFLevel icfLevel = ICFLevel::none;
+  ObjCStubsMode objcStubsMode = ObjCStubsMode::fast;
   llvm::MachO::HeaderFileType outputType;
   std::vector<llvm::StringRef> systemLibraryRoots;
   std::vector<llvm::StringRef> librarySearchPaths;
   std::vector<llvm::StringRef> frameworkSearchPaths;
   llvm::SmallVector<llvm::StringRef, 0> runtimePaths;
   std::vector<std::string> astPaths;
   std::vector<Symbol *> explicitUndefineds;
   llvm::StringSet<> explicitDynamicLookups;

lld/MachO/Driver.cpp

static ICFLevel getICFLevel(const ArgList &args) {
   if (icfLevel == ICFLevel::unknown) {
     warn(Twine("unknown --icf=OPTION `") + icfLevelStr +
          "', defaulting to `none'");
     icfLevel = ICFLevel::none;
   }
   return icfLevel;
 }
 
+static ObjCStubsMode getObjCStubsMode(const ArgList &args) {
+  const Arg *arg = args.getLastArg(OPT_objc_stubs_fast, OPT_objc_stubs_small);
+  if (!arg)
+    return ObjCStubsMode::fast;
+
+  if (arg->getOption().getID() == OPT_objc_stubs_small)
+    warn("-objc_stubs_small is not yet implemented, defaulting to "
+         "-objc_stubs_fast");
+  return ObjCStubsMode::fast;
+}
+
 static void warnIfDeprecatedOption(const Option &opt) {
   if (!opt.getGroup().isValid())
     return;
   if (opt.getGroup().getID() == OPT_grp_deprecated) {
     warn("Option `" + opt.getPrefixedName() + "' is deprecated in ld64:");
     warn(opt.getHelpText());
   }
 }
 
 static void warnIfUnimplementedOption(const Option &opt) {
   if (!opt.getGroup().isValid() || !opt.hasFlag(DriverFlag::HelpHidden))
     return;
for (const Section *section : file->sections) {
             continue;
           isec->outSecOff = inputOrder++;
           if (!osec)
             osec = ConcatOutputSection::getOrCreateForInput(isec);
           isec->parent = osec;
           inputSections.push_back(isec);
         } else if (auto *isec =
                        dyn_cast<CStringInputSection>(subsection.isec)) {
+          if (isec->getName() == section_names::objcMethname) {
+            if (in.objcMethnameSection->inputOrder == UnspecifiedInputOrder)
+              in.objcMethnameSection->inputOrder = inputOrder++;
+            in.objcMethnameSection->addInput(isec);
+          } else {
             if (in.cStringSection->inputOrder == UnspecifiedInputOrder)
               in.cStringSection->inputOrder = inputOrder++;
             in.cStringSection->addInput(isec);
+          }
         } else if (auto *isec =
                        dyn_cast<WordLiteralInputSection>(subsection.isec)) {
           if (in.wordLiteralSection->inputOrder == UnspecifiedInputOrder)
             in.wordLiteralSection->inputOrder = inputOrder++;
           in.wordLiteralSection->addInput(isec);
         } else {
           llvm_unreachable("unexpected input section kind");
         }
       }
     }
     if (!file->objCImageInfo.empty())
       in.objCImageInfo->addFile(file);
   }
   assert(inputOrder <= UnspecifiedInputOrder);
 }
 
 static void foldIdenticalLiterals() {
   TimeTraceScope timeScope("Fold identical literals");
   // We always create a cStringSection, regardless of whether dedupLiterals is
   // true. If it isn't, we simply create a non-deduplicating CStringSection.
   // Either way, we must unconditionally finalize it here.
   in.cStringSection->finalizeContents();
+  in.objcMethnameSection->finalizeContents();
   if (in.wordLiteralSection)
     in.wordLiteralSection->finalizeContents();
 }
 
+static void addSynthenticMethnames() {
+  std::string &data = *make<std::string>();
+  llvm::raw_string_ostream os(data);
+  const int prefixLength = ObjCStubsSection::symbolPrefix.size();
+  for (Symbol *sym : symtab->getSymbols())
+    if (const auto *undefined = dyn_cast<Undefined>(sym))
+      if (sym->getName().startswith(ObjCStubsSection::symbolPrefix))
+        os << sym->getName().drop_front(prefixLength) << '\0';
+
+  if (data.empty())
+    return;
+
+  const auto *buf = reinterpret_cast<const uint8_t *>(data.c_str());
+  Section &section = *make<Section>(/*file=*/nullptr, segment_names::text,
+                                    section_names::objcMethname,
+                                    S_CSTRING_LITERALS, /*addr=*/0);
+
+  auto *isec =
+      make<CStringInputSection>(section, ArrayRef<uint8_t>{buf, data.size()},
+                                /*align=*/1, /*dedupLiterals=*/true);
+  isec->splitIntoPieces();
+  for (auto &piece : isec->pieces)
+    piece.live = true;
+  section.subsections.push_back({0, isec});
+  in.objcMethnameSection->addInput(isec);
+  in.objcMethnameSection->isec->markLive(0);
+}
+
 static void referenceStubBinder() {
   bool needsStubHelper = config->outputType == MH_DYLIB ||
                          config->outputType == MH_EXECUTE ||
                          config->outputType == MH_BUNDLE;
   if (!needsStubHelper || !symtab->find("dyld_stub_binder"))
     return;
 
   // dyld_stub_binder is used by dyld to resolve lazy bindings. This code here
bool macho::link(ArrayRef<const char *> argsArr, llvm::raw_ostream &stdoutOS,
   config->warnDylibInstallName = args.hasFlag(
       OPT_warn_dylib_install_name, OPT_no_warn_dylib_install_name, false);
   config->ignoreOptimizationHints = args.hasArg(OPT_ignore_optimization_hints);
   config->callGraphProfileSort = args.hasFlag(
       OPT_call_graph_profile_sort, OPT_no_call_graph_profile_sort, true);
   config->printSymbolOrder = args.getLastArgValue(OPT_print_symbol_order);
   config->forceExactCpuSubtypeMatch =
       getenv("LD_DYLIB_CPU_SUBTYPES_MUST_MATCH");
+  config->objcStubsMode = getObjCStubsMode(args);
 
   for (const Arg *arg : args.filtered(OPT_alias)) {
     config->aliasedSymbols.push_back(
         std::make_pair(arg->getValue(0), arg->getValue(1)));
   }
 
   // FIXME: Add a commandline flag for this too.
   config->zeroModTime = getenv("ZERO_AR_DATE");
if (const Arg *arg = args.getLastArg(OPT_mcpu))
       parseClangOption(saver().save("-mcpu=" + StringRef(arg->getValue())),
                        arg->getSpelling());
 
     for (const Arg *arg : args.filtered(OPT_mllvm))
       parseClangOption(arg->getValue(), arg->getSpelling());
 
     createSyntheticSections();
     createSyntheticSymbols();
+    addSynthenticMethnames();
 
     createAliases();
     // If we are in "explicit exports" mode, hide everything that isn't
     // explicitly exported. Do this before running LTO so that LTO can better
     // optimize.
     handleExplicitExports();
     // LTO may emit a non-hidden (extern) object file symbol even if the
     // corresponding bitcode symbol is hidden. In particular, this happens for

lld/MachO/InputFiles.cpp

if (sectionType(sec.flags) == S_CSTRING_LITERALS ||
       if (sec.nreloc && config->dedupLiterals)
         fatal(toString(this) + " contains relocations in " + sec.segname + "," +
               sec.sectname +
               ", so LLD cannot deduplicate literals. Try re-running without "
               "--deduplicate-literals.");
 
       InputSection *isec;
       if (sectionType(sec.flags) == S_CSTRING_LITERALS) {
-        isec = make<CStringInputSection>(section, data, align);
+        isec = make<CStringInputSection>(section, data, align,
+                                         /*dedupLiterals=*/name ==
+                                                 section_names::objcMethname ||
+                                             config->dedupLiterals);
         // FIXME: parallelize this?
         cast<CStringInputSection>(isec)->splitIntoPieces();
       } else {
         isec = make<WordLiteralInputSection>(section, data, align);
       }
       section.subsections.push_back({0, isec});
     } else if (auto recordSize = getRecordSize(segname, name)) {
       splitRecords(*recordSize);

lld/MachO/InputSection.h

 // NOTE: One significant difference between LLD and ld64 is that we merge all
 // cstring literals, even those referenced directly by non-private symbols.
 // ld64 is more conservative and does not do that. This was mostly done for
 // implementation simplicity; if we find programs that need the more
 // conservative behavior we can certainly implement that.
 class CStringInputSection final : public InputSection {
 public:
   CStringInputSection(const Section &section, ArrayRef<uint8_t> data,
-                      uint32_t align)
-      : InputSection(CStringLiteralKind, section, data, align) {}
+                      uint32_t align, bool dedupLiterals)
+      : InputSection(CStringLiteralKind, section, data, align),
+        deduplicateLiterals(dedupLiterals) {}
+
   uint64_t getOffset(uint64_t off) const override;
   bool isLive(uint64_t off) const override { return getStringPiece(off).live; }
   void markLive(uint64_t off) override { getStringPiece(off).live = true; }
   // Find the StringPiece that contains this offset.
   StringPiece &getStringPiece(uint64_t off);
   const StringPiece &getStringPiece(uint64_t off) const;
   // Split at each null byte.
   void splitIntoPieces();
 
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   StringRef getStringRef(size_t i) const {
     size_t begin = pieces[i].inSecOff;
     size_t end =
         (pieces.size() - 1 == i) ? data.size() : pieces[i + 1].inSecOff;
     return toStringRef(data.slice(begin, end - begin));
   }
 
   // Returns i'th piece as a CachedHashStringRef. This function is very hot when
   // string merging is enabled, so we want to inline.
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   llvm::CachedHashStringRef getCachedHashStringRef(size_t i) const {
-    assert(config->dedupLiterals);
+    assert(deduplicateLiterals);
     return {getStringRef(i), pieces[i].hash};
   }
 
   static bool classof(const InputSection *isec) {
     return isec->kind() == CStringLiteralKind;
   }
 
+  bool deduplicateLiterals = false;
   std::vector<StringPiece> pieces;
 };
 
 class WordLiteralInputSection final : public InputSection {
 public:
   WordLiteralInputSection(const Section &section, ArrayRef<uint8_t> data,
                           uint32_t align);
   uint64_t getOffset(uint64_t off) const override;

 constexpr const char moduleInitFunc[] = "__mod_init_func";
 constexpr const char moduleTermFunc[] = "__mod_term_func";
 constexpr const char nonLazySymbolPtr[] = "__nl_symbol_ptr";
 constexpr const char objcCatList[] = "__objc_catlist";
 constexpr const char objcClassList[] = "__objc_classlist";
 constexpr const char objcClassRefs[] = "__objc_classrefs";
 constexpr const char objcConst[] = "__objc_const";
 constexpr const char objCImageInfo[] = "__objc_imageinfo";
+constexpr const char objcStubs[] = "__objc_stubs";
+constexpr const char objcSelrefs[] = "__objc_selrefs";
+constexpr const char objcMethname[] = "__objc_methname";
 constexpr const char objcNonLazyCatList[] = "__objc_nlcatlist";
 constexpr const char objcNonLazyClassList[] = "__objc_nlclslist";
 constexpr const char objcProtoList[] = "__objc_protolist";
 constexpr const char pageZero[] = "__pagezero";
 constexpr const char pointers[] = "__pointers";
 constexpr const char rebase[] = "__rebase";
 constexpr const char staticInit[] = "__StaticInit";
 constexpr const char stringTable[] = "__string_table";

lld/MachO/InputSection.cpp

 void CStringInputSection::splitIntoPieces() {
   size_t off = 0;
   StringRef s = toStringRef(data);
   while (!s.empty()) {
     size_t end = s.find(0);
     if (end == StringRef::npos)
       fatal(getLocation(off) + ": string is not null terminated");
     size_t size = end + 1;
-    uint32_t hash = config->dedupLiterals ? xxHash64(s.substr(0, size)) : 0;
+    uint32_t hash = deduplicateLiterals ? xxHash64(s.substr(0, size)) : 0;
     pieces.emplace_back(off, hash);
     s = s.substr(size);
     off += size;
   }
 }
 
 StringPiece &CStringInputSection::getStringPiece(uint64_t off) {
   if (off >= data.size())

lld/MachO/Options.td

def mllvm : Separate<["-"], "mllvm">,
     HelpText<"Options to pass to LLVM">,
     Group<grp_rare>;
 def mcpu : Separate<["-"], "mcpu">,
     HelpText<"Processor family target for LTO code generation">,
     Group<grp_rare>;
 def no_dtrace_dof : Flag<["-"], "no_dtrace_dof">,
     HelpText<"Disable dtrace-dof processing (default).">,
     Group<grp_rare>;
+def objc_stubs_fast : Flag<["-"], "objc_stubs_fast">,
+    HelpText<"Produce larger stubs for Objective-C method calls with fewer jumps (default).">,
+    Group<grp_rare>;
+def objc_stubs_small : Flag<["-"], "objc_stubs_small">,
+    HelpText<"Produce smaller stubs for Objective-C method calls with more jumps.">,
+    Group<grp_rare>;
 
 def grp_deprecated : OptionGroup<"deprecated">, HelpText<"DEPRECATED">;
 
 def lazy_framework : Separate<["-"], "lazy_framework">,
     MetaVarName<"<name>">,
     HelpText<"This option is deprecated and is now an alias for -framework.">,
     Flags<[HelpHidden]>,
     Group<grp_deprecated>;

lld/MachO/SyntheticSections.h

public:
   void writeTo(uint8_t *buf) const override;
 
   void setup();
 
   DylibSymbol *stubBinder = nullptr;
   Defined *dyldPrivate = nullptr;
 };
 
+// Objective-C stubs are hoisted objc_msgSend calls per selector called in the
+// program. Apple Clang produces undefined symbols to each stub, such as
+// '_objc_msgSend$foo', which are then synthesized by the linker. The stubs
+// load the particular selector 'foo' from __objc_selrefs, setting it to the
+// first argument of the objc_msgSend call, and then jumps to objc_msgSend. The
+// actual stub contents are mirrored from ld64.
+class ObjCStubsSection final : public SyntheticSection {
+public:
+  ObjCStubsSection();
+  void addEntry(Symbol *sym);
+  uint64_t getSize() const override;
+  bool isNeeded() const override { return !symbols.empty(); }
+  void finalize() override { isec->isFinal = true; }
+  void writeTo(uint8_t *buf) const override;
+  void setup();
+
+  static constexpr llvm::StringLiteral symbolPrefix = "_objc_msgSend$";
+
+private:
+  std::vector<Defined *> symbols;
+  std::vector<uint32_t> offsets;
+  int objcMsgSendGotIndex = 0;
+};
+
 // Note that this section may also be targeted by non-lazy bindings. In
 // particular, this happens when branch relocations target weak symbols.
 class LazyPointerSection final : public SyntheticSection {
 public:
   LazyPointerSection();
   uint64_t getSize() const override;
   bool isNeeded() const override;
   void writeTo(uint8_t *buf) const override;

 
 private:
   llvm::SmallString<261> xarPath;
   uint64_t xarSize;
 };
 
 class CStringSection : public SyntheticSection {
 public:
-  CStringSection();
+  CStringSection(const char *name);
   void addInput(CStringInputSection *);
   uint64_t getSize() const override { return size; }
   virtual void finalizeContents();
   bool isNeeded() const override { return !inputs.empty(); }
   void writeTo(uint8_t *buf) const override;
 
   std::vector<CStringInputSection *> inputs;
 
 private:
   uint64_t size;
 };
 
 class DeduplicatedCStringSection final : public CStringSection {
 public:
+  DeduplicatedCStringSection(const char *name) : CStringSection(name){};
   uint64_t getSize() const override { return size; }
   void finalizeContents() override;
   void writeTo(uint8_t *buf) const override;
 
-private:
   struct StringOffset {
     uint8_t trailingZeros;
     uint64_t outSecOff = UINT64_MAX;
 
     explicit StringOffset(uint8_t zeros) : trailingZeros(zeros) {}
   };
+
+  StringOffset getStringOffset(StringRef str) const;
+
+private:
   llvm::DenseMap<llvm::CachedHashStringRef, StringOffset> stringOffsetMap;
   size_t size = 0;
 };
 
 /*
  * This section contains deduplicated literal values. The 16-byte values are
  * laid out first, followed by the 8- and then the 4-byte ones.
  */
private:
   static ImageInfo parseImageInfo(const InputFile *);
   std::vector<const InputFile *> files; // files with image info
 };
 
 struct InStruct {
   const uint8_t *bufferStart = nullptr;
   MachHeaderSection *header = nullptr;
   CStringSection *cStringSection = nullptr;
+  DeduplicatedCStringSection *objcMethnameSection = nullptr;
   WordLiteralSection *wordLiteralSection = nullptr;
   RebaseSection *rebase = nullptr;
   BindingSection *binding = nullptr;
   WeakBindingSection *weakBinding = nullptr;
   LazyBindingSection *lazyBinding = nullptr;
   ExportSection *exports = nullptr;
   GotSection *got = nullptr;
   TlvPointerSection *tlvPointers = nullptr;
   LazyPointerSection *lazyPointers = nullptr;
   StubsSection *stubs = nullptr;
   StubHelperSection *stubHelper = nullptr;
+  ObjCStubsSection *objcStubs = nullptr;
+  ConcatInputSection *objcSelrefs = nullptr;
   UnwindInfoSection *unwindInfo = nullptr;
   ObjCImageInfoSection *objCImageInfo = nullptr;
   ConcatInputSection *imageLoaderCache = nullptr;
 };
 
 extern InStruct in;
 extern std::vector<SyntheticSection *> syntheticSections;
 
 void createSyntheticSymbols();
 
 } // namespace lld::macho
 
 #endif

lld/MachO/SyntheticSections.cpp

 #include "lld/Common/CommonLinkerContext.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/EndianStream.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/xxhash.h"
 
 #if defined(__APPLE__)
 #include <sys/mman.h>
 
 #define COMMON_DIGEST_FOR_OPENSSL
 #include <CommonCrypto/CommonDigest.h>
 #else
 #include "llvm/Support/SHA256.h"
dyldPrivate =
                     /*isWeakDef=*/false,
                     /*isExternal=*/false, /*isPrivateExtern=*/false,
                     /*includeInSymtab=*/true,
                     /*isThumb=*/false, /*isReferencedDynamically=*/false,
                     /*noDeadStrip=*/false);
   dyldPrivate->used = true;
 }
 
+ObjCStubsSection::ObjCStubsSection()
+    : SyntheticSection(segment_names::text, section_names::objcStubs) {
+  flags = S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
+  align = target->objcStubsAlignment;
+}
+
+void ObjCStubsSection::addEntry(Symbol *sym) {
+  assert(sym->getName().startswith(symbolPrefix) && "not an objc stub");
+  // Ensure our lookup string has the length of the actual string + the null
+  // terminator to mirror
+  StringRef methname =
+      StringRef(sym->getName().data() + symbolPrefix.size(),
+                sym->getName().size() - symbolPrefix.size() + 1);
+  offsets.push_back(
+      in.objcMethnameSection->getStringOffset(methname).outSecOff);
+  Defined *newSym = replaceSymbol<Defined>(
+      sym, sym->getName(), nullptr, isec,
+      /*value=*/symbols.size() * target->objcStubsFastSize,
+      /*size=*/target->objcStubsFastSize,
+      /*isWeakDef=*/false, /*isExternal=*/true, /*isPrivateExtern=*/true,
+      /*includeInSymtab=*/true, /*isThumb=*/false,
+      /*isReferencedDynamically=*/false, /*noDeadStrip=*/false);
+  symbols.push_back(newSym);
+}
+
+void ObjCStubsSection::setup() {
+  Symbol *objcMsgSend = symtab->addUndefined("_objc_msgSend", /*file=*/nullptr,
+                                             /*isWeakRef=*/false);
+  objcMsgSend->used = true;
+  in.got->addEntry(objcMsgSend);
+  assert(objcMsgSend->isInGot());
+  objcMsgSendGotIndex = objcMsgSend->gotIndex;
+
+  size_t size = offsets.size() * target->wordSize;
+  uint8_t *selrefsData = bAlloc().Allocate<uint8_t>(size);
+  for (size_t i = 0, n = offsets.size(); i < n; ++i)
+    write64le(&selrefsData[i * target->wordSize], offsets[i]);
+
+  in.objcSelrefs =
+      makeSyntheticInputSection(segment_names::data, section_names::objcSelrefs,
+                                S_LITERAL_POINTERS | S_ATTR_NO_DEAD_STRIP,
+                                ArrayRef<uint8_t>{selrefsData, size},
+                                /*align=*/target->wordSize);
+  in.objcSelrefs->live = true;
+
+  for (size_t i = 0, n = offsets.size(); i < n; ++i) {
+    in.objcSelrefs->relocs.push_back(
+        {/*type=*/target->unsignedRelocType,
+         /*pcrel=*/false, /*length=*/3,
+         /*offset=*/static_cast<uint32_t>(i * target->wordSize),
+         /*addend=*/offsets[i] * in.objcMethnameSection->align,
+         /*referent=*/in.objcMethnameSection->isec});
+  }
+
+  in.objcSelrefs->parent =
+      ConcatOutputSection::getOrCreateForInput(in.objcSelrefs);
+  inputSections.push_back(in.objcSelrefs);
+  in.objcSelrefs->isFinal = true;
+}
+
+uint64_t ObjCStubsSection::getSize() const {
+  return target->objcStubsFastSize * symbols.size();
+}
+
+void ObjCStubsSection::writeTo(uint8_t *buf) const {
+  assert(in.objcSelrefs->live);
+  assert(in.objcSelrefs->isFinal);
+
+  uint64_t stubOffset = 0;
+  for (size_t i = 0, n = symbols.size(); i < n; ++i) {
+    Defined *sym = symbols[i];
+    target->writeObjCMsgSendStub(buf + stubOffset, sym, in.objcStubs->addr,
+                                 stubOffset, in.objcSelrefs->getVA(), i,
+                                 in.got->addr, objcMsgSendGotIndex);
+    stubOffset += target->objcStubsFastSize;
+  }
+}
+
 LazyPointerSection::LazyPointerSection()
     : SyntheticSection(segment_names::data, section_names::lazySymbolPtr) {
   align = target->wordSize;
   flags = S_LAZY_SYMBOL_POINTERS;
 }
 
 uint64_t LazyPointerSection::getSize() const {
   return in.stubs->getEntries().size() * target->wordSize;
void BitcodeBundleSection::writeTo(uint8_t *buf) const {
   if (ec)
     fatal("failed to map XAR file");
   memcpy(buf, xarMap.const_data(), xarSize);
 
   closeFile(handle);
   remove(xarPath);
 }
 
-CStringSection::CStringSection()
-    : SyntheticSection(segment_names::text, section_names::cString) {
+CStringSection::CStringSection(const char *name)
+    : SyntheticSection(segment_names::text, name) {
   flags = S_CSTRING_LITERALS;
 }
 
 void CStringSection::addInput(CStringInputSection *isec) {
   isec->parent = this;
   inputs.push_back(isec);
   if (isec->align > align)
     align = isec->align;
for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
       auto it = stringOffsetMap.find(s);
       assert(it != stringOffsetMap.end());
       StringOffset &offsetInfo = it->second;
       if (offsetInfo.outSecOff == UINT64_MAX) {
         offsetInfo.outSecOff = alignTo(size, 1ULL << offsetInfo.trailingZeros);
         size = offsetInfo.outSecOff + s.size();
       }
       isec->pieces[i].outSecOff = offsetInfo.outSecOff;
     }
     isec->isFinal = true;
   }
 }
 
 void DeduplicatedCStringSection::writeTo(uint8_t *buf) const {
   for (const auto &p : stringOffsetMap) {
     StringRef data = p.first.val();
     uint64_t off = p.second.outSecOff;
     if (!data.empty())
       memcpy(buf + off, data.data(), data.size());
   }
 }
 
+DeduplicatedCStringSection::StringOffset
+DeduplicatedCStringSection::getStringOffset(StringRef str) const {
+  // StringPiece uses 31 bits to store the hashes, so we replicate that
+  uint32_t hash = xxHash64(str) & 0x7fffffff;
+  auto offset = stringOffsetMap.find(CachedHashStringRef(str, hash));
+  assert(offset != stringOffsetMap.end() &&
+         "Looked-up strings should always exist in section");
+  return offset->second;
+}
+
 // This section is actually emitted as __TEXT,__const by ld64, but clang may
 // emit input sections of that name, and LLD doesn't currently support mixing
 // synthetic and concat-type OutputSections. To work around this, I've given
 // our merged-literals section a different name.
 WordLiteralSection::WordLiteralSection()
     : SyntheticSection(segment_names::text, section_names::literals) {
   align = 16;
 }

lld/MachO/Target.h

public:
 
   // Write code for lazy binding. See the comments on StubsSection for more
   // details.
   virtual void writeStub(uint8_t *buf, const Symbol &) const = 0;
   virtual void writeStubHelperHeader(uint8_t *buf) const = 0;
   virtual void writeStubHelperEntry(uint8_t *buf, const Symbol &,
                                     uint64_t entryAddr) const = 0;
 
+  virtual void writeObjCMsgSendStub(uint8_t *buf, Symbol *sym,
+                                    uint64_t stubsAddr, uint64_t stubOffset,
+                                    uint64_t selrefsVA, uint64_t selectorIndex,
+                                    uint64_t gotAddr,
+                                    uint64_t msgSendIndex) const = 0;
+
   // Symbols may be referenced via either the GOT or the stubs section,
   // depending on the relocation type. prepareSymbolRelocation() will set up the
   // GOT/stubs entries, and resolveSymbolVA() will return the addresses of those
   // entries. resolveSymbolVA() may also relax the target instructions to save
   // on a level of address indirection.
   virtual void relaxGotLoad(uint8_t *loc, uint8_t type) const = 0;
 
   virtual uint64_t getPageSize() const = 0;
public:
   llvm::MachO::CPUType cpuType;
   uint32_t cpuSubtype;
 
   uint64_t pageZeroSize;
   size_t headerSize;
   size_t stubSize;
   size_t stubHelperHeaderSize;
   size_t stubHelperEntrySize;
+  size_t objcStubsFastSize;
+  size_t objcStubsAlignment;
   uint8_t p2WordSize;
   size_t wordSize;
 
   size_t thunkSize = 0;
   uint64_t forwardBranchRange = 0;
   uint64_t backwardBranchRange = 0;
 
   uint32_t modeDwarfEncoding;

lld/MachO/Writer.cpp

if (auto *defined = dyn_cast<Defined>(sym)) {
       if (!defined->isAbsolute() && isCodeSection(defined->isec))
         in.unwindInfo->addSymbol(defined);
     } else if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
       // This branch intentionally doesn't check isLive().
       if (dysym->isDynamicLookup())
         continue;
       dysym->getFile()->refState =
           std::max(dysym->getFile()->refState, dysym->getRefState());
+    } else if (const auto *undefined = dyn_cast<Undefined>(sym)) {
+      if (sym->getName().startswith(ObjCStubsSection::symbolPrefix))
+        in.objcStubs->addEntry(sym);
     }
   }
 
   for (const InputFile *file : inputFiles) {
     if (auto *objFile = dyn_cast<ObjFile>(file))
       for (Symbol *sym : objFile->symbols) {
         if (auto *defined = dyn_cast_or_null<Defined>(sym)) {
           if (!defined->isLive())
template <class LP> void Writer::run() {
   treatSpecialUndefineds();
   if (config->entry && !isa<Undefined>(config->entry))
     prepareBranchTarget(config->entry);
 
   // Canonicalization of all pointers to InputSections should be handled by
   // these two scan* methods. I.e. from this point onward, for all live
   // InputSections, we should have `isec->canonical() == isec`.
   scanSymbols();
+  if (in.objcStubs->isNeeded())
+    in.objcStubs->setup();
   scanRelocations();
 
   // Do not proceed if there was an undefined symbol.
   reportPendingUndefinedSymbols();
   if (errorCount())
     return;
 
   if (in.stubHelper->isNeeded())

 
 template <class LP> void macho::writeResult() { Writer().run<LP>(); }
 
 void macho::resetWriter() { LCDylib::resetInstanceCount(); }
 
 void macho::createSyntheticSections() {
   in.header = make<MachHeaderSection>();
   if (config->dedupLiterals)
-    in.cStringSection = make<DeduplicatedCStringSection>();
+    in.cStringSection =
+        make<DeduplicatedCStringSection>(section_names::cString);
   else
-    in.cStringSection = make<CStringSection>();
+    in.cStringSection = make<CStringSection>(section_names::cString);
+  in.objcMethnameSection =
+      make<DeduplicatedCStringSection>(section_names::objcMethname);
   in.wordLiteralSection =
       config->dedupLiterals ? make<WordLiteralSection>() : nullptr;
   in.rebase = make<RebaseSection>();
   in.binding = make<BindingSection>();
   in.weakBinding = make<WeakBindingSection>();
   in.lazyBinding = make<LazyBindingSection>();
   in.exports = make<ExportSection>();
   in.got = make<GotSection>();
   in.tlvPointers = make<TlvPointerSection>();
   in.lazyPointers = make<LazyPointerSection>();
   in.stubs = make<StubsSection>();
   in.stubHelper = make<StubHelperSection>();
+  in.objcStubs = make<ObjCStubsSection>();
   in.unwindInfo = makeUnwindInfoSection();
   in.objCImageInfo = make<ObjCImageInfoSection>();
 
   // This section contains space for just a single word, and will be used by
   // dyld to cache an address to the image loader it uses.
   uint8_t *arr = bAlloc().Allocate<uint8_t>(target->wordSize);
   memset(arr, 0, target->wordSize);
   in.imageLoaderCache = makeSyntheticInputSection(

lld/test/MachO/arm64-objc-stubs.s

+# REQUIRES: aarch64
+
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %s -o %t.o
+# RUN: %lld -arch arm64 -lSystem -o %t.out %t.o
+# RUN: llvm-otool -vs __TEXT __objc_stubs %t.out | FileCheck %s
+# RUN: %lld -arch arm64 -lSystem -o %t.out %t.o -dead_strip
+# RUN: llvm-otool -vs __TEXT __objc_stubs %t.out | FileCheck %s
+# RUN: %lld -arch arm64 -lSystem -o %t.out %t.o -objc_stubs_fast
+# RUN: llvm-otool -vs __TEXT __objc_stubs %t.out | FileCheck %s
+# RUN: %no-fatal-warnings-lld -arch arm64 -lSystem -o %t.out %t.o -objc_stubs_small 2>&1 | FileCheck %s --check-prefix=WARNING
+# RUN: llvm-otool -vs __TEXT __objc_stubs %t.out | FileCheck %s
+
+# WARNING: warning: -objc_stubs_small is not yet implemented, defaulting to -objc_stubs_fast
+
+# CHECK: Contents of (__TEXT,__objc_stubs) section
+
+# CHECK-NEXT: _objc_msgSend$foo:
+# CHECK-NEXT: adrp    x1, 8 ; 0x100008000
+# CHECK-NEXT: ldr     x1, [x1, #0x10]
+# CHECK-NEXT: adrp    x16, 4 ; 0x100004000
+# CHECK-NEXT: ldr     x16, [x16]
+# CHECK-NEXT: br      x16
+# CHECK-NEXT: brk     #0x1
+# CHECK-NEXT: brk     #0x1
+# CHECK-NEXT: brk     #0x1
+
+# CHECK-NEXT: _objc_msgSend$length:
+# CHECK-NEXT: adrp    x1, 8 ; 0x100008000
+# CHECK-NEXT: ldr     x1, [x1, #0x18]
+# CHECK-NEXT: adrp    x16, 4 ; 0x100004000
+# CHECK-NEXT: ldr     x16, [x16]
+# CHECK-NEXT: br      x16
+# CHECK-NEXT: brk     #0x1
+# CHECK-NEXT: brk     #0x1
+# CHECK-NEXT: brk     #0x1
+
+# CHECK-EMPTY:
+
+.section  __TEXT,__objc_methname,cstring_literals
+lselref1:
+  .asciz  "foo"
+lselref2:
+  .asciz  "bar"
+
+.section  __DATA,__objc_selrefs,literal_pointers,no_dead_strip
+.p2align  3
+.quad lselref1
+.quad lselref2
+
+.text
+.globl _objc_msgSend
+_objc_msgSend:
+  ret
+
+.globl _main
+_main:
+  bl  _objc_msgSend$length
+  bl  _objc_msgSend$foo
+  bl  _objc_msgSend$foo
+  ret

lld/test/MachO/objc-methname.s

+# REQUIRES: aarch64
+# RUN: rm -rf %t; split-file %s %t
+
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/strings.s -o %t/strings.o
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/main.s -o %t/main.o
+
+# RUN: %lld -arch arm64 -lSystem -o %t.out %t/strings.o %t/main.o
+
+# RUN: llvm-otool -vs __TEXT __cstring %t.out | FileCheck %s --check-prefix=CSTRING
+# RUN: llvm-otool -vs __TEXT __objc_methname %t.out | FileCheck %s --check-prefix=METHNAME
+
+# RUN: %lld -arch arm64 -lSystem -o %t/duplicates %t/strings.o %t/strings.o %t/main.o --deduplicate-literals
+
+# RUN: llvm-otool -vs __TEXT __cstring %t/duplicates | FileCheck %s --check-prefix=CSTRING
+# RUN: llvm-otool -vs __TEXT __objc_methname %t/duplicates | FileCheck %s --check-prefix=METHNAME
+
+# CSTRING: Contents of (__TEXT,__cstring) section
+# CSTRING-NEXT: existing-cstring
+# CSTIRNG-EMPTY:
+
+# METHNAME: Contents of (__TEXT,__objc_methname) section
+# METHNAME-NEXT: existing_methname
+# METHNAME-NEXT: synthetic_methname
+# METHNAME-EMPTY:
+
+#--- strings.s
+.cstring
+.p2align 2
+  .asciz "existing-cstring"
+
+.section __TEXT,__objc_methname,cstring_literals
+  .asciz  "existing_methname"
+
+#--- main.s
+.text
+.globl _objc_msgSend
+_objc_msgSend:
+  ret
+
+.globl _main
+_main:
+  bl  _objc_msgSend$existing_methname
+  bl  _objc_msgSend$synthetic_methname
+  ret

lld/test/MachO/objc-selrefs.s

+# REQUIRES: aarch64
+# RUN: rm -rf %t; split-file %s %t
+
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/existing.s -o %t/existing.o
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/main.s -o %t/main.o
+
+# RUN: %lld -arch arm64 -lSystem -o %t/out %t/existing.o %t/main.o
+# RUN: llvm-otool -vs __DATA __objc_selrefs %t/out | FileCheck %s --check-prefix=SELREFS
+
+# SELREFS: Contents of (__DATA,__objc_selrefs) section
+# SELREFS-NEXT: __TEXT:__objc_methname:foo
+# SELREFS-NEXT: __TEXT:__objc_methname:bar
+# SELREFS-NEXT: __TEXT:__objc_methname:foo
+# SELREFS-NEXT: __TEXT:__objc_methname:length
+# SELREFS-EMPTY:
+
+# RUN: %lld -arch arm64 -lSystem -o %t/out %t/existing.o %t/main.o --deduplicate-literals
+# RUN: llvm-otool -vs __DATA __objc_selrefs %t/out | FileCheck %s --check-prefix=DEDUP
+
+# DEDUP: Contents of (__DATA,__objc_selrefs) section
+# DEDUP-NEXT: __TEXT:__objc_methname:foo
+# DEDUP-NEXT: __TEXT:__objc_methname:bar
+# NOTE: Ideally this wouldn't exist, but while it does it needs to point to the deduplicated string
+# DEDUP-NEXT: __TEXT:__objc_methname:foo
+# DEDUP-NEXT: __TEXT:__objc_methname:length
+# DEDUP-EMPTY:
+
+#--- existing.s
+.section  __TEXT,__objc_methname,cstring_literals
+lselref1:
+  .asciz  "foo"
+lselref2:
+  .asciz  "bar"
+
+.section  __DATA,__objc_selrefs,literal_pointers,no_dead_strip
+.p2align  3
+.quad lselref1
+.quad lselref2
+
+#--- main.s
+.text
+.globl _objc_msgSend
+_objc_msgSend:
+  ret
+
+.globl _main
+_main:
+  bl  _objc_msgSend$length
+  bl  _objc_msgSend$foo
+  ret

lld/test/MachO/x86-64-objc-stubs.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
+# RUN: %lld -arch x86_64 -lSystem -o %t.out %t.o
+# RUN: llvm-otool -vs __TEXT __objc_stubs %t.out | FileCheck %s
+
+# CHECK: Contents of (__TEXT,__objc_stubs) section
+
+# CHECK-NEXT: _objc_msgSend$foo:
+# CHECK-NEXT: 00000001000004b8  movq  0x1b51(%rip), %rsi
+# CHECK-NEXT: 00000001000004bf  jmpq  *0xb3b(%rip)
+
+# CHECK-NEXT: _objc_msgSend$length:
+# CHECK-NEXT: 00000001000004c5  movq  0x1b4c(%rip), %rsi
+# CHECK-NEXT: 00000001000004cc  jmpq  *0xb2e(%rip)
+
+# CHECK-EMPTY:
+
+.section  __TEXT,__objc_methname,cstring_literals
+lselref1:
+  .asciz  "foo"
+lselref2:
+  .asciz  "bar"
+
+.section  __DATA,__objc_selrefs,literal_pointers,no_dead_strip
+.p2align  3
+.quad lselref1
+.quad lselref2
+
+.text
+.globl _objc_msgSend
+_objc_msgSend:
+  ret
+
+.globl _main
+_main:
+  callq  _objc_msgSend$length
+  callq  _objc_msgSend$foo
+  callq  _objc_msgSend$foo
+  ret