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