Changes in directory llvm/lib/VMCore:
Dominators.cpp updated: 1.91 -> 1.92
---
Log message:
Convert ImmediateDominators::DFSPass from being recursive to being iterative.
---
Diffs of the changes: (+43 -1)
Dominators.cpp | 44 +++++++++++++++++++++++++++++++++++++++++++-
1 files changed, 43 insertions(+), 1 deletion(-)
Index: llvm/lib/VMCore/Dominators.cpp
diff -u llvm/lib/VMCore/Dominators.cpp:1.91 llvm/lib/VMCore/Dominators.cpp:1.92
--- llvm/lib/VMCore/Dominators.cpp:1.91 Mon Apr 9 01:10:06 2007
+++ llvm/lib/VMCore/Dominators.cpp Mon Apr 9 01:44:42 2007
@@ -50,12 +50,16 @@
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 @@
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;
}
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
