From 59a4bb90b9214f66df0854979c5bf6a180b286e7 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Sun, 10 Apr 2016 19:33:56 -0700 Subject: remove set_locals with no remaining gets in SimplifyLocals --- src/passes/SimplifyLocals.cpp | 55 +++++++++++++++++++++++++++++++++++++++---- 1 file changed, 51 insertions(+), 4 deletions(-) (limited to 'src/passes/SimplifyLocals.cpp') diff --git a/src/passes/SimplifyLocals.cpp b/src/passes/SimplifyLocals.cpp index 53e77eb22..cba4979a4 100644 --- a/src/passes/SimplifyLocals.cpp +++ b/src/passes/SimplifyLocals.cpp @@ -17,7 +17,9 @@ // // Locals-related optimizations // -// This "sinks" set_locals, pushing them to the next get_local where possible +// This "sinks" set_locals, pushing them to the next get_local where possible, +// and removing the set if there are no gets remaining (the latter is +// particularly useful in ssa mode, but not only). #include #include @@ -39,6 +41,12 @@ struct SimplifyLocals : public WalkerPass> // locals in current linear execution trace, which we try to sink std::map sinkables; + // name => # of get_locals for it + std::map numGetLocals; + + // for each set_local, its origin pointer + std::map setLocalOrigins; + void noteNonLinear() { sinkables.clear(); } @@ -52,6 +60,8 @@ struct SimplifyLocals : public WalkerPass> *found->second.item = curr; ExpressionManipulator::nop(curr); sinkables.erase(found); + } else { + numGetLocals[curr->name]++; } } @@ -79,17 +89,28 @@ struct SimplifyLocals : public WalkerPass> } static void visitPre(SimplifyLocals* self, Expression** currp) { + Expression* curr = *currp; + EffectAnalyzer effects; - if (effects.checkPre(*currp)) { + if (effects.checkPre(curr)) { self->checkInvalidations(effects); } } static void visitPost(SimplifyLocals* self, Expression** currp) { + Expression* curr = *currp; + EffectAnalyzer effects; - if (effects.checkPost(*currp)) { + if (effects.checkPost(curr)) { self->checkInvalidations(effects); } + + // noting origins in the post means it happens after a + // get_local was replaced by a set_local in a sinking + // operation, so we track those movements properly. + if (curr->is()) { + self->setLocalOrigins[curr->cast()] = currp; + } } static void tryMarkSinkable(SimplifyLocals* self, Expression** currp) { @@ -107,7 +128,6 @@ struct SimplifyLocals : public WalkerPass> auto* curr = *currp; - if (curr->is()) { // special-case blocks, by marking their children as locals. // TODO sink from elsewhere? (need to make sure value is not used) @@ -129,6 +149,33 @@ struct SimplifyLocals : public WalkerPass> self->pushTask(visitPre, currp); } + + void visitFunction(Function *curr) { + // after optimizing a function, we can see if we have set_locals + // for a local with no remaining gets, in which case, we can + // remove the set. + std::vector optimizables; + for (auto pair : setLocalOrigins) { + SetLocal* curr = pair.first; + if (numGetLocals[curr->name] == 0) { + // no gets, can remove the set and leave just the value + optimizables.push_back(curr); + } + } + for (auto* curr : optimizables) { + Expression** origin = setLocalOrigins[curr]; + *origin = curr->value; + // nested set_values need to be handled properly. + // consider (set_local x (set_local y (..)), where both can be + // reduced to their values, and we might do it in either + // order. + if (curr->value->is()) { + setLocalOrigins[curr->value->cast()] = origin; + } + } + numGetLocals.clear(); + setLocalOrigins.clear(); + } }; static RegisterPass registerPass("simplify-locals", "miscellaneous locals-related optimizations"); -- cgit v1.2.3 From 1044d6cbca6d279d457cdd1cf7000671ec48e841 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Mon, 11 Apr 2016 17:31:10 -0700 Subject: dyn_cast => dynCast --- src/asm2wasm.h | 4 ++-- src/binaryen-shell.cpp | 4 ++-- src/passes/MergeBlocks.cpp | 2 +- src/passes/OptimizeInstructions.cpp | 4 ++-- src/passes/PostEmscripten.cpp | 6 +++--- src/passes/Print.cpp | 10 +++++----- src/passes/RemoveUnusedBrs.cpp | 10 +++++----- src/passes/SimplifyLocals.cpp | 2 +- src/s2wasm.h | 2 +- src/wasm-s-parser.h | 2 +- src/wasm.h | 2 +- test/example/find_div0s.cpp | 2 +- 12 files changed, 25 insertions(+), 25 deletions(-) (limited to 'src/passes/SimplifyLocals.cpp') diff --git a/src/asm2wasm.h b/src/asm2wasm.h index 72a8b9048..a5a76b396 100644 --- a/src/asm2wasm.h +++ b/src/asm2wasm.h @@ -433,7 +433,7 @@ private: // ensure a nameless block Block* blockify(Expression* expression) { - if (expression->is() && !expression->cast()->name.is()) return expression->dyn_cast(); + if (expression->is() && !expression->cast()->name.is()) return expression->dynCast(); auto ret = allocator.alloc(); ret->list.push_back(expression); ret->finalize(); @@ -1351,7 +1351,7 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) { auto ret = processStatements(ast[1], 0); if (name.is()) { breakStack.pop_back(); - Block* block = ret->dyn_cast(); + Block* block = ret->dynCast(); if (block && block->name.isNull()) { block->name = name; } else { diff --git a/src/binaryen-shell.cpp b/src/binaryen-shell.cpp index 7f5b3077e..dd0f0eeca 100644 --- a/src/binaryen-shell.cpp +++ b/src/binaryen-shell.cpp @@ -52,7 +52,7 @@ struct Invocation { name = invoke[1]->str(); for (size_t j = 2; j < invoke.size(); j++) { Expression* argument = builder.parseExpression(*invoke[j]); - arguments.push_back(argument->dyn_cast()->value); + arguments.push_back(argument->dynCast()->value); } } @@ -150,7 +150,7 @@ static void run_asserts(size_t* i, bool* checked, AllocatingModule* wasm, if (curr.size() >= 3) { Literal expected = builder->get() ->parseExpression(*curr[2]) - ->dyn_cast() + ->dynCast() ->value; std::cerr << "seen " << result << ", expected " << expected << '\n'; verify_result(expected, result); diff --git a/src/passes/MergeBlocks.cpp b/src/passes/MergeBlocks.cpp index ab210123c..578d4fc45 100644 --- a/src/passes/MergeBlocks.cpp +++ b/src/passes/MergeBlocks.cpp @@ -29,7 +29,7 @@ struct MergeBlocks : public WalkerPass> { while (more) { more = false; for (size_t i = 0; i < curr->list.size(); i++) { - Block* child = curr->list[i]->dyn_cast(); + Block* child = curr->list[i]->dynCast(); if (!child) continue; if (child->name.is()) continue; // named blocks can have breaks to them (and certainly do, if we ran RemoveUnusedNames and RemoveUnusedBrs) ExpressionList merged; diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 3d89d7af4..ca79468f5 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -29,7 +29,7 @@ struct OptimizeInstructions : public WalkerPass void visitIf(If* curr) { // flip branches to get rid of an i32.eqz if (curr->ifFalse) { - auto condition = curr->condition->dyn_cast(); + auto condition = curr->condition->dynCast(); if (condition && condition->op == EqZ && condition->value->type == i32) { curr->condition = condition->value; std::swap(curr->ifTrue, curr->ifFalse); @@ -39,7 +39,7 @@ struct OptimizeInstructions : public WalkerPass void visitUnary(Unary* curr) { if (curr->op == EqZ) { // fold comparisons that flow into an EqZ - auto* child = curr->value->dyn_cast(); + auto* child = curr->value->dynCast(); if (child && (child->type == i32 || child->type == i64)) { switch (child->op) { case Eq: child->op = Ne; break; diff --git a/src/passes/PostEmscripten.cpp b/src/passes/PostEmscripten.cpp index 99b172d65..effbad30a 100644 --- a/src/passes/PostEmscripten.cpp +++ b/src/passes/PostEmscripten.cpp @@ -44,12 +44,12 @@ struct PostEmscripten : public WalkerPass> { void visitMemoryOp(T *curr) { if (curr->offset) return; Expression* ptr = curr->ptr; - auto add = ptr->dyn_cast(); + auto add = ptr->dynCast(); if (!add || add->op != Add) return; assert(add->type == i32); - auto c = add->right->dyn_cast(); + auto c = add->right->dynCast(); if (!c) { - c = add->left->dyn_cast(); + c = add->left->dynCast(); if (c) { // if one is a const, it's ok to swap add->left = add->right; diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp index 7b68d956e..ce974c5f0 100644 --- a/src/passes/Print.cpp +++ b/src/passes/Print.cpp @@ -105,14 +105,14 @@ struct PrintSExpression : public Visitor { incIndent(); printFullLine(curr->condition); // ifTrue and False have implict blocks, avoid printing them if possible - if (!fullAST && curr->ifTrue->is() && curr->ifTrue->dyn_cast()->name.isNull() && curr->ifTrue->dyn_cast()->list.size() == 1) { - printFullLine(curr->ifTrue->dyn_cast()->list.back()); + if (!fullAST && curr->ifTrue->is() && curr->ifTrue->dynCast()->name.isNull() && curr->ifTrue->dynCast()->list.size() == 1) { + printFullLine(curr->ifTrue->dynCast()->list.back()); } else { printFullLine(curr->ifTrue); } if (curr->ifFalse) { - if (!fullAST && curr->ifFalse->is() && curr->ifFalse->dyn_cast()->name.isNull() && curr->ifFalse->dyn_cast()->list.size() == 1) { - printFullLine(curr->ifFalse->dyn_cast()->list.back()); + if (!fullAST && curr->ifFalse->is() && curr->ifFalse->dynCast()->name.isNull() && curr->ifFalse->dynCast()->list.size() == 1) { + printFullLine(curr->ifFalse->dynCast()->list.back()); } else { printFullLine(curr->ifFalse); } @@ -129,7 +129,7 @@ struct PrintSExpression : public Visitor { o << ' ' << curr->in; } incIndent(); - auto block = curr->body->dyn_cast(); + auto block = curr->body->dynCast(); if (!fullAST && block && block->name.isNull()) { // wasm spec has loops containing children directly, while our ast // has a single child for simplicity. print out the optimal form. diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp index 998142724..41db36d2c 100644 --- a/src/passes/RemoveUnusedBrs.cpp +++ b/src/passes/RemoveUnusedBrs.cpp @@ -30,7 +30,7 @@ struct RemoveUnusedBrs : public WalkerPass> { void visitIf(If* curr) { if (!curr->ifFalse) { // try to reduce an if (condition) br => br_if (condition) , which might open up other optimization opportunities - Break* br = curr->ifTrue->dyn_cast(); + Break* br = curr->ifTrue->dynCast(); if (br && !br->condition) { // TODO: if there is a condition, join them br->condition = curr->condition; replaceCurrent(br); @@ -40,7 +40,7 @@ struct RemoveUnusedBrs : public WalkerPass> { 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->dyn_cast(); + Block* b = side->dynCast(); if (!b) return nullptr; if (b->list.size() == 0) return nullptr; return b->list.back(); @@ -49,7 +49,7 @@ struct RemoveUnusedBrs : public WalkerPass> { Expression* last = getLast(side); if (!last) return Name(); Block* b = side->cast(); - Break* br = last->dyn_cast(); + Break* br = last->dynCast(); if (!br) return Name(); if (br->condition) return Name(); if (!br->value) return Name(); @@ -76,14 +76,14 @@ struct RemoveUnusedBrs : public WalkerPass> { 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]->dyn_cast(); + 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->dyn_cast()) { + if (Break* br = last->dynCast()) { if (br->condition) return; if (br->name == curr->name) { if (!br->value) { diff --git a/src/passes/SimplifyLocals.cpp b/src/passes/SimplifyLocals.cpp index cba4979a4..77e4f788a 100644 --- a/src/passes/SimplifyLocals.cpp +++ b/src/passes/SimplifyLocals.cpp @@ -114,7 +114,7 @@ struct SimplifyLocals : public WalkerPass> } static void tryMarkSinkable(SimplifyLocals* self, Expression** currp) { - auto* curr = (*currp)->dyn_cast(); + auto* curr = (*currp)->dynCast(); if (curr) { Name name = curr->name; assert(self->sinkables.count(name) == 0); diff --git a/src/s2wasm.h b/src/s2wasm.h index 9d166624c..9bdc4961d 100644 --- a/src/s2wasm.h +++ b/src/s2wasm.h @@ -1086,7 +1086,7 @@ class S2WasmBuilder { for (auto block : loopBlocks) { block->name = Name(); } - func->body->dyn_cast()->finalize(); + func->body->dynCast()->finalize(); wasm.addFunction(func); } diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h index 0d2ecd570..40f2a41a0 100644 --- a/src/wasm-s-parser.h +++ b/src/wasm-s-parser.h @@ -897,7 +897,7 @@ private: auto* ret = parseExpression(&s); labelStack.pop_back(); if (explicitThenElse) { - ret->dyn_cast()->name = name; + ret->dynCast()->name = name; } else { // add a block if we must if (BreakSeeker::has(ret, name)) { diff --git a/src/wasm.h b/src/wasm.h index c9494d4d6..2b04ed8cd 100644 --- a/src/wasm.h +++ b/src/wasm.h @@ -758,7 +758,7 @@ public: } template - T* dyn_cast() { + T* dynCast() { return _id == T()._id ? (T*)this : nullptr; } diff --git a/test/example/find_div0s.cpp b/test/example/find_div0s.cpp index 9f1cf911f..14eac95bb 100644 --- a/test/example/find_div0s.cpp +++ b/test/example/find_div0s.cpp @@ -44,7 +44,7 @@ int main() { // In every Binary, look for integer divisions if (curr->op == BinaryOp::DivS || curr->op == BinaryOp::DivU) { // Check if the right operand is a constant, and if it is 0 - auto right = curr->right->dyn_cast(); + auto right = curr->right->dynCast(); if (right && right->value.getInteger() == 0) { std::cout << "We found that " << curr->left << " is divided by zero\n"; } -- cgit v1.2.3