[WebAssembly] GC constructor functions in otherwise unused archive objects

[sunfish]

Summary

This allows __wasilibc_populate_libpreopen to be GC'd in more cases
where it isn't needed, including when linked from Rust's libstd.

[sbc100]

To be clear this change only relates to object files at are part of ar archives and are not part of the link? Perhaps mention that in the PR title/description.

lld/wasm/InputFiles.h

105

My understanding is that any file that is created as an ObjFile is by definition live. and that all files in symtab->objectFiles are also by definition live.

Archive files don't create any ObjFiles until they are pulled into the link for some reason (i.e. they are live).

What am I missing here?

[sunfish]

In D85062#2188643, @sbc100 wrote:

To be clear this change only relates to object files at are part of ar archives and are not part of the link? Perhaps mention that in the PR title/description.

Yes, this relates to functions in objects which don't, after GC, contribute any functions to the link. I've now added "archive" to the title.

lld/wasm/InputFiles.h

105

There are effectively two GC algorithms in wasm-ld today. The first selects the objects that aren't in archives, plus the objects in archives they (transitively) reference. The second one is MarkLive.cpp, which selects exported functions, plus functions they (transitively) reference.

What this patch is saying is, if a constructor function gets pulled in because its object is selected in the first phase, but MarkLive.cpp's GC determines that no functions in that object are transitively called from an export in the second phase, the constructor doesn't need to be called.

[sbc100]

lld/wasm/InputFiles.h

105

I see .. so something like this:

1. Transitive dependency pulls object out of archive.
2. Source of dependency turns out to not be live in the final link due to --gc-sections.
3. Object file should no longer be considered part of the link after all, reversing the decision made in (1).

If I'm understanding correctly, one possible problem with this is that is makes --gc-sections observable. I could get a static ctor that runs with --no-gc-sections but then is not run with --gc-sections.... maybe this is so subtle as not to matter? But I would normally expect those two builds with be identical in their behaviour.

[sunfish]

lld/wasm/InputFiles.h

105

That's correct.

You can get similar observable behavior changes from any optimization that can delete code, which can lead fewer object files being pulled in. Consider C code that does this:

int x = 0;
if (x) {
    foo();
}

Plain -O2 will remove the call to foo here. If that's the only call to foo and foo is defined in an object which has a static constructor, the constructor will run at -O0 and won't run at -O2. This patch has a similar effect.

This patch upholds the rule that if the constructor is defined in a .o file which contributes to the final link, it'll run. It's just doing more optimization before making that determination.

[sunfish]

• Reorganize the code a little so that we don't have to call mark multiple times.
• Fix a bug where we weren't considering calls from constructors as keeping other constructors live.
• Add a few more tests.

[sbc100]

lld/test/wasm/Inputs/ctor-ctor.s

14

Can we call this something less generic like myctor or test_ctor so its not confused with maybe keyword or magic symbol?

lld/test/wasm/Inputs/ctor-lib.s

6

What do you think about renaming usethis -> lib_func and bar -> unused_lib_func?

I think you can also from the .hidden lines in all these tests to keep them short.

lld/test/wasm/Inputs/ctor-start.s

4

I think you can drop the .section and .type lines for functions which i think makes the tests more readable.

7

Extra spaces there and in other .s files?

lld/test/wasm/ctor-gc-setup.test

11

Why not put both these in the same archive file? Seems like it would at least make the test a little more concise.

lld/wasm/InputFiles.h

63

How about a comment along the lines of. "An InputFile is considered live if any of the symbols defined by it are live"?

lld/wasm/MarkLive.cpp

62

So here we are detecting the first time a given object is marked as live and then marking its init functions at that time.

The guess this is inherently iterative since queuing the init functions creates more marking work?

72

isn't cast<> an equivalent way of saying these two lines?

(in which case this if body can probably just be one line)

113

Maybe move the above three lines of comment to the declaration of enqueueInitFunctions since it seems like a general comment not specific to this callsite.

lld/wasm/Writer.cpp

1115

I think !sym->isLive() is enough since all discarded symbols will be non-live.

oh. wait.. I think I forgot about --no-gc-sections in which case everything is live but stuff can still get discarded.

1116–1117

I guess you can drop this assert now.

[sunfish]

Address review feedback.

[sunfish]

lld/test/wasm/Inputs/ctor-start.s

7

These were tabs, because that's what LLVM emits. I've now changed them to single plain spaces.

lld/wasm/MarkLive.cpp

62

Yes, it's iterative in the same way that the broader mark-and-sweep is iterative. When it sees an edge to something that's already live, it doesn't traverse that edge.

[sunfish]

I've finished addressing the review comments, so this is now ready for review again.

[sbc100]

lgtm % test nits

lld/test/wasm/Inputs/ctor-setup-call-def.s

22

I've been putting these external declaration in column 0

lld/test/wasm/Inputs/ctor-setup.s

5

No need to .section for functions since each one implicitly gets its own one anyway.

[sbc100]

Looks like we have a specific emscripten test for this since it started failing on our llvm roller:
https://github.com/emscripten-core/emscripten/blob/bd8e5b5296721e33cfad98322e6b70b9985cfd2d/tests/test_other.py#L900

Was this change supposed to effect archive object included via --whole-archive too?

[sbc100]

Fix (I believe) is in https://reviews.llvm.org/D89290

[sunfish]

In D85062#2326618, @sbc100 wrote:

Fix (I believe) is in https://reviews.llvm.org/D89290

Oops, I accidentally raced here and posted https://reviews.llvm.org/D89293. Looks like our fixes are very similar, so I'll review yours and you can land whichever you prefer.

[sbc100]

Looks like there is bug here: https://bugs.llvm.org/show_bug.cgi?id=48156

lld/test/wasm/Inputs/ctor-ctor.s

+  .section  .text.def,"",@
+  .globl def
+def:
+  .functype def () -> ()
+  end_function
+
+  .section  .text.test_ctor,"",@
+  .globl test_ctor
+test_ctor:
+  .functype test_ctor () -> ()
+  end_function
+
+  .section  .init_array,"",@
+  .p2align  2
+  .int32 test_ctor

lld/test/wasm/Inputs/ctor-lib.s

+  .section  .text.lib_func,"",@
+  .globl  lib_func
+lib_func:
+  .functype lib_func () -> ()
+  end_function
+
+  .section  .text.unused_lib_func,"",@
+  .globl unused_lib_func
+unused_lib_func:
+  .functype unused_lib_func () -> ()
+  call def
+  end_function
+
+  .functype def () -> ()

lld/test/wasm/Inputs/ctor-setup-call-def.s

+# Like Inputs/ctor-setup.s, except it calls `def` instead of `lib_func`,
+# so it pulls in the .o file containing `ctor`.
+
+  .section  .text._start,"",@
+  .globl  _start
+_start:
+  .functype _start () -> ()
+  end_function
+
+  .section  .text.setup,"",@
+  .globl setup
+setup:
+  .functype setup () -> ()
+  call def
+  end_function
+
+  .section  .init_array,"",@
+  .p2align  2
+  .int32 setup
+
+.functype       def () -> ()

lld/test/wasm/Inputs/ctor-setup.s

+# Like Inputs/ctor-start.s, except it calls `lib_func` from a ctor
+# instead of from `_start`.
+
+  .globl  _start
+_start:
+  .functype _start () -> ()
+  end_function
+
+  .globl  setup
+setup:
+  .functype setup () -> ()
+  call  lib_func
+  end_function
+
+  .section  .init_array,"",@
+  .p2align  2
+  .int32  setup
+
+        .functype       lib_func () -> ()

lld/test/wasm/Inputs/ctor-start.s

+  .globl _start
+_start:
+  .functype _start () -> ()
+  call lib_func
+  end_function
+
+  .functype lib_func () -> ()

lld/test/wasm/ctor-gc-setup.test

+; Like ctor-gc.test, but main object calls a function from its constructor,
+; which shouldn't matter; `ctor` shouldn't be pulled in.
+;
+; RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %p/Inputs/ctor-ctor.s -o %t.ctor.o
+; RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %p/Inputs/ctor-lib.s -o %t.lib.o
+; RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %p/Inputs/ctor-setup.s -o %t.setup.o
+; RUN: rm -f %t.lib.a
+; RUN: llvm-ar rcs %t.lib.a %t.lib.o %t.ctor.o
+; RUN: wasm-ld %t.setup.o %t.lib.a -o %t.wasm
+; RUN: obj2yaml %t.wasm | FileCheck %s
+
+; CHECK-NOT: Name: test_ctor

lld/test/wasm/ctor-gc.test

+; Verify that constructors from a .o file which it initially depends on but
+; doesn't ultimately contribute to the final link are not included.
+;
+; RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %p/Inputs/ctor-ctor.s -o %t.ctor.o
+; RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %p/Inputs/ctor-lib.s -o %t.lib.o
+; RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %p/Inputs/ctor-start.s -o %t.start.o
+; RUN: rm -f %t.lib.a
+; RUN: llvm-ar rcs %t.lib.a %t.lib.o %t.ctor.o
+; RUN: wasm-ld %t.start.o %t.lib.a -o %t.wasm
+; RUN: obj2yaml %t.wasm | FileCheck %s
+
+; CHECK-NOT: __wasm_call_ctors

lld/test/wasm/ctor-no-gc.test

+; Like ctor-gc-setup.test, but it calls a different function, so it does pull
+; in the object containing `ctor`, so `ctor` is linked in.
+;
+; RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %p/Inputs/ctor-ctor.s -o %t.ctor.o
+; RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %p/Inputs/ctor-lib.s -o %t.lib.o
+; RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %p/Inputs/ctor-setup-call-def.s -o %t.setup-call-def.o
+; RUN: rm -f %t.lib.a
+; RUN: llvm-ar rcs %t.lib.a %t.lib.o %t.ctor.o
+; RUN: wasm-ld %t.setup-call-def.o %t.lib.a -o %t.wasm
+; RUN: obj2yaml %t.wasm | FileCheck %s
+
+; CHECK: Name: test_ctor

lld/wasm/InputFiles.h

public:
 
   // An archive file name if this file is created from an archive.
   std::string archiveName;
 
   ArrayRef<Symbol *> getSymbols() const { return symbols; }
 
   MutableArrayRef<Symbol *> getMutableSymbols() { return symbols; }
 
+  // An InputFile is considered live if any of the symbols defined by it
+  // are live.
+  void markLive() { live = true; }
+  bool isLive() const { return live; }
+
 protected:
-  InputFile(Kind k, MemoryBufferRef m) : mb(m), fileKind(k) {}
+  InputFile(Kind k, MemoryBufferRef m)
+      : mb(m), fileKind(k), live(!config->gcSections) {}
   MemoryBufferRef mb;
 
   // List of all symbols referenced or defined by this file.
   std::vector<Symbol *> symbols;
 
 private:
   const Kind fileKind;
+  bool live;
 };
 
 // .a file (ar archive)
 class ArchiveFile : public InputFile {
 public:
   explicit ArchiveFile(MemoryBufferRef m) : InputFile(ArchiveKind, m) {}
   static bool classof(const InputFile *f) { return f->kind() == ArchiveKind; }
 
   void addMember(const llvm::object::Archive::Symbol *sym);
 
   void parse();
 
 private:
   std::unique_ptr<llvm::object::Archive> file;
   llvm::DenseSet<uint64_t> seen;
 };
 
 // .o file (wasm object file)
 class ObjFile : public InputFile {
 public:
   explicit ObjFile(MemoryBufferRef m, StringRef archiveName)
       : InputFile(ObjectKind, m) {
     this->archiveName = std::string(archiveName);
+
+    // If this isn't part of an archive, it's eagerly linked, so mark it live.
+    if (archiveName.empty())
+      markLive();
   }
   static bool classof(const InputFile *f) { return f->kind() == ObjectKind; }
 
   void parse(bool ignoreComdats = false);
 
   // Returns the underlying wasm file.
   const WasmObjectFile *getWasmObj() const { return wasmObj.get(); }
 

 };
 
 // .bc file
 class BitcodeFile : public InputFile {
 public:
   explicit BitcodeFile(MemoryBufferRef m, StringRef archiveName)
       : InputFile(BitcodeKind, m) {
     this->archiveName = std::string(archiveName);
+
+    // If this isn't part of an archive, it's eagerly linked, so mark it live.
+    if (archiveName.empty())
+      markLive();
   }
   static bool classof(const InputFile *f) { return f->kind() == BitcodeKind; }
 
   void parse();
   std::unique_ptr<llvm::lto::InputFile> obj;
 
   // Set to true once LTO is complete in order prevent further bitcode objects
   // being added.

lld/wasm/MarkLive.cpp

 namespace {
 
 class MarkLive {
 public:
   void run();
 
 private:
   void enqueue(Symbol *sym);
+  void enqueueInitFunctions(const ObjFile *sym);
   void markSymbol(Symbol *sym);
   void mark();
   bool isCallCtorsLive();
 
   // A list of chunks to visit.
   SmallVector<InputChunk *, 256> queue;
 };
 
 } // namespace
 
 void MarkLive::enqueue(Symbol *sym) {
   if (!sym || sym->isLive())
     return;
   LLVM_DEBUG(dbgs() << "markLive: " << sym->getName() << "\n");
+
+  InputFile *file = sym->getFile();
+  bool needInitFunctions = file && !file->isLive() && sym->isDefined();
+
   sym->markLive();
+
+  // Mark ctor functions in the object that defines this symbol live.
+  // The ctor functions are all referenced by the synthetic callCtors
+  // function. However, this function does not contain relocations so we
+  // have to manually mark the ctors as live.
+  if (needInitFunctions)
+    enqueueInitFunctions(cast<ObjFile>(file));
+
   if (InputChunk *chunk = sym->getChunk())
     queue.push_back(chunk);
 }
 
+// The ctor functions are all referenced by the synthetic callCtors
+// function.  However, this function does not contain relocations so we
+// have to manually mark the ctors as live.
+void MarkLive::enqueueInitFunctions(const ObjFile *obj) {
+  const WasmLinkingData &l = obj->getWasmObj()->linkingData();
+  for (const WasmInitFunc &f : l.InitFunctions) {
+    auto *initSym = obj->getFunctionSymbol(f.Symbol);
+    if (!initSym->isDiscarded())
+      enqueue(initSym);
+  }
+}
+
 void MarkLive::run() {
   // Add GC root symbols.
   if (!config->entry.empty())
     enqueue(symtab->find(config->entry));
 
   // We need to preserve any no-strip or exported symbol
   for (Symbol *sym : symtab->getSymbols())
     if (sym->isNoStrip() || sym->isExported())
       enqueue(sym);
 
   // If we'll be calling the user's `__wasm_call_dtors` function, mark it live.
   if (Symbol *callDtors = WasmSym::callDtors)
     enqueue(callDtors);
 
-  // The ctor functions are all referenced by the synthetic callCtors
-  // function.  However, this function does not contain relocations so we
-  // have to manually mark the ctors as live.
-  for (const ObjFile *obj : symtab->objectFiles) {
-    const WasmLinkingData &l = obj->getWasmObj()->linkingData();
-    for (const WasmInitFunc &f : l.InitFunctions) {
-      auto *initSym = obj->getFunctionSymbol(f.Symbol);
-      if (!initSym->isDiscarded())
-        enqueue(initSym);
-    }
-  }
-
   // In Emscripten-style PIC, `__wasm_call_ctors` calls `__wasm_apply_relocs`.
   if (config->isPic)
     enqueue(WasmSym::applyRelocs);
 
-  // If we have any non-discarded init functions, mark `__wasm_call_ctors` as
-  // live so that we assign it an index and call it.
-  if (isCallCtorsLive())
-    enqueue(WasmSym::callCtors);
-
   if (config->sharedMemory && !config->shared)
     enqueue(WasmSym::initMemory);
 
+  // Enqueue constructors in objects explicitly live from the command-line.
+  for (const ObjFile *obj : symtab->objectFiles)
+    if (obj->isLive())
+      enqueueInitFunctions(obj);
+
   mark();
+
+  // If we have any non-discarded init functions, mark `__wasm_call_ctors` as
+  // live so that we assign it an index and call it.
+  if (isCallCtorsLive())
+    WasmSym::callCtors->markLive();
 }
 
 void MarkLive::mark() {
   // Follow relocations to mark all reachable chunks.
   while (!queue.empty()) {
     InputChunk *c = queue.pop_back_val();
 
     for (const WasmRelocation reloc : c->getRelocations()) {
bool MarkLive::isCallCtorsLive() {
   // `__wasm_apply_relocs`.
   if (config->isPic)
     return true;
 
   // If there are any init functions, mark `__wasm_call_ctors` live so that
   // it can call them.
   for (const ObjFile *file : symtab->objectFiles) {
     const WasmLinkingData &l = file->getWasmObj()->linkingData();
-    for (const WasmInitFunc &f : l.InitFunctions)
-      if (!file->getFunctionSymbol(f.Symbol)->isDiscarded())
+    for (const WasmInitFunc &f : l.InitFunctions) {
+      auto *sym = file->getFunctionSymbol(f.Symbol);
+      if (!sym->isDiscarded() && sym->isLive())
         return true;
     }
+  }
 
   return false;
 }
 
 } // namespace wasm
 } // namespace lld

lld/wasm/Symbols.cpp

if (auto *e = dyn_cast<DefinedEvent>(this))
     return e->event->live;
   if (InputChunk *c = getChunk())
     return c->live;
   return referenced;
 }
 
 void Symbol::markLive() {
   assert(!isDiscarded());
+  if (file != NULL)
+    file->markLive();
   if (auto *g = dyn_cast<DefinedGlobal>(this))
     g->global->live = true;
   if (auto *e = dyn_cast<DefinedEvent>(this))
     e->event->live = true;
   if (InputChunk *c = getChunk())
     c->live = true;
   referenced = true;
 }

lld/wasm/Writer.cpp

void Writer::calculateInitFunctions() {
   if (!config->relocatable && !WasmSym::callCtors->isLive())
     return;
 
   for (ObjFile *file : symtab->objectFiles) {
     const WasmLinkingData &l = file->getWasmObj()->linkingData();
     for (const WasmInitFunc &f : l.InitFunctions) {
       FunctionSymbol *sym = file->getFunctionSymbol(f.Symbol);
       // comdat exclusions can cause init functions be discarded.
-      if (sym->isDiscarded())
+      if (sym->isDiscarded() || !sym->isLive())
         continue;
-      assert(sym->isLive());
       if (sym->signature->Params.size() != 0)
         error("constructor functions cannot take arguments: " + toString(*sym));
       LLVM_DEBUG(dbgs() << "initFunctions: " << toString(*sym) << "\n");
       initFunctions.emplace_back(WasmInitEntry{sym, f.Priority});
     }
   }
 
   // Sort in order of priority (lowest first) so that they are called
   // in the correct order.