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.

5 files changed, 234 insertions, 171 deletions

diff --git a/src/analysis/lattice.h b/src/analysis/lattice.h
index bad11284f..4fb794f1b 100644
--- a/src/analysis/lattice.h
+++ b/src/analysis/lattice.h
@@ -1,55 +1,108 @@
 #ifndef wasm_analysis_lattice_h
 #define wasm_analysis_lattice_h
 
-#include "wasm.h"
-#include <bitset>
 #include <iostream>
+#include <vector>
+
+#include "wasm.h"
 
 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>
+template<typename Lattice>
+constexpr bool has_getBottom =
+  std::is_invocable_r<typename Lattice::Element,
+                      decltype(&Lattice::getBottom),
+                      Lattice>::value;
+template<typename Lattice>
+constexpr bool has_compare =
+  std::is_invocable_r<LatticeComparison,
+                      decltype(Lattice::compare),
+                      const typename Lattice::Element&,
+                      const typename Lattice::Element&>::value;
+template<typename Element>
+constexpr bool has_makeLeastUpperBound =
+  std::is_invocable_r<void,
+                      decltype(&Element::makeLeastUpperBound),
+                      Element,
+                      const Element&>::value;
+template<typename Element>
 constexpr bool has_isTop =
-  std::is_invocable_r<bool, decltype(T::isTop), const T&>::value;
-template<typename T>
+  std::is_invocable_r<bool, decltype(&Element::isTop), Element>::value;
+template<typename Element>
 constexpr bool has_isBottom =
-  std::is_invocable_r<bool, decltype(T::isBottom), const T&>::value;
+  std::is_invocable_r<bool, decltype(&Element::isBottom), Element>::value;
+
+template<typename Lattice>
+constexpr bool is_lattice = has_getBottom<Lattice>&& has_compare<Lattice>&&
+  has_makeLeastUpperBound<typename Lattice::Element>&& has_isTop<
+    typename Lattice::Element>&& has_isBottom<typename Lattice::Element>;
+
+// Represents a powerset lattice which is constructed from a finite set which
+// can be represented by a bitvector. Set elements are represented by
+// FinitePowersetLattice::Element, which represents members present in each
+// element by bits in the bitvector.
+class FinitePowersetLattice {
+
+  // The size of the set that the powerset lattice was created from. This is
+  // equivalent to the size of the Top lattice element.
+  size_t setSize;
+
+public:
+  FinitePowersetLattice(size_t setSize) : setSize(setSize) {}
+
+  // This represents an element of a powerset lattice. The element is itself a
+  // set which has set members. The bitvector tracks which possible members of
+  // the element are actually present.
+  class Element {
+    // If bitvector[i] is true, then member i is present in the lattice element,
+    // otherwise it isn't.
+    std::vector<bool> bitvector;
 
-template<typename T>
-constexpr bool is_lattice =
-  has_compare<T>&& has_getLeastUpperBound<T>&& has_isTop<T>&& has_isBottom<T>;
+    // This constructs a bottom element, given the lattice set size. Used by the
+    // lattice's getBottom function.
+    Element(size_t latticeSetSize) : bitvector(latticeSetSize) {}
 
-// 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;
+  public:
+    Element(Element&& source) = default;
+    Element(Element& source) = default;
 
-  static BitsetPowersetLattice<N> getBottom();
-  static bool isTop(const BitsetPowersetLattice<N>& element);
-  static bool isBottom(const BitsetPowersetLattice<N>& element);
+    Element& operator=(Element&& source) = default;
+    Element& operator=(const Element& source) = default;
+
+    // Counts the number of members present the element itself. For instance, if
+    // we had {true, false, true}, the count would be 2. O(N) operation which
+    // iterates through the bitvector.
+    size_t count();
+
+    bool get(size_t index) { return bitvector[index]; }
+    void set(size_t index, bool value) { bitvector[index] = value; }
+
+    bool isTop() { return count() == bitvector.size(); }
+    bool isBottom() { return count() == 0; }
+
+    // Calculates the LUB of this element with some other element and sets
+    // this element to the LUB in place. Returns true if this element before
+    // this method call was different than the LUB.
+    bool makeLeastUpperBound(const Element& other);
+
+    // Prints out the bits in the bitvector for a lattice element.
+    void print(std::ostream& os);
+
+    friend FinitePowersetLattice;
+  };
 
   // 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);
+  static LatticeComparison compare(const Element& left, const Element& 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);
+  // Returns an instance of the bottom lattice element.
+  Element getBottom();
 };
 
+static_assert(is_lattice<FinitePowersetLattice>);
+
 } // namespace wasm::analysis
 
 #include "powerset-lattice-impl.h"
diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h
index 61cd2ad0e..a2e059e29 100644
--- a/src/analysis/monotone-analyzer-impl.h
+++ b/src/analysis/monotone-analyzer-impl.h
@@ -7,63 +7,59 @@
 #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;
+// All states are set to the bottom lattice element using the lattice in this
+// constructor.
+template<typename Lattice>
+inline BlockState<Lattice>::BlockState(const BasicBlock* underlyingBlock,
+                                       Lattice& lattice)
+  : index(underlyingBlock->getIndex()), cfgBlock(underlyingBlock),
+    beginningState(lattice.getBottom()), endState(lattice.getBottom()),
+    currState(lattice.getBottom()) {}
+
+// In our current limited implementation, we just update state on gets
+// and sets of local indices.
+template<typename Lattice>
+inline void BlockState<Lattice>::visitLocalSet(LocalSet* curr) {
+  currState.set(curr->index, false);
 }
 
-template<size_t N> inline void BlockState<N>::visitLocalGet(LocalGet* curr) {
-  currState.value[curr->index] = true;
+template<typename Lattice>
+inline void BlockState<Lattice>::visitLocalGet(LocalGet* curr) {
+  currState.set(curr->index, true);
 }
 
-template<size_t N> inline void BlockState<N>::transfer() {
+template<typename Lattice> inline void BlockState<Lattice>::transfer() {
   // If the block is empty, we propagate the state by endState = currState, then
-  // currState = beginningState
+  // currState = beginningState.
 
-  // compute transfer function for all expressions in the CFG block
+  // 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);
+    // Run transfer function.
+    BlockState::visit(*cfgIter);
     ++cfgIter;
   }
-  beginningState = currState;
+  beginningState = std::move(currState);
 }
 
-template<size_t N> inline void BlockState<N>::print(std::ostream& os) {
+template<typename Lattice>
+inline void BlockState<Lattice>::print(std::ostream& os) {
   os << "State Block: " << index << std::endl;
-  os << "State at beginning: ";
+  os << "Beginning State: ";
   beginningState.print(os);
-  os << std::endl << "State at end: ";
+  os << std::endl << "End State: ";
   endState.print(os);
+  os << std::endl << "Predecessors:";
+  for (auto pred : predecessors) {
+    os << " " << pred->cfgBlock->getIndex();
+  }
+  os << std::endl << "Successors:";
+  for (auto succ : successors) {
+    os << " " << succ->cfgBlock->getIndex();
+  }
   os << std::endl << "Intermediate States (reverse order): " << std::endl;
 
   currState = endState;
@@ -71,47 +67,47 @@ template<size_t N> inline void BlockState<N>::print(std::ostream& os) {
   os << std::endl;
   auto cfgIter = cfgBlock->rbegin();
 
+  // Since we don't store the intermediate states in the BlockState, we need to
+  // re-run the transfer function on all the CFG node expressions to reconstruct
+  // the intermediate states here.
   while (cfgIter != cfgBlock->rend()) {
-    // run transfer function.
     os << ShallowExpression{*cfgIter} << std::endl;
-    BlockState<N>::visit(*cfgIter);
+    BlockState::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
+template<typename Lattice>
+inline void MonotoneCFGAnalyzer<Lattice>::fromCFG(CFG* cfg) {
+  // Construct BlockStates for each BasicBlock and map each BasicBlock to each
+  // BlockState's index in stateBlocks.
   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));
+    stateBlocks.emplace_back(&(*it), lattice);
     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);
+  for (index = 0; index < stateBlocks.size(); ++index) {
+    BlockState<Lattice>& currBlock = 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& pred : preds) {
+      currBlock.predecessors.push_back(&stateBlocks[basicBlockToState[&pred]]);
     }
 
-    for (auto succ : succs) {
-      currBlock.addSuccessor(&result.stateBlocks[basicBlockToState[&succ]]);
+    for (auto& succ : succs) {
+      currBlock.successors.push_back(&stateBlocks[basicBlockToState[&succ]]);
     }
   }
-
-  return result;
 }
 
-template<size_t N> inline void MonotoneCFGAnalyzer<N>::evaluate() {
+template<typename Lattice>
+inline void MonotoneCFGAnalyzer<Lattice>::evaluate() {
   std::queue<Index> worklist;
 
   for (auto it = stateBlocks.rbegin(); it != stateBlocks.rend(); ++it) {
@@ -119,28 +115,27 @@ template<size_t N> inline void MonotoneCFGAnalyzer<N>::evaluate() {
   }
 
   while (!worklist.empty()) {
-    BlockState<N>& currBlockState = stateBlocks[worklist.front()];
+    BlockState<Lattice>& currBlockState = stateBlocks[worklist.front()];
     worklist.pop();
+
+    // For each expression, applies the transfer function, using the expression,
+    // on the state of the expression it depends upon (here the next expression)
+    // to arrive at the expression's state. The beginning and end states of the
+    // CFG block will be updated.
     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());
+      if (currBlockState.predecessors[j]->getLastState().makeLeastUpperBound(
+            currBlockState.getFirstState())) {
         worklist.push(currBlockState.predecessors[j]->index);
       }
     }
   }
 }
 
-template<size_t N> inline void MonotoneCFGAnalyzer<N>::print(std::ostream& os) {
+template<typename Lattice>
+inline void MonotoneCFGAnalyzer<Lattice>::print(std::ostream& os) {
   os << "CFG Analyzer" << std::endl;
   for (auto state : stateBlocks) {
     state.print(os);
diff --git a/src/analysis/monotone-analyzer.h b/src/analysis/monotone-analyzer.h
index dfe6143d5..7c0dcc630 100644
--- a/src/analysis/monotone-analyzer.h
+++ b/src/analysis/monotone-analyzer.h
@@ -11,18 +11,17 @@
 
 namespace wasm::analysis {
 
-template<size_t N> struct MonotoneCFGAnalyzer;
+template<typename Lattice> 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);
+template<typename Lattice>
+struct BlockState : public Visitor<BlockState<Lattice>> {
+  static_assert(is_lattice<Lattice>);
+  // All states are set to the bottom lattice element in this constructor.
+  BlockState(const BasicBlock* underlyingBlock, Lattice& lattice);
 
-  void addPredecessor(BlockState* pred);
-  void addSuccessor(BlockState* succ);
-
-  BitsetPowersetLattice<N>& getFirstState();
-  BitsetPowersetLattice<N>& getLastState();
+  typename Lattice::Element& getFirstState() { return beginningState; }
+  typename Lattice::Element& getLastState() { return endState; }
 
   // Transfer function implementation. Modifies the state for a particular
   // expression type.
@@ -30,11 +29,10 @@ template<size_t N> struct BlockState : public Visitor<BlockState<N>> {
   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).
+  // CFG node.
   void transfer();
 
-  // prints out all states.
+  // Prints out all intermediate states in the block.
   void print(std::ostream& os);
 
 private:
@@ -42,32 +40,33 @@ private:
   Index index;
   const BasicBlock* cfgBlock;
   // State at beginning of CFG node.
-  BitsetPowersetLattice<N> beginningState;
+  typename Lattice::Element beginningState;
   // State at the end of the CFG node.
-  BitsetPowersetLattice<N> endState;
+  typename Lattice::Element endState;
   // Holds intermediate state values.
-  BitsetPowersetLattice<N> currState;
-  std::vector<BlockState*> predecessors;
-  std::vector<BlockState*> successors;
+  typename Lattice::Element currState;
+  std::vector<BlockState<Lattice>*> predecessors;
+  std::vector<BlockState<Lattice>*> successors;
 
-  friend MonotoneCFGAnalyzer<N>;
+  friend MonotoneCFGAnalyzer<Lattice>;
 };
 
-template<size_t N> struct MonotoneCFGAnalyzer {
-  static_assert(is_lattice<BitsetPowersetLattice<N>>);
+template<typename Lattice> struct MonotoneCFGAnalyzer {
+  MonotoneCFGAnalyzer(Lattice lattice) : lattice(lattice) {}
 
   // 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);
+  void fromCFG(CFG* cfg);
 
   // Runs the worklist algorithm to compute the states for the BlockList graph.
   void evaluate();
 
+  // Prints out all BlockStates in this analyzer.
   void print(std::ostream& os);
 
 private:
-  std::vector<BlockState<N>> stateBlocks;
-  friend BlockState<N>;
+  Lattice lattice;
+  std::vector<BlockState<Lattice>> stateBlocks;
 };
 
 } // namespace wasm::analysis
diff --git a/src/analysis/powerset-lattice-impl.h b/src/analysis/powerset-lattice-impl.h
index 6207c2bec..24931618a 100644
--- a/src/analysis/powerset-lattice-impl.h
+++ b/src/analysis/powerset-lattice-impl.h
@@ -5,61 +5,81 @@
 
 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;
-}
+inline LatticeComparison
+FinitePowersetLattice::compare(const FinitePowersetLattice::Element& left,
+                               const FinitePowersetLattice::Element& right) {
+  // Both must be from the powerset lattice of the same set.
+  assert(left.bitvector.size() == right.bitvector.size());
 
-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();
-}
+  // True in left, false in right.
+  bool leftNotRight = false;
 
-template<size_t N>
-inline bool
-BitsetPowersetLattice<N>::isBottom(const BitsetPowersetLattice<N>& element) {
-  // Bottom lattice element is the empty set.
-  return element.value.none();
-}
+  // True in right, false in left.
+  bool rightNotLeft = false;
 
-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;
+  size_t size = left.bitvector.size();
+
+  for (size_t i = 0; i < size; ++i) {
+    leftNotRight |= (left.bitvector[i] && !right.bitvector[i]);
+    rightNotLeft |= (right.bitvector[i] && !left.bitvector[i]);
+
+    // We can end early if we know neither is a subset of the other.
+    if (leftNotRight && rightNotLeft) {
+      return NO_RELATION;
     }
-    // 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;
+  }
+
+  if (!leftNotRight) {
+    if (!rightNotLeft) {
+      return EQUAL;
     }
-  } else if (left.value == right.value) {
-    return EQUAL;
+    return LESS;
+  } else if (!rightNotLeft) {
+    return GREATER;
   }
 
   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;
+inline FinitePowersetLattice::Element FinitePowersetLattice::getBottom() {
+  FinitePowersetLattice::Element result(setSize);
+  return result;
+}
+
+// We count the number of element members present in the element by counting the
+// trues in the bitvector.
+inline size_t FinitePowersetLattice::Element::count() {
+  size_t count = 0;
+  for (auto it : bitvector) {
+    count += it;
+  }
+  return count;
+}
+
+// Least upper bound is implemented as a logical OR between the bitvectors on
+// both sides. We return true if a bit is flipped in-place on the left so the
+// worklist algorithm will know if when to enqueue more work.
+inline bool FinitePowersetLattice::Element::makeLeastUpperBound(
+  const FinitePowersetLattice::Element& other) {
+  // Both must be from powerset lattice of the same set.
+  assert(other.bitvector.size() == bitvector.size());
+
+  bool modified = false;
+  for (size_t i = 0; i < bitvector.size(); ++i) {
+    // Bit is flipped on self only if self is false and other is true when self
+    // and other are OR'ed together.
+    modified |= (!bitvector[i] && other.bitvector[i]);
+    bitvector[i] = bitvector[i] || other.bitvector[i];
+  }
+
+  return modified;
 }
 
-template<size_t N>
-inline void BitsetPowersetLattice<N>::print(std::ostream& os) {
-  os << value;
+inline void FinitePowersetLattice::Element::print(std::ostream& os) {
+  // Element member 0 is on the left, element member N is on the right.
+  for (auto it : bitvector) {
+    os << it;
+  }
 }
 
 }; // namespace wasm::analysis
diff --git a/src/analysis/sign-lattice.cpp b/src/analysis/sign-lattice.cpp
index 9baa2f2fd..0d9379938 100644
--- a/src/analysis/sign-lattice.cpp
+++ b/src/analysis/sign-lattice.cpp
@@ -11,11 +11,9 @@ private:
   Sign value;
 
 public:
-  static bool isTop(const SignLattice& element) { return element.value == TOP; }
+  bool isTop() { return value == TOP; }
 
-  static bool isBottom(const SignLattice& element) {
-    return element.value == BOTTOM;
-  }
+  bool isBottom() { return value == BOTTOM; }
 
   static LatticeComparison compare(const SignLattice& left,
                                    const SignLattice& right) {
@@ -44,6 +42,4 @@ public:
   }
 };
 
-static_assert(is_lattice<SignLattice>);
-
 } // namespace wasm::analysis