diff options
| -rw-r--r-- | src/passes/GlobalEffects.cpp | 189 | ||||
| -rw-r--r-- | test/lit/passes/global-effects.wast | 121 | ||||
| -rw-r--r-- | test/lit/passes/global-effects_simplify-locals.wast | 113 |
3 files changed, 386 insertions, 37 deletions
diff --git a/src/passes/GlobalEffects.cpp b/src/passes/GlobalEffects.cpp index a2c34b644..47c4d54ab 100644 --- a/src/passes/GlobalEffects.cpp +++ b/src/passes/GlobalEffects.cpp @@ -22,60 +22,183 @@ #include "ir/effects.h" #include "ir/module-utils.h" #include "pass.h" +#include "support/unique_deferring_queue.h" #include "wasm.h" namespace wasm { struct GenerateGlobalEffects : public Pass { void run(Module* module) override { - // TODO: Full transitive closure of effects. For now, we just look at each - // function by itself. + // First, we do a scan of each function to see what effects they have, + // including which functions they call directly (so that we can compute + // transitive effects later). - auto& funcEffectsMap = getPassOptions().funcEffectsMap; - - // First, clear any previous effects. - funcEffectsMap.reset(); + struct FuncInfo { + // Effects in this function. + std::optional<EffectAnalyzer> effects; - // When we find useful effects, we'll save them. If we can't find anything, - // the final map we emit will not have an entry there at all. - using PossibleEffects = std::unique_ptr<EffectAnalyzer>; + // Directly-called functions from this function. + std::unordered_set<Name> calledFunctions; + }; - ModuleUtils::ParallelFunctionAnalysis<PossibleEffects> analysis( - *module, [&](Function* func, PossibleEffects& storedEffects) { + ModuleUtils::ParallelFunctionAnalysis<FuncInfo> 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 - // map. + // map (which we do by not setting funcInfo.effects). return; } // Gather the effects. - auto effects = - std::make_unique<EffectAnalyzer>(getPassOptions(), *module, func); - - // If the body has a call, give up - that means we can't infer a more - // specific set of effects than the pessimistic case of just assuming - // any call to here is an arbitrary call. (See the TODO above for - // improvements.) - if (effects->calls) { - return; + funcInfo.effects.emplace(getPassOptions(), *module, func); + + if (funcInfo.effects->calls) { + // There are calls in this function, which we will analyze in detail. + // Clear the |calls| field first, and we'll handle calls of all sorts + // below. + funcInfo.effects->calls = false; + + // Clear throws as well, as we are "forgetting" calls right now, and + // want to forget their throwing effect as well. If we see something + // else that throws, below, then we'll note that there. + funcInfo.effects->throws_ = false; + + struct CallScanner + : public PostWalker<CallScanner, + UnifiedExpressionVisitor<CallScanner>> { + Module& wasm; + PassOptions& options; + FuncInfo& funcInfo; + + CallScanner(Module& wasm, PassOptions& options, FuncInfo& funcInfo) + : wasm(wasm), options(options), funcInfo(funcInfo) {} + + void visitExpression(Expression* curr) { + ShallowEffectAnalyzer effects(options, wasm, curr); + if (auto* call = curr->dynCast<Call>()) { + // Note the direct call. + funcInfo.calledFunctions.insert(call->target); + } else if (effects.calls) { + // This is an indirect call of some sort, so we must assume the + // worst. To do so, clear the effects, which indicates nothing + // is known (so anything is possible). + // TODO: We could group effects by function type etc. + funcInfo.effects.reset(); + } else { + // No call here, but update throwing if we see it. (Only do so, + // however, if we have effects; if we cleared it - see before - + // then we assume the worst anyhow, and have nothing to update.) + if (effects.throws_ && funcInfo.effects) { + funcInfo.effects->throws_ = true; + } + } + } + }; + CallScanner scanner(*module, getPassOptions(), funcInfo); + scanner.walkFunction(func); } - - // Save the useful effects we found. - storedEffects = std::move(effects); }); - // Generate the final data structure. - for (auto& [func, possibleEffects] : analysis.map) { - if (possibleEffects) { - // Only allocate a new funcEffectsMap if we actually have data for it - // (which might make later effect computation slightly faster, to - // quickly skip the funcEffectsMap code path). - if (!funcEffectsMap) { - funcEffectsMap = std::make_shared<FuncEffectsMap>(); + // Compute the transitive closure of effects. To do so, first construct for + // each function a list of the functions that it is called by (so we need to + // propogate its effects to them), and then we'll construct the closure of + // that. + // + // callers[foo] = [func that calls foo, another func that calls foo, ..] + // + std::unordered_map<Name, std::unordered_set<Name>> callers; + + // Our work queue contains info about a new call pair: a call from a caller + // to a called function, that is information we then apply and propagate. + using CallPair = std::pair<Name, Name>; // { caller, called } + UniqueDeferredQueue<CallPair> work; + for (auto& [func, info] : analysis.map) { + for (auto& called : info.calledFunctions) { + work.push({func->name, called}); + } + } + + // Compute the transitive closure of the call graph, that is, fill out + // |callers| so that it contains the list of all callers - even through a + // chain - of each function. + while (!work.empty()) { + auto [caller, called] = work.pop(); + + // We must not already have an entry for this call (that would imply we + // are doing wasted work). + assert(!callers[called].count(caller)); + + // Apply the new call information. + callers[called].insert(caller); + + // We just learned that |caller| calls |called|. It also calls + // transitively, which we need to propagate to all places unaware of that + // information yet. + // + // caller => called => called by called + // + auto& calledInfo = analysis.map[module->getFunction(called)]; + for (auto calledByCalled : calledInfo.calledFunctions) { + if (!callers[calledByCalled].count(caller)) { + work.push({caller, calledByCalled}); + } + } + } + + // Now that we have transitively propagated all static calls, apply that + // information. First, apply infinite recursion: if a function can call + // itself then it might recurse infinitely, which we consider an effect (a + // trap). + for (auto& [func, info] : analysis.map) { + if (callers[func->name].count(func->name)) { + if (info.effects) { + info.effects->trap = true; + } + } + } + + // Next, apply function effects to their callers. + for (auto& [func, info] : analysis.map) { + auto& funcEffects = info.effects; + + for (auto& caller : callers[func->name]) { + auto& callerEffects = analysis.map[module->getFunction(caller)].effects; + if (!callerEffects) { + // Nothing is known for the caller, which is already the worst case. + continue; } - funcEffectsMap->emplace(func->name, *possibleEffects); + + if (!funcEffects) { + // Nothing is known for the called function, which means nothing is + // known for the caller either. + callerEffects.reset(); + continue; + } + + // Add func's effects to the caller. + callerEffects->mergeIn(*funcEffects); + } + } + + // Generate the final data structure, starting from a blank slate where + // nothing is known. + auto& funcEffectsMap = getPassOptions().funcEffectsMap; + funcEffectsMap.reset(); + + for (auto& [func, info] : analysis.map) { + if (!info.effects) { + // Add no entry to funcEffectsMap, since nothing is known. + continue; + } + + // Only allocate a new funcEffectsMap here when we actually have data for + // it (which might make later effect computation slightly faster, to + // quickly skip the funcEffectsMap code path). + if (!funcEffectsMap) { + funcEffectsMap = std::make_shared<FuncEffectsMap>(); } + funcEffectsMap->emplace(func->name, *info.effects); } } }; diff --git a/test/lit/passes/global-effects.wast b/test/lit/passes/global-effects.wast index e5ea1b429..066604679 100644 --- a/test/lit/passes/global-effects.wast +++ b/test/lit/passes/global-effects.wast @@ -8,12 +8,15 @@ ;; RUN: foreach %s %t wasm-opt -all --generate-global-effects --discard-global-effects --vacuum -S -o - | filecheck %s --check-prefix DISCARD (module + ;; WITHOUT: (type $0 (func)) ;; WITHOUT: (type $1 (func (result i32))) ;; WITHOUT: (type $2 (func (param i32))) + ;; WITHOUT: (import "a" "b" (func $import (type $0))) + ;; WITHOUT: (tag $tag) ;; INCLUDE: (type $0 (func)) @@ -21,6 +24,8 @@ ;; INCLUDE: (type $2 (func (param i32))) + ;; INCLUDE: (import "a" "b" (func $import (type $0))) + ;; INCLUDE: (tag $tag) ;; DISCARD: (type $0 (func)) @@ -28,9 +33,13 @@ ;; DISCARD: (type $2 (func (param i32))) + ;; DISCARD: (import "a" "b" (func $import (type $0))) + ;; DISCARD: (tag $tag) (tag $tag) + (import "a" "b" (func $import)) + ;; WITHOUT: (func $main (type $0) ;; WITHOUT-NEXT: (call $nop) ;; WITHOUT-NEXT: (call $unreachable) @@ -39,11 +48,14 @@ ;; WITHOUT-NEXT: (drop ;; WITHOUT-NEXT: (call $unimportant-effects) ;; WITHOUT-NEXT: ) + ;; WITHOUT-NEXT: (call $throw) + ;; WITHOUT-NEXT: (call $throw-and-import) ;; WITHOUT-NEXT: ) ;; INCLUDE: (func $main (type $0) ;; INCLUDE-NEXT: (call $unreachable) - ;; INCLUDE-NEXT: (call $call-nop) ;; INCLUDE-NEXT: (call $call-unreachable) + ;; INCLUDE-NEXT: (call $throw) + ;; INCLUDE-NEXT: (call $throw-and-import) ;; INCLUDE-NEXT: ) ;; DISCARD: (func $main (type $0) ;; DISCARD-NEXT: (call $nop) @@ -53,6 +65,8 @@ ;; DISCARD-NEXT: (drop ;; DISCARD-NEXT: (call $unimportant-effects) ;; DISCARD-NEXT: ) + ;; DISCARD-NEXT: (call $throw) + ;; DISCARD-NEXT: (call $throw-and-import) ;; DISCARD-NEXT: ) (func $main ;; Calling a function with no effects can be optimized away in INCLUDE (but @@ -61,8 +75,7 @@ ;; Calling a function with effects cannot. (call $unreachable) ;; Calling something that calls something with no effects can be optimized - ;; away in principle, but atm we don't look that far, so this is not - ;; optimized. + ;; away, since we compute transitive effects (call $call-nop) ;; Calling something that calls something with effects cannot. (call $call-unreachable) @@ -71,6 +84,10 @@ (drop (call $unimportant-effects) ) + ;; A throwing function cannot be removed. + (call $throw) + ;; A function that throws and calls an import definitely cannot be removed. + (call $throw-and-import) ) ;; WITHOUT: (func $cycle (type $0) @@ -88,6 +105,33 @@ (call $cycle) ) + ;; WITHOUT: (func $cycle-1 (type $0) + ;; WITHOUT-NEXT: (call $cycle-2) + ;; WITHOUT-NEXT: ) + ;; INCLUDE: (func $cycle-1 (type $0) + ;; INCLUDE-NEXT: (call $cycle-2) + ;; INCLUDE-NEXT: ) + ;; DISCARD: (func $cycle-1 (type $0) + ;; DISCARD-NEXT: (call $cycle-2) + ;; DISCARD-NEXT: ) + (func $cycle-1 + ;; $cycle-1 and -2 form a cycle together, in which no call can be removed. + (call $cycle-2) + ) + + ;; WITHOUT: (func $cycle-2 (type $0) + ;; WITHOUT-NEXT: (call $cycle-1) + ;; WITHOUT-NEXT: ) + ;; INCLUDE: (func $cycle-2 (type $0) + ;; INCLUDE-NEXT: (call $cycle-1) + ;; INCLUDE-NEXT: ) + ;; DISCARD: (func $cycle-2 (type $0) + ;; DISCARD-NEXT: (call $cycle-1) + ;; DISCARD-NEXT: ) + (func $cycle-2 + (call $cycle-1) + ) + ;; WITHOUT: (func $nop (type $0) ;; WITHOUT-NEXT: (nop) ;; WITHOUT-NEXT: ) @@ -190,9 +234,24 @@ ;; WITHOUT-NEXT: (nop) ;; WITHOUT-NEXT: ) ;; WITHOUT-NEXT: ) + ;; WITHOUT-NEXT: (try $try0 + ;; WITHOUT-NEXT: (do + ;; WITHOUT-NEXT: (call $throw-and-import) + ;; WITHOUT-NEXT: ) + ;; WITHOUT-NEXT: (catch_all + ;; WITHOUT-NEXT: (nop) + ;; WITHOUT-NEXT: ) + ;; WITHOUT-NEXT: ) ;; WITHOUT-NEXT: ) ;; INCLUDE: (func $call-throw-and-catch (type $0) - ;; INCLUDE-NEXT: (nop) + ;; INCLUDE-NEXT: (try $try0 + ;; INCLUDE-NEXT: (do + ;; INCLUDE-NEXT: (call $throw-and-import) + ;; INCLUDE-NEXT: ) + ;; INCLUDE-NEXT: (catch_all + ;; INCLUDE-NEXT: (nop) + ;; INCLUDE-NEXT: ) + ;; INCLUDE-NEXT: ) ;; INCLUDE-NEXT: ) ;; DISCARD: (func $call-throw-and-catch (type $0) ;; DISCARD-NEXT: (try $try @@ -203,6 +262,14 @@ ;; DISCARD-NEXT: (nop) ;; DISCARD-NEXT: ) ;; DISCARD-NEXT: ) + ;; DISCARD-NEXT: (try $try0 + ;; DISCARD-NEXT: (do + ;; DISCARD-NEXT: (call $throw-and-import) + ;; DISCARD-NEXT: ) + ;; DISCARD-NEXT: (catch_all + ;; DISCARD-NEXT: (nop) + ;; DISCARD-NEXT: ) + ;; DISCARD-NEXT: ) ;; DISCARD-NEXT: ) (func $call-throw-and-catch (try @@ -214,6 +281,13 @@ ) (catch_all) ) + (try + (do + ;; This call both throws and calls an import, and cannot be removed. + (call $throw-and-import) + ) + (catch_all) + ) ) ;; WITHOUT: (func $call-unreachable-and-catch (type $0) @@ -320,4 +394,43 @@ (func $throw (throw $tag) ) + + ;; WITHOUT: (func $throw-and-import (type $0) + ;; WITHOUT-NEXT: (throw $tag) + ;; WITHOUT-NEXT: ) + ;; INCLUDE: (func $throw-and-import (type $0) + ;; INCLUDE-NEXT: (throw $tag) + ;; INCLUDE-NEXT: ) + ;; DISCARD: (func $throw-and-import (type $0) + ;; DISCARD-NEXT: (throw $tag) + ;; DISCARD-NEXT: ) + (func $throw-and-import + (if + (i32.const 1) + (throw $tag) + (call $import) + ) + ) + + ;; WITHOUT: (func $cycle-with-unknown-call (type $0) + ;; WITHOUT-NEXT: (call $cycle-with-unknown-call) + ;; WITHOUT-NEXT: (call $import) + ;; WITHOUT-NEXT: ) + ;; INCLUDE: (func $cycle-with-unknown-call (type $0) + ;; INCLUDE-NEXT: (call $cycle-with-unknown-call) + ;; INCLUDE-NEXT: (call $import) + ;; INCLUDE-NEXT: ) + ;; DISCARD: (func $cycle-with-unknown-call (type $0) + ;; DISCARD-NEXT: (call $cycle-with-unknown-call) + ;; DISCARD-NEXT: (call $import) + ;; DISCARD-NEXT: ) + (func $cycle-with-unknown-call + ;; This function can not only call itself recursively, but also calls an + ;; import. We should not remove anything here, and not error during the + ;; analysis (this guards against a bug where the import would make us toss + ;; away the effects object, and the infinite loop makes us set a property on + ;; that object, so it must check the object still exists). + (call $cycle-with-unknown-call) + (call $import) + ) ) diff --git a/test/lit/passes/global-effects_simplify-locals.wast b/test/lit/passes/global-effects_simplify-locals.wast new file mode 100644 index 000000000..3053c59f0 --- /dev/null +++ b/test/lit/passes/global-effects_simplify-locals.wast @@ -0,0 +1,113 @@ +;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited. + +;; Test that global effects let us optimize more in a pass like simplify-locals. + +;; RUN: foreach %s %t wasm-opt --simplify-locals -S -o - | filecheck %s --check-prefix NORMAL_EFFECTS +;; RUN: foreach %s %t wasm-opt --generate-global-effects --simplify-locals -S -o - | filecheck %s --check-prefix GLOBAL_EFFECTS + +(module + ;; NORMAL_EFFECTS: (type $0 (func)) + + ;; NORMAL_EFFECTS: (global $global (mut i32) (i32.const 0)) + ;; GLOBAL_EFFECTS: (type $0 (func)) + + ;; GLOBAL_EFFECTS: (global $global (mut i32) (i32.const 0)) + (global $global (mut i32) (i32.const 0)) + + ;; NORMAL_EFFECTS: (func $past-get + ;; NORMAL_EFFECTS-NEXT: (local $x i32) + ;; NORMAL_EFFECTS-NEXT: (local.set $x + ;; NORMAL_EFFECTS-NEXT: (global.get $global) + ;; NORMAL_EFFECTS-NEXT: ) + ;; NORMAL_EFFECTS-NEXT: (call $get-global) + ;; NORMAL_EFFECTS-NEXT: (drop + ;; NORMAL_EFFECTS-NEXT: (local.get $x) + ;; NORMAL_EFFECTS-NEXT: ) + ;; NORMAL_EFFECTS-NEXT: ) + ;; GLOBAL_EFFECTS: (func $past-get + ;; GLOBAL_EFFECTS-NEXT: (local $x i32) + ;; GLOBAL_EFFECTS-NEXT: (nop) + ;; GLOBAL_EFFECTS-NEXT: (call $get-global) + ;; GLOBAL_EFFECTS-NEXT: (drop + ;; GLOBAL_EFFECTS-NEXT: (global.get $global) + ;; GLOBAL_EFFECTS-NEXT: ) + ;; GLOBAL_EFFECTS-NEXT: ) + (func $past-get + (local $x i32) + ;; We can move this set past the call (when we have global effects), since + ;; the call only reads the global. + (local.set $x + (global.get $global) + ) + (call $get-global) + (drop + (local.get $x) + ) + ) + + ;; NORMAL_EFFECTS: (func $past-set + ;; NORMAL_EFFECTS-NEXT: (local $x i32) + ;; NORMAL_EFFECTS-NEXT: (local.set $x + ;; NORMAL_EFFECTS-NEXT: (global.get $global) + ;; NORMAL_EFFECTS-NEXT: ) + ;; NORMAL_EFFECTS-NEXT: (call $set-global) + ;; NORMAL_EFFECTS-NEXT: (drop + ;; NORMAL_EFFECTS-NEXT: (local.get $x) + ;; NORMAL_EFFECTS-NEXT: ) + ;; NORMAL_EFFECTS-NEXT: ) + ;; GLOBAL_EFFECTS: (func $past-set + ;; GLOBAL_EFFECTS-NEXT: (local $x i32) + ;; GLOBAL_EFFECTS-NEXT: (local.set $x + ;; GLOBAL_EFFECTS-NEXT: (global.get $global) + ;; GLOBAL_EFFECTS-NEXT: ) + ;; GLOBAL_EFFECTS-NEXT: (call $set-global) + ;; GLOBAL_EFFECTS-NEXT: (drop + ;; GLOBAL_EFFECTS-NEXT: (local.get $x) + ;; GLOBAL_EFFECTS-NEXT: ) + ;; GLOBAL_EFFECTS-NEXT: ) + (func $past-set + (local $x i32) + ;; We cannot move this set past the call, since the call writes the global. + (local.set $x + (global.get $global) + ) + (call $set-global) + (drop + (local.get $x) + ) + ) + + ;; NORMAL_EFFECTS: (func $set-global + ;; NORMAL_EFFECTS-NEXT: (global.set $global + ;; NORMAL_EFFECTS-NEXT: (i32.const 1) + ;; NORMAL_EFFECTS-NEXT: ) + ;; NORMAL_EFFECTS-NEXT: ) + ;; GLOBAL_EFFECTS: (func $set-global + ;; GLOBAL_EFFECTS-NEXT: (global.set $global + ;; GLOBAL_EFFECTS-NEXT: (i32.const 1) + ;; GLOBAL_EFFECTS-NEXT: ) + ;; GLOBAL_EFFECTS-NEXT: ) + (func $set-global + ;; Helper function. + (global.set $global + (i32.const 1) + ) + ) + + ;; NORMAL_EFFECTS: (func $get-global + ;; NORMAL_EFFECTS-NEXT: (drop + ;; NORMAL_EFFECTS-NEXT: (global.get $global) + ;; NORMAL_EFFECTS-NEXT: ) + ;; NORMAL_EFFECTS-NEXT: ) + ;; GLOBAL_EFFECTS: (func $get-global + ;; GLOBAL_EFFECTS-NEXT: (drop + ;; GLOBAL_EFFECTS-NEXT: (global.get $global) + ;; GLOBAL_EFFECTS-NEXT: ) + ;; GLOBAL_EFFECTS-NEXT: ) + (func $get-global + ;; Helper function. + (drop + (global.get $global) + ) + ) +) |