summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ir/equivalent_sets.h4
-rw-r--r--src/passes/SimplifyLocals.cpp122
2 files changed, 97 insertions, 29 deletions
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<Index> Set;
+ // A set of indexes. This is ordered for deterministic iteration.
+ typedef std::set<Index> Set;
std::unordered_map<Index, std::shared_ptr<Set>> 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 WalkerPass<LinearExecutionWalker<SimplifyLocals<a
} else if (curr->is<Block>()) {
return; // handled in visitBlock
} else if (curr->is<If>()) {
- assert(!curr->cast<If>()->ifFalse); // if-elses are handled by doNoteIfElse* methods
+ assert(!curr->cast<If>()->ifFalse); // if-elses are handled by doNoteIf* methods
} else if (curr->is<Switch>()) {
auto* sw = curr->cast<Switch>();
auto targets = BranchUtils::getUniqueTargets(sw);
@@ -138,26 +138,34 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals<a
self->sinkables.clear();
}
- static void doNoteIfElseCondition(SimplifyLocals<allowTee, allowStructure, allowNesting>* self, Expression** currp) {
+ static void doNoteIfCondition(SimplifyLocals<allowTee, allowStructure, allowNesting>* 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<If>()->ifFalse);
self->sinkables.clear();
}
- static void doNoteIfElseTrue(SimplifyLocals<allowTee, allowStructure, allowNesting>* self, Expression** currp) {
- // we processed the ifTrue side of this if-else, save it on the stack
- assert((*currp)->cast<If>()->ifFalse);
- self->ifStack.push_back(std::move(self->sinkables));
+ static void doNoteIfTrue(SimplifyLocals<allowTee, allowStructure, allowNesting>* self, Expression** currp) {
+ auto* iff = (*currp)->dynCast<If>();
+ if (iff->ifFalse) {
+ // We processed the ifTrue side of this if-else, save it on the stack.
+ assert((*currp)->cast<If>()->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<allowTee, allowStructure, allowNesting>* self, Expression** currp) {
+ static void doNoteIfFalse(SimplifyLocals<allowTee, allowStructure, allowNesting>* 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<If>();
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 WalkerPass<LinearExecutionWalker<SimplifyLocals<a
}
// optimize set_locals from both sides of an if into a return value
- void optimizeIfReturn(If* iff, Expression** currp, Sinkables& ifTrue) {
+ void optimizeIfElseReturn(If* iff, Expression** currp, Sinkables& ifTrue) {
assert(iff->ifFalse);
// if this if already has a result, or is unreachable code, we have
// nothing to do
@@ -497,14 +505,14 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals<a
// need another cycle
auto* ifTrueBlock = iff->ifTrue->dynCast<Block>();
if (iff->ifTrue->type != unreachable) {
- if (!ifTrueBlock || ifTrueBlock->list.size() == 0 || !ifTrueBlock->list.back()->is<Nop>()) {
+ if (!ifTrueBlock || ifTrueBlock->name.is() || ifTrueBlock->list.size() == 0 || !ifTrueBlock->list.back()->is<Nop>()) {
ifsToEnlarge.push_back(iff);
return;
}
}
auto* ifFalseBlock = iff->ifFalse->dynCast<Block>();
if (iff->ifFalse->type != unreachable) {
- if (!ifFalseBlock || ifFalseBlock->list.size() == 0 || !ifFalseBlock->list.back()->is<Nop>()) {
+ if (!ifFalseBlock || ifFalseBlock->name.is() || ifFalseBlock->list.size() == 0 || !ifFalseBlock->list.back()->is<Nop>()) {
ifsToEnlarge.push_back(iff);
return;
}
@@ -532,20 +540,78 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals<a
anotherCycle = true;
}
+ // Optimize set_locals from a one-sided iff, adding a get on the other:
+ // (if
+ // (..condition..)
+ // (block
+ // (set_local $x (..value..))
+ // )
+ // )
+ // =>
+ // (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<Block>();
+ if (!ifTrueBlock || ifTrueBlock->name.is() || ifTrueBlock->list.size() == 0 || !ifTrueBlock->list.back()->is<Nop>()) {
+ ifsToEnlarge.push_back(iff);
+ return;
+ }
+ // Update the ifTrue side.
+ Builder builder(*this->getModule());
+ auto** item = sinkables.at(goodIndex).item;
+ auto* set = (*item)->template cast<SetLocal>();
+ 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<allowTee, allowStructure, allowNesting>* self, Expression** currp) {
self->pushTask(visitPost, currp);
auto* curr = *currp;
- if (curr->is<If>() && curr->cast<If>()->ifFalse) {
- // handle if-elses in a special manner, using the ifStack
- self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::doNoteIfElseFalse, currp);
- self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::scan, &curr->cast<If>()->ifFalse);
- self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::doNoteIfElseTrue, currp);
- self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::scan, &curr->cast<If>()->ifTrue);
- self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::doNoteIfElseCondition, currp);
- self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::scan, &curr->cast<If>()->condition);
+ if (auto* iff = curr->dynCast<If>()) {
+ // handle if in a special manner, using the ifStack for if-elses etc.
+ if (iff->ifFalse) {
+ self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::doNoteIfFalse, currp);
+ self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::scan, &iff->ifFalse);
+ }
+ self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::doNoteIfTrue, currp);
+ self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::scan, &iff->ifTrue);
+ self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::doNoteIfCondition, currp);
+ self->pushTask(SimplifyLocals<allowTee, allowStructure, allowNesting>::scan, &iff->condition);
} else {
WalkerPass<LinearExecutionWalker<SimplifyLocals<allowTee, allowStructure, allowNesting>>>::scan(self, currp);
}
@@ -582,7 +648,7 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals<a
// opts; continue only if they do. In other words, do not end up
// doing final opts again and again when no main opts are being
// enabled.
- if (runFinalOptimizations(func) && runMainOptimizations(func)) {
+ if (runLateOptimizations(func) && runMainOptimizations(func)) {
anotherCycle = true;
}
}
@@ -603,15 +669,17 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals<a
// enlarge ifs that were marked, for the next round
if (ifsToEnlarge.size() > 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<Nop>()) {
ifTrue->list.push_back(this->getModule()->allocator.template alloc<Nop>());
}
- auto ifFalse = Builder(*this->getModule()).blockify(iff->ifFalse);
- iff->ifFalse = ifFalse;
- if (ifFalse->list.size() == 0 || !ifFalse->list.back()->template is<Nop>()) {
- ifFalse->list.push_back(this->getModule()->allocator.template alloc<Nop>());
+ 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<Nop>()) {
+ ifFalse->list.push_back(this->getModule()->allocator.template alloc<Nop>());
+ }
}
}
ifsToEnlarge.clear();
@@ -641,7 +709,7 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals<a
return anotherCycle;
}
- bool runFinalOptimizations(Function* func) {
+ bool runLateOptimizations(Function* func) {
// Finally, after optimizing a function we can do some additional
// optimization.
getCounter.analyze(func);
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-06 15:13:15 +0000