summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/cfg/CMakeLists.txt4
-rw-r--r--src/cfg/Relooper.cpp1
-rw-r--r--src/pass.h9
-rw-r--r--src/passes/CMakeLists.txt1
-rw-r--r--src/passes/ReReloop.cpp325
-rw-r--r--src/passes/pass.cpp15
-rw-r--r--src/passes/passes.h1
7 files changed, 342 insertions, 14 deletions
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();
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-07 17:28:32 +0000