Index: lld/test/wasm/duplicate-function-imports.s =================================================================== --- /dev/null +++ lld/test/wasm/duplicate-function-imports.s @@ -0,0 +1,57 @@ +# RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %s -o %t.o +# RUN: wasm-ld -o %t1.wasm %t.o +# RUN: obj2yaml %t1.wasm | FileCheck %s + +.globl f1 +.import_module f1, env +.import_name f1, f +.functype f1 () -> (i32) + +# Same import module/name/type as `f1`, should be de-duped. +.globl f2 +.import_module f2, env +.import_name f2, f +.functype f2 () -> (i32) + +# Same import module/name, but different type. Should not be de-duped. +.globl f3 +.import_module f3, env +.import_name f3, f +.functype f3 () -> (f32) + +.globl _start +_start: + .functype _start () -> () + call f1 + drop + call f2 + drop + call f3 + drop + end_function + + +# CHECK: - Type: TYPE +# CHECK-NEXT: Signatures: +# CHECK-NEXT: - Index: 0 +# CHECK-NEXT: ParamTypes: [] +# CHECK-NEXT: ReturnTypes: +# CHECK-NEXT: - I32 +# CHECK-NEXT: - Index: 1 +# CHECK-NEXT: ParamTypes: [] +# CHECK-NEXT: ReturnTypes: +# CHECK-NEXT: - F32 +# CHECK-NEXT: - Index: 2 +# CHECK-NEXT: ParamTypes: [] +# CHECK-NEXT: ReturnTypes: [] +# CHECK-NEXT: - Type: IMPORT +# CHECK-NEXT: Imports: +# CHECK-NEXT: - Module: env +# CHECK-NEXT: Field: f +# CHECK-NEXT: Kind: FUNCTION +# CHECK-NEXT: SigIndex: 0 +# CHECK-NEXT: - Module: env +# CHECK-NEXT: Field: f +# CHECK-NEXT: Kind: FUNCTION +# CHECK-NEXT: SigIndex: 1 +# CHECK-NEXT: - Type: Index: lld/test/wasm/duplicate-global-imports.s =================================================================== --- /dev/null +++ lld/test/wasm/duplicate-global-imports.s @@ -0,0 +1,69 @@ +# RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %s -o %t.o +# RUN: wasm-ld --no-check-features -o %t1.wasm %t.o +# RUN: obj2yaml %t1.wasm | FileCheck %s + +.global g1 +.import_module g1, env +.import_name g1, g +.globaltype g1, i64, immutable + +# Same import module/name/type as `g1`, should be de-duped. +.global g2 +.import_module g2, env +.import_name g2, g +.globaltype g2, i64, immutable + +# Imported as an i32 instead of i64, so should not be de-duped. +.global g3 +.import_module g3, env +.import_name g3, g +.globaltype g3, i32, immutable + +# Imported as mutable instead of immutable, so should not be de-duped. +.global g4 +.import_module g4, env +.import_name g4, g +.globaltype g4, i64 + +.globl _start +_start: + .functype _start () -> () + global.get g1 + drop + global.get g2 + drop + global.get g3 + drop + global.get g4 + drop + end_function + + +# CHECK: - Type: IMPORT +# CHECK-NEXT: Imports: +# CHECK-NEXT: - Module: env +# CHECK-NEXT: Field: g +# CHECK-NEXT: Kind: GLOBAL +# CHECK-NEXT: GlobalType: I64 +# CHECK-NEXT: GlobalMutable: false +# CHECK-NEXT: - Module: env +# CHECK-NEXT: Field: g +# CHECK-NEXT: Kind: GLOBAL +# CHECK-NEXT: GlobalType: I32 +# CHECK-NEXT: GlobalMutable: false +# CHECK-NEXT: - Module: env +# CHECK-NEXT: Field: g +# CHECK-NEXT: Kind: GLOBAL +# CHECK-NEXT: GlobalType: I64 +# CHECK-NEXT: GlobalMutable: true +# CHECK-NEXT: - Type: + +# CHECK: GlobalNames: +# CHECK-NEXT: - Index: 0 +# CHECK-NEXT: Name: g1 +# CHECK-NEXT: - Index: 1 +# CHECK-NEXT: Name: g3 +# CHECK-NEXT: - Index: 2 +# CHECK-NEXT: Name: g4 +# CHECK-NEXT: - Index: 3 +# CHECK-NEXT: Name: __stack_pointer Index: lld/test/wasm/duplicate-table-imports.s =================================================================== --- /dev/null +++ lld/test/wasm/duplicate-table-imports.s @@ -0,0 +1,94 @@ +# RUN: llvm-mc -mattr=+reference-types -triple=wasm32-unknown-unknown -filetype=obj -o %t.o %s +# RUN: wasm-ld --no-entry --export-all --allow-undefined -o %t1.wasm %t.o +# RUN: obj2yaml %t1.wasm | FileCheck %s + +.globl t1 +.import_module t1, env +.import_name t1, t +.tabletype t1, funcref + +# Same import module/name/type as `t1`, should be de-duped. +.globl t2 +.import_module t2, env +.import_name t2, t +.tabletype t2, funcref + +# Imported as an externref instead of funcref, so should not be de-duped. +.globl t3 +.import_module t3, env +.import_name t3, t +.tabletype t3, externref + +.globl read_funcref_1 +read_funcref_1: + .functype read_funcref_1 () -> (funcref) + i32.const 0 + table.get t1 + end_function + +.globl read_funcref_2 +read_funcref_2: + .functype read_funcref_2 () -> (funcref) + i32.const 0 + table.get t2 + end_function + +.globl read_externref +read_externref: + .functype read_externref () -> (externref) + i32.const 0 + table.get t3 + end_function + +# XXX: the second imported table has index 1, not 0. I've verified by hand (with +# `wasm2wat`) that the resulting Wasm file is correct: `t3` does end up at index +# 1 and our `read_*` functions contain `table.get` instructions using the proper +# table index immediates. This is also asserted (less legibly) in the hexdump of +# their code bodies below. It looks like there's a bug in how `obj2yaml` +# disassembles multiple table imports. + +# CHECK: - Type: IMPORT +# CHECK-NEXT: Imports: +# CHECK-NEXT: - Module: env +# CHECK-NEXT: Field: t +# CHECK-NEXT: Kind: TABLE +# CHECK-NEXT: Table: +# CHECK-NEXT: Index: 0 +# CHECK-NEXT: ElemType: FUNCREF +# CHECK-NEXT: Limits: +# CHECK-NEXT: Minimum: 0x0 +# CHECK-NEXT: - Module: env +# CHECK-NEXT: Field: t +# CHECK-NEXT: Kind: TABLE +# CHECK-NEXT: Table: +# CHECK-NEXT: Index: 0 +# CHECK-NEXT: ElemType: EXTERNREF +# CHECK-NEXT: Limits: +# CHECK-NEXT: Minimum: 0x0 +# CHECK-NEXT: - Type: + +# CHECK: - Type: CODE +# CHECK-NEXT: Functions: +# CHECK-NEXT: - Index: 0 +# CHECK-NEXT: Locals: [] +# CHECK-NEXT: Body: 0B +# CHECK-NEXT: - Index: 1 +# CHECK-NEXT: Locals: [] +# CHECK-NEXT: Body: 41002580808080000B +# CHECK-NEXT: - Index: 2 +# CHECK-NEXT: Locals: [] +# CHECK-NEXT: Body: 41002580808080000B +# CHECK-NEXT: - Index: 3 +# CHECK-NEXT: Locals: [] +# CHECK-NEXT: Body: 41002581808080000B +# 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: read_funcref_1 +# CHECK-NEXT: - Index: 2 +# CHECK-NEXT: Name: read_funcref_2 +# CHECK-NEXT: - Index: 3 +# CHECK-NEXT: Name: read_externref Index: lld/wasm/SyntheticSections.h =================================================================== --- lld/wasm/SyntheticSections.h +++ lld/wasm/SyntheticSections.h @@ -96,6 +96,68 @@ llvm::DenseMap typeIndices; }; +/** + * A key for some kind of imported entity of type `T`. + * + * Used when de-duplicating imports. + */ +template struct ImportKey { +public: + enum class State { Plain, Empty, Tombstone }; + +public: + T type; + llvm::Optional importModule; + llvm::Optional importName; + State state; + +public: + ImportKey(T type) : type(type), state(State::Plain) {} + ImportKey(T type, State state) : type(type), state(state) {} + ImportKey(T type, llvm::Optional importModule, + llvm::Optional importName) + : type(type), importModule(importModule), importName(importName), + state(State::Plain) {} +}; + +template +inline bool operator==(const ImportKey &lhs, const ImportKey &rhs) { + return lhs.state == rhs.state && lhs.importModule == rhs.importModule && + lhs.importName == rhs.importName && lhs.type == rhs.type; +} + +} // namespace wasm +} // namespace lld + +// `ImportKey` can be used as a key in a `DenseMap` if `T` can be used as a +// key in a `DenseMap`. +template struct llvm::DenseMapInfo> { + static lld::wasm::ImportKey getEmptyKey() { + typename lld::wasm::ImportKey key(llvm::DenseMapInfo::getEmptyKey()); + key.state = lld::wasm::ImportKey::State::Empty; + return key; + } + static lld::wasm::ImportKey getTombstoneKey() { + typename lld::wasm::ImportKey key(llvm::DenseMapInfo::getEmptyKey()); + key.state = lld::wasm::ImportKey::State::Tombstone; + return key; + } + static unsigned getHashValue(const lld::wasm::ImportKey &key) { + uintptr_t hash = hash_value(key.importModule); + hash = hash_combine(hash, key.importName); + hash = hash_combine(hash, llvm::DenseMapInfo::getHashValue(key.type)); + hash = hash_combine(hash, key.state); + return hash; + } + static bool isEqual(const lld::wasm::ImportKey &lhs, + const lld::wasm::ImportKey &rhs) { + return lhs == rhs; + } +}; + +namespace lld { +namespace wasm { + class ImportSection : public SyntheticSection { public: ImportSection() : SyntheticSection(llvm::wasm::WASM_SEC_IMPORT) {} @@ -131,6 +193,9 @@ unsigned numImportedFunctions = 0; unsigned numImportedTags = 0; unsigned numImportedTables = 0; + llvm::DenseMap, uint32_t> importedGlobals; + llvm::DenseMap, uint32_t> importedFunctions; + llvm::DenseMap, uint32_t> importedTables; }; class FunctionSection : public SyntheticSection { Index: lld/wasm/SyntheticSections.cpp =================================================================== --- lld/wasm/SyntheticSections.cpp +++ lld/wasm/SyntheticSections.cpp @@ -107,17 +107,61 @@ gotSymbols.push_back(sym); } +template +static void getImportModuleAndName(Symbol *sym, + llvm::Optional *outModule, + llvm::Optional *outName) { + if (auto *undef = dyn_cast(sym)) { + *outModule = undef->importModule ? *undef->importModule : defaultModule; + *outName = undef->importName ? *undef->importName : sym->getName(); + } else { + *outModule = defaultModule; + *outName = sym->getName(); + } +} + void ImportSection::addImport(Symbol *sym) { assert(!isSealed); - importedSymbols.emplace_back(sym); - if (auto *f = dyn_cast(sym)) - f->setFunctionIndex(numImportedFunctions++); - else if (auto *g = dyn_cast(sym)) - g->setGlobalIndex(numImportedGlobals++); - else if (auto *t = dyn_cast(sym)) + llvm::Optional module; + llvm::Optional name; + if (auto *f = dyn_cast(sym)) { + getImportModuleAndName(sym, &module, &name); + ImportKey key(*(f->getSignature()), module, name); + auto entry = + importedFunctions.try_emplace(key, numImportedFunctions); + if (entry.second) { + importedSymbols.emplace_back(sym); + f->setFunctionIndex(numImportedFunctions++); + } else { + f->setFunctionIndex(entry.first->second); + } + } else if (auto *g = dyn_cast(sym)) { + getImportModuleAndName(sym, &module, &name); + ImportKey key(*(g->getGlobalType()), module, name); + auto entry = importedGlobals.try_emplace(key, numImportedGlobals); + if (entry.second) { + importedSymbols.emplace_back(sym); + g->setGlobalIndex(numImportedGlobals++); + } else { + g->setGlobalIndex(entry.first->second); + } + } else if (auto *t = dyn_cast(sym)) { + // NB: There's currently only one possible kind of tag, and no + // `UndefinedTag`, so we don't bother de-duplicating tag imports. + importedSymbols.emplace_back(sym); t->setTagIndex(numImportedTags++); - else - cast(sym)->setTableNumber(numImportedTables++); + } else { + auto *table = cast(sym); + getImportModuleAndName(sym, &module, &name); + ImportKey key(*(table->getTableType()), module, name); + auto entry = importedTables.try_emplace(key, numImportedTables); + if (entry.second) { + importedSymbols.emplace_back(sym); + table->setTableNumber(numImportedTables++); + } else { + table->setTableNumber(entry.first->second); + } + } } void ImportSection::writeBody() { Index: llvm/include/llvm/BinaryFormat/Wasm.h =================================================================== --- llvm/include/llvm/BinaryFormat/Wasm.h +++ llvm/include/llvm/BinaryFormat/Wasm.h @@ -67,11 +67,20 @@ uint64_t Maximum; }; +inline bool operator==(const WasmLimits &LHS, const WasmLimits &RHS) { + return LHS.Flags == RHS.Flags && LHS.Minimum == RHS.Minimum && + LHS.Maximum == RHS.Maximum; +} + struct WasmTableType { uint8_t ElemType; WasmLimits Limits; }; +inline bool operator==(const WasmTableType &LHS, const WasmTableType &RHS) { + return LHS.ElemType == RHS.ElemType && LHS.Limits == RHS.Limits; +} + struct WasmTable { uint32_t Index; WasmTableType Type; Index: llvm/include/llvm/BinaryFormat/WasmTraits.h =================================================================== --- llvm/include/llvm/BinaryFormat/WasmTraits.h +++ llvm/include/llvm/BinaryFormat/WasmTraits.h @@ -63,6 +63,47 @@ } }; +// Traits for using WasmLimits in a DenseMap +template <> struct DenseMapInfo { + static wasm::WasmLimits getEmptyKey() { + return wasm::WasmLimits{0xff, 0xff, 0xff}; + } + static wasm::WasmLimits getTombstoneKey() { + return wasm::WasmLimits{0xee, 0xee, 0xee}; + } + static unsigned getHashValue(const wasm::WasmLimits &Limits) { + unsigned Hash = hash_value(Limits.Flags); + Hash = hash_combine(Hash, Limits.Minimum); + Hash = hash_combine(Hash, Limits.Maximum); + return Hash; + } + static bool isEqual(const wasm::WasmLimits &LHS, + const wasm::WasmLimits &RHS) { + return LHS == RHS; + } +}; + +// Traits for using WasmTableType in a DenseMap +template <> struct DenseMapInfo { + static wasm::WasmTableType getEmptyKey() { + return wasm::WasmTableType{0, + DenseMapInfo::getEmptyKey()}; + } + static wasm::WasmTableType getTombstoneKey() { + return wasm::WasmTableType{ + 1, DenseMapInfo::getTombstoneKey()}; + } + static unsigned getHashValue(const wasm::WasmTableType &TableType) { + return hash_combine( + TableType.ElemType, + DenseMapInfo::getHashValue(TableType.Limits)); + } + static bool isEqual(const wasm::WasmTableType &LHS, + const wasm::WasmTableType &RHS) { + return LHS == RHS; + } +}; + } // end namespace llvm #endif // LLVM_BINARYFORMAT_WASMTRAITS_H