done?
diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h index 50b67df..d6a696c 100644 --- a/src/ir/module-utils.h +++ b/src/ir/module-utils.h
@@ -271,7 +271,7 @@ template<typename K, typename V> using DefaultMap = std::map<K, V>; template<typename T, Mutability Mut = Immutable, - template<typename, typename> class MapT = DefaultMap> + template<typename, typename, typename...> class MapT = DefaultMap> struct ParallelFunctionAnalysis { Module& wasm;
diff --git a/src/passes/GlobalEffects.cpp b/src/passes/GlobalEffects.cpp index 5fcf8cf..3d41915 100644 --- a/src/passes/GlobalEffects.cpp +++ b/src/passes/GlobalEffects.cpp
@@ -47,10 +47,10 @@ std::unordered_set<HeapType> indirectCalledTypes; }; -std::map<Function*, FuncInfo> analyzeFuncs(Module& module, - const PassOptions& passOptions) { - ModuleUtils::ParallelFunctionAnalysis<FuncInfo> analysis( - module, [&](Function* func, FuncInfo& funcInfo) { +std::unordered_map<Function*, FuncInfo> +analyzeFuncs(Module& module, const PassOptions& passOptions) { + ModuleUtils::ParallelFunctionAnalysis<FuncInfo, Immutable, std::unordered_map> + analysis(module, [&](Function* func, FuncInfo& funcInfo) { if (func->imported()) { // Imports can do anything, so we need to assume the worst anyhow, // which is the same as not specifying any effects for them in the @@ -101,7 +101,7 @@ } else if (auto* callIndirect = curr->dynCast<CallIndirect>()) { type = callIndirect->heapType; } else { - assert(false && "Unexpected type of call"); + assert("Unexpected type of call"); } funcInfo.indirectCalledTypes.insert(type); @@ -123,59 +123,35 @@ return std::move(analysis.map); } -// Funcs that can be the target of a virtual call -// These are either: -// - Part of an (elem declare ...) or (elem ...) directive -// - Exported, since they may flow back to us from the host -std::unordered_set<Name> getFuncsWithAddress(Module& module) { - std::unordered_set<Name> funcsWithAddress; - for (const auto& fun : module.functions) { - funcsWithAddress.insert(fun->name); - } - return funcsWithAddress; - - // { - // auto refFuncs = TableUtils::getFunctionsNeedingElemDeclare(module); - // funcsWithAddress.insert(refFuncs.begin(), refFuncs.end()); - // } - - // ElementUtils::iterAllElementFunctionNames( - // &module, - // [&funcsWithAddress](Name name) { funcsWithAddress.insert(name); }); - // for (const auto& export_ : module.exports) { - // if (export_->kind == ExternalKind::Function) { - // // This exported function might flow back to us even in a closed world, - // // so it's essentially addressed. - // funcsWithAddress.insert(export_->name); - // } - // } - - // return funcsWithAddress; -} - using CallGraphNode = std::variant<Name, HeapType>; // Build a call graph for indirect and direct calls. // key (callee) -> value (caller) // Name -> Name : callee is called directly by caller -// Name -> HeapType : callee is a potential target of a virtual call with this HeapType -// HeapType -> Name : callee is indirectly called by caller -// HeapType -> HeapType : callee is a subtype of caller - -// TODO: only track indirect calls in closed world -std::unordered_map<CallGraphNode, std::unordered_set<CallGraphNode>> buildReverseCallGraph(Module& module, const std::map<Function*, FuncInfo> funcInfos) { +// Name -> HeapType : callee is a potential target of a virtual call +// with this HeapType HeapType -> Name : callee is indirectly called by +// caller HeapType -> HeapType : callee is a subtype of caller If we're +// running in an open world, we only include Name -> Name edges. +std::unordered_map<CallGraphNode, std::unordered_set<CallGraphNode>> +buildReverseCallGraph(Module& module, + const std::unordered_map<Function*, FuncInfo>& funcInfos, + bool closedWorld) { // callee : caller - std::unordered_map<CallGraphNode, std::unordered_set<CallGraphNode>> - callers; + std::unordered_map<CallGraphNode, std::unordered_set<CallGraphNode>> callers; + + if (!closedWorld) { + for (const auto& [func, info] : funcInfos) { + // Name -> Name for direct calls + for (const auto& callee : info.calledFunctions) { + callers[callee].insert(func->name); + } + } + + return callers; + } std::unordered_set<HeapType> allIndirectCalledTypes; - // Funcs that can be the target of a virtual call - // These are either: - // - Part of an (elem declare ...) or (elem ...) directive - // - Exported, since they may flow back to us from the host - std::unordered_set<Name> funcsWithAddress = getFuncsWithAddress(module); - for (const auto& [func, info] : funcInfos) { // Name -> Name for direct calls for (const auto& callee : info.calledFunctions) { @@ -188,16 +164,16 @@ } // Name -> HeapType for function types - if (funcsWithAddress.contains(func->name)) { - callers[func->name].insert(func->type.getHeapType()); - } + // TODO: only look at functions that are addressable + // i.e. appear in a (ref.func) or are exported + callers[func->name].insert(func->type.getHeapType()); allIndirectCalledTypes.insert(func->type.getHeapType()); } SubTypes subtypes(module); for (auto type : allIndirectCalledTypes) { - subtypes.iterSubTypes(type, [&callers, type](HeapType sub, int _) { + subtypes.iterSubTypes(type, [&callers, type](HeapType sub, Index _) { // HeapType -> HeapType // A subtype is a 'callee' of its supertype. // Supertypes need to inherit effects from their subtypes since they may @@ -217,19 +193,27 @@ const Module& module, const std::unordered_map<CallGraphNode, std::unordered_set<CallGraphNode>>& reverseCallGraph, - std::map<Function*, FuncInfo>& funcInfos) { + std::unordered_map<Function*, FuncInfo>& funcInfos) { using CallGraphEdge = std::pair<CallGraphNode, CallGraphNode>; UniqueNonrepeatingDeferredQueue<CallGraphEdge> work; for (const auto& [callee, callers] : reverseCallGraph) { + // We only care about roots that will lead to a Name -> Name connection + // If there's a HeapType with no Name callee, we don't need to process it + // anyway. + if (!std::holds_alternative<Name>(callee)) { + continue; + } for (const auto& caller : callers) { work.push(std::pair(callee, caller)); } } - auto propagate = [&](const CallGraphNode& calleeNode, const CallGraphNode& callerNode) { - if (!std::get_if<Name>(&calleeNode) || !std::get_if<Name>(&callerNode)) { + auto propagate = [&](const CallGraphNode& calleeNode, + const CallGraphNode& callerNode) { + if (!std::holds_alternative<Name>(calleeNode) || + !std::holds_alternative<Name>(callerNode)) { return; } @@ -257,15 +241,6 @@ while (!work.empty()) { auto [callee, caller] = work.pop(); - if (std::get_if<Name>(&callee) == std::get_if<Name>(&caller) && - std::holds_alternative<Name>(callee)) { - auto& callerEffects = - funcInfos.at(module.getFunction(std::get<Name>(caller))).effects; - if (callerEffects) { - callerEffects->trap = true; - } - } - // Even if nothing changed, we still need to keep traversing the callers // to look for a potential cycle which adds a trap affect on the above // lines. @@ -276,6 +251,7 @@ continue; } + // TODO: handle exact refs here for (const CallGraphNode& callerCaller : callerCallers->second) { work.push(std::pair(callee, callerCaller)); } @@ -284,21 +260,13 @@ struct GenerateGlobalEffects : public Pass { void run(Module* module) override { - std::map<Function*, FuncInfo> funcInfos = + std::unordered_map<Function*, FuncInfo> funcInfos = analyzeFuncs(*module, getPassOptions()); // callee : caller std::unordered_map<CallGraphNode, std::unordered_set<CallGraphNode>> - callers = buildReverseCallGraph(*module, funcInfos); - - // for (const auto& [callee, callers] : callers) { - // for (const auto& caller : callers) { - // const auto* calleeName = std::get_if<Name>(&callee); - // const auto* callerName = std::get_if<Name>(&caller); - // if (!calleeName || !callerName) continue; - // std::cout<<*calleeName<<"\t\t->\t\t"<<*callerName<<"\n"; - // } - // } + callers = + buildReverseCallGraph(*module, funcInfos, getPassOptions().closedWorld); propagateEffects(*module, callers, funcInfos);
diff --git a/test/lit/passes/global-effects-closed-world.wast b/test/lit/passes/global-effects-closed-world.wast index 659f997..8d89c48 100644 --- a/test/lit/passes/global-effects-closed-world.wast +++ b/test/lit/passes/global-effects-closed-world.wast
@@ -155,6 +155,56 @@ ) ) +;; 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. +(module + ;; CHECK: (type $super (sub (struct))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct))) + (type $sub (sub $super (struct))) + + ;; Supertype + ;; CHECK: (type $func-with-sub-param (sub (func (param (ref $sub))))) + (type $func-with-sub-param (sub (func (param (ref $sub))))) + ;; Subtype + ;; CHECK: (type $func-with-super-param (sub $func-with-sub-param (func (param (ref $super))))) + (type $func-with-super-param (sub $func-with-sub-param (func (param (ref $super))))) + + ;; CHECK: (func $nop-with-supertype (type $func-with-sub-param) (param $0 (ref $sub)) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $nop-with-supertype (export "nop-with-supertype") (type $func-with-sub-param) (param (ref $sub)) + ) + + ;; CHECK: (func $effectful-with-subtype (type $func-with-super-param) (param $0 (ref $super)) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $effectful-with-subtype (export "effectful-with-subtype") (type $func-with-super-param) (param (ref $super)) + (unreachable) + ) + + ;; CHECK: (func $calls-ref-with-subtype (type $3) (param $func (ref (exact $func-with-sub-param))) (param $sub (ref $sub)) + ;; CHECK-NEXT: (call_ref $func-with-sub-param + ;; CHECK-NEXT: (local.get $sub) + ;; CHECK-NEXT: (local.get $func) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $calls-ref-with-subtype (param $func (ref (exact $func-with-sub-param))) (param $sub (ref $sub)) + (call_ref $func-with-sub-param (local.get $sub) (local.get $func)) + ) + + ;; CHECK: (func $f (type $3) (param $func (ref (exact $func-with-sub-param))) (param $sub (ref $sub)) + ;; CHECK-NEXT: (call $calls-ref-with-subtype + ;; CHECK-NEXT: (local.get $func) + ;; CHECK-NEXT: (local.get $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $f (param $func (ref (exact $func-with-sub-param))) (param $sub (ref $sub)) + (call $calls-ref-with-subtype (local.get $func) (local.get $sub)) + ) +) + (module ;; CHECK: (type $only-has-effects-in-not-addressable-function (func (param i32))) (type $only-has-effects-in-not-addressable-function (func (param i32))) @@ -183,9 +233,15 @@ ) ;; CHECK: (func $f (type $1) (param $ref (ref $only-has-effects-in-not-addressable-function)) - ;; CHECK-NEXT: (nop) + ;; 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)) ) ) @@ -255,7 +311,9 @@ ) ;; CHECK: (func $f (type $1) (param $ref (ref $t)) - ;; CHECK-NEXT: (nop) + ;; 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, @@ -264,5 +322,5 @@ ) ) -;; TODO exact types + ;; TODO functions that are referenced other ways besides exporting
diff --git a/test/lit/passes/global-effects-eh-legacy.wast b/test/lit/passes/global-effects-eh-legacy.wast index 65cd8db..dae6127 100644 --- a/test/lit/passes/global-effects-eh-legacy.wast +++ b/test/lit/passes/global-effects-eh-legacy.wast
@@ -327,6 +327,22 @@ ;; WITHOUT-NEXT: (call $return-call-ref-throw-and-catch) ;; WITHOUT-NEXT: ) ;; INCLUDE: (func $call-return-call-throw-and-catch (type $void) + ;; INCLUDE-NEXT: (try + ;; INCLUDE-NEXT: (do + ;; INCLUDE-NEXT: (call $return-call-indirect-throw-and-catch) + ;; INCLUDE-NEXT: ) + ;; INCLUDE-NEXT: (catch_all + ;; INCLUDE-NEXT: (nop) + ;; INCLUDE-NEXT: ) + ;; INCLUDE-NEXT: ) + ;; INCLUDE-NEXT: (try + ;; INCLUDE-NEXT: (do + ;; INCLUDE-NEXT: (call $return-call-ref-throw-and-catch) + ;; INCLUDE-NEXT: ) + ;; INCLUDE-NEXT: (catch_all + ;; INCLUDE-NEXT: (nop) + ;; INCLUDE-NEXT: ) + ;; INCLUDE-NEXT: ) ;; INCLUDE-NEXT: (call $return-call-throw-and-catch) ;; INCLUDE-NEXT: (call $return-call-indirect-throw-and-catch) ;; INCLUDE-NEXT: (call $return-call-ref-throw-and-catch)
diff --git a/test/lit/passes/global-effects.wast b/test/lit/passes/global-effects.wast index 1125f73..0691a41 100644 --- a/test/lit/passes/global-effects.wast +++ b/test/lit/passes/global-effects.wast
@@ -13,14 +13,23 @@ ;; INCLUDE: (type $void (func)) (type $void (func)) - ;; WITHOUT: (type $1 (func (result i32))) + ;; WITHOUT: (type $indirect-type (func (param f32))) + ;; INCLUDE: (type $indirect-type (func (param f32))) + (type $indirect-type (func (param f32))) - ;; WITHOUT: (type $2 (func (param i32))) + + ;; WITHOUT: (type $2 (func (param (ref $indirect-type)))) + + ;; WITHOUT: (type $3 (func (result i32))) + + ;; WITHOUT: (type $4 (func (param i32))) ;; WITHOUT: (import "a" "b" (func $import (type $void))) - ;; INCLUDE: (type $1 (func (result i32))) + ;; INCLUDE: (type $2 (func (param (ref $indirect-type)))) - ;; INCLUDE: (type $2 (func (param i32))) + ;; INCLUDE: (type $3 (func (result i32))) + + ;; INCLUDE: (type $4 (func (param i32))) ;; INCLUDE: (import "a" "b" (func $import (type $void))) (import "a" "b" (func $import)) @@ -150,7 +159,7 @@ (call $unreachable) ) - ;; WITHOUT: (func $unimportant-effects (type $1) (result i32) + ;; WITHOUT: (func $unimportant-effects (type $3) (result i32) ;; WITHOUT-NEXT: (local $x i32) ;; WITHOUT-NEXT: (local.set $x ;; WITHOUT-NEXT: (i32.const 100) @@ -159,7 +168,7 @@ ;; WITHOUT-NEXT: (local.get $x) ;; WITHOUT-NEXT: ) ;; WITHOUT-NEXT: ) - ;; INCLUDE: (func $unimportant-effects (type $1) (result i32) + ;; INCLUDE: (func $unimportant-effects (type $3) (result i32) ;; INCLUDE-NEXT: (local $x i32) ;; INCLUDE-NEXT: (local.set $x ;; INCLUDE-NEXT: (i32.const 100) @@ -380,7 +389,7 @@ ) ) - ;; WITHOUT: (func $call-throw-or-unreachable-and-catch (type $2) (param $x i32) + ;; WITHOUT: (func $call-throw-or-unreachable-and-catch (type $4) (param $x i32) ;; WITHOUT-NEXT: (block $tryend ;; WITHOUT-NEXT: (try_table (catch_all $tryend) ;; WITHOUT-NEXT: (if @@ -395,7 +404,7 @@ ;; WITHOUT-NEXT: ) ;; WITHOUT-NEXT: ) ;; WITHOUT-NEXT: ) - ;; INCLUDE: (func $call-throw-or-unreachable-and-catch (type $2) (param $x i32) + ;; INCLUDE: (func $call-throw-or-unreachable-and-catch (type $4) (param $x i32) ;; INCLUDE-NEXT: (block $tryend ;; INCLUDE-NEXT: (try_table (catch_all $tryend) ;; INCLUDE-NEXT: (if @@ -473,4 +482,46 @@ (call $cycle-with-unknown-call) (call $import) ) + + ;; WITHOUT: (func $nop-indirect (type $indirect-type) (param $0 f32) + ;; WITHOUT-NEXT: (nop) + ;; WITHOUT-NEXT: ) + ;; INCLUDE: (func $nop-indirect (type $indirect-type) (param $0 f32) + ;; INCLUDE-NEXT: (nop) + ;; INCLUDE-NEXT: ) + (func $nop-indirect (type $indirect-type) (param f32) + ) + + ;; WITHOUT: (func $unknown-indirect-call (type $2) (param $ref (ref $indirect-type)) + ;; WITHOUT-NEXT: (call_ref $indirect-type + ;; WITHOUT-NEXT: (f32.const 1) + ;; WITHOUT-NEXT: (local.get $ref) + ;; WITHOUT-NEXT: ) + ;; WITHOUT-NEXT: ) + ;; INCLUDE: (func $unknown-indirect-call (type $2) (param $ref (ref $indirect-type)) + ;; INCLUDE-NEXT: (call_ref $indirect-type + ;; INCLUDE-NEXT: (f32.const 1) + ;; INCLUDE-NEXT: (local.get $ref) + ;; INCLUDE-NEXT: ) + ;; INCLUDE-NEXT: ) + (func $unknown-indirect-call (param $ref (ref $indirect-type)) + (call_ref $indirect-type (f32.const 1) (local.get $ref)) + ) + + ;; WITHOUT: (func $calls-unknown-indirect-call (type $2) (param $ref (ref $indirect-type)) + ;; WITHOUT-NEXT: (call $unknown-indirect-call + ;; WITHOUT-NEXT: (local.get $ref) + ;; WITHOUT-NEXT: ) + ;; WITHOUT-NEXT: ) + ;; INCLUDE: (func $calls-unknown-indirect-call (type $2) (param $ref (ref $indirect-type)) + ;; INCLUDE-NEXT: (call $unknown-indirect-call + ;; INCLUDE-NEXT: (local.get $ref) + ;; INCLUDE-NEXT: ) + ;; INCLUDE-NEXT: ) + (func $calls-unknown-indirect-call (param $ref (ref $indirect-type)) + ;; In a closed world, we could determine that the ref can only possibly be + ;; $nop-direct and optimize it out. See global-effects-closed-world.wast + ;; for related tests. + (call $unknown-indirect-call (local.get $ref)) + ) )