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, 49 insertions, 0 deletions

diff --git a/src/analysis/sign-lattice.cpp b/src/analysis/sign-lattice.cpp
new file mode 100644
index 000000000..9baa2f2fd
--- /dev/null
+++ b/src/analysis/sign-lattice.cpp
@@ -0,0 +1,49 @@
+#include "lattice.h"
+#include <type_traits>
+
+namespace wasm::analysis {
+
+struct SignLattice {
+public:
+  enum Sign { BOTTOM, NEGATIVE, ZERO, POSITIVE, TOP };
+
+private:
+  Sign value;
+
+public:
+  static bool isTop(const SignLattice& element) { return element.value == TOP; }
+
+  static bool isBottom(const SignLattice& element) {
+    return element.value == BOTTOM;
+  }
+
+  static LatticeComparison compare(const SignLattice& left,
+                                   const SignLattice& right) {
+    if (left.value == right.value) {
+      return EQUAL;
+    } else if (left.value == BOTTOM || right.value == TOP) {
+      return LESS;
+    } else if (left.value == TOP || right.value == BOTTOM) {
+      return GREATER;
+    } else {
+      return NO_RELATION;
+    }
+  }
+
+  // Modifies the left lattice element to the least upper bound between
+  // it and the right hand lattice element in-place. Returns true
+  // if the left lattice element has been changed.
+  void getLeastUpperBound(const SignLattice& right) {
+    if (value == right.value || value == TOP || right.value == BOTTOM) {
+      return;
+    } else if (value == BOTTOM || right.value == TOP) {
+      value = right.value;
+    } else {
+      value = TOP;
+    }
+  }
+};
+
+static_assert(is_lattice<SignLattice>);
+
+} // namespace wasm::analysis