[GUFA] Infer a RefEq value of 0 when possible (#5081)

If the PossibleContents for the two sides have no possible intersection then the
result must be 0.

3 files changed, 115 insertions, 11 deletions

diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp
index 83d55e6f9..4755c9904 100644
--- a/src/ir/possible-contents.cpp
+++ b/src/ir/possible-contents.cpp
@@ -86,7 +86,7 @@ void PossibleContents::combine(const PossibleContents& other) {
     // combination here is if they have the same type (since we've already ruled
     // out the case of them being equal). If they have the same type then
     // neither is a reference and we can emit an exact type (since subtyping is
-    // not relevant for non-references.
+    // not relevant for non-references).
     if (type == otherType) {
       value = ExactType(type);
     } else {
@@ -132,6 +132,48 @@ void PossibleContents::combine(const PossibleContents& other) {
   value = Many();
 }
 
+bool PossibleContents::haveIntersection(const PossibleContents& a,
+                                        const PossibleContents& b) {
+  if (a.isNone() || b.isNone()) {
+    // One is the empty set, so nothing can intersect here.
+    return false;
+  }
+
+  if (a.isMany() || b.isMany()) {
+    // One is the set of all things, so definitely something can intersect since
+    // we've ruled out an empty set for both.
+    return true;
+  }
+
+  auto aType = a.getType();
+  auto bType = b.getType();
+
+  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.
+    return true;
+  }
+
+  if (a.hasExactType() && b.hasExactType() && a.getType() != b.getType()) {
+    // The values must be different since their types are different.
+    return false;
+  }
+
+  if (!Type::isSubType(aType, bType) && !Type::isSubType(bType, aType)) {
+    // No type can appear in both a and b, so the types differ, so the values
+    // differ.
+    return false;
+  }
+
+  // TODO: we can also optimize things like different Literals, but existing
+  //       passes do such things already so it is low priority.
+
+  // It appears they can intersect.
+  return true;
+}
+
 namespace {
 
 // We are going to do a very large flow operation, potentially, as we create
@@ -378,9 +420,6 @@ struct InfoCollector
       PossibleContents::literal(Literal(curr->func, curr->type.getHeapType())));
   }
   void visitRefEq(RefEq* curr) {
-    // TODO: optimize when possible (e.g. when both sides must contain the same
-    //       global, or if we infer exact types that are different then the
-    //       result must be 0)
     addRoot(curr);
   }
   void visitTableGet(TableGet* curr) {
@@ -416,12 +455,9 @@ struct InfoCollector
   }
 
   void visitRefCast(RefCast* curr) {
-    // We will handle this in a special way later during the flow, as ref.cast
-    // only allows valid values to flow through.
     addChildParentLink(curr->ref, curr);
   }
   void visitRefTest(RefTest* curr) {
-    // We will handle this similarly to RefCast.
     addChildParentLink(curr->ref, curr);
   }
   void visitBrOn(BrOn* curr) {
@@ -1114,7 +1150,11 @@ private:
   // values to flow through it.
   void flowRefCast(const PossibleContents& contents, RefCast* cast);
 
-  // The possible contents may allow us to infer an outcome, like with RefCast.
+  // The possible contents may allow us to infer an outcome in various
+  // instructions. If the expression has a single child, that is what is
+  // updated by the new |contents| (which we pass in to avoid doing an extra
+  // lookup); if there is more than one child, then to keep the code simple we
+  // expect the function to look up the children's effects manually.
   void flowRefTest(const PossibleContents& contents, RefTest* test);
 
   // We will need subtypes during the flow, so compute them once ahead of time.
@@ -1734,6 +1774,7 @@ void Flower::flowRefCast(const PossibleContents& contents, RefCast* cast) {
 }
 
 void Flower::flowRefTest(const PossibleContents& contents, RefTest* test) {
+  // TODO move to gufa pass; this must happen at the end
   PossibleContents filtered;
   if (contents.isMany()) {
     // Just pass the Many through.
@@ -1792,8 +1833,6 @@ void Flower::dump(Location location) {
     std::cout << "  sigresultloc " << '\n';
   } else if (auto* loc = std::get_if<NullLocation>(&location)) {
     std::cout << "  Nullloc " << loc->type << '\n';
-  } else if (auto* loc = std::get_if<UniqueLocation>(&location)) {
-    std::cout << "  Specialloc " << loc->index << '\n';
   } else {
     std::cout << "  (other)\n";
   }
diff --git a/src/ir/possible-contents.h b/src/ir/possible-contents.h
index 38bc263e9..f3ad37d92 100644
--- a/src/ir/possible-contents.h
+++ b/src/ir/possible-contents.h
@@ -167,6 +167,13 @@ public:
   // This returns false for None and Many, for whom it is not well-defined.
   bool hasExactType() const { return isExactType() || isLiteral(); }
 
+  // Returns whether the given contents have any intersection, that is, whether
+  // some value exists that can appear in both |a| and |b|. For example, if
+  // either is None, or if they are both ExactTypes but of different types, then
+  // they have no intersection.
+  static bool haveIntersection(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.
@@ -529,6 +536,13 @@ public:
     return iter->second;
   }
 
+  // Helper for the common case of an expression location that is not a
+  // multivalue.
+  PossibleContents getContents(Expression* curr) {
+    assert(curr->type.size() == 1);
+    return getContents(ExpressionLocation{curr, 0});
+  }
+
 private:
   std::unordered_map<Location, PossibleContents> locationContents;
 };
diff --git a/src/passes/GUFA.cpp b/src/passes/GUFA.cpp
index 1467b1312..53693420e 100644
--- a/src/passes/GUFA.cpp
+++ b/src/passes/GUFA.cpp
@@ -69,6 +69,34 @@ struct GUFAOptimizer
 
   bool optimized = false;
 
+  // As we optimize, we replace expressions and create new ones. For new ones
+  // we can infer their contents based on what they replaced, e.g., if we
+  // replaced a local.get with a const, then the PossibleContents of the const
+  // are the same as the local.get (in this simple example, we could also just
+  // infer them from the const itself, of course). Rather than update the
+  // ContentOracle with new contents, which is a shared object among threads,
+  // each function-parallel worker stores a map of new things it created to the
+  // contents for them.
+  std::unordered_map<Expression*, PossibleContents> newContents;
+
+  Expression* replaceCurrent(Expression* rep) {
+    newContents[rep] = oracle.getContents(getCurrent());
+
+    return WalkerPass<
+      PostWalker<GUFAOptimizer,
+                 UnifiedExpressionVisitor<GUFAOptimizer>>>::replaceCurrent(rep);
+  }
+
+  const PossibleContents getContents(Expression* curr) {
+    // If this is something we added ourselves, use that; otherwise the info is
+    // in the oracle.
+    if (auto iter = newContents.find(curr); iter != newContents.end()) {
+      return iter->second;
+    }
+
+    return oracle.getContents(curr);
+  }
+
   void visitExpression(Expression* curr) {
     // Skip things we can't improve in any way.
     auto type = curr->type;
@@ -91,7 +119,7 @@ struct GUFAOptimizer
 
     // Ok, this is an interesting location that we might optimize. See what the
     // oracle says is possible there.
-    auto contents = oracle.getContents(ExpressionLocation{curr, 0});
+    auto contents = getContents(curr);
 
     auto& options = getPassOptions();
     auto& wasm = *getModule();
@@ -182,6 +210,29 @@ struct GUFAOptimizer
     }
   }
 
+  void visitRefEq(RefEq* curr) {
+    if (curr->type == Type::unreachable) {
+      // Leave this for DCE.
+      return;
+    }
+
+    auto leftContents = getContents(curr->left);
+    auto rightContents = getContents(curr->right);
+
+    if (!PossibleContents::haveIntersection(leftContents, rightContents)) {
+      // The contents prove the two sides cannot contain the same reference, so
+      // we infer 0.
+      //
+      // Note that this is fine even if one of the sides is None. In that case,
+      // no value is possible there, and the intersection is empty, so we will
+      // get here and emit a 0. That 0 will never be reached as the None child
+      // will be turned into an unreachable, so it does not cause any problem.
+      auto* result = Builder(*getModule()).makeConst(Literal(int32_t(0)));
+      replaceCurrent(getDroppedChildrenAndAppend(
+        curr, *getModule(), getPassOptions(), result));
+    }
+  }
+
   // TODO: If an instruction would trap on null, like struct.get, we could
   //       remove it here if it has no possible contents and if we are in
   //       traps-never-happen mode (that is, we'd have proven it can only trap,