contrib/llvm/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/ADT/SmallSet.h"
  26 #include "llvm/Analysis/AliasAnalysis.h"
  27 #include "llvm/Analysis/LoopIterator.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/LoopUtils.h"
  40 #include "llvm/Transforms/Utils/UnrollLoop.h"
  41 #include <algorithm>
  42
  43 using namespace llvm;
  44
  45 #define DEBUG_TYPE "loop-unroll"
  46
  47 STATISTIC(NumRuntimeUnrolled,
  48           "Number of loops unrolled with run-time trip counts");
  49 static cl::opt<bool> UnrollRuntimeMultiExit(
  50     "unroll-runtime-multi-exit", cl::init(false), cl::Hidden,
  51     cl::desc("Allow runtime unrolling for loops with multiple exits, when "
  52              "epilog is generated"));
  53
  54 /// Connect the unrolling prolog code to the original loop.
  55 /// The unrolling prolog code contains code to execute the
  56 /// 'extra' iterations if the run-time trip count modulo the
  57 /// unroll count is non-zero.
  58 ///
  59 /// This function performs the following:
  60 /// - Create PHI nodes at prolog end block to combine values
  61 ///   that exit the prolog code and jump around the prolog.
  62 /// - Add a PHI operand to a PHI node at the loop exit block
  63 ///   for values that exit the prolog and go around the loop.
  64 /// - Branch around the original loop if the trip count is less
  65 ///   than the unroll factor.
  66 ///
  67 static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
  68                           BasicBlock *PrologExit,
  69                           BasicBlock *OriginalLoopLatchExit,
  70                           BasicBlock *PreHeader, BasicBlock *NewPreHeader,
  71                           ValueToValueMapTy &VMap, DominatorTree *DT,
  72                           LoopInfo *LI, bool PreserveLCSSA) {
  73   BasicBlock *Latch = L->getLoopLatch();
  74   assert(Latch && "Loop must have a latch");
  75   BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);
  76
  77   // Create a PHI node for each outgoing value from the original loop
  78   // (which means it is an outgoing value from the prolog code too).
  79   // The new PHI node is inserted in the prolog end basic block.
  80   // The new PHI node value is added as an operand of a PHI node in either
  81   // the loop header or the loop exit block.
  82   for (BasicBlock *Succ : successors(Latch)) {
  83     for (PHINode &PN : Succ->phis()) {
  84       // Add a new PHI node to the prolog end block and add the
  85       // appropriate incoming values.
  86       PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
  87                                        PrologExit->getFirstNonPHI());
  88       // Adding a value to the new PHI node from the original loop preheader.
  89       // This is the value that skips all the prolog code.
  90       if (L->contains(&PN)) {
  91         NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader),
  92                            PreHeader);
  93       } else {
  94         NewPN->addIncoming(UndefValue::get(PN.getType()), PreHeader);
  95       }
  96
  97       Value *V = PN.getIncomingValueForBlock(Latch);
  98       if (Instruction *I = dyn_cast<Instruction>(V)) {
  99         if (L->contains(I)) {
 100           V = VMap.lookup(I);
 101         }
 102       }
 103       // Adding a value to the new PHI node from the last prolog block
 104       // that was created.
 105       NewPN->addIncoming(V, PrologLatch);
 106
 107       // Update the existing PHI node operand with the value from the
 108       // new PHI node.  How this is done depends on if the existing
 109       // PHI node is in the original loop block, or the exit block.
 110       if (L->contains(&PN)) {
 111         PN.setIncomingValue(PN.getBasicBlockIndex(NewPreHeader), NewPN);
 112       } else {
 113         PN.addIncoming(NewPN, PrologExit);
 114       }
 115     }
 116   }
 117
 118   // Make sure that created prolog loop is in simplified form
 119   SmallVector<BasicBlock *, 4> PrologExitPreds;
 120   Loop *PrologLoop = LI->getLoopFor(PrologLatch);
 121   if (PrologLoop) {
 122     for (BasicBlock *PredBB : predecessors(PrologExit))
 123       if (PrologLoop->contains(PredBB))
 124         PrologExitPreds.push_back(PredBB);
 125
 126     SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI,
 127                            PreserveLCSSA);
 128   }
 129
 130   // Create a branch around the original loop, which is taken if there are no
 131   // iterations remaining to be executed after running the prologue.
 132   Instruction *InsertPt = PrologExit->getTerminator();
 133   IRBuilder<> B(InsertPt);
 134
 135   assert(Count != 0 && "nonsensical Count!");
 136
 137   // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)
 138   // This means %xtraiter is (BECount + 1) and all of the iterations of this
 139   // loop were executed by the prologue.  Note that if BECount <u (Count - 1)
 140   // then (BECount + 1) cannot unsigned-overflow.
 141   Value *BrLoopExit =
 142       B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1));
 143   // Split the exit to maintain loop canonicalization guarantees
 144   SmallVector<BasicBlock *, 4> Preds(predecessors(OriginalLoopLatchExit));
 145   SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI,
 146                          PreserveLCSSA);
 147   // Add the branch to the exit block (around the unrolled loop)
 148   B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader);
 149   InsertPt->eraseFromParent();
 150   if (DT)
 151     DT->changeImmediateDominator(OriginalLoopLatchExit, PrologExit);
 152 }
 153
 154 /// Connect the unrolling epilog code to the original loop.
 155 /// The unrolling epilog code contains code to execute the
 156 /// 'extra' iterations if the run-time trip count modulo the
 157 /// unroll count is non-zero.
 158 ///
 159 /// This function performs the following:
 160 /// - Update PHI nodes at the unrolling loop exit and epilog loop exit
 161 /// - Create PHI nodes at the unrolling loop exit to combine
 162 ///   values that exit the unrolling loop code and jump around it.
 163 /// - Update PHI operands in the epilog loop by the new PHI nodes
 164 /// - Branch around the epilog loop if extra iters (ModVal) is zero.
 165 ///
 166 static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,
 167                           BasicBlock *Exit, BasicBlock *PreHeader,
 168                           BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader,
 169                           ValueToValueMapTy &VMap, DominatorTree *DT,
 170                           LoopInfo *LI, bool PreserveLCSSA)  {
 171   BasicBlock *Latch = L->getLoopLatch();
 172   assert(Latch && "Loop must have a latch");
 173   BasicBlock *EpilogLatch = cast<BasicBlock>(VMap[Latch]);
 174
 175   // Loop structure should be the following:
 176   //
 177   // PreHeader
 178   // NewPreHeader
 179   //   Header
 180   //   ...
 181   //   Latch
 182   // NewExit (PN)
 183   // EpilogPreHeader
 184   //   EpilogHeader
 185   //   ...
 186   //   EpilogLatch
 187   // Exit (EpilogPN)
 188
 189   // Update PHI nodes at NewExit and Exit.
 190   for (PHINode &PN : NewExit->phis()) {
 191     // PN should be used in another PHI located in Exit block as
 192     // Exit was split by SplitBlockPredecessors into Exit and NewExit
 193     // Basicaly it should look like:
 194     // NewExit:
 195     //   PN = PHI [I, Latch]
 196     // ...
 197     // Exit:
 198     //   EpilogPN = PHI [PN, EpilogPreHeader]
 199     //
 200     // There is EpilogPreHeader incoming block instead of NewExit as
 201     // NewExit was spilt 1 more time to get EpilogPreHeader.
 202     assert(PN.hasOneUse() && "The phi should have 1 use");
 203     PHINode *EpilogPN = cast<PHINode>(PN.use_begin()->getUser());
 204     assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block");
 205
 206     // Add incoming PreHeader from branch around the Loop
 207     PN.addIncoming(UndefValue::get(PN.getType()), PreHeader);
 208
 209     Value *V = PN.getIncomingValueForBlock(Latch);
 210     Instruction *I = dyn_cast<Instruction>(V);
 211     if (I && L->contains(I))
 212       // If value comes from an instruction in the loop add VMap value.
 213       V = VMap.lookup(I);
 214     // For the instruction out of the loop, constant or undefined value
 215     // insert value itself.
 216     EpilogPN->addIncoming(V, EpilogLatch);
 217
 218     assert(EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 &&
 219           "EpilogPN should have EpilogPreHeader incoming block");
 220     // Change EpilogPreHeader incoming block to NewExit.
 221     EpilogPN->setIncomingBlock(EpilogPN->getBasicBlockIndex(EpilogPreHeader),
 222                                NewExit);
 223     // Now PHIs should look like:
 224     // NewExit:
 225     //   PN = PHI [I, Latch], [undef, PreHeader]
 226     // ...
 227     // Exit:
 228     //   EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]
 229   }
 230
 231   // Create PHI nodes at NewExit (from the unrolling loop Latch and PreHeader).
 232   // Update corresponding PHI nodes in epilog loop.
 233   for (BasicBlock *Succ : successors(Latch)) {
 234     // Skip this as we already updated phis in exit blocks.
 235     if (!L->contains(Succ))
 236       continue;
 237     for (PHINode &PN : Succ->phis()) {
 238       // Add new PHI nodes to the loop exit block and update epilog
 239       // PHIs with the new PHI values.
 240       PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
 241                                        NewExit->getFirstNonPHI());
 242       // Adding a value to the new PHI node from the unrolling loop preheader.
 243       NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader), PreHeader);
 244       // Adding a value to the new PHI node from the unrolling loop latch.
 245       NewPN->addIncoming(PN.getIncomingValueForBlock(Latch), Latch);
 246
 247       // Update the existing PHI node operand with the value from the new PHI
 248       // node.  Corresponding instruction in epilog loop should be PHI.
 249       PHINode *VPN = cast<PHINode>(VMap[&PN]);
 250       VPN->setIncomingValue(VPN->getBasicBlockIndex(EpilogPreHeader), NewPN);
 251     }
 252   }
 253
 254   Instruction *InsertPt = NewExit->getTerminator();
 255   IRBuilder<> B(InsertPt);
 256   Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");
 257   assert(Exit && "Loop must have a single exit block only");
 258   // Split the epilogue exit to maintain loop canonicalization guarantees
 259   SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
 260   SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI,
 261                          PreserveLCSSA);
 262   // Add the branch to the exit block (around the unrolling loop)
 263   B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
 264   InsertPt->eraseFromParent();
 265   if (DT)
 266     DT->changeImmediateDominator(Exit, NewExit);
 267
 268   // Split the main loop exit to maintain canonicalization guarantees.
 269   SmallVector<BasicBlock*, 4> NewExitPreds{Latch};
 270   SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI,
 271                          PreserveLCSSA);
 272 }
 273
 274 /// Create a clone of the blocks in a loop and connect them together.
 275 /// If CreateRemainderLoop is false, loop structure will not be cloned,
 276 /// otherwise a new loop will be created including all cloned blocks, and the
 277 /// iterator of it switches to count NewIter down to 0.
 278 /// The cloned blocks should be inserted between InsertTop and InsertBot.
 279 /// If loop structure is cloned InsertTop should be new preheader, InsertBot
 280 /// new loop exit.
 281 /// Return the new cloned loop that is created when CreateRemainderLoop is true.
 282 static Loop *
 283 CloneLoopBlocks(Loop *L, Value *NewIter, const bool CreateRemainderLoop,
 284                 const bool UseEpilogRemainder, const bool UnrollRemainder,
 285                 BasicBlock *InsertTop,
 286                 BasicBlock *InsertBot, BasicBlock *Preheader,
 287                 std::vector<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
 288                 ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI) {
 289   StringRef suffix = UseEpilogRemainder ? "epil" : "prol";
 290   BasicBlock *Header = L->getHeader();
 291   BasicBlock *Latch = L->getLoopLatch();
 292   Function *F = Header->getParent();
 293   LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
 294   LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
 295   Loop *ParentLoop = L->getParentLoop();
 296   NewLoopsMap NewLoops;
 297   NewLoops[ParentLoop] = ParentLoop;
 298   if (!CreateRemainderLoop)
 299     NewLoops[L] = ParentLoop;
 300
 301   // For each block in the original loop, create a new copy,
 302   // and update the value map with the newly created values.
 303   for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
 304     BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, "." + suffix, F);
 305     NewBlocks.push_back(NewBB);
 306
 307     // If we're unrolling the outermost loop, there's no remainder loop,
 308     // and this block isn't in a nested loop, then the new block is not
 309     // in any loop. Otherwise, add it to loopinfo.
 310     if (CreateRemainderLoop || LI->getLoopFor(*BB) != L || ParentLoop)
 311       addClonedBlockToLoopInfo(*BB, NewBB, LI, NewLoops);
 312
 313     VMap[*BB] = NewBB;
 314     if (Header == *BB) {
 315       // For the first block, add a CFG connection to this newly
 316       // created block.
 317       InsertTop->getTerminator()->setSuccessor(0, NewBB);
 318     }
 319
 320     if (DT) {
 321       if (Header == *BB) {
 322         // The header is dominated by the preheader.
 323         DT->addNewBlock(NewBB, InsertTop);
 324       } else {
 325         // Copy information from original loop to unrolled loop.
 326         BasicBlock *IDomBB = DT->getNode(*BB)->getIDom()->getBlock();
 327         DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDomBB]));
 328       }
 329     }
 330
 331     if (Latch == *BB) {
 332       // For the last block, if CreateRemainderLoop is false, create a direct
 333       // jump to InsertBot. If not, create a loop back to cloned head.
 334       VMap.erase((*BB)->getTerminator());
 335       BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]);
 336       BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());
 337       IRBuilder<> Builder(LatchBR);
 338       if (!CreateRemainderLoop) {
 339         Builder.CreateBr(InsertBot);
 340       } else {
 341         PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2,
 342                                           suffix + ".iter",
 343                                           FirstLoopBB->getFirstNonPHI());
 344         Value *IdxSub =
 345             Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
 346                               NewIdx->getName() + ".sub");
 347         Value *IdxCmp =
 348             Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp");
 349         Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot);
 350         NewIdx->addIncoming(NewIter, InsertTop);
 351         NewIdx->addIncoming(IdxSub, NewBB);
 352       }
 353       LatchBR->eraseFromParent();
 354     }
 355   }
 356
 357   // Change the incoming values to the ones defined in the preheader or
 358   // cloned loop.
 359   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 360     PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
 361     if (!CreateRemainderLoop) {
 362       if (UseEpilogRemainder) {
 363         unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
 364         NewPHI->setIncomingBlock(idx, InsertTop);
 365         NewPHI->removeIncomingValue(Latch, false);
 366       } else {
 367         VMap[&*I] = NewPHI->getIncomingValueForBlock(Preheader);
 368         cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
 369       }
 370     } else {
 371       unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
 372       NewPHI->setIncomingBlock(idx, InsertTop);
 373       BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
 374       idx = NewPHI->getBasicBlockIndex(Latch);
 375       Value *InVal = NewPHI->getIncomingValue(idx);
 376       NewPHI->setIncomingBlock(idx, NewLatch);
 377       if (Value *V = VMap.lookup(InVal))
 378         NewPHI->setIncomingValue(idx, V);
 379     }
 380   }
 381   if (CreateRemainderLoop) {
 382     Loop *NewLoop = NewLoops[L];
 383     assert(NewLoop && "L should have been cloned");
 384
 385     // Only add loop metadata if the loop is not going to be completely
 386     // unrolled.
 387     if (UnrollRemainder)
 388       return NewLoop;
 389
 390     // Add unroll disable metadata to disable future unrolling for this loop.
 391     NewLoop->setLoopAlreadyUnrolled();
 392     return NewLoop;
 393   }
 394   else
 395     return nullptr;
 396 }
 397
 398 /// Returns true if we can safely unroll a multi-exit/exiting loop. OtherExits
 399 /// is populated with all the loop exit blocks other than the LatchExit block.
 400 static bool
 401 canSafelyUnrollMultiExitLoop(Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits,
 402                              BasicBlock *LatchExit, bool PreserveLCSSA,
 403                              bool UseEpilogRemainder) {
 404
 405   // We currently have some correctness constrains in unrolling a multi-exit
 406   // loop. Check for these below.
 407
 408   // We rely on LCSSA form being preserved when the exit blocks are transformed.
 409   if (!PreserveLCSSA)
 410     return false;
 411   SmallVector<BasicBlock *, 4> Exits;
 412   L->getUniqueExitBlocks(Exits);
 413   for (auto *BB : Exits)
 414     if (BB != LatchExit)
 415       OtherExits.push_back(BB);
 416
 417   // TODO: Support multiple exiting blocks jumping to the `LatchExit` when
 418   // UnrollRuntimeMultiExit is true. This will need updating the logic in
 419   // connectEpilog/connectProlog.
 420   if (!LatchExit->getSinglePredecessor()) {
 421     DEBUG(dbgs() << "Bailout for multi-exit handling when latch exit has >1 "
 422                     "predecessor.\n");
 423     return false;
 424   }
 425   // FIXME: We bail out of multi-exit unrolling when epilog loop is generated
 426   // and L is an inner loop. This is because in presence of multiple exits, the
 427   // outer loop is incorrect: we do not add the EpilogPreheader and exit to the
 428   // outer loop. This is automatically handled in the prolog case, so we do not
 429   // have that bug in prolog generation.
 430   if (UseEpilogRemainder && L->getParentLoop())
 431     return false;
 432
 433   // All constraints have been satisfied.
 434   return true;
 435 }
 436
 437 /// Returns true if we can profitably unroll the multi-exit loop L. Currently,
 438 /// we return true only if UnrollRuntimeMultiExit is set to true.
 439 static bool canProfitablyUnrollMultiExitLoop(
 440     Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,
 441     bool PreserveLCSSA, bool UseEpilogRemainder) {
 442
 443 #if !defined(NDEBUG)
 444   SmallVector<BasicBlock *, 8> OtherExitsDummyCheck;
 445   assert(canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck, LatchExit,
 446                                       PreserveLCSSA, UseEpilogRemainder) &&
 447          "Should be safe to unroll before checking profitability!");
 448 #endif
 449
 450   // Priority goes to UnrollRuntimeMultiExit if it's supplied.
 451   if (UnrollRuntimeMultiExit.getNumOccurrences())
 452     return UnrollRuntimeMultiExit;
 453
 454   // The main pain point with multi-exit loop unrolling is that once unrolled,
 455   // we will not be able to merge all blocks into a straight line code.
 456   // There are branches within the unrolled loop that go to the OtherExits.
 457   // The second point is the increase in code size, but this is true
 458   // irrespective of multiple exits.
 459
 460   // Note: Both the heuristics below are coarse grained. We are essentially
 461   // enabling unrolling of loops that have a single side exit other than the
 462   // normal LatchExit (i.e. exiting into a deoptimize block).
 463   // The heuristics considered are:
 464   // 1. low number of branches in the unrolled version.
 465   // 2. high predictability of these extra branches.
 466   // We avoid unrolling loops that have more than two exiting blocks. This
 467   // limits the total number of branches in the unrolled loop to be atmost
 468   // the unroll factor (since one of the exiting blocks is the latch block).
 469   SmallVector<BasicBlock*, 4> ExitingBlocks;
 470   L->getExitingBlocks(ExitingBlocks);
 471   if (ExitingBlocks.size() > 2)
 472     return false;
 473
 474   // The second heuristic is that L has one exit other than the latchexit and
 475   // that exit is a deoptimize block. We know that deoptimize blocks are rarely
 476   // taken, which also implies the branch leading to the deoptimize block is
 477   // highly predictable.
 478   return (OtherExits.size() == 1 &&
 479           OtherExits[0]->getTerminatingDeoptimizeCall());
 480   // TODO: These can be fine-tuned further to consider code size or deopt states
 481   // that are captured by the deoptimize exit block.
 482   // Also, we can extend this to support more cases, if we actually
 483   // know of kinds of multiexit loops that would benefit from unrolling.
 484 }
 485
 486 /// Insert code in the prolog/epilog code when unrolling a loop with a
 487 /// run-time trip-count.
 488 ///
 489 /// This method assumes that the loop unroll factor is total number
 490 /// of loop bodies in the loop after unrolling. (Some folks refer
 491 /// to the unroll factor as the number of *extra* copies added).
 492 /// We assume also that the loop unroll factor is a power-of-two. So, after
 493 /// unrolling the loop, the number of loop bodies executed is 2,
 494 /// 4, 8, etc.  Note - LLVM converts the if-then-sequence to a switch
 495 /// instruction in SimplifyCFG.cpp.  Then, the backend decides how code for
 496 /// the switch instruction is generated.
 497 ///
 498 /// ***Prolog case***
 499 ///        extraiters = tripcount % loopfactor
 500 ///        if (extraiters == 0) jump Loop:
 501 ///        else jump Prol:
 502 /// Prol:  LoopBody;
 503 ///        extraiters -= 1                 // Omitted if unroll factor is 2.
 504 ///        if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
 505 ///        if (tripcount < loopfactor) jump End:
 506 /// Loop:
 507 /// ...
 508 /// End:
 509 ///
 510 /// ***Epilog case***
 511 ///        extraiters = tripcount % loopfactor
 512 ///        if (tripcount < loopfactor) jump LoopExit:
 513 ///        unroll_iters = tripcount - extraiters
 514 /// Loop:  LoopBody; (executes unroll_iter times);
 515 ///        unroll_iter -= 1
 516 ///        if (unroll_iter != 0) jump Loop:
 517 /// LoopExit:
 518 ///        if (extraiters == 0) jump EpilExit:
 519 /// Epil:  LoopBody; (executes extraiters times)
 520 ///        extraiters -= 1                 // Omitted if unroll factor is 2.
 521 ///        if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
 522 /// EpilExit:
 523
 524 bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
 525                                       bool AllowExpensiveTripCount,
 526                                       bool UseEpilogRemainder,
 527                                       bool UnrollRemainder,
 528                                       LoopInfo *LI, ScalarEvolution *SE,
 529                                       DominatorTree *DT, AssumptionCache *AC,
 530                                       bool PreserveLCSSA) {
 531   DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
 532   DEBUG(L->dump());
 533   DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n" :
 534         dbgs() << "Using prolog remainder.\n");
 535
 536   // Make sure the loop is in canonical form.
 537   if (!L->isLoopSimplifyForm()) {
 538     DEBUG(dbgs() << "Not in simplify form!\n");
 539     return false;
 540   }
 541
 542   // Guaranteed by LoopSimplifyForm.
 543   BasicBlock *Latch = L->getLoopLatch();
 544   BasicBlock *Header = L->getHeader();
 545
 546   BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
 547   unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 1 : 0;
 548   BasicBlock *LatchExit = LatchBR->getSuccessor(ExitIndex);
 549   // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
 550   // targets of the Latch be an exit block out of the loop. This needs
 551   // to be guaranteed by the callers of UnrollRuntimeLoopRemainder.
 552   assert(!L->contains(LatchExit) &&
 553          "one of the loop latch successors should be the exit block!");
 554   // These are exit blocks other than the target of the latch exiting block.
 555   SmallVector<BasicBlock *, 4> OtherExits;
 556   bool isMultiExitUnrollingEnabled =
 557       canSafelyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
 558                                    UseEpilogRemainder) &&
 559       canProfitablyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
 560                                        UseEpilogRemainder);
 561   // Support only single exit and exiting block unless multi-exit loop unrolling is enabled.
 562   if (!isMultiExitUnrollingEnabled &&
 563       (!L->getExitingBlock() || OtherExits.size())) {
 564     DEBUG(
 565         dbgs()
 566         << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
 567            "enabled!\n");
 568     return false;
 569   }
 570   // Use Scalar Evolution to compute the trip count. This allows more loops to
 571   // be unrolled than relying on induction var simplification.
 572   if (!SE)
 573     return false;
 574
 575   // Only unroll loops with a computable trip count, and the trip count needs
 576   // to be an int value (allowing a pointer type is a TODO item).
 577   // We calculate the backedge count by using getExitCount on the Latch block,
 578   // which is proven to be the only exiting block in this loop. This is same as
 579   // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
 580   // exiting blocks).
 581   const SCEV *BECountSC = SE->getExitCount(L, Latch);
 582   if (isa<SCEVCouldNotCompute>(BECountSC) ||
 583       !BECountSC->getType()->isIntegerTy()) {
 584     DEBUG(dbgs() << "Could not compute exit block SCEV\n");
 585     return false;
 586   }
 587
 588   unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
 589
 590   // Add 1 since the backedge count doesn't include the first loop iteration.
 591   const SCEV *TripCountSC =
 592       SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
 593   if (isa<SCEVCouldNotCompute>(TripCountSC)) {
 594     DEBUG(dbgs() << "Could not compute trip count SCEV.\n");
 595     return false;
 596   }
 597
 598   BasicBlock *PreHeader = L->getLoopPreheader();
 599   BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
 600   const DataLayout &DL = Header->getModule()->getDataLayout();
 601   SCEVExpander Expander(*SE, DL, "loop-unroll");
 602   if (!AllowExpensiveTripCount &&
 603       Expander.isHighCostExpansion(TripCountSC, L, PreHeaderBR)) {
 604     DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
 605     return false;
 606   }
 607
 608   // This constraint lets us deal with an overflowing trip count easily; see the
 609   // comment on ModVal below.
 610   if (Log2_32(Count) > BEWidth) {
 611     DEBUG(dbgs()
 612           << "Count failed constraint on overflow trip count calculation.\n");
 613     return false;
 614   }
 615
 616   // Loop structure is the following:
 617   //
 618   // PreHeader
 619   //   Header
 620   //   ...
 621   //   Latch
 622   // LatchExit
 623
 624   BasicBlock *NewPreHeader;
 625   BasicBlock *NewExit = nullptr;
 626   BasicBlock *PrologExit = nullptr;
 627   BasicBlock *EpilogPreHeader = nullptr;
 628   BasicBlock *PrologPreHeader = nullptr;
 629
 630   if (UseEpilogRemainder) {
 631     // If epilog remainder
 632     // Split PreHeader to insert a branch around loop for unrolling.
 633     NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
 634     NewPreHeader->setName(PreHeader->getName() + ".new");
 635     // Split LatchExit to create phi nodes from branch above.
 636     SmallVector<BasicBlock*, 4> Preds(predecessors(LatchExit));
 637     NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa",
 638                                      DT, LI, PreserveLCSSA);
 639     // NewExit gets its DebugLoc from LatchExit, which is not part of the
 640     // original Loop.
 641     // Fix this by setting Loop's DebugLoc to NewExit.
 642     auto *NewExitTerminator = NewExit->getTerminator();
 643     NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());
 644     // Split NewExit to insert epilog remainder loop.
 645     EpilogPreHeader = SplitBlock(NewExit, NewExitTerminator, DT, LI);
 646     EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
 647   } else {
 648     // If prolog remainder
 649     // Split the original preheader twice to insert prolog remainder loop
 650     PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
 651     PrologPreHeader->setName(Header->getName() + ".prol.preheader");
 652     PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
 653                             DT, LI);
 654     PrologExit->setName(Header->getName() + ".prol.loopexit");
 655     // Split PrologExit to get NewPreHeader.
 656     NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
 657     NewPreHeader->setName(PreHeader->getName() + ".new");
 658   }
 659   // Loop structure should be the following:
 660   //  Epilog             Prolog
 661   //
 662   // PreHeader         PreHeader
 663   // *NewPreHeader     *PrologPreHeader
 664   //   Header          *PrologExit
 665   //   ...             *NewPreHeader
 666   //   Latch             Header
 667   // *NewExit            ...
 668   // *EpilogPreHeader    Latch
 669   // LatchExit              LatchExit
 670
 671   // Calculate conditions for branch around loop for unrolling
 672   // in epilog case and around prolog remainder loop in prolog case.
 673   // Compute the number of extra iterations required, which is:
 674   //  extra iterations = run-time trip count % loop unroll factor
 675   PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
 676   Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
 677                                             PreHeaderBR);
 678   Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
 679                                           PreHeaderBR);
 680   IRBuilder<> B(PreHeaderBR);
 681   Value *ModVal;
 682   // Calculate ModVal = (BECount + 1) % Count.
 683   // Note that TripCount is BECount + 1.
 684   if (isPowerOf2_32(Count)) {
 685     // When Count is power of 2 we don't BECount for epilog case, however we'll
 686     // need it for a branch around unrolling loop for prolog case.
 687     ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");
 688     //  1. There are no iterations to be run in the prolog/epilog loop.
 689     // OR
 690     //  2. The addition computing TripCount overflowed.
 691     //
 692     // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
 693     // the number of iterations that remain to be run in the original loop is a
 694     // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (we
 695     // explicitly check this above).
 696   } else {
 697     // As (BECount + 1) can potentially unsigned overflow we count
 698     // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
 699     Value *ModValTmp = B.CreateURem(BECount,
 700                                     ConstantInt::get(BECount->getType(),
 701                                                      Count));
 702     Value *ModValAdd = B.CreateAdd(ModValTmp,
 703                                    ConstantInt::get(ModValTmp->getType(), 1));
 704     // At that point (BECount % Count) + 1 could be equal to Count.
 705     // To handle this case we need to take mod by Count one more time.
 706     ModVal = B.CreateURem(ModValAdd,
 707                           ConstantInt::get(BECount->getType(), Count),
 708                           "xtraiter");
 709   }
 710   Value *BranchVal =
 711       UseEpilogRemainder ? B.CreateICmpULT(BECount,
 712                                            ConstantInt::get(BECount->getType(),
 713                                                             Count - 1)) :
 714                            B.CreateIsNotNull(ModVal, "lcmp.mod");
 715   BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
 716   BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
 717   // Branch to either remainder (extra iterations) loop or unrolling loop.
 718   B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
 719   PreHeaderBR->eraseFromParent();
 720   if (DT) {
 721     if (UseEpilogRemainder)
 722       DT->changeImmediateDominator(NewExit, PreHeader);
 723     else
 724       DT->changeImmediateDominator(PrologExit, PreHeader);
 725   }
 726   Function *F = Header->getParent();
 727   // Get an ordered list of blocks in the loop to help with the ordering of the
 728   // cloned blocks in the prolog/epilog code
 729   LoopBlocksDFS LoopBlocks(L);
 730   LoopBlocks.perform(LI);
 731
 732   //
 733   // For each extra loop iteration, create a copy of the loop's basic blocks
 734   // and generate a condition that branches to the copy depending on the
 735   // number of 'left over' iterations.
 736   //
 737   std::vector<BasicBlock *> NewBlocks;
 738   ValueToValueMapTy VMap;
 739
 740   // For unroll factor 2 remainder loop will have 1 iterations.
 741   // Do not create 1 iteration loop.
 742   bool CreateRemainderLoop = (Count != 2);
 743
 744   // Clone all the basic blocks in the loop. If Count is 2, we don't clone
 745   // the loop, otherwise we create a cloned loop to execute the extra
 746   // iterations. This function adds the appropriate CFG connections.
 747   BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;
 748   BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
 749   Loop *remainderLoop = CloneLoopBlocks(
 750       L, ModVal, CreateRemainderLoop, UseEpilogRemainder, UnrollRemainder,
 751       InsertTop, InsertBot,
 752       NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
 753
 754   // Insert the cloned blocks into the function.
 755   F->getBasicBlockList().splice(InsertBot->getIterator(),
 756                                 F->getBasicBlockList(),
 757                                 NewBlocks[0]->getIterator(),
 758                                 F->end());
 759
 760   // Now the loop blocks are cloned and the other exiting blocks from the
 761   // remainder are connected to the original Loop's exit blocks. The remaining
 762   // work is to update the phi nodes in the original loop, and take in the
 763   // values from the cloned region. Also update the dominator info for
 764   // OtherExits and their immediate successors, since we have new edges into
 765   // OtherExits.
 766   SmallSet<BasicBlock*, 8> ImmediateSuccessorsOfExitBlocks;
 767   for (auto *BB : OtherExits) {
 768    for (auto &II : *BB) {
 769
 770      // Given we preserve LCSSA form, we know that the values used outside the
 771      // loop will be used through these phi nodes at the exit blocks that are
 772      // transformed below.
 773      if (!isa<PHINode>(II))
 774        break;
 775      PHINode *Phi = cast<PHINode>(&II);
 776      unsigned oldNumOperands = Phi->getNumIncomingValues();
 777      // Add the incoming values from the remainder code to the end of the phi
 778      // node.
 779      for (unsigned i =0; i < oldNumOperands; i++){
 780        Value *newVal = VMap.lookup(Phi->getIncomingValue(i));
 781        // newVal can be a constant or derived from values outside the loop, and
 782        // hence need not have a VMap value. Also, since lookup already generated
 783        // a default "null" VMap entry for this value, we need to populate that
 784        // VMap entry correctly, with the mapped entry being itself.
 785        if (!newVal) {
 786          newVal = Phi->getIncomingValue(i);
 787          VMap[Phi->getIncomingValue(i)] = Phi->getIncomingValue(i);
 788        }
 789        Phi->addIncoming(newVal,
 790                            cast<BasicBlock>(VMap[Phi->getIncomingBlock(i)]));
 791      }
 792    }
 793 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
 794     for (BasicBlock *SuccBB : successors(BB)) {
 795       assert(!(any_of(OtherExits,
 796                       [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) ||
 797                SuccBB == LatchExit) &&
 798              "Breaks the definition of dedicated exits!");
 799     }
 800 #endif
 801    // Update the dominator info because the immediate dominator is no longer the
 802    // header of the original Loop. BB has edges both from L and remainder code.
 803    // Since the preheader determines which loop is run (L or directly jump to
 804    // the remainder code), we set the immediate dominator as the preheader.
 805    if (DT) {
 806      DT->changeImmediateDominator(BB, PreHeader);
 807      // Also update the IDom for immediate successors of BB.  If the current
 808      // IDom is the header, update the IDom to be the preheader because that is
 809      // the nearest common dominator of all predecessors of SuccBB.  We need to
 810      // check for IDom being the header because successors of exit blocks can
 811      // have edges from outside the loop, and we should not incorrectly update
 812      // the IDom in that case.
 813      for (BasicBlock *SuccBB: successors(BB))
 814        if (ImmediateSuccessorsOfExitBlocks.insert(SuccBB).second) {
 815          if (DT->getNode(SuccBB)->getIDom()->getBlock() == Header) {
 816            assert(!SuccBB->getSinglePredecessor() &&
 817                   "BB should be the IDom then!");
 818            DT->changeImmediateDominator(SuccBB, PreHeader);
 819          }
 820        }
 821     }
 822   }
 823
 824   // Loop structure should be the following:
 825   //  Epilog             Prolog
 826   //
 827   // PreHeader         PreHeader
 828   // NewPreHeader      PrologPreHeader
 829   //   Header            PrologHeader
 830   //   ...               ...
 831   //   Latch             PrologLatch
 832   // NewExit           PrologExit
 833   // EpilogPreHeader   NewPreHeader
 834   //   EpilogHeader      Header
 835   //   ...               ...
 836   //   EpilogLatch       Latch
 837   // LatchExit              LatchExit
 838
 839   // Rewrite the cloned instruction operands to use the values created when the
 840   // clone is created.
 841   for (BasicBlock *BB : NewBlocks) {
 842     for (Instruction &I : *BB) {
 843       RemapInstruction(&I, VMap,
 844                        RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
 845     }
 846   }
 847
 848   if (UseEpilogRemainder) {
 849     // Connect the epilog code to the original loop and update the
 850     // PHI functions.
 851     ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader,
 852                   EpilogPreHeader, NewPreHeader, VMap, DT, LI,
 853                   PreserveLCSSA);
 854
 855     // Update counter in loop for unrolling.
 856     // I should be multiply of Count.
 857     IRBuilder<> B2(NewPreHeader->getTerminator());
 858     Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
 859     BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
 860     B2.SetInsertPoint(LatchBR);
 861     PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
 862                                       Header->getFirstNonPHI());
 863     Value *IdxSub =
 864         B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
 865                      NewIdx->getName() + ".nsub");
 866     Value *IdxCmp;
 867     if (LatchBR->getSuccessor(0) == Header)
 868       IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
 869     else
 870       IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
 871     NewIdx->addIncoming(TestVal, NewPreHeader);
 872     NewIdx->addIncoming(IdxSub, Latch);
 873     LatchBR->setCondition(IdxCmp);
 874   } else {
 875     // Connect the prolog code to the original loop and update the
 876     // PHI functions.
 877     ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,
 878                   NewPreHeader, VMap, DT, LI, PreserveLCSSA);
 879   }
 880
 881   // If this loop is nested, then the loop unroller changes the code in the
 882   // parent loop, so the Scalar Evolution pass needs to be run again.
 883   if (Loop *ParentLoop = L->getParentLoop())
 884     SE->forgetLoop(ParentLoop);
 885
 886   // Canonicalize to LoopSimplifyForm both original and remainder loops. We
 887   // cannot rely on the LoopUnrollPass to do this because it only does
 888   // canonicalization for parent/subloops and not the sibling loops.
 889   if (OtherExits.size() > 0) {
 890     // Generate dedicated exit blocks for the original loop, to preserve
 891     // LoopSimplifyForm.
 892     formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA);
 893     // Generate dedicated exit blocks for the remainder loop if one exists, to
 894     // preserve LoopSimplifyForm.
 895     if (remainderLoop)
 896       formDedicatedExitBlocks(remainderLoop, DT, LI, PreserveLCSSA);
 897   }
 898
 899   if (remainderLoop && UnrollRemainder) {
 900     DEBUG(dbgs() << "Unrolling remainder loop\n");
 901     UnrollLoop(remainderLoop, /*Count*/ Count - 1, /*TripCount*/ Count - 1,
 902                /*Force*/ false, /*AllowRuntime*/ false,
 903                /*AllowExpensiveTripCount*/ false, /*PreserveCondBr*/ true,
 904                /*PreserveOnlyFirst*/ false, /*TripMultiple*/ 1,
 905                /*PeelCount*/ 0, /*UnrollRemainder*/ false, LI, SE, DT, AC,
 906                /*ORE*/ nullptr, PreserveLCSSA);
 907   }
 908
 909   NumRuntimeUnrolled++;
 910   return true;
 911 }