Index: include/llvm/Support/GenericDomTree.h
===================================================================
--- include/llvm/Support/GenericDomTree.h
+++ include/llvm/Support/GenericDomTree.h
@@ -653,6 +653,10 @@
        unsigned LastLinked);
 
   template <class GraphT>
+  friend unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+                                 typename GraphT::NodeRef V, unsigned N);
+
+  template <class GraphT>
   friend unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
                           typename GraphT::NodeRef V, unsigned N);
 
Index: include/llvm/Support/GenericDomTreeConstruction.h
===================================================================
--- include/llvm/Support/GenericDomTreeConstruction.h
+++ include/llvm/Support/GenericDomTreeConstruction.h
@@ -24,82 +24,47 @@
 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/GenericDomTree.h"
 
 namespace llvm {
 
 template <class GraphT>
-unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                 typename GraphT::NodeRef V, unsigned N) {
-  // This is more understandable as a recursive algorithm, but we can't use the
-  // recursive algorithm due to stack depth issues.  Keep it here for
-  // documentation purposes.
-#if 0
-  InfoRec &VInfo = DT.Info[DT.Roots[i]];
-  VInfo.DFSNum = VInfo.Semi = ++N;
-  VInfo.Label = V;
-
-  Vertex.push_back(V);        // Vertex[n] = V;
-
-  for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
-    InfoRec &SuccVInfo = DT.Info[*SI];
-    if (SuccVInfo.Semi == 0) {
-      SuccVInfo.Parent = V;
-      N = DTDFSPass(DT, *SI, N);
-    }
-  }
-#else
+unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+                        typename GraphT::NodeRef V, unsigned N) {
   bool IsChildOfArtificialExit = (N != 0);
-
-  SmallVector<
-      std::pair<typename GraphT::NodeRef, typename GraphT::ChildIteratorType>,
-      32>
-      Worklist;
-  Worklist.push_back(std::make_pair(V, GraphT::child_begin(V)));
-  while (!Worklist.empty()) {
-    typename GraphT::NodeRef BB = Worklist.back().first;
-    typename GraphT::ChildIteratorType NextSucc = Worklist.back().second;
-
+  for (auto I = idf_begin(V), E = idf_end(V); I != E; ++I) {
+    typename GraphT::NodeRef BB = *I;
     auto &BBInfo = DT.Info[BB];
+    BBInfo.DFSNum = BBInfo.Semi = ++N;
+    BBInfo.Label = BB;
+    // Set the parent to the top of the visited stack
+    if (I.getPathLength() > 1)
+      BBInfo.Parent = DT.Info[I.getPath(I.getPathLength() - 2)].DFSNum;
+    DT.Vertex.push_back(BB); // Vertex[n] = V;
 
-    // First time we visited this BB?
-    if (NextSucc == GraphT::child_begin(BB)) {
-      BBInfo.DFSNum = BBInfo.Semi = ++N;
-      BBInfo.Label = BB;
-
-      DT.Vertex.push_back(BB);       // Vertex[n] = V;
-
-      if (IsChildOfArtificialExit)
-        BBInfo.Parent = 1;
-
-      IsChildOfArtificialExit = false;
-    }
-
-    // store the DFS number of the current BB - the reference to BBInfo might
-    // get invalidated when processing the successors.
-    unsigned BBDFSNum = BBInfo.DFSNum;
-
-    // If we are done with this block, remove it from the worklist.
-    if (NextSucc == GraphT::child_end(BB)) {
-      Worklist.pop_back();
-      continue;
-    }
-
-    // Increment the successor number for the next time we get to it.
-    ++Worklist.back().second;
-
-    // Visit the successor next, if it isn't already visited.
-    typename GraphT::NodeRef Succ = *NextSucc;
+    if (IsChildOfArtificialExit)
+      BBInfo.Parent = 1;
 
-    auto &SuccVInfo = DT.Info[Succ];
-    if (SuccVInfo.Semi == 0) {
-      SuccVInfo.Parent = BBDFSNum;
-      Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ)));
-    }
+    IsChildOfArtificialExit = false;
   }
-#endif
-    return N;
+  return N;
+}
+template <class GraphT>
+unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+                 typename GraphT::NodeRef V, unsigned N) {
+  for (auto I = df_begin(V), E = df_end(V); I != E; ++I) {
+    typename GraphT::NodeRef BB = *I;
+    auto &BBInfo = DT.Info[BB];
+    BBInfo.DFSNum = BBInfo.Semi = ++N;
+    BBInfo.Label = BB;
+    // Set the parent to the top of the visited stack
+    if (I.getPathLength() > 1)
+      BBInfo.Parent = DT.Info[I.getPath(I.getPathLength() - 2)].DFSNum;
+    DT.Vertex.push_back(BB); // Vertex[n] = V;
+  }
+  return N;
 }
 
 template <class GraphT>
@@ -163,9 +128,13 @@
 
   // Step #1: Number blocks in depth-first order and initialize variables used
   // in later stages of the algorithm.
-  for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
-       i != e; ++i)
-    N = DFSPass<GraphT>(DT, DT.Roots[i], N);
+  if (DT.isPostDominator()){
+    for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
+         i != e; ++i)
+      N = ReverseDFSPass<GraphT>(DT, DT.Roots[i], N);
+  } else {
+    N = DFSPass<GraphT>(DT, DT.Roots[0], N);
+  }
 
   // it might be that some blocks did not get a DFS number (e.g., blocks of
   // infinite loops). In these cases an artificial exit node is required.
Index: unittests/Transforms/Utils/MemorySSA.cpp
===================================================================
--- unittests/Transforms/Utils/MemorySSA.cpp
+++ unittests/Transforms/Utils/MemorySSA.cpp
@@ -65,10 +65,10 @@
       : M("MemorySSATest", C), B(C), DL(DLString), TLI(TLII), F(nullptr) {}
 };
 
-TEST_F(MemorySSATest, CreateALoadAndPhi) {
+TEST_F(MemorySSATest, CreateALoad) {
   // We create a diamond where there is a store on one side, and then after
   // building MemorySSA, create a load after the merge point, and use it to test
-  // updating by creating an access for the load and a memoryphi.
+  // updating by creating an access for the load.
   F = Function::Create(
       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
       GlobalValue::ExternalLinkage, "F", &M);
@@ -80,7 +80,7 @@
   B.CreateCondBr(B.getTrue(), Left, Right);
   B.SetInsertPoint(Left);
   Argument *PointerArg = &*F->arg_begin();
-  StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg);
+  B.CreateStore(B.getInt8(16), PointerArg);
   BranchInst::Create(Merge, Left);
   BranchInst::Create(Merge, Right);
 
@@ -89,14 +89,10 @@
   // Add the load
   B.SetInsertPoint(Merge);
   LoadInst *LoadInst = B.CreateLoad(PointerArg);
-  // Should be no phi to start
-  EXPECT_EQ(MSSA.getMemoryAccess(Merge), nullptr);
 
-  // Create the phi
-  MemoryPhi *MP = MSSA.createMemoryPhi(Merge);
-  MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));
-  MP->addIncoming(StoreAccess, Left);
-  MP->addIncoming(MSSA.getLiveOnEntryDef(), Right);
+  // MemoryPHI should already exist.
+  MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
+  EXPECT_NE(MP, nullptr);
 
   // Create the load memory acccess
   MemoryUse *LoadAccess = cast<MemoryUse>(