contrib/llvm-project/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

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