[LoopUnroll] Properly update loopinfo for runtime unrolling by 2

[mkuper]

Summary

Even when we don't actually create a remainder loop (that is, when we unroll by 2), we may have nested loops that we need to create.
This is complicated by the fact the remainder may either live in an outer loop or in the top-level, which means we may create new top-level loops.

I'm not too happy with this patch, better suggestions are welcome.

[chandlerc]

I understand why this is a bit gross, but I dunno... I don't have any better ideas. Ship it? (Feel free to wait for mzolotukhin or others if you're not sure.)

lib/Transforms/Utils/LoopUnrollRuntime.cpp

328 ↗

(On Diff #85830)

indent looks off here? maybe just phab...

[fhahn]

LGTM. I also looked into creating a patch for this issue and I think this patch addresses the issue relatively nicely.

lib/Transforms/Utils/LoopUnroll.cpp

205 ↗

(On Diff #85830)

Unnecessary { and }, not sure if you want to keep them. In your change in LoopUnrollRuntime.cpp you don't use them for single statement blocks.

[mkuper]

Ok, thanks.
If two people think it's good enough, it's going on. @mzolotukhin , feel free to suggest improvements post-commit. :-)

lib/Transforms/Utils/LoopUnrollRuntime.cpp

328 ↗

(On Diff #85830)

No, not phab, my bad, thanks.

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

PreservedAnalyses LoopUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
 
   // The parent must not be damaged by unrolling!
 #ifndef NDEBUG
   if (ParentL)
     ParentL->verifyLoop();
 #endif
 
   // Unrolling can do several things to introduce new loops into a loop nest:
-  // - Partial unrolling clones child loops within the current loop.
+  // - Partial unrolling clones child loops within the current loop. If it
+  //   uses a remainder, then it can also create any number of sibling loops.
   // - Full unrolling clones child loops within the current loop but then
   //   removes the current loop making all of the children appear to be new
   //   sibling loops.
   // - Loop peeling can directly introduce new sibling loops by peeling one
   //   iteration.
   //
   // When a new loop appears as a sibling loop, either from peeling an
   // iteration or fully unrolling, its nesting structure has fundamentally

llvm/trunk/lib/Transforms/Utils/LoopUnroll.cpp

const Loop* llvm::addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
   assert(OldLoop && "Should (at least) be in the loop being unrolled!");
 
   Loop *&NewLoop = NewLoops[OldLoop];
   if (!NewLoop) {
     // Found a new sub-loop.
     assert(OriginalBB == OldLoop->getHeader() &&
            "Header should be first in RPO");
 
+    NewLoop = new Loop();
     Loop *NewLoopParent = NewLoops.lookup(OldLoop->getParentLoop());
-    assert(NewLoopParent &&
-           "Expected parent loop before sub-loop in RPO");
-    NewLoop = new Loop;
+
+    if (NewLoopParent)
       NewLoopParent->addChildLoop(NewLoop);
+    else
+      LI->addTopLevelLoop(NewLoop);
+
     NewLoop->addBasicBlockToLoop(ClonedBB, *LI);
     return OldLoop;
   } else {
     NewLoop->addBasicBlockToLoop(ClonedBB, *LI);
     return nullptr;
   }
 }
 

llvm/trunk/lib/Transforms/Utils/LoopUnrollRuntime.cpp

if (CreateRemainderLoop) {
     NewLoop = new Loop();
     if (ParentLoop)
       ParentLoop->addChildLoop(NewLoop);
     else
       LI->addTopLevelLoop(NewLoop);
   }
 
   NewLoopsMap NewLoops;
+  if (NewLoop)
     NewLoops[L] = NewLoop;
+  else if (ParentLoop)
+    NewLoops[L] = ParentLoop;
+
   // For each block in the original loop, create a new copy,
   // and update the value map with the newly created values.
   for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
     BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, "." + suffix, F);
     NewBlocks.push_back(NewBB);
    
-    if (NewLoop) {
+    // If we're unrolling the outermost loop, there's no remainder loop,
+    // and this block isn't in a nested loop, then the new block is not
+    // in any loop. Otherwise, add it to loopinfo.
+    if (CreateRemainderLoop || LI->getLoopFor(*BB) != L || ParentLoop)
       addClonedBlockToLoopInfo(*BB, NewBB, LI, NewLoops);
-    } else if (ParentLoop)
-      ParentLoop->addBasicBlockToLoop(NewBB, *LI);
 
     VMap[*BB] = NewBB;
     if (Header == *BB) {
       // For the first block, add a CFG connection to this newly
       // created block.
       InsertTop->getTerminator()->setSuccessor(0, NewBB);
     }
 

llvm/trunk/test/Transforms/LoopUnroll/revisit.ll

 ; CHECK-NOT: LoopUnrollPass
 
 l0.0.latch:
   %cmp = icmp slt i32 %iv.next, %count
   br i1 %cmp, label %l0.0, label %l0.latch, !llvm.loop !1
 ; CHECK: LoopUnrollPass on Loop at depth 2 containing: %l0.0
 ; CHECK-NOT: LoopUnrollPass
 ;
-; Partial unrolling occurs which introduces new child loops but not new sibling
+; Partial unrolling occurs which introduces both new child loops and new sibling
 ; loops. We only visit the child loops in a special mode, not by default.
 ; CHECK-CHILDREN: LoopUnrollPass on Loop at depth 3 containing: %l0.0.0<header>
 ; CHECK-CHILDREN-NOT: LoopUnrollPass
 ; CHECK-CHILDREN: LoopUnrollPass on Loop at depth 3 containing: %l0.0.1<header>
 ; CHECK-CHILDREN-NOT: LoopUnrollPass
 ; CHECK-CHILDREN: LoopUnrollPass on Loop at depth 3 containing: %l0.0.0.1<header>
 ; CHECK-CHILDREN-NOT: LoopUnrollPass
 ; CHECK-CHILDREN: LoopUnrollPass on Loop at depth 3 containing: %l0.0.1.1<header>
 ; CHECK-CHILDREN-NOT: LoopUnrollPass
 ;
 ; When we revisit children, we also revisit the current loop.
 ; CHECK-CHILDREN: LoopUnrollPass on Loop at depth 2 containing: %l0.0<header>
 ; CHECK-CHILDREN-NOT: LoopUnrollPass
-
+;
+; Revisit the children of the outer loop that are part of the prologue.
+; 
+; CHECK: LoopUnrollPass on Loop at depth 2 containing: %l0.0.0.prol<header>
+; CHECK-NOT: LoopUnrollPass
+; CHECK: LoopUnrollPass on Loop at depth 2 containing: %l0.0.1.prol<header>
+; CHECK-NOT: LoopUnrollPass
 l0.latch:
   br label %l0
 ; CHECK: LoopUnrollPass on Loop at depth 1 containing: %l0<header>
 ; CHECK-NOT: LoopUnrollPass
 
 exit:
   ret void
 }
 !1 = !{!1, !2}
 !2 = !{!"llvm.loop.unroll.count", i32 2}

llvm/trunk/test/Transforms/LoopUnroll/runtime-li.ll

+; RUN: opt -S -loop-unroll -unroll-runtime -unroll-count=2 -verify-loop-info -pass-remarks=loop-unroll < %s 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Verify that runtime-unrolling a top-level loop that has nested loops does not
+; make the unroller produce invalid loop-info.
+; CHECK: remark: {{.*}}: unrolled loop by a factor of 2 with run-time trip count
+; CHECK: @widget
+; CHECK: ret void
+define void @widget(double* %arg, double* %arg1, double* %p, i64* %q1, i64* %q2) local_unnamed_addr {
+entry:
+  br label %header.outer
+
+header.outer:                                     ; preds = %latch.outer, %entry
+  %tmp = phi double* [ %tmp8, %latch.outer ], [ %arg, %entry ]
+  br label %header.inner
+
+header.inner:                                     ; preds = %latch.inner, %header.outer
+  br i1 undef, label %latch.inner, label %latch.outer
+
+latch.inner:                                      ; preds = %header.inner
+  %tmp5 = load i64, i64* %q1, align 8
+  store i64 %tmp5, i64* %q2, align 8
+  %tmp6 = icmp eq double* %p, %arg
+  br label %header.inner
+
+latch.outer:                                      ; preds = %header.inner
+  store double 0.0, double* %p, align 8
+  %tmp8 = getelementptr inbounds double, double* %tmp, i64 1
+  %tmp9 = icmp eq double* %tmp8, %arg1
+  br i1 %tmp9, label %exit, label %header.outer
+
+exit:                                             ; preds = %latch.outer
+  ret void
+}