Reaching Definitions Analysis for LocalGraph (#5817)

This change implements a reaching definitions analysis which is intended
to be equivalent to the information provided by LocalGraph, specifically
the Flower class of LocalGraph.

It also introduces a CRTP utility in visitor-transfer-function.h which
implements most commonly found visitor-type transfer function
functionalities. The MonotoneCFGAnalyzer is also modified to add a phase
to collect results after the analysis is solved from the final CFG
states.

1 files changed, 20 insertions, 0 deletions

diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h
index 471dc62f6..8599bccf2 100644
--- a/src/analysis/monotone-analyzer-impl.h
+++ b/src/analysis/monotone-analyzer-impl.h
@@ -44,6 +44,13 @@ inline MonotoneCFGAnalyzer<Lattice, TransferFunction>::MonotoneCFGAnalyzer(
 }
 
 template<typename Lattice, typename TransferFunction>
+inline void
+MonotoneCFGAnalyzer<Lattice, TransferFunction>::evaluateFunctionEntry(
+  Function* func) {
+  transferFunction.evaluateFunctionEntry(func, stateBlocks[0].inputState);
+}
+
+template<typename Lattice, typename TransferFunction>
 inline void MonotoneCFGAnalyzer<Lattice, TransferFunction>::evaluate() {
   std::queue<const BasicBlock*> worklist;
 
@@ -74,6 +81,19 @@ inline void MonotoneCFGAnalyzer<Lattice, TransferFunction>::evaluate() {
   }
 }
 
+template<typename Lattice, typename TransferFunction>
+inline void MonotoneCFGAnalyzer<Lattice, TransferFunction>::collectResults() {
+  for (BlockState currBlockState : stateBlocks) {
+    typename Lattice::Element inputStateCopy = currBlockState.inputState;
+
+    // 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.
+    transferFunction.collectResults(currBlockState.cfgBlock, inputStateCopy);
+  }
+}
+
 // Currently prints both the basic information and intermediate states of each
 // BlockState.
 template<typename Lattice, typename TransferFunction>