diff options
author | Owen Anderson <resistor@mac.com> | 2007-09-27 23:23:00 +0000 |
---|---|---|
committer | Owen Anderson <resistor@mac.com> | 2007-09-27 23:23:00 +0000 |
commit | 58ec8825d46085841a1af55ee7f8117ad25ecf2f (patch) | |
tree | 45827034331e50d9428ab72317932bf532e95bb7 /lib | |
parent | 82482944edd810c7a1803d6694d435adf341e611 (diff) | |
download | external_llvm-58ec8825d46085841a1af55ee7f8117ad25ecf2f.zip external_llvm-58ec8825d46085841a1af55ee7f8117ad25ecf2f.tar.gz external_llvm-58ec8825d46085841a1af55ee7f8117ad25ecf2f.tar.bz2 |
Convert DFSPass into a templated friend function, in preparation for making it common to DomTree and PostDomTree.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42420 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/VMCore/DominatorCalculation.h | 5 | ||||
-rw-r--r-- | lib/VMCore/DominatorInternals.cpp | 4 | ||||
-rw-r--r-- | lib/VMCore/Dominators.cpp | 62 |
3 files changed, 5 insertions, 66 deletions
diff --git a/lib/VMCore/DominatorCalculation.h b/lib/VMCore/DominatorCalculation.h index 0ad4bc0..bf90a97 100644 --- a/lib/VMCore/DominatorCalculation.h +++ b/lib/VMCore/DominatorCalculation.h @@ -11,6 +11,7 @@ #define LLVM_VMCORE_DOMINATOR_CALCULATION_H #include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/DominatorInternals.h" //===----------------------------------------------------------------------===// // @@ -32,7 +33,7 @@ //===----------------------------------------------------------------------===// namespace llvm { - + void DTcalculate(DominatorTree& DT, Function &F) { BasicBlock* Root = DT.Roots[0]; @@ -43,7 +44,7 @@ void DTcalculate(DominatorTree& DT, Function &F) { // Step #1: Number blocks in depth-first order and initialize variables used // in later stages of the algorithm. - unsigned N = DT.DFSPass(Root, 0); + unsigned N = DFSPass<GraphTraits<BasicBlock*> >(DT, Root, 0); for (unsigned i = N; i >= 2; --i) { BasicBlock *W = DT.Vertex[i]; diff --git a/lib/VMCore/DominatorInternals.cpp b/lib/VMCore/DominatorInternals.cpp index b40e2d9..fbbac9f 100644 --- a/lib/VMCore/DominatorInternals.cpp +++ b/lib/VMCore/DominatorInternals.cpp @@ -7,8 +7,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H -#define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H +#ifndef LIB_LLVM_ANALYSIS_DOMINATOR_INTERNALS_H +#define LIB_LLVM_ANALYSIS_DOMINATOR_INTERNALS_H #include "llvm/Analysis/Dominators.h" #include "llvm/ADT/DenseMap.h" diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 0fc024b..a1eaf4a 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -53,68 +53,6 @@ char DominatorTree::ID = 0; static RegisterPass<DominatorTree> E("domtree", "Dominator Tree Construction", true); -unsigned DominatorTree::DFSPass(BasicBlock *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 = Info[Roots[i]]; - VInfo.Semi = ++N; - VInfo.Label = V; - - Vertex.push_back(V); // Vertex[n] = V; - //Info[V].Ancestor = 0; // Ancestor[n] = 0 - //Info[V].Child = 0; // Child[v] = 0 - VInfo.Size = 1; // Size[v] = 1 - - for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { - InfoRec &SuccVInfo = Info[*SI]; - if (SuccVInfo.Semi == 0) { - SuccVInfo.Parent = V; - N = DFSPass(*SI, N); - } - } -#else - std::vector<std::pair<BasicBlock*, unsigned> > Worklist; - Worklist.push_back(std::make_pair(V, 0U)); - while (!Worklist.empty()) { - BasicBlock *BB = Worklist.back().first; - unsigned NextSucc = Worklist.back().second; - - // First time we visited this BB? - if (NextSucc == 0) { - InfoRec &BBInfo = Info[BB]; - BBInfo.Semi = ++N; - BBInfo.Label = BB; - - Vertex.push_back(BB); // Vertex[n] = V; - //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0 - //BBInfo[V].Child = 0; // Child[v] = 0 - BBInfo.Size = 1; // Size[v] = 1 - } - - // If we are done with this block, remove it from the worklist. - if (NextSucc == BB->getTerminator()->getNumSuccessors()) { - Worklist.pop_back(); - continue; - } - - // Otherwise, 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. - BasicBlock *Succ = BB->getTerminator()->getSuccessor(NextSucc); - - InfoRec &SuccVInfo = Info[Succ]; - if (SuccVInfo.Semi == 0) { - SuccVInfo.Parent = BB; - Worklist.push_back(std::make_pair(Succ, 0U)); - } - } -#endif - return N; -} - // NewBB is split and now it has one successor. Update dominator tree to // reflect this change. void DominatorTree::splitBlock(BasicBlock *NewBB) { |