[analysis] Simplify core analysis code (#6034)

Simplify the monotone analyzer by replacing all the state it used to store in
`BlockState` with a simple vector of lattice elements. Use simple indices to
refer to both blocks and their associated states in the vector. Remove the
ability for transfer functions to control the initial enqueued order of basic
blocks since that was a leaky abstraction. Replace the worklist with a
UniqueDeferredQueue since that has generally proven to be more efficient in
smiilarly contexts, and more importantly, it has a nicer API. Make miscellaneous
simplifications to other code as well.

Delete a few unit tests that exposed the order in which blocks were analyzed
because they printed intermediate results. These tests should be replaced with
tests of analyses' public APIs in the future.

1 files changed, 40 insertions, 59 deletions

diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h
index f6b869493..e52ac5759 100644
--- a/src/analysis/monotone-analyzer-impl.h
+++ b/src/analysis/monotone-analyzer-impl.h
@@ -5,74 +5,48 @@
 #include <unordered_map>
 
 #include "monotone-analyzer.h"
+#include "support/unique_deferring_queue.h"
 
 namespace wasm::analysis {
 
-// All states are set to the bottom lattice element using the lattice in this
-// constructor.
-template<Lattice L>
-inline BlockState<L>::BlockState(const BasicBlock* underlyingBlock, L& lattice)
-  : cfgBlock(underlyingBlock), inputState(lattice.getBottom()) {}
-
-// Prints out inforamtion about a CFG node's state, but not intermediate states.
-template<Lattice L> inline void BlockState<L>::print(std::ostream& os) {
-  os << "CFG Block: " << cfgBlock->getIndex() << std::endl;
-  os << "Input State: ";
-  inputState.print(os);
-  os << std::endl << "Predecessors:";
-  for (auto pred : cfgBlock->preds()) {
-    os << " " << pred.getIndex();
-  }
-  os << std::endl << "Successors:";
-  for (auto succ : cfgBlock->succs()) {
-    os << " " << succ.getIndex();
-  }
-  os << std::endl;
-}
-
 template<Lattice L, TransferFunction TxFn>
 inline MonotoneCFGAnalyzer<L, TxFn>::MonotoneCFGAnalyzer(L& lattice,
                                                          TxFn& txfn,
                                                          CFG& cfg)
-  : lattice(lattice), txfn(txfn), cfg(cfg) {
-
-  // Construct BlockStates for each BasicBlock.
-  for (auto it = cfg.begin(); it != cfg.end(); it++) {
-    stateBlocks.emplace_back(&(*it), lattice);
-  }
-}
+  : lattice(lattice), txfn(txfn), cfg(cfg),
+    states(cfg.size(), lattice.getBottom()) {}
 
 template<Lattice L, TransferFunction TxFn>
 inline void
 MonotoneCFGAnalyzer<L, TxFn>::evaluateFunctionEntry(Function* func) {
-  txfn.evaluateFunctionEntry(func, stateBlocks[0].inputState);
+  txfn.evaluateFunctionEntry(func, states[0]);
 }
 
 template<Lattice L, TransferFunction TxFn>
 inline void MonotoneCFGAnalyzer<L, TxFn>::evaluate() {
-  std::queue<const BasicBlock*> worklist;
+  UniqueDeferredQueue<Index> worklist;
 
-  // Transfer function enqueues the work in some order which is efficient.
-  txfn.enqueueWorklist(cfg, worklist);
+  // Start with all blocks on the work list. TODO: optimize the iteration order
+  // using e.g. strongly-connected components.
+  for (Index i = 0; i < cfg.size(); ++i) {
+    worklist.push(i);
+  }
 
   while (!worklist.empty()) {
-    BlockState<L>& currBlockState = stateBlocks[worklist.front()->getIndex()];
-    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.
-    typename L::Element outputState = currBlockState.inputState;
-    txfn.transfer(currBlockState.cfgBlock, outputState);
-
-    // Propagate state to dependents of currBlockState.
-    for (auto& dep : txfn.getDependents(currBlockState.cfgBlock)) {
-      // If we need to change the input state of a dependent, we need
-      // to enqueue the dependent to recalculate it.
-      if (stateBlocks[dep.getIndex()].inputState.makeLeastUpperBound(
-            outputState)) {
-        worklist.push(&dep);
+    // The index of the block we will analyze.
+    Index i = worklist.pop();
+
+    // Apply the transfer function to the input state to compute the output
+    // state for the block.
+    auto state = states[i];
+    txfn.transfer(cfg[i], state);
+
+    // Propagate state to the dependent blocks.
+    for (auto& dep : txfn.getDependents(cfg[i])) {
+      // If the input state for the dependent block changes, we need to
+      // re-analyze it.
+      if (states[dep.getIndex()].makeLeastUpperBound(state)) {
+        worklist.push(dep.getIndex());
       }
     }
   }
@@ -80,14 +54,12 @@ inline void MonotoneCFGAnalyzer<L, TxFn>::evaluate() {
 
 template<Lattice L, TransferFunction TxFn>
 inline void MonotoneCFGAnalyzer<L, TxFn>::collectResults() {
-  for (BlockState currBlockState : stateBlocks) {
-    typename L::Element inputStateCopy = currBlockState.inputState;
-
+  for (Index i = 0, size = cfg.size(); i < size; ++i) {
     // The transfer function generates the final set of states and uses it to
     // produce useful information. For example, in reaching definitions
     // analysis, these final states are used to populate a mapping of
     // local.get's to a set of local.set's that affect its value.
-    txfn.collectResults(currBlockState.cfgBlock, inputStateCopy);
+    txfn.collectResults(cfg[i], states[i]);
   }
 }
 
@@ -96,12 +68,21 @@ inline void MonotoneCFGAnalyzer<L, TxFn>::collectResults() {
 template<Lattice L, TransferFunction TxFn>
 inline void MonotoneCFGAnalyzer<L, TxFn>::print(std::ostream& os) {
   os << "CFG Analyzer" << std::endl;
-  for (auto state : stateBlocks) {
-    state.print(os);
-    typename L::Element temp = state.inputState;
-    txfn.print(os, state.cfgBlock, temp);
+  for (Index i = 0, size = cfg.size(); i < size; ++i) {
+    os << "CFG Block: " << cfg[i].getIndex() << std::endl;
+    os << "Input State: ";
+    states[i].print(os);
+    for (auto& pred : cfg[i].preds()) {
+      os << " " << pred.getIndex();
+    }
+    os << std::endl << "Successors:";
+    for (auto& succ : cfg[i].succs()) {
+      os << " " << succ.getIndex();
+    }
+    os << "\n";
+    txfn.print(os, cfg[i], states[i]);
   }
-  os << "End" << std::endl;
+  os << "End\n";
 }
 
 } // namespace wasm::analysis