[RemoveUnusedModuleElements] Handle global.get in element segments (#9371) Active element segments (and table initializers) can initialize table slots using global.get expressions referencing either module-defined immutable globals or imported globals. Previously, Analyzer::prepare() only checked for RefFunc items when populating FlatTableInfo::typeFuncs and FlatTableInfo::typeElems, so active element segments whose items were global.gets were omitted from typeElems, causing RemoveUnusedModuleElements to delete the element segment and its referenced global even when a reachable call_indirect could call through that table slot. Fix this by tracing through module-defined immutable globals in notePossibleFunc so chains ending in RefFunc populate typeFuncs and typeElems directly, preserving called functions' bodies and maintaining type precision when a defined global has a broader declared type like funcref. For remaining function-typed items in active element segments whose concrete target is unknown (such as imported globals), propagateUnknownFuncElem pre-propagates the segment into typeElems for the item's heap type and its supertypes. Elements with inexact types are also recorded and keep their element segments alive when there are indirect calls to their subtypes. Fixes #9366.
diff --git a/src/passes/RemoveUnusedModuleElements.cpp b/src/passes/RemoveUnusedModuleElements.cpp index 9b58c52..bb7bdb4 100644 --- a/src/passes/RemoveUnusedModuleElements.cpp +++ b/src/passes/RemoveUnusedModuleElements.cpp
@@ -294,6 +294,12 @@ std::unordered_map<HeapType, std::unordered_set<Name>> typeFuncs; std::unordered_map<HeapType, std::unordered_set<Name>> typeElems; + // Maps each heap type of an inexact unknown function item (such as an + // imported global.get) to its segments. When a subtype of that heap type is + // called indirectly, walking the call type's supertypes finds these + // segments without eagerly expanding to all subtypes in the module. + std::unordered_map<HeapType, std::unordered_set<Name>> inexactTypeElems; + // All elems, regardless of type. std::unordered_set<Name> allElems; @@ -336,12 +342,23 @@ auto notePossibleFunc = [&](FlatTableInfo& info, Expression* item, Name elem = Name()) { + // Trace through module-defined immutable globals to find the + // underlying constant expression (which may be a RefFunc, RefNull, or + // an imported GlobalGet). + while (auto* get = item->dynCast<GlobalGet>()) { + auto* global = module->getGlobal(get->name); + if (global->imported()) { + break; + } + // Note that infinite recursion is not a danger here since a global + // can only refer to previous globals. + item = global->init; + } if (auto* refFunc = item->dynCast<RefFunc>()) { auto* func = module->getFunction(refFunc->func); std::optional<HeapType> type = func->type.getHeapType(); // Add this function and element to all relevant types: each function // might be called by its type, or a supertype. - // TODO: use exactness here while (type) { info.typeFuncs[*type].insert(func->name); if (elem) { @@ -349,6 +366,11 @@ } type = type->getSuperType(); } + } else if (elem && item->type.isFunction()) { + // This might be e.g. a global.get of an imported global. Note that + // ref.null always has a bottom heap type, for which isFunction() is + // false. + propagateUnknownFuncElem(info, item->type, elem); } }; @@ -399,6 +421,24 @@ } } + void propagateUnknownFuncElem(FlatTableInfo& info, Type itemType, Name elem) { + // We do not know the concrete function (because this might be e.g. a + // global.get of an imported global), so this segment might be called by the + // item's type, any supertype, or (if inexact) any subtype. Record the + // item's type and its supertypes in |typeElems|, and record inexact types + // in |inexactTypeElems| so subtype calls find them by walking supertypes. + auto type = itemType.getHeapType(); + for (std::optional<HeapType> super = type; super; + super = super->getSuperType()) { + if (!info.typeElems[*super].insert(elem).second) { + break; + } + } + if (!itemType.isExact()) { + info.inexactTypeElems[type].insert(elem); + } + } + // Process expressions in the expression queue while we have any, visiting // them (using their contents) and adding children. Returns whether we did any // work. @@ -440,9 +480,16 @@ return worked; } - // We'll compute SubTypes if we need them. + // Lazily compute SubTypes at most once for the module. std::optional<SubTypes> subTypes; + SubTypes& getSubTypes() { + if (!subTypes) { + subTypes = SubTypes(*module); + } + return *subTypes; + } + void useCallRefType(HeapType type) { if (type.isBasic()) { // Nothing to do for something like a bottom type; attempts to call such a @@ -450,13 +497,9 @@ return; } - if (!subTypes) { - subTypes = SubTypes(*module); - } - // Call all the functions of that signature, and subtypes. We can then // forget about them, as those signatures will be marked as called. - for (auto subType : subTypes->getSubTypes(type)) { + getSubTypes().iterSubTypes(type, [&](HeapType subType, Index depth) { auto iter = uncalledRefFuncMap.find(subType); if (iter != uncalledRefFuncMap.end()) { // We must not have a type in both calledSignatures and @@ -472,7 +515,8 @@ } calledSignatures.insert(subType); - } + return true; + }); } std::unordered_set<IndirectCall> usedIndirectCalls; @@ -495,6 +539,16 @@ for (auto& elem : info.typeElems[type]) { reference({ModuleElementKind::ElementSegment, elem}); } + for (auto super = type.getSuperType(); super; + super = super->getSuperType()) { + if (auto iter = info.inexactTypeElems.find(*super); + iter != info.inexactTypeElems.end()) { + for (auto& elem : iter->second) { + reference({ModuleElementKind::ElementSegment, elem}); + } + info.inexactTypeElems.erase(iter); + } + } // If traps might happen, and the table has an initial value, we must // consider more: imagine that we call a function with the wrong type, so we @@ -574,10 +628,7 @@ // This is the first time we see a read of this data. Note that it is // read, and also all subtypes since we might be reading from them as // well. - if (!subTypes) { - subTypes = SubTypes(*module); - } - subTypes->iterSubTypes(type, [&](HeapType subType, Index depth) { + getSubTypes().iterSubTypes(type, [&](HeapType subType, Index depth) { auto subStructField = StructField{subType, index}; readStructFields.insert(subStructField);
diff --git a/test/lit/passes/remove-unused-module-elements_ci-types.wast b/test/lit/passes/remove-unused-module-elements_ci-types.wast index f4ea678..38fa236 100644 --- a/test/lit/passes/remove-unused-module-elements_ci-types.wast +++ b/test/lit/passes/remove-unused-module-elements_ci-types.wast
@@ -546,3 +546,270 @@ ) ) ) + +;; Active element segments initialized via imported globals, and a table +;; initialized via an imported global. +;; +;; * $g-funcref (funcref) may hold $A, so $e-funcref and $g-funcref are kept. +;; * $g-super ((ref null $A-super)) may hold $A, so $e-super and $g-super are +;; kept. +;; * $g-sub ((ref null $A-sub)) is a subtype of $A, so $e-sub and $g-sub are +;; kept. +;; * $g-exact-super ((ref null (exact $A-super))) cannot hold $A, so +;; $e-exact-super and $g-exact-super are removed. +;; * $g-exact-sub ((ref null (exact $A-sub))) is a subtype of $A, so +;; $e-exact-sub and $g-exact-sub are kept. +;; * $g-other ((ref null $B)) is unrelated to $A, so $e-other and $g-other are +;; removed. +;; * $g-nofunc (nullfuncref) can only hold null, so $e-nofunc and $g-nofunc +;; are removed. +;; * $e-null ((ref.null $A)) can only hold null, so $e-null is removed. +;; * $t2's init (global.get $g-init) keeps $g-init alive. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $A-super (sub (func))) + (type $A-super (sub (func))) + ;; CHECK: (type $A (sub $A-super (func))) + (type $A (sub $A-super (func))) + ;; CHECK: (type $A-sub (sub $A (func))) + (type $A-sub (sub $A (func))) + ;; CHECK: (type $B (func (param f64))) + (type $B (func (param f64))) + ) + + ;; CHECK: (type $4 (func)) + + ;; CHECK: (import "env" "g-funcref" (global $g-funcref funcref)) + (import "env" "g-funcref" (global $g-funcref funcref)) + ;; CHECK: (import "env" "g-super" (global $g-super (ref null $A-super))) + (import "env" "g-super" (global $g-super (ref null $A-super))) + ;; CHECK: (import "env" "g-sub" (global $g-sub (ref null $A-sub))) + (import "env" "g-sub" (global $g-sub (ref null $A-sub))) + (import "env" "g-exact-super" (global $g-exact-super (ref null (exact $A-super)))) + ;; CHECK: (import "env" "g-exact-sub" (global $g-exact-sub (ref null (exact $A-sub)))) + (import "env" "g-exact-sub" (global $g-exact-sub (ref null (exact $A-sub)))) + (import "env" "g-other" (global $g-other (ref null $B))) + (import "env" "g-nofunc" (global $g-nofunc nullfuncref)) + ;; CHECK: (import "env" "g-init" (global $g-init funcref)) + (import "env" "g-init" (global $g-init funcref)) + + ;; CHECK: (table $t1 10 10 funcref) + (table $t1 10 10 funcref) + ;; CHECK: (table $t2 1 1 funcref (global.get $g-init)) + (table $t2 1 1 funcref (global.get $g-init)) + + ;; CHECK: (elem $e-funcref (table $t1) (i32.const 0) funcref (item (global.get $g-funcref)) (item (global.get $g-funcref))) + (elem $e-funcref (table $t1) (i32.const 0) funcref (item (global.get $g-funcref)) (item (global.get $g-funcref))) + ;; CHECK: (elem $e-super (table $t1) (i32.const 2) funcref (item (global.get $g-super))) + (elem $e-super (table $t1) (i32.const 2) funcref (item (global.get $g-super))) + ;; CHECK: (elem $e-sub (table $t1) (i32.const 3) funcref (item (global.get $g-sub))) + (elem $e-sub (table $t1) (i32.const 3) funcref (item (global.get $g-sub))) + (elem $e-exact-super (table $t1) (i32.const 4) funcref (item (global.get $g-exact-super))) + ;; CHECK: (elem $e-exact-sub (table $t1) (i32.const 5) funcref (item (global.get $g-exact-sub))) + (elem $e-exact-sub (table $t1) (i32.const 5) funcref (item (global.get $g-exact-sub))) + (elem $e-other (table $t1) (i32.const 6) funcref (item (global.get $g-other))) + (elem $e-nofunc (table $t1) (i32.const 7) funcref (item (global.get $g-nofunc))) + (elem $e-null (table $t1) (i32.const 8) (ref null $A) (item (ref.null $A))) + + ;; CHECK: (export "export" (func $export)) + + ;; CHECK: (func $export (type $4) + ;; CHECK-NEXT: (call_indirect $t1 (type $A) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call_indirect $t2 (type $A) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $export (export "export") + (call_indirect $t1 (type $A) + (i32.const 0) + ) + (call_indirect $t2 (type $A) + (i32.const 0) + ) + ) +) + +;; Active element segments initialized via shared imported globals, verifying +;; that shared and unshared function types remain isolated. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $unshared-A (sub (func))) + (type $unshared-A (sub (func))) + ;; CHECK: (type $shared-A (sub (shared (func)))) + (type $shared-A (sub (shared (func)))) + ;; CHECK: (type $shared-sub (sub $shared-A (shared (func)))) + (type $shared-sub (sub $shared-A (shared (func)))) + ;; CHECK: (type $shared-B (shared (func (param f64)))) + (type $shared-B (shared (func (param f64)))) + ) + + ;; CHECK: (type $4 (func)) + + ;; CHECK: (import "env" "g-shared-func" (global $g-shared-func (ref null (shared func)))) + (import "env" "g-shared-func" (global $g-shared-func (ref null (shared func)))) + ;; CHECK: (import "env" "g-shared-super" (global $g-shared-super (ref null $shared-A))) + (import "env" "g-shared-super" (global $g-shared-super (ref null $shared-A))) + (import "env" "g-shared-other" (global $g-shared-other (ref null $shared-B))) + (import "env" "g-shared-unused" (global $g-shared-unused (ref null (shared func)))) + + ;; CHECK: (table $t-shared 10 10 (ref null (shared func))) + (table $t-shared 10 10 (ref null (shared func))) + ;; CHECK: (table $t-cross 10 10 (ref null (shared func))) + + ;; CHECK: (elem $e-shared-func (table $t-shared) (i32.const 0) (ref null (shared func)) (item (global.get $g-shared-func))) + (elem $e-shared-func (table $t-shared) (i32.const 0) (ref null (shared func)) (item (global.get $g-shared-func))) + ;; CHECK: (elem $e-shared-super (table $t-shared) (i32.const 1) (ref null (shared func)) (item (global.get $g-shared-super))) + (elem $e-shared-super (table $t-shared) (i32.const 1) (ref null (shared func)) (item (global.get $g-shared-super))) + (elem $e-shared-other (table $t-shared) (i32.const 2) (ref null (shared func)) (item (global.get $g-shared-other))) + + (table $t-cross 10 10 (ref null (shared func))) + (elem $e-cross (table $t-cross) (i32.const 0) (ref null (shared func)) (item (global.get $g-shared-unused))) + + ;; CHECK: (export "export" (func $export)) + + ;; CHECK: (func $export (type $4) + ;; CHECK-NEXT: (call_indirect $t-shared (type $shared-sub) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call_indirect $t-cross (type $unshared-A) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $export (export "export") + ;; Shared call_indirect keeps $e-shared-func and $e-shared-super, and drops + ;; $e-shared-other. + (call_indirect $t-shared (type $shared-sub) + (i32.const 0) + ) + ;; Unshared signature call_indirect on a shared table cannot match shared + ;; functions, so $e-cross and $g-shared-unused are removed. + (call_indirect $t-cross (type $unshared-A) + (i32.const 0) + ) + ) +) + +;; Active element segments initialized via module-defined immutable globals +;; (directly and via chained global.gets). +;; +;; * $g-func-A holds (ref.func $func-A), so $e-def-A, $g-func-A, and $func-A's +;; body are kept. +;; * $g-chain-1 -> $g-chain-2 -> (ref.func $func-subA) resolves to $func-subA +;; (subtype of $A), so $e-chain-func, $g-chain-1, $g-chain-2, and +;; $func-subA's body are kept. +;; * $g-chain-imp-def -> (global.get $g-imp) resolves to imported $g-imp +;; (funcref), so $e-chain-imp, $g-chain-imp-def, and $g-imp are kept. +;; * $g-def-B has static type funcref, which is a supertype of $A, but traces +;; to (ref.func $func-B) of unrelated type $B, so $e-def-B, $g-def-B, and +;; $func-B are all removed. +;; * $g-def-null traces to (ref.null $A), so $e-def-null and $g-def-null are +;; removed. +;; * $e-mixed has both (ref.func $func-A-2) and (global.get $g-dead-B). $e-mixed +;; and $g-dead-B are kept, $func-A-2's body is kept, and $func-dead-B's body +;; is emptied to unreachable. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $A (sub (func))) + (type $A (sub (func))) + ;; CHECK: (type $subA (sub $A (func))) + (type $subA (sub $A (func))) + ;; CHECK: (type $B (func (param f64))) + (type $B (func (param f64))) + ) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (import "env" "g-imp" (global $g-imp funcref)) + (import "env" "g-imp" (global $g-imp funcref)) + + ;; CHECK: (global $g-func-A funcref (ref.func $func-A)) + (global $g-func-A funcref (ref.func $func-A)) + ;; CHECK: (global $g-chain-2 (ref $subA) (ref.func $func-subA)) + (global $g-chain-2 (ref $subA) (ref.func $func-subA)) + ;; CHECK: (global $g-chain-1 funcref (global.get $g-chain-2)) + (global $g-chain-1 funcref (global.get $g-chain-2)) + ;; CHECK: (global $g-chain-imp-def funcref (global.get $g-imp)) + (global $g-chain-imp-def funcref (global.get $g-imp)) + (global $g-def-B funcref (ref.func $func-B)) + (global $g-def-null (ref null $A) (ref.null $A)) + ;; CHECK: (global $g-dead-B funcref (ref.func $func-dead-B)) + (global $g-dead-B funcref (ref.func $func-dead-B)) + + ;; CHECK: (table $t 10 10 funcref) + (table $t 10 10 funcref) + + ;; CHECK: (elem $e-def-A (table $t) (i32.const 0) funcref (item (global.get $g-func-A))) + (elem $e-def-A (table $t) (i32.const 0) funcref (item (global.get $g-func-A))) + ;; CHECK: (elem $e-chain-func (table $t) (i32.const 1) funcref (item (global.get $g-chain-1))) + (elem $e-chain-func (table $t) (i32.const 1) funcref (item (global.get $g-chain-1))) + ;; CHECK: (elem $e-chain-imp (table $t) (i32.const 2) funcref (item (global.get $g-chain-imp-def))) + (elem $e-chain-imp (table $t) (i32.const 2) funcref (item (global.get $g-chain-imp-def))) + (elem $e-def-B (table $t) (i32.const 3) funcref (item (global.get $g-def-B))) + (elem $e-def-null (table $t) (i32.const 4) funcref (item (global.get $g-def-null))) + ;; CHECK: (elem $e-mixed (table $t) (i32.const 5) funcref (item (ref.func $func-A-2)) (item (global.get $g-dead-B))) + (elem $e-mixed (table $t) (i32.const 5) funcref + (item (ref.func $func-A-2)) + (item (global.get $g-dead-B)) + ) + + ;; CHECK: (export "export" (func $export)) + + ;; CHECK: (func $export (type $3) + ;; CHECK-NEXT: (call_indirect $t (type $A) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $export (export "export") + (call_indirect $t (type $A) + (i32.const 0) + ) + ) + + ;; CHECK: (func $func-A (type $A) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 10) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $func-A (type $A) + ;; Kept in full via $g-func-A. + (drop (i32.const 10)) + ) + + ;; CHECK: (func $func-subA (type $subA) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 20) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $func-subA (type $subA) + ;; Kept in full via $g-chain-1 -> $g-chain-2. + (drop (i32.const 20)) + ) + + (func $func-B (type $B) (param $p f64) + ;; Removed entirely despite $g-def-B having type funcref. + (drop (i32.const 30)) + ) + + ;; CHECK: (func $func-A-2 (type $A) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 40) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $func-A-2 (type $A) + ;; Kept in full via $e-mixed. + (drop (i32.const 40)) + ) + + ;; CHECK: (func $func-dead-B (type $B) (param $p f64) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $func-dead-B (type $B) (param $p f64) + ;; Referenced via $e-mixed -> $g-dead-B, so emptied to unreachable. + (drop (i32.const 50)) + ) +)