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

   1 //===- LoopPeel.cpp -------------------------------------------------------===//
   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 // Loop Peeling Utilities.
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "llvm/Transforms/Utils/LoopPeel.h"
  13 #include "llvm/ADT/DenseMap.h"
  14 #include "llvm/ADT/Optional.h"
  15 #include "llvm/ADT/SmallVector.h"
  16 #include "llvm/ADT/Statistic.h"
  17 #include "llvm/Analysis/Loads.h"
  18 #include "llvm/Analysis/LoopInfo.h"
  19 #include "llvm/Analysis/LoopIterator.h"
  20 #include "llvm/Analysis/ScalarEvolution.h"
  21 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  22 #include "llvm/Analysis/TargetTransformInfo.h"
  23 #include "llvm/IR/BasicBlock.h"
  24 #include "llvm/IR/Dominators.h"
  25 #include "llvm/IR/Function.h"
  26 #include "llvm/IR/InstrTypes.h"
  27 #include "llvm/IR/Instruction.h"
  28 #include "llvm/IR/Instructions.h"
  29 #include "llvm/IR/LLVMContext.h"
  30 #include "llvm/IR/MDBuilder.h"
  31 #include "llvm/IR/Metadata.h"
  32 #include "llvm/IR/PatternMatch.h"
  33 #include "llvm/Support/Casting.h"
  34 #include "llvm/Support/CommandLine.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Support/raw_ostream.h"
  37 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  38 #include "llvm/Transforms/Utils/Cloning.h"
  39 #include "llvm/Transforms/Utils/LoopSimplify.h"
  40 #include "llvm/Transforms/Utils/LoopUtils.h"
  41 #include "llvm/Transforms/Utils/UnrollLoop.h"
  42 #include "llvm/Transforms/Utils/ValueMapper.h"
  43 #include <algorithm>
  44 #include <cassert>
  45 #include <cstdint>
  46 #include <limits>
  47
  48 using namespace llvm;
  49 using namespace llvm::PatternMatch;
  50
  51 #define DEBUG_TYPE "loop-peel"
  52
  53 STATISTIC(NumPeeled, "Number of loops peeled");
  54
  55 static cl::opt<unsigned> UnrollPeelCount(
  56     "unroll-peel-count", cl::Hidden,
  57     cl::desc("Set the unroll peeling count, for testing purposes"));
  58
  59 static cl::opt<bool>
  60     UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden,
  61                        cl::desc("Allows loops to be peeled when the dynamic "
  62                                 "trip count is known to be low."));
  63
  64 static cl::opt<bool>
  65     UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling",
  66                                 cl::init(false), cl::Hidden,
  67                                 cl::desc("Allows loop nests to be peeled."));
  68
  69 static cl::opt<unsigned> UnrollPeelMaxCount(
  70     "unroll-peel-max-count", cl::init(7), cl::Hidden,
  71     cl::desc("Max average trip count which will cause loop peeling."));
  72
  73 static cl::opt<unsigned> UnrollForcePeelCount(
  74     "unroll-force-peel-count", cl::init(0), cl::Hidden,
  75     cl::desc("Force a peel count regardless of profiling information."));
  76
  77 static const char *PeeledCountMetaData = "llvm.loop.peeled.count";
  78
  79 // Check whether we are capable of peeling this loop.
  80 bool llvm::canPeel(Loop *L) {
  81   // Make sure the loop is in simplified form
  82   if (!L->isLoopSimplifyForm())
  83     return false;
  84
  85   // Don't try to peel loops where the latch is not the exiting block.
  86   // This can be an indication of two different things:
  87   // 1) The loop is not rotated.
  88   // 2) The loop contains irreducible control flow that involves the latch.
  89   const BasicBlock *Latch = L->getLoopLatch();
  90   if (!L->isLoopExiting(Latch))
  91     return false;
  92
  93   // Peeling is only supported if the latch is a branch.
  94   if (!isa<BranchInst>(Latch->getTerminator()))
  95     return false;
  96
  97   SmallVector<BasicBlock *, 4> Exits;
  98   L->getUniqueNonLatchExitBlocks(Exits);
  99   // The latch must either be the only exiting block or all non-latch exit
 100   // blocks have either a deopt or unreachable terminator or compose a chain of
 101   // blocks where the last one is either deopt or unreachable terminated. Both
 102   // deopt and unreachable terminators are a strong indication they are not
 103   // taken. Note that this is a profitability check, not a legality check. Also
 104   // note that LoopPeeling currently can only update the branch weights of latch
 105   // blocks and branch weights to blocks with deopt or unreachable do not need
 106   // updating.
 107   return all_of(Exits, [](const BasicBlock *BB) {
 108     return IsBlockFollowedByDeoptOrUnreachable(BB);
 109   });
 110 }
 111
 112 // This function calculates the number of iterations after which the given Phi
 113 // becomes an invariant. The pre-calculated values are memorized in the map. The
 114 // function (shortcut is I) is calculated according to the following definition:
 115 // Given %x = phi <Inputs from above the loop>, ..., [%y, %back.edge].
 116 //   If %y is a loop invariant, then I(%x) = 1.
 117 //   If %y is a Phi from the loop header, I(%x) = I(%y) + 1.
 118 //   Otherwise, I(%x) is infinite.
 119 // TODO: Actually if %y is an expression that depends only on Phi %z and some
 120 //       loop invariants, we can estimate I(%x) = I(%z) + 1. The example
 121 //       looks like:
 122 //         %x = phi(0, %a),  <-- becomes invariant starting from 3rd iteration.
 123 //         %y = phi(0, 5),
 124 //         %a = %y + 1.
 125 static Optional<unsigned> calculateIterationsToInvariance(
 126     PHINode *Phi, Loop *L, BasicBlock *BackEdge,
 127     SmallDenseMap<PHINode *, Optional<unsigned> > &IterationsToInvariance) {
 128   assert(Phi->getParent() == L->getHeader() &&
 129          "Non-loop Phi should not be checked for turning into invariant.");
 130   assert(BackEdge == L->getLoopLatch() && "Wrong latch?");
 131   // If we already know the answer, take it from the map.
 132   auto I = IterationsToInvariance.find(Phi);
 133   if (I != IterationsToInvariance.end())
 134     return I->second;
 135
 136   // Otherwise we need to analyze the input from the back edge.
 137   Value *Input = Phi->getIncomingValueForBlock(BackEdge);
 138   // Place infinity to map to avoid infinite recursion for cycled Phis. Such
 139   // cycles can never stop on an invariant.
 140   IterationsToInvariance[Phi] = None;
 141   Optional<unsigned> ToInvariance = None;
 142
 143   if (L->isLoopInvariant(Input))
 144     ToInvariance = 1u;
 145   else if (PHINode *IncPhi = dyn_cast<PHINode>(Input)) {
 146     // Only consider Phis in header block.
 147     if (IncPhi->getParent() != L->getHeader())
 148       return None;
 149     // If the input becomes an invariant after X iterations, then our Phi
 150     // becomes an invariant after X + 1 iterations.
 151     auto InputToInvariance = calculateIterationsToInvariance(
 152         IncPhi, L, BackEdge, IterationsToInvariance);
 153     if (InputToInvariance)
 154       ToInvariance = *InputToInvariance + 1u;
 155   }
 156
 157   // If we found that this Phi lies in an invariant chain, update the map.
 158   if (ToInvariance)
 159     IterationsToInvariance[Phi] = ToInvariance;
 160   return ToInvariance;
 161 }
 162
 163 // Try to find any invariant memory reads that will become dereferenceable in
 164 // the remainder loop after peeling. The load must also be used (transitively)
 165 // by an exit condition. Returns the number of iterations to peel off (at the
 166 // moment either 0 or 1).
 167 static unsigned peelToTurnInvariantLoadsDerefencebale(Loop &L,
 168                                                       DominatorTree &DT) {
 169   // Skip loops with a single exiting block, because there should be no benefit
 170   // for the heuristic below.
 171   if (L.getExitingBlock())
 172     return 0;
 173
 174   // All non-latch exit blocks must have an UnreachableInst terminator.
 175   // Otherwise the heuristic below may not be profitable.
 176   SmallVector<BasicBlock *, 4> Exits;
 177   L.getUniqueNonLatchExitBlocks(Exits);
 178   if (any_of(Exits, [](const BasicBlock *BB) {
 179         return !isa<UnreachableInst>(BB->getTerminator());
 180       }))
 181     return 0;
 182
 183   // Now look for invariant loads that dominate the latch and are not known to
 184   // be dereferenceable. If there are such loads and no writes, they will become
 185   // dereferenceable in the loop if the first iteration is peeled off. Also
 186   // collect the set of instructions controlled by such loads. Only peel if an
 187   // exit condition uses (transitively) such a load.
 188   BasicBlock *Header = L.getHeader();
 189   BasicBlock *Latch = L.getLoopLatch();
 190   SmallPtrSet<Value *, 8> LoadUsers;
 191   const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
 192   for (BasicBlock *BB : L.blocks()) {
 193     for (Instruction &I : *BB) {
 194       if (I.mayWriteToMemory())
 195         return 0;
 196
 197       auto Iter = LoadUsers.find(&I);
 198       if (Iter != LoadUsers.end()) {
 199         for (Value *U : I.users())
 200           LoadUsers.insert(U);
 201       }
 202       // Do not look for reads in the header; they can already be hoisted
 203       // without peeling.
 204       if (BB == Header)
 205         continue;
 206       if (auto *LI = dyn_cast<LoadInst>(&I)) {
 207         Value *Ptr = LI->getPointerOperand();
 208         if (DT.dominates(BB, Latch) && L.isLoopInvariant(Ptr) &&
 209             !isDereferenceablePointer(Ptr, LI->getType(), DL, LI, &DT))
 210           for (Value *U : I.users())
 211             LoadUsers.insert(U);
 212       }
 213     }
 214   }
 215   SmallVector<BasicBlock *> ExitingBlocks;
 216   L.getExitingBlocks(ExitingBlocks);
 217   if (any_of(ExitingBlocks, [&LoadUsers](BasicBlock *Exiting) {
 218         return LoadUsers.contains(Exiting->getTerminator());
 219       }))
 220     return 1;
 221   return 0;
 222 }
 223
 224 // Return the number of iterations to peel off that make conditions in the
 225 // body true/false. For example, if we peel 2 iterations off the loop below,
 226 // the condition i < 2 can be evaluated at compile time.
 227 //  for (i = 0; i < n; i++)
 228 //    if (i < 2)
 229 //      ..
 230 //    else
 231 //      ..
 232 //   }
 233 static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount,
 234                                          ScalarEvolution &SE) {
 235   assert(L.isLoopSimplifyForm() && "Loop needs to be in loop simplify form");
 236   unsigned DesiredPeelCount = 0;
 237
 238   for (auto *BB : L.blocks()) {
 239     auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
 240     if (!BI || BI->isUnconditional())
 241       continue;
 242
 243     // Ignore loop exit condition.
 244     if (L.getLoopLatch() == BB)
 245       continue;
 246
 247     Value *Condition = BI->getCondition();
 248     Value *LeftVal, *RightVal;
 249     CmpInst::Predicate Pred;
 250     if (!match(Condition, m_ICmp(Pred, m_Value(LeftVal), m_Value(RightVal))))
 251       continue;
 252
 253     const SCEV *LeftSCEV = SE.getSCEV(LeftVal);
 254     const SCEV *RightSCEV = SE.getSCEV(RightVal);
 255
 256     // Do not consider predicates that are known to be true or false
 257     // independently of the loop iteration.
 258     if (SE.evaluatePredicate(Pred, LeftSCEV, RightSCEV))
 259       continue;
 260
 261     // Check if we have a condition with one AddRec and one non AddRec
 262     // expression. Normalize LeftSCEV to be the AddRec.
 263     if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
 264       if (isa<SCEVAddRecExpr>(RightSCEV)) {
 265         std::swap(LeftSCEV, RightSCEV);
 266         Pred = ICmpInst::getSwappedPredicate(Pred);
 267       } else
 268         continue;
 269     }
 270
 271     const SCEVAddRecExpr *LeftAR = cast<SCEVAddRecExpr>(LeftSCEV);
 272
 273     // Avoid huge SCEV computations in the loop below, make sure we only
 274     // consider AddRecs of the loop we are trying to peel.
 275     if (!LeftAR->isAffine() || LeftAR->getLoop() != &L)
 276       continue;
 277     if (!(ICmpInst::isEquality(Pred) && LeftAR->hasNoSelfWrap()) &&
 278         !SE.getMonotonicPredicateType(LeftAR, Pred))
 279       continue;
 280
 281     // Check if extending the current DesiredPeelCount lets us evaluate Pred
 282     // or !Pred in the loop body statically.
 283     unsigned NewPeelCount = DesiredPeelCount;
 284
 285     const SCEV *IterVal = LeftAR->evaluateAtIteration(
 286         SE.getConstant(LeftSCEV->getType(), NewPeelCount), SE);
 287
 288     // If the original condition is not known, get the negated predicate
 289     // (which holds on the else branch) and check if it is known. This allows
 290     // us to peel of iterations that make the original condition false.
 291     if (!SE.isKnownPredicate(Pred, IterVal, RightSCEV))
 292       Pred = ICmpInst::getInversePredicate(Pred);
 293
 294     const SCEV *Step = LeftAR->getStepRecurrence(SE);
 295     const SCEV *NextIterVal = SE.getAddExpr(IterVal, Step);
 296     auto PeelOneMoreIteration = [&IterVal, &NextIterVal, &SE, Step,
 297                                  &NewPeelCount]() {
 298       IterVal = NextIterVal;
 299       NextIterVal = SE.getAddExpr(IterVal, Step);
 300       NewPeelCount++;
 301     };
 302
 303     auto CanPeelOneMoreIteration = [&NewPeelCount, &MaxPeelCount]() {
 304       return NewPeelCount < MaxPeelCount;
 305     };
 306
 307     while (CanPeelOneMoreIteration() &&
 308            SE.isKnownPredicate(Pred, IterVal, RightSCEV))
 309       PeelOneMoreIteration();
 310
 311     // With *that* peel count, does the predicate !Pred become known in the
 312     // first iteration of the loop body after peeling?
 313     if (!SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), IterVal,
 314                              RightSCEV))
 315       continue; // If not, give up.
 316
 317     // However, for equality comparisons, that isn't always sufficient to
 318     // eliminate the comparsion in loop body, we may need to peel one more
 319     // iteration. See if that makes !Pred become unknown again.
 320     if (ICmpInst::isEquality(Pred) &&
 321         !SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), NextIterVal,
 322                              RightSCEV) &&
 323         !SE.isKnownPredicate(Pred, IterVal, RightSCEV) &&
 324         SE.isKnownPredicate(Pred, NextIterVal, RightSCEV)) {
 325       if (!CanPeelOneMoreIteration())
 326         continue; // Need to peel one more iteration, but can't. Give up.
 327       PeelOneMoreIteration(); // Great!
 328     }
 329
 330     DesiredPeelCount = std::max(DesiredPeelCount, NewPeelCount);
 331   }
 332
 333   return DesiredPeelCount;
 334 }
 335
 336 // Return the number of iterations we want to peel off.
 337 void llvm::computePeelCount(Loop *L, unsigned LoopSize,
 338                             TargetTransformInfo::PeelingPreferences &PP,
 339                             unsigned &TripCount, DominatorTree &DT,
 340                             ScalarEvolution &SE, unsigned Threshold) {
 341   assert(LoopSize > 0 && "Zero loop size is not allowed!");
 342   // Save the PP.PeelCount value set by the target in
 343   // TTI.getPeelingPreferences or by the flag -unroll-peel-count.
 344   unsigned TargetPeelCount = PP.PeelCount;
 345   PP.PeelCount = 0;
 346   if (!canPeel(L))
 347     return;
 348
 349   // Only try to peel innermost loops by default.
 350   // The constraint can be relaxed by the target in TTI.getUnrollingPreferences
 351   // or by the flag -unroll-allow-loop-nests-peeling.
 352   if (!PP.AllowLoopNestsPeeling && !L->isInnermost())
 353     return;
 354
 355   // If the user provided a peel count, use that.
 356   bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0;
 357   if (UserPeelCount) {
 358     LLVM_DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount
 359                       << " iterations.\n");
 360     PP.PeelCount = UnrollForcePeelCount;
 361     PP.PeelProfiledIterations = true;
 362     return;
 363   }
 364
 365   // Skip peeling if it's disabled.
 366   if (!PP.AllowPeeling)
 367     return;
 368
 369   unsigned AlreadyPeeled = 0;
 370   if (auto Peeled = getOptionalIntLoopAttribute(L, PeeledCountMetaData))
 371     AlreadyPeeled = *Peeled;
 372   // Stop if we already peeled off the maximum number of iterations.
 373   if (AlreadyPeeled >= UnrollPeelMaxCount)
 374     return;
 375
 376   // Here we try to get rid of Phis which become invariants after 1, 2, ..., N
 377   // iterations of the loop. For this we compute the number for iterations after
 378   // which every Phi is guaranteed to become an invariant, and try to peel the
 379   // maximum number of iterations among these values, thus turning all those
 380   // Phis into invariants.
 381   // First, check that we can peel at least one iteration.
 382   if (2 * LoopSize <= Threshold && UnrollPeelMaxCount > 0) {
 383     // Store the pre-calculated values here.
 384     SmallDenseMap<PHINode *, Optional<unsigned> > IterationsToInvariance;
 385     // Now go through all Phis to calculate their the number of iterations they
 386     // need to become invariants.
 387     // Start the max computation with the UP.PeelCount value set by the target
 388     // in TTI.getUnrollingPreferences or by the flag -unroll-peel-count.
 389     unsigned DesiredPeelCount = TargetPeelCount;
 390     BasicBlock *BackEdge = L->getLoopLatch();
 391     assert(BackEdge && "Loop is not in simplified form?");
 392     for (auto BI = L->getHeader()->begin(); isa<PHINode>(&*BI); ++BI) {
 393       PHINode *Phi = cast<PHINode>(&*BI);
 394       auto ToInvariance = calculateIterationsToInvariance(
 395           Phi, L, BackEdge, IterationsToInvariance);
 396       if (ToInvariance)
 397         DesiredPeelCount = std::max(DesiredPeelCount, *ToInvariance);
 398     }
 399
 400     // Pay respect to limitations implied by loop size and the max peel count.
 401     unsigned MaxPeelCount = UnrollPeelMaxCount;
 402     MaxPeelCount = std::min(MaxPeelCount, Threshold / LoopSize - 1);
 403
 404     DesiredPeelCount = std::max(DesiredPeelCount,
 405                                 countToEliminateCompares(*L, MaxPeelCount, SE));
 406
 407     if (DesiredPeelCount == 0)
 408       DesiredPeelCount = peelToTurnInvariantLoadsDerefencebale(*L, DT);
 409
 410     if (DesiredPeelCount > 0) {
 411       DesiredPeelCount = std::min(DesiredPeelCount, MaxPeelCount);
 412       // Consider max peel count limitation.
 413       assert(DesiredPeelCount > 0 && "Wrong loop size estimation?");
 414       if (DesiredPeelCount + AlreadyPeeled <= UnrollPeelMaxCount) {
 415         LLVM_DEBUG(dbgs() << "Peel " << DesiredPeelCount
 416                           << " iteration(s) to turn"
 417                           << " some Phis into invariants.\n");
 418         PP.PeelCount = DesiredPeelCount;
 419         PP.PeelProfiledIterations = false;
 420         return;
 421       }
 422     }
 423   }
 424
 425   // Bail if we know the statically calculated trip count.
 426   // In this case we rather prefer partial unrolling.
 427   if (TripCount)
 428     return;
 429
 430   // Do not apply profile base peeling if it is disabled.
 431   if (!PP.PeelProfiledIterations)
 432     return;
 433   // If we don't know the trip count, but have reason to believe the average
 434   // trip count is low, peeling should be beneficial, since we will usually
 435   // hit the peeled section.
 436   // We only do this in the presence of profile information, since otherwise
 437   // our estimates of the trip count are not reliable enough.
 438   if (L->getHeader()->getParent()->hasProfileData()) {
 439     Optional<unsigned> PeelCount = getLoopEstimatedTripCount(L);
 440     if (!PeelCount)
 441       return;
 442
 443     LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is " << *PeelCount
 444                       << "\n");
 445
 446     if (*PeelCount) {
 447       if ((*PeelCount + AlreadyPeeled <= UnrollPeelMaxCount) &&
 448           (LoopSize * (*PeelCount + 1) <= Threshold)) {
 449         LLVM_DEBUG(dbgs() << "Peeling first " << *PeelCount
 450                           << " iterations.\n");
 451         PP.PeelCount = *PeelCount;
 452         return;
 453       }
 454       LLVM_DEBUG(dbgs() << "Requested peel count: " << *PeelCount << "\n");
 455       LLVM_DEBUG(dbgs() << "Already peel count: " << AlreadyPeeled << "\n");
 456       LLVM_DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n");
 457       LLVM_DEBUG(dbgs() << "Peel cost: " << LoopSize * (*PeelCount + 1)
 458                         << "\n");
 459       LLVM_DEBUG(dbgs() << "Max peel cost: " << Threshold << "\n");
 460     }
 461   }
 462 }
 463
 464 /// Update the branch weights of the latch of a peeled-off loop
 465 /// iteration.
 466 /// This sets the branch weights for the latch of the recently peeled off loop
 467 /// iteration correctly.
 468 /// Let F is a weight of the edge from latch to header.
 469 /// Let E is a weight of the edge from latch to exit.
 470 /// F/(F+E) is a probability to go to loop and E/(F+E) is a probability to
 471 /// go to exit.
 472 /// Then, Estimated TripCount = F / E.
 473 /// For I-th (counting from 0) peeled off iteration we set the the weights for
 474 /// the peeled latch as (TC - I, 1). It gives us reasonable distribution,
 475 /// The probability to go to exit 1/(TC-I) increases. At the same time
 476 /// the estimated trip count of remaining loop reduces by I.
 477 /// To avoid dealing with division rounding we can just multiple both part
 478 /// of weights to E and use weight as (F - I * E, E).
 479 ///
 480 /// \param Header The copy of the header block that belongs to next iteration.
 481 /// \param LatchBR The copy of the latch branch that belongs to this iteration.
 482 /// \param[in,out] FallThroughWeight The weight of the edge from latch to
 483 /// header before peeling (in) and after peeled off one iteration (out).
 484 static void updateBranchWeights(BasicBlock *Header, BranchInst *LatchBR,
 485                                 uint64_t ExitWeight,
 486                                 uint64_t &FallThroughWeight) {
 487   // FallThroughWeight is 0 means that there is no branch weights on original
 488   // latch block or estimated trip count is zero.
 489   if (!FallThroughWeight)
 490     return;
 491
 492   unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
 493   MDBuilder MDB(LatchBR->getContext());
 494   MDNode *WeightNode =
 495       HeaderIdx ? MDB.createBranchWeights(ExitWeight, FallThroughWeight)
 496                 : MDB.createBranchWeights(FallThroughWeight, ExitWeight);
 497   LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
 498   FallThroughWeight =
 499       FallThroughWeight > ExitWeight ? FallThroughWeight - ExitWeight : 1;
 500 }
 501
 502 /// Initialize the weights.
 503 ///
 504 /// \param Header The header block.
 505 /// \param LatchBR The latch branch.
 506 /// \param[out] ExitWeight The weight of the edge from Latch to Exit.
 507 /// \param[out] FallThroughWeight The weight of the edge from Latch to Header.
 508 static void initBranchWeights(BasicBlock *Header, BranchInst *LatchBR,
 509                               uint64_t &ExitWeight,
 510                               uint64_t &FallThroughWeight) {
 511   uint64_t TrueWeight, FalseWeight;
 512   if (!LatchBR->extractProfMetadata(TrueWeight, FalseWeight))
 513     return;
 514   unsigned HeaderIdx = LatchBR->getSuccessor(0) == Header ? 0 : 1;
 515   ExitWeight = HeaderIdx ? TrueWeight : FalseWeight;
 516   FallThroughWeight = HeaderIdx ? FalseWeight : TrueWeight;
 517 }
 518
 519 /// Update the weights of original Latch block after peeling off all iterations.
 520 ///
 521 /// \param Header The header block.
 522 /// \param LatchBR The latch branch.
 523 /// \param ExitWeight The weight of the edge from Latch to Exit.
 524 /// \param FallThroughWeight The weight of the edge from Latch to Header.
 525 static void fixupBranchWeights(BasicBlock *Header, BranchInst *LatchBR,
 526                                uint64_t ExitWeight,
 527                                uint64_t FallThroughWeight) {
 528   // FallThroughWeight is 0 means that there is no branch weights on original
 529   // latch block or estimated trip count is zero.
 530   if (!FallThroughWeight)
 531     return;
 532
 533   // Sets the branch weights on the loop exit.
 534   MDBuilder MDB(LatchBR->getContext());
 535   unsigned HeaderIdx = LatchBR->getSuccessor(0) == Header ? 0 : 1;
 536   MDNode *WeightNode =
 537       HeaderIdx ? MDB.createBranchWeights(ExitWeight, FallThroughWeight)
 538                 : MDB.createBranchWeights(FallThroughWeight, ExitWeight);
 539   LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
 540 }
 541
 542 /// Clones the body of the loop L, putting it between \p InsertTop and \p
 543 /// InsertBot.
 544 /// \param IterNumber The serial number of the iteration currently being
 545 /// peeled off.
 546 /// \param ExitEdges The exit edges of the original loop.
 547 /// \param[out] NewBlocks A list of the blocks in the newly created clone
 548 /// \param[out] VMap The value map between the loop and the new clone.
 549 /// \param LoopBlocks A helper for DFS-traversal of the loop.
 550 /// \param LVMap A value-map that maps instructions from the original loop to
 551 /// instructions in the last peeled-off iteration.
 552 static void cloneLoopBlocks(
 553     Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot,
 554     SmallVectorImpl<std::pair<BasicBlock *, BasicBlock *>> &ExitEdges,
 555     SmallVectorImpl<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
 556     ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT,
 557     LoopInfo *LI, ArrayRef<MDNode *> LoopLocalNoAliasDeclScopes) {
 558   BasicBlock *Header = L->getHeader();
 559   BasicBlock *Latch = L->getLoopLatch();
 560   BasicBlock *PreHeader = L->getLoopPreheader();
 561
 562   Function *F = Header->getParent();
 563   LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
 564   LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
 565   Loop *ParentLoop = L->getParentLoop();
 566
 567   // For each block in the original loop, create a new copy,
 568   // and update the value map with the newly created values.
 569   for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
 570     BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".peel", F);
 571     NewBlocks.push_back(NewBB);
 572
 573     // If an original block is an immediate child of the loop L, its copy
 574     // is a child of a ParentLoop after peeling. If a block is a child of
 575     // a nested loop, it is handled in the cloneLoop() call below.
 576     if (ParentLoop && LI->getLoopFor(*BB) == L)
 577       ParentLoop->addBasicBlockToLoop(NewBB, *LI);
 578
 579     VMap[*BB] = NewBB;
 580
 581     // If dominator tree is available, insert nodes to represent cloned blocks.
 582     if (DT) {
 583       if (Header == *BB)
 584         DT->addNewBlock(NewBB, InsertTop);
 585       else {
 586         DomTreeNode *IDom = DT->getNode(*BB)->getIDom();
 587         // VMap must contain entry for IDom, as the iteration order is RPO.
 588         DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDom->getBlock()]));
 589       }
 590     }
 591   }
 592
 593   {
 594     // Identify what other metadata depends on the cloned version. After
 595     // cloning, replace the metadata with the corrected version for both
 596     // memory instructions and noalias intrinsics.
 597     std::string Ext = (Twine("Peel") + Twine(IterNumber)).str();
 598     cloneAndAdaptNoAliasScopes(LoopLocalNoAliasDeclScopes, NewBlocks,
 599                                Header->getContext(), Ext);
 600   }
 601
 602   // Recursively create the new Loop objects for nested loops, if any,
 603   // to preserve LoopInfo.
 604   for (Loop *ChildLoop : *L) {
 605     cloneLoop(ChildLoop, ParentLoop, VMap, LI, nullptr);
 606   }
 607
 608   // Hook-up the control flow for the newly inserted blocks.
 609   // The new header is hooked up directly to the "top", which is either
 610   // the original loop preheader (for the first iteration) or the previous
 611   // iteration's exiting block (for every other iteration)
 612   InsertTop->getTerminator()->setSuccessor(0, cast<BasicBlock>(VMap[Header]));
 613
 614   // Similarly, for the latch:
 615   // The original exiting edge is still hooked up to the loop exit.
 616   // The backedge now goes to the "bottom", which is either the loop's real
 617   // header (for the last peeled iteration) or the copied header of the next
 618   // iteration (for every other iteration)
 619   BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
 620   BranchInst *LatchBR = cast<BranchInst>(NewLatch->getTerminator());
 621   for (unsigned idx = 0, e = LatchBR->getNumSuccessors(); idx < e; ++idx)
 622     if (LatchBR->getSuccessor(idx) == Header) {
 623       LatchBR->setSuccessor(idx, InsertBot);
 624       break;
 625     }
 626   if (DT)
 627     DT->changeImmediateDominator(InsertBot, NewLatch);
 628
 629   // The new copy of the loop body starts with a bunch of PHI nodes
 630   // that pick an incoming value from either the preheader, or the previous
 631   // loop iteration. Since this copy is no longer part of the loop, we
 632   // resolve this statically:
 633   // For the first iteration, we use the value from the preheader directly.
 634   // For any other iteration, we replace the phi with the value generated by
 635   // the immediately preceding clone of the loop body (which represents
 636   // the previous iteration).
 637   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 638     PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
 639     if (IterNumber == 0) {
 640       VMap[&*I] = NewPHI->getIncomingValueForBlock(PreHeader);
 641     } else {
 642       Value *LatchVal = NewPHI->getIncomingValueForBlock(Latch);
 643       Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
 644       if (LatchInst && L->contains(LatchInst))
 645         VMap[&*I] = LVMap[LatchInst];
 646       else
 647         VMap[&*I] = LatchVal;
 648     }
 649     cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
 650   }
 651
 652   // Fix up the outgoing values - we need to add a value for the iteration
 653   // we've just created. Note that this must happen *after* the incoming
 654   // values are adjusted, since the value going out of the latch may also be
 655   // a value coming into the header.
 656   for (auto Edge : ExitEdges)
 657     for (PHINode &PHI : Edge.second->phis()) {
 658       Value *LatchVal = PHI.getIncomingValueForBlock(Edge.first);
 659       Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
 660       if (LatchInst && L->contains(LatchInst))
 661         LatchVal = VMap[LatchVal];
 662       PHI.addIncoming(LatchVal, cast<BasicBlock>(VMap[Edge.first]));
 663     }
 664
 665   // LastValueMap is updated with the values for the current loop
 666   // which are used the next time this function is called.
 667   for (auto KV : VMap)
 668     LVMap[KV.first] = KV.second;
 669 }
 670
 671 TargetTransformInfo::PeelingPreferences llvm::gatherPeelingPreferences(
 672     Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI,
 673     Optional<bool> UserAllowPeeling,
 674     Optional<bool> UserAllowProfileBasedPeeling, bool UnrollingSpecficValues) {
 675   TargetTransformInfo::PeelingPreferences PP;
 676
 677   // Set the default values.
 678   PP.PeelCount = 0;
 679   PP.AllowPeeling = true;
 680   PP.AllowLoopNestsPeeling = false;
 681   PP.PeelProfiledIterations = true;
 682
 683   // Get the target specifc values.
 684   TTI.getPeelingPreferences(L, SE, PP);
 685
 686   // User specified values using cl::opt.
 687   if (UnrollingSpecficValues) {
 688     if (UnrollPeelCount.getNumOccurrences() > 0)
 689       PP.PeelCount = UnrollPeelCount;
 690     if (UnrollAllowPeeling.getNumOccurrences() > 0)
 691       PP.AllowPeeling = UnrollAllowPeeling;
 692     if (UnrollAllowLoopNestsPeeling.getNumOccurrences() > 0)
 693       PP.AllowLoopNestsPeeling = UnrollAllowLoopNestsPeeling;
 694   }
 695
 696   // User specifed values provided by argument.
 697   if (UserAllowPeeling.hasValue())
 698     PP.AllowPeeling = *UserAllowPeeling;
 699   if (UserAllowProfileBasedPeeling.hasValue())
 700     PP.PeelProfiledIterations = *UserAllowProfileBasedPeeling;
 701
 702   return PP;
 703 }
 704
 705 /// Peel off the first \p PeelCount iterations of loop \p L.
 706 ///
 707 /// Note that this does not peel them off as a single straight-line block.
 708 /// Rather, each iteration is peeled off separately, and needs to check the
 709 /// exit condition.
 710 /// For loops that dynamically execute \p PeelCount iterations or less
 711 /// this provides a benefit, since the peeled off iterations, which account
 712 /// for the bulk of dynamic execution, can be further simplified by scalar
 713 /// optimizations.
 714 bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
 715                     ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,
 716                     bool PreserveLCSSA) {
 717   assert(PeelCount > 0 && "Attempt to peel out zero iterations?");
 718   assert(canPeel(L) && "Attempt to peel a loop which is not peelable?");
 719
 720   LoopBlocksDFS LoopBlocks(L);
 721   LoopBlocks.perform(LI);
 722
 723   BasicBlock *Header = L->getHeader();
 724   BasicBlock *PreHeader = L->getLoopPreheader();
 725   BasicBlock *Latch = L->getLoopLatch();
 726   SmallVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitEdges;
 727   L->getExitEdges(ExitEdges);
 728
 729   // Remember dominators of blocks we might reach through exits to change them
 730   // later. Immediate dominator of such block might change, because we add more
 731   // routes which can lead to the exit: we can reach it from the peeled
 732   // iterations too.
 733   DenseMap<BasicBlock *, BasicBlock *> NonLoopBlocksIDom;
 734   if (DT) {
 735     for (auto *BB : L->blocks()) {
 736       auto *BBDomNode = DT->getNode(BB);
 737       SmallVector<BasicBlock *, 16> ChildrenToUpdate;
 738       for (auto *ChildDomNode : BBDomNode->children()) {
 739         auto *ChildBB = ChildDomNode->getBlock();
 740         if (!L->contains(ChildBB))
 741           ChildrenToUpdate.push_back(ChildBB);
 742       }
 743       // The new idom of the block will be the nearest common dominator
 744       // of all copies of the previous idom. This is equivalent to the
 745       // nearest common dominator of the previous idom and the first latch,
 746       // which dominates all copies of the previous idom.
 747       BasicBlock *NewIDom = DT->findNearestCommonDominator(BB, Latch);
 748       for (auto *ChildBB : ChildrenToUpdate)
 749         NonLoopBlocksIDom[ChildBB] = NewIDom;
 750     }
 751   }
 752
 753   Function *F = Header->getParent();
 754
 755   // Set up all the necessary basic blocks. It is convenient to split the
 756   // preheader into 3 parts - two blocks to anchor the peeled copy of the loop
 757   // body, and a new preheader for the "real" loop.
 758
 759   // Peeling the first iteration transforms.
 760   //
 761   // PreHeader:
 762   // ...
 763   // Header:
 764   //   LoopBody
 765   //   If (cond) goto Header
 766   // Exit:
 767   //
 768   // into
 769   //
 770   // InsertTop:
 771   //   LoopBody
 772   //   If (!cond) goto Exit
 773   // InsertBot:
 774   // NewPreHeader:
 775   // ...
 776   // Header:
 777   //  LoopBody
 778   //  If (cond) goto Header
 779   // Exit:
 780   //
 781   // Each following iteration will split the current bottom anchor in two,
 782   // and put the new copy of the loop body between these two blocks. That is,
 783   // after peeling another iteration from the example above, we'll split
 784   // InsertBot, and get:
 785   //
 786   // InsertTop:
 787   //   LoopBody
 788   //   If (!cond) goto Exit
 789   // InsertBot:
 790   //   LoopBody
 791   //   If (!cond) goto Exit
 792   // InsertBot.next:
 793   // NewPreHeader:
 794   // ...
 795   // Header:
 796   //  LoopBody
 797   //  If (cond) goto Header
 798   // Exit:
 799
 800   BasicBlock *InsertTop = SplitEdge(PreHeader, Header, DT, LI);
 801   BasicBlock *InsertBot =
 802       SplitBlock(InsertTop, InsertTop->getTerminator(), DT, LI);
 803   BasicBlock *NewPreHeader =
 804       SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI);
 805
 806   InsertTop->setName(Header->getName() + ".peel.begin");
 807   InsertBot->setName(Header->getName() + ".peel.next");
 808   NewPreHeader->setName(PreHeader->getName() + ".peel.newph");
 809
 810   ValueToValueMapTy LVMap;
 811
 812   // If we have branch weight information, we'll want to update it for the
 813   // newly created branches.
 814   BranchInst *LatchBR =
 815       cast<BranchInst>(cast<BasicBlock>(Latch)->getTerminator());
 816   uint64_t ExitWeight = 0, FallThroughWeight = 0;
 817   initBranchWeights(Header, LatchBR, ExitWeight, FallThroughWeight);
 818
 819   // Identify what noalias metadata is inside the loop: if it is inside the
 820   // loop, the associated metadata must be cloned for each iteration.
 821   SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;
 822   identifyNoAliasScopesToClone(L->getBlocks(), LoopLocalNoAliasDeclScopes);
 823
 824   // For each peeled-off iteration, make a copy of the loop.
 825   for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
 826     SmallVector<BasicBlock *, 8> NewBlocks;
 827     ValueToValueMapTy VMap;
 828
 829     cloneLoopBlocks(L, Iter, InsertTop, InsertBot, ExitEdges, NewBlocks,
 830                     LoopBlocks, VMap, LVMap, DT, LI,
 831                     LoopLocalNoAliasDeclScopes);
 832
 833     // Remap to use values from the current iteration instead of the
 834     // previous one.
 835     remapInstructionsInBlocks(NewBlocks, VMap);
 836
 837     if (DT) {
 838       // Update IDoms of the blocks reachable through exits.
 839       if (Iter == 0)
 840         for (auto BBIDom : NonLoopBlocksIDom)
 841           DT->changeImmediateDominator(BBIDom.first,
 842                                        cast<BasicBlock>(LVMap[BBIDom.second]));
 843 #ifdef EXPENSIVE_CHECKS
 844       assert(DT->verify(DominatorTree::VerificationLevel::Fast));
 845 #endif
 846     }
 847
 848     auto *LatchBRCopy = cast<BranchInst>(VMap[LatchBR]);
 849     updateBranchWeights(InsertBot, LatchBRCopy, ExitWeight, FallThroughWeight);
 850     // Remove Loop metadata from the latch branch instruction
 851     // because it is not the Loop's latch branch anymore.
 852     LatchBRCopy->setMetadata(LLVMContext::MD_loop, nullptr);
 853
 854     InsertTop = InsertBot;
 855     InsertBot = SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI);
 856     InsertBot->setName(Header->getName() + ".peel.next");
 857
 858     F->getBasicBlockList().splice(InsertTop->getIterator(),
 859                                   F->getBasicBlockList(),
 860                                   NewBlocks[0]->getIterator(), F->end());
 861   }
 862
 863   // Now adjust the phi nodes in the loop header to get their initial values
 864   // from the last peeled-off iteration instead of the preheader.
 865   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 866     PHINode *PHI = cast<PHINode>(I);
 867     Value *NewVal = PHI->getIncomingValueForBlock(Latch);
 868     Instruction *LatchInst = dyn_cast<Instruction>(NewVal);
 869     if (LatchInst && L->contains(LatchInst))
 870       NewVal = LVMap[LatchInst];
 871
 872     PHI->setIncomingValueForBlock(NewPreHeader, NewVal);
 873   }
 874
 875   fixupBranchWeights(Header, LatchBR, ExitWeight, FallThroughWeight);
 876
 877   // Update Metadata for count of peeled off iterations.
 878   unsigned AlreadyPeeled = 0;
 879   if (auto Peeled = getOptionalIntLoopAttribute(L, PeeledCountMetaData))
 880     AlreadyPeeled = *Peeled;
 881   addStringMetadataToLoop(L, PeeledCountMetaData, AlreadyPeeled + PeelCount);
 882
 883   if (Loop *ParentLoop = L->getParentLoop())
 884     L = ParentLoop;
 885
 886   // We modified the loop, update SE.
 887   SE->forgetTopmostLoop(L);
 888
 889   // Finally DomtTree must be correct.
 890   assert(DT->verify(DominatorTree::VerificationLevel::Fast));
 891
 892   // FIXME: Incrementally update loop-simplify
 893   simplifyLoop(L, DT, LI, SE, AC, nullptr, PreserveLCSSA);
 894
 895   NumPeeled++;
 896
 897   return true;
 898 }