LocalCSE rewrite (#4079)

Technically this is not a new pass, but it is a rewrite almost from scratch.

Local Common Subexpression Elimination looks for repeated patterns,
stuff like this:

x = (a + b) + c
y = a + b

=>

temp = a + b
x = temp + c
y = temp

The old pass worked on flat IR, which is inefficient, and was overly
complicated because of that. The new pass uses a new algorithm that
I think is pretty simple, see the detailed comment at the top.

This keeps the pass enabled only in -O4, like before - right after
flattening the IR. That is to make this as minimal a change as possible.
Followups will enable the pass in the main pipeline, that is, we will
finally be able to run it by default. (Note that to make the pass work
well after flatten, an extra simplify-locals is added - the old pass used
to do part of simplify-locals internally, which was one source of
complexity. Even so, some of the -O4 tests have changes, due to
minor factors - they are just minor orderings etc., which can be
seen by inspecting the outputs before and after using e.g.
--metrics)

This plus some followup work leads to large wins on wasm GC output.
On j2cl there is a common pattern of repeated struct.gets, so common
that this pass removes 85% of all struct.gets, which makes the total
binary 15% smaller. However, on LLVM-emitted code the benefit is
minor, less than 1%.

1 files changed, 9 insertions, 18 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 18fbf6d83..43d0d912f 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -1470,30 +1470,21 @@ private:
     // First, check for side effects. If there are any, then we can't even
     // assume things like local.get's of the same index being identical.
     auto passOptions = getPassOptions();
-    if (EffectAnalyzer(passOptions, getModule()->features, left)
-          .hasSideEffects() ||
-        EffectAnalyzer(passOptions, getModule()->features, right)
-          .hasSideEffects()) {
+    auto features = getModule()->features;
+    if (EffectAnalyzer(passOptions, features, left).hasSideEffects() ||
+        EffectAnalyzer(passOptions, features, right).hasSideEffects()) {
       return false;
     }
     // Ignore extraneous things and compare them structurally.
-    left = Properties::getFallthrough(left, passOptions, getModule()->features);
-    right =
-      Properties::getFallthrough(right, passOptions, getModule()->features);
+    left = Properties::getFallthrough(left, passOptions, features);
+    right = Properties::getFallthrough(right, passOptions, features);
     if (!ExpressionAnalyzer::equal(left, right)) {
       return false;
     }
-    // Reference equality also needs to check for allocation, which is *not* a
-    // side effect, but which results in different references:
-    // repeatedly calling (struct.new $foo)'s output will return different
-    // results (while i32.const etc. of course does not).
-    // Note that allocations may have appeared in the original inputs to this
-    // function, and skipped when we focused on what falls through; since there
-    // are no side effects, any allocations there cannot reach the fallthrough.
-    if (left->type.isRef()) {
-      if (FindAll<StructNew>(left).has() || FindAll<ArrayNew>(left).has()) {
-        return false;
-      }
+    // To be equal, they must also be known to return the same result
+    // deterministically.
+    if (Properties::isIntrinsicallyNondeterministic(left, features)) {
+      return false;
     }
     return true;
   }