[WebAssembly] Implement GC for imports

[ncw]

Summary

It's fairly straightforward - we just need a Live flag on the symbol to track whether undefined symbols were accessed or not.

[ruiu]

InputGlobal has a "Live" member, and this patch adds a new "Live" member to Symbol which seems odd to me. It feels like something isn't quite right...

wasm/MarkLive.cpp

43–45

nit: you can merge these two ifs.

wasm/Symbols.h

79–80

I don't think we should add a notion of "liveness" to symbols. It is easy to be confused, but "liveness" is for chunks, data, globals, etc, and symbols themselves are not subject of GC. I understand that since each wasm global have only one symbol associated with it, that distinction is ambiguous, but I still want to maintain that distinction to make things easy to understand.

[sbc100]

Nice!

I don't really like the yaml test case, but hopefully it will be shortlived.

wasm/Symbols.cpp

63

I think getChunk can now be removed and inlines into isLive and getLive, it think it will be more readable that wasy.

67

Maybe assert isUndefined here?

wasm/Symbols.h

79–80

But for undefined symbols we need to know which ones to write to the relocatable output. For undefined symbols there is no chunk.

We already have in in ELF/Symbols.h: unsigned Used : 1;

If you prefer we can give it the same name here for consistency.

I'm not sure there is any difference between Used and Live though, so it might be worth renaming the one in ELF?

[sbc100]

wasm/Symbols.cpp

67

Alternatively we might want to set this unconditionally at the top of the function?

In which case isLive becomes just return Live?

[ruiu]

wasm/Symbols.h

79–80

If symbol is referenced by someone else, we have to do something in some cases. E.g. we have to put it to the dynamic symbol table if it is being used. But that's different from garbage collection.

[ncw]

Thanks for the comments, I'll deal with those nits.

Would it be a good compromise to rename "Symbol::Live" to "Symbol::ImportLive"? That would make it clear that it's the imported function object that's being GC'd, not the Symbol itself. Even more strictly, I could move the Live bit to the UndefinedGlobal/UndefinedFunction/UndefinedData classes (although that's more mess code-wise it might be seen as clearer?).

wasm/Symbols.cpp

67

I'd have to check if that's possible, or it would break aliasing. Liveness isn't really a property of the Symbol, it conceptually is a property of the "thing" that the symbol points to. It's just that for undefined symbols there is no "thing". To me, it's cleaner to avoid getting/setting the Live bit on the Symbol except in the undefined case where we have to.

wasm/Symbols.h

79–80

I understand that since each wasm global have only one symbol associated with it, that distinction is ambiguous

On a side note - A Wasm global is just like any other symbol. There can be many Symbols for the InputGlobal just as there can be many Symbols aliasing the same InputFunction.

I agree that we don't want to GC symbols. I've added a Live bit to the Symbol, not in order to GC the symbol, but in order to GC the function/global object which is imported. The Symbol itself is not GC'ed, but in the case of undefined Symbols, there isn't any existing object to hold the "Live" flag. It has to go somewhere on the Symbol, although it could be renamed to "Used" or heavily commented to clarify.

Regardless of whether a symbol is used/live, it's always included in the symbol table - no pruning is being done there.

[sbc100]

wasm/Symbols.h

79–80

This is a little like the dynamic symbol table. Our imports a the moral equivalent right now of dynamic undefined symbols. We want to populate it only with those symbols that we use. This change as an incremental improvement makes sense to me.

79–80

I don't think that last statement is true is it?

If an undefined symbols it not used (or not live if you prefer), it should not appear in the symbol table, and it should not appear in the imports of the final binary.

[ncw]

Updated:

• rebased and fixed conflicts
• Move Live flag from Symbol to UndefinedFunction::ImportLive to clarify what it is that we're marking live
• small nits based on feedback

wasm/Symbols.cpp

63

I've inlined it if that's neater for you (and converted to switch after inlining), but it'll still be used in MarkLive

wasm/Symbols.h

79–80

Currently, symbol table is only written out when there's no GC, and the full contents of LLD's Symtab are written out. But you're right it might not be true in future if we were ever to write out a symtab from LLD for non-relocatable output.

[sbc100]

wasm/Symbols.cpp

71

I think this was nicer how you had it before. Why not just use a single bit on the symbol base class? Especially since we are about to add undefined data to the final output.. we don't want to repeat the ImportLive again.

I also don't have a problem with the Live bit of a symbol mirroring the Live bit on the segment it points too, I think both concepts are useful.

For this kind of switch case, I think we are moving towards just using dyn_cast<>.

[ncw]

wasm/Symbols.cpp

71

I know! But you can't please everyone... I pulled it out of Symbol and into the derived classes in order to try and please Rui's request to remove the Live bit from Symbol.

Would we all be happy to have an "ImportLive" bit in the Symbol base class?

(I used a switch just to avoid a six-way if chain...)

[ruiu]

Well, I know you guys want to add the notion of "liveness" to symbols, but I think that's sematnically not correct. Symbol is essentially a label attached to something, and they are not dead or alive themselves. What we mark and garbage collect is chunks. It even feels wrong to add markLive() to a symbol is not quite right. That shouldn't belong to symbol. Can you keep it in MarkLive.cpp?

[sbc100]

In D44313#1037653, @ruiu wrote:

Well, I know you guys want to add the notion of "liveness" to symbols, but I think that's sematnically not correct. Symbol is essentially a label attached to something, and they are not dead or alive themselves. What we mark and garbage collect is chunks. It even feels wrong to add markLive() to a symbol is not quite right. That shouldn't belong to symbol. Can you keep it in MarkLive.cpp?

OK, in this case we are using this information to build the imports (i.e. the dynamic symbols table) so perhaps if we go back to the idea that sections can be "Live" and symbols can be "Used", would that be ok with you? That would match the ELF linker better perhaps?

[ruiu]

Similarity to or disparity from ELF isn't that important, but perhaps yes, though I'm not 100% sure if it's the best way. "Used" is probably a bit ambiguous, so I'd rename it "Referenced" or something.

Also, I think that the current way of representing an imported symbol doesn't hit the sweet spot. IIUC, undefined symbols are used to represent imported symbols, but I believe we should have a dedicated symbol type for imported symbols. After resolving and before writing, we can read all .import files, find all symbols referenced by the files, and replace them with some kind of imported symbol type, so that we can handle undefined symbols as really undefined.

[ncw]

Thanks for that! OK, I'll update these reviews and nudge them forwards next week. I've just been very busy at work this week with a customer project, and nut been able to spend and time on wasm in the evenings at home.

[ncw]

Updated - sorry for the long wait!

I think this now represents the consensus? At least, I think I've made all the changes requested above.

It's now looking almost identical to the very first revision of the diff actually..!

Rebased, and changed to add a "Referenced" bit on the Symbol class.

[ncw]

It's been another fortnight on this issue - is it now ready to go?

I made the change Rui requested (as best I could understand it), and I think I've addressed all the comments Sam has added to this PR (although I'm aware that you weren't happy with the approach on another related PR, this change itself has so far met with approval, based on the comments above).

[sbc100]

Mostly this LGTM. I like the addition of markLive() to the symbol class, although I know ruiu has objections to it. I think it makes sense since it is symmetric with the existing isLive() (which has precedence in COFF/Symbols.h)

In terms of doing the marking as part of GC or not I think I'm OK with this change, although I don't really consider globals to be sections. I think there is a wider discussion to be had about the utility of --no-gc-sections for wasm and what exactly it means.

[ncw]

Thanks for the feedback! I'll merge in a week if I haven't heard anything more.

test/wasm/Inputs/undefined-globals.yaml

+--- !WASM
+FileHeader:
+  Version:         0x00000001
+Sections:
+  - Type:            TYPE
+    Signatures:
+      - Index:           0
+        ReturnType:      I64
+        ParamTypes:
+  - Type:            IMPORT
+    Imports:
+      - Module:          env
+        Field:           unused_undef_global
+        Kind:            GLOBAL
+        GlobalType:      I64
+        GlobalMutable:   true
+      - Module:          env
+        Field:           used_undef_global
+        Kind:            GLOBAL
+        GlobalType:      I64
+        GlobalMutable:   true
+  - Type:            FUNCTION
+    FunctionTypes:   [ 0 ]
+  - Type:            CODE
+    Functions:
+      - Index:           0
+        Locals:
+        Body:            2381808080000B
+    Relocations:
+      - Type:            R_WEBASSEMBLY_GLOBAL_INDEX_LEB
+        Index:           1
+        Offset:          0x00000004
+  - Type:            CUSTOM
+    Name:            linking
+    SymbolTable:
+      - Index:           0
+        Kind:            GLOBAL
+        Name:            unused_undef_global
+        Flags:           [ VISIBILITY_HIDDEN, UNDEFINED ]
+        Global:          0
+      - Index:           1
+        Kind:            GLOBAL
+        Name:            used_undef_global
+        Flags:           [ VISIBILITY_HIDDEN, UNDEFINED ]
+        Global:          1
+      - Index:           2
+        Kind:            FUNCTION
+        Name:            use_undef_global
+        Flags:           [ VISIBILITY_HIDDEN ]
+        Function:        0
+...

test/wasm/gc-imports.ll

+; RUN: llc -filetype=obj %s -o %t.o
+; RUN: yaml2obj %S/Inputs/undefined-globals.yaml -o %t_globals.o
+; RUN: wasm-ld -print-gc-sections --allow-undefined -o %t1.wasm %t.o %t_globals.o
+
+target triple = "wasm32-unknown-unknown-wasm"
+
+declare hidden i64 @unused_undef_function(i64 %arg)
+
+declare hidden i32 @used_undef_function()
+
+declare i64 @use_undef_global()
+
+define hidden void @_start() {
+entry:
+  call i32 @used_undef_function()
+  call i64 @use_undef_global()
+  ret void
+}
+
+; RUN: obj2yaml %t1.wasm | FileCheck %s
+
+; CHECK:        - Type:            TYPE
+; CHECK-NEXT:     Signatures:
+; CHECK-NEXT:       - Index:           0
+; CHECK-NEXT:         ReturnType:      I32
+; CHECK-NEXT:         ParamTypes:
+; CHECK-NEXT:       - Index:           1
+; CHECK-NEXT:         ReturnType:      NORESULT
+; CHECK-NEXT:         ParamTypes:
+; CHECK-NEXT:       - Index:           2
+; CHECK-NEXT:         ReturnType:      I64
+; CHECK-NEXT:         ParamTypes:
+; CHECK-NEXT:   - Type:            IMPORT
+; CHECK-NEXT:     Imports:
+; CHECK-NEXT:       - Module:          env
+; CHECK-NEXT:         Field:           used_undef_function
+; CHECK-NEXT:         Kind:            FUNCTION
+; CHECK-NEXT:         SigIndex:        0
+; CHECK-NEXT:       - Module:          env
+; CHECK-NEXT:         Field:           used_undef_global
+; CHECK-NEXT:         Kind:            GLOBAL
+; CHECK-NEXT:         GlobalType:      I64
+; CHECK-NEXT:         GlobalMutable:   true
+; CHECK-NEXT:   - Type:
+; CHECK:        - Type:            CUSTOM
+; CHECK-NEXT:     Name:            name
+; CHECK-NEXT:     FunctionNames:
+; CHECK-NEXT:       - Index:           0
+; CHECK-NEXT:         Name:            used_undef_function
+; CHECK-NEXT:       - Index:           1
+; CHECK-NEXT:         Name:            __wasm_call_ctors
+; CHECK-NEXT:       - Index:           2
+; CHECK-NEXT:         Name:            _start
+; CHECK-NEXT:       - Index:           3
+; CHECK-NEXT:         Name:            use_undef_global
+; CHECK-NEXT: ...
+
+; RUN: wasm-ld -print-gc-sections --no-gc-sections --allow-undefined \
+; RUN:     -o %t1.no-gc.wasm %t.o %t_globals.o
+; RUN: obj2yaml %t1.no-gc.wasm | FileCheck %s -check-prefix=NO-GC
+
+; NO-GC:        - Type:            TYPE
+; NO-GC-NEXT:     Signatures:
+; NO-GC-NEXT:       - Index:           0
+; NO-GC-NEXT:         ReturnType:      I32
+; NO-GC-NEXT:         ParamTypes:
+; NO-GC-NEXT:       - Index:           1
+; NO-GC-NEXT:         ReturnType:      I64
+; NO-GC-NEXT:         ParamTypes:
+; NO-GC-NEXT:           - I64
+; NO-GC-NEXT:       - Index:           2
+; NO-GC-NEXT:         ReturnType:      NORESULT
+; NO-GC-NEXT:         ParamTypes:
+; NO-GC-NEXT:       - Index:           3
+; NO-GC-NEXT:         ReturnType:      I64
+; NO-GC-NEXT:         ParamTypes:
+; NO-GC-NEXT:   - Type:            IMPORT
+; NO-GC-NEXT:     Imports:
+; NO-GC-NEXT:       - Module:          env
+; NO-GC-NEXT:         Field:           used_undef_function
+; NO-GC-NEXT:         Kind:            FUNCTION
+; NO-GC-NEXT:         SigIndex:        0
+; NO-GC-NEXT:       - Module:          env
+; NO-GC-NEXT:         Field:           unused_undef_function
+; NO-GC-NEXT:         Kind:            FUNCTION
+; NO-GC-NEXT:         SigIndex:        1
+; NO-GC-NEXT:       - Module:          env
+; NO-GC-NEXT:         Field:           unused_undef_global
+; NO-GC-NEXT:         Kind:            GLOBAL
+; NO-GC-NEXT:         GlobalType:      I64
+; NO-GC-NEXT:         GlobalMutable:   true
+; NO-GC-NEXT:       - Module:          env
+; NO-GC-NEXT:         Field:           used_undef_global
+; NO-GC-NEXT:         Kind:            GLOBAL
+; NO-GC-NEXT:         GlobalType:      I64
+; NO-GC-NEXT:         GlobalMutable:   true
+; NO-GC-NEXT:   - Type:
+; NO-GC:        - Type:            CUSTOM
+; NO-GC-NEXT:     Name:            name
+; NO-GC-NEXT:     FunctionNames:
+; NO-GC-NEXT:       - Index:           0
+; NO-GC-NEXT:         Name:            used_undef_function
+; NO-GC-NEXT:       - Index:           1
+; NO-GC-NEXT:         Name:            unused_undef_function
+; NO-GC-NEXT:       - Index:           2
+; NO-GC-NEXT:         Name:            __wasm_call_ctors
+; NO-GC-NEXT:       - Index:           3
+; NO-GC-NEXT:         Name:            _start
+; NO-GC-NEXT:       - Index:           4
+; NO-GC-NEXT:         Name:            use_undef_global
+; NO-GC-NEXT: ...

wasm/MarkLive.cpp

 void lld::wasm::markLive() {
   if (!Config->GcSections)
     return;
 
   DEBUG(dbgs() << "markLive\n");
   SmallVector<InputChunk *, 256> Q;
 
   auto Enqueue = [&](Symbol *Sym) {
-    if (!Sym)
+    if (!Sym || Sym->isLive())
       return;
-    InputChunk *Chunk = Sym->getChunk();
-    if (!Chunk || Chunk->Live)
-      return;
-    Chunk->Live = true;
+    Sym->markLive();
+    if (InputChunk *Chunk = Sym->getChunk())
       Q.push_back(Chunk);
   };
 
   // Add GC root symbols.
   if (!Config->Entry.empty())
     Enqueue(Symtab->find(Config->Entry));
   Enqueue(WasmSym::CallCtors);
 
   // By default we export all non-hidden, so they are gc roots too

wasm/Symbols.h

 //===- Symbols.h ------------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_WASM_SYMBOLS_H
 #define LLD_WASM_SYMBOLS_H
 
+#include "Config.h"
 #include "lld/Common/LLVM.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/Wasm.h"
 
 using llvm::object::Archive;
 using llvm::object::WasmSymbol;
 using llvm::wasm::WasmGlobal;
 using llvm::wasm::WasmGlobalType;
public:
   // Returns the symbol name.
   StringRef getName() const { return Name; }
 
   // Returns the file from which this symbol was created.
   InputFile *getFile() const { return File; }
 
   InputChunk *getChunk() const;
 
-  // Indicates that this symbol will be included in the final image.
+  // Indicates that the section or import for this symbol will be included in
+  // the final image.
   bool isLive() const;
 
+  // Marks the symbol's InputChunk as Live, so that it will be included in the
+  // final image.
+  void markLive();
+
   void setHidden(bool IsHidden);
 
   // Get/set the index in the output symbol table.  This is only used for
   // relocatable output.
   uint32_t getOutputSymbolIndex() const;
   void setOutputSymbolIndex(uint32_t Index);
 
   WasmSymbolType getWasmType() const;
 
 protected:
   Symbol(StringRef Name, Kind K, uint32_t Flags, InputFile *F)
-      : Name(Name), SymbolKind(K), Flags(Flags), File(F) {}
+      : Name(Name), SymbolKind(K), Flags(Flags), File(F),
+        Referenced(!Config->GcSections) {}
 
   StringRef Name;
   Kind SymbolKind;
   uint32_t Flags;
   InputFile *File;
   uint32_t OutputSymbolIndex = INVALID_INDEX;
+  bool Referenced = false;
 };
 
 class FunctionSymbol : public Symbol {
 public:
   static bool classof(const Symbol *S) {
     return S->kind() == DefinedFunctionKind ||
            S->kind() == UndefinedFunctionKind;
   }

wasm/Symbols.cpp

InputChunk *Symbol::getChunk() const {
   return nullptr;
 }
 
 bool Symbol::isLive() const {
   if (auto *G = dyn_cast<DefinedGlobal>(this))
     return G->Global->Live;
   if (InputChunk *C = getChunk())
     return C->Live;
-  // Assume any other kind of symbol is live.
-  return true;
+  return Referenced;
+}
+
+void Symbol::markLive() {
+  if (auto *G = dyn_cast<DefinedGlobal>(this))
+    G->Global->Live = true;
+  if (InputChunk *C = getChunk())
+    C->Live = true;
+  Referenced = true;
 }
 
 uint32_t Symbol::getOutputSymbolIndex() const {
   assert(OutputSymbolIndex != INVALID_INDEX);
   return OutputSymbolIndex;
 }
 
 void Symbol::setOutputSymbolIndex(uint32_t Index) {
   DEBUG(dbgs() << "setOutputSymbolIndex " << Name << " -> " << Index << "\n");
   assert(OutputSymbolIndex == INVALID_INDEX);
   OutputSymbolIndex = Index;
 }
 
 bool Symbol::isWeak() const {
   return (Flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK;
 }

wasm/Writer.cpp

 void Writer::calculateImports() {
   for (Symbol *Sym : Symtab->getSymbols()) {
     if (!Sym->isUndefined())
       continue;
     if (isa<DataSymbol>(Sym))
       continue;
     if (Sym->isWeak() && !Config->Relocatable)
       continue;
+    if (!Sym->isLive())
+      continue;
 
     DEBUG(dbgs() << "import: " << Sym->getName() << "\n");
     ImportedSymbols.emplace_back(Sym);
     if (auto *F = dyn_cast<FunctionSymbol>(Sym))
       F->setFunctionIndex(NumImportedFunctions++);
     else
       cast<GlobalSymbol>(Sym)->setGlobalIndex(NumImportedGlobals++);
   }
for (const WasmRelocation &Reloc : Chunk->getRelocations()) {
         if (Sym->hasTableIndex() || !Sym->hasFunctionIndex())
           continue;
         Sym->setTableIndex(TableIndex++);
         IndirectFunctions.emplace_back(Sym);
       } else if (Reloc.Type == R_WEBASSEMBLY_TYPE_INDEX_LEB) {
         // Mark target type as live
         File->TypeMap[Reloc.Index] = registerType(Types[Reloc.Index]);
         File->TypeIsUsed[Reloc.Index] = true;
-      } else if (Reloc.Type == R_WEBASSEMBLY_GLOBAL_INDEX_LEB) {
-        // Mark target global as live
-        GlobalSymbol *Sym = File->getGlobalSymbol(Reloc.Index);
-        if (auto *G = dyn_cast<DefinedGlobal>(Sym)) {
-          DEBUG(dbgs() << "marking global live: " << Sym->getName() << "\n");
-          G->Global->Live = true;
-        }
       }
     }
   };
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     DEBUG(dbgs() << "Handle relocs: " << File->getName() << "\n");
     for (InputChunk *Chunk : File->Functions)
       HandleRelocs(Chunk);