NOT FOR REVIEW: [lld/mac] why_live sketch

[thakis]

Summary

As-is, regresses -dead_strip perf by > 3%

[int3]

clearing my queue

[thakis]

landed in improved form in D120377

lld/Common/ErrorHandler.cpp

   lld::errs() << logName << ": " << msg << "\n";
 }
 
-void ErrorHandler::message(const Twine &msg) {
+void ErrorHandler::message(const Twine &msg, llvm::raw_ostream &s) {
   if (disableOutput)
     return;
   std::lock_guard<std::mutex> lock(mu);
-  lld::outs() << msg << "\n";
-  lld::outs().flush();
+  s << msg << "\n";
+  s.flush();
 }
 
 void ErrorHandler::warn(const Twine &msg) {

lld/MachO/Config.h

 
   SymbolPatterns exportedSymbols;
   SymbolPatterns unexportedSymbols;
+  SymbolPatterns whyLive;
 
   bool zeroModTime = false;
 

lld/MachO/Driver.cpp

     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(

lld/MachO/MarkLive.cpp

 void markLive() {
   ScopedTimer t(gctimer);
 
+  // FIXME: PointerUniion<InputSection*, WorklistEntry*> based on if we whyLive?
+  struct WorklistEntry {
+    Symbol *sym;
+    InputSection *sec;
+    WorklistEntry *prev;
+  };
+
   // 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.
-  SmallVector<InputSection *, 256> worklist;
+  SmallVector<WorklistEntry *, 256> worklist;
 
-  auto enqueue = [&](InputSection *s) {
-    if (s->live)
+  auto enqueue = [&](WorklistEntry entry) {
+    if (entry.sec->live)
       return;
-    s->live = true;
-    worklist.push_back(s);
+    entry.sec->live = true;
+    worklist.push_back(make<WorklistEntry>(entry)); // XXX just keep in arena?
   };
 
-  auto addSym = [&](Symbol *s) {
+  auto addSym = [&](Symbol *s, WorklistEntry *prev) {
+    // XXX have to do this here for undefs?
+    if (!config->whyLive.empty() &&
+        config->whyLive.match(s->getName())) {
+      message(toString(*s) + " from " + toString(s->getFile()),
+              lld::errs());
+      int indent = 2;
+      for (WorklistEntry *p = prev; p; p = p->prev, indent += 2) {
+        if (p->sym)
+          message(std::string(indent, ' ') + toString(*p->sym) + " from " +
+                      toString(p->sym->getFile()),
+                  lld::errs());
+      }
+    }
+
     s->used = true;
     if (auto *d = dyn_cast<Defined>(s))
       if (d->isec)
-        enqueue(d->isec);
+        enqueue(WorklistEntry{s, d->isec, prev});
   };
 
   // Add GC roots.
   if (config->entry)
-    addSym(config->entry);
+    addSym(config->entry, nullptr);
   for (Symbol *sym : symtab->getSymbols()) {
     if (auto *defined = dyn_cast<Defined>(sym)) {
       // -exported_symbol(s_list)

         // explicitUndefineds code below would handle this automatically.
         assert(!defined->privateExtern &&
                "should have been rejected by driver");
-        addSym(defined);
+        addSym(defined, nullptr);
         continue;
       }
 
       // public symbols explicitly marked .no_dead_strip
       if (defined->referencedDynamically || defined->noDeadStrip) {
-        addSym(defined);
+        addSym(defined, nullptr);
         continue;
       }
 

       // In dylibs and bundles, all external functions are GC roots.
       // FIXME: -export_dynamic should enable this for executables too.
       if (config->outputType != MH_EXECUTE && !defined->privateExtern) {
-        addSym(defined);
+        addSym(defined, nullptr);
         continue;
       }
     }

   // -u symbols
   for (Symbol *sym : config->explicitUndefineds)
     if (auto *defined = dyn_cast<Defined>(sym))
-      addSym(defined);
+      addSym(defined, nullptr);
   // 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)
-            addSym(defined);
+            addSym(defined, nullptr);
   if (auto *stubBinder =
           dyn_cast_or_null<DylibSymbol>(symtab->find("dyld_stub_binder")))
-    addSym(stubBinder);
+    addSym(stubBinder, nullptr);
   for (InputSection *isec : inputSections) {
     // Sections marked no_dead_strip
     if (isec->flags & S_ATTR_NO_DEAD_STRIP) {
-      enqueue(isec);
+      enqueue(WorklistEntry{nullptr, isec, nullptr});
       continue;
     }
 
     // mod_init_funcs, mod_term_funcs sections
     if ((isec->flags & SECTION_TYPE) == S_MOD_INIT_FUNC_POINTERS ||
         (isec->flags & SECTION_TYPE) == S_MOD_TERM_FUNC_POINTERS) {
-      enqueue(isec);
+      enqueue(WorklistEntry{nullptr, isec, nullptr});
       continue;
     }
 

           continue;
 
         if (auto *s = r.referent.dyn_cast<Symbol *>())
-          addSym(s);
+          addSym(s, nullptr);
         else {
           auto *referentIsec = r.referent.get<InputSection *>();
           assert(!referentIsec->isCoalescedWeak());
-          enqueue(referentIsec);
+          enqueue({nullptr, referentIsec, nullptr});
         }
       }
       continue;

   do {
     // Mark things reachable from GC roots as live.
     while (!worklist.empty()) {
-      InputSection *s = worklist.pop_back_val();
-      assert(s->live && "We mark as live when pushing onto the worklist!");
+      WorklistEntry *entry = worklist.pop_back_val();
+      assert(entry->sec->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 : entry->sec->relocs) {
         if (auto *s = r.referent.dyn_cast<Symbol *>()) {
-          addSym(s);
+          addSym(s, entry);
         } else {
           auto *referentIsec = r.referent.get<InputSection *>();
           assert(!referentIsec->isCoalescedWeak());
-          enqueue(referentIsec);
+          enqueue({nullptr, referentIsec, entry});
         }
       }
     }

         else
           referentLive = r.referent.get<InputSection *>()->live;
         if (referentLive)
-          enqueue(isec);
+          enqueue({nullptr, isec, nullptr});  // XXX nullptr here is wrong
       }
     }
 

lld/MachO/Options.td

 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">,

lld/include/lld/Common/ErrorHandler.h

   void error(const Twine &msg, ErrorTag tag, ArrayRef<StringRef> args);
   LLVM_ATTRIBUTE_NORETURN void fatal(const Twine &msg);
   void log(const Twine &msg);
-  void message(const Twine &msg);
+  void message(const Twine &msg, llvm::raw_ostream &s);
   void warn(const Twine &msg);
 
   void reset() {

   errorHandler().fatal(msg);
 }
 inline void log(const Twine &msg) { errorHandler().log(msg); }
-inline void message(const Twine &msg) { errorHandler().message(msg); }
+inline void message(const Twine &msg, llvm::raw_ostream &s = outs()) {
+  errorHandler().message(msg, s);
+}
 inline void warn(const Twine &msg) { errorHandler().warn(msg); }
 inline uint64_t errorCount() { return errorHandler().errorCount; }
 

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 %t.o -o /dev/null
+.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
+  retq
+
+.subsections_via_symbols