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.

7 files changed, 410 insertions, 0 deletions

diff --git a/src/analysis/CMakeLists.txt b/src/analysis/CMakeLists.txt
index ea0494859..2fc4be305 100644
--- a/src/analysis/CMakeLists.txt
+++ b/src/analysis/CMakeLists.txt
@@ -1,6 +1,7 @@
 file(GLOB analysis_HEADERS *.h)
 set(analysis_SOURCES
   cfg.cpp
+  sign-lattice.cpp
   ${analysis_HEADERS}
 )
 add_library(analysis OBJECT ${analysis_SOURCES})
diff --git a/src/analysis/cfg.h b/src/analysis/cfg.h
index ba4d7a774..c14cf70f4 100644
--- a/src/analysis/cfg.h
+++ b/src/analysis/cfg.h
@@ -40,6 +40,10 @@ struct BasicBlock {
   iterator end() const { return insts.cend(); }
   size_t size() const { return insts.size(); }
 
+  using reverse_iterator = std::vector<Expression*>::const_reverse_iterator;
+  reverse_iterator rbegin() const { return insts.rbegin(); }
+  reverse_iterator rend() const { return insts.rend(); }
+
   // Iterables for predecessor and successor blocks.
   struct Predecessors;
   struct Successors;
@@ -48,6 +52,8 @@ struct BasicBlock {
 
   void print(std::ostream& os, Module* wasm = nullptr, size_t start = 0) const;
 
+  Index getIndex() const { return index; }
+
 private:
   Index index;
   std::vector<Expression*> insts;
diff --git a/src/analysis/lattice.h b/src/analysis/lattice.h
new file mode 100644
index 000000000..bad11284f
--- /dev/null
+++ b/src/analysis/lattice.h
@@ -0,0 +1,57 @@
+#ifndef wasm_analysis_lattice_h
+#define wasm_analysis_lattice_h
+
+#include "wasm.h"
+#include <bitset>
+#include <iostream>
+
+namespace wasm::analysis {
+
+enum LatticeComparison { NO_RELATION, EQUAL, LESS, GREATER };
+
+template<typename T>
+constexpr bool has_compare = std::is_invocable_r<LatticeComparison,
+                                                 decltype(T::compare),
+                                                 const T&,
+                                                 const T&>::value;
+template<typename T>
+constexpr bool has_getLeastUpperBound = std::
+  is_invocable_r<void, decltype(&T::getLeastUpperBound), T, const T&>::value;
+template<typename T>
+constexpr bool has_isTop =
+  std::is_invocable_r<bool, decltype(T::isTop), const T&>::value;
+template<typename T>
+constexpr bool has_isBottom =
+  std::is_invocable_r<bool, decltype(T::isBottom), const T&>::value;
+
+template<typename T>
+constexpr bool is_lattice =
+  has_compare<T>&& has_getLeastUpperBound<T>&& has_isTop<T>&& has_isBottom<T>;
+
+// Represents a powerset lattice element (i.e. a set) as a bitvector. A true
+// means that an element is present in the set.
+template<size_t N> struct BitsetPowersetLattice {
+  std::bitset<N> value;
+
+  static BitsetPowersetLattice<N> getBottom();
+  static bool isTop(const BitsetPowersetLattice<N>& element);
+  static bool isBottom(const BitsetPowersetLattice<N>& element);
+
+  // Compares two lattice elements and returns a result indicating the
+  // left element's relation to the right element.
+  static LatticeComparison compare(const BitsetPowersetLattice<N>& left,
+                                   const BitsetPowersetLattice<N>& right);
+
+  // Calculates the LUB of this current (left) lattice element with some right
+  // element. It then updates this current lattice element to the LUB in place.
+  void getLeastUpperBound(const BitsetPowersetLattice<N>& right);
+
+  // Prints out the bits in the bitvector for a lattice element.
+  void print(std::ostream& os);
+};
+
+} // namespace wasm::analysis
+
+#include "powerset-lattice-impl.h"
+
+#endif // wasm_analysis_lattice_h
diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h
new file mode 100644
index 000000000..61cd2ad0e
--- /dev/null
+++ b/src/analysis/monotone-analyzer-impl.h
@@ -0,0 +1,153 @@
+#ifndef wasm_analysis_monotone_analyzer_impl_h
+#define wasm_analysis_monotone_analyzer_impl_h
+
+#include <iostream>
+#include <unordered_map>
+
+#include "monotone-analyzer.h"
+
+namespace wasm::analysis {
+template<size_t N>
+inline BlockState<N>::BlockState(const BasicBlock* underlyingBlock)
+  : index(underlyingBlock->getIndex()), cfgBlock(underlyingBlock),
+    beginningState(BitsetPowersetLattice<N>::getBottom()),
+    endState(BitsetPowersetLattice<N>::getBottom()),
+    currState(BitsetPowersetLattice<N>::getBottom()) {}
+
+template<size_t N> inline void BlockState<N>::addPredecessor(BlockState* pred) {
+  predecessors.push_back(pred);
+}
+
+template<size_t N> inline void BlockState<N>::addSuccessor(BlockState* succ) {
+  successors.push_back(succ);
+}
+
+template<size_t N>
+inline BitsetPowersetLattice<N>& BlockState<N>::getFirstState() {
+  return beginningState;
+}
+
+template<size_t N>
+inline BitsetPowersetLattice<N>& BlockState<N>::getLastState() {
+  return endState;
+}
+
+// In our current limited implementation, we just update a new live variable
+// when it it is used in a get or set.
+template<size_t N> inline void BlockState<N>::visitLocalSet(LocalSet* curr) {
+  currState.value[curr->index] = false;
+}
+
+template<size_t N> inline void BlockState<N>::visitLocalGet(LocalGet* curr) {
+  currState.value[curr->index] = true;
+}
+
+template<size_t N> inline void BlockState<N>::transfer() {
+  // If the block is empty, we propagate the state by endState = currState, then
+  // currState = beginningState
+
+  // compute transfer function for all expressions in the CFG block
+  auto cfgIter = cfgBlock->rbegin();
+  currState = endState;
+
+  while (cfgIter != cfgBlock->rend()) {
+    // run transfer function.
+    BlockState<N>::visit(*cfgIter);
+    ++cfgIter;
+  }
+  beginningState = currState;
+}
+
+template<size_t N> inline void BlockState<N>::print(std::ostream& os) {
+  os << "State Block: " << index << std::endl;
+  os << "State at beginning: ";
+  beginningState.print(os);
+  os << std::endl << "State at end: ";
+  endState.print(os);
+  os << std::endl << "Intermediate States (reverse order): " << std::endl;
+
+  currState = endState;
+  currState.print(os);
+  os << std::endl;
+  auto cfgIter = cfgBlock->rbegin();
+
+  while (cfgIter != cfgBlock->rend()) {
+    // run transfer function.
+    os << ShallowExpression{*cfgIter} << std::endl;
+    BlockState<N>::visit(*cfgIter);
+    currState.print(os);
+    os << std::endl;
+    ++cfgIter;
+  }
+}
+
+template<size_t N>
+MonotoneCFGAnalyzer<N> inline MonotoneCFGAnalyzer<N>::fromCFG(CFG* cfg) {
+  MonotoneCFGAnalyzer<N> result;
+
+  // Map BasicBlocks to each BlockState's index
+  std::unordered_map<const BasicBlock*, size_t> basicBlockToState;
+  size_t index = 0;
+  for (auto it = cfg->begin(); it != cfg->end(); it++) {
+    result.stateBlocks.emplace_back(&(*it));
+    basicBlockToState[&(*it)] = index++;
+  }
+
+  // Update predecessors and successors of each BlockState object
+  // according to the BasicBlock's predecessors and successors.
+  for (index = 0; index < result.stateBlocks.size(); ++index) {
+    BlockState<N>& currBlock = result.stateBlocks.at(index);
+    BasicBlock::Predecessors preds = currBlock.cfgBlock->preds();
+    BasicBlock::Successors succs = currBlock.cfgBlock->succs();
+    for (auto pred : preds) {
+      currBlock.addPredecessor(&result.stateBlocks[basicBlockToState[&pred]]);
+    }
+
+    for (auto succ : succs) {
+      currBlock.addSuccessor(&result.stateBlocks[basicBlockToState[&succ]]);
+    }
+  }
+
+  return result;
+}
+
+template<size_t N> inline void MonotoneCFGAnalyzer<N>::evaluate() {
+  std::queue<Index> worklist;
+
+  for (auto it = stateBlocks.rbegin(); it != stateBlocks.rend(); ++it) {
+    worklist.push(it->index);
+  }
+
+  while (!worklist.empty()) {
+    BlockState<N>& currBlockState = stateBlocks[worklist.front()];
+    worklist.pop();
+    currBlockState.transfer();
+
+    // Propagate state to dependents
+    for (size_t j = 0; j < currBlockState.predecessors.size(); ++j) {
+      BitsetPowersetLattice<N>& predLast =
+        currBlockState.predecessors[j]->getLastState();
+
+      LatticeComparison cmp = BitsetPowersetLattice<N>::compare(
+        predLast, currBlockState.getFirstState());
+
+      if (cmp == LatticeComparison::NO_RELATION ||
+          cmp == LatticeComparison::LESS) {
+        predLast.getLeastUpperBound(currBlockState.getFirstState());
+        worklist.push(currBlockState.predecessors[j]->index);
+      }
+    }
+  }
+}
+
+template<size_t N> inline void MonotoneCFGAnalyzer<N>::print(std::ostream& os) {
+  os << "CFG Analyzer" << std::endl;
+  for (auto state : stateBlocks) {
+    state.print(os);
+  }
+  os << "End" << std::endl;
+}
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_monotone_analyzer_impl_h
diff --git a/src/analysis/monotone-analyzer.h b/src/analysis/monotone-analyzer.h
new file mode 100644
index 000000000..dfe6143d5
--- /dev/null
+++ b/src/analysis/monotone-analyzer.h
@@ -0,0 +1,77 @@
+#ifndef wasm_analysis_monotone_analyzer_h
+#define wasm_analysis_monotone_analyzer_h
+
+#include <iostream>
+#include <queue>
+#include <vector>
+
+#include "cfg.h"
+#include "lattice.h"
+#include "wasm-traversal.h"
+
+namespace wasm::analysis {
+
+template<size_t N> struct MonotoneCFGAnalyzer;
+
+// A node which contains all the lattice states for a given CFG node.
+template<size_t N> struct BlockState : public Visitor<BlockState<N>> {
+  static_assert(is_lattice<BitsetPowersetLattice<N>>);
+  BlockState(const BasicBlock* underlyingBlock);
+
+  void addPredecessor(BlockState* pred);
+  void addSuccessor(BlockState* succ);
+
+  BitsetPowersetLattice<N>& getFirstState();
+  BitsetPowersetLattice<N>& getLastState();
+
+  // Transfer function implementation. Modifies the state for a particular
+  // expression type.
+  void visitLocalSet(LocalSet* curr);
+  void visitLocalGet(LocalGet* curr);
+
+  // Executes the transfer function on all the expressions of the corresponding
+  // CFG and then propagates the state to all predecessors (which depend on the
+  // current node).
+  void transfer();
+
+  // prints out all states.
+  void print(std::ostream& os);
+
+private:
+  // The index of the block is same as the CFG index.
+  Index index;
+  const BasicBlock* cfgBlock;
+  // State at beginning of CFG node.
+  BitsetPowersetLattice<N> beginningState;
+  // State at the end of the CFG node.
+  BitsetPowersetLattice<N> endState;
+  // Holds intermediate state values.
+  BitsetPowersetLattice<N> currState;
+  std::vector<BlockState*> predecessors;
+  std::vector<BlockState*> successors;
+
+  friend MonotoneCFGAnalyzer<N>;
+};
+
+template<size_t N> struct MonotoneCFGAnalyzer {
+  static_assert(is_lattice<BitsetPowersetLattice<N>>);
+
+  // Constructs a graph of BlockState objects which parallels
+  // the CFG graph. Each CFG node corresponds to a BlockState node.
+  static MonotoneCFGAnalyzer<N> fromCFG(CFG* cfg);
+
+  // Runs the worklist algorithm to compute the states for the BlockList graph.
+  void evaluate();
+
+  void print(std::ostream& os);
+
+private:
+  std::vector<BlockState<N>> stateBlocks;
+  friend BlockState<N>;
+};
+
+} // namespace wasm::analysis
+
+#include "monotone-analyzer-impl.h"
+
+#endif // wasm_analysis_monotone_analyzer_h
diff --git a/src/analysis/powerset-lattice-impl.h b/src/analysis/powerset-lattice-impl.h
new file mode 100644
index 000000000..6207c2bec
--- /dev/null
+++ b/src/analysis/powerset-lattice-impl.h
@@ -0,0 +1,67 @@
+#ifndef wasm_analysis_lattice_impl_h
+#define wasm_analysis_lattice_impl_h
+
+#include "lattice.h"
+
+namespace wasm::analysis {
+
+template<size_t N>
+inline BitsetPowersetLattice<N> BitsetPowersetLattice<N>::getBottom() {
+  // Return the empty set as the bottom lattice element.
+  BitsetPowersetLattice<N> result{0};
+  return result;
+}
+
+template<size_t N>
+inline bool
+BitsetPowersetLattice<N>::isTop(const BitsetPowersetLattice<N>& element) {
+  // Top lattice element is the set containing all possible elements.
+  return element.value.all();
+}
+
+template<size_t N>
+inline bool
+BitsetPowersetLattice<N>::isBottom(const BitsetPowersetLattice<N>& element) {
+  // Bottom lattice element is the empty set.
+  return element.value.none();
+}
+
+template<size_t N>
+inline LatticeComparison
+BitsetPowersetLattice<N>::compare(const BitsetPowersetLattice<N>& left,
+                                  const BitsetPowersetLattice<N>& right) {
+  size_t leftCount = left.value.count();
+  size_t rightCount = right.value.count();
+
+  // If left has more elements, left might be a superset of right.
+  if (leftCount > rightCount) {
+    if ((left.value | right.value) == left.value) {
+      return GREATER;
+    }
+    // If right has more elements, right might be a superset of left.
+  } else if (leftCount < rightCount) {
+    if ((left.value | right.value) == right.value) {
+      return LESS;
+    }
+  } else if (left.value == right.value) {
+    return EQUAL;
+  }
+
+  return NO_RELATION;
+}
+
+// Implement LUB as an OR of the two bitsets.
+template<size_t N>
+inline void BitsetPowersetLattice<N>::getLeastUpperBound(
+  const BitsetPowersetLattice<N>& right) {
+  value |= right.value;
+}
+
+template<size_t N>
+inline void BitsetPowersetLattice<N>::print(std::ostream& os) {
+  os << value;
+}
+
+}; // namespace wasm::analysis
+
+#endif // wasm_analysis_lattice_impl_h
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