diff options
12 files changed, 1651 insertions, 24 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index c6acad7dc..751752fec 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -168,6 +168,7 @@ ENDIF() # Static libraries ADD_SUBDIRECTORY(src/ast) ADD_SUBDIRECTORY(src/asmjs) +ADD_SUBDIRECTORY(src/cfg) ADD_SUBDIRECTORY(src/emscripten-optimizer) ADD_SUBDIRECTORY(src/passes) ADD_SUBDIRECTORY(src/support) @@ -178,14 +179,13 @@ ADD_SUBDIRECTORY(src/wasm) SET(binaryen_SOURCES src/binaryen-c.cpp - src/cfg/Relooper.cpp ) IF(BUILD_STATIC_LIB) ADD_LIBRARY(binaryen STATIC ${binaryen_SOURCES}) ELSE() ADD_LIBRARY(binaryen SHARED ${binaryen_SOURCES}) ENDIF() -TARGET_LINK_LIBRARIES(binaryen ${all_passes} wasm asmjs ast support) +TARGET_LINK_LIBRARIES(binaryen ${all_passes} wasm asmjs ast cfg support) INSTALL(TARGETS binaryen DESTINATION ${CMAKE_INSTALL_LIBDIR}) INSTALL(FILES src/binaryen-c.h DESTINATION ${CMAKE_INSTALL_INCLUDEDIR}) @@ -198,7 +198,7 @@ SET(wasm-shell_SOURCES ) ADD_EXECUTABLE(wasm-shell ${wasm-shell_SOURCES}) -TARGET_LINK_LIBRARIES(wasm-shell wasm asmjs emscripten-optimizer ${all_passes} ast support) +TARGET_LINK_LIBRARIES(wasm-shell wasm asmjs emscripten-optimizer ${all_passes} ast cfg support) SET_PROPERTY(TARGET wasm-shell PROPERTY CXX_STANDARD 11) SET_PROPERTY(TARGET wasm-shell PROPERTY CXX_STANDARD_REQUIRED ON) INSTALL(TARGETS wasm-shell DESTINATION ${CMAKE_INSTALL_BINDIR}) @@ -208,7 +208,7 @@ SET(wasm-opt_SOURCES ) ADD_EXECUTABLE(wasm-opt ${wasm-opt_SOURCES}) -TARGET_LINK_LIBRARIES(wasm-opt wasm asmjs emscripten-optimizer ${all_passes} ast support) +TARGET_LINK_LIBRARIES(wasm-opt wasm asmjs emscripten-optimizer ${all_passes} ast cfg support) SET_PROPERTY(TARGET wasm-opt PROPERTY CXX_STANDARD 11) SET_PROPERTY(TARGET wasm-opt PROPERTY CXX_STANDARD_REQUIRED ON) INSTALL(TARGETS wasm-opt DESTINATION ${CMAKE_INSTALL_BINDIR}) @@ -218,7 +218,7 @@ SET(wasm-merge_SOURCES ) ADD_EXECUTABLE(wasm-merge ${wasm-merge_SOURCES}) -TARGET_LINK_LIBRARIES(wasm-merge wasm asmjs emscripten-optimizer ${all_passes} ast support) +TARGET_LINK_LIBRARIES(wasm-merge wasm asmjs emscripten-optimizer ${all_passes} ast cfg support) SET_PROPERTY(TARGET wasm-merge PROPERTY CXX_STANDARD 11) SET_PROPERTY(TARGET wasm-merge PROPERTY CXX_STANDARD_REQUIRED ON) INSTALL(TARGETS wasm-merge DESTINATION bin) @@ -229,7 +229,7 @@ SET(asm2wasm_SOURCES ) ADD_EXECUTABLE(asm2wasm ${asm2wasm_SOURCES}) -TARGET_LINK_LIBRARIES(asm2wasm emscripten-optimizer ${all_passes} wasm asmjs ast support) +TARGET_LINK_LIBRARIES(asm2wasm emscripten-optimizer ${all_passes} wasm asmjs ast cfg support) SET_PROPERTY(TARGET asm2wasm PROPERTY CXX_STANDARD 11) SET_PROPERTY(TARGET asm2wasm PROPERTY CXX_STANDARD_REQUIRED ON) INSTALL(TARGETS asm2wasm DESTINATION ${CMAKE_INSTALL_BINDIR}) @@ -241,7 +241,7 @@ SET(s2wasm_SOURCES ) ADD_EXECUTABLE(s2wasm ${s2wasm_SOURCES}) -TARGET_LINK_LIBRARIES(s2wasm passes wasm asmjs ast support) +TARGET_LINK_LIBRARIES(s2wasm passes wasm asmjs ast cfg support) SET_PROPERTY(TARGET s2wasm PROPERTY CXX_STANDARD 11) SET_PROPERTY(TARGET s2wasm PROPERTY CXX_STANDARD_REQUIRED ON) INSTALL(TARGETS s2wasm DESTINATION ${CMAKE_INSTALL_BINDIR}) @@ -251,7 +251,7 @@ SET(wasm_as_SOURCES ) ADD_EXECUTABLE(wasm-as ${wasm_as_SOURCES}) -TARGET_LINK_LIBRARIES(wasm-as wasm asmjs passes ast support) +TARGET_LINK_LIBRARIES(wasm-as wasm asmjs passes ast cfg support) SET_PROPERTY(TARGET wasm-as PROPERTY CXX_STANDARD 11) SET_PROPERTY(TARGET wasm-as PROPERTY CXX_STANDARD_REQUIRED ON) INSTALL(TARGETS wasm-as DESTINATION ${CMAKE_INSTALL_BINDIR}) @@ -261,7 +261,7 @@ SET(wasm_dis_SOURCES ) ADD_EXECUTABLE(wasm-dis ${wasm_dis_SOURCES}) -TARGET_LINK_LIBRARIES(wasm-dis passes wasm asmjs ast support) +TARGET_LINK_LIBRARIES(wasm-dis passes wasm asmjs ast cfg support) SET_PROPERTY(TARGET wasm-dis PROPERTY CXX_STANDARD 11) SET_PROPERTY(TARGET wasm-dis PROPERTY CXX_STANDARD_REQUIRED ON) INSTALL(TARGETS wasm-dis DESTINATION ${CMAKE_INSTALL_BINDIR}) @@ -271,7 +271,7 @@ SET(wasm-ctor-eval_SOURCES ) ADD_EXECUTABLE(wasm-ctor-eval ${wasm-ctor-eval_SOURCES}) -TARGET_LINK_LIBRARIES(wasm-ctor-eval wasm asmjs emscripten-optimizer ${all_passes} ast support) +TARGET_LINK_LIBRARIES(wasm-ctor-eval wasm asmjs emscripten-optimizer ${all_passes} ast cfg support) SET_PROPERTY(TARGET wasm-ctor-eval PROPERTY CXX_STANDARD 11) SET_PROPERTY(TARGET wasm-ctor-eval PROPERTY CXX_STANDARD_REQUIRED ON) INSTALL(TARGETS wasm-ctor-eval DESTINATION bin) diff --git a/src/cfg/CMakeLists.txt b/src/cfg/CMakeLists.txt new file mode 100644 index 000000000..f0825b454 --- /dev/null +++ b/src/cfg/CMakeLists.txt @@ -0,0 +1,4 @@ +SET(cfg_SOURCES + Relooper.cpp +) +ADD_LIBRARY(cfg STATIC ${cfg_SOURCES}) diff --git a/src/cfg/Relooper.cpp b/src/cfg/Relooper.cpp index b49114b74..a900c6608 100644 --- a/src/cfg/Relooper.cpp +++ b/src/cfg/Relooper.cpp @@ -57,6 +57,7 @@ static wasm::Expression* HandleFollowupMultiples(wasm::Expression* Ret, Shape* P int Id = iter.first; Shape* Body = iter.second; Curr->name = Builder.getBlockBreakName(Id); + Curr->finalize(); // it may now be reachable, via a break auto* Outer = Builder.makeBlock(Curr); Outer->list.push_back(Body->Render(Builder, InLoop)); Outer->finalize(); // TODO: not really necessary diff --git a/src/pass.h b/src/pass.h index 3f0c2c29d..513979954 100644 --- a/src/pass.h +++ b/src/pass.h @@ -152,11 +152,14 @@ public: virtual void prepareToRun(PassRunner* runner, Module* module) {} // Implement this with code to run the pass on the whole module - virtual void run(PassRunner* runner, Module* module) = 0; + virtual void run(PassRunner* runner, Module* module) { + WASM_UNREACHABLE(); + } - // Implement this with code to run the pass on a single function + // Implement this with code to run the pass on a single function, for + // a function-parallel pass virtual void runFunction(PassRunner* runner, Module* module, Function* function) { - WASM_UNREACHABLE(); // by default, passes cannot be run this way + WASM_UNREACHABLE(); } // Function parallelism. By default, passes are not run in parallel, but you diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt index d7f17a3ca..66f86a02f 100644 --- a/src/passes/CMakeLists.txt +++ b/src/passes/CMakeLists.txt @@ -23,6 +23,7 @@ SET(passes_SOURCES Print.cpp PrintCallGraph.cpp RelooperJumpThreading.cpp + ReReloop.cpp RemoveImports.cpp RemoveMemory.cpp RemoveUnusedBrs.cpp diff --git a/src/passes/ReReloop.cpp b/src/passes/ReReloop.cpp new file mode 100644 index 000000000..6bdc0eb06 --- /dev/null +++ b/src/passes/ReReloop.cpp @@ -0,0 +1,325 @@ +/* + * 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. + */ + +// +// Convert the AST to a CFG, and optimize+convert it back to the AST +// using the relooper. +// +// This pass depends on flatten-control-flow being run before it. +// + +#include <memory> + +#include "wasm.h" +#include "wasm-builder.h" +#include "wasm-traversal.h" +#include "pass.h" +#include "cfg/Relooper.h" + +namespace wasm { + +struct ReReloop : public Pass { + bool isFunctionParallel() override { return true; } + + Pass* create() override { return new ReReloop; } + + CFG::Relooper relooper; + std::unique_ptr<Builder> builder; + + // block handling + + CFG::Block* currCFGBlock = nullptr; + + CFG::Block* makeCFGBlock() { + auto* ret = new CFG::Block(builder->makeBlock()); + relooper.AddBlock(ret); + return ret; + } + + CFG::Block* setCurrCFGBlock(CFG::Block* curr) { + if (currCFGBlock) { + finishBlock(); + } + return currCFGBlock = curr; + } + + CFG::Block* startCFGBlock() { + return setCurrCFGBlock(makeCFGBlock()); + } + + CFG::Block* getCurrCFGBlock() { + return currCFGBlock; + } + + Block* getCurrBlock() { + return currCFGBlock->Code->cast<Block>(); + } + + void finishBlock() { + getCurrBlock()->finalize(); + } + + // break handling + + std::map<Name, CFG::Block*> breakTargets; + + void addBreakTarget(Name name, CFG::Block* target) { + breakTargets[name] = target; + } + + CFG::Block* getBreakTarget(Name name) { + return breakTargets[name]; + } + + // branch handling + + void addBranch(CFG::Block* from, CFG::Block* to, Expression* condition = nullptr) { + from->AddBranchTo(to, condition); + } + + void addSwitchBranch(CFG::Block* from, CFG::Block* to, const std::set<Index>& values) { + std::vector<Index> list; + for (auto i : values) list.push_back(i); + from->AddSwitchBranchTo(to, std::move(list)); + } + + // we work using a stack of control flow tasks + + struct Task { + ReReloop& parent; + Task(ReReloop& parent) : parent(parent) {} + virtual void run() { + WASM_UNREACHABLE(); + } + }; + + typedef std::shared_ptr<Task> TaskPtr; + std::vector<TaskPtr> stack; + + struct TriageTask : public Task { + Expression* curr; + + TriageTask(ReReloop& parent, Expression* curr) : Task(parent), curr(curr) {} + + void run() override { + parent.triage(curr); + } + }; + + struct BlockTask : public Task { + Block* curr; + CFG::Block* later; + + BlockTask(ReReloop& parent, Block* curr) : Task(parent), curr(curr) {} + + static void handle(ReReloop& parent, Block* curr) { + if (curr->name.is()) { + // we may be branched to. create a target, and + // ensure we are called at the join point + auto task = std::make_shared<BlockTask>(parent, curr); + task->curr = curr; + task->later = parent.makeCFGBlock(); + parent.addBreakTarget(curr->name, task->later); + parent.stack.push_back(task); + } + auto& list = curr->list; + for (int i = int(list.size()) - 1; i >= 0; i--) { + parent.stack.push_back(std::make_shared<TriageTask>(parent, list[i])); + } + } + + void run() override { + // add fallthrough + parent.addBranch(parent.getCurrCFGBlock(), later); + parent.setCurrCFGBlock(later); + } + }; + + struct LoopTask : public Task { + static void handle(ReReloop& parent, Loop* curr) { + parent.stack.push_back(std::make_shared<TriageTask>(parent, curr->body)); + if (curr->name.is()) { + // we may be branched to. create a target + auto* before = parent.getCurrCFGBlock(); + auto* top = parent.startCFGBlock(); + parent.addBreakTarget(curr->name, top); + parent.addBranch(before, top); + } + } + }; + + struct IfTask : public Task { + If* curr; + CFG::Block* condition; + CFG::Block* ifTrueEnd; + int phase = 0; + + IfTask(ReReloop& parent, If* curr) : Task(parent), curr(curr) {} + + static void handle(ReReloop& parent, If* curr) { + auto task = std::make_shared<IfTask>(parent, curr); + task->curr = curr; + task->condition = parent.getCurrCFGBlock(); + auto* ifTrueBegin = parent.startCFGBlock(); + parent.addBranch(task->condition, ifTrueBegin, curr->condition); + if (curr->ifFalse) { + parent.stack.push_back(task); + parent.stack.push_back(std::make_shared<TriageTask>(parent, curr->ifFalse)); + } + parent.stack.push_back(task); + parent.stack.push_back(std::make_shared<TriageTask>(parent, curr->ifTrue)); + } + + void run() override { + if (phase == 0) { + // end of ifTrue + ifTrueEnd = parent.getCurrCFGBlock(); + auto* after = parent.startCFGBlock(); + parent.addBranch(condition, after); // if condition was false, go after the ifTrue, to ifFalse or outside + if (!curr->ifFalse) { + parent.addBranch(ifTrueEnd, after); + } + phase++; + } else if (phase == 1) { + // end if ifFalse + auto* ifFalseEnd = parent.getCurrCFGBlock(); + auto* after = parent.startCFGBlock(); + parent.addBranch(ifTrueEnd, after); + parent.addBranch(ifFalseEnd, after); + } else { + WASM_UNREACHABLE(); + } + } + }; + + struct BreakTask : public Task { + static void handle(ReReloop& parent, Break* curr) { + // add the branch. note how if the condition is false, it is the right value there as well + auto* before = parent.getCurrCFGBlock(); + parent.addBranch(before, parent.getBreakTarget(curr->name), curr->condition); + if (curr->condition) { + auto* after = parent.startCFGBlock(); + parent.addBranch(before, after); + } else { + parent.stopControlFlow(); + } + } + }; + + struct SwitchTask : public Task { + static void handle(ReReloop& parent, Switch* curr) { + // set the switch condition for the block ending now + auto* before = parent.getCurrCFGBlock(); + assert(!before->SwitchCondition); + before->SwitchCondition = curr->condition; + std::map<Name, std::set<Index>> targetValues; + auto& targets = curr->targets; + auto num = targets.size(); + for (Index i = 0; i < num; i++) { + targetValues[targets[i]].insert(i); + } + for (auto& iter : targetValues) { + parent.addSwitchBranch(before, parent.getBreakTarget(iter.first), iter.second); + } + // the default may be among the targets, in which case, we can't add it simply as + // it would be a duplicate, so create a temp block + if (targetValues.count(curr->default_) == 0) { + parent.addSwitchBranch(before, parent.getBreakTarget(curr->default_), std::set<Index>()); + } else { + auto* temp = parent.startCFGBlock(); + parent.addSwitchBranch(before, temp, std::set<Index>()); + parent.addBranch(temp, parent.getBreakTarget(curr->default_)); + } + parent.stopControlFlow(); + } + }; + + struct ReturnTask : public Task { + static void handle(ReReloop& parent, Return* curr) { + // reuse the return + parent.getCurrBlock()->list.push_back(curr); + parent.stopControlFlow(); + } + }; + + struct UnreachableTask : public Task { + static void handle(ReReloop& parent, Unreachable* curr) { + // reuse the unreachable + parent.getCurrBlock()->list.push_back(curr); + parent.stopControlFlow(); + } + }; + + // handle an element we encounter + + void triage(Expression* curr) { + if (auto* block = curr->dynCast<Block>()) { + BlockTask::handle(*this, block); + } else if (auto* loop = curr->dynCast<Loop>()) { + LoopTask::handle(*this, loop); + } else if (auto* iff = curr->dynCast<If>()) { + IfTask::handle(*this, iff); + } else if (auto* br = curr->dynCast<Break>()) { + BreakTask::handle(*this, br); + } else if (auto* sw = curr->dynCast<Switch>()) { + SwitchTask::handle(*this, sw); + } else if (auto* ret = curr->dynCast<Return>()) { + ReturnTask::handle(*this, ret); + } else if (auto* un = curr->dynCast<Unreachable>()) { + UnreachableTask::handle(*this, un); + } else { + // not control flow, so just a simple element + getCurrBlock()->list.push_back(curr); + } + } + + void stopControlFlow() { + startCFGBlock(); + // TODO: optimize with this? + } + + void runFunction(PassRunner* runner, Module* module, Function* function) override { + // since control flow is flattened, this is pretty simple + // first, traverse the function body. note how we don't need to traverse + // into expressions, as we know they contain no control flow + builder = make_unique<Builder>(*module); + auto* entry = startCFGBlock(); + stack.push_back(TaskPtr(new TriageTask(*this, function->body))); + // main loop + while (stack.size() > 0) { + TaskPtr curr = stack.back(); + stack.pop_back(); + curr->run(); + } + // finish the current block + finishBlock(); + // run the relooper to recreate control flow + relooper.Calculate(entry); + // render + { + auto temp = builder->addVar(function, i32); + CFG::RelooperBuilder builder(*module, temp); + function->body = relooper.Render(builder); + } + } +}; + +Pass *createReReloopPass() { + return new ReReloop(); +} + +} // namespace wasm + diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp index 92ab694e0..7b4a896eb 100644 --- a/src/passes/pass.cpp +++ b/src/passes/pass.cpp @@ -96,6 +96,7 @@ void PassRegistry::registerPasses() { registerPass("remove-unused-names", "removes names from locations that are never branched to", createRemoveUnusedNamesPass); registerPass("reorder-functions", "sorts functions by access frequency", createReorderFunctionsPass); registerPass("reorder-locals", "sorts locals by access frequency", createReorderLocalsPass); + registerPass("rereloop", "re-optimize control flow using the relooper algorithm", createReReloopPass); registerPass("simplify-locals", "miscellaneous locals-related optimizations", createSimplifyLocalsPass); registerPass("simplify-locals-notee", "miscellaneous locals-related optimizations", createSimplifyLocalsNoTeePass); registerPass("simplify-locals-nostructure", "miscellaneous locals-related optimizations", createSimplifyLocalsNoStructurePass); @@ -293,18 +294,10 @@ void PassRunner::doAdd(Pass* pass) { } void PassRunner::runPassOnFunction(Pass* pass, Function* func) { -#if 0 - if (debug) { - std::cerr << "[PassRunner] runPass " << pass->name << " OnFunction " << func->name << "\n"; - } -#endif + assert(pass->isFunctionParallel()); // function-parallel passes get a new instance per function - if (pass->isFunctionParallel()) { - auto instance = std::unique_ptr<Pass>(pass->create()); - instance->runFunction(this, wasm, func); - } else { - pass->runFunction(this, wasm, func); - } + auto instance = std::unique_ptr<Pass>(pass->create()); + instance->runFunction(this, wasm, func); } } // namespace wasm diff --git a/src/passes/passes.h b/src/passes/passes.h index 302d82b9f..6322aad3c 100644 --- a/src/passes/passes.h +++ b/src/passes/passes.h @@ -54,6 +54,7 @@ Pass *createRemoveUnusedModuleElementsPass(); Pass *createRemoveUnusedNamesPass(); Pass *createReorderFunctionsPass(); Pass *createReorderLocalsPass(); +Pass *createReReloopPass(); Pass *createSimplifyLocalsPass(); Pass *createSimplifyLocalsNoTeePass(); Pass *createSimplifyLocalsNoStructurePass(); diff --git a/test/passes/rereloop.txt b/test/passes/rereloop.txt new file mode 100644 index 000000000..c15934c0b --- /dev/null +++ b/test/passes/rereloop.txt @@ -0,0 +1,707 @@ +(module + (type $0 (func)) + (type $1 (func (result i32))) + (type $2 (func (param i32) (result i32))) + (type $3 (func (param i32))) + (memory $0 0) + (func $trivial (type $0) + (local $0 i32) + (block + (nop) + ) + ) + (func $trivial2 (type $0) + (local $0 i32) + (block + (call $trivial) + (call $trivial) + ) + ) + (func $return-void (type $0) + (local $0 i32) + (block + (return) + ) + ) + (func $return-val (type $1) (result i32) + (local $0 i32) + (block + (return + (i32.const 1) + ) + ) + ) + (func $ifs (type $2) (param $x i32) (result i32) + (local $1 i32) + (block + ) + (if + (get_local $x) + (block + (block + ) + (if + (get_local $x) + (block + (block + (return + (i32.const 2) + ) + ) + ) + (block + (block + (return + (i32.const 3) + ) + ) + ) + ) + ) + (block + (block + ) + (if + (get_local $x) + (block + (block + (return + (i32.const 4) + ) + ) + ) + (block + (block + (return + (i32.const 5) + ) + ) + ) + ) + ) + ) + ) + (func $loops (type $3) (param $x i32) + (local $1 i32) + (block $block$5$break + (block + ) + (if + (get_local $x) + (block + (block $block$3$break + (block + ) + (block + (br $block$3$break) + ) + ) + (loop $shape$3$continue + (block + (call $trivial) + ) + (block + (br $shape$3$continue) + ) + ) + ) + (br $block$5$break) + ) + ) + (block + (block $block$6$break + (block + ) + (block + (br $block$6$break) + ) + ) + (block + (block $block$7$break + (loop $shape$6$continue + (block + (call $trivial) + ) + (if + (get_local $x) + (br $shape$6$continue) + (br $block$7$break) + ) + ) + ) + (block + (block $block$8$break + (block + ) + (block + (br $block$8$break) + ) + ) + (block + (block $block$11$break + (loop $shape$9$continue + (block $block$9$break + (block + (call $trivial) + ) + (if + (get_local $x) + (br $block$9$break) + (br $block$11$break) + ) + ) + (block + (block + ) + (block + (br $shape$9$continue) + ) + ) + ) + ) + (block + (block + ) + ) + ) + ) + ) + ) + ) + (func $br-out (type $3) (param $x i32) + (local $1 i32) + (block $block$2$break + (block + (call $br-out + (i32.const 5) + ) + ) + (block + (br $block$2$break) + ) + ) + (block + (block + ) + ) + ) + (func $unreachable (type $3) (param $x i32) + (local $1 i32) + (block $block$2$break + (block + ) + (if + (get_local $x) + (br $block$2$break) + (block + (block $block$11$break + (block + (call $unreachable + (i32.const 5) + ) + ) + (block + (br $block$11$break) + ) + ) + (block + (block + ) + ) + ) + ) + ) + (block + (block + ) + (if + (get_local $x) + (block + (block + (call $unreachable + (i32.const 1) + ) + (unreachable) + ) + ) + (block + (block + (call $unreachable + (i32.const 3) + ) + (return) + ) + ) + ) + ) + ) + (func $empty-blocks (type $3) (param $x i32) + (local $1 i32) + (block $block$2$break + (block + ) + (block + (br $block$2$break) + ) + ) + (block + (block $block$3$break + (block + ) + (block + (br $block$3$break) + ) + ) + (block + (block + ) + ) + ) + ) + (func $before-and-after (type $3) (param $x i32) + (local $1 i32) + (block $block$2$break + (block + (call $before-and-after + (i32.const 1) + ) + (call $before-and-after + (i32.const 2) + ) + ) + (block + (br $block$2$break) + ) + ) + (block + (block $block$3$break + (block + (call $before-and-after + (i32.const 3) + ) + (call $before-and-after + (i32.const 4) + ) + ) + (if + (get_local $x) + (br $block$3$break) + (block + (block + (call $before-and-after + (i32.const 5) + ) + ) + (block + (br $block$3$break) + ) + ) + ) + ) + (block + (block $block$5$break + (block + (call $before-and-after + (i32.const 6) + ) + ) + (block + (br $block$5$break) + ) + ) + (block + (block $block$6$break + (block + (nop) + (call $before-and-after + (i32.const 7) + ) + ) + (block + (br $block$6$break) + ) + ) + (block + (block $block$7$break + (block + (nop) + (call $before-and-after + (i32.const 8) + ) + ) + (block + (br $block$7$break) + ) + ) + (block + (block $block$8$break + (loop $shape$7$continue + (block + (call $before-and-after + (i32.const 9) + ) + ) + (if + (get_local $x) + (br $shape$7$continue) + (br $block$8$break) + ) + ) + ) + (block + (block $block$10$break + (block + (call $before-and-after + (i32.const 10) + ) + (call $before-and-after + (i32.const 11) + ) + ) + (if + (get_local $x) + (block + (block + (call $before-and-after + (i32.const 12) + ) + ) + (block + (br $block$10$break) + ) + ) + (br $block$10$break) + ) + ) + (block + (block $block$13$break + (block + (call $before-and-after + (i32.const 13) + ) + ) + (if + (get_local $x) + (block + (block + (call $before-and-after + (i32.const 14) + ) + ) + (block + (br $block$13$break) + ) + ) + (block + (block + (call $before-and-after + (i32.const 15) + ) + ) + (block + (br $block$13$break) + ) + ) + ) + ) + (block + (block $block$16$break + (block + ) + (if + (get_local $x) + (block + (block $block$15$break + (block + (call $before-and-after + (i32.const 16) + ) + ) + (block + (br $block$15$break) + ) + ) + (block + (block + ) + (block + (br $block$16$break) + ) + ) + ) + (br $block$16$break) + ) + ) + (block + (block $block$18$break + (block + (call $before-and-after + (i32.const 17) + ) + (call $before-and-after + (i32.const 18) + ) + (call $before-and-after + (i32.const 19) + ) + ) + (block + (br $block$18$break) + ) + ) + (block + (block $block$17$break + (block + (call $before-and-after + (i32.const 20) + ) + ) + (block + (br $block$17$break) + ) + ) + (block + (block $block$20$break + (block + (call $before-and-after + (i32.const 21) + ) + (call $before-and-after + (i32.const 22) + ) + ) + (block + (br $block$20$break) + ) + ) + (block + (block $block$19$break + (block + ) + (block + (br $block$19$break) + ) + ) + (block + (block $block$22$break + (block + (call $before-and-after + (i32.const 23) + ) + (call $before-and-after + (i32.const 24) + ) + ) + (block + (br $block$22$break) + ) + ) + (block + (block $block$21$break + (block + ) + (block + (br $block$21$break) + ) + ) + (block + (block + (call $before-and-after + (i32.const 25) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + (func $switch (type $3) (param $x i32) + (local $1 i32) + (block $block$3$break + (block + ) + (block $switch$1$leave + (block $switch$1$default + (block $switch$1$case$3 + (br_table $switch$1$case$3 $switch$1$default + (get_local $x) + ) + ) + (block + (br $block$3$break) + ) + (br $switch$1$leave) + ) + (block + (block + (block + ) + (block + (br $block$3$break) + ) + ) + ) + (br $switch$1$leave) + ) + ) + (block + (block $block$6$break + (block + (call $switch + (i32.const 1) + ) + ) + (block $switch$3$leave + (block $switch$3$default + (block $switch$3$case$6 + (br_table $switch$3$case$6 $switch$3$case$6 $switch$3$case$6 $switch$3$default + (get_local $x) + ) + ) + (block + (br $block$6$break) + ) + (br $switch$3$leave) + ) + (block + (block + (block + (call $switch + (i32.const 2) + ) + ) + (block + (br $block$6$break) + ) + ) + ) + (br $switch$3$leave) + ) + ) + (block + (block $block$2$break + (block + (call $switch + (i32.const 3) + ) + ) + (block + (br $block$2$break) + ) + ) + (block + (block + ) + ) + ) + ) + ) + (func $no-return (type $0) + (local $0 i32) + (block $block$4$break + (block + ) + (if + (i32.const 1) + (block + (block + (drop + (i32.const 2) + ) + ) + (block + (br $block$4$break) + ) + ) + (block + (block + (drop + (i32.const 3) + ) + ) + (block + (br $block$4$break) + ) + ) + ) + ) + (block + (block + ) + ) + ) + (func $if-br-wat (type $3) (param $x i32) + (local $1 i32) + (block $block$2$break + (block $block$8$break + (block + (call $if-br-wat + (i32.const 0) + ) + ) + (if + (get_local $x) + (block + (block + (call $if-br-wat + (i32.const 1) + ) + ) + (block + (br $block$8$break) + ) + ) + (block + (block + ) + (if + (get_local $x) + (block + (block + ) + (block + (br $block$2$break) + ) + ) + (block + (block + ) + (block + (br $block$8$break) + ) + ) + ) + ) + ) + ) + (block + (block + (call $if-br-wat + (i32.const 2) + ) + ) + (block + (br $block$2$break) + ) + ) + ) + (block + (block + (call $if-br-wat + (i32.const 3) + ) + ) + ) + ) +) diff --git a/test/passes/rereloop.wast b/test/passes/rereloop.wast new file mode 100644 index 000000000..38c74ff56 --- /dev/null +++ b/test/passes/rereloop.wast @@ -0,0 +1,179 @@ +(module + (func $trivial + (nop) + ) + (func $trivial2 + (call $trivial) + (call $trivial) + ) + (func $return-void + (return) + ) + (func $return-val (result i32) + (return (i32.const 1)) + ) + (func $ifs (param $x i32) (result i32) + (if + (get_local $x) + (if + (get_local $x) + (return (i32.const 2)) + (return (i32.const 3)) + ) + ) + (if + (get_local $x) + (return (i32.const 4)) + ) + (return (i32.const 5)) + ) + (func $loops (param $x i32) + (if (get_local $x) + (loop $top + (call $trivial) + (br $top) + ) + ) + (loop $top2 + (call $trivial) + (br_if $top2 (get_local $x)) + ) + (loop $top3 + (call $trivial) + (if (get_local $x) (br $top3)) + ) + ) + (func $br-out (param $x i32) + (block $out + (call $br-out (i32.const 5)) + (br $out) + ) + ) + (func $unreachable (param $x i32) + (if (get_local $x) + (if (get_local $x) + (block + (call $unreachable (i32.const 1)) + (unreachable) + (call $unreachable (i32.const 2)) + ) + (block + (call $unreachable (i32.const 3)) + (return) + (call $unreachable (i32.const 4)) + ) + ) + ) + (block $out + (call $unreachable (i32.const 5)) + (br $out) + (call $unreachable (i32.const 6)) + ) + ) + (func $empty-blocks (param $x i32) + (block) + (block) + ) + (func $before-and-after (param $x i32) + (call $before-and-after (i32.const 1)) + (block + (call $before-and-after (i32.const 2)) + ) + (call $before-and-after (i32.const 3)) + (block $out + (call $before-and-after (i32.const 4)) + (br_if $out (get_local $x)) + (call $before-and-after (i32.const 5)) + ) + (call $before-and-after (i32.const 6)) + (loop) + (call $before-and-after (i32.const 7)) + (loop $top) + (call $before-and-after (i32.const 8)) + (loop $top2 + (call $before-and-after (i32.const 9)) + (br_if $top2 (get_local $x)) + (call $before-and-after (i32.const 10)) + ) + (call $before-and-after (i32.const 11)) + (if (get_local $x) + (call $before-and-after (i32.const 12)) + ) + (call $before-and-after (i32.const 13)) + (if (get_local $x) + (call $before-and-after (i32.const 14)) + (call $before-and-after (i32.const 15)) + ) + (if (get_local $x) + (block + (call $before-and-after (i32.const 16)) + ) + ) + (call $before-and-after (i32.const 17)) + (block + (call $before-and-after (i32.const 18)) + (block + (call $before-and-after (i32.const 19)) + ) + (call $before-and-after (i32.const 20)) + ) + (call $before-and-after (i32.const 21)) + (block + (block + (call $before-and-after (i32.const 22)) + ) + ) + (call $before-and-after (i32.const 23)) + (block $no1 + (block $no2 + (call $before-and-after (i32.const 24)) + ) + ) + (call $before-and-after (i32.const 25)) + ) + (func $switch (param $x i32) + (block $out + (block $a + (br_table $a $a (get_local $x)) + ) + (call $switch (i32.const 1)) + (block $b + (block $c + (br_table $b $b $b $c (get_local $x)) + ) + (call $switch (i32.const 2)) + ) + (call $switch (i32.const 3)) + ) + ) + (func $no-return + (if (i32.const 1) + (drop (i32.const 2)) + (drop (i32.const 3)) + ) + ) + (func $if-br-wat (param $x i32) + (call $if-br-wat + (i32.const 0) + ) + (block $label$2 + (if + (get_local $x) + (call $if-br-wat + (i32.const 1) + ) + (if + (get_local $x) + (br $label$2) ;; waka + ) + ) + (call $if-br-wat + (i32.const 2) + ) + ) + (call $if-br-wat + (i32.const 3) + ) + ) +) + diff --git a/test/passes/rereloop_dce_remove-unused-brs_remove-unused-names_simplify-locals-nostructure_vacuum_reorder-locals_coalesce-locals_simplify-locals_reorder-locals_merge-blocks_remove-unused-brs_merge-blocks_vacuum.txt b/test/passes/rereloop_dce_remove-unused-brs_remove-unused-names_simplify-locals-nostructure_vacuum_reorder-locals_coalesce-locals_simplify-locals_reorder-locals_merge-blocks_remove-unused-brs_merge-blocks_vacuum.txt new file mode 100644 index 000000000..5ed8e80c7 --- /dev/null +++ b/test/passes/rereloop_dce_remove-unused-brs_remove-unused-names_simplify-locals-nostructure_vacuum_reorder-locals_coalesce-locals_simplify-locals_reorder-locals_merge-blocks_remove-unused-brs_merge-blocks_vacuum.txt @@ -0,0 +1,234 @@ +(module + (type $0 (func)) + (type $1 (func (result i32))) + (type $2 (func (param i32) (result i32))) + (type $3 (func (param i32))) + (memory $0 0) + (func $trivial (type $0) + (nop) + ) + (func $trivial2 (type $0) + (call $trivial) + (call $trivial) + ) + (func $return-void (type $0) + (nop) + ) + (func $return-val (type $1) (result i32) + (i32.const 1) + ) + (func $ifs (type $2) (param $0 i32) (result i32) + (if i32 + (get_local $0) + (if i32 + (get_local $0) + (i32.const 2) + (i32.const 3) + ) + (if i32 + (get_local $0) + (i32.const 4) + (i32.const 5) + ) + ) + ) + (func $loops (type $3) (param $0 i32) + (if + (get_local $0) + (loop $shape$3$continue + (call $trivial) + (br $shape$3$continue) + ) + ) + (loop $shape$6$continue + (call $trivial) + (br_if $shape$6$continue + (get_local $0) + ) + ) + (block $block$11$break + (loop $shape$9$continue + (call $trivial) + (br_if $shape$9$continue + (i32.eqz + (i32.eqz + (get_local $0) + ) + ) + ) + ) + ) + ) + (func $br-out (type $3) (param $0 i32) + (call $br-out + (i32.const 5) + ) + ) + (func $unreachable (type $3) (param $0 i32) + (if + (i32.eqz + (get_local $0) + ) + (call $unreachable + (i32.const 5) + ) + ) + (if + (get_local $0) + (block + (call $unreachable + (i32.const 1) + ) + (unreachable) + ) + (call $unreachable + (i32.const 3) + ) + ) + ) + (func $empty-blocks (type $3) (param $0 i32) + (nop) + ) + (func $before-and-after (type $3) (param $0 i32) + (call $before-and-after + (i32.const 1) + ) + (call $before-and-after + (i32.const 2) + ) + (call $before-and-after + (i32.const 3) + ) + (call $before-and-after + (i32.const 4) + ) + (if + (i32.eqz + (get_local $0) + ) + (call $before-and-after + (i32.const 5) + ) + ) + (call $before-and-after + (i32.const 6) + ) + (call $before-and-after + (i32.const 7) + ) + (call $before-and-after + (i32.const 8) + ) + (loop $shape$7$continue + (call $before-and-after + (i32.const 9) + ) + (br_if $shape$7$continue + (get_local $0) + ) + ) + (call $before-and-after + (i32.const 10) + ) + (call $before-and-after + (i32.const 11) + ) + (if + (get_local $0) + (call $before-and-after + (i32.const 12) + ) + ) + (call $before-and-after + (i32.const 13) + ) + (if + (get_local $0) + (call $before-and-after + (i32.const 14) + ) + (call $before-and-after + (i32.const 15) + ) + ) + (if + (get_local $0) + (call $before-and-after + (i32.const 16) + ) + ) + (call $before-and-after + (i32.const 17) + ) + (call $before-and-after + (i32.const 18) + ) + (call $before-and-after + (i32.const 19) + ) + (call $before-and-after + (i32.const 20) + ) + (call $before-and-after + (i32.const 21) + ) + (call $before-and-after + (i32.const 22) + ) + (call $before-and-after + (i32.const 23) + ) + (call $before-and-after + (i32.const 24) + ) + (call $before-and-after + (i32.const 25) + ) + ) + (func $switch (type $3) (param $0 i32) + (block $block$6$break + (call $switch + (i32.const 1) + ) + (block $switch$3$default + (block $switch$3$case$6 + (br_table $switch$3$case$6 $switch$3$case$6 $switch$3$case$6 $switch$3$default + (get_local $0) + ) + ) + (br $block$6$break) + ) + (call $switch + (i32.const 2) + ) + ) + (call $switch + (i32.const 3) + ) + ) + (func $no-return (type $0) + (nop) + ) + (func $if-br-wat (type $3) (param $0 i32) + (block $block$2$break + (call $if-br-wat + (i32.const 0) + ) + (if + (get_local $0) + (call $if-br-wat + (i32.const 1) + ) + (br_if $block$2$break + (get_local $0) + ) + ) + (call $if-br-wat + (i32.const 2) + ) + ) + (call $if-br-wat + (i32.const 3) + ) + ) +) diff --git a/test/passes/rereloop_dce_remove-unused-brs_remove-unused-names_simplify-locals-nostructure_vacuum_reorder-locals_coalesce-locals_simplify-locals_reorder-locals_merge-blocks_remove-unused-brs_merge-blocks_vacuum.wast b/test/passes/rereloop_dce_remove-unused-brs_remove-unused-names_simplify-locals-nostructure_vacuum_reorder-locals_coalesce-locals_simplify-locals_reorder-locals_merge-blocks_remove-unused-brs_merge-blocks_vacuum.wast new file mode 100644 index 000000000..38c74ff56 --- /dev/null +++ b/test/passes/rereloop_dce_remove-unused-brs_remove-unused-names_simplify-locals-nostructure_vacuum_reorder-locals_coalesce-locals_simplify-locals_reorder-locals_merge-blocks_remove-unused-brs_merge-blocks_vacuum.wast @@ -0,0 +1,179 @@ +(module + (func $trivial + (nop) + ) + (func $trivial2 + (call $trivial) + (call $trivial) + ) + (func $return-void + (return) + ) + (func $return-val (result i32) + (return (i32.const 1)) + ) + (func $ifs (param $x i32) (result i32) + (if + (get_local $x) + (if + (get_local $x) + (return (i32.const 2)) + (return (i32.const 3)) + ) + ) + (if + (get_local $x) + (return (i32.const 4)) + ) + (return (i32.const 5)) + ) + (func $loops (param $x i32) + (if (get_local $x) + (loop $top + (call $trivial) + (br $top) + ) + ) + (loop $top2 + (call $trivial) + (br_if $top2 (get_local $x)) + ) + (loop $top3 + (call $trivial) + (if (get_local $x) (br $top3)) + ) + ) + (func $br-out (param $x i32) + (block $out + (call $br-out (i32.const 5)) + (br $out) + ) + ) + (func $unreachable (param $x i32) + (if (get_local $x) + (if (get_local $x) + (block + (call $unreachable (i32.const 1)) + (unreachable) + (call $unreachable (i32.const 2)) + ) + (block + (call $unreachable (i32.const 3)) + (return) + (call $unreachable (i32.const 4)) + ) + ) + ) + (block $out + (call $unreachable (i32.const 5)) + (br $out) + (call $unreachable (i32.const 6)) + ) + ) + (func $empty-blocks (param $x i32) + (block) + (block) + ) + (func $before-and-after (param $x i32) + (call $before-and-after (i32.const 1)) + (block + (call $before-and-after (i32.const 2)) + ) + (call $before-and-after (i32.const 3)) + (block $out + (call $before-and-after (i32.const 4)) + (br_if $out (get_local $x)) + (call $before-and-after (i32.const 5)) + ) + (call $before-and-after (i32.const 6)) + (loop) + (call $before-and-after (i32.const 7)) + (loop $top) + (call $before-and-after (i32.const 8)) + (loop $top2 + (call $before-and-after (i32.const 9)) + (br_if $top2 (get_local $x)) + (call $before-and-after (i32.const 10)) + ) + (call $before-and-after (i32.const 11)) + (if (get_local $x) + (call $before-and-after (i32.const 12)) + ) + (call $before-and-after (i32.const 13)) + (if (get_local $x) + (call $before-and-after (i32.const 14)) + (call $before-and-after (i32.const 15)) + ) + (if (get_local $x) + (block + (call $before-and-after (i32.const 16)) + ) + ) + (call $before-and-after (i32.const 17)) + (block + (call $before-and-after (i32.const 18)) + (block + (call $before-and-after (i32.const 19)) + ) + (call $before-and-after (i32.const 20)) + ) + (call $before-and-after (i32.const 21)) + (block + (block + (call $before-and-after (i32.const 22)) + ) + ) + (call $before-and-after (i32.const 23)) + (block $no1 + (block $no2 + (call $before-and-after (i32.const 24)) + ) + ) + (call $before-and-after (i32.const 25)) + ) + (func $switch (param $x i32) + (block $out + (block $a + (br_table $a $a (get_local $x)) + ) + (call $switch (i32.const 1)) + (block $b + (block $c + (br_table $b $b $b $c (get_local $x)) + ) + (call $switch (i32.const 2)) + ) + (call $switch (i32.const 3)) + ) + ) + (func $no-return + (if (i32.const 1) + (drop (i32.const 2)) + (drop (i32.const 3)) + ) + ) + (func $if-br-wat (param $x i32) + (call $if-br-wat + (i32.const 0) + ) + (block $label$2 + (if + (get_local $x) + (call $if-br-wat + (i32.const 1) + ) + (if + (get_local $x) + (br $label$2) ;; waka + ) + ) + (call $if-br-wat + (i32.const 2) + ) + ) + (call $if-br-wat + (i32.const 3) + ) + ) +) + |