From fa75a7ca5c341dbb9752e7ec546d0a8a81942a11 Mon Sep 17 00:00:00 2001
From: Daniel Berlin <dberlin@dberlin.org>
Date: Sat, 1 Apr 2017 09:44:24 +0000
Subject: [PATCH] NewGVN: Use def_chain iterator in singleReachablePhiPath
 instead of recursion

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@299298 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Transforms/Utils/MemorySSA.h | 18 +++++++------
 lib/Transforms/Scalar/NewGVN.cpp          | 44 +++++++++++++++++--------------
 2 files changed, 34 insertions(+), 28 deletions(-)

diff --git a/include/llvm/Transforms/Utils/MemorySSA.h b/include/llvm/Transforms/Utils/MemorySSA.h
index 1b91796be89..25142cd8aa7 100644
--- a/include/llvm/Transforms/Utils/MemorySSA.h
+++ b/include/llvm/Transforms/Utils/MemorySSA.h
@@ -1064,13 +1064,14 @@ upward_defs(const MemoryAccessPair &Pair) {
 /// no defining use (e.g. a MemoryPhi or liveOnEntry). Note that, when comparing
 /// against a null def_chain_iterator, this will compare equal only after
 /// walking said Phi/liveOnEntry.
+template <class T>
 struct def_chain_iterator
-    : public iterator_facade_base<def_chain_iterator, std::forward_iterator_tag,
-                                  MemoryAccess *> {
+    : public iterator_facade_base<def_chain_iterator<T>,
+                                  std::forward_iterator_tag, MemoryAccess *> {
   def_chain_iterator() : MA(nullptr) {}
-  def_chain_iterator(MemoryAccess *MA) : MA(MA) {}
+  def_chain_iterator(T MA) : MA(MA) {}
 
-  MemoryAccess *operator*() const { return MA; }
+  T operator*() const { return MA; }
 
   def_chain_iterator &operator++() {
     // N.B. liveOnEntry has a null defining access.
@@ -1084,16 +1085,17 @@ struct def_chain_iterator
   bool operator==(const def_chain_iterator &O) const { return MA == O.MA; }
 
 private:
-  MemoryAccess *MA;
+  T MA;
 };
 
-inline iterator_range<def_chain_iterator>
-def_chain(MemoryAccess *MA, MemoryAccess *UpTo = nullptr) {
+template <class T>
+inline iterator_range<def_chain_iterator<T>>
+def_chain(T MA, MemoryAccess *UpTo = nullptr) {
 #ifdef EXPENSIVE_CHECKS
   assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator()) &&
          "UpTo isn't in the def chain!");
 #endif
-  return make_range(def_chain_iterator(MA), def_chain_iterator(UpTo));
+  return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
 }
 
 } // end namespace llvm
diff --git a/lib/Transforms/Scalar/NewGVN.cpp b/lib/Transforms/Scalar/NewGVN.cpp
index 9dbafec09df..34efa7860f1 100644
--- a/lib/Transforms/Scalar/NewGVN.cpp
+++ b/lib/Transforms/Scalar/NewGVN.cpp
@@ -1899,28 +1899,32 @@ bool NewGVN::singleReachablePHIPath(const MemoryAccess *First,
                                     const MemoryAccess *Second) const {
   if (First == Second)
     return true;
-
-  if (auto *FirstDef = dyn_cast<MemoryUseOrDef>(First)) {
-    auto *DefAccess = FirstDef->getDefiningAccess();
-    return singleReachablePHIPath(DefAccess, Second);
-  } else {
-    auto *MP = cast<MemoryPhi>(First);
-    auto ReachableOperandPred = [&](const Use &U) {
-      return ReachableEdges.count({MP->getIncomingBlock(U), MP->getBlock()});
-    };
-    auto FilteredPhiArgs =
-        make_filter_range(MP->operands(), ReachableOperandPred);
-    SmallVector<const Value *, 32> OperandList;
-    std::copy(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
-              std::back_inserter(OperandList));
-    bool Okay = OperandList.size() == 1;
-    if (!Okay)
-      Okay = std::equal(OperandList.begin(), OperandList.end(),
-                        OperandList.begin());
-    if (Okay)
-      return singleReachablePHIPath(cast<MemoryAccess>(OperandList[0]), Second);
+  if (MSSA->isLiveOnEntryDef(First))
     return false;
+  const auto *EndDef = First;
+  for (auto *ChainDef : def_chain(First)) {
+    if (ChainDef == Second)
+      return true;
+    if (MSSA->isLiveOnEntryDef(ChainDef))
+      return false;
+    EndDef = ChainDef;
   }
+  auto *MP = cast<MemoryPhi>(EndDef);
+  auto ReachableOperandPred = [&](const Use &U) {
+    return ReachableEdges.count({MP->getIncomingBlock(U), MP->getBlock()});
+  };
+  auto FilteredPhiArgs =
+      make_filter_range(MP->operands(), ReachableOperandPred);
+  SmallVector<const Value *, 32> OperandList;
+  std::copy(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
+            std::back_inserter(OperandList));
+  bool Okay = OperandList.size() == 1;
+  if (!Okay)
+    Okay =
+        std::equal(OperandList.begin(), OperandList.end(), OperandList.begin());
+  if (Okay)
+    return singleReachablePHIPath(cast<MemoryAccess>(OperandList[0]), Second);
+  return false;
 }
 
 // Verify the that the memory equivalence table makes sense relative to the
-- 
2.11.0