diff options
| author | Cameron Zwarich <zwarich@apple.com> | 2010-11-23 06:32:37 +0000 |
|---|---|---|
| committer | Cameron Zwarich <zwarich@apple.com> | 2010-11-23 06:32:37 +0000 |
| commit | 2974b6ffbcffcd7fb02958c7382edf45e4a30f14 (patch) | |
| tree | 04a5289edd5db7e43b613a7eb8e0dfec0747a38e | |
| parent | 9f9bd8e4af8c5e7ae02eb5de418a49a6fdafb3f1 (diff) | |
Optimize a common case in the Lengauer-Tarjan dominators algorithm. This gives a
9.7% speedup running domtree on test-suite.
Reviewed by Chris Lattner.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120003 91177308-0d34-0410-b5e6-96231b3b80d8
| -rw-r--r-- | include/llvm/Analysis/DominatorInternals.h | 11 |
1 files changed, 9 insertions, 2 deletions
diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h index 654289e630..54993e29cd 100644 --- a/include/llvm/Analysis/DominatorInternals.h +++ b/include/llvm/Analysis/DominatorInternals.h @@ -278,9 +278,16 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT, } } - DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W); - typename GraphT::NodeType* WParent = DT.Vertex[WInfo.Parent]; + + // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is + // necessarily parent(V). In this case, set idom(V) here and avoid placing + // V into a bucket. + if (WInfo.Semi == WInfo.Parent) + DT.IDoms[W] = WParent; + else + DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W); + Link<GraphT>(DT, WInfo.Parent, W, WInfo); // Step #3: Implicitly define the immediate dominator of vertices |