LLVM 17.0.0git
LoopPeel.cpp
Go to the documentation of this file.
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
13#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/Statistic.h"
16#include "llvm/Analysis/Loads.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"
28#include "llvm/IR/LLVMContext.h"
29#include "llvm/IR/MDBuilder.h"
34#include "llvm/Support/Debug.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
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(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(false), cl::Hidden,
65 cl::desc("Allows loop nests to be peeled."));
66
68 "unroll-peel-max-count", cl::init(7), cl::Hidden,
69 cl::desc("Max average trip count which will cause loop peeling."));
70
72 "unroll-force-peel-count", cl::init(0), cl::Hidden,
73 cl::desc("Force a peel count regardless of profiling information."));
74
76 "disable-advanced-peeling", cl::init(false), cl::Hidden,
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;
88 return true;
89
91 L->getUniqueNonLatchExitBlocks(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.
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(&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))
218 // Loop invariant so known at start.
219 return (IterationsToInvariance[&V] = 0);
220 if (const PHINode *Phi = dyn_cast<PHINode>(&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(L.getLoopLatch());
228 PeelCounter Iterations = calculate(*Input);
229 assert(IterationsToInvariance[Input] == Iterations &&
230 "unexpected value saved");
231 return (IterationsToInvariance[Phi] = addOne(Iterations));
232 }
233 if (const Instruction *I = dyn_cast<Instruction>(&V)) {
234 if (isa<CmpInst>(I) || I->isBinaryOp()) {
235 // Binary instructions get the max of the operands.
236 PeelCounter LHS = calculate(*I->getOperand(0));
237 if (LHS == Unknown)
238 return Unknown;
239 PeelCounter RHS = calculate(*I->getOperand(1));
240 if (RHS == Unknown)
241 return Unknown;
242 return (IterationsToInvariance[I] = {std::max(*LHS, *RHS)});
243 }
244 if (I->isCast())
245 // Cast instructions get the value of the operand.
246 return (IterationsToInvariance[I] = calculate(*I->getOperand(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(PHI);
259 if (ToInvariance != Unknown) {
260 assert(*ToInvariance <= MaxIterations && "bad result in phi analysis");
261 Iterations = std::max(Iterations, *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).
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.
287 L.getUniqueNonLatchExitBlocks(Exits);
288 if (any_of(Exits, [](const BasicBlock *BB) {
289 return !isa<UnreachableInst>(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(&I);
308 if (Iter != LoadUsers.end()) {
309 for (Value *U : I.users())
310 LoadUsers.insert(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>(&I)) {
317 Value *Ptr = LI->getPointerOperand();
318 if (DT.dominates(BB, Latch) && L.isLoopInvariant(Ptr) &&
319 !isDereferenceablePointer(Ptr, LI->getType(), DL, LI, AC, &DT))
320 for (Value *U : I.users())
321 LoadUsers.insert(U);
322 }
323 }
324 }
325 SmallVector<BasicBlock *> ExitingBlocks;
326 L.getExitingBlocks(ExitingBlocks);
327 if (any_of(ExitingBlocks, [&LoadUsers](BasicBlock *Exiting) {
328 return LoadUsers.contains(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 for (auto *BB : L.blocks()) {
349 auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
350 if (!BI || BI->isUnconditional())
351 continue;
352
353 // Ignore loop exit condition.
354 if (L.getLoopLatch() == BB)
355 continue;
356
357 Value *Condition = BI->getCondition();
358 Value *LeftVal, *RightVal;
360 if (!match(Condition, m_ICmp(Pred, m_Value(LeftVal), m_Value(RightVal))))
361 continue;
362
363 const SCEV *LeftSCEV = SE.getSCEV(LeftVal);
364 const SCEV *RightSCEV = SE.getSCEV(RightVal);
365
366 // Do not consider predicates that are known to be true or false
367 // independently of the loop iteration.
368 if (SE.evaluatePredicate(Pred, LeftSCEV, RightSCEV))
369 continue;
370
371 // Check if we have a condition with one AddRec and one non AddRec
372 // expression. Normalize LeftSCEV to be the AddRec.
373 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
374 if (isa<SCEVAddRecExpr>(RightSCEV)) {
375 std::swap(LeftSCEV, RightSCEV);
376 Pred = ICmpInst::getSwappedPredicate(Pred);
377 } else
378 continue;
379 }
380
381 const SCEVAddRecExpr *LeftAR = cast<SCEVAddRecExpr>(LeftSCEV);
382
383 // Avoid huge SCEV computations in the loop below, make sure we only
384 // consider AddRecs of the loop we are trying to peel.
385 if (!LeftAR->isAffine() || LeftAR->getLoop() != &L)
386 continue;
387 if (!(ICmpInst::isEquality(Pred) && LeftAR->hasNoSelfWrap()) &&
388 !SE.getMonotonicPredicateType(LeftAR, Pred))
389 continue;
390
391 // Check if extending the current DesiredPeelCount lets us evaluate Pred
392 // or !Pred in the loop body statically.
393 unsigned NewPeelCount = DesiredPeelCount;
394
395 const SCEV *IterVal = LeftAR->evaluateAtIteration(
396 SE.getConstant(LeftSCEV->getType(), NewPeelCount), SE);
397
398 // If the original condition is not known, get the negated predicate
399 // (which holds on the else branch) and check if it is known. This allows
400 // us to peel of iterations that make the original condition false.
401 if (!SE.isKnownPredicate(Pred, IterVal, RightSCEV))
402 Pred = ICmpInst::getInversePredicate(Pred);
403
404 const SCEV *Step = LeftAR->getStepRecurrence(SE);
405 const SCEV *NextIterVal = SE.getAddExpr(IterVal, Step);
406 auto PeelOneMoreIteration = [&IterVal, &NextIterVal, &SE, Step,
407 &NewPeelCount]() {
408 IterVal = NextIterVal;
409 NextIterVal = SE.getAddExpr(IterVal, Step);
410 NewPeelCount++;
411 };
412
413 auto CanPeelOneMoreIteration = [&NewPeelCount, &MaxPeelCount]() {
414 return NewPeelCount < MaxPeelCount;
415 };
416
417 while (CanPeelOneMoreIteration() &&
418 SE.isKnownPredicate(Pred, IterVal, RightSCEV))
419 PeelOneMoreIteration();
420
421 // With *that* peel count, does the predicate !Pred become known in the
422 // first iteration of the loop body after peeling?
423 if (!SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), IterVal,
424 RightSCEV))
425 continue; // If not, give up.
426
427 // However, for equality comparisons, that isn't always sufficient to
428 // eliminate the comparsion in loop body, we may need to peel one more
429 // iteration. See if that makes !Pred become unknown again.
430 if (ICmpInst::isEquality(Pred) &&
431 !SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), NextIterVal,
432 RightSCEV) &&
433 !SE.isKnownPredicate(Pred, IterVal, RightSCEV) &&
434 SE.isKnownPredicate(Pred, NextIterVal, RightSCEV)) {
435 if (!CanPeelOneMoreIteration())
436 continue; // Need to peel one more iteration, but can't. Give up.
437 PeelOneMoreIteration(); // Great!
438 }
439
440 DesiredPeelCount = std::max(DesiredPeelCount, NewPeelCount);
441 }
442
443 return DesiredPeelCount;
444}
445
446/// This "heuristic" exactly matches implicit behavior which used to exist
447/// inside getLoopEstimatedTripCount. It was added here to keep an
448/// improvement inside that API from causing peeling to become more aggressive.
449/// This should probably be removed.
451 BasicBlock *Latch = L->getLoopLatch();
452 if (!Latch)
453 return true;
454
455 BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
456 if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
457 return true;
458
459 assert((LatchBR->getSuccessor(0) == L->getHeader() ||
460 LatchBR->getSuccessor(1) == L->getHeader()) &&
461 "At least one edge out of the latch must go to the header");
462
464 L->getUniqueNonLatchExitBlocks(ExitBlocks);
465 return any_of(ExitBlocks, [](const BasicBlock *EB) {
466 return !EB->getTerminatingDeoptimizeCall();
467 });
468}
469
470
471// Return the number of iterations we want to peel off.
472void llvm::computePeelCount(Loop *L, unsigned LoopSize,
474 unsigned TripCount, DominatorTree &DT,
476 unsigned Threshold) {
477 assert(LoopSize > 0 && "Zero loop size is not allowed!");
478 // Save the PP.PeelCount value set by the target in
479 // TTI.getPeelingPreferences or by the flag -unroll-peel-count.
480 unsigned TargetPeelCount = PP.PeelCount;
481 PP.PeelCount = 0;
482 if (!canPeel(L))
483 return;
484
485 // Only try to peel innermost loops by default.
486 // The constraint can be relaxed by the target in TTI.getPeelingPreferences
487 // or by the flag -unroll-allow-loop-nests-peeling.
488 if (!PP.AllowLoopNestsPeeling && !L->isInnermost())
489 return;
490
491 // If the user provided a peel count, use that.
492 bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0;
493 if (UserPeelCount) {
494 LLVM_DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount
495 << " iterations.\n");
497 PP.PeelProfiledIterations = true;
498 return;
499 }
500
501 // Skip peeling if it's disabled.
502 if (!PP.AllowPeeling)
503 return;
504
505 // Check that we can peel at least one iteration.
506 if (2 * LoopSize > Threshold)
507 return;
508
509 unsigned AlreadyPeeled = 0;
511 AlreadyPeeled = *Peeled;
512 // Stop if we already peeled off the maximum number of iterations.
513 if (AlreadyPeeled >= UnrollPeelMaxCount)
514 return;
515
516 // Pay respect to limitations implied by loop size and the max peel count.
517 unsigned MaxPeelCount = UnrollPeelMaxCount;
518 MaxPeelCount = std::min(MaxPeelCount, Threshold / LoopSize - 1);
519
520 // Start the max computation with the PP.PeelCount value set by the target
521 // in TTI.getPeelingPreferences or by the flag -unroll-peel-count.
522 unsigned DesiredPeelCount = TargetPeelCount;
523
524 // Here we try to get rid of Phis which become invariants after 1, 2, ..., N
525 // iterations of the loop. For this we compute the number for iterations after
526 // which every Phi is guaranteed to become an invariant, and try to peel the
527 // maximum number of iterations among these values, thus turning all those
528 // Phis into invariants.
529 if (MaxPeelCount > DesiredPeelCount) {
530 // Check how many iterations are useful for resolving Phis
531 auto NumPeels = PhiAnalyzer(*L, MaxPeelCount).calculateIterationsToPeel();
532 if (NumPeels)
533 DesiredPeelCount = std::max(DesiredPeelCount, *NumPeels);
534 }
535
536 DesiredPeelCount = std::max(DesiredPeelCount,
537 countToEliminateCompares(*L, MaxPeelCount, SE));
538
539 if (DesiredPeelCount == 0)
540 DesiredPeelCount = peelToTurnInvariantLoadsDerefencebale(*L, DT, AC);
541
542 if (DesiredPeelCount > 0) {
543 DesiredPeelCount = std::min(DesiredPeelCount, MaxPeelCount);
544 // Consider max peel count limitation.
545 assert(DesiredPeelCount > 0 && "Wrong loop size estimation?");
546 if (DesiredPeelCount + AlreadyPeeled <= UnrollPeelMaxCount) {
547 LLVM_DEBUG(dbgs() << "Peel " << DesiredPeelCount
548 << " iteration(s) to turn"
549 << " some Phis into invariants.\n");
550 PP.PeelCount = DesiredPeelCount;
551 PP.PeelProfiledIterations = false;
552 return;
553 }
554 }
555
556 // Bail if we know the statically calculated trip count.
557 // In this case we rather prefer partial unrolling.
558 if (TripCount)
559 return;
560
561 // Do not apply profile base peeling if it is disabled.
563 return;
564 // If we don't know the trip count, but have reason to believe the average
565 // trip count is low, peeling should be beneficial, since we will usually
566 // hit the peeled section.
567 // We only do this in the presence of profile information, since otherwise
568 // our estimates of the trip count are not reliable enough.
569 if (L->getHeader()->getParent()->hasProfileData()) {
571 return;
572 std::optional<unsigned> EstimatedTripCount = getLoopEstimatedTripCount(L);
573 if (!EstimatedTripCount)
574 return;
575
576 LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is "
577 << *EstimatedTripCount << "\n");
578
579 if (*EstimatedTripCount) {
580 if (*EstimatedTripCount + AlreadyPeeled <= MaxPeelCount) {
581 unsigned PeelCount = *EstimatedTripCount;
582 LLVM_DEBUG(dbgs() << "Peeling first " << PeelCount << " iterations.\n");
583 PP.PeelCount = PeelCount;
584 return;
585 }
586 LLVM_DEBUG(dbgs() << "Already peel count: " << AlreadyPeeled << "\n");
587 LLVM_DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n");
588 LLVM_DEBUG(dbgs() << "Loop cost: " << LoopSize << "\n");
589 LLVM_DEBUG(dbgs() << "Max peel cost: " << Threshold << "\n");
590 LLVM_DEBUG(dbgs() << "Max peel count by cost: "
591 << (Threshold / LoopSize - 1) << "\n");
592 }
593 }
594}
595
597 // Weights for current iteration.
599 // Weights to subtract after each iteration.
601};
602
603/// Update the branch weights of an exiting block of a peeled-off loop
604/// iteration.
605/// Let F is a weight of the edge to continue (fallthrough) into the loop.
606/// Let E is a weight of the edge to an exit.
607/// F/(F+E) is a probability to go to loop and E/(F+E) is a probability to
608/// go to exit.
609/// Then, Estimated ExitCount = F / E.
610/// For I-th (counting from 0) peeled off iteration we set the the weights for
611/// the peeled exit as (EC - I, 1). It gives us reasonable distribution,
612/// The probability to go to exit 1/(EC-I) increases. At the same time
613/// the estimated exit count in the remainder loop reduces by I.
614/// To avoid dealing with division rounding we can just multiple both part
615/// of weights to E and use weight as (F - I * E, E).
616static void updateBranchWeights(Instruction *Term, WeightInfo &Info) {
617 MDBuilder MDB(Term->getContext());
618 Term->setMetadata(LLVMContext::MD_prof,
619 MDB.createBranchWeights(Info.Weights));
620 for (auto [Idx, SubWeight] : enumerate(Info.SubWeights))
621 if (SubWeight != 0)
622 Info.Weights[Idx] = Info.Weights[Idx] > SubWeight
623 ? Info.Weights[Idx] - SubWeight
624 : 1;
625}
626
627/// Initialize the weights for all exiting blocks.
629 Loop *L) {
630 SmallVector<BasicBlock *> ExitingBlocks;
631 L->getExitingBlocks(ExitingBlocks);
632 for (BasicBlock *ExitingBlock : ExitingBlocks) {
633 Instruction *Term = ExitingBlock->getTerminator();
634 SmallVector<uint32_t> Weights;
635 if (!extractBranchWeights(*Term, Weights))
636 continue;
637
638 // See the comment on updateBranchWeights() for an explanation of what we
639 // do here.
640 uint32_t FallThroughWeights = 0;
641 uint32_t ExitWeights = 0;
642 for (auto [Succ, Weight] : zip(successors(Term), Weights)) {
643 if (L->contains(Succ))
644 FallThroughWeights += Weight;
645 else
646 ExitWeights += Weight;
647 }
648
649 // Don't try to update weights for degenerate case.
650 if (FallThroughWeights == 0)
651 continue;
652
653 SmallVector<uint32_t> SubWeights;
654 for (auto [Succ, Weight] : zip(successors(Term), Weights)) {
655 if (!L->contains(Succ)) {
656 // Exit weights stay the same.
657 SubWeights.push_back(0);
658 continue;
659 }
660
661 // Subtract exit weights on each iteration, distributed across all
662 // fallthrough edges.
663 double W = (double)Weight / (double)FallThroughWeights;
664 SubWeights.push_back((uint32_t)(ExitWeights * W));
665 }
666
667 WeightInfos.insert({Term, {std::move(Weights), std::move(SubWeights)}});
668 }
669}
670
671/// Update the weights of original exiting block after peeling off all
672/// iterations.
673static void fixupBranchWeights(Instruction *Term, const WeightInfo &Info) {
674 MDBuilder MDB(Term->getContext());
675 Term->setMetadata(LLVMContext::MD_prof,
676 MDB.createBranchWeights(Info.Weights));
677}
678
679/// Clones the body of the loop L, putting it between \p InsertTop and \p
680/// InsertBot.
681/// \param IterNumber The serial number of the iteration currently being
682/// peeled off.
683/// \param ExitEdges The exit edges of the original loop.
684/// \param[out] NewBlocks A list of the blocks in the newly created clone
685/// \param[out] VMap The value map between the loop and the new clone.
686/// \param LoopBlocks A helper for DFS-traversal of the loop.
687/// \param LVMap A value-map that maps instructions from the original loop to
688/// instructions in the last peeled-off iteration.
689static void cloneLoopBlocks(
690 Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot,
691 SmallVectorImpl<std::pair<BasicBlock *, BasicBlock *>> &ExitEdges,
692 SmallVectorImpl<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
694 LoopInfo *LI, ArrayRef<MDNode *> LoopLocalNoAliasDeclScopes,
695 ScalarEvolution &SE) {
696 BasicBlock *Header = L->getHeader();
697 BasicBlock *Latch = L->getLoopLatch();
698 BasicBlock *PreHeader = L->getLoopPreheader();
699
700 Function *F = Header->getParent();
701 LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
702 LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
703 Loop *ParentLoop = L->getParentLoop();
704
705 // For each block in the original loop, create a new copy,
706 // and update the value map with the newly created values.
707 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
708 BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".peel", F);
709 NewBlocks.push_back(NewBB);
710
711 // If an original block is an immediate child of the loop L, its copy
712 // is a child of a ParentLoop after peeling. If a block is a child of
713 // a nested loop, it is handled in the cloneLoop() call below.
714 if (ParentLoop && LI->getLoopFor(*BB) == L)
715 ParentLoop->addBasicBlockToLoop(NewBB, *LI);
716
717 VMap[*BB] = NewBB;
718
719 // If dominator tree is available, insert nodes to represent cloned blocks.
720 if (DT) {
721 if (Header == *BB)
722 DT->addNewBlock(NewBB, InsertTop);
723 else {
724 DomTreeNode *IDom = DT->getNode(*BB)->getIDom();
725 // VMap must contain entry for IDom, as the iteration order is RPO.
726 DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDom->getBlock()]));
727 }
728 }
729 }
730
731 {
732 // Identify what other metadata depends on the cloned version. After
733 // cloning, replace the metadata with the corrected version for both
734 // memory instructions and noalias intrinsics.
735 std::string Ext = (Twine("Peel") + Twine(IterNumber)).str();
736 cloneAndAdaptNoAliasScopes(LoopLocalNoAliasDeclScopes, NewBlocks,
737 Header->getContext(), Ext);
738 }
739
740 // Recursively create the new Loop objects for nested loops, if any,
741 // to preserve LoopInfo.
742 for (Loop *ChildLoop : *L) {
743 cloneLoop(ChildLoop, ParentLoop, VMap, LI, nullptr);
744 }
745
746 // Hook-up the control flow for the newly inserted blocks.
747 // The new header is hooked up directly to the "top", which is either
748 // the original loop preheader (for the first iteration) or the previous
749 // iteration's exiting block (for every other iteration)
750 InsertTop->getTerminator()->setSuccessor(0, cast<BasicBlock>(VMap[Header]));
751
752 // Similarly, for the latch:
753 // The original exiting edge is still hooked up to the loop exit.
754 // The backedge now goes to the "bottom", which is either the loop's real
755 // header (for the last peeled iteration) or the copied header of the next
756 // iteration (for every other iteration)
757 BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
758 auto *LatchTerm = cast<Instruction>(NewLatch->getTerminator());
759 for (unsigned idx = 0, e = LatchTerm->getNumSuccessors(); idx < e; ++idx)
760 if (LatchTerm->getSuccessor(idx) == Header) {
761 LatchTerm->setSuccessor(idx, InsertBot);
762 break;
763 }
764 if (DT)
765 DT->changeImmediateDominator(InsertBot, NewLatch);
766
767 // The new copy of the loop body starts with a bunch of PHI nodes
768 // that pick an incoming value from either the preheader, or the previous
769 // loop iteration. Since this copy is no longer part of the loop, we
770 // resolve this statically:
771 // For the first iteration, we use the value from the preheader directly.
772 // For any other iteration, we replace the phi with the value generated by
773 // the immediately preceding clone of the loop body (which represents
774 // the previous iteration).
775 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
776 PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
777 if (IterNumber == 0) {
778 VMap[&*I] = NewPHI->getIncomingValueForBlock(PreHeader);
779 } else {
780 Value *LatchVal = NewPHI->getIncomingValueForBlock(Latch);
781 Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
782 if (LatchInst && L->contains(LatchInst))
783 VMap[&*I] = LVMap[LatchInst];
784 else
785 VMap[&*I] = LatchVal;
786 }
787 NewPHI->eraseFromParent();
788 }
789
790 // Fix up the outgoing values - we need to add a value for the iteration
791 // we've just created. Note that this must happen *after* the incoming
792 // values are adjusted, since the value going out of the latch may also be
793 // a value coming into the header.
794 for (auto Edge : ExitEdges)
795 for (PHINode &PHI : Edge.second->phis()) {
796 Value *LatchVal = PHI.getIncomingValueForBlock(Edge.first);
797 Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
798 if (LatchInst && L->contains(LatchInst))
799 LatchVal = VMap[LatchVal];
800 PHI.addIncoming(LatchVal, cast<BasicBlock>(VMap[Edge.first]));
801 SE.forgetValue(&PHI);
802 }
803
804 // LastValueMap is updated with the values for the current loop
805 // which are used the next time this function is called.
806 for (auto KV : VMap)
807 LVMap[KV.first] = KV.second;
808}
809
813 std::optional<bool> UserAllowPeeling,
814 std::optional<bool> UserAllowProfileBasedPeeling,
815 bool UnrollingSpecficValues) {
817
818 // Set the default values.
819 PP.PeelCount = 0;
820 PP.AllowPeeling = true;
821 PP.AllowLoopNestsPeeling = false;
822 PP.PeelProfiledIterations = true;
823
824 // Get the target specifc values.
825 TTI.getPeelingPreferences(L, SE, PP);
826
827 // User specified values using cl::opt.
828 if (UnrollingSpecficValues) {
829 if (UnrollPeelCount.getNumOccurrences() > 0)
831 if (UnrollAllowPeeling.getNumOccurrences() > 0)
833 if (UnrollAllowLoopNestsPeeling.getNumOccurrences() > 0)
835 }
836
837 // User specifed values provided by argument.
838 if (UserAllowPeeling)
839 PP.AllowPeeling = *UserAllowPeeling;
840 if (UserAllowProfileBasedPeeling)
841 PP.PeelProfiledIterations = *UserAllowProfileBasedPeeling;
842
843 return PP;
844}
845
846/// Peel off the first \p PeelCount iterations of loop \p L.
847///
848/// Note that this does not peel them off as a single straight-line block.
849/// Rather, each iteration is peeled off separately, and needs to check the
850/// exit condition.
851/// For loops that dynamically execute \p PeelCount iterations or less
852/// this provides a benefit, since the peeled off iterations, which account
853/// for the bulk of dynamic execution, can be further simplified by scalar
854/// optimizations.
855bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
857 bool PreserveLCSSA, ValueToValueMapTy &LVMap) {
858 assert(PeelCount > 0 && "Attempt to peel out zero iterations?");
859 assert(canPeel(L) && "Attempt to peel a loop which is not peelable?");
860
861 LoopBlocksDFS LoopBlocks(L);
862 LoopBlocks.perform(LI);
863
864 BasicBlock *Header = L->getHeader();
865 BasicBlock *PreHeader = L->getLoopPreheader();
866 BasicBlock *Latch = L->getLoopLatch();
868 L->getExitEdges(ExitEdges);
869
870 // Remember dominators of blocks we might reach through exits to change them
871 // later. Immediate dominator of such block might change, because we add more
872 // routes which can lead to the exit: we can reach it from the peeled
873 // iterations too.
874 DenseMap<BasicBlock *, BasicBlock *> NonLoopBlocksIDom;
875 for (auto *BB : L->blocks()) {
876 auto *BBDomNode = DT.getNode(BB);
877 SmallVector<BasicBlock *, 16> ChildrenToUpdate;
878 for (auto *ChildDomNode : BBDomNode->children()) {
879 auto *ChildBB = ChildDomNode->getBlock();
880 if (!L->contains(ChildBB))
881 ChildrenToUpdate.push_back(ChildBB);
882 }
883 // The new idom of the block will be the nearest common dominator
884 // of all copies of the previous idom. This is equivalent to the
885 // nearest common dominator of the previous idom and the first latch,
886 // which dominates all copies of the previous idom.
887 BasicBlock *NewIDom = DT.findNearestCommonDominator(BB, Latch);
888 for (auto *ChildBB : ChildrenToUpdate)
889 NonLoopBlocksIDom[ChildBB] = NewIDom;
890 }
891
892 Function *F = Header->getParent();
893
894 // Set up all the necessary basic blocks. It is convenient to split the
895 // preheader into 3 parts - two blocks to anchor the peeled copy of the loop
896 // body, and a new preheader for the "real" loop.
897
898 // Peeling the first iteration transforms.
899 //
900 // PreHeader:
901 // ...
902 // Header:
903 // LoopBody
904 // If (cond) goto Header
905 // Exit:
906 //
907 // into
908 //
909 // InsertTop:
910 // LoopBody
911 // If (!cond) goto Exit
912 // InsertBot:
913 // NewPreHeader:
914 // ...
915 // Header:
916 // LoopBody
917 // If (cond) goto Header
918 // Exit:
919 //
920 // Each following iteration will split the current bottom anchor in two,
921 // and put the new copy of the loop body between these two blocks. That is,
922 // after peeling another iteration from the example above, we'll split
923 // InsertBot, and get:
924 //
925 // InsertTop:
926 // LoopBody
927 // If (!cond) goto Exit
928 // InsertBot:
929 // LoopBody
930 // If (!cond) goto Exit
931 // InsertBot.next:
932 // NewPreHeader:
933 // ...
934 // Header:
935 // LoopBody
936 // If (cond) goto Header
937 // Exit:
938
939 BasicBlock *InsertTop = SplitEdge(PreHeader, Header, &DT, LI);
940 BasicBlock *InsertBot =
941 SplitBlock(InsertTop, InsertTop->getTerminator(), &DT, LI);
942 BasicBlock *NewPreHeader =
943 SplitBlock(InsertBot, InsertBot->getTerminator(), &DT, LI);
944
945 InsertTop->setName(Header->getName() + ".peel.begin");
946 InsertBot->setName(Header->getName() + ".peel.next");
947 NewPreHeader->setName(PreHeader->getName() + ".peel.newph");
948
949 Instruction *LatchTerm =
950 cast<Instruction>(cast<BasicBlock>(Latch)->getTerminator());
951
952 // If we have branch weight information, we'll want to update it for the
953 // newly created branches.
955 initBranchWeights(Weights, L);
956
957 // Identify what noalias metadata is inside the loop: if it is inside the
958 // loop, the associated metadata must be cloned for each iteration.
959 SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;
960 identifyNoAliasScopesToClone(L->getBlocks(), LoopLocalNoAliasDeclScopes);
961
962 // For each peeled-off iteration, make a copy of the loop.
963 for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
966
967 cloneLoopBlocks(L, Iter, InsertTop, InsertBot, ExitEdges, NewBlocks,
968 LoopBlocks, VMap, LVMap, &DT, LI,
969 LoopLocalNoAliasDeclScopes, *SE);
970
971 // Remap to use values from the current iteration instead of the
972 // previous one.
973 remapInstructionsInBlocks(NewBlocks, VMap);
974
975 // Update IDoms of the blocks reachable through exits.
976 if (Iter == 0)
977 for (auto BBIDom : NonLoopBlocksIDom)
978 DT.changeImmediateDominator(BBIDom.first,
979 cast<BasicBlock>(LVMap[BBIDom.second]));
980#ifdef EXPENSIVE_CHECKS
981 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
982#endif
983
984 for (auto &[Term, Info] : Weights) {
985 auto *TermCopy = cast<Instruction>(VMap[Term]);
986 updateBranchWeights(TermCopy, Info);
987 }
988
989 // Remove Loop metadata from the latch branch instruction
990 // because it is not the Loop's latch branch anymore.
991 auto *LatchTermCopy = cast<Instruction>(VMap[LatchTerm]);
992 LatchTermCopy->setMetadata(LLVMContext::MD_loop, nullptr);
993
994 InsertTop = InsertBot;
995 InsertBot = SplitBlock(InsertBot, InsertBot->getTerminator(), &DT, LI);
996 InsertBot->setName(Header->getName() + ".peel.next");
997
998 F->splice(InsertTop->getIterator(), F, NewBlocks[0]->getIterator(),
999 F->end());
1000 }
1001
1002 // Now adjust the phi nodes in the loop header to get their initial values
1003 // from the last peeled-off iteration instead of the preheader.
1004 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
1005 PHINode *PHI = cast<PHINode>(I);
1006 Value *NewVal = PHI->getIncomingValueForBlock(Latch);
1007 Instruction *LatchInst = dyn_cast<Instruction>(NewVal);
1008 if (LatchInst && L->contains(LatchInst))
1009 NewVal = LVMap[LatchInst];
1010
1011 PHI->setIncomingValueForBlock(NewPreHeader, NewVal);
1012 }
1013
1014 for (const auto &[Term, Info] : Weights)
1015 fixupBranchWeights(Term, Info);
1016
1017 // Update Metadata for count of peeled off iterations.
1018 unsigned AlreadyPeeled = 0;
1020 AlreadyPeeled = *Peeled;
1021 addStringMetadataToLoop(L, PeeledCountMetaData, AlreadyPeeled + PeelCount);
1022
1023 if (Loop *ParentLoop = L->getParentLoop())
1024 L = ParentLoop;
1025
1026 // We modified the loop, update SE.
1027 SE->forgetTopmostLoop(L);
1028
1029#ifdef EXPENSIVE_CHECKS
1030 // Finally DomtTree must be correct.
1031 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
1032#endif
1033
1034 // FIXME: Incrementally update loop-simplify
1035 simplifyLoop(L, &DT, LI, SE, AC, nullptr, PreserveLCSSA);
1036
1037 NumPeeled++;
1038
1039 return true;
1040}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Rewrite undef for PHI
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
static void updateBranchWeights(Instruction *Term, WeightInfo &Info)
Update the branch weights of an exiting block of a peeled-off loop iteration.
Definition: LoopPeel.cpp:616
static cl::opt< bool > DisableAdvancedPeeling("disable-advanced-peeling", cl::init(false), cl::Hidden, cl::desc("Disable advance peeling. Issues for convergent targets (D134803)."))
static cl::opt< unsigned > UnrollPeelMaxCount("unroll-peel-max-count", cl::init(7), cl::Hidden, cl::desc("Max average trip count which will cause loop peeling."))
static cl::opt< bool > UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden, cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low."))
static cl::opt< unsigned > UnrollForcePeelCount("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))
static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE)
Definition: LoopPeel.cpp:343
static bool violatesLegacyMultiExitLoopCheck(Loop *L)
This "heuristic" exactly matches implicit behavior which used to exist inside getLoopEstimatedTripCou...
Definition: LoopPeel.cpp:450
static const char * PeeledCountMetaData
Definition: LoopPeel.cpp:80
static void cloneLoopBlocks(Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot, SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &ExitEdges, SmallVectorImpl< BasicBlock * > &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT, LoopInfo *LI, ArrayRef< MDNode * > LoopLocalNoAliasDeclScopes, ScalarEvolution &SE)
Clones the body of the loop L, putting it between InsertTop and InsertBot.
Definition: LoopPeel.cpp:689
static cl::opt< bool > UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling", cl::init(false), cl::Hidden, cl::desc("Allows loop nests to be peeled."))
static cl::opt< unsigned > UnrollPeelCount("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))
static unsigned peelToTurnInvariantLoadsDerefencebale(Loop &L, DominatorTree &DT, AssumptionCache *AC)
Definition: LoopPeel.cpp:276
static void fixupBranchWeights(Instruction *Term, const WeightInfo &Info)
Update the weights of original exiting block after peeling off all iterations.
Definition: LoopPeel.cpp:673
static void initBranchWeights(DenseMap< Instruction *, WeightInfo > &WeightInfos, Loop *L)
Initialize the weights for all exiting blocks.
Definition: LoopPeel.cpp:628
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file contains the declarations for profiling metadata utility functions.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
Definition: BasicBlock.cpp:181
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:127
Conditional or Unconditional Branch instruction.
unsigned getNumSuccessors() const
BasicBlock * getSuccessor(unsigned i) const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
DomTreeNodeBase * getIDom() const
NodeT * getBlock() const
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
Definition: Dominators.cpp:344
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
bool isEquality() const
Return true if this predicate is either EQ or NE.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:258
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:101
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1222
RPOIterator endRPO() const
Definition: LoopIterator.h:140
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
Definition: MDBuilder.cpp:37
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
std::optional< bool > evaluatePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
void forgetTopmostLoop(const Loop *L)
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
iterator find(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:386
iterator end() const
Definition: SmallPtrSet.h:408
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
void getPeelingPreferences(Loop *L, ScalarEvolution &SE, PeelingPreferences &PP) const
Get target-customized preferences for the generic loop peeling transformation.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
LLVM Value Representation.
Definition: Value.h:74
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
self_iterator getIterator()
Definition: ilist_node.h:82
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:927
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:824
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1782
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::PeelingPreferences &PP, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, AssumptionCache *AC=nullptr, unsigned Threshold=UINT_MAX)
Definition: LoopPeel.cpp:472
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
Definition: STLExtras.h:2387
auto successors(const MachineBasicBlock *BB)
bool canPeel(const Loop *L)
Definition: LoopPeel.cpp:83
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
Definition: LoopUtils.cpp:214
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1789
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, std::optional< bool > UserAllowPeeling, std::optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)
Definition: LoopPeel.cpp:811
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
Definition: LoopInfo.cpp:1089
void cloneAndAdaptNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, ArrayRef< BasicBlock * > NewBlocks, LLVMContext &Context, StringRef Ext)
Clone the specified noalias decl scopes.
void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
Definition: Loads.cpp:221
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree &DT, AssumptionCache *AC, bool PreserveLCSSA, ValueToValueMapTy &VMap)
VMap is the value-map that maps instructions from the original loop to instructions in the last peele...
Definition: LoopPeel.cpp:855
Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
Definition: LoopUtils.cpp:1554
Definition: BitVector.h:851
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
SmallVector< uint32_t > Weights
Definition: LoopPeel.cpp:598
const SmallVector< uint32_t > SubWeights
Definition: LoopPeel.cpp:600
bool AllowPeeling
Allow peeling off loop iterations.
bool AllowLoopNestsPeeling
Allow peeling off loop iterations for loop nests.
bool PeelProfiledIterations
Allow peeling basing on profile.
unsigned PeelCount
A forced peeling factor (the number of bodied of the original loop that should be peeled off before t...