Do not special case ref.null in `LUBFinder` (#5307)

Before we implemented bottom heap types, `ref.null` had to be annotated with
specific types. The `LUBFinder` utility ignored these types so that it could
find the best LUB from all considered non-null expressions, then go back and
update the type annotations on the nulls to match that LUB. Now that we have
bottom types, however, none of that is necessary, and in fact ignoring nulls can
miss possible refinements to bottom types.

Update and simplify `LUBFinder` so that it is a simple wrapper around the
underlying `Type::getLeastUpperBound` utility with no additional logic. Update
tests to account for the more powerful optimizations.

7 files changed, 31 insertions, 120 deletions

diff --git a/src/ir/lubs.cpp b/src/ir/lubs.cpp
index 852c27677..ead1299b5 100644
--- a/src/ir/lubs.cpp
+++ b/src/ir/lubs.cpp
@@ -45,15 +45,15 @@ LUBFinder getResultsLUB(Function* func, Module& wasm) {
   //  )
   ReFinalize().walkFunctionInModule(func, &wasm);
 
-  lub.noteUpdatableExpression(func->body);
-  if (lub.getBestPossible() == originalType) {
+  lub.note(func->body->type);
+  if (lub.getLUB() == originalType) {
     return lub;
   }
 
   // Scan the body and look at the returns. First, return expressions.
   for (auto* ret : FindAll<Return>(func->body).list) {
-    lub.noteUpdatableExpression(ret->value);
-    if (lub.getBestPossible() == originalType) {
+    lub.note(ret->value->type);
+    if (lub.getLUB() == originalType) {
       return lub;
     }
   }
@@ -64,7 +64,7 @@ LUBFinder getResultsLUB(Function* func, Module& wasm) {
     // Return whether we still look ok to do the optimization. If this is
     // false then we can stop here.
     lub.note(type);
-    return lub.getBestPossible() != originalType;
+    return lub.getLUB() != originalType;
   };
 
   for (auto* call : FindAll<Call>(func->body).list) {
diff --git a/src/ir/lubs.h b/src/ir/lubs.h
index 05c6b07fd..afc5c0676 100644
--- a/src/ir/lubs.h
+++ b/src/ir/lubs.h
@@ -25,16 +25,7 @@ namespace wasm {
 //
 // Helper to find a LUB of a series of expressions. This works incrementally so
 // that if we see we are not improving on an existing type then we can stop
-// early. It also notes null expressions that can be updated later, and if
-// updating them would allow a better LUB it can do so. That is, given this:
-//
-//   (ref.null any)  ;; an expression that we can update
-//   (.. something of type data ..)
-//
-// We can update that null to type (ref null data) which would allow setting
-// that as the LUB. This is important in cases where there is a null initial
-// value in a field, for example: we should not let the type there prevent us
-// from optimizing - after all, all nulls compare equally anyhow.
+// early.
 //
 struct LUBFinder {
   LUBFinder() {}
@@ -44,61 +35,11 @@ struct LUBFinder {
   // Note another type to take into account in the lub.
   void note(Type type) { lub = Type::getLeastUpperBound(lub, type); }
 
-  // Note an expression that can be updated, that is, that we can modify in
-  // safe ways if doing so would allow us to get a better lub. The specific
-  // optimization possible here involves nulls, see the top comment.
-  void noteUpdatableExpression(Expression* curr) {
-    if (auto* null = curr->dynCast<RefNull>()) {
-      nulls.insert(null);
-    } else {
-      note(curr->type);
-    }
-  }
-
-  void noteNullDefault() {
-    // A default value is indicated by a null pointer.
-    nulls.insert(nullptr);
-  }
-
-  // Returns whether we noted any (reachable) value. This ignores nulls, as they
-  // do not contribute type information - we do not try to find a lub based on
-  // them (rather we update them to the LUB).
+  // Returns whether we noted any (reachable) value.
   bool noted() { return lub != Type::unreachable; }
 
-  // Returns the best possible lub. This ignores updatable nulls for the reasons
-  // mentioned above, since they will not limit us, aside from making the type
-  // nullable if nulls exist. This does not update the nulls.
-  Type getBestPossible() {
-    if (lub == Type::unreachable) {
-      // Perhaps if we have seen nulls we could compute a lub on them, but it's
-      // not clear that is helpful.
-      return lub;
-    }
-
-    // We have a lub. Make it nullable if we need to.
-    if (!lub.isNullable() && !nulls.empty()) {
-      return Type(lub.getHeapType(), Nullable);
-    } else {
-      return lub;
-    }
-  }
-
-  // Update the nulls for the best possible LUB, if we found one.
-  void updateNulls() {
-    auto newType = getBestPossible();
-    if (newType != Type::unreachable) {
-      for (auto* null : nulls) {
-        // Default null values (represented as nullptr here) do not need to be
-        // updated. Aside from that, if this null is already of a more specific
-        // type, also do not update it - it's never worth making a type less
-        // specific. What we care about here is making sure the nulls are all
-        // specific enough given the LUB that is being applied.
-        if (null && !Type::isSubType(null->type, newType)) {
-          null->finalize(newType);
-        }
-      }
-    }
-  }
+  // Returns the lub.
+  Type getLUB() { return lub; }
 
   // Combines the information in another LUBFinder into this one, and returns
   // whether we changed anything.
@@ -106,26 +47,13 @@ struct LUBFinder {
     // Check if the lub was changed.
     auto old = lub;
     note(other.lub);
-    bool changed = old != lub;
-
-    // Check if we added new updatable nulls.
-    for (auto* null : other.nulls) {
-      if (nulls.insert(null).second) {
-        changed = true;
-      }
-    }
-
-    return changed;
+    return old != lub;
   }
 
 private:
   // The least upper bound. As we go this always contains the latest value based
   // on everything we've seen so far, except for nulls.
   Type lub = Type::unreachable;
-
-  // Nulls that we can update. A nullptr here indicates an "implicit" null, that
-  // is, a null default value.
-  std::unordered_set<RefNull*> nulls;
 };
 
 namespace LUB {
diff --git a/src/passes/DeadArgumentElimination.cpp b/src/passes/DeadArgumentElimination.cpp
index d319340b8..f739e9263 100644
--- a/src/passes/DeadArgumentElimination.cpp
+++ b/src/passes/DeadArgumentElimination.cpp
@@ -381,8 +381,8 @@ private:
       auto& lub = lubs[i];
       for (auto* call : calls) {
         auto* operand = call->operands[i];
-        lub.noteUpdatableExpression(operand);
-        if (lub.getBestPossible() == originalType) {
+        lub.note(operand->type);
+        if (lub.getLUB() == originalType) {
           // We failed to refine this parameter to anything more specific.
           break;
         }
@@ -392,7 +392,7 @@ private:
       if (!lub.noted()) {
         return;
       }
-      newParamTypes.push_back(lub.getBestPossible());
+      newParamTypes.push_back(lub.getLUB());
     }
 
     // Check if we are able to optimize here before we do the work to scan the
@@ -405,12 +405,7 @@ private:
     // We can do this!
     TypeUpdating::updateParamTypes(func, newParamTypes, *module);
 
-    // Update anything the lubs need to update.
-    for (auto& lub : lubs) {
-      lub.updateNulls();
-    }
-
-    // Also update the function's type.
+    // Update the function's type.
     func->setParams(newParams);
   }
 
@@ -436,9 +431,8 @@ private:
     if (!lub.noted()) {
       return false;
     }
-    auto newType = lub.getBestPossible();
+    auto newType = lub.getLUB();
     if (newType != func->getResults()) {
-      lub.updateNulls();
       func->setResults(newType);
       for (auto* call : calls) {
         if (call->type != Type::unreachable) {
diff --git a/src/passes/GlobalRefining.cpp b/src/passes/GlobalRefining.cpp
index 0576e3285..67a186f92 100644
--- a/src/passes/GlobalRefining.cpp
+++ b/src/passes/GlobalRefining.cpp
@@ -59,7 +59,7 @@ struct GlobalRefining : public Pass {
     // Combine all the information we gathered and compute lubs.
     for (auto& [func, info] : analysis.map) {
       for (auto* set : info.sets) {
-        lubs[set->name].noteUpdatableExpression(set->value);
+        lubs[set->name].note(set->value->type);
       }
     }
 
@@ -73,7 +73,7 @@ struct GlobalRefining : public Pass {
       auto& lub = lubs[global->name];
 
       // Note the initial value.
-      lub.noteUpdatableExpression(global->init);
+      lub.note(global->init->type);
 
       // The initial value cannot be unreachable, but it might be null, and all
       // other values might be too. In that case, we've noted nothing useful
@@ -83,12 +83,11 @@ struct GlobalRefining : public Pass {
       }
 
       auto oldType = global->type;
-      auto newType = lub.getBestPossible();
+      auto newType = lub.getLUB();
       if (newType != oldType) {
         // We found an improvement!
         assert(Type::isSubType(newType, oldType));
         global->type = newType;
-        lub.updateNulls();
         optimized = true;
       }
     }
diff --git a/src/passes/LocalSubtyping.cpp b/src/passes/LocalSubtyping.cpp
index cf8570986..0d41434fc 100644
--- a/src/passes/LocalSubtyping.cpp
+++ b/src/passes/LocalSubtyping.cpp
@@ -134,8 +134,8 @@ struct LocalSubtyping : public WalkerPass<PostWalker<LocalSubtyping>> {
         // Find all the types assigned to the var, and compute the optimal LUB.
         LUBFinder lub;
         for (auto* set : setsForLocal[i]) {
-          lub.noteUpdatableExpression(set->value);
-          if (lub.getBestPossible() == oldType) {
+          lub.note(set->value->type);
+          if (lub.getLUB() == oldType) {
             break;
           }
         }
@@ -144,7 +144,7 @@ struct LocalSubtyping : public WalkerPass<PostWalker<LocalSubtyping>> {
           continue;
         }
 
-        auto newType = lub.getBestPossible();
+        auto newType = lub.getLUB();
         assert(newType != Type::none); // in valid wasm there must be a LUB
 
         // Remove non-nullability if we disallow that in locals.
@@ -165,7 +165,6 @@ struct LocalSubtyping : public WalkerPass<PostWalker<LocalSubtyping>> {
           func->vars[i - varBase] = newType;
           more = true;
           optimized = true;
-          lub.updateNulls();
 
           // Update gets and tees.
           for (auto* get : getsForLocal[i]) {
diff --git a/src/passes/SignatureRefining.cpp b/src/passes/SignatureRefining.cpp
index 132079b76..15b89b2a7 100644
--- a/src/passes/SignatureRefining.cpp
+++ b/src/passes/SignatureRefining.cpp
@@ -161,7 +161,7 @@ struct SignatureRefining : public Pass {
 
       auto updateLUBs = [&](const ExpressionList& operands) {
         for (Index i = 0; i < numParams; i++) {
-          paramLUBs[i].noteUpdatableExpression(operands[i]);
+          paramLUBs[i].note(operands[i]->type);
         }
       };
 
@@ -178,7 +178,7 @@ struct SignatureRefining : public Pass {
         if (!lub.noted()) {
           break;
         }
-        newParamsTypes.push_back(lub.getBestPossible());
+        newParamsTypes.push_back(lub.getLUB());
       }
       Type newParams;
       if (newParamsTypes.size() < numParams) {
@@ -197,7 +197,7 @@ struct SignatureRefining : public Pass {
         // value, or it can return a value but traps instead etc.).
         newResults = func->getResults();
       } else {
-        newResults = resultsLUB.getBestPossible();
+        newResults = resultsLUB.getLUB();
       }
 
       if (newParams == func->getParams() && newResults == func->getResults()) {
@@ -207,14 +207,7 @@ struct SignatureRefining : public Pass {
       // We found an improvement!
       newSignatures[type] = Signature(newParams, newResults);
 
-      // Update nulls as necessary, now that we are changing things.
-      if (newParams != func->getParams()) {
-        for (auto& lub : paramLUBs) {
-          lub.updateNulls();
-        }
-      }
       if (newResults != func->getResults()) {
-        resultsLUB.updateNulls();
         refinedResults = true;
 
         // Update the types of calls using the signature.
diff --git a/src/passes/TypeRefining.cpp b/src/passes/TypeRefining.cpp
index e9aa07ca6..6e2c96fce 100644
--- a/src/passes/TypeRefining.cpp
+++ b/src/passes/TypeRefining.cpp
@@ -53,7 +53,7 @@ struct FieldInfoScanner
                       HeapType type,
                       Index index,
                       FieldInfo& info) {
-    info.noteUpdatableExpression(expr);
+    info.note(expr->type);
   }
 
   void
@@ -61,7 +61,7 @@ struct FieldInfoScanner
     // Default values do not affect what the heap type of a field can be turned
     // into. Note them, however, as they force us to keep the type nullable.
     if (fieldType.isRef()) {
-      info.noteNullDefault();
+      info.note(Type(fieldType.getHeapType().getBottom(), Nullable));
     }
   }
 
@@ -173,9 +173,9 @@ struct TypeRefining : public Pass {
       if (auto super = type.getSuperType()) {
         auto& superFields = super->getStruct().fields;
         for (Index i = 0; i < superFields.size(); i++) {
-          auto newSuperType = finalInfos[*super][i].getBestPossible();
+          auto newSuperType = finalInfos[*super][i].getLUB();
           auto& info = finalInfos[type][i];
-          auto newType = info.getBestPossible();
+          auto newType = info.getLUB();
           if (!Type::isSubType(newType, newSuperType)) {
             // To ensure we are a subtype of the super's field, simply copy that
             // value, which is more specific than us.
@@ -210,10 +210,9 @@ struct TypeRefining : public Pass {
       for (Index i = 0; i < fields.size(); i++) {
         auto oldType = fields[i].type;
         auto& lub = finalInfos[type][i];
-        auto newType = lub.getBestPossible();
+        auto newType = lub.getLUB();
         if (newType != oldType) {
           canOptimize = true;
-          lub.updateNulls();
         }
       }
 
@@ -256,8 +255,7 @@ struct TypeRefining : public Pass {
         }
 
         auto oldType = curr->ref->type.getHeapType();
-        auto newFieldType =
-          parent.finalInfos[oldType][curr->index].getBestPossible();
+        auto newFieldType = parent.finalInfos[oldType][curr->index].getLUB();
         if (!Type::isSubType(newFieldType, curr->type)) {
           // This instruction is invalid, so it must be the result of the
           // situation described above: we ignored the read during our
@@ -298,7 +296,7 @@ struct TypeRefining : public Pass {
           if (!oldType.isRef()) {
             continue;
           }
-          auto newType = parent.finalInfos[oldStructType][i].getBestPossible();
+          auto newType = parent.finalInfos[oldStructType][i].getLUB();
           newFields[i].type = getTempType(newType);
         }
       }