LLVM  7.0.0svn
LoopUnrollPeel.cpp
Go to the documentation of this file.
1 //===- UnrollLoopPeel.cpp - Loop peeling utilities ------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements some loop unrolling utilities for peeling loops
11 // with dynamically inferred (from PGO) trip counts. See LoopUnroll.cpp for
12 // unrolling loops with compile-time constant trip counts.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/Optional.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/LoopInfo.h"
25 #include "llvm/IR/BasicBlock.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/IR/InstrTypes.h"
29 #include "llvm/IR/Instruction.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/LLVMContext.h"
32 #include "llvm/IR/MDBuilder.h"
33 #include "llvm/IR/Metadata.h"
34 #include "llvm/IR/PatternMatch.h"
35 #include "llvm/Support/Casting.h"
37 #include "llvm/Support/Debug.h"
45 #include <algorithm>
46 #include <cassert>
47 #include <cstdint>
48 #include <limits>
49 
50 using namespace llvm;
51 using namespace llvm::PatternMatch;
52 
53 #define DEBUG_TYPE "loop-unroll"
54 
55 STATISTIC(NumPeeled, "Number of loops peeled");
56 
58  "unroll-peel-max-count", cl::init(7), cl::Hidden,
59  cl::desc("Max average trip count which will cause loop peeling."));
60 
62  "unroll-force-peel-count", cl::init(0), cl::Hidden,
63  cl::desc("Force a peel count regardless of profiling information."));
64 
65 // Designates that a Phi is estimated to become invariant after an "infinite"
66 // number of loop iterations (i.e. only may become an invariant if the loop is
67 // fully unrolled).
68 static const unsigned InfiniteIterationsToInvariance =
70 
71 // Check whether we are capable of peeling this loop.
72 bool llvm::canPeel(Loop *L) {
73  // Make sure the loop is in simplified form
74  if (!L->isLoopSimplifyForm())
75  return false;
76 
77  // Only peel loops that contain a single exit
78  if (!L->getExitingBlock() || !L->getUniqueExitBlock())
79  return false;
80 
81  // Don't try to peel loops where the latch is not the exiting block.
82  // This can be an indication of two different things:
83  // 1) The loop is not rotated.
84  // 2) The loop contains irreducible control flow that involves the latch.
85  if (L->getLoopLatch() != L->getExitingBlock())
86  return false;
87 
88  return true;
89 }
90 
91 // This function calculates the number of iterations after which the given Phi
92 // becomes an invariant. The pre-calculated values are memorized in the map. The
93 // function (shortcut is I) is calculated according to the following definition:
94 // Given %x = phi <Inputs from above the loop>, ..., [%y, %back.edge].
95 // If %y is a loop invariant, then I(%x) = 1.
96 // If %y is a Phi from the loop header, I(%x) = I(%y) + 1.
97 // Otherwise, I(%x) is infinite.
98 // TODO: Actually if %y is an expression that depends only on Phi %z and some
99 // loop invariants, we can estimate I(%x) = I(%z) + 1. The example
100 // looks like:
101 // %x = phi(0, %a), <-- becomes invariant starting from 3rd iteration.
102 // %y = phi(0, 5),
103 // %a = %y + 1.
105  PHINode *Phi, Loop *L, BasicBlock *BackEdge,
106  SmallDenseMap<PHINode *, unsigned> &IterationsToInvariance) {
107  assert(Phi->getParent() == L->getHeader() &&
108  "Non-loop Phi should not be checked for turning into invariant.");
109  assert(BackEdge == L->getLoopLatch() && "Wrong latch?");
110  // If we already know the answer, take it from the map.
111  auto I = IterationsToInvariance.find(Phi);
112  if (I != IterationsToInvariance.end())
113  return I->second;
114 
115  // Otherwise we need to analyze the input from the back edge.
116  Value *Input = Phi->getIncomingValueForBlock(BackEdge);
117  // Place infinity to map to avoid infinite recursion for cycled Phis. Such
118  // cycles can never stop on an invariant.
119  IterationsToInvariance[Phi] = InfiniteIterationsToInvariance;
120  unsigned ToInvariance = InfiniteIterationsToInvariance;
121 
122  if (L->isLoopInvariant(Input))
123  ToInvariance = 1u;
124  else if (PHINode *IncPhi = dyn_cast<PHINode>(Input)) {
125  // Only consider Phis in header block.
126  if (IncPhi->getParent() != L->getHeader())
127  return InfiniteIterationsToInvariance;
128  // If the input becomes an invariant after X iterations, then our Phi
129  // becomes an invariant after X + 1 iterations.
130  unsigned InputToInvariance = calculateIterationsToInvariance(
131  IncPhi, L, BackEdge, IterationsToInvariance);
132  if (InputToInvariance != InfiniteIterationsToInvariance)
133  ToInvariance = InputToInvariance + 1u;
134  }
135 
136  // If we found that this Phi lies in an invariant chain, update the map.
137  if (ToInvariance != InfiniteIterationsToInvariance)
138  IterationsToInvariance[Phi] = ToInvariance;
139  return ToInvariance;
140 }
141 
142 // Return the number of iterations to peel off that make conditions in the
143 // body true/false. For example, if we peel 2 iterations off the loop below,
144 // the condition i < 2 can be evaluated at compile time.
145 // for (i = 0; i < n; i++)
146 // if (i < 2)
147 // ..
148 // else
149 // ..
150 // }
151 static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount,
152  ScalarEvolution &SE) {
153  assert(L.isLoopSimplifyForm() && "Loop needs to be in loop simplify form");
154  unsigned DesiredPeelCount = 0;
155 
156  for (auto *BB : L.blocks()) {
157  auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
158  if (!BI || BI->isUnconditional())
159  continue;
160 
161  // Ignore loop exit condition.
162  if (L.getLoopLatch() == BB)
163  continue;
164 
165  Value *Condition = BI->getCondition();
166  Value *LeftVal, *RightVal;
167  CmpInst::Predicate Pred;
168  if (!match(Condition, m_ICmp(Pred, m_Value(LeftVal), m_Value(RightVal))))
169  continue;
170 
171  const SCEV *LeftSCEV = SE.getSCEV(LeftVal);
172  const SCEV *RightSCEV = SE.getSCEV(RightVal);
173 
174  // Do not consider predicates that are known to be true or false
175  // independently of the loop iteration.
176  if (SE.isKnownPredicate(Pred, LeftSCEV, RightSCEV) ||
178  RightSCEV))
179  continue;
180 
181  // Check if we have a condition with one AddRec and one non AddRec
182  // expression. Normalize LeftSCEV to be the AddRec.
183  if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
184  if (isa<SCEVAddRecExpr>(RightSCEV)) {
185  std::swap(LeftSCEV, RightSCEV);
186  Pred = ICmpInst::getSwappedPredicate(Pred);
187  } else
188  continue;
189  }
190 
191  const SCEVAddRecExpr *LeftAR = cast<SCEVAddRecExpr>(LeftSCEV);
192 
193  // Avoid huge SCEV computations in the loop below, make sure we only
194  // consider AddRecs of the loop we are trying to peel and avoid
195  // non-monotonic predicates, as we will not be able to simplify the loop
196  // body.
197  // FIXME: For the non-monotonic predicates ICMP_EQ and ICMP_NE we can
198  // simplify the loop, if we peel 1 additional iteration, if there
199  // is no wrapping.
200  bool Increasing;
201  if (!LeftAR->isAffine() || LeftAR->getLoop() != &L ||
202  !SE.isMonotonicPredicate(LeftAR, Pred, Increasing))
203  continue;
204  (void)Increasing;
205 
206  // Check if extending the current DesiredPeelCount lets us evaluate Pred
207  // or !Pred in the loop body statically.
208  unsigned NewPeelCount = DesiredPeelCount;
209 
210  const SCEV *IterVal = LeftAR->evaluateAtIteration(
211  SE.getConstant(LeftSCEV->getType(), NewPeelCount), SE);
212 
213  // If the original condition is not known, get the negated predicate
214  // (which holds on the else branch) and check if it is known. This allows
215  // us to peel of iterations that make the original condition false.
216  if (!SE.isKnownPredicate(Pred, IterVal, RightSCEV))
217  Pred = ICmpInst::getInversePredicate(Pred);
218 
219  const SCEV *Step = LeftAR->getStepRecurrence(SE);
220  while (NewPeelCount < MaxPeelCount &&
221  SE.isKnownPredicate(Pred, IterVal, RightSCEV)) {
222  IterVal = SE.getAddExpr(IterVal, Step);
223  NewPeelCount++;
224  }
225 
226  // Only peel the loop if the monotonic predicate !Pred becomes known in the
227  // first iteration of the loop body after peeling.
228  if (NewPeelCount > DesiredPeelCount &&
230  RightSCEV))
231  DesiredPeelCount = NewPeelCount;
232  }
233 
234  return DesiredPeelCount;
235 }
236 
237 // Return the number of iterations we want to peel off.
238 void llvm::computePeelCount(Loop *L, unsigned LoopSize,
240  unsigned &TripCount, ScalarEvolution &SE) {
241  assert(LoopSize > 0 && "Zero loop size is not allowed!");
242  // Save the UP.PeelCount value set by the target in
243  // TTI.getUnrollingPreferences or by the flag -unroll-peel-count.
244  unsigned TargetPeelCount = UP.PeelCount;
245  UP.PeelCount = 0;
246  if (!canPeel(L))
247  return;
248 
249  // Only try to peel innermost loops.
250  if (!L->empty())
251  return;
252 
253  // If the user provided a peel count, use that.
254  bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0;
255  if (UserPeelCount) {
256  LLVM_DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount
257  << " iterations.\n");
259  return;
260  }
261 
262  // Skip peeling if it's disabled.
263  if (!UP.AllowPeeling)
264  return;
265 
266  // Here we try to get rid of Phis which become invariants after 1, 2, ..., N
267  // iterations of the loop. For this we compute the number for iterations after
268  // which every Phi is guaranteed to become an invariant, and try to peel the
269  // maximum number of iterations among these values, thus turning all those
270  // Phis into invariants.
271  // First, check that we can peel at least one iteration.
272  if (2 * LoopSize <= UP.Threshold && UnrollPeelMaxCount > 0) {
273  // Store the pre-calculated values here.
274  SmallDenseMap<PHINode *, unsigned> IterationsToInvariance;
275  // Now go through all Phis to calculate their the number of iterations they
276  // need to become invariants.
277  // Start the max computation with the UP.PeelCount value set by the target
278  // in TTI.getUnrollingPreferences or by the flag -unroll-peel-count.
279  unsigned DesiredPeelCount = TargetPeelCount;
280  BasicBlock *BackEdge = L->getLoopLatch();
281  assert(BackEdge && "Loop is not in simplified form?");
282  for (auto BI = L->getHeader()->begin(); isa<PHINode>(&*BI); ++BI) {
283  PHINode *Phi = cast<PHINode>(&*BI);
284  unsigned ToInvariance = calculateIterationsToInvariance(
285  Phi, L, BackEdge, IterationsToInvariance);
286  if (ToInvariance != InfiniteIterationsToInvariance)
287  DesiredPeelCount = std::max(DesiredPeelCount, ToInvariance);
288  }
289 
290  // Pay respect to limitations implied by loop size and the max peel count.
291  unsigned MaxPeelCount = UnrollPeelMaxCount;
292  MaxPeelCount = std::min(MaxPeelCount, UP.Threshold / LoopSize - 1);
293 
294  DesiredPeelCount = std::max(DesiredPeelCount,
295  countToEliminateCompares(*L, MaxPeelCount, SE));
296 
297  if (DesiredPeelCount > 0) {
298  DesiredPeelCount = std::min(DesiredPeelCount, MaxPeelCount);
299  // Consider max peel count limitation.
300  assert(DesiredPeelCount > 0 && "Wrong loop size estimation?");
301  LLVM_DEBUG(dbgs() << "Peel " << DesiredPeelCount
302  << " iteration(s) to turn"
303  << " some Phis into invariants.\n");
304  UP.PeelCount = DesiredPeelCount;
305  return;
306  }
307  }
308 
309  // Bail if we know the statically calculated trip count.
310  // In this case we rather prefer partial unrolling.
311  if (TripCount)
312  return;
313 
314  // If we don't know the trip count, but have reason to believe the average
315  // trip count is low, peeling should be beneficial, since we will usually
316  // hit the peeled section.
317  // We only do this in the presence of profile information, since otherwise
318  // our estimates of the trip count are not reliable enough.
319  if (L->getHeader()->getParent()->hasProfileData()) {
321  if (!PeelCount)
322  return;
323 
324  LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is " << *PeelCount
325  << "\n");
326 
327  if (*PeelCount) {
328  if ((*PeelCount <= UnrollPeelMaxCount) &&
329  (LoopSize * (*PeelCount + 1) <= UP.Threshold)) {
330  LLVM_DEBUG(dbgs() << "Peeling first " << *PeelCount
331  << " iterations.\n");
332  UP.PeelCount = *PeelCount;
333  return;
334  }
335  LLVM_DEBUG(dbgs() << "Requested peel count: " << *PeelCount << "\n");
336  LLVM_DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n");
337  LLVM_DEBUG(dbgs() << "Peel cost: " << LoopSize * (*PeelCount + 1)
338  << "\n");
339  LLVM_DEBUG(dbgs() << "Max peel cost: " << UP.Threshold << "\n");
340  }
341  }
342 }
343 
344 /// Update the branch weights of the latch of a peeled-off loop
345 /// iteration.
346 /// This sets the branch weights for the latch of the recently peeled off loop
347 /// iteration correctly.
348 /// Our goal is to make sure that:
349 /// a) The total weight of all the copies of the loop body is preserved.
350 /// b) The total weight of the loop exit is preserved.
351 /// c) The body weight is reasonably distributed between the peeled iterations.
352 ///
353 /// \param Header The copy of the header block that belongs to next iteration.
354 /// \param LatchBR The copy of the latch branch that belongs to this iteration.
355 /// \param IterNumber The serial number of the iteration that was just
356 /// peeled off.
357 /// \param AvgIters The average number of iterations we expect the loop to have.
358 /// \param[in,out] PeeledHeaderWeight The total number of dynamic loop
359 /// iterations that are unaccounted for. As an input, it represents the number
360 /// of times we expect to enter the header of the iteration currently being
361 /// peeled off. The output is the number of times we expect to enter the
362 /// header of the next iteration.
363 static void updateBranchWeights(BasicBlock *Header, BranchInst *LatchBR,
364  unsigned IterNumber, unsigned AvgIters,
365  uint64_t &PeeledHeaderWeight) {
366  // FIXME: Pick a more realistic distribution.
367  // Currently the proportion of weight we assign to the fall-through
368  // side of the branch drops linearly with the iteration number, and we use
369  // a 0.9 fudge factor to make the drop-off less sharp...
370  if (PeeledHeaderWeight) {
371  uint64_t FallThruWeight =
372  PeeledHeaderWeight * ((float)(AvgIters - IterNumber) / AvgIters * 0.9);
373  uint64_t ExitWeight = PeeledHeaderWeight - FallThruWeight;
374  PeeledHeaderWeight -= ExitWeight;
375 
376  unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
377  MDBuilder MDB(LatchBR->getContext());
378  MDNode *WeightNode =
379  HeaderIdx ? MDB.createBranchWeights(ExitWeight, FallThruWeight)
380  : MDB.createBranchWeights(FallThruWeight, ExitWeight);
381  LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
382  }
383 }
384 
385 /// Clones the body of the loop L, putting it between \p InsertTop and \p
386 /// InsertBot.
387 /// \param IterNumber The serial number of the iteration currently being
388 /// peeled off.
389 /// \param Exit The exit block of the original loop.
390 /// \param[out] NewBlocks A list of the blocks in the newly created clone
391 /// \param[out] VMap The value map between the loop and the new clone.
392 /// \param LoopBlocks A helper for DFS-traversal of the loop.
393 /// \param LVMap A value-map that maps instructions from the original loop to
394 /// instructions in the last peeled-off iteration.
395 static void cloneLoopBlocks(Loop *L, unsigned IterNumber, BasicBlock *InsertTop,
396  BasicBlock *InsertBot, BasicBlock *Exit,
398  LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap,
399  ValueToValueMapTy &LVMap, DominatorTree *DT,
400  LoopInfo *LI) {
401  BasicBlock *Header = L->getHeader();
402  BasicBlock *Latch = L->getLoopLatch();
403  BasicBlock *PreHeader = L->getLoopPreheader();
404 
405  Function *F = Header->getParent();
406  LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
407  LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
408  Loop *ParentLoop = L->getParentLoop();
409 
410  // For each block in the original loop, create a new copy,
411  // and update the value map with the newly created values.
412  for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
413  BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".peel", F);
414  NewBlocks.push_back(NewBB);
415 
416  if (ParentLoop)
417  ParentLoop->addBasicBlockToLoop(NewBB, *LI);
418 
419  VMap[*BB] = NewBB;
420 
421  // If dominator tree is available, insert nodes to represent cloned blocks.
422  if (DT) {
423  if (Header == *BB)
424  DT->addNewBlock(NewBB, InsertTop);
425  else {
426  DomTreeNode *IDom = DT->getNode(*BB)->getIDom();
427  // VMap must contain entry for IDom, as the iteration order is RPO.
428  DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDom->getBlock()]));
429  }
430  }
431  }
432 
433  // Hook-up the control flow for the newly inserted blocks.
434  // The new header is hooked up directly to the "top", which is either
435  // the original loop preheader (for the first iteration) or the previous
436  // iteration's exiting block (for every other iteration)
437  InsertTop->getTerminator()->setSuccessor(0, cast<BasicBlock>(VMap[Header]));
438 
439  // Similarly, for the latch:
440  // The original exiting edge is still hooked up to the loop exit.
441  // The backedge now goes to the "bottom", which is either the loop's real
442  // header (for the last peeled iteration) or the copied header of the next
443  // iteration (for every other iteration)
444  BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
445  BranchInst *LatchBR = cast<BranchInst>(NewLatch->getTerminator());
446  unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
447  LatchBR->setSuccessor(HeaderIdx, InsertBot);
448  LatchBR->setSuccessor(1 - HeaderIdx, Exit);
449  if (DT)
450  DT->changeImmediateDominator(InsertBot, NewLatch);
451 
452  // The new copy of the loop body starts with a bunch of PHI nodes
453  // that pick an incoming value from either the preheader, or the previous
454  // loop iteration. Since this copy is no longer part of the loop, we
455  // resolve this statically:
456  // For the first iteration, we use the value from the preheader directly.
457  // For any other iteration, we replace the phi with the value generated by
458  // the immediately preceding clone of the loop body (which represents
459  // the previous iteration).
460  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
461  PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
462  if (IterNumber == 0) {
463  VMap[&*I] = NewPHI->getIncomingValueForBlock(PreHeader);
464  } else {
465  Value *LatchVal = NewPHI->getIncomingValueForBlock(Latch);
466  Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
467  if (LatchInst && L->contains(LatchInst))
468  VMap[&*I] = LVMap[LatchInst];
469  else
470  VMap[&*I] = LatchVal;
471  }
472  cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
473  }
474 
475  // Fix up the outgoing values - we need to add a value for the iteration
476  // we've just created. Note that this must happen *after* the incoming
477  // values are adjusted, since the value going out of the latch may also be
478  // a value coming into the header.
479  for (BasicBlock::iterator I = Exit->begin(); isa<PHINode>(I); ++I) {
480  PHINode *PHI = cast<PHINode>(I);
481  Value *LatchVal = PHI->getIncomingValueForBlock(Latch);
482  Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
483  if (LatchInst && L->contains(LatchInst))
484  LatchVal = VMap[LatchVal];
485  PHI->addIncoming(LatchVal, cast<BasicBlock>(VMap[Latch]));
486  }
487 
488  // LastValueMap is updated with the values for the current loop
489  // which are used the next time this function is called.
490  for (const auto &KV : VMap)
491  LVMap[KV.first] = KV.second;
492 }
493 
494 /// Peel off the first \p PeelCount iterations of loop \p L.
495 ///
496 /// Note that this does not peel them off as a single straight-line block.
497 /// Rather, each iteration is peeled off separately, and needs to check the
498 /// exit condition.
499 /// For loops that dynamically execute \p PeelCount iterations or less
500 /// this provides a benefit, since the peeled off iterations, which account
501 /// for the bulk of dynamic execution, can be further simplified by scalar
502 /// optimizations.
503 bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
505  AssumptionCache *AC, bool PreserveLCSSA) {
506  assert(PeelCount > 0 && "Attempt to peel out zero iterations?");
507  assert(canPeel(L) && "Attempt to peel a loop which is not peelable?");
508 
509  LoopBlocksDFS LoopBlocks(L);
510  LoopBlocks.perform(LI);
511 
512  BasicBlock *Header = L->getHeader();
513  BasicBlock *PreHeader = L->getLoopPreheader();
514  BasicBlock *Latch = L->getLoopLatch();
515  BasicBlock *Exit = L->getUniqueExitBlock();
516 
517  Function *F = Header->getParent();
518 
519  // Set up all the necessary basic blocks. It is convenient to split the
520  // preheader into 3 parts - two blocks to anchor the peeled copy of the loop
521  // body, and a new preheader for the "real" loop.
522 
523  // Peeling the first iteration transforms.
524  //
525  // PreHeader:
526  // ...
527  // Header:
528  // LoopBody
529  // If (cond) goto Header
530  // Exit:
531  //
532  // into
533  //
534  // InsertTop:
535  // LoopBody
536  // If (!cond) goto Exit
537  // InsertBot:
538  // NewPreHeader:
539  // ...
540  // Header:
541  // LoopBody
542  // If (cond) goto Header
543  // Exit:
544  //
545  // Each following iteration will split the current bottom anchor in two,
546  // and put the new copy of the loop body between these two blocks. That is,
547  // after peeling another iteration from the example above, we'll split
548  // InsertBot, and get:
549  //
550  // InsertTop:
551  // LoopBody
552  // If (!cond) goto Exit
553  // InsertBot:
554  // LoopBody
555  // If (!cond) goto Exit
556  // InsertBot.next:
557  // NewPreHeader:
558  // ...
559  // Header:
560  // LoopBody
561  // If (cond) goto Header
562  // Exit:
563 
564  BasicBlock *InsertTop = SplitEdge(PreHeader, Header, DT, LI);
565  BasicBlock *InsertBot =
566  SplitBlock(InsertTop, InsertTop->getTerminator(), DT, LI);
567  BasicBlock *NewPreHeader =
568  SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI);
569 
570  InsertTop->setName(Header->getName() + ".peel.begin");
571  InsertBot->setName(Header->getName() + ".peel.next");
572  NewPreHeader->setName(PreHeader->getName() + ".peel.newph");
573 
574  ValueToValueMapTy LVMap;
575 
576  // If we have branch weight information, we'll want to update it for the
577  // newly created branches.
578  BranchInst *LatchBR =
579  cast<BranchInst>(cast<BasicBlock>(Latch)->getTerminator());
580  unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
581 
582  uint64_t TrueWeight, FalseWeight;
583  uint64_t ExitWeight = 0, CurHeaderWeight = 0;
584  if (LatchBR->extractProfMetadata(TrueWeight, FalseWeight)) {
585  ExitWeight = HeaderIdx ? TrueWeight : FalseWeight;
586  // The # of times the loop body executes is the sum of the exit block
587  // weight and the # of times the backedges are taken.
588  CurHeaderWeight = TrueWeight + FalseWeight;
589  }
590 
591  // For each peeled-off iteration, make a copy of the loop.
592  for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
594  ValueToValueMapTy VMap;
595 
596  // Subtract the exit weight from the current header weight -- the exit
597  // weight is exactly the weight of the previous iteration's header.
598  // FIXME: due to the way the distribution is constructed, we need a
599  // guard here to make sure we don't end up with non-positive weights.
600  if (ExitWeight < CurHeaderWeight)
601  CurHeaderWeight -= ExitWeight;
602  else
603  CurHeaderWeight = 1;
604 
605  cloneLoopBlocks(L, Iter, InsertTop, InsertBot, Exit,
606  NewBlocks, LoopBlocks, VMap, LVMap, DT, LI);
607 
608  // Remap to use values from the current iteration instead of the
609  // previous one.
610  remapInstructionsInBlocks(NewBlocks, VMap);
611 
612  if (DT) {
613  // Latches of the cloned loops dominate over the loop exit, so idom of the
614  // latter is the first cloned loop body, as original PreHeader dominates
615  // the original loop body.
616  if (Iter == 0)
617  DT->changeImmediateDominator(Exit, cast<BasicBlock>(LVMap[Latch]));
619  }
620 
621  updateBranchWeights(InsertBot, cast<BranchInst>(VMap[LatchBR]), Iter,
622  PeelCount, ExitWeight);
623 
624  InsertTop = InsertBot;
625  InsertBot = SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI);
626  InsertBot->setName(Header->getName() + ".peel.next");
627 
628  F->getBasicBlockList().splice(InsertTop->getIterator(),
629  F->getBasicBlockList(),
630  NewBlocks[0]->getIterator(), F->end());
631  }
632 
633  // Now adjust the phi nodes in the loop header to get their initial values
634  // from the last peeled-off iteration instead of the preheader.
635  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
636  PHINode *PHI = cast<PHINode>(I);
637  Value *NewVal = PHI->getIncomingValueForBlock(Latch);
638  Instruction *LatchInst = dyn_cast<Instruction>(NewVal);
639  if (LatchInst && L->contains(LatchInst))
640  NewVal = LVMap[LatchInst];
641 
642  PHI->setIncomingValue(PHI->getBasicBlockIndex(NewPreHeader), NewVal);
643  }
644 
645  // Adjust the branch weights on the loop exit.
646  if (ExitWeight) {
647  // The backedge count is the difference of current header weight and
648  // current loop exit weight. If the current header weight is smaller than
649  // the current loop exit weight, we mark the loop backedge weight as 1.
650  uint64_t BackEdgeWeight = 0;
651  if (ExitWeight < CurHeaderWeight)
652  BackEdgeWeight = CurHeaderWeight - ExitWeight;
653  else
654  BackEdgeWeight = 1;
655  MDBuilder MDB(LatchBR->getContext());
656  MDNode *WeightNode =
657  HeaderIdx ? MDB.createBranchWeights(ExitWeight, BackEdgeWeight)
658  : MDB.createBranchWeights(BackEdgeWeight, ExitWeight);
659  LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
660  }
661 
662  // If the loop is nested, we changed the parent loop, update SE.
663  if (Loop *ParentLoop = L->getParentLoop()) {
664  SE->forgetLoop(ParentLoop);
665 
666  // FIXME: Incrementally update loop-simplify
667  simplifyLoop(ParentLoop, DT, LI, SE, AC, PreserveLCSSA);
668  } else {
669  // FIXME: Incrementally update loop-simplify
670  simplifyLoop(L, DT, LI, SE, AC, PreserveLCSSA);
671  }
672 
673  NumPeeled++;
674 
675  return true;
676 }
void push_back(const T &Elt)
Definition: SmallVector.h:213
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:157
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
const SCEV * getConstant(ConstantInt *V)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
iterator end()
Definition: Function.h:644
The main scalar evolution driver.
This file contains the declarations for metadata subclasses.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:106
A cache of @llvm.assume calls within a function.
BasicBlock * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfo.cpp:436
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:713
BasicBlock * getSuccessor(unsigned i) const
bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, bool &Increasing)
Return true if, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or...
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:862
F(f)
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
static unsigned calculateIterationsToInvariance(PHINode *Phi, Loop *L, BasicBlock *BackEdge, SmallDenseMap< PHINode *, unsigned > &IterationsToInvariance)
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
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."))
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:983
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
static void updateBranchWeights(BasicBlock *Header, BranchInst *LatchBR, unsigned IterNumber, unsigned AvgIters, uint64_t &PeeledHeaderWeight)
Update the branch weights of the latch of a peeled-off loop iteration.
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
bool AllowPeeling
Allow peeling off loop iterations for loops with low dynamic tripcount.
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:295
RPOIterator endRPO() const
Definition: LoopIterator.h:141
BlockT * getHeader() const
Definition: LoopInfo.h:100
void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::UnrollingPreferences &UP, unsigned &TripCount, ScalarEvolution &SE)
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:183
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:827
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
NodeT * getBlock() const
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
void setSuccessor(unsigned idx, BasicBlock *B)
Update the specified successor to point at the provided block.
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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&#39;s...
static cl::opt< unsigned > UnrollForcePeelCount("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))
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.
static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE)
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.
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:329
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:885
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:102
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:82
Optional< unsigned > getLoopEstimatedTripCount(Loop *L)
Get a loop&#39;s estimated trip count based on branch weight metadata.
Definition: LoopUtils.cpp:1489
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:1226
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:57
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
Iterator for intrusive lists based on ilist_node.
Type * getType() const
Return the LLVM type of this SCEV expression.
static const unsigned InfiniteIterationsToInvariance
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
static void cloneLoopBlocks(Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot, BasicBlock *Exit, 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.
bool canPeel(Loop *L)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
Store the result of a depth first search within basic blocks contained by a single loop...
Definition: LoopIterator.h:98
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
CloneBasicBlock - Return a copy of the specified basic block, but without embedding the block into a ...
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:43
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:192
unsigned PeelCount
A forced peeling factor (the number of bodied of the original loop that should be peeled off before t...
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
unsigned Threshold
The cost threshold for the unrolled loop.
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:445
Parameters that control the generic loop unrolling transformation.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:619
bool empty() const
Definition: LoopInfo.h:146
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
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:137
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the edge connecting specified block.
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:999
This pass exposes codegen information to IR-level passes.
const TerminatorInst * 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:138
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:119
bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) const
Retrieve the raw weight values of a conditional branch or select.
Definition: Metadata.cpp:1315
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:50
bool hasProfileData() const
Return true if the function is annotated with profile data.
Definition: Function.h:294
const BasicBlock * getParent() const
Definition: Instruction.h:67
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:974
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock *> &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.