diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/ir/iteration.h | 52 | ||||
| -rw-r--r-- | src/ir/properties.h | 1 | ||||
| -rw-r--r-- | src/ir/stack-utils.cpp | 20 | ||||
| -rw-r--r-- | src/wasm-stack.h | 554 |
4 files changed, 103 insertions, 524 deletions
diff --git a/src/ir/iteration.h b/src/ir/iteration.h index fd275f749..eb04a1e5f 100644 --- a/src/ir/iteration.h +++ b/src/ir/iteration.h @@ -17,6 +17,7 @@ #ifndef wasm_ir_iteration_h #define wasm_ir_iteration_h +#include "ir/properties.h" #include "wasm-traversal.h" #include "wasm.h" @@ -29,18 +30,24 @@ namespace wasm { // * This skips missing children, e.g. if an if has no else, it is represented // as having 2 children (and not 3 with the last a nullptr). // -// In general, it is preferable not to use this class and to directly access -// the children (using e.g. iff->ifTrue etc.), as that is faster. However, in -// cases where speed does not matter, this can be convenient. +// In general, it is preferable not to use this class and to directly access the +// children (using e.g. iff->ifTrue etc.), as that is faster. However, in cases +// where speed does not matter, this can be convenient. TODO: reimplement these +// to avoid materializing all the chilren at once. // - -class ChildIterator { +// ChildIterator - Iterates over all children +// +// ValueChildIterator - Iterates over all children that produce values used by +// this instruction. For example, includes If::condition +// but not If::ifTrue. +// +template<template<class, class> class Scanner> class AbstractChildIterator { + using Self = AbstractChildIterator<Scanner>; struct Iterator { - const ChildIterator& parent; + const Self& parent; Index index; - Iterator(const ChildIterator& parent, Index index) - : parent(parent), index(index) {} + Iterator(const Self& parent, Index index) : parent(parent), index(index) {} bool operator!=(const Iterator& other) const { return index != other.index || &parent != &(other.parent); @@ -52,12 +59,12 @@ class ChildIterator { }; public: - std::vector<Expression*> children; + SmallVector<Expression*, 4> children; - ChildIterator(Expression* parent) { + AbstractChildIterator(Expression* parent) { struct Traverser : public PostWalker<Traverser> { Expression* parent; - std::vector<Expression*>* children; + SmallVector<Expression*, 4>* children; // We need to scan subchildren exactly once - just the parent. bool scanned = false; @@ -65,8 +72,8 @@ public: static void scan(Traverser* self, Expression** currp) { if (!self->scanned) { self->scanned = true; - PostWalker<Traverser, UnifiedExpressionVisitor<Traverser>>::scan( - self, currp); + Scanner<Traverser, UnifiedExpressionVisitor<Traverser>>::scan(self, + currp); } else { // This is one of the children. Do not scan further, just note it. self->children->push_back(*currp); @@ -82,6 +89,25 @@ public: Iterator end() const { return Iterator(*this, children.size()); } }; +template<class SubType, class Visitor> +struct ValueChildScanner : PostWalker<SubType, Visitor> { + static void scan(SubType* self, Expression** currp) { + auto* curr = *currp; + if (Properties::isControlFlowStructure(curr)) { + // If conditions are the only value children of control flow structures + if (auto* iff = curr->dynCast<If>()) { + self->pushTask(SubType::scan, &iff->condition); + } + } else { + // All children on non-control flow expressions are value children + PostWalker<SubType, Visitor>::scan(self, currp); + } + } +}; + +using ChildIterator = AbstractChildIterator<PostWalker>; +using ValueChildIterator = AbstractChildIterator<ValueChildScanner>; + // Returns true if the current expression contains a certain kind of expression, // within the given depth of BFS. If depth is -1, this searches all children. template<typename T> bool containsChild(Expression* parent, int depth = -1) { diff --git a/src/ir/properties.h b/src/ir/properties.h index ac61f787e..f38773bd8 100644 --- a/src/ir/properties.h +++ b/src/ir/properties.h @@ -19,7 +19,6 @@ #include "ir/bits.h" #include "ir/effects.h" -#include "ir/iteration.h" #include "wasm.h" namespace wasm { diff --git a/src/ir/stack-utils.cpp b/src/ir/stack-utils.cpp index bc0fd2eb4..1f70a6618 100644 --- a/src/ir/stack-utils.cpp +++ b/src/ir/stack-utils.cpp @@ -15,6 +15,7 @@ */ #include "stack-utils.h" +#include "ir/iteration.h" #include "ir/properties.h" namespace wasm { @@ -56,20 +57,13 @@ bool mayBeUnreachable(Expression* expr) { } // namespace StackUtils StackSignature::StackSignature(Expression* expr) { - params = Type::none; - if (Properties::isControlFlowStructure(expr)) { - if (expr->is<If>()) { - params = Type::i32; - } - } else { - std::vector<Type> inputs; - for (auto* child : ChildIterator(expr)) { - assert(child->type.isConcrete()); - // Children might be tuple pops, so expand their types - inputs.insert(inputs.end(), child->type.begin(), child->type.end()); - } - params = Type(inputs); + std::vector<Type> inputs; + for (auto* child : ValueChildIterator(expr)) { + assert(child->type.isConcrete()); + // Children might be tuple pops, so expand their types + inputs.insert(inputs.end(), child->type.begin(), child->type.end()); } + params = Type(inputs); if (expr->type == Type::unreachable) { unreachable = true; results = Type::none; diff --git a/src/wasm-stack.h b/src/wasm-stack.h index d80618225..ed9245d4f 100644 --- a/src/wasm-stack.h +++ b/src/wasm-stack.h @@ -18,6 +18,7 @@ #define wasm_stack_h #include "ir/branch-utils.h" +#include "ir/properties.h" #include "pass.h" #include "wasm-binary.h" #include "wasm-traversal.h" @@ -182,7 +183,7 @@ private: // Takes binaryen IR and converts it to something else (binary or stack IR) template<typename SubType> -class BinaryenIRWriter : public OverriddenVisitor<BinaryenIRWriter<SubType>> { +class BinaryenIRWriter : public Visitor<BinaryenIRWriter<SubType>> { public: BinaryenIRWriter(Function* func) : func(func) {} @@ -194,50 +195,7 @@ public: void visitBlock(Block* curr); void visitIf(If* curr); void visitLoop(Loop* curr); - void visitBreak(Break* curr); - void visitSwitch(Switch* curr); - void visitCall(Call* curr); - void visitCallIndirect(CallIndirect* curr); - void visitLocalGet(LocalGet* curr); - void visitLocalSet(LocalSet* curr); - void visitGlobalGet(GlobalGet* curr); - void visitGlobalSet(GlobalSet* curr); - void visitLoad(Load* curr); - void visitStore(Store* curr); - void visitAtomicRMW(AtomicRMW* curr); - void visitAtomicCmpxchg(AtomicCmpxchg* curr); - void visitAtomicWait(AtomicWait* curr); - void visitAtomicNotify(AtomicNotify* curr); - void visitAtomicFence(AtomicFence* curr); - void visitSIMDExtract(SIMDExtract* curr); - void visitSIMDReplace(SIMDReplace* curr); - void visitSIMDShuffle(SIMDShuffle* curr); - void visitSIMDTernary(SIMDTernary* curr); - void visitSIMDShift(SIMDShift* curr); - void visitSIMDLoad(SIMDLoad* curr); - void visitMemoryInit(MemoryInit* curr); - void visitDataDrop(DataDrop* curr); - void visitMemoryCopy(MemoryCopy* curr); - void visitMemoryFill(MemoryFill* curr); - void visitConst(Const* curr); - void visitUnary(Unary* curr); - void visitBinary(Binary* curr); - void visitSelect(Select* curr); - void visitReturn(Return* curr); - void visitHost(Host* curr); - void visitRefNull(RefNull* curr); - void visitRefIsNull(RefIsNull* curr); - void visitRefFunc(RefFunc* curr); void visitTry(Try* curr); - void visitThrow(Throw* curr); - void visitRethrow(Rethrow* curr); - void visitBrOnExn(BrOnExn* curr); - void visitNop(Nop* curr); - void visitUnreachable(Unreachable* curr); - void visitDrop(Drop* curr); - void visitPop(Pop* curr); - void visitTupleMake(TupleMake* curr); - void visitTupleExtract(TupleExtract* curr); protected: Function* func = nullptr; @@ -275,19 +233,44 @@ void BinaryenIRWriter<SubType>::visitPossibleBlockContents(Expression* curr) { } for (auto* child : block->list) { visit(child); - } - if (block->type == Type::unreachable && - block->list.back()->type != Type::unreachable) { - // similar to in visitBlock, here we could skip emitting the block itself, - // but must still end the 'block' (the contents, really) with an unreachable - emitUnreachable(); + // Since this child was unreachable, either this child or one of its + // descendants was a source of unreachability that was actually + // emitted. Subsequent children won't be reachable, so skip them. + if (child->type == Type::unreachable) { + break; + } } } template<typename SubType> void BinaryenIRWriter<SubType>::visit(Expression* curr) { emitDebugLocation(curr); - OverriddenVisitor<BinaryenIRWriter>::visit(curr); + // We emit unreachable instructions that create unreachability, but not + // unreachable instructions that just inherit unreachability from their + // children, since the latter won't be reached. This (together with logic in + // the control flow visitors) also ensures that the final instruction in each + // unreachable block is a source of unreachability, which means we don't need + // to emit an extra `unreachable` before the end of the block to prevent type + // errors. + bool hasUnreachableChild = false; + for (auto* child : ValueChildIterator(curr)) { + visit(child); + if (child->type == Type::unreachable) { + hasUnreachableChild = true; + break; + } + } + if (hasUnreachableChild) { + // `curr` is not reachable, so don't emit it. + return; + } + // Control flow requires special handling, but most instructions can be + // emitted directly after their children. + if (Properties::isControlFlowStructure(curr)) { + Visitor<BinaryenIRWriter>::visit(curr); + } else { + emit(curr); + } } template<typename SubType> @@ -295,22 +278,26 @@ void BinaryenIRWriter<SubType>::visitBlock(Block* curr) { auto visitChildren = [this](Block* curr, Index from) { auto& list = curr->list; while (from < list.size()) { - visit(list[from++]); + auto* child = list[from]; + visit(child); + if (child->type == Type::unreachable) { + break; + } + ++from; } }; auto afterChildren = [this](Block* curr) { - if (curr->type == Type::unreachable) { - // an unreachable block is one that cannot be exited. We cannot encode - // this directly in wasm, where blocks must be none,i32,i64,f32,f64. Since - // the block cannot be exited, we can emit an unreachable at the end, and - // that will always be valid, and then the block is ok as a none - emitUnreachable(); - } emitScopeEnd(curr); if (curr->type == Type::unreachable) { - // and emit an unreachable *outside* the block too, so later things can - // pop anything + // Since this block is unreachable, no instructions will be emitted after + // it in its enclosing scope. That means that this block will be the last + // instruction before the end of its parent scope, so its type must match + // the type of its parent. But we don't have a concrete type for this + // block and we don't know what type its parent expects, so we can't + // ensure the types match. To work around this, we insert an `unreachable` + // instruction after every unreachable control flow structure and depend + // on its polymorphic behavior to paper over any type mismatches. emitUnreachable(); } }; @@ -331,12 +318,16 @@ void BinaryenIRWriter<SubType>::visitBlock(Block* curr) { emit(curr); visitChildren(curr, 0); afterChildren(curr); + bool childUnreachable = curr->type == Type::unreachable; // Finish the later parts of all the parent blocks. while (!parents.empty()) { auto* parent = parents.back(); parents.pop_back(); - visitChildren(parent, 1); + if (!childUnreachable) { + visitChildren(parent, 1); + } afterChildren(parent); + childUnreachable = parent->type == Type::unreachable; } return; } @@ -347,13 +338,6 @@ void BinaryenIRWriter<SubType>::visitBlock(Block* curr) { } template<typename SubType> void BinaryenIRWriter<SubType>::visitIf(If* curr) { - visit(curr->condition); - if (curr->condition->type == Type::unreachable) { - // this if-else is unreachable because of the condition, i.e., the condition - // does not exit. So don't emit the if (but do consume the condition) - emitUnreachable(); - return; - } emit(curr); visitPossibleBlockContents(curr->ifTrue); @@ -364,11 +348,10 @@ template<typename SubType> void BinaryenIRWriter<SubType>::visitIf(If* curr) { emitScopeEnd(curr); if (curr->type == Type::unreachable) { - // we already handled the case of the condition being unreachable. - // otherwise, we may still be unreachable, if we are an if-else with both - // sides unreachable. wasm does not allow this to be emitted directly, so we - // must do something more. we could do better, but for now we emit an extra - // unreachable instruction after the if, so it is not consumed itself, + // We already handled the case of the condition being unreachable in + // `visit`. Otherwise, we may still be unreachable, if we are an if-else + // with both sides unreachable. Just like with blocks, we emit an extra + // `unreachable` to work around potential type mismatches. assert(curr->ifFalse); emitUnreachable(); } @@ -378,11 +361,6 @@ template<typename SubType> void BinaryenIRWriter<SubType>::visitLoop(Loop* curr) { emit(curr); visitPossibleBlockContents(curr->body); - if (curr->type == Type::unreachable) { - // we emitted a loop without a return type, and the body might be block - // contents, so ensure it is not consumed - emitUnreachable(); - } emitScopeEnd(curr); if (curr->type == Type::unreachable) { // we emitted a loop without a return type, so it must not be consumed @@ -390,361 +368,6 @@ void BinaryenIRWriter<SubType>::visitLoop(Loop* curr) { } } -template<typename SubType> -void BinaryenIRWriter<SubType>::visitBreak(Break* curr) { - if (curr->value) { - visit(curr->value); - } - if (curr->condition) { - visit(curr->condition); - } - emit(curr); - if (curr->condition && curr->type == Type::unreachable) { - // a br_if is normally none or emits a value. if it is unreachable, then - // either the condition or the value is unreachable, which is extremely - // rare, and may require us to make the stack polymorphic (if the block we - // branch to has a value, we may lack one as we are not a reachable branch; - // the wasm spec on the other hand does presume the br_if emits a value of - // the right type, even if it popped unreachable) - emitUnreachable(); - } -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitSwitch(Switch* curr) { - if (curr->value) { - visit(curr->value); - } - visit(curr->condition); - if (!BranchUtils::isBranchReachable(curr)) { - // if the branch is not reachable, then it's dangerous to emit it, as wasm - // type checking rules are different, especially in unreachable code. so - // just don't emit that unreachable code. - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitCall(Call* curr) { - for (auto* operand : curr->operands) { - visit(operand); - } - - // For non-control-flow value-returning instructions, if the type of an - // expression is unreachable, we emit an unreachable and don't emit the - // instruction itself. If we don't emit an unreachable, instructions that - // follow can have a validation failure in wasm binary format. For example: - // [unreachable] (f32.add - // [unreachable] (i32.eqz - // [unreachable] (unreachable) - // ) - // ... - // ) - // This is a valid prgram in binaryen IR, because the unreachable type - // propagates out of an expression, making both i32.eqz and f32.add - // unreachable. But in binary format, this becomes: - // unreachable - // i32.eqz - // f32.add ;; validation failure; it takes an i32! - // And here f32.add causes validation failure in wasm validation. So in this - // case we add an unreachable to prevent following instructions to consume - // the current value (here i32.eqz). - // - // The same applies for other expressions. - if (curr->type == Type::unreachable && !curr->isReturn) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitCallIndirect(CallIndirect* curr) { - for (auto* operand : curr->operands) { - visit(operand); - } - visit(curr->target); - if (curr->type == Type::unreachable && !curr->isReturn) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitLocalGet(LocalGet* curr) { - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitLocalSet(LocalSet* curr) { - visit(curr->value); - if (curr->isTee() && curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitGlobalGet(GlobalGet* curr) { - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitGlobalSet(GlobalSet* curr) { - visit(curr->value); - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitLoad(Load* curr) { - visit(curr->ptr); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitStore(Store* curr) { - visit(curr->ptr); - visit(curr->value); - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitAtomicRMW(AtomicRMW* curr) { - visit(curr->ptr); - visit(curr->value); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitAtomicCmpxchg(AtomicCmpxchg* curr) { - visit(curr->ptr); - visit(curr->expected); - visit(curr->replacement); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitAtomicWait(AtomicWait* curr) { - visit(curr->ptr); - visit(curr->expected); - visit(curr->timeout); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitAtomicNotify(AtomicNotify* curr) { - visit(curr->ptr); - visit(curr->notifyCount); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitAtomicFence(AtomicFence* curr) { - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitSIMDExtract(SIMDExtract* curr) { - visit(curr->vec); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitSIMDReplace(SIMDReplace* curr) { - visit(curr->vec); - visit(curr->value); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitSIMDShuffle(SIMDShuffle* curr) { - visit(curr->left); - visit(curr->right); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitSIMDTernary(SIMDTernary* curr) { - visit(curr->a); - visit(curr->b); - visit(curr->c); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitSIMDShift(SIMDShift* curr) { - visit(curr->vec); - visit(curr->shift); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitSIMDLoad(SIMDLoad* curr) { - visit(curr->ptr); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitMemoryInit(MemoryInit* curr) { - visit(curr->dest); - visit(curr->offset); - visit(curr->size); - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitDataDrop(DataDrop* curr) { - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitMemoryCopy(MemoryCopy* curr) { - visit(curr->dest); - visit(curr->source); - visit(curr->size); - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitMemoryFill(MemoryFill* curr) { - visit(curr->dest); - visit(curr->value); - visit(curr->size); - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitConst(Const* curr) { - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitUnary(Unary* curr) { - visit(curr->value); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitBinary(Binary* curr) { - visit(curr->left); - visit(curr->right); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitSelect(Select* curr) { - visit(curr->ifTrue); - visit(curr->ifFalse); - visit(curr->condition); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitReturn(Return* curr) { - if (curr->value) { - visit(curr->value); - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitHost(Host* curr) { - switch (curr->op) { - case MemorySize: { - break; - } - case MemoryGrow: { - visit(curr->operands[0]); - break; - } - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitRefNull(RefNull* curr) { - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitRefIsNull(RefIsNull* curr) { - visit(curr->value); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitRefFunc(RefFunc* curr) { - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - template<typename SubType> void BinaryenIRWriter<SubType>::visitTry(Try* curr) { emit(curr); visitPossibleBlockContents(curr->body); @@ -756,69 +379,6 @@ template<typename SubType> void BinaryenIRWriter<SubType>::visitTry(Try* curr) { } } -template<typename SubType> -void BinaryenIRWriter<SubType>::visitThrow(Throw* curr) { - for (auto* operand : curr->operands) { - visit(operand); - } - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitRethrow(Rethrow* curr) { - visit(curr->exnref); - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitBrOnExn(BrOnExn* curr) { - visit(curr->exnref); - emit(curr); - if (curr->type == Type::unreachable) { - emitUnreachable(); - } -} - -template<typename SubType> void BinaryenIRWriter<SubType>::visitNop(Nop* curr) { - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitUnreachable(Unreachable* curr) { - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitDrop(Drop* curr) { - visit(curr->value); - emit(curr); -} - -template<typename SubType> void BinaryenIRWriter<SubType>::visitPop(Pop* curr) { - emit(curr); -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitTupleMake(TupleMake* curr) { - for (auto* operand : curr->operands) { - visit(operand); - } - emit(curr); - if (curr->type == Type::unreachable) { - emitUnreachable(); - } -} - -template<typename SubType> -void BinaryenIRWriter<SubType>::visitTupleExtract(TupleExtract* curr) { - visit(curr->tuple); - if (curr->type == Type::unreachable) { - emitUnreachable(); - return; - } - emit(curr); -} - // Binaryen IR to binary writer class BinaryenIRToBinaryWriter : public BinaryenIRWriter<BinaryenIRToBinaryWriter> { |