LocalCSE: Check effects/generativity early (#6587)

Previously we checked late, and as a result might end up failing to optimize when
a sub-pattern could have worked. E.g.

(call
  (A)
)
(call
  (A)
)

The call cannot be optimized, but the A pattern repeats. Before this PR we'd
greedily focus on the entire call and then fail. After this PR we skip the call
before we commit to which patterns to try to optimize, so we succeed.

Add a isShallowlyGenerative helper here as we compute this step by step as
we go. Also remove a parameter to the generativity code (it did not use the
features it was passed).

4 files changed, 74 insertions, 28 deletions

diff --git a/src/ir/properties.cpp b/src/ir/properties.cpp
index 05dae897e..1346f6cad 100644
--- a/src/ir/properties.cpp
+++ b/src/ir/properties.cpp
@@ -19,27 +19,40 @@
 
 namespace wasm::Properties {
 
-bool isGenerative(Expression* curr, FeatureSet features) {
-  struct Scanner : public PostWalker<Scanner> {
-    bool generative = false;
+namespace {
 
-    void visitCall(Call* curr) {
-      // TODO: We could in principle look at the called function to see if it is
-      //       generative. To do that we'd need to compute generativity like we
-      //       compute global effects (we can't just peek from here, as the
-      //       other function might be modified in parallel).
-      generative = true;
-    }
-    void visitCallIndirect(CallIndirect* curr) { generative = true; }
-    void visitCallRef(CallRef* curr) { generative = true; }
-    void visitStructNew(StructNew* curr) { generative = true; }
-    void visitArrayNew(ArrayNew* curr) { generative = true; }
-    void visitArrayNewFixed(ArrayNewFixed* curr) { generative = true; }
-  } scanner;
+struct GenerativityScanner : public PostWalker<GenerativityScanner> {
+  bool generative = false;
+
+  void visitCall(Call* curr) {
+    // TODO: We could in principle look at the called function to see if it is
+    //       generative. To do that we'd need to compute generativity like we
+    //       compute global effects (we can't just peek from here, as the
+    //       other function might be modified in parallel).
+    generative = true;
+  }
+  void visitCallIndirect(CallIndirect* curr) { generative = true; }
+  void visitCallRef(CallRef* curr) { generative = true; }
+  void visitStructNew(StructNew* curr) { generative = true; }
+  void visitArrayNew(ArrayNew* curr) { generative = true; }
+  void visitArrayNewFixed(ArrayNewFixed* curr) { generative = true; }
+};
+
+} // anonymous namespace
+
+bool isGenerative(Expression* curr) {
+  GenerativityScanner scanner;
   scanner.walk(curr);
   return scanner.generative;
 }
 
+// As above, but only checks |curr| and not children.
+bool isShallowlyGenerative(Expression* curr) {
+  GenerativityScanner scanner;
+  scanner.visit(curr);
+  return scanner.generative;
+}
+
 // Checks an expression in a shallow manner (i.e., does not check children) as
 // to whether it is valid in a wasm constant expression.
 static bool isValidInConstantExpression(Module& wasm, Expression* expr) {
diff --git a/src/ir/properties.h b/src/ir/properties.h
index 301f15e16..4b73b7211 100644
--- a/src/ir/properties.h
+++ b/src/ir/properties.h
@@ -527,7 +527,10 @@ inline bool canEmitSelectWithArms(Expression* ifTrue, Expression* ifFalse) {
 //    the latter because calls are already handled best in other manners (using
 //    EffectAnalyzer).
 //
-bool isGenerative(Expression* curr, FeatureSet features);
+bool isGenerative(Expression* curr);
+
+// As above, but only checks |curr| and not children.
+bool isShallowlyGenerative(Expression* curr);
 
 // Whether this expression is valid in a context where WebAssembly requires a
 // constant expression, such as a global initializer.
diff --git a/src/passes/LocalCSE.cpp b/src/passes/LocalCSE.cpp
index 52346030c..bb017e938 100644
--- a/src/passes/LocalCSE.cpp
+++ b/src/passes/LocalCSE.cpp
@@ -330,6 +330,40 @@ struct Scanner
       return false;
     }
 
+    // We will fully compute effects later, but consider shallow effects at this
+    // early time to ignore things that cannot be optimized later, because we
+    // use a greedy algorithm. Specifically, imagine we see this:
+    //
+    //  (call
+    //    (i32.add
+    //      ..
+    //    )
+    //  )
+    //
+    // If we considered the call relevant then we'd start to look for that
+    // larger pattern that contains the add, but then when we find that it
+    // cannot be optimized later it is too late for the add. (Instead of
+    // checking effects here we could perhaps add backtracking, but that sounds
+    // more complex.)
+    //
+    // We use |hasNonTrapSideEffects| because if a trap occurs the optimization
+    // remains valid: both this and the copy of it would trap, which means the
+    // first traps and the second isn't reached anyhow.
+    //
+    // (We don't stash these effects because we may compute many of them here,
+    // and only need the few for those patterns that repeat.)
+    if (ShallowEffectAnalyzer(options, *getModule(), curr)
+          .hasNonTrapSideEffects()) {
+      return false;
+    }
+
+    // We also cannot optimize away something that is intrinsically
+    // nondeterministic: even if it has no side effects, if it may return a
+    // different result each time, and then we cannot optimize away repeats.
+    if (Properties::isShallowlyGenerative(curr)) {
+      return false;
+    }
+
     // If the size is at least 3, then if we have two of them we have 6,
     // and so adding one set+one get and removing one of the items itself
     // is not detrimental, and may be beneficial.
@@ -438,16 +472,12 @@ struct Checker
       // none of them.)
       effects.trap = false;
 
-      // We also cannot optimize away something that is intrinsically
-      // nondeterministic: even if it has no side effects, if it may return a
-      // different result each time, then we cannot optimize away repeats.
-      if (effects.hasSideEffects() ||
-          Properties::isGenerative(curr, getModule()->features)) {
-        requestInfos.erase(curr);
-      } else {
-        activeOriginals.emplace(
-          curr, ActiveOriginalInfo{info.requests, std::move(effects)});
-      }
+      // Note that we've already checked above that this has no side effects or
+      // generativity: if we got here, then it is good to go from the
+      // perspective of this expression itself (but may be invalidated by other
+      // code in between, see above).
+      activeOriginals.emplace(
+        curr, ActiveOriginalInfo{info.requests, std::move(effects)});
     } else if (info.original) {
       // The original may have already been invalidated. If so, remove our info
       // as well.
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 3486fe82a..1a474be2c 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -2508,7 +2508,7 @@ private:
 
     // To be equal, they must also be known to return the same result
     // deterministically.
-    return !Properties::isGenerative(left, getModule()->features);
+    return !Properties::isGenerative(left);
   }
 
   // Similar to areConsecutiveInputsEqual() but also checks if we can remove