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, 4 insertions, 1 deletions

diff --git a/src/passes/Precompute.cpp b/src/passes/Precompute.cpp
index 99741ebe3..82504bff5 100644
--- a/src/passes/Precompute.cpp
+++ b/src/passes/Precompute.cpp
@@ -307,7 +307,10 @@ private:
         // value*. A case where that can happen is GC data (each struct.new
         // creates a new, unique struct, even if the data is equal), and so
         // PrecomputingExpressionRunner will return a nonconstant flow for all
-        // GC heap operations.
+        // GC heap operations. (We could also have used
+        // Properties::isIntrinsicallyNondeterministic here, but that would be
+        // less efficient to re-scan the entire expression.)
+        //
         // (Other side effects are fine; if an expression does a call and we
         // somehow know the entire expression precomputes to a 42, then we can
         // propagate that 42 along to the users, regardless of whatever the call