diff options
author | Chris Lattner <sabre@nondot.org> | 2007-04-09 06:44:42 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2007-04-09 06:44:42 +0000 |
commit | a9f120bd9f208f8e7ed03c02cc63b2f487edb84f (patch) | |
tree | 6f2e7e85b2e4f85dc4e755a7c7ea54aad478b8f5 /lib/VMCore/Dominators.cpp | |
parent | 5694b6e90eaf94fa7a21f101a8e4424d813a85ce (diff) | |
download | llvm-a9f120bd9f208f8e7ed03c02cc63b2f487edb84f.tar.gz llvm-a9f120bd9f208f8e7ed03c02cc63b2f487edb84f.tar.bz2 llvm-a9f120bd9f208f8e7ed03c02cc63b2f487edb84f.tar.xz |
Convert ImmediateDominators::DFSPass from being recursive to being iterative.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35815 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/VMCore/Dominators.cpp')
-rw-r--r-- | lib/VMCore/Dominators.cpp | 44 |
1 files changed, 43 insertions, 1 deletions
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 631b0e167e..707f133303 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -50,12 +50,16 @@ C("idom", "Immediate Dominators Construction", true); unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, 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 VInfo.Semi = ++N; VInfo.Label = V; Vertex.push_back(V); // Vertex[n] = V; //Info[V].Ancestor = 0; // Ancestor[n] = 0 - //Child[V] = 0; // Child[v] = 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) { @@ -65,6 +69,44 @@ unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, N = DFSPass(*SI, SuccVInfo, 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; } |