[LoopRotate] Fix DomTree update logic for unreachable nodes. Fix PR33701.

[kuhar]

Summary

LoopRotate manually updates the DoomTree by iterating over all predecessors of a basic block and computing the Nearest Common Dominator.

When a predecessor happens to be unreachable, DT.findNearestCommonDominator returns nullptr.

This patch teaches LoopRotate to handle this case and fixes PR33701.

In the future, LoopRotate should be taught to use the new incremental API for updating the DomTree.

[efriedma]

lib/Transforms/Scalar/LoopRotation.cpp

492 ↗

(On Diff #105481)

What if *PI isn't reachable?

[davide]

lib/Transforms/Scalar/LoopRotation.cpp

492 ↗

(On Diff #105481)

How hard is to craft a test where *PI is not reachable as well?

[kuhar]

lib/Transforms/Scalar/LoopRotation.cpp

492 ↗

(On Diff #105481)

I haven't been able to figure that out, but the code doesn't rely on the order now. There's also an assert for a situation when all predecessors are unreachable (which I don't think is possible) that should catch situations like that.

[• dberlin]

I think this is fine for now (the test case actually tests the patch), especially if we are going to move it to use the incremental updater.
It tends to be hard to formulate certain types of testcases right now due to the preconditions of loop-rotate

llvm/trunk/lib/Transforms/Scalar/LoopRotation.cpp

if (DT) {
                                                    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);
+          BasicBlock *NearestDom = nullptr;
+          for (BasicBlock *Pred : predecessors(BB)) {
+            // Consider only reachable basic blocks.
+            if (!DT->getNode(Pred))
+              continue;
+
+            if (!NearestDom) {
+              NearestDom = Pred;
+              continue;
+            }
+
+            NearestDom = DT->findNearestCommonDominator(NearestDom, Pred);
+            assert(NearestDom && "No NearestCommonDominator found");
+          }
+
+          assert(NearestDom && "Nearest dominator not found");
 
           // Remember if this changes the DomTree.
           if (Node->getIDom()->getBlock() != NearestDom) {
             DT->changeImmediateDominator(BB, NearestDom);
             Changed = true;
           }
         }
 

llvm/trunk/test/Transforms/LoopRotate/pr33701.ll

+; RUN: opt < %s -loop-rotate -verify-dom-info -verify-loop-info -disable-output
+
+define void @func() {
+bb0:
+  br label %bb1
+
+bb1:                                              ; preds = %bb4, %bb0
+  %0 = phi i16 [ %2, %bb4 ], [ 0, %bb0 ]
+  %1 = icmp sle i16 %0, 2
+  br i1 %1, label %bb2, label %bb5
+
+bb2:                                              ; preds = %bb1
+  br i1 undef, label %bb6, label %bb4
+
+bb3:                                              ; No predecessors!
+  br label %bb6
+
+bb4:                                              ; preds = %bb2
+  %2 = add i16 undef, 1
+  br label %bb1
+
+bb5:                                              ; preds = %bb1
+  br label %bb6
+
+bb6:                                              ; preds = %bb5, %bb3, %bb2
+  unreachable
+}