diff options
34 files changed, 1223 insertions, 497 deletions
diff --git a/build-js.sh b/build-js.sh index 2c1c130bd..915a5a257 100755 --- a/build-js.sh +++ b/build-js.sh @@ -97,6 +97,7 @@ echo "building shared bitcode" src/passes/Precompute.cpp \ src/passes/Print.cpp \ src/passes/PrintCallGraph.cpp \ + src/passes/RedundantSetElimination.cpp \ src/passes/RelooperJumpThreading.cpp \ src/passes/RemoveImports.cpp \ src/passes/RemoveMemory.cpp \ diff --git a/src/cfg/liveness-traversal.h b/src/cfg/liveness-traversal.h index 24578dcd7..15e41428e 100644 --- a/src/cfg/liveness-traversal.h +++ b/src/cfg/liveness-traversal.h @@ -1,4 +1,3 @@ -#include <wasm-printing.h> /* * Copyright 2017 WebAssembly Community Group participants * diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt index 1da9b57f7..e5334fff1 100644 --- a/src/passes/CMakeLists.txt +++ b/src/passes/CMakeLists.txt @@ -26,6 +26,7 @@ SET(passes_SOURCES Precompute.cpp Print.cpp PrintCallGraph.cpp + RedundantSetElimination.cpp RelooperJumpThreading.cpp ReReloop.cpp RemoveImports.cpp diff --git a/src/passes/RedundantSetElimination.cpp b/src/passes/RedundantSetElimination.cpp new file mode 100644 index 000000000..a63866111 --- /dev/null +++ b/src/passes/RedundantSetElimination.cpp @@ -0,0 +1,374 @@ +/* + * Copyright 2017 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. + */ + +// +// Eliminate redundant set_locals: if a local already has a particular +// value, we don't need to set it again. A common case here is loops +// that start at zero, since the default value is initialized to +// zero anyhow. +// +// A risk here is that we extend live ranges, e.g. we may use the default +// value at the very end of a function, keeping that local alive throughout. +// For that reason it is probably better to run this near the end of +// optimization, and especially after coalesce-locals. A final vaccum +// should be done after it, as this pass can leave around drop()s of +// values no longer necessary. +// +// So far this tracks constant values, and for everything else it considers +// them unique (so each set_local of a non-constant is a unique value, each +// merge is a unique value, etc.; there is no sophisticated value numbering +// here). +// + +#include <wasm.h> +#include <pass.h> +#include <wasm-builder.h> +#include <cfg/cfg-traversal.h> +#include <ir/literal-utils.h> +#include <ir/utils.h> +#include <support/unique_deferring_queue.h> + +namespace wasm { + +// We do a very simple numbering of local values, just a unique +// number for constants so far, enough to see +// trivial duplication. LocalValues maps each local index to +// its current value +typedef std::vector<Index> LocalValues; + +// information in a basic block +struct Info { + LocalValues start, end; // the local values at the start and end of the block + std::vector<Expression**> setps; +}; + +struct RedundantSetElimination : public WalkerPass<CFGWalker<RedundantSetElimination, Visitor<RedundantSetElimination>, Info>> { + bool isFunctionParallel() override { return true; } + + Pass* create() override { return new RedundantSetElimination(); } + + Index numLocals; + + // cfg traversal work + + static void doVisitSetLocal(RedundantSetElimination* self, Expression** currp) { + if (self->currBasicBlock) { + self->currBasicBlock->contents.setps.push_back(currp); + } + } + + // main entry point + + void doWalkFunction(Function* func) { + numLocals = func->getNumLocals(); + // create the CFG by walking the IR + CFGWalker<RedundantSetElimination, Visitor<RedundantSetElimination>, Info>::doWalkFunction(func); + // flow values across blocks + flowValues(func); + // remove redundant sets + optimize(); + } + + // numbering + + Index nextValue = 1; // 0 is reserved for the "unseen value" + std::unordered_map<Literal, Index> literalValues; // each constant has a value + std::unordered_map<Expression*, Index> expressionValues; // each value can have a value + std::unordered_map<BasicBlock*, std::unordered_map<Index, Index>> blockMergeValues; // each block has values for each merge + + Index getUnseenValue() { // we haven't seen this location yet + return 0; + } + Index getUniqueValue() { +#ifdef RSE_DEBUG + std::cout << "new unique value " << nextValue << '\n'; +#endif + return nextValue++; + } + + Index getLiteralValue(Literal lit) { + auto iter = literalValues.find(lit); + if (iter != literalValues.end()) { + return iter->second; + } +#ifdef RSE_DEBUG + std::cout << "new literal value for " << lit << '\n'; +#endif + return literalValues[lit] = getUniqueValue(); + } + + Index getExpressionValue(Expression* expr) { + auto iter = expressionValues.find(expr); + if (iter != expressionValues.end()) { + return iter->second; + } +#ifdef RSE_DEBUG + std::cout << "new expr value for " << expr << '\n'; +#endif + return expressionValues[expr] = getUniqueValue(); + } + + Index getBlockMergeValue(BasicBlock* block, Index index) { + auto& mergeValues = blockMergeValues[block]; + auto iter = mergeValues.find(index); + if (iter != mergeValues.end()) { + return iter->second; + } +#ifdef RSE_DEBUG + std::cout << "new block-merge value for " << block << " : " << index << '\n'; +#endif + return mergeValues[index] = getUniqueValue(); + } + + bool isBlockMergeValue(BasicBlock* block, Index index, Index value) { + auto iter = blockMergeValues.find(block); + if (iter == blockMergeValues.end()) return false; + auto& mergeValues = iter->second; + auto iter2 = mergeValues.find(index); + if (iter2 == mergeValues.end()) return false; + return value == iter2->second; + } + + Index getValue(Expression* value, LocalValues& currValues) { + if (auto* c = value->dynCast<Const>()) { + // a constant + return getLiteralValue(c->value); + } else if (auto* get = value->dynCast<GetLocal>()) { + // a copy of whatever that was + return currValues[get->index]; + } else { + // get the value's own unique value + return getExpressionValue(value); + } + } + + // flowing + + void flowValues(Function* func) { + for (auto& block : basicBlocks) { + LocalValues& start = block->contents.start; + start.resize(numLocals); + if (block.get() == entry) { + // params are complex values we can't optimize; vars are zeros + for (Index i = 0; i < numLocals; i++) { + if (func->isParam(i)) { +#ifdef RSE_DEBUG + std::cout << "new param value for " << i << '\n'; +#endif + start[i] = getUniqueValue(); + } else { + start[i] = getLiteralValue(LiteralUtils::makeLiteralZero(func->getLocalType(i))); + } + } + } else { + // other blocks have all unseen values to begin with + for (Index i = 0; i < numLocals; i++) { + start[i] = getUnseenValue(); + } + } + // the ends all begin unseen + LocalValues& end = block->contents.end; + end.resize(numLocals); + for (Index i = 0; i < numLocals; i++) { + end[i] = getUnseenValue(); + } + } + // keep working while stuff is flowing. we use a unique deferred queue + // which ensures both FIFO and that we don't do needless work - if + // A and B reach C, and both queue C, we only want to do C at the latest + // time, when we have information from all those reaching it. + UniqueDeferredQueue<BasicBlock*> work; + work.push(entry); + while (!work.empty()) { + auto* curr = work.pop(); +#ifdef RSE_DEBUG + std::cout << "flow block " << curr << '\n'; +#endif + // process a block: first, update its start based on those reaching it + if (!curr->in.empty()) { + if (curr->in.size() == 1) { + // just copy the pred, nothing to merge + curr->contents.start = (*curr->in.begin())->contents.end; + } else { + // perform a merge + auto in = curr->in; + for (Index i = 0; i < numLocals; i++) { + auto old = curr->contents.start[i]; + // If we already had a merge value here, keep it. + // TODO This may have some false positives, as we may e.g. have + // a single pred that first gives us x, then later y after + // flow led to a merge, and we may see x and y at the same + // time due to flow from a successor, and then it looks like + // we need a merge but we don't. avoiding that would require + // more memory and is probably not worth it, but might be + // worth investigating + // NB While suboptimal, this simplification provides a simple proof + // of convergence. We prove that, in each fixed block+local, + // the value number at the end is nondecreasing across + // iterations, by induction on the iteration: + // * The first iteration is on the entry block. It increases + // the value number at the end from 0 (unseen) to something + // else (a value number for 0 for locals, a unique value + // for params; all >0). + // * Induction step: assuming the property holds for all past + // iterations, consider the current iteration. Of our + // predecessors, those that we iterated on have the property; + // those that we haven't will have 0 (unseen). + // * If we assign to that local in this block, that will be + // the value in the output, forever, and it is greater + // than the initial value of 0. + // * If we see different values coming in, we create a merge + // value number. Its number is higher than everything + // else since we give it the next available number, so we + // do not decrease in this iteration, and we will output + // the same value in the future too (here is where we use + // the simplification property). + // * Otherwise, we will flow the incoming value through, + // and it did not decrease (by induction), so neither do + // we. + // Finally, given value numbers are nondecreasing, we must + // converge since we only keep working as long as we see new + // values at the end of a block. + // + // Not that we don't trust this proof, but the convergence + // property (value numbers at block ends do not decrease) is + // verified later down. + if (isBlockMergeValue(curr, i, old)) { + continue; + } + auto iter = in.begin(); + auto value = (*iter)->contents.end[i]; + iter++; + while (iter != in.end()) { + auto otherValue = (*iter)->contents.end[i]; + if (value == getUnseenValue()) { + value = otherValue; + } else if (otherValue == getUnseenValue()) { + // nothing to do, other has no information + } else if (value != otherValue) { + // 2 different values, this is a merged value + value = getBlockMergeValue(curr, i); + break; // no more work once we see a merge + } + iter++; + } + curr->contents.start[i] = value; + } + } + } +#ifdef RSE_DEBUG + dump("start", curr->contents.start); +#endif + // flow values through it, then add those we can reach if they need an update. + auto currValues = curr->contents.start; // we'll modify this as we go + auto& setps = curr->contents.setps; + for (auto** setp : setps) { + auto* set = (*setp)->cast<SetLocal>(); + currValues[set->index] = getValue(set->value, currValues); + } + if (currValues == curr->contents.end) { + // nothing changed, so no more work to do + // note that the first iteration this is always not the case, + // since end contains unseen (and then the comparison ends on + // the first element) + continue; + } + // update the end state and update children +#ifndef NDEBUG + // verify the convergence property mentioned in the NB comment + // above: the value numbers at the end must be nondecreasing + for (Index i = 0; i < numLocals; i++) { + assert(currValues[i] >= curr->contents.end[i]); + } +#endif + curr->contents.end.swap(currValues); +#ifdef RSE_DEBUG + dump("end ", curr->contents.end); +#endif + for (auto* next : curr->out) { + work.push(next); + } + } + } + + // optimizing + void optimize() { + // in each block, run the values through the sets, + // and remove redundant sets when we see them + for (auto& block : basicBlocks) { + auto currValues = block->contents.start; // we'll modify this as we go + auto& setps = block->contents.setps; + for (auto** setp : setps) { + auto* set = (*setp)->cast<SetLocal>(); + auto oldValue = currValues[set->index]; + auto newValue = getValue(set->value, currValues); + auto index = set->index; + if (newValue == oldValue) { + remove(setp); + continue; // no more work to do + } + // update for later steps + currValues[index] = newValue; + } + } + } + + void remove(Expression** setp) { + auto* set = (*setp)->cast<SetLocal>(); + auto* value = set->value; + if (!set->isTee()) { + auto* drop = ExpressionManipulator::convert<SetLocal, Drop>(set); + drop->value = value; + drop->finalize(); + } else { + *setp = value; + } + } + + // debugging + + void dump(BasicBlock* block) { + std::cout << "====\n"; + if (block) { + std::cout << "block: " << block << '\n'; + for (auto* out : block->out) { + std::cout << " goes to " << out << '\n'; + } + } + for (Index i = 0; i < block->contents.start.size(); i++) { + std::cout << " start[" << i << "] = " << block->contents.start[i] << '\n'; + } + for (auto** setp : block->contents.setps) { + std::cout << " " << *setp << '\n'; + } + std::cout << "====\n"; + } + + void dump(const char* desc, LocalValues& values) { + std::cout << desc << ": "; + for (auto x : values) { + std::cout << x << ' '; + } + std::cout << '\n'; + } +}; + +Pass *createRedundantSetEliminationPass() { + return new RedundantSetElimination(); +} + +} // namespace wasm + diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp index 339b1d1da..9fe2980fd 100644 --- a/src/passes/pass.cpp +++ b/src/passes/pass.cpp @@ -95,6 +95,7 @@ void PassRegistry::registerPasses() { registerPass("print-minified", "print in minified s-expression format", createMinifiedPrinterPass); registerPass("print-full", "print in full s-expression format", createFullPrinterPass); registerPass("print-call-graph", "print call graph", createPrintCallGraphPass); + registerPass("rse", "remove redundant set_locals", createRedundantSetEliminationPass); registerPass("relooper-jump-threading", "thread relooper jumps (fastcomp output only)", createRelooperJumpThreadingPass); registerPass("remove-imports", "removes imports and replaces them with nops", createRemoveImportsPass); registerPass("remove-memory", "removes memory segments", createRemoveMemoryPass); @@ -167,6 +168,9 @@ void PassRunner::addDefaultFunctionOptimizationPasses() { add("local-cse"); // TODO: run this early, before first coalesce-locals. right now doing so uncovers some deficiencies we need to fix first add("coalesce-locals"); // just for localCSE } + if (options.optimizeLevel >= 2 || options.shrinkLevel >= 1) { + add("rse"); // after all coalesce-locals, and before a final vacuum + } add("vacuum"); // just to be safe } diff --git a/src/passes/passes.h b/src/passes/passes.h index 53198bf56..081f7e203 100644 --- a/src/passes/passes.h +++ b/src/passes/passes.h @@ -62,6 +62,7 @@ Pass* createRemoveUnusedNamesPass(); Pass* createReorderFunctionsPass(); Pass* createReorderLocalsPass(); Pass* createReReloopPass(); +Pass* createRedundantSetEliminationPass(); Pass* createSafeHeapPass(); Pass* createSimplifyLocalsPass(); Pass* createSimplifyLocalsNoTeePass(); diff --git a/src/support/sorted_vector.h b/src/support/sorted_vector.h index 607a30578..bb157f590 100644 --- a/src/support/sorted_vector.h +++ b/src/support/sorted_vector.h @@ -15,7 +15,7 @@ */ // -// Command line helpers. +// A vector of sorted elements. // #ifndef wasm_support_sorted_vector_h diff --git a/src/support/unique_deferring_queue.h b/src/support/unique_deferring_queue.h new file mode 100644 index 000000000..eb024e5b8 --- /dev/null +++ b/src/support/unique_deferring_queue.h @@ -0,0 +1,65 @@ +/* + * Copyright 2017 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. + */ + +// +// A FIFO queue of unique items, in which if an item is queued that already +// exists, it is placed at the end. That means that it is done at the +// last (most deferred) time from all the times it was queued. +// + +#ifndef wasm_support_unique_deferring_queue_h +#define wasm_support_unique_deferring_queue_h + +#include <queue> +#include <unordered_map> + +namespace wasm { + +template<typename T> +struct UniqueDeferredQueue { + // implemented as an internal queue, plus a map + // that says how many times an element appears. we + // can then skip non-final appearances. this lets us + // avoid needing to remove elements from the middle + // when there are duplicates. + std::queue<T> data; + std::unordered_map<T, size_t> count; + + size_t size() { return data.size(); } + bool empty() { return size() == 0; } + + void push(T item) { + data.push(item); + count[item]++; + } + + T pop() { + while (1) { + assert(!empty()); + T item = data.front(); + count[item]--; + data.pop(); + if (count[item] == 0) { + return item; + } + // skip this one, keep going + } + } +}; + +} // namespace wasm + +#endif // wasm_support_unique_deferring_queue_h diff --git a/test/debugInfo.fromasm b/test/debugInfo.fromasm index 70d5183e7..af058db39 100644 --- a/test/debugInfo.fromasm +++ b/test/debugInfo.fromasm @@ -74,16 +74,8 @@ (get_local $0) (i32.const 0) ) - (block - (set_local $4 - (i32.const 0) - ) - (set_local $2 - (i32.const 0) - ) - (set_local $3 - (i32.const 1) - ) + (set_local $3 + (i32.const 1) ) (block (set_local $1 diff --git a/test/debugInfo.fromasm.clamp b/test/debugInfo.fromasm.clamp index 70d5183e7..af058db39 100644 --- a/test/debugInfo.fromasm.clamp +++ b/test/debugInfo.fromasm.clamp @@ -74,16 +74,8 @@ (get_local $0) (i32.const 0) ) - (block - (set_local $4 - (i32.const 0) - ) - (set_local $2 - (i32.const 0) - ) - (set_local $3 - (i32.const 1) - ) + (set_local $3 + (i32.const 1) ) (block (set_local $1 diff --git a/test/debugInfo.fromasm.clamp.map b/test/debugInfo.fromasm.clamp.map index 6fb01998b..ecc297b63 100644 --- a/test/debugInfo.fromasm.clamp.map +++ b/test/debugInfo.fromasm.clamp.map @@ -1 +1 @@ -{"version":3,"sources":["tests/hello_world.c","tests/other_file.cpp","return.cpp","even-opted.cpp","fib.c","/tmp/emscripten_test_binaryen2_28hnAe/src.c","(unknown)"],"names":[],"mappings":"iLC8ylTA,QC7vlTA,OAkDA,UCnGA,OACA,OACA,uBCAA,wBAKA,MAJA,OADA,0BAKA,0FCsi1DA,KCrvyDA"}
\ No newline at end of file +{"version":3,"sources":["tests/hello_world.c","tests/other_file.cpp","return.cpp","even-opted.cpp","fib.c","/tmp/emscripten_test_binaryen2_28hnAe/src.c","(unknown)"],"names":[],"mappings":"iLC8ylTA,QC7vlTA,OAkDA,UCnGA,OACA,OACA,uBCAA,gBAKA,MAJA,OADA,0BAKA,0FCsi1DA,KCrvyDA"}
\ No newline at end of file diff --git a/test/debugInfo.fromasm.imprecise b/test/debugInfo.fromasm.imprecise index 5db316589..390aa7f1e 100644 --- a/test/debugInfo.fromasm.imprecise +++ b/test/debugInfo.fromasm.imprecise @@ -66,16 +66,8 @@ (get_local $0) (i32.const 0) ) - (block - (set_local $4 - (i32.const 0) - ) - (set_local $2 - (i32.const 0) - ) - (set_local $3 - (i32.const 1) - ) + (set_local $3 + (i32.const 1) ) (block (set_local $1 diff --git a/test/debugInfo.fromasm.imprecise.map b/test/debugInfo.fromasm.imprecise.map index b7ca07106..5efd89334 100644 --- a/test/debugInfo.fromasm.imprecise.map +++ b/test/debugInfo.fromasm.imprecise.map @@ -1 +1 @@ -{"version":3,"sources":["tests/hello_world.c","tests/other_file.cpp","return.cpp","even-opted.cpp","fib.c","/tmp/emscripten_test_binaryen2_28hnAe/src.c","(unknown)"],"names":[],"mappings":"iLC8ylTA,QC7vlTA,OAkDA,QCnGA,OACA,OACA,aCAA,wBAKA,MAJA,OADA,0BAKA,0FCsi1DA,KCrvyDA"}
\ No newline at end of file +{"version":3,"sources":["tests/hello_world.c","tests/other_file.cpp","return.cpp","even-opted.cpp","fib.c","/tmp/emscripten_test_binaryen2_28hnAe/src.c","(unknown)"],"names":[],"mappings":"iLC8ylTA,QC7vlTA,OAkDA,QCnGA,OACA,OACA,aCAA,gBAKA,MAJA,OADA,0BAKA,0FCsi1DA,KCrvyDA"}
\ No newline at end of file diff --git a/test/debugInfo.fromasm.map b/test/debugInfo.fromasm.map index 6fb01998b..ecc297b63 100644 --- a/test/debugInfo.fromasm.map +++ b/test/debugInfo.fromasm.map @@ -1 +1 @@ -{"version":3,"sources":["tests/hello_world.c","tests/other_file.cpp","return.cpp","even-opted.cpp","fib.c","/tmp/emscripten_test_binaryen2_28hnAe/src.c","(unknown)"],"names":[],"mappings":"iLC8ylTA,QC7vlTA,OAkDA,UCnGA,OACA,OACA,uBCAA,wBAKA,MAJA,OADA,0BAKA,0FCsi1DA,KCrvyDA"}
\ No newline at end of file +{"version":3,"sources":["tests/hello_world.c","tests/other_file.cpp","return.cpp","even-opted.cpp","fib.c","/tmp/emscripten_test_binaryen2_28hnAe/src.c","(unknown)"],"names":[],"mappings":"iLC8ylTA,QC7vlTA,OAkDA,UCnGA,OACA,OACA,uBCAA,gBAKA,MAJA,OADA,0BAKA,0FCsi1DA,KCrvyDA"}
\ No newline at end of file diff --git a/test/emcc_O2_hello_world.fromasm b/test/emcc_O2_hello_world.fromasm index c9bb769e0..aa1a08dc6 100644 --- a/test/emcc_O2_hello_world.fromasm +++ b/test/emcc_O2_hello_world.fromasm @@ -894,12 +894,7 @@ (set_local $5 (get_local $11) ) - (block - (set_local $19 - (i32.const 0) - ) - (br $do-once4) - ) + (br $do-once4) ) ) (loop $while-in7 @@ -1524,9 +1519,6 @@ (set_local $10 (get_local $15) ) - (set_local $5 - (i32.const 0) - ) (loop $while-in14 (if (i32.lt_u @@ -1655,12 +1647,6 @@ (set_local $33 (get_local $0) ) - (set_local $6 - (i32.const 0) - ) - (set_local $30 - (i32.const 0) - ) (set_local $7 (i32.const 86) ) @@ -2006,12 +1992,7 @@ (set_local $1 (get_local $15) ) - (block - (set_local $8 - (i32.const 0) - ) - (br $do-once17) - ) + (br $do-once17) ) ) (loop $while-in20 @@ -4049,12 +4030,7 @@ (set_local $0 (get_local $16) ) - (block - (set_local $24 - (i32.const 0) - ) - (br $do-once47) - ) + (br $do-once47) ) ) (loop $while-in50 @@ -6244,7 +6220,7 @@ (get_local $7) ) ) - (if + (br_if $do-once0 (i32.eqz (tee_local $0 (i32.load @@ -6252,12 +6228,6 @@ ) ) ) - (block - (set_local $6 - (i32.const 0) - ) - (br $do-once0) - ) ) ) (loop $while-in @@ -6804,12 +6774,7 @@ (set_local $3 (get_local $0) ) - (block - (set_local $12 - (i32.const 0) - ) - (br $do-once6) - ) + (br $do-once6) ) ) (loop $while-in9 @@ -8126,11 +8091,10 @@ ) ) (if - (call $___towrite - (get_local $2) - ) - (set_local $4 - (i32.const 0) + (i32.eqz + (call $___towrite + (get_local $2) + ) ) (block (set_local $6 diff --git a/test/emcc_O2_hello_world.fromasm.clamp b/test/emcc_O2_hello_world.fromasm.clamp index c9bb769e0..aa1a08dc6 100644 --- a/test/emcc_O2_hello_world.fromasm.clamp +++ b/test/emcc_O2_hello_world.fromasm.clamp @@ -894,12 +894,7 @@ (set_local $5 (get_local $11) ) - (block - (set_local $19 - (i32.const 0) - ) - (br $do-once4) - ) + (br $do-once4) ) ) (loop $while-in7 @@ -1524,9 +1519,6 @@ (set_local $10 (get_local $15) ) - (set_local $5 - (i32.const 0) - ) (loop $while-in14 (if (i32.lt_u @@ -1655,12 +1647,6 @@ (set_local $33 (get_local $0) ) - (set_local $6 - (i32.const 0) - ) - (set_local $30 - (i32.const 0) - ) (set_local $7 (i32.const 86) ) @@ -2006,12 +1992,7 @@ (set_local $1 (get_local $15) ) - (block - (set_local $8 - (i32.const 0) - ) - (br $do-once17) - ) + (br $do-once17) ) ) (loop $while-in20 @@ -4049,12 +4030,7 @@ (set_local $0 (get_local $16) ) - (block - (set_local $24 - (i32.const 0) - ) - (br $do-once47) - ) + (br $do-once47) ) ) (loop $while-in50 @@ -6244,7 +6220,7 @@ (get_local $7) ) ) - (if + (br_if $do-once0 (i32.eqz (tee_local $0 (i32.load @@ -6252,12 +6228,6 @@ ) ) ) - (block - (set_local $6 - (i32.const 0) - ) - (br $do-once0) - ) ) ) (loop $while-in @@ -6804,12 +6774,7 @@ (set_local $3 (get_local $0) ) - (block - (set_local $12 - (i32.const 0) - ) - (br $do-once6) - ) + (br $do-once6) ) ) (loop $while-in9 @@ -8126,11 +8091,10 @@ ) ) (if - (call $___towrite - (get_local $2) - ) - (set_local $4 - (i32.const 0) + (i32.eqz + (call $___towrite + (get_local $2) + ) ) (block (set_local $6 diff --git a/test/emcc_O2_hello_world.fromasm.imprecise b/test/emcc_O2_hello_world.fromasm.imprecise index 21e641976..af05b1e3f 100644 --- a/test/emcc_O2_hello_world.fromasm.imprecise +++ b/test/emcc_O2_hello_world.fromasm.imprecise @@ -893,12 +893,7 @@ (set_local $5 (get_local $11) ) - (block - (set_local $19 - (i32.const 0) - ) - (br $do-once4) - ) + (br $do-once4) ) ) (loop $while-in7 @@ -1523,9 +1518,6 @@ (set_local $10 (get_local $15) ) - (set_local $5 - (i32.const 0) - ) (loop $while-in14 (if (i32.lt_u @@ -1654,12 +1646,6 @@ (set_local $33 (get_local $0) ) - (set_local $6 - (i32.const 0) - ) - (set_local $30 - (i32.const 0) - ) (set_local $7 (i32.const 86) ) @@ -2005,12 +1991,7 @@ (set_local $1 (get_local $15) ) - (block - (set_local $8 - (i32.const 0) - ) - (br $do-once17) - ) + (br $do-once17) ) ) (loop $while-in20 @@ -4048,12 +4029,7 @@ (set_local $0 (get_local $16) ) - (block - (set_local $24 - (i32.const 0) - ) - (br $do-once47) - ) + (br $do-once47) ) ) (loop $while-in50 @@ -6243,7 +6219,7 @@ (get_local $7) ) ) - (if + (br_if $do-once0 (i32.eqz (tee_local $0 (i32.load @@ -6251,12 +6227,6 @@ ) ) ) - (block - (set_local $6 - (i32.const 0) - ) - (br $do-once0) - ) ) ) (loop $while-in @@ -6803,12 +6773,7 @@ (set_local $3 (get_local $0) ) - (block - (set_local $12 - (i32.const 0) - ) - (br $do-once6) - ) + (br $do-once6) ) ) (loop $while-in9 @@ -8125,11 +8090,10 @@ ) ) (if - (call $___towrite - (get_local $2) - ) - (set_local $4 - (i32.const 0) + (i32.eqz + (call $___towrite + (get_local $2) + ) ) (block (set_local $6 diff --git a/test/emcc_hello_world.fromasm b/test/emcc_hello_world.fromasm index 3246cd8d1..a9843a84e 100644 --- a/test/emcc_hello_world.fromasm +++ b/test/emcc_hello_world.fromasm @@ -261,9 +261,6 @@ (func $_strerror (; 28 ;) (param $0 i32) (result i32) (local $1 i32) (local $2 i32) - (set_local $1 - (i32.const 0) - ) (block $__rjto$1 (block $__rjti$1 (block $__rjti$0 @@ -2417,15 +2414,9 @@ (i32.const 8) ) ) - (set_local $16 - (i32.const 0) - ) (set_local $5 (get_local $1) ) - (set_local $10 - (i32.const 0) - ) (set_local $1 (i32.const 0) ) @@ -8580,7 +8571,7 @@ ) ) ) - (if + (br_if $do-once4 (i32.eqz (tee_local $1 (i32.load @@ -8593,12 +8584,6 @@ ) ) ) - (block - (set_local $9 - (i32.const 0) - ) - (br $do-once4) - ) ) ) (loop $while-in7 @@ -9206,9 +9191,6 @@ ) ) (block - (set_local $6 - (i32.const 0) - ) (set_local $8 (i32.shl (get_local $2) @@ -9346,13 +9328,8 @@ ) ) ) - (block - (set_local $4 - (i32.const 0) - ) - (set_local $0 - (i32.const 0) - ) + (set_local $0 + (i32.const 0) ) ) (if @@ -9631,7 +9608,7 @@ ) ) ) - (if + (br_if $do-once17 (i32.eqz (tee_local $1 (i32.load @@ -9644,12 +9621,6 @@ ) ) ) - (block - (set_local $11 - (i32.const 0) - ) - (br $do-once17) - ) ) ) (loop $while-in20 @@ -10971,9 +10942,6 @@ (get_local $1) ) ) - (set_local $3 - (get_local $1) - ) ) (if (i32.ne @@ -11639,12 +11607,7 @@ (set_local $0 (get_local $3) ) - (block - (set_local $12 - (i32.const 0) - ) - (br $do-once55) - ) + (br $do-once55) ) ) (loop $while-in58 @@ -13629,12 +13592,7 @@ (set_local $4 (get_local $7) ) - (block - (set_local $6 - (i32.const 0) - ) - (br $do-once0) - ) + (br $do-once0) ) ) (loop $while-in @@ -14281,12 +14239,7 @@ (set_local $0 (get_local $1) ) - (block - (set_local $9 - (i32.const 0) - ) - (br $do-once6) - ) + (br $do-once6) ) ) (loop $while-in9 diff --git a/test/emcc_hello_world.fromasm.clamp b/test/emcc_hello_world.fromasm.clamp index 2f52a5eac..86bfe811e 100644 --- a/test/emcc_hello_world.fromasm.clamp +++ b/test/emcc_hello_world.fromasm.clamp @@ -259,9 +259,6 @@ (func $_strerror (; 27 ;) (param $0 i32) (result i32) (local $1 i32) (local $2 i32) - (set_local $1 - (i32.const 0) - ) (block $__rjto$1 (block $__rjti$1 (block $__rjti$0 @@ -2467,15 +2464,9 @@ (i32.const 8) ) ) - (set_local $16 - (i32.const 0) - ) (set_local $5 (get_local $1) ) - (set_local $10 - (i32.const 0) - ) (set_local $1 (i32.const 0) ) @@ -8630,7 +8621,7 @@ ) ) ) - (if + (br_if $do-once4 (i32.eqz (tee_local $1 (i32.load @@ -8643,12 +8634,6 @@ ) ) ) - (block - (set_local $9 - (i32.const 0) - ) - (br $do-once4) - ) ) ) (loop $while-in7 @@ -9256,9 +9241,6 @@ ) ) (block - (set_local $6 - (i32.const 0) - ) (set_local $8 (i32.shl (get_local $2) @@ -9396,13 +9378,8 @@ ) ) ) - (block - (set_local $4 - (i32.const 0) - ) - (set_local $0 - (i32.const 0) - ) + (set_local $0 + (i32.const 0) ) ) (if @@ -9681,7 +9658,7 @@ ) ) ) - (if + (br_if $do-once17 (i32.eqz (tee_local $1 (i32.load @@ -9694,12 +9671,6 @@ ) ) ) - (block - (set_local $11 - (i32.const 0) - ) - (br $do-once17) - ) ) ) (loop $while-in20 @@ -11021,9 +10992,6 @@ (get_local $1) ) ) - (set_local $3 - (get_local $1) - ) ) (if (i32.ne @@ -11689,12 +11657,7 @@ (set_local $0 (get_local $3) ) - (block - (set_local $12 - (i32.const 0) - ) - (br $do-once55) - ) + (br $do-once55) ) ) (loop $while-in58 @@ -13679,12 +13642,7 @@ (set_local $4 (get_local $7) ) - (block - (set_local $6 - (i32.const 0) - ) - (br $do-once0) - ) + (br $do-once0) ) ) (loop $while-in @@ -14331,12 +14289,7 @@ (set_local $0 (get_local $1) ) - (block - (set_local $9 - (i32.const 0) - ) - (br $do-once6) - ) + (br $do-once6) ) ) (loop $while-in9 diff --git a/test/emcc_hello_world.fromasm.imprecise b/test/emcc_hello_world.fromasm.imprecise index b387f8cac..54c162195 100644 --- a/test/emcc_hello_world.fromasm.imprecise +++ b/test/emcc_hello_world.fromasm.imprecise @@ -258,9 +258,6 @@ (func $_strerror (; 27 ;) (param $0 i32) (result i32) (local $1 i32) (local $2 i32) - (set_local $1 - (i32.const 0) - ) (block $__rjto$1 (block $__rjti$1 (block $__rjti$0 @@ -2370,15 +2367,9 @@ (i32.const 8) ) ) - (set_local $16 - (i32.const 0) - ) (set_local $5 (get_local $1) ) - (set_local $10 - (i32.const 0) - ) (set_local $1 (i32.const 0) ) @@ -8519,7 +8510,7 @@ ) ) ) - (if + (br_if $do-once4 (i32.eqz (tee_local $1 (i32.load @@ -8532,12 +8523,6 @@ ) ) ) - (block - (set_local $9 - (i32.const 0) - ) - (br $do-once4) - ) ) ) (loop $while-in7 @@ -9145,9 +9130,6 @@ ) ) (block - (set_local $6 - (i32.const 0) - ) (set_local $8 (i32.shl (get_local $2) @@ -9285,13 +9267,8 @@ ) ) ) - (block - (set_local $4 - (i32.const 0) - ) - (set_local $0 - (i32.const 0) - ) + (set_local $0 + (i32.const 0) ) ) (if @@ -9570,7 +9547,7 @@ ) ) ) - (if + (br_if $do-once17 (i32.eqz (tee_local $1 (i32.load @@ -9583,12 +9560,6 @@ ) ) ) - (block - (set_local $11 - (i32.const 0) - ) - (br $do-once17) - ) ) ) (loop $while-in20 @@ -10910,9 +10881,6 @@ (get_local $1) ) ) - (set_local $3 - (get_local $1) - ) ) (if (i32.ne @@ -11578,12 +11546,7 @@ (set_local $0 (get_local $3) ) - (block - (set_local $12 - (i32.const 0) - ) - (br $do-once55) - ) + (br $do-once55) ) ) (loop $while-in58 @@ -13567,12 +13530,7 @@ (set_local $4 (get_local $8) ) - (block - (set_local $6 - (i32.const 0) - ) - (br $do-once0) - ) + (br $do-once0) ) ) (loop $while-in @@ -14219,12 +14177,7 @@ (set_local $0 (get_local $1) ) - (block - (set_local $9 - (i32.const 0) - ) - (br $do-once6) - ) + (br $do-once6) ) ) (loop $while-in9 diff --git a/test/memorygrowth.fromasm b/test/memorygrowth.fromasm index 560b34249..c556c8896 100644 --- a/test/memorygrowth.fromasm +++ b/test/memorygrowth.fromasm @@ -902,7 +902,7 @@ (get_local $9) ) ) - (if + (br_if $do-once4 (i32.eqz (tee_local $14 (i32.load @@ -915,12 +915,6 @@ ) ) ) - (block - (set_local $23 - (i32.const 0) - ) - (br $do-once4) - ) ) ) (loop $while-in7 @@ -1560,9 +1554,6 @@ (set_local $7 (get_local $12) ) - (set_local $8 - (i32.const 0) - ) (loop $while-in14 (if (i32.lt_u @@ -1691,12 +1682,6 @@ (set_local $36 (get_local $4) ) - (set_local $5 - (i32.const 0) - ) - (set_local $33 - (i32.const 0) - ) (set_local $7 (i32.const 86) ) @@ -2039,12 +2024,7 @@ (set_local $1 (get_local $12) ) - (block - (set_local $22 - (i32.const 0) - ) - (br $do-once17) - ) + (br $do-once17) ) ) (loop $while-in20 @@ -4218,12 +4198,7 @@ (get_local $18) ) ) - (block - (set_local $24 - (i32.const 0) - ) - (br $do-once51) - ) + (br $do-once51) ) ) (loop $while-in54 @@ -6290,7 +6265,7 @@ (get_local $3) ) ) - (if + (br_if $do-once0 (i32.eqz (tee_local $0 (i32.load @@ -6298,12 +6273,6 @@ ) ) ) - (block - (set_local $5 - (i32.const 0) - ) - (br $do-once0) - ) ) ) (loop $while-in @@ -6967,12 +6936,7 @@ (set_local $6 (get_local $0) ) - (block - (set_local $11 - (i32.const 0) - ) - (br $do-once6) - ) + (br $do-once6) ) ) (loop $while-in9 @@ -8172,11 +8136,10 @@ ) ) (if - (call $Xa - (get_local $2) - ) - (set_local $4 - (i32.const 0) + (i32.eqz + (call $Xa + (get_local $2) + ) ) (block (set_local $6 diff --git a/test/memorygrowth.fromasm.clamp b/test/memorygrowth.fromasm.clamp index 560b34249..c556c8896 100644 --- a/test/memorygrowth.fromasm.clamp +++ b/test/memorygrowth.fromasm.clamp @@ -902,7 +902,7 @@ (get_local $9) ) ) - (if + (br_if $do-once4 (i32.eqz (tee_local $14 (i32.load @@ -915,12 +915,6 @@ ) ) ) - (block - (set_local $23 - (i32.const 0) - ) - (br $do-once4) - ) ) ) (loop $while-in7 @@ -1560,9 +1554,6 @@ (set_local $7 (get_local $12) ) - (set_local $8 - (i32.const 0) - ) (loop $while-in14 (if (i32.lt_u @@ -1691,12 +1682,6 @@ (set_local $36 (get_local $4) ) - (set_local $5 - (i32.const 0) - ) - (set_local $33 - (i32.const 0) - ) (set_local $7 (i32.const 86) ) @@ -2039,12 +2024,7 @@ (set_local $1 (get_local $12) ) - (block - (set_local $22 - (i32.const 0) - ) - (br $do-once17) - ) + (br $do-once17) ) ) (loop $while-in20 @@ -4218,12 +4198,7 @@ (get_local $18) ) ) - (block - (set_local $24 - (i32.const 0) - ) - (br $do-once51) - ) + (br $do-once51) ) ) (loop $while-in54 @@ -6290,7 +6265,7 @@ (get_local $3) ) ) - (if + (br_if $do-once0 (i32.eqz (tee_local $0 (i32.load @@ -6298,12 +6273,6 @@ ) ) ) - (block - (set_local $5 - (i32.const 0) - ) - (br $do-once0) - ) ) ) (loop $while-in @@ -6967,12 +6936,7 @@ (set_local $6 (get_local $0) ) - (block - (set_local $11 - (i32.const 0) - ) - (br $do-once6) - ) + (br $do-once6) ) ) (loop $while-in9 @@ -8172,11 +8136,10 @@ ) ) (if - (call $Xa - (get_local $2) - ) - (set_local $4 - (i32.const 0) + (i32.eqz + (call $Xa + (get_local $2) + ) ) (block (set_local $6 diff --git a/test/memorygrowth.fromasm.imprecise b/test/memorygrowth.fromasm.imprecise index 6e5e9e996..522944903 100644 --- a/test/memorygrowth.fromasm.imprecise +++ b/test/memorygrowth.fromasm.imprecise @@ -901,7 +901,7 @@ (get_local $9) ) ) - (if + (br_if $do-once4 (i32.eqz (tee_local $14 (i32.load @@ -914,12 +914,6 @@ ) ) ) - (block - (set_local $23 - (i32.const 0) - ) - (br $do-once4) - ) ) ) (loop $while-in7 @@ -1559,9 +1553,6 @@ (set_local $7 (get_local $12) ) - (set_local $8 - (i32.const 0) - ) (loop $while-in14 (if (i32.lt_u @@ -1690,12 +1681,6 @@ (set_local $36 (get_local $4) ) - (set_local $5 - (i32.const 0) - ) - (set_local $33 - (i32.const 0) - ) (set_local $7 (i32.const 86) ) @@ -2038,12 +2023,7 @@ (set_local $1 (get_local $12) ) - (block - (set_local $22 - (i32.const 0) - ) - (br $do-once17) - ) + (br $do-once17) ) ) (loop $while-in20 @@ -4217,12 +4197,7 @@ (get_local $18) ) ) - (block - (set_local $24 - (i32.const 0) - ) - (br $do-once51) - ) + (br $do-once51) ) ) (loop $while-in54 @@ -6289,7 +6264,7 @@ (get_local $3) ) ) - (if + (br_if $do-once0 (i32.eqz (tee_local $0 (i32.load @@ -6297,12 +6272,6 @@ ) ) ) - (block - (set_local $5 - (i32.const 0) - ) - (br $do-once0) - ) ) ) (loop $while-in @@ -6966,12 +6935,7 @@ (set_local $6 (get_local $0) ) - (block - (set_local $11 - (i32.const 0) - ) - (br $do-once6) - ) + (br $do-once6) ) ) (loop $while-in9 @@ -8171,11 +8135,10 @@ ) ) (if - (call $Xa - (get_local $2) - ) - (set_local $4 - (i32.const 0) + (i32.eqz + (call $Xa + (get_local $2) + ) ) (block (set_local $6 diff --git a/test/passes/rse.txt b/test/passes/rse.txt new file mode 100644 index 000000000..017616cce --- /dev/null +++ b/test/passes/rse.txt @@ -0,0 +1,434 @@ +(module + (type $0 (func (param i32 f64))) + (type $1 (func (param i32))) + (type $2 (func)) + (type $3 (func (param i32 i32))) + (memory $0 0) + (func $basic (; 0 ;) (type $0) (param $x i32) (param $y f64) + (local $a f32) + (local $b i64) + (set_local $x + (i32.const 0) + ) + (set_local $y + (f64.const 0) + ) + (drop + (f32.const 0) + ) + (drop + (i64.const 0) + ) + ) + (func $later-param-use (; 1 ;) (type $1) (param $x i32) + (set_local $x + (i32.const 0) + ) + (drop + (i32.const 0) + ) + ) + (func $diff-value (; 2 ;) (type $1) (param $x i32) + (local $a i32) + (set_local $x + (i32.const 0) + ) + (set_local $x + (i32.const 1) + ) + (drop + (i32.const 1) + ) + (set_local $a + (i32.const 1) + ) + (drop + (i32.const 1) + ) + (set_local $a + (i32.const 0) + ) + ) + (func $unreach (; 3 ;) (type $2) + (local $a i32) + (block $x + (drop + (i32.const 0) + ) + (set_local $a + (i32.const 1) + ) + (drop + (i32.const 1) + ) + (br $x) + (set_local $a + (i32.const 1) + ) + (set_local $a + (i32.const 2) + ) + (set_local $a + (i32.const 2) + ) + ) + ) + (func $loop (; 4 ;) (type $2) + (local $a i32) + (local $b i32) + (loop $x + (set_local $a + (i32.const 0) + ) + (set_local $a + (i32.const 1) + ) + (br_if $x + (i32.const 1) + ) + ) + (block $y + (drop + (i32.const 0) + ) + (set_local $b + (i32.const 1) + ) + (br $y) + ) + (drop + (i32.const 1) + ) + ) + (func $if (; 5 ;) (type $2) + (local $x i32) + (if + (i32.const 0) + (set_local $x + (i32.const 1) + ) + (set_local $x + (i32.const 1) + ) + ) + (drop + (i32.const 1) + ) + ) + (func $if2 (; 6 ;) (type $2) + (local $x i32) + (if + (tee_local $x + (i32.const 1) + ) + (drop + (i32.const 1) + ) + (drop + (i32.const 1) + ) + ) + (drop + (i32.const 1) + ) + ) + (func $if3 (; 7 ;) (type $2) + (local $x i32) + (if + (tee_local $x + (i32.const 1) + ) + (drop + (i32.const 1) + ) + (set_local $x + (i32.const 2) + ) + ) + (set_local $x + (i32.const 1) + ) + ) + (func $copy (; 8 ;) (type $2) + (local $x i32) + (local $y i32) + (set_local $x + (i32.const 1) + ) + (set_local $y + (get_local $x) + ) + (drop + (i32.const 1) + ) + (set_local $x + (i32.const 2) + ) + (if + (i32.const 1) + (nop) + (nop) + ) + (set_local $y + (get_local $x) + ) + (drop + (i32.const 2) + ) + (if + (i32.const 1) + (nop) + (nop) + ) + (drop + (i32.const 2) + ) + (set_local $x + (i32.const 3) + ) + (set_local $y + (i32.const 3) + ) + (drop + (get_local $x) + ) + ) + (func $param-unique (; 9 ;) (type $1) (param $x i32) + (local $a i32) + (set_local $a + (get_local $x) + ) + (drop + (get_local $x) + ) + (set_local $x + (i32.eqz + (i32.const 9999) + ) + ) + (set_local $a + (get_local $x) + ) + (drop + (get_local $x) + ) + ) + (func $set-unique (; 10 ;) (type $2) + (local $x i32) + (local $y i32) + (set_local $x + (i32.eqz + (i32.const 123) + ) + ) + (set_local $y + (get_local $x) + ) + (drop + (get_local $x) + ) + (set_local $x + (i32.eqz + (i32.const 456) + ) + ) + (set_local $y + (get_local $x) + ) + (drop + (get_local $x) + ) + (set_local $x + (i32.eqz + (i32.const 789) + ) + ) + (if + (i32.const 1) + (nop) + (nop) + ) + (set_local $y + (get_local $x) + ) + (drop + (get_local $x) + ) + (set_local $x + (i32.eqz + (i32.const 1000) + ) + ) + (set_local $y + (get_local $x) + ) + (if + (i32.const 1) + (nop) + (nop) + ) + (drop + (get_local $x) + ) + ) + (func $identical_complex (; 11 ;) (type $1) (param $x i32) + (local $y i32) + (set_local $y + (get_local $x) + ) + (drop + (get_local $x) + ) + (drop + (get_local $x) + ) + (drop + (get_local $x) + ) + (drop + (get_local $y) + ) + (drop + (get_local $y) + ) + ) + (func $merge (; 12 ;) (type $2) + (local $x i32) + (if + (i32.const 1) + (set_local $x + (i32.const 1) + ) + (set_local $x + (i32.const 1) + ) + ) + (drop + (i32.const 1) + ) + (set_local $x + (i32.const 2) + ) + (loop $loop + (drop + (i32.const 2) + ) + (set_local $x + (i32.const 3) + ) + (set_local $x + (i32.const 2) + ) + (br_if $loop + (i32.const 2) + ) + ) + (drop + (i32.const 2) + ) + ) + (func $one-arm (; 13 ;) (type $3) (param $1 i32) (param $3 i32) + (set_local $1 + (get_local $3) + ) + (if + (i32.const 1) + (nop) + (drop + (get_local $1) + ) + ) + ) + (func $one-arm2 (; 14 ;) (type $3) (param $1 i32) (param $3 i32) + (set_local $1 + (get_local $3) + ) + (if + (i32.const 1) + (drop + (get_local $1) + ) + ) + ) + (func $many-merges (; 15 ;) (type $2) + (local $0 i32) + (local $1 i32) + (block $block + (br_if $block + (i32.const 0) + ) + (loop $loop + (set_local $1 + (get_local $0) + ) + (set_local $0 + (i32.const 99) + ) + (br_if $loop + (i32.const 1) + ) + ) + ) + (set_local $0 + (get_local $1) + ) + (if + (i32.const 0) + (drop + (get_local $0) + ) + ) + ) + (func $fuzz (; 16 ;) (type $2) + (local $x i32) + (loop $label$4 + (block $label$5 + (if + (i32.const 1) + (block $block + (set_local $x + (i32.const 203) + ) + (br $label$5) + ) + ) + (br_if $label$4 + (i32.const 2) + ) + ) + ) + (loop $label$7 + (if + (if (result i32) + (i32.const 3) + (i32.const 4) + (i32.const 5) + ) + (br $label$7) + ) + ) + ) + (func $fuzz2 (; 17 ;) (type $2) + (local $var$1 i32) + (if + (i32.const 0) + (if + (i32.const 1) + (set_local $var$1 + (i32.const 2) + ) + ) + ) + (loop $label$10 + (block $label$11 + (if + (i32.const 5) + (br_if $label$11 + (i32.const 6) + ) + ) + (br $label$10) + ) + ) + ) +) diff --git a/test/passes/rse.wast b/test/passes/rse.wast new file mode 100644 index 000000000..6a0ada018 --- /dev/null +++ b/test/passes/rse.wast @@ -0,0 +1,252 @@ +(module + (func $basic (param $x i32) (param $y f64) + (local $a f32) + (local $b i64) + (set_local $x (i32.const 0)) + (set_local $y (f64.const 0)) + (set_local $a (f32.const 0)) + (set_local $b (i64.const 0)) + ) + (func $later-param-use (param $x i32) + (set_local $x (i32.const 0)) + (set_local $x (i32.const 0)) + ) + (func $diff-value (param $x i32) + (local $a i32) + (set_local $x (i32.const 0)) + (set_local $x (i32.const 1)) + (set_local $x (i32.const 1)) + (set_local $a (i32.const 1)) + (set_local $a (i32.const 1)) + (set_local $a (i32.const 0)) + ) + (func $unreach + (local $a i32) + (block $x + (set_local $a (i32.const 0)) + (set_local $a (i32.const 1)) + (set_local $a (i32.const 1)) + (br $x) + (set_local $a (i32.const 1)) ;; ignore all these + (set_local $a (i32.const 2)) + (set_local $a (i32.const 2)) + ) + ) + (func $loop + (local $a i32) + (local $b i32) + (loop $x + (set_local $a (i32.const 0)) + (set_local $a (i32.const 1)) + (br_if $x (i32.const 1)) + ) + (block $y + (set_local $b (i32.const 0)) + (set_local $b (i32.const 1)) + (br $y) + ) + (set_local $b (i32.const 1)) + ) + (func $if + (local $x i32) + (if (tee_local $x (i32.const 0)) + (set_local $x (i32.const 1)) + (set_local $x (i32.const 1)) + ) + (set_local $x (i32.const 1)) + ) + (func $if2 + (local $x i32) + (if (tee_local $x (i32.const 1)) + (set_local $x (i32.const 1)) + (set_local $x (i32.const 1)) + ) + (set_local $x (i32.const 1)) + ) + (func $if3 + (local $x i32) + (if (tee_local $x (i32.const 1)) + (set_local $x (i32.const 1)) + (set_local $x (i32.const 2)) + ) + (set_local $x (i32.const 1)) + ) + (func $copy + (local $x i32) + (local $y i32) + (set_local $x (i32.const 1)) + (set_local $y (get_local $x)) + (set_local $y (i32.const 1)) + (set_local $x (i32.const 2)) + (if (i32.const 1) (nop) (nop)) ;; control flow + (set_local $y (get_local $x)) + (set_local $y (i32.const 2)) + (if (i32.const 1) (nop) (nop)) ;; control flow + (set_local $y (i32.const 2)) + ;; flip + (set_local $x (i32.const 3)) + (set_local $y (i32.const 3)) + (set_local $y (get_local $x)) ;; do this last + ) + (func $param-unique + (param $x i32) + (local $a i32) + (set_local $a (get_local $x)) + (set_local $a (get_local $x)) + (set_local $x (i32.eqz (i32.const 9999))) + (set_local $a (get_local $x)) + (set_local $a (get_local $x)) + ) + (func $set-unique + (local $x i32) + (local $y i32) + (set_local $x (i32.eqz (i32.const 123))) + (set_local $y (get_local $x)) + (set_local $y (get_local $x)) + (set_local $x (i32.eqz (i32.const 456))) + (set_local $y (get_local $x)) + (set_local $y (get_local $x)) + (set_local $x (i32.eqz (i32.const 789))) + (if (i32.const 1) (nop) (nop)) ;; control flow + (set_local $y (get_local $x)) + (set_local $y (get_local $x)) + (set_local $x (i32.eqz (i32.const 1000))) + (set_local $y (get_local $x)) + (if (i32.const 1) (nop) (nop)) ;; control flow + (set_local $y (get_local $x)) + ) + (func $identical_complex (param $x i32) + (local $y i32) + (set_local $y (get_local $x)) + (set_local $y (get_local $x)) + (set_local $y (get_local $x)) + (set_local $x (get_local $x)) + (set_local $y (get_local $y)) + (set_local $x (get_local $y)) + ) + (func $merge + (local $x i32) + (if (i32.const 1) + (set_local $x (i32.const 1)) + (set_local $x (i32.const 1)) + ) + (set_local $x (i32.const 1)) + (set_local $x (i32.const 2)) + (loop $loop + (set_local $x (i32.const 2)) + (set_local $x (i32.const 3)) + (set_local $x (i32.const 2)) + (br_if $loop (i32.const 2)) + ) + (set_local $x (i32.const 2)) + ) + (func $one-arm + (param $1 i32) + (param $3 i32) + (set_local $1 + (get_local $3) + ) + (if + (i32.const 1) + (nop) + (set_local $3 + (get_local $1) + ) + ) + ) + (func $one-arm2 + (param $1 i32) + (param $3 i32) + (set_local $1 + (get_local $3) + ) + (if + (i32.const 1) + (set_local $3 + (get_local $1) + ) + ) + ) + (func $many-merges + (local $0 i32) + (local $1 i32) + (block $block + (br_if $block + (i32.const 0) + ) + (loop $loop + (set_local $1 + (get_local $0) + ) + (set_local $0 + (i32.const 99) + ) + (br_if $loop + (i32.const 1) + ) + ) + ) + (set_local $0 ;; make them equal + (get_local $1) + ) + (if + (i32.const 0) + (set_local $1 ;; we can drop this + (get_local $0) + ) + ) + ) + (func $fuzz + (local $x i32) + (loop $label$4 + (block $label$5 + (if + (i32.const 1) + (block + (set_local $x + (i32.const 203) + ) + (br $label$5) + ) + ) + (br_if $label$4 + (i32.const 2) + ) + ) + ) + (loop $label$7 + (if + (if (result i32) + (i32.const 3) + (i32.const 4) + (i32.const 5) + ) + (br $label$7) + ) + ) + ) + (func $fuzz2 + (local $var$1 i32) + (if + (i32.const 0) + (if + (i32.const 1) + (set_local $var$1 + (i32.const 2) + ) + ) + ) + (loop $label$10 + (block $label$11 + (if + (i32.const 5) + (br_if $label$11 + (i32.const 6) + ) + ) + (br $label$10) + ) + ) + ) +) + diff --git a/test/threads.fromasm b/test/threads.fromasm index 7aafe4a4b..97a3f7de9 100644 --- a/test/threads.fromasm +++ b/test/threads.fromasm @@ -24,9 +24,7 @@ (i32.atomic.load16_u (i32.const 2458) ) - (tee_local $0 - (i32.const 0) - ) + (i32.const 0) ) (i32.atomic.rmw.xchg (get_local $0) diff --git a/test/threads.fromasm.clamp b/test/threads.fromasm.clamp index 7aafe4a4b..97a3f7de9 100644 --- a/test/threads.fromasm.clamp +++ b/test/threads.fromasm.clamp @@ -24,9 +24,7 @@ (i32.atomic.load16_u (i32.const 2458) ) - (tee_local $0 - (i32.const 0) - ) + (i32.const 0) ) (i32.atomic.rmw.xchg (get_local $0) diff --git a/test/threads.fromasm.imprecise b/test/threads.fromasm.imprecise index 546f27370..a166a49ef 100644 --- a/test/threads.fromasm.imprecise +++ b/test/threads.fromasm.imprecise @@ -23,9 +23,7 @@ (i32.atomic.load16_u (i32.const 2458) ) - (tee_local $0 - (i32.const 0) - ) + (i32.const 0) ) (i32.atomic.rmw.xchg (get_local $0) diff --git a/test/unit.fromasm b/test/unit.fromasm index c890b3a55..9a58b7747 100644 --- a/test/unit.fromasm +++ b/test/unit.fromasm @@ -771,9 +771,6 @@ (local $0 i32) (local $1 i32) (local $2 i32) - (set_local $1 - (i32.const 0) - ) (loop $label$continue$L7 (block $label$break$L7 (set_local $0 diff --git a/test/unit.fromasm.clamp b/test/unit.fromasm.clamp index 09c68d8f1..4d8776037 100644 --- a/test/unit.fromasm.clamp +++ b/test/unit.fromasm.clamp @@ -819,9 +819,6 @@ (local $0 i32) (local $1 i32) (local $2 i32) - (set_local $1 - (i32.const 0) - ) (loop $label$continue$L7 (block $label$break$L7 (set_local $0 diff --git a/test/unit.fromasm.imprecise b/test/unit.fromasm.imprecise index 6cda1e7c1..1212a4c34 100644 --- a/test/unit.fromasm.imprecise +++ b/test/unit.fromasm.imprecise @@ -760,9 +760,6 @@ (local $0 i32) (local $1 i32) (local $2 i32) - (set_local $1 - (i32.const 0) - ) (loop $label$continue$L7 (block $label$break$L7 (set_local $0 diff --git a/test/wasm-only.fromasm b/test/wasm-only.fromasm index 8ac681f2b..2f9a2a37b 100644 --- a/test/wasm-only.fromasm +++ b/test/wasm-only.fromasm @@ -667,9 +667,7 @@ (block $switch8 (if (i32.ne - (tee_local $1 - (i32.const 100) - ) + (i32.const 100) (i32.const 214748364) ) (br_if $switch8 diff --git a/test/wasm-only.fromasm.clamp b/test/wasm-only.fromasm.clamp index 8ac681f2b..2f9a2a37b 100644 --- a/test/wasm-only.fromasm.clamp +++ b/test/wasm-only.fromasm.clamp @@ -667,9 +667,7 @@ (block $switch8 (if (i32.ne - (tee_local $1 - (i32.const 100) - ) + (i32.const 100) (i32.const 214748364) ) (br_if $switch8 diff --git a/test/wasm-only.fromasm.imprecise b/test/wasm-only.fromasm.imprecise index 8aab435ef..df12f655b 100644 --- a/test/wasm-only.fromasm.imprecise +++ b/test/wasm-only.fromasm.imprecise @@ -352,9 +352,7 @@ (block $switch8 (if (i32.ne - (tee_local $1 - (i32.const 100) - ) + (i32.const 100) (i32.const 214748364) ) (br_if $switch8 |