9 files changed, 567 insertions, 67 deletions

diff --git a/src/analysis/cfg-impl.h b/src/analysis/cfg-impl.h
index cf348fa09..14fadd22c 100644
--- a/src/analysis/cfg-impl.h
+++ b/src/analysis/cfg-impl.h
@@ -118,21 +118,17 @@ template<typename T> struct _indirect_ptr_vec {
   iterator end() const { return {&vec.data()[vec.size()]}; }
 };
 
-struct BasicBlock::Predecessors : _indirect_ptr_vec<BasicBlock> {
-  Predecessors(const BasicBlock& block)
-    : _indirect_ptr_vec(block.predecessors) {}
+struct BasicBlock::BasicBlockIterable : _indirect_ptr_vec<BasicBlock> {
+  BasicBlockIterable(const std::vector<BasicBlock*>& blocks)
+    : _indirect_ptr_vec(blocks) {}
 };
 
-struct BasicBlock::Successors : _indirect_ptr_vec<BasicBlock> {
-  Successors(const BasicBlock& block) : _indirect_ptr_vec(block.successors) {}
-};
-
-inline BasicBlock::Predecessors BasicBlock::preds() const {
-  return Predecessors(*this);
+inline BasicBlock::BasicBlockIterable BasicBlock::preds() const {
+  return BasicBlockIterable(predecessors);
 }
 
-inline BasicBlock::Successors BasicBlock::succs() const {
-  return Successors(*this);
+inline BasicBlock::BasicBlockIterable BasicBlock::succs() const {
+  return BasicBlockIterable(successors);
 }
 
 } // namespace wasm::analysis
diff --git a/src/analysis/cfg.h b/src/analysis/cfg.h
index 650a8c6fe..a7f67c041 100644
--- a/src/analysis/cfg.h
+++ b/src/analysis/cfg.h
@@ -45,10 +45,9 @@ struct BasicBlock {
   reverse_iterator rend() const { return insts.rend(); }
 
   // Iterables for predecessor and successor blocks.
-  struct Predecessors;
-  struct Successors;
-  Predecessors preds() const;
-  Successors succs() const;
+  struct BasicBlockIterable;
+  BasicBlockIterable preds() const;
+  BasicBlockIterable succs() const;
 
   void print(std::ostream& os, Module* wasm = nullptr, size_t start = 0) const;
 
diff --git a/src/analysis/lattice.h b/src/analysis/lattice.h
index 6b468c2fc..5ab92a320 100644
--- a/src/analysis/lattice.h
+++ b/src/analysis/lattice.h
@@ -52,6 +52,9 @@ class FiniteIntPowersetLattice {
 public:
   FiniteIntPowersetLattice(size_t setSize) : setSize(setSize) {}
 
+  // Returns the size of the set that the powerset lattices was created from.
+  size_t getSetSize() { return setSize; }
+
   // This represents an element of a powerset lattice. The element is itself a
   // set which has set members. The bitvector tracks which possible members of
   // the element are actually present.
@@ -127,6 +130,12 @@ public:
     }
   }
 
+  // Iterator to access the list of element members.
+  using membersIterator = typename std::vector<T>::const_iterator;
+  membersIterator membersBegin() { return members.cbegin(); }
+  membersIterator membersEnd() { return members.cend(); }
+  size_t getSetSize() { return intLattice.getSetSize(); }
+
   T indexToMember(size_t index) { return members[index]; }
 
   size_t memberToIndex(T member) { return memberIndices[member]; }
diff --git a/src/analysis/liveness-transfer-function.h b/src/analysis/liveness-transfer-function.h
index b8dfb13b5..c6d564659 100644
--- a/src/analysis/liveness-transfer-function.h
+++ b/src/analysis/liveness-transfer-function.h
@@ -1,16 +1,14 @@
 #ifndef wasm_analysis_liveness_transfer_function_h
 #define wasm_analysis_liveness_transfer_function_h
 
-#include "lattice.h"
-#include "monotone-analyzer.h"
-#include "wasm-traversal.h"
+#include "visitor-transfer-function.h"
 
 namespace wasm::analysis {
 
-class LivenessTransferFunction : public Visitor<LivenessTransferFunction> {
-  FiniteIntPowersetLattice::Element* currState = nullptr;
-
-public:
+struct LivenessTransferFunction
+  : public VisitorTransferFunc<LivenessTransferFunction,
+                               FiniteIntPowersetLattice,
+                               AnalysisDirection::Backward> {
   // Transfer function implementation. A local becomes live before a get
   // and becomes dead before a set.
   void visitLocalSet(LocalSet* curr) {
@@ -22,43 +20,6 @@ public:
     currState->set(curr->index, true);
   }
 
-  // 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,
-                FiniteIntPowersetLattice::Element& inputState) {
-    // If the block is empty, we propagate the state by inputState =
-    // outputState.
-
-    currState = &inputState;
-
-    // This is a backward analysis, so we start from the end of the CFG
-    // and evaluate every expression until the beginning.
-    for (auto cfgIter = cfgBlock->rbegin(); cfgIter != cfgBlock->rend();
-         ++cfgIter) {
-      // Run transfer function.
-      visit(*cfgIter);
-    }
-    currState = nullptr;
-  }
-
-  // Enqueues the worklist before the worklist algorithm is run. For
-  // liveness analysis, we are doing a backward analysis, so we want
-  // to enqueue the worklist backward so that later CFG blocks are
-  // run before earlier CFG blocks. This improves performance by
-  // reducing the number of state propagations needed, since we are
-  // naturally following the backward flow at the beginning.
-  void enqueueWorklist(CFG& cfg, std::queue<const BasicBlock*>& worklist) {
-    for (auto it = cfg.rbegin(); it != cfg.rend(); ++it) {
-      worklist.push(&(*it));
-    }
-  }
-
-  // Predecessors depend on current basic block for information.
-  BasicBlock::Predecessors getDependents(const BasicBlock* currBlock) {
-    return currBlock->preds();
-  }
-
   // Prints the intermediate states of each basic block cfgBlock by applying
   // the transfer function on each expression of the CFG block. This data is
   // not stored. Requires the cfgBlock, and a temp copy of the input state
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>
diff --git a/src/analysis/monotone-analyzer.h b/src/analysis/monotone-analyzer.h
index aa49aaef9..2b0e0ae16 100644
--- a/src/analysis/monotone-analyzer.h
+++ b/src/analysis/monotone-analyzer.h
@@ -66,19 +66,18 @@ constexpr bool has_enqueueWorklist =
                       CFG&,
                       std::queue<const BasicBlock*>&>::value;
 
-// <iterable> getDependents(const BasicBlock* currBlock);
+// BasicBlock::BasicBlockIterable getDependents(const BasicBlock* currBlock);
 
 // Returns an iterable to the CFG BasicBlocks which depend on currBlock for
 // information (e.g. predecessors in a backward analysis). Used to select which
-// blocks to propagate to after applying the transfer function to a block. At
-// present, we allow this function to return any iterable, so we only assert
-// that the method exists with the following parameters.
+// blocks to propagate to after applying the transfer function to a block.
 
 template<typename TransferFunction>
 constexpr bool has_getDependents =
-  std::is_invocable<decltype(&TransferFunction::getDependents),
-                    TransferFunction,
-                    const BasicBlock*>::value;
+  std::is_invocable_r<BasicBlock::BasicBlockIterable,
+                      decltype(&TransferFunction::getDependents),
+                      TransferFunction,
+                      const BasicBlock*>::value;
 
 // Combined TransferFunction assertions.
 template<typename TransferFunction, typename Lattice>
@@ -103,9 +102,31 @@ public:
                       TransferFunction& transferFunction,
                       CFG& cfg);
 
-  // Runs the worklist algorithm to compute the states for the BlockList graph.
+  // Runs the worklist algorithm to compute the states for the BlockState graph.
   void evaluate();
 
+  // This modifies the state of the CFG's entry block, with function
+  // information. This cannot be done otherwise in a forward analysis, as the
+  // entry block depends on no other blocks, and hence cannot be changed by
+  // them.
+  void evaluateFunctionEntry(Function* func);
+
+  // Iterates over all of the BlockStates after evaluate() is completed for the
+  // transfer function to collect the finalized intermediate states from each
+  // block. For instance, the reaching definitions analysis transfer functions
+  // will take the final states and use it to populate a map of local.get's to
+  // sets of local.set's which affect it.
+  void collectResults();
+
+  // The analyzer is run in two distinct phases. First evaluate() runs the
+  // worklist algorithm to obtain a solution. Then collectResults() iterates
+  // over the vector of BlockState's, allowing the transfer function to access
+  // the final states to and turn them into some result.
+  void evaluateAndCollectResults() {
+    evaluate();
+    collectResults();
+  }
+
   // Prints out all BlockStates in this analyzer.
   void print(std::ostream& os);
 };
diff --git a/src/analysis/reaching-definitions-transfer-function.h b/src/analysis/reaching-definitions-transfer-function.h
new file mode 100644
index 000000000..8d29afd12
--- /dev/null
+++ b/src/analysis/reaching-definitions-transfer-function.h
@@ -0,0 +1,178 @@
+#ifndef wasm_analysis_reaching_definitions_transfer_function_h
+#define wasm_analysis_reaching_definitions_transfer_function_h
+
+#include "ir/find_all.h"
+#include "ir/local-graph.h"
+#include "visitor-transfer-function.h"
+
+namespace wasm::analysis {
+
+// A state contains all the "live" LocalSet instances at some particular
+// point in a program. The state tracks every LocalSet instance, not just
+// ones which influence a particular local index.
+
+// In addition to LocalSet expressions modifying a local index's value, we
+// must also account for the fact that the value of a local index could be
+// the default value at initialization or its value passed in as a parameter.
+// As a result, we use a fictitious LocalSet object held by the transfer
+// function to represent the local index obtaining its current value on
+// initialization or parameter passing.
+
+// Each local index gets an individual fictitious LocalSet, because the state
+// tracks all local indices, and setting one local index should not affect the
+// initial value of another.
+
+// When collecting results, the transfer function takes the states and converts
+// it into a map of LocalGets to LocalSets which affect it. The fictitious
+// inital value LocalSetes will be converted to nullptrs.
+
+class ReachingDefinitionsTransferFunction
+  : public VisitorTransferFunc<ReachingDefinitionsTransferFunction,
+                               FinitePowersetLattice<LocalSet*>,
+                               AnalysisDirection::Forward> {
+
+  // Number of locals in the function.
+  size_t numLocals;
+
+  // Maps a local index to a list of LocalSets that modify the index's value.
+  // The most common case is to have a single set; after that, to be a phi of 2
+  // items, so we use a small set of size 2 to avoid allocations there.
+  std::unordered_map<Index, SmallVector<LocalSet*, 2>> indexSetses;
+
+  // LocalGraph members we need to update.
+  LocalGraph::GetSetses& getSetses;
+
+  // Fictitious LocalSet objects to reprsent a local index obtaining its value
+  // from its default initial value or parameter value.
+  std::vector<LocalSet> fakeInitialValueSetses;
+
+  // Pointers to the fictitious LocalSet objects.
+  std::unordered_set<LocalSet*> fakeSetPtrs;
+
+  // Helper function which creates fictitious LocalSetses for a function,
+  // inserts them into fakeInitialValueSetses and fakeSetPtrs. It returns a
+  // vector of actual LocalSetses in the function and fictitious LocalSetses for
+  // use when instatitating the lattice.
+  static std::vector<LocalSet*>
+  listLocalSetses(Function* func,
+                  std::vector<LocalSet>& fakeInitialValueSetses,
+                  std::unordered_set<LocalSet*>& fakeSetPtrs) {
+    // Create a fictitious LocalSet for each local index.
+    for (Index i = 0; i < func->getNumLocals(); ++i) {
+      LocalSet currSet;
+      currSet.index = i;
+      fakeInitialValueSetses.push_back(currSet);
+    }
+
+    // Find all actual LocalSetses.
+    FindAll<LocalSet> setFinder(func->body);
+    std::vector<LocalSet*> setsesList = std::move(setFinder.list);
+
+    // Take a pointer for each fictitious LocalSet.
+    for (size_t i = 0; i < fakeInitialValueSetses.size(); ++i) {
+      setsesList.push_back(&fakeInitialValueSetses[i]);
+      fakeSetPtrs.insert(&fakeInitialValueSetses[i]);
+    }
+    return setsesList;
+  }
+
+public:
+  // Analysis lattice. Public, as the monotone analyzer may need it.
+  FinitePowersetLattice<LocalSet*> lattice;
+
+  // We actually don't update LocalGraph::Locations right now since the CFG we
+  // are working with doesn't contain the correct Expression**s, but this is
+  // left in for future improvements. TODO.
+  ReachingDefinitionsTransferFunction(Function* func,
+                                      LocalGraph::GetSetses& getSetses,
+                                      LocalGraph::Locations& locations)
+    : numLocals(func->getNumLocals()), getSetses(getSetses),
+      lattice(listLocalSetses(func, fakeInitialValueSetses, fakeSetPtrs)) {
+
+    // Map every local index to a set of all the local sets which affect it.
+    for (auto it = lattice.membersBegin(); it != lattice.membersEnd(); ++it) {
+      indexSetses[(*it)->index].push_back(*it);
+    }
+  }
+
+  void visitLocalSet(LocalSet* curr) {
+    assert(currState);
+
+    // This is only needed to derive states when solving the analysis, and
+    // not for collecting results from the final states.
+
+    // For a LocalSet, we remove all previous setses modifying its index and
+    // adds itself.
+    auto& currSetses = indexSetses[curr->index];
+    for (auto setInstance : currSetses) {
+      lattice.remove(currState, setInstance);
+    }
+
+    lattice.add(currState, curr);
+  }
+
+  // Only for collecting results. For curr, collects all of the sets to curr's
+  // index which are present in the state (i.e. those that set index's current
+  // value).
+  void visitLocalGet(LocalGet* curr) {
+    assert(currState);
+
+    // This is only to be run in the second phase where we iterate over the
+    // final (i.e. solved) states. Thus, only done when collectingResults is
+    // true.
+    if (collectingResults) {
+      auto& matchingSetses = indexSetses[curr->index];
+
+      for (auto setInstance : matchingSetses) {
+        if (lattice.exists(currState, setInstance)) {
+          // If a pointer to a real LocalSet, add it, otherwise add a nullptr.
+          if (fakeSetPtrs.find(setInstance) == fakeSetPtrs.end()) {
+            getSetses[curr].insert(setInstance);
+          } else {
+            getSetses[curr].insert(nullptr);
+          }
+        }
+      }
+    }
+  }
+
+  // At the entry point of the function, we must set the state to signify that
+  // the values in each local index are from either a parameter value or their
+  // default initialized value. This cannot be done normally, because the
+  // initial state of the entry block is initialized as the bottom element, but
+  // no one can modify it because this block doesn't depend on any other. Hence
+  // the need for this function.
+  void
+  evaluateFunctionEntry(Function* func,
+                        FinitePowersetLattice<LocalSet*>::Element& inputState) {
+    for (auto currSet : fakeSetPtrs) {
+      lattice.add(&inputState, currSet);
+    }
+  }
+
+  void print(std::ostream& os,
+             const BasicBlock* cfgBlock,
+             FinitePowersetLattice<LocalSet*>::Element& inputState) {
+    os << "Intermediate States: " << std::endl;
+    currState = &inputState;
+    currState->print(os);
+    os << std::endl;
+    auto cfgIter = cfgBlock->begin();
+
+    // Since we don't store the intermediate states, we need to re-run the
+    // transfer function on all the CFG node expressions to reconstruct
+    // the intermediate states here.
+    while (cfgIter != cfgBlock->end()) {
+      os << ShallowExpression{*cfgIter} << std::endl;
+      visit(*cfgIter);
+      currState->print(os);
+      os << std::endl;
+      ++cfgIter;
+    }
+    currState = nullptr;
+  }
+};
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_reaching_definitions_transfer_function_h
diff --git a/src/analysis/visitor-transfer-function.h b/src/analysis/visitor-transfer-function.h
new file mode 100644
index 000000000..18ee35392
--- /dev/null
+++ b/src/analysis/visitor-transfer-function.h
@@ -0,0 +1,111 @@
+#ifndef wasm_analysis_visitor_transfer_function_h
+#define wasm_analysis_visitor_transfer_function_h
+
+#include <queue>
+
+#include "cfg.h"
+#include "lattice.h"
+#include "wasm-traversal.h"
+
+namespace wasm::analysis {
+
+enum class AnalysisDirection { Forward, Backward };
+
+// Utility for visitor-based transfer functions for forward and backward
+// analysis. Forward analysis is chosen by default unless the template parameter
+// Backward is true.
+template<typename SubType, typename Lattice, AnalysisDirection Direction>
+struct VisitorTransferFunc : public Visitor<SubType> {
+protected:
+  typename Lattice::Element* currState = nullptr;
+
+  // There are two distinct phases in the execution of the analyzer. First,
+  // the worklist algorithm will be run to obtain a solution, calling
+  // transfer() for each block. Then, to collect the final states, the analyzer
+  // will iterate over every block, calling collectResults().
+
+  // As there is only one set of visitor functions, they are used both to
+  // mutate intermediate states as the transfer function, and also to
+  // collect results from the final states. Therefore, we have the variable
+  // collectingResults to signal whether we are collecting results from the
+  // solved analysis, as opposed to solving the analysis to the visitor
+  // functions.
+  bool collectingResults = false;
+
+public:
+  // Returns an iterable to all the BasicBlocks which depend on currBlock for
+  // information.
+  BasicBlock::BasicBlockIterable getDependents(const BasicBlock* currBlock) {
+    if constexpr (Direction == AnalysisDirection::Backward) {
+      return currBlock->preds();
+    } else {
+      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,
+                typename Lattice::Element& inputState) {
+    // 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) {
+        static_cast<SubType*>(this)->visit(*cfgIter);
+      }
+    } else {
+      for (auto cfgIter = cfgBlock->begin(); cfgIter != cfgBlock->end();
+           ++cfgIter) {
+        static_cast<SubType*>(this)->visit(*cfgIter);
+      }
+    }
+    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(CFG& cfg, std::queue<const BasicBlock*>& worklist) {
+    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 Lattice::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);
+      }
+    } else {
+      for (auto cfgIter = cfgBlock->begin(); cfgIter != cfgBlock->end();
+           ++cfgIter) {
+        static_cast<SubType*>(this)->visit(*cfgIter);
+      }
+    }
+    currState = nullptr;
+    collectingResults = false;
+  }
+};
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_visitor_transfer_function_h
diff --git a/test/gtest/cfg.cpp b/test/gtest/cfg.cpp
index c18d81499..3ee63b9b0 100644
--- a/test/gtest/cfg.cpp
+++ b/test/gtest/cfg.cpp
@@ -4,6 +4,8 @@
 #include "analysis/lattice.h"
 #include "analysis/liveness-transfer-function.h"
 #include "analysis/monotone-analyzer.h"
+#include "analysis/reaching-definitions-transfer-function.h"
+#include "ir/find_all.h"
 #include "print-test.h"
 #include "wasm.h"
 #include "gtest/gtest.h"
@@ -290,3 +292,206 @@ TEST_F(CFGTest, FinitePowersetLatticeFunctioning) {
   element2.print(ss);
   EXPECT_EQ(ss.str(), "101101");
 }
+
+TEST_F(CFGTest, LinearReachingDefinitions) {
+  auto moduleText = R"wasm(
+    (module
+      (func $bar
+        (local $a (i32))
+        (local $b (i32))
+        (local $c (i32))
+        (local.set $a
+          (i32.const 1)
+        )
+        (drop
+          (local.get $a)
+        )
+        (local.set $b
+          (local.get $a)
+        )
+        (drop
+          (local.get $c)
+        )
+        (local.set $c
+          (i32.const 1)
+        )
+        (local.set $a
+          (i32.const 2)
+        )
+      )
+    )
+  )wasm";
+
+  Module wasm;
+  parseWast(wasm, moduleText);
+
+  Function* func = wasm.getFunction("bar");
+  CFG cfg = CFG::fromFunction(func);
+
+  LocalGraph::GetSetses getSetses;
+  LocalGraph::Locations locations;
+  ReachingDefinitionsTransferFunction transferFunction(
+    func, getSetses, locations);
+
+  MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>,
+                      ReachingDefinitionsTransferFunction>
+    analyzer(transferFunction.lattice, transferFunction, cfg);
+
+  // TODO: Make evaluating function entry point more automatic (i.e. part of
+  // existing evaluate call).
+  analyzer.evaluateFunctionEntry(func);
+  analyzer.evaluateAndCollectResults();
+
+  FindAll<LocalSet> foundSets(func->body);
+  FindAll<LocalGet> foundGets(func->body);
+
+  LocalGet* getA1 = foundGets.list[0];
+  LocalGet* getA2 = foundGets.list[1];
+  LocalGet* getC = foundGets.list[2];
+  LocalSet* setA1 = foundSets.list[0];
+
+  LocalGraph::GetSetses expectedResult;
+  expectedResult[getA1].insert(setA1);
+  expectedResult[getA2].insert(setA1);
+  expectedResult[getC].insert(nullptr);
+
+  EXPECT_EQ(expectedResult, getSetses);
+}
+
+TEST_F(CFGTest, ReachingDefinitionsIf) {
+  auto moduleText = R"wasm(
+    (module
+      (func $bar
+        (local $a (i32))
+        (local $b (i32))
+        (local.set $a
+          (i32.const 1)
+        )
+        (if
+          (i32.eq
+            (local.get $a)
+            (i32.const 2)
+          )
+          (local.set $b
+            (i32.const 3)
+          )
+          (local.set $a
+            (i32.const 4)
+          )
+        )
+        (drop
+          (local.get $b)
+        )
+        (drop
+          (local.get $a)
+        )
+      )
+    )
+  )wasm";
+
+  Module wasm;
+  parseWast(wasm, moduleText);
+
+  Function* func = wasm.getFunction("bar");
+  CFG cfg = CFG::fromFunction(func);
+
+  LocalGraph::GetSetses getSetses;
+  LocalGraph::Locations locations;
+  ReachingDefinitionsTransferFunction transferFunction(
+    func, getSetses, locations);
+
+  MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>,
+                      ReachingDefinitionsTransferFunction>
+    analyzer(transferFunction.lattice, transferFunction, cfg);
+  analyzer.evaluateFunctionEntry(func);
+  analyzer.evaluateAndCollectResults();
+
+  FindAll<LocalSet> foundSets(func->body);
+  FindAll<LocalGet> foundGets(func->body);
+
+  LocalGet* getA1 = foundGets.list[0];
+  LocalGet* getB = foundGets.list[1];
+  LocalGet* getA2 = foundGets.list[2];
+  LocalSet* setA1 = foundSets.list[0];
+  LocalSet* setB = foundSets.list[1];
+  LocalSet* setA2 = foundSets.list[2];
+
+  LocalGraph::GetSetses expectedResult;
+  expectedResult[getA1].insert(setA1);
+  expectedResult[getB].insert(nullptr);
+  expectedResult[getB].insert(setB);
+  expectedResult[getA2].insert(setA1);
+  expectedResult[getA2].insert(setA2);
+
+  EXPECT_EQ(expectedResult, getSetses);
+}
+
+TEST_F(CFGTest, ReachingDefinitionsLoop) {
+  auto moduleText = R"wasm(
+    (module
+      (func $bar (param $a (i32)) (param $b (i32))
+        (loop $loop
+          (drop
+            (local.get $a)
+          )
+          (local.set $a
+             (i32.add
+               (i32.const 1)
+               (local.get $a)
+             )
+          )
+          (br_if $loop
+            (i32.le_u
+              (local.get $a)
+              (i32.const 7)
+            )
+          )
+        )
+        (local.set $b
+          (i32.sub
+            (local.get $b)
+            (local.get $a)
+          )
+        )
+      )
+    )
+  )wasm";
+
+  Module wasm;
+  parseWast(wasm, moduleText);
+
+  Function* func = wasm.getFunction("bar");
+  CFG cfg = CFG::fromFunction(func);
+
+  LocalGraph::GetSetses getSetses;
+  LocalGraph::Locations locations;
+  ReachingDefinitionsTransferFunction transferFunction(
+    func, getSetses, locations);
+
+  MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>,
+                      ReachingDefinitionsTransferFunction>
+    analyzer(transferFunction.lattice, transferFunction, cfg);
+  analyzer.evaluateFunctionEntry(func);
+  analyzer.evaluateAndCollectResults();
+
+  FindAll<LocalSet> foundSets(func->body);
+  FindAll<LocalGet> foundGets(func->body);
+
+  LocalGet* getA1 = foundGets.list[0];
+  LocalGet* getA2 = foundGets.list[1];
+  LocalGet* getA3 = foundGets.list[2];
+  LocalGet* getB = foundGets.list[3];
+  LocalGet* getA4 = foundGets.list[4];
+  LocalSet* setA = foundSets.list[0];
+
+  LocalGraph::GetSetses expectedResult;
+  expectedResult[getA1].insert(nullptr);
+  expectedResult[getA1].insert(setA);
+  expectedResult[getA2].insert(nullptr);
+  expectedResult[getA2].insert(setA);
+  expectedResult[getA3].insert(setA);
+  expectedResult[getB].insert(nullptr);
+  expectedResult[getA4].insert(setA);
+
+  EXPECT_EQ(expectedResult, getSetses);
+}