diff options
| -rw-r--r-- | include/llvm/Analysis/Dominators.h | 2 | ||||
| -rw-r--r-- | lib/VMCore/Dominators.cpp | 46 |
2 files changed, 34 insertions, 14 deletions
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index cca73bf..20c2c5f 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -225,7 +225,7 @@ private: void calculate(Function& F); Node *getNodeForBlock(BasicBlock *BB); unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N); - void Compress(BasicBlock *V, InfoRec &VInfo); + void Compress(BasicBlock *V); BasicBlock *Eval(BasicBlock *v); void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); inline BasicBlock *getIDom(BasicBlock *BB) const { diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 9f49b55..4c674c2 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -124,20 +124,40 @@ unsigned DominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo, 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); + std::vector<BasicBlock *> Work; + std::set<BasicBlock *> Visited; + InfoRec &VInInfo = Info[VIn]; + BasicBlock *VInAncestor = VInInfo.Ancestor; + InfoRec &VInVAInfo = Info[VInAncestor]; - BasicBlock *VAncestorLabel = VAInfo.Label; - BasicBlock *VLabel = VInfo.Label; - if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) - VInfo.Label = VAncestorLabel; + 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 @@ BasicBlock *DominatorTree::Eval(BasicBlock *V) { // 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; |