diff options
| -rwxr-xr-x | scripts/fuzz_opt.py | 6 | ||||
| -rw-r--r-- | src/cfg/domtree.h | 7 | ||||
| -rw-r--r-- | src/passes/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/passes/OnceReduction.cpp | 444 | ||||
| -rw-r--r-- | src/passes/pass.cpp | 6 | ||||
| -rw-r--r-- | src/passes/passes.h | 1 | ||||
| -rw-r--r-- | test/lit/help/optimization-opts.test | 3 | ||||
| -rw-r--r-- | test/lit/passes/once-reduction.wast | 1429 |
8 files changed, 1894 insertions, 3 deletions
diff --git a/scripts/fuzz_opt.py b/scripts/fuzz_opt.py index 3e2d83e34..9ccdeb1e4 100755 --- a/scripts/fuzz_opt.py +++ b/scripts/fuzz_opt.py @@ -165,8 +165,13 @@ def randomize_fuzz_settings(): IMPORTANT_INITIAL_CONTENTS = [ + # Perenially-important passes os.path.join('lit', 'passes', 'optimize-instructions.wast'), os.path.join('passes', 'optimize-instructions_fuzz-exec.wast'), + + # Recently-added or modified passes. These can be added to and pruned + # frequently. + os.path.join('lit', 'passes', 'once-reduction.wast'), ] IMPORTANT_INITIAL_CONTENTS = [os.path.join(shared.get_test_dir('.'), t) for t in IMPORTANT_INITIAL_CONTENTS] @@ -1058,6 +1063,7 @@ opt_choices = [ ["--memory-packing"], ["--merge-blocks"], ['--merge-locals'], + ['--once-reduction'], ["--optimize-instructions"], ["--optimize-stack-ir"], ["--generate-stack-ir", "--optimize-stack-ir"], diff --git a/src/cfg/domtree.h b/src/cfg/domtree.h index 5e54f7c32..5753a3114 100644 --- a/src/cfg/domtree.h +++ b/src/cfg/domtree.h @@ -47,6 +47,10 @@ namespace wasm { template<typename BasicBlock> struct DomTree { std::vector<Index> iDoms; + // Use a nonsense value to indicate what has yet to be initialized or what is + // irrelevant. + enum { nonsense = Index(-1) }; + DomTree(std::vector<std::unique_ptr<BasicBlock>>& blocks); }; @@ -84,9 +88,6 @@ DomTree<BasicBlock>::DomTree(std::vector<std::unique_ptr<BasicBlock>>& blocks) { blockIndices[blocks[i].get()] = i; } - // Use a nonsense value to indicate what has yet to be initialized. - const Index nonsense = -1; - // Initialize the iDoms array. The entry starts with its own index, which is // used as a guard value in effect (we will never process it, and we will fix // up this value at the very end). All other nodes start with a nonsense value diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt index ad5600f1b..b61b895ef 100644 --- a/src/passes/CMakeLists.txt +++ b/src/passes/CMakeLists.txt @@ -50,6 +50,7 @@ set(passes_SOURCES NameList.cpp NameTypes.cpp NoExitRuntime.cpp + OnceReduction.cpp OptimizeAddedConstants.cpp OptimizeInstructions.cpp OptimizeForJS.cpp diff --git a/src/passes/OnceReduction.cpp b/src/passes/OnceReduction.cpp new file mode 100644 index 000000000..73e221c69 --- /dev/null +++ b/src/passes/OnceReduction.cpp @@ -0,0 +1,444 @@ +/* + * Copyright 2021 WebAssembly Community Group participants + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +// +// Reduces the amount of calls to functions that only run once. A "run-once" +// or "once" function is a function guarded by a global to make sure it runs a +// single time: +// +// global foo$once = 0; +// +// function foo() { +// if (foo$once) return; +// foo$once = 1; +// ..do some work.. +// } +// +// If we verify that there are no other kind of sets to that global - that is, +// it is only used to guard this code - then we can remove subsequent calls to +// the function, +// +// foo(); +// ..stuff.. +// foo(); // this call can be removed +// +// The latter call can be removed since it has definitely run by then. +// +// TODO: "Once" globals are effectively boolean in that all non-zero values are +// indistinguishable, and so we could rewrite them all to be 1. +// + +#include <atomic> + +#include "cfg/domtree.h" +#include "ir/utils.h" +#include "pass.h" +#include "support/unique_deferring_queue.h" +#include "wasm-builder.h" +#include "wasm.h" + +namespace wasm { + +namespace { + +struct OptInfo { + // Maps global names to whether they are possible indicators of "once" + // functions. A "once" global has these properties: + // + // * They are only ever written to with non-zero values. + // * They are never read from except in the beginning of a "once" function + // (otherwise, execution might be affected by the specific values of the + // global, instead of just using it to guard the "once" function). + // + // Those properties ensure that the global is monotonic in the sense that it + // begins at zero and, if they are written to, will only receive a non-zero + // value - they never return to 0. + std::unordered_map<Name, std::atomic<bool>> onceGlobals; + + // Maps functions to whether they are "once", by indicating the global that + // they use for that purpose. An empty name means they are not "once". + std::unordered_map<Name, Name> onceFuncs; + + // For each function, the "once" globals that are definitely set after calling + // it. If the function is "once" itself, that is included, but it also + // includes any other "once" functions we definitely call, and so forth. + // The "new" version is written to in each iteration, and then swapped with + // the main one (to avoid reading and writing in parallel). + std::unordered_map<Name, std::unordered_set<Name>> onceGlobalsSetInFuncs, + newOnceGlobalsSetInFuncs; +}; + +struct Scanner : public WalkerPass<PostWalker<Scanner>> { + bool isFunctionParallel() override { return true; } + + Scanner(OptInfo& optInfo) : optInfo(optInfo) {} + + Scanner* create() override { return new Scanner(optInfo); } + + // All the globals we read from. Any read of a global prevents us from + // optimizing, unless it is the single read at the top of an "only" function + // (as other reads might be used to check for the value of the global in + // complex ways that we do not want to try to reason about). + std::unordered_map<Name, Index> readGlobals; + + void visitGlobalGet(GlobalGet* curr) { readGlobals[curr->name]++; } + + void visitGlobalSet(GlobalSet* curr) { + if (!curr->value->type.isInteger()) { + // This is either a type we don't care about, or an unreachable set which + // we also don't care about. + return; + } + + if (auto* c = curr->value->dynCast<Const>()) { + if (c->value.getInteger() > 0) { + // This writes a non-zero constant, which is what we hoped for. + return; + } + } + + // This is not a constant, or it is zero - failure. + optInfo.onceGlobals.at(curr->name) = false; + } + + void visitFunction(Function* curr) { + // TODO: support params and results? + if (curr->getParams() == Type::none && curr->getResults() == Type::none) { + auto global = getOnceGlobal(curr->body); + if (global.is()) { + // This is a "once" function, as best we can tell for now. Further + // information may cause a problem, say, if the global is used in a bad + // way in another function, so we may undo this. + optInfo.onceFuncs.at(curr->name) = global; + + // We can ignore the get in the "once" pattern at the top of the + // function. + readGlobals[global]--; + } + } + + for (auto& kv : readGlobals) { + auto global = kv.first; + auto count = kv.second; + if (count > 0) { + // This global has reads we cannot reason about, so do not optimize it. + optInfo.onceGlobals.at(global) = false; + } + } + } + + // Check if a function body is in the "once" pattern. Return the name of the + // global if so, or an empty name otherwise. + // + // TODO: This pattern can show up in random places and not just at the top of + // the "once" function - say, if that function was inlined somewhere - + // so it might be good to look for the more general pattern everywhere. + // TODO: Handle related patterns like if (!once) { .. }, but other opts will + // tend to normalize to this form anyhow. + Name getOnceGlobal(Expression* body) { + // Look the pattern mentioned above: + // + // function foo() { + // if (foo$once) return; + // foo$once = 1; + // ... + // + auto* block = body->dynCast<Block>(); + if (!block) { + return Name(); + } + auto& list = block->list; + if (list.size() < 2) { + return Name(); + } + auto* iff = list[0]->dynCast<If>(); + if (!iff) { + return Name(); + } + auto* get = iff->condition->dynCast<GlobalGet>(); + if (!get) { + return Name(); + } + if (!iff->ifTrue->is<Return>() || iff->ifFalse) { + return Name(); + } + auto* set = list[1]->dynCast<GlobalSet>(); + + // Note that we have already checked the set's value earlier - that if it is + // reached then it writes a non-zero constant. Those are properties that we + // need from all sets. For this specific set, we also need it to actually + // perform the write, that is, to not be unreachable (otherwise, the global + // is not written here, and the function can execute more than once). + if (!set || set->name != get->name || set->type == Type::unreachable) { + return Name(); + } + return get->name; + } + +private: + OptInfo& optInfo; +}; + +// Information in a basic block. We track relevant expressions, which are calls +// calls to "once" functions, and writes to "once" globals. +struct BlockInfo { + std::vector<Expression*> exprs; +}; + +// Performs optimization in all functions. This reads onceGlobalsSetInFuncs in +// order to know what "once" globals are written by each function (so that when +// we see a call, we can infer things), and when it finishes with a function it +// has learned which "once" globals it must set, and it then writes out +// newOnceGlobalsSetInFuncs with that result. Later iterations will then use +// those values in place of onceGlobalsSetInFuncs, which propagate things to +// callers. This in effect mixes local optimization with the global propagation +// - as we need to run the full local optimization in order to infer the new +// values for onceGlobalsSetInFuncs, that is unavoidable (in principle, we could +// also do a full propagation to a fixed point in between running local +// optimization, but that would require more code - it might be more efficient, +// though). +struct Optimizer + : public WalkerPass<CFGWalker<Optimizer, Visitor<Optimizer>, BlockInfo>> { + bool isFunctionParallel() override { return true; } + + Optimizer(OptInfo& optInfo) : optInfo(optInfo) {} + + Optimizer* create() override { return new Optimizer(optInfo); } + + void visitGlobalSet(GlobalSet* curr) { + if (currBasicBlock) { + currBasicBlock->contents.exprs.push_back(curr); + } + } + + void visitCall(Call* curr) { + if (currBasicBlock) { + currBasicBlock->contents.exprs.push_back(curr); + } + } + + void doWalkFunction(Function* func) { + using Parent = + WalkerPass<CFGWalker<Optimizer, Visitor<Optimizer>, BlockInfo>>; + + // Walk the function to builds the CFG. + Parent::doWalkFunction(func); + if (basicBlocks.empty()) { + return; + } + + // Build a dominator tree, which then tells us what to remove: if a call + // appears in block A, then we do not need to make any calls in any blocks + // dominated by A. + DomTree<Parent::BasicBlock> domTree(basicBlocks); + + // Perform the work by going through the blocks in reverse postorder and + // filling out which "once" globals have been written to. + + // Each index in this vector is the set of "once" globals written to in the + // basic block with the same index. + std::vector<std::unordered_set<Name>> onceGlobalsWrittenVec; + auto numBlocks = basicBlocks.size(); + onceGlobalsWrittenVec.resize(numBlocks); + + for (Index i = 0; i < numBlocks; i++) { + auto* block = basicBlocks[i].get(); + + // Note that we take a reference here, which is how the data we accumulate + // ends up stored. The blocks we dominate will see it later. + auto& onceGlobalsWritten = onceGlobalsWrittenVec[i]; + + // Note information from our immediate dominator. + // TODO: we could also intersect information from all of our preds. + auto parent = domTree.iDoms[i]; + if (parent == domTree.nonsense) { + // This is either the entry node (which we need to process), or an + // unreachable block (which we do not need to process - we leave that to + // DCE). + if (i > 0) { + continue; + } + } else { + // This block has an immediate dominator, so we know that everything + // written to there can be assumed written. + onceGlobalsWritten = onceGlobalsWrittenVec[parent]; + } + + // Process the block's expressions. + auto& exprs = block->contents.exprs; + for (auto* expr : exprs) { + // Given the name of a "once" global that is written by this + // instruction, optimize. + auto optimizeOnce = [&](Name globalName) { + assert(optInfo.onceGlobals.at(globalName)); + if (onceGlobalsWritten.count(globalName)) { + // This global has already been written, so this expr is not needed, + // regardless of whether it is a global.set or a call. + // + // Note that assertions below verify that there are no children that + // we need to keep around, and so we can just nop the entire node. + ExpressionManipulator::nop(expr); + } else { + // From here on, this global is set, hopefully allowing us to + // optimize away others. + onceGlobalsWritten.insert(globalName); + } + }; + + if (auto* set = expr->dynCast<GlobalSet>()) { + if (optInfo.onceGlobals.at(set->name)) { + // This global is written. + assert(set->value->is<Const>()); + optimizeOnce(set->name); + } + } else if (auto* call = expr->dynCast<Call>()) { + if (optInfo.onceFuncs.at(call->target).is()) { + // The global used by the "once" func is written. + assert(call->operands.empty()); + optimizeOnce(optInfo.onceFuncs.at(call->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)) { + onceGlobalsWritten.insert(globalName); + } + } else { + WASM_UNREACHABLE("invalid expr"); + } + } + } + + // As a result of the above optimization, we know which "once" globals are + // definitely written in this function. Regardless of whether this is a + // "once" function itself, that set of globals can be used in further + // optimizations, as any call to this function must set those. + // TODO: Aside from the entry block, we could intersect all the exit blocks. + optInfo.newOnceGlobalsSetInFuncs[func->name] = + std::move(onceGlobalsWrittenVec[0]); + } + +private: + OptInfo& optInfo; +}; + +} // anonymous namespace + +struct OnceReduction : public Pass { + void run(PassRunner* runner, Module* module) override { + OptInfo optInfo; + + // Fill out the initial data. + for (auto& global : module->globals) { + // For a global to possibly be "once", it must be an integer, and to not + // be imported (as a mutable import may be read and written to from the + // outside). As we scan code we will turn this into false if we see + // anything that proves the global is not "once". + // TODO: This limitation could perhaps only be on mutable ones, but + // immutable globals will not be considered "once" anyhow as they do + // not fit the pattern of being written after the first call. + // TODO: non-integer types? + optInfo.onceGlobals[global->name] = + global->type.isInteger() && !global->imported(); + } + for (auto& func : module->functions) { + // Fill in the map so that it can be operated on in parallel. + optInfo.onceFuncs[func->name] = Name(); + } + for (auto& ex : module->exports) { + if (ex->kind == ExternalKind::Global) { + // An exported global cannot be "once" since the outside may read and + // write to it in ways we are unaware. + // TODO: See comment above on mutability. + optInfo.onceGlobals[ex->value] = false; + } + } + + // Scan the module to find out which globals and functions are "once". + Scanner(optInfo).run(runner, module); + + // Combine the information. We found which globals appear to be "once", but + // other information may have proven they are not so, in fact. Specifically, + // for a function to be "once" we need its global to also be such. + for (auto& kv : optInfo.onceFuncs) { + Name& onceGlobal = kv.second; + if (onceGlobal.is() && !optInfo.onceGlobals[onceGlobal]) { + onceGlobal = Name(); + } + } + + // Optimize using what we found. Keep iterating while we find things to + // optimize, which we estimate using a counter of the total number of once + // globals set by functions: as that increases, it means we are propagating + // useful information. + // TODO: limit # of iterations? + Index lastOnceGlobalsSet = 0; + + // First, initialize onceGlobalsSetInFuncs for the first iteration, by + // ensuring each item is present, and adding the "once" global for "once" + // funcs. + bool foundOnce = false; + for (auto& func : module->functions) { + // Either way, at least fill the data structure for parallel operation. + auto& set = optInfo.onceGlobalsSetInFuncs[func->name]; + + auto global = optInfo.onceFuncs[func->name]; + if (global.is()) { + set.insert(global); + foundOnce = true; + } + } + + if (!foundOnce) { + // Nothing to optimize. + return; + } + + while (1) { + // Initialize all the items in the new data structure that will be + // populated. + for (auto& func : module->functions) { + optInfo.newOnceGlobalsSetInFuncs[func->name]; + } + + Optimizer(optInfo).run(runner, module); + + optInfo.onceGlobalsSetInFuncs = + std::move(optInfo.newOnceGlobalsSetInFuncs); + + // Count how many once globals are set, and see if we have any more work + // to do. + Index currOnceGlobalsSet = 0; + for (auto& kv : optInfo.onceGlobalsSetInFuncs) { + auto& globals = kv.second; + currOnceGlobalsSet += globals.size(); + } + assert(currOnceGlobalsSet >= lastOnceGlobalsSet); + if (currOnceGlobalsSet > lastOnceGlobalsSet) { + lastOnceGlobalsSet = currOnceGlobalsSet; + continue; + } + return; + } + } +}; + +Pass* createOnceReductionPass() { return new OnceReduction(); } + +} // namespace wasm diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp index 3713ed8b7..878ecb3cb 100644 --- a/src/passes/pass.cpp +++ b/src/passes/pass.cpp @@ -233,6 +233,9 @@ void PassRegistry::registerPasses() { "removes calls to atexit(), which is valid if the C runtime " "will never be exited", createNoExitRuntimePass); + registerPass("once-reduction", + "reduces calls to code that only runs once", + createOnceReductionPass); registerPass("optimize-added-constants", "optimizes added constants into load/store offsets", createOptimizeAddedConstantsPass); @@ -511,6 +514,9 @@ void PassRunner::addDefaultFunctionOptimizationPasses() { void PassRunner::addDefaultGlobalOptimizationPrePasses() { addIfNoDWARFIssues("duplicate-function-elimination"); addIfNoDWARFIssues("memory-packing"); + if (options.optimizeLevel >= 2) { + addIfNoDWARFIssues("once-reduction"); + } if (wasm->features.hasGC() && getTypeSystem() == TypeSystem::Nominal && options.optimizeLevel >= 2) { addIfNoDWARFIssues("cfp"); diff --git a/src/passes/passes.h b/src/passes/passes.h index 9a9d6378d..715e5c443 100644 --- a/src/passes/passes.h +++ b/src/passes/passes.h @@ -77,6 +77,7 @@ Pass* createMetricsPass(); Pass* createNameListPass(); Pass* createNameTypesPass(); Pass* createNoExitRuntimePass(); +Pass* createOnceReductionPass(); Pass* createOptimizeAddedConstantsPass(); Pass* createOptimizeAddedConstantsPropagatePass(); Pass* createOptimizeInstructionsPass(); diff --git a/test/lit/help/optimization-opts.test b/test/lit/help/optimization-opts.test index 52695077a..18f8970c2 100644 --- a/test/lit/help/optimization-opts.test +++ b/test/lit/help/optimization-opts.test @@ -348,6 +348,9 @@ ;; CHECK-NEXT: is valid if the C runtime will ;; CHECK-NEXT: never be exited ;; CHECK-NEXT: +;; CHECK-NEXT: --once-reduction reduces calls to code that only +;; CHECK-NEXT: runs once +;; CHECK-NEXT: ;; CHECK-NEXT: --optimize-added-constants optimizes added constants into ;; CHECK-NEXT: load/store offsets ;; CHECK-NEXT: diff --git a/test/lit/passes/once-reduction.wast b/test/lit/passes/once-reduction.wast new file mode 100644 index 000000000..6cd0c9d64 --- /dev/null +++ b/test/lit/passes/once-reduction.wast @@ -0,0 +1,1429 @@ +;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited. +;; RUN: foreach %s %t wasm-opt --once-reduction -all -S -o - | filecheck %s + +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; 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: ) + (func $once + ;; A minimal "once" function. + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller + ;; Call a once function more than once, in a way that we can optimize: the + ;; first dominates the second. The second call will become a nop. + (call $once) + (call $once) + ) +) + +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; 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: (drop + ;; CHECK-NEXT: (i32.const 100) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ;; Add some more content in the function. + (drop (i32.const 100)) + ) + + ;; CHECK: (func $caller-if-1 + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (block $block + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller-if-1 + ;; Add more calls, and ones that are conditional. + (if + (i32.const 1) + (block + (call $once) + (call $once) + (call $once) + (call $once) + ) + ) + (call $once) + (call $once) + ) + + ;; CHECK: (func $caller-if-2 + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (block $block + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller-if-2 + ;; Call in both arms. As we only handle dominance, and not merges, the first + ;; call after the if is *not* optimized. + (if + (i32.const 1) + (call $once) + (block + (call $once) + (call $once) + ) + ) + (call $once) + (call $once) + ) + + ;; CHECK: (func $caller-loop-1 + ;; CHECK-NEXT: (loop $loop + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (br_if $loop + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller-loop-1 + ;; Add calls in a loop. + (loop $loop + (if + (i32.const 1) + (call $once) + ) + (call $once) + (call $once) + (br_if $loop (i32.const 1)) + ) + (call $once) + (call $once) + ) + + ;; CHECK: (func $caller-loop-2 + ;; CHECK-NEXT: (loop $loop + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (br_if $loop + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller-loop-2 + ;; Add a single conditional call in a loop. + (loop $loop + (if + (i32.const 1) + (call $once) + ) + (br_if $loop (i32.const 1)) + ) + (call $once) + (call $once) + ) + + ;; CHECK: (func $caller-single + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller-single + ;; A short function with a single call. + (call $once) + ) + + ;; CHECK: (func $caller-empty + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller-empty + ;; A tiny function with nothing at all, just to verify we do not crash on + ;; such things. + ) +) + +;; Corner case: Initial value is not zero. We can still optimize this here, +;; though in fact the function will never execute the payload call of foo(), +;; which in theory we could further optimize. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (import "env" "foo" (func $foo)) + (import "env" "foo" (func $foo)) + + ;; CHECK: (global $once (mut i32) (i32.const 42)) + (global $once (mut i32) (i32.const 42)) + + ;; CHECK: (func $once + ;; 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 $foo) + ;; CHECK-NEXT: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + (call $foo) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: function is not quite once, there is code before the if, so no +;; optimization will happen. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (import "env" "foo" (func $foo)) + (import "env" "foo" (func $foo)) + + ;; CHECK: (global $once (mut i32) (i32.const 42)) + (global $once (mut i32) (i32.const 42)) + + ;; CHECK: (func $once + ;; CHECK-NEXT: (nop) + ;; 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 $foo) + ;; CHECK-NEXT: ) + (func $once + (nop) + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + (call $foo) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: a nop after the if. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (import "env" "foo" (func $foo)) + (import "env" "foo" (func $foo)) + + ;; CHECK: (global $once (mut i32) (i32.const 42)) + (global $once (mut i32) (i32.const 42)) + + ;; CHECK: (func $once + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (global.set $once + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $foo) + ;; CHECK-NEXT: ) + (func $once + (if + (global.get $once) + (return) + ) + (nop) + (global.set $once (i32.const 1)) + (call $foo) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: The if has an else. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (import "env" "foo" (func $foo)) + (import "env" "foo" (func $foo)) + + ;; CHECK: (global $once (mut i32) (i32.const 42)) + (global $once (mut i32) (i32.const 42)) + + ;; CHECK: (func $once + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: (call $foo) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $foo) + ;; CHECK-NEXT: ) + (func $once + (if + (global.get $once) + (return) + (call $foo) + ) + (global.set $once (i32.const 1)) + (call $foo) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: different global names in the get and set +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once1 (mut i32) (i32.const 0)) + (global $once1 (mut i32) (i32.const 0)) + ;; CHECK: (global $once2 (mut i32) (i32.const 0)) + (global $once2 (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once1) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once2 + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $once + (if + (global.get $once1) + (return) + ) + (global.set $once2 (i32.const 1)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: The global is written a zero. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 0)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: The global is written a zero elsewhere. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; 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: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (global.set $once + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + (global.set $once (i32.const 0)) + ) +) + +;; Corner case: The global is written a non-zero value elsewhere. This is ok to +;; optimize, and in fact we can write a value different than 1 both there and +;; in the "once" function, and we can still optimize. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; 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: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 42)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + (global.set $once (i32.const 1337)) + ) + + ;; CHECK: (func $caller-2 + ;; CHECK-NEXT: (global.set $once + ;; CHECK-NEXT: (i32.const 1337) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller-2 + ;; Reverse order of the above. + (global.set $once (i32.const 1337)) + (call $once) + (call $once) + ) +) + +;; It is ok to call the "once" function inside itself - as that call appears +;; behind a set of the global, the call is redundant and we optimize it away. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; 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)) + (call $once) + ) +) + +;; Corner case: Non-integer global, which we ignore. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut f64) (f64.const 0)) + (global $once (mut f64) (f64.const 0)) + + ;; CHECK: (func $once + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.trunc_f64_s + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once + ;; CHECK-NEXT: (f64.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $once + (if + ;; We must cast this to an integer for the wasm to validate. + (i32.trunc_f64_s + (global.get $once) + ) + (return) + ) + (global.set $once (f64.const 1)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: Non-constant initial value. This is fine, as the initial value +;; does not matter (if it is zero, then this is a "classic" "once" global; if +;; not then it will never be written to, and the "once" function will never run +;; at all, which is fine too) +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (import "env" "glob" (global $import i32)) + (import "env" "glob" (global $import i32)) + + ;; CHECK: (global $once (mut i32) (global.get $import)) + (global $once (mut i32) (global.get $import)) + + ;; CHECK: (func $once + ;; 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: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: Non-constant later value. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once + ;; CHECK-NEXT: (i32.eqz + ;; CHECK-NEXT: (i32.eqz + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.eqz (i32.eqz (i32.const 1)))) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: "Once" function has a param. +(module + ;; CHECK: (type $i32_=>_none (func (param i32))) + + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once (param $x i32) + ;; 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: ) + (func $once (param $x i32) + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $once + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $caller + (call $once (i32.const 1)) + (call $once (i32.const 1)) + ) +) + +;; Corner case: "Once" function has a result. +(module + ;; CHECK: (type $none_=>_i32 (func (result i32))) + + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once (result i32) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: (return + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 3) + ;; CHECK-NEXT: ) + (func $once (result i32) + (if + (global.get $once) + (return (i32.const 2)) + ) + (global.set $once (i32.const 1)) + (i32.const 3) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $caller + (drop (call $once)) + (drop (call $once)) + ) +) + +;; Corner case: "Once" function body is not a block. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; CHECK-NEXT: (loop $loop + ;; 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: ) + ;; CHECK-NEXT: ) + (func $once + (loop $loop + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: Once body is too short. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $once + (if + (global.get $once) + (return) + ) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: Additional reads of the global. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; 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: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + (drop (global.get $once)) + ) +) + +;; Corner case: Additional reads of the global in the "once" func. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; 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: (drop + ;; CHECK-NEXT: (global.get $once) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + (drop (global.get $once)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: Optimization opportunties in unreachable code (which we can +;; ignore, but should not error on). +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; 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: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + (unreachable) + (call $once) + (call $once) + ) +) + +;; Add a very long chain of control flow. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; 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: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $caller + (if + (i32.const 1) + (call $once) + ) + (if + (i32.const 1) + (call $once) + ) + (if + (i32.const 1) + (call $once) + ) + (call $once) + (if + (i32.const 1) + (call $once) + ) + (call $once) + (if + (i32.const 1) + (nop) + (nop) + ) + (call $once) + (if + (i32.const 1) + (nop) + (call $once) + ) + (call $once) + (if + (i32.const 1) + (call $once) + ) + (call $once) + (if + (i32.const 1) + (nop) + (call $once) + ) + (call $once) + (if + (i32.const 1) + (call $once) + ) + (call $once) + (if + (i32.const 1) + (call $once) + ) + (call $once) + (call $once) + ) +) + +;; A test with a try-catch. This verifies that we emit their contents properly +;; in reverse postorder and do not hit any assertions. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (type $i32_=>_none (func (param i32))) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (tag $tag (param i32)) + (tag $tag (param i32)) + + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; 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: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $try-catch + ;; CHECK-NEXT: (try $label$5 + ;; CHECK-NEXT: (do + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (catch $tag + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (pop i32) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $try-catch + (try $label$5 + (do + (if + (i32.const 1) + (call $once) + ) + ) + (catch $tag + (drop + (pop i32) + ) + ) + ) + ) +) + +(module + ;; Test a module with more than one global that we can optimize, and more than + ;; one that we cannot. + + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once1 (mut i32) (i32.const 0)) + (global $once1 (mut i32) (i32.const 0)) + ;; CHECK: (global $many1 (mut i32) (i32.const 0)) + (global $many1 (mut i32) (i32.const 0)) + ;; CHECK: (global $once2 (mut i32) (i32.const 0)) + (global $once2 (mut i32) (i32.const 0)) + ;; CHECK: (global $many2 (mut i32) (i32.const 0)) + (global $many2 (mut i32) (i32.const 0)) + + ;; CHECK: (func $once1 + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once1) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once1 + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $many1) + ;; CHECK-NEXT: (call $once2) + ;; CHECK-NEXT: (call $many2) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $many1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $many2) + ;; CHECK-NEXT: ) + (func $once1 + (if + (global.get $once1) + (return) + ) + (global.set $once1 (i32.const 1)) + (call $once1) + (call $many1) + (call $once2) + (call $many2) + (call $once1) + (call $many1) + (call $once2) + (call $many2) + ) + + ;; CHECK: (func $many1 + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $many1) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $many1 + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $many2) + ;; CHECK-NEXT: (call $once1) + ;; CHECK-NEXT: (call $many1) + ;; CHECK-NEXT: (call $once2) + ;; CHECK-NEXT: (call $many2) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $many1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $many1 + (if + (global.get $many1) + (return) + ) + (global.set $many1 (i32.const 0)) ;; prevent this global being "once" + (call $many2) + (call $once1) + (call $many1) + (call $once2) + (call $many2) + (call $once1) + (call $many1) + (call $once2) + ) + + ;; CHECK: (func $once2 + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $once2) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $once2 + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $many2) + ;; CHECK-NEXT: (call $once1) + ;; CHECK-NEXT: (call $many1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $many2) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $many1) + ;; CHECK-NEXT: ) + (func $once2 + (if + (global.get $once2) + (return) + ) + (global.set $once2 (i32.const 2)) + (call $once2) + (call $many2) + (call $once1) + (call $many1) + (call $once2) + (call $many2) + (call $once1) + (call $many1) + ) + + ;; CHECK: (func $many2 + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (global.get $many2) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.set $many1 + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $many1) + ;; CHECK-NEXT: (call $once2) + ;; CHECK-NEXT: (call $many2) + ;; CHECK-NEXT: (call $once1) + ;; CHECK-NEXT: (call $many1) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $many2) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $many2 + (if + (global.get $many2) + (return) + ) + (global.set $many1 (i32.const 0)) + (call $many1) + (call $once2) + (call $many2) + (call $once1) + (call $many1) + (call $once2) + (call $many2) + (call $once1) + ) +) + +;; Test for propagation of information about called functions: if A->B->C->D +;; and D calls some "once" functions, then A can infer that it's call to B does +;; so. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (func $once + ;; 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: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $A + ;; CHECK-NEXT: (call $B) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $A + ;; We can infer that calling B calls C and then D, and D calls this "once" + ;; function, so we can remove the call after it + (call $B) + (call $once) + ) + + ;; CHECK: (func $B + ;; CHECK-NEXT: (call $C) + ;; CHECK-NEXT: ) + (func $B + (call $C) + ) + + ;; CHECK: (func $C + ;; CHECK-NEXT: (call $D) + ;; CHECK-NEXT: ) + (func $C + (call $D) + ) + + ;; CHECK: (func $D + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $D + (call $once) + (call $once) + ) + + ;; CHECK: (func $bad-A + ;; CHECK-NEXT: (call $bad-B) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $bad-A + ;; Call a function that does *not* do anything useful. We should not remove + ;; the second call here. + (call $bad-B) + (call $once) + ) + + ;; CHECK: (func $bad-B + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $bad-B + ) +) + +;; Corner case: Imported mutable global. We cannot optimize it, since the +;; outside may read and write it. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (import "env" "glob" (global $once (mut i32))) + (import "env" "glob" (global $once (mut i32))) + + ;; CHECK: (func $once + ;; 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: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) + +;; Corner case: Exported mutable global. We cannot optimize it, since the +;; outside may read and write it. +(module + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (global $once (mut i32) (i32.const 0)) + (global $once (mut i32) (i32.const 0)) + + ;; CHECK: (export "once-global" (global $once)) + (export "once-global" (global $once)) + + ;; CHECK: (func $once + ;; 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: ) + (func $once + (if + (global.get $once) + (return) + ) + (global.set $once (i32.const 1)) + ) + + ;; CHECK: (func $caller + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: (call $once) + ;; CHECK-NEXT: ) + (func $caller + (call $once) + (call $once) + ) +) |