[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, 13 insertions, 36 deletions

diff --git a/src/analysis/visitor-transfer-function.h b/src/analysis/visitor-transfer-function.h
index 79acf00da..d77fc9fcd 100644
--- a/src/analysis/visitor-transfer-function.h
+++ b/src/analysis/visitor-transfer-function.h
@@ -5,6 +5,7 @@
 
 #include "cfg.h"
 #include "lattice.h"
+#include "support/unique_deferring_queue.h"
 #include "wasm-traversal.h"
 
 namespace wasm::analysis {
@@ -36,71 +37,47 @@ public:
   // Returns an iterable to all the BasicBlocks which depend on currBlock for
   // information.
   BasicBlock::BasicBlockIterable
-  getDependents(const BasicBlock* currBlock) noexcept {
+  getDependents(const BasicBlock& currBlock) noexcept {
     if constexpr (Direction == AnalysisDirection::Backward) {
-      return currBlock->preds();
+      return currBlock.preds();
     } else {
-      return currBlock->succs();
+      return currBlock.succs();
     }
   }
 
   // Executes the transfer function on all the expressions of the corresponding
   // CFG node, starting with the node's input state, and changes the input state
   // to the final output state of the node in place.
-  void transfer(const BasicBlock* cfgBlock,
+  void transfer(const BasicBlock& bb,
                 typename L::Element& inputState) noexcept {
     // If the block is empty, we propagate the state by inputState =
     // outputState.
 
     currState = &inputState;
     if constexpr (Direction == AnalysisDirection::Backward) {
-      for (auto cfgIter = cfgBlock->rbegin(); cfgIter != cfgBlock->rend();
-           ++cfgIter) {
+      for (auto cfgIter = bb.rbegin(); cfgIter != bb.rend(); ++cfgIter) {
         static_cast<SubType*>(this)->visit(*cfgIter);
       }
     } else {
-      for (auto cfgIter = cfgBlock->begin(); cfgIter != cfgBlock->end();
-           ++cfgIter) {
-        static_cast<SubType*>(this)->visit(*cfgIter);
+      for (auto* inst : bb) {
+        static_cast<SubType*>(this)->visit(inst);
       }
     }
     currState = nullptr;
   }
 
-  // Enqueues the worklist before the worklist algorithm is run. We want to
-  // evaluate the blocks in an order matching the "flow" of the analysis to
-  // reduce the number of state propagations needed. Thus, for a forward
-  // analysis, we push all the blocks in order, while for backward analysis, we
-  // push them in reverse order, so that later blocks are evaluated before
-  // earlier ones.
-  void enqueueWorklist(const CFG& cfg,
-                       std::queue<const BasicBlock*>& worklist) noexcept {
-    if constexpr (Direction == AnalysisDirection::Backward) {
-      for (auto it = cfg.rbegin(); it != cfg.rend(); ++it) {
-        worklist.push(&(*it));
-      }
-    } else {
-      for (auto it = cfg.begin(); it != cfg.end(); ++it) {
-        worklist.push(&(*it));
-      }
-    }
-  }
-
   // This is for collecting results after solving an analysis. Implemented in
   // the same way as transfer(), but we also set the collectingResults flag.
-  void collectResults(const BasicBlock* cfgBlock,
-                      typename L::Element& inputState) {
+  void collectResults(const BasicBlock& bb, typename L::Element& inputState) {
     collectingResults = true;
     currState = &inputState;
     if constexpr (Direction == AnalysisDirection::Backward) {
-      for (auto cfgIter = cfgBlock->rbegin(); cfgIter != cfgBlock->rend();
-           ++cfgIter) {
-        static_cast<SubType*>(this)->visit(*cfgIter);
+      for (auto it = bb.rbegin(); it != bb.rend(); ++it) {
+        static_cast<SubType*>(this)->visit(*it);
       }
     } else {
-      for (auto cfgIter = cfgBlock->begin(); cfgIter != cfgBlock->end();
-           ++cfgIter) {
-        static_cast<SubType*>(this)->visit(*cfgIter);
+      for (auto it = bb.begin(); it != bb.end(); ++it) {
+        static_cast<SubType*>(this)->visit(*it);
       }
     }
     currState = nullptr;