From 7de7078933292b0487f1f39f539bece922e3dde5 Mon Sep 17 00:00:00 2001
From: Benjamin Kramer <benny.kra@googlemail.com>
Date: Sun, 2 Sep 2012 11:57:22 +0000
Subject: [PATCH] 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
---
 lib/Transforms/Scalar/LoopRotation.cpp       | 53 +++++++++++-----------------
 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 f8122bf9803..abe07aa9d34 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 066b7e45d97..675d71f60da 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
+}
-- 
2.11.0