Grand Unified Flow Analysis (GUFA) (#4598)

This tracks the possible contents in the entire program all at once using a single IR.
That is in contrast to say DeadArgumentElimination of LocalRefining etc., all of whom
look at one particular aspect of the program (function params and returns in DAE,
locals in LocalRefining). The cost is to build up an entire new IR, which takes a lot
of new code (mostly in the already-landed PossibleContents). Another cost
is this new IR is very big and requires a lot of time and memory to process.
The benefit is that this can find opportunities that are only obvious when looking
at the entire program, and also it can track information that is more specialized
than the normal type system in the IR - in particular, this can track an ExactType,
which is the case where we know the value is of a particular type exactly and not
a subtype.

2 files changed, 104 insertions, 15 deletions

diff --git a/src/ir/drop.h b/src/ir/drop.h
index 9ed5276ff..a13b83332 100644
--- a/src/ir/drop.h
+++ b/src/ir/drop.h
@@ -17,6 +17,7 @@
 #ifndef wasm_ir_drop_h
 #define wasm_ir_drop_h
 
+#include "ir/branch-utils.h"
 #include "ir/effects.h"
 #include "ir/iteration.h"
 #include "wasm-builder.h"
@@ -32,10 +33,10 @@ namespace wasm {
 //
 // The caller must also pass in a last item to append to the output (which is
 // typically what the original expression is replaced with).
-Expression* getDroppedChildrenAndAppend(Expression* curr,
-                                        Module& wasm,
-                                        const PassOptions& options,
-                                        Expression* last) {
+inline Expression* getDroppedChildrenAndAppend(Expression* curr,
+                                               Module& wasm,
+                                               const PassOptions& options,
+                                               Expression* last) {
   Builder builder(wasm);
   std::vector<Expression*> contents;
   for (auto* child : ChildIterator(curr)) {
@@ -57,6 +58,80 @@ Expression* getDroppedChildrenAndAppend(Expression* curr,
   return builder.makeBlock(contents);
 }
 
+// As the above, but only operates on children that execute unconditionally.
+// That is the case in almost all expressions, except for those with
+// conditional execution, like if, which unconditionally executes the condition
+// but then conditionally executes one of the two arms. The above function
+// simply returns all children in order, so it does this to if:
+//
+//  (if
+//    (condition)
+//    (arm-A)
+//    (arm-B)
+//  )
+// =>
+//  (drop
+//    (condition)
+//  )
+//  (drop
+//    (arm-A)
+//  )
+//  (drop
+//    (arm-B)
+//  )
+//  (appended last item)
+//
+// This is dangerous as it executes what were conditional children in an
+// unconditional way. To avoid that issue, this function will only operate on
+// unconditional children, and keep conditional ones as they were. That means
+// it will not split up and drop the children of an if, for example. All we do
+// in that case is drop the entire if and append the last item:
+//
+//  (drop
+//    (if
+//      (condition)
+//      (arm-A)
+//      (arm-B)
+//    )
+//  )
+//  (appended last item)
+//
+//  Also this function preserves other unremovable expressions like trys and
+//  pops.
+inline Expression*
+getDroppedUnconditionalChildrenAndAppend(Expression* curr,
+                                         Module& wasm,
+                                         const PassOptions& options,
+                                         Expression* last) {
+  // We check for shallow effects here, since we may be able to remove |curr|
+  // itself but keep its children around - we don't want effects in the children
+  // to stop us from improving the code. Note that there are cases where the
+  // combined curr+children has fewer effects than curr itself, such as if curr
+  // is a block and the child branches to it, but in such cases we cannot remove
+  // curr anyhow (those cases are ruled out below), so looking at non-shallow
+  // effects would never help us (and would be slower to run).
+  ShallowEffectAnalyzer effects(options, wasm, curr);
+  // Ignore a trap, as the unreachable replacement would trap too.
+  if (last->type == Type::unreachable) {
+    effects.trap = false;
+  }
+
+  // We cannot remove
+  // 1. Expressions with unremovable side effects
+  // 2. if: 'if's contains conditional expressions
+  // 3. try: Removing a try could leave a pop without a proper parent
+  // 4. pop: Pops are struturally necessary in catch bodies
+  // 5. Branch targets: We will need the target for the branches to it to
+  //                    validate.
+  if (effects.hasUnremovableSideEffects() || curr->is<If>() ||
+      curr->is<Try>() || curr->is<Pop>() ||
+      BranchUtils::getDefinedName(curr).is()) {
+    Builder builder(wasm);
+    return builder.makeSequence(builder.makeDrop(curr), last);
+  }
+  return getDroppedChildrenAndAppend(curr, wasm, options, last);
+}
+
 } // namespace wasm
 
 #endif // wasm_ir_drop_h
diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp
index a0e64e236..3677516b3 100644
--- a/src/ir/possible-contents.cpp
+++ b/src/ir/possible-contents.cpp
@@ -42,9 +42,22 @@ std::ostream& operator<<(std::ostream& stream,
 namespace wasm {
 
 void PossibleContents::combine(const PossibleContents& other) {
+  auto type = getType();
+  auto otherType = other.getType();
   // First handle the trivial cases of them being equal, or one of them is
   // None or Many.
   if (*this == other) {
+    // Nulls are a special case, since they compare equal even if their type is
+    // different. We would like to make this function symmetric, that is, that
+    // combine(a, b) == combine(b, a) (otherwise, things can be odd and we could
+    // get nondeterminism in the flow analysis which does not have a
+    // determinstic order). To fix that, pick the LUB.
+    if (isNull()) {
+      assert(other.isNull());
+      auto lub = HeapType::getLeastUpperBound(type.getHeapType(),
+                                              otherType.getHeapType());
+      value = Literal::makeNull(lub);
+    }
     return;
   }
   if (other.isNone()) {
@@ -62,9 +75,6 @@ void PossibleContents::combine(const PossibleContents& other) {
     return;
   }
 
-  auto type = getType();
-  auto otherType = other.getType();
-
   if (!type.isRef() || !otherType.isRef()) {
     // At least one is not a reference. The only possibility left for a useful
     // combination here is if they have the same type (since we've already ruled
@@ -83,6 +93,9 @@ void PossibleContents::combine(const PossibleContents& other) {
 
   // Nulls are always equal to each other, even if their types differ.
   if (isNull() || other.isNull()) {
+    // Only one of them can be null here, since we already checked if *this ==
+    // other, which would have been true had both been 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).
@@ -92,12 +105,6 @@ void PossibleContents::combine(const PossibleContents& other) {
     } else if (!other.isNull() && other.hasExactType()) {
       value = ExactType(Type(otherType.getHeapType(), Nullable));
       return;
-    } else if (isNull() && other.isNull()) {
-      // Both are null. The result is a null, of the LUB.
-      auto lub = HeapType::getLeastUpperBound(type.getHeapType(),
-                                              otherType.getHeapType());
-      value = Literal::makeNull(lub);
-      return;
     }
   }
 
@@ -1312,7 +1319,13 @@ bool Flower::updateContents(LocationIndex locationIndex,
     worthSendingMore = false;
   }
 
-  if (contents == oldContents) {
+  // Check if anything changed. Note that we check not just the content but
+  // also its type. That handles the case of nulls, that compare equal even if
+  // their type differs. We want to keep flowing if the type can change, so that
+  // we always end up with a deterministic result no matter in what order the
+  // flow happens (the final result will be the LUB of all the types of nulls
+  // that can arrive).
+  if (contents == oldContents && contents.getType() == oldContents.getType()) {
     // Nothing actually changed, so just return.
     return worthSendingMore;
   }
@@ -1322,7 +1335,8 @@ bool Flower::updateContents(LocationIndex locationIndex,
   if (auto* globalLoc =
         std::get_if<GlobalLocation>(&getLocation(locationIndex))) {
     filterGlobalContents(contents, *globalLoc);
-    if (contents == oldContents) {
+    if (contents == oldContents &&
+        contents.getType() == oldContents.getType()) {
       // Nothing actually changed after filtering, so just return.
       return worthSendingMore;
     }