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, 42 insertions, 0 deletions

diff --git a/src/ir/properties.cpp b/src/ir/properties.cpp
new file mode 100644
index 000000000..889ece57b
--- /dev/null
+++ b/src/ir/properties.cpp
@@ -0,0 +1,42 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "ir/properties.h"
+#include "wasm-traversal.h"
+
+namespace wasm {
+
+namespace Properties {
+
+bool isIntrinsicallyNondeterministic(Expression* curr, FeatureSet features) {
+  // Practically no wasm instructions are intrinsically nondeterministic.
+  // Exceptions occur only in GC atm.
+  if (!features.hasGC()) {
+    return false;
+  }
+
+  struct Scanner : public PostWalker<Scanner> {
+    bool deterministic = true;
+    void visitStructNew(StructNew* curr) { deterministic = false; }
+    void visitArrayNew(ArrayNew* curr) { deterministic = false; }
+  } scanner;
+  scanner.walk(curr);
+  return !scanner.deterministic;
+}
+
+} // namespace Properties
+
+} // namespace wasm