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

1 files changed, 21 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);
     }
   }