[RuntimeLoopUnroller] Add assert that we dont unroll non-rotated loops

[anna]

Summary

Cloning basic blocks in the loop for runtime loop unroller depends on loop being
in rotated form (i.e. loop latch target is the exit block).
Assert that this is true, so that callers of runtime loop unroller pass in
canonical loops.
The single caller of this function has that check recently added:
https://reviews.llvm.org/rL301239

[anna]

Some tests are failing, need to understand why.

[anna]

Move the assert before the loop is being modified to support prolog/epilog remainders.
All tests passing.

[davide]

LGTM.

lib/Transforms/Utils/LoopUnrollRuntime.cpp

515–521

This seems like a natural extension of what I did.
I think the fact that the other successor is the header is given by the definition of a latch, so we should be fine with this.

[anna]

lib/Transforms/Utils/LoopUnrollRuntime.cpp

515–521

Thanks, yes. I had spotted this implicit dependency (latch's successor is an exit) in the runtime unroller's clone function and was wondering if we can have such a situation where the dependency is not true. Sanjoy had pointed me to your fix (and test case) in the loop unroller.

[davide]

lib/Transforms/Utils/LoopUnrollRuntime.cpp

515–521

Side note: ideally I'd like to teach the unroller to handle more complicated loops in the future rather than bailing out, but that would require more time than the one I can devote to the cause for the next 3 months at least.
Thanks for your patch. Feel free to land.

lib/Transforms/Utils/LoopUnrollRuntime.cpp

bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
 
   // This constraint lets us deal with an overflowing trip count easily; see the
   // comment on ModVal below.
   if (Log2_32(Count) > BEWidth)
     return false;
 
   BasicBlock *Latch = L->getLoopLatch();
 
   // Loop structure is the following:
   //
   // PreHeader
   //   Header
   //   ...
   //   Latch
   // Exit
 
   BasicBlock *NewPreHeader;
   BasicBlock *NewExit = nullptr;
   BasicBlock *PrologExit = nullptr;
   BasicBlock *EpilogPreHeader = nullptr;
   BasicBlock *PrologPreHeader = nullptr;
 
   if (UseEpilogRemainder) {
bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
   // Do not create 1 iteration loop.
   bool CreateRemainderLoop = (Count != 2);
 
   // Clone all the basic blocks in the loop. If Count is 2, we don't clone
   // the loop, otherwise we create a cloned loop to execute the extra
   // iterations. This function adds the appropriate CFG connections.
   BasicBlock *InsertBot = UseEpilogRemainder ? Exit : PrologExit;
   BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
+  // Cloning the loop basic blocks requires that one of the targets of the Latch
+  // be the (single) exit block out of the loop. This needs to be guaranteed by
+  // the callers of UnrollRuntimeLoopRemainder.
+  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
+  assert(LatchBR->getSuccessor(0) == Exit ||
+         LatchBR->getSuccessor(1) == Exit && "loop latch successor should be "
+                                             "exit block!");
   CloneLoopBlocks(L, ModVal, CreateRemainderLoop, UseEpilogRemainder, InsertTop,
                   InsertBot, NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
 
   // Insert the cloned blocks into the function.
   F->getBasicBlockList().splice(InsertBot->getIterator(),
                                 F->getBasicBlockList(),
                                 NewBlocks[0]->getIterator(),
                                 F->end());