LoopRotation: Make the brute force DomTree update more brute force.
We update until we hit a fixpoint. This is probably slow but also
slightly simplifies the code. It should also fix the occasional
invalid domtrees observed when building with expensive checking.
I couldn't find a case where this had a measurable slowdown, but
if someone finds a pathological case where it does we may have
to find a cleverer way of updating dominators here.
Thanks to Duncan for the test case.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163091 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/Scalar/LoopRotation.cpp b/lib/Transforms/Scalar/LoopRotation.cpp
index f8122bf..abe07aa 100644
--- a/lib/Transforms/Scalar/LoopRotation.cpp
+++ b/lib/Transforms/Scalar/LoopRotation.cpp
@@ -453,41 +453,30 @@
// findNearestCommonDominator on all CFG predecessors of each child of the
// original header.
DomTreeNode *OrigHeaderNode = DT->getNode(OrigHeader);
- SmallVector<DomTreeNode *, 8> WorkList(OrigHeaderNode->begin(),
- OrigHeaderNode->end());
- while (!WorkList.empty()) {
- DomTreeNode *Node = WorkList.pop_back_val();
- BasicBlock *BB = Node->getBlock();
- BasicBlock *NearestDom = 0;
- for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
- ++PI) {
- BasicBlock *Pred = *PI;
+ SmallVector<DomTreeNode *, 8> HeaderChildren(OrigHeaderNode->begin(),
+ OrigHeaderNode->end());
+ bool Changed;
+ do {
+ Changed = false;
+ for (unsigned I = 0, E = HeaderChildren.size(); I != E; ++I) {
+ DomTreeNode *Node = HeaderChildren[I];
+ BasicBlock *BB = Node->getBlock();
- // We have to process predecessors of a node before we touch the
- // actual node. If one of the predecessors is in our worklist, put it
- // and the currently processed node on the worklist and go processing
- // the predecessor.
- SmallVectorImpl<DomTreeNode *>::iterator I =
- std::find(WorkList.begin(), WorkList.end(), DT->getNode(Pred));
- if (I != WorkList.end()) {
- WorkList.push_back(Node);
- std::swap(*I, WorkList.back());
- // The predecessor is now at the end of the worklist.
- NearestDom = 0;
- break;
+ pred_iterator PI = pred_begin(BB);
+ BasicBlock *NearestDom = *PI;
+ for (pred_iterator PE = pred_end(BB); PI != PE; ++PI)
+ NearestDom = DT->findNearestCommonDominator(NearestDom, *PI);
+
+ // Remember if this changes the DomTree.
+ if (Node->getIDom()->getBlock() != NearestDom) {
+ DT->changeImmediateDominator(BB, NearestDom);
+ Changed = true;
}
-
- // On the first iteration start with Pred, on the other iterations we
- // narrow it down to the nearest common dominator.
- if (!NearestDom)
- NearestDom = Pred;
- else
- NearestDom = DT->findNearestCommonDominator(NearestDom, Pred);
}
- if (NearestDom)
- DT->changeImmediateDominator(BB, NearestDom);
- }
+ // If the dominator changed, this may have an effect on other
+ // predecessors, continue until we reach a fixpoint.
+ } while (Changed);
}
}