1 files changed, 205 insertions, 0 deletions
diff --git a/test/gtest/cfg.cpp b/test/gtest/cfg.cpp
index c18d81499..3ee63b9b0 100644
--- a/test/gtest/cfg.cpp
+++ b/test/gtest/cfg.cpp
@@ -4,6 +4,8 @@
 #include "analysis/lattice.h"
 #include "analysis/liveness-transfer-function.h"
 #include "analysis/monotone-analyzer.h"
+#include "analysis/reaching-definitions-transfer-function.h"
+#include "ir/find_all.h"
 #include "print-test.h"
 #include "wasm.h"
 #include "gtest/gtest.h"
@@ -290,3 +292,206 @@ TEST_F(CFGTest, FinitePowersetLatticeFunctioning) {
   element2.print(ss);
   EXPECT_EQ(ss.str(), "101101");
 }
+
+TEST_F(CFGTest, LinearReachingDefinitions) {
+  auto moduleText = R"wasm(
+    (module
+      (func $bar
+        (local $a (i32))
+        (local $b (i32))
+        (local $c (i32))
+        (local.set $a
+          (i32.const 1)
+        )
+        (drop
+          (local.get $a)
+        )
+        (local.set $b
+          (local.get $a)
+        )
+        (drop
+          (local.get $c)
+        )
+        (local.set $c
+          (i32.const 1)
+        )
+        (local.set $a
+          (i32.const 2)
+        )
+      )
+    )
+  )wasm";
+
+  Module wasm;
+  parseWast(wasm, moduleText);
+
+  Function* func = wasm.getFunction("bar");
+  CFG cfg = CFG::fromFunction(func);
+
+  LocalGraph::GetSetses getSetses;
+  LocalGraph::Locations locations;
+  ReachingDefinitionsTransferFunction transferFunction(
+    func, getSetses, locations);
+
+  MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>,
+                      ReachingDefinitionsTransferFunction>
+    analyzer(transferFunction.lattice, transferFunction, cfg);
+
+  // TODO: Make evaluating function entry point more automatic (i.e. part of
+  // existing evaluate call).
+  analyzer.evaluateFunctionEntry(func);
+  analyzer.evaluateAndCollectResults();
+
+  FindAll<LocalSet> foundSets(func->body);
+  FindAll<LocalGet> foundGets(func->body);
+
+  LocalGet* getA1 = foundGets.list[0];
+  LocalGet* getA2 = foundGets.list[1];
+  LocalGet* getC = foundGets.list[2];
+  LocalSet* setA1 = foundSets.list[0];
+
+  LocalGraph::GetSetses expectedResult;
+  expectedResult[getA1].insert(setA1);
+  expectedResult[getA2].insert(setA1);
+  expectedResult[getC].insert(nullptr);
+
+  EXPECT_EQ(expectedResult, getSetses);
+}
+
+TEST_F(CFGTest, ReachingDefinitionsIf) {
+  auto moduleText = R"wasm(
+    (module
+      (func $bar
+        (local $a (i32))
+        (local $b (i32))
+        (local.set $a
+          (i32.const 1)
+        )
+        (if
+          (i32.eq
+            (local.get $a)
+            (i32.const 2)
+          )
+          (local.set $b
+            (i32.const 3)
+          )
+          (local.set $a
+            (i32.const 4)
+          )
+        )
+        (drop
+          (local.get $b)
+        )
+        (drop
+          (local.get $a)
+        )
+      )
+    )
+  )wasm";
+
+  Module wasm;
+  parseWast(wasm, moduleText);
+
+  Function* func = wasm.getFunction("bar");
+  CFG cfg = CFG::fromFunction(func);
+
+  LocalGraph::GetSetses getSetses;
+  LocalGraph::Locations locations;
+  ReachingDefinitionsTransferFunction transferFunction(
+    func, getSetses, locations);
+
+  MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>,
+                      ReachingDefinitionsTransferFunction>
+    analyzer(transferFunction.lattice, transferFunction, cfg);
+  analyzer.evaluateFunctionEntry(func);
+  analyzer.evaluateAndCollectResults();
+
+  FindAll<LocalSet> foundSets(func->body);
+  FindAll<LocalGet> foundGets(func->body);
+
+  LocalGet* getA1 = foundGets.list[0];
+  LocalGet* getB = foundGets.list[1];
+  LocalGet* getA2 = foundGets.list[2];
+  LocalSet* setA1 = foundSets.list[0];
+  LocalSet* setB = foundSets.list[1];
+  LocalSet* setA2 = foundSets.list[2];
+
+  LocalGraph::GetSetses expectedResult;
+  expectedResult[getA1].insert(setA1);
+  expectedResult[getB].insert(nullptr);
+  expectedResult[getB].insert(setB);
+  expectedResult[getA2].insert(setA1);
+  expectedResult[getA2].insert(setA2);
+
+  EXPECT_EQ(expectedResult, getSetses);
+}
+
+TEST_F(CFGTest, ReachingDefinitionsLoop) {
+  auto moduleText = R"wasm(
+    (module
+      (func $bar (param $a (i32)) (param $b (i32))
+        (loop $loop
+          (drop
+            (local.get $a)
+          )
+          (local.set $a
+             (i32.add
+               (i32.const 1)
+               (local.get $a)
+             )
+          )
+          (br_if $loop
+            (i32.le_u
+              (local.get $a)
+              (i32.const 7)
+            )
+          )
+        )
+        (local.set $b
+          (i32.sub
+            (local.get $b)
+            (local.get $a)
+          )
+        )
+      )
+    )
+  )wasm";
+
+  Module wasm;
+  parseWast(wasm, moduleText);
+
+  Function* func = wasm.getFunction("bar");
+  CFG cfg = CFG::fromFunction(func);
+
+  LocalGraph::GetSetses getSetses;
+  LocalGraph::Locations locations;
+  ReachingDefinitionsTransferFunction transferFunction(
+    func, getSetses, locations);
+
+  MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>,
+                      ReachingDefinitionsTransferFunction>
+    analyzer(transferFunction.lattice, transferFunction, cfg);
+  analyzer.evaluateFunctionEntry(func);
+  analyzer.evaluateAndCollectResults();
+
+  FindAll<LocalSet> foundSets(func->body);
+  FindAll<LocalGet> foundGets(func->body);
+
+  LocalGet* getA1 = foundGets.list[0];
+  LocalGet* getA2 = foundGets.list[1];
+  LocalGet* getA3 = foundGets.list[2];
+  LocalGet* getB = foundGets.list[3];
+  LocalGet* getA4 = foundGets.list[4];
+  LocalSet* setA = foundSets.list[0];
+
+  LocalGraph::GetSetses expectedResult;
+  expectedResult[getA1].insert(nullptr);
+  expectedResult[getA1].insert(setA);
+  expectedResult[getA2].insert(nullptr);
+  expectedResult[getA2].insert(setA);
+  expectedResult[getA3].insert(setA);
+  expectedResult[getB].insert(nullptr);
+  expectedResult[getA4].insert(setA);
+
+  EXPECT_EQ(expectedResult, getSetses);
+}