From a1e299f58b2340a3c452f567626ed4baa62f8818 Mon Sep 17 00:00:00 2001 From: Nicholas Wilson Date: Fri, 20 Apr 2018 17:18:06 +0000 Subject: [PATCH] [WebAssembly] Implement GC for imports Differential Revision: https://reviews.llvm.org/D44313 llvm-svn: 330454 --- lld/test/wasm/Inputs/undefined-globals.yaml | 51 +++++++++++++ lld/test/wasm/gc-imports.ll | 111 ++++++++++++++++++++++++++++ lld/wasm/MarkLive.cpp | 10 +-- lld/wasm/Symbols.cpp | 11 ++- lld/wasm/Symbols.h | 12 ++- lld/wasm/Writer.cpp | 9 +-- 6 files changed, 187 insertions(+), 17 deletions(-) create mode 100644 lld/test/wasm/Inputs/undefined-globals.yaml create mode 100644 lld/test/wasm/gc-imports.ll diff --git a/lld/test/wasm/Inputs/undefined-globals.yaml b/lld/test/wasm/Inputs/undefined-globals.yaml new file mode 100644 index 0000000..e9f2f4a --- /dev/null +++ b/lld/test/wasm/Inputs/undefined-globals.yaml @@ -0,0 +1,51 @@ +--- !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 +... diff --git a/lld/test/wasm/gc-imports.ll b/lld/test/wasm/gc-imports.ll new file mode 100644 index 0000000..d46b9c9 --- /dev/null +++ b/lld/test/wasm/gc-imports.ll @@ -0,0 +1,111 @@ +; 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: ... diff --git a/lld/wasm/MarkLive.cpp b/lld/wasm/MarkLive.cpp index 38ffbcb..2b30f6a 100644 --- a/lld/wasm/MarkLive.cpp +++ b/lld/wasm/MarkLive.cpp @@ -40,13 +40,11 @@ void lld::wasm::markLive() { SmallVector Q; auto Enqueue = [&](Symbol *Sym) { - if (!Sym) + if (!Sym || Sym->isLive()) return; - InputChunk *Chunk = Sym->getChunk(); - if (!Chunk || Chunk->Live) - return; - Chunk->Live = true; - Q.push_back(Chunk); + Sym->markLive(); + if (InputChunk *Chunk = Sym->getChunk()) + Q.push_back(Chunk); }; // Add GC root symbols. diff --git a/lld/wasm/Symbols.cpp b/lld/wasm/Symbols.cpp index bcebcdc..d20a590 100644 --- a/lld/wasm/Symbols.cpp +++ b/lld/wasm/Symbols.cpp @@ -52,8 +52,15 @@ bool Symbol::isLive() const { 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(this)) + G->Global->Live = true; + if (InputChunk *C = getChunk()) + C->Live = true; + Referenced = true; } uint32_t Symbol::getOutputSymbolIndex() const { diff --git a/lld/wasm/Symbols.h b/lld/wasm/Symbols.h index 92084f7..237a2d6 100644 --- a/lld/wasm/Symbols.h +++ b/lld/wasm/Symbols.h @@ -10,6 +10,7 @@ #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" @@ -71,9 +72,14 @@ public: 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 @@ -85,13 +91,15 @@ public: 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 { diff --git a/lld/wasm/Writer.cpp b/lld/wasm/Writer.cpp index 4a52b52..41aa165 100644 --- a/lld/wasm/Writer.cpp +++ b/lld/wasm/Writer.cpp @@ -697,6 +697,8 @@ void Writer::calculateImports() { continue; if (Sym->isWeak() && !Config->Relocatable) continue; + if (!Sym->isLive()) + continue; DEBUG(dbgs() << "import: " << Sym->getName() << "\n"); ImportedSymbols.emplace_back(Sym); @@ -825,13 +827,6 @@ void Writer::assignIndexes() { // 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(Sym)) { - DEBUG(dbgs() << "marking global live: " << Sym->getName() << "\n"); - G->Global->Live = true; - } } } }; -- 2.7.4