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