[lld-macho] Simplify the handling of "no unwind info" functions

[int3]

Summary

This diff does away with addEntriesForFunctionsWithoutUnwindInfo(),
because addSymbol() can now determine which functions need those
entries.

While overhauling UnwindInfoSection, I also parallelized the relocation
of the contents of the CUEs. This somewhat offsets the time regression
from creating one InputSection per CUE (which was done in D109944).

[oontvoo]

lld/MachO/UnwindInfoSection.cpp

146–151

Please include the explanation on why we're doing this (for eg., "because we'll use it with parallelForEachN" )

(or perhaps move this comment to the symbols's decl statement.)

287

this never changes - would be nice to have it fixed somewhere rather than having to re-type it in a few places

[int3]

elaborate on comment

lld/MachO/UnwindInfoSection.cpp

287

If we end up using it in multiple places, sure

[oontvoo]

LGTM

[nickdesaulniers]

I think this may have broken: lld/test/MachO/invalid/compact-unwind-bad-reloc.s?

: 'RUN: at line 2';   /android0/llvm-project/llvm/build/bin/llvm-mc -filetype=obj -triple=x86_64-apple-darwin19.0.0 /android0/llvm-project/lld/test/MachO/invalid/compact-unwind-bad-reloc.s -o /android0/llvm-project/llvm/build/tools/lld/test/MachO/invalid/Output/compact-unwind-bad-reloc.s.tmp.o
: 'RUN: at line 3';   not ld64.lld -arch x86_64 -platform_version macos 10.15 11.0 -syslibroot /android0/llvm-project/lld/test/MachO/Inputs/MacOSX.sdk -fatal_warnings -pie -lSystem -lc++ /android0/llvm-project/llvm/build/tools/lld/test/MachO/invalid/Output/compact-unwind-bad-reloc.s.tmp.o -o /android0/llvm-project/llvm/build/tools/lld/test/MachO/invalid/Output/compact-unwind-bad-reloc.s.tmp 2>&1 | /android0/llvm-project/llvm/build/bin/FileCheck /android0/llvm-project/lld/test/MachO/invalid/compact-unwind-bad-reloc.s -DFILE=/android0/llvm-project/llvm/build/tools/lld/test/MachO/invalid/Output/compact-unwind-bad-reloc.s.tmp.o
--
Exit Code: 2

Command Output (stderr):
--
+ : 'RUN: at line 2'
+ /android0/llvm-project/llvm/build/bin/llvm-mc -filetype=obj -triple=x86_64-apple-darwin19.0.0 /android0/llvm-project/lld/test/MachO/invalid/compact-unwind-bad-reloc.s -o /android0/llvm-project/llvm/build/tools/lld/test/MachO/invalid/Output/compact-unwind-bad-reloc.s.tmp.o
+ : 'RUN: at line 3'
+ not ld64.lld -arch x86_64 -platform_version macos 10.15 11.0 -syslibroot /android0/llvm-project/lld/test/MachO/Inputs/MacOSX.sdk -fatal_warnings -pie -lSystem -lc++ /android0/llvm-project/llvm/build/tools/lld/test/MachO/invalid/Output/compact-unwind-bad-reloc.s.tmp.o -o /android0/llvm-project/llvm/build/tools/lld/test/MachO/invalid/Output/compact-unwind-bad-reloc.s.tmp
+ /android0/llvm-project/llvm/build/bin/FileCheck /android0/llvm-project/lld/test/MachO/invalid/compact-unwind-bad-reloc.s -DFILE=/android0/llvm-project/llvm/build/tools/lld/test/MachO/invalid/Output/compact-unwind-bad-reloc.s.tmp.o
FileCheck error: '<stdin>' is empty.
FileCheck command line:  /android0/llvm-project/llvm/build/bin/FileCheck /android0/llvm-project/lld/test/MachO/invalid/compact-unwind-bad-reloc.s -DFILE=/android0/llvm-project/llvm/build/tools/lld/test/MachO/invalid/Output/compact-unwind-bad-reloc.s.tmp.o

lld/MachO/UnwindInfoSection.h

 //===- UnwindInfoSection.h ------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_UNWIND_INFO_H
 #define LLD_MACHO_UNWIND_INFO_H
 
 #include "ConcatOutputSection.h"
 #include "SyntheticSections.h"
+#include "llvm/ADT/MapVector.h"
 
 #include "mach-o/compact_unwind_encoding.h"
 
 namespace lld {
 namespace macho {
 
-template <class Ptr> struct CompactUnwindEntry {
-  Ptr functionAddress;
-  uint32_t functionLength;
-  compact_unwind_encoding_t encoding;
-  Ptr personality;
-  Ptr lsda;
-};
-
 class UnwindInfoSection : public SyntheticSection {
 public:
-  bool isNeeded() const override {
-    return !compactUnwindSection->inputs.empty() && !allEntriesAreOmitted;
-  }
+  // If all functions are free of unwind info, we can omit the unwind info
+  // section entirely.
+  bool isNeeded() const override { return !allEntriesAreOmitted; }
   uint64_t getSize() const override { return unwindInfoSize; }
-  virtual void addSymbol(const Defined *) = 0;
-  std::vector<ConcatInputSection *> getInputs() {
-    return compactUnwindSection->inputs;
-  }
+  void addSymbol(const Defined *);
   void prepareRelocations();
 
 protected:
   UnwindInfoSection();
   virtual void prepareRelocations(ConcatInputSection *) = 0;
 
-  ConcatOutputSection *compactUnwindSection;
+  llvm::MapVector<std::pair<const InputSection *, uint64_t /*Defined::value*/>,
+                  const Defined *>
+      symbols;
   uint64_t unwindInfoSize = 0;
   bool allEntriesAreOmitted = true;
 };
 
 UnwindInfoSection *makeUnwindInfoSection();
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/UnwindInfoSection.cpp

 #include "SyntheticSections.h"
 #include "Target.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/BinaryFormat/MachO.h"
+#include "llvm/Support/Parallel.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace lld;
 using namespace lld::macho;
 
 #define COMMON_ENCODINGS_MAX 127
 #define COMPACT_ENCODINGS_MAX 256

 //
 // Refer to the definition of unwind_info_section_header in
 // compact_unwind_encoding.h for an overview of the format we are encoding
 // here.
 
 // TODO(gkm): prune __eh_frame entries superseded by __unwind_info, PR50410
 // TODO(gkm): how do we align the 2nd-level pages?
 
+template <class Ptr> struct CompactUnwindEntry {
+  Ptr functionAddress;
+  uint32_t functionLength;
+  compact_unwind_encoding_t encoding;
+  Ptr personality;
+  Ptr lsda;
+};
+
 using EncodingMap = DenseMap<compact_unwind_encoding_t, size_t>;
 
 struct SecondLevelPage {
   uint32_t kind;
   size_t entryIndex;
   size_t entryCount;
   size_t byteCount;
   std::vector<compact_unwind_encoding_t> localEncodings;
   EncodingMap localEncodingIndexes;
 };
 
 template <class Ptr>
 class UnwindInfoSectionImpl final : public UnwindInfoSection {
 public:
   void prepareRelocations(ConcatInputSection *) override;
-  void addSymbol(const Defined *) override;
+  void relocateCompactUnwind(std::vector<CompactUnwindEntry<Ptr>> &);
   void finalize() override;
   void writeTo(uint8_t *buf) const override;
 
 private:
   std::vector<std::pair<compact_unwind_encoding_t, size_t>> commonEncodings;
   EncodingMap commonEncodingIndexes;
   // Indices of personality functions within the GOT.
   std::vector<Ptr> personalities;
   SmallDenseMap<std::pair<InputSection *, uint64_t /* addend */>, Symbol *>
       personalityTable;
   std::vector<unwind_info_section_header_lsda_index_entry> lsdaEntries;
   // Map of function offset (from the image base) to an index within the LSDA
   // array.
   DenseMap<uint32_t, uint32_t> functionToLsdaIndex;
   std::vector<CompactUnwindEntry<Ptr>> cuVector;
   std::vector<CompactUnwindEntry<Ptr> *> cuPtrVector;
   std::vector<SecondLevelPage> secondLevelPages;
   uint64_t level2PagesOffset = 0;
 };
 
 UnwindInfoSection::UnwindInfoSection()
     : SyntheticSection(segment_names::text, section_names::unwindInfo) {
   align = 4;
-  compactUnwindSection =
-      make<ConcatOutputSection>(section_names::compactUnwind);
 }
 
 void UnwindInfoSection::prepareRelocations() {
-  for (ConcatInputSection *isec : compactUnwindSection->inputs)
-    prepareRelocations(isec);
-}
-
-template <class Ptr>
-void UnwindInfoSectionImpl<Ptr>::addSymbol(const Defined *d) {
-  if (d->compactUnwind) {
-    d->compactUnwind->parent = compactUnwindSection;
-    compactUnwindSection->addInput(d->compactUnwind);
+  // This iteration needs to be deterministic, since prepareRelocations may add
+  // entries to the GOT. Hence the use of a MapVector for
+  // UnwindInfoSection::symbols.
+  for (const Defined *d : make_second_range(symbols))
+    if (d->compactUnwind)
+      prepareRelocations(d->compactUnwind);
+}
+
+// Record function symbols that may need entries emitted in __unwind_info, which
+// stores unwind data for address ranges.
+//
+// Note that if several adjacent functions have the same unwind encoding, LSDA,
+// and personality function, they share one unwind entry. For this to work,
+// functions without unwind info need explicit "no unwind info" unwind entries
+// -- else the unwinder would think they have the unwind info of the closest
+// function with unwind info right before in the image. Thus, we add function
+// symbols for each unique address regardless of whether they have associated
+// unwind info.
+void UnwindInfoSection::addSymbol(const Defined *d) {
+  if (d->compactUnwind)
+    allEntriesAreOmitted = false;
+  // We don't yet know the final output address of this symbol, but we know that
+  // they are uniquely determined by a combination of the isec and value, so
+  // we use that as the key here.
+  auto p = symbols.insert({{d->isec, d->value}, d});
+  // If we have multiple symbols at the same address, only one of them can have
+  // an associated CUE.
+  if (!p.second && d->compactUnwind) {
+    assert(!p.first->second->compactUnwind);
+    p.first->second = d;
   }
 }
 
 // Compact unwind relocations have different semantics, so we handle them in a
 // separate code path from regular relocations. First, we do not wish to add
 // rebase opcodes for __LD,__compact_unwind, because that section doesn't
 // actually end up in the final binary. Second, personality pointers always
 // reside in the GOT and must be treated specially.
 template <class Ptr>
 void UnwindInfoSectionImpl<Ptr>::prepareRelocations(ConcatInputSection *isec) {
   assert(!isec->shouldOmitFromOutput() &&
          "__compact_unwind section should not be omitted");
 
   // FIXME: Make this skip relocations for CompactUnwindEntries that
   // point to dead-stripped functions. That might save some amount of
   // work. But since there are usually just few personality functions
   // that are referenced from many places, at least some of them likely
   // live, it wouldn't reduce number of got entries.
   for (size_t i = 0; i < isec->relocs.size(); ++i) {
     Reloc &r = isec->relocs[i];
     assert(target->hasAttr(r.type, RelocAttrBits::UNSIGNED));
 
-    if (r.offset % sizeof(CompactUnwindEntry<Ptr>) == 0) {
-      InputSection *referentIsec;
-      if (auto *isec = r.referent.dyn_cast<InputSection *>())
-        referentIsec = isec;
-      else
-        referentIsec = cast<Defined>(r.referent.dyn_cast<Symbol *>())->isec;
-
-      if (!cast<ConcatInputSection>(referentIsec)->shouldOmitFromOutput())
-        allEntriesAreOmitted = false;
-      continue;
-    }
-
     if (r.offset % sizeof(CompactUnwindEntry<Ptr>) !=
         offsetof(CompactUnwindEntry<Ptr>, personality))
       continue;
 
     if (auto *s = r.referent.dyn_cast<Symbol *>()) {
       if (auto *defined = dyn_cast<Defined>(s)) {
         // XXX(vyng) This is a a special case for handling duplicate personality
         // symbols. Note that LD64's behavior is a bit different and it is
static ConcatInputSection *checkTextSegment(InputSection *isec) {
   return cast<ConcatInputSection>(isec);
 }
 
 // We need to apply the relocations to the pre-link compact unwind section
 // before converting it to post-link form. There should only be absolute
 // relocations here: since we are not emitting the pre-link CU section, there
 // is no source address to make a relative location meaningful.
 template <class Ptr>
-static void
-relocateCompactUnwind(ConcatOutputSection *compactUnwindSection,
-                      std::vector<CompactUnwindEntry<Ptr>> &cuVector) {
-  for (const ConcatInputSection *isec : compactUnwindSection->inputs) {
-    assert(isec->parent == compactUnwindSection);
-
-    uint8_t *buf =
-        reinterpret_cast<uint8_t *>(cuVector.data()) + isec->outSecOff;
-    memcpy(buf, isec->data.data(), isec->data.size());
+void UnwindInfoSectionImpl<Ptr>::relocateCompactUnwind(
+  auto symbolsVec = symbols.takeVector();
+  parallelForEachN(0, symbolsVec.size(), [&](size_t i) {
+    uint8_t *buf = reinterpret_cast<uint8_t *>(cuVector.data()) +
+                   i * sizeof(CompactUnwindEntry<Ptr>);
+    const Defined *d = symbolsVec[i].second;
+    // Write the functionAddress.
+    writeAddress(buf, d->getVA(), sizeof(Ptr) == 8 ? 3 : 2);
+    if (!d->compactUnwind)
+      return;
 
-    for (const Reloc &r : isec->relocs) {
+    // Write the rest of the CUE.
+    memcpy(buf, d->compactUnwind->data.data(), d->compactUnwind->data.size());
+    for (const Reloc &r : d->compactUnwind->relocs) {
       uint64_t referentVA = 0;
       if (auto *referentSym = r.referent.dyn_cast<Symbol *>()) {
         if (!isa<Undefined>(referentSym)) {
           if (auto *defined = dyn_cast<Defined>(referentSym))
             checkTextSegment(defined->isec);
           // At this point in the link, we may not yet know the final address of
           // the GOT, so we just encode the index. We make it a 1-based index so
           // that we can distinguish the null pointer case.
           referentVA = referentSym->gotIndex + 1;
         }
       } else {
         auto *referentIsec = r.referent.get<InputSection *>();
         ConcatInputSection *concatIsec = checkTextSegment(referentIsec);
         if (!concatIsec->shouldOmitFromOutput())
           referentVA = referentIsec->getVA(r.addend);
       }
       writeAddress(buf + r.offset, referentVA, r.length);
     }
-  }
+  });
 }
 
 // There should only be a handful of unique personality pointers, so we can
 // encode them as 2-bit indices into a small array.
 template <class Ptr>
 static void
 encodePersonalities(const std::vector<CompactUnwindEntry<Ptr> *> &cuPtrVector,
                     std::vector<Ptr> &personalities) {
cu->encoding |=
         personalityIndex << countTrailingZeros(
             static_cast<compact_unwind_encoding_t>(UNWIND_PERSONALITY_MASK));
   }
   if (personalities.size() > 3)
     error("too many personalities (" + std::to_string(personalities.size()) +
           ") for compact unwind to encode");
 }
 
-// __unwind_info stores unwind data for address ranges. If several
-// adjacent functions have the same unwind encoding, LSDA, and personality
-// function, they share one unwind entry. For this to work, functions without
-// unwind info need explicit "no unwind info" unwind entries -- else the
-// unwinder would think they have the unwind info of the closest function
-// with unwind info right before in the image.
-template <class Ptr>
-static void addEntriesForFunctionsWithoutUnwindInfo(
-    std::vector<CompactUnwindEntry<Ptr>> &cuVector) {
-  DenseSet<Ptr> hasUnwindInfo;
-  for (CompactUnwindEntry<Ptr> &cuEntry : cuVector)
-    hasUnwindInfo.insert(cuEntry.functionAddress);
-
-  // Add explicit "has no unwind info" entries for all global and local symbols
-  // without unwind info.
-  auto markNoUnwindInfo = [&cuVector, &hasUnwindInfo](const Defined *d) {
-    if (d->isLive() && d->isec && isCodeSection(d->isec)) {
-      Ptr ptr = d->getVA();
-      if (!hasUnwindInfo.count(ptr))
-        cuVector.push_back({ptr, 0, 0, 0, 0});
-    }
-  };
-  for (Symbol *sym : symtab->getSymbols())
-    if (auto *d = dyn_cast<Defined>(sym))
-      markNoUnwindInfo(d);
-  for (const InputFile *file : inputFiles)
-    if (auto *objFile = dyn_cast<ObjFile>(file))
-      for (Symbol *sym : objFile->symbols)
-        if (auto *d = dyn_cast_or_null<Defined>(sym))
-          if (!d->isExternal())
-            markNoUnwindInfo(d);
-}
-
 static bool canFoldEncoding(compact_unwind_encoding_t encoding) {
   // From compact_unwind_encoding.h:
   //  UNWIND_X86_64_MODE_STACK_IND:
   //  A "frameless" (RBP not used as frame pointer) function large constant
   //  stack size.  This case is like the previous, except the stack size is too
   //  large to encode in the compact unwind encoding.  Instead it requires that
   //  the function contains "subq $nnnnnnnn,RSP" in its prolog.  The compact
   //  encoding contains the offset to the nnnnnnnn value in the function in
if ((target->cpuType == CPU_TYPE_X86_64 || target->cpuType == CPU_TYPE_X86) &&
     return false;
   }
   return true;
 }
 
 // Scan the __LD,__compact_unwind entries and compute the space needs of
 // __TEXT,__unwind_info and __TEXT,__eh_frame
 template <class Ptr> void UnwindInfoSectionImpl<Ptr>::finalize() {
-  if (compactUnwindSection == nullptr)
+  if (symbols.empty())
     return;
 
   // At this point, the address space for __TEXT,__text has been
   // assigned, so we can relocate the __LD,__compact_unwind entries
   // into a temporary buffer. Relocation is necessary in order to sort
   // the CU entries by function address. Sorting is necessary so that
   // we can fold adjacent CU entries with identical
   // encoding+personality+lsda. Folding is necessary because it reduces
   // the number of CU entries by as much as 3 orders of magnitude!
-  compactUnwindSection->finalize();
-  assert(compactUnwindSection->getSize() % sizeof(CompactUnwindEntry<Ptr>) ==
-         0);
-  size_t cuCount =
-      compactUnwindSection->getSize() / sizeof(CompactUnwindEntry<Ptr>);
-  cuVector.resize(cuCount);
-  relocateCompactUnwind(compactUnwindSection, cuVector);
-
-  addEntriesForFunctionsWithoutUnwindInfo(cuVector);
+  cuVector.resize(symbols.size());
+  relocateCompactUnwind(cuVector);
 
   // Rather than sort & fold the 32-byte entries directly, we create a
   // vector of pointers to entries and sort & fold that instead.
   cuPtrVector.reserve(cuVector.size());
   for (CompactUnwindEntry<Ptr> &cuEntry : cuVector)
     cuPtrVector.emplace_back(&cuEntry);
   llvm::sort(cuPtrVector, [](const CompactUnwindEntry<Ptr> *a,
                              const CompactUnwindEntry<Ptr> *b) {

lld/MachO/Writer.cpp

 void Writer::scanSymbols() {
   TimeTraceScope timeScope("Scan symbols");
   for (const Symbol *sym : symtab->getSymbols()) {
     if (const auto *defined = dyn_cast<Defined>(sym)) {
       if (!defined->isLive())
         continue;
       if (defined->overridesWeakDef)
         in.weakBinding->addNonWeakDefinition(defined);
+      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());
     }
   }
 
   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->isExternal() && defined->isLive())
+          if (!defined->isExternal() && defined->isLive() &&
+              !defined->isAbsolute() && isCodeSection(defined->isec))
             in.unwindInfo->addSymbol(defined);
       }
   }
 }
 
 // TODO: ld64 enforces the old load commands in a few other cases.
 static bool useLCBuildVersion(const PlatformInfo &platformInfo) {
   static const std::vector<std::pair<PlatformKind, VersionTuple>> minVersion = {