Use effects for indirect call expressions
diff --git a/src/ir/effects.h b/src/ir/effects.h index af866b9..6be8f34 100644 --- a/src/ir/effects.h +++ b/src/ir/effects.h
@@ -770,6 +770,12 @@ } } void visitCallIndirect(CallIndirect* curr) { + if (auto it = parent.module.typeEffects.find(curr->heapType); + it != parent.module.typeEffects.end()) { + parent.mergeIn(*it->second); + return; + } + parent.calls = true; if (curr->isReturn) { parent.branchesOut = true; @@ -1040,6 +1046,14 @@ if (trapOnNull(curr->target)) { return; } + + if (auto it = + parent.module.typeEffects.find(curr->target->type.getHeapType()); + it != parent.module.typeEffects.end()) { + parent.mergeIn(*it->second); + return; + } + if (curr->isReturn) { parent.branchesOut = true; if (parent.features.hasExceptionHandling()) {
diff --git a/src/passes/GlobalEffects.cpp b/src/passes/GlobalEffects.cpp index 1625b55..8da805e 100644 --- a/src/passes/GlobalEffects.cpp +++ b/src/passes/GlobalEffects.cpp
@@ -26,6 +26,7 @@ #include "pass.h" #include "support/graph_traversal.h" #include "support/strongly_connected_components.h" +#include "support/utilities.h" #include "wasm.h" namespace wasm { @@ -227,10 +228,13 @@ // - Merge all of the effects of functions within the CC // - Also merge the (already computed) effects of each callee CC // - Add trap effects for potentially recursive call chains -void propagateEffects(const Module& module, - const PassOptions& passOptions, - std::map<Function*, FuncInfo>& funcInfos, - const CallGraph& callGraph) { +void propagateEffects( + const Module& module, + const PassOptions& passOptions, + std::map<Function*, FuncInfo>& funcInfos, + std::unordered_map<HeapType, std::shared_ptr<const EffectAnalyzer>>& + typeEffects, + const CallGraph& callGraph) { // We only care about Functions that are roots, not types. // A type would be a root if a function exists with that type, but no-one // indirect calls the type. @@ -319,12 +323,21 @@ } // Assign each function's effects to its CC effects. - for (Function* f : ccFuncs) { - if (!ccEffects) { - funcInfos.at(f).effects = UnknownEffects; - } else { - funcInfos.at(f).effects.emplace(*ccEffects); - } + for (auto node : cc) { + std::visit(overloaded{[&](HeapType type) { + if (ccEffects != UnknownEffects) { + typeEffects[type] = + std::make_shared<EffectAnalyzer>(*ccEffects); + } + }, + [&](Function* f) { + if (!ccEffects) { + funcInfos.at(f).effects = UnknownEffects; + } else { + funcInfos.at(f).effects.emplace(*ccEffects); + } + }}, + node); } } } @@ -348,7 +361,8 @@ auto callGraph = buildCallGraph(*module, funcInfos, getPassOptions().closedWorld); - propagateEffects(*module, getPassOptions(), funcInfos, callGraph); + propagateEffects( + *module, getPassOptions(), funcInfos, module->typeEffects, callGraph); copyEffectsToFunctions(funcInfos); }
diff --git a/src/support/utilities.h b/src/support/utilities.h index 3f40111..99d5489 100644 --- a/src/support/utilities.h +++ b/src/support/utilities.h
@@ -94,6 +94,10 @@ #define WASM_UNREACHABLE(msg) wasm::handle_unreachable() #endif +template<class... Ts> struct overloaded : Ts... { + using Ts::operator()...; +}; + } // namespace wasm #endif // wasm_support_utilities_h
diff --git a/src/wasm.h b/src/wasm.h index e59f996..c74e39e 100644 --- a/src/wasm.h +++ b/src/wasm.h
@@ -2684,6 +2684,11 @@ std::unordered_map<HeapType, TypeNames> typeNames; std::unordered_map<HeapType, Index> typeIndices; + // Potential effects for bodies of indirect calls to this type. + // TODO: make this into Type + std::unordered_map<HeapType, std::shared_ptr<const EffectAnalyzer>> + typeEffects; + MixedArena allocator; private:
diff --git a/test/lit/passes/global-effects-closed-world-tnh.wast b/test/lit/passes/global-effects-closed-world-tnh.wast index 4c4558f..64aeab8 100644 --- a/test/lit/passes/global-effects-closed-world-tnh.wast +++ b/test/lit/passes/global-effects-closed-world-tnh.wast
@@ -16,22 +16,9 @@ ) ;; CHECK: (func $calls-nop-via-nullable-ref (type $1) (param $ref (ref null $nopType)) - ;; CHECK-NEXT: (call_ref $nopType - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: (local.get $ref) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) (func $calls-nop-via-nullable-ref (param $ref (ref null $nopType)) (call_ref $nopType (i32.const 1) (local.get $ref)) ) - - ;; CHECK: (func $f (type $1) (param $ref (ref null $nopType)) - ;; CHECK-NEXT: (nop) - ;; CHECK-NEXT: ) - (func $f (param $ref (ref null $nopType)) - ;; The only possible implementation of $nopType has no effects. - ;; $calls-nop-via-nullable-ref may trap from a null reference, but - ;; --traps-never-happen is enabled, so we're free to optimize this out. - (call $calls-nop-via-nullable-ref (local.get $ref)) - ) )
diff --git a/test/lit/passes/global-effects-closed-world.wast b/test/lit/passes/global-effects-closed-world.wast index 77484c6..48779e0 100644 --- a/test/lit/passes/global-effects-closed-world.wast +++ b/test/lit/passes/global-effects-closed-world.wast
@@ -17,18 +17,10 @@ ) ;; CHECK: (func $calls-nop-via-ref (type $1) (param $ref (ref $nopType)) - ;; CHECK-NEXT: (call_ref $nopType - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: (local.get $ref) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) (func $calls-nop-via-ref (param $ref (ref $nopType)) ;; This can only possibly be a nop in closed-world. - ;; Ideally vacuum could optimize this out but we don't have a way to share - ;; this information with other passes today. - ;; For now, we can at least annotate that the call to this function in $f - ;; has no effects. - ;; TODO: This call_ref could be marked as having no effects, like the call below. (call_ref $nopType (i32.const 1) (local.get $ref)) ) @@ -41,27 +33,6 @@ (func $calls-nop-via-nullable-ref (param $ref (ref null $nopType)) (call_ref $nopType (i32.const 1) (local.get $ref)) ) - - - ;; CHECK: (func $f (type $1) (param $ref (ref $nopType)) - ;; CHECK-NEXT: (nop) - ;; CHECK-NEXT: ) - (func $f (param $ref (ref $nopType)) - ;; $calls-nop-via-ref has no effects because we determined that it can only - ;; call $nop. We can optimize this call out. - (call $calls-nop-via-ref (local.get $ref)) - ) - - ;; CHECK: (func $g (type $2) (param $ref (ref null $nopType)) - ;; CHECK-NEXT: (call $calls-nop-via-nullable-ref - ;; CHECK-NEXT: (local.get $ref) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) - (func $g (param $ref (ref null $nopType)) - ;; Similar to $f, but we may still trap here because the ref is null, so we - ;; don't optimize. - (call $calls-nop-via-nullable-ref (local.get $ref)) - ) ) ;; Same as the above but with call_indirect @@ -79,28 +50,10 @@ ) ;; CHECK: (func $calls-nop-via-ref (type $1) - ;; CHECK-NEXT: (call_indirect $0 (type $nopType) - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: (i32.const 0) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) - (func $calls-nop-via-ref - ;; This can only possibly be a nop in closed-world. - ;; Ideally vacuum could optimize this out but we don't have a way to share - ;; this information with other passes today. - ;; For now, we can at least annotate that the call to this function in $f - ;; has no effects. - ;; TODO: This call_ref could be marked as having no effects, like the call below. - (call_indirect (type $nopType) (i32.const 1) (i32.const 0)) - ) - - ;; CHECK: (func $f (type $1) ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) - (func $f - ;; $calls-nop-via-ref has no effects because we determined that it can only - ;; call $nop. We can optimize this call out. - (call $calls-nop-via-ref) + (func $calls-nop-via-ref + (call_indirect (type $nopType) (i32.const 1) (i32.const 0)) ) ) @@ -129,18 +82,9 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) (func $calls-effectful-function-via-ref (param $ref (ref $maybe-has-effects)) - (call_ref $maybe-has-effects (i32.const 1) (local.get $ref)) - ) - - ;; CHECK: (func $f (type $1) (param $ref (ref $maybe-has-effects)) - ;; CHECK-NEXT: (call $calls-effectful-function-via-ref - ;; CHECK-NEXT: (local.get $ref) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) - (func $f (param $ref (ref $maybe-has-effects)) - ;; This may be a nop or it may trap depending on the ref. + ;; This may be a nop or it may trap depending on the ref ;; We don't know so don't optimize it out. - (call $calls-effectful-function-via-ref (local.get $ref)) + (call_ref $maybe-has-effects (i32.const 1) (local.get $ref)) ) ) @@ -172,16 +116,9 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) (func $calls-effectful-function-via-ref - (call_indirect (type $maybe-has-effects) (i32.const 1) (i32.const 1)) - ) - - ;; CHECK: (func $f (type $1) - ;; CHECK-NEXT: (call $calls-effectful-function-via-ref) - ;; CHECK-NEXT: ) - (func $f ;; This may be a nop or it may trap depending on the ref. ;; We don't know so don't optimize it out. - (call $calls-effectful-function-via-ref) + (call_indirect (type $maybe-has-effects) (i32.const 1) (i32.const 1)) ) ) @@ -190,13 +127,12 @@ (type $uninhabited (func (param i32))) ;; CHECK: (func $calls-uninhabited (type $1) (param $ref (ref $uninhabited)) - ;; CHECK-NEXT: (call_ref $uninhabited - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: (local.get $ref) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) (func $calls-uninhabited (param $ref (ref $uninhabited)) - ;; It's impossible to create a ref to call this function with. + ;; There's no function with this type, so it's impossible to create a ref to + ;; call this function with and there are no effects to aggregate. + ;; Remove this call. ;; TODO: Optimize this to (unreachable). (call_ref $uninhabited (i32.const 1) (local.get $ref)) ) @@ -212,28 +148,6 @@ ;; TODO: Optimize this to (unreachable). (call_ref $uninhabited (i32.const 1) (local.get $ref)) ) - - - ;; CHECK: (func $f (type $1) (param $ref (ref $uninhabited)) - ;; CHECK-NEXT: (nop) - ;; CHECK-NEXT: ) - (func $f (param $ref (ref $uninhabited)) - ;; There's no function with this type, so it's impossible to create a ref to - ;; call this function with and there are no effects to aggregate. - ;; Remove this call. - (call $calls-uninhabited (local.get $ref)) - ) - - ;; CHECK: (func $g (type $2) (param $ref (ref null $uninhabited)) - ;; CHECK-NEXT: (call $calls-nullable-uninhabited - ;; CHECK-NEXT: (local.get $ref) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) - (func $g (param $ref (ref null $uninhabited)) - ;; Similar to above but we have a nullable reference, so we may trap and - ;; can't optimize the call out. - (call $calls-nullable-uninhabited (local.get $ref)) - ) ) (module @@ -256,7 +170,7 @@ (unreachable) ) - ;; CHECK: (func $calls-ref-with-supertype (type $1) (param $func (ref $super)) + ;; CHECK: (func $calls-ref-with-supertype (type $2) (param $func (ref $super)) ;; CHECK-NEXT: (call_ref $super ;; CHECK-NEXT: (local.get $func) ;; CHECK-NEXT: ) @@ -273,32 +187,6 @@ (func $calls-ref-with-exact-supertype (param $func (ref (exact $super))) (call_ref $super (local.get $func)) ) - - ;; CHECK: (func $f (type $1) (param $func (ref $super)) - ;; CHECK-NEXT: (call $calls-ref-with-supertype - ;; CHECK-NEXT: (local.get $func) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) - (func $f (param $func (ref $super)) - ;; Check that we account for subtyping correctly. - ;; $super has no effects (i.e. the union of all effects of functions with - ;; this type is empty). However, $sub does have effects, and we can call_ref - ;; with that subtype, so we need to include the unreachable effect and we - ;; can't optimize out this call. - (call $calls-ref-with-supertype (local.get $func)) - ) - - ;; CHECK: (func $g (type $2) (param $func (ref (exact $super))) - ;; CHECK-NEXT: (call $calls-ref-with-exact-supertype - ;; CHECK-NEXT: (local.get $func) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) - (func $g (param $func (ref (exact $super))) - ;; Same as above but this time our reference is the exact supertype - ;; so we know not to aggregate effects from the subtype. - ;; TODO: this case doesn't optimize today. Add exact ref support in the pass. - (call $calls-ref-with-exact-supertype (local.get $func)) - ) ) (module @@ -325,21 +213,11 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) (func $calls-type-with-effects-but-not-addressable (param $ref (ref $only-has-effects-in-not-addressable-function)) - (call_ref $only-has-effects-in-not-addressable-function (i32.const 1) (local.get $ref)) - ) - - ;; CHECK: (func $f (type $1) (param $ref (ref $only-has-effects-in-not-addressable-function)) - ;; CHECK-NEXT: (call $calls-type-with-effects-but-not-addressable - ;; CHECK-NEXT: (local.get $ref) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) - (func $f (param $ref (ref $only-has-effects-in-not-addressable-function)) ;; The type $has-effects-but-not-exported doesn't have an address because ;; it's not exported and it's never the target of a ref.func. - ;; We should be able to determine that $ref can only point to $nop. - ;; TODO: Only aggregate effects from functions that are addressed. - (call $calls-type-with-effects-but-not-addressable (local.get $ref)) - ) + ;; So the call_ref has no potential targets and thus no effects. + (call_ref $only-has-effects-in-not-addressable-function (i32.const 1) (local.get $ref)) + ) ) (module @@ -406,18 +284,9 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) (func $indirect-calls (param $ref (ref $t)) - (call_ref $t (i32.const 1) (local.get $ref)) - ) - - ;; CHECK: (func $f (type $1) (param $ref (ref $t)) - ;; CHECK-NEXT: (call $indirect-calls - ;; CHECK-NEXT: (local.get $ref) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) - (func $f (param $ref (ref $t)) ;; $indirect-calls might end up calling an imported function, ;; so we don't know anything about effects here - (call $indirect-calls (local.get $ref)) + (call_ref $t (i32.const 1) (local.get $ref)) ) ) @@ -435,15 +304,8 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) (func $calls-unreachable (export "calls-unreachable") - (call_ref $t (unreachable)) - ) - - ;; CHECK: (func $f (type $0) - ;; CHECK-NEXT: (call $calls-unreachable) - ;; CHECK-NEXT: ) - (func $f ;; $t looks like it has no effects, but unreachable is passed in, ;; so preserve the trap. - (call $calls-unreachable) + (call_ref $t (unreachable)) ) )