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/SmallVector.h"
15#include "llvm/ADT/Statistic.h"
16#include "llvm/Analysis/Loads.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/PatternMatch.h"
31#include "llvm/IR/ProfDataUtils.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/ValueMapper.h"
41#include <algorithm>
42#include <cassert>
43#include <cstdint>
44#include <optional>
45
46using namespace llvm;
47using namespace llvm::PatternMatch;
48
49#define DEBUG_TYPE "loop-peel"
50
51STATISTIC(NumPeeled, "Number of loops peeled");
52
53static cl::opt<unsigned> UnrollPeelCount(
54 "unroll-peel-count", cl::Hidden,
55 cl::desc("Set the unroll peeling count, for testing purposes"));
56
57static cl::opt<bool>
58 UnrollAllowPeeling("unroll-allow-peeling", cl::init(Val: true), cl::Hidden,
59 cl::desc("Allows loops to be peeled when the dynamic "
60 "trip count is known to be low."));
61
62static cl::opt<bool>
63 UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling",
64 cl::init(Val: false), cl::Hidden,
65 cl::desc("Allows loop nests to be peeled."));
66
67static cl::opt<unsigned> UnrollPeelMaxCount(
68 "unroll-peel-max-count", cl::init(Val: 7), cl::Hidden,
69 cl::desc("Max average trip count which will cause loop peeling."));
70
71static cl::opt<unsigned> UnrollForcePeelCount(
72 "unroll-force-peel-count", cl::init(Val: 0), cl::Hidden,
73 cl::desc("Force a peel count regardless of profiling information."));
74
75static cl::opt<bool> DisableAdvancedPeeling(
76 "disable-advanced-peeling", cl::init(Val: false), cl::Hidden,
77 cl::desc(
78 "Disable advance peeling. Issues for convergent targets (D134803)."));
79
80static const char *PeeledCountMetaData = "llvm.loop.peeled.count";
81
82// Check whether we are capable of peeling this loop.
83bool llvm::canPeel(const Loop *L) {
84 // Make sure the loop is in simplified form
85 if (!L->isLoopSimplifyForm())
86 return false;
87 if (!DisableAdvancedPeeling)
88 return true;
89
90 SmallVector<BasicBlock *, 4> Exits;
91 L->getUniqueNonLatchExitBlocks(ExitBlocks&: Exits);
92 // The latch must either be the only exiting block or all non-latch exit
93 // blocks have either a deopt or unreachable terminator or compose a chain of
94 // blocks where the last one is either deopt or unreachable terminated. Both
95 // deopt and unreachable terminators are a strong indication they are not
96 // taken. Note that this is a profitability check, not a legality check. Also
97 // note that LoopPeeling currently can only update the branch weights of latch
98 // blocks and branch weights to blocks with deopt or unreachable do not need
99 // updating.
100 return llvm::all_of(Range&: Exits, P: IsBlockFollowedByDeoptOrUnreachable);
101}
102
103namespace {
104
105// As a loop is peeled, it may be the case that Phi nodes become
106// loop-invariant (ie, known because there is only one choice).
107// For example, consider the following function:
108// void g(int);
109// void binary() {
110// int x = 0;
111// int y = 0;
112// int a = 0;
113// for(int i = 0; i <100000; ++i) {
114// g(x);
115// x = y;
116// g(a);
117// y = a + 1;
118// a = 5;
119// }
120// }
121// Peeling 3 iterations is beneficial because the values for x, y and a
122// become known. The IR for this loop looks something like the following:
123//
124// %i = phi i32 [ 0, %entry ], [ %inc, %if.end ]
125// %a = phi i32 [ 0, %entry ], [ 5, %if.end ]
126// %y = phi i32 [ 0, %entry ], [ %add, %if.end ]
127// %x = phi i32 [ 0, %entry ], [ %y, %if.end ]
128// ...
129// tail call void @_Z1gi(i32 signext %x)
130// tail call void @_Z1gi(i32 signext %a)
131// %add = add nuw nsw i32 %a, 1
132// %inc = add nuw nsw i32 %i, 1
133// %exitcond = icmp eq i32 %inc, 100000
134// br i1 %exitcond, label %for.cond.cleanup, label %for.body
135//
136// The arguments for the calls to g will become known after 3 iterations
137// of the loop, because the phi nodes values become known after 3 iterations
138// of the loop (ie, they are known on the 4th iteration, so peel 3 iterations).
139// The first iteration has g(0), g(0); the second has g(0), g(5); the
140// third has g(1), g(5) and the fourth (and all subsequent) have g(6), g(5).
141// Now consider the phi nodes:
142// %a is a phi with constants so it is determined after iteration 1.
143// %y is a phi based on a constant and %a so it is determined on
144// the iteration after %a is determined, so iteration 2.
145// %x is a phi based on a constant and %y so it is determined on
146// the iteration after %y, so iteration 3.
147// %i is based on itself (and is an induction variable) so it is
148// never determined.
149// This means that peeling off 3 iterations will result in being able to
150// remove the phi nodes for %a, %y, and %x. The arguments for the
151// corresponding calls to g are determined and the code for computing
152// x, y, and a can be removed.
153//
154// The PhiAnalyzer class calculates how many times a loop should be
155// peeled based on the above analysis of the phi nodes in the loop while
156// respecting the maximum specified.
157class PhiAnalyzer {
158public:
159 PhiAnalyzer(const Loop &L, unsigned MaxIterations);
160
161 // Calculate the sufficient minimum number of iterations of the loop to peel
162 // such that phi instructions become determined (subject to allowable limits)
163 std::optional<unsigned> calculateIterationsToPeel();
164
165protected:
166 using PeelCounter = std::optional<unsigned>;
167 const PeelCounter Unknown = std::nullopt;
168
169 // Add 1 respecting Unknown and return Unknown if result over MaxIterations
170 PeelCounter addOne(PeelCounter PC) const {
171 if (PC == Unknown)
172 return Unknown;
173 return (*PC + 1 <= MaxIterations) ? PeelCounter{*PC + 1} : Unknown;
174 }
175
176 // Calculate the number of iterations after which the given value
177 // becomes an invariant.
178 PeelCounter calculate(const Value &);
179
180 const Loop &L;
181 const unsigned MaxIterations;
182
183 // Map of Values to number of iterations to invariance
184 SmallDenseMap<const Value *, PeelCounter> IterationsToInvariance;
185};
186
187PhiAnalyzer::PhiAnalyzer(const Loop &L, unsigned MaxIterations)
188 : L(L), MaxIterations(MaxIterations) {
189 assert(canPeel(&L) && "loop is not suitable for peeling");
190 assert(MaxIterations > 0 && "no peeling is allowed?");
191}
192
193// This function calculates the number of iterations after which the value
194// becomes an invariant. The pre-calculated values are memorized in a map.
195// N.B. This number will be Unknown or <= MaxIterations.
196// The function is calculated according to the following definition:
197// Given %x = phi <Inputs from above the loop>, ..., [%y, %back.edge].
198// F(%x) = G(%y) + 1 (N.B. [MaxIterations | Unknown] + 1 => Unknown)
199// G(%y) = 0 if %y is a loop invariant
200// G(%y) = G(%BackEdgeValue) if %y is a phi in the header block
201// G(%y) = TODO: if %y is an expression based on phis and loop invariants
202// The example looks like:
203// %x = phi(0, %a) <-- becomes invariant starting from 3rd iteration.
204// %y = phi(0, 5)
205// %a = %y + 1
206// G(%y) = Unknown otherwise (including phi not in header block)
207PhiAnalyzer::PeelCounter PhiAnalyzer::calculate(const Value &V) {
208 // If we already know the answer, take it from the map.
209 auto I = IterationsToInvariance.find(Val: &V);
210 if (I != IterationsToInvariance.end())
211 return I->second;
212
213 // Place Unknown to map to avoid infinite recursion. Such
214 // cycles can never stop on an invariant.
215 IterationsToInvariance[&V] = Unknown;
216
217 if (L.isLoopInvariant(V: &V))
218 // Loop invariant so known at start.
219 return (IterationsToInvariance[&V] = 0);
220 if (const PHINode *Phi = dyn_cast<PHINode>(Val: &V)) {
221 if (Phi->getParent() != L.getHeader()) {
222 // Phi is not in header block so Unknown.
223 assert(IterationsToInvariance[&V] == Unknown && "unexpected value saved");
224 return Unknown;
225 }
226 // We need to analyze the input from the back edge and add 1.
227 Value *Input = Phi->getIncomingValueForBlock(BB: L.getLoopLatch());
228 PeelCounter Iterations = calculate(V: *Input);
229 assert(IterationsToInvariance[Input] == Iterations &&
230 "unexpected value saved");
231 return (IterationsToInvariance[Phi] = addOne(PC: Iterations));
232 }
233 if (const Instruction *I = dyn_cast<Instruction>(Val: &V)) {
234 if (isa<CmpInst>(Val: I) || I->isBinaryOp()) {
235 // Binary instructions get the max of the operands.
236 PeelCounter LHS = calculate(V: *I->getOperand(i: 0));
237 if (LHS == Unknown)
238 return Unknown;
239 PeelCounter RHS = calculate(V: *I->getOperand(i: 1));
240 if (RHS == Unknown)
241 return Unknown;
242 return (IterationsToInvariance[I] = {std::max(a: *LHS, b: *RHS)});
243 }
244 if (I->isCast())
245 // Cast instructions get the value of the operand.
246 return (IterationsToInvariance[I] = calculate(V: *I->getOperand(i: 0)));
247 }
248 // TODO: handle more expressions
249
250 // Everything else is Unknown.
251 assert(IterationsToInvariance[&V] == Unknown && "unexpected value saved");
252 return Unknown;
253}
254
255std::optional<unsigned> PhiAnalyzer::calculateIterationsToPeel() {
256 unsigned Iterations = 0;
257 for (auto &PHI : L.getHeader()->phis()) {
258 PeelCounter ToInvariance = calculate(V: PHI);
259 if (ToInvariance != Unknown) {
260 assert(*ToInvariance <= MaxIterations && "bad result in phi analysis");
261 Iterations = std::max(a: Iterations, b: *ToInvariance);
262 if (Iterations == MaxIterations)
263 break;
264 }
265 }
266 assert((Iterations <= MaxIterations) && "bad result in phi analysis");
267 return Iterations ? std::optional<unsigned>(Iterations) : std::nullopt;
268}
269
270} // unnamed namespace
271
272// Try to find any invariant memory reads that will become dereferenceable in
273// the remainder loop after peeling. The load must also be used (transitively)
274// by an exit condition. Returns the number of iterations to peel off (at the
275// moment either 0 or 1).
276static unsigned peelToTurnInvariantLoadsDerefencebale(Loop &L,
277 DominatorTree &DT,
278 AssumptionCache *AC) {
279 // Skip loops with a single exiting block, because there should be no benefit
280 // for the heuristic below.
281 if (L.getExitingBlock())
282 return 0;
283
284 // All non-latch exit blocks must have an UnreachableInst terminator.
285 // Otherwise the heuristic below may not be profitable.
286 SmallVector<BasicBlock *, 4> Exits;
287 L.getUniqueNonLatchExitBlocks(ExitBlocks&: Exits);
288 if (any_of(Range&: Exits, P: [](const BasicBlock *BB) {
289 return !isa<UnreachableInst>(Val: BB->getTerminator());
290 }))
291 return 0;
292
293 // Now look for invariant loads that dominate the latch and are not known to
294 // be dereferenceable. If there are such loads and no writes, they will become
295 // dereferenceable in the loop if the first iteration is peeled off. Also
296 // collect the set of instructions controlled by such loads. Only peel if an
297 // exit condition uses (transitively) such a load.
298 BasicBlock *Header = L.getHeader();
299 BasicBlock *Latch = L.getLoopLatch();
300 SmallPtrSet<Value *, 8> LoadUsers;
301 const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
302 for (BasicBlock *BB : L.blocks()) {
303 for (Instruction &I : *BB) {
304 if (I.mayWriteToMemory())
305 return 0;
306
307 auto Iter = LoadUsers.find(Ptr: &I);
308 if (Iter != LoadUsers.end()) {
309 for (Value *U : I.users())
310 LoadUsers.insert(Ptr: U);
311 }
312 // Do not look for reads in the header; they can already be hoisted
313 // without peeling.
314 if (BB == Header)
315 continue;
316 if (auto *LI = dyn_cast<LoadInst>(Val: &I)) {
317 Value *Ptr = LI->getPointerOperand();
318 if (DT.dominates(A: BB, B: Latch) && L.isLoopInvariant(V: Ptr) &&
319 !isDereferenceablePointer(V: Ptr, Ty: LI->getType(), DL, CtxI: LI, AC, DT: &DT))
320 for (Value *U : I.users())
321 LoadUsers.insert(Ptr: U);
322 }
323 }
324 }
325 SmallVector<BasicBlock *> ExitingBlocks;
326 L.getExitingBlocks(ExitingBlocks);
327 if (any_of(Range&: ExitingBlocks, P: [&LoadUsers](BasicBlock *Exiting) {
328 return LoadUsers.contains(Ptr: Exiting->getTerminator());
329 }))
330 return 1;
331 return 0;
332}
333
334// Return the number of iterations to peel off that make conditions in the
335// body true/false. For example, if we peel 2 iterations off the loop below,
336// the condition i < 2 can be evaluated at compile time.
337// for (i = 0; i < n; i++)
338// if (i < 2)
339// ..
340// else
341// ..
342// }
343static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount,
344 ScalarEvolution &SE) {
345 assert(L.isLoopSimplifyForm() && "Loop needs to be in loop simplify form");
346 unsigned DesiredPeelCount = 0;
347
348 // Do not peel the entire loop.
349 const SCEV *BE = SE.getConstantMaxBackedgeTakenCount(L: &L);
350 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Val: BE))
351 MaxPeelCount =
352 std::min(a: (unsigned)SC->getAPInt().getLimitedValue() - 1, b: MaxPeelCount);
353
354 const unsigned MaxDepth = 4;
355 std::function<void(Value *, unsigned)> ComputePeelCount =
356 [&](Value *Condition, unsigned Depth) -> void {
357 if (!Condition->getType()->isIntegerTy() || Depth >= MaxDepth)
358 return;
359
360 Value *LeftVal, *RightVal;
361 if (match(V: Condition, P: m_And(L: m_Value(V&: LeftVal), R: m_Value(V&: RightVal))) ||
362 match(V: Condition, P: m_Or(L: m_Value(V&: LeftVal), R: m_Value(V&: RightVal)))) {
363 ComputePeelCount(LeftVal, Depth + 1);
364 ComputePeelCount(RightVal, Depth + 1);
365 return;
366 }
367
368 CmpInst::Predicate Pred;
369 if (!match(V: Condition, P: m_ICmp(Pred, L: m_Value(V&: LeftVal), R: m_Value(V&: RightVal))))
370 return;
371
372 const SCEV *LeftSCEV = SE.getSCEV(V: LeftVal);
373 const SCEV *RightSCEV = SE.getSCEV(V: RightVal);
374
375 // Do not consider predicates that are known to be true or false
376 // independently of the loop iteration.
377 if (SE.evaluatePredicate(Pred, LHS: LeftSCEV, RHS: RightSCEV))
378 return;
379
380 // Check if we have a condition with one AddRec and one non AddRec
381 // expression. Normalize LeftSCEV to be the AddRec.
382 if (!isa<SCEVAddRecExpr>(Val: LeftSCEV)) {
383 if (isa<SCEVAddRecExpr>(Val: RightSCEV)) {
384 std::swap(a&: LeftSCEV, b&: RightSCEV);
385 Pred = ICmpInst::getSwappedPredicate(pred: Pred);
386 } else
387 return;
388 }
389
390 const SCEVAddRecExpr *LeftAR = cast<SCEVAddRecExpr>(Val: LeftSCEV);
391
392 // Avoid huge SCEV computations in the loop below, make sure we only
393 // consider AddRecs of the loop we are trying to peel.
394 if (!LeftAR->isAffine() || LeftAR->getLoop() != &L)
395 return;
396 if (!(ICmpInst::isEquality(P: Pred) && LeftAR->hasNoSelfWrap()) &&
397 !SE.getMonotonicPredicateType(LHS: LeftAR, Pred))
398 return;
399
400 // Check if extending the current DesiredPeelCount lets us evaluate Pred
401 // or !Pred in the loop body statically.
402 unsigned NewPeelCount = DesiredPeelCount;
403
404 const SCEV *IterVal = LeftAR->evaluateAtIteration(
405 It: SE.getConstant(Ty: LeftSCEV->getType(), V: NewPeelCount), SE);
406
407 // If the original condition is not known, get the negated predicate
408 // (which holds on the else branch) and check if it is known. This allows
409 // us to peel of iterations that make the original condition false.
410 if (!SE.isKnownPredicate(Pred, LHS: IterVal, RHS: RightSCEV))
411 Pred = ICmpInst::getInversePredicate(pred: Pred);
412
413 const SCEV *Step = LeftAR->getStepRecurrence(SE);
414 const SCEV *NextIterVal = SE.getAddExpr(LHS: IterVal, RHS: Step);
415 auto PeelOneMoreIteration = [&IterVal, &NextIterVal, &SE, Step,
416 &NewPeelCount]() {
417 IterVal = NextIterVal;
418 NextIterVal = SE.getAddExpr(LHS: IterVal, RHS: Step);
419 NewPeelCount++;
420 };
421
422 auto CanPeelOneMoreIteration = [&NewPeelCount, &MaxPeelCount]() {
423 return NewPeelCount < MaxPeelCount;
424 };
425
426 while (CanPeelOneMoreIteration() &&
427 SE.isKnownPredicate(Pred, LHS: IterVal, RHS: RightSCEV))
428 PeelOneMoreIteration();
429
430 // With *that* peel count, does the predicate !Pred become known in the
431 // first iteration of the loop body after peeling?
432 if (!SE.isKnownPredicate(Pred: ICmpInst::getInversePredicate(pred: Pred), LHS: IterVal,
433 RHS: RightSCEV))
434 return; // If not, give up.
435
436 // However, for equality comparisons, that isn't always sufficient to
437 // eliminate the comparsion in loop body, we may need to peel one more
438 // iteration. See if that makes !Pred become unknown again.
439 if (ICmpInst::isEquality(P: Pred) &&
440 !SE.isKnownPredicate(Pred: ICmpInst::getInversePredicate(pred: Pred), LHS: NextIterVal,
441 RHS: RightSCEV) &&
442 !SE.isKnownPredicate(Pred, LHS: IterVal, RHS: RightSCEV) &&
443 SE.isKnownPredicate(Pred, LHS: NextIterVal, RHS: RightSCEV)) {
444 if (!CanPeelOneMoreIteration())
445 return; // Need to peel one more iteration, but can't. Give up.
446 PeelOneMoreIteration(); // Great!
447 }
448
449 DesiredPeelCount = std::max(a: DesiredPeelCount, b: NewPeelCount);
450 };
451
452 for (BasicBlock *BB : L.blocks()) {
453 for (Instruction &I : *BB) {
454 if (SelectInst *SI = dyn_cast<SelectInst>(Val: &I))
455 ComputePeelCount(SI->getCondition(), 0);
456 }
457
458 auto *BI = dyn_cast<BranchInst>(Val: BB->getTerminator());
459 if (!BI || BI->isUnconditional())
460 continue;
461
462 // Ignore loop exit condition.
463 if (L.getLoopLatch() == BB)
464 continue;
465
466 ComputePeelCount(BI->getCondition(), 0);
467 }
468
469 return DesiredPeelCount;
470}
471
472/// This "heuristic" exactly matches implicit behavior which used to exist
473/// inside getLoopEstimatedTripCount. It was added here to keep an
474/// improvement inside that API from causing peeling to become more aggressive.
475/// This should probably be removed.
476static bool violatesLegacyMultiExitLoopCheck(Loop *L) {
477 BasicBlock *Latch = L->getLoopLatch();
478 if (!Latch)
479 return true;
480
481 BranchInst *LatchBR = dyn_cast<BranchInst>(Val: Latch->getTerminator());
482 if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(BB: Latch))
483 return true;
484
485 assert((LatchBR->getSuccessor(0) == L->getHeader() ||
486 LatchBR->getSuccessor(1) == L->getHeader()) &&
487 "At least one edge out of the latch must go to the header");
488
489 SmallVector<BasicBlock *, 4> ExitBlocks;
490 L->getUniqueNonLatchExitBlocks(ExitBlocks);
491 return any_of(Range&: ExitBlocks, P: [](const BasicBlock *EB) {
492 return !EB->getTerminatingDeoptimizeCall();
493 });
494}
495
496
497// Return the number of iterations we want to peel off.
498void llvm::computePeelCount(Loop *L, unsigned LoopSize,
499 TargetTransformInfo::PeelingPreferences &PP,
500 unsigned TripCount, DominatorTree &DT,
501 ScalarEvolution &SE, AssumptionCache *AC,
502 unsigned Threshold) {
503 assert(LoopSize > 0 && "Zero loop size is not allowed!");
504 // Save the PP.PeelCount value set by the target in
505 // TTI.getPeelingPreferences or by the flag -unroll-peel-count.
506 unsigned TargetPeelCount = PP.PeelCount;
507 PP.PeelCount = 0;
508 if (!canPeel(L))
509 return;
510
511 // Only try to peel innermost loops by default.
512 // The constraint can be relaxed by the target in TTI.getPeelingPreferences
513 // or by the flag -unroll-allow-loop-nests-peeling.
514 if (!PP.AllowLoopNestsPeeling && !L->isInnermost())
515 return;
516
517 // If the user provided a peel count, use that.
518 bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0;
519 if (UserPeelCount) {
520 LLVM_DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount
521 << " iterations.\n");
522 PP.PeelCount = UnrollForcePeelCount;
523 PP.PeelProfiledIterations = true;
524 return;
525 }
526
527 // Skip peeling if it's disabled.
528 if (!PP.AllowPeeling)
529 return;
530
531 // Check that we can peel at least one iteration.
532 if (2 * LoopSize > Threshold)
533 return;
534
535 unsigned AlreadyPeeled = 0;
536 if (auto Peeled = getOptionalIntLoopAttribute(TheLoop: L, Name: PeeledCountMetaData))
537 AlreadyPeeled = *Peeled;
538 // Stop if we already peeled off the maximum number of iterations.
539 if (AlreadyPeeled >= UnrollPeelMaxCount)
540 return;
541
542 // Pay respect to limitations implied by loop size and the max peel count.
543 unsigned MaxPeelCount = UnrollPeelMaxCount;
544 MaxPeelCount = std::min(a: MaxPeelCount, b: Threshold / LoopSize - 1);
545
546 // Start the max computation with the PP.PeelCount value set by the target
547 // in TTI.getPeelingPreferences or by the flag -unroll-peel-count.
548 unsigned DesiredPeelCount = TargetPeelCount;
549
550 // Here we try to get rid of Phis which become invariants after 1, 2, ..., N
551 // iterations of the loop. For this we compute the number for iterations after
552 // which every Phi is guaranteed to become an invariant, and try to peel the
553 // maximum number of iterations among these values, thus turning all those
554 // Phis into invariants.
555 if (MaxPeelCount > DesiredPeelCount) {
556 // Check how many iterations are useful for resolving Phis
557 auto NumPeels = PhiAnalyzer(*L, MaxPeelCount).calculateIterationsToPeel();
558 if (NumPeels)
559 DesiredPeelCount = std::max(a: DesiredPeelCount, b: *NumPeels);
560 }
561
562 DesiredPeelCount = std::max(a: DesiredPeelCount,
563 b: countToEliminateCompares(L&: *L, MaxPeelCount, SE));
564
565 if (DesiredPeelCount == 0)
566 DesiredPeelCount = peelToTurnInvariantLoadsDerefencebale(L&: *L, DT, AC);
567
568 if (DesiredPeelCount > 0) {
569 DesiredPeelCount = std::min(a: DesiredPeelCount, b: MaxPeelCount);
570 // Consider max peel count limitation.
571 assert(DesiredPeelCount > 0 && "Wrong loop size estimation?");
572 if (DesiredPeelCount + AlreadyPeeled <= UnrollPeelMaxCount) {
573 LLVM_DEBUG(dbgs() << "Peel " << DesiredPeelCount
574 << " iteration(s) to turn"
575 << " some Phis into invariants.\n");
576 PP.PeelCount = DesiredPeelCount;
577 PP.PeelProfiledIterations = false;
578 return;
579 }
580 }
581
582 // Bail if we know the statically calculated trip count.
583 // In this case we rather prefer partial unrolling.
584 if (TripCount)
585 return;
586
587 // Do not apply profile base peeling if it is disabled.
588 if (!PP.PeelProfiledIterations)
589 return;
590 // If we don't know the trip count, but have reason to believe the average
591 // trip count is low, peeling should be beneficial, since we will usually
592 // hit the peeled section.
593 // We only do this in the presence of profile information, since otherwise
594 // our estimates of the trip count are not reliable enough.
595 if (L->getHeader()->getParent()->hasProfileData()) {
596 if (violatesLegacyMultiExitLoopCheck(L))
597 return;
598 std::optional<unsigned> EstimatedTripCount = getLoopEstimatedTripCount(L);
599 if (!EstimatedTripCount)
600 return;
601
602 LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is "
603 << *EstimatedTripCount << "\n");
604
605 if (*EstimatedTripCount) {
606 if (*EstimatedTripCount + AlreadyPeeled <= MaxPeelCount) {
607 unsigned PeelCount = *EstimatedTripCount;
608 LLVM_DEBUG(dbgs() << "Peeling first " << PeelCount << " iterations.\n");
609 PP.PeelCount = PeelCount;
610 return;
611 }
612 LLVM_DEBUG(dbgs() << "Already peel count: " << AlreadyPeeled << "\n");
613 LLVM_DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n");
614 LLVM_DEBUG(dbgs() << "Loop cost: " << LoopSize << "\n");
615 LLVM_DEBUG(dbgs() << "Max peel cost: " << Threshold << "\n");
616 LLVM_DEBUG(dbgs() << "Max peel count by cost: "
617 << (Threshold / LoopSize - 1) << "\n");
618 }
619 }
620}
621
622struct WeightInfo {
623 // Weights for current iteration.
624 SmallVector<uint32_t> Weights;
625 // Weights to subtract after each iteration.
626 const SmallVector<uint32_t> SubWeights;
627};
628
629/// Update the branch weights of an exiting block of a peeled-off loop
630/// iteration.
631/// Let F is a weight of the edge to continue (fallthrough) into the loop.
632/// Let E is a weight of the edge to an exit.
633/// F/(F+E) is a probability to go to loop and E/(F+E) is a probability to
634/// go to exit.
635/// Then, Estimated ExitCount = F / E.
636/// For I-th (counting from 0) peeled off iteration we set the weights for
637/// the peeled exit as (EC - I, 1). It gives us reasonable distribution,
638/// The probability to go to exit 1/(EC-I) increases. At the same time
639/// the estimated exit count in the remainder loop reduces by I.
640/// To avoid dealing with division rounding we can just multiple both part
641/// of weights to E and use weight as (F - I * E, E).
642static void updateBranchWeights(Instruction *Term, WeightInfo &Info) {
643 setBranchWeights(I&: *Term, Weights: Info.Weights);
644 for (auto [Idx, SubWeight] : enumerate(First: Info.SubWeights))
645 if (SubWeight != 0)
646 // Don't set the probability of taking the edge from latch to loop header
647 // to less than 1:1 ratio (meaning Weight should not be lower than
648 // SubWeight), as this could significantly reduce the loop's hotness,
649 // which would be incorrect in the case of underestimating the trip count.
650 Info.Weights[Idx] =
651 Info.Weights[Idx] > SubWeight
652 ? std::max(a: Info.Weights[Idx] - SubWeight, b: SubWeight)
653 : SubWeight;
654}
655
656/// Initialize the weights for all exiting blocks.
657static void initBranchWeights(DenseMap<Instruction *, WeightInfo> &WeightInfos,
658 Loop *L) {
659 SmallVector<BasicBlock *> ExitingBlocks;
660 L->getExitingBlocks(ExitingBlocks);
661 for (BasicBlock *ExitingBlock : ExitingBlocks) {
662 Instruction *Term = ExitingBlock->getTerminator();
663 SmallVector<uint32_t> Weights;
664 if (!extractBranchWeights(I: *Term, Weights))
665 continue;
666
667 // See the comment on updateBranchWeights() for an explanation of what we
668 // do here.
669 uint32_t FallThroughWeights = 0;
670 uint32_t ExitWeights = 0;
671 for (auto [Succ, Weight] : zip(t: successors(I: Term), u&: Weights)) {
672 if (L->contains(BB: Succ))
673 FallThroughWeights += Weight;
674 else
675 ExitWeights += Weight;
676 }
677
678 // Don't try to update weights for degenerate case.
679 if (FallThroughWeights == 0)
680 continue;
681
682 SmallVector<uint32_t> SubWeights;
683 for (auto [Succ, Weight] : zip(t: successors(I: Term), u&: Weights)) {
684 if (!L->contains(BB: Succ)) {
685 // Exit weights stay the same.
686 SubWeights.push_back(Elt: 0);
687 continue;
688 }
689
690 // Subtract exit weights on each iteration, distributed across all
691 // fallthrough edges.
692 double W = (double)Weight / (double)FallThroughWeights;
693 SubWeights.push_back(Elt: (uint32_t)(ExitWeights * W));
694 }
695
696 WeightInfos.insert(KV: {Term, {.Weights: std::move(Weights), .SubWeights: std::move(SubWeights)}});
697 }
698}
699
700/// Clones the body of the loop L, putting it between \p InsertTop and \p
701/// InsertBot.
702/// \param IterNumber The serial number of the iteration currently being
703/// peeled off.
704/// \param ExitEdges The exit edges of the original loop.
705/// \param[out] NewBlocks A list of the blocks in the newly created clone
706/// \param[out] VMap The value map between the loop and the new clone.
707/// \param LoopBlocks A helper for DFS-traversal of the loop.
708/// \param LVMap A value-map that maps instructions from the original loop to
709/// instructions in the last peeled-off iteration.
710static void cloneLoopBlocks(
711 Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot,
712 SmallVectorImpl<std::pair<BasicBlock *, BasicBlock *>> &ExitEdges,
713 SmallVectorImpl<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
714 ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT,
715 LoopInfo *LI, ArrayRef<MDNode *> LoopLocalNoAliasDeclScopes,
716 ScalarEvolution &SE) {
717 BasicBlock *Header = L->getHeader();
718 BasicBlock *Latch = L->getLoopLatch();
719 BasicBlock *PreHeader = L->getLoopPreheader();
720
721 Function *F = Header->getParent();
722 LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
723 LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
724 Loop *ParentLoop = L->getParentLoop();
725
726 // For each block in the original loop, create a new copy,
727 // and update the value map with the newly created values.
728 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
729 BasicBlock *NewBB = CloneBasicBlock(BB: *BB, VMap, NameSuffix: ".peel", F);
730 NewBlocks.push_back(Elt: NewBB);
731
732 // If an original block is an immediate child of the loop L, its copy
733 // is a child of a ParentLoop after peeling. If a block is a child of
734 // a nested loop, it is handled in the cloneLoop() call below.
735 if (ParentLoop && LI->getLoopFor(BB: *BB) == L)
736 ParentLoop->addBasicBlockToLoop(NewBB, LI&: *LI);
737
738 VMap[*BB] = NewBB;
739
740 // If dominator tree is available, insert nodes to represent cloned blocks.
741 if (DT) {
742 if (Header == *BB)
743 DT->addNewBlock(BB: NewBB, DomBB: InsertTop);
744 else {
745 DomTreeNode *IDom = DT->getNode(BB: *BB)->getIDom();
746 // VMap must contain entry for IDom, as the iteration order is RPO.
747 DT->addNewBlock(BB: NewBB, DomBB: cast<BasicBlock>(Val&: VMap[IDom->getBlock()]));
748 }
749 }
750 }
751
752 {
753 // Identify what other metadata depends on the cloned version. After
754 // cloning, replace the metadata with the corrected version for both
755 // memory instructions and noalias intrinsics.
756 std::string Ext = (Twine("Peel") + Twine(IterNumber)).str();
757 cloneAndAdaptNoAliasScopes(NoAliasDeclScopes: LoopLocalNoAliasDeclScopes, NewBlocks,
758 Context&: Header->getContext(), Ext);
759 }
760
761 // Recursively create the new Loop objects for nested loops, if any,
762 // to preserve LoopInfo.
763 for (Loop *ChildLoop : *L) {
764 cloneLoop(L: ChildLoop, PL: ParentLoop, VM&: VMap, LI, LPM: nullptr);
765 }
766
767 // Hook-up the control flow for the newly inserted blocks.
768 // The new header is hooked up directly to the "top", which is either
769 // the original loop preheader (for the first iteration) or the previous
770 // iteration's exiting block (for every other iteration)
771 InsertTop->getTerminator()->setSuccessor(Idx: 0, BB: cast<BasicBlock>(Val&: VMap[Header]));
772
773 // Similarly, for the latch:
774 // The original exiting edge is still hooked up to the loop exit.
775 // The backedge now goes to the "bottom", which is either the loop's real
776 // header (for the last peeled iteration) or the copied header of the next
777 // iteration (for every other iteration)
778 BasicBlock *NewLatch = cast<BasicBlock>(Val&: VMap[Latch]);
779 auto *LatchTerm = cast<Instruction>(Val: NewLatch->getTerminator());
780 for (unsigned idx = 0, e = LatchTerm->getNumSuccessors(); idx < e; ++idx)
781 if (LatchTerm->getSuccessor(Idx: idx) == Header) {
782 LatchTerm->setSuccessor(Idx: idx, BB: InsertBot);
783 break;
784 }
785 if (DT)
786 DT->changeImmediateDominator(BB: InsertBot, NewBB: NewLatch);
787
788 // The new copy of the loop body starts with a bunch of PHI nodes
789 // that pick an incoming value from either the preheader, or the previous
790 // loop iteration. Since this copy is no longer part of the loop, we
791 // resolve this statically:
792 // For the first iteration, we use the value from the preheader directly.
793 // For any other iteration, we replace the phi with the value generated by
794 // the immediately preceding clone of the loop body (which represents
795 // the previous iteration).
796 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(Val: I); ++I) {
797 PHINode *NewPHI = cast<PHINode>(Val&: VMap[&*I]);
798 if (IterNumber == 0) {
799 VMap[&*I] = NewPHI->getIncomingValueForBlock(BB: PreHeader);
800 } else {
801 Value *LatchVal = NewPHI->getIncomingValueForBlock(BB: Latch);
802 Instruction *LatchInst = dyn_cast<Instruction>(Val: LatchVal);
803 if (LatchInst && L->contains(Inst: LatchInst))
804 VMap[&*I] = LVMap[LatchInst];
805 else
806 VMap[&*I] = LatchVal;
807 }
808 NewPHI->eraseFromParent();
809 }
810
811 // Fix up the outgoing values - we need to add a value for the iteration
812 // we've just created. Note that this must happen *after* the incoming
813 // values are adjusted, since the value going out of the latch may also be
814 // a value coming into the header.
815 for (auto Edge : ExitEdges)
816 for (PHINode &PHI : Edge.second->phis()) {
817 Value *LatchVal = PHI.getIncomingValueForBlock(BB: Edge.first);
818 Instruction *LatchInst = dyn_cast<Instruction>(Val: LatchVal);
819 if (LatchInst && L->contains(Inst: LatchInst))
820 LatchVal = VMap[LatchVal];
821 PHI.addIncoming(V: LatchVal, BB: cast<BasicBlock>(Val&: VMap[Edge.first]));
822 SE.forgetValue(V: &PHI);
823 }
824
825 // LastValueMap is updated with the values for the current loop
826 // which are used the next time this function is called.
827 for (auto KV : VMap)
828 LVMap[KV.first] = KV.second;
829}
830
831TargetTransformInfo::PeelingPreferences
832llvm::gatherPeelingPreferences(Loop *L, ScalarEvolution &SE,
833 const TargetTransformInfo &TTI,
834 std::optional<bool> UserAllowPeeling,
835 std::optional<bool> UserAllowProfileBasedPeeling,
836 bool UnrollingSpecficValues) {
837 TargetTransformInfo::PeelingPreferences PP;
838
839 // Set the default values.
840 PP.PeelCount = 0;
841 PP.AllowPeeling = true;
842 PP.AllowLoopNestsPeeling = false;
843 PP.PeelProfiledIterations = true;
844
845 // Get the target specifc values.
846 TTI.getPeelingPreferences(L, SE, PP);
847
848 // User specified values using cl::opt.
849 if (UnrollingSpecficValues) {
850 if (UnrollPeelCount.getNumOccurrences() > 0)
851 PP.PeelCount = UnrollPeelCount;
852 if (UnrollAllowPeeling.getNumOccurrences() > 0)
853 PP.AllowPeeling = UnrollAllowPeeling;
854 if (UnrollAllowLoopNestsPeeling.getNumOccurrences() > 0)
855 PP.AllowLoopNestsPeeling = UnrollAllowLoopNestsPeeling;
856 }
857
858 // User specifed values provided by argument.
859 if (UserAllowPeeling)
860 PP.AllowPeeling = *UserAllowPeeling;
861 if (UserAllowProfileBasedPeeling)
862 PP.PeelProfiledIterations = *UserAllowProfileBasedPeeling;
863
864 return PP;
865}
866
867/// Peel off the first \p PeelCount iterations of loop \p L.
868///
869/// Note that this does not peel them off as a single straight-line block.
870/// Rather, each iteration is peeled off separately, and needs to check the
871/// exit condition.
872/// For loops that dynamically execute \p PeelCount iterations or less
873/// this provides a benefit, since the peeled off iterations, which account
874/// for the bulk of dynamic execution, can be further simplified by scalar
875/// optimizations.
876bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
877 ScalarEvolution *SE, DominatorTree &DT, AssumptionCache *AC,
878 bool PreserveLCSSA, ValueToValueMapTy &LVMap) {
879 assert(PeelCount > 0 && "Attempt to peel out zero iterations?");
880 assert(canPeel(L) && "Attempt to peel a loop which is not peelable?");
881
882 LoopBlocksDFS LoopBlocks(L);
883 LoopBlocks.perform(LI);
884
885 BasicBlock *Header = L->getHeader();
886 BasicBlock *PreHeader = L->getLoopPreheader();
887 BasicBlock *Latch = L->getLoopLatch();
888 SmallVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitEdges;
889 L->getExitEdges(ExitEdges);
890
891 // Remember dominators of blocks we might reach through exits to change them
892 // later. Immediate dominator of such block might change, because we add more
893 // routes which can lead to the exit: we can reach it from the peeled
894 // iterations too.
895 DenseMap<BasicBlock *, BasicBlock *> NonLoopBlocksIDom;
896 for (auto *BB : L->blocks()) {
897 auto *BBDomNode = DT.getNode(BB);
898 SmallVector<BasicBlock *, 16> ChildrenToUpdate;
899 for (auto *ChildDomNode : BBDomNode->children()) {
900 auto *ChildBB = ChildDomNode->getBlock();
901 if (!L->contains(BB: ChildBB))
902 ChildrenToUpdate.push_back(Elt: ChildBB);
903 }
904 // The new idom of the block will be the nearest common dominator
905 // of all copies of the previous idom. This is equivalent to the
906 // nearest common dominator of the previous idom and the first latch,
907 // which dominates all copies of the previous idom.
908 BasicBlock *NewIDom = DT.findNearestCommonDominator(A: BB, B: Latch);
909 for (auto *ChildBB : ChildrenToUpdate)
910 NonLoopBlocksIDom[ChildBB] = NewIDom;
911 }
912
913 Function *F = Header->getParent();
914
915 // Set up all the necessary basic blocks. It is convenient to split the
916 // preheader into 3 parts - two blocks to anchor the peeled copy of the loop
917 // body, and a new preheader for the "real" loop.
918
919 // Peeling the first iteration transforms.
920 //
921 // PreHeader:
922 // ...
923 // Header:
924 // LoopBody
925 // If (cond) goto Header
926 // Exit:
927 //
928 // into
929 //
930 // InsertTop:
931 // LoopBody
932 // If (!cond) goto Exit
933 // InsertBot:
934 // NewPreHeader:
935 // ...
936 // Header:
937 // LoopBody
938 // If (cond) goto Header
939 // Exit:
940 //
941 // Each following iteration will split the current bottom anchor in two,
942 // and put the new copy of the loop body between these two blocks. That is,
943 // after peeling another iteration from the example above, we'll split
944 // InsertBot, and get:
945 //
946 // InsertTop:
947 // LoopBody
948 // If (!cond) goto Exit
949 // InsertBot:
950 // LoopBody
951 // If (!cond) goto Exit
952 // InsertBot.next:
953 // NewPreHeader:
954 // ...
955 // Header:
956 // LoopBody
957 // If (cond) goto Header
958 // Exit:
959
960 BasicBlock *InsertTop = SplitEdge(From: PreHeader, To: Header, DT: &DT, LI);
961 BasicBlock *InsertBot =
962 SplitBlock(Old: InsertTop, SplitPt: InsertTop->getTerminator(), DT: &DT, LI);
963 BasicBlock *NewPreHeader =
964 SplitBlock(Old: InsertBot, SplitPt: InsertBot->getTerminator(), DT: &DT, LI);
965
966 InsertTop->setName(Header->getName() + ".peel.begin");
967 InsertBot->setName(Header->getName() + ".peel.next");
968 NewPreHeader->setName(PreHeader->getName() + ".peel.newph");
969
970 Instruction *LatchTerm =
971 cast<Instruction>(Val: cast<BasicBlock>(Val: Latch)->getTerminator());
972
973 // If we have branch weight information, we'll want to update it for the
974 // newly created branches.
975 DenseMap<Instruction *, WeightInfo> Weights;
976 initBranchWeights(WeightInfos&: Weights, L);
977
978 // Identify what noalias metadata is inside the loop: if it is inside the
979 // loop, the associated metadata must be cloned for each iteration.
980 SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;
981 identifyNoAliasScopesToClone(BBs: L->getBlocks(), NoAliasDeclScopes&: LoopLocalNoAliasDeclScopes);
982
983 // For each peeled-off iteration, make a copy of the loop.
984 for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
985 SmallVector<BasicBlock *, 8> NewBlocks;
986 ValueToValueMapTy VMap;
987
988 cloneLoopBlocks(L, IterNumber: Iter, InsertTop, InsertBot, ExitEdges, NewBlocks,
989 LoopBlocks, VMap, LVMap, DT: &DT, LI,
990 LoopLocalNoAliasDeclScopes, SE&: *SE);
991
992 // Remap to use values from the current iteration instead of the
993 // previous one.
994 remapInstructionsInBlocks(Blocks: NewBlocks, VMap);
995
996 // Update IDoms of the blocks reachable through exits.
997 if (Iter == 0)
998 for (auto BBIDom : NonLoopBlocksIDom)
999 DT.changeImmediateDominator(BB: BBIDom.first,
1000 NewBB: cast<BasicBlock>(Val&: LVMap[BBIDom.second]));
1001#ifdef EXPENSIVE_CHECKS
1002 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
1003#endif
1004
1005 for (auto &[Term, Info] : Weights) {
1006 auto *TermCopy = cast<Instruction>(Val&: VMap[Term]);
1007 updateBranchWeights(Term: TermCopy, Info);
1008 }
1009
1010 // Remove Loop metadata from the latch branch instruction
1011 // because it is not the Loop's latch branch anymore.
1012 auto *LatchTermCopy = cast<Instruction>(Val&: VMap[LatchTerm]);
1013 LatchTermCopy->setMetadata(KindID: LLVMContext::MD_loop, Node: nullptr);
1014
1015 InsertTop = InsertBot;
1016 InsertBot = SplitBlock(Old: InsertBot, SplitPt: InsertBot->getTerminator(), DT: &DT, LI);
1017 InsertBot->setName(Header->getName() + ".peel.next");
1018
1019 F->splice(ToIt: InsertTop->getIterator(), FromF: F, FromBeginIt: NewBlocks[0]->getIterator(),
1020 FromEndIt: F->end());
1021 }
1022
1023 // Now adjust the phi nodes in the loop header to get their initial values
1024 // from the last peeled-off iteration instead of the preheader.
1025 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(Val: I); ++I) {
1026 PHINode *PHI = cast<PHINode>(Val&: I);
1027 Value *NewVal = PHI->getIncomingValueForBlock(BB: Latch);
1028 Instruction *LatchInst = dyn_cast<Instruction>(Val: NewVal);
1029 if (LatchInst && L->contains(Inst: LatchInst))
1030 NewVal = LVMap[LatchInst];
1031
1032 PHI->setIncomingValueForBlock(BB: NewPreHeader, V: NewVal);
1033 }
1034
1035 for (const auto &[Term, Info] : Weights) {
1036 setBranchWeights(I&: *Term, Weights: Info.Weights);
1037 }
1038
1039 // Update Metadata for count of peeled off iterations.
1040 unsigned AlreadyPeeled = 0;
1041 if (auto Peeled = getOptionalIntLoopAttribute(TheLoop: L, Name: PeeledCountMetaData))
1042 AlreadyPeeled = *Peeled;
1043 addStringMetadataToLoop(TheLoop: L, MDString: PeeledCountMetaData, V: AlreadyPeeled + PeelCount);
1044
1045 if (Loop *ParentLoop = L->getParentLoop())
1046 L = ParentLoop;
1047
1048 // We modified the loop, update SE.
1049 SE->forgetTopmostLoop(L);
1050 SE->forgetBlockAndLoopDispositions();
1051
1052#ifdef EXPENSIVE_CHECKS
1053 // Finally DomtTree must be correct.
1054 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
1055#endif
1056
1057 // FIXME: Incrementally update loop-simplify
1058 simplifyLoop(L, DT: &DT, LI, SE, AC, MSSAU: nullptr, PreserveLCSSA);
1059
1060 NumPeeled++;
1061
1062 return true;
1063}
1064

source code of llvm/lib/Transforms/Utils/LoopPeel.cpp