diff options
| -rwxr-xr-x | scripts/fuzz_opt.py | 1 | ||||
| -rw-r--r-- | src/pass.h | 3 | ||||
| -rw-r--r-- | src/passes/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/passes/Unsubtyping.cpp | 579 | ||||
| -rw-r--r-- | src/passes/pass.cpp | 3 | ||||
| -rw-r--r-- | src/passes/passes.h | 1 | ||||
| -rw-r--r-- | src/wasm-traversal.h | 2 | ||||
| -rw-r--r-- | src/wasm-type.h | 1 | ||||
| -rw-r--r-- | src/wasm/wasm-type.cpp | 4 | ||||
| -rw-r--r-- | test/lit/help/wasm-opt.test | 3 | ||||
| -rw-r--r-- | test/lit/help/wasm2js.test | 3 | ||||
| -rw-r--r-- | test/lit/passes/unsubtyping-casts.wast | 452 | ||||
| -rw-r--r-- | test/lit/passes/unsubtyping.wast | 1633 |
13 files changed, 2683 insertions, 3 deletions
diff --git a/scripts/fuzz_opt.py b/scripts/fuzz_opt.py index 08b07bece..6362b3c3f 100755 --- a/scripts/fuzz_opt.py +++ b/scripts/fuzz_opt.py @@ -1551,6 +1551,7 @@ opt_choices = [ ("--type-merging",), ("--type-ssa",), ("--type-unfinalizing",), + ("--unsubtyping",), ("--vacuum",), ] diff --git a/src/pass.h b/src/pass.h index da9a12b95..74b501eab 100644 --- a/src/pass.h +++ b/src/pass.h @@ -485,7 +485,8 @@ public: protected: Pass() = default; - Pass(Pass&) = default; + Pass(const Pass&) = default; + Pass(Pass&&) = default; Pass& operator=(const Pass&) = delete; }; diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt index 2d04d9a6f..bd1dd8598 100644 --- a/src/passes/CMakeLists.txt +++ b/src/passes/CMakeLists.txt @@ -116,6 +116,7 @@ set(passes_SOURCES SSAify.cpp TupleOptimization.cpp TypeFinalizing.cpp + Unsubtyping.cpp Untee.cpp Vacuum.cpp ${CMAKE_CURRENT_BINARY_DIR}/WasmIntrinsics.cpp diff --git a/src/passes/Unsubtyping.cpp b/src/passes/Unsubtyping.cpp new file mode 100644 index 000000000..3e88a7f91 --- /dev/null +++ b/src/passes/Unsubtyping.cpp @@ -0,0 +1,579 @@ +/* + * Copyright 2023 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. + */ + +#include <unordered_map> + +#include "ir/branch-utils.h" +#include "ir/subtypes.h" +#include "ir/type-updating.h" +#include "ir/utils.h" +#include "pass.h" +#include "support/unique_deferring_queue.h" +#include "wasm-traversal.h" +#include "wasm-type.h" +#include "wasm.h" + +// Compute and use the minimal subtype relation required to maintain module +// validity and behavior. This minimal relation will be a subset of the original +// subtype relation. Start by walking the IR and collecting pairs of types that +// need to be in the subtype relation for each expression to validate. For +// example, a local.set requires that the type of its operand be a subtype of +// the local's type. Casts do not generate subtypings at this point because it +// is not necessary for the cast target to be a subtype of the cast source for +// the cast to validate. +// +// From that initial subtype relation, we then start finding new subtypings that +// are required by the subtypings we have found already. These transitively +// required subtypings come from two sources. +// +// The first source is type definitions. Consider these type definitions: +// +// (type $A (sub (struct (ref $X)))) +// (type $B (sub $A (struct (ref $Y)))) +// +// If we have determined that $B must remain a subtype of $A, then we know that +// $Y must remain a subtype of $X as well, since the type definitions would not +// be valid otherwise. Similarly, knowing that $X must remain a subtype of $Y +// may transitively require other subtypings as well based on their type +// definitions. +// +// The second source of transitive subtyping requirements is casts. Although +// casting from one type to another does not necessarily require that those +// types are related, we do need to make sure that we do not change the +// behavior of casts by removing subtype relationships they might observe. For +// example, consider this module: +// +// (module +// ;; original subtyping: $bot <: $mid <: $top +// (type $top (sub (struct))) +// (type $mid (sub $top (struct))) +// (type $bot (sub $mid (struct))) +// +// (func $f +// (local $top (ref $top)) +// (local $mid (ref $mid)) +// +// ;; Requires $bot <: $top +// (local.set $top (struct.new $bot)) +// +// ;; Cast $top to $mid +// (local.set $mid (ref.cast (ref $mid) (local.get $top))) +// ) +// ) +// +// The only subtype relation directly required by the IR for this module is $bot +// <: $top. However, if we optimized the module so that $bot <: $top was the +// only subtype relation, we would change the behavior of the cast. In the +// original module, a value of type (ref $bot) is cast to (ref $mid). The cast +// succeeds because in the original module, $bot <: $mid. If we optimize so that +// we have $bot <: $top and no other subtypings, though, the cast will fail +// because the value of type (ref $bot) no longer inhabits (ref $mid). To +// prevent the cast's behavior from changing, we need to ensure that $bot <: +// $mid. +// +// The set of subtyping requirements generated by a cast from $src to $dest is +// that for every known remaining subtype $v of $src, if $v <: $dest in the +// original module, then $v <: $dest in the optimized module. In other words, +// for every type $v of values we know can flow into the cast, if the cast would +// have succeeded for values of type $v before, then we know the cast must +// continue to succeed for values of type $v. These requirements arising from +// casts can also generate transitive requirements because we learn about new +// types of values that can flow into casts as we learn about new subtypes of +// cast sources. +// +// Starting with the initial subtype relation determined by walking the IR, +// repeatedly search for new subtypings by analyzing type definitions and casts +// in lock step until we reach a fixed point. This is the minimal subtype +// relation that preserves module validity and behavior that can be found +// without a more precise analysis of types that might flow into each cast. + +namespace wasm { + +namespace { + +struct Unsubtyping + : WalkerPass<ControlFlowWalker<Unsubtyping, OverriddenVisitor<Unsubtyping>>> { + // The new set of supertype relations. + std::unordered_map<HeapType, HeapType> supertypes; + + // Map from cast source types to their destinations. + std::unordered_map<HeapType, std::unordered_set<HeapType>> castTypes; + + // The set of subtypes that need to have their type definitions analyzed to + // transitively find other subtype relations they depend on. We add to it + // every time we find a new subtype relationship we need to keep. + UniqueDeferredQueue<HeapType> work; + + void run(Module* wasm) override { + if (!wasm->features.hasGC()) { + return; + } + analyzePublicTypes(*wasm); + walkModule(wasm); + analyzeTransitiveDependencies(); + optimizeTypes(*wasm); + // Cast types may be refinable if their source and target types are no + // longer related. TODO: Experiment with running this only after checking + // whether it is necessary. + ReFinalize().run(getPassRunner(), wasm); + } + + // Note that sub must remain a subtype of super. + void noteSubtype(HeapType sub, HeapType super) { + if (sub == super || sub.isBottom() || super.isBottom()) { + return; + } + + auto [it, inserted] = supertypes.insert({sub, super}); + if (inserted) { + work.push(sub); + // TODO: Incrementally check all subtypes (inclusive) of sub against super + // and all its supertypes if we have already analyzed casts. + return; + } + // We already had a recorded supertype. The new supertype might be deeper, + // shallower, or identical to the old supertype. + auto oldSuper = it->second; + if (super == oldSuper) { + return; + } + // There are two different supertypes, but each type can only have a single + // direct subtype so the supertype chain cannot fork and one of the + // supertypes must be a supertype of the other. Recursively record that + // relationship as well. + if (HeapType::isSubType(super, oldSuper)) { + // sub <: super <: oldSuper + it->second = super; + work.push(sub); + // TODO: Incrementally check all subtypes (inclusive) of sub against super + // if we have already analyzed casts. + noteSubtype(super, oldSuper); + } else { + // sub <: oldSuper <: super + noteSubtype(oldSuper, super); + } + } + + void noteSubtype(Type sub, Type super) { + if (sub.isTuple()) { + assert(super.isTuple() && sub.size() == super.size()); + for (size_t i = 0, size = sub.size(); i < size; ++i) { + noteSubtype(sub[i], super[i]); + } + return; + } + if (!sub.isRef() || !super.isRef()) { + return; + } + noteSubtype(sub.getHeapType(), super.getHeapType()); + } + + void noteCast(HeapType src, HeapType dest) { + if (src == dest || dest.isBottom()) { + return; + } + assert(HeapType::isSubType(dest, src)); + castTypes[src].insert(dest); + } + + void noteCast(Type src, Type dest) { + assert(!src.isTuple() && !dest.isTuple()); + if (src == Type::unreachable) { + return; + } + assert(src.isRef() && dest.isRef()); + noteCast(src.getHeapType(), dest.getHeapType()); + } + + void analyzePublicTypes(Module& wasm) { + // We cannot change supertypes for anything public. + for (auto type : ModuleUtils::getPublicHeapTypes(wasm)) { + if (auto super = type.getSuperType()) { + noteSubtype(type, *super); + } + } + } + + void analyzeTransitiveDependencies() { + // While we have found new subtypings and have not reached a fixed point... + while (!work.empty()) { + // Subtype relationships that we are keeping might depend on other subtype + // relationships that we are not yet planning to keep. Transitively find + // all the relationships we need to keep all our type definitions valid. + while (!work.empty()) { + auto type = work.pop(); + auto super = supertypes.at(type); + if (super.isBasic()) { + continue; + } + if (type.isStruct()) { + const auto& fields = type.getStruct().fields; + const auto& superFields = super.getStruct().fields; + for (size_t i = 0, size = superFields.size(); i < size; ++i) { + noteSubtype(fields[i].type, superFields[i].type); + } + } else if (type.isArray()) { + auto elem = type.getArray().element; + noteSubtype(elem.type, super.getArray().element.type); + } else { + assert(type.isSignature()); + auto sig = type.getSignature(); + auto superSig = super.getSignature(); + noteSubtype(superSig.params, sig.params); + noteSubtype(sig.results, superSig.results); + } + } + + // Analyze all casts at once. + // TODO: This is expensive. Analyze casts incrementally after we + // initially analyze them. + analyzeCasts(); + } + } + + void analyzeCasts() { + // For each cast (src, dest) pair, any type that remains a subtype of src + // (meaning its values can inhabit locations typed src) and that was + // originally a subtype of dest (meaning its values would have passed the + // cast) should remain a subtype of dest so that its values continue to pass + // the cast. + // + // For every type, walk up its new supertype chain to find cast sources and + // compare against their associated cast destinations. + for (auto it = supertypes.begin(); it != supertypes.end(); ++it) { + auto type = it->first; + for (auto srcIt = it; srcIt != supertypes.end(); + srcIt = supertypes.find(srcIt->second)) { + auto src = srcIt->second; + auto destsIt = castTypes.find(src); + if (destsIt == castTypes.end()) { + continue; + } + for (auto dest : destsIt->second) { + if (HeapType::isSubType(type, dest)) { + noteSubtype(type, dest); + } + } + } + } + } + + void optimizeTypes(Module& wasm) { + struct Rewriter : GlobalTypeRewriter { + Unsubtyping& parent; + Rewriter(Unsubtyping& parent, Module& wasm) + : GlobalTypeRewriter(wasm), parent(parent) {} + std::optional<HeapType> getSuperType(HeapType type) override { + if (auto it = parent.supertypes.find(type); + it != parent.supertypes.end() && !it->second.isBasic()) { + return it->second; + } + return std::nullopt; + } + }; + Rewriter(*this, wasm).update(); + } + + void doWalkModule(Module* wasm) { + // Visit the functions in parallel, filling in `supertypes` and `castTypes` + // on separate instances which will later be merged. + ModuleUtils::ParallelFunctionAnalysis<Unsubtyping> analysis( + *wasm, [&](Function* func, Unsubtyping& unsubtyping) { + if (!func->imported()) { + unsubtyping.walkFunctionInModule(func, wasm); + } + }); + // Collect the results from the functions. + for (auto& [_, unsubtyping] : analysis.map) { + for (auto [sub, super] : unsubtyping.supertypes) { + noteSubtype(sub, super); + } + for (auto& [src, dests] : unsubtyping.castTypes) { + for (auto dest : dests) { + noteCast(src, dest); + } + } + } + // Collect constraints from top-level items. + for (auto& global : wasm->globals) { + visitGlobal(global.get()); + } + for (auto& seg : wasm->elementSegments) { + visitElementSegment(seg.get()); + } + // Visit the rest of the code that is not in functions. + walkModuleCode(wasm); + } + + void visitFunction(Function* func) { + if (func->body) { + noteSubtype(func->body->type, func->getResults()); + } + } + void visitGlobal(Global* global) { + if (global->init) { + noteSubtype(global->init->type, global->type); + } + } + void visitElementSegment(ElementSegment* seg) { + if (seg->offset) { + noteSubtype(seg->type, getModule()->getTable(seg->table)->type); + } + for (auto init : seg->data) { + noteSubtype(init->type, seg->type); + } + } + void visitNop(Nop* curr) {} + void visitBlock(Block* curr) { + if (!curr->list.empty()) { + noteSubtype(curr->list.back()->type, curr->type); + } + } + void visitIf(If* curr) { + if (curr->ifFalse) { + noteSubtype(curr->ifTrue->type, curr->type); + noteSubtype(curr->ifFalse->type, curr->type); + } + } + void visitLoop(Loop* curr) { noteSubtype(curr->body->type, curr->type); } + void visitBreak(Break* curr) { + if (curr->value) { + noteSubtype(curr->value->type, findBreakTarget(curr->name)->type); + } + } + void visitSwitch(Switch* curr) { + if (curr->value) { + for (auto name : BranchUtils::getUniqueTargets(curr)) { + noteSubtype(curr->value->type, findBreakTarget(name)->type); + } + } + } + template<typename T> void handleCall(T* curr, Signature sig) { + assert(curr->operands.size() == sig.params.size()); + for (size_t i = 0, size = sig.params.size(); i < size; ++i) { + noteSubtype(curr->operands[i]->type, sig.params[i]); + } + if (curr->isReturn) { + noteSubtype(sig.results, getFunction()->getResults()); + } + } + void visitCall(Call* curr) { + handleCall(curr, getModule()->getFunction(curr->target)->getSig()); + } + void visitCallIndirect(CallIndirect* curr) { + handleCall(curr, curr->heapType.getSignature()); + auto* table = getModule()->getTable(curr->table); + auto tableType = table->type.getHeapType(); + if (HeapType::isSubType(tableType, curr->heapType)) { + // Unlike other casts, where cast targets are always subtypes of cast + // sources, call_indirect target types may be supertypes of their source + // table types. In this case, the cast will always succeed, but only if we + // keep the types related. + noteSubtype(tableType, curr->heapType); + } else if (HeapType::isSubType(curr->heapType, tableType)) { + noteCast(tableType, curr->heapType); + } else { + // The types are unrelated and the cast will fail. We can keep the types + // unrelated. + } + } + void visitLocalGet(LocalGet* curr) {} + void visitLocalSet(LocalSet* curr) { + noteSubtype(curr->value->type, getFunction()->getLocalType(curr->index)); + } + void visitGlobalGet(GlobalGet* curr) {} + void visitGlobalSet(GlobalSet* curr) { + noteSubtype(curr->value->type, getModule()->getGlobal(curr->name)->type); + } + 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 visitSIMDLoadStoreLane(SIMDLoadStoreLane* 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) { + noteSubtype(curr->ifTrue->type, curr->type); + noteSubtype(curr->ifFalse->type, curr->type); + } + void visitDrop(Drop* curr) {} + void visitReturn(Return* curr) { + if (curr->value) { + noteSubtype(curr->value->type, getFunction()->getResults()); + } + } + void visitMemorySize(MemorySize* curr) {} + void visitMemoryGrow(MemoryGrow* curr) {} + void visitUnreachable(Unreachable* curr) {} + void visitPop(Pop* curr) {} + void visitRefNull(RefNull* curr) {} + void visitRefIsNull(RefIsNull* curr) {} + void visitRefFunc(RefFunc* curr) {} + void visitRefEq(RefEq* curr) {} + void visitTableGet(TableGet* curr) {} + void visitTableSet(TableSet* curr) { + noteSubtype(curr->value->type, getModule()->getTable(curr->table)->type); + } + void visitTableSize(TableSize* curr) {} + void visitTableGrow(TableGrow* curr) {} + void visitTableFill(TableFill* curr) { + noteSubtype(curr->value->type, getModule()->getTable(curr->table)->type); + } + void visitTry(Try* curr) { + noteSubtype(curr->body->type, curr->type); + for (auto* body : curr->catchBodies) { + noteSubtype(body->type, curr->type); + } + } + void visitThrow(Throw* curr) { + Type params = getModule()->getTag(curr->tag)->sig.params; + assert(params.size() == curr->operands.size()); + for (size_t i = 0, size = curr->operands.size(); i < size; ++i) { + noteSubtype(curr->operands[i]->type, params[i]); + } + } + void visitRethrow(Rethrow* curr) {} + void visitTupleMake(TupleMake* curr) {} + void visitTupleExtract(TupleExtract* curr) {} + void visitRefI31(RefI31* curr) {} + void visitI31Get(I31Get* curr) {} + void visitCallRef(CallRef* curr) { + if (!curr->target->type.isSignature()) { + return; + } + handleCall(curr, curr->target->type.getHeapType().getSignature()); + } + void visitRefTest(RefTest* curr) { + noteCast(curr->ref->type, curr->castType); + } + void visitRefCast(RefCast* curr) { noteCast(curr->ref->type, curr->type); } + void visitBrOn(BrOn* curr) { + if (curr->op == BrOnCast || curr->op == BrOnCastFail) { + noteCast(curr->ref->type, curr->castType); + } + noteSubtype(curr->getSentType(), findBreakTarget(curr->name)->type); + } + void visitStructNew(StructNew* curr) { + if (!curr->type.isStruct() || curr->isWithDefault()) { + return; + } + const auto& fields = curr->type.getHeapType().getStruct().fields; + assert(fields.size() == curr->operands.size()); + for (size_t i = 0, size = fields.size(); i < size; ++i) { + noteSubtype(curr->operands[i]->type, fields[i].type); + } + } + void visitStructGet(StructGet* curr) {} + void visitStructSet(StructSet* curr) { + if (!curr->ref->type.isStruct()) { + return; + } + const auto& fields = curr->ref->type.getHeapType().getStruct().fields; + noteSubtype(curr->value->type, fields[curr->index].type); + } + void visitArrayNew(ArrayNew* curr) { + if (!curr->type.isArray() || curr->isWithDefault()) { + return; + } + auto array = curr->type.getHeapType().getArray(); + noteSubtype(curr->init->type, array.element.type); + } + void visitArrayNewData(ArrayNewData* curr) {} + void visitArrayNewElem(ArrayNewElem* curr) { + if (!curr->type.isArray()) { + return; + } + auto array = curr->type.getHeapType().getArray(); + auto* seg = getModule()->getElementSegment(curr->segment); + noteSubtype(seg->type, array.element.type); + } + void visitArrayNewFixed(ArrayNewFixed* curr) { + if (!curr->type.isArray()) { + return; + } + auto array = curr->type.getHeapType().getArray(); + for (auto* value : curr->values) { + noteSubtype(value->type, array.element.type); + } + } + void visitArrayGet(ArrayGet* curr) {} + void visitArraySet(ArraySet* curr) { + if (!curr->ref->type.isArray()) { + return; + } + auto array = curr->ref->type.getHeapType().getArray(); + noteSubtype(curr->value->type, array.element.type); + } + void visitArrayLen(ArrayLen* curr) {} + void visitArrayCopy(ArrayCopy* curr) { + if (!curr->srcRef->type.isArray() || !curr->destRef->type.isArray()) { + return; + } + auto src = curr->srcRef->type.getHeapType().getArray(); + auto dest = curr->destRef->type.getHeapType().getArray(); + noteSubtype(src.element.type, dest.element.type); + } + void visitArrayFill(ArrayFill* curr) { + if (!curr->ref->type.isArray()) { + return; + } + auto array = curr->ref->type.getHeapType().getArray(); + noteSubtype(curr->value->type, array.element.type); + } + void visitArrayInitData(ArrayInitData* curr) {} + void visitArrayInitElem(ArrayInitElem* curr) { + if (!curr->ref->type.isArray()) { + return; + } + auto array = curr->ref->type.getHeapType().getArray(); + auto* seg = getModule()->getElementSegment(curr->segment); + noteSubtype(seg->type, array.element.type); + } + void visitRefAs(RefAs* curr) {} + void visitStringNew(StringNew* curr) {} + void visitStringConst(StringConst* curr) {} + void visitStringMeasure(StringMeasure* curr) {} + void visitStringEncode(StringEncode* curr) {} + void visitStringConcat(StringConcat* curr) {} + void visitStringEq(StringEq* curr) {} + void visitStringAs(StringAs* curr) {} + void visitStringWTF8Advance(StringWTF8Advance* curr) {} + void visitStringWTF16Get(StringWTF16Get* curr) {} + void visitStringIterNext(StringIterNext* curr) {} + void visitStringIterMove(StringIterMove* curr) {} + void visitStringSliceWTF(StringSliceWTF* curr) {} + void visitStringSliceIter(StringSliceIter* curr) {} +}; + +} // anonymous namespace + +Pass* createUnsubtypingPass() { return new Unsubtyping(); } + +} // namespace wasm diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp index 9b03310b5..35085c201 100644 --- a/src/passes/pass.cpp +++ b/src/passes/pass.cpp @@ -495,6 +495,9 @@ void PassRegistry::registerPasses() { registerPass("type-unfinalizing", "mark all types as non-final (open)", createTypeUnFinalizingPass); + registerPass("unsubtyping", + "removes unnecessary subtyping relationships", + createUnsubtypingPass); registerPass("untee", "removes local.tees, replacing them with sets and gets", createUnteePass); diff --git a/src/passes/passes.h b/src/passes/passes.h index f84cfcaab..2bace5bcc 100644 --- a/src/passes/passes.h +++ b/src/passes/passes.h @@ -159,6 +159,7 @@ Pass* createTypeFinalizingPass(); Pass* createTypeMergingPass(); Pass* createTypeSSAPass(); Pass* createTypeUnFinalizingPass(); +Pass* createUnsubtypingPass(); Pass* createUnteePass(); Pass* createVacuumPass(); diff --git a/src/wasm-traversal.h b/src/wasm-traversal.h index 212ded365..57e3a021f 100644 --- a/src/wasm-traversal.h +++ b/src/wasm-traversal.h @@ -406,8 +406,6 @@ using ExpressionStack = SmallVector<Expression*, 10>; template<typename SubType, typename VisitorType = Visitor<SubType>> struct ControlFlowWalker : public PostWalker<SubType, VisitorType> { - ControlFlowWalker() = default; - ExpressionStack controlFlowStack; // contains blocks, loops, and ifs // Uses the control flow stack to find the target of a break to a name diff --git a/src/wasm-type.h b/src/wasm-type.h index d97bdeba3..f5cb0bbb0 100644 --- a/src/wasm-type.h +++ b/src/wasm-type.h @@ -163,6 +163,7 @@ public: bool isNonNullable() const; // Whether this type is only inhabited by null values. bool isNull() const; + bool isSignature() const; bool isStruct() const; bool isArray() const; bool isString() const; diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp index 4ce72582c..7f8cde318 100644 --- a/src/wasm/wasm-type.cpp +++ b/src/wasm/wasm-type.cpp @@ -778,6 +778,10 @@ bool Type::isNonNullable() const { } } +bool Type::isSignature() const { + return isRef() && getHeapType().isSignature(); +} + bool Type::isStruct() const { return isRef() && getHeapType().isStruct(); } bool Type::isArray() const { return isRef() && getHeapType().isArray(); } diff --git a/test/lit/help/wasm-opt.test b/test/lit/help/wasm-opt.test index 213b09e88..4607a94b9 100644 --- a/test/lit/help/wasm-opt.test +++ b/test/lit/help/wasm-opt.test @@ -492,6 +492,9 @@ ;; CHECK-NEXT: --type-unfinalizing mark all types as non-final ;; CHECK-NEXT: (open) ;; CHECK-NEXT: +;; CHECK-NEXT: --unsubtyping removes unnecessary subtyping +;; CHECK-NEXT: relationships +;; CHECK-NEXT: ;; CHECK-NEXT: --untee removes local.tees, replacing ;; CHECK-NEXT: them with sets and gets ;; CHECK-NEXT: diff --git a/test/lit/help/wasm2js.test b/test/lit/help/wasm2js.test index 04c7d5577..0b041ddd3 100644 --- a/test/lit/help/wasm2js.test +++ b/test/lit/help/wasm2js.test @@ -451,6 +451,9 @@ ;; CHECK-NEXT: --type-unfinalizing mark all types as non-final ;; CHECK-NEXT: (open) ;; CHECK-NEXT: +;; CHECK-NEXT: --unsubtyping removes unnecessary subtyping +;; CHECK-NEXT: relationships +;; CHECK-NEXT: ;; CHECK-NEXT: --untee removes local.tees, replacing ;; CHECK-NEXT: them with sets and gets ;; CHECK-NEXT: diff --git a/test/lit/passes/unsubtyping-casts.wast b/test/lit/passes/unsubtyping-casts.wast new file mode 100644 index 000000000..8019efcd8 --- /dev/null +++ b/test/lit/passes/unsubtyping-casts.wast @@ -0,0 +1,452 @@ +;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited. +;; RUN: foreach %s %t wasm-opt --closed-world --unsubtyping --remove-unused-types -all -S -o - | filecheck %s + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $top (sub (struct ))) + (type $top (sub (struct))) + (type $mid (sub $top (struct))) + (type $bot (sub $mid (struct))) + + ;; CHECK: (type $1 (func)) + + ;; CHECK: (func $cast-optimizable (type $1) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast (ref none) + ;; CHECK-NEXT: (struct.new_default $top) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $cast-optimizable + (drop + ;; Simply casting from $top to $mid does not require $mid <: $top, since we + ;; haven't shown that it's possible for $mid to inhabit $top. We should + ;; optimize this case. + (ref.cast (ref $mid) + (struct.new $top) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $top (sub (struct ))) + (type $top (sub (struct))) + ;; CHECK: (type $mid (sub $top (struct ))) + (type $mid (sub $top (struct))) + ;; CHECK: (type $bot (sub $mid (struct ))) + (type $bot (sub $mid (struct))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $cast (type $3) + ;; CHECK-NEXT: (local $l (ref null $top)) + ;; CHECK-NEXT: (local.set $l + ;; CHECK-NEXT: (struct.new_default $bot) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast (ref $mid) + ;; CHECK-NEXT: (struct.new_default $top) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $cast + (local $l (ref null $top)) + (local.set $l + ;; Require $bot <: $top. + (struct.new $bot) + ) + (drop + ;; Now the cast requires $mid <: $top so that a $bot value appearing in the + ;; $top location would still pass the cast to $mid. + (ref.cast (ref $mid) + (struct.new $top) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $top (sub (struct ))) + (type $top (sub (struct))) + ;; CHECK: (type $mid (sub $top (struct ))) + (type $mid (sub $top (struct))) + ;; CHECK: (type $bot (sub $mid (struct ))) + (type $bot (sub $mid (struct))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $cast (type $3) + ;; CHECK-NEXT: (local $l (ref null $top)) + ;; CHECK-NEXT: (local.set $l + ;; CHECK-NEXT: (struct.new_default $bot) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.test (ref $mid) + ;; CHECK-NEXT: (struct.new_default $top) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $cast + (local $l (ref null $top)) + (local.set $l + ;; Require $bot <: $top. + (struct.new $bot) + ) + (drop + ;; Same as above, but with a ref.test. + (ref.test (ref $mid) + (struct.new $top) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $top (sub (struct ))) + (type $top (sub (struct))) + ;; CHECK: (type $mid (sub $top (struct ))) + (type $mid (sub $top (struct))) + ;; CHECK: (type $bot (sub $mid (struct ))) + (type $bot (sub $mid (struct))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $cast (type $3) + ;; CHECK-NEXT: (local $l (ref null $top)) + ;; CHECK-NEXT: (local.set $l + ;; CHECK-NEXT: (struct.new_default $bot) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $l (result (ref $mid)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (br_on_cast $l (ref $top) (ref $mid) + ;; CHECK-NEXT: (struct.new_default $top) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $cast + (local $l (ref null $top)) + (local.set $l + ;; Require $bot <: $top. + (struct.new $bot) + ) + (drop + (block $l (result (ref $mid)) + ;; Same as above, but with a br_on_cast. + (drop + (br_on_cast $l anyref (ref $mid) + (struct.new $top) + ) + ) + (unreachable) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $top (sub (struct ))) + (type $top (sub (struct))) + ;; CHECK: (type $mid (sub $top (struct ))) + (type $mid (sub $top (struct))) + ;; CHECK: (type $bot (sub $mid (struct ))) + (type $bot (sub $mid (struct))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $cast (type $3) + ;; CHECK-NEXT: (local $l (ref null $top)) + ;; CHECK-NEXT: (local.set $l + ;; CHECK-NEXT: (struct.new_default $bot) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $l (result (ref $top)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (br_on_cast_fail $l (ref $top) (ref $mid) + ;; CHECK-NEXT: (struct.new_default $top) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $cast + (local $l (ref null $top)) + (local.set $l + ;; Require $bot <: $top. + (struct.new $bot) + ) + (drop + (block $l (result (ref $top)) + ;; Same as above, but with a br_on_cast_fail. + (drop + (br_on_cast_fail $l anyref (ref $mid) + (struct.new $top) + ) + ) + (unreachable) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $top (sub (func))) + (type $top (sub (func))) + ;; CHECK: (type $mid (sub $top (func))) + (type $mid (sub $top (func))) + ;; CHECK: (type $bot (sub $mid (func))) + (type $bot (sub $mid (func))) + + ;; CHECK: (table $t 1 1 (ref null $top)) + (table $t 1 1 (ref null $top)) + + ;; CHECK: (elem declare func $cast) + + ;; CHECK: (func $cast (type $bot) + ;; CHECK-NEXT: (local $l (ref null $top)) + ;; CHECK-NEXT: (local.set $l + ;; CHECK-NEXT: (ref.func $cast) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call_indirect $t (type $mid) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $cast (type $bot) + (local $l (ref null $top)) + (local.set $l + ;; Require $bot <: $top. + (ref.func $cast) + ) + ;; Same as above, but with a call_indirect + (call_indirect $t (type $mid) + (i32.const 0) + ) + ) +) + +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $unrelated (sub (func))) + (type $unrelated (sub (func))) + + ;; CHECK: (type $top (sub (func))) + (type $top (sub (func))) + ;; CHECK: (type $bot (sub $top (func))) + (type $bot (sub $top (func))) + ) + + ;; CHECK: (table $t 1 1 (ref null $bot)) + (table $t 1 1 (ref null $bot)) + + ;; CHECK: (func $call-indirect (type $bot) + ;; CHECK-NEXT: (call_indirect $t (type $top) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call_indirect $t (type $unrelated) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $call-indirect (type $bot) + ;; This cast is guaranteed to succeed, so this directly requires $bot <: $top. + (call_indirect $t (type $top) + (i32.const 0) + ) + ;; This cast is guaraneed to fail. We should not introduce any subtype + ;; relationships that were not already there. + (call_indirect $t (type $unrelated) + (i32.const 0) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $top (sub (struct ))) + (type $top (sub (struct))) + ;; CHECK: (type $mid (sub (struct ))) + (type $mid (sub $top (struct))) + ;; CHECK: (type $bot (sub $mid (struct ))) + (type $bot (sub $mid (struct))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $cast-optimizable (type $3) + ;; CHECK-NEXT: (local $l (ref null $mid)) + ;; CHECK-NEXT: (local.set $l + ;; CHECK-NEXT: (struct.new_default $bot) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast (ref none) + ;; CHECK-NEXT: (struct.new_default $top) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $cast-optimizable + (local $l (ref null $mid)) + (local.set $l + ;; This time we require $bot <: $mid. + (struct.new $bot) + ) + (drop + ;; Even though $bot can now inhabit $mid, it cannot inhabit $top, so it can + ;; never appear in this cast, so we do not require $mid <: $top or $bot <: + ;; $top. + (ref.cast (ref $mid) + (struct.new $top) + ) + ) + ) +) + +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $top (sub (struct ))) + (type $top (sub (struct))) + ;; CHECK: (type $mid (sub $top (struct ))) + (type $mid (sub $top (struct))) + ;; CHECK: (type $bot (sub (struct ))) + (type $bot (sub $mid (struct))) + ) + + ;; CHECK: (type $3 (func (param anyref))) + + ;; CHECK: (func $cast (type $3) (param $any anyref) + ;; CHECK-NEXT: (local $l anyref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast (ref $bot) + ;; CHECK-NEXT: (local.get $any) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast (ref $top) + ;; CHECK-NEXT: (local.get $any) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast (ref $mid) + ;; CHECK-NEXT: (local.get $any) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.set $l + ;; CHECK-NEXT: (struct.new_default $mid) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $cast (param $any anyref) + (local $l anyref) + (drop + ;; Cast any -> $bot + (ref.cast (ref $bot) + (local.get $any) + ) + ) + (drop + ;; Cast any -> $top + (ref.cast (ref $top) + (local.get $any) + ) + ) + (drop + ;; Cast any -> $mid + (ref.cast (ref $mid) + (local.get $any) + ) + ) + + ;; Require $mid <: any. This will transitively require $mid <: $top and + ;; $top <: any, but $bot is unaffected. + (local.set $l + (struct.new $mid) + ) + ) +) + +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $topC (sub (struct ))) + (type $topC (sub (struct))) + ;; CHECK: (type $midC (sub $topC (struct ))) + (type $midC (sub $topC (struct))) + ;; CHECK: (type $botC (sub $midC (struct ))) + (type $botC (sub $midC (struct))) + + ;; CHECK: (type $topB (sub (struct (field (ref null $topC))))) + (type $topB (sub (struct (ref null $topC)))) + ;; CHECK: (type $midB (sub $topB (struct (field (ref null $botC))))) + (type $midB (sub $topB (struct (ref null $botC)))) + ;; CHECK: (type $botB (sub $midB (struct (field (ref null $botC))))) + (type $botB (sub $midB (struct (ref null $botC)))) + + ;; CHECK: (type $topA (sub (struct (field (ref null $topB))))) + (type $topA (sub (struct (ref null $topB)))) + ;; CHECK: (type $midA (sub $topA (struct (field (ref null $botB))))) + (type $midA (sub $topA (struct (ref null $botB)))) + ;; CHECK: (type $botA (sub $midA (struct (field (ref null $botB))))) + (type $botA (sub $midA (struct (ref null $botB)))) + ) + + ;; CHECK: (type $9 (func)) + + ;; CHECK: (func $cast (type $9) + ;; CHECK-NEXT: (local $l (ref null $topA)) + ;; CHECK-NEXT: (local.set $l + ;; CHECK-NEXT: (struct.new_default $botA) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast (ref $midA) + ;; CHECK-NEXT: (struct.new_default $topA) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast (ref $midB) + ;; CHECK-NEXT: (struct.new_default $topB) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast (ref $midC) + ;; CHECK-NEXT: (struct.new_default $topC) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $cast + (local $l (ref null $topA)) + (local.set $l + ;; Require $botA <: $topA. + (struct.new $botA) + ) + (drop + ;; Now the cast requires $midA <: $topA so that a $botA value appearing in + ;; the $topA location would still pass the cast to $midA. This will + ;; transitively require $botB <: $topB. + (ref.cast (ref $midA) + (struct.new $topA) + ) + ) + (drop + ;; Same as before, but now for the B types. This requires $botC <: $topC, but + ;; only after the previous cast has already been analyzed. + (ref.cast (ref $midB) + (struct.new $topB) + ) + ) + (drop + ;; Same as before, but now for the C types. Now no types will able to be + ;; optimized. + (ref.cast (ref $midC) + (struct.new $topC) + ) + ) + ) +) diff --git a/test/lit/passes/unsubtyping.wast b/test/lit/passes/unsubtyping.wast new file mode 100644 index 000000000..a82d601cc --- /dev/null +++ b/test/lit/passes/unsubtyping.wast @@ -0,0 +1,1633 @@ +;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited. +;; RUN: foreach %s %t wasm-opt --closed-world --unsubtyping --remove-unused-types -all -S -o - | filecheck %s + +(module + ;; $sub1 and $sub2 should become parent types and $super should be removed. + (type $super (sub (struct))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $sub2 (sub (struct (field f32)))) + + ;; CHECK: (type $sub1 (sub (struct (field i32)))) + (type $sub1 (sub $super (struct i32))) + (type $sub2 (sub $super (struct f32))) + + ;; CHECK: (global $sub1 (ref $sub1) (struct.new_default $sub1)) + (global $sub1 (ref $sub1) (struct.new_default $sub1)) + ;; CHECK: (global $sub2 (ref $sub2) (struct.new_default $sub2)) + (global $sub2 (ref $sub2) (struct.new_default $sub2)) +) + +(module + ;; Same result, but we start with $sub2 <: $sub1. + (type $super (sub (struct))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $sub2 (sub (struct (field i32) (field i32)))) + + ;; CHECK: (type $sub1 (sub (struct (field i32)))) + (type $sub1 (sub $super (struct i32))) + (type $sub2 (sub $sub1 (struct i32 i32))) + + ;; CHECK: (global $sub1 (ref $sub1) (struct.new_default $sub1)) + (global $sub1 (ref $sub1) (struct.new_default $sub1)) + ;; CHECK: (global $sub2 (ref $sub2) (struct.new_default $sub2)) + (global $sub2 (ref $sub2) (struct.new_default $sub2)) +) + +(module + ;; CHECK: (type $super (sub (func))) + (type $super (sub (func))) + ;; CHECK: (type $sub (sub $super (func))) + (type $sub (sub $super (func))) + + ;; Public types should not be changed. + ;; CHECK: (export "super" (func $super)) + + ;; CHECK: (export "sub" (func $sub)) + + ;; CHECK: (func $super (type $super) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $super (export "super") (type $super) + (unreachable) + ) + + ;; CHECK: (func $sub (type $sub) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $sub (export "sub") (type $sub) + (unreachable) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; A function body requires subtyping + ;; CHECK: (type $2 (func (result (ref $super)))) + + ;; CHECK: (func $foo (type $2) (result (ref $super)) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + (func $foo (result (ref $super)) + (struct.new $sub) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; A global initializer requires subtyping + ;; CHECK: (global $g1 (ref $super) (struct.new_default $sub)) + (global $g1 (ref $super) (struct.new $sub)) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + ;; CHECK: (type $subsub (sub $sub (struct ))) + (type $subsub (sub $sub (struct))) + + ;; CHECK: (table $t 1 1 (ref null $super)) + (table $t 1 1 (ref null $super)) + + ;; An active element segment requires subtyping. So does an element segment + ;; element. + ;; CHECK: (elem $e (table $t) (i32.const 0) (ref null $sub) (struct.new_default $subsub)) + (elem $e (table $t) (offset (i32.const 0)) (ref null $sub) (struct.new $subsub)) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $X (sub (struct ))) + (type $X (sub (struct))) + ;; CHECK: (type $Y (sub $X (struct ))) + (type $Y (sub $X (struct))) + + ;; CHECK: (type $A (sub (struct (field (ref null $X))))) + (type $A (sub (struct (ref null $X)))) + ;; CHECK: (type $B (sub $A (struct (field (ref null $Y))))) + (type $B (sub $A (struct (ref null $Y)))) + + ;; Requiring B <: A also requires X <: Y + ;; CHECK: (global $g (ref $A) (struct.new_default $B)) + (global $g (ref $A) (struct.new_default $B)) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $X (sub (struct ))) + (type $X (sub (struct))) + ;; CHECK: (type $Y (sub $X (struct ))) + (type $Y (sub $X (struct))) + + ;; CHECK: (type $A (sub (array (ref null $X)))) + (type $A (sub (array (field (ref null $X))))) + ;; CHECK: (type $B (sub $A (array (ref null $Y)))) + (type $B (sub $A (array (field (ref null $Y))))) + + ;; Transitive dependencies through an array. + ;; CHECK: (global $g (ref $A) (array.new_default $B + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: )) + (global $g (ref $A) (array.new_default $B (i32.const 0))) +) + +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $X (sub (struct ))) + (type $X (sub (struct))) + ;; CHECK: (type $Y (sub $X (struct ))) + (type $Y (sub $X (struct))) + + ;; CHECK: (type $X' (sub (struct ))) + (type $X' (sub (struct))) + ;; CHECK: (type $Y' (sub $X' (struct ))) + (type $Y' (sub $X' (struct))) + + ;; CHECK: (type $A (sub (func (param (ref $Y')) (result (ref $X))))) + (type $A (sub (func (param (ref $Y')) (result (ref $X))))) + ;; CHECK: (type $B (sub $A (func (param (ref $X')) (result (ref $Y))))) + (type $B (sub $A (func (param (ref $X')) (result (ref $Y))))) + ) + + ;; Transitive dependencies through a function type. + ;; CHECK: (global $g (ref null $A) (ref.func $foo)) + (global $g (ref null $A) (ref.func $foo)) + + ;; CHECK: (func $foo (type $B) (param $0 (ref $X')) (result (ref $Y)) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $foo (type $B) + (unreachable) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $block-fallthrough (type $2) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $l (result (ref $super)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (br_if $l + ;; CHECK-NEXT: (struct.new_default $super) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $block-fallthrough + (drop + (block $l (result (ref $super)) + (drop + (br_if $l + (struct.new $super) + (i32.const 0) + ) + ) + ;; This requires $sub <: $super + (struct.new $sub) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $opt (sub (struct (field i32)))) + + ;; CHECK: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + (type $opt (sub $super (struct i32))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $block-br (type $3) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $l (result (ref $super)) + ;; CHECK-NEXT: (br $l + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $other (result (ref $opt)) + ;; CHECK-NEXT: (br $other + ;; CHECK-NEXT: (struct.new_default $opt) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new_default $super) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $block-br + (drop + (block $l (result (ref $super)) + (br $l + ;; This requires $sub <: $super + (struct.new $sub) + ) + (drop + (block $other (result (ref $opt)) + (br $other + ;; But this doesn't require anything, so $opt will be optimized. + (struct.new_default $opt) + ) + ) + ) + (struct.new $super) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $if (type $2) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (if (result (ref $sub)) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $if + (drop + (if (result (ref $super)) + (i32.const 0) + ;; This requires $sub <: $super. + (struct.new $sub) + (struct.new $sub) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $loop (type $2) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (loop $loop-in (result (ref $sub)) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $loop + (drop + (loop (result (ref $super)) + ;; This requires $sub <: $super. + (struct.new $sub) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $loop (type $2) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $super (result (ref $sub)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $sub (result (ref $sub)) + ;; CHECK-NEXT: (br_table $super $sub + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $loop + (drop + (block $super (result (ref $super)) + (drop + (block $sub (result (ref $sub)) + ;; This requires $sub <: $super. + (br_table $super $sub + (struct.new $sub) + (i32.const 0) + ) + ) + ) + (unreachable) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $br-table (type $2) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $super (result (ref $sub)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $sub (result (ref $sub)) + ;; CHECK-NEXT: (br_table $sub $super + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $br-table + (drop + (block $super (result (ref $super)) + (drop + (block $sub (result (ref $sub)) + ;; Same as above with labels reversed. This requires $sub <: $super. + (br_table $sub $super + (struct.new $sub) + (i32.const 0) + ) + ) + ) + (unreachable) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func (param (ref $super)))) + + ;; CHECK: (func $call (type $2) (param $0 (ref $super)) + ;; CHECK-NEXT: (call $call + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $call (param (ref $super)) + ;; This requires $sub <: $super + (call $call + (struct.new $sub) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func (result (ref $sub)))) + + ;; CHECK: (type $3 (func (result (ref $super)))) + + ;; CHECK: (func $return-call (type $3) (result (ref $super)) + ;; CHECK-NEXT: (return_call $callee) + ;; CHECK-NEXT: ) + (func $return-call (result (ref $super)) + ;; This requires $sub <: $super + (return_call $callee) + ) + + ;; CHECK: (func $callee (type $2) (result (ref $sub)) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $callee (result (ref $sub)) + (unreachable) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func (param (ref $super)))) + + ;; CHECK: (table $t 0 funcref) + (table $t funcref) + + ;; CHECK: (func $call-indirect (type $2) (param $0 (ref $super)) + ;; CHECK-NEXT: (call_indirect $t (type $2) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $call-indirect (param (ref $super)) + ;; This requires $sub <: $super. + (call_indirect $t (param (ref $super)) + (struct.new $sub) + (i32.const 0) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func (result (ref $sub)))) + + ;; CHECK: (type $3 (func (result (ref $super)))) + + ;; CHECK: (table $t 0 funcref) + (table $t funcref) + + ;; CHECK: (func $return-call-indirect (type $3) (result (ref $super)) + ;; CHECK-NEXT: (return_call_indirect $t (type $2) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $return-call-indirect (result (ref $super)) + ;; This requires $sub <: $super. + (return_call_indirect $t (result (ref $sub)) + (i32.const 0) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $sub (sub (func))) + + ;; CHECK: (type $super (sub (func))) + (type $super (sub (func))) + (type $sub (sub $super (func))) + + ;; CHECK: (table $t 0 (ref null $super)) + (table $t (ref null $super) 1 1) + + ;; CHECK: (func $call-indirect-table (type $sub) + ;; CHECK-NEXT: (call_indirect $t (type $sub) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $call-indirect-table (type $sub) + ;; This does *not* require $sub <: $super on its own, although if that + ;; subtyping is not required at all, then it must be impossible for the table + ;; to contain a $sub and this call will trap. + (call_indirect $t (type $sub) + (i32.const 0) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $local-set (type $2) + ;; CHECK-NEXT: (local $l (ref null $super)) + ;; CHECK-NEXT: (local.set $l + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $local-set + (local $l (ref null $super)) + ;; This requires $sub <: $super. + (local.set $l + (struct.new $sub) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $local-tee (type $2) + ;; CHECK-NEXT: (local $l (ref null $super)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $l + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $local-tee + (local $l (ref null $super)) + (drop + ;; This requires $sub <: $super. + (local.tee $l + (struct.new $sub) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (global $g (mut (ref null $super)) (ref.null none)) + (global $g (mut (ref null $super)) (ref.null none)) + + ;; CHECK: (func $global-set (type $2) + ;; CHECK-NEXT: (global.set $g + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $global-set + ;; This requires $sub <: $super. + (global.set $g + (struct.new $sub) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub2 (sub $super (struct (field i32)))) + + ;; CHECK: (type $sub1 (sub $super (struct ))) + (type $sub1 (sub $super (struct))) + (type $sub2 (sub $super (struct i32))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $select (type $3) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (select (result (ref $super)) + ;; CHECK-NEXT: (struct.new_default $sub1) + ;; CHECK-NEXT: (struct.new_default $sub2) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $select + (drop + ;; This requires $sub1 <: $super and $sub2 <: super. + (select (result (ref $super)) + (struct.new $sub1) + (struct.new_default $sub2) + (i32.const 0) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func (result (ref $super)))) + + ;; CHECK: (func $return (type $2) (result (ref $super)) + ;; CHECK-NEXT: (return + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $return (result (ref $super)) + (return + ;; This requires $sub <: $super. + (struct.new $sub) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $sub (sub (struct ))) + + ;; CHECK: (type $super (sub (struct ))) + (type $super (sub (struct))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $return-none (type $2) + ;; CHECK-NEXT: (local $super (ref null $super)) + ;; CHECK-NEXT: (local $sub (ref null $sub)) + ;; CHECK-NEXT: (return) + ;; CHECK-NEXT: ) + (func $return-none + (local $super (ref null $super)) + (local $sub (ref null $sub)) + ;; Check that we don't get confused by bare returns. + (return) + ) +) + +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super2 (sub (struct ))) + + ;; CHECK: (type $sub2 (sub $super2 (struct ))) + + ;; CHECK: (type $super1 (sub (struct ))) + (type $super1 (sub (struct))) + (type $super2 (sub (struct))) + ;; CHECK: (type $sub1 (sub $super1 (struct ))) + (type $sub1 (sub $super1 (struct))) + (type $sub2 (sub $super2 (struct))) + ) + + ;; CHECK: (type $4 (func (result (ref $super1) (ref $super2)))) + + ;; CHECK: (func $return-many (type $4) (result (ref $super1) (ref $super2)) + ;; CHECK-NEXT: (return + ;; CHECK-NEXT: (tuple.make + ;; CHECK-NEXT: (struct.new_default $sub1) + ;; CHECK-NEXT: (struct.new_default $sub2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $return-many (result (ref $super1) (ref $super2)) + ;; This requires $sub1 <: $super1 and $sub2 <: super2. + (return + (tuple.make + (struct.new $sub1) + (struct.new $sub2) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (table $t 0 (ref null $super)) + (table $t (ref null $super) 1 1) + + ;; CHECK: (func $table-set (type $2) + ;; CHECK-NEXT: (table.set $t + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $table-set + ;; This requires $sub <: $super. + (table.set $t + (i32.const 0) + (struct.new $sub) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (table $t 0 (ref null $super)) + (table $t (ref null $super) 1 1) + + ;; CHECK: (func $table-set (type $2) + ;; CHECK-NEXT: (table.fill $t + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $table-set + ;; This requires $sub <: $super. + (table.fill $t + (i32.const 0) + (struct.new $sub) + (i32.const 0) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $try (type $2) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (try $try (result (ref $super)) + ;; CHECK-NEXT: (do + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (catch_all + ;; CHECK-NEXT: (struct.new_default $super) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $try + (drop + (try (result (ref $super)) + (do + ;; This requires $sub <: $super. + (struct.new $sub) + ) + (catch_all + (struct.new $super) + ) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $try-catch (type $2) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (try $try (result (ref $super)) + ;; CHECK-NEXT: (do + ;; CHECK-NEXT: (struct.new_default $super) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (catch_all + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $try-catch + (drop + (try (result (ref $super)) + (do + (struct.new $super) + ) + (catch_all + ;; This requires $sub <: $super. + (struct.new $sub) + ) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (type $3 (func (param (ref $super)))) + + ;; CHECK: (type $4 (func (param (ref $super)))) + + ;; CHECK: (tag $t (param (ref $super))) + (tag $t (param (ref $super))) + + ;; CHECK: (func $throw (type $2) + ;; CHECK-NEXT: (throw $t + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $throw + (throw $t + ;; This requires $sub <: $super. + (struct.new $sub) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $f (func (param (ref $super)))) + (type $f (func (param (ref $super)))) + + ;; CHECK: (elem declare func $call-ref) + + ;; CHECK: (func $call-ref (type $f) (param $0 (ref $super)) + ;; CHECK-NEXT: (call_ref $f + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: (ref.func $call-ref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block ;; (replaces something unreachable we can't emit) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block ;; (replaces something unreachable we can't emit) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.null nofunc) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $call-ref (type $f) (param (ref $super)) + ;; This requires $sub <: $super. + (call_ref $f + (struct.new $sub) + (ref.func $call-ref) + ) + ;; This should not trip us up. + (call_ref $f + (struct.new $sub) + (unreachable) + ) + ;; Nor should this. + (call_ref $f + (struct.new $sub) + (ref.null nofunc) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $f (func (result (ref $sub)))) + (type $f (func (result (ref $sub)))) + + ;; CHECK: (type $3 (func (result (ref $super)))) + + ;; CHECK: (elem declare func $callee) + + ;; CHECK: (func $return-call-ref (type $3) (result (ref $super)) + ;; CHECK-NEXT: (return_call_ref $f + ;; CHECK-NEXT: (ref.func $callee) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $return-call-ref (result (ref $super)) + ;; This requires $sub <: $super. + (return_call_ref $f + (ref.func $callee) + ) + ) + + ;; CHECK: (func $callee (type $f) (result (ref $sub)) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $callee (result (ref $sub)) + (unreachable) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $br-on-non-null (type $2) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $l (result (ref $super)) + ;; CHECK-NEXT: (br_on_non_null $l + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new_default $super) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $br-on-non-null + (drop + (block $l (result (ref $super)) + ;; This requires $sub <: $super. + (br_on_non_null $l + (struct.new $sub) + ) + (struct.new $super) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $br-on-cast (type $2) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $l (result (ref $super)) + ;; CHECK-NEXT: (br_on_cast $l (ref $super) (ref $sub) + ;; CHECK-NEXT: (struct.new_default $super) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $br-on-cast + (drop + (block $l (result (ref $super)) + ;; This requires $sub <: $super. + (br_on_cast $l anyref (ref $sub) + (struct.new $super) + ) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $2 (func)) + + ;; CHECK: (func $br-on-cast-fail (type $2) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block $l (result (ref $sub)) + ;; CHECK-NEXT: (br_on_cast_fail $l (ref $sub) (ref none) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $br-on-cast-fail + (drop + (block $l (result (ref $super)) + ;; This requires $sub <: $super. + (br_on_cast_fail $l anyref (ref none) + (struct.new $sub) + ) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $struct (sub (struct (field (ref null $super))))) + + ;; CHECK: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + (type $struct (sub (struct (ref null $super)))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $struct-new (type $3) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new_default $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block ;; (replaces something unreachable we can't emit) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $struct-new + (drop + ;; This requires $sub <: $super. + (struct.new $struct + (struct.new $sub) + ) + ) + (drop + ;; This should not trip us up. + (struct.new_default $struct) + ) + ;; Nor should this. + (struct.new $struct + (unreachable) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $struct (sub (struct (field (mut (ref null $super)))))) + + ;; CHECK: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + (type $struct (sub (struct (mut (ref null $super))))) + + ;; CHECK: (type $3 (func (param (ref null $struct)))) + + ;; CHECK: (func $struct-set (type $3) (param $struct (ref null $struct)) + ;; CHECK-NEXT: (struct.set $struct 0 + ;; CHECK-NEXT: (local.get $struct) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block ;; (replaces something unreachable we can't emit) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block ;; (replaces something unreachable we can't emit) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.null none) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $struct-set (param $struct (ref null $struct)) + ;; This requires $sub <: $super. + (struct.set $struct 0 + (local.get $struct) + (struct.new $sub) + ) + ;; This should not trip us up. + (struct.set $struct 0 + (unreachable) + (struct.new $sub) + ) + ;; Nor should this. + (struct.set $struct 0 + (ref.null none) + (struct.new $sub) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $array (sub (array (ref null $super)))) + + ;; CHECK: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + (type $array (sub (array (ref null $super)))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $array-new (type $3) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (array.new $array + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (array.new_default $array + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block ;; (replaces something unreachable we can't emit) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $array-new + (drop + ;; This requires $sub <: $super. + (array.new $array + (struct.new $sub) + (i32.const 0) + ) + ) + (drop + ;; This should not trip us up. + (array.new_default $array + (i32.const 0) + ) + ) + (drop + ;; Nor should this. + (array.new $array + (unreachable) + (i32.const 0) + ) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $array (sub (array (ref null $super)))) + + ;; CHECK: (type $1 (func)) + + ;; CHECK: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + (type $array (sub (array (ref null $super)))) + + ;; CHECK: (elem $e (ref null $sub)) + (elem $e (ref null $sub)) + + ;; CHECK: (func $array-new-elem (type $1) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (array.new_elem $array $e + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block ;; (replaces something unreachable we can't emit) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $array-new-elem + (drop + ;; This requires $sub <: $super. + (array.new_elem $array $e + (i32.const 0) + (i32.const 0) + ) + ) + ;; This should not trip us up. + (array.new_elem $array $e + (unreachable) + (i32.const 0) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $array (sub (array (ref null $super)))) + + ;; CHECK: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + (type $array (sub (array (ref null $super)))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $array-new-fixed (type $3) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (array.new_fixed $array 1 + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block ;; (replaces something unreachable we can't emit) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $array-new-fixed + (drop + ;; This requires $sub <: $super. + (array.new_fixed $array 1 + (struct.new $sub) + ) + ) + ;; This should not trip us up. + (array.new_fixed $array 1 + (unreachable) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $array (sub (array (mut (ref null $super))))) + (type $array (sub (array (mut (ref null $super))))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $array-set (type $3) + ;; CHECK-NEXT: (array.set $array + ;; CHECK-NEXT: (array.new_fixed $array 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block ;; (replaces something unreachable we can't emit) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block ;; (replaces something unreachable we can't emit) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.null none) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $array-set + ;; This requires $sub <: $super. + (array.set $array + (array.new_fixed $array 0) + (i32.const 0) + (struct.new $sub) + ) + ;; This should not trip us up. + (array.set $array + (unreachable) + (i32.const 0) + (struct.new $sub) + ) + ;; Nor should this. + (array.set $array + (ref.null none) + (i32.const 0) + (struct.new $sub) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $sub-array (sub (array (mut (ref null $sub))))) + + ;; CHECK: (type $super-array (sub (array (mut (ref null $super))))) + (type $super-array (sub (array (mut (ref null $super))))) + (type $sub-array (sub (array (mut (ref null $sub))))) + + ;; CHECK: (type $4 (func)) + + ;; CHECK: (func $array-copy (type $4) + ;; CHECK-NEXT: (array.copy $super-array $sub-array + ;; CHECK-NEXT: (array.new_fixed $super-array 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (array.new_fixed $sub-array 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (array.new_fixed $sub-array 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block + ;; CHECK-NEXT: (array.new_fixed $super-array 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (ref.null none) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $array-copy + ;; This requires $sub <: $super. + (array.copy $super-array $sub-array + (array.new_fixed $super-array 0) + (i32.const 0) + (array.new_fixed $sub-array 0) + (i32.const 0) + (i32.const 0) + ) + ;; This should not trip us up. + (array.copy $super-array $sub-array + (unreachable) + (i32.const 0) + (array.new_fixed $sub-array 0) + (i32.const 0) + (i32.const 0) + ) + ;; Nor should this. + (array.copy $super-array $sub-array + (array.new_fixed $super-array 0) + (i32.const 0) + (ref.null none) + (i32.const 0) + (i32.const 0) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + ;; CHECK: (type $array (sub (array (mut (ref null $super))))) + (type $array (sub (array (mut (ref null $super))))) + + ;; CHECK: (type $3 (func)) + + ;; CHECK: (func $array-fill (type $3) + ;; CHECK-NEXT: (array.fill $array + ;; CHECK-NEXT: (array.new_fixed $array 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block + ;; CHECK-NEXT: (ref.null none) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (struct.new_default $sub) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $array-fill + ;; This requires $sub <: $super. + (array.fill $array + (array.new_fixed $array 0) + (i32.const 0) + (struct.new $sub) + (i32.const 0) + ) + ;; This should not trip us up. + (array.fill $array + (unreachable) + (i32.const 0) + (struct.new $sub) + (i32.const 0) + ) + ;; Nor should this. + (array.fill $array + (ref.null none) + (i32.const 0) + (struct.new $sub) + (i32.const 0) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $array (sub (array (mut (ref null $super))))) + + ;; CHECK: (type $1 (func)) + + ;; CHECK: (type $super (sub (struct ))) + (type $super (sub (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $super (struct))) + + (type $array (sub (array (mut (ref null $super))))) + + ;; CHECK: (elem $e (ref null $sub)) + (elem $e (ref null $sub)) + + ;; CHECK: (func $array-init-elem (type $1) + ;; CHECK-NEXT: (array.init_elem $array $e + ;; CHECK-NEXT: (array.new_fixed $array 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block + ;; CHECK-NEXT: (ref.null none) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $array-init-elem + ;; This requires $sub <: $super. + (array.init_elem $array $e + (array.new_fixed $array 0) + (i32.const 0) + (i32.const 0) + (i32.const 0) + ) + ;; This should not trip us up. + (array.init_elem $array $e + (unreachable) + (i32.const 0) + (i32.const 0) + (i32.const 0) + ) + ;; Nor should this. + (array.init_elem $array $e + (ref.null none) + (i32.const 0) + (i32.const 0) + (i32.const 0) + ) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct ))) + (type $super (sub (struct))) + (type $mid (sub $super (struct))) + ;; CHECK: (type $sub (sub $super (struct ))) + (type $sub (sub $mid (struct))) + + ;; $sub <: $super, but it no longer needs to be related to $mid. + ;; CHECK: (global $g (ref $super) (struct.new_default $sub)) + (global $g (ref $super) (struct.new $sub)) +) + +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct (field (ref null $mid))))) + (type $super (sub (struct (ref null $mid)))) + ;; CHECK: (type $mid (sub $super (struct (field (ref null $mid)) (field i32)))) + (type $mid (sub $super (struct (ref null $mid) i32))) + ;; CHECK: (type $sub (sub $mid (struct (field (ref null $sub)) (field i32) (field i32)))) + (type $sub (sub $mid (struct (ref null $sub) i32 i32))) + ) + + ;; Same as above, but now that transitively requires $sub <: $mid, so we don't + ;; end up changing anything. + ;; CHECK: (global $g (ref $super) (struct.new_default $sub)) + (global $g (ref $super) (struct.new_default $sub)) +) + +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $super (sub (struct (field (ref null $super))))) + (type $super (sub (struct (ref null $super)))) + ;; CHECK: (type $mid (sub $super (struct (field (ref null $super)) (field i32)))) + (type $mid (sub $super (struct (ref null $super) i32))) + ;; CHECK: (type $sub (sub $mid (struct (field (ref null $sub)) (field i32) (field i32)))) + (type $sub (sub $mid (struct (ref null $sub) i32 i32))) + ) + + ;; Similar, but now we directly require that $sub <: $mid and transitively + ;; require that $sub <: $super, so again we cannot change anything. + ;; CHECK: (global $g (ref $mid) (struct.new_default $sub)) + (global $g (ref $mid) (struct.new_default $sub)) +) + +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $X (sub (struct ))) + (type $X (sub (struct))) + ;; CHECK: (type $Y (sub $X (struct ))) + (type $Y (sub $X (struct))) + + ;; CHECK: (type $super (sub (struct (field (ref null $mid))))) + (type $super (sub (struct (ref null $mid)))) + ;; CHECK: (type $mid (sub $super (struct (field (ref null $sub)) (field (ref null $X))))) + (type $mid (sub $super (struct (ref null $sub) (ref null $X)))) + ;; CHECK: (type $sub (sub $mid (struct (field (ref null $sub)) (field (ref null $Y))))) + (type $sub (sub $mid (struct (ref null $sub) (ref null $Y)))) + ) + + ;; Require $sub <: $super, which transitively requires $sub <: $mid, which then + ;; requires $Y <: $X. This only works because we put $sub back in the work list + ;; when we find a more refined supertype for it. + ;; CHECK: (global $g (ref $super) (struct.new_default $sub)) + (global $g (ref $super) (struct.new_default $sub)) +) |