From 9f1849ef99db9fa8a8a44daec348b7f2bb562453 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Sat, 23 Apr 2016 20:00:39 -0700 Subject: handle general control flow in RemoveUnusedBrs --- src/passes/RemoveUnusedBrs.cpp | 148 +++++++++++++++++++++++++---------------- 1 file changed, 89 insertions(+), 59 deletions(-) (limited to 'src/passes/RemoveUnusedBrs.cpp') diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp index cfd9ea7ce..255d86b9c 100644 --- a/src/passes/RemoveUnusedBrs.cpp +++ b/src/passes/RemoveUnusedBrs.cpp @@ -15,89 +15,119 @@ */ // -// Removes branches that go to where they go anyhow +// Removes branches for which we go to where they go anyhow // #include #include +#include namespace wasm { struct RemoveUnusedBrs : public WalkerPass>> { bool isFunctionParallel() { return true; } - // preparation: try to unify branches, as the fewer there are, the higher a chance we can remove them - // specifically for if-else, turn an if-else with branches to the same target at the end of each - // child, and with a value, to a branch to that target containing the if-else + typedef std::vector Flows; + + // list of breaks that are currently flowing. if they reach their target without + // interference, they can be removed (or their value forwarded TODO) + Flows flows; + + // a stack for if-else contents, we merge their outputs + std::vector ifStack; + + static void visitAny(RemoveUnusedBrs* self, Expression** currp) { + auto* curr = *currp; + auto& flows = self->flows; + + if (curr->is()) { + flows.clear(); + auto* br = curr->cast(); + if (!br->condition && !br->value) { // TODO: optimize in those cases? + // a break, let's see where it flows to + flows.push_back(br); + } + } else if (curr->is()) { + flows.clear(); + } else if (curr->is()) { + auto* iff = curr->cast(); + if (iff->ifFalse) { + assert(self->ifStack.size() > 0); + for (auto* flow : self->ifStack.back()) { + flows.push_back(flow); + } + self->ifStack.pop_back(); + } + } else if (curr->is()) { + // any breaks flowing to here are unnecessary, as we get here anyhow + auto name = curr->cast()->name; + if (name.is()) { + size_t size = flows.size(); + size_t skip = 0; + for (size_t i = 0; i < size; i++) { + if (flows[i]->name == name) { + ExpressionManipulator::nop(flows[i]); + skip++; + } else if (skip > 0) { + flows[i - skip] = flows[i]; + } + } + if (skip > 0) { + flows.resize(size - skip); + } + } + } else if (curr->is()) { + // TODO we might optimize branches out of here + flows.clear(); + } else { + // anything else stops the flow + flows.clear(); + } + } + + static void clear(RemoveUnusedBrs* self, Expression** currp) { + self->flows.clear(); + } + + static void saveIfTrue(RemoveUnusedBrs* self, Expression** currp) { + self->ifStack.push_back(std::move(self->flows)); + } + void visitIf(If* curr) { if (!curr->ifFalse) { - // try to reduce an if (condition) br => br_if (condition) , which might open up other optimization opportunities + // if without an else. try to reduce if (condition) br => br_if (condition) Break* br = curr->ifTrue->dynCast(); if (br && !br->condition) { // TODO: if there is a condition, join them br->condition = curr->condition; replaceCurrent(br); } - return; - } - if (isConcreteWasmType(curr->type)) return; // already has a returned value - // an if_else that indirectly returns a value by breaking to the same target can potentially remove both breaks, and break outside once - auto getLast = [](Expression *side) -> Expression* { - Block* b = side->dynCast(); - if (!b) return nullptr; - if (b->list.size() == 0) return nullptr; - return b->list.back(); - }; - auto process = [&](Expression *side, bool doIt) { - Expression* last = getLast(side); - if (!last) return Name(); - Block* b = side->cast(); - Break* br = last->dynCast(); - if (!br) return Name(); - if (br->condition) return Name(); - if (!br->value) return Name(); - if (doIt) { - b->list[b->list.size()-1] = br->value; - } - return br->name; - }; - // do both, or none - if (process(curr->ifTrue, false).is() && process(curr->ifTrue, false) == process(curr->ifFalse, false)) { - auto br = getLast(curr->ifTrue)->cast(); // we are about to discard this, so why not reuse it! - process(curr->ifTrue, true); - process(curr->ifFalse, true); - curr->type = br->value->type; // if_else now returns a value - br->value = curr; - // no need to change anything else in the br - target is correct already - replaceCurrent(br); } } - // main portion - void visitBlock(Block *curr) { - if (curr->name.isNull()) return; - if (curr->list.size() == 0) return; - // preparation - remove all code after an unconditional break, since it can't execute, and it might confuse us (we look at the last) - for (size_t i = 0; i < curr->list.size()-1; i++) { - Break* br = curr->list[i]->dynCast(); - if (br && !br->condition) { - curr->list.resize(i+1); - break; - } - } - Expression* last = curr->list.back(); - if (Break* br = last->dynCast()) { - if (br->condition) return; - if (br->name == curr->name) { - if (!br->value) { - curr->list.pop_back(); - } else { - curr->list[curr->list.size()-1] = br->value; // can replace with the value - } + // override scan to add a pre and a post check task to all nodes + static void scan(RemoveUnusedBrs* self, Expression** currp) { + self->pushTask(visitAny, currp); + + auto* iff = (*currp)->dynCast(); + + if (iff) { + self->pushTask(doVisitIf, currp); + if (iff->ifFalse) { + // we need to join up if-else control flow, and clear after the condition + self->pushTask(scan, &iff->ifFalse); + self->pushTask(saveIfTrue, currp); // safe the ifTrue flow, we'll join it later } + self->pushTask(scan, &iff->ifTrue); + self->pushTask(clear, currp); // clear all flow after the condition + self->pushTask(scan, &iff->condition); + } else { + WalkerPass>>::scan(self, currp); } } + + // TODO: multiple rounds? }; -static RegisterPass registerPass("remove-unused-brs", "removes breaks from locations that are never branched to"); +static RegisterPass registerPass("remove-unused-brs", "removes breaks from locations that are not needed"); } // namespace wasm -- cgit v1.2.3 From 186765307f12e6c7628ad6da11b332c2bfbcaa07 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Sat, 23 Apr 2016 21:50:20 -0700 Subject: run multiple cycles of RemoveUnusedBrs --- src/passes/RemoveUnusedBrs.cpp | 16 +++++++++++++++- test/emcc_hello_world.fromasm | 1 - test/emcc_hello_world.fromasm.imprecise | 1 - test/passes/remove-unused-brs.txt | 8 ++++---- 4 files changed, 19 insertions(+), 7 deletions(-) (limited to 'src/passes/RemoveUnusedBrs.cpp') diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp index 255d86b9c..3d6d6973f 100644 --- a/src/passes/RemoveUnusedBrs.cpp +++ b/src/passes/RemoveUnusedBrs.cpp @@ -27,6 +27,8 @@ namespace wasm { struct RemoveUnusedBrs : public WalkerPass>> { bool isFunctionParallel() { return true; } + bool anotherCycle; + typedef std::vector Flows; // list of breaks that are currently flowing. if they reach their target without @@ -68,6 +70,7 @@ struct RemoveUnusedBrs : public WalkerPassname == name) { ExpressionManipulator::nop(flows[i]); skip++; + self->anotherCycle = true; } else if (skip > 0) { flows[i - skip] = flows[i]; } @@ -79,6 +82,8 @@ struct RemoveUnusedBrs : public WalkerPassis()) { // TODO we might optimize branches out of here flows.clear(); + } else if (curr->is()) { + // ignore (could be result of a previous cycle) } else { // anything else stops the flow flows.clear(); @@ -100,6 +105,7 @@ struct RemoveUnusedBrs : public WalkerPasscondition) { // TODO: if there is a condition, join them br->condition = curr->condition; replaceCurrent(br); + anotherCycle = true; } } } @@ -125,7 +131,15 @@ struct RemoveUnusedBrs : public WalkerPass>>::walk(root); + assert(ifStack.empty()); + assert(flows.empty()); + } while (anotherCycle); + } }; static RegisterPass registerPass("remove-unused-brs", "removes breaks from locations that are not needed"); diff --git a/test/emcc_hello_world.fromasm b/test/emcc_hello_world.fromasm index 9d50d32b2..75e2bf024 100644 --- a/test/emcc_hello_world.fromasm +++ b/test/emcc_hello_world.fromasm @@ -10864,7 +10864,6 @@ (get_local $$arg) (get_local $$110) ) - (br $label$break$L1) ) ) ) diff --git a/test/emcc_hello_world.fromasm.imprecise b/test/emcc_hello_world.fromasm.imprecise index b303c5cac..4ada9b367 100644 --- a/test/emcc_hello_world.fromasm.imprecise +++ b/test/emcc_hello_world.fromasm.imprecise @@ -10862,7 +10862,6 @@ (get_local $$arg) (get_local $$110) ) - (br $label$break$L1) ) ) ) diff --git a/test/passes/remove-unused-brs.txt b/test/passes/remove-unused-brs.txt index 2404e7b39..226065f3f 100644 --- a/test/passes/remove-unused-brs.txt +++ b/test/passes/remove-unused-brs.txt @@ -169,9 +169,9 @@ (block $a (block $b (block $c - (br $a) + (nop) ) - (br $a) + (nop) ) (nop) ) @@ -187,9 +187,9 @@ (block $a (block $b (block $c - (br $b) + (nop) ) - (br $a) + (nop) ) (nop) ) -- cgit v1.2.3