[lld/mac] Add support for $ld$previous symbols with explicit symbol name

A symbol `$ld$previous$/Another$1.2.3$1$3.0$14.0$_xxx$` means
"pretend symbol `_xxx` is in dylib `/Another` with version `1.2.3`
if the deployment target is between `3.0` and `14.0` and we're
targeting platform `1` (ie macOS)".

This means dylibs can now inject synthetic dylibs into the link, so
DylibFile needs to grow a 3rd constructor.

The only other interesting thing is that such an injected dylib
counts as a use of the original dylib. This patch gets this mostly
right (if _only_ `$ld$previous` symbols are used from a dylib,
we don't add a dep on the dylib itself, matching ld64), but one case
where we don't match ld64 yet is that ld64 even omits the original
dylib when linking it with `-needed-l`. Lld currently still adds a load
command for the original dylib in that case. (That's for a future
patch.)

Fixes #56074.

Differential Revision: https://reviews.llvm.org/D130725

(cherry picked from commit 241f0e8b76d544a4a07a7f775b8421632539be19)

5 files changed, 219 insertions, 76 deletions

diff --git a/lld/MachO/DriverUtils.cpp b/lld/MachO/DriverUtils.cpp
index d8e474d15cfd..b91a43552443 100644
--- a/lld/MachO/DriverUtils.cpp
+++ b/lld/MachO/DriverUtils.cpp
@@ -211,7 +211,7 @@ DylibFile *macho::loadDylib(MemoryBufferRef mbref, DylibFile *umbrella,
   DylibFile *&file = loadedDylibs[path];
   if (file) {
     if (explicitlyLinked)
-      file->explicitlyLinked = explicitlyLinked;
+      file->setExplicitlyLinked();
     return file;
   }
 
diff --git a/lld/MachO/InputFiles.cpp b/lld/MachO/InputFiles.cpp
index b463d7817594..cbb04a3bf04f 100644
--- a/lld/MachO/InputFiles.cpp
+++ b/lld/MachO/InputFiles.cpp
@@ -1944,6 +1944,14 @@ DylibFile::DylibFile(const InterfaceFile &interface, DylibFile *umbrella,
   }
 }
 
+DylibFile::DylibFile(DylibFile *umbrella)
+    : InputFile(DylibKind, MemoryBufferRef{}), refState(RefState::Unreferenced),
+      explicitlyLinked(false), isBundleLoader(false) {
+  if (umbrella == nullptr)
+    umbrella = this;
+  this->umbrella = umbrella;
+}
+
 void DylibFile::parseReexports(const InterfaceFile &interface) {
   const InterfaceFile *topLevel =
       interface.getParent() == nullptr ? &interface : interface.getParent();
@@ -1955,6 +1963,39 @@ void DylibFile::parseReexports(const InterfaceFile &interface) {
   }
 }
 
+bool DylibFile::isExplicitlyLinked() const {
+  if (!explicitlyLinked)
+    return false;
+
+  // If this dylib was explicitly linked, but at least one of the symbols
+  // of the synthetic dylibs it created via $ld$previous symbols is
+  // referenced, then that synthetic dylib fulfils the explicit linkedness
+  // and we can deadstrip this dylib if it's unreferenced.
+  for (const auto *dylib : extraDylibs)
+    if (dylib->isReferenced())
+      return false;
+
+  return true;
+}
+
+DylibFile *DylibFile::getSyntheticDylib(StringRef installName,
+                                        uint32_t currentVersion,
+                                        uint32_t compatVersion) {
+  for (DylibFile *dylib : extraDylibs)
+    if (dylib->installName == installName) {
+      // FIXME: Check what to do if different $ld$previous symbols
+      // request the same dylib, but with different versions.
+      return dylib;
+    }
+
+  auto *dylib = make<DylibFile>(umbrella == this ? nullptr : umbrella);
+  dylib->installName = saver().save(installName);
+  dylib->currentVersion = currentVersion;
+  dylib->compatibilityVersion = compatVersion;
+  extraDylibs.push_back(dylib);
+  return dylib;
+}
+
 // $ld$ symbols modify the properties/behavior of the library (e.g. its install
 // name, compatibility version or hide/add symbols) for specific target
 // versions.
@@ -1990,10 +2031,9 @@ void DylibFile::handleLDPreviousSymbol(StringRef name, StringRef originalName) {
   std::tie(platformStr, name) = name.split('$');
   std::tie(startVersion, name) = name.split('$');
   std::tie(endVersion, name) = name.split('$');
-  std::tie(symbolName, rest) = name.split('$');
-  // TODO: ld64 contains some logic for non-empty symbolName as well.
-  if (!symbolName.empty())
-    return;
+  std::tie(symbolName, rest) = name.rsplit('$');
+
+  // FIXME: Does this do the right thing for zippered files?
   unsigned platform;
   if (platformStr.getAsInteger(10, platform) ||
       platform != static_cast<unsigned>(config->platform()))
@@ -2014,8 +2054,9 @@ void DylibFile::handleLDPreviousSymbol(StringRef name, StringRef originalName) {
       config->platformInfo.minimum >= end)
     return;
 
-  this->installName = saver().save(installName);
-
+  // Initialized to compatibilityVersion for the symbolName branch below.
+  uint32_t newCompatibilityVersion = compatibilityVersion;
+  uint32_t newCurrentVersionForSymbol = currentVersion;
   if (!compatVersion.empty()) {
     VersionTuple cVersion;
     if (cVersion.tryParse(compatVersion)) {
@@ -2023,8 +2064,27 @@ void DylibFile::handleLDPreviousSymbol(StringRef name, StringRef originalName) {
            "' ignored");
       return;
     }
-    compatibilityVersion = encodeVersion(cVersion);
+    newCompatibilityVersion = encodeVersion(cVersion);
+    newCurrentVersionForSymbol = newCompatibilityVersion;
+  }
+
+  if (!symbolName.empty()) {
+    // A $ld$previous$ symbol with symbol name adds a symbol with that name to
+    // a dylib with given name and version.
+    auto *dylib = getSyntheticDylib(installName, newCurrentVersionForSymbol,
+                                    newCompatibilityVersion);
+
+    // Just adding the symbol to the symtab works because dylibs contain their
+    // symbols in alphabetical order, guaranteeing $ld$ symbols to precede
+    // normal symbols.
+    dylib->symbols.push_back(symtab->addDylib(
+        saver().save(symbolName), dylib, /*isWeakDef=*/false, /*isTlv=*/false));
+    return;
   }
+
+  // A $ld$previous$ symbol without symbol name modifies the dylib it's in.
+  this->installName = saver().save(installName);
+  this->compatibilityVersion = newCompatibilityVersion;
 }
 
 void DylibFile::handleLDInstallNameSymbol(StringRef name,
diff --git a/lld/MachO/InputFiles.h b/lld/MachO/InputFiles.h
index ea6802814e4c..89172922a0a7 100644
--- a/lld/MachO/InputFiles.h
+++ b/lld/MachO/InputFiles.h
@@ -219,10 +219,13 @@ public:
   explicit DylibFile(const llvm::MachO::InterfaceFile &interface,
                      DylibFile *umbrella, bool isBundleLoader,
                      bool explicitlyLinked);
+  explicit DylibFile(DylibFile *umbrella);
 
   void parseLoadCommands(MemoryBufferRef mb);
   void parseReexports(const llvm::MachO::InterfaceFile &interface);
   bool isReferenced() const { return numReferencedSymbols > 0; }
+  bool isExplicitlyLinked() const;
+  void setExplicitlyLinked() { explicitlyLinked = true; }
 
   static bool classof(const InputFile *f) { return f->kind() == DylibKind; }
 
@@ -239,14 +242,26 @@ public:
   bool forceNeeded = false;
   bool forceWeakImport = false;
   bool deadStrippable = false;
-  bool explicitlyLinked = false;
+
+private:
+  bool explicitlyLinked = false; // Access via isExplicitlyLinked().
+
+public:
   // An executable can be used as a bundle loader that will load the output
   // file being linked, and that contains symbols referenced, but not
   // implemented in the bundle. When used like this, it is very similar
   // to a dylib, so we've used the same class to represent it.
   bool isBundleLoader;
 
+  // Synthetic Dylib objects created by $ld$previous symbols in this dylib.
+  // Usually empty. These synthetic dylibs won't have synthetic dylibs
+  // themselves.
+  SmallVector<DylibFile *, 2> extraDylibs;
+
 private:
+  DylibFile *getSyntheticDylib(StringRef installName, uint32_t currentVersion,
+                               uint32_t compatVersion);
+
   bool handleLDSymbol(StringRef originalName);
   void handleLDPreviousSymbol(StringRef name, StringRef originalName);
   void handleLDInstallNameSymbol(StringRef name, StringRef originalName);
diff --git a/lld/MachO/Writer.cpp b/lld/MachO/Writer.cpp
index 7fad9f5564ce..3c44a60f4be2 100644
--- a/lld/MachO/Writer.cpp
+++ b/lld/MachO/Writer.cpp
@@ -780,70 +780,80 @@ template <class LP> void Writer::createLoadCommands() {
   if (config->outputType == MH_EXECUTE)
     in.header->addLoadCommand(make<LCMain>());
 
+  // See ld64's OutputFile::buildDylibOrdinalMapping for the corresponding
+  // library ordinal computation code in ld64.
   int64_t dylibOrdinal = 1;
   DenseMap<StringRef, int64_t> ordinalForInstallName;
+
+  std::vector<DylibFile *> dylibFiles;
   for (InputFile *file : inputFiles) {
-    if (auto *dylibFile = dyn_cast<DylibFile>(file)) {
-      if (dylibFile->isBundleLoader) {
-        dylibFile->ordinal = BIND_SPECIAL_DYLIB_MAIN_EXECUTABLE;
-        // Shortcut since bundle-loader does not re-export the symbols.
+    if (auto *dylibFile = dyn_cast<DylibFile>(file))
+      dylibFiles.push_back(dylibFile);
+  }
+  for (size_t i = 0; i < dylibFiles.size(); ++i)
+    dylibFiles.insert(dylibFiles.end(), dylibFiles[i]->extraDylibs.begin(),
+                      dylibFiles[i]->extraDylibs.end());
 
-        dylibFile->reexport = false;
-        continue;
-      }
+  for (DylibFile *dylibFile : dylibFiles) {
+    if (dylibFile->isBundleLoader) {
+      dylibFile->ordinal = BIND_SPECIAL_DYLIB_MAIN_EXECUTABLE;
+      // Shortcut since bundle-loader does not re-export the symbols.
 
-      // Don't emit load commands for a dylib that is not referenced if:
-      // - it was added implicitly (via a reexport, an LC_LOAD_DYLINKER --
-      //   if it's on the linker command line, it's explicit)
-      // - or it's marked MH_DEAD_STRIPPABLE_DYLIB
-      // - or the flag -dead_strip_dylibs is used
-      // FIXME: `isReferenced()` is currently computed before dead code
-      // stripping, so references from dead code keep a dylib alive. This
-      // matches ld64, but it's something we should do better.
-      if (!dylibFile->isReferenced() && !dylibFile->forceNeeded &&
-          (!dylibFile->explicitlyLinked || dylibFile->deadStrippable ||
-           config->deadStripDylibs))
-        continue;
+      dylibFile->reexport = false;
+      continue;
+    }
 
-      // Several DylibFiles can have the same installName. Only emit a single
-      // load command for that installName and give all these DylibFiles the
-      // same ordinal.
-      // This can happen in several cases:
-      // - a new framework could change its installName to an older
-      //   framework name via an $ld$ symbol depending on platform_version
-      // - symlinks (for example, libpthread.tbd is a symlink to libSystem.tbd;
-      //   Foo.framework/Foo.tbd is usually a symlink to
-      //   Foo.framework/Versions/Current/Foo.tbd, where
-      //   Foo.framework/Versions/Current is usually a symlink to
-      //   Foo.framework/Versions/A)
-      // - a framework can be linked both explicitly on the linker
-      //   command line and implicitly as a reexport from a different
-      //   framework. The re-export will usually point to the tbd file
-      //   in Foo.framework/Versions/A/Foo.tbd, while the explicit link will
-      //   usually find Foo.framework/Foo.tbd. These are usually symlinks,
-      //   but in a --reproduce archive they will be identical but distinct
-      //   files.
-      // In the first case, *semantically distinct* DylibFiles will have the
-      // same installName.
-      int64_t &ordinal = ordinalForInstallName[dylibFile->installName];
-      if (ordinal) {
-        dylibFile->ordinal = ordinal;
-        continue;
-      }
+    // Don't emit load commands for a dylib that is not referenced if:
+    // - it was added implicitly (via a reexport, an LC_LOAD_DYLINKER --
+    //   if it's on the linker command line, it's explicit)
+    // - or it's marked MH_DEAD_STRIPPABLE_DYLIB
+    // - or the flag -dead_strip_dylibs is used
+    // FIXME: `isReferenced()` is currently computed before dead code
+    // stripping, so references from dead code keep a dylib alive. This
+    // matches ld64, but it's something we should do better.
+    if (!dylibFile->isReferenced() && !dylibFile->forceNeeded &&
+        (!dylibFile->isExplicitlyLinked() || dylibFile->deadStrippable ||
+         config->deadStripDylibs))
+      continue;
 
-      ordinal = dylibFile->ordinal = dylibOrdinal++;
-      LoadCommandType lcType =
-          dylibFile->forceWeakImport || dylibFile->refState == RefState::Weak
-              ? LC_LOAD_WEAK_DYLIB
-              : LC_LOAD_DYLIB;
-      in.header->addLoadCommand(make<LCDylib>(lcType, dylibFile->installName,
-                                              dylibFile->compatibilityVersion,
-                                              dylibFile->currentVersion));
-
-      if (dylibFile->reexport)
-        in.header->addLoadCommand(
-            make<LCDylib>(LC_REEXPORT_DYLIB, dylibFile->installName));
+    // Several DylibFiles can have the same installName. Only emit a single
+    // load command for that installName and give all these DylibFiles the
+    // same ordinal.
+    // This can happen in several cases:
+    // - a new framework could change its installName to an older
+    //   framework name via an $ld$ symbol depending on platform_version
+    // - symlinks (for example, libpthread.tbd is a symlink to libSystem.tbd;
+    //   Foo.framework/Foo.tbd is usually a symlink to
+    //   Foo.framework/Versions/Current/Foo.tbd, where
+    //   Foo.framework/Versions/Current is usually a symlink to
+    //   Foo.framework/Versions/A)
+    // - a framework can be linked both explicitly on the linker
+    //   command line and implicitly as a reexport from a different
+    //   framework. The re-export will usually point to the tbd file
+    //   in Foo.framework/Versions/A/Foo.tbd, while the explicit link will
+    //   usually find Foo.framework/Foo.tbd. These are usually symlinks,
+    //   but in a --reproduce archive they will be identical but distinct
+    //   files.
+    // In the first case, *semantically distinct* DylibFiles will have the
+    // same installName.
+    int64_t &ordinal = ordinalForInstallName[dylibFile->installName];
+    if (ordinal) {
+      dylibFile->ordinal = ordinal;
+      continue;
     }
+
+    ordinal = dylibFile->ordinal = dylibOrdinal++;
+    LoadCommandType lcType =
+        dylibFile->forceWeakImport || dylibFile->refState == RefState::Weak
+            ? LC_LOAD_WEAK_DYLIB
+            : LC_LOAD_DYLIB;
+    in.header->addLoadCommand(make<LCDylib>(lcType, dylibFile->installName,
+                                            dylibFile->compatibilityVersion,
+                                            dylibFile->currentVersion));
+
+    if (dylibFile->reexport)
+      in.header->addLoadCommand(
+          make<LCDylib>(LC_REEXPORT_DYLIB, dylibFile->installName));
   }
 
   if (functionStartsSection)
diff --git a/lld/test/MachO/special-symbol-ld-previous.s b/lld/test/MachO/special-symbol-ld-previous.s
index db397353287f..8cdfb976dd04 100644
--- a/lld/test/MachO/special-symbol-ld-previous.s
+++ b/lld/test/MachO/special-symbol-ld-previous.s
@@ -2,52 +2,110 @@
 
 # RUN: rm -rf %t; split-file --no-leading-lines %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/ref_xxx.s -o %t/ref_xxx.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/ref_ySyy.s -o %t/ref_ySyy.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/ref_zzz.s -o %t/ref_zzz.o
 
 ## Case 1: special symbol $ld$previous affects the install name / compatibility version
 ## since the specified version 11.0.0 is within the affected range [3.0, 14.0).
 
-# RUN: %lld -o %t/libfoo1.dylib %t/libLDPreviousInstallName.tbd %t/foo.o -dylib -platform_version macos 11.0.0 11.0.0
+# RUN: %lld -o %t/libfoo1.dylib %t/libLDPreviousInstallName.tbd %t/ref_xxx.o -dylib -platform_version macos 11.0.0 11.0.0
 # RUN: llvm-objdump --macho --dylibs-used %t/libfoo1.dylib | FileCheck --check-prefix=CASE1 %s
-# CASE1: /New (compatibility version 1.2.3, current version 5.0.0)
+# CASE1: /Old (compatibility version 1.2.3, current version 5.0.0)
 
 ## Case 2: special symbol $ld$previous does not affect the install name / compatibility version
 ## since the specified version 2.0.0 is lower than the affected range [3.0, 14.0).
 
-# RUN: %lld -o %t/libfoo2.dylib %t/libLDPreviousInstallName.tbd %t/foo.o -dylib -platform_version macos 2.0.0 2.0.0
+# RUN: %lld -o %t/libfoo2.dylib %t/libLDPreviousInstallName.tbd %t/ref_xxx.o -dylib -platform_version macos 2.0.0 2.0.0
 # RUN: llvm-objdump --macho --dylibs-used %t/libfoo2.dylib | FileCheck --check-prefix=CASE2 %s
-# CASE2: /Old (compatibility version 1.1.1, current version 5.0.0)
+# CASE2: /New (compatibility version 1.1.1, current version 5.0.0)
 
 ## Case 3: special symbol $ld$previous does not affect the install name / compatibility version
 ## since the specified version 14.0.0 is higher than the affected range [3.0, 14.0).
 
-# RUN: %lld -o %t/libfoo3.dylib %t/libLDPreviousInstallName.tbd %t/foo.o -dylib -platform_version macos 2.0.0 2.0.0
+# RUN: %lld -o %t/libfoo3.dylib %t/libLDPreviousInstallName.tbd %t/ref_xxx.o -dylib -platform_version macos 2.0.0 2.0.0
 # RUN: llvm-objdump --macho --dylibs-used %t/libfoo3.dylib | FileCheck --check-prefix=CASE3 %s
-# CASE3: /Old (compatibility version 1.1.1, current version 5.0.0)
+# CASE3: /New (compatibility version 1.1.1, current version 5.0.0)
+
+## The remaining cases test handling when a symbol name is part of $ld$previous.
+
+## Case 4: special symbol $ld$previous affects the install name / compatibility version
+## when the specified version 11.0.0 is within the affected range [3.0, 14.0) when a symbol
+## is part of $previous$ if and only if that named symbol is referenced.
+## That is, for $ld$previous$/NewName$$3.0$14.0$_symNam$, if _symNam is
+## referenced, it refers to dylib /NewName if the deployment target is
+## in [3.0, 14.0).
+
+# RUN: %lld -o %t/libfoo4_yes.dylib %t/libLDPreviousInstallName-Symbol.tbd %t/ref_ySyy.o -dylib -platform_version macos 11.0.0 11.0.0
+# RUN: llvm-otool -L %t/libfoo4_yes.dylib | FileCheck --check-prefix=CASE4-YES --implicit-check-not=/New %s
+# CASE4-YES: /Old (compatibility version 1.2.3, current version 1.2.3)
+
+## $previous has no effect because deployment target is too new.
+# RUN: %lld -o %t/libfoo4_no.dylib %t/libLDPreviousInstallName-Symbol.tbd %t/ref_ySyy.o -dylib -platform_version macos 14.0.0 14.0.0
+# RUN: llvm-otool -L %t/libfoo4_no.dylib | FileCheck --check-prefix=CASE4-NO --implicit-check-not=/Old %s
+# CASE4-NO: /New (compatibility version 1.1.1, current version 5.0.0)
+
+## $previous has no effect because named symbol isn't referenced.
+# RUN: %lld -o %t/libfoo4_no.dylib %t/libLDPreviousInstallName-Symbol.tbd %t/ref_zzz.o -dylib -platform_version macos 11.0.0 11.0.0
+# RUN: llvm-otool -L %t/libfoo4_no.dylib | FileCheck --check-prefix=CASE4-NO %s
+
+## Case 5: Reference two symbols that add different $previous names each,
+## and one that references the "normal" dylib.
+## This should produce three different load commands.
+# RUN: %lld -o %t/libfoo5.dylib %t/libLDPreviousInstallName-Symbol.tbd %t/ref_xxx.o %t/ref_ySyy.o %t/ref_zzz.o -dylib -platform_version macos 11.0.0 11.0.0
+# RUN: llvm-otool -L %t/libfoo5.dylib | FileCheck --check-prefix=CASE5 %s
+# CASE5: /New (compatibility version 1.1.1, current version 5.0.0)
+# CASE5-DAG: /Another (compatibility version 1.1.1, current version 5.0.0)
+# CASE5-DAG: /Old (compatibility version 1.2.3, current version 1.2.3)
 
 ## Check that we emit a warning for an invalid start, end and compatibility versions.
 
-# RUN: %no-fatal-warnings-lld -o %t/libfoo1.dylib %t/libLDPreviousInvalid.tbd %t/foo.o -dylib \
+# RUN: %no-fatal-warnings-lld -o %t/libfoo1.dylib %t/libLDPreviousInvalid.tbd %t/ref_xxx.o -dylib \
 # RUN:  -platform_version macos 11.0.0 11.0.0 2>&1 | FileCheck --check-prefix=INVALID-VERSION %s
 
 # INVALID-VERSION-DAG: failed to parse start version, symbol '$ld$previous$/New$1.2.3$1$3.a$14.0$$' ignored
 # INVALID-VERSION-DAG: failed to parse end version, symbol '$ld$previous$/New$1.2.3$1$3.0$14.b$$' ignored
 # INVALID-VERSION-DAG: failed to parse compatibility version, symbol '$ld$previous$/New$1.2.c$1$3.0$14.0$$' ignored
 
-#--- foo.s
+#--- ref_xxx.s
 .long	_xxx@GOTPCREL
 
+#--- ref_ySyy.s
+.long	_y$yy@GOTPCREL
+
+#--- ref_zzz.s
+.long	_zzz@GOTPCREL
+
 #--- libLDPreviousInstallName.tbd
 --- !tapi-tbd-v3
 archs:           [ x86_64 ]
 uuids:           [ 'x86_64: 19311019-01AB-342E-812B-73A74271A715' ]
 platform:        macosx
-install-name:    '/Old'
+install-name:    '/New'
+current-version: 5
+compatibility-version: 1.1.1
+exports:
+  - archs:           [ x86_64 ]
+    symbols:         [ '$ld$previous$/Old$1.2.3$1$3.0$14.0$$', _xxx ]
+...
+
+#--- libLDPreviousInstallName-Symbol.tbd
+--- !tapi-tbd-v3
+archs:           [ x86_64 ]
+uuids:           [ 'x86_64: 19311019-01AB-342E-812B-73A74271A715' ]
+platform:        macosx
+install-name:    '/New'
 current-version: 5
 compatibility-version: 1.1.1
 exports:
   - archs:           [ x86_64 ]
-    symbols:         [ '$ld$previous$/New$1.2.3$1$3.0$14.0$$', _xxx ]
+    symbols:         [
+      '$ld$previous$/Another$$1$3.0$14.0$_xxx$',
+      '$ld$previous$/Old$1.2.3$1$3.0$14.0$_y$yy$',
+      _xxx,
+      '_y$yy',
+      _zzz,
+    ]
 ...
 
 #--- libLDPreviousInvalid.tbd