Lattice to model Stack (#5849)

This change introduces StackLattice, a lattice to model stack-related
behavior. It is templated on a separate lattice whose elements model
some property of individual values on the stack. The StackLattice
allows users to access the top of the stack, push abstract values, and
pop them. Comparisons and least upper bound operations are done on a
value by value basis starting from the top of the stack and moving
toward the bottom. This is because it allows stacks from different
scopes to be joined easily.

An application of StackLattice is to model the wasm value stack. The goal
is to organize lattice elements representing individual stack values in a
natural way which mirrors the wasm value stack. Transfer functions operate
on each stack value individually. The stack lattice is an intermediate
structure which is not intended to be directly operated on. Rather, it
simulates the push and pop behavior of instructions.

2 files changed, 215 insertions, 34 deletions

diff --git a/test/gtest/cfg.cpp b/test/gtest/cfg.cpp
index 07b44e261..6873f63fa 100644
--- a/test/gtest/cfg.cpp
+++ b/test/gtest/cfg.cpp
@@ -5,6 +5,7 @@
 #include "analysis/liveness-transfer-function.h"
 #include "analysis/monotone-analyzer.h"
 #include "analysis/reaching-definitions-transfer-function.h"
+#include "analysis/stack-lattice.h"
 #include "ir/find_all.h"
 #include "print-test.h"
 #include "wasm.h"
@@ -579,3 +580,100 @@ TEST_F(CFGTest, ReachingDefinitionsLoop) {
 
   EXPECT_EQ(expectedResult, getSetses);
 }
+
+TEST_F(CFGTest, StackLatticeFunctioning) {
+  FiniteIntPowersetLattice contentLattice(4);
+  StackLattice<FiniteIntPowersetLattice> stackLattice(contentLattice);
+
+  // These are constructed as expected references to compare everything else.
+  StackLattice<FiniteIntPowersetLattice>::Element expectedStack =
+    stackLattice.getBottom();
+  FiniteIntPowersetLattice::Element expectedStackElement =
+    contentLattice.getBottom();
+
+  StackLattice<FiniteIntPowersetLattice>::Element firstStack =
+    stackLattice.getBottom();
+  StackLattice<FiniteIntPowersetLattice>::Element secondStack =
+    stackLattice.getBottom();
+
+  for (size_t i = 0; i < 4; i++) {
+    FiniteIntPowersetLattice::Element temp = contentLattice.getBottom();
+    for (size_t j = 0; j <= i; j++) {
+      temp.set(j, true);
+    }
+    firstStack.push(temp);
+    secondStack.push(temp);
+    if (i < 2) {
+      expectedStack.push(temp);
+    }
+  }
+
+  EXPECT_EQ(stackLattice.compare(firstStack, secondStack),
+            LatticeComparison::EQUAL);
+
+  for (size_t j = 0; j < 4; ++j) {
+    expectedStackElement.set(j, true);
+  }
+
+  EXPECT_EQ(contentLattice.compare(secondStack.pop(), expectedStackElement),
+            LatticeComparison::EQUAL);
+  expectedStackElement.set(3, false);
+  EXPECT_EQ(contentLattice.compare(secondStack.pop(), expectedStackElement),
+            LatticeComparison::EQUAL);
+
+  EXPECT_EQ(stackLattice.compare(firstStack, secondStack),
+            LatticeComparison::GREATER);
+  EXPECT_EQ(stackLattice.compare(secondStack, firstStack),
+            LatticeComparison::LESS);
+
+  EXPECT_EQ(stackLattice.compare(secondStack, expectedStack),
+            LatticeComparison::EQUAL);
+
+  {
+    expectedStack.stackTop().set(0, false);
+    expectedStack.stackTop().set(2, true);
+    FiniteIntPowersetLattice::Element temp = expectedStack.pop();
+    expectedStack.stackTop().set(3, true);
+    expectedStack.push(temp);
+
+    FiniteIntPowersetLattice::Element temp2 = contentLattice.getBottom();
+    temp2.set(1, true);
+    temp2.set(3, true);
+    expectedStack.push(temp2);
+  }
+
+  StackLattice<FiniteIntPowersetLattice>::Element thirdStack =
+    stackLattice.getBottom();
+  {
+    FiniteIntPowersetLattice::Element temp = contentLattice.getBottom();
+    temp.set(0, true);
+    temp.set(3, true);
+    FiniteIntPowersetLattice::Element temp2 = contentLattice.getBottom();
+    temp2.set(1, true);
+    temp2.set(2, true);
+    FiniteIntPowersetLattice::Element temp3 = contentLattice.getBottom();
+    temp3.set(1, true);
+    temp3.set(3, true);
+    thirdStack.push(std::move(temp));
+    thirdStack.push(std::move(temp2));
+    thirdStack.push(std::move(temp3));
+  }
+
+  EXPECT_EQ(stackLattice.compare(secondStack, thirdStack),
+            LatticeComparison::NO_RELATION);
+
+  EXPECT_EQ(stackLattice.compare(thirdStack, expectedStack),
+            LatticeComparison::EQUAL);
+
+  EXPECT_EQ(thirdStack.makeLeastUpperBound(secondStack), true);
+
+  {
+    expectedStack.stackTop().set(0, true);
+    FiniteIntPowersetLattice::Element temp = expectedStack.pop();
+    expectedStack.stackTop().set(0, true);
+    expectedStack.push(temp);
+  }
+
+  EXPECT_EQ(stackLattice.compare(thirdStack, expectedStack),
+            LatticeComparison::EQUAL);
+}
diff --git a/test/lit/fuzz-lattices.test b/test/lit/fuzz-lattices.test
index 361c46930..29533d6c5 100644
--- a/test/lit/fuzz-lattices.test
+++ b/test/lit/fuzz-lattices.test
@@ -1227,79 +1227,162 @@
 ;; CHECK-NEXT: )
 ;; CHECK-NEXT: 
 ;; CHECK-NEXT: Using lattice element seed 4234964801256893051
-;; CHECK-NEXT: Generated FinitePowersetLattice<LocalSet*> elements:
-;; CHECK-NEXT: 1111000011,
-;; CHECK-NEXT: 0110011101,
-;; CHECK-NEXT: 0010001110
-;; CHECK-NEXT: for func to test ReachingDefinitionsTransferFunction.
+;; CHECK-NEXT: Generated FiniteIntPowersetLattice elements:
+;; CHECK-NEXT: 1,
+;; CHECK-NEXT: 1,
+;; CHECK-NEXT: 0
+;; CHECK-NEXT: for func to test LivenessTransferFunction.
 ;; CHECK-NEXT: 
 ;; CHECK-NEXT: Using lattice element seed 4577570485573586799
-;; CHECK-NEXT: Generated FiniteIntPowersetLattice elements:
+;; CHECK-NEXT: Generated FinitePowersetLattice<LocalSet*> elements:
 ;; CHECK-NEXT: ,
 ;; CHECK-NEXT: ,
 ;; CHECK-NEXT: 
-;; CHECK-NEXT: for func_invoker to test LivenessTransferFunction.
+;; CHECK-NEXT: for func_invoker to test ReachingDefinitionsTransferFunction.
 ;; CHECK-NEXT: 
 ;; CHECK-NEXT: Using lattice element seed 8191301589003135276
 ;; CHECK-NEXT: Generated FinitePowersetLattice<LocalSet*> elements:
 ;; CHECK-NEXT: 0,
-;; CHECK-NEXT: 1,
+;; CHECK-NEXT: 0,
 ;; CHECK-NEXT: 1
 ;; CHECK-NEXT: for func_6 to test ReachingDefinitionsTransferFunction.
 ;; CHECK-NEXT: 
 ;; CHECK-NEXT: Using lattice element seed 8068299453651594774
-;; CHECK-NEXT: Generated FiniteIntPowersetLattice elements:
+;; CHECK-NEXT: Generated FinitePowersetLattice<LocalSet*> elements:
 ;; CHECK-NEXT: ,
 ;; CHECK-NEXT: ,
 ;; CHECK-NEXT: 
-;; CHECK-NEXT: for func_6_invoker to test LivenessTransferFunction.
+;; CHECK-NEXT: for func_6_invoker to test ReachingDefinitionsTransferFunction.
 ;; CHECK-NEXT: 
 ;; CHECK-NEXT: Using lattice element seed 5852178751023674337
-;; CHECK-NEXT: Generated FiniteIntPowersetLattice elements:
-;; CHECK-NEXT: 111111,
-;; CHECK-NEXT: 000100,
-;; CHECK-NEXT: 010000
+;; CHECK-NEXT: Generated StackLattice<FiniteIntPowersetLattice> elements:
+;; CHECK-NEXT: 010010
+;; CHECK-NEXT: 000110
+;; CHECK-NEXT: 000010
+;; CHECK-NEXT: 111100
+;; CHECK-NEXT: 111001
+;; CHECK-NEXT: ,
+;; CHECK-NEXT: 110111
+;; CHECK-NEXT: 001000
+;; CHECK-NEXT: 100000
+;; CHECK-NEXT: 010010
+;; CHECK-NEXT: 011110
+;; CHECK-NEXT: 101111
+;; CHECK-NEXT: 000001
+;; CHECK-NEXT: 011011
+;; CHECK-NEXT: ,
+;; CHECK-NEXT: 111011
+;; CHECK-NEXT: 010111
+;; CHECK-NEXT: 111011
+;; CHECK-NEXT: 011001
+;; CHECK-NEXT: 001000
+;; CHECK-NEXT: 001110
+;; CHECK-NEXT: 101001
+;; CHECK-NEXT: 010100
+;; CHECK-NEXT: 111111
+;; CHECK-NEXT: 
 ;; CHECK-NEXT: for func_8 to test LivenessTransferFunction.
 ;; CHECK-NEXT: 
 ;; CHECK-NEXT: Using lattice element seed 13832862600605363478
-;; CHECK-NEXT: Generated FinitePowersetLattice<LocalSet*> elements:
+;; CHECK-NEXT: Generated StackLattice<FiniteIntPowersetLattice> elements:
 ;; CHECK-NEXT: ,
 ;; CHECK-NEXT: ,
 ;; CHECK-NEXT: 
-;; CHECK-NEXT: for func_8_invoker to test ReachingDefinitionsTransferFunction.
+;; CHECK-NEXT: for func_8_invoker to test LivenessTransferFunction.
 ;; CHECK-NEXT: 
 ;; CHECK-NEXT: Using lattice element seed 7970088265179676333
 ;; CHECK-NEXT: Generated FiniteIntPowersetLattice elements:
-;; CHECK-NEXT: 011,
-;; CHECK-NEXT: 011,
+;; CHECK-NEXT: 110,
+;; CHECK-NEXT: 001,
 ;; CHECK-NEXT: 000
 ;; CHECK-NEXT: for func_10 to test LivenessTransferFunction.
 ;; CHECK-NEXT: 
 ;; CHECK-NEXT: Using lattice element seed 14582942952639200251
-;; CHECK-NEXT: Generated FinitePowersetLattice<LocalSet*> elements:
+;; CHECK-NEXT: Generated FiniteIntPowersetLattice elements:
 ;; CHECK-NEXT: ,
 ;; CHECK-NEXT: ,
 ;; CHECK-NEXT: 
-;; CHECK-NEXT: for func_10_invoker to test ReachingDefinitionsTransferFunction.
+;; CHECK-NEXT: for func_10_invoker to test LivenessTransferFunction.
 ;; CHECK-NEXT: 
 ;; CHECK-NEXT: Using lattice element seed 16331556144677973625
-;; CHECK-NEXT: Generated FinitePowersetLattice<LocalSet*> elements:
-;; CHECK-NEXT: 001000110000,
-;; CHECK-NEXT: 011010100000,
-;; CHECK-NEXT: 001011001101
-;; CHECK-NEXT: for func_12 to test ReachingDefinitionsTransferFunction.
+;; CHECK-NEXT: Generated StackLattice<FiniteIntPowersetLattice> elements:
+;; CHECK-NEXT: 111011111001
+;; CHECK-NEXT: 111101000101
+;; CHECK-NEXT: 010000101000
+;; CHECK-NEXT: 001010000110
+;; CHECK-NEXT: 010100100001
+;; CHECK-NEXT: 111101100101
+;; CHECK-NEXT: 111110001001
+;; CHECK-NEXT: 100110000100
+;; CHECK-NEXT: 000111111001
+;; CHECK-NEXT: ,
+;; CHECK-NEXT: 111100110101
+;; CHECK-NEXT: 100010111101
+;; CHECK-NEXT: 010100011110
+;; CHECK-NEXT: 000011001000
+;; CHECK-NEXT: 010000100101
+;; CHECK-NEXT: 010010101010
+;; CHECK-NEXT: 110101110000
+;; CHECK-NEXT: 010110000100
+;; CHECK-NEXT: 111101011111
+;; CHECK-NEXT: 010101001111
+;; CHECK-NEXT: 111000110111
+;; CHECK-NEXT: ,
+;; CHECK-NEXT: 110000010011
+;; CHECK-NEXT: 010000001001
+;; CHECK-NEXT: 001111100000
+;; CHECK-NEXT: 011010110101
+;; CHECK-NEXT: 011110111110
+;; CHECK-NEXT: 001111010001
+;; CHECK-NEXT: 100100001010
+;; CHECK-NEXT: 010010100001
+;; CHECK-NEXT: 010101001000
+;; CHECK-NEXT: 011111011001
+;; CHECK-NEXT: 001111100010
+;; CHECK-NEXT: 100111000001
+;; CHECK-NEXT: 001011010100
+;; CHECK-NEXT: 101001010010
+;; CHECK-NEXT: 
+;; CHECK-NEXT: for func_12 to test LivenessTransferFunction.
 ;; CHECK-NEXT: 
 ;; CHECK-NEXT: Using lattice element seed 6783688792201211800
-;; CHECK-NEXT: Generated FiniteIntPowersetLattice elements:
-;; CHECK-NEXT: 00001,
-;; CHECK-NEXT: 00011,
-;; CHECK-NEXT: 10000
+;; CHECK-NEXT: Generated StackLattice<FiniteIntPowersetLattice> elements:
+;; CHECK-NEXT: 00100
+;; CHECK-NEXT: 11100
+;; CHECK-NEXT: 00110
+;; CHECK-NEXT: 10110
+;; CHECK-NEXT: 01001
+;; CHECK-NEXT: 00110
+;; CHECK-NEXT: 10110
+;; CHECK-NEXT: 11100
+;; CHECK-NEXT: 00101
+;; CHECK-NEXT: 01001
+;; CHECK-NEXT: 01000
+;; CHECK-NEXT: 00101
+;; CHECK-NEXT: ,
+;; CHECK-NEXT: 11010
+;; CHECK-NEXT: 11001
+;; CHECK-NEXT: 00101
+;; CHECK-NEXT: 10010
+;; CHECK-NEXT: 00101
+;; CHECK-NEXT: 00111
+;; CHECK-NEXT: 00000
+;; CHECK-NEXT: 10111
+;; CHECK-NEXT: ,
+;; CHECK-NEXT: 11010
+;; CHECK-NEXT: 11100
+;; CHECK-NEXT: 10001
+;; CHECK-NEXT: 11011
+;; CHECK-NEXT: 01001
+;; CHECK-NEXT: 11011
+;; CHECK-NEXT: 00101
+;; CHECK-NEXT: 
 ;; CHECK-NEXT: for func_13 to test LivenessTransferFunction.
 ;; CHECK-NEXT: 
 ;; CHECK-NEXT: Using lattice element seed 15457352654905208821
-;; CHECK-NEXT: Generated FinitePowersetLattice<LocalSet*> elements:
-;; CHECK-NEXT: 111000100001010101,
-;; CHECK-NEXT: 001110111010000110,
-;; CHECK-NEXT: 111010111111110110
-;; CHECK-NEXT: for hashMemory to test ReachingDefinitionsTransferFunction.
+;; CHECK-NEXT: Generated FiniteIntPowersetLattice elements:
+;; CHECK-NEXT: 1,
+;; CHECK-NEXT: 0,
+;; CHECK-NEXT: 1
+;; CHECK-NEXT: for hashMemory to test LivenessTransferFunction.
 ;; CHECK-NEXT: