diff options
author | Benjamin Kramer <benny.kra@googlemail.com> | 2012-09-02 11:57:22 +0000 |
---|---|---|
committer | Benjamin Kramer <benny.kra@googlemail.com> | 2012-09-02 11:57:22 +0000 |
commit | 7de7078933292b0487f1f39f539bece922e3dde5 (patch) | |
tree | cb8374fa628d864571eef888bac2ef34d768a6b0 | |
parent | 43bf70986bb13c812e87ca959dd8f2dd9edf802c (diff) | |
download | llvm-7de7078933292b0487f1f39f539bece922e3dde5.tar.gz llvm-7de7078933292b0487f1f39f539bece922e3dde5.tar.bz2 llvm-7de7078933292b0487f1f39f539bece922e3dde5.tar.xz |
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
-rw-r--r-- | lib/Transforms/Scalar/LoopRotation.cpp | 53 | ||||
-rw-r--r-- | test/Transforms/LoopRotate/multiple-exits.ll | 36 |
2 files changed, 57 insertions, 32 deletions
diff --git a/lib/Transforms/Scalar/LoopRotation.cpp b/lib/Transforms/Scalar/LoopRotation.cpp index f8122bf980..abe07aa9d3 100644 --- a/lib/Transforms/Scalar/LoopRotation.cpp +++ b/lib/Transforms/Scalar/LoopRotation.cpp @@ -453,41 +453,30 @@ bool LoopRotate::rotateLoop(Loop *L) { // 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; - - // 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; + 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(); + + 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); } } diff --git a/test/Transforms/LoopRotate/multiple-exits.ll b/test/Transforms/LoopRotate/multiple-exits.ll index 066b7e45d9..675d71f60d 100644 --- a/test/Transforms/LoopRotate/multiple-exits.ll +++ b/test/Transforms/LoopRotate/multiple-exits.ll @@ -198,3 +198,39 @@ declare i32 @llvm.eh.typeid.for(i8*) nounwind readnone declare i8* @__cxa_begin_catch(i8*) declare void @__cxa_end_catch() + +define void @test4() nounwind uwtable { +entry: + br label %"7" + +"3": ; preds = %"7" + br i1 undef, label %"31", label %"4" + +"4": ; preds = %"3" + %. = select i1 undef, float 0x3F50624DE0000000, float undef + %0 = add i32 %1, 1 + br label %"7" + +"7": ; preds = %"4", %entry + %1 = phi i32 [ %0, %"4" ], [ 0, %entry ] + %2 = icmp slt i32 %1, 100 + br i1 %2, label %"3", label %"8" + +"8": ; preds = %"7" + br i1 undef, label %"9", label %"31" + +"9": ; preds = %"8" + br label %"33" + +"27": ; preds = %"31" + unreachable + +"31": ; preds = %"8", %"3" + br i1 undef, label %"27", label %"32" + +"32": ; preds = %"31" + br label %"33" + +"33": ; preds = %"32", %"9" + ret void +} |