2 files changed, 43 insertions, 1 deletions
diff --git a/src/ir/LocalGraph.cpp b/src/ir/LocalGraph.cpp
index bf1f7e576..2fdf1e4a4 100644
--- a/src/ir/LocalGraph.cpp
+++ b/src/ir/LocalGraph.cpp
@@ -227,7 +227,7 @@ struct Flower : public CFGWalker<Flower, Visitor<Flower>, Info> {
 
 // LocalGraph implementation
 
-LocalGraph::LocalGraph(Function* func) {
+LocalGraph::LocalGraph(Function* func) : func(func) {
   LocalGraphInternal::Flower flower(getSetses, locations, func);
 
 #ifdef LOCAL_GRAPH_DEBUG
@@ -244,6 +244,43 @@ LocalGraph::LocalGraph(Function* func) {
 #endif
 }
 
+bool LocalGraph::equivalent(LocalGet* a, LocalGet* b) {
+  auto& aSets = getSetses[a];
+  auto& bSets = getSetses[b];
+  // The simple case of one set dominating two gets easily proves that they must
+  // have the same value. (Note that we can infer dominance from the fact that
+  // there is a single set: if the set did not dominate one of the gets then
+  // there would definitely be another set for that get, the zero initialization
+  // at the function entry, if nothing else.)
+  if (aSets.size() != 1 || bSets.size() != 1) {
+    // TODO: use a LinearExecutionWalker to find trivially equal gets in basic
+    //       blocks. that plus the above should handle 80% of cases.
+    // TODO: handle chains, merges and other situations
+    return false;
+  }
+  auto* aSet = *aSets.begin();
+  auto* bSet = *bSets.begin();
+  if (aSet != bSet) {
+    return false;
+  }
+  if (!aSet) {
+    // They are both nullptr, indicating the implicit value for a parameter
+    // or the zero for a local.
+    if (func->isParam(a->index)) {
+      // For parameters to be equivalent they must have the exact same
+      // index.
+      return a->index == b->index;
+    } else {
+      // As locals, they are both of value zero, but must have the right
+      // type as well.
+      return func->getLocalType(a->index) == func->getLocalType(b->index);
+    }
+  } else {
+    // They are both the same actual set.
+    return true;
+  }
+}
+
 void LocalGraph::computeInfluences() {
   for (auto& pair : locations) {
     auto* curr = pair.first;
diff --git a/src/ir/local-graph.h b/src/ir/local-graph.h
index 42a560c61..9e63bb3a8 100644
--- a/src/ir/local-graph.h
+++ b/src/ir/local-graph.h
@@ -48,6 +48,10 @@ struct LocalGraph {
                        // param)
   Locations locations; // where each get and set is (for easy replacing)
 
+  // Checks if two gets are equivalent, that is, definitely have the same
+  // value.
+  bool equivalent(LocalGet* a, LocalGet* b);
+
   // Optional: compute the influence graphs between sets and gets
   // (useful for algorithms that propagate changes).
 
@@ -84,6 +88,7 @@ struct LocalGraph {
   bool isSSA(Index x);
 
 private:
+  Function* func;
   std::set<Index> SSAIndexes;
 };