diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/ast_utils.h | 2 | ||||
| -rw-r--r-- | src/passes/RemoveUnusedBrs.cpp | 94 |
2 files changed, 81 insertions, 15 deletions
diff --git a/src/ast_utils.h b/src/ast_utils.h index 36895ac51..5cda48578 100644 --- a/src/ast_utils.h +++ b/src/ast_utils.h @@ -52,7 +52,7 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer, Visitor<EffectAnalyzer bool accessesLocal() { return localsRead.size() + localsWritten.size() > 0; } bool accessesMemory() { return calls || readsMemory || writesMemory; } - bool hasSideEffects() { return calls || localsWritten.size() > 0 || writesMemory; } + bool hasSideEffects() { return calls || localsWritten.size() > 0 || writesMemory || branches; } bool hasAnything() { return branches || calls || accessesLocal() || readsMemory || writesMemory; } // checks if these effects would invalidate another set (e.g., if we write, we invalidate someone that reads, they can't be moved past us) diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp index 3d6d6973f..f4efef173 100644 --- a/src/passes/RemoveUnusedBrs.cpp +++ b/src/passes/RemoveUnusedBrs.cpp @@ -29,7 +29,11 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs, Visitor<R bool anotherCycle; - typedef std::vector<Break*> Flows; + // Whether a value can flow in the current path. If so, then a br with value + // can be turned into a value, which will flow through blocks/ifs to the right place + bool valueCanFlow; + + typedef std::vector<Expression**> Flows; // list of breaks that are currently flowing. if they reach their target without // interference, they can be removed (or their value forwarded TODO) @@ -45,12 +49,17 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs, Visitor<R if (curr->is<Break>()) { flows.clear(); auto* br = curr->cast<Break>(); - if (!br->condition && !br->value) { // TODO: optimize in those cases? + if (!br->condition) { // TODO: optimize? // a break, let's see where it flows to - flows.push_back(br); + flows.push_back(currp); + self->valueCanFlow = true; // start optimistic + } else { + self->valueCanFlow = false; } - } else if (curr->is<Switch>()) { + } else if (curr->is<Return>()) { flows.clear(); + flows.push_back(currp); + self->valueCanFlow = true; // start optimistic } else if (curr->is<If>()) { auto* iff = curr->cast<If>(); if (iff->ifFalse) { @@ -62,15 +71,25 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs, Visitor<R } } else if (curr->is<Block>()) { // any breaks flowing to here are unnecessary, as we get here anyhow - auto name = curr->cast<Block>()->name; + auto* block = curr->cast<Block>(); + auto name = block->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++; - self->anotherCycle = true; + auto* flow = (*flows[i])->dynCast<Break>(); + if (flow && flow->name == name) { + if (!flow->value || self->valueCanFlow) { + if (!flow->value) { + // br => nop + ExpressionManipulator::nop(flow); + } else { + // br with value => value + *flows[i] = flow->value; + } + skip++; + self->anotherCycle = true; + } } else if (skip > 0) { flows[i - skip] = flows[i]; } @@ -78,15 +97,19 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs, Visitor<R if (skip > 0) { flows.resize(size - skip); } + // drop a nop at the end of a block, which prevents a value flowing + while (block->list.size() > 0 && block->list.back()->is<Nop>()) { + block->list.resize(block->list.size() - 1); + self->anotherCycle = true; + } } - } else if (curr->is<Loop>()) { - // TODO we might optimize branches out of here - flows.clear(); } else if (curr->is<Nop>()) { // ignore (could be result of a previous cycle) + self->valueCanFlow = false; } else { - // anything else stops the flow + // anything else stops the flow TODO: optimize loops? flows.clear(); + self->valueCanFlow = false; } } @@ -137,8 +160,51 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs, Visitor<R anotherCycle = false; WalkerPass<PostWalker<RemoveUnusedBrs, Visitor<RemoveUnusedBrs>>>::walk(root); assert(ifStack.empty()); - assert(flows.empty()); + // flows may contain returns, which are flowing out and so can be optimized + for (size_t i = 0; i < flows.size(); i++) { + auto* flow = (*flows[i])->cast<Return>(); // cannot be a break + if (!flow->value) { + // return => nop + ExpressionManipulator::nop(flow); + anotherCycle = true; + } else if (valueCanFlow) { + // return with value => value + *flows[i] = flow->value; + anotherCycle = true; + } + } + flows.clear(); } while (anotherCycle); + // finally, we may have simplified ifs enough to turn them into selects + struct Selectifier : public WalkerPass<PostWalker<Selectifier, Visitor<Selectifier>>> { + void visitIf(If* curr) { + if (curr->ifFalse) { + // if with else, consider turning it into a select if there is no control flow + // TODO: estimate cost + EffectAnalyzer condition; + condition.walk(curr->condition); + if (!condition.hasSideEffects()) { + EffectAnalyzer ifTrue; + ifTrue.walk(curr->ifTrue); + if (!ifTrue.hasSideEffects()) { + EffectAnalyzer ifFalse; + ifFalse.walk(curr->ifFalse); + if (!ifFalse.hasSideEffects()) { + auto* select = getModule()->allocator.alloc<Select>(); + select->condition = curr->condition; + select->ifTrue = curr->ifTrue; + select->ifFalse = curr->ifFalse; + select->finalize(); + replaceCurrent(select); + } + } + } + } + } + }; + Selectifier selectifier; + selectifier.setModule(getModule()); + selectifier.walk(root); } }; |