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>(