aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorChris Lattner <sabre@nondot.org>2004-03-13 22:01:26 +0000
committerChris Lattner <sabre@nondot.org>2004-03-13 22:01:26 +0000
commit786c5646e9cd15f18a6a7938673f74b02a05adb8 (patch)
treee0cef88637c919f34843bd4d1d6c9317e50a16cb /lib
parent2c7b430bc0831227f8c77478c1bda597f8f9fe29 (diff)
downloadexternal_llvm-786c5646e9cd15f18a6a7938673f74b02a05adb8.zip
external_llvm-786c5646e9cd15f18a6a7938673f74b02a05adb8.tar.gz
external_llvm-786c5646e9cd15f18a6a7938673f74b02a05adb8.tar.bz2
This little patch speeds up the loop used to update the dominator set analysis.
On the testcase from GCC PR12440, which has a LOT of loops (1392 of which require preheaders to be inserted), this speeds up the loopsimplify pass from 1.931s to 0.1875s. The loop in question goes from 1.65s -> 0.0097s, which isn't bad. All of these times are a debug build. This adds a dependency on DominatorTree analysis that was not there before, but we always had dominatortree available anyway, because LICM requires both loop simplify and DT, so this doesn't add any extra analysis in practice. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12362 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r--lib/Transforms/Utils/LoopSimplify.cpp35
1 files changed, 18 insertions, 17 deletions
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 00ee59d..08bbc09 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -56,6 +56,7 @@ namespace {
// We need loop information to identify the loops...
AU.addRequired<LoopInfo>();
AU.addRequired<DominatorSet>();
+ AU.addRequired<DominatorTree>();
AU.addPreserved<LoopInfo>();
AU.addPreserved<DominatorSet>();
@@ -279,6 +280,9 @@ void LoopSimplify::InsertPreheaderForLoop(Loop *L) {
ChangeExitBlock(*ParentLoops, Header, NewBB);
DominatorSet &DS = getAnalysis<DominatorSet>(); // Update dominator info
+ DominatorTree &DT = getAnalysis<DominatorTree>();
+ DominatorTree::Node *HeaderDTNode = DT.getNode(Header);
+
{
// The blocks that dominate NewBB are the blocks that dominate Header,
// minus Header, plus NewBB.
@@ -288,10 +292,20 @@ void LoopSimplify::InsertPreheaderForLoop(Loop *L) {
DS.addBasicBlock(NewBB, DomSet);
// The newly created basic block dominates all nodes dominated by Header.
- for (Function::iterator I = Header->getParent()->begin(),
- E = Header->getParent()->end(); I != E; ++I)
- if (DS.dominates(Header, I))
- DS.addDominator(I, NewBB);
+ for (DominatorTree::Node::iterator I = HeaderDTNode->begin(),
+ E = HeaderDTNode->end(); I != E; ++I)
+ DS.addDominator((*I)->getBlock(), NewBB);
+ }
+
+ { // Update the dominator tree information.
+ // The immediate dominator of the preheader is the immediate dominator of
+ // the old header.
+ //
+ DominatorTree::Node *PHNode =
+ DT.createNewNode(NewBB, HeaderDTNode->getIDom());
+
+ // Change the header node so that PNHode is the new immediate dominator
+ DT.changeImmediateDominator(HeaderDTNode, PHNode);
}
// Update immediate dominator information if we have it...
@@ -303,19 +317,6 @@ void LoopSimplify::InsertPreheaderForLoop(Loop *L) {
ID->setImmediateDominator(Header, NewBB);
}
- // Update DominatorTree information if it is active.
- if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
- // The immediate dominator of the preheader is the immediate dominator of
- // the old header.
- //
- DominatorTree::Node *HeaderNode = DT->getNode(Header);
- DominatorTree::Node *PHNode = DT->createNewNode(NewBB,
- HeaderNode->getIDom());
-
- // Change the header node so that PNHode is the new immediate dominator
- DT->changeImmediateDominator(HeaderNode, PHNode);
- }
-
// Update dominance frontier information...
if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) {
// The DF(NewBB) is just (DF(Header)-Header), because NewBB dominates