LocalGraph::canMoveSet (#7039)

This new API lets us ask if a set can be safely moved to a new position. The new
position must be the location of an expression from a particular class (this
allows us to populate the IR once and then query any of those locations).

2 files changed, 348 insertions, 0 deletions

diff --git a/test/gtest/CMakeLists.txt b/test/gtest/CMakeLists.txt
index 7ef72db13..9b648fb65 100644
--- a/test/gtest/CMakeLists.txt
+++ b/test/gtest/CMakeLists.txt
@@ -8,6 +8,7 @@ set(unittest_SOURCES
   disjoint_sets.cpp
   json.cpp
   lattices.cpp
+  local-graph.cpp
   possible-contents.cpp
   printing.cpp
   scc.cpp
diff --git a/test/gtest/local-graph.cpp b/test/gtest/local-graph.cpp
new file mode 100644
index 000000000..5360813ce
--- /dev/null
+++ b/test/gtest/local-graph.cpp
@@ -0,0 +1,347 @@
+#include "ir/local-graph.h"
+#include "parser/wat-parser.h"
+#include "wasm.h"
+
+#include "gtest/gtest.h"
+
+using LocalGraphTest = ::testing::Test;
+
+using namespace wasm;
+
+TEST_F(LocalGraphTest, ObstacleBasics) {
+  auto moduleText = R"wasm(
+    (module
+      (func $foo (result i32)
+        ;; A local with a set and a get, and some nops in between.
+        (local $x i32)
+        (nop)
+        (local.set $x
+          (i32.const 10)
+        )
+        (nop)
+        (local.get $x)
+      )
+    )
+  )wasm";
+
+  Module wasm;
+  WATParser::parseModule(wasm, moduleText);
+
+  // Get access to the contents of the wasm.
+  auto* func = wasm.functions[0].get();
+  auto* block = func->body->cast<Block>();
+  auto* nopA = block->list[0]->cast<Nop>();
+  auto* set = block->list[1]->cast<LocalSet>();
+  auto* nopB = block->list[2]->cast<Nop>();
+  auto* get = block->list[3]->cast<LocalGet>();
+
+  {
+    LazyLocalGraph graph(func, &wasm);
+    // The set has one get.
+    EXPECT_EQ(graph.getSetInfluences(set).size(), 1U);
+  }
+
+  {
+    // Construct the graph with an obstacle class, Nop.
+    LazyLocalGraph graph(func, &wasm, Nop::SpecificId);
+    // The set has one get, like before.
+    EXPECT_EQ(graph.getSetInfluences(set).size(), 1U);
+    // If the first nop is an obstacle, nothing changes: the path between the
+    // set and get does not include it.
+    EXPECT_EQ(graph.canMoveSet(set, nopA).size(), 1U);
+    EXPECT_EQ(*graph.canMoveSet(set, nopA).begin(), get);
+    // But if the second one is an obstacle, it severs the connection.
+    EXPECT_EQ(graph.canMoveSet(set, nopB).size(), 0U);
+  }
+}
+
+TEST_F(LocalGraphTest, ObstacleMultiblock) {
+  auto moduleText = R"wasm(
+    (module
+      (func $foo (result i32)
+        ;; An if between the set and get.
+        (local $x i32)
+        (local.set $x
+          (i32.const 10)
+        )
+        (if
+          (i32.const 42)
+          (then
+            (nop)
+          )
+          (else
+            (nop)
+          )
+        )
+        (nop)
+        (local.get $x)
+      )
+    )
+  )wasm";
+  Module wasm;
+  WATParser::parseModule(wasm, moduleText);
+  auto* func = wasm.functions[0].get();
+  auto* block = func->body->cast<Block>();
+  auto* set = block->list[0]->cast<LocalSet>();
+  auto* iff = block->list[1]->cast<If>();
+  auto* nopA = iff->ifTrue->cast<Nop>();
+  auto* nopB = iff->ifTrue->cast<Nop>();
+  auto* nopC = block->list[2]->cast<Nop>();
+
+  LazyLocalGraph graph(func, &wasm, Nop::SpecificId);
+  // No matter which if arm is an obstacle, we still connect.
+  EXPECT_EQ(graph.canMoveSet(set, nopA).size(), 1U);
+  EXPECT_EQ(graph.canMoveSet(set, nopB).size(), 1U);
+  // But the nop after the if stops us.
+  EXPECT_EQ(graph.canMoveSet(set, nopC).size(), 0U);
+}
+
+TEST_F(LocalGraphTest, ObstacleUnreachable) {
+  auto moduleText = R"wasm(
+    (module
+      (func $foo (result i32)
+        ;; An unreachable between the set and get.
+        (local $x i32)
+        (local.set $x
+          (i32.const 10)
+        )
+        (nop)
+        (unreachable)
+        (nop)
+        (local.get $x)
+      )
+    )
+  )wasm";
+  Module wasm;
+  WATParser::parseModule(wasm, moduleText);
+  auto* func = wasm.functions[0].get();
+  auto* block = func->body->cast<Block>();
+  auto* set = block->list[0]->cast<LocalSet>();
+  auto* nopA = block->list[1]->cast<Nop>();
+  auto* nopB = block->list[3]->cast<Nop>();
+
+  LazyLocalGraph graph(func, &wasm, Nop::SpecificId);
+  // The get is unreachable, and the set has no gets.
+  EXPECT_EQ(graph.getSetInfluences(set).size(), 0U);
+  EXPECT_EQ(graph.canMoveSet(set, nopA).size(), 0U);
+  EXPECT_EQ(graph.canMoveSet(set, nopB).size(), 0U);
+}
+
+TEST_F(LocalGraphTest, ObstacleMultiGet) {
+  auto moduleText = R"wasm(
+    (module
+      (func $foo
+        ;; A set with multiple gets.
+        (local $x i32)
+        (local.set $x
+          (i32.const 10)
+        )
+        (nop)
+        (drop
+          (local.get $x)
+        )
+        (nop)
+        (drop
+          (local.get $x)
+        )
+        (nop)
+      )
+    )
+  )wasm";
+  Module wasm;
+  WATParser::parseModule(wasm, moduleText);
+  auto* func = wasm.functions[0].get();
+  auto* block = func->body->cast<Block>();
+  auto* set = block->list[0]->cast<LocalSet>();
+  auto* nopA = block->list[1]->cast<Nop>();
+  auto* nopB = block->list[3]->cast<Nop>();
+  auto* nopC = block->list[5]->cast<Nop>();
+
+  LazyLocalGraph graph(func, &wasm, Nop::SpecificId);
+  // The first nop blocks them both, but not the second, and the third blocks
+  // nothing.
+  EXPECT_EQ(graph.canMoveSet(set, nopA).size(), 0U);
+  EXPECT_EQ(graph.canMoveSet(set, nopB).size(), 1U);
+  EXPECT_EQ(graph.canMoveSet(set, nopC).size(), 2U);
+}
+
+TEST_F(LocalGraphTest, ObstacleMultiSet) {
+  auto moduleText = R"wasm(
+    (module
+      (func $foo
+        ;; Two sets.
+        (local $x i32)
+        (local.set $x
+          (i32.const 10)
+        )
+        (local.set $x
+          (i32.const 20)
+        )
+        (nop)
+        (drop
+          (local.get $x)
+        )
+      )
+    )
+  )wasm";
+  Module wasm;
+  WATParser::parseModule(wasm, moduleText);
+  auto* func = wasm.functions[0].get();
+  auto* block = func->body->cast<Block>();
+  auto* setA = block->list[0]->cast<LocalSet>();
+  auto* setB = block->list[1]->cast<LocalSet>();
+  auto* nop = block->list[2]->cast<Nop>();
+
+  LazyLocalGraph graph(func, &wasm, Nop::SpecificId);
+  // The first set has no gets, the second has one.
+  EXPECT_EQ(graph.getSetInfluences(setA).size(), 0U);
+  EXPECT_EQ(graph.getSetInfluences(setB).size(), 1U);
+  // The nop blocks on the second (and the first, but it had none anyhow).
+  EXPECT_EQ(graph.canMoveSet(setA, nop).size(), 0U);
+  EXPECT_EQ(graph.canMoveSet(setB, nop).size(), 0U);
+}
+
+TEST_F(LocalGraphTest, ObstacleMultiSetIndexes) {
+  auto moduleText = R"wasm(
+    (module
+      (func $foo
+        ;; Two sets of different indexes.
+        (local $x i32)
+        (local $y i32)
+        (local.set $x
+          (i32.const 10)
+        )
+        (local.set $y
+          (i32.const 20)
+        )
+        (nop)
+        (drop
+          (local.get $x)
+        )
+        (nop)
+        (drop
+          (local.get $y)
+        )
+        (nop)
+      )
+    )
+  )wasm";
+  Module wasm;
+  WATParser::parseModule(wasm, moduleText);
+  auto* func = wasm.functions[0].get();
+  auto* block = func->body->cast<Block>();
+  auto* setA = block->list[0]->cast<LocalSet>();
+  auto* setB = block->list[1]->cast<LocalSet>();
+  auto* nopA = block->list[2]->cast<Nop>();
+  auto* nopB = block->list[4]->cast<Nop>();
+  auto* nopC = block->list[6]->cast<Nop>();
+
+  LazyLocalGraph graph(func, &wasm, Nop::SpecificId);
+  // The first nop blocks them both.
+  EXPECT_EQ(graph.canMoveSet(setA, nopA).size(), 0U);
+  EXPECT_EQ(graph.canMoveSet(setB, nopA).size(), 0U);
+  // The second nop only blocks one.
+  EXPECT_EQ(graph.canMoveSet(setA, nopB).size(), 1U);
+  EXPECT_EQ(graph.canMoveSet(setB, nopB).size(), 0U);
+  // The last nop blocks nothing.
+  EXPECT_EQ(graph.canMoveSet(setA, nopC).size(), 1U);
+  EXPECT_EQ(graph.canMoveSet(setB, nopC).size(), 1U);
+}
+
+TEST_F(LocalGraphTest, ObstacleMultiSetIf) {
+  auto moduleText = R"wasm(
+    (module
+      (func $foo
+        ;; Two sets in an if.
+        (local $x i32)
+        (if
+          (i32.const 42)
+          (then
+            (local.set $x
+              (i32.const 10)
+            )
+          )
+          (else
+            (local.set $x
+              (i32.const 20)
+            )
+          )
+        )
+        (nop)
+        (drop
+          (local.get $x)
+        )
+        (nop)
+      )
+    )
+  )wasm";
+  Module wasm;
+  WATParser::parseModule(wasm, moduleText);
+  auto* func = wasm.functions[0].get();
+  auto* block = func->body->cast<Block>();
+  auto* iff = block->list[0]->cast<If>();
+  auto* setA = iff->ifTrue->cast<LocalSet>();
+  auto* setB = iff->ifFalse->cast<LocalSet>();
+  auto* nopA = block->list[1]->cast<Nop>();
+  auto* nopB = block->list[3]->cast<Nop>();
+
+  LazyLocalGraph graph(func, &wasm, Nop::SpecificId);
+  // Both sets have a get.
+  EXPECT_EQ(graph.getSetInfluences(setA).size(), 1U);
+  EXPECT_EQ(graph.getSetInfluences(setB).size(), 1U);
+  // The first nop blocks both.
+  EXPECT_EQ(graph.canMoveSet(setA, nopA).size(), 0U);
+  EXPECT_EQ(graph.canMoveSet(setB, nopA).size(), 0U);
+  // The first nop blocks neither.
+  EXPECT_EQ(graph.canMoveSet(setA, nopB).size(), 1U);
+  EXPECT_EQ(graph.canMoveSet(setB, nopB).size(), 1U);
+}
+
+TEST_F(LocalGraphTest, ObstacleStructSet) {
+  // Use something other than a nop to obstruct. Here we show a realistic
+  // situation using GC.
+  auto moduleText = R"wasm(
+    (module
+     (type $struct (struct (field (mut i32))))
+
+     (func $test
+      (local $struct (ref null $struct))
+      (block $label
+       ;; A struct.set that may be skipped by the br in the if.
+       (struct.set $struct 0
+        (local.tee $struct
+         (struct.new_default $struct)
+        )
+        (if (result i32)
+         (i32.const 1)
+         (then
+          (br $label)
+         )
+         (else
+          (i32.const 0)
+         )
+        )
+       )
+      )
+      (drop
+       (struct.get $struct 0
+        (local.get $struct)
+       )
+      )
+     )
+    )
+  )wasm";
+  Module wasm;
+  WATParser::parseModule(wasm, moduleText);
+  auto* func = wasm.functions[0].get();
+  auto* outerBlock = func->body->cast<Block>();
+  auto* block = outerBlock->list[0]->cast<Block>();
+  auto* structSet = block->list[0]->cast<StructSet>();
+  auto* tee = structSet->ref->cast<LocalSet>();
+
+  LazyLocalGraph graph(func, &wasm, StructSet::SpecificId);
+  // The tee has one get.
+  EXPECT_EQ(graph.getSetInfluences(tee).size(), 1U);
+  // The struct.set blocks one path, but not the path that skips it via the br.
+  EXPECT_EQ(graph.canMoveSet(tee, structSet).size(), 1U);
+}