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