Add LocalGraph::equivalent (#3848)

This compares two local.gets and checks whether we are sure they are
equivalent, that is, they contain the same value.

This does not solve the general problem, but uses the existing info to get
a positive answer for the common case where two gets only receive values
by a single set, like

(local.set $x ..)
(a use.. (local.get $x))
(another use.. (local.get $x))
If they only receive values from the same single set, then we know it must
dominate them. The only risk is that the set is "in between" the gets, that is,
that the set occurs after one get and before the other. That can happen in
a loop in theory,

(loop $loop
  (use (local.get $x))
  (local.set $x ..some new value each iteration..)
  (use (local.get $x))
  (br_if $loop ..)
)

Both of those gets receive a value from the set, and they may be different
values, from different loop iterations. But as mentioned in the source code,
this is not a problem since wasm always has a zero-initialization value, and
so the first local.get in that loop would have another set from which it can
receive a value, the function entry. (The only way to avoid that is for this
entire code to be unreachable, in which case nothing matters.)

This will be useful in dead store elimination, which has to use this to reason
about references and pointers in order to be able to do anything useful with
GC and memory.

1 files changed, 118 insertions, 0 deletions

diff --git a/test/example/local-graph.cpp b/test/example/local-graph.cpp
new file mode 100644
index 000000000..0ac435883
--- /dev/null
+++ b/test/example/local-graph.cpp
@@ -0,0 +1,118 @@
+#include <iostream>
+
+#include <ir/local-graph.h>
+#include <wasm-builder.h>
+#include <wasm.h>
+
+using namespace wasm;
+
+int main() {
+  Module wasm;
+  Builder builder(wasm);
+
+  {
+    Function foo;
+    foo.vars = {Type::i32};
+    auto* get1 = builder.makeLocalGet(0, Type::i32);
+    auto* get2 = builder.makeLocalGet(0, Type::i32);
+    foo.body = builder.makeBlock({
+      builder.makeLocalSet(0, builder.makeConst(Literal(int32_t(0)))),
+      // two equivalent gets, as both are preceded by the same single set
+      builder.makeDrop(get1),
+      builder.makeDrop(get2),
+    });
+    LocalGraph graph(&foo);
+    assert(graph.equivalent(get1, get2));
+  }
+
+  {
+    Function foo;
+    foo.vars = {Type::i32};
+    auto* get1 = builder.makeLocalGet(0, Type::i32);
+    auto* get2 = builder.makeLocalGet(0, Type::i32);
+    foo.body = builder.makeBlock({
+      // two non-equivalent gets, as there is a set in between them
+      builder.makeDrop(get1),
+      builder.makeLocalSet(0, builder.makeConst(Literal(int32_t(0)))),
+      builder.makeDrop(get2),
+    });
+    LocalGraph graph(&foo);
+    assert(!graph.equivalent(get1, get2));
+  }
+
+  {
+    Function foo;
+    foo.sig = Signature({Type::i32}, Type::none);
+    auto* get1 = builder.makeLocalGet(0, Type::i32);
+    auto* get2 = builder.makeLocalGet(0, Type::i32);
+    foo.body = builder.makeBlock({
+      // two equivalent gets of the same parameter
+      builder.makeDrop(get1),
+      builder.makeDrop(get2),
+    });
+    LocalGraph graph(&foo);
+    assert(graph.equivalent(get1, get2));
+  }
+
+  {
+    Function foo;
+    foo.sig = Signature({Type::i32}, Type::none);
+    auto* get1 = builder.makeLocalGet(0, Type::i32);
+    auto* get2 = builder.makeLocalGet(0, Type::i32);
+    foo.body = builder.makeBlock({
+      // two non-equivalent gets of the same parameter, as there is a set
+      builder.makeDrop(get1),
+      builder.makeLocalSet(0, builder.makeConst(Literal(int32_t(0)))),
+      builder.makeDrop(get2),
+    });
+    LocalGraph graph(&foo);
+    assert(!graph.equivalent(get1, get2));
+  }
+
+  {
+    Function foo;
+    foo.sig = Signature({Type::i32, Type::i32}, Type::none);
+    auto* get1 = builder.makeLocalGet(0, Type::i32);
+    auto* get2 = builder.makeLocalGet(1, Type::i32);
+    foo.body = builder.makeBlock({
+      // two non-equivalent gets as they are of different parameters
+      builder.makeDrop(get1),
+      builder.makeDrop(get2),
+    });
+    LocalGraph graph(&foo);
+    assert(!graph.equivalent(get1, get2));
+  }
+
+  {
+    Function foo;
+    foo.vars = {Type::i32, Type::i32};
+    auto* get1 = builder.makeLocalGet(0, Type::i32);
+    auto* get2 = builder.makeLocalGet(1, Type::i32);
+    foo.body = builder.makeBlock({
+      // two equivalent gets, even though they have a different index, as both
+      // use the zero initialized value
+      builder.makeDrop(get1),
+      builder.makeDrop(get2),
+    });
+    LocalGraph graph(&foo);
+    assert(graph.equivalent(get1, get2));
+  }
+
+  {
+    Function foo;
+    foo.vars = {Type::i32, Type::f64};
+    auto* get1 = builder.makeLocalGet(0, Type::i32);
+    auto* get2 = builder.makeLocalGet(1, Type::f64);
+    foo.body = builder.makeBlock({
+      // two non-equivalent gets as their zero-init value is different
+      builder.makeDrop(get1),
+      builder.makeDrop(get2),
+    });
+    LocalGraph graph(&foo);
+    assert(!graph.equivalent(get1, get2));
+  }
+
+  std::cout << "Success." << std::endl;
+
+  return 0;
+}