[Wasm GC] [GUFA] Add initial ConeType support (#5116)

A cone type is a PossibleContents that has a base type and a depth, and it
contains all subtypes up to that depth. So depth 0 is an exact type from
before, etc.

This only adds cone type computations when combining types, that is, when we
combine two exact types we might get a cone, etc. This does not yet use the
cone info in all places (like struct gets and sets), and it does not yet define roots
of cone types, all of which is left for later. IOW this is the MVP of cone types that
is just enough to add them + pass tests + test the new functionality.

2 files changed, 711 insertions, 92 deletions

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: )