diff options
-rw-r--r-- | src/passes/OnceReduction.cpp | 122 | ||||
-rw-r--r-- | test/lit/passes/once-reduction.wast | 506 |
2 files changed, 568 insertions, 60 deletions
diff --git a/src/passes/OnceReduction.cpp b/src/passes/OnceReduction.cpp index c1500f185..d97e19302 100644 --- a/src/passes/OnceReduction.cpp +++ b/src/passes/OnceReduction.cpp @@ -197,9 +197,10 @@ private: OptInfo& optInfo; }; -// Information in a basic block. We track relevant expressions, which are calls -// calls to "once" functions, and writes to "once" globals. +// Information in a basic block. struct BlockInfo { + // We track relevant expressions, which are call to "once" functions, and + // writes to "once" globals. std::vector<Expression*> exprs; }; @@ -312,18 +313,16 @@ struct Optimizer optimizeOnce(set->name); } } else if (auto* call = expr->dynCast<Call>()) { - if (optInfo.onceFuncs.at(call->target).is()) { + auto target = call->target; + if (optInfo.onceFuncs.at(target).is()) { // The global used by the "once" func is written. assert(call->operands.empty()); - optimizeOnce(optInfo.onceFuncs.at(call->target)); + optimizeOnce(optInfo.onceFuncs.at(target)); continue; } - // This is not a call to a "once" func. However, we may have inferred - // that it definitely sets some "once" globals before it returns, and - // we can use that information. - for (auto globalName : - optInfo.onceGlobalsSetInFuncs.at(call->target)) { + // Note as written all globals the called function is known to write. + for (auto globalName : optInfo.onceGlobalsSetInFuncs.at(target)) { onceGlobalsWritten.insert(globalName); } } else { @@ -439,7 +438,110 @@ struct OnceReduction : public Pass { lastOnceGlobalsSet = currOnceGlobalsSet; continue; } - return; + break; + } + + // Finally, apply some optimizations to "once" functions themselves. We do + // this at the end to not modify them as we go, which could confuse the main + // part of this pass right before us. + optimizeOnceBodies(optInfo, module); + } + + void optimizeOnceBodies(const OptInfo& optInfo, Module* module) { + // Track which "once" functions we remove the exit logic from, as we cannot + // create loops without exit logic, see below. + std::unordered_set<Name> removedExitLogic; + + // Iterate deterministically on functions, as the order matters (since we + // make decisions based on previous actions; see below). + for (auto& func : module->functions) { + if (!optInfo.onceFuncs.at(func->name).is()) { + // This is not a "once" function. + continue; + } + + // We optimize the case where the payload is trivial, that is where we + // have this: + // + // function foo() { + // if (!foo$once) return; // two lines of + // foo$once = 1; // early-exit code + // PAYLOAD + // } + // + // And PAYLOAD is simple. + auto* body = func->body; + auto& list = body->cast<Block>()->list; + if (list.size() == 2) { + // No payload at all; we don't need the early-exit code then. + // + // Note that this overlaps with SimplifyGlobals' optimization on + // "read-only-to-write" globals: with no payload, this global is really + // only read in order to write itself, and nothing more, so there is no + // observable behavior we need to preserve, and the global can be + // removed. We might as well handle this case here as well since we've + // done all the work up to here, and it is just one line to implement + // the nopping out. (And doing so here can accelerate the optimization + // pipeline by not needing to wait until the next SimplifyGlobals.) + ExpressionManipulator::nop(body); + continue; + } + if (list.size() != 3) { + // Something non-trivial; too many items for us to consider. + continue; + } + auto* payload = list[2]; + if (auto* call = payload->dynCast<Call>()) { + if (optInfo.onceFuncs.at(call->target).is()) { + // All this "once" function does is call another. We do not need the + // early-exit logic in this one, then, because of the following + // reasoning. We are comparing these forms: + // + // // BEFORE + // function foo() { + // if (!foo$once) return; // two lines of + // foo$once = 1; // early-exit code + // bar(); + // } + // + // to + // + // // AFTER + // function foo() { + // bar(); + // } + // + // The question is whether different behavior can be observed between + // those two. There are two cases, when we enter foo: + // + // 1. foo has been called before. Then we early-exit in BEFORE, and + // in AFTER we call bar which will early-exit (since foo was + // called, which means bar was at least entered, which set its + // global; bar might be on the stack, if it called foo, so it has + // not necessarily fully executed - this is a tricky situation to + // handle in general, like recursive imports of modules in various + // languages - but we do know bar has been *entered*, which means + // the global was set). + // 2. foo has never been called before. In this case in BEFORE we set + // the global and call bar, and in AFTER we also call bar. + // + // Thus, the behavior is the same, and we can remove the early-exit + // lines. + // + // We must be careful of loops, however: If A calls B and B calls A, + // then at least one must keep the early-exit logic, or else they + // would infinitely loop if one is called. To avoid that, we track + // which functions we remove the early-exit logic from, and never + // remove the logic if we are calling such a function. (As a result, + // the order of iteration matters here, and so the outer loop in this + // function must be deterministic.) + if (!removedExitLogic.count(call->target)) { + ExpressionManipulator::nop(list[0]); + ExpressionManipulator::nop(list[1]); + removedExitLogic.insert(func->name); + } + } + } } } }; diff --git a/test/lit/passes/once-reduction.wast b/test/lit/passes/once-reduction.wast index d76fba414..45170a0e1 100644 --- a/test/lit/passes/once-reduction.wast +++ b/test/lit/passes/once-reduction.wast @@ -8,16 +8,10 @@ (global $once (mut i32) (i32.const 0)) ;; CHECK: (func $once (type $0) - ;; CHECK-NEXT: (if - ;; CHECK-NEXT: (global.get $once) - ;; CHECK-NEXT: (return) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (global.set $once - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) (func $once - ;; A minimal "once" function. + ;; A minimal "once" function. It is so trivial we can remove its body. (if (global.get $once) (return) @@ -476,13 +470,7 @@ (global $once (mut i32) (i32.const 0)) ;; CHECK: (func $once (type $0) - ;; CHECK-NEXT: (if - ;; CHECK-NEXT: (global.get $once) - ;; CHECK-NEXT: (return) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (global.set $once - ;; CHECK-NEXT: (i32.const 42) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) (func $once (if @@ -599,13 +587,7 @@ (global $once (mut i32) (global.get $import)) ;; CHECK: (func $once (type $0) - ;; CHECK-NEXT: (if - ;; CHECK-NEXT: (global.get $once) - ;; CHECK-NEXT: (return) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (global.set $once - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) (func $once (if @@ -900,13 +882,7 @@ (global $once (mut i32) (i32.const 0)) ;; CHECK: (func $once (type $0) - ;; CHECK-NEXT: (if - ;; CHECK-NEXT: (global.get $once) - ;; CHECK-NEXT: (return) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (global.set $once - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) (func $once (if @@ -940,13 +916,7 @@ (global $once (mut i32) (i32.const 0)) ;; CHECK: (func $once (type $0) - ;; CHECK-NEXT: (if - ;; CHECK-NEXT: (global.get $once) - ;; CHECK-NEXT: (return) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (global.set $once - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) (func $once (if @@ -1081,13 +1051,7 @@ (global $once (mut i32) (i32.const 0)) ;; CHECK: (func $once (type $0) - ;; CHECK-NEXT: (if - ;; CHECK-NEXT: (global.get $once) - ;; CHECK-NEXT: (return) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (global.set $once - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) (func $once (if @@ -1287,13 +1251,7 @@ (global $once (mut i32) (i32.const 0)) ;; CHECK: (func $once (type $0) - ;; CHECK-NEXT: (if - ;; CHECK-NEXT: (global.get $once) - ;; CHECK-NEXT: (return) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (global.set $once - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) (func $once (if @@ -1427,3 +1385,451 @@ (call $once) ) ) + +;; Test calls of other "once" functions in "once" functions. +(module + ;; CHECK: (type $0 (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (global $once.1 (mut i32) (i32.const 0)) + (global $once.1 (mut i32) (i32.const 0)) + + ;; CHECK: (func $once (type $0) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $once.1) + ;; CHECK-NEXT: ) + (func $once + ;; A minimal "once" function, which calls another. We can remove the first + ;; two lines here (the early-exit logic). + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + (call $once.1) + ) + + ;; CHECK: (func $once.1 (type $0) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $once.1 + ;; Another minimal "once" function. It has no payload and we can empty it + ;; out. + (if + (global.get $once.1) + (return) + ) + (global.set $once.1 (i32.const 1)) + ) + + ;; CHECK: (func $caller (type $0) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller + ;; Call a once function more than once. The second call will become a nop. + (call $once) + (call $once) + ) + + ;; CHECK: (func $caller$1 (type $0) + ;; CHECK-NEXT: (call $once.1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller$1 + ;; Two calls to the second function. Again, the second becomes a nop. + (call $once.1) + (call $once.1) + ) + + ;; CHECK: (func $caller$2 (type $0) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once.1) + ;; CHECK-NEXT: ) + (func $caller$2 + ;; A mix of calls. We can remove the second in principle, because we know + ;; the first will call it, but we leave that for later optimizations + ;; ($once turns into a call to $once.1 that inlining will remove, and then + ;; we'll have two identical calls here). + (call $once) + (call $once.1) + ) + + ;; CHECK: (func $caller$3 (type $0) + ;; CHECK-NEXT: (call $once.1) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller$3 + ;; Reverse of the above; again we cannot optimize (as $once.1 does not call + ;; $once). + (call $once.1) + (call $once) + ) + + ;; CHECK: (func $caller$4 (type $0) + ;; CHECK-NEXT: (call $once.1) + ;; CHECK-NEXT: (call $caller$4) + ;; CHECK-NEXT: ) + (func $caller$4 + ;; Here we cannot optimize, since the second function is not a "once" + ;; function. + (call $once.1) + (call $caller$4) + ) +) + +;; Test loops between "once" functions. +(module + ;; CHECK: (type $0 (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (global $once.1 (mut i32) (i32.const 0)) + (global $once.1 (mut i32) (i32.const 0)) + + ;; CHECK: (func $once (type $0) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $once.1) + ;; CHECK-NEXT: ) + (func $once + ;; This "once" function calls another, and so we can remove the early-exit + ;; logic. + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + (call $once.1) + ) + + ;; CHECK: (func $once.1 (type $0) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once.1) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once.1 + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $once.1 + ;; This early-exit logic looks removable, since we call another "once" + ;; function. However, we remove that function's early-exit logic, so we + ;; cannot do so here (it would risk an infinite loop). + (if + (global.get $once.1) + (return) + ) + (global.set $once.1 (i32.const 1)) + (call $once) ;; This call was added. + ) + + ;; CHECK: (func $caller (type $0) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller + ;; The second call will become a nop. + (call $once) + (call $once) + ) + + ;; CHECK: (func $caller$1 (type $0) + ;; CHECK-NEXT: (call $once.1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller$1 + ;; Again, the second becomes a nop. + (call $once.1) + (call $once.1) + ) + + ;; CHECK: (func $caller$2 (type $0) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once.1) + ;; CHECK-NEXT: ) + (func $caller$2 + ;; The second could become a nop, but we leave that for later optimizations + ;; (after inlining the call to $once becomes a call to $once.1). + (call $once) + (call $once.1) + ) + + ;; CHECK: (func $caller$3 (type $0) + ;; CHECK-NEXT: (call $once.1) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller$3 + ;; Reverse order, same result (no optimization). + (call $once.1) + (call $once) + ) +) + +;; Test a dangerous triple loop. +(module + ;; CHECK: (type $0 (func)) + + ;; CHECK: (type $1 (func (param i32))) + + ;; CHECK: (import "env" "foo" (func $import (type $1) (param i32))) + (import "env" "foo" (func $import (param i32))) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (global $once.1 (mut i32) (i32.const 0)) + (global $once.1 (mut i32) (i32.const 0)) + + ;; CHECK: (global $once.2 (mut i32) (i32.const 0)) + (global $once.2 (mut i32) (i32.const 0)) + + + ;; CHECK: (func $once (type $0) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $once.1) + ;; CHECK-NEXT: (call $once.2) + ;; CHECK-NEXT: (call $import + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + (call $once.1) + ;; We cannot remove this second call. While $once.1 calls $once.2, we may + ;; be in this situation: a call started at $once.1, which calls $once + ;; (here) which then calls $once.1 which immediately exits (as the global + ;; has been set for it), and then we call $once.2 from here, which calls + ;; the other two that immediately exit as well, and then we call the import + ;; from there with value 2. Then we call it from here with value 0, and + ;; then we return to the caller, $once.1, which calls with 1, so we have + ;; 2, 0, 1. If we remove the call here to $once.2 then the order would be + ;; 0, 2, 1. + ;; + ;; The problem is that the setting of the global happens at the very start + ;; of the once function, but that does not mean we have executed the body + ;; yet, and without executing it, we cannot infer anything about other + ;; globals. + (call $once.2) + (call $import + (i32.const 0) + ) + ) + + ;; CHECK: (func $once.1 (type $0) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once.1) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once.1 + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once.2) + ;; CHECK-NEXT: (call $import + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $once.1 + (if + (global.get $once.1) + (return) + ) + (global.set $once.1 (i32.const 1)) + (call $once) + ;; As above, by symmetry, we cannot remove this second call. + (call $once.2) + (call $import + (i32.const 1) + ) + ) + + ;; CHECK: (func $once.2 (type $0) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once.2) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once.2 + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once.1) + ;; CHECK-NEXT: (call $import + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $once.2 + (if + (global.get $once.2) + (return) + ) + (global.set $once.2 (i32.const 1)) + (call $once) + ;; As above, by symmetry, we cannot remove this second call. + (call $once.1) + (call $import + (i32.const 2) + ) + ) +) + +;; Test a self-loop. +(module + ;; CHECK: (type $0 (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + + ;; CHECK: (func $once (type $0) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ;; A recursive call. This of course does not recurse infinitely since the + ;; next call early exits, as the global is set, and for that reason we can + ;; optimize this to a nop. + (call $once) + ) + + ;; CHECK: (func $caller (type $0) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller + ;; The second call will become a nop. + (call $once) + (call $once) + ) +) + +;; Calls from non-"once" functions to "once" functions. +(module + ;; CHECK: (type $0 (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once (type $0) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $once + ;; A minimal "once" function. + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $do-once (type $0) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $do-once + ;; Call the once function. + (call $once) + ) + + ;; CHECK: (func $caller (type $0) + ;; CHECK-NEXT: (call $do-once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller + ;; The first proves the second is not needed, and can be nopped. + (call $do-once) + (call $once) + ) + + ;; CHECK: (func $caller2 (type $0) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $do-once) + ;; CHECK-NEXT: ) + (func $caller2 + ;; Reverse order of the above. We cannot optimize here: $do-once does + ;; nothing aside from call $once, but all we know is that it is not a "once" + ;; function itself, and we only remove calls to "once" functions. + (call $once) + (call $do-once) + ) +) + +;; Calls from "once" functions to non-"once" functions. +(module + ;; CHECK: (type $0 (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once (type $0) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $other) + ;; CHECK-NEXT: ) + (func $once + ;; We should not remove this early-exit logic. + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ;; A call to a non-"once" function. + (call $other) + ) + + ;; CHECK: (func $other (type $0) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $other + ) + + ;; CHECK: (func $caller (type $0) + ;; CHECK-NEXT: (call $other) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + ;; There is nothing to optimize here. + (call $other) + (call $once) + ) + + ;; CHECK: (func $caller2 (type $0) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $other) + ;; CHECK-NEXT: ) + (func $caller2 + ;; Reverse order of the above. Also nothing to do. + (call $once) + (call $other) + ) +) |