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;
 }