Adding ability to unroll loops using epilogue remainder.

[evstupac]

Summary

The patch adds an ability to unroll loops using epilogue remainder and makes it default (instead of current prologue),
The epilogue remainder is better as it do not produce additional non-constant phi nodes.
for(i = 0; i < n; i++)

...

For now loop unrolling looks like:
PROLOG:

ip = phi [0, ip.next]
...
ip.next = ip + 1
cmp ip, n&7

jne PROLOG
i0 = phi [0, ip.next]
LOOP (unrolling on 8):

i = phi [**i0**, i.next]
i.next = i + 1
cmp i, n

jne LOOP

In the LOOP (this is supposed to be unrolled) we have i = phi [i0, i.next].
Basically, that means that we don't know where we start now, however before unrolling we knew the start position is 0.
Assuming unrolled part of the loop is hotter than remainder (prologue currently), it is better to move this induction variable with unknown start to remainder code (which is done by epilogue technique).

[mzolotukhin]

Hi Evgeny,

I'm going to look at this patch soon, but at first glance I find one thing that distracts from the actual stuff: your patch contains a lot of unnecessary changes, such as typo fixes, rewording of not directly related comments, variables renaming etc. While such changes are fine by itself, there is no need to include them in the main patch. You can commit them before the patch, and no pre-commit review is required for obvious patches, such as typo fixes.

Michael

[evstupac]

Hi Michael,

Thanks for taking the patch into pipeline.
Yes there are some rewording and comment changes in previously written code. However most of them implicitly related to newly written code and comments (basically because bigger code requires more detailed comments for understanding). Separating the patch into 2 is not a big deal. If it is more convenient for you to review the code after rewording I'll try to do it first.

Evgeny

[mzolotukhin]

Hi Evgeny,

A bunch of mostly stylistic comments from me are inline, I'd take a closer look later. I'm fine with keeping it in one patch too, usually it's just more convenient to commit small stuff before to move it out of the way.

Michael

lib/Transforms/Utils/LoopUnrollRuntime.cpp

130 ↗

(On Diff #50633)

I was talking mostly about stuff like this. This is very local change, that doesn't depend on the rest of the patch in any way.

174–175 ↗

(On Diff #50633)

You could use range-loop here.

179–183 ↗

(On Diff #50633)

Maybe use IR syntax in the comments?

192 ↗

(On Diff #50633)

Why is it UndefValue?

194–195 ↗

(On Diff #50633)

Why not

Instruction *I = dyn_cast<Instruction>(PN->getIncomingValueForBlock(Latch));

? And then use I instead of V.

218–219 ↗

(On Diff #50633)

You could do

for (BasicBlock *Succ : successors(Latch))

223–224 ↗

(On Diff #50633)

We can just check if(L->contains(*SBI)) before the loop, right?

235–236 ↗

(On Diff #50633)

Nitpick: this looks wrapped before 80 characters.

292 ↗

(On Diff #50633)

Unnecessary change.

365–366 ↗

(On Diff #50633)

Unnecessary change.

446–447 ↗

(On Diff #50633)

Nitpick: why remove the dot?

480–481 ↗

(On Diff #50633)

Looks like an unnecessary change.

test/Transforms/LoopUnroll/AArch64/runtime-loop.ll

1–2 ↗

(On Diff #50633)

Where did -mtriple aarch64 -mcpu=cortex-a57 go?

test/Transforms/LoopUnroll/high-cost-trip-count-computation.ll

37 ↗

(On Diff #50633)

These CHECK lines were intended to check the code before the loop, so if we start doing remainder iterations in epilogue, then we should look for for.body rather than for.body.epil, as it will appear first. This doesn't matter much in the current testcase since there are no udiv in the loop, but still.

[evstupac]

lib/Transforms/Utils/LoopUnrollRuntime.cpp

174–175 ↗

(On Diff #50633)

Almost the same loops to iterate PHIs are widely used in Unroll code. If we change it here we should change everywhere.
As for the range itself, do you mean we can construct vector of PHIs and iterate them?

179–183 ↗

(On Diff #50633)

Will make it more closer to IR, however I'd like to keep variable names from code here.

192 ↗

(On Diff #50633)

Since we added a branch around the Loop to NewExit this UndefValue will be updated correctly (the same technique is used in ConnectProlog). Here we can find value from PreHeader based on V from Latch, however it will be more complicated and further update.

194–195 ↗

(On Diff #50633)

We'll need an additional cast in this case as VMap[I] returns not an Instruction.
And add additional check to add incoming value to EpilogPN, verifying when I is null (to add UndefValue).

218–219 ↗

(On Diff #50633)

Will update.

223–224 ↗

(On Diff #50633)

Correct. There is similar place in LoopUnroll.cpp which has this check in place already.

[evstupac]

Updated according to latest comments:

1. Fix comments
2. Exclude unnecessary changes
3. Update iterators

[mzolotukhin]

Hi Evgeny,

Some comments inline. I hope to take a more detailed look into the actual logic of the patch soon.

Thanks,
Michael

lib/Transforms/Utils/LoopUnrollRuntime.cpp

173–174 ↗

(On Diff #51084)

No, I mean

for (Instruction &I : NewExit) {
  auto *PN = dyn_cast<PHINode>(&I);
  if (!PN)
    break;
  ...

Personally, I find this easier to read than the version with explicit iterators. No need to change the other code, at least definitely not in this patch.

178–182 ↗

(On Diff #51084)

Sure, no complains about the variable names:)

193–194 ↗

(On Diff #51084)

Right, I see now, thanks.

257 ↗

(On Diff #51084)

CreateLoop is a bit misleading name. Maybe CreateRemainderLoop or CreateLoopForRemainder? Also, some comments about InsertTop and InsertBot would be helpful here (I know we didn't have them before, but since you've already dug into the code, it's probably easy for you).

543–544 ↗

(On Diff #51084)

Maybe expand it just before the actual use?

[evstupac]

lib/Transforms/Utils/LoopUnrollRuntime.cpp

543–544 ↗

(On Diff #51084)

Since TripCount is BECount + 1 it would be easier for combiner to optimize them when they are close.
BECount expanded here before my changes. For epilog remainder I don't need it.
Also when we add runtime unroll with non-power-of-2 factors we'll need BECount for extra iteration (for non-power-of-2 cases).

[evstupac]

Updated according to latest comments.

[mzolotukhin]

lib/Transforms/Utils/LoopUnroll.cpp

301 ↗

(On Diff #51507)

Trailing whitespace.

lib/Transforms/Utils/LoopUnrollRuntime.cpp

555–557 ↗

(On Diff #51507)

I believe the patch for non-power-of-2 factor has already been committed. Could you please rebase this patch on ToT (and that would probably resolve my concern about BECount).

[evstupac]

Patch rebased.

[evstupac]

lib/Transforms/Utils/LoopUnrollRuntime.cpp

549–550 ↗

(On Diff #51871)

The other point here is that to expand BECount before actual use we'll need to recompute PreHeaderBR, as it is deleted at line 602.

[mzolotukhin]

lib/Transforms/Utils/LoopUnrollRuntime.cpp

549–550 ↗

(On Diff #51871)

This makes sense now, thanks. I still feel uneasy about this function though, it's becoming kind of a spaghetti code. Would it be possible to refactor it a bit to get rid of multiple if (UseEpilogRemainder)? I think now the amount of code that is shared between these two cases isn't much bigger than the amount of code that is different. If we shuffle the code around (where possible), and factor out some common blocks to helper functions, we can keep only one if (UseEpilogRemainder), or rather have two specialized functions.

[evstupac]

Tried to minimize UseEpilogRemainder condition blocks.
The change affect tests (which I have not updated yet). If you agree the change is better solution, I'll update tests.

[evstupac]

lib/Transforms/Utils/LoopUnrollRuntime.cpp

549–550 ↗

(On Diff #51871)

Shared code requires a lot of parameters. That way helper functions will add a lot of unnecessary parameters passing. Not sure this will simplify the code.
The difference between epilog and prolog now refers to another way of prolog implementation. I can make prolog implementation closer to epilog, however this will affect prolog source code.
Say prolog implementation do not create PrologPreHeader explicitly, while epilog do create EpilogPreHeader.

[evstupac]

Tests updated.
Comments at UseEpilogRemainder if-then-else united to shorten modified code.

[mzolotukhin]

Thanks, I like it better now! It looks good to me (with one remark inline).

Michael

lib/Transforms/Utils/LoopUnrollRuntime.cpp

652 ↗

(On Diff #52300)

You could reuse existing IRBuilder (just use SetInsertPoint method).

[zzheng]

I've seen 'unrolling loop' in comments, personally I prefer 'unrolled loop' for clarity.

lib/Transforms/Utils/LoopUnroll.cpp

297 ↗

(On Diff #52300)

'prolog'?

I recommend changing prolog/remainder here to 'leftover'

lib/Transforms/Utils/LoopUnrollRuntime.cpp

146 ↗

(On Diff #52300)

You mean 'unrolled loop', right?

191 ↗

(On Diff #52300)

PN shoudl have 2 uses, right? One in epilogue loop or its preheader and one in Exit.

Please clarify it only has 1 use for now as we'll add the use in epilogue later.

[evstupac]

lib/Transforms/Utils/LoopUnroll.cpp

297 ↗

(On Diff #52300)

Thanks for catching this. For sure it is not only for prolog it is for all kind of remainder loops. "leftover" is also good, but since I used "remainder" in all other places it is better to keep the same name here.

lib/Transforms/Utils/LoopUnrollRuntime.cpp

146 ↗

(On Diff #52300)

Actually the loop is in unrolling process. Here in "UnrollRuntimeLoopRemainder" we only prepare loop for unroll. Actual unroll occurs at UnrollLoop function. So I'd like to keep "unrolling" here.

191 ↗

(On Diff #52300)

It has one use after splitting. It will have 2 uses. Line 196 add incoming value from PreHeader. Lines 214-217 explain how it will look like. The loop structure are commented at lines 162-172.

[evstupac]

1 comment fix + SetInsetPoint instead of new Builder according to comments.

llvm/trunk/include/llvm/Transforms/Utils/UnrollLoop.h

 class Pass;
 class ScalarEvolution;
 
 bool UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool AllowRuntime,
                 bool AllowExpensiveTripCount, unsigned TripMultiple,
                 LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
                 AssumptionCache *AC, bool PreserveLCSSA);
 
-bool UnrollRuntimeLoopProlog(Loop *L, unsigned Count,
-                             bool AllowExpensiveTripCount, LoopInfo *LI,
+bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
+                                bool AllowExpensiveTripCount,
+                                bool UseEpilogRemainder, LoopInfo *LI,
                                 ScalarEvolution *SE, DominatorTree *DT,
                                 bool PreserveLCSSA);
 
 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
 }
 
 #endif

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

 using namespace llvm;
 
 #define DEBUG_TYPE "loop-unroll"
 
 // TODO: Should these be here or in LoopUnroll?
 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
 STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");
 
+static cl::opt<bool>
+UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(true), cl::Hidden,
+                    cl::desc("Allow runtime unrolled loops to be unrolled "
+                             "with epilog instead of prolog."));
+
 /// Convert the instruction operands from referencing the current values into
 /// those specified by VMap.
 static inline void remapInstruction(Instruction *I,
                                     ValueToValueMapTy &VMap) {
   for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) {
     Value *Op = I->getOperand(op);
     ValueToValueMapTy::iterator It = VMap.find(Op);
     if (It != VMap.end())
DEBUG(
           for (auto &I : *BB)
             if (auto CS = CallSite(&I))
               HasConvergent |= CS.isConvergent();
         assert((!HasConvergent || TripMultiple % Count == 0) &&
                "Unroll count must divide trip multiple if loop contains a "
                "convergent "
                "operation.");
       });
-  // Don't output the runtime loop prolog if Count is a multiple of
-  // TripMultiple.  Such a prolog is never needed, and is unsafe if the loop
+  // Don't output the runtime loop remainder if Count is a multiple of
+  // TripMultiple.  Such a remainder is never needed, and is unsafe if the loop
   // contains a convergent instruction.
   if (RuntimeTripCount && TripMultiple % Count != 0 &&
-      !UnrollRuntimeLoopProlog(L, Count, AllowExpensiveTripCount, LI, SE, DT,
+      !UnrollRuntimeLoopRemainder(L, Count, AllowExpensiveTripCount,
+                                  UnrollRuntimeEpilog, LI, SE, DT, 
                                   PreserveLCSSA))
     return false;
 
   // Notify ScalarEvolution that the loop will be substantially changed,
   // if not outright eliminated.
   if (SE)
     SE->forgetLoop(L);
 
   // If we know the trip count, we know the multiple...

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

 // trip counts.  See LoopUnroll.cpp for unrolling loops with compile-time
 // trip counts.
 //
 // The functions in this file are used to generate extra code when the
 // run-time trip count modulo the unroll factor is not 0.  When this is the
 // case, we need to generate code to execute these 'left over' iterations.
 //
 // The current strategy generates an if-then-else sequence prior to the
-// unrolled loop to execute the 'left over' iterations.  Other strategies
-// include generate a loop before or after the unrolled loop.
+// unrolled loop to execute the 'left over' iterations before or after the
+// unrolled loop.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/UnrollLoop.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"

 /// - Create PHI nodes at prolog end block to combine values
 ///   that exit the prolog code and jump around the prolog.
 /// - Add a PHI operand to a PHI node at the loop exit block
 ///   for values that exit the prolog and go around the loop.
 /// - Branch around the original loop if the trip count is less
 ///   than the unroll factor.
 ///
 static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
-                          BasicBlock *LastPrologBB, BasicBlock *PrologEnd,
-                          BasicBlock *OrigPH, BasicBlock *NewPH,
-                          ValueToValueMapTy &VMap, DominatorTree *DT,
-                          LoopInfo *LI, bool PreserveLCSSA) {
+                          BasicBlock *PrologExit, BasicBlock *PreHeader,
+                          BasicBlock *NewPreHeader, ValueToValueMapTy &VMap,
+                          DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA) {
   BasicBlock *Latch = L->getLoopLatch();
   assert(Latch && "Loop must have a latch");
+  BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);
 
   // Create a PHI node for each outgoing value from the original loop
   // (which means it is an outgoing value from the prolog code too).
   // The new PHI node is inserted in the prolog end basic block.
-  // The new PHI name is added as an operand of a PHI node in either
+  // The new PHI node value is added as an operand of a PHI node in either
   // the loop header or the loop exit block.
-  for (succ_iterator SBI = succ_begin(Latch), SBE = succ_end(Latch);
-       SBI != SBE; ++SBI) {
-    for (BasicBlock::iterator BBI = (*SBI)->begin();
-         PHINode *PN = dyn_cast<PHINode>(BBI); ++BBI) {
-
+  for (BasicBlock *Succ : successors(Latch)) {
+    for (Instruction &BBI : *Succ) {
+      PHINode *PN = dyn_cast<PHINode>(&BBI);
+      // Exit when we passed all PHI nodes.
+      if (!PN)
+        break;
       // Add a new PHI node to the prolog end block and add the
       // appropriate incoming values.
-      PHINode *NewPN = PHINode::Create(PN->getType(), 2, PN->getName()+".unr",
-                                       PrologEnd->getTerminator());
+      PHINode *NewPN = PHINode::Create(PN->getType(), 2, PN->getName() + ".unr",
+                                       PrologExit->getFirstNonPHI());
       // Adding a value to the new PHI node from the original loop preheader.
       // This is the value that skips all the prolog code.
       if (L->contains(PN)) {
-        NewPN->addIncoming(PN->getIncomingValueForBlock(NewPH), OrigPH);
+        NewPN->addIncoming(PN->getIncomingValueForBlock(NewPreHeader),
+                           PreHeader);
       } else {
-        NewPN->addIncoming(UndefValue::get(PN->getType()), OrigPH);
+        NewPN->addIncoming(UndefValue::get(PN->getType()), PreHeader);
       }
 
       Value *V = PN->getIncomingValueForBlock(Latch);
       if (Instruction *I = dyn_cast<Instruction>(V)) {
         if (L->contains(I)) {
           V = VMap[I];
         }
       }
       // Adding a value to the new PHI node from the last prolog block
       // that was created.
-      NewPN->addIncoming(V, LastPrologBB);
+      NewPN->addIncoming(V, PrologLatch);
 
       // Update the existing PHI node operand with the value from the
       // new PHI node.  How this is done depends on if the existing
       // PHI node is in the original loop block, or the exit block.
       if (L->contains(PN)) {
-        PN->setIncomingValue(PN->getBasicBlockIndex(NewPH), NewPN);
+        PN->setIncomingValue(PN->getBasicBlockIndex(NewPreHeader), NewPN);
       } else {
-        PN->addIncoming(NewPN, PrologEnd);
+        PN->addIncoming(NewPN, PrologExit);
       }
     }
   }
 
   // Create a branch around the original loop, which is taken if there are no
   // iterations remaining to be executed after running the prologue.
-  Instruction *InsertPt = PrologEnd->getTerminator();
+  Instruction *InsertPt = PrologExit->getTerminator();
   IRBuilder<> B(InsertPt);
 
   assert(Count != 0 && "nonsensical Count!");
 
   // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)
   // This means %xtraiter is (BECount + 1) and all of the iterations of this
   // loop were executed by the prologue.  Note that if BECount <u (Count - 1)
   // then (BECount + 1) cannot unsigned-overflow.
   Value *BrLoopExit =
       B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1));
   BasicBlock *Exit = L->getUniqueExitBlock();
   assert(Exit && "Loop must have a single exit block only");
   // Split the exit to maintain loop canonicalization guarantees
-  SmallVector<BasicBlock*, 4> Preds(pred_begin(Exit), pred_end(Exit));
+  SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
   SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", DT, LI,
                          PreserveLCSSA);
   // Add the branch to the exit block (around the unrolled loop)
-  B.CreateCondBr(BrLoopExit, Exit, NewPH);
+  B.CreateCondBr(BrLoopExit, Exit, NewPreHeader);
+  InsertPt->eraseFromParent();
+}
+
+/// Connect the unrolling epilog code to the original loop.
+/// The unrolling epilog code contains code to execute the
+/// 'extra' iterations if the run-time trip count modulo the
+/// unroll count is non-zero.
+///
+/// This function performs the following:
+/// - Update PHI nodes at the unrolling loop exit and epilog loop exit
+/// - Create PHI nodes at the unrolling loop exit to combine
+///   values that exit the unrolling loop code and jump around it.
+/// - Update PHI operands in the epilog loop by the new PHI nodes
+/// - Branch around the epilog loop if extra iters (ModVal) is zero.
+///
+static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,
+                          BasicBlock *Exit, BasicBlock *PreHeader,
+                          BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader,
+                          ValueToValueMapTy &VMap, DominatorTree *DT,
+                          LoopInfo *LI, bool PreserveLCSSA)  {
+  BasicBlock *Latch = L->getLoopLatch();
+  assert(Latch && "Loop must have a latch");
+  BasicBlock *EpilogLatch = cast<BasicBlock>(VMap[Latch]);
+
+  // Loop structure should be the following:
+  //
+  // PreHeader
+  // NewPreHeader
+  //   Header
+  //   ...
+  //   Latch
+  // NewExit (PN)
+  // EpilogPreHeader
+  //   EpilogHeader
+  //   ...
+  //   EpilogLatch
+  // Exit (EpilogPN)
+
+  // Update PHI nodes at NewExit and Exit.
+  for (Instruction &BBI : *NewExit) {
+    PHINode *PN = dyn_cast<PHINode>(&BBI);
+    // Exit when we passed all PHI nodes.
+    if (!PN)
+      break;
+    // PN should be used in another PHI located in Exit block as
+    // Exit was split by SplitBlockPredecessors into Exit and NewExit
+    // Basicaly it should look like:
+    // NewExit:
+    //   PN = PHI [I, Latch]
+    // ...
+    // Exit:
+    //   EpilogPN = PHI [PN, EpilogPreHeader]
+    //
+    // There is EpilogPreHeader incoming block instead of NewExit as
+    // NewExit was spilt 1 more time to get EpilogPreHeader.
+    assert(PN->hasOneUse() && "The phi should have 1 use");
+    PHINode *EpilogPN = cast<PHINode> (PN->use_begin()->getUser());
+    assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block");
+
+    // Add incoming PreHeader from branch around the Loop
+    PN->addIncoming(UndefValue::get(PN->getType()), PreHeader);
+
+    Value *V = PN->getIncomingValueForBlock(Latch);
+    Instruction *I = dyn_cast<Instruction>(V);
+    if (I && L->contains(I))
+      // If value comes from an instruction in the loop add VMap value.
+      V = VMap[I];
+    // For the instruction out of the loop, constant or undefined value
+    // insert value itself.
+    EpilogPN->addIncoming(V, EpilogLatch);
+
+    assert(EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 &&
+          "EpilogPN should have EpilogPreHeader incoming block");
+    // Change EpilogPreHeader incoming block to NewExit.
+    EpilogPN->setIncomingBlock(EpilogPN->getBasicBlockIndex(EpilogPreHeader),
+                               NewExit);
+    // Now PHIs should look like:
+    // NewExit:
+    //   PN = PHI [I, Latch], [undef, PreHeader]
+    // ...
+    // Exit:
+    //   EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]
+  }
+
+  // Create PHI nodes at NewExit (from the unrolling loop Latch and PreHeader).
+  // Update corresponding PHI nodes in epilog loop.
+  for (BasicBlock *Succ : successors(Latch)) {
+    // Skip this as we already updated phis in exit blocks.
+    if (!L->contains(Succ))
+      continue;
+    for (Instruction &BBI : *Succ) {
+      PHINode *PN = dyn_cast<PHINode>(&BBI);
+      // Exit when we passed all PHI nodes.
+      if (!PN)
+        break;
+      // Add new PHI nodes to the loop exit block and update epilog
+      // PHIs with the new PHI values.
+      PHINode *NewPN = PHINode::Create(PN->getType(), 2, PN->getName() + ".unr",
+                                       NewExit->getFirstNonPHI());
+      // Adding a value to the new PHI node from the unrolling loop preheader.
+      NewPN->addIncoming(PN->getIncomingValueForBlock(NewPreHeader), PreHeader);
+      // Adding a value to the new PHI node from the unrolling loop latch.
+      NewPN->addIncoming(PN->getIncomingValueForBlock(Latch), Latch);
+
+      // Update the existing PHI node operand with the value from the new PHI
+      // node.  Corresponding instruction in epilog loop should be PHI.
+      PHINode *VPN = cast<PHINode>(VMap[&BBI]);
+      VPN->setIncomingValue(VPN->getBasicBlockIndex(EpilogPreHeader), NewPN);
+    }
+  }
+
+  Instruction *InsertPt = NewExit->getTerminator();
+  IRBuilder<> B(InsertPt);
+  Value *BrLoopExit = B.CreateIsNotNull(ModVal);
+  assert(Exit && "Loop must have a single exit block only");
+  // Split the exit to maintain loop canonicalization guarantees
+  SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
+  SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI,
+                         PreserveLCSSA);
+  // Add the branch to the exit block (around the unrolling loop)
+  B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
   InsertPt->eraseFromParent();
 }
 
 /// Create a clone of the blocks in a loop and connect them together.
-/// If UnrollProlog is true, loop structure will not be cloned, otherwise a new
-/// loop will be created including all cloned blocks, and the iterator of it
-/// switches to count NewIter down to 0.
+/// If CreateRemainderLoop is false, loop structure will not be cloned,
+/// otherwise a new loop will be created including all cloned blocks, and the
+/// iterator of it switches to count NewIter down to 0.
+/// The cloned blocks should be inserted between InsertTop and InsertBot.
+/// If loop structure is cloned InsertTop should be new preheader, InsertBot
+/// new loop exit.
 ///
-static void CloneLoopBlocks(Loop *L, Value *NewIter, const bool UnrollProlog,
+static void CloneLoopBlocks(Loop *L, Value *NewIter,
+                            const bool CreateRemainderLoop,
+                            const bool UseEpilogRemainder,
                             BasicBlock *InsertTop, BasicBlock *InsertBot,
+                            BasicBlock *Preheader,
                             std::vector<BasicBlock *> &NewBlocks,
                             LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap,
                             LoopInfo *LI) {
-  BasicBlock *Preheader = L->getLoopPreheader();
+  StringRef suffix = UseEpilogRemainder ? "epil" : "prol";
   BasicBlock *Header = L->getHeader();
   BasicBlock *Latch = L->getLoopLatch();
   Function *F = Header->getParent();
   LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
   LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
   Loop *NewLoop = nullptr;
   Loop *ParentLoop = L->getParentLoop();
-  if (!UnrollProlog) {
+  if (CreateRemainderLoop) {
     NewLoop = new Loop();
     if (ParentLoop)
       ParentLoop->addChildLoop(NewLoop);
     else
       LI->addTopLevelLoop(NewLoop);
   }
 
   // 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, ".prol", F);
+    BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, "." + suffix, F);
     NewBlocks.push_back(NewBB);
 
     if (NewLoop)
       NewLoop->addBasicBlockToLoop(NewBB, *LI);
     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);
     }
 
     if (Latch == *BB) {
-      // For the last block, if UnrollProlog is true, create a direct jump to
-      // InsertBot. If not, create a loop back to cloned head.
+      // For the last block, if CreateRemainderLoop is false, create a direct
+      // jump to InsertBot. If not, create a loop back to cloned head.
       VMap.erase((*BB)->getTerminator());
       BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]);
       BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());
       IRBuilder<> Builder(LatchBR);
-      if (UnrollProlog) {
+      if (!CreateRemainderLoop) {
         Builder.CreateBr(InsertBot);
       } else {
-        PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2, "prol.iter",
+        PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2,
+                                          suffix + ".iter",
                                           FirstLoopBB->getFirstNonPHI());
         Value *IdxSub =
             Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
                               NewIdx->getName() + ".sub");
         Value *IdxCmp =
             Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp");
         Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot);
         NewIdx->addIncoming(NewIter, InsertTop);
         NewIdx->addIncoming(IdxSub, NewBB);
       }
       LatchBR->eraseFromParent();
     }
   }
 
   // Change the incoming values to the ones defined in the preheader or
   // cloned loop.
   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
     PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
-    if (UnrollProlog) {
+    if (!CreateRemainderLoop) {
+      if (UseEpilogRemainder) {
+        unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
+        NewPHI->setIncomingBlock(idx, InsertTop);
+        NewPHI->removeIncomingValue(Latch, false);
+      } else {
         VMap[&*I] = NewPHI->getIncomingValueForBlock(Preheader);
         cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
+      }
     } else {
       unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
       NewPHI->setIncomingBlock(idx, InsertTop);
       BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
       idx = NewPHI->getBasicBlockIndex(Latch);
       Value *InVal = NewPHI->getIncomingValue(idx);
       NewPHI->setIncomingBlock(idx, NewLatch);
       if (VMap[InVal])
if (NewLoop) {
 
     MDNode *NewLoopID = MDNode::get(Context, MDs);
     // Set operand 0 to refer to the loop id itself.
     NewLoopID->replaceOperandWith(0, NewLoopID);
     NewLoop->setLoopID(NewLoopID);
   }
 }
 
-/// Insert code in the prolog code when unrolling a loop with a
+/// Insert code in the prolog/epilog code when unrolling a loop with a
 /// run-time trip-count.
 ///
 /// This method assumes that the loop unroll factor is total number
 /// of loop bodies in the loop after unrolling. (Some folks refer
 /// to the unroll factor as the number of *extra* copies added).
 /// We assume also that the loop unroll factor is a power-of-two. So, after
 /// unrolling the loop, the number of loop bodies executed is 2,
 /// 4, 8, etc.  Note - LLVM converts the if-then-sequence to a switch
 /// instruction in SimplifyCFG.cpp.  Then, the backend decides how code for
 /// the switch instruction is generated.
 ///
+/// ***Prolog case***
 ///        extraiters = tripcount % loopfactor
 ///        if (extraiters == 0) jump Loop:
 ///        else jump Prol
 /// Prol:  LoopBody;
 ///        extraiters -= 1                 // Omitted if unroll factor is 2.
 ///        if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
 ///        if (tripcount < loopfactor) jump End
 /// Loop:
 /// ...
 /// End:
 ///
-bool llvm::UnrollRuntimeLoopProlog(Loop *L, unsigned Count,
-                                   bool AllowExpensiveTripCount, LoopInfo *LI,
-                                   ScalarEvolution *SE, DominatorTree *DT,
-                                   bool PreserveLCSSA) {
-  // For now, only unroll loops that contain a single exit.
+/// ***Epilog case***
+///        extraiters = tripcount % loopfactor
+///        if (extraiters == tripcount) jump LoopExit:
+///        unroll_iters = tripcount - extraiters
+/// Loop:  LoopBody; (executes unroll_iter times);
+///        unroll_iter -= 1
+///        if (unroll_iter != 0) jump Loop:
+/// LoopExit:
+///        if (extraiters == 0) jump EpilExit:
+/// Epil:  LoopBody; (executes extraiters times)
+///        extraiters -= 1                 // Omitted if unroll factor is 2.
+///        if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
+/// EpilExit:
+
+bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
+                                      bool AllowExpensiveTripCount,
+                                      bool UseEpilogRemainder,
+                                      LoopInfo *LI, ScalarEvolution *SE,
+                                      DominatorTree *DT, bool PreserveLCSSA) {
+  // for now, only unroll loops that contain a single exit
   if (!L->getExitingBlock())
     return false;
 
   // Make sure the loop is in canonical form, and there is a single
   // exit block only.
-  if (!L->isLoopSimplifyForm() || !L->getUniqueExitBlock())
+  if (!L->isLoopSimplifyForm())
+    return false;
+  BasicBlock *Exit = L->getUniqueExitBlock(); // successor out of loop
+  if (!Exit)
     return false;
 
   // Use Scalar Evolution to compute the trip count. This allows more loops to
   // be unrolled than relying on induction var simplification.
   if (!SE)
     return false;
 
   // Only unroll loops with a computable trip count, and the trip count needs
   // to be an int value (allowing a pointer type is a TODO item).
   const SCEV *BECountSC = SE->getBackedgeTakenCount(L);
   if (isa<SCEVCouldNotCompute>(BECountSC) ||
       !BECountSC->getType()->isIntegerTy())
     return false;
 
   unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
 
   // Add 1 since the backedge count doesn't include the first loop iteration.
   const SCEV *TripCountSC =
       SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
   if (isa<SCEVCouldNotCompute>(TripCountSC))
     return false;
 
   BasicBlock *Header = L->getHeader();
-  BasicBlock *PH = L->getLoopPreheader();
-  BranchInst *PreHeaderBR = cast<BranchInst>(PH->getTerminator());
+  BasicBlock *PreHeader = L->getLoopPreheader();
+  BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
   const DataLayout &DL = Header->getModule()->getDataLayout();
   SCEVExpander Expander(*SE, DL, "loop-unroll");
   if (!AllowExpensiveTripCount &&
       Expander.isHighCostExpansion(TripCountSC, L, PreHeaderBR))
     return false;
 
   // This constraint lets us deal with an overflowing trip count easily; see the
   // comment on ModVal below.
   if (Log2_32(Count) > BEWidth)
     return false;
 
   // If this loop is nested, then the loop unroller changes the code in the
   // parent loop, so the Scalar Evolution pass needs to be run again.
   if (Loop *ParentLoop = L->getParentLoop())
     SE->forgetLoop(ParentLoop);
 
   BasicBlock *Latch = L->getLoopLatch();
-  // It helps to split the original preheader twice, one for the end of the
-  // prolog code and one for a new loop preheader.
-  BasicBlock *PEnd = SplitEdge(PH, Header, DT, LI);
-  BasicBlock *NewPH = SplitBlock(PEnd, PEnd->getTerminator(), DT, LI);
-  PreHeaderBR = cast<BranchInst>(PH->getTerminator());
 
+  // 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) {
+    // If epilog remainder
+    // Split PreHeader to insert a branch around loop for unrolling.
+    NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
+    NewPreHeader->setName(PreHeader->getName() + ".new");
+    // Split Exit to create phi nodes from branch above.
+    SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
+    NewExit = SplitBlockPredecessors(Exit, Preds, ".unr-lcssa",
+                                     DT, LI, PreserveLCSSA);
+    // Split NewExit to insert epilog remainder loop.
+    EpilogPreHeader = SplitBlock(NewExit, NewExit->getTerminator(), DT, LI);
+    EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
+  } else {
+    // If prolog remainder
+    // Split the original preheader twice to insert prolog remainder loop
+    PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
+    PrologPreHeader->setName(Header->getName() + ".prol.preheader");
+    PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
+                            DT, LI);
+    PrologExit->setName(Header->getName() + ".prol.loopexit");
+    // Split PrologExit to get NewPreHeader.
+    NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
+    NewPreHeader->setName(PreHeader->getName() + ".new");
+  }
+  // Loop structure should be the following:
+  //  Epilog             Prolog
+  //
+  // PreHeader         PreHeader
+  // *NewPreHeader     *PrologPreHeader
+  //   Header          *PrologExit
+  //   ...             *NewPreHeader
+  //   Latch             Header
+  // *NewExit            ...
+  // *EpilogPreHeader    Latch
+  // Exit              Exit
+
+  // Calculate conditions for branch around loop for unrolling
+  // in epilog case and around prolog remainder loop in prolog case.
   // Compute the number of extra iterations required, which is:
-  //  extra iterations = run-time trip count % (loop unroll factor + 1)
+  //  extra iterations = run-time trip count % loop unroll factor
+  PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
   Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
                                             PreHeaderBR);
   Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
                                           PreHeaderBR);
-
   IRBuilder<> B(PreHeaderBR);
   Value *ModVal;
   // Calculate ModVal = (BECount + 1) % Count.
   // Note that TripCount is BECount + 1.
   if (isPowerOf2_32(Count)) {
+    // When Count is power of 2 we don't BECount for epilog case, however we'll
+    // need it for a branch around unrolling loop for prolog case.
     ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");
-    //  1. There are no iterations to be run in the prologue loop.
+    //  1. There are no iterations to be run in the prolog/epilog loop.
     // OR
     //  2. The addition computing TripCount overflowed.
     //
     // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
     // the number of iterations that remain to be run in the original loop is a
     // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (we
     // explicitly check this above).
   } else {
     // As (BECount + 1) can potentially unsigned overflow we count
     // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
     Value *ModValTmp = B.CreateURem(BECount,
                                     ConstantInt::get(BECount->getType(),
                                                      Count));
     Value *ModValAdd = B.CreateAdd(ModValTmp,
                                    ConstantInt::get(ModValTmp->getType(), 1));
     // At that point (BECount % Count) + 1 could be equal to Count.
     // To handle this case we need to take mod by Count one more time.
     ModVal = B.CreateURem(ModValAdd,
                           ConstantInt::get(BECount->getType(), Count),
                           "xtraiter");
   }
-  Value *BranchVal = B.CreateIsNotNull(ModVal, "lcmp.mod");
-
-  // Branch to either the extra iterations or the cloned/unrolled loop.
-  // We will fix up the true branch label when adding loop body copies.
-  B.CreateCondBr(BranchVal, PEnd, PEnd);
-  assert(PreHeaderBR->isUnconditional() &&
-         PreHeaderBR->getSuccessor(0) == PEnd &&
-         "CFG edges in Preheader are not correct");
+  Value *CmpOperand =
+      UseEpilogRemainder ? TripCount :
+                           ConstantInt::get(TripCount->getType(), 0);
+  Value *BranchVal = B.CreateICmpNE(ModVal, CmpOperand, "lcmp.mod");
+  BasicBlock *FirstLoop = UseEpilogRemainder ? NewPreHeader : PrologPreHeader;
+  BasicBlock *SecondLoop = UseEpilogRemainder ? NewExit : PrologExit;
+  // Branch to either remainder (extra iterations) loop or unrolling loop.
+  B.CreateCondBr(BranchVal, FirstLoop, SecondLoop);
   PreHeaderBR->eraseFromParent();
   Function *F = Header->getParent();
   // Get an ordered list of blocks in the loop to help with the ordering of the
-  // cloned blocks in the prolog code.
+  // cloned blocks in the prolog/epilog code
   LoopBlocksDFS LoopBlocks(L);
   LoopBlocks.perform(LI);
 
   //
   // For each extra loop iteration, create a copy of the loop's basic blocks
   // and generate a condition that branches to the copy depending on the
   // number of 'left over' iterations.
   //
   std::vector<BasicBlock *> NewBlocks;
   ValueToValueMapTy VMap;
 
-  bool UnrollPrologue = Count == 2;
+  // For unroll factor 2 remainder loop will have 1 iterations.
+  // 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.
-  CloneLoopBlocks(L, ModVal, UnrollPrologue, PH, PEnd, NewBlocks, LoopBlocks,
-                  VMap, LI);
+  BasicBlock *InsertBot = UseEpilogRemainder ? Exit : PrologExit;
+  BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
+  CloneLoopBlocks(L, ModVal, CreateRemainderLoop, UseEpilogRemainder, InsertTop,
+                  InsertBot, NewPreHeader, NewBlocks, LoopBlocks, VMap, LI);
+
+  // Insert the cloned blocks into the function.
+  F->getBasicBlockList().splice(InsertBot->getIterator(),
+                                F->getBasicBlockList(),
+                                NewBlocks[0]->getIterator(),
+                                F->end());
 
-  // Insert the cloned blocks into the function just before the original loop.
-  F->getBasicBlockList().splice(PEnd->getIterator(), F->getBasicBlockList(),
-                                NewBlocks[0]->getIterator(), F->end());
+  // Loop structure should be the following:
+  //  Epilog             Prolog
+  //
+  // PreHeader         PreHeader
+  // NewPreHeader      PrologPreHeader
+  //   Header            PrologHeader
+  //   ...               ...
+  //   Latch             PrologLatch
+  // NewExit           PrologExit
+  // EpilogPreHeader   NewPreHeader
+  //   EpilogHeader      Header
+  //   ...               ...
+  //   EpilogLatch       Latch
+  // Exit              Exit
 
   // Rewrite the cloned instruction operands to use the values created when the
   // clone is created.
   for (BasicBlock *BB : NewBlocks) {
     for (Instruction &I : *BB) {
       RemapInstruction(&I, VMap,
                        RF_NoModuleLevelChanges | RF_IgnoreMissingEntries);
     }
   }
 
-  // Connect the prolog code to the original loop and update the
+  if (UseEpilogRemainder) {
+    // Connect the epilog code to the original loop and update the
     // PHI functions.
-  BasicBlock *LastLoopBB = cast<BasicBlock>(VMap[Latch]);
-  ConnectProlog(L, BECount, Count, LastLoopBB, PEnd, PH, NewPH, VMap, DT, LI,
+    ConnectEpilog(L, ModVal, NewExit, Exit, PreHeader,
+                  EpilogPreHeader, NewPreHeader, VMap, DT, LI,
                   PreserveLCSSA);
+
+    // Update counter in loop for unrolling.
+    // I should be multiply of Count.
+    IRBuilder<> B2(NewPreHeader->getTerminator());
+    Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
+    BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
+    B2.SetInsertPoint(LatchBR);
+    PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
+                                      Header->getFirstNonPHI());
+    Value *IdxSub =
+        B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
+                     NewIdx->getName() + ".nsub");
+    Value *IdxCmp;
+    if (LatchBR->getSuccessor(0) == Header)
+      IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
+    else
+      IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
+    NewIdx->addIncoming(TestVal, NewPreHeader);
+    NewIdx->addIncoming(IdxSub, Latch);
+    LatchBR->setCondition(IdxCmp);
+  } else {
+    // Connect the prolog code to the original loop and update the
+    // PHI functions.
+    ConnectProlog(L, BECount, Count, PrologExit, PreHeader, NewPreHeader,
+                  VMap, DT, LI, PreserveLCSSA);
+  }
   NumRuntimeUnrolled++;
   return true;
 }

llvm/trunk/test/Transforms/LoopUnroll/AArch64/runtime-loop.ll

-; RUN: opt < %s -S -loop-unroll -mtriple aarch64 -mcpu=cortex-a57 | FileCheck %s
+; RUN: opt < %s -S -loop-unroll -mtriple aarch64 -mcpu=cortex-a57 | FileCheck %s -check-prefix=EPILOG
+; RUN: opt < %s -S -loop-unroll -mtriple aarch64 -mcpu=cortex-a57 -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 
 ; Tests for unrolling loops with run-time trip counts
 
-; CHECK:  %xtraiter = and i32 %n
-; CHECK:  %lcmp.mod = icmp ne i32 %xtraiter, 0
-; CHECK:  br i1 %lcmp.mod, label %for.body.prol, label %for.body.preheader.split
+; EPILOG:  %xtraiter = and i32 %n
+; EPILOG:  %lcmp.mod = icmp ne i32 %xtraiter, %n
+; EPILOG:  br i1 %lcmp.mod, label %for.body.preheader.new, label %for.end.loopexit.unr-lcssa
+
+; PROLOG:  %xtraiter = and i32 %n
+; PROLOG:  %lcmp.mod = icmp ne i32 %xtraiter, 0
+; PROLOG:  br i1 %lcmp.mod, label %for.body.prol.preheader, label %for.body.prol.loopexit
 
-; CHECK:  for.body.prol:
-; CHECK:  for.body:
+; EPILOG:  for.body:
+; EPILOG:  for.body.epil:
+
+; PROLOG:  for.body.prol:
+; PROLOG:  for.body:
 
 define i32 @test(i32* nocapture %a, i32 %n) nounwind uwtable readonly {
 entry:
   %cmp1 = icmp eq i32 %n, 0
   br i1 %cmp1, label %for.end, label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]

llvm/trunk/test/Transforms/LoopUnroll/PowerPC/a2-unrolling.ll

-; RUN: opt < %s -S -mtriple=powerpc64-unknown-linux-gnu -mcpu=a2 -loop-unroll | FileCheck %s
+; RUN: opt < %s -S -mtriple=powerpc64-unknown-linux-gnu -mcpu=a2 -loop-unroll | FileCheck %s -check-prefix=EPILOG
+; RUN: opt < %s -S -mtriple=powerpc64-unknown-linux-gnu -mcpu=a2 -loop-unroll -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 define void @unroll_opt_for_size() nounwind optsize {
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %inc, %loop ]
   %inc = add i32 %iv, 1
   %exitcnd = icmp uge i32 %inc, 1024
   br i1 %exitcnd, label %exit, label %loop
 
 exit:
   ret void
 }
 
-; CHECK-LABEL: @unroll_opt_for_size
-; CHECK:      add
-; CHECK-NEXT: add
-; CHECK-NEXT: add
-; CHECK: icmp
+; EPILOG-LABEL: @unroll_opt_for_size
+; EPILOG:      add
+; EPILOG-NEXT: add
+; EPILOG-NEXT: add
+; EPILOG: icmp
+
+; PROLOG-LABEL: @unroll_opt_for_size
+; PROLOG:      add
+; PROLOG-NEXT: add
+; PROLOG-NEXT: add
+; PROLOG: icmp
 
 define i32 @test(i32* nocapture %a, i32 %n) nounwind uwtable readonly {
 entry:
   %cmp1 = icmp eq i32 %n, 0
   br i1 %cmp1, label %for.end, label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
   %sum.02 = phi i32 [ %add, %for.body ], [ 0, %entry ]
   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
   %0 = load i32, i32* %arrayidx, align 4
   %add = add nsw i32 %0, %sum.02
   %indvars.iv.next = add i64 %indvars.iv, 1
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
   %exitcond = icmp eq i32 %lftr.wideiv, %n
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   %sum.0.lcssa = phi i32 [ 0, %entry ], [ %add, %for.body ]
   ret i32 %sum.0.lcssa
 }
 
-; CHECK-LABEL: @test
-; CHECK: for.body.prol{{.*}}:
-; CHECK: for.body:
-; CHECK: br i1 %exitcond.7, label %for.end.loopexit{{.*}}, label %for.body
+; EPILOG-LABEL: @test
+; EPILOG: for.body:
+; EPILOG: br i1 %niter.ncmp.7, label %for.end.loopexit{{.*}}, label %for.body
+; EPILOG: for.body.epil{{.*}}:
+
+; PROLOG-LABEL: @test
+; PROLOG: for.body.prol{{.*}}:
+; PROLOG: for.body:
+; PROLOG: br i1 %exitcond.7, label %for.end.loopexit{{.*}}, label %for.body
 

llvm/trunk/test/Transforms/LoopUnroll/X86/mmx.ll

 ; RUN: opt < %s -S -loop-unroll | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define x86_mmx @f() #0 {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %phi = phi i32 [ 1, %entry ], [ %add, %for.body ]
   %add = add i32 %phi, 1
   %cmp = icmp eq i32 %phi, 0
   br i1 %cmp, label %exit, label %for.body
 
 exit:                                             ; preds = %for.body
   %ret = phi x86_mmx [ undef, %for.body ]
-  ; CHECK: %[[ret_unr:.*]] = phi x86_mmx [ undef,
-  ; CHECK: %[[ret_ph:.*]]  = phi x86_mmx [ undef,
-  ; CHECK: %[[ret:.*]] = phi x86_mmx [ %[[ret_unr]], {{.*}} ], [ %[[ret_ph]]
+  ; CHECK: %[[ret_ph:.*]] = phi x86_mmx [ undef, %entry
+  ; CHECK: %[[ret_ph1:.*]]  = phi x86_mmx [ undef,
+  ; CHECK: %[[ret:.*]] = phi x86_mmx [ %[[ret_ph]], {{.*}} ], [ %[[ret_ph1]],
   ; CHECK: ret x86_mmx %[[ret]]
   ret x86_mmx %ret
 }
 
 attributes #0 = { "target-cpu"="x86-64" }

llvm/trunk/test/Transforms/LoopUnroll/high-cost-trip-count-computation.ll

 ;; exists in the code and we don't need to expand it once more.
 ;; Thus, it shouldn't prevent us from unrolling the loop.
 
 define i32 @test2(i64* %loc, i64 %conv7) {
 ; CHECK-LABEL: @test2(
 ; CHECK: udiv
 ; CHECK: udiv
 ; CHECK-NOT: udiv
-; CHECK-LABEL: for.body.prol
+; CHECK-LABEL: for.body
 entry:
   %rem0 = load i64, i64* %loc, align 8
   %ExpensiveComputation = udiv i64 %rem0, 42 ; <<< Extra computations are added to the trip-count expression
   br label %bb1
 bb1:
   %div11 = udiv i64 %ExpensiveComputation, %conv7
   %cmp.i38 = icmp ugt i64 %div11, 1
   %div12 = select i1 %cmp.i38, i64 %div11, i64 1

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

-; RUN: opt < %s -S -loop-unroll -unroll-runtime=true | FileCheck %s
+; RUN: opt < %s -S -loop-unroll -unroll-runtime=true | FileCheck %s -check-prefix=EPILOG
+; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 ; Tests for unrolling loops with run-time trip counts
 
-; CHECK: %xtraiter = and i32 %n
-; CHECK:  %lcmp.mod = icmp ne i32 %xtraiter, 0
-; CHECK:  br i1 %lcmp.mod, label %for.body.prol, label %for.body.preheader.split
-
-; CHECK: for.body.prol:
-; CHECK: %indvars.iv.prol = phi i64 [ %indvars.iv.next.prol, %for.body.prol ], [ 0, %for.body.preheader ]
-; CHECK:  %prol.iter.sub = sub i32 %prol.iter, 1
-; CHECK:  %prol.iter.cmp = icmp ne i32 %prol.iter.sub, 0
-; CHECK:  br i1 %prol.iter.cmp, label %for.body.prol, label %for.body.preheader.split, !llvm.loop !0
+; EPILOG: %xtraiter = and i32 %n
+; EPILOG:  %lcmp.mod = icmp ne i32 %xtraiter, %n
+; EPILOG:  br i1 %lcmp.mod, label %for.body.preheader.new, label %for.end.loopexit.unr-lcssa
+
+; PROLOG: %xtraiter = and i32 %n
+; PROLOG:  %lcmp.mod = icmp ne i32 %xtraiter, 0
+; PROLOG:  br i1 %lcmp.mod, label %for.body.prol.preheader, label %for.body.prol.loopexit
+
+; EPILOG: for.body.epil:
+; EPILOG: %indvars.iv.epil = phi i64 [ %indvars.iv.next.epil, %for.body.epil ],  [ %indvars.iv.unr, %for.body.epil.preheader ]
+; EPILOG:  %epil.iter.sub = sub i32 %epil.iter, 1
+; EPILOG:  %epil.iter.cmp = icmp ne i32 %epil.iter.sub, 0
+; EPILOG:  br i1 %epil.iter.cmp, label %for.body.epil, label %for.end.loopexit.epilog-lcssa, !llvm.loop !0
+
+; PROLOG: for.body.prol:
+; PROLOG: %indvars.iv.prol = phi i64 [ %indvars.iv.next.prol, %for.body.prol ], [ 0, %for.body.prol.preheader ]
+; PROLOG:  %prol.iter.sub = sub i32 %prol.iter, 1
+; PROLOG:  %prol.iter.cmp = icmp ne i32 %prol.iter.sub, 0
+; PROLOG:  br i1 %prol.iter.cmp, label %for.body.prol, label %for.body.prol.loopexit, !llvm.loop !0
+
 
 define i32 @test(i32* nocapture %a, i32 %n) nounwind uwtable readonly {
 entry:
   %cmp1 = icmp eq i32 %n, 0
   br i1 %cmp1, label %for.end, label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
for.end:                                          ; preds = %for.body, %entry
   %sum.0.lcssa = phi i32 [ 0, %entry ], [ %add, %for.body ]
   ret i32 %sum.0.lcssa
 }
 
 
 ; Still try to completely unroll loops with compile-time trip counts
 ; even if the -unroll-runtime is specified
 
-; CHECK: for.body:
-; CHECK-NOT: for.body.prol:
+; EPILOG: for.body:
+; EPILOG-NOT: for.body.epil:
+
+; PROLOG: for.body:
+; PROLOG-NOT: for.body.prol:
 
 define i32 @test1(i32* nocapture %a) nounwind uwtable readonly {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
   %sum.01 = phi i32 [ 0, %entry ], [ %add, %for.body ]
   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
   %0 = load i32, i32* %arrayidx, align 4
   %add = add nsw i32 %0, %sum.01
   %indvars.iv.next = add i64 %indvars.iv, 1
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
   %exitcond = icmp eq i32 %lftr.wideiv, 5
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret i32 %add
 }
 
 ; This is test 2007-05-09-UnknownTripCount.ll which can be unrolled now
 ; if the -unroll-runtime option is turned on
 
-; CHECK: bb72.2:
+; EPILOG: bb72.2:
+; PROLOG: bb72.2:
 
 define void @foo(i32 %trips) {
 entry:
         br label %cond_true.outer
 
 cond_true.outer:
         %indvar1.ph = phi i32 [ 0, %entry ], [ %indvar.next2, %bb72 ]
         br label %bb72
 
 bb72:
         %indvar.next2 = add i32 %indvar1.ph, 1
         %exitcond3 = icmp eq i32 %indvar.next2, %trips
         br i1 %exitcond3, label %cond_true138, label %cond_true.outer
 
 cond_true138:
         ret void
 }
 
 
 ; Test run-time unrolling for a loop that counts down by -2.
 
-; CHECK: for.body.prol:
-; CHECK: br i1 %prol.iter.cmp, label %for.body.prol, label %for.body.preheader.split
+; EPILOG: for.body.epil:
+; EPILOG: br i1 %epil.iter.cmp, label %for.body.epil, label %for.cond.for.end_crit_edge.epilog-lcssa
+
+; PROLOG: for.body.prol:
+; PROLOG: br i1 %prol.iter.cmp, label %for.body.prol, label %for.body.prol.loopexit
 
 define zeroext i16 @down(i16* nocapture %p, i32 %len) nounwind uwtable readonly {
 entry:
   %cmp2 = icmp eq i32 %len, 0
   br i1 %cmp2, label %for.end, label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %p.addr.05 = phi i16* [ %incdec.ptr, %for.body ], [ %p, %entry ]
for.cond.for.end_crit_edge:                       ; preds = %for.body
   br label %for.end
 
 for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
   %res.0.lcssa = phi i16 [ %phitmp, %for.cond.for.end_crit_edge ], [ 0, %entry ]
   ret i16 %res.0.lcssa
 }
 
 ; Test run-time unrolling disable metadata.
-; CHECK: for.body:
-; CHECK-NOT: for.body.prol:
+; EPILOG: for.body:
+; EPILOG-NOT: for.body.epil:
+
+; PROLOG: for.body:
+; PROLOG-NOT: for.body.prol:
 
 define zeroext i16 @test2(i16* nocapture %p, i32 %len) nounwind uwtable readonly {
 entry:
   %cmp2 = icmp eq i32 %len, 0
   br i1 %cmp2, label %for.end, label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %p.addr.05 = phi i16* [ %incdec.ptr, %for.body ], [ %p, %entry ]

 for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
   %res.0.lcssa = phi i16 [ %phitmp, %for.cond.for.end_crit_edge ], [ 0, %entry ]
   ret i16 %res.0.lcssa
 }
 
 !0 = distinct !{!0, !1}
 !1 = !{!"llvm.loop.unroll.runtime.disable"}
 
-; CHECK: !0 = distinct !{!0, !1}
-; CHECK: !1 = !{!"llvm.loop.unroll.disable"}
+; EPILOG: !0 = distinct !{!0, !1}
+; EPILOG: !1 = !{!"llvm.loop.unroll.disable"}
 
+; PROLOG: !0 = distinct !{!0, !1}
+; PROLOG: !1 = !{!"llvm.loop.unroll.disable"}

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

-; RUN: opt < %s -S -loop-unroll -unroll-runtime -unroll-count=2 | FileCheck %s
+; RUN: opt < %s -S -loop-unroll -unroll-runtime -unroll-count=2 | FileCheck %s -check-prefix=EPILOG
+; RUN: opt < %s -S -loop-unroll -unroll-runtime -unroll-count=2 -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 
 ; This tests that setting the unroll count works
 
-; CHECK: for.body.preheader:
-; CHECK:   br {{.*}} label %for.body.prol, label %for.body.preheader.split, !dbg [[PH_LOC:![0-9]+]]
-; CHECK: for.body.prol:
-; CHECK:   br label %for.body.preheader.split, !dbg [[BODY_LOC:![0-9]+]]
-; CHECK: for.body.preheader.split:
-; CHECK:   br {{.*}} label %for.end.loopexit, label %for.body.preheader.split.split, !dbg [[PH_LOC]]
-; CHECK: for.body:
-; CHECK:   br i1 %exitcond.1, label %for.end.loopexit.unr-lcssa, label %for.body, !dbg [[BODY_LOC]]
-; CHECK-NOT: br i1 %exitcond.4, label %for.end.loopexit{{.*}}, label %for.body
 
-; CHECK-DAG: [[PH_LOC]] = !DILocation(line: 101, column: 1, scope: !{{.*}})
-; CHECK-DAG: [[BODY_LOC]] = !DILocation(line: 102, column: 1, scope: !{{.*}})
+; EPILOG: for.body.preheader:
+; EPILOG:   br i1 %lcmp.mod, label %for.body.preheader.new, label %for.end.loopexit.unr-lcssa, !dbg [[PH_LOC:![0-9]+]]
+; EPILOG: for.body:
+; EPILOG:   br i1 %niter.ncmp.1, label %for.end.loopexit.unr-lcssa.loopexit, label %for.body, !dbg [[BODY_LOC:![0-9]+]]
+; EPILOG-NOT: br i1 %niter.ncmp.2, label %for.end.loopexit{{.*}}, label %for.body
+; EPILOG: for.body.epil.preheader:
+; EPILOG:   br label %for.body.epil, !dbg [[EXIT_LOC:![0-9]+]]
+; EPILOG: for.body.epil:
+; EPILOG:   br label %for.end.loopexit.epilog-lcssa, !dbg [[BODY_LOC:![0-9]+]]
+
+; EPILOG-DAG: [[PH_LOC]] = !DILocation(line: 101, column: 1, scope: !{{.*}})
+; EPILOG-DAG: [[BODY_LOC]] = !DILocation(line: 102, column: 1, scope: !{{.*}})
+; EPILOG-DAG: [[EXIT_LOC]] = !DILocation(line: 103, column: 1, scope: !{{.*}})
+
+; PROLOG: for.body.preheader:
+; PROLOG:   br {{.*}} label %for.body.prol.preheader, label %for.body.prol.loopexit, !dbg [[PH_LOC:![0-9]+]]
+; PROLOG: for.body.prol:
+; PROLOG:   br label %for.body.prol.loopexit, !dbg [[BODY_LOC:![0-9]+]]
+; PROLOG: for.body.prol.loopexit:
+; PROLOG:   br {{.*}} label %for.end.loopexit, label %for.body.preheader.new, !dbg [[PH_LOC]]
+; PROLOG: for.body:
+; PROLOG:   br i1 %exitcond.1, label %for.end.loopexit.unr-lcssa, label %for.body, !dbg [[BODY_LOC]]
+; PROLOG-NOT: br i1 %exitcond.4, label %for.end.loopexit{{.*}}, label %for.body
+
+; PROLOG-DAG: [[PH_LOC]] = !DILocation(line: 101, column: 1, scope: !{{.*}})
+; PROLOG-DAG: [[BODY_LOC]] = !DILocation(line: 102, column: 1, scope: !{{.*}})
 
 define i32 @test(i32* nocapture %a, i32 %n) nounwind uwtable readonly !dbg !6 {
 entry:
   %cmp1 = icmp eq i32 %n, 0, !dbg !7
   br i1 %cmp1, label %for.end, label %for.body, !dbg !7
 
 for.body:                                         ; preds = %for.body, %entry
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]

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

-; RUN: opt < %s -S -loop-unroll -unroll-threshold=25 -unroll-runtime -unroll-count=8 | FileCheck %s
+; RUN: opt < %s -S -loop-unroll -unroll-threshold=25 -unroll-runtime -unroll-count=8 | FileCheck %s  -check-prefix=EPILOG
+; RUN: opt < %s -S -loop-unroll -unroll-threshold=25 -unroll-runtime -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 
 ; Choose a smaller, power-of-two, unroll count if the loop is too large.
 ; This test makes sure we're not unrolling 'odd' counts
 
-; CHECK: for.body.prol:
-; CHECK: for.body:
-; CHECK: br i1 %exitcond.3, label %for.end.loopexit{{.*}}, label %for.body
-; CHECK-NOT: br i1 %exitcond.4, label %for.end.loopexit{{.*}}, label %for.body
+; EPILOG: for.body:
+; EPILOG: br i1 %niter.ncmp.3, label %for.end.loopexit.unr-lcssa.loopexit{{.*}}, label %for.body
+; EPILOG-NOT: br i1 %niter.ncmp.4, label %for.end.loopexit.unr-lcssa.loopexit{{.*}}, label %for.body
+; EPILOG: for.body.epil:
+
+; PROLOG: for.body.prol:
+; PROLOG: for.body:
+; PROLOG: br i1 %exitcond.3, label %for.end.loopexit{{.*}}, label %for.body
+; PROLOG-NOT: br i1 %exitcond.4, label %for.end.loopexit{{.*}}, label %for.body
 
 define i32 @test(i32* nocapture %a, i32 %n) nounwind uwtable readonly {
 entry:
   %cmp1 = icmp eq i32 %n, 0
   br i1 %cmp1, label %for.end, label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]

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

-; RUN: opt < %s -S -O2 -unroll-runtime=true | FileCheck %s
+; RUN: opt < %s -S -O2 -unroll-runtime=true | FileCheck %s -check-prefix=EPILOG
+; RUN: opt < %s -S -O2 -unroll-runtime=true -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 
 ; Check runtime unrolling prologue can be promoted by LICM pass.
 
-; CHECK: entry:
-; CHECK: %xtraiter
-; CHECK: %lcmp.mod
-; CHECK: loop1:
-; CHECK: br i1 %lcmp.mod
-; CHECK: loop2.prol:
+; EPILOG: entry:
+; EPILOG: %xtraiter
+; EPILOG: %lcmp.mod
+; EPILOG: loop1:
+; EPILOG: br i1 %lcmp.mod
+; EPILOG: loop2.epil:
+
+; PROLOG: entry:
+; PROLOG: %xtraiter
+; PROLOG: %lcmp.mod
+; PROLOG: loop1:
+; PROLOG: br i1 %lcmp.mod
+; PROLOG: loop2.prol:
 
 define void @unroll(i32 %iter, i32* %addr1, i32* %addr2) nounwind {
 entry:
   br label %loop1
 
 loop1:
   %iv1 = phi i32 [ 0, %entry ], [ %inc1, %loop1.latch ]
   %offset1 = getelementptr i32, i32* %addr1, i32 %iv1

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

 ; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-count=16 | FileCheck --check-prefix=UNROLL-16 %s
 ; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-count=4 | FileCheck --check-prefix=UNROLL-4 %s
 
 ; Given that the trip-count of this loop is a 3-bit value, we cannot
 ; safely unroll it with a count of anything more than 8.
 
 define i3 @test(i3* %a, i3 %n) {
 ; UNROLL-16-LABEL: @test(
 ; UNROLL-4-LABEL: @test(
 entry:
   %cmp1 = icmp eq i3 %n, 0
   br i1 %cmp1, label %for.end, label %for.body
 
-; UNROLL-16-NOT: for.body.prol:
-; UNROLL-4: for.body.prol:
-
 for.body:                                         ; preds = %for.body, %entry
 ; UNROLL-16-LABEL: for.body:
 ; UNROLL-4-LABEL: for.body:
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
   %sum.02 = phi i3 [ %add, %for.body ], [ 0, %entry ]
   %arrayidx = getelementptr inbounds i3, i3* %a, i64 %indvars.iv
 
 ; UNROLL-16-LABEL: for.body
; UNROLL-4-LABEL: getelementptr
   %add = add nsw i3 %0, %sum.02
   %indvars.iv.next = add i64 %indvars.iv, 1
   %lftr.wideiv = trunc i64 %indvars.iv.next to i3
   %exitcond = icmp eq i3 %lftr.wideiv, %n
   br i1 %exitcond, label %for.end, label %for.body
 
 ; UNROLL-16-LABEL: for.end
 ; UNROLL-4-LABEL: for.end
+
+; UNROLL-16-NOT: for.body.epil:
+; UNROLL-4: for.body.epil:
+
 for.end:                                          ; preds = %for.body, %entry
   %sum.0.lcssa = phi i3 [ 0, %entry ], [ %add, %for.body ]
   ret i3 %sum.0.lcssa
 }

llvm/trunk/test/Transforms/LoopUnroll/tripcount-overflow.ll

 ; RUN: opt < %s -S -unroll-runtime -unroll-count=2 -loop-unroll | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 ; This test case documents how runtime loop unrolling handles the case
 ; when the backedge-count is -1.
 
 ; If %N, the backedge-taken count, is -1 then %0 unsigned-overflows
 ; and is 0.  %xtraiter too is 0, signifying that the total trip-count
 ; is divisible by 2.  The prologue then branches to the unrolled loop
 ; and executes the 2^32 iterations there, in groups of 2.
 
 
 ; CHECK: entry:
 ; CHECK-NEXT: %0 = add i32 %N, 1
 ; CHECK-NEXT: %xtraiter = and i32 %0, 1
-; CHECK-NEXT: %lcmp.mod = icmp ne i32 %xtraiter, 0
-; CHECK-NEXT: br i1 %lcmp.mod, label %while.body.prol, label %entry.split
+; CHECK-NEXT: %lcmp.mod = icmp ne i32 %xtraiter, %0
+; CHECK-NEXT: br i1 %lcmp.mod, label %entry.new, label %while.end.unr-lcssa
 
-; CHECK: while.body.prol:
-; CHECK: br label %entry.split
+; CHECK: while.body.epil:
+; CHECK: br label %while.end.epilog-lcssa
 
-; CHECK: entry.split:
+; CHECK: while.end.epilog-lcssa:
 
 ; Function Attrs: nounwind readnone ssp uwtable
 define i32 @foo(i32 %N) {
 entry:
   br label %while.body
 
 while.body:                                       ; preds = %while.body, %entry
   %i = phi i32 [ 0, %entry ], [ %inc, %while.body ]
   %cmp = icmp eq i32 %i, %N
   %inc = add i32 %i, 1
   br i1 %cmp, label %while.end, label %while.body
 
 while.end:                                        ; preds = %while.body
   ret i32 %i
 }

llvm/trunk/test/Transforms/LoopUnroll/unroll-cleanup.ll

 ; PR23524
 ; The test is to check redundency produced by loop unroll pass
 ; should be cleaned up by later pass.
 ; RUN: opt < %s -O2 -S | FileCheck %s
 
 ; After loop unroll:
-;       %dec18 = add nsw i32 %dec18.in, -1
+;       %niter.nsub = add nsw i32 %niter, -1
 ;       ...
-;       %dec18.1 = add nsw i32 %dec18, -1
+;       %niter.nsub.1 = add nsw i32 %niter.nsub, -1
 ; should be merged to:
-;       %dec18.1 = add nsw i32 %dec18.in, -2
+;       %dec18.1 = add nsw i32 %niter, -2
 ;
 ; CHECK-LABEL: @_Z3fn1v(
-; CHECK: %dec18.1 = add nsw i32 %dec18.in, -2
+; CHECK: %niter.nsub.1 = add i32 %niter, -2
 
 ; ModuleID = '<stdin>'
 target triple = "x86_64-unknown-linux-gnu"
 
 @b = global i32 0, align 4
 @c = global i32 0, align 4
 
 ; Function Attrs: nounwind uwtable

llvm/trunk/test/Transforms/LoopUnroll/unroll-pragmas.ll

 }
 !8 = !{!8, !4}
 
 ; #pragma clang loop unroll_count(4)
 ; Loop has a runtime trip count.  Runtime unrolling should occur and loop
 ; should be duplicated (original and 4x unrolled).
 ;
 ; CHECK-LABEL: @runtime_loop_with_count4(
-; CHECK: for.body.prol:
-; CHECK: store
-; CHECK-NOT: store
-; CHECK: br i1
 ; CHECK: for.body
 ; CHECK: store
 ; CHECK: store
 ; CHECK: store
 ; CHECK: store
 ; CHECK-NOT: store
 ; CHECK: br i1
+; CHECK: for.body.epil:
+; CHECK: store
+; CHECK-NOT: store
+; CHECK: br i1
 define void @runtime_loop_with_count4(i32* nocapture %a, i32 %b) {
 entry:
   %cmp3 = icmp sgt i32 %b, 0
   br i1 %cmp3, label %for.body, label %for.end, !llvm.loop !9
 
 for.body:                                         ; preds = %entry, %for.body
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv

 !13 = !{!13, !14}
 !14 = !{!"llvm.loop.unroll.enable"}
 
 ; #pragma clang loop unroll(enable)
 ; Loop has a runtime trip count and should be runtime unrolled and duplicated
 ; (original and 8x).
 ;
 ; CHECK-LABEL: @runtime_loop_with_enable(
-; CHECK: for.body.prol:
-; CHECK: store
-; CHECK-NOT: store
-; CHECK: br i1
 ; CHECK: for.body:
 ; CHECK: store i32
 ; CHECK: store i32
 ; CHECK: store i32
 ; CHECK: store i32
 ; CHECK: store i32
 ; CHECK: store i32
 ; CHECK: store i32
 ; CHECK: store i32
 ; CHECK-NOT: store i32
 ; CHECK: br i1
+; CHECK: for.body.epil:
+; CHECK: store
+; CHECK-NOT: store
+; CHECK: br i1
 define void @runtime_loop_with_enable(i32* nocapture %a, i32 %b) {
 entry:
   %cmp3 = icmp sgt i32 %b, 0
   br i1 %cmp3, label %for.body, label %for.end, !llvm.loop !8
 
 for.body:                                         ; preds = %entry, %for.body
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv

 }
 !15 = !{!15, !14}
 
 ; #pragma clang loop unroll_count(3)
 ; Loop has a runtime trip count.  Runtime unrolling should occur and loop
 ; should be duplicated (original and 3x unrolled).
 ;
 ; CHECK-LABEL: @runtime_loop_with_count3(
-; CHECK: for.body.prol:
-; CHECK: store
-; CHECK-NOT: store
-; CHECK: br i1
 ; CHECK: for.body
 ; CHECK: store
 ; CHECK: store
 ; CHECK: store
 ; CHECK-NOT: store
 ; CHECK: br i1
+; CHECK: for.body.epil:
+; CHECK: store
+; CHECK-NOT: store
+; CHECK: br i1
 define void @runtime_loop_with_count3(i32* nocapture %a, i32 %b) {
 entry:
   %cmp3 = icmp sgt i32 %b, 0
   br i1 %cmp3, label %for.body, label %for.end, !llvm.loop !16
 
 for.body:                                         ; preds = %entry, %for.body
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv