lib/Transforms/Utils/LoopUnrollRuntime.cpp

   1 //===-- UnrollLoopRuntime.cpp - Runtime Loop unrolling utilities ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements some loop unrolling utilities for loops with run-time
  11 // trip counts.  See LoopUnroll.cpp for unrolling loops with compile-time
  12 // trip counts.
  13 //
  14 // The functions in this file are used to generate extra code when the
  15 // run-time trip count modulo the unroll factor is not 0.  When this is the
  16 // case, we need to generate code to execute these 'left over' iterations.
  17 //
  18 // The current strategy generates an if-then-else sequence prior to the
  19 // unrolled loop to execute the 'left over' iterations before or after the
  20 // unrolled loop.
  21 //
  22 //===----------------------------------------------------------------------===//
  23
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/Analysis/AliasAnalysis.h"
  26 #include "llvm/Analysis/LoopIterator.h"
  27 #include "llvm/Analysis/LoopPass.h"
  28 #include "llvm/Analysis/ScalarEvolution.h"
  29 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  30 #include "llvm/IR/BasicBlock.h"
  31 #include "llvm/IR/Dominators.h"
  32 #include "llvm/IR/Metadata.h"
  33 #include "llvm/IR/Module.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/raw_ostream.h"
  36 #include "llvm/Transforms/Scalar.h"
  37 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  38 #include "llvm/Transforms/Utils/Cloning.h"
  39 #include "llvm/Transforms/Utils/UnrollLoop.h"
  40 #include <algorithm>
  41
  42 using namespace llvm;
  43
  44 #define DEBUG_TYPE "loop-unroll"
  45
  46 STATISTIC(NumRuntimeUnrolled,
  47           "Number of loops unrolled with run-time trip counts");
  48
  49 /// Connect the unrolling prolog code to the original loop.
  50 /// The unrolling prolog code contains code to execute the
  51 /// 'extra' iterations if the run-time trip count modulo the
  52 /// unroll count is non-zero.
  53 ///
  54 /// This function performs the following:
  55 /// - Create PHI nodes at prolog end block to combine values
  56 ///   that exit the prolog code and jump around the prolog.
  57 /// - Add a PHI operand to a PHI node at the loop exit block
  58 ///   for values that exit the prolog and go around the loop.
  59 /// - Branch around the original loop if the trip count is less
  60 ///   than the unroll factor.
  61 ///
  62 static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
  63                           BasicBlock *PrologExit, BasicBlock *PreHeader,
  64                           BasicBlock *NewPreHeader, ValueToValueMapTy &VMap,
  65                           DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA) {
  66   BasicBlock *Latch = L->getLoopLatch();
  67   assert(Latch && "Loop must have a latch");
  68   BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);
  69
  70   // Create a PHI node for each outgoing value from the original loop
  71   // (which means it is an outgoing value from the prolog code too).
  72   // The new PHI node is inserted in the prolog end basic block.
  73   // The new PHI node value is added as an operand of a PHI node in either
  74   // the loop header or the loop exit block.
  75   for (BasicBlock *Succ : successors(Latch)) {
  76     for (Instruction &BBI : *Succ) {
  77       PHINode *PN = dyn_cast<PHINode>(&BBI);
  78       // Exit when we passed all PHI nodes.
  79       if (!PN)
  80         break;
  81       // Add a new PHI node to the prolog end block and add the
  82       // appropriate incoming values.
  83       PHINode *NewPN = PHINode::Create(PN->getType(), 2, PN->getName() + ".unr",
  84                                        PrologExit->getFirstNonPHI());
  85       // Adding a value to the new PHI node from the original loop preheader.
  86       // This is the value that skips all the prolog code.
  87       if (L->contains(PN)) {
  88         NewPN->addIncoming(PN->getIncomingValueForBlock(NewPreHeader),
  89                            PreHeader);
  90       } else {
  91         NewPN->addIncoming(UndefValue::get(PN->getType()), PreHeader);
  92       }
  93
  94       Value *V = PN->getIncomingValueForBlock(Latch);
  95       if (Instruction *I = dyn_cast<Instruction>(V)) {
  96         if (L->contains(I)) {
  97           V = VMap.lookup(I);
  98         }
  99       }
 100       // Adding a value to the new PHI node from the last prolog block
 101       // that was created.
 102       NewPN->addIncoming(V, PrologLatch);
 103
 104       // Update the existing PHI node operand with the value from the
 105       // new PHI node.  How this is done depends on if the existing
 106       // PHI node is in the original loop block, or the exit block.
 107       if (L->contains(PN)) {
 108         PN->setIncomingValue(PN->getBasicBlockIndex(NewPreHeader), NewPN);
 109       } else {
 110         PN->addIncoming(NewPN, PrologExit);
 111       }
 112     }
 113   }
 114
 115   // Make sure that created prolog loop is in simplified form
 116   SmallVector<BasicBlock *, 4> PrologExitPreds;
 117   Loop *PrologLoop = LI->getLoopFor(PrologLatch);
 118   if (PrologLoop) {
 119     for (BasicBlock *PredBB : predecessors(PrologExit))
 120       if (PrologLoop->contains(PredBB))
 121         PrologExitPreds.push_back(PredBB);
 122
 123     SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI,
 124                            PreserveLCSSA);
 125   }
 126
 127   // Create a branch around the original loop, which is taken if there are no
 128   // iterations remaining to be executed after running the prologue.
 129   Instruction *InsertPt = PrologExit->getTerminator();
 130   IRBuilder<> B(InsertPt);
 131
 132   assert(Count != 0 && "nonsensical Count!");
 133
 134   // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)
 135   // This means %xtraiter is (BECount + 1) and all of the iterations of this
 136   // loop were executed by the prologue.  Note that if BECount <u (Count - 1)
 137   // then (BECount + 1) cannot unsigned-overflow.
 138   Value *BrLoopExit =
 139       B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1));
 140   BasicBlock *Exit = L->getUniqueExitBlock();
 141   assert(Exit && "Loop must have a single exit block only");
 142   // Split the exit to maintain loop canonicalization guarantees
 143   SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
 144   SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", DT, LI,
 145                          PreserveLCSSA);
 146   // Add the branch to the exit block (around the unrolled loop)
 147   B.CreateCondBr(BrLoopExit, Exit, NewPreHeader);
 148   InsertPt->eraseFromParent();
 149   if (DT)
 150     DT->changeImmediateDominator(Exit, PrologExit);
 151 }
 152
 153 /// Connect the unrolling epilog code to the original loop.
 154 /// The unrolling epilog code contains code to execute the
 155 /// 'extra' iterations if the run-time trip count modulo the
 156 /// unroll count is non-zero.
 157 ///
 158 /// This function performs the following:
 159 /// - Update PHI nodes at the unrolling loop exit and epilog loop exit
 160 /// - Create PHI nodes at the unrolling loop exit to combine
 161 ///   values that exit the unrolling loop code and jump around it.
 162 /// - Update PHI operands in the epilog loop by the new PHI nodes
 163 /// - Branch around the epilog loop if extra iters (ModVal) is zero.
 164 ///
 165 static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,
 166                           BasicBlock *Exit, BasicBlock *PreHeader,
 167                           BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader,
 168                           ValueToValueMapTy &VMap, DominatorTree *DT,
 169                           LoopInfo *LI, bool PreserveLCSSA)  {
 170   BasicBlock *Latch = L->getLoopLatch();
 171   assert(Latch && "Loop must have a latch");
 172   BasicBlock *EpilogLatch = cast<BasicBlock>(VMap[Latch]);
 173
 174   // Loop structure should be the following:
 175   //
 176   // PreHeader
 177   // NewPreHeader
 178   //   Header
 179   //   ...
 180   //   Latch
 181   // NewExit (PN)
 182   // EpilogPreHeader
 183   //   EpilogHeader
 184   //   ...
 185   //   EpilogLatch
 186   // Exit (EpilogPN)
 187
 188   // Update PHI nodes at NewExit and Exit.
 189   for (Instruction &BBI : *NewExit) {
 190     PHINode *PN = dyn_cast<PHINode>(&BBI);
 191     // Exit when we passed all PHI nodes.
 192     if (!PN)
 193       break;
 194     // PN should be used in another PHI located in Exit block as
 195     // Exit was split by SplitBlockPredecessors into Exit and NewExit
 196     // Basicaly it should look like:
 197     // NewExit:
 198     //   PN = PHI [I, Latch]
 199     // ...
 200     // Exit:
 201     //   EpilogPN = PHI [PN, EpilogPreHeader]
 202     //
 203     // There is EpilogPreHeader incoming block instead of NewExit as
 204     // NewExit was spilt 1 more time to get EpilogPreHeader.
 205     assert(PN->hasOneUse() && "The phi should have 1 use");
 206     PHINode *EpilogPN = cast<PHINode> (PN->use_begin()->getUser());
 207     assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block");
 208
 209     // Add incoming PreHeader from branch around the Loop
 210     PN->addIncoming(UndefValue::get(PN->getType()), PreHeader);
 211
 212     Value *V = PN->getIncomingValueForBlock(Latch);
 213     Instruction *I = dyn_cast<Instruction>(V);
 214     if (I && L->contains(I))
 215       // If value comes from an instruction in the loop add VMap value.
 216       V = VMap.lookup(I);
 217     // For the instruction out of the loop, constant or undefined value
 218     // insert value itself.
 219     EpilogPN->addIncoming(V, EpilogLatch);
 220
 221     assert(EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 &&
 222           "EpilogPN should have EpilogPreHeader incoming block");
 223     // Change EpilogPreHeader incoming block to NewExit.
 224     EpilogPN->setIncomingBlock(EpilogPN->getBasicBlockIndex(EpilogPreHeader),
 225                                NewExit);
 226     // Now PHIs should look like:
 227     // NewExit:
 228     //   PN = PHI [I, Latch], [undef, PreHeader]
 229     // ...
 230     // Exit:
 231     //   EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]
 232   }
 233
 234   // Create PHI nodes at NewExit (from the unrolling loop Latch and PreHeader).
 235   // Update corresponding PHI nodes in epilog loop.
 236   for (BasicBlock *Succ : successors(Latch)) {
 237     // Skip this as we already updated phis in exit blocks.
 238     if (!L->contains(Succ))
 239       continue;
 240     for (Instruction &BBI : *Succ) {
 241       PHINode *PN = dyn_cast<PHINode>(&BBI);
 242       // Exit when we passed all PHI nodes.
 243       if (!PN)
 244         break;
 245       // Add new PHI nodes to the loop exit block and update epilog
 246       // PHIs with the new PHI values.
 247       PHINode *NewPN = PHINode::Create(PN->getType(), 2, PN->getName() + ".unr",
 248                                        NewExit->getFirstNonPHI());
 249       // Adding a value to the new PHI node from the unrolling loop preheader.
 250       NewPN->addIncoming(PN->getIncomingValueForBlock(NewPreHeader), PreHeader);
 251       // Adding a value to the new PHI node from the unrolling loop latch.
 252       NewPN->addIncoming(PN->getIncomingValueForBlock(Latch), Latch);
 253
 254       // Update the existing PHI node operand with the value from the new PHI
 255       // node.  Corresponding instruction in epilog loop should be PHI.
 256       PHINode *VPN = cast<PHINode>(VMap[&BBI]);
 257       VPN->setIncomingValue(VPN->getBasicBlockIndex(EpilogPreHeader), NewPN);
 258     }
 259   }
 260
 261   Instruction *InsertPt = NewExit->getTerminator();
 262   IRBuilder<> B(InsertPt);
 263   Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");
 264   assert(Exit && "Loop must have a single exit block only");
 265   // Split the epilogue exit to maintain loop canonicalization guarantees
 266   SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
 267   SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI,
 268                          PreserveLCSSA);
 269   // Add the branch to the exit block (around the unrolling loop)
 270   B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
 271   InsertPt->eraseFromParent();
 272   if (DT)
 273     DT->changeImmediateDominator(Exit, NewExit);
 274
 275   // Split the main loop exit to maintain canonicalization guarantees.
 276   SmallVector<BasicBlock*, 4> NewExitPreds{Latch};
 277   SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI,
 278                          PreserveLCSSA);
 279 }
 280
 281 /// Create a clone of the blocks in a loop and connect them together.
 282 /// If CreateRemainderLoop is false, loop structure will not be cloned,
 283 /// otherwise a new loop will be created including all cloned blocks, and the
 284 /// iterator of it switches to count NewIter down to 0.
 285 /// The cloned blocks should be inserted between InsertTop and InsertBot.
 286 /// If loop structure is cloned InsertTop should be new preheader, InsertBot
 287 /// new loop exit.
 288 ///
 289 static void CloneLoopBlocks(Loop *L, Value *NewIter,
 290                             const bool CreateRemainderLoop,
 291                             const bool UseEpilogRemainder,
 292                             BasicBlock *InsertTop, BasicBlock *InsertBot,
 293                             BasicBlock *Preheader,
 294                             std::vector<BasicBlock *> &NewBlocks,
 295                             LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap,
 296                             DominatorTree *DT, LoopInfo *LI) {
 297   StringRef suffix = UseEpilogRemainder ? "epil" : "prol";
 298   BasicBlock *Header = L->getHeader();
 299   BasicBlock *Latch = L->getLoopLatch();
 300   Function *F = Header->getParent();
 301   LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
 302   LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
 303   Loop *ParentLoop = L->getParentLoop();
 304   NewLoopsMap NewLoops;
 305   NewLoops[ParentLoop] = ParentLoop;
 306   if (!CreateRemainderLoop)
 307     NewLoops[L] = ParentLoop;
 308
 309   // For each block in the original loop, create a new copy,
 310   // and update the value map with the newly created values.
 311   for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
 312     BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, "." + suffix, F);
 313     NewBlocks.push_back(NewBB);
 314
 315     // If we're unrolling the outermost loop, there's no remainder loop,
 316     // and this block isn't in a nested loop, then the new block is not
 317     // in any loop. Otherwise, add it to loopinfo.
 318     if (CreateRemainderLoop || LI->getLoopFor(*BB) != L || ParentLoop)
 319       addClonedBlockToLoopInfo(*BB, NewBB, LI, NewLoops);
 320
 321     VMap[*BB] = NewBB;
 322     if (Header == *BB) {
 323       // For the first block, add a CFG connection to this newly
 324       // created block.
 325       InsertTop->getTerminator()->setSuccessor(0, NewBB);
 326     }
 327
 328     if (DT) {
 329       if (Header == *BB) {
 330         // The header is dominated by the preheader.
 331         DT->addNewBlock(NewBB, InsertTop);
 332       } else {
 333         // Copy information from original loop to unrolled loop.
 334         BasicBlock *IDomBB = DT->getNode(*BB)->getIDom()->getBlock();
 335         DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDomBB]));
 336       }
 337     }
 338
 339     if (Latch == *BB) {
 340       // For the last block, if CreateRemainderLoop is false, create a direct
 341       // jump to InsertBot. If not, create a loop back to cloned head.
 342       VMap.erase((*BB)->getTerminator());
 343       BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]);
 344       BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());
 345       IRBuilder<> Builder(LatchBR);
 346       if (!CreateRemainderLoop) {
 347         Builder.CreateBr(InsertBot);
 348       } else {
 349         PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2,
 350                                           suffix + ".iter",
 351                                           FirstLoopBB->getFirstNonPHI());
 352         Value *IdxSub =
 353             Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
 354                               NewIdx->getName() + ".sub");
 355         Value *IdxCmp =
 356             Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp");
 357         Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot);
 358         NewIdx->addIncoming(NewIter, InsertTop);
 359         NewIdx->addIncoming(IdxSub, NewBB);
 360       }
 361       LatchBR->eraseFromParent();
 362     }
 363   }
 364
 365   // Change the incoming values to the ones defined in the preheader or
 366   // cloned loop.
 367   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 368     PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
 369     if (!CreateRemainderLoop) {
 370       if (UseEpilogRemainder) {
 371         unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
 372         NewPHI->setIncomingBlock(idx, InsertTop);
 373         NewPHI->removeIncomingValue(Latch, false);
 374       } else {
 375         VMap[&*I] = NewPHI->getIncomingValueForBlock(Preheader);
 376         cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
 377       }
 378     } else {
 379       unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
 380       NewPHI->setIncomingBlock(idx, InsertTop);
 381       BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
 382       idx = NewPHI->getBasicBlockIndex(Latch);
 383       Value *InVal = NewPHI->getIncomingValue(idx);
 384       NewPHI->setIncomingBlock(idx, NewLatch);
 385       if (Value *V = VMap.lookup(InVal))
 386         NewPHI->setIncomingValue(idx, V);
 387     }
 388   }
 389   if (CreateRemainderLoop) {
 390     Loop *NewLoop = NewLoops[L];
 391     assert(NewLoop && "L should have been cloned");
 392     // Add unroll disable metadata to disable future unrolling for this loop.
 393     SmallVector<Metadata *, 4> MDs;
 394     // Reserve first location for self reference to the LoopID metadata node.
 395     MDs.push_back(nullptr);
 396     MDNode *LoopID = NewLoop->getLoopID();
 397     if (LoopID) {
 398       // First remove any existing loop unrolling metadata.
 399       for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
 400         bool IsUnrollMetadata = false;
 401         MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
 402         if (MD) {
 403           const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
 404           IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
 405         }
 406         if (!IsUnrollMetadata)
 407           MDs.push_back(LoopID->getOperand(i));
 408       }
 409     }
 410
 411     LLVMContext &Context = NewLoop->getHeader()->getContext();
 412     SmallVector<Metadata *, 1> DisableOperands;
 413     DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
 414     MDNode *DisableNode = MDNode::get(Context, DisableOperands);
 415     MDs.push_back(DisableNode);
 416
 417     MDNode *NewLoopID = MDNode::get(Context, MDs);
 418     // Set operand 0 to refer to the loop id itself.
 419     NewLoopID->replaceOperandWith(0, NewLoopID);
 420     NewLoop->setLoopID(NewLoopID);
 421   }
 422 }
 423
 424 /// Insert code in the prolog/epilog code when unrolling a loop with a
 425 /// run-time trip-count.
 426 ///
 427 /// This method assumes that the loop unroll factor is total number
 428 /// of loop bodies in the loop after unrolling. (Some folks refer
 429 /// to the unroll factor as the number of *extra* copies added).
 430 /// We assume also that the loop unroll factor is a power-of-two. So, after
 431 /// unrolling the loop, the number of loop bodies executed is 2,
 432 /// 4, 8, etc.  Note - LLVM converts the if-then-sequence to a switch
 433 /// instruction in SimplifyCFG.cpp.  Then, the backend decides how code for
 434 /// the switch instruction is generated.
 435 ///
 436 /// ***Prolog case***
 437 ///        extraiters = tripcount % loopfactor
 438 ///        if (extraiters == 0) jump Loop:
 439 ///        else jump Prol:
 440 /// Prol:  LoopBody;
 441 ///        extraiters -= 1                 // Omitted if unroll factor is 2.
 442 ///        if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
 443 ///        if (tripcount < loopfactor) jump End:
 444 /// Loop:
 445 /// ...
 446 /// End:
 447 ///
 448 /// ***Epilog case***
 449 ///        extraiters = tripcount % loopfactor
 450 ///        if (tripcount < loopfactor) jump LoopExit:
 451 ///        unroll_iters = tripcount - extraiters
 452 /// Loop:  LoopBody; (executes unroll_iter times);
 453 ///        unroll_iter -= 1
 454 ///        if (unroll_iter != 0) jump Loop:
 455 /// LoopExit:
 456 ///        if (extraiters == 0) jump EpilExit:
 457 /// Epil:  LoopBody; (executes extraiters times)
 458 ///        extraiters -= 1                 // Omitted if unroll factor is 2.
 459 ///        if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
 460 /// EpilExit:
 461
 462 bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
 463                                       bool AllowExpensiveTripCount,
 464                                       bool UseEpilogRemainder,
 465                                       LoopInfo *LI, ScalarEvolution *SE,
 466                                       DominatorTree *DT, bool PreserveLCSSA) {
 467   // for now, only unroll loops that contain a single exit
 468   if (!L->getExitingBlock())
 469     return false;
 470
 471   // Make sure the loop is in canonical form, and there is a single
 472   // exit block only.
 473   if (!L->isLoopSimplifyForm())
 474     return false;
 475   BasicBlock *Exit = L->getUniqueExitBlock(); // successor out of loop
 476   if (!Exit)
 477     return false;
 478
 479   // Use Scalar Evolution to compute the trip count. This allows more loops to
 480   // be unrolled than relying on induction var simplification.
 481   if (!SE)
 482     return false;
 483
 484   // Only unroll loops with a computable trip count, and the trip count needs
 485   // to be an int value (allowing a pointer type is a TODO item).
 486   const SCEV *BECountSC = SE->getBackedgeTakenCount(L);
 487   if (isa<SCEVCouldNotCompute>(BECountSC) ||
 488       !BECountSC->getType()->isIntegerTy())
 489     return false;
 490
 491   unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
 492
 493   // Add 1 since the backedge count doesn't include the first loop iteration.
 494   const SCEV *TripCountSC =
 495       SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
 496   if (isa<SCEVCouldNotCompute>(TripCountSC))
 497     return false;
 498
 499   BasicBlock *Header = L->getHeader();
 500   BasicBlock *PreHeader = L->getLoopPreheader();
 501   BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
 502   const DataLayout &DL = Header->getModule()->getDataLayout();
 503   SCEVExpander Expander(*SE, DL, "loop-unroll");
 504   if (!AllowExpensiveTripCount &&
 505       Expander.isHighCostExpansion(TripCountSC, L, PreHeaderBR))
 506     return false;
 507
 508   // This constraint lets us deal with an overflowing trip count easily; see the
 509   // comment on ModVal below.
 510   if (Log2_32(Count) > BEWidth)
 511     return false;
 512
 513   BasicBlock *Latch = L->getLoopLatch();
 514
 515   // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
 516   // targets of the Latch be the single exit block out of the loop. This needs
 517   // to be guaranteed by the callers of UnrollRuntimeLoopRemainder.
 518   BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
 519   assert(
 520       (LatchBR->getSuccessor(0) == Exit || LatchBR->getSuccessor(1) == Exit) &&
 521       "one of the loop latch successors should be "
 522       "the exit block!");
 523   // Avoid warning of unused `LatchBR` variable in release builds.
 524   (void)LatchBR;
 525   // Loop structure is the following:
 526   //
 527   // PreHeader
 528   //   Header
 529   //   ...
 530   //   Latch
 531   // Exit
 532
 533   BasicBlock *NewPreHeader;
 534   BasicBlock *NewExit = nullptr;
 535   BasicBlock *PrologExit = nullptr;
 536   BasicBlock *EpilogPreHeader = nullptr;
 537   BasicBlock *PrologPreHeader = nullptr;
 538
 539   if (UseEpilogRemainder) {
 540     // If epilog remainder
 541     // Split PreHeader to insert a branch around loop for unrolling.
 542     NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
 543     NewPreHeader->setName(PreHeader->getName() + ".new");
 544     // Split Exit to create phi nodes from branch above.
 545     SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
 546     NewExit = SplitBlockPredecessors(Exit, Preds, ".unr-lcssa",
 547                                      DT, LI, PreserveLCSSA);
 548     // Split NewExit to insert epilog remainder loop.
 549     EpilogPreHeader = SplitBlock(NewExit, NewExit->getTerminator(), DT, LI);
 550     EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
 551   } else {
 552     // If prolog remainder
 553     // Split the original preheader twice to insert prolog remainder loop
 554     PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
 555     PrologPreHeader->setName(Header->getName() + ".prol.preheader");
 556     PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
 557                             DT, LI);
 558     PrologExit->setName(Header->getName() + ".prol.loopexit");
 559     // Split PrologExit to get NewPreHeader.
 560     NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
 561     NewPreHeader->setName(PreHeader->getName() + ".new");
 562   }
 563   // Loop structure should be the following:
 564   //  Epilog             Prolog
 565   //
 566   // PreHeader         PreHeader
 567   // *NewPreHeader     *PrologPreHeader
 568   //   Header          *PrologExit
 569   //   ...             *NewPreHeader
 570   //   Latch             Header
 571   // *NewExit            ...
 572   // *EpilogPreHeader    Latch
 573   // Exit              Exit
 574
 575   // Calculate conditions for branch around loop for unrolling
 576   // in epilog case and around prolog remainder loop in prolog case.
 577   // Compute the number of extra iterations required, which is:
 578   //  extra iterations = run-time trip count % loop unroll factor
 579   PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
 580   Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
 581                                             PreHeaderBR);
 582   Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
 583                                           PreHeaderBR);
 584   IRBuilder<> B(PreHeaderBR);
 585   Value *ModVal;
 586   // Calculate ModVal = (BECount + 1) % Count.
 587   // Note that TripCount is BECount + 1.
 588   if (isPowerOf2_32(Count)) {
 589     // When Count is power of 2 we don't BECount for epilog case, however we'll
 590     // need it for a branch around unrolling loop for prolog case.
 591     ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");
 592     //  1. There are no iterations to be run in the prolog/epilog loop.
 593     // OR
 594     //  2. The addition computing TripCount overflowed.
 595     //
 596     // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
 597     // the number of iterations that remain to be run in the original loop is a
 598     // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (we
 599     // explicitly check this above).
 600   } else {
 601     // As (BECount + 1) can potentially unsigned overflow we count
 602     // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
 603     Value *ModValTmp = B.CreateURem(BECount,
 604                                     ConstantInt::get(BECount->getType(),
 605                                                      Count));
 606     Value *ModValAdd = B.CreateAdd(ModValTmp,
 607                                    ConstantInt::get(ModValTmp->getType(), 1));
 608     // At that point (BECount % Count) + 1 could be equal to Count.
 609     // To handle this case we need to take mod by Count one more time.
 610     ModVal = B.CreateURem(ModValAdd,
 611                           ConstantInt::get(BECount->getType(), Count),
 612                           "xtraiter");
 613   }
 614   Value *BranchVal =
 615       UseEpilogRemainder ? B.CreateICmpULT(BECount,
 616                                            ConstantInt::get(BECount->getType(),
 617                                                             Count - 1)) :
 618                            B.CreateIsNotNull(ModVal, "lcmp.mod");
 619   BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
 620   BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
 621   // Branch to either remainder (extra iterations) loop or unrolling loop.
 622   B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
 623   PreHeaderBR->eraseFromParent();
 624   if (DT) {
 625     if (UseEpilogRemainder)
 626       DT->changeImmediateDominator(NewExit, PreHeader);
 627     else
 628       DT->changeImmediateDominator(PrologExit, PreHeader);
 629   }
 630   Function *F = Header->getParent();
 631   // Get an ordered list of blocks in the loop to help with the ordering of the
 632   // cloned blocks in the prolog/epilog code
 633   LoopBlocksDFS LoopBlocks(L);
 634   LoopBlocks.perform(LI);
 635
 636   //
 637   // For each extra loop iteration, create a copy of the loop's basic blocks
 638   // and generate a condition that branches to the copy depending on the
 639   // number of 'left over' iterations.
 640   //
 641   std::vector<BasicBlock *> NewBlocks;
 642   ValueToValueMapTy VMap;
 643
 644   // For unroll factor 2 remainder loop will have 1 iterations.
 645   // Do not create 1 iteration loop.
 646   bool CreateRemainderLoop = (Count != 2);
 647
 648   // Clone all the basic blocks in the loop. If Count is 2, we don't clone
 649   // the loop, otherwise we create a cloned loop to execute the extra
 650   // iterations. This function adds the appropriate CFG connections.
 651   BasicBlock *InsertBot = UseEpilogRemainder ? Exit : PrologExit;
 652   BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
 653   CloneLoopBlocks(L, ModVal, CreateRemainderLoop, UseEpilogRemainder, InsertTop,
 654                   InsertBot, NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
 655
 656   // Insert the cloned blocks into the function.
 657   F->getBasicBlockList().splice(InsertBot->getIterator(),
 658                                 F->getBasicBlockList(),
 659                                 NewBlocks[0]->getIterator(),
 660                                 F->end());
 661
 662   // Loop structure should be the following:
 663   //  Epilog             Prolog
 664   //
 665   // PreHeader         PreHeader
 666   // NewPreHeader      PrologPreHeader
 667   //   Header            PrologHeader
 668   //   ...               ...
 669   //   Latch             PrologLatch
 670   // NewExit           PrologExit
 671   // EpilogPreHeader   NewPreHeader
 672   //   EpilogHeader      Header
 673   //   ...               ...
 674   //   EpilogLatch       Latch
 675   // Exit              Exit
 676
 677   // Rewrite the cloned instruction operands to use the values created when the
 678   // clone is created.
 679   for (BasicBlock *BB : NewBlocks) {
 680     for (Instruction &I : *BB) {
 681       RemapInstruction(&I, VMap,
 682                        RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
 683     }
 684   }
 685
 686   if (UseEpilogRemainder) {
 687     // Connect the epilog code to the original loop and update the
 688     // PHI functions.
 689     ConnectEpilog(L, ModVal, NewExit, Exit, PreHeader,
 690                   EpilogPreHeader, NewPreHeader, VMap, DT, LI,
 691                   PreserveLCSSA);
 692
 693     // Update counter in loop for unrolling.
 694     // I should be multiply of Count.
 695     IRBuilder<> B2(NewPreHeader->getTerminator());
 696     Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
 697     BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
 698     B2.SetInsertPoint(LatchBR);
 699     PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
 700                                       Header->getFirstNonPHI());
 701     Value *IdxSub =
 702         B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
 703                      NewIdx->getName() + ".nsub");
 704     Value *IdxCmp;
 705     if (LatchBR->getSuccessor(0) == Header)
 706       IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
 707     else
 708       IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
 709     NewIdx->addIncoming(TestVal, NewPreHeader);
 710     NewIdx->addIncoming(IdxSub, Latch);
 711     LatchBR->setCondition(IdxCmp);
 712   } else {
 713     // Connect the prolog code to the original loop and update the
 714     // PHI functions.
 715     ConnectProlog(L, BECount, Count, PrologExit, PreHeader, NewPreHeader,
 716                   VMap, DT, LI, PreserveLCSSA);
 717   }
 718
 719   // If this loop is nested, then the loop unroller changes the code in the
 720   // parent loop, so the Scalar Evolution pass needs to be run again.
 721   if (Loop *ParentLoop = L->getParentLoop())
 722     SE->forgetLoop(ParentLoop);
 723
 724   NumRuntimeUnrolled++;
 725   return true;
 726 }