From e6048c1dabde9e511d25c8bd6d2da68461807f74 Mon Sep 17 00:00:00 2001 From: "Alon Zakai (kripken)" Date: Sat, 1 Dec 2018 18:28:52 -0800 Subject: Speculate in simplify-locals that it is worth turning an if into an if-else. If an if sets a local, (if (..condition..) (set_local $x (..value..)) ) we can turn it into (set_local $x (if (..condition..) (..value..) (get_local $x) ) ) This increases code size and adds a branch in the if, but allows the set to be optimized into a tee or optimized out entirely. In the worst case, other optimizations can break up an if with a copy in one of its arms later. Includes a determinism fix for EquivalentSets, which this patch triggered. --- src/ir/equivalent_sets.h | 4 +- src/passes/SimplifyLocals.cpp | 122 ++++++++++++++++++++++++++++++++---------- 2 files changed, 97 insertions(+), 29 deletions(-) (limited to 'src') diff --git a/src/ir/equivalent_sets.h b/src/ir/equivalent_sets.h index d1a957bbd..dc3e348d2 100644 --- a/src/ir/equivalent_sets.h +++ b/src/ir/equivalent_sets.h @@ -25,8 +25,8 @@ namespace wasm { // A map of each index to all those it is equivalent to, and some helpers. // struct EquivalentSets { - // A set of indexes. - typedef std::unordered_set Set; + // A set of indexes. This is ordered for deterministic iteration. + typedef std::set Set; std::unordered_map> indexSets; diff --git a/src/passes/SimplifyLocals.cpp b/src/passes/SimplifyLocals.cpp index bf4eed24e..f3645c1f3 100644 --- a/src/passes/SimplifyLocals.cpp +++ b/src/passes/SimplifyLocals.cpp @@ -126,7 +126,7 @@ struct SimplifyLocals : public WalkerPassis()) { return; // handled in visitBlock } else if (curr->is()) { - assert(!curr->cast()->ifFalse); // if-elses are handled by doNoteIfElse* methods + assert(!curr->cast()->ifFalse); // if-elses are handled by doNoteIf* methods } else if (curr->is()) { auto* sw = curr->cast(); auto targets = BranchUtils::getUniqueTargets(sw); @@ -138,26 +138,34 @@ struct SimplifyLocals : public WalkerPasssinkables.clear(); } - static void doNoteIfElseCondition(SimplifyLocals* self, Expression** currp) { + static void doNoteIfCondition(SimplifyLocals* self, Expression** currp) { // we processed the condition of this if-else, and now control flow branches // into either the true or the false sides - assert((*currp)->cast()->ifFalse); self->sinkables.clear(); } - static void doNoteIfElseTrue(SimplifyLocals* self, Expression** currp) { - // we processed the ifTrue side of this if-else, save it on the stack - assert((*currp)->cast()->ifFalse); - self->ifStack.push_back(std::move(self->sinkables)); + static void doNoteIfTrue(SimplifyLocals* self, Expression** currp) { + auto* iff = (*currp)->dynCast(); + if (iff->ifFalse) { + // We processed the ifTrue side of this if-else, save it on the stack. + assert((*currp)->cast()->ifFalse); + self->ifStack.push_back(std::move(self->sinkables)); + } else { + // This is an if without an else. + if (allowStructure) { + self->optimizeIfReturn(iff, currp); + } + self->sinkables.clear(); + } } - static void doNoteIfElseFalse(SimplifyLocals* self, Expression** currp) { + static void doNoteIfFalse(SimplifyLocals* self, Expression** currp) { // we processed the ifFalse side of this if-else, we can now try to // mere with the ifTrue side and optimize a return value, if possible auto* iff = (*currp)->cast(); assert(iff->ifFalse); if (allowStructure) { - self->optimizeIfReturn(iff, currp, self->ifStack.back()); + self->optimizeIfElseReturn(iff, currp, self->ifStack.back()); } self->ifStack.pop_back(); self->sinkables.clear(); @@ -444,7 +452,7 @@ struct SimplifyLocals : public WalkerPassifFalse); // if this if already has a result, or is unreachable code, we have // nothing to do @@ -497,14 +505,14 @@ struct SimplifyLocals : public WalkerPassifTrue->dynCast(); if (iff->ifTrue->type != unreachable) { - if (!ifTrueBlock || ifTrueBlock->list.size() == 0 || !ifTrueBlock->list.back()->is()) { + if (!ifTrueBlock || ifTrueBlock->name.is() || ifTrueBlock->list.size() == 0 || !ifTrueBlock->list.back()->is()) { ifsToEnlarge.push_back(iff); return; } } auto* ifFalseBlock = iff->ifFalse->dynCast(); if (iff->ifFalse->type != unreachable) { - if (!ifFalseBlock || ifFalseBlock->list.size() == 0 || !ifFalseBlock->list.back()->is()) { + if (!ifFalseBlock || ifFalseBlock->name.is() || ifFalseBlock->list.size() == 0 || !ifFalseBlock->list.back()->is()) { ifsToEnlarge.push_back(iff); return; } @@ -532,20 +540,78 @@ struct SimplifyLocals : public WalkerPass + // (set_local $x + // (if (result ..) + // (..condition..) + // (block (result ..) + // (..value..) + // ) + // (get_local $x) + // ) + // ) + // This is a speculative optimization: we add a get here, as well as a branch + // in the if, so this is harmful for code size and for speed. However, later + // optimizations may sink the set and enable other useful things. If none of + // that happens, other passes can "undo" this by turning an if with a copy + // arm into a one-sided if. + void optimizeIfReturn(If* iff, Expression** currp) { + // If this if is unreachable code, we have nothing to do. + if (iff->type != none || iff->ifTrue->type != none) return; + // Anything sinkable is good for us. + if (sinkables.empty()) return; + Index goodIndex = sinkables.begin()->first; + // Ensure we have a place to write the return values for, if not, we + // need another cycle. + auto* ifTrueBlock = iff->ifTrue->dynCast(); + if (!ifTrueBlock || ifTrueBlock->name.is() || ifTrueBlock->list.size() == 0 || !ifTrueBlock->list.back()->is()) { + ifsToEnlarge.push_back(iff); + return; + } + // Update the ifTrue side. + Builder builder(*this->getModule()); + auto** item = sinkables.at(goodIndex).item; + auto* set = (*item)->template cast(); + ifTrueBlock->list[ifTrueBlock->list.size() - 1] = set->value; + *item = builder.makeNop(); + ifTrueBlock->finalize(); + assert(ifTrueBlock->type != none); + // Update the ifFalse side. + iff->ifFalse = builder.makeGetLocal(set->index, set->value->type); + iff->finalize(); // update type + // Update the get count. + getCounter.num[set->index]++; + assert(iff->type != none); + // Finally, reuse the set_local on the iff itself. + set->value = iff; + set->finalize(); + *currp = set; + anotherCycle = true; + } + // override scan to add a pre and a post check task to all nodes static void scan(SimplifyLocals* self, Expression** currp) { self->pushTask(visitPost, currp); auto* curr = *currp; - if (curr->is() && curr->cast()->ifFalse) { - // handle if-elses in a special manner, using the ifStack - self->pushTask(SimplifyLocals::doNoteIfElseFalse, currp); - self->pushTask(SimplifyLocals::scan, &curr->cast()->ifFalse); - self->pushTask(SimplifyLocals::doNoteIfElseTrue, currp); - self->pushTask(SimplifyLocals::scan, &curr->cast()->ifTrue); - self->pushTask(SimplifyLocals::doNoteIfElseCondition, currp); - self->pushTask(SimplifyLocals::scan, &curr->cast()->condition); + if (auto* iff = curr->dynCast()) { + // handle if in a special manner, using the ifStack for if-elses etc. + if (iff->ifFalse) { + self->pushTask(SimplifyLocals::doNoteIfFalse, currp); + self->pushTask(SimplifyLocals::scan, &iff->ifFalse); + } + self->pushTask(SimplifyLocals::doNoteIfTrue, currp); + self->pushTask(SimplifyLocals::scan, &iff->ifTrue); + self->pushTask(SimplifyLocals::doNoteIfCondition, currp); + self->pushTask(SimplifyLocals::scan, &iff->condition); } else { WalkerPass>>::scan(self, currp); } @@ -582,7 +648,7 @@ struct SimplifyLocals : public WalkerPass 0) { for (auto* iff : ifsToEnlarge) { - auto ifTrue = Builder(*this->getModule()).blockify(iff->ifTrue); + auto ifTrue = Builder(*this->getModule()).blockifyWithName(iff->ifTrue, Name()); iff->ifTrue = ifTrue; if (ifTrue->list.size() == 0 || !ifTrue->list.back()->template is()) { ifTrue->list.push_back(this->getModule()->allocator.template alloc()); } - auto ifFalse = Builder(*this->getModule()).blockify(iff->ifFalse); - iff->ifFalse = ifFalse; - if (ifFalse->list.size() == 0 || !ifFalse->list.back()->template is()) { - ifFalse->list.push_back(this->getModule()->allocator.template alloc()); + if (iff->ifFalse) { + auto ifFalse = Builder(*this->getModule()).blockifyWithName(iff->ifFalse, Name()); + iff->ifFalse = ifFalse; + if (ifFalse->list.size() == 0 || !ifFalse->list.back()->template is()) { + ifFalse->list.push_back(this->getModule()->allocator.template alloc()); + } } } ifsToEnlarge.clear(); @@ -641,7 +709,7 @@ struct SimplifyLocals : public WalkerPass