diff options
| -rw-r--r-- | src/ir/possible-contents.cpp | 303 | ||||
| -rw-r--r-- | src/ir/possible-contents.h | 55 | ||||
| -rw-r--r-- | src/passes/GUFA.cpp | 14 | ||||
| -rw-r--r-- | test/gtest/possible-contents.cpp | 428 | ||||
| -rw-r--r-- | test/lit/passes/gufa-refs.wast | 375 |
5 files changed, 1007 insertions, 168 deletions
diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp index 6d75d65ca..8349939e1 100644 --- a/src/ir/possible-contents.cpp +++ b/src/ir/possible-contents.cpp @@ -89,39 +89,184 @@ void PossibleContents::combine(const PossibleContents& other) { return; } + auto lub = Type::getLeastUpperBound(type, otherType); + if (lub == Type::none) { + // The types are not in the same hierarchy. + value = Many(); + return; + } + + // From here we can assume there is a useful LUB. + // Nulls can be combined in by just adding nullability to a type. if (isNull() || other.isNull()) { // Only one of them can be null here, since we already handled the case // where they were both null. assert(!isNull() || !other.isNull()); - // If only one is a null, but the other's type is known exactly, then the - // combination is to add nullability (if the type is *not* known exactly, - // like for a global, then we cannot do anything useful here). - if (!isNull() && hasExactType()) { - value = ExactType(Type(type.getHeapType(), Nullable)); + // If only one is a null then we can use the type info from the other, and + // just add in nullability. For example, a literal of type T and a null + // becomes an exact type of T that allows nulls, and so forth. + auto mixInNull = [](ConeType cone) { + cone.type = Type(cone.type.getHeapType(), Nullable); + return cone; + }; + if (!isNull()) { + value = mixInNull(getCone()); return; - } else if (!other.isNull() && other.hasExactType()) { - value = ExactType(Type(otherType.getHeapType(), Nullable)); + } else if (!other.isNull()) { + value = mixInNull(other.getCone()); return; } } - if (hasExactType() && other.hasExactType() && - type.getHeapType() == otherType.getHeapType()) { - // We know the types here exactly, and even the heap types match, but - // there is some other difference that prevents them from being 100% - // identical (for example, one might be an ExactType and the other a - // Literal; or both might be ExactTypes and only one might be nullable). - // In these cases we can emit a proper ExactType here, adding nullability - // if we need to. - value = ExactType(Type( - type.getHeapType(), - type.isNullable() || otherType.isNullable() ? Nullable : NonNullable)); + // Find a ConeType that describes both inputs, using the shared ancestor which + // is the LUB. We need to find how big a cone we need: the cone must be big + // enough to contain both the inputs. + auto depth = getCone().depth; + auto otherDepth = other.getCone().depth; + Index newDepth; + if (depth == FullDepth || otherDepth == FullDepth) { + // At least one has full (infinite) depth, so we know the new depth must + // be the same. + newDepth = FullDepth; + } else { + // The depth we need under the lub is how far from the lub we are, plus + // the depth of our cone. + // TODO: we could make a single loop that also does the LUB, at the same + // time, and also avoids calling getDepth() which loops once more? + auto depthFromRoot = type.getHeapType().getDepth(); + auto otherDepthFromRoot = otherType.getHeapType().getDepth(); + auto lubDepthFromRoot = lub.getHeapType().getDepth(); + assert(lubDepthFromRoot <= depthFromRoot); + assert(lubDepthFromRoot <= otherDepthFromRoot); + Index depthUnderLub = depthFromRoot - lubDepthFromRoot + depth; + Index otherDepthUnderLub = + otherDepthFromRoot - lubDepthFromRoot + otherDepth; + + // The total cone must be big enough to contain all the above. + newDepth = std::max(depthUnderLub, otherDepthUnderLub); + } + + value = ConeType{lub, newDepth}; +} + +void PossibleContents::intersectWithFullCone(const PossibleContents& other) { + assert(other.isFullConeType()); + + if (isSubContents(other, *this)) { + // The intersection is just |other|. + // Note that this code path handles |this| being Many. + value = other.value; + return; + } + + if (!haveIntersection(*this, other)) { + // There is no intersection at all. + // Note that this code path handles |this| being None. + value = None(); + return; + } + + // There is an intersection here. Note that this implies |this| is a reference + // type, as it has an intersection with |other| which is a full cone type + // (which must be a reference type). + auto type = getType(); + auto otherType = other.getType(); + auto heapType = type.getHeapType(); + auto otherHeapType = otherType.getHeapType(); + + // If both inputs are nullable then the intersection is nullable as well. + auto nullability = + type.isNullable() && otherType.isNullable() ? Nullable : NonNullable; + + auto setNoneOrNull = [&]() { + if (nullability == Nullable) { + value = Literal::makeNull(otherHeapType); + } else { + value = None(); + } + }; + + if (isNull()) { + // The intersection is either this null itself, or nothing if a null is not + // allowed. + setNoneOrNull(); + return; + } + + // If the heap types are not compatible then they are in separate hierarchies + // and there is no intersection. + auto isSubType = HeapType::isSubType(heapType, otherHeapType); + auto otherIsSubType = HeapType::isSubType(otherHeapType, heapType); + if (!isSubType && !otherIsSubType) { + value = None(); return; } - // Nothing else possible combines in an interesting way; emit a Many. - value = Many(); + if (isLiteral() || isGlobal()) { + // The information about the value being identical to a particular literal + // or immutable global is not removed by intersection, if the type is in the + // cone we are intersecting with. + if (isSubType) { + return; + } + + // The type must change, so continue down to the generic code path. + // TODO: for globals we could perhaps refine the type here, but then the + // type on GlobalInfo would not match the module, so that needs some + // refactoring. + } + + // Intersect the cones, as there is no more specific information we can use. + auto depthFromRoot = heapType.getDepth(); + auto otherDepthFromRoot = otherHeapType.getDepth(); + + // To compute the new cone, find the new heap type for it, and to compute its + // depth, consider the adjustments to the existing depths that stem from the + // choice of new heap type. + HeapType newHeapType; + + if (depthFromRoot < otherDepthFromRoot) { + newHeapType = otherHeapType; + } else { + newHeapType = heapType; + } + + auto newType = Type(newHeapType, nullability); + + // By assumption |other| has full depth. Consider the other cone in |this|. + if (hasFullCone()) { + // Both are full cones, so the result is as well. + value = FullConeType(newType); + } else { + // The result is a partial cone. If the cone starts in |otherHeapType| then + // we need to adjust the depth down, since it will be smaller than the + // original cone: + /* + // .. + // / + // otherHeapType + // / \ + // heapType .. + // \ + */ + // E.g. if |this| is a cone of depth 10, and |otherHeapType| is an immediate + // subtype of |this|, then the new cone must be of depth 9. + auto newDepth = getCone().depth; + if (newHeapType == otherHeapType) { + assert(depthFromRoot <= otherDepthFromRoot); + auto reduction = otherDepthFromRoot - depthFromRoot; + if (reduction > newDepth) { + // The cone on heapType does not even reach the cone on otherHeapType, + // so the result is not a cone. + setNoneOrNull(); + return; + } + newDepth -= reduction; + } + + value = ConeType{newType, newDepth}; + } } bool PossibleContents::haveIntersection(const PossibleContents& a, @@ -148,43 +293,77 @@ bool PossibleContents::haveIntersection(const PossibleContents& a, // From here on we focus on references. - if (aType.isNullable() && bType.isNullable()) { - // Null is possible on both sides. Assume that an intersection can exist, - // but we could be more precise here and check if the types belong to - // different hierarchies, in which case the nulls would differ TODO. For - // now we only use this API from the RefEq logic, so this is fully precise. + auto aHeapType = aType.getHeapType(); + auto bHeapType = bType.getHeapType(); + + if (aType.isNullable() && bType.isNullable() && + aHeapType.getBottom() == bHeapType.getBottom()) { + // A compatible null is possible on both sides. return true; } - // We ruled out a null on both sides, so at least one is non-nullable. If the - // other is a null then no chance for an intersection remains. + // We ruled out having a compatible null on both sides. If one is simply a + // null then no chance for an intersection remains. if (a.isNull() || b.isNull()) { return false; } + auto aSubB = HeapType::isSubType(aHeapType, bHeapType); + auto bSubA = HeapType::isSubType(bHeapType, aHeapType); + if (!aSubB && !bSubA) { + // No type can appear in both a and b, so the types differ, so the values + // do not overlap. + return false; + } + // From here on we focus on references and can ignore the case of null - any // intersection must be of a non-null value, so we can focus on the heap // types. - auto aHeapType = aType.getHeapType(); - auto bHeapType = bType.getHeapType(); - - if (a.hasExactType() && b.hasExactType() && aHeapType != bHeapType) { - // The values must be different since their types are different. - return false; - } - if (!HeapType::isSubType(aHeapType, bHeapType) && - !HeapType::isSubType(bHeapType, aHeapType)) { - // No type can appear in both a and b, so the types differ, so the values - // differ. - return false; + auto aDepthFromRoot = aHeapType.getDepth(); + auto bDepthFromRoot = bHeapType.getDepth(); + + if (aSubB) { + // A is a subtype of B. For there to be an intersection we need their cones + // to intersect, that is, to rule out the case where the cone from B is not + // deep enough to reach A. + assert(aDepthFromRoot >= bDepthFromRoot); + return aDepthFromRoot - bDepthFromRoot <= b.getCone().depth; + } else if (bSubA) { + assert(bDepthFromRoot >= aDepthFromRoot); + return bDepthFromRoot - aDepthFromRoot <= a.getCone().depth; + } else { + WASM_UNREACHABLE("we ruled out no subtyping before"); } // TODO: we can also optimize things like different Literals, but existing // passes do such things already so it is low priority. +} + +bool PossibleContents::isSubContents(const PossibleContents& a, + const PossibleContents& b) { + // TODO: Everything else. For now we only call this when |a| or |b| is a full + // cone type. + if (b.isFullConeType()) { + if (a.isNone()) { + return true; + } + if (a.isMany()) { + return false; + } + if (a.isNull()) { + return b.getType().isNullable(); + } + return Type::isSubType(a.getType(), b.getType()); + } + + if (a.isFullConeType()) { + // We've already ruled out b being a full cone type before, so the only way + // |a| can be contained in |b| is if |b| is everything. + return b.isMany(); + } - // It appears they can intersect. - return true; + WASM_UNREACHABLE("a or b must be a full cone"); } namespace { @@ -1018,6 +1197,7 @@ struct InfoCollector // verbose code). void addRoot(Expression* curr, PossibleContents contents = PossibleContents::many()) { + // TODO Use a cone type here when relevant if (isRelevant(curr)) { addRoot(ExpressionLocation{curr, 0}, contents); } @@ -1675,7 +1855,11 @@ void Flower::readFromData(HeapType declaredHeapType, // represent them as an exact type). // See the test TODO with text "We optimize some of this, but stop at // reading from the immutable global" - assert(refContents.isMany() || refContents.isGlobal()); + assert(refContents.isMany() || refContents.isGlobal() || + refContents.isConeType()); + + // TODO: Use the cone depth here for ConeType. Right now we do the + // pessimistic thing and assume a full cone of all subtypes. // We create a ConeReadLocation for the canonical cone of this type, to // avoid bloating the graph, see comment on ConeReadLocation(). @@ -1737,9 +1921,12 @@ void Flower::writeToData(Expression* ref, Expression* value, Index fieldIndex) { DataLocation{refContents.getType().getHeapType(), fieldIndex}; updateContents(heapLoc, valueContents); } else { - assert(refContents.isMany() || refContents.isGlobal()); + assert(refContents.isMany() || refContents.isGlobal() || + refContents.isConeType()); // Update all possible subtypes here. + // TODO: Use the cone depth here for ConeType. Right now we do the + // pessimistic thing and assume a full cone of all subtypes. auto type = ref->type.getHeapType(); for (auto subType : subTypes->getAllSubTypes(type)) { auto heapLoc = DataLocation{subType, fieldIndex}; @@ -1751,32 +1938,10 @@ void Flower::writeToData(Expression* ref, Expression* value, Index fieldIndex) { void Flower::flowRefCast(const PossibleContents& contents, RefCast* cast) { // RefCast only allows valid values to go through: nulls and things of the // cast type. Filter anything else out. - PossibleContents filtered; - if (contents.isMany()) { - // Just pass the Many through. - // TODO: we could emit a cone type here when we get one, instead of - // emitting a Many in any of these code paths - filtered = contents; - } else { - bool isSubType = - HeapType::isSubType(contents.getType().getHeapType(), cast->intendedType); - if (isSubType) { - // The contents are not Many, but their heap type is a subtype of the - // intended type, so we'll pass that through. Note that we pass the entire - // contents here, which includes nullability, but that is fine, it would - // just overlap with the code below that handles nulls (that is, the code - // below only makes a difference when the heap type is *not* a subtype but - // the type is nullable). - // TODO: When we get cone types, we could filter the cone here. - filtered.combine(contents); - } - bool mayBeNull = contents.getType().isNullable(); - if (mayBeNull) { - // A null is possible, so pass that along. - filtered.combine( - PossibleContents::literal(Literal::makeNull(cast->intendedType))); - } - } + auto intendedCone = + PossibleContents::fullConeType(Type(cast->intendedType, Nullable)); + PossibleContents filtered = contents; + filtered.intersectWithFullCone(intendedCone); if (!filtered.isNone()) { #if defined(POSSIBLE_CONTENTS_DEBUG) && POSSIBLE_CONTENTS_DEBUG >= 2 std::cout << " ref.cast passing through\n"; diff --git a/src/ir/possible-contents.h b/src/ir/possible-contents.h index a6a27062a..ee817deae 100644 --- a/src/ir/possible-contents.h +++ b/src/ir/possible-contents.h @@ -50,6 +50,7 @@ namespace wasm { // then only the exact type is possible; if the depth is 1 // then either that type or its immediate subtypes, and so // forth. +// A depth of -1 means unlimited: all subtypes are allowed. // If the type here is nullable then null is also allowed. // TODO: Add ConeTypePlusContents or such, which would be // used on e.g. a struct.new with an immutable field @@ -96,6 +97,12 @@ class PossibleContents { // type. static ConeType ExactType(Type type) { return ConeType{type, 0}; } + static constexpr Index FullDepth = -1; + + // Internal convenience for creating a cone type of unbounded depth, i.e., the + // full cone of all subtypes for that type. + static ConeType FullConeType(Type type) { return ConeType{type, FullDepth}; } + public: PossibleContents() : value(None()) {} PossibleContents(const PossibleContents& other) = default; @@ -114,8 +121,13 @@ public: static PossibleContents exactType(Type type) { return PossibleContents{ExactType(type)}; } + // Helper for a cone with unbounded depth, i.e., the full cone of all subtypes + // for that type. + static PossibleContents fullConeType(Type type) { + return PossibleContents{FullConeType(type)}; + } static PossibleContents coneType(Type type, Index depth) { - WASM_UNREACHABLE("actual cones are not supported yet"); + return PossibleContents{ConeType{type, depth}}; } static PossibleContents many() { return PossibleContents{Many()}; } @@ -133,6 +145,11 @@ public: // contents here will then include whatever content was possible in |other|. void combine(const PossibleContents& other); + // Removes anything not in |other| from this object, so that it ends up with + // only their intersection. Currently this only handles an intersection with a + // full cone. + void intersectWithFullCone(const PossibleContents& other); + bool isNone() const { return std::get_if<None>(&value); } bool isLiteral() const { return std::get_if<Literal>(&value); } bool isGlobal() const { return std::get_if<GlobalInfo>(&value); } @@ -174,6 +191,37 @@ public: } } + // Returns cone type info. This can be called on non-cone types as well, and + // it returns a cone that best describes them. That is, this is like getType() + // but it also provides an indication about the depth, if relevant. (If cone + // info is not relevant, like when getType() returns none or unreachable, the + // depth is set to 0.) + ConeType getCone() const { + if (auto* literal = std::get_if<Literal>(&value)) { + return ExactType(literal->type); + } else if (auto* global = std::get_if<GlobalInfo>(&value)) { + return FullConeType(global->type); + } else if (auto* coneType = std::get_if<ConeType>(&value)) { + return *coneType; + } else if (std::get_if<None>(&value)) { + return ExactType(Type::unreachable); + } else if (std::get_if<Many>(&value)) { + return ExactType(Type::none); + } else { + WASM_UNREACHABLE("bad value"); + } + } + + // Returns whether the relevant cone for this, as computed by getCone(), is of + // full size, that is, includes all subtypes. + bool hasFullCone() const { return getCone().depth == FullDepth; } + + // Returns whether this is a cone type and also is of full size. This differs + // from hasFullCone() in that the former can return true for a global, for + // example, while this cannot (a global is not a cone type, but the + // information we have about its cone is that it is full). + bool isFullConeType() const { return isConeType() && hasFullCone(); } + // Returns whether the type we can report here is exact, that is, nothing of a // strict subtype might show up - the contents here have an exact type. // @@ -197,6 +245,11 @@ public: static bool haveIntersection(const PossibleContents& a, const PossibleContents& b); + // Returns whether |a| is a subset of |b|, that is, all possible contents of + // |a| are also possible in |b|. + static bool isSubContents(const PossibleContents& a, + const PossibleContents& b); + // Whether we can make an Expression* for this containing the proper contents. // We can do that for a Literal (emitting a Const or RefFunc etc.) or a // Global (emitting a GlobalGet), but not for anything else yet. diff --git a/src/passes/GUFA.cpp b/src/passes/GUFA.cpp index eedf5f20c..9774c1bb7 100644 --- a/src/passes/GUFA.cpp +++ b/src/passes/GUFA.cpp @@ -243,10 +243,11 @@ struct GUFAOptimizer auto refType = refContents.getType(); if (refType.isRef()) { // We have some knowledge of the type here. Use that to optimize: RefTest - // returns 1 iff the input is not null and is also a subtype. - bool isSubType = - HeapType::isSubType(refType.getHeapType(), curr->intendedType); - bool mayBeNull = refType.isNullable(); + // returns 1 if the input is of a subtype of the intended type, that is, + // we are looking for a type in that cone of types. (Note that we use a + // non-nullable cone since only a non-null can pass the test.) + auto intendedContents = + PossibleContents::fullConeType(Type(curr->intendedType, NonNullable)); auto optimize = [&](int32_t result) { auto* last = Builder(*getModule()).makeConst(Literal(int32_t(result))); @@ -254,9 +255,10 @@ struct GUFAOptimizer curr, *getModule(), getPassOptions(), last)); }; - if (!isSubType) { + if (!PossibleContents::haveIntersection(refContents, intendedContents)) { optimize(0); - } else if (!mayBeNull) { + } else if (PossibleContents::isSubContents(refContents, + intendedContents)) { optimize(1); } } diff --git a/test/gtest/possible-contents.cpp b/test/gtest/possible-contents.cpp index 2ba008570..04c288806 100644 --- a/test/gtest/possible-contents.cpp +++ b/test/gtest/possible-contents.cpp @@ -66,6 +66,7 @@ protected: Type anyref = Type(HeapType::any, Nullable); Type funcref = Type(HeapType::func, Nullable); Type i31ref = Type(HeapType::i31, Nullable); + Type dataref = Type(HeapType::data, Nullable); PossibleContents none = PossibleContents::none(); @@ -95,6 +96,7 @@ protected: PossibleContents exactI32 = PossibleContents::exactType(Type::i32); PossibleContents exactAnyref = PossibleContents::exactType(anyref); PossibleContents exactFuncref = PossibleContents::exactType(funcref); + PossibleContents exactDataref = PossibleContents::exactType(dataref); PossibleContents exactI31ref = PossibleContents::exactType(i31ref); PossibleContents exactNonNullAnyref = PossibleContents::exactType(Type(HeapType::any, NonNullable)); @@ -109,6 +111,10 @@ protected: Type(Signature(Type::none, Type::none), NonNullable)); PossibleContents many = PossibleContents::many(); + + PossibleContents coneAnyref = PossibleContents::fullConeType(anyref); + PossibleContents coneFuncref = PossibleContents::fullConeType(funcref); + PossibleContents coneFuncref1 = PossibleContents::coneType(funcref, 1); }; TEST_F(PossibleContentsTest, TestComparisons) { @@ -161,11 +167,16 @@ TEST_F(PossibleContentsTest, TestHash) { EXPECT_NE(none.hash(), funcGlobal.hash()); EXPECT_NE(none.hash(), exactAnyref.hash()); EXPECT_NE(none.hash(), exactFuncSignatureType.hash()); - // TODO: cones + EXPECT_NE(none.hash(), coneAnyref.hash()); + EXPECT_NE(none.hash(), coneFuncref.hash()); + EXPECT_NE(none.hash(), coneFuncref1.hash()); EXPECT_NE(i32Zero.hash(), i32One.hash()); EXPECT_NE(anyGlobal.hash(), funcGlobal.hash()); EXPECT_NE(exactAnyref.hash(), exactFuncSignatureType.hash()); + EXPECT_NE(coneAnyref.hash(), coneFuncref.hash()); + EXPECT_NE(coneAnyref.hash(), coneFuncref1.hash()); + EXPECT_NE(coneFuncref.hash(), coneFuncref1.hash()); } TEST_F(PossibleContentsTest, TestCombinations) { @@ -200,10 +211,11 @@ TEST_F(PossibleContentsTest, TestCombinations) { assertCombination(many, many, many); // Exact references: An exact reference only stays exact when combined with - // the same heap type (nullability may be added, but nothing else). + // the same heap type (nullability may be added, but nothing else). Otherwise + // we go to a cone type or to many. assertCombination(exactFuncref, exactAnyref, many); assertCombination(exactFuncref, anyGlobal, many); - assertCombination(exactFuncref, nonNullFunc, many); + assertCombination(exactFuncref, nonNullFunc, coneFuncref1); assertCombination(exactFuncref, exactFuncref, exactFuncref); assertCombination(exactFuncref, exactNonNullFuncref, exactFuncref); @@ -241,10 +253,11 @@ TEST_F(PossibleContentsTest, TestCombinations) { nonNullFunc, exactNonNullFuncSignatureType, exactNonNullFuncSignatureType); assertCombination(nonNullFunc, exactI32, many); - // Globals vs nulls. + // Globals vs nulls. The result is either the global or a null, so all we can + // say is that it is something of the global's type, or a null: a cone. - assertCombination(anyGlobal, anyNull, many); - assertCombination(anyGlobal, i31Null, many); + assertCombination(anyGlobal, anyNull, coneAnyref); + assertCombination(anyGlobal, i31Null, coneAnyref); } TEST_F(PossibleContentsTest, TestOracleMinimal) { @@ -271,6 +284,13 @@ TEST_F(PossibleContentsTest, TestOracleMinimal) { void assertHaveIntersection(PossibleContents a, PossibleContents b) { EXPECT_TRUE(PossibleContents::haveIntersection(a, b)); EXPECT_TRUE(PossibleContents::haveIntersection(b, a)); +#if BINARYEN_TEST_DEBUG + if (!PossibleContents::haveIntersection(a, b) || + !PossibleContents::haveIntersection(b, a)) { + std::cout << "\nFailure: no intersection:\n" << a << '\n' << b << '\n'; + abort(); + } +#endif } void assertLackIntersection(PossibleContents a, PossibleContents b) { EXPECT_FALSE(PossibleContents::haveIntersection(a, b)); @@ -291,10 +311,12 @@ TEST_F(PossibleContentsTest, TestIntersection) { assertLackIntersection(exactI32, exactAnyref); assertLackIntersection(i32Zero, exactAnyref); - // But nullable ones can - the null can be the intersection. - assertHaveIntersection(exactFuncSignatureType, exactAnyref); + // But nullable ones can - the null can be the intersection, if they are not + // in separate hierarchies. assertHaveIntersection(exactFuncSignatureType, funcNull); - assertHaveIntersection(anyNull, funcNull); + + assertLackIntersection(exactFuncSignatureType, exactAnyref); + assertLackIntersection(anyNull, funcNull); // Identical types might. assertHaveIntersection(exactI32, exactI32); @@ -313,12 +335,8 @@ TEST_F(PossibleContentsTest, TestIntersection) { assertHaveIntersection(funcGlobal, exactNonNullFuncSignatureType); assertHaveIntersection(nonNullFuncGlobal, exactNonNullFuncSignatureType); - // Neither is a subtype of the other, but nulls are possible, so a null can be - // the intersection. - assertHaveIntersection(funcGlobal, anyGlobal); - - // Without null on one side, we cannot intersect. - assertLackIntersection(nonNullFuncGlobal, anyGlobal); + // Separate hierarchies. + assertLackIntersection(funcGlobal, anyGlobal); } TEST_F(PossibleContentsTest, TestIntersectWithCombinations) { @@ -363,11 +381,12 @@ TEST_F(PossibleContentsTest, TestIntersectWithCombinations) { } #if BINARYEN_TEST_DEBUG if (!PossibleContents::haveIntersection(combination, item)) { + std::cout << "\nFailure: no expected intersection. Indexes:\n"; for (auto index : indexes) { - std::cout << index << ' '; - combination.combine(item); + std::cout << index << "\n "; + vec[index].dump(std::cout); + std::cout << '\n'; } - std::cout << '\n'; std::cout << "combo:\n"; combination.dump(std::cout); std::cout << "\ncompared item (index " << index << "):\n"; @@ -377,6 +396,24 @@ TEST_F(PossibleContentsTest, TestIntersectWithCombinations) { } #endif assertHaveIntersection(combination, item); + + // Test intersectWithFullCone() method, which is supported with a full + // cone type. In that case we can test that the intersection of A with + // A + B is simply A. + if (combination.isFullConeType()) { + auto intersection = item; + intersection.intersectWithFullCone(combination); + EXPECT_EQ(intersection, item); +#if BINARYEN_TEST_DEBUG + if (intersection != item) { + std::cout << "\nFailure: wrong intersection.\n"; + std::cout << "item: " << item << '\n'; + std::cout << "combination: " << combination << '\n'; + std::cout << "intersection: " << intersection << '\n'; + abort(); + } +#endif + } } // Move to the next permutation. @@ -417,13 +454,17 @@ TEST_F(PossibleContentsTest, TestIntersectWithCombinations) { exactI32, exactAnyref, exactFuncref, + exactDataref, exactI31ref, exactNonNullAnyref, exactNonNullFuncref, exactNonNullI31ref, exactFuncSignatureType, exactNonNullFuncSignatureType, - many}; + many, + coneAnyref, + coneFuncref, + coneFuncref1}; // After testing on the initial contents, also test using anything new that // showed up while combining them. @@ -434,10 +475,348 @@ TEST_F(PossibleContentsTest, TestIntersectWithCombinations) { } } +void assertIntersection(PossibleContents a, + PossibleContents b, + PossibleContents result) { + auto intersection = a; + intersection.intersectWithFullCone(b); + EXPECT_EQ(intersection, result); +} + +TEST_F(PossibleContentsTest, TestStructCones) { + /* + A E + / \ + B C + \ + D + */ + TypeBuilder builder(5); + builder.setHeapType(0, Struct(FieldList{})); + builder.setHeapType(1, Struct(FieldList{})); + builder.setHeapType(2, Struct(FieldList{})); + builder.setHeapType(3, Struct(FieldList{})); + builder.setHeapType(4, Struct(FieldList{})); + builder.setSubType(1, builder.getTempHeapType(0)); + builder.setSubType(2, builder.getTempHeapType(0)); + builder.setSubType(3, builder.getTempHeapType(2)); + auto result = builder.build(); + ASSERT_TRUE(result); + auto types = *result; + auto A = types[0]; + auto B = types[1]; + auto C = types[2]; + auto D = types[3]; + auto E = types[4]; + ASSERT_TRUE(B.getSuperType() == A); + ASSERT_TRUE(C.getSuperType() == A); + ASSERT_TRUE(D.getSuperType() == C); + + auto nullA = Type(A, Nullable); + auto nullB = Type(B, Nullable); + auto nullC = Type(C, Nullable); + auto nullD = Type(D, Nullable); + auto nullE = Type(E, Nullable); + + auto exactA = PossibleContents::exactType(nullA); + auto exactB = PossibleContents::exactType(nullB); + auto exactC = PossibleContents::exactType(nullC); + auto exactD = PossibleContents::exactType(nullD); + auto exactE = PossibleContents::exactType(nullE); + + auto nnA = Type(A, NonNullable); + auto nnB = Type(B, NonNullable); + auto nnC = Type(C, NonNullable); + auto nnD = Type(D, NonNullable); + auto nnE = Type(E, NonNullable); + + auto nnExactA = PossibleContents::exactType(nnA); + auto nnExactB = PossibleContents::exactType(nnB); + auto nnExactC = PossibleContents::exactType(nnC); + auto nnExactD = PossibleContents::exactType(nnD); + auto nnExactE = PossibleContents::exactType(nnE); + + assertCombination(exactA, exactA, exactA); + assertCombination(exactA, exactA, PossibleContents::coneType(nullA, 0)); + assertCombination(exactA, exactB, PossibleContents::coneType(nullA, 1)); + assertCombination(exactA, exactC, PossibleContents::coneType(nullA, 1)); + assertCombination(exactA, exactD, PossibleContents::coneType(nullA, 2)); + assertCombination(exactA, exactE, PossibleContents::coneType(dataref, 1)); + assertCombination( + exactA, exactDataref, PossibleContents::coneType(dataref, 1)); + + assertCombination(exactB, exactB, exactB); + assertCombination(exactB, exactC, PossibleContents::coneType(nullA, 1)); + assertCombination(exactB, exactD, PossibleContents::coneType(nullA, 2)); + assertCombination(exactB, exactE, PossibleContents::coneType(dataref, 2)); + assertCombination( + exactB, exactDataref, PossibleContents::coneType(dataref, 2)); + + assertCombination(exactC, exactC, exactC); + assertCombination(exactC, exactD, PossibleContents::coneType(nullC, 1)); + assertCombination(exactC, exactE, PossibleContents::coneType(dataref, 2)); + assertCombination( + exactC, exactDataref, PossibleContents::coneType(dataref, 2)); + + assertCombination(exactD, exactD, exactD); + assertCombination(exactD, exactE, PossibleContents::coneType(dataref, 3)); + assertCombination( + exactD, exactDataref, PossibleContents::coneType(dataref, 3)); + + assertCombination(exactE, exactE, exactE); + assertCombination( + exactE, exactDataref, PossibleContents::coneType(dataref, 1)); + + assertCombination(exactDataref, exactDataref, exactDataref); + + assertCombination( + exactDataref, exactAnyref, PossibleContents::coneType(anyref, 2)); + + // Combinations of cones. + assertCombination(PossibleContents::coneType(nullA, 5), + PossibleContents::coneType(nullA, 7), + PossibleContents::coneType(nullA, 7)); + + // Increment the cone of D as we go here, until it matters. + assertCombination(PossibleContents::coneType(nullA, 5), + PossibleContents::coneType(nullD, 2), + PossibleContents::coneType(nullA, 5)); + assertCombination(PossibleContents::coneType(nullA, 5), + PossibleContents::coneType(nullD, 3), + PossibleContents::coneType(nullA, 5)); + assertCombination(PossibleContents::coneType(nullA, 5), + PossibleContents::coneType(nullD, 4), + PossibleContents::coneType(nullA, 6)); + + assertCombination(PossibleContents::coneType(nullA, 5), + PossibleContents::coneType(nullE, 7), + PossibleContents::coneType(dataref, 8)); + + assertCombination(PossibleContents::coneType(nullB, 4), + PossibleContents::coneType(dataref, 1), + PossibleContents::coneType(dataref, 6)); + + // Combinations of cones and exact types. + assertCombination(exactA, + PossibleContents::coneType(nullA, 3), + PossibleContents::coneType(nullA, 3)); + assertCombination(exactA, + PossibleContents::coneType(nullD, 3), + PossibleContents::coneType(nullA, 5)); + assertCombination(exactD, + PossibleContents::coneType(nullA, 3), + PossibleContents::coneType(nullA, 3)); + assertCombination(exactA, + PossibleContents::coneType(nullE, 2), + PossibleContents::coneType(dataref, 3)); + + assertCombination(exactA, + PossibleContents::coneType(dataref, 1), + PossibleContents::coneType(dataref, 1)); + assertCombination(exactA, + PossibleContents::coneType(dataref, 2), + PossibleContents::coneType(dataref, 2)); + + assertCombination(exactDataref, + PossibleContents::coneType(nullB, 3), + PossibleContents::coneType(dataref, 5)); + + // Full cones. + assertCombination(PossibleContents::fullConeType(nullA), + exactA, + PossibleContents::fullConeType(nullA)); + assertCombination(PossibleContents::fullConeType(nullA), + PossibleContents::coneType(nullA, 2), + PossibleContents::fullConeType(nullA)); + + // All full cones with A remain full cones, except for E. + assertCombination(PossibleContents::fullConeType(nullA), + PossibleContents::fullConeType(nullA), + PossibleContents::fullConeType(nullA)); + assertCombination(PossibleContents::fullConeType(nullA), + PossibleContents::fullConeType(nullB), + PossibleContents::fullConeType(nullA)); + assertCombination(PossibleContents::fullConeType(nullA), + PossibleContents::fullConeType(nullC), + PossibleContents::fullConeType(nullA)); + assertCombination(PossibleContents::fullConeType(nullA), + PossibleContents::fullConeType(nullD), + PossibleContents::fullConeType(nullA)); + assertCombination(PossibleContents::fullConeType(nullA), + PossibleContents::fullConeType(nullE), + PossibleContents::fullConeType(dataref)); + + // Intersections. Test with non-nullable types to avoid the null being a + // possible intersection. + assertHaveIntersection(nnExactA, nnExactA); + assertLackIntersection(nnExactA, nnExactB); + assertLackIntersection(nnExactA, nnExactC); + assertLackIntersection(nnExactA, nnExactD); + assertLackIntersection(nnExactA, nnExactE); + + assertHaveIntersection(PossibleContents::coneType(nnA, 1), nnExactB); + assertHaveIntersection(PossibleContents::coneType(nnA, 1), nnExactC); + assertHaveIntersection(PossibleContents::coneType(nnA, 2), nnExactD); + + assertLackIntersection(PossibleContents::coneType(nnA, 1), nnExactD); + assertLackIntersection(PossibleContents::coneType(nnA, 1), nnExactE); + assertLackIntersection(PossibleContents::coneType(nnA, 2), nnExactE); + + assertHaveIntersection(PossibleContents::coneType(nnA, 1), + PossibleContents::coneType(nnC, 100)); + assertLackIntersection(PossibleContents::coneType(nnA, 1), + PossibleContents::coneType(nnD, 100)); + + // Neither is a subtype of the other, but nulls are possible, so a null can be + // the intersection. + assertHaveIntersection(PossibleContents::fullConeType(nullA), + PossibleContents::fullConeType(nullE)); + + // Without null on one side, we cannot intersect. + assertLackIntersection(PossibleContents::fullConeType(nnA), + PossibleContents::fullConeType(nullE)); + + // Computing intersections is supported with a full cone type. + assertIntersection(none, PossibleContents::fullConeType(nnA), none); + assertIntersection(many, + PossibleContents::fullConeType(nnA), + PossibleContents::fullConeType(nnA)); + assertIntersection(many, + PossibleContents::fullConeType(nullA), + PossibleContents::fullConeType(nullA)); + + assertIntersection(exactA, PossibleContents::fullConeType(nullA), exactA); + assertIntersection(nnExactA, PossibleContents::fullConeType(nullA), nnExactA); + assertIntersection(exactA, PossibleContents::fullConeType(nnA), nnExactA); + + assertIntersection(exactB, PossibleContents::fullConeType(nullA), exactB); + assertIntersection(nnExactB, PossibleContents::fullConeType(nullA), nnExactB); + assertIntersection(exactB, PossibleContents::fullConeType(nnA), nnExactB); + + auto literalNullA = PossibleContents::literal(Literal::makeNull(A)); + + assertIntersection( + literalNullA, PossibleContents::fullConeType(nullA), literalNullA); + assertIntersection(literalNullA, PossibleContents::fullConeType(nnA), none); + + assertIntersection( + literalNullA, PossibleContents::fullConeType(nullB), literalNullA); + assertIntersection(literalNullA, PossibleContents::fullConeType(nnB), none); + + assertIntersection( + literalNullA, PossibleContents::fullConeType(nullE), literalNullA); + assertIntersection(literalNullA, PossibleContents::fullConeType(nnE), none); + + assertIntersection(exactA, + PossibleContents::fullConeType(nullB), + PossibleContents::literal(Literal::makeNull(B))); + assertIntersection(nnExactA, PossibleContents::fullConeType(nullB), none); + assertIntersection(exactA, PossibleContents::fullConeType(nnB), none); + + assertIntersection(PossibleContents::coneType(nnA, 1), + PossibleContents::fullConeType(nnB), + nnExactB); + assertIntersection(PossibleContents::coneType(nnB, 1), + PossibleContents::fullConeType(nnA), + PossibleContents::coneType(nnB, 1)); + assertIntersection(PossibleContents::coneType(nnD, 2), + PossibleContents::fullConeType(nnA), + PossibleContents::coneType(nnD, 2)); + assertIntersection(PossibleContents::coneType(nnA, 5), + PossibleContents::fullConeType(nnD), + PossibleContents::coneType(nnD, 3)); + + assertIntersection(PossibleContents::coneType(nnA, 1), + PossibleContents::fullConeType(nnD), + none); + + // Globals stay as globals if their type is in the cone. Otherwise, they lose + // the global info and we compute a normal cone intersection on them. The + // same for literals. + assertIntersection( + funcGlobal, PossibleContents::fullConeType(funcref), funcGlobal); + + auto signature = Type(Signature(Type::none, Type::none), Nullable); + assertIntersection( + nonNullFunc, PossibleContents::fullConeType(signature), nonNullFunc); + assertIntersection(funcGlobal, + PossibleContents::fullConeType(signature), + PossibleContents::fullConeType(signature)); + + // Incompatible hierarchies have no intersection. + assertIntersection( + literalNullA, PossibleContents::fullConeType(funcref), none); + + // Subcontents. This API only supports the case where one of the inputs is a + // full cone type. + // First, compare exact types to such a cone. + EXPECT_TRUE(PossibleContents::isSubContents( + exactA, PossibleContents::fullConeType(nullA))); + EXPECT_TRUE(PossibleContents::isSubContents( + nnExactA, PossibleContents::fullConeType(nnA))); + EXPECT_TRUE(PossibleContents::isSubContents( + nnExactA, PossibleContents::fullConeType(nullA))); + EXPECT_TRUE(PossibleContents::isSubContents( + nnExactD, PossibleContents::fullConeType(nullA))); + + EXPECT_FALSE(PossibleContents::isSubContents( + exactA, PossibleContents::fullConeType(nnA))); + EXPECT_FALSE(PossibleContents::isSubContents( + exactA, PossibleContents::fullConeType(nullB))); + + // Next, compare cones. + EXPECT_TRUE( + PossibleContents::isSubContents(PossibleContents::fullConeType(nullA), + PossibleContents::fullConeType(nullA))); + EXPECT_TRUE( + PossibleContents::isSubContents(PossibleContents::fullConeType(nnA), + PossibleContents::fullConeType(nullA))); + EXPECT_TRUE(PossibleContents::isSubContents( + PossibleContents::fullConeType(nnA), PossibleContents::fullConeType(nnA))); + EXPECT_TRUE( + PossibleContents::isSubContents(PossibleContents::fullConeType(nullD), + PossibleContents::fullConeType(nullA))); + + EXPECT_FALSE( + PossibleContents::isSubContents(PossibleContents::fullConeType(nullA), + PossibleContents::fullConeType(nnA))); + EXPECT_FALSE( + PossibleContents::isSubContents(PossibleContents::fullConeType(nullA), + PossibleContents::fullConeType(nullD))); + + // Trivial values. + EXPECT_TRUE(PossibleContents::isSubContents( + PossibleContents::none(), PossibleContents::fullConeType(nullA))); + EXPECT_FALSE(PossibleContents::isSubContents( + PossibleContents::many(), PossibleContents::fullConeType(nullA))); + + EXPECT_TRUE(PossibleContents::isSubContents( + anyNull, PossibleContents::fullConeType(nullA))); + EXPECT_FALSE(PossibleContents::isSubContents( + anyNull, PossibleContents::fullConeType(nnA))); + + // Tests cases with a full cone only on the left. Such a cone is only a sub- + // contents of Many. + EXPECT_FALSE(PossibleContents::isSubContents( + PossibleContents::fullConeType(nullA), exactA)); + EXPECT_FALSE(PossibleContents::isSubContents( + PossibleContents::fullConeType(nullA), nnExactA)); + + EXPECT_FALSE(PossibleContents::isSubContents( + PossibleContents::fullConeType(nullA), PossibleContents::none())); + EXPECT_TRUE(PossibleContents::isSubContents( + PossibleContents::fullConeType(nullA), PossibleContents::many())); + + EXPECT_FALSE(PossibleContents::isSubContents( + PossibleContents::fullConeType(nullA), anyNull)); + EXPECT_FALSE(PossibleContents::isSubContents( + PossibleContents::fullConeType(nnA), anyNull)); +} + TEST_F(PossibleContentsTest, TestOracleManyTypes) { // Test for a node with many possible types. The pass limits how many it // notices to not use excessive memory, so even though 4 are possible here, - // we'll just report that more than one is possible ("many"). + // we'll just report that more than one is possible, a cone of data. auto wasm = parse(R"( (module (type $A (struct_subtype (field i32) data)) @@ -462,7 +841,10 @@ TEST_F(PossibleContentsTest, TestOracleManyTypes) { ) )"); ContentOracle oracle(*wasm); - // The function's body should be Many. - EXPECT_TRUE( - oracle.getContents(ResultLocation{wasm->getFunction("foo"), 0}).isMany()); + // The body's contents must be a cone of data with depth 1. + auto bodyContents = + oracle.getContents(ResultLocation{wasm->getFunction("foo"), 0}); + ASSERT_TRUE(bodyContents.isConeType()); + EXPECT_TRUE(bodyContents.getType().getHeapType() == HeapType::data); + EXPECT_TRUE(bodyContents.getCone().depth == 1); } diff --git a/test/lit/passes/gufa-refs.wast b/test/lit/passes/gufa-refs.wast index e02fdc70a..9e17a3a69 100644 --- a/test/lit/passes/gufa-refs.wast +++ b/test/lit/passes/gufa-refs.wast @@ -2452,11 +2452,11 @@ (type $substruct (struct_subtype (field i32) (field i32) $struct)) ;; CHECK: (type $none_=>_none (func_subtype func)) + ;; CHECK: (type $i32_=>_none (func_subtype (param i32) func)) + ;; CHECK: (type $subsubstruct (struct_subtype (field i32) (field i32) (field i32) $substruct)) (type $subsubstruct (struct_subtype (field i32) (field i32) (field i32) $substruct)) - ;; CHECK: (type $i32_=>_none (func_subtype (param i32) func)) - ;; CHECK: (type $other (struct_subtype data)) (type $other (struct_subtype data)) @@ -2469,12 +2469,16 @@ ;; CHECK: (import "a" "b" (func $import (result i32))) (import "a" "b" (func $import (result i32))) + ;; CHECK: (export "test-cones" (func $test-cones)) + ;; CHECK: (export "ref.test-inexact" (func $ref.test-inexact)) ;; CHECK: (export "ref.eq-zero" (func $ref.eq-zero)) ;; CHECK: (export "ref.eq-unknown" (func $ref.eq-unknown)) + ;; CHECK: (export "ref.eq-cone" (func $ref.eq-cone)) + ;; CHECK: (export "local-no" (func $ref.eq-local-no)) ;; CHECK: (func $test (type $none_=>_none) @@ -2608,6 +2612,114 @@ ) ) + ;; CHECK: (func $test-cones (type $i32_=>_none) (param $x i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast_static $struct + ;; CHECK-NEXT: (select (result (ref null $struct)) + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.null none) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast_static $struct + ;; CHECK-NEXT: (select (result (ref $struct)) + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new $substruct + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: (i32.const 3) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast_static $substruct + ;; CHECK-NEXT: (select (result (ref $struct)) + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (i32.const 4) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new $substruct + ;; CHECK-NEXT: (i32.const 5) + ;; CHECK-NEXT: (i32.const 6) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $test-cones (export "test-cones") (param $x i32) + ;; The input to the ref.cast is potentially null, so we cannot infer here. + (drop + (ref.cast_static $struct + (select + (struct.new $struct + (i32.const 0) + ) + (ref.null any) + (local.get $x) + ) + ) + ) + ;; The input to the ref.cast is either $struct or $substruct, both of which + ;; work, so we cannot optimize anything here away. + (drop + (ref.cast_static $struct + (select + (struct.new $struct + (i32.const 1) + ) + (struct.new $substruct + (i32.const 2) + (i32.const 3) + ) + (local.get $x) + ) + ) + ) + ;; As above, but now we test with $substruct, so one possibility fails and + ;; one succeeds. We cannot infer here either. + (drop + (ref.cast_static $substruct + (select + (struct.new $struct + (i32.const 4) + ) + (struct.new $substruct + (i32.const 5) + (i32.const 6) + ) + (local.get $x) + ) + ) + ) + ;; Two possible types, both are supertypes, so neither is a subtype, and we + ;; can infer an unreachable. The combination of these two is a cone from + ;; $struct of depth 1, which does not overlap with $subsubstruct. + (drop + (ref.cast_static $subsubstruct + (select + (struct.new $struct + (i32.const 7) + ) + (struct.new $substruct + (i32.const 8) + (i32.const 9) + ) + (local.get $x) + ) + ) + ) + ) + ;; CHECK: (func $ref.test-exact (type $none_=>_none) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (i32.const 0) @@ -2663,18 +2775,7 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (ref.test_static $struct - ;; CHECK-NEXT: (select (result (ref $struct)) - ;; CHECK-NEXT: (struct.new $struct - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (struct.new $substruct - ;; CHECK-NEXT: (i32.const 2) - ;; CHECK-NEXT: (i32.const 3) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (local.get $x) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 1) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.test_static $substruct @@ -2691,18 +2792,7 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (ref.test_static $subsubstruct - ;; CHECK-NEXT: (select (result (ref $struct)) - ;; CHECK-NEXT: (struct.new $struct - ;; CHECK-NEXT: (i32.const 7) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (struct.new $substruct - ;; CHECK-NEXT: (i32.const 8) - ;; CHECK-NEXT: (i32.const 9) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (local.get $x) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 0) ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) (func $ref.test-inexact (export "ref.test-inexact") (param $x i32) @@ -2719,7 +2809,9 @@ ) ) ;; The input to the ref.test is either $struct or $substruct, both of which - ;; work, so here we can infer a 1 - but we need a cone type for that TODO + ;; work, so here we can infer a 1. We do so using a cone type: the + ;; combination of those two types is a cone on $struct of depth 1, and that + ;; cone is 100% a subtype of $struct, so the test will succeed. (drop (ref.test_static $struct (select @@ -2751,7 +2843,8 @@ ) ) ;; Two possible types, both are supertypes, so neither is a subtype, and we - ;; can infer a 0 - but we need more precise type info than we have TODO + ;; can infer a 0. The combination of these two is a cone from $struct of + ;; depth 1, which does not overlap with $subsubstruct. (drop (ref.test_static $subsubstruct (select @@ -2832,25 +2925,6 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.eq - ;; CHECK-NEXT: (struct.new $struct - ;; CHECK-NEXT: (i32.const 1) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (select (result (ref $substruct)) - ;; CHECK-NEXT: (struct.new $substruct - ;; CHECK-NEXT: (i32.const 2) - ;; CHECK-NEXT: (i32.const 3) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (struct.new $subsubstruct - ;; CHECK-NEXT: (i32.const 4) - ;; CHECK-NEXT: (i32.const 5) - ;; CHECK-NEXT: (i32.const 6) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (local.get $x) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (ref.eq ;; CHECK-NEXT: (local.get $struct) ;; CHECK-NEXT: (local.get $other) ;; CHECK-NEXT: ) @@ -2918,28 +2992,6 @@ (ref.null $struct) ) ) - ;; One side has two possible types, which we see as Many, and so we cannot - ;; infer anything here. With a cone type, however, we could infer a 0. - ;; TODO: add more tests for cone types here when we get them - (drop - (ref.eq - (struct.new $struct - (i32.const 1) - ) - (select - (struct.new $substruct - (i32.const 2) - (i32.const 3) - ) - (struct.new $subsubstruct - (i32.const 4) - (i32.const 5) - (i32.const 6) - ) - (local.get $x) - ) - ) - ) ;; When nulls are possible, we cannot infer anything (with or without the ;; same type on both sides). (drop @@ -2998,6 +3050,191 @@ ) ) + ;; CHECK: (func $ref.eq-cone (type $i32_=>_none) (param $x i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (struct.new $substruct + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (select (result (ref $struct)) + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (i32.const 3) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new $subsubstruct + ;; CHECK-NEXT: (i32.const 4) + ;; CHECK-NEXT: (i32.const 5) + ;; CHECK-NEXT: (i32.const 6) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (struct.new $substruct + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (select (result (ref $struct)) + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (i32.const 3) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new $substruct + ;; CHECK-NEXT: (i32.const 4) + ;; CHECK-NEXT: (i32.const 5) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (struct.new $substruct + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (select (result (ref $substruct)) + ;; CHECK-NEXT: (struct.new $substruct + ;; CHECK-NEXT: (i32.const 3) + ;; CHECK-NEXT: (i32.const 4) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new $subsubstruct + ;; CHECK-NEXT: (i32.const 5) + ;; CHECK-NEXT: (i32.const 6) + ;; CHECK-NEXT: (i32.const 7) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (struct.new $substruct + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (select (result (ref $substruct)) + ;; CHECK-NEXT: (struct.new $substruct + ;; CHECK-NEXT: (i32.const 3) + ;; CHECK-NEXT: (i32.const 4) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new $substruct + ;; CHECK-NEXT: (i32.const 5) + ;; CHECK-NEXT: (i32.const 6) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $ref.eq-cone (export "ref.eq-cone") (param $x i32) + ;; One side has two possible types, so we have a cone there. This cone is + ;; of subtypes of the other type, which is exact, so we cannot intersect + ;; here and we infer a 0. + (drop + (ref.eq + (struct.new $struct + (i32.const 1) + ) + (select + (struct.new $substruct + (i32.const 2) + (i32.const 3) + ) + (struct.new $subsubstruct + (i32.const 4) + (i32.const 5) + (i32.const 6) + ) + (local.get $x) + ) + ) + ) + ;; Now the cone is large enough, so there might be an intersection, and we + ;; do not optimize (the cone of $struct and $subsubstruct contains + ;; $substruct which is in the middle). + (drop + (ref.eq + (struct.new $substruct + (i32.const 1) + (i32.const 2) + ) + (select + (struct.new $struct + (i32.const 3) + ) + (struct.new $subsubstruct + (i32.const 4) + (i32.const 5) + (i32.const 6) + ) + (local.get $x) + ) + ) + ) + (drop + (ref.eq + (struct.new $substruct + (i32.const 1) + (i32.const 2) + ) + (select + (struct.new $struct + (i32.const 3) + ) + (struct.new $substruct ;; As above, but with this changed. We still + (i32.const 4) ;; cannot optimize. + (i32.const 5) + ) + (local.get $x) + ) + ) + ) + (drop + (ref.eq + (struct.new $substruct + (i32.const 1) + (i32.const 2) + ) + (select + (struct.new $substruct ;; As above, but with this changed. We still + (i32.const 3) ;; cannot optimize. + (i32.const 4) + ) + (struct.new $subsubstruct + (i32.const 5) + (i32.const 6) + (i32.const 7) + ) + (local.get $x) + ) + ) + ) + (drop + (ref.eq + (struct.new $substruct + (i32.const 1) + (i32.const 2) + ) + (select + (struct.new $substruct + (i32.const 3) + (i32.const 4) + ) + (struct.new $substruct ;; As above, but with this changed. We still + (i32.const 5) ;; cannot optimize (here the type is actually + (i32.const 6) ;; exact, despite the select). + ) + (local.get $x) + ) + ) + ) + ) + ;; CHECK: (func $unreachable (type $none_=>_ref|eq|) (result (ref eq)) ;; CHECK-NEXT: (unreachable) ;; CHECK-NEXT: ) |