[WebAssembly] Implement -print-gc-sections to test global GC

[ncw]

Summary

We don't have any tests for GC of globals yet. I've therefore implemented -print-gc-sections for globals, and extended the tests to exercise it. I've also made it follow the --no-gc-sections flag, so the tests are consistent.

It does require the addition of a YAML file, since user-defined globals aren't accessible from LLC at the moment. It's better to have the test in there than not!

[ncw]

Improve test a bit

[ruiu]

wasm/Writer.cpp

790–791

I believe you added Config->GcSections because if GC is off, all globals are alive by default and therefore we don't need to set that bit at all. Is this correct? If so, please add a comment.

807

It seems a bit too late to do this kind of stuff, since this is a writer. Is there any way to detect liveness of globals earlier than it is now, move code to MarkLive, and also move this code to MarkLive?

[sbc100]

wasm/InputGlobal.h

55

Non of this is needed if you don't include globals in the output of --print-gc-section.

wasm/MarkLive.cpp

110 ↗

(On Diff #137779)

Can you make this a separate change?

wasm/Writer.cpp

790–791

I don't really consider what we are going here as GC of sections. Its more like we are building the sythentic type and global section, and we always do it precisely based on what is needed. There is no option to disable this, as there is no need to a more conservative approach AFAICT.

Perhaps it we rename Global->Live to Global->Used it will make the distinction more clear?

So I don't agree with this part of the change.

[ncw]

wasm/Writer.cpp

790–791

Globals are an externally-visible piece of linked output. The browser can tell whether globals were GC'ed or not, so it's very different to say building the TYPE section. That's purely a filesize compression, using the TypeIsUsed map. It's not GC as such, since the contents of the TYPE section are not visible as part of the module's "interface" (no way of telling if extra types were included or not).

But for globals, they really are usable/callable objects just like functions are. Hence --no-gc-sections ought to prevent them being stripped. They are part of the objects that the user passed to the linker, and requested to be included in the final output!

(To be honest, I slightly struggle to see whether --no-gc-sections has any good use-cases, in fact. Are there situations where you'd want it - maybe to include some functions in the indirect table, that are never called from the Wasm code but should be callable externally via an indirect call?)

790–791

I believe you added Config->GcSections because if GC is off, all globals are alive by default and therefore we don't need to set that bit at all. Is this correct? If so, please add a comment.

I added it here, so that globals behave the same as functions. This exact same check is made in MarkLive, so adding it here is simply removing a existing difference, rather than introducing something "weird". We currently don't have any tests at all for GC of globals, so when I added them to tests/wasm/gc-sections.ll the test started to look very odd. In a test file that exercises --gc-sections and --no-gc-sections for functions and data symbols, it would strange to assert that the same options don't have any effect on globals!

807

Yes, it can certainly be done in MarkLive, and I feel it really ought to be done in MarkLive. Sam was resistant to that though, so this change preserves the status quo.

In D44313 (which builds on this patch) I've moved all the GC into MarkLive, where I feel it belongs.

[ncw]

Updated: removed chunk from MarkLive, fixed conflicts on rebase.

Not sure how to resolve the discussion on this one... Rui suggested moving it to MarkLive to sit alongside the function GC, which I've done in D44313 rather than open that can of worms here. But Sam isn't too keen on that, and prefers doing global GC in a separate later pass, although the code for handling function/global GC looks essentially the same.

Really all this commit is trying to do is just add a simple test for global GC, and implement --print-gc-sections with the same behaviour as function GC, just so that the test output matches.

I had hoped to be able to merge this one without stirring up disagreement :( I'm sorry.

[ncw]

wasm/InputGlobal.h

55

True... but it's not a lot of code, and why would we support and test --print-gc-section for functions but not globals? I added it because otherwise the existing tests would look lopsided. It seems odd if the test has an assertion that does: "check that a function and a global were GC'd and the logging indicates that the function but not the global was GC'd".

wasm/MarkLive.cpp

110 ↗

(On Diff #137779)

Done, sorry, it's pulled out now.

[sbc100]

wasm/InputGlobal.h

55

There a couple of reasons I don't think this is needed/wanted. Firstly, I don't consider wasm globals to be sections. Secondly that building of types and globals section I chose not be contolled by the --gc-sections flag. Rather its always generated precisely, based on the inputs. In the future maybe we could revisit this, and maybe we want to completely remove --gc-section/--print-gc-sections from the wasm port, since we probably always want to enable them. However I think this incremental change muddies the water.

Perhaps once we have more use for wasm globals we can revisit? At least then we won't need to include the yaml test input.

[ncw]

wasm/InputGlobal.h

55

Hmm. It's linked to whether you're happy to move the GC of globals into MarkLive (as Rui suggested, and which would tidy up Writer).

I can do it - and keep globals as they are.. it's just going to mean that yet another block of MarkLive is going to get copy-and-pasted into Writer in D44313 (import GC). By the time we have chunk/global GC and import GC and print-gc-sections duplicated between MarkLive and Writer it's just getting progressively uglier keep two implementations going.

I realise you don't see it as a section... I just want to check you're happy with the implications. Because in order to keep the existing behaviour of doing global GC regardless of whether gc-sections is on, that implies not moving global GC to MarkLive in D44313 (which you hadn't objected to in that review).

[sbc100]

wasm/InputGlobal.h

55

I don't think I'd want to move this handling to markLive, at least no unless we completely remove the --no-gc-sections option and have markLive always called. Given that we are already processing relocations twice, once in markLive and once here, then I think it makes sense to only handle functions and data segments in markLive. I don't see any real urgency to unify these two.

Is see this code not so much as "mark live", more as "find and build the import table". Just like we use this same loop to build the indirect function table.

[ncw]

wasm/InputGlobal.h

55

In my defence - the sole purpose of the code in question is to set the Live bit on InputGlobal. (And markLive is there to set the Live bit on InputGlobal).

The urgency/immediate reason was simply that the Live/Used bit on a symbol is the same for globals as for functions. If we continue to handle InputGlobal::Live in Writer, we'd be in the awkward situation of doing GC for global imports in a different place to the InputGlobals.

What I'll do is rebase these GC patches onto master, and see how it looks just with each change in isolation rather than as a sequence of cumulative changes.

Thanks for your patience!

[ncw]

Updated: rebased.

Now there's nothing contentious, I think this one is safe to land too? It's been a loong time (weeks) since there was any movement on these LLD bugs. If you want me to come back and make further changes however, I'm happy to do that.

test/wasm/Inputs/globals.yaml

+--- !WASM
+FileHeader:
+  Version:         0x00000001
+Sections:
+  - Type:            TYPE
+    Signatures:
+      - Index:           0
+        ReturnType:      I64
+        ParamTypes:
+  - Type:            FUNCTION
+    FunctionTypes:   [ 0 ]
+  - Type:            GLOBAL
+    Globals:
+      - Index:       0
+        Type:        I64
+        Mutable:     true
+        InitExpr:
+          Opcode:          I64_CONST
+          Value:           123
+      - Index:       1
+        Type:        I64
+        Mutable:     true
+        InitExpr:
+          Opcode:          I64_CONST
+          Value:           456
+  - 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_global
+        Flags:           [ VISIBILITY_HIDDEN ]
+        Global:          0
+      - Index:           1
+        Kind:            GLOBAL
+        Name:            used_global
+        Flags:           [ VISIBILITY_HIDDEN ]
+        Global:          1
+      - Index:           2
+        Kind:            FUNCTION
+        Name:            use_global
+        Flags:           [ VISIBILITY_HIDDEN ]
+        Function:        0
+...

test/wasm/gc-sections.ll

 ; RUN: llc -filetype=obj %s -o %t.o
-; RUN: wasm-ld -print-gc-sections -o %t1.wasm %t.o | FileCheck %s -check-prefix=PRINT-GC
+; RUN: yaml2obj %S/Inputs/globals.yaml -o %t_globals.o
+; RUN: wasm-ld -print-gc-sections -o %t1.wasm %t.o %t_globals.o | \
+; RUN:     FileCheck %s -check-prefix=PRINT-GC
 ; PRINT-GC: removing unused section {{.*}}:(unused_function)
 ; PRINT-GC-NOT: removing unused section {{.*}}:(used_function)
 ; PRINT-GC: removing unused section {{.*}}:(.data.unused_data)
 ; PRINT-GC-NOT: removing unused section {{.*}}:(.data.used_data)
+; PRINT-GC: removing unused section {{.*}}:(unused_global)
+; PRINT-GC-NOT: removing unused section {{.*}}:(used_global)
 
 target triple = "wasm32-unknown-unknown-wasm"
 
 @unused_data = hidden global i64 1, align 4
 @used_data = hidden global i32 2, align 4
 
-define hidden i64 @unused_function() {
+define hidden i64 @unused_function(i64 %arg) {
   %1 = load i64, i64* @unused_data, align 4
   ret i64 %1
 }
 
 define hidden i32 @used_function() {
   %1 = load i32, i32* @used_data, align 4
   ret i32 %1
 }
 
+declare i64 @use_global()
+
 define hidden void @_start() {
 entry:
   call i32 @used_function()
+  call i64 @use_global()
   ret void
 }
 
 ; RUN: obj2yaml %t1.wasm | FileCheck %s
 
 ; CHECK:        - Type:            TYPE
-; CHECK-NEXT:     Signatures:      
+; CHECK-NEXT:     Signatures:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         ReturnType:      NORESULT
-; CHECK-NEXT:         ParamTypes:      
+; CHECK-NEXT:         ParamTypes:
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         ReturnType:      I32
-; CHECK-NEXT:         ParamTypes:      
+; CHECK-NEXT:         ParamTypes:
+; CHECK-NEXT:       - Index:           2
+; CHECK-NEXT:         ReturnType:      I64
+; CHECK-NEXT:         ParamTypes:
 ; CHECK-NEXT:   - Type:            FUNCTION
 
+; CHECK:        - Type:            GLOBAL
+; CHECK-NEXT:     Globals:
+; CHECK-NEXT:       - Index:           0
+; CHECK-NEXT:         Type:            I32
+; CHECK-NEXT:         Mutable:         true
+; CHECK-NEXT:         InitExpr:
+; CHECK-NEXT:           Opcode:          I32_CONST
+; CHECK-NEXT:           Value:           66576
+; CHECK-NEXT:       - Index:       1
+; CHECK-NEXT:         Type:        I64
+; CHECK-NEXT:         Mutable:     true
+; CHECK-NEXT:         InitExpr:
+; CHECK-NEXT:           Opcode:          I64_CONST
+; CHECK-NEXT:           Value:           456
+
 ; CHECK:        - Type:            DATA
 ; CHECK-NEXT:     Segments:        
 ; CHECK-NEXT:       - SectionOffset:   7
 ; CHECK-NEXT:         MemoryIndex:     0
 ; CHECK-NEXT:         Offset:          
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           1024
 ; CHECK-NEXT:         Content:         '02000000'
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            name
 ; CHECK-NEXT:     FunctionNames:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Name:            __wasm_call_ctors
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         Name:            used_function
 ; CHECK-NEXT:       - Index:           2
 ; CHECK-NEXT:         Name:            _start
+; CHECK-NEXT:       - Index:           3
+; CHECK-NEXT:         Name:            use_global
 ; CHECK-NEXT: ...
 
-; RUN: wasm-ld -print-gc-sections --no-gc-sections -o %t1.no-gc.wasm %t.o
+; RUN: wasm-ld -print-gc-sections --no-gc-sections -o %t1.no-gc.wasm \
+; RUN:     %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:     Signatures:
 ; NO-GC-NEXT:       - Index:           0
 ; NO-GC-NEXT:         ReturnType:      NORESULT
 ; NO-GC-NEXT:         ParamTypes:
 ; NO-GC-NEXT:       - Index:           1
 ; NO-GC-NEXT:         ReturnType:      I64
-; NO-GC-NEXT:         ParamTypes:      
+; NO-GC-NEXT:         ParamTypes:
+; NO-GC-NEXT:           - I64
 ; NO-GC-NEXT:       - Index:           2
 ; NO-GC-NEXT:         ReturnType:      I32
-; NO-GC-NEXT:         ParamTypes:      
+; NO-GC-NEXT:         ParamTypes:
+; NO-GC-NEXT:       - Index:           3
+; NO-GC-NEXT:         ReturnType:      I64
+; NO-GC-NEXT:         ParamTypes:
 ; NO-GC-NEXT:   - Type:            FUNCTION
 
+; NO-GC:        - Type:            GLOBAL
+; NO-GC-NEXT:     Globals:
+; NO-GC-NEXT:       - Index:           0
+; NO-GC-NEXT:         Type:            I32
+; NO-GC-NEXT:         Mutable:         true
+; NO-GC-NEXT:         InitExpr:
+; NO-GC-NEXT:           Opcode:          I32_CONST
+; NO-GC-NEXT:           Value:           66576
+; NO-GC-NEXT:       - Index:       1
+; NO-GC-NEXT:         Type:        I64
+; NO-GC-NEXT:         Mutable:     true
+; NO-GC-NEXT:         InitExpr:
+; NO-GC-NEXT:           Opcode:          I64_CONST
+; NO-GC-NEXT:           Value:           123
+; NO-GC-NEXT:       - Index:       2
+; NO-GC-NEXT:         Type:        I64
+; NO-GC-NEXT:         Mutable:     true
+; NO-GC-NEXT:         InitExpr:
+; NO-GC-NEXT:           Opcode:          I64_CONST
+; NO-GC-NEXT:           Value:           456
+
 ; NO-GC:        - Type:            DATA
 ; NO-GC-NEXT:     Segments:        
 ; NO-GC-NEXT:       - SectionOffset:   7
 ; NO-GC-NEXT:         MemoryIndex:     0
 ; NO-GC-NEXT:         Offset:          
 ; NO-GC-NEXT:           Opcode:          I32_CONST
 ; NO-GC-NEXT:           Value:           1024
 ; NO-GC-NEXT:         Content:         '010000000000000002000000'
 ; NO-GC-NEXT:   - Type:            CUSTOM
 ; NO-GC-NEXT:     Name:            name
 ; NO-GC-NEXT:     FunctionNames:
 ; NO-GC-NEXT:       - Index:           0
 ; NO-GC-NEXT:         Name:            __wasm_call_ctors
 ; NO-GC-NEXT:       - Index:           1
 ; NO-GC-NEXT:         Name:            unused_function
 ; NO-GC-NEXT:       - Index:           2
 ; NO-GC-NEXT:         Name:            used_function
 ; NO-GC-NEXT:       - Index:           3
 ; NO-GC-NEXT:         Name:            _start
+; NO-GC-NEXT:       - Index:           4
+; NO-GC-NEXT:         Name:            use_global
 ; NO-GC-NEXT: ...
 
 ; RUN: not wasm-ld --gc-sections --relocatable -o %t1.no-gc.wasm %t.o 2>&1 | FileCheck %s -check-prefix=CHECK-ERROR
 ; CHECK-ERROR: wasm-ld: error: -r and --gc-sections may not be used together

wasm/Driver.cpp

void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   if (!Config->Relocatable) {
     // Can't export the SP right now because it's mutable, and mutable
     // globals aren't yet supported in the official binary format.
     // TODO(sbc): Remove WASM_SYMBOL_VISIBILITY_HIDDEN if/when the
     // "mutable global" proposal is accepted.
     StackPointerGlobal.Type = {WASM_TYPE_I32, true};
     StackPointerGlobal.InitExpr.Value.Int32 = 0;
     StackPointerGlobal.InitExpr.Opcode = WASM_OPCODE_I32_CONST;
-    InputGlobal *StackPointer = make<InputGlobal>(StackPointerGlobal);
+    StackPointerGlobal.Name = "__stack_pointer";
+    InputGlobal *StackPointer = make<InputGlobal>(StackPointerGlobal, nullptr);
     StackPointer->Live = true;
 
     static WasmSignature NullSignature = {{}, WASM_TYPE_NORESULT};
 
     // Add synthetic symbols before any others
     WasmSym::CallCtors = Symtab->addSyntheticFunction(
         "__wasm_call_ctors", WASM_SYMBOL_VISIBILITY_HIDDEN,
         make<SyntheticFunction>(NullSignature, "__wasm_call_ctors"));

wasm/InputFiles.cpp

for (size_t I = 0, E = Funcs.size(); I != E; ++I) {
     InputFunction *F =
         make<InputFunction>(Types[FuncTypes[I]], &Funcs[I], this);
     F->copyRelocations(*CodeSection);
     Functions.emplace_back(F);
   }
 
   // Populate `Globals`.
   for (const WasmGlobal &G : WasmObj->globals())
-    Globals.emplace_back(make<InputGlobal>(G));
+    Globals.emplace_back(make<InputGlobal>(G, this));
 
   // Populate `Symbols` based on the WasmSymbols in the object.
   Symbols.reserve(WasmObj->getNumberOfSymbols());
   for (const SymbolRef &Sym : WasmObj->symbols()) {
     const WasmSymbol &WasmSym = WasmObj->getWasmSymbol(Sym.getRawDataRefImpl());
     if (Symbol *Sym = createDefined(WasmSym))
       Symbols.push_back(Sym);
     else

wasm/InputGlobal.h

 
 namespace lld {
 namespace wasm {
 
 // Represents a single Wasm Global Variable within an input file. These are
 // combined to form the final GLOBALS section.
 class InputGlobal {
 public:
-  InputGlobal(const WasmGlobal &G) : Global(G) {}
+  InputGlobal(const WasmGlobal &G, ObjFile *F)
+      : File(F), Global(G), Live(!Config->GcSections) {}
 
+  StringRef getName() const { return Global.Name; }
   const WasmGlobalType &getType() const { return Global.Type; }
 
   uint32_t getGlobalIndex() const { return GlobalIndex.getValue(); }
   bool hasGlobalIndex() const { return GlobalIndex.hasValue(); }
   void setGlobalIndex(uint32_t Index) {
     assert(!hasGlobalIndex());
     GlobalIndex = Index;
   }
 
-  bool Live = false;
-
+  ObjFile *File;
   WasmGlobal Global;
 
+  bool Live = false;
+
 protected:
   llvm::Optional<uint32_t> GlobalIndex;
 };
 
 } // namespace wasm
 
+inline std::string toString(const wasm::InputGlobal *G) {
+  return (toString(G->File) + ":(" + G->getName() + ")").str();
+}
+
 } // namespace lld
 
 #endif // LLD_WASM_INPUT_GLOBAL_H

wasm/Writer.cpp

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) {
+      } else if (Reloc.Type == R_WEBASSEMBLY_GLOBAL_INDEX_LEB &&
+                 Config->GcSections) {
         // 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");
+        if (auto *G = dyn_cast<DefinedGlobal>(Sym))
           G->Global->Live = true;
-        }
-      }
-    }
   };
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     DEBUG(dbgs() << "Handle relocs: " << File->getName() << "\n");
     for (InputChunk *Chunk : File->Functions)
       HandleRelocs(Chunk);
     for (InputChunk *Chunk : File->Segments)
       HandleRelocs(Chunk);
   }
 
+  if (Config->PrintGcSections) {
+    for (const ObjFile *Obj : Symtab->ObjectFiles) {
+      for (InputGlobal *G : Obj->Globals)
+        if (!G->Live)
+          message("removing unused section " + toString(G));
+    }
+    for (InputGlobal *G : Symtab->SyntheticGlobals)
+      if (!G->Live)
+        message("removing unused section " + toString(G));
+  }
+
   uint32_t GlobalIndex = NumImportedGlobals + InputGlobals.size();
   auto AddDefinedGlobal = [&](InputGlobal *Global) {
     if (Global->Live) {
       DEBUG(dbgs() << "AddDefinedGlobal: " << GlobalIndex << "\n");
       Global->setGlobalIndex(GlobalIndex++);
       InputGlobals.push_back(Global);
     }
   };