Changes in directory llvm/lib/VMCore:
Dominators.cpp updated: 1.100 -> 1.101 --- Log message: Use iterative while loop instead of recursive function call. --- Diffs of the changes: (+34 -14) Dominators.cpp | 48 ++++++++++++++++++++++++++++++++++-------------- 1 files changed, 34 insertions(+), 14 deletions(-) Index: llvm/lib/VMCore/Dominators.cpp diff -u llvm/lib/VMCore/Dominators.cpp:1.100 llvm/lib/VMCore/Dominators.cpp:1.101 --- llvm/lib/VMCore/Dominators.cpp:1.100 Wed May 2 20:11:54 2007 +++ llvm/lib/VMCore/Dominators.cpp Thu May 3 15:55:18 2007 @@ -124,20 +124,40 @@ return N; } -void DominatorTree::Compress(BasicBlock *V, InfoRec &VInfo) { - BasicBlock *VAncestor = VInfo.Ancestor; - InfoRec &VAInfo = Info[VAncestor]; - if (VAInfo.Ancestor == 0) - return; +void DominatorTree::Compress(BasicBlock *VIn) { - Compress(VAncestor, VAInfo); - - BasicBlock *VAncestorLabel = VAInfo.Label; - BasicBlock *VLabel = VInfo.Label; - if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) - VInfo.Label = VAncestorLabel; + std::vector<BasicBlock *> Work; + std::set<BasicBlock *> Visited; + InfoRec &VInInfo = Info[VIn]; + BasicBlock *VInAncestor = VInInfo.Ancestor; + InfoRec &VInVAInfo = Info[VInAncestor]; + + if (VInVAInfo.Ancestor != 0) + Work.push_back(VIn); + + while (!Work.empty()) { + BasicBlock *V = Work.back(); + InfoRec &VInfo = Info[V]; + BasicBlock *VAncestor = VInfo.Ancestor; + InfoRec &VAInfo = Info[VAncestor]; + + // Process Ancestor first + if (Visited.count(VAncestor) == 0 && VAInfo.Ancestor != 0) { + Work.push_back(VAncestor); + Visited.insert(VAncestor); + continue; + } + Work.pop_back(); - VInfo.Ancestor = VAInfo.Ancestor; + // Update VINfo based on Ancestor info + if (VAInfo.Ancestor == 0) + continue; + BasicBlock *VAncestorLabel = VAInfo.Label; + BasicBlock *VLabel = VInfo.Label; + if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) + VInfo.Label = VAncestorLabel; + VInfo.Ancestor = VAInfo.Ancestor; + } } BasicBlock *DominatorTree::Eval(BasicBlock *V) { @@ -146,13 +166,13 @@ // Higher-complexity but faster implementation if (VInfo.Ancestor == 0) return V; - Compress(V, VInfo); + Compress(V); return VInfo.Label; #else // Lower-complexity but slower implementation if (VInfo.Ancestor == 0) return VInfo.Label; - Compress(V, VInfo); + Compress(V); BasicBlock *VLabel = VInfo.Label; BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label; _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits