Dynamic Sized Bitvector Powerset Lattice for Static Analysis (#5784)

This change introduces a finite-height powerset lattice FinitePowersetLattice where each element's height is determined when constructed in runtime. This is implemented using a vector of `bools. This change also modifies BlockState and MonotoneCFGAnalyzer to be templated on a generic lattice type instead of using a hardcoded lattice. It additionally fixes an iterator bug in MonotoneCFGAnalyzer::fromCFG which assigned a temporary iterator object as predecessor and successor pointers to BlockStates instead of pointers to actual BlockState objects.

1 files changed, 35 insertions, 23 deletions

diff --git a/test/gtest/cfg.cpp b/test/gtest/cfg.cpp
index 8780af8ca..ae1b9215e 100644
--- a/test/gtest/cfg.cpp
+++ b/test/gtest/cfg.cpp
@@ -112,8 +112,10 @@ TEST_F(CFGTest, LinearLiveness) {
 
   auto analyzerText = R"analyzer(CFG Analyzer
 State Block: 0
-State at beginning: 000
-State at end: 000
+Beginning State: 000
+End State: 000
+Predecessors:
+Successors:
 Intermediate States (reverse order): 
 000
 block
@@ -121,7 +123,7 @@ block
 drop
 000
 local.get $2
-100
+001
 local.set $2
 000
 i32.const 1
@@ -129,11 +131,11 @@ i32.const 1
 local.set $1
 000
 local.get $0
-001
+100
 drop
-001
+100
 local.get $0
-001
+100
 local.set $0
 000
 i32.const 1
@@ -145,8 +147,9 @@ End
   parseWast(wasm, moduleText);
 
   CFG cfg = CFG::fromFunction(wasm.getFunction("bar"));
-  const size_t sz = 3;
-  MonotoneCFGAnalyzer<sz> analyzer = MonotoneCFGAnalyzer<sz>::fromCFG(&cfg);
+  FinitePowersetLattice lattice(wasm.getFunction("bar")->getNumLocals());
+  MonotoneCFGAnalyzer<FinitePowersetLattice> analyzer(lattice);
+  analyzer.fromCFG(&cfg);
   analyzer.evaluate();
 
   std::stringstream ss;
@@ -182,23 +185,27 @@ TEST_F(CFGTest, NonlinearLiveness) {
 
   auto analyzerText = R"analyzer(CFG Analyzer
 State Block: 0
-State at beginning: 00
-State at end: 01
+Beginning State: 00
+End State: 10
+Predecessors:
+Successors: 1 2
 Intermediate States (reverse order): 
-01
+10
 i32.eq
-01
+10
 i32.const 2
-01
+10
 local.get $0
-01
+10
 local.set $0
 00
 i32.const 1
 00
 State Block: 1
-State at beginning: 00
-State at end: 00
+Beginning State: 00
+End State: 00
+Predecessors: 0
+Successors: 3
 Intermediate States (reverse order): 
 00
 local.set $1
@@ -206,17 +213,21 @@ local.set $1
 i32.const 4
 00
 State Block: 2
-State at beginning: 01
-State at end: 00
+Beginning State: 10
+End State: 00
+Predecessors: 0
+Successors: 3
 Intermediate States (reverse order): 
 00
 drop
 00
 local.get $0
-01
+10
 State Block: 3
-State at beginning: 00
-State at end: 00
+Beginning State: 00
+End State: 00
+Predecessors: 2 1
+Successors:
 Intermediate States (reverse order): 
 00
 block
@@ -228,8 +239,9 @@ End
   parseWast(wasm, moduleText);
 
   CFG cfg = CFG::fromFunction(wasm.getFunction("bar"));
-  const size_t sz = 2;
-  MonotoneCFGAnalyzer<sz> analyzer = MonotoneCFGAnalyzer<sz>::fromCFG(&cfg);
+  FinitePowersetLattice lattice(wasm.getFunction("bar")->getNumLocals());
+  MonotoneCFGAnalyzer<FinitePowersetLattice> analyzer(lattice);
+  analyzer.fromCFG(&cfg);
   analyzer.evaluate();
 
   std::stringstream ss;