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

1 files changed, 40 insertions, 10 deletions

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.