[lld-macho] Implement -why_live (without perf overhead)

[int3]

Summary

This was based off @thakis' draft in D103517: NOT FOR REVIEW: [lld/mac] why_live sketch. I employed templates to ensure
the support for -why_live wouldn't slow down the regular non-why-live code
path.

No stat sig perf difference on my 3.2 GHz 16-Core Intel Xeon W:

           base           diff           difference (95% CI)
sys_time   1.195 ± 0.015  1.199 ± 0.022  [  -0.4% ..   +1.0%]
user_time  3.716 ± 0.022  3.701 ± 0.025  [  -0.7% ..   -0.1%]
wall_time  4.606 ± 0.034  4.597 ± 0.046  [  -0.6% ..   +0.2%]
samples    44             37

[thakis]

Neat!

lld/MachO/MarkLive.cpp

100

errs() is unbuffered by default, no?

111

can you add a comment on why this doesn't use message()?

191

Do you want a makeEntry(nullptr, nullptr) for Undefineds here, or a nullptr?

Hm, I guess an Undefined never has relocs. Do we always have a Defined here? If so, we should probably just cast<> without conditional.

If there are non-Undefined non-Defined cases, the original question if you want makeEntry(nullptr, nullptr) stands for that :)

[int3]

lld/MachO/MarkLive.cpp

100

I'd have thought so, but I didn't get messages emitted before adding this flush()...

111

oh yeah... I was thinking about how we would handle parallelization in the future, and I realized that message() wasn't ideal here because it would take one lock per call, whereas we want to take one lock for the whole of printWhyLiveImpl so that the lines wouldn't get interleaved with other concurrent messages. I'll add that comment.

[int3]

add comment

[thakis]

lld/MachO/MarkLive.cpp

111

Oh, good point. But maybe it's nicer to accumulate the message in a string and only call message() once at the end? Then we need to hold the lock for a shorter time.

(Are our bumpptr allocators in a per-thread tls?)

191

(this is still open)

[oontvoo]

lld/MachO/MarkLive.cpp

111

(Are our bumpptr allocators in a per-thread tls?)

No - the allocators are shared (and very much not thread-safe :\ )

[int3]

update

lld/MachO/MarkLive.cpp

111

But maybe it's nicer to accumulate the message in a string and only call message() once at the end? Then we need to hold the lock for a shorter time.

Good point!

Also, in case you missed it, there's this discussion going on: https://discourse.llvm.org/t/parallel-thread-safe-algorithms-allocators-and-containers/60472

191

Oh whoops, almost forgot about this one.

We could have dylib or undefined symbols here too, yeah. In fact, I'd neglected to add a test for that... and adding that test revealed a null deref issue due to this makeEntry(nullptr, nullptr) thing. Good catch :)

I'll have makeEntry() itself do the null check so that we don't have an extra conditional in the non-why-live-enabled case.

[thakis]

Looks like this doesn't build on Linux (and windows): http://45.33.8.238/linux/69521/step_4.txt

Please take a look and revert for now if it takes a while to fix.

[int3]

Whoops, forgot to check the asserts build. Looks like I was beaten to the fix in da11f17e90a86525b8902f0812180799f8d8fca9.

lld/MachO/Config.h

struct Configuration {
   bool callGraphProfileSort = false;
   llvm::StringRef printSymbolOrder;
 
   SectionRenameMap sectionRenameMap;
   SegmentRenameMap segmentRenameMap;
 
   SymbolPatterns exportedSymbols;
   SymbolPatterns unexportedSymbols;
+  SymbolPatterns whyLive;
 
   bool zeroModTime = false;
 
   llvm::StringRef osoPrefix;
 
   llvm::MachO::Architecture arch() const { return platformInfo.target.Arch; }
 
   llvm::MachO::PlatformType platform() const {

lld/MachO/Driver.cpp

#endif
   }
   // Explicitly-exported literal symbols must be defined, but might
   // languish in an archive if unreferenced elsewhere. Light a fire
   // under those lazy symbols!
   for (const CachedHashStringRef &cachedName : config->exportedSymbols.literals)
     symtab->addUndefined(cachedName.val(), /*file=*/nullptr,
                          /*isWeakRef=*/false);
 
+  for (const Arg *arg : args.filtered(OPT_why_live))
+    config->whyLive.insert(arg->getValue());
+  if (!config->whyLive.empty() && !config->deadStrip)
+    warn("-why_live has no effect without -dead_strip, ignoring");
+
   config->saveTemps = args.hasArg(OPT_save_temps);
 
   config->adhocCodesign = args.hasFlag(
       OPT_adhoc_codesign, OPT_no_adhoc_codesign,
       (config->arch() == AK_arm64 || config->arch() == AK_arm64e) &&
           config->platform() == PLATFORM_MACOS);
 
   if (args.hasArg(OPT_v)) {

lld/MachO/MarkLive.cpp

 #include "llvm/Support/TimeProfiler.h"
 
 namespace lld {
 namespace macho {
 
 using namespace llvm;
 using namespace llvm::MachO;
 
+struct WhyLiveEntry {
+  InputSection *isec;
+  // Keep track of the entry that caused us to mark `isec` as live.
+  const WhyLiveEntry *prev;
+
+  WhyLiveEntry(InputSection *isec, const WhyLiveEntry *prev)
+      : isec(isec), prev(prev) {}
+};
+
+// Type-erased interface to MarkLiveImpl. Used for adding roots to the liveness
+// graph.
 class MarkLive {
 public:
-  void enqueue(InputSection *isec, uint64_t off);
-  void addSym(Symbol *s);
-  void markTransitively();
+  virtual void enqueue(InputSection *isec, uint64_t off) = 0;
+  virtual void addSym(Symbol *s) = 0;
+  virtual void markTransitively() = 0;
+  virtual ~MarkLive() = default;
+};
+
+template <bool RecordWhyLive> class MarkLiveImpl : public MarkLive {
+public:
+  // -why_live is a rarely used option, so we don't want support for that flag
+  // to slow down the main -dead_strip code path. As such, we employ templates
+  // to avoid the usage of WhyLiveEntry in the main code path. This saves us
+  // from needless allocations and pointer indirections.
+  using WorklistEntry =
+      std::conditional_t<RecordWhyLive, WhyLiveEntry, InputSection>;
+
+  void enqueue(InputSection *isec, uint64_t off) override {
+    enqueue(isec, off, nullptr);
+  }
+  void addSym(Symbol *s) override { addSym(s, nullptr); }
+  void markTransitively() override;
 
 private:
+  void enqueue(InputSection *isec, uint64_t off, const WorklistEntry *prev);
+  void addSym(Symbol *s, const WorklistEntry *prev);
+  void printWhyLive(Symbol *s, const WorklistEntry *prev);
+  const InputSection *getInputSection(const WorklistEntry *) const;
+  WorklistEntry *makeEntry(InputSection *, const WorklistEntry *prev) const;
+
   // We build up a worklist of sections which have been marked as live. We
   // only push into the worklist when we discover an unmarked section, and we
   // mark as we push, so sections never appear twice in the list. Literal
   // sections cannot contain references to other sections, so we only store
   // ConcatInputSections in our worklist.
-  SmallVector<ConcatInputSection *, 256> worklist;
+  SmallVector<WorklistEntry *, 256> worklist;
 };
 
-void MarkLive::enqueue(InputSection *isec, uint64_t off) {
+template <bool RecordWhyLive>
+void MarkLiveImpl<RecordWhyLive>::enqueue(
+    InputSection *isec, uint64_t off,
+    const typename MarkLiveImpl<RecordWhyLive>::WorklistEntry *prev) {
   if (isec->isLive(off))
     return;
   isec->markLive(off);
   if (auto s = dyn_cast<ConcatInputSection>(isec)) {
     assert(!s->isCoalescedWeak());
-    worklist.push_back(s);
+    worklist.push_back(makeEntry(s, prev));
   }
 }
 
-void MarkLive::addSym(Symbol *s) {
+template <bool RecordWhyLive>
+void MarkLiveImpl<RecordWhyLive>::addSym(
+    Symbol *s,
+    const typename MarkLiveImpl<RecordWhyLive>::WorklistEntry *prev) {
   if (s->used)
     return;
   s->used = true;
+  printWhyLive(s, prev);
   if (auto *d = dyn_cast<Defined>(s)) {
     if (d->isec)
-      enqueue(d->isec, d->value);
+      enqueue(d->isec, d->value, prev);
     if (d->unwindEntry)
-      enqueue(d->unwindEntry, 0);
+      enqueue(d->unwindEntry, 0, prev);
+  }
+}
+
+static void printWhyLiveImpl(const Symbol *s, const WhyLiveEntry *prev) {
+  std::string out = toString(*s) + " from " + toString(s->getFile());
+  int indent = 2;
+  for (const WhyLiveEntry *entry = prev; entry;
+       entry = entry->prev, indent += 2) {
+    const TinyPtrVector<Defined *> &symbols = entry->isec->symbols;
+    // With .subsections_with_symbols set, most isecs will have exactly one
+    // entry in their symbols vector, so we just print the first one.
+    if (!symbols.empty())
+      out += "\n" + std::string(indent, ' ') + toString(*symbols.front()) +
+             " from " + toString(symbols.front()->getFile());
   }
+  message(out);
+}
+
+// NOTE: if/when `constexpr if` becomes available, we can simplify a lot of
+// the partial template specializations below.
+
+template <>
+void MarkLiveImpl<true>::printWhyLive(Symbol *s, const WhyLiveEntry *prev) {
+  if (!config->whyLive.empty() && config->whyLive.match(s->getName()))
+    printWhyLiveImpl(s, prev);
 }
 
-void MarkLive::markTransitively() {
+template <>
+void MarkLiveImpl<false>::printWhyLive(Symbol *s, const InputSection *prev) {}
+
+template <>
+const InputSection *
+MarkLiveImpl<true>::getInputSection(const WhyLiveEntry *entry) const {
+  return entry->isec;
+}
+
+template <>
+const InputSection *
+MarkLiveImpl<false>::getInputSection(const InputSection *isec) const {
+  return isec;
+}
+
+template <>
+typename MarkLiveImpl<true>::WorklistEntry *MarkLiveImpl<true>::makeEntry(
+    InputSection *isec, const MarkLiveImpl<true>::WorklistEntry *prev) const {
+  if (!isec) {
+    assert(!prev);
+    return nullptr;
+  }
+  return make<WhyLiveEntry>(isec, prev);
+}
+
+template <>
+typename MarkLiveImpl<false>::WorklistEntry *MarkLiveImpl<false>::makeEntry(
+    InputSection *isec, const MarkLiveImpl<false>::WorklistEntry *prev) const {
+  return isec;
+}
+
+template <bool RecordWhyLive>
+void MarkLiveImpl<RecordWhyLive>::markTransitively() {
   do {
     // Mark things reachable from GC roots as live.
     while (!worklist.empty()) {
-      ConcatInputSection *s = worklist.pop_back_val();
-      assert(s->live && "We mark as live when pushing onto the worklist!");
+      WorklistEntry *entry = worklist.pop_back_val();
+      assert(getInputSection(entry)->live &&
+             "We mark as live when pushing onto the worklist!");
 
       // Mark all symbols listed in the relocation table for this section.
-      for (const Reloc &r : s->relocs) {
+      for (const Reloc &r : getInputSection(entry)->relocs) {
         if (auto *s = r.referent.dyn_cast<Symbol *>())
-          addSym(s);
+          addSym(s, entry);
         else
-          enqueue(r.referent.get<InputSection *>(), r.addend);
+          enqueue(r.referent.get<InputSection *>(), r.addend, entry);
       }
-      for (Defined *d : s->symbols)
-        addSym(d);
+      for (Defined *d : getInputSection(entry)->symbols)
+        addSym(d, entry);
     }
 
     // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live
     // section. Process them in a second pass.
     for (ConcatInputSection *isec : inputSections) {
       // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a
       // separate vector and only walking that here is faster.
       if (!(isec->getFlags() & S_ATTR_LIVE_SUPPORT) || isec->live)
         continue;
 
       for (const Reloc &r : isec->relocs) {
-        bool referentLive;
-        if (auto *s = r.referent.dyn_cast<Symbol *>())
-          referentLive = s->isLive();
-        else
-          referentLive = r.referent.get<InputSection *>()->isLive(r.addend);
-        if (referentLive)
-          enqueue(isec, 0);
+        if (auto *s = r.referent.dyn_cast<Symbol *>()) {
+          if (s->isLive()) {
+            InputSection *referentIsec = nullptr;
+            if (auto *d = dyn_cast<Defined>(s))
+              referentIsec = d->isec;
+            enqueue(isec, 0, makeEntry(referentIsec, nullptr));
+          }
+        } else {
+          auto *referentIsec = r.referent.get<InputSection *>();
+          if (referentIsec->isLive(r.addend))
+            enqueue(isec, 0, makeEntry(referentIsec, nullptr));
+        }
       }
     }
 
     // S_ATTR_LIVE_SUPPORT could have marked additional sections live,
     // which in turn could mark additional S_ATTR_LIVE_SUPPORT sections live.
     // Iterate. In practice, the second iteration won't mark additional
     // S_ATTR_LIVE_SUPPORT sections live.
   } while (!worklist.empty());
 }
 
 // Set live bit on for each reachable chunk. Unmarked (unreachable)
 // InputSections will be ignored by Writer, so they will be excluded
 // from the final output.
 void markLive() {
   TimeTraceScope timeScope("markLive");
-  MarkLive marker;
+  MarkLive *marker;
+  if (config->whyLive.empty())
+    marker = make<MarkLiveImpl<false>>();
+  else
+    marker = make<MarkLiveImpl<true>>();
   // Add GC roots.
   if (config->entry)
-    marker.addSym(config->entry);
+    marker->addSym(config->entry);
   for (Symbol *sym : symtab->getSymbols()) {
     if (auto *defined = dyn_cast<Defined>(sym)) {
       // -exported_symbol(s_list)
       if (!config->exportedSymbols.empty() &&
           config->exportedSymbols.match(defined->getName())) {
         // FIXME: Instead of doing this here, maybe the Driver code doing
         // the matching should add them to explicitUndefineds? Then the
         // explicitUndefineds code below would handle this automatically.
         assert(!defined->privateExtern &&
                "should have been rejected by driver");
-        marker.addSym(defined);
+        marker->addSym(defined);
         continue;
       }
 
       // public symbols explicitly marked .no_dead_strip
       if (defined->referencedDynamically || defined->noDeadStrip) {
-        marker.addSym(defined);
+        marker->addSym(defined);
         continue;
       }
 
       // FIXME: When we implement these flags, make symbols from them GC
       // roots:
       // * -reexported_symbol(s_list)
       // * -alias(-list)
       // * -init
 
       // In dylibs and bundles and in executables with -export_dynamic,
       // all external functions are GC roots.
       bool externsAreRoots =
           config->outputType != MH_EXECUTE || config->exportDynamic;
       if (externsAreRoots && !defined->privateExtern) {
-        marker.addSym(defined);
+        marker->addSym(defined);
         continue;
       }
     }
   }
   // -u symbols
   for (Symbol *sym : config->explicitUndefineds)
-    marker.addSym(sym);
+    marker->addSym(sym);
   // local symbols explicitly marked .no_dead_strip
   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->noDeadStrip)
-            marker.addSym(defined);
+            marker->addSym(defined);
   if (auto *stubBinder =
           dyn_cast_or_null<DylibSymbol>(symtab->find("dyld_stub_binder")))
-    marker.addSym(stubBinder);
+    marker->addSym(stubBinder);
   for (ConcatInputSection *isec : inputSections) {
     // Sections marked no_dead_strip
     if (isec->getFlags() & S_ATTR_NO_DEAD_STRIP) {
-      marker.enqueue(isec, 0);
+      marker->enqueue(isec, 0);
       continue;
     }
 
     // mod_init_funcs, mod_term_funcs sections
     if (sectionType(isec->getFlags()) == S_MOD_INIT_FUNC_POINTERS ||
         sectionType(isec->getFlags()) == S_MOD_TERM_FUNC_POINTERS) {
-      marker.enqueue(isec, 0);
+      marker->enqueue(isec, 0);
       continue;
     }
   }
 
-  marker.markTransitively();
+  marker->markTransitively();
 }
 
 } // namespace macho
 } // namespace lld

lld/MachO/Options.td

def why_load : Flag<["-"], "why_load">,
     Group<grp_introspect>;
 def whyload : Flag<["-"], "whyload">,
     Alias<why_load>,
     HelpText<"Alias for -why_load">,
     Group<grp_introspect>;
 def why_live : Separate<["-"], "why_live">,
     MetaVarName<"<symbol>">,
     HelpText<"Log a chain of references to <symbol>, for use with -dead_strip">,
-    Flags<[HelpHidden]>,
     Group<grp_introspect>;
 def print_statistics : Flag<["-"], "print_statistics">,
     HelpText<"Log the linker's memory and CPU usage">,
     Flags<[HelpHidden]>,
     Group<grp_introspect>;
 def t : Flag<["-"], "t">,
     HelpText<"Log every file the linker loads: object, archive, and dylib">,
     Group<grp_introspect>;

lld/MachO/Symbols.h

protected:
   const char *nameData;
   InputFile *file;
   mutable uint32_t nameSize;
 
 public:
   // True if this symbol was referenced by a regular (non-bitcode) object.
   bool isUsedInRegularObj : 1;
 
-  // True if an undefined or dylib symbol is used from a live section.
+  // True if this symbol is used from a live section.
   bool used : 1;
 };
 
 class Defined : public Symbol {
 public:
   Defined(StringRefZ name, InputFile *file, InputSection *isec, uint64_t value,
           uint64_t size, bool isWeakDef, bool isExternal, bool isPrivateExtern,
           bool isThumb, bool isReferencedDynamically, bool noDeadStrip,

lld/test/MachO/why-live.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos %s -o %t.o
+# RUN: %lld -lSystem -dead_strip -why_live _foo -why_live _undef -U _undef \
+# RUN:   -why_live _support -why_live _support_refs_dylib_fun \
+# RUN:   -why_live _abs %t.o -o /dev/null 2>&1 | FileCheck %s
+
+## Due to an implementation detail, LLD is not able to report -why_live info for
+## absolute symbols. (ld64 has the same shortcoming.)
+# CHECK-NOT:   _abs
+# CHECK:       _foo from {{.*}}why-live.s.tmp.o
+# CHECK-NEXT:    _quux from {{.*}}why-live.s.tmp.o
+# CHECK-NEXT:  _undef from {{.*}}why-live.s.tmp.o
+# CHECK-NEXT:    _main from {{.*}}why-live.s.tmp.o
+## Our handling of live_support sections can be improved... we should print the
+## dylib symbol that keeps _support_refs_dylib_fun alive, instead of printing
+## the live_support symbol's name itself. (ld64 seems to have the same issue.)
+# CHECK-NEXT: _support_refs_dylib_fun from {{.*}}why-live.s.tmp.o
+# CHECK-NEXT:   _support_refs_dylib_fun from {{.*}}why-live.s.tmp.o
+## Again, this can be improved: we shouldn't be printing _support twice. (ld64
+## seems to have the same issue.)
+# CHECK-NEXT:  _support from {{.*}}why-live.s.tmp.o
+# CHECK-NEXT:    _support from {{.*}}why-live.s.tmp.o
+# CHECK-NEXT:      _foo from {{.*}}why-live.s.tmp.o
+# CHECK-EMPTY:
+
+.text
+_foo:
+  retq
+
+_bar:
+  retq
+
+_baz:
+  callq _foo
+  retq
+
+.no_dead_strip _quux
+_quux:
+  callq _foo
+  retq
+
+.globl _main
+_main:
+  callq _foo
+  callq _baz
+  callq _undef
+  callq ___isnan
+  retq
+
+.globl _abs
+_abs = 0x1000
+
+.section __TEXT,support,regular,live_support
+_support:
+  callq _foo
+  callq _abs
+  retq
+
+_support_refs_dylib_fun:
+  callq ___isnan
+  retq
+
+.subsections_via_symbols