diff options
45 files changed, 1254 insertions, 370 deletions
diff --git a/src/asm2wasm.h b/src/asm2wasm.h index 4395054f6..2245bd2b5 100644 --- a/src/asm2wasm.h +++ b/src/asm2wasm.h @@ -32,6 +32,7 @@ #include "pass.h" #include "parsing.h" #include "ast_utils.h" +#include "ast/branch-utils.h" #include "wasm-builder.h" #include "wasm-emscripten.h" #include "wasm-module-building.h" @@ -1983,9 +1984,9 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) { // No wasm support, so use a temp local ensureI32Temp(); auto set = allocator.alloc<SetLocal>(); - set->setTee(false); set->index = function->getLocalIndex(I32_TEMP); set->value = value; + set->setTee(false); set->finalize(); auto get = [&]() { auto ret = allocator.alloc<GetLocal>(); @@ -2335,9 +2336,9 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) { nameMapper.popLabelName(more); nameMapper.popLabelName(stop); // if we never continued, we don't need a loop - BreakSeeker breakSeeker(more); - breakSeeker.walk(child); - if (breakSeeker.found == 0) { + BranchUtils::BranchSeeker seeker(more); + seeker.walk(child); + if (seeker.found == 0) { auto block = allocator.alloc<Block>(); block->list.push_back(child); if (isConcreteWasmType(child->type)) { diff --git a/src/ast/block-utils.h b/src/ast/block-utils.h index 7b1b9dcff..56c11f240 100644 --- a/src/ast/block-utils.h +++ b/src/ast/block-utils.h @@ -19,7 +19,8 @@ #include "literal.h" #include "wasm.h" -#include "ast_utils.h" +#include "ast/branch-utils.h" +#include "ast/effects.h" namespace wasm { @@ -29,7 +30,7 @@ namespace BlockUtils { template<typename T> inline Expression* simplifyToContents(Block* block, T* parent, bool allowTypeChange = false) { auto& list = block->list; - if (list.size() == 1 && !BreakSeeker::has(list[0], block->name)) { + if (list.size() == 1 && !BranchUtils::BranchSeeker::hasNamed(list[0], block->name)) { // just one element. try to replace the block auto* singleton = list[0]; auto sideEffects = EffectAnalyzer(parent->getPassOptions(), singleton).hasSideEffects(); diff --git a/src/ast/branch-utils.h b/src/ast/branch-utils.h index bdf52d36a..77ec70753 100644 --- a/src/ast/branch-utils.h +++ b/src/ast/branch-utils.h @@ -37,6 +37,15 @@ inline bool isBranchTaken(Switch* sw) { sw->condition->type != unreachable; } +inline bool isBranchTaken(Expression* expr) { + if (auto* br = expr->dynCast<Break>()) { + return isBranchTaken(br); + } else if (auto* sw = expr->dynCast<Switch>()) { + return isBranchTaken(sw); + } + WASM_UNREACHABLE(); +} + // returns the set of targets to which we branch that are // outside of a node inline std::set<Name> getExitingBranches(Expression* ast) { @@ -91,6 +100,81 @@ inline std::set<Name> getBranchTargets(Expression* ast) { return scanner.targets; } +// Finds if there are branches targeting a name. Note that since names are +// unique in our IR, we just need to look for the name, and do not need +// to analyze scoping. +// By default we ignore untaken branches. You can set named to +// note those as well, then any named branch is noted, even if untaken +struct BranchSeeker : public PostWalker<BranchSeeker> { + Name target; + bool named = false; + + Index found; + WasmType valueType; + + BranchSeeker(Name target) : target(target), found(0) {} + + void noteFound(Expression* value) { + found++; + if (found == 1) valueType = unreachable; + if (!value) valueType = none; + else if (value->type != unreachable) valueType = value->type; + } + + void visitBreak(Break *curr) { + if (!named) { + // ignore an unreachable break + if (curr->condition && curr->condition->type == unreachable) return; + if (curr->value && curr->value->type == unreachable) return; + } + // check the break + if (curr->name == target) noteFound(curr->value); + } + + void visitSwitch(Switch *curr) { + if (!named) { + // ignore an unreachable switch + if (curr->condition->type == unreachable) return; + if (curr->value && curr->value->type == unreachable) return; + } + // check the switch + for (auto name : curr->targets) { + if (name == target) noteFound(curr->value); + } + if (curr->default_ == target) noteFound(curr->value); + } + + static bool has(Expression* tree, Name target) { + if (!target.is()) return false; + BranchSeeker seeker(target); + seeker.walk(tree); + return seeker.found > 0; + } + + static Index count(Expression* tree, Name target) { + if (!target.is()) return 0; + BranchSeeker seeker(target); + seeker.walk(tree); + return seeker.found; + } + + static bool hasNamed(Expression* tree, Name target) { + if (!target.is()) return false; + BranchSeeker seeker(target); + seeker.named = true; + seeker.walk(tree); + return seeker.found > 0; + } + + static Index countNamed(Expression* tree, Name target) { + if (!target.is()) return 0; + BranchSeeker seeker(target); + seeker.named = true; + seeker.walk(tree); + return seeker.found; + } +}; + } // namespace BranchUtils } // namespace wasm diff --git a/src/ast/effects.h b/src/ast/effects.h new file mode 100644 index 000000000..a7a5d8fb2 --- /dev/null +++ b/src/ast/effects.h @@ -0,0 +1,215 @@ +/* + * 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_ast_effects_h +#define wasm_ast_effects_h + +namespace wasm { + +// Look for side effects, including control flow +// TODO: optimize + +struct EffectAnalyzer : public PostWalker<EffectAnalyzer> { + EffectAnalyzer(PassOptions& passOptions, Expression *ast = nullptr) { + ignoreImplicitTraps = passOptions.ignoreImplicitTraps; + debugInfo = passOptions.debugInfo; + if (ast) analyze(ast); + } + + bool ignoreImplicitTraps; + bool debugInfo; + + void analyze(Expression *ast) { + breakNames.clear(); + walk(ast); + // if we are left with breaks, they are external + if (breakNames.size() > 0) branches = true; + } + + bool branches = false; // branches out of this expression + bool calls = false; + std::set<Index> localsRead; + std::set<Index> localsWritten; + std::set<Name> globalsRead; + 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, and we + // also allow reordering them with other effects + // (so a trap may occur later or earlier, if it is + // going to occur anyhow), but we can't remove them, + // they count as side effects + + bool accessesLocal() { return localsRead.size() + localsWritten.size() > 0; } + bool accessesGlobal() { return globalsRead.size() + globalsWritten.size() > 0; } + bool accessesMemory() { return calls || readsMemory || writesMemory; } + bool hasSideEffects() { return calls || localsWritten.size() > 0 || writesMemory || branches || globalsWritten.size() > 0 || implicitTrap; } + bool hasAnything() { return branches || calls || accessesLocal() || readsMemory || writesMemory || accessesGlobal() || implicitTrap; } + + // 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(EffectAnalyzer& other) { + if (branches || other.branches + || ((writesMemory || calls) && other.accessesMemory()) + || (accessesMemory() && (other.writesMemory || other.calls))) { + 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.branches) || (other.implicitTrap && branches)) { + return true; + } + return false; + } + + void mergeIn(EffectAnalyzer& other) { + branches = branches || other.branches; + calls = calls || other.calls; + readsMemory = readsMemory || other.readsMemory; + writesMemory = writesMemory || other.writesMemory; + 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 + bool checkPre(Expression* curr) { + if (curr->is<Loop>()) { + branches = true; + return true; + } + return false; + } + + bool checkPost(Expression* curr) { + visit(curr); + if (curr->is<Loop>()) { + branches = true; + } + return hasAnything(); + } + + std::set<Name> breakNames; + + 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 visitBlock(Block* curr) { + if (curr->name.is()) breakNames.erase(curr->name); // these were internal breaks + } + void visitLoop(Loop* curr) { + if (curr->name.is()) breakNames.erase(curr->name); // these were internal breaks + } + + void visitCall(Call *curr) { calls = true; } + void visitCallImport(CallImport *curr) { + calls = true; + if (debugInfo) { + // debugInfo call imports must be preserved very strongly, do not + // move code around them + 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) { + readsMemory = true; + if (!ignoreImplicitTraps) implicitTrap = true; + } + void visitStore(Store *curr) { + writesMemory = true; + if (!ignoreImplicitTraps) implicitTrap = true; + } + 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; + } + 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; + } + default: {} + } + } + } + void visitReturn(Return *curr) { branches = true; } + void visitHost(Host *curr) { calls = true; } + void visitUnreachable(Unreachable *curr) { branches = true; } +}; + +} // namespace wasm + +#endif // wasm_ast_effects_h + diff --git a/src/ast_utils.h b/src/ast_utils.h index 83818daa8..253da8050 100644 --- a/src/ast_utils.h +++ b/src/ast_utils.h @@ -25,247 +25,6 @@ namespace wasm { -// Finds if there are breaks targeting a name. Note that since names are -// unique in our IR, we just need to look for the name, and do not need -// to analyze scoping. -struct BreakSeeker : public PostWalker<BreakSeeker> { - Name target; - Index found; - WasmType valueType; - - BreakSeeker(Name target) : target(target), found(0) {} - - void noteFound(Expression* value) { - found++; - if (found == 1) valueType = unreachable; - if (!value) valueType = none; - else if (value->type != unreachable) valueType = value->type; - } - - void visitBreak(Break *curr) { - // ignore an unreachable break - if (curr->condition && curr->condition->type == unreachable) return; - if (curr->value && curr->value->type == unreachable) return; - // check the break - if (curr->name == target) noteFound(curr->value); - } - - void visitSwitch(Switch *curr) { - // ignore an unreachable switch - if (curr->condition->type == unreachable) return; - if (curr->value && curr->value->type == unreachable) return; - // check the switch - for (auto name : curr->targets) { - if (name == target) noteFound(curr->value); - } - if (curr->default_ == target) noteFound(curr->value); - } - - static bool has(Expression* tree, Name target) { - if (!target.is()) return false; - BreakSeeker breakSeeker(target); - breakSeeker.walk(tree); - return breakSeeker.found > 0; - } - - static Index count(Expression* tree, Name target) { - if (!target.is()) return 0; - BreakSeeker breakSeeker(target); - breakSeeker.walk(tree); - return breakSeeker.found; - } -}; - -// Look for side effects, including control flow -// TODO: optimize - -struct EffectAnalyzer : public PostWalker<EffectAnalyzer> { - EffectAnalyzer(PassOptions& passOptions, Expression *ast = nullptr) { - ignoreImplicitTraps = passOptions.ignoreImplicitTraps; - debugInfo = passOptions.debugInfo; - if (ast) analyze(ast); - } - - bool ignoreImplicitTraps; - bool debugInfo; - - void analyze(Expression *ast) { - breakNames.clear(); - walk(ast); - // if we are left with breaks, they are external - if (breakNames.size() > 0) branches = true; - } - - bool branches = false; // branches out of this expression - bool calls = false; - std::set<Index> localsRead; - std::set<Index> localsWritten; - std::set<Name> globalsRead; - 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, and we - // also allow reordering them with other effects - // (so a trap may occur later or earlier, if it is - // going to occur anyhow), but we can't remove them, - // they count as side effects - - bool accessesLocal() { return localsRead.size() + localsWritten.size() > 0; } - bool accessesGlobal() { return globalsRead.size() + globalsWritten.size() > 0; } - bool accessesMemory() { return calls || readsMemory || writesMemory; } - bool hasSideEffects() { return calls || localsWritten.size() > 0 || writesMemory || branches || globalsWritten.size() > 0 || implicitTrap; } - bool hasAnything() { return branches || calls || accessesLocal() || readsMemory || writesMemory || accessesGlobal() || implicitTrap; } - - // 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(EffectAnalyzer& other) { - if (branches || other.branches - || ((writesMemory || calls) && other.accessesMemory()) - || (accessesMemory() && (other.writesMemory || other.calls))) { - 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.branches) || (other.implicitTrap && branches)) { - return true; - } - return false; - } - - void mergeIn(EffectAnalyzer& other) { - branches = branches || other.branches; - calls = calls || other.calls; - readsMemory = readsMemory || other.readsMemory; - writesMemory = writesMemory || other.writesMemory; - 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 - bool checkPre(Expression* curr) { - if (curr->is<Loop>()) { - branches = true; - return true; - } - return false; - } - - bool checkPost(Expression* curr) { - visit(curr); - if (curr->is<Loop>()) { - branches = true; - } - return hasAnything(); - } - - std::set<Name> breakNames; - - 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 visitBlock(Block* curr) { - if (curr->name.is()) breakNames.erase(curr->name); // these were internal breaks - } - void visitLoop(Loop* curr) { - if (curr->name.is()) breakNames.erase(curr->name); // these were internal breaks - } - - void visitCall(Call *curr) { calls = true; } - void visitCallImport(CallImport *curr) { - calls = true; - if (debugInfo) { - // debugInfo call imports must be preserved very strongly, do not - // move code around them - 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) { - readsMemory = true; - if (!ignoreImplicitTraps) implicitTrap = true; - } - void visitStore(Store *curr) { - writesMemory = true; - if (!ignoreImplicitTraps) implicitTrap = true; - } - 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; - } - 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; - } - default: {} - } - } - } - void visitReturn(Return *curr) { branches = true; } - void visitHost(Host *curr) { calls = true; } - void visitUnreachable(Unreachable *curr) { branches = true; } -}; - // Measure the size of an AST struct Measurer : public PostWalker<Measurer, UnifiedExpressionVisitor<Measurer>> { @@ -303,7 +62,7 @@ struct ExpressionAnalyzer { if (auto* br = curr->dynCast<Break>()) { if (!br->condition) return true; } else if (auto* block = curr->dynCast<Block>()) { - if (block->list.size() > 0 && obviouslyDoesNotFlowOut(block->list.back()) && !BreakSeeker::has(block, block->name)) return true; + if (block->list.size() > 0 && obviouslyDoesNotFlowOut(block->list.back()) && !BranchUtils::BranchSeeker::has(block, block->name)) return true; } return false; } diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp index 83d0e155f..dfdca516f 100644 --- a/src/binaryen-c.cpp +++ b/src/binaryen-c.cpp @@ -30,6 +30,7 @@ #include "wasm-s-parser.h" #include "wasm-validator.h" #include "cfg/Relooper.h" +#include "ast_utils.h" #include "shell-interface.h" using namespace wasm; diff --git a/src/passes/CoalesceLocals.cpp b/src/passes/CoalesceLocals.cpp index fb81a5981..b36542a97 100644 --- a/src/passes/CoalesceLocals.cpp +++ b/src/passes/CoalesceLocals.cpp @@ -168,9 +168,13 @@ struct CoalesceLocals : public WalkerPass<CFGWalker<CoalesceLocals, Visitor<Coal static void doVisitSetLocal(CoalesceLocals* self, Expression** currp) { auto* curr = (*currp)->cast<SetLocal>(); - // if in unreachable code, ignore + // if in unreachable code, we don't need the tee (but might need the value, if it has side effects) if (!self->currBasicBlock) { - *currp = Builder(*self->getModule()).replaceWithIdenticalType(curr); + if (curr->isTee()) { + *currp = curr->value; + } else { + *currp = Builder(*self->getModule()).makeDrop(curr->value); + } return; } self->currBasicBlock->contents.actions.emplace_back(Action::Set, curr->index, currp); diff --git a/src/passes/CodePushing.cpp b/src/passes/CodePushing.cpp index 2876228ee..e73794f5a 100644 --- a/src/passes/CodePushing.cpp +++ b/src/passes/CodePushing.cpp @@ -21,8 +21,8 @@ #include <wasm.h> #include <pass.h> -#include <ast_utils.h> #include <wasm-builder.h> +#include <ast/effects.h> namespace wasm { diff --git a/src/passes/DeadCodeElimination.cpp b/src/passes/DeadCodeElimination.cpp index 209180e23..321bc0f9a 100644 --- a/src/passes/DeadCodeElimination.cpp +++ b/src/passes/DeadCodeElimination.cpp @@ -30,9 +30,9 @@ #include <wasm.h> #include <pass.h> -#include <ast_utils.h> #include <wasm-builder.h> #include <ast/block-utils.h> +#include <ast/branch-utils.h> #include <ast/type-updating.h> namespace wasm { @@ -184,7 +184,7 @@ struct DeadCodeElimination : public WalkerPass<PostWalker<DeadCodeElimination>> if (curr->name.is()) { reachableBreaks.erase(curr->name); } - if (isUnreachable(curr->body) && !BreakSeeker::has(curr->body, curr->name)) { + if (isUnreachable(curr->body) && !BranchUtils::BranchSeeker::hasNamed(curr->body, curr->name)) { replaceCurrent(curr->body); return; } diff --git a/src/passes/LocalCSE.cpp b/src/passes/LocalCSE.cpp index 6d48a1107..a3e0dff76 100644 --- a/src/passes/LocalCSE.cpp +++ b/src/passes/LocalCSE.cpp @@ -29,7 +29,7 @@ #include <wasm-builder.h> #include <wasm-traversal.h> #include <pass.h> -#include <ast_utils.h> +#include <ast/effects.h> #include <ast/hashed.h> namespace wasm { diff --git a/src/passes/MergeBlocks.cpp b/src/passes/MergeBlocks.cpp index 1ec8843d6..2c983d991 100644 --- a/src/passes/MergeBlocks.cpp +++ b/src/passes/MergeBlocks.cpp @@ -63,8 +63,9 @@ #include <wasm.h> #include <pass.h> -#include <ast_utils.h> #include <wasm-builder.h> +#include <ast_utils.h> +#include <ast/effects.h> namespace wasm { @@ -121,6 +122,11 @@ struct BreakValueDropper : public ControlFlowWalker<BreakValueDropper> { if (curr->value && curr->name == origin) { Builder builder(*getModule()); auto* value = curr->value; + if (value->type == unreachable) { + // the break isn't even reached + replaceCurrent(value); + return; + } curr->value = nullptr; curr->finalize(); replaceCurrent(builder.makeSequence(builder.makeDrop(value), curr)); @@ -129,7 +135,8 @@ struct BreakValueDropper : public ControlFlowWalker<BreakValueDropper> { void visitDrop(Drop* curr) { // if we dropped a br_if whose value we removed, then we are now dropping a (block (drop value) (br_if)) with type none, which does not need a drop - if (curr->value->type == none) { + // likewise, unreachable does not need to be dropped, so we just leave drops of concrete values + if (!isConcreteWasmType(curr->value->type)) { replaceCurrent(curr->value); } } diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 0e7c34564..d1b419a06 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -26,8 +26,9 @@ #include <support/threads.h> #include <ast_utils.h> #include <ast/cost.h> -#include <ast/properties.h> +#include <ast/effects.h> #include <ast/manipulation.h> +#include <ast/properties.h> namespace wasm { diff --git a/src/passes/Precompute.cpp b/src/passes/Precompute.cpp index e06103c11..122501de9 100644 --- a/src/passes/Precompute.cpp +++ b/src/passes/Precompute.cpp @@ -100,6 +100,7 @@ struct Precompute : public WalkerPass<PostWalker<Precompute, UnifiedExpressionVi if (ret->value) { if (auto* value = ret->value->dynCast<Const>()) { value->value = flow.value; + value->finalize(); return; } } @@ -117,12 +118,13 @@ struct Precompute : public WalkerPass<PostWalker<Precompute, UnifiedExpressionVi if (auto* br = curr->dynCast<Break>()) { br->name = flow.breakTo; br->condition = nullptr; - br->finalize(); // if we removed a condition, the type may change if (flow.value.type != none) { // reuse a const value if there is one if (br->value) { if (auto* value = br->value->dynCast<Const>()) { value->value = flow.value; + value->finalize(); + br->finalize(); return; } } @@ -130,6 +132,7 @@ struct Precompute : public WalkerPass<PostWalker<Precompute, UnifiedExpressionVi } else { br->value = nullptr; } + br->finalize(); } else { Builder builder(*getModule()); replaceCurrent(builder.makeBreak(flow.breakTo, flow.value.type != none ? builder.makeConst(flow.value) : nullptr)); diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp index 1fa996ae6..b725de901 100644 --- a/src/passes/RemoveUnusedBrs.cpp +++ b/src/passes/RemoveUnusedBrs.cpp @@ -21,6 +21,8 @@ #include <wasm.h> #include <pass.h> #include <ast_utils.h> +#include <ast/branch-utils.h> +#include <ast/effects.h> #include <wasm-builder.h> namespace wasm { @@ -257,7 +259,7 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> { // so only do it if it looks useful, which it definitely is if // (a) $somewhere is straight out (so the br out vanishes), and // (b) this br_if is the only branch to that block (so the block will vanish) - if (brIf->name == block->name && BreakSeeker::count(block, block->name) == 1) { + if (brIf->name == block->name && BranchUtils::BranchSeeker::countNamed(block, block->name) == 1) { // note that we could drop the last element here, it is a br we know for sure is removable, // but telling stealSlice to steal all to the end is more efficient, it can just truncate. list[i] = builder.makeIf(brIf->condition, builder.makeBreak(brIf->name), builder.stealSlice(block, i + 1, list.size())); @@ -447,7 +449,7 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> { auto* br = list[0]->dynCast<Break>(); if (br && br->condition && br->name == curr->name) { assert(!br->value); // can't, it would be dropped or last in the block - if (BreakSeeker::count(curr, curr->name) == 1) { + if (BranchUtils::BranchSeeker::countNamed(curr, curr->name) == 1) { // no other breaks to that name, so we can do this Builder builder(*getModule()); replaceCurrent(builder.makeIf( diff --git a/src/passes/SimplifyLocals.cpp b/src/passes/SimplifyLocals.cpp index a9e9de34b..2d4a02337 100644 --- a/src/passes/SimplifyLocals.cpp +++ b/src/passes/SimplifyLocals.cpp @@ -45,8 +45,8 @@ #include <wasm-builder.h> #include <wasm-traversal.h> #include <pass.h> -#include <ast_utils.h> #include <ast/count.h> +#include <ast/effects.h> #include <ast/manipulation.h> namespace wasm { @@ -64,6 +64,7 @@ struct SetLocalRemover : public PostWalker<SetLocalRemover> { } else { Drop* drop = ExpressionManipulator::convert<SetLocal, Drop>(curr); drop->value = value; + drop->finalize(); } } } @@ -268,6 +269,7 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals>> auto* previousValue = previous->value; Drop* drop = ExpressionManipulator::convert<SetLocal, Drop>(previous); drop->value = previousValue; + drop->finalize(); self->sinkables.erase(found); self->anotherCycle = true; } diff --git a/src/passes/Vacuum.cpp b/src/passes/Vacuum.cpp index 4e47ad9a3..40f4a6e59 100644 --- a/src/passes/Vacuum.cpp +++ b/src/passes/Vacuum.cpp @@ -20,9 +20,9 @@ #include <wasm.h> #include <pass.h> -#include <ast_utils.h> #include <wasm-builder.h> #include <ast/block-utils.h> +#include <ast/effects.h> #include <ast/type-updating.h> namespace wasm { @@ -49,6 +49,8 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> { // returns nullptr if curr is dead, curr if it must stay as is, or another node if it can be replaced Expression* optimize(Expression* curr, bool resultUsed) { + // an unreachable node must not be changed + if (curr->type == unreachable) return curr; while (1) { switch (curr->_id) { case Expression::Id::NopId: return nullptr; // never needed @@ -71,7 +73,9 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> { case Expression::Id::UnreachableId: return curr; // always needed case Expression::Id::LoadId: { - if (!resultUsed) { + // it is ok to remove a load if the result is not used, and it has no + // side effects (the load itself may trap, if we are not ignoring such things) + if (!resultUsed && !EffectAnalyzer(getPassOptions(), curr).hasSideEffects()) { return curr->cast<Load>()->ptr; } return curr; @@ -89,8 +93,14 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> { if (resultUsed) { return curr; // used, keep it } - // for unary, binary, and select, we need to check their arguments for side effects + // for unary, binary, and select, we need to check their arguments for side effects, + // as well as the node itself, as some unaries and binaries have implicit traps if (auto* unary = curr->dynCast<Unary>()) { + EffectAnalyzer tester(getPassOptions()); + tester.visitUnary(unary); + if (tester.hasSideEffects()) { + return curr; + } if (EffectAnalyzer(getPassOptions(), unary->value).hasSideEffects()) { curr = unary->value; continue; @@ -98,6 +108,11 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> { return nullptr; } } else if (auto* binary = curr->dynCast<Binary>()) { + EffectAnalyzer tester(getPassOptions()); + tester.visitBinary(binary); + if (tester.hasSideEffects()) { + return curr; + } if (EffectAnalyzer(getPassOptions(), binary->left).hasSideEffects()) { if (EffectAnalyzer(getPassOptions(), binary->right).hasSideEffects()) { return curr; // leave them @@ -202,9 +217,13 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> { Expression* child; if (value->value.getInteger()) { child = curr->ifTrue; + if (curr->ifFalse) { + typeUpdater.noteRecursiveRemoval(curr->ifFalse); + } } else { if (curr->ifFalse) { child = curr->ifFalse; + typeUpdater.noteRecursiveRemoval(curr->ifTrue); } else { ExpressionManipulator::nop(curr); return; @@ -270,10 +289,11 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> { // we may be able to remove this, if there are no brs bool canPop = true; if (block->name.is()) { - BreakSeeker breakSeeker(block->name); + BranchUtils::BranchSeeker seeker(block->name); + seeker.named = true; Expression* temp = block; - breakSeeker.walk(temp); - if (breakSeeker.found && breakSeeker.valueType != none) { + seeker.walk(temp); + if (seeker.found && seeker.valueType != none) { canPop = false; } } diff --git a/src/wasm-binary.h b/src/wasm-binary.h index 6b984642c..ca3d69989 100644 --- a/src/wasm-binary.h +++ b/src/wasm-binary.h @@ -30,7 +30,6 @@ #include "asmjs/shared-constants.h" #include "asm_v_wasm.h" #include "wasm-builder.h" -#include "ast_utils.h" #include "parsing.h" #include "wasm-validator.h" diff --git a/src/wasm-validator.h b/src/wasm-validator.h index 24affdb44..2ec530476 100644 --- a/src/wasm-validator.h +++ b/src/wasm-validator.h @@ -72,8 +72,9 @@ struct WasmValidator : public PostWalker<WasmValidator> { BreakInfo(WasmType type, Index arity) : type(type), arity(arity) {} }; - std::map<Name, std::vector<Expression*>> breakTargets; // more than one block/loop may use a label name, so stack them + std::map<Name, Expression*> breakTargets; std::map<Expression*, BreakInfo> breakInfos; + std::set<Name> namedBreakTargets; // even breaks not taken must not be named if they go to a place that does not exist WasmType returnType = unreachable; // type used in returns @@ -105,14 +106,14 @@ public: static void visitPreBlock(WasmValidator* self, Expression** currp) { auto* curr = (*currp)->cast<Block>(); - if (curr->name.is()) self->breakTargets[curr->name].push_back(curr); + if (curr->name.is()) self->breakTargets[curr->name] = curr; } void visitBlock(Block *curr); static void visitPreLoop(WasmValidator* self, Expression** currp) { auto* curr = (*currp)->cast<Loop>(); - if (curr->name.is()) self->breakTargets[curr->name].push_back(curr); + if (curr->name.is()) self->breakTargets[curr->name] = curr; } void visitLoop(Loop *curr); diff --git a/src/wasm.h b/src/wasm.h index 1f9e1c7af..e5b1eaea3 100644 --- a/src/wasm.h +++ b/src/wasm.h @@ -464,6 +464,8 @@ public: Literal value; Const* set(Literal value_); + + void finalize(); }; class Unary : public SpecificExpression<Expression::UnaryId> { diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp index efbd82e8b..2df7f2e26 100644 --- a/src/wasm/wasm-binary.cpp +++ b/src/wasm/wasm-binary.cpp @@ -14,10 +14,11 @@ * limitations under the License. */ -#include "wasm-binary.h" - #include <fstream> + #include "support/bits.h" +#include "wasm-binary.h" +#include "ast/branch-utils.h" namespace wasm { @@ -544,7 +545,7 @@ void WasmBinaryWriter::recurse(Expression*& curr) { } static bool brokenTo(Block* block) { - return block->name.is() && BreakSeeker::has(block, block->name); + return block->name.is() && BranchUtils::BranchSeeker::has(block, block->name); } void WasmBinaryWriter::visitBlock(Block *curr) { diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp index 2fede28fc..e991f71de 100644 --- a/src/wasm/wasm-s-parser.cpp +++ b/src/wasm/wasm-s-parser.cpp @@ -22,7 +22,7 @@ #include "asm_v_wasm.h" #include "asmjs/shared-constants.h" -#include "ast_utils.h" +#include "ast/branch-utils.h" #include "shared-constants.h" #include "wasm-binary.h" #include "wasm-builder.h" @@ -1262,7 +1262,7 @@ Expression* SExpressionWasmBuilder::makeIf(Element& s) { ret->finalize(type); nameMapper.popLabelName(label); // create a break target if we must - if (BreakSeeker::has(ret, label)) { + if (BranchUtils::BranchSeeker::hasNamed(ret, label)) { auto* block = allocator.alloc<Block>(); block->name = label; block->list.push_back(ret); diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp index 4c02fe6d3..c1f44a68b 100644 --- a/src/wasm/wasm-validator.cpp +++ b/src/wasm/wasm-validator.cpp @@ -57,7 +57,8 @@ void WasmValidator::visitBlock(Block *curr) { } } } - breakTargets[curr->name].pop_back(); + breakTargets.erase(curr->name); + namedBreakTargets.erase(curr->name); } if (curr->list.size() > 1) { for (Index i = 0; i < curr->list.size() - 1; i++) { @@ -88,7 +89,8 @@ void WasmValidator::visitBlock(Block *curr) { void WasmValidator::visitLoop(Loop *curr) { if (curr->name.is()) { noteLabelName(curr->name); - breakTargets[curr->name].pop_back(); + breakTargets.erase(curr->name); + namedBreakTargets.erase(curr->name); if (breakInfos.count(curr) > 0) { auto& info = breakInfos[curr]; shouldBeEqual(info.arity, Index(0), curr, "breaks to a loop cannot pass a value"); @@ -120,6 +122,11 @@ void WasmValidator::visitIf(If *curr) { } void WasmValidator::noteBreak(Name name, Expression* value, Expression* curr) { + if (!BranchUtils::isBranchTaken(curr)) { + // if not actually taken, just note the name + namedBreakTargets.insert(name); + return; + } WasmType valueType = none; Index arity = 0; if (value) { @@ -127,8 +134,8 @@ void WasmValidator::noteBreak(Name name, Expression* value, Expression* curr) { shouldBeUnequal(valueType, none, curr, "breaks must have a valid value"); arity = 1; } - if (!shouldBeTrue(breakTargets[name].size() > 0, curr, "all break targets must be valid")) return; - auto* target = breakTargets[name].back(); + if (!shouldBeTrue(breakTargets.count(name) > 0, curr, "all break targets must be valid")) return; + auto* target = breakTargets[name]; if (breakInfos.count(target) == 0) { breakInfos[target] = BreakInfo(valueType, arity); } else { @@ -146,23 +153,17 @@ void WasmValidator::noteBreak(Name name, Expression* value, Expression* curr) { } } void WasmValidator::visitBreak(Break *curr) { - // note breaks (that are actually taken) - if (BranchUtils::isBranchTaken(curr)) { - noteBreak(curr->name, curr->value, curr); - } + noteBreak(curr->name, curr->value, curr); if (curr->condition) { shouldBeTrue(curr->condition->type == unreachable || curr->condition->type == i32, curr, "break condition must be i32"); } } void WasmValidator::visitSwitch(Switch *curr) { - // note breaks (that are actually taken) - if (BranchUtils::isBranchTaken(curr)) { - for (auto& target : curr->targets) { - noteBreak(target, curr->value, curr); - } - noteBreak(curr->default_, curr->value, curr); + for (auto& target : curr->targets) { + noteBreak(target, curr->value, curr); } + noteBreak(curr->default_, curr->value, curr); shouldBeTrue(curr->condition->type == unreachable || curr->condition->type == i32, curr, "br_table condition must be i32"); } void WasmValidator::visitCall(Call *curr) { @@ -493,7 +494,7 @@ void WasmValidator::visitGlobal(Global* curr) { shouldBeTrue(curr->init != nullptr, curr->name, "global init must be non-null"); shouldBeTrue(curr->init->is<Const>() || curr->init->is<GetGlobal>(), curr->name, "global init must be valid"); if (!shouldBeEqual(curr->type, curr->init->type, curr->init, "global init must have correct type")) { - std::cerr << "(on global " << curr->name << '\n'; + std::cerr << "(on global " << curr->name << ")\n"; } } @@ -506,6 +507,9 @@ void WasmValidator::visitFunction(Function *curr) { if (returnType != unreachable) { shouldBeEqual(curr->result, returnType, curr->body, "function result must match, if function has returns"); } + if (!shouldBeTrue(namedBreakTargets.empty(), curr->body, "all named break targets must exist (even if not taken)")) { + std::cerr << "(on label " << *namedBreakTargets.begin() << ")\n"; + } returnType = unreachable; labelNames.clear(); } diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp index d331ba3a2..4f5f46f0a 100644 --- a/src/wasm/wasm.cpp +++ b/src/wasm/wasm.cpp @@ -16,7 +16,7 @@ #include "wasm.h" #include "wasm-traversal.h" -#include "ast_utils.h" +#include "ast/branch-utils.h" namespace wasm { @@ -175,7 +175,7 @@ static void handleUnreachable(Block* block) { for (auto* child : block->list) { if (child->type == unreachable) { // there is an unreachable child, so we are unreachable, unless we have a break - BreakSeeker seeker(block->name); + BranchUtils::BranchSeeker seeker(block->name); Expression* expr = block; seeker.walk(expr); if (!seeker.found) { @@ -324,6 +324,7 @@ bool SetLocal::isTee() { void SetLocal::setTee(bool is) { if (is) type = value->type; else type = none; + finalize(); // type may need to be unreachable } void SetLocal::finalize() { @@ -371,6 +372,10 @@ Const* Const::set(Literal value_) { return this; } +void Const::finalize() { + type = value.type; +} + bool Unary::isRelational() { return op == EqZInt32 || op == EqZInt64; } diff --git a/test/emcc_hello_world.fromasm b/test/emcc_hello_world.fromasm index a7ad859f6..10d0f69e9 100644 --- a/test/emcc_hello_world.fromasm +++ b/test/emcc_hello_world.fromasm @@ -2819,17 +2819,21 @@ ) (i32.const 10) ) - (set_local $6 - (i32.add - (get_local $3) - (i32.shl + (drop + (i32.load offset=4 + (tee_local $6 (i32.add - (i32.load8_s - (get_local $6) + (get_local $3) + (i32.shl + (i32.add + (i32.load8_s + (get_local $6) + ) + (i32.const -48) + ) + (i32.const 3) ) - (i32.const -48) ) - (i32.const 3) ) ) ) @@ -3157,17 +3161,21 @@ ) (i32.const 10) ) - (set_local $6 - (i32.add - (get_local $3) - (i32.shl + (drop + (i32.load offset=4 + (tee_local $6 (i32.add - (i32.load8_s - (get_local $6) + (get_local $3) + (i32.shl + (i32.add + (i32.load8_s + (get_local $6) + ) + (i32.const -48) + ) + (i32.const 3) ) - (i32.const -48) ) - (i32.const 3) ) ) ) @@ -3885,8 +3893,12 @@ ) (br $__rjti$4) ) - (set_local $5 - (get_local $19) + (drop + (i32.load offset=4 + (tee_local $5 + (get_local $19) + ) + ) ) (i32.store8 (get_local $40) @@ -3935,8 +3947,12 @@ ) (br $__rjti$5) ) - (set_local $5 - (get_local $19) + (drop + (i32.load offset=4 + (tee_local $5 + (get_local $19) + ) + ) ) (i32.store (get_local $41) @@ -3993,6 +4009,11 @@ (get_global $tempDoublePtr) (get_local $15) ) + (drop + (i32.load + (get_global $tempDoublePtr) + ) + ) (set_local $31 (if (result i32) (i32.lt_s @@ -4045,6 +4066,11 @@ (get_global $tempDoublePtr) (get_local $15) ) + (drop + (i32.load + (get_global $tempDoublePtr) + ) + ) (set_local $7 (block $do-once49 (result i32) (if (result i32) diff --git a/test/emcc_hello_world.fromasm.clamp b/test/emcc_hello_world.fromasm.clamp index 80a1f92b2..af2b8a467 100644 --- a/test/emcc_hello_world.fromasm.clamp +++ b/test/emcc_hello_world.fromasm.clamp @@ -2843,17 +2843,21 @@ ) (i32.const 10) ) - (set_local $6 - (i32.add - (get_local $3) - (i32.shl + (drop + (i32.load offset=4 + (tee_local $6 (i32.add - (i32.load8_s - (get_local $6) + (get_local $3) + (i32.shl + (i32.add + (i32.load8_s + (get_local $6) + ) + (i32.const -48) + ) + (i32.const 3) ) - (i32.const -48) ) - (i32.const 3) ) ) ) @@ -3181,17 +3185,21 @@ ) (i32.const 10) ) - (set_local $6 - (i32.add - (get_local $3) - (i32.shl + (drop + (i32.load offset=4 + (tee_local $6 (i32.add - (i32.load8_s - (get_local $6) + (get_local $3) + (i32.shl + (i32.add + (i32.load8_s + (get_local $6) + ) + (i32.const -48) + ) + (i32.const 3) ) - (i32.const -48) ) - (i32.const 3) ) ) ) @@ -3909,8 +3917,12 @@ ) (br $__rjti$4) ) - (set_local $5 - (get_local $19) + (drop + (i32.load offset=4 + (tee_local $5 + (get_local $19) + ) + ) ) (i32.store8 (get_local $40) @@ -3959,8 +3971,12 @@ ) (br $__rjti$5) ) - (set_local $5 - (get_local $19) + (drop + (i32.load offset=4 + (tee_local $5 + (get_local $19) + ) + ) ) (i32.store (get_local $41) @@ -4017,6 +4033,11 @@ (get_global $tempDoublePtr) (get_local $15) ) + (drop + (i32.load + (get_global $tempDoublePtr) + ) + ) (set_local $31 (if (result i32) (i32.lt_s @@ -4069,6 +4090,11 @@ (get_global $tempDoublePtr) (get_local $15) ) + (drop + (i32.load + (get_global $tempDoublePtr) + ) + ) (set_local $7 (block $do-once49 (result i32) (if (result i32) diff --git a/test/emcc_hello_world.fromasm.imprecise b/test/emcc_hello_world.fromasm.imprecise index 65fda0e77..96344b09d 100644 --- a/test/emcc_hello_world.fromasm.imprecise +++ b/test/emcc_hello_world.fromasm.imprecise @@ -2763,17 +2763,21 @@ ) (i32.const 10) ) - (set_local $6 - (i32.add - (get_local $3) - (i32.shl + (drop + (i32.load offset=4 + (tee_local $6 (i32.add - (i32.load8_s - (get_local $6) + (get_local $3) + (i32.shl + (i32.add + (i32.load8_s + (get_local $6) + ) + (i32.const -48) + ) + (i32.const 3) ) - (i32.const -48) ) - (i32.const 3) ) ) ) @@ -3102,17 +3106,21 @@ ) (i32.const 10) ) - (set_local $6 - (i32.add - (get_local $3) - (i32.shl + (drop + (i32.load offset=4 + (tee_local $6 (i32.add - (i32.load8_s - (get_local $6) + (get_local $3) + (i32.shl + (i32.add + (i32.load8_s + (get_local $6) + ) + (i32.const -48) + ) + (i32.const 3) ) - (i32.const -48) ) - (i32.const 3) ) ) ) @@ -3830,8 +3838,12 @@ ) (br $__rjti$4) ) - (set_local $5 - (get_local $19) + (drop + (i32.load offset=4 + (tee_local $5 + (get_local $19) + ) + ) ) (i32.store8 (get_local $40) @@ -3880,8 +3892,12 @@ ) (br $__rjti$5) ) - (set_local $5 - (get_local $19) + (drop + (i32.load offset=4 + (tee_local $5 + (get_local $19) + ) + ) ) (i32.store (get_local $41) diff --git a/test/passes/coalesce-locals-learning.txt b/test/passes/coalesce-locals-learning.txt index 3bd04680d..2377c4051 100644 --- a/test/passes/coalesce-locals-learning.txt +++ b/test/passes/coalesce-locals-learning.txt @@ -108,11 +108,15 @@ ) (block $block (br $block) - (nop) (drop (i32.const 0) ) - (nop) + (drop + (i32.const 0) + ) + (drop + (i32.const -1) + ) ) (drop (get_local $0) diff --git a/test/passes/coalesce-locals.txt b/test/passes/coalesce-locals.txt index 8f2908153..f8dc3ef0f 100644 --- a/test/passes/coalesce-locals.txt +++ b/test/passes/coalesce-locals.txt @@ -6,6 +6,7 @@ (type $4 (func (param i32))) (type $FUNCSIG$i (func (result i32))) (type $FUNCSIG$vi (func (param i32))) + (type $7 (func (param i32) (result i32))) (import "env" "_emscripten_autodebug_i32" (func $_emscripten_autodebug_i32 (param i32 i32) (result i32))) (import "env" "get" (func $get (result i32))) (import "env" "set" (func $set (param i32))) @@ -112,11 +113,15 @@ ) (block $block (br $block) - (nop) (drop (i32.const 0) ) - (nop) + (drop + (i32.const 0) + ) + (drop + (i32.const -1) + ) ) (drop (get_local $0) @@ -902,37 +907,53 @@ (local $0 i32) (block $x (return) - (nop) + (drop + (i32.const 1) + ) + (drop + (i32.const 0) + ) (drop (i32.const 0) ) - (nop) ) (block $y (unreachable) - (nop) + (drop + (i32.const 1) + ) + (drop + (i32.const 0) + ) (drop (i32.const 0) ) - (nop) ) (block $z (br $z) - (nop) + (drop + (i32.const 1) + ) + (drop + (i32.const 0) + ) (drop (i32.const 0) ) - (nop) ) (block $z14 (br_table $z14 $z14 (i32.const 100) ) - (nop) + (drop + (i32.const 1) + ) + (drop + (i32.const 0) + ) (drop (i32.const 0) ) - (nop) ) ) (func $nop-in-unreachable (type $2) @@ -1083,4 +1104,12 @@ (br $top) ) ) + (func $tee_br (type $7) (param $0 i32) (result i32) + (block $b + (return + (br $b) + ) + ) + (i32.const 1) + ) ) diff --git a/test/passes/coalesce-locals.wast b/test/passes/coalesce-locals.wast index d6d499d36..336c75e0e 100644 --- a/test/passes/coalesce-locals.wast +++ b/test/passes/coalesce-locals.wast @@ -1075,4 +1075,14 @@ (br $top) ) ) + (func $tee_br (param $x i32) (result i32) + (block $b + (return + (tee_local $x + (br $b) + ) + ) + ) + (i32.const 1) + ) ) diff --git a/test/passes/merge-blocks.txt b/test/passes/merge-blocks.txt index 33f16785a..dd496df2f 100644 --- a/test/passes/merge-blocks.txt +++ b/test/passes/merge-blocks.txt @@ -1,6 +1,7 @@ (module (type $0 (func)) (type $1 (func (param i32))) + (type $2 (func (result i32))) (memory $0 0) (func $drop-block (type $0) (block $block @@ -75,4 +76,15 @@ ) ) ) + (func $drop-unreachable-br_if (type $2) (result i32) + (block $label$0 (result i32) + (block $label$2 + (drop + (br $label$0 + (i32.const 538976371) + ) + ) + ) + ) + ) ) diff --git a/test/passes/merge-blocks.wast b/test/passes/merge-blocks.wast index a61027778..4b2f248e2 100644 --- a/test/passes/merge-blocks.wast +++ b/test/passes/merge-blocks.wast @@ -53,5 +53,21 @@ ) ) ) + (func $drop-unreachable-br_if (result i32) + (block $label$0 (result i32) + (drop + (block $label$2 + (drop + (br_if $label$2 + (br $label$0 + (i32.const 538976371) + ) + (i32.const 1918987552) + ) + ) + ) + ) + ) + ) ) diff --git a/test/passes/precompute.txt b/test/passes/precompute.txt index c0dd8df0a..74e4989dc 100644 --- a/test/passes/precompute.txt +++ b/test/passes/precompute.txt @@ -2,6 +2,7 @@ (type $0 (func (param i32))) (type $1 (func (result i32))) (type $2 (func)) + (type $3 (func (result f64))) (memory $0 0) (func $x (type $0) (param $x i32) (call $x @@ -129,4 +130,31 @@ ) ) ) + (func $reuse-br-value (type $3) (result f64) + (block $label$0 (result f64) + (i32.store8 + (i32.const 1919623207) + (if (result i32) + (i32.const 1) + (block $label$2 + (drop + (i64.and + (i64.trunc_u/f32 + (f32.const 70847791997969805621592064) + ) + (i64.const 729618461987467893) + ) + ) + (br $label$0 + (f64.const 6.134856208230095e-154) + ) + ) + (i32.load offset=3 align=2 + (i32.const 169901344) + ) + ) + ) + (f64.const 4776014875438170098655851e156) + ) + ) ) diff --git a/test/passes/precompute.wast b/test/passes/precompute.wast index 84945f225..3eb2683bf 100644 --- a/test/passes/precompute.wast +++ b/test/passes/precompute.wast @@ -210,4 +210,43 @@ ) ) ) + (func $reuse-br-value (result f64) + (block $label$0 (result f64) + (i32.store8 + (i32.const 1919623207) + (if (result i32) + (i32.const 1) + (block $label$2 (result i32) + (drop + (i64.and + (i64.trunc_u/f32 + (f32.const 70847791997969805621592064) + ) + (i64.const 729618461987467893) + ) + ) + (br_if $label$2 + (i32.const 2049535349) + (f32.eq + (f32.demote/f64 + (f64.mul + (br_if $label$0 ;; this br is optimized, and br *and* values reused + (f64.const 6.134856208230095e-154) + (i32.const 690910817) + ) + (f64.const 1.515470884183969e-152) + ) + ) + (f32.const 66524025679377434935296) + ) + ) + ) + (i32.load offset=3 align=2 + (i32.const 169901344) + ) + ) + ) + (f64.const 4776014875438170098655851e156) + ) + ) ) diff --git a/test/passes/remove-unused-brs.txt b/test/passes/remove-unused-brs.txt index 62643ae00..07b4575ce 100644 --- a/test/passes/remove-unused-brs.txt +++ b/test/passes/remove-unused-brs.txt @@ -4,6 +4,7 @@ (type $2 (func (result i32))) (type $3 (func (param i32 i32) (result i32))) (type $4 (func (param i32 i32))) + (type $5 (func (param f32 i32 f32 i32 i32 f64 f32) (result i32))) (memory $0 256 256) (func $b0-yes (type $0) (param $i1 i32) (block $topmost @@ -975,4 +976,39 @@ ) ) ) + (func $untaken-brs-might-prevent-block-removal (type $5) (param $0 f32) (param $1 i32) (param $2 f32) (param $3 i32) (param $4 i32) (param $5 f64) (param $6 f32) (result i32) + (block $label$0 (result i32) + (block $label$1 + (br_if $label$1 + (i32.const 607395945) + ) + (br_if $label$1 + (unreachable.load16_s offset=3 align=1 + (select + (call $untaken-brs-might-prevent-block-removal + (f32.const 1.4904844647389837e-07) + (br_if $label$0 + (i32.store16 offset=4 align=1 + (i32.const 1900641) + (br $label$0 + (i32.const 1628075109) + ) + ) + (i32.const 1764950569) + ) + (f32.const 1.1910939690100655e-32) + (i32.const 1628057906) + (i32.const 859068982) + (f64.const 2.524518840347722e-258) + (f32.const -nan:0x40a63) + ) + (i32.const 688529440) + (i32.const 1751478890) + ) + ) + ) + ) + (i32.const 1935947830) + ) + ) ) diff --git a/test/passes/remove-unused-brs.wast b/test/passes/remove-unused-brs.wast index a573a385a..04ebdac33 100644 --- a/test/passes/remove-unused-brs.wast +++ b/test/passes/remove-unused-brs.wast @@ -866,5 +866,40 @@ ) ) ) + (func $untaken-brs-might-prevent-block-removal (param $0 f32) (param $1 i32) (param $2 f32) (param $3 i32) (param $4 i32) (param $5 f64) (param $6 f32) (result i32) + (block $label$0 (result i32) + (block $label$1 ;; this block has no taken brs, but we can't remove it without removing them first + (br_if $label$1 + (i32.const 607395945) + ) + (br_if $label$1 + (i32.load16_s offset=3 align=1 + (select + (call $untaken-brs-might-prevent-block-removal + (f32.const 1.4904844647389837e-07) + (br_if $label$0 + (i32.store16 offset=4 align=1 + (i32.const 1900641) + (br $label$0 + (i32.const 1628075109) + ) + ) + (i32.const 1764950569) + ) + (f32.const 1.1910939690100655e-32) + (i32.const 1628057906) + (i32.const 859068982) + (f64.const 2.524518840347722e-258) + (f32.const -nan:0x40a63) + ) + (i32.const 688529440) + (i32.const 1751478890) + ) + ) + ) + ) + (i32.const 1935947830) + ) + ) ) diff --git a/test/passes/simplify-locals-nostructure.txt b/test/passes/simplify-locals-nostructure.txt index 2502c4549..2cb942f43 100644 --- a/test/passes/simplify-locals-nostructure.txt +++ b/test/passes/simplify-locals-nostructure.txt @@ -62,4 +62,8 @@ (get_local $b) ) ) + (func $no-unreachable (type $0) + (local $x i32) + (unreachable) + ) ) diff --git a/test/passes/simplify-locals-nostructure.wast b/test/passes/simplify-locals-nostructure.wast index 33f891e61..548109237 100644 --- a/test/passes/simplify-locals-nostructure.wast +++ b/test/passes/simplify-locals-nostructure.wast @@ -28,5 +28,13 @@ ) (drop (get_local $b)) ) + (func $no-unreachable + (local $x i32) + (drop + (tee_local $x + (unreachable) + ) + ) + ) ) diff --git a/test/passes/simplify-locals.txt b/test/passes/simplify-locals.txt index 8c12c274a..2be81e8c6 100644 --- a/test/passes/simplify-locals.txt +++ b/test/passes/simplify-locals.txt @@ -866,4 +866,13 @@ ) ) ) + (func $drop-tee-unreachable (type $FUNCSIG$v) + (local $x i32) + (tee_local $x + (unreachable) + ) + (drop + (get_local $x) + ) + ) ) diff --git a/test/passes/simplify-locals.wast b/test/passes/simplify-locals.wast index 359620a18..534bd8883 100644 --- a/test/passes/simplify-locals.wast +++ b/test/passes/simplify-locals.wast @@ -860,4 +860,15 @@ ) (get_local $label) ) + (func $drop-tee-unreachable + (local $x i32) + (drop + (tee_local $x + (unreachable) + ) + ) + (drop + (get_local $x) + ) + ) ) diff --git a/test/passes/vacuum.txt b/test/passes/vacuum.txt index d1a388333..e07357296 100644 --- a/test/passes/vacuum.txt +++ b/test/passes/vacuum.txt @@ -5,6 +5,7 @@ (type $3 (func (result i32))) (type $4 (func (param i32 f64 i32 i32))) (type $FUNCSIG$i (func (result i32))) + (type $6 (func (result f64))) (import "env" "int" (func $int (result i32))) (global $Int i32 (i32.const 0)) (memory $0 256 256) @@ -28,16 +29,25 @@ (nop) ) (func $unary (type $2) (result f32) - (unreachable) + (f32.abs + (unreachable) + ) ) (func $binary (type $2) (result f32) (drop - (unreachable) + (f32.add + (unreachable) + (f32.const 3) + ) ) ) (func $select (type $3) (result i32) (drop - (unreachable) + (select + (unreachable) + (i32.const 4) + (i32.const 5) + ) ) ) (func $block-to-one (type $0) @@ -198,4 +208,69 @@ (local $2 i32) (nop) ) + (func $a (type $0) + (block $block + (i32.store + (i32.const 1) + (i32.const 2) + ) + (f64.div + (f64.const -nan:0xfffffffffa361) + (loop $label$1 + (br $label$1) + ) + ) + ) + ) + (func $leave-block-even-if-br-not-taken (type $6) (result f64) + (block $label$0 + (f64.store align=1 + (i32.const 879179022) + (br_if $label$0 + (loop $label$9 + (br $label$9) + ) + (i32.const 677803374) + ) + ) + ) + ) + (func $executed-if-in-block (type $0) + (unreachable) + ) + (func $executed-if-in-block2 (type $0) + (unreachable) + ) + (func $executed-if-in-block3 (type $0) + (block $label$0 + (br $label$0) + ) + (unreachable) + ) + (func $load-may-have-side-effects (type $3) (result i32) + (i64.ge_s + (block $block (result i64) + (drop + (i64.load32_s + (i32.const 678585719) + ) + ) + (i64.const 2912825531628789796) + ) + (i64.const 0) + ) + ) + (func $unary-binary-may-trap (type $0) + (drop + (i64.div_s + (i64.const -1) + (i64.const 729618461987467893) + ) + ) + (drop + (i64.trunc_u/f32 + (f32.const 70847791997969805621592064) + ) + ) + ) ) diff --git a/test/passes/vacuum.wast b/test/passes/vacuum.wast index c1a84d646..77ffabd60 100644 --- a/test/passes/vacuum.wast +++ b/test/passes/vacuum.wast @@ -509,4 +509,88 @@ ) ) ) + (func $a + (block + (i32.store (i32.const 1) (i32.const 2)) + (f64.div + (f64.const -nan:0xfffffffffa361) + (loop $label$1 ;; unreachable, so the div is too. keep + (br $label$1) + ) + ) + ) + ) + (func $leave-block-even-if-br-not-taken (result f64) + (block $label$0 (result f64) + (f64.store align=1 + (i32.const 879179022) + (br_if $label$0 + (loop $label$9 + (br $label$9) + ) + (i32.const 677803374) + ) + ) + (f64.const 2097914503796645752267195e31) + ) + ) + (func $executed-if-in-block + (block $label$0 + (if + (i32.const 170996275) + (unreachable) + (br $label$0) + ) + ) + (unreachable) + ) + (func $executed-if-in-block2 + (block $label$0 + (if + (i32.const 170996275) + (nop) + (br $label$0) + ) + ) + (unreachable) + ) + (func $executed-if-in-block3 + (block $label$0 + (if + (i32.const 170996275) + (br $label$0) + (nop) + ) + ) + (unreachable) + ) + (func $load-may-have-side-effects (result i32) + (i64.ge_s + (block (result i64) + (drop + (i64.eq + (i64.load32_s + (i32.const 678585719) + ) + (i64.const 8097879367757079605) + ) + ) + (i64.const 2912825531628789796) + ) + (i64.const 0) + ) + ) + (func $unary-binary-may-trap + (drop + (i64.div_s + (i64.const 70847791997969805621592064) + (i64.const 729618461987467893) + ) + ) + (drop + (i64.trunc_u/f32 + (f32.const 70847791997969805621592064) + ) + ) + ) ) diff --git a/test/passes/vacuum_ignore-implicit-traps.txt b/test/passes/vacuum_ignore-implicit-traps.txt new file mode 100644 index 000000000..e5ff28583 --- /dev/null +++ b/test/passes/vacuum_ignore-implicit-traps.txt @@ -0,0 +1,14 @@ +(module + (type $0 (func (result i32))) + (type $1 (func)) + (memory $0 0) + (func $load-would-normally-have-side-effects (type $0) (result i32) + (i64.ge_s + (i64.const 2912825531628789796) + (i64.const 0) + ) + ) + (func $unary-binary-may-trap (type $1) + (nop) + ) +) diff --git a/test/passes/vacuum_ignore-implicit-traps.wast b/test/passes/vacuum_ignore-implicit-traps.wast new file mode 100644 index 000000000..21e87e10c --- /dev/null +++ b/test/passes/vacuum_ignore-implicit-traps.wast @@ -0,0 +1,32 @@ +(module + (func $load-would-normally-have-side-effects (result i32) + (i64.ge_s + (block (result i64) + (drop + (i64.eq + (i64.load32_s + (i32.const 678585719) + ) + (i64.const 8097879367757079605) + ) + ) + (i64.const 2912825531628789796) + ) + (i64.const 0) + ) + ) + (func $unary-binary-may-trap + (drop + (i64.div_s + (i64.const 70847791997969805621592064) + (i64.const 729618461987467893) + ) + ) + (drop + (i64.trunc_u/f32 + (f32.const 70847791997969805621592064) + ) + ) + ) +) + diff --git a/test/wasm-only.fromasm b/test/wasm-only.fromasm index 6ac8c0ef1..a746c45e3 100644 --- a/test/wasm-only.fromasm +++ b/test/wasm-only.fromasm @@ -26,7 +26,116 @@ (export "illegalResult" (func $legalstub$result)) (export "keepAlive" (func $keepAlive)) (func $loads - (nop) + (drop + (i32.load8_s + (i32.const 100) + ) + ) + (drop + (i32.load8_s + (i32.const 101) + ) + ) + (drop + (i32.load16_s + (i32.const 102) + ) + ) + (drop + (i32.load16_s + (i32.const 103) + ) + ) + (drop + (i32.load16_s align=1 + (i32.const 104) + ) + ) + (drop + (i32.load16_s + (i32.const 105) + ) + ) + (drop + (i32.load + (i32.const 106) + ) + ) + (drop + (i32.load + (i32.const 107) + ) + ) + (drop + (i32.load align=1 + (i32.const 108) + ) + ) + (drop + (i32.load align=2 + (i32.const 109) + ) + ) + (drop + (i32.load + (i32.const 110) + ) + ) + (drop + (f32.load + (i32.const 111) + ) + ) + (drop + (f32.load + (i32.const 112) + ) + ) + (drop + (f32.load align=1 + (i32.const 113) + ) + ) + (drop + (f32.load align=2 + (i32.const 114) + ) + ) + (drop + (f32.load + (i32.const 115) + ) + ) + (drop + (f64.load + (i32.const 116) + ) + ) + (drop + (f64.load + (i32.const 117) + ) + ) + (drop + (f64.load align=1 + (i32.const 118) + ) + ) + (drop + (f64.load align=2 + (i32.const 119) + ) + ) + (drop + (f64.load align=4 + (i32.const 120) + ) + ) + (drop + (f64.load + (i32.const 121) + ) + ) ) (func $stores (local $0 i32) @@ -249,6 +358,26 @@ (get_local $1) ) ) + (drop + (i64.load + (i32.const 120) + ) + ) + (drop + (i64.load + (i32.const 120) + ) + ) + (drop + (i64.load align=2 + (i32.const 120) + ) + ) + (drop + (i64.load align=4 + (i32.const 120) + ) + ) (i64.store (i32.const 120) (tee_local $0 diff --git a/test/wasm-only.fromasm.clamp b/test/wasm-only.fromasm.clamp index 6ac8c0ef1..a746c45e3 100644 --- a/test/wasm-only.fromasm.clamp +++ b/test/wasm-only.fromasm.clamp @@ -26,7 +26,116 @@ (export "illegalResult" (func $legalstub$result)) (export "keepAlive" (func $keepAlive)) (func $loads - (nop) + (drop + (i32.load8_s + (i32.const 100) + ) + ) + (drop + (i32.load8_s + (i32.const 101) + ) + ) + (drop + (i32.load16_s + (i32.const 102) + ) + ) + (drop + (i32.load16_s + (i32.const 103) + ) + ) + (drop + (i32.load16_s align=1 + (i32.const 104) + ) + ) + (drop + (i32.load16_s + (i32.const 105) + ) + ) + (drop + (i32.load + (i32.const 106) + ) + ) + (drop + (i32.load + (i32.const 107) + ) + ) + (drop + (i32.load align=1 + (i32.const 108) + ) + ) + (drop + (i32.load align=2 + (i32.const 109) + ) + ) + (drop + (i32.load + (i32.const 110) + ) + ) + (drop + (f32.load + (i32.const 111) + ) + ) + (drop + (f32.load + (i32.const 112) + ) + ) + (drop + (f32.load align=1 + (i32.const 113) + ) + ) + (drop + (f32.load align=2 + (i32.const 114) + ) + ) + (drop + (f32.load + (i32.const 115) + ) + ) + (drop + (f64.load + (i32.const 116) + ) + ) + (drop + (f64.load + (i32.const 117) + ) + ) + (drop + (f64.load align=1 + (i32.const 118) + ) + ) + (drop + (f64.load align=2 + (i32.const 119) + ) + ) + (drop + (f64.load align=4 + (i32.const 120) + ) + ) + (drop + (f64.load + (i32.const 121) + ) + ) ) (func $stores (local $0 i32) @@ -249,6 +358,26 @@ (get_local $1) ) ) + (drop + (i64.load + (i32.const 120) + ) + ) + (drop + (i64.load + (i32.const 120) + ) + ) + (drop + (i64.load align=2 + (i32.const 120) + ) + ) + (drop + (i64.load align=4 + (i32.const 120) + ) + ) (i64.store (i32.const 120) (tee_local $0 |