[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

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

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

No, not phab, my bad, thanks.

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;
   }
 }
 

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 outernmost 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);
     }
 

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"
+
+; 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) local_unnamed_addr {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %tmp = phi double* [ %tmp8, %bb7 ], [ undef, %bb ]
+  br label %bb3
+
+bb3:                                              ; preds = %bb4, %bb2
+  br i1 undef, label %bb4, label %bb7
+
+bb4:                                              ; preds = %bb3
+  %tmp5 = load i64, i64* undef, align 8
+  store i64 %tmp5, i64* undef, align 8
+  %tmp6 = icmp eq double* undef, %arg
+  br label %bb3
+
+bb7:                                              ; preds = %bb3
+  store double undef, double* undef, align 8
+  %tmp8 = getelementptr inbounds double, double* %tmp, i64 1
+  %tmp9 = icmp eq double* %tmp8, %arg1
+  br i1 %tmp9, label %bb10, label %bb2
+
+bb10:                                             ; preds = %bb7
+  ret void
+}