Make the Transfer Function a Generic, Interchangeable Type for the Monotone Analyzer (#5794)

This change makes the transfer function an object separate from the monotone analyzer. The transfer function class type is a generic template of the monotone analyzer, and an instance of the transfer function is instantiated and then passed into the monotone analyzer via its constructor. The API of the transfer function is enforced by a static assertion.

This change also introduces LivenessTransferFunction as a transfer function for liveness analysis as an example.

1 files changed, 40 insertions, 95 deletions

diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h
index a2e059e29..471dc62f6 100644
--- a/src/analysis/monotone-analyzer-impl.h
+++ b/src/analysis/monotone-analyzer-impl.h
@@ -13,132 +13,77 @@ namespace wasm::analysis {
 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<typename Lattice>
-inline void BlockState<Lattice>::visitLocalGet(LocalGet* curr) {
-  currState.set(curr->index, true);
-}
-
-template<typename Lattice> inline void BlockState<Lattice>::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::visit(*cfgIter);
-    ++cfgIter;
-  }
-  beginningState = std::move(currState);
-}
+  : cfgBlock(underlyingBlock), inputState(lattice.getBottom()) {}
 
+// Prints out inforamtion about a CFG node's state, but not intermediate states.
 template<typename Lattice>
 inline void BlockState<Lattice>::print(std::ostream& os) {
-  os << "State Block: " << index << std::endl;
-  os << "Beginning State: ";
-  beginningState.print(os);
-  os << std::endl << "End State: ";
-  endState.print(os);
+  os << "CFG Block: " << cfgBlock->getIndex() << std::endl;
+  os << "Input State: ";
+  inputState.print(os);
   os << std::endl << "Predecessors:";
-  for (auto pred : predecessors) {
-    os << " " << pred->cfgBlock->getIndex();
+  for (auto pred : cfgBlock->preds()) {
+    os << " " << pred.getIndex();
   }
   os << std::endl << "Successors:";
-  for (auto succ : successors) {
-    os << " " << succ->cfgBlock->getIndex();
+  for (auto succ : cfgBlock->succs()) {
+    os << " " << succ.getIndex();
   }
-  os << std::endl << "Intermediate States (reverse order): " << std::endl;
-
-  currState = endState;
-  currState.print(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()) {
-    os << ShallowExpression{*cfgIter} << std::endl;
-    BlockState::visit(*cfgIter);
-    currState.print(os);
-    os << std::endl;
-    ++cfgIter;
-  }
 }
 
-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++) {
-    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 < 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.predecessors.push_back(&stateBlocks[basicBlockToState[&pred]]);
-    }
+template<typename Lattice, typename TransferFunction>
+inline MonotoneCFGAnalyzer<Lattice, TransferFunction>::MonotoneCFGAnalyzer(
+  Lattice& lattice, TransferFunction& transferFunction, CFG& cfg)
+  : lattice(lattice), transferFunction(transferFunction), cfg(cfg) {
 
-    for (auto& succ : succs) {
-      currBlock.successors.push_back(&stateBlocks[basicBlockToState[&succ]]);
-    }
+  // Construct BlockStates for each BasicBlock.
+  for (auto it = cfg.begin(); it != cfg.end(); it++) {
+    stateBlocks.emplace_back(&(*it), lattice);
   }
 }
 
-template<typename Lattice>
-inline void MonotoneCFGAnalyzer<Lattice>::evaluate() {
-  std::queue<Index> worklist;
+template<typename Lattice, typename TransferFunction>
+inline void MonotoneCFGAnalyzer<Lattice, TransferFunction>::evaluate() {
+  std::queue<const BasicBlock*> worklist;
 
-  for (auto it = stateBlocks.rbegin(); it != stateBlocks.rend(); ++it) {
-    worklist.push(it->index);
-  }
+  // Transfer function enqueues the work in some order which is efficient.
+  transferFunction.enqueueWorklist(cfg, worklist);
 
   while (!worklist.empty()) {
-    BlockState<Lattice>& currBlockState = stateBlocks[worklist.front()];
+    BlockState<Lattice>& 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.
-    currBlockState.transfer();
-
-    // Propagate state to dependents
-    for (size_t j = 0; j < currBlockState.predecessors.size(); ++j) {
-      if (currBlockState.predecessors[j]->getLastState().makeLeastUpperBound(
-            currBlockState.getFirstState())) {
-        worklist.push(currBlockState.predecessors[j]->index);
+    typename Lattice::Element outputState = currBlockState.inputState;
+    transferFunction.transfer(currBlockState.cfgBlock, outputState);
+
+    // Propagate state to dependents of currBlockState.
+    for (auto& dep : transferFunction.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);
       }
     }
   }
 }
 
-template<typename Lattice>
-inline void MonotoneCFGAnalyzer<Lattice>::print(std::ostream& os) {
+// Currently prints both the basic information and intermediate states of each
+// BlockState.
+template<typename Lattice, typename TransferFunction>
+inline void
+MonotoneCFGAnalyzer<Lattice, TransferFunction>::print(std::ostream& os) {
   os << "CFG Analyzer" << std::endl;
   for (auto state : stateBlocks) {
     state.print(os);
+    typename Lattice::Element temp = state.inputState;
+    transferFunction.print(os, state.cfgBlock, temp);
   }
   os << "End" << std::endl;
 }