contrib/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp

   1 //===- UnrollLoopPeel.cpp - Loop peeling 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 peeling loops
  11 // with dynamically inferred (from PGO) trip counts. See LoopUnroll.cpp for
  12 // unrolling loops with compile-time constant trip counts.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/ADT/DenseMap.h"
  17 #include "llvm/ADT/Optional.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/Analysis/LoopInfo.h"
  21 #include "llvm/Analysis/LoopIterator.h"
  22 #include "llvm/Analysis/ScalarEvolution.h"
  23 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  24 #include "llvm/Analysis/TargetTransformInfo.h"
  25 #include "llvm/IR/BasicBlock.h"
  26 #include "llvm/IR/Dominators.h"
  27 #include "llvm/IR/Function.h"
  28 #include "llvm/IR/InstrTypes.h"
  29 #include "llvm/IR/Instruction.h"
  30 #include "llvm/IR/Instructions.h"
  31 #include "llvm/IR/LLVMContext.h"
  32 #include "llvm/IR/MDBuilder.h"
  33 #include "llvm/IR/Metadata.h"
  34 #include "llvm/IR/PatternMatch.h"
  35 #include "llvm/Support/Casting.h"
  36 #include "llvm/Support/CommandLine.h"
  37 #include "llvm/Support/Debug.h"
  38 #include "llvm/Support/raw_ostream.h"
  39 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  40 #include "llvm/Transforms/Utils/Cloning.h"
  41 #include "llvm/Transforms/Utils/LoopSimplify.h"
  42 #include "llvm/Transforms/Utils/LoopUtils.h"
  43 #include "llvm/Transforms/Utils/UnrollLoop.h"
  44 #include "llvm/Transforms/Utils/ValueMapper.h"
  45 #include <algorithm>
  46 #include <cassert>
  47 #include <cstdint>
  48 #include <limits>
  49
  50 using namespace llvm;
  51 using namespace llvm::PatternMatch;
  52
  53 #define DEBUG_TYPE "loop-unroll"
  54
  55 STATISTIC(NumPeeled, "Number of loops peeled");
  56
  57 static cl::opt<unsigned> UnrollPeelMaxCount(
  58     "unroll-peel-max-count", cl::init(7), cl::Hidden,
  59     cl::desc("Max average trip count which will cause loop peeling."));
  60
  61 static cl::opt<unsigned> UnrollForcePeelCount(
  62     "unroll-force-peel-count", cl::init(0), cl::Hidden,
  63     cl::desc("Force a peel count regardless of profiling information."));
  64
  65 // Designates that a Phi is estimated to become invariant after an "infinite"
  66 // number of loop iterations (i.e. only may become an invariant if the loop is
  67 // fully unrolled).
  68 static const unsigned InfiniteIterationsToInvariance =
  69     std::numeric_limits<unsigned>::max();
  70
  71 // Check whether we are capable of peeling this loop.
  72 bool llvm::canPeel(Loop *L) {
  73   // Make sure the loop is in simplified form
  74   if (!L->isLoopSimplifyForm())
  75     return false;
  76
  77   // Only peel loops that contain a single exit
  78   if (!L->getExitingBlock() || !L->getUniqueExitBlock())
  79     return false;
  80
  81   // Don't try to peel loops where the latch is not the exiting block.
  82   // This can be an indication of two different things:
  83   // 1) The loop is not rotated.
  84   // 2) The loop contains irreducible control flow that involves the latch.
  85   if (L->getLoopLatch() != L->getExitingBlock())
  86     return false;
  87
  88   return true;
  89 }
  90
  91 // This function calculates the number of iterations after which the given Phi
  92 // becomes an invariant. The pre-calculated values are memorized in the map. The
  93 // function (shortcut is I) is calculated according to the following definition:
  94 // Given %x = phi <Inputs from above the loop>, ..., [%y, %back.edge].
  95 //   If %y is a loop invariant, then I(%x) = 1.
  96 //   If %y is a Phi from the loop header, I(%x) = I(%y) + 1.
  97 //   Otherwise, I(%x) is infinite.
  98 // TODO: Actually if %y is an expression that depends only on Phi %z and some
  99 //       loop invariants, we can estimate I(%x) = I(%z) + 1. The example
 100 //       looks like:
 101 //         %x = phi(0, %a),  <-- becomes invariant starting from 3rd iteration.
 102 //         %y = phi(0, 5),
 103 //         %a = %y + 1.
 104 static unsigned calculateIterationsToInvariance(
 105     PHINode *Phi, Loop *L, BasicBlock *BackEdge,
 106     SmallDenseMap<PHINode *, unsigned> &IterationsToInvariance) {
 107   assert(Phi->getParent() == L->getHeader() &&
 108          "Non-loop Phi should not be checked for turning into invariant.");
 109   assert(BackEdge == L->getLoopLatch() && "Wrong latch?");
 110   // If we already know the answer, take it from the map.
 111   auto I = IterationsToInvariance.find(Phi);
 112   if (I != IterationsToInvariance.end())
 113     return I->second;
 114
 115   // Otherwise we need to analyze the input from the back edge.
 116   Value *Input = Phi->getIncomingValueForBlock(BackEdge);
 117   // Place infinity to map to avoid infinite recursion for cycled Phis. Such
 118   // cycles can never stop on an invariant.
 119   IterationsToInvariance[Phi] = InfiniteIterationsToInvariance;
 120   unsigned ToInvariance = InfiniteIterationsToInvariance;
 121
 122   if (L->isLoopInvariant(Input))
 123     ToInvariance = 1u;
 124   else if (PHINode *IncPhi = dyn_cast<PHINode>(Input)) {
 125     // Only consider Phis in header block.
 126     if (IncPhi->getParent() != L->getHeader())
 127       return InfiniteIterationsToInvariance;
 128     // If the input becomes an invariant after X iterations, then our Phi
 129     // becomes an invariant after X + 1 iterations.
 130     unsigned InputToInvariance = calculateIterationsToInvariance(
 131         IncPhi, L, BackEdge, IterationsToInvariance);
 132     if (InputToInvariance != InfiniteIterationsToInvariance)
 133       ToInvariance = InputToInvariance + 1u;
 134   }
 135
 136   // If we found that this Phi lies in an invariant chain, update the map.
 137   if (ToInvariance != InfiniteIterationsToInvariance)
 138     IterationsToInvariance[Phi] = ToInvariance;
 139   return ToInvariance;
 140 }
 141
 142 // Return the number of iterations to peel off that make conditions in the
 143 // body true/false. For example, if we peel 2 iterations off the loop below,
 144 // the condition i < 2 can be evaluated at compile time.
 145 //  for (i = 0; i < n; i++)
 146 //    if (i < 2)
 147 //      ..
 148 //    else
 149 //      ..
 150 //   }
 151 static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount,
 152                                          ScalarEvolution &SE) {
 153   assert(L.isLoopSimplifyForm() && "Loop needs to be in loop simplify form");
 154   unsigned DesiredPeelCount = 0;
 155
 156   for (auto *BB : L.blocks()) {
 157     auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
 158     if (!BI || BI->isUnconditional())
 159       continue;
 160
 161     // Ignore loop exit condition.
 162     if (L.getLoopLatch() == BB)
 163       continue;
 164
 165     Value *Condition = BI->getCondition();
 166     Value *LeftVal, *RightVal;
 167     CmpInst::Predicate Pred;
 168     if (!match(Condition, m_ICmp(Pred, m_Value(LeftVal), m_Value(RightVal))))
 169       continue;
 170
 171     const SCEV *LeftSCEV = SE.getSCEV(LeftVal);
 172     const SCEV *RightSCEV = SE.getSCEV(RightVal);
 173
 174     // Do not consider predicates that are known to be true or false
 175     // independently of the loop iteration.
 176     if (SE.isKnownPredicate(Pred, LeftSCEV, RightSCEV) ||
 177         SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), LeftSCEV,
 178                             RightSCEV))
 179       continue;
 180
 181     // Check if we have a condition with one AddRec and one non AddRec
 182     // expression. Normalize LeftSCEV to be the AddRec.
 183     if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
 184       if (isa<SCEVAddRecExpr>(RightSCEV)) {
 185         std::swap(LeftSCEV, RightSCEV);
 186         Pred = ICmpInst::getSwappedPredicate(Pred);
 187       } else
 188         continue;
 189     }
 190
 191     const SCEVAddRecExpr *LeftAR = cast<SCEVAddRecExpr>(LeftSCEV);
 192
 193     // Avoid huge SCEV computations in the loop below, make sure we only
 194     // consider AddRecs of the loop we are trying to peel and avoid
 195     // non-monotonic predicates, as we will not be able to simplify the loop
 196     // body.
 197     // FIXME: For the non-monotonic predicates ICMP_EQ and ICMP_NE we can
 198     //        simplify the loop, if we peel 1 additional iteration, if there
 199     //        is no wrapping.
 200     bool Increasing;
 201     if (!LeftAR->isAffine() || LeftAR->getLoop() != &L ||
 202         !SE.isMonotonicPredicate(LeftAR, Pred, Increasing))
 203       continue;
 204     (void)Increasing;
 205
 206     // Check if extending the current DesiredPeelCount lets us evaluate Pred
 207     // or !Pred in the loop body statically.
 208     unsigned NewPeelCount = DesiredPeelCount;
 209
 210     const SCEV *IterVal = LeftAR->evaluateAtIteration(
 211         SE.getConstant(LeftSCEV->getType(), NewPeelCount), SE);
 212
 213     // If the original condition is not known, get the negated predicate
 214     // (which holds on the else branch) and check if it is known. This allows
 215     // us to peel of iterations that make the original condition false.
 216     if (!SE.isKnownPredicate(Pred, IterVal, RightSCEV))
 217       Pred = ICmpInst::getInversePredicate(Pred);
 218
 219     const SCEV *Step = LeftAR->getStepRecurrence(SE);
 220     while (NewPeelCount < MaxPeelCount &&
 221            SE.isKnownPredicate(Pred, IterVal, RightSCEV)) {
 222       IterVal = SE.getAddExpr(IterVal, Step);
 223       NewPeelCount++;
 224     }
 225
 226     // Only peel the loop if the monotonic predicate !Pred becomes known in the
 227     // first iteration of the loop body after peeling.
 228     if (NewPeelCount > DesiredPeelCount &&
 229         SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), IterVal,
 230                             RightSCEV))
 231       DesiredPeelCount = NewPeelCount;
 232   }
 233
 234   return DesiredPeelCount;
 235 }
 236
 237 // Return the number of iterations we want to peel off.
 238 void llvm::computePeelCount(Loop *L, unsigned LoopSize,
 239                             TargetTransformInfo::UnrollingPreferences &UP,
 240                             unsigned &TripCount, ScalarEvolution &SE) {
 241   assert(LoopSize > 0 && "Zero loop size is not allowed!");
 242   // Save the UP.PeelCount value set by the target in
 243   // TTI.getUnrollingPreferences or by the flag -unroll-peel-count.
 244   unsigned TargetPeelCount = UP.PeelCount;
 245   UP.PeelCount = 0;
 246   if (!canPeel(L))
 247     return;
 248
 249   // Only try to peel innermost loops.
 250   if (!L->empty())
 251     return;
 252
 253   // If the user provided a peel count, use that.
 254   bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0;
 255   if (UserPeelCount) {
 256     LLVM_DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount
 257                       << " iterations.\n");
 258     UP.PeelCount = UnrollForcePeelCount;
 259     return;
 260   }
 261
 262   // Skip peeling if it's disabled.
 263   if (!UP.AllowPeeling)
 264     return;
 265
 266   // Here we try to get rid of Phis which become invariants after 1, 2, ..., N
 267   // iterations of the loop. For this we compute the number for iterations after
 268   // which every Phi is guaranteed to become an invariant, and try to peel the
 269   // maximum number of iterations among these values, thus turning all those
 270   // Phis into invariants.
 271   // First, check that we can peel at least one iteration.
 272   if (2 * LoopSize <= UP.Threshold && UnrollPeelMaxCount > 0) {
 273     // Store the pre-calculated values here.
 274     SmallDenseMap<PHINode *, unsigned> IterationsToInvariance;
 275     // Now go through all Phis to calculate their the number of iterations they
 276     // need to become invariants.
 277     // Start the max computation with the UP.PeelCount value set by the target
 278     // in TTI.getUnrollingPreferences or by the flag -unroll-peel-count.
 279     unsigned DesiredPeelCount = TargetPeelCount;
 280     BasicBlock *BackEdge = L->getLoopLatch();
 281     assert(BackEdge && "Loop is not in simplified form?");
 282     for (auto BI = L->getHeader()->begin(); isa<PHINode>(&*BI); ++BI) {
 283       PHINode *Phi = cast<PHINode>(&*BI);
 284       unsigned ToInvariance = calculateIterationsToInvariance(
 285           Phi, L, BackEdge, IterationsToInvariance);
 286       if (ToInvariance != InfiniteIterationsToInvariance)
 287         DesiredPeelCount = std::max(DesiredPeelCount, ToInvariance);
 288     }
 289
 290     // Pay respect to limitations implied by loop size and the max peel count.
 291     unsigned MaxPeelCount = UnrollPeelMaxCount;
 292     MaxPeelCount = std::min(MaxPeelCount, UP.Threshold / LoopSize - 1);
 293
 294     DesiredPeelCount = std::max(DesiredPeelCount,
 295                                 countToEliminateCompares(*L, MaxPeelCount, SE));
 296
 297     if (DesiredPeelCount > 0) {
 298       DesiredPeelCount = std::min(DesiredPeelCount, MaxPeelCount);
 299       // Consider max peel count limitation.
 300       assert(DesiredPeelCount > 0 && "Wrong loop size estimation?");
 301       LLVM_DEBUG(dbgs() << "Peel " << DesiredPeelCount
 302                         << " iteration(s) to turn"
 303                         << " some Phis into invariants.\n");
 304       UP.PeelCount = DesiredPeelCount;
 305       return;
 306     }
 307   }
 308
 309   // Bail if we know the statically calculated trip count.
 310   // In this case we rather prefer partial unrolling.
 311   if (TripCount)
 312     return;
 313
 314   // If we don't know the trip count, but have reason to believe the average
 315   // trip count is low, peeling should be beneficial, since we will usually
 316   // hit the peeled section.
 317   // We only do this in the presence of profile information, since otherwise
 318   // our estimates of the trip count are not reliable enough.
 319   if (L->getHeader()->getParent()->hasProfileData()) {
 320     Optional<unsigned> PeelCount = getLoopEstimatedTripCount(L);
 321     if (!PeelCount)
 322       return;
 323
 324     LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is " << *PeelCount
 325                       << "\n");
 326
 327     if (*PeelCount) {
 328       if ((*PeelCount <= UnrollPeelMaxCount) &&
 329           (LoopSize * (*PeelCount + 1) <= UP.Threshold)) {
 330         LLVM_DEBUG(dbgs() << "Peeling first " << *PeelCount
 331                           << " iterations.\n");
 332         UP.PeelCount = *PeelCount;
 333         return;
 334       }
 335       LLVM_DEBUG(dbgs() << "Requested peel count: " << *PeelCount << "\n");
 336       LLVM_DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n");
 337       LLVM_DEBUG(dbgs() << "Peel cost: " << LoopSize * (*PeelCount + 1)
 338                         << "\n");
 339       LLVM_DEBUG(dbgs() << "Max peel cost: " << UP.Threshold << "\n");
 340     }
 341   }
 342 }
 343
 344 /// Update the branch weights of the latch of a peeled-off loop
 345 /// iteration.
 346 /// This sets the branch weights for the latch of the recently peeled off loop
 347 /// iteration correctly.
 348 /// Our goal is to make sure that:
 349 /// a) The total weight of all the copies of the loop body is preserved.
 350 /// b) The total weight of the loop exit is preserved.
 351 /// c) The body weight is reasonably distributed between the peeled iterations.
 352 ///
 353 /// \param Header The copy of the header block that belongs to next iteration.
 354 /// \param LatchBR The copy of the latch branch that belongs to this iteration.
 355 /// \param IterNumber The serial number of the iteration that was just
 356 /// peeled off.
 357 /// \param AvgIters The average number of iterations we expect the loop to have.
 358 /// \param[in,out] PeeledHeaderWeight The total number of dynamic loop
 359 /// iterations that are unaccounted for. As an input, it represents the number
 360 /// of times we expect to enter the header of the iteration currently being
 361 /// peeled off. The output is the number of times we expect to enter the
 362 /// header of the next iteration.
 363 static void updateBranchWeights(BasicBlock *Header, BranchInst *LatchBR,
 364                                 unsigned IterNumber, unsigned AvgIters,
 365                                 uint64_t &PeeledHeaderWeight) {
 366   // FIXME: Pick a more realistic distribution.
 367   // Currently the proportion of weight we assign to the fall-through
 368   // side of the branch drops linearly with the iteration number, and we use
 369   // a 0.9 fudge factor to make the drop-off less sharp...
 370   if (PeeledHeaderWeight) {
 371     uint64_t FallThruWeight =
 372         PeeledHeaderWeight * ((float)(AvgIters - IterNumber) / AvgIters * 0.9);
 373     uint64_t ExitWeight = PeeledHeaderWeight - FallThruWeight;
 374     PeeledHeaderWeight -= ExitWeight;
 375
 376     unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
 377     MDBuilder MDB(LatchBR->getContext());
 378     MDNode *WeightNode =
 379         HeaderIdx ? MDB.createBranchWeights(ExitWeight, FallThruWeight)
 380                   : MDB.createBranchWeights(FallThruWeight, ExitWeight);
 381     LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
 382   }
 383 }
 384
 385 /// Clones the body of the loop L, putting it between \p InsertTop and \p
 386 /// InsertBot.
 387 /// \param IterNumber The serial number of the iteration currently being
 388 /// peeled off.
 389 /// \param Exit The exit block of the original loop.
 390 /// \param[out] NewBlocks A list of the blocks in the newly created clone
 391 /// \param[out] VMap The value map between the loop and the new clone.
 392 /// \param LoopBlocks A helper for DFS-traversal of the loop.
 393 /// \param LVMap A value-map that maps instructions from the original loop to
 394 /// instructions in the last peeled-off iteration.
 395 static void cloneLoopBlocks(Loop *L, unsigned IterNumber, BasicBlock *InsertTop,
 396                             BasicBlock *InsertBot, BasicBlock *Exit,
 397                             SmallVectorImpl<BasicBlock *> &NewBlocks,
 398                             LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap,
 399                             ValueToValueMapTy &LVMap, DominatorTree *DT,
 400                             LoopInfo *LI) {
 401   BasicBlock *Header = L->getHeader();
 402   BasicBlock *Latch = L->getLoopLatch();
 403   BasicBlock *PreHeader = L->getLoopPreheader();
 404
 405   Function *F = Header->getParent();
 406   LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
 407   LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
 408   Loop *ParentLoop = L->getParentLoop();
 409
 410   // For each block in the original loop, create a new copy,
 411   // and update the value map with the newly created values.
 412   for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
 413     BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".peel", F);
 414     NewBlocks.push_back(NewBB);
 415
 416     if (ParentLoop)
 417       ParentLoop->addBasicBlockToLoop(NewBB, *LI);
 418
 419     VMap[*BB] = NewBB;
 420
 421     // If dominator tree is available, insert nodes to represent cloned blocks.
 422     if (DT) {
 423       if (Header == *BB)
 424         DT->addNewBlock(NewBB, InsertTop);
 425       else {
 426         DomTreeNode *IDom = DT->getNode(*BB)->getIDom();
 427         // VMap must contain entry for IDom, as the iteration order is RPO.
 428         DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDom->getBlock()]));
 429       }
 430     }
 431   }
 432
 433   // Hook-up the control flow for the newly inserted blocks.
 434   // The new header is hooked up directly to the "top", which is either
 435   // the original loop preheader (for the first iteration) or the previous
 436   // iteration's exiting block (for every other iteration)
 437   InsertTop->getTerminator()->setSuccessor(0, cast<BasicBlock>(VMap[Header]));
 438
 439   // Similarly, for the latch:
 440   // The original exiting edge is still hooked up to the loop exit.
 441   // The backedge now goes to the "bottom", which is either the loop's real
 442   // header (for the last peeled iteration) or the copied header of the next
 443   // iteration (for every other iteration)
 444   BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
 445   BranchInst *LatchBR = cast<BranchInst>(NewLatch->getTerminator());
 446   unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
 447   LatchBR->setSuccessor(HeaderIdx, InsertBot);
 448   LatchBR->setSuccessor(1 - HeaderIdx, Exit);
 449   if (DT)
 450     DT->changeImmediateDominator(InsertBot, NewLatch);
 451
 452   // The new copy of the loop body starts with a bunch of PHI nodes
 453   // that pick an incoming value from either the preheader, or the previous
 454   // loop iteration. Since this copy is no longer part of the loop, we
 455   // resolve this statically:
 456   // For the first iteration, we use the value from the preheader directly.
 457   // For any other iteration, we replace the phi with the value generated by
 458   // the immediately preceding clone of the loop body (which represents
 459   // the previous iteration).
 460   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 461     PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
 462     if (IterNumber == 0) {
 463       VMap[&*I] = NewPHI->getIncomingValueForBlock(PreHeader);
 464     } else {
 465       Value *LatchVal = NewPHI->getIncomingValueForBlock(Latch);
 466       Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
 467       if (LatchInst && L->contains(LatchInst))
 468         VMap[&*I] = LVMap[LatchInst];
 469       else
 470         VMap[&*I] = LatchVal;
 471     }
 472     cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
 473   }
 474
 475   // Fix up the outgoing values - we need to add a value for the iteration
 476   // we've just created. Note that this must happen *after* the incoming
 477   // values are adjusted, since the value going out of the latch may also be
 478   // a value coming into the header.
 479   for (BasicBlock::iterator I = Exit->begin(); isa<PHINode>(I); ++I) {
 480     PHINode *PHI = cast<PHINode>(I);
 481     Value *LatchVal = PHI->getIncomingValueForBlock(Latch);
 482     Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
 483     if (LatchInst && L->contains(LatchInst))
 484       LatchVal = VMap[LatchVal];
 485     PHI->addIncoming(LatchVal, cast<BasicBlock>(VMap[Latch]));
 486   }
 487
 488   // LastValueMap is updated with the values for the current loop
 489   // which are used the next time this function is called.
 490   for (const auto &KV : VMap)
 491     LVMap[KV.first] = KV.second;
 492 }
 493
 494 /// Peel off the first \p PeelCount iterations of loop \p L.
 495 ///
 496 /// Note that this does not peel them off as a single straight-line block.
 497 /// Rather, each iteration is peeled off separately, and needs to check the
 498 /// exit condition.
 499 /// For loops that dynamically execute \p PeelCount iterations or less
 500 /// this provides a benefit, since the peeled off iterations, which account
 501 /// for the bulk of dynamic execution, can be further simplified by scalar
 502 /// optimizations.
 503 bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
 504                     ScalarEvolution *SE, DominatorTree *DT,
 505                     AssumptionCache *AC, bool PreserveLCSSA) {
 506   assert(PeelCount > 0 && "Attempt to peel out zero iterations?");
 507   assert(canPeel(L) && "Attempt to peel a loop which is not peelable?");
 508
 509   LoopBlocksDFS LoopBlocks(L);
 510   LoopBlocks.perform(LI);
 511
 512   BasicBlock *Header = L->getHeader();
 513   BasicBlock *PreHeader = L->getLoopPreheader();
 514   BasicBlock *Latch = L->getLoopLatch();
 515   BasicBlock *Exit = L->getUniqueExitBlock();
 516
 517   Function *F = Header->getParent();
 518
 519   // Set up all the necessary basic blocks. It is convenient to split the
 520   // preheader into 3 parts - two blocks to anchor the peeled copy of the loop
 521   // body, and a new preheader for the "real" loop.
 522
 523   // Peeling the first iteration transforms.
 524   //
 525   // PreHeader:
 526   // ...
 527   // Header:
 528   //   LoopBody
 529   //   If (cond) goto Header
 530   // Exit:
 531   //
 532   // into
 533   //
 534   // InsertTop:
 535   //   LoopBody
 536   //   If (!cond) goto Exit
 537   // InsertBot:
 538   // NewPreHeader:
 539   // ...
 540   // Header:
 541   //  LoopBody
 542   //  If (cond) goto Header
 543   // Exit:
 544   //
 545   // Each following iteration will split the current bottom anchor in two,
 546   // and put the new copy of the loop body between these two blocks. That is,
 547   // after peeling another iteration from the example above, we'll split
 548   // InsertBot, and get:
 549   //
 550   // InsertTop:
 551   //   LoopBody
 552   //   If (!cond) goto Exit
 553   // InsertBot:
 554   //   LoopBody
 555   //   If (!cond) goto Exit
 556   // InsertBot.next:
 557   // NewPreHeader:
 558   // ...
 559   // Header:
 560   //  LoopBody
 561   //  If (cond) goto Header
 562   // Exit:
 563
 564   BasicBlock *InsertTop = SplitEdge(PreHeader, Header, DT, LI);
 565   BasicBlock *InsertBot =
 566       SplitBlock(InsertTop, InsertTop->getTerminator(), DT, LI);
 567   BasicBlock *NewPreHeader =
 568       SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI);
 569
 570   InsertTop->setName(Header->getName() + ".peel.begin");
 571   InsertBot->setName(Header->getName() + ".peel.next");
 572   NewPreHeader->setName(PreHeader->getName() + ".peel.newph");
 573
 574   ValueToValueMapTy LVMap;
 575
 576   // If we have branch weight information, we'll want to update it for the
 577   // newly created branches.
 578   BranchInst *LatchBR =
 579       cast<BranchInst>(cast<BasicBlock>(Latch)->getTerminator());
 580   unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
 581
 582   uint64_t TrueWeight, FalseWeight;
 583   uint64_t ExitWeight = 0, CurHeaderWeight = 0;
 584   if (LatchBR->extractProfMetadata(TrueWeight, FalseWeight)) {
 585     ExitWeight = HeaderIdx ? TrueWeight : FalseWeight;
 586     // The # of times the loop body executes is the sum of the exit block
 587     // weight and the # of times the backedges are taken.
 588     CurHeaderWeight = TrueWeight + FalseWeight;
 589   }
 590
 591   // For each peeled-off iteration, make a copy of the loop.
 592   for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
 593     SmallVector<BasicBlock *, 8> NewBlocks;
 594     ValueToValueMapTy VMap;
 595
 596     // Subtract the exit weight from the current header weight -- the exit
 597     // weight is exactly the weight of the previous iteration's header.
 598     // FIXME: due to the way the distribution is constructed, we need a
 599     // guard here to make sure we don't end up with non-positive weights.
 600     if (ExitWeight < CurHeaderWeight)
 601       CurHeaderWeight -= ExitWeight;
 602     else
 603       CurHeaderWeight = 1;
 604
 605     cloneLoopBlocks(L, Iter, InsertTop, InsertBot, Exit,
 606                     NewBlocks, LoopBlocks, VMap, LVMap, DT, LI);
 607
 608     // Remap to use values from the current iteration instead of the
 609     // previous one.
 610     remapInstructionsInBlocks(NewBlocks, VMap);
 611
 612     if (DT) {
 613       // Latches of the cloned loops dominate over the loop exit, so idom of the
 614       // latter is the first cloned loop body, as original PreHeader dominates
 615       // the original loop body.
 616       if (Iter == 0)
 617         DT->changeImmediateDominator(Exit, cast<BasicBlock>(LVMap[Latch]));
 618 #ifdef EXPENSIVE_CHECKS
 619       assert(DT->verify(DominatorTree::VerificationLevel::Fast));
 620 #endif
 621     }
 622
 623     auto *LatchBRCopy = cast<BranchInst>(VMap[LatchBR]);
 624     updateBranchWeights(InsertBot, LatchBRCopy, Iter,
 625                         PeelCount, ExitWeight);
 626     // Remove Loop metadata from the latch branch instruction
 627     // because it is not the Loop's latch branch anymore.
 628     LatchBRCopy->setMetadata(LLVMContext::MD_loop, nullptr);
 629
 630     InsertTop = InsertBot;
 631     InsertBot = SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI);
 632     InsertBot->setName(Header->getName() + ".peel.next");
 633
 634     F->getBasicBlockList().splice(InsertTop->getIterator(),
 635                                   F->getBasicBlockList(),
 636                                   NewBlocks[0]->getIterator(), F->end());
 637   }
 638
 639   // Now adjust the phi nodes in the loop header to get their initial values
 640   // from the last peeled-off iteration instead of the preheader.
 641   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 642     PHINode *PHI = cast<PHINode>(I);
 643     Value *NewVal = PHI->getIncomingValueForBlock(Latch);
 644     Instruction *LatchInst = dyn_cast<Instruction>(NewVal);
 645     if (LatchInst && L->contains(LatchInst))
 646       NewVal = LVMap[LatchInst];
 647
 648     PHI->setIncomingValue(PHI->getBasicBlockIndex(NewPreHeader), NewVal);
 649   }
 650
 651   // Adjust the branch weights on the loop exit.
 652   if (ExitWeight) {
 653     // The backedge count is the difference of current header weight and
 654     // current loop exit weight. If the current header weight is smaller than
 655     // the current loop exit weight, we mark the loop backedge weight as 1.
 656     uint64_t BackEdgeWeight = 0;
 657     if (ExitWeight < CurHeaderWeight)
 658       BackEdgeWeight = CurHeaderWeight - ExitWeight;
 659     else
 660       BackEdgeWeight = 1;
 661     MDBuilder MDB(LatchBR->getContext());
 662     MDNode *WeightNode =
 663         HeaderIdx ? MDB.createBranchWeights(ExitWeight, BackEdgeWeight)
 664                   : MDB.createBranchWeights(BackEdgeWeight, ExitWeight);
 665     LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
 666   }
 667
 668   // If the loop is nested, we changed the parent loop, update SE.
 669   if (Loop *ParentLoop = L->getParentLoop()) {
 670     SE->forgetLoop(ParentLoop);
 671
 672     // FIXME: Incrementally update loop-simplify
 673     simplifyLoop(ParentLoop, DT, LI, SE, AC, PreserveLCSSA);
 674   } else {
 675     // FIXME: Incrementally update loop-simplify
 676     simplifyLoop(L, DT, LI, SE, AC, PreserveLCSSA);
 677   }
 678
 679   NumPeeled++;
 680
 681   return true;
 682 }