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"
14 #include "llvm/ADT/SmallVector.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/Analysis/Loads.h"
17 #include "llvm/Analysis/LoopInfo.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"
34 #include "llvm/Support/Debug.h"
41 #include <algorithm>
42 #include <cassert>
43 #include <cstdint>
44 #include <optional>
45 
46 using namespace llvm;
47 using namespace llvm::PatternMatch;
48 
49 #define DEBUG_TYPE "loop-peel"
50 
51 STATISTIC(NumPeeled, "Number of loops peeled");
52 
54  "unroll-peel-count", cl::Hidden,
55  cl::desc("Set the unroll peeling count, for testing purposes"));
56 
57 static 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 
62 static 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,
77  cl::desc(
78  "Disable advance peeling. Issues for convergent targets (D134803)."));
79 
80 static const char *PeeledCountMetaData = "llvm.loop.peeled.count";
81 
82 // Check whether we are capable of peeling this loop.
83 bool 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 
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 
103 namespace {
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.
157 class PhiAnalyzer {
158 public:
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 
165 protected:
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 
187 PhiAnalyzer::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)
207 PhiAnalyzer::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 
255 std::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.
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 // }
343 static 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;
359  CmpInst::Predicate Pred;
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 
463  SmallVector<BasicBlock *, 4> ExitBlocks;
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.
472 void 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;
510  if (auto Peeled = getOptionalIntLoopAttribute(L, PeeledCountMetaData))
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.
562  if (!PP.PeelProfiledIterations)
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 
596 struct WeightInfo {
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).
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.
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.
689 static 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 
812  const TargetTransformInfo &TTI,
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)
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.
855 bool 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) {
965  ValueToValueMapTy VMap;
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
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)
1016 
1017  // Update Metadata for count of peeled off iterations.
1018  unsigned AlreadyPeeled = 0;
1019  if (auto Peeled = getOptionalIntLoopAttribute(L, PeeledCountMetaData))
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.
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 }
UnrollPeelCount
static cl::opt< unsigned > UnrollPeelCount("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))
llvm::BasicBlock::getTerminatingDeoptimizeCall
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
Definition: BasicBlock.cpp:181
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:60
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
LoopSimplify.h
ValueMapper.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:114
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
llvm::SCEVAddRecExpr::isAffine
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
Definition: ScalarEvolutionExpressions.h:358
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:90
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
Loads.h
violatesLegacyMultiExitLoopCheck
static bool violatesLegacyMultiExitLoopCheck(Loop *L)
This "heuristic" exactly matches implicit behavior which used to exist inside getLoopEstimatedTripCou...
Definition: LoopPeel.cpp:450
llvm::Function
Definition: Function.h:59
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::computePeelCount
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
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
double
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in and only one load from a constant double
Definition: README-SSE.txt:85
llvm::successors
auto successors(const MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::TargetTransformInfo::PeelingPreferences::AllowPeeling
bool AllowPeeling
Allow peeling off loop iterations.
Definition: TargetTransformInfo.h:534
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:276
llvm::enumerate
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:2264
UnrollPeelMaxCount
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."))
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:172
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:452
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::PPC::getSwappedPredicate
Predicate getSwappedPredicate(Predicate Opcode)
Assume the condition register is set by MI(a,b), return the predicate if we modify the instructions s...
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:138
ScalarEvolution.h
DenseMap.h
llvm::TargetTransformInfo::PeelingPreferences
Definition: TargetTransformInfo.h:528
updateBranchWeights
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
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:367
llvm::LoopBase::getExitEdges
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
Definition: LoopInfoImpl.h:164
llvm::BranchInst::getNumSuccessors
unsigned getNumSuccessors() const
Definition: Instructions.h:3230
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::canPeel
bool canPeel(const Loop *L)
Definition: LoopPeel.cpp:83
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:90
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:105
WeightInfo
Definition: LoopPeel.cpp:596
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::LoopBlocksDFS::beginRPO
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
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
PeeledCountMetaData
static const char * PeeledCountMetaData
Definition: LoopPeel.cpp:80
Instruction.h
CommandLine.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
WeightInfo::SubWeights
const SmallVector< uint32_t > SubWeights
Definition: LoopPeel.cpp:600
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
llvm::all_of
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:1735
llvm::TargetTransformInfo::PeelingPreferences::PeelProfiledIterations
bool PeelProfiledIterations
Allow peeling basing on profile.
Definition: TargetTransformInfo.h:541
WeightInfo::Weights
SmallVector< uint32_t > Weights
Definition: LoopPeel.cpp:598
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
countToEliminateCompares
static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE)
Definition: LoopPeel.cpp:343
InstrTypes.h
llvm::remapInstructionsInBlocks
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock * > &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
Definition: CloneFunction.cpp:940
llvm::MDBuilder::createBranchWeights
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
Definition: MDBuilder.cpp:37
UnrollForcePeelCount
static cl::opt< unsigned > UnrollForcePeelCount("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))
llvm::cloneLoop
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:1541
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:195
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2889
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:188
llvm::ScalarEvolution::isKnownPredicate
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,...
Definition: ScalarEvolution.cpp:10904
llvm::Instruction
Definition: Instruction.h:41
llvm::LoopBlocksDFS::endRPO
RPOIterator endRPO() const
Definition: LoopIterator.h:140
MDBuilder.h
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:372
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:33
llvm::cl::Option::getNumOccurrences
int getNumOccurrences() const
Definition: CommandLine.h:401
LoopUtils.h
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::BasicBlock::getModule
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:146
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: GenericDomTree.h:672
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
PatternMatch.h
LoopIterator.h
llvm::peelLoop
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
LoopInfo.h
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4534
llvm::LoopBlocksDFS::RPOIterator
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:101
llvm::LoopBlocksDFS
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
llvm::cloneAndAdaptNoAliasScopes
void cloneAndAdaptNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, ArrayRef< BasicBlock * > NewBlocks, LLVMContext &Context, StringRef Ext)
Clone the specified noalias decl scopes.
Definition: CloneFunction.cpp:1143
llvm::ScalarEvolution::evaluatePredicate
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.
Definition: ScalarEvolution.cpp:10919
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:479
llvm::CloneBasicBlock
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...
Definition: CloneFunction.cpp:42
BasicBlock.h
llvm::cl::opt
Definition: CommandLine.h:1410
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::MipsISD::Ext
@ Ext
Definition: MipsISelLowering.h:159
llvm::SmallPtrSetImpl::find
iterator find(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:386
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:89
llvm::pdb::Unknown
@ Unknown
Definition: PDBTypes.h:396
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:408
llvm::addStringMetadataToLoop
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
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
ProfDataUtils.h
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:31
llvm::DenseMap
Definition: DenseMap.h:714
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
I
#define I(x, y, z)
Definition: MD5.cpp:58
Cloning.h
llvm::SCEVNAryExpr::hasNoSelfWrap
bool hasNoSelfWrap() const
Definition: ScalarEvolutionExpressions.h:217
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
llvm::ScalarEvolution::forgetValue
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...
Definition: ScalarEvolution.cpp:8523
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1222
llvm::TargetTransformInfo::PeelingPreferences::AllowLoopNestsPeeling
bool AllowLoopNestsPeeling
Allow peeling off loop iterations for loop nests.
Definition: TargetTransformInfo.h:536
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:232
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:62
llvm::ScalarEvolution::forgetTopmostLoop
void forgetTopmostLoop(const Loop *L)
Definition: ScalarEvolution.cpp:8519
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::TargetTransformInfo::PeelingPreferences::PeelCount
unsigned PeelCount
A forced peeling factor (the number of bodied of the original loop that should be peeled off before t...
Definition: TargetTransformInfo.h:532
llvm::getOptionalIntLoopAttribute
std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
Definition: LoopInfo.cpp:1089
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::ScalarEvolution::getMonotonicPredicateType
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,...
Definition: ScalarEvolution.cpp:10962
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::any_of
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:1742
llvm::isDereferenceablePointer
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
llvm::identifyNoAliasScopesToClone
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
Definition: CloneFunction.cpp:1180
llvm::Instruction::setSuccessor
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Definition: Instruction.cpp:847
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:497
UnrollAllowLoopNestsPeeling
static cl::opt< bool > UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling", cl::init(false), cl::Hidden, cl::desc("Allows loop nests to be peeled."))
uint32_t
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::gatherPeelingPreferences
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
UnrollAllowPeeling
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."))
llvm::DomTreeNodeBase< BasicBlock >
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::LoopBase::getUniqueNonLatchExitBlocks
void getUniqueNonLatchExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop except successors from Latch block are not considered...
Definition: LoopInfoImpl.h:149
llvm::DominatorTreeBase::addNewBlock
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
Definition: GenericDomTree.h:636
llvm::LoopBase::isInnermost
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
Definition: LoopInfo.h:182
llvm::SplitEdge
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...
Definition: BasicBlockUtils.cpp:615
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
fixupBranchWeights
static void fixupBranchWeights(Instruction *Term, const WeightInfo &Info)
Update the weights of original exiting block after peeling off all iterations.
Definition: LoopPeel.cpp:673
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:342
std
Definition: BitVector.h:851
initBranchWeights
static void initBranchWeights(DenseMap< Instruction *, WeightInfo > &WeightInfos, Loop *L)
Initialize the weights for all exiting blocks.
Definition: LoopPeel.cpp:628
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:330
Casting.h
Function.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
llvm::DominatorTree::findNearestCommonDominator
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:358
llvm::simplifyLoop
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
Definition: LoopSimplify.cpp:708
llvm::Function::hasProfileData
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
Definition: Function.h:289
llvm::MDBuilder
Definition: MDBuilder.h:36
ScalarEvolutionExpressions.h
Instructions.h
llvm::IsBlockFollowedByDeoptOrUnreachable
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 @...
Definition: BasicBlockUtils.cpp:596
peelToTurnInvariantLoadsDerefencebale
static unsigned peelToTurnInvariantLoadsDerefencebale(Loop &L, DominatorTree &DT, AssumptionCache *AC)
Definition: LoopPeel.cpp:276
SmallVector.h
cloneLoopBlocks
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
llvm::LoopBase::addBasicBlockToLoop
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:258
llvm::zip
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:882
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1394
Dominators.h
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:819
TargetTransformInfo.h
llvm::TargetTransformInfo::getPeelingPreferences
void getPeelingPreferences(Loop *L, ScalarEvolution &SE, PeelingPreferences &PP) const
Get target-customized preferences for the generic loop peeling transformation.
Definition: TargetTransformInfo.cpp:341
llvm::PHINode
Definition: Instructions.h:2708
llvm::BasicBlock::getTerminator
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
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:401
llvm::ScalarEvolution::getAddExpr
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.
Definition: ScalarEvolution.cpp:2537
llvm::LoopBase::isLoopExiting
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
Definition: LoopInfo.h:242
llvm::extractBranchWeights
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
Definition: ProfDataUtils.cpp:122
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
LLVMContext.h
llvm::cl::desc
Definition: CommandLine.h:411
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3139
raw_ostream.h
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
LoopPeel.h
BasicBlockUtils.h
DisableAdvancedPeeling
static cl::opt< bool > DisableAdvancedPeeling("disable-advanced-peeling", cl::init(false), cl::Hidden, cl::desc("Disable advance peeling. Issues for convergent targets (D134803)."))
llvm::SplitBlock
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.
Definition: BasicBlockUtils.cpp:935
llvm::getLoopEstimatedTripCount
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:811
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3232
llvm::SCEVAddRecExpr::getStepRecurrence
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Definition: ScalarEvolutionExpressions.h:348
llvm::SCEVAddRecExpr::evaluateAtIteration
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
Definition: ScalarEvolution.cpp:1034
llvm::SmallPtrSetImpl::insert
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