summaryrefslogtreecommitdiff
path: root/src/ir/effects.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/ir/effects.h')
-rw-r--r--src/ir/effects.h195
1 files changed, 116 insertions, 79 deletions
diff --git a/src/ir/effects.h b/src/ir/effects.h
index e1fa77af0..9a3f29d8a 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -17,31 +17,38 @@
#ifndef wasm_ir_effects_h
#define wasm_ir_effects_h
+#include "pass.h"
+#include "wasm-traversal.h"
+
namespace wasm {
// Look for side effects, including control flow
// TODO: optimize
-struct EffectAnalyzer : public PostWalker<EffectAnalyzer, OverriddenVisitor<EffectAnalyzer>> {
- EffectAnalyzer(PassOptions& passOptions, Expression *ast = nullptr) {
+struct EffectAnalyzer
+ : public PostWalker<EffectAnalyzer, OverriddenVisitor<EffectAnalyzer>> {
+ EffectAnalyzer(PassOptions& passOptions, Expression* ast = nullptr) {
ignoreImplicitTraps = passOptions.ignoreImplicitTraps;
debugInfo = passOptions.debugInfo;
- if (ast) analyze(ast);
+ if (ast)
+ analyze(ast);
}
bool ignoreImplicitTraps;
bool debugInfo;
- void analyze(Expression *ast) {
+ void analyze(Expression* ast) {
breakNames.clear();
walk(ast);
// if we are left with breaks, they are external
- if (breakNames.size() > 0) branches = true;
+ if (breakNames.size() > 0)
+ branches = true;
}
// Core effect tracking
- bool branches = false; // branches out of this expression, returns, infinite loops, etc
+ // branches out of this expression, returns, infinite loops, etc
+ bool branches = false;
bool calls = false;
std::set<Index> localsRead;
std::set<Index> localsWritten;
@@ -49,30 +56,46 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer, OverriddenVisitor<Effe
std::set<Name> globalsWritten;
bool readsMemory = false;
bool writesMemory = false;
- bool implicitTrap = false; // a load or div/rem, which may trap. we ignore trap
- // differences, so it is ok to reorder these, but we can't
- // remove them, as they count as side effects, and we
- // can't move them in a way that would cause other noticeable
- // (global) side effects
- bool isAtomic = false; // An atomic load/store/RMW/Cmpxchg or an operator that
- // has a defined ordering wrt atomics (e.g. grow_memory)
+ // a load or div/rem, which may trap. we ignore trap differences, so it is ok
+ // to reorder these, but we can't remove them, as they count as side effects,
+ // and we can't move them in a way that would cause other noticeable (global)
+ // side effects
+ bool implicitTrap = false;
+ // An atomic load/store/RMW/Cmpxchg or an operator that has a defined ordering
+ // wrt atomics (e.g. grow_memory)
+ bool isAtomic = false;
// Helper functions to check for various effect types
- bool accessesLocal() const { return localsRead.size() + localsWritten.size() > 0; }
- bool accessesGlobal() const { return globalsRead.size() + globalsWritten.size() > 0; }
+ bool accessesLocal() const {
+ return localsRead.size() + localsWritten.size() > 0;
+ }
+ bool accessesGlobal() const {
+ return globalsRead.size() + globalsWritten.size() > 0;
+ }
bool accessesMemory() const { return calls || readsMemory || writesMemory; }
- bool hasGlobalSideEffects() const { return calls || globalsWritten.size() > 0 || writesMemory || isAtomic; }
- bool hasSideEffects() const { return hasGlobalSideEffects() || localsWritten.size() > 0 || branches || implicitTrap; }
- bool hasAnything() const { return branches || calls || accessesLocal() || readsMemory || writesMemory || accessesGlobal() || implicitTrap || isAtomic; }
+ bool hasGlobalSideEffects() const {
+ return calls || globalsWritten.size() > 0 || writesMemory || isAtomic;
+ }
+ bool hasSideEffects() const {
+ return hasGlobalSideEffects() || localsWritten.size() > 0 || branches ||
+ implicitTrap;
+ }
+ bool hasAnything() const {
+ return branches || calls || accessesLocal() || readsMemory ||
+ writesMemory || accessesGlobal() || implicitTrap || isAtomic;
+ }
- bool noticesGlobalSideEffects() { return calls || readsMemory || isAtomic || globalsRead.size(); }
+ bool noticesGlobalSideEffects() {
+ return calls || readsMemory || isAtomic || globalsRead.size();
+ }
// check if we break to anything external from ourselves
bool hasExternalBreakTargets() { return !breakNames.empty(); }
- // 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)
+ // 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)
bool invalidates(const EffectAnalyzer& other) {
if ((branches && other.hasSideEffects()) ||
(other.branches && hasSideEffects()) ||
@@ -92,25 +115,30 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer, OverriddenVisitor<Effe
}
}
for (auto local : localsRead) {
- if (other.localsWritten.count(local)) return true;
+ if (other.localsWritten.count(local))
+ return true;
}
- if ((accessesGlobal() && other.calls) || (other.accessesGlobal() && calls)) {
+ if ((accessesGlobal() && other.calls) ||
+ (other.accessesGlobal() && calls)) {
return true;
}
for (auto global : globalsWritten) {
- if (other.globalsWritten.count(global) || other.globalsRead.count(global)) {
+ if (other.globalsWritten.count(global) ||
+ other.globalsRead.count(global)) {
return true;
}
}
for (auto global : globalsRead) {
- if (other.globalsWritten.count(global)) return true;
+ if (other.globalsWritten.count(global))
+ return true;
}
// we are ok to reorder implicit traps, but not conditionalize them
if ((implicitTrap && other.branches) || (other.implicitTrap && branches)) {
return true;
}
// we can't reorder an implicit trap in a way that alters global state
- if ((implicitTrap && other.hasGlobalSideEffects()) || (other.implicitTrap && hasGlobalSideEffects())) {
+ if ((implicitTrap && other.hasGlobalSideEffects()) ||
+ (other.implicitTrap && hasGlobalSideEffects())) {
return true;
}
return false;
@@ -123,14 +151,19 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer, OverriddenVisitor<Effe
writesMemory = writesMemory || other.writesMemory;
implicitTrap = implicitTrap || other.implicitTrap;
isAtomic = isAtomic || other.isAtomic;
- for (auto i : other.localsRead) localsRead.insert(i);
- for (auto i : other.localsWritten) localsWritten.insert(i);
- for (auto i : other.globalsRead) globalsRead.insert(i);
- for (auto i : other.globalsWritten) globalsWritten.insert(i);
+ for (auto i : other.localsRead)
+ localsRead.insert(i);
+ for (auto i : other.localsWritten)
+ localsWritten.insert(i);
+ for (auto i : other.globalsRead)
+ globalsRead.insert(i);
+ for (auto i : other.globalsWritten)
+ globalsWritten.insert(i);
}
- // the checks above happen after the node's children were processed, in the order of execution
- // we must also check for control flow that happens before the children, i.e., loops
+ // the checks above happen after the node's children were processed, in the
+ // order of execution we must also check for control flow that happens before
+ // the children, i.e., loops
bool checkPre(Expression* curr) {
if (curr->is<Loop>()) {
branches = true;
@@ -150,35 +183,35 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer, OverriddenVisitor<Effe
std::set<Name> breakNames;
void visitBlock(Block* curr) {
- if (curr->name.is()) breakNames.erase(curr->name); // these were internal breaks
+ if (curr->name.is())
+ breakNames.erase(curr->name); // these were internal breaks
}
void visitIf(If* curr) {}
void visitLoop(Loop* curr) {
- if (curr->name.is()) breakNames.erase(curr->name); // these were internal breaks
+ if (curr->name.is())
+ breakNames.erase(curr->name); // these were internal breaks
// if the loop is unreachable, then there is branching control flow:
- // (1) if the body is unreachable because of a (return), uncaught (br) etc., then we
- // already noted branching, so it is ok to mark it again (if we have *caught*
- // (br)s, then they did not lead to the loop body being unreachable).
- // (same logic applies to blocks)
- // (2) if the loop is unreachable because it only has branches up to the loop
- // top, but no way to get out, then it is an infinite loop, and we consider
- // that a branching side effect (note how the same logic does not apply to
- // blocks).
+ // (1) if the body is unreachable because of a (return), uncaught (br)
+ // etc., then we already noted branching, so it is ok to mark it again
+ // (if we have *caught* (br)s, then they did not lead to the loop body
+ // being unreachable). (same logic applies to blocks)
+ // (2) if the loop is unreachable because it only has branches up to the
+ // loop top, but no way to get out, then it is an infinite loop, and we
+ // consider that a branching side effect (note how the same logic does
+ // not apply to blocks).
if (curr->type == unreachable) {
branches = true;
}
}
- void visitBreak(Break *curr) {
- breakNames.insert(curr->name);
- }
- void visitSwitch(Switch *curr) {
+ void visitBreak(Break* curr) { breakNames.insert(curr->name); }
+ void visitSwitch(Switch* curr) {
for (auto name : curr->targets) {
breakNames.insert(name);
}
breakNames.insert(curr->default_);
}
- void visitCall(Call *curr) {
+ void visitCall(Call* curr) {
calls = true;
if (debugInfo) {
// debugInfo call imports must be preserved very strongly, do not
@@ -187,40 +220,36 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer, OverriddenVisitor<Effe
branches = true;
}
}
- void visitCallIndirect(CallIndirect *curr) { calls = true; }
- void visitGetLocal(GetLocal *curr) {
- localsRead.insert(curr->index);
- }
- void visitSetLocal(SetLocal *curr) {
- localsWritten.insert(curr->index);
- }
- void visitGetGlobal(GetGlobal *curr) {
- globalsRead.insert(curr->name);
- }
- void visitSetGlobal(SetGlobal *curr) {
- globalsWritten.insert(curr->name);
- }
- void visitLoad(Load *curr) {
+ void visitCallIndirect(CallIndirect* curr) { calls = true; }
+ void visitGetLocal(GetLocal* curr) { localsRead.insert(curr->index); }
+ void visitSetLocal(SetLocal* curr) { localsWritten.insert(curr->index); }
+ void visitGetGlobal(GetGlobal* curr) { globalsRead.insert(curr->name); }
+ void visitSetGlobal(SetGlobal* curr) { globalsWritten.insert(curr->name); }
+ void visitLoad(Load* curr) {
readsMemory = true;
isAtomic |= curr->isAtomic;
- if (!ignoreImplicitTraps) implicitTrap = true;
+ if (!ignoreImplicitTraps)
+ implicitTrap = true;
}
- void visitStore(Store *curr) {
+ void visitStore(Store* curr) {
writesMemory = true;
isAtomic |= curr->isAtomic;
- if (!ignoreImplicitTraps) implicitTrap = true;
+ if (!ignoreImplicitTraps)
+ implicitTrap = true;
}
void visitAtomicRMW(AtomicRMW* curr) {
readsMemory = true;
writesMemory = true;
isAtomic = true;
- if (!ignoreImplicitTraps) implicitTrap = true;
+ if (!ignoreImplicitTraps)
+ implicitTrap = true;
}
void visitAtomicCmpxchg(AtomicCmpxchg* curr) {
readsMemory = true;
writesMemory = true;
isAtomic = true;
- if (!ignoreImplicitTraps) implicitTrap = true;
+ if (!ignoreImplicitTraps)
+ implicitTrap = true;
}
void visitAtomicWait(AtomicWait* curr) {
readsMemory = true;
@@ -229,16 +258,18 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer, OverriddenVisitor<Effe
// write.
writesMemory = true;
isAtomic = true;
- if (!ignoreImplicitTraps) implicitTrap = true;
+ if (!ignoreImplicitTraps)
+ implicitTrap = true;
}
void visitAtomicNotify(AtomicNotify* curr) {
- // AtomicNotify doesn't strictly write memory, but it does modify the waiters
- // list associated with the specified address, which we can think of as a
- // write.
+ // AtomicNotify doesn't strictly write memory, but it does modify the
+ // waiters list associated with the specified address, which we can think of
+ // as a write.
readsMemory = true;
writesMemory = true;
isAtomic = true;
- if (!ignoreImplicitTraps) implicitTrap = true;
+ if (!ignoreImplicitTraps)
+ implicitTrap = true;
};
void visitSIMDExtract(SIMDExtract* curr) {}
void visitSIMDReplace(SIMDReplace* curr) {}
@@ -247,21 +278,25 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer, OverriddenVisitor<Effe
void visitSIMDShift(SIMDShift* curr) {}
void visitMemoryInit(MemoryInit* curr) {
writesMemory = true;
- if (!ignoreImplicitTraps) implicitTrap = true;
+ if (!ignoreImplicitTraps)
+ implicitTrap = true;
}
void visitDataDrop(DataDrop* curr) {
// prevent reordering with memory.init
readsMemory = true;
- if (!ignoreImplicitTraps) implicitTrap = true;
+ if (!ignoreImplicitTraps)
+ implicitTrap = true;
}
void visitMemoryCopy(MemoryCopy* curr) {
readsMemory = true;
writesMemory = true;
- if (!ignoreImplicitTraps) implicitTrap = true;
+ if (!ignoreImplicitTraps)
+ implicitTrap = true;
}
void visitMemoryFill(MemoryFill* curr) {
writesMemory = true;
- if (!ignoreImplicitTraps) implicitTrap = true;
+ if (!ignoreImplicitTraps)
+ implicitTrap = true;
}
void visitConst(Const* curr) {}
void visitUnary(Unary* curr) {
@@ -302,20 +337,22 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer, OverriddenVisitor<Effe
}
void visitSelect(Select* curr) {}
void visitDrop(Drop* curr) {}
- void visitReturn(Return *curr) { branches = true; }
- void visitHost(Host *curr) {
+ void visitReturn(Return* curr) { branches = true; }
+ void visitHost(Host* curr) {
calls = true;
- // grow_memory modifies the set of valid addresses, and thus can be modeled as modifying memory
+ // grow_memory modifies the set of valid addresses, and thus can be modeled
+ // as modifying memory
writesMemory = true;
// Atomics are also sequentially consistent with grow_memory.
isAtomic = true;
}
void visitNop(Nop* curr) {}
- void visitUnreachable(Unreachable *curr) { branches = true; }
+ void visitUnreachable(Unreachable* curr) { branches = true; }
// Helpers
- static bool canReorder(PassOptions& passOptions, Expression* a, Expression* b) {
+ static bool
+ canReorder(PassOptions& passOptions, Expression* a, Expression* b) {
EffectAnalyzer aEffects(passOptions, a);
EffectAnalyzer bEffects(passOptions, b);
return !aEffects.invalidates(bEffects);
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-09 03:54:01 +0000