summaryrefslogtreecommitdiff
path: root/src/passes/RelooperJumpThreading.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/passes/RelooperJumpThreading.cpp')
-rw-r--r--src/passes/RelooperJumpThreading.cpp109
1 files changed, 66 insertions, 43 deletions
diff --git a/src/passes/RelooperJumpThreading.cpp b/src/passes/RelooperJumpThreading.cpp
index db865d1bb..9fcf7a4a8 100644
--- a/src/passes/RelooperJumpThreading.cpp
+++ b/src/passes/RelooperJumpThreading.cpp
@@ -19,14 +19,13 @@
// This assumes the very specific output the fastcomp relooper emits,
// including the name of the 'label' variable.
-#include "wasm.h"
-#include "pass.h"
-#include "ir/utils.h"
#include "ir/manipulation.h"
+#include "ir/utils.h"
+#include "pass.h"
+#include "wasm.h"
namespace wasm {
-
static Name LABEL("label");
static Name getInnerName(int i) {
@@ -38,13 +37,17 @@ static Name getOuterName(int i) {
}
static If* isLabelCheckingIf(Expression* curr, Index labelIndex) {
- if (!curr) return nullptr;
+ if (!curr)
+ return nullptr;
auto* iff = curr->dynCast<If>();
- if (!iff) return nullptr;
+ if (!iff)
+ return nullptr;
auto* condition = iff->condition->dynCast<Binary>();
- if (!(condition && condition->op == EqInt32)) return nullptr;
+ if (!(condition && condition->op == EqInt32))
+ return nullptr;
auto* left = condition->left->dynCast<GetLocal>();
- if (!(left && left->index == labelIndex)) return nullptr;
+ if (!(left && left->index == labelIndex))
+ return nullptr;
return iff;
}
@@ -53,10 +56,13 @@ static Index getCheckedLabelValue(If* iff) {
}
static SetLocal* isLabelSettingSetLocal(Expression* curr, Index labelIndex) {
- if (!curr) return nullptr;
+ if (!curr)
+ return nullptr;
auto* set = curr->dynCast<SetLocal>();
- if (!set) return nullptr;
- if (set->index != labelIndex) return nullptr;
+ if (!set)
+ return nullptr;
+ if (set->index != labelIndex)
+ return nullptr;
return set;
}
@@ -69,7 +75,10 @@ struct LabelUseFinder : public PostWalker<LabelUseFinder> {
std::map<Index, Index>& checks; // label value => number of checks on it
std::map<Index, Index>& sets; // label value => number of sets to it
- LabelUseFinder(Index labelIndex, std::map<Index, Index>& checks, std::map<Index, Index>& sets) : labelIndex(labelIndex), checks(checks), sets(sets) {}
+ LabelUseFinder(Index labelIndex,
+ std::map<Index, Index>& checks,
+ std::map<Index, Index>& sets)
+ : labelIndex(labelIndex), checks(checks), sets(sets) {}
void visitIf(If* curr) {
if (isLabelCheckingIf(curr, labelIndex)) {
@@ -84,7 +93,8 @@ struct LabelUseFinder : public PostWalker<LabelUseFinder> {
}
};
-struct RelooperJumpThreading : public WalkerPass<ExpressionStackWalker<RelooperJumpThreading>> {
+struct RelooperJumpThreading
+ : public WalkerPass<ExpressionStackWalker<RelooperJumpThreading>> {
bool isFunctionParallel() override { return true; }
Pass* create() override { return new RelooperJumpThreading; }
@@ -98,9 +108,11 @@ struct RelooperJumpThreading : public WalkerPass<ExpressionStackWalker<RelooperJ
void visitBlock(Block* curr) {
// look for the if label == X pattern
auto& list = curr->list;
- if (list.size() == 0) return;
+ if (list.size() == 0)
+ return;
for (Index i = 0; i < list.size() - 1; i++) {
- // once we see something that might be irreducible, we must skip that if and the rest of the dependents
+ // once we see something that might be irreducible, we must skip that if
+ // and the rest of the dependents
bool irreducible = false;
Index origin = i;
for (Index j = i + 1; j < list.size(); j++) {
@@ -113,15 +125,20 @@ struct RelooperJumpThreading : public WalkerPass<ExpressionStackWalker<RelooperJ
i++;
continue;
}
- // if the next element is a block, it may be the holding block of label-checking ifs
+ // if the next element is a block, it may be the holding block of
+ // label-checking ifs
if (auto* holder = list[j]->dynCast<Block>()) {
if (holder->list.size() > 0) {
if (If* iff = isLabelCheckingIf(holder->list[0], labelIndex)) {
irreducible |= hasIrreducibleControlFlow(iff, list[origin]);
if (!irreducible) {
- // this is indeed a holder. we can process the ifs, and must also move
- // the block to enclose the origin, so it is properly reachable
- assert(holder->list.size() == 1); // must be size 1, a relooper multiple will have its own label, and is an if-else sequence and nothing more
+ // this is indeed a holder. we can process the ifs, and must
+ // also move the block to enclose the origin, so it is properly
+ // reachable
+
+ // must be size 1, a relooper multiple will have its own label,
+ // and is an if-else sequence and nothing more
+ assert(holder->list.size() == 1);
optimizeJumpsToLabelCheck(list[origin], iff);
holder->list[0] = list[origin];
list[origin] = holder;
@@ -155,13 +172,13 @@ struct RelooperJumpThreading : public WalkerPass<ExpressionStackWalker<RelooperJ
}
private:
-
bool hasIrreducibleControlFlow(If* iff, Expression* origin) {
- // Gather the checks in this if chain. If all the label values checked are only set in origin,
- // then since origin is right before us, this is not irreducible - we can replace all sets
- // in origin with jumps forward to us, and since there is nothing else, this is safe and complete.
- // We must also have the property that there is just one check for the label value, as otherwise
- // node splitting has complicated things.
+ // Gather the checks in this if chain. If all the label values checked are
+ // only set in origin, then since origin is right before us, this is not
+ // irreducible - we can replace all sets in origin with jumps forward to us,
+ // and since there is nothing else, this is safe and complete. We must also
+ // have the property that there is just one check for the label value, as
+ // otherwise node splitting has complicated things.
std::map<Index, Index> labelChecksInOrigin;
std::map<Index, Index> labelSetsInOrigin;
LabelUseFinder finder(labelIndex, labelChecksInOrigin, labelSetsInOrigin);
@@ -169,23 +186,27 @@ private:
while (iff) {
auto num = getCheckedLabelValue(iff);
assert(labelChecks[num] > 0);
- if (labelChecks[num] > 1) return true; // checked more than once, somewhere in function
+ if (labelChecks[num] > 1)
+ return true; // checked more than once, somewhere in function
assert(labelChecksInOrigin[num] == 0);
if (labelSetsInOrigin[num] != labelSets[num]) {
assert(labelSetsInOrigin[num] < labelSets[num]);
// the label is set outside of the origin
- // if the only other location is inside the if body, then it is ok - it must be in a loop
- // and returning to the top of the loop body, so we don't need to do anything for that
- // label setting anyhow
+ // if the only other location is inside the if body, then it is ok - it
+ // must be in a loop and returning to the top of the loop body, so we
+ // don't need to do anything for that label setting anyhow
std::map<Index, Index> labelChecksInIfTrue;
std::map<Index, Index> labelSetsInIfTrue;
- LabelUseFinder finder(labelIndex, labelChecksInIfTrue, labelSetsInIfTrue);
+ LabelUseFinder finder(
+ labelIndex, labelChecksInIfTrue, labelSetsInIfTrue);
finder.walk(iff->ifTrue);
if (labelSetsInOrigin[num] + labelSetsInIfTrue[num] < labelSets[num]) {
- // label set somewhere we can't see now, could be irreducible control flow
- // TODO: one case where this happens is instead of an if-chain, we have
- // ifs and a switch on label|0, in separate elements. perhaps not
- // emitting switches on label|0 in the relooper would avoid that.
+ // label set somewhere we can't see now, could be irreducible control
+ // flow
+ // TODO: one case where this happens is instead of an if-chain, we
+ // have ifs and a switch on label|0, in separate elements.
+ // perhaps not emitting switches on label|0 in the relooper
+ // would avoid that.
return true;
}
}
@@ -195,19 +216,23 @@ private:
}
// optimizes jumps to a label check
- // * origin is where the jumps originate, and also where we should write our output
+ // * origin is where the jumps originate, and also where we should write our
+ // output
// * iff is the if
void optimizeJumpsToLabelCheck(Expression*& origin, If* iff) {
Index nameCounter = newNameCounter++;
Index num = getCheckedLabelValue(iff);
// create a new block for this jump target
Builder builder(*getModule());
- // origin is where all jumps to this target must come from - the element right before this if
- // we break out of inner to reach the target. instead of flowing out of normally, we break out of the outer, so we skip the target.
+ // origin is where all jumps to this target must come from - the element
+ // right before this if we break out of inner to reach the target. instead
+ // of flowing out of normally, we break out of the outer, so we skip the
+ // target.
auto innerName = getInnerName(nameCounter);
auto outerName = getOuterName(nameCounter);
auto* ifFalse = iff->ifFalse;
- // all assignments of label to the target can be replaced with breaks to the target, via innerName
+ // all assignments of label to the target can be replaced with breaks to the
+ // target, via innerName
struct JumpUpdater : public PostWalker<JumpUpdater> {
Index labelIndex;
Index targetNum;
@@ -228,7 +253,8 @@ private:
updater.setModule(getModule());
updater.walk(origin);
// restructure code
- auto* inner = builder.blockifyWithName(origin, innerName, builder.makeBreak(outerName));
+ auto* inner =
+ builder.blockifyWithName(origin, innerName, builder.makeBreak(outerName));
auto* outer = builder.makeSequence(inner, iff->ifTrue);
outer->name = outerName;
origin = outer;
@@ -241,9 +267,6 @@ private:
// declare pass
-Pass *createRelooperJumpThreadingPass() {
- return new RelooperJumpThreading();
-}
+Pass* createRelooperJumpThreadingPass() { return new RelooperJumpThreading(); }
} // namespace wasm
-
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-06 22:04:20 +0000