/* * Copyright 2017 WebAssembly Community Group participants * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #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(const PassOptions& passOptions, FeatureSet features, Expression* ast = nullptr) : ignoreImplicitTraps(passOptions.ignoreImplicitTraps), debugInfo(passOptions.debugInfo), features(features) { if (ast) { analyze(ast); } } bool ignoreImplicitTraps; bool debugInfo; FeatureSet features; void analyze(Expression* ast) { breakTargets.clear(); walk(ast); assert(tryDepth == 0); } // Core effect tracking // Definitely branches out of this expression, or does a return, etc. // breakTargets tracks individual targets, which we may eventually see are // internal, while this is set when we see something that will definitely // not be internal, or is otherwise special like an infinite loop (which // does not technically branch "out", but it does break the normal assumption // of control flow proceeding normally). bool branchesOut = false; bool calls = false; std::set localsRead; std::set localsWritten; std::set globalsRead; std::set globalsWritten; bool readsMemory = false; bool writesMemory = 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 implicitTrap = false; // An atomic load/store/RMW/Cmpxchg or an operator that has a defined ordering // wrt atomics (e.g. memory.grow) bool isAtomic = false; bool throws = false; // The nested depth of try. If an instruction that may throw is inside an // inner try, we don't mark it as 'throws', because it will be caught by an // inner catch. size_t tryDepth = 0; // The nested depth of catch. This is necessary to track danglng pops. size_t catchDepth = 0; // If this expression contains 'exnref.pop's that are not enclosed in 'catch' // body. For example, (drop (exnref.pop)) should set this to true. bool danglingPop = false; static void scan(EffectAnalyzer* self, Expression** currp) { Expression* curr = *currp; // We need to decrement try depth before catch starts, so handle it // separately if (curr->is()) { self->pushTask(doVisitTry, currp); self->pushTask(doEndCatch, currp); self->pushTask(scan, &curr->cast()->catchBody); self->pushTask(doStartCatch, currp); self->pushTask(scan, &curr->cast()->body); self->pushTask(doStartTry, currp); return; } PostWalker>::scan(self, currp); } static void doStartTry(EffectAnalyzer* self, Expression** currp) { self->tryDepth++; } static void doStartCatch(EffectAnalyzer* self, Expression** currp) { assert(self->tryDepth > 0 && "try depth cannot be negative"); self->tryDepth--; self->catchDepth++; } static void doEndCatch(EffectAnalyzer* self, Expression** currp) { assert(self->catchDepth > 0 && "catch depth cannot be negative"); self->catchDepth--; } // 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 accessesMemory() const { return calls || readsMemory || writesMemory; } // Check whether this may transfer control flow to somewhere outside of this // expression (aside from just flowing out normally). That includes a break // or a throw (if the throw is not known to be caught inside this expression; // note that if the throw is not caught in this expression then it might be // caught in this function but outside of this expression, or it might not be // caught in the function at all, which would mean control flow cannot be // transferred inside the function, but this expression does not know that). bool transfersControlFlow() const { return branchesOut || throws || hasExternalBreakTargets(); } bool hasGlobalSideEffects() const { return calls || globalsWritten.size() > 0 || writesMemory || isAtomic || throws; } bool hasSideEffects() const { return hasGlobalSideEffects() || localsWritten.size() > 0 || transfersControlFlow() || implicitTrap || danglingPop; } bool hasAnything() const { return hasSideEffects() || accessesLocal() || readsMemory || accessesGlobal() || isAtomic; } bool noticesGlobalSideEffects() const { return calls || readsMemory || isAtomic || globalsRead.size(); } // check if we break to anything external from ourselves bool hasExternalBreakTargets() const { return !breakTargets.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) bool invalidates(const EffectAnalyzer& other) { if ((transfersControlFlow() && other.hasSideEffects()) || (other.transfersControlFlow() && hasSideEffects()) || ((writesMemory || calls) && other.accessesMemory()) || (accessesMemory() && (other.writesMemory || other.calls)) || (danglingPop || other.danglingPop)) { return true; } // All atomics are sequentially consistent for now, and ordered wrt other // memory references. if ((isAtomic && other.accessesMemory()) || (other.isAtomic && accessesMemory())) { return true; } for (auto local : localsWritten) { if (other.localsWritten.count(local) || other.localsRead.count(local)) { return true; } } for (auto local : localsRead) { if (other.localsWritten.count(local)) { return true; } } if ((accessesGlobal() && other.calls) || (other.accessesGlobal() && calls)) { return true; } for (auto global : globalsWritten) { if (other.globalsWritten.count(global) || other.globalsRead.count(global)) { return true; } } for (auto global : globalsRead) { if (other.globalsWritten.count(global)) { return true; } } // we are ok to reorder implicit traps, but not conditionalize them if ((implicitTrap && other.transfersControlFlow()) || (other.implicitTrap && transfersControlFlow())) { return true; } // we can't reorder an implicit trap in a way that alters global state if ((implicitTrap && other.hasGlobalSideEffects()) || (other.implicitTrap && hasGlobalSideEffects())) { return true; } return false; } void mergeIn(EffectAnalyzer& other) { branchesOut = branchesOut || other.branchesOut; calls = calls || other.calls; readsMemory = readsMemory || other.readsMemory; writesMemory = writesMemory || other.writesMemory; implicitTrap = implicitTrap || other.implicitTrap; isAtomic = isAtomic || other.isAtomic; throws = throws || other.throws; danglingPop = danglingPop || other.danglingPop; 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.breakTargets) { breakTargets.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 bool checkPre(Expression* curr) { if (curr->is()) { branchesOut = true; return true; } return false; } bool checkPost(Expression* curr) { visit(curr); if (curr->is()) { branchesOut = true; } return hasAnything(); } std::set breakTargets; void visitBlock(Block* curr) { if (curr->name.is()) { breakTargets.erase(curr->name); // these were internal breaks } } void visitIf(If* curr) {} void visitLoop(Loop* curr) { if (curr->name.is()) { breakTargets.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). if (curr->type == Type::unreachable) { branchesOut = true; } } void visitBreak(Break* curr) { breakTargets.insert(curr->name); } void visitSwitch(Switch* curr) { for (auto name : curr->targets) { breakTargets.insert(name); } breakTargets.insert(curr->default_); } void visitCall(Call* curr) { calls = true; // When EH is enabled, any call can throw. if (features.hasExceptionHandling() && tryDepth == 0) { throws = true; } if (curr->isReturn) { branchesOut = true; } if (debugInfo) { // debugInfo call imports must be preserved very strongly, do not // move code around them // FIXME: we could check if the call is to an import branchesOut = true; } } void visitCallIndirect(CallIndirect* curr) { calls = true; if (features.hasExceptionHandling() && tryDepth == 0) { throws = true; } if (curr->isReturn) { branchesOut = true; } } void visitLocalGet(LocalGet* curr) { localsRead.insert(curr->index); } void visitLocalSet(LocalSet* curr) { localsWritten.insert(curr->index); } void visitGlobalGet(GlobalGet* curr) { globalsRead.insert(curr->name); } void visitGlobalSet(GlobalSet* curr) { globalsWritten.insert(curr->name); } void visitLoad(Load* curr) { readsMemory = true; isAtomic |= curr->isAtomic; if (!ignoreImplicitTraps) { implicitTrap = true; } } void visitStore(Store* curr) { writesMemory = true; isAtomic |= curr->isAtomic; if (!ignoreImplicitTraps) { implicitTrap = true; } } void visitAtomicRMW(AtomicRMW* curr) { readsMemory = true; writesMemory = true; isAtomic = true; if (!ignoreImplicitTraps) { implicitTrap = true; } } void visitAtomicCmpxchg(AtomicCmpxchg* curr) { readsMemory = true; writesMemory = true; isAtomic = true; if (!ignoreImplicitTraps) { implicitTrap = true; } } void visitAtomicWait(AtomicWait* curr) { readsMemory = true; // AtomicWait 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. writesMemory = true; isAtomic = 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. readsMemory = true; writesMemory = true; isAtomic = true; if (!ignoreImplicitTraps) { implicitTrap = true; } } void visitAtomicFence(AtomicFence* curr) { // AtomicFence should not be reordered with any memory operations, so we set // these to true. readsMemory = true; writesMemory = true; isAtomic = true; } void visitSIMDExtract(SIMDExtract* curr) {} void visitSIMDReplace(SIMDReplace* curr) {} void visitSIMDShuffle(SIMDShuffle* curr) {} void visitSIMDTernary(SIMDTernary* curr) {} void visitSIMDShift(SIMDShift* curr) {} void visitSIMDLoad(SIMDLoad* curr) { readsMemory = true; if (!ignoreImplicitTraps) { implicitTrap = true; } } void visitMemoryInit(MemoryInit* curr) { writesMemory = true; if (!ignoreImplicitTraps) { implicitTrap = true; } } void visitDataDrop(DataDrop* curr) { // data.drop does not actually write memory, but it does alter the size of // a segment, which can be noticeable later by memory.init, so we need to // mark it as having a global side effect of some kind. writesMemory = true; if (!ignoreImplicitTraps) { implicitTrap = true; } } void visitMemoryCopy(MemoryCopy* curr) { readsMemory = true; writesMemory = true; if (!ignoreImplicitTraps) { implicitTrap = true; } } void visitMemoryFill(MemoryFill* curr) { writesMemory = true; if (!ignoreImplicitTraps) { implicitTrap = true; } } void visitConst(Const* curr) {} void visitUnary(Unary* curr) { if (!ignoreImplicitTraps) { switch (curr->op) { case TruncSFloat32ToInt32: case TruncSFloat32ToInt64: case TruncUFloat32ToInt32: case TruncUFloat32ToInt64: case TruncSFloat64ToInt32: case TruncSFloat64ToInt64: case TruncUFloat64ToInt32: case TruncUFloat64ToInt64: { implicitTrap = true; break; } default: { } } } } void visitBinary(Binary* curr) { if (!ignoreImplicitTraps) { switch (curr->op) { case DivSInt32: case DivUInt32: case RemSInt32: case RemUInt32: case DivSInt64: case DivUInt64: case RemSInt64: case RemUInt64: { implicitTrap = true; break; } default: { } } } } void visitSelect(Select* curr) {} void visitDrop(Drop* curr) {} void visitReturn(Return* curr) { branchesOut = true; } void visitMemorySize(MemorySize* curr) { // memory.size accesses the size of the memory, and thus can be modeled as // reading memory readsMemory = true; // Atomics are sequentially consistent with memory.size. isAtomic = true; } void visitMemoryGrow(MemoryGrow* curr) { calls = true; // memory.grow technically does a read-modify-write operation on the memory // size in the successful case, modifying the set of valid addresses, and // just a read operation in the failure case readsMemory = true; writesMemory = true; // Atomics are also sequentially consistent with memory.grow. isAtomic = true; } void visitRefNull(RefNull* curr) {} void visitRefIsNull(RefIsNull* curr) {} void visitRefFunc(RefFunc* curr) {} void visitRefEq(RefEq* curr) {} void visitTry(Try* curr) {} void visitThrow(Throw* curr) { if (tryDepth == 0) { throws = true; } } void visitRethrow(Rethrow* curr) { if (tryDepth == 0) { throws = true; } if (!ignoreImplicitTraps) { // rethrow traps when the arg is null implicitTrap = true; } } void visitBrOnExn(BrOnExn* curr) { breakTargets.insert(curr->name); if (!ignoreImplicitTraps) { // br_on_exn traps when the arg is null implicitTrap = true; } } void visitNop(Nop* curr) {} void visitUnreachable(Unreachable* curr) { branchesOut = true; } void visitPop(Pop* curr) { if (catchDepth == 0) { danglingPop = true; } } void visitTupleMake(TupleMake* curr) {} void visitTupleExtract(TupleExtract* curr) {} void visitI31New(I31New* curr) {} void visitI31Get(I31Get* curr) {} void visitRefTest(RefTest* curr) { WASM_UNREACHABLE("TODO (gc): ref.test"); } void visitRefCast(RefCast* curr) { WASM_UNREACHABLE("TODO (gc): ref.cast"); } void visitBrOnCast(BrOnCast* curr) { WASM_UNREACHABLE("TODO (gc): br_on_cast"); } void visitRttCanon(RttCanon* curr) { WASM_UNREACHABLE("TODO (gc): rtt.canon"); } void visitRttSub(RttSub* curr) { WASM_UNREACHABLE("TODO (gc): rtt.sub"); } void visitStructNew(StructNew* curr) { WASM_UNREACHABLE("TODO (gc): struct.new"); } void visitStructGet(StructGet* curr) { WASM_UNREACHABLE("TODO (gc): struct.get"); } void visitStructSet(StructSet* curr) { WASM_UNREACHABLE("TODO (gc): struct.set"); } void visitArrayNew(ArrayNew* curr) { WASM_UNREACHABLE("TODO (gc): array.new"); } void visitArrayGet(ArrayGet* curr) { WASM_UNREACHABLE("TODO (gc): array.get"); } void visitArraySet(ArraySet* curr) { WASM_UNREACHABLE("TODO (gc): array.set"); } void visitArrayLen(ArrayLen* curr) { WASM_UNREACHABLE("TODO (gc): array.len"); } // Helpers static bool canReorder(const PassOptions& passOptions, FeatureSet features, Expression* a, Expression* b) { EffectAnalyzer aEffects(passOptions, features, a); EffectAnalyzer bEffects(passOptions, features, b); return !aEffects.invalidates(bEffects); } // C-API enum SideEffects : uint32_t { None = 0, Branches = 1 << 0, Calls = 1 << 1, ReadsLocal = 1 << 2, WritesLocal = 1 << 3, ReadsGlobal = 1 << 4, WritesGlobal = 1 << 5, ReadsMemory = 1 << 6, WritesMemory = 1 << 7, ImplicitTrap = 1 << 8, IsAtomic = 1 << 9, Throws = 1 << 10, DanglingPop = 1 << 11, Any = (1 << 12) - 1 }; uint32_t getSideEffects() const { uint32_t effects = 0; if (branchesOut || hasExternalBreakTargets()) { effects |= SideEffects::Branches; } if (calls) { effects |= SideEffects::Calls; } if (localsRead.size() > 0) { effects |= SideEffects::ReadsLocal; } if (localsWritten.size() > 0) { effects |= SideEffects::WritesLocal; } if (globalsRead.size() > 0) { effects |= SideEffects::ReadsGlobal; } if (globalsWritten.size() > 0) { effects |= SideEffects::WritesGlobal; } if (readsMemory) { effects |= SideEffects::ReadsMemory; } if (writesMemory) { effects |= SideEffects::WritesMemory; } if (implicitTrap) { effects |= SideEffects::ImplicitTrap; } if (isAtomic) { effects |= SideEffects::IsAtomic; } if (throws) { effects |= SideEffects::Throws; } if (danglingPop) { effects |= SideEffects::DanglingPop; } return effects; } void ignoreBranches() { branchesOut = false; breakTargets.clear(); } }; } // namespace wasm #endif // wasm_ir_effects_h