Liveness Analysis Proof of Concept (#5771)

This introduces a limited monotone flow-sensitive liveness analysis on local indices as an initial proof of concept for the creation of a monotone flow-sensitive static analysis framework. Tests are included in test/gtest/cfg.cpp.

1 files changed, 158 insertions, 0 deletions

diff --git a/test/gtest/cfg.cpp b/test/gtest/cfg.cpp
index b8ff9cb38..8780af8ca 100644
--- a/test/gtest/cfg.cpp
+++ b/test/gtest/cfg.cpp
@@ -1,4 +1,8 @@
+#include <iostream>
+
 #include "analysis/cfg.h"
+#include "analysis/lattice.h"
+#include "analysis/monotone-analyzer.h"
 #include "print-test.h"
 #include "wasm.h"
 #include "gtest/gtest.h"
@@ -79,3 +83,157 @@ TEST_F(CFGTest, Print) {
 
   EXPECT_EQ(ss.str(), cfgText);
 }
+
+TEST_F(CFGTest, LinearLiveness) {
+  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)
+        )
+        (local.set $c
+          (i32.const 1)
+        )
+        (drop
+          (local.get $c)
+        )
+      )
+    )
+  )wasm";
+
+  auto analyzerText = R"analyzer(CFG Analyzer
+State Block: 0
+State at beginning: 000
+State at end: 000
+Intermediate States (reverse order): 
+000
+block
+000
+drop
+000
+local.get $2
+100
+local.set $2
+000
+i32.const 1
+000
+local.set $1
+000
+local.get $0
+001
+drop
+001
+local.get $0
+001
+local.set $0
+000
+i32.const 1
+000
+End
+)analyzer";
+
+  Module wasm;
+  parseWast(wasm, moduleText);
+
+  CFG cfg = CFG::fromFunction(wasm.getFunction("bar"));
+  const size_t sz = 3;
+  MonotoneCFGAnalyzer<sz> analyzer = MonotoneCFGAnalyzer<sz>::fromCFG(&cfg);
+  analyzer.evaluate();
+
+  std::stringstream ss;
+  analyzer.print(ss);
+
+  EXPECT_EQ(ss.str(), analyzerText);
+}
+
+TEST_F(CFGTest, NonlinearLiveness) {
+  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 4)
+          )
+          (drop
+            (local.get $a)
+          )
+        )
+      )
+    )
+  )wasm";
+
+  auto analyzerText = R"analyzer(CFG Analyzer
+State Block: 0
+State at beginning: 00
+State at end: 01
+Intermediate States (reverse order): 
+01
+i32.eq
+01
+i32.const 2
+01
+local.get $0
+01
+local.set $0
+00
+i32.const 1
+00
+State Block: 1
+State at beginning: 00
+State at end: 00
+Intermediate States (reverse order): 
+00
+local.set $1
+00
+i32.const 4
+00
+State Block: 2
+State at beginning: 01
+State at end: 00
+Intermediate States (reverse order): 
+00
+drop
+00
+local.get $0
+01
+State Block: 3
+State at beginning: 00
+State at end: 00
+Intermediate States (reverse order): 
+00
+block
+00
+End
+)analyzer";
+
+  Module wasm;
+  parseWast(wasm, moduleText);
+
+  CFG cfg = CFG::fromFunction(wasm.getFunction("bar"));
+  const size_t sz = 2;
+  MonotoneCFGAnalyzer<sz> analyzer = MonotoneCFGAnalyzer<sz>::fromCFG(&cfg);
+  analyzer.evaluate();
+
+  std::stringstream ss;
+  analyzer.print(ss);
+
+  EXPECT_EQ(ss.str(), analyzerText);
+}