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 } 899