xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Utils/LoopPeel.cpp (revision 370e009188ba90c3290b1479aa06ec98b66e140a)
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 
12 #include "llvm/Transforms/Utils/LoopPeel.h"
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/Loads.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Analysis/LoopIterator.h"
20 #include "llvm/Analysis/ScalarEvolution.h"
21 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
22 #include "llvm/Analysis/TargetTransformInfo.h"
23 #include "llvm/IR/BasicBlock.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/Function.h"
26 #include "llvm/IR/InstrTypes.h"
27 #include "llvm/IR/Instruction.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/LLVMContext.h"
30 #include "llvm/IR/MDBuilder.h"
31 #include "llvm/IR/PatternMatch.h"
32 #include "llvm/Support/Casting.h"
33 #include "llvm/Support/CommandLine.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/raw_ostream.h"
36 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
37 #include "llvm/Transforms/Utils/Cloning.h"
38 #include "llvm/Transforms/Utils/LoopSimplify.h"
39 #include "llvm/Transforms/Utils/LoopUtils.h"
40 #include "llvm/Transforms/Utils/ValueMapper.h"
41 #include <algorithm>
42 #include <cassert>
43 #include <cstdint>
44 
45 using namespace llvm;
46 using namespace llvm::PatternMatch;
47 
48 #define DEBUG_TYPE "loop-peel"
49 
50 STATISTIC(NumPeeled, "Number of loops peeled");
51 
52 static cl::opt<unsigned> UnrollPeelCount(
53     "unroll-peel-count", cl::Hidden,
54     cl::desc("Set the unroll peeling count, for testing purposes"));
55 
56 static cl::opt<bool>
57     UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden,
58                        cl::desc("Allows loops to be peeled when the dynamic "
59                                 "trip count is known to be low."));
60 
61 static cl::opt<bool>
62     UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling",
63                                 cl::init(false), cl::Hidden,
64                                 cl::desc("Allows loop nests to be peeled."));
65 
66 static cl::opt<unsigned> UnrollPeelMaxCount(
67     "unroll-peel-max-count", cl::init(7), cl::Hidden,
68     cl::desc("Max average trip count which will cause loop peeling."));
69 
70 static cl::opt<unsigned> UnrollForcePeelCount(
71     "unroll-force-peel-count", cl::init(0), cl::Hidden,
72     cl::desc("Force a peel count regardless of profiling information."));
73 
74 static const char *PeeledCountMetaData = "llvm.loop.peeled.count";
75 
76 // Check whether we are capable of peeling this loop.
77 bool llvm::canPeel(Loop *L) {
78   // Make sure the loop is in simplified form
79   if (!L->isLoopSimplifyForm())
80     return false;
81 
82   // Don't try to peel loops where the latch is not the exiting block.
83   // This can be an indication of two different things:
84   // 1) The loop is not rotated.
85   // 2) The loop contains irreducible control flow that involves the latch.
86   const BasicBlock *Latch = L->getLoopLatch();
87   if (!L->isLoopExiting(Latch))
88     return false;
89 
90   // Peeling is only supported if the latch is a branch.
91   if (!isa<BranchInst>(Latch->getTerminator()))
92     return false;
93 
94   SmallVector<BasicBlock *, 4> Exits;
95   L->getUniqueNonLatchExitBlocks(Exits);
96   // The latch must either be the only exiting block or all non-latch exit
97   // blocks have either a deopt or unreachable terminator or compose a chain of
98   // blocks where the last one is either deopt or unreachable terminated. Both
99   // deopt and unreachable terminators are a strong indication they are not
100   // taken. Note that this is a profitability check, not a legality check. Also
101   // note that LoopPeeling currently can only update the branch weights of latch
102   // blocks and branch weights to blocks with deopt or unreachable do not need
103   // updating.
104   return llvm::all_of(Exits, IsBlockFollowedByDeoptOrUnreachable);
105 }
106 
107 // This function calculates the number of iterations after which the given Phi
108 // becomes an invariant. The pre-calculated values are memorized in the map. The
109 // function (shortcut is I) is calculated according to the following definition:
110 // Given %x = phi <Inputs from above the loop>, ..., [%y, %back.edge].
111 //   If %y is a loop invariant, then I(%x) = 1.
112 //   If %y is a Phi from the loop header, I(%x) = I(%y) + 1.
113 //   Otherwise, I(%x) is infinite.
114 // TODO: Actually if %y is an expression that depends only on Phi %z and some
115 //       loop invariants, we can estimate I(%x) = I(%z) + 1. The example
116 //       looks like:
117 //         %x = phi(0, %a),  <-- becomes invariant starting from 3rd iteration.
118 //         %y = phi(0, 5),
119 //         %a = %y + 1.
120 static Optional<unsigned> calculateIterationsToInvariance(
121     PHINode *Phi, Loop *L, BasicBlock *BackEdge,
122     SmallDenseMap<PHINode *, Optional<unsigned> > &IterationsToInvariance) {
123   assert(Phi->getParent() == L->getHeader() &&
124          "Non-loop Phi should not be checked for turning into invariant.");
125   assert(BackEdge == L->getLoopLatch() && "Wrong latch?");
126   // If we already know the answer, take it from the map.
127   auto I = IterationsToInvariance.find(Phi);
128   if (I != IterationsToInvariance.end())
129     return I->second;
130 
131   // Otherwise we need to analyze the input from the back edge.
132   Value *Input = Phi->getIncomingValueForBlock(BackEdge);
133   // Place infinity to map to avoid infinite recursion for cycled Phis. Such
134   // cycles can never stop on an invariant.
135   IterationsToInvariance[Phi] = None;
136   Optional<unsigned> ToInvariance = None;
137 
138   if (L->isLoopInvariant(Input))
139     ToInvariance = 1u;
140   else if (PHINode *IncPhi = dyn_cast<PHINode>(Input)) {
141     // Only consider Phis in header block.
142     if (IncPhi->getParent() != L->getHeader())
143       return None;
144     // If the input becomes an invariant after X iterations, then our Phi
145     // becomes an invariant after X + 1 iterations.
146     auto InputToInvariance = calculateIterationsToInvariance(
147         IncPhi, L, BackEdge, IterationsToInvariance);
148     if (InputToInvariance)
149       ToInvariance = *InputToInvariance + 1u;
150   }
151 
152   // If we found that this Phi lies in an invariant chain, update the map.
153   if (ToInvariance)
154     IterationsToInvariance[Phi] = ToInvariance;
155   return ToInvariance;
156 }
157 
158 // Try to find any invariant memory reads that will become dereferenceable in
159 // the remainder loop after peeling. The load must also be used (transitively)
160 // by an exit condition. Returns the number of iterations to peel off (at the
161 // moment either 0 or 1).
162 static unsigned peelToTurnInvariantLoadsDerefencebale(Loop &L,
163                                                       DominatorTree &DT) {
164   // Skip loops with a single exiting block, because there should be no benefit
165   // for the heuristic below.
166   if (L.getExitingBlock())
167     return 0;
168 
169   // All non-latch exit blocks must have an UnreachableInst terminator.
170   // Otherwise the heuristic below may not be profitable.
171   SmallVector<BasicBlock *, 4> Exits;
172   L.getUniqueNonLatchExitBlocks(Exits);
173   if (any_of(Exits, [](const BasicBlock *BB) {
174         return !isa<UnreachableInst>(BB->getTerminator());
175       }))
176     return 0;
177 
178   // Now look for invariant loads that dominate the latch and are not known to
179   // be dereferenceable. If there are such loads and no writes, they will become
180   // dereferenceable in the loop if the first iteration is peeled off. Also
181   // collect the set of instructions controlled by such loads. Only peel if an
182   // exit condition uses (transitively) such a load.
183   BasicBlock *Header = L.getHeader();
184   BasicBlock *Latch = L.getLoopLatch();
185   SmallPtrSet<Value *, 8> LoadUsers;
186   const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
187   for (BasicBlock *BB : L.blocks()) {
188     for (Instruction &I : *BB) {
189       if (I.mayWriteToMemory())
190         return 0;
191 
192       auto Iter = LoadUsers.find(&I);
193       if (Iter != LoadUsers.end()) {
194         for (Value *U : I.users())
195           LoadUsers.insert(U);
196       }
197       // Do not look for reads in the header; they can already be hoisted
198       // without peeling.
199       if (BB == Header)
200         continue;
201       if (auto *LI = dyn_cast<LoadInst>(&I)) {
202         Value *Ptr = LI->getPointerOperand();
203         if (DT.dominates(BB, Latch) && L.isLoopInvariant(Ptr) &&
204             !isDereferenceablePointer(Ptr, LI->getType(), DL, LI, &DT))
205           for (Value *U : I.users())
206             LoadUsers.insert(U);
207       }
208     }
209   }
210   SmallVector<BasicBlock *> ExitingBlocks;
211   L.getExitingBlocks(ExitingBlocks);
212   if (any_of(ExitingBlocks, [&LoadUsers](BasicBlock *Exiting) {
213         return LoadUsers.contains(Exiting->getTerminator());
214       }))
215     return 1;
216   return 0;
217 }
218 
219 // Return the number of iterations to peel off that make conditions in the
220 // body true/false. For example, if we peel 2 iterations off the loop below,
221 // the condition i < 2 can be evaluated at compile time.
222 //  for (i = 0; i < n; i++)
223 //    if (i < 2)
224 //      ..
225 //    else
226 //      ..
227 //   }
228 static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount,
229                                          ScalarEvolution &SE) {
230   assert(L.isLoopSimplifyForm() && "Loop needs to be in loop simplify form");
231   unsigned DesiredPeelCount = 0;
232 
233   for (auto *BB : L.blocks()) {
234     auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
235     if (!BI || BI->isUnconditional())
236       continue;
237 
238     // Ignore loop exit condition.
239     if (L.getLoopLatch() == BB)
240       continue;
241 
242     Value *Condition = BI->getCondition();
243     Value *LeftVal, *RightVal;
244     CmpInst::Predicate Pred;
245     if (!match(Condition, m_ICmp(Pred, m_Value(LeftVal), m_Value(RightVal))))
246       continue;
247 
248     const SCEV *LeftSCEV = SE.getSCEV(LeftVal);
249     const SCEV *RightSCEV = SE.getSCEV(RightVal);
250 
251     // Do not consider predicates that are known to be true or false
252     // independently of the loop iteration.
253     if (SE.evaluatePredicate(Pred, LeftSCEV, RightSCEV))
254       continue;
255 
256     // Check if we have a condition with one AddRec and one non AddRec
257     // expression. Normalize LeftSCEV to be the AddRec.
258     if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
259       if (isa<SCEVAddRecExpr>(RightSCEV)) {
260         std::swap(LeftSCEV, RightSCEV);
261         Pred = ICmpInst::getSwappedPredicate(Pred);
262       } else
263         continue;
264     }
265 
266     const SCEVAddRecExpr *LeftAR = cast<SCEVAddRecExpr>(LeftSCEV);
267 
268     // Avoid huge SCEV computations in the loop below, make sure we only
269     // consider AddRecs of the loop we are trying to peel.
270     if (!LeftAR->isAffine() || LeftAR->getLoop() != &L)
271       continue;
272     if (!(ICmpInst::isEquality(Pred) && LeftAR->hasNoSelfWrap()) &&
273         !SE.getMonotonicPredicateType(LeftAR, Pred))
274       continue;
275 
276     // Check if extending the current DesiredPeelCount lets us evaluate Pred
277     // or !Pred in the loop body statically.
278     unsigned NewPeelCount = DesiredPeelCount;
279 
280     const SCEV *IterVal = LeftAR->evaluateAtIteration(
281         SE.getConstant(LeftSCEV->getType(), NewPeelCount), SE);
282 
283     // If the original condition is not known, get the negated predicate
284     // (which holds on the else branch) and check if it is known. This allows
285     // us to peel of iterations that make the original condition false.
286     if (!SE.isKnownPredicate(Pred, IterVal, RightSCEV))
287       Pred = ICmpInst::getInversePredicate(Pred);
288 
289     const SCEV *Step = LeftAR->getStepRecurrence(SE);
290     const SCEV *NextIterVal = SE.getAddExpr(IterVal, Step);
291     auto PeelOneMoreIteration = [&IterVal, &NextIterVal, &SE, Step,
292                                  &NewPeelCount]() {
293       IterVal = NextIterVal;
294       NextIterVal = SE.getAddExpr(IterVal, Step);
295       NewPeelCount++;
296     };
297 
298     auto CanPeelOneMoreIteration = [&NewPeelCount, &MaxPeelCount]() {
299       return NewPeelCount < MaxPeelCount;
300     };
301 
302     while (CanPeelOneMoreIteration() &&
303            SE.isKnownPredicate(Pred, IterVal, RightSCEV))
304       PeelOneMoreIteration();
305 
306     // With *that* peel count, does the predicate !Pred become known in the
307     // first iteration of the loop body after peeling?
308     if (!SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), IterVal,
309                              RightSCEV))
310       continue; // If not, give up.
311 
312     // However, for equality comparisons, that isn't always sufficient to
313     // eliminate the comparsion in loop body, we may need to peel one more
314     // iteration. See if that makes !Pred become unknown again.
315     if (ICmpInst::isEquality(Pred) &&
316         !SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), NextIterVal,
317                              RightSCEV) &&
318         !SE.isKnownPredicate(Pred, IterVal, RightSCEV) &&
319         SE.isKnownPredicate(Pred, NextIterVal, RightSCEV)) {
320       if (!CanPeelOneMoreIteration())
321         continue; // Need to peel one more iteration, but can't. Give up.
322       PeelOneMoreIteration(); // Great!
323     }
324 
325     DesiredPeelCount = std::max(DesiredPeelCount, NewPeelCount);
326   }
327 
328   return DesiredPeelCount;
329 }
330 
331 /// This "heuristic" exactly matches implicit behavior which used to exist
332 /// inside getLoopEstimatedTripCount.  It was added here to keep an
333 /// improvement inside that API from causing peeling to become more agressive.
334 /// This should probably be removed.
335 static bool violatesLegacyMultiExitLoopCheck(Loop *L) {
336   BasicBlock *Latch = L->getLoopLatch();
337   if (!Latch)
338     return true;
339 
340   BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
341   if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
342     return true;
343 
344   assert((LatchBR->getSuccessor(0) == L->getHeader() ||
345           LatchBR->getSuccessor(1) == L->getHeader()) &&
346          "At least one edge out of the latch must go to the header");
347 
348   SmallVector<BasicBlock *, 4> ExitBlocks;
349   L->getUniqueNonLatchExitBlocks(ExitBlocks);
350   return any_of(ExitBlocks, [](const BasicBlock *EB) {
351       return !EB->getTerminatingDeoptimizeCall();
352     });
353 }
354 
355 
356 // Return the number of iterations we want to peel off.
357 void llvm::computePeelCount(Loop *L, unsigned LoopSize,
358                             TargetTransformInfo::PeelingPreferences &PP,
359                             unsigned TripCount, DominatorTree &DT,
360                             ScalarEvolution &SE, unsigned Threshold) {
361   assert(LoopSize > 0 && "Zero loop size is not allowed!");
362   // Save the PP.PeelCount value set by the target in
363   // TTI.getPeelingPreferences or by the flag -unroll-peel-count.
364   unsigned TargetPeelCount = PP.PeelCount;
365   PP.PeelCount = 0;
366   if (!canPeel(L))
367     return;
368 
369   // Only try to peel innermost loops by default.
370   // The constraint can be relaxed by the target in TTI.getPeelingPreferences
371   // or by the flag -unroll-allow-loop-nests-peeling.
372   if (!PP.AllowLoopNestsPeeling && !L->isInnermost())
373     return;
374 
375   // If the user provided a peel count, use that.
376   bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0;
377   if (UserPeelCount) {
378     LLVM_DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount
379                       << " iterations.\n");
380     PP.PeelCount = UnrollForcePeelCount;
381     PP.PeelProfiledIterations = true;
382     return;
383   }
384 
385   // Skip peeling if it's disabled.
386   if (!PP.AllowPeeling)
387     return;
388 
389   // Check that we can peel at least one iteration.
390   if (2 * LoopSize > Threshold)
391     return;
392 
393   unsigned AlreadyPeeled = 0;
394   if (auto Peeled = getOptionalIntLoopAttribute(L, PeeledCountMetaData))
395     AlreadyPeeled = *Peeled;
396   // Stop if we already peeled off the maximum number of iterations.
397   if (AlreadyPeeled >= UnrollPeelMaxCount)
398     return;
399 
400   // Here we try to get rid of Phis which become invariants after 1, 2, ..., N
401   // iterations of the loop. For this we compute the number for iterations after
402   // which every Phi is guaranteed to become an invariant, and try to peel the
403   // maximum number of iterations among these values, thus turning all those
404   // Phis into invariants.
405 
406   // Store the pre-calculated values here.
407   SmallDenseMap<PHINode *, Optional<unsigned>> IterationsToInvariance;
408   // Now go through all Phis to calculate their the number of iterations they
409   // need to become invariants.
410   // Start the max computation with the PP.PeelCount value set by the target
411   // in TTI.getPeelingPreferences or by the flag -unroll-peel-count.
412   unsigned DesiredPeelCount = TargetPeelCount;
413   BasicBlock *BackEdge = L->getLoopLatch();
414   assert(BackEdge && "Loop is not in simplified form?");
415   for (auto BI = L->getHeader()->begin(); isa<PHINode>(&*BI); ++BI) {
416     PHINode *Phi = cast<PHINode>(&*BI);
417     auto ToInvariance = calculateIterationsToInvariance(Phi, L, BackEdge,
418                                                         IterationsToInvariance);
419     if (ToInvariance)
420       DesiredPeelCount = std::max(DesiredPeelCount, *ToInvariance);
421   }
422 
423   // Pay respect to limitations implied by loop size and the max peel count.
424   unsigned MaxPeelCount = UnrollPeelMaxCount;
425   MaxPeelCount = std::min(MaxPeelCount, Threshold / LoopSize - 1);
426 
427   DesiredPeelCount = std::max(DesiredPeelCount,
428                               countToEliminateCompares(*L, MaxPeelCount, SE));
429 
430   if (DesiredPeelCount == 0)
431     DesiredPeelCount = peelToTurnInvariantLoadsDerefencebale(*L, DT);
432 
433   if (DesiredPeelCount > 0) {
434     DesiredPeelCount = std::min(DesiredPeelCount, MaxPeelCount);
435     // Consider max peel count limitation.
436     assert(DesiredPeelCount > 0 && "Wrong loop size estimation?");
437     if (DesiredPeelCount + AlreadyPeeled <= UnrollPeelMaxCount) {
438       LLVM_DEBUG(dbgs() << "Peel " << DesiredPeelCount
439                         << " iteration(s) to turn"
440                         << " some Phis into invariants.\n");
441       PP.PeelCount = DesiredPeelCount;
442       PP.PeelProfiledIterations = false;
443       return;
444     }
445   }
446 
447   // Bail if we know the statically calculated trip count.
448   // In this case we rather prefer partial unrolling.
449   if (TripCount)
450     return;
451 
452   // Do not apply profile base peeling if it is disabled.
453   if (!PP.PeelProfiledIterations)
454     return;
455   // If we don't know the trip count, but have reason to believe the average
456   // trip count is low, peeling should be beneficial, since we will usually
457   // hit the peeled section.
458   // We only do this in the presence of profile information, since otherwise
459   // our estimates of the trip count are not reliable enough.
460   if (L->getHeader()->getParent()->hasProfileData()) {
461     if (violatesLegacyMultiExitLoopCheck(L))
462       return;
463     Optional<unsigned> EstimatedTripCount = getLoopEstimatedTripCount(L);
464     if (!EstimatedTripCount)
465       return;
466 
467     LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is "
468                       << *EstimatedTripCount << "\n");
469 
470     if (*EstimatedTripCount) {
471       if (*EstimatedTripCount + AlreadyPeeled <= MaxPeelCount) {
472         unsigned PeelCount = *EstimatedTripCount;
473         LLVM_DEBUG(dbgs() << "Peeling first " << PeelCount << " iterations.\n");
474         PP.PeelCount = PeelCount;
475         return;
476       }
477       LLVM_DEBUG(dbgs() << "Already peel count: " << AlreadyPeeled << "\n");
478       LLVM_DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n");
479       LLVM_DEBUG(dbgs() << "Loop cost: " << LoopSize << "\n");
480       LLVM_DEBUG(dbgs() << "Max peel cost: " << Threshold << "\n");
481       LLVM_DEBUG(dbgs() << "Max peel count by cost: "
482                         << (Threshold / LoopSize - 1) << "\n");
483     }
484   }
485 }
486 
487 /// Update the branch weights of the latch of a peeled-off loop
488 /// iteration.
489 /// This sets the branch weights for the latch of the recently peeled off loop
490 /// iteration correctly.
491 /// Let F is a weight of the edge from latch to header.
492 /// Let E is a weight of the edge from latch to exit.
493 /// F/(F+E) is a probability to go to loop and E/(F+E) is a probability to
494 /// go to exit.
495 /// Then, Estimated TripCount = F / E.
496 /// For I-th (counting from 0) peeled off iteration we set the the weights for
497 /// the peeled latch as (TC - I, 1). It gives us reasonable distribution,
498 /// The probability to go to exit 1/(TC-I) increases. At the same time
499 /// the estimated trip count of remaining loop reduces by I.
500 /// To avoid dealing with division rounding we can just multiple both part
501 /// of weights to E and use weight as (F - I * E, E).
502 ///
503 /// \param Header The copy of the header block that belongs to next iteration.
504 /// \param LatchBR The copy of the latch branch that belongs to this iteration.
505 /// \param[in,out] FallThroughWeight The weight of the edge from latch to
506 /// header before peeling (in) and after peeled off one iteration (out).
507 static void updateBranchWeights(BasicBlock *Header, BranchInst *LatchBR,
508                                 uint64_t ExitWeight,
509                                 uint64_t &FallThroughWeight) {
510   // FallThroughWeight is 0 means that there is no branch weights on original
511   // latch block or estimated trip count is zero.
512   if (!FallThroughWeight)
513     return;
514 
515   unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
516   MDBuilder MDB(LatchBR->getContext());
517   MDNode *WeightNode =
518       HeaderIdx ? MDB.createBranchWeights(ExitWeight, FallThroughWeight)
519                 : MDB.createBranchWeights(FallThroughWeight, ExitWeight);
520   LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
521   FallThroughWeight =
522       FallThroughWeight > ExitWeight ? FallThroughWeight - ExitWeight : 1;
523 }
524 
525 /// Initialize the weights.
526 ///
527 /// \param Header The header block.
528 /// \param LatchBR The latch branch.
529 /// \param[out] ExitWeight The weight of the edge from Latch to Exit.
530 /// \param[out] FallThroughWeight The weight of the edge from Latch to Header.
531 static void initBranchWeights(BasicBlock *Header, BranchInst *LatchBR,
532                               uint64_t &ExitWeight,
533                               uint64_t &FallThroughWeight) {
534   uint64_t TrueWeight, FalseWeight;
535   if (!LatchBR->extractProfMetadata(TrueWeight, FalseWeight))
536     return;
537   unsigned HeaderIdx = LatchBR->getSuccessor(0) == Header ? 0 : 1;
538   ExitWeight = HeaderIdx ? TrueWeight : FalseWeight;
539   FallThroughWeight = HeaderIdx ? FalseWeight : TrueWeight;
540 }
541 
542 /// Update the weights of original Latch block after peeling off all iterations.
543 ///
544 /// \param Header The header block.
545 /// \param LatchBR The latch branch.
546 /// \param ExitWeight The weight of the edge from Latch to Exit.
547 /// \param FallThroughWeight The weight of the edge from Latch to Header.
548 static void fixupBranchWeights(BasicBlock *Header, BranchInst *LatchBR,
549                                uint64_t ExitWeight,
550                                uint64_t FallThroughWeight) {
551   // FallThroughWeight is 0 means that there is no branch weights on original
552   // latch block or estimated trip count is zero.
553   if (!FallThroughWeight)
554     return;
555 
556   // Sets the branch weights on the loop exit.
557   MDBuilder MDB(LatchBR->getContext());
558   unsigned HeaderIdx = LatchBR->getSuccessor(0) == Header ? 0 : 1;
559   MDNode *WeightNode =
560       HeaderIdx ? MDB.createBranchWeights(ExitWeight, FallThroughWeight)
561                 : MDB.createBranchWeights(FallThroughWeight, ExitWeight);
562   LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
563 }
564 
565 /// Clones the body of the loop L, putting it between \p InsertTop and \p
566 /// InsertBot.
567 /// \param IterNumber The serial number of the iteration currently being
568 /// peeled off.
569 /// \param ExitEdges The exit edges of the original loop.
570 /// \param[out] NewBlocks A list of the blocks in the newly created clone
571 /// \param[out] VMap The value map between the loop and the new clone.
572 /// \param LoopBlocks A helper for DFS-traversal of the loop.
573 /// \param LVMap A value-map that maps instructions from the original loop to
574 /// instructions in the last peeled-off iteration.
575 static void cloneLoopBlocks(
576     Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot,
577     SmallVectorImpl<std::pair<BasicBlock *, BasicBlock *>> &ExitEdges,
578     SmallVectorImpl<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
579     ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT,
580     LoopInfo *LI, ArrayRef<MDNode *> LoopLocalNoAliasDeclScopes,
581     ScalarEvolution &SE) {
582   BasicBlock *Header = L->getHeader();
583   BasicBlock *Latch = L->getLoopLatch();
584   BasicBlock *PreHeader = L->getLoopPreheader();
585 
586   Function *F = Header->getParent();
587   LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
588   LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
589   Loop *ParentLoop = L->getParentLoop();
590 
591   // For each block in the original loop, create a new copy,
592   // and update the value map with the newly created values.
593   for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
594     BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".peel", F);
595     NewBlocks.push_back(NewBB);
596 
597     // If an original block is an immediate child of the loop L, its copy
598     // is a child of a ParentLoop after peeling. If a block is a child of
599     // a nested loop, it is handled in the cloneLoop() call below.
600     if (ParentLoop && LI->getLoopFor(*BB) == L)
601       ParentLoop->addBasicBlockToLoop(NewBB, *LI);
602 
603     VMap[*BB] = NewBB;
604 
605     // If dominator tree is available, insert nodes to represent cloned blocks.
606     if (DT) {
607       if (Header == *BB)
608         DT->addNewBlock(NewBB, InsertTop);
609       else {
610         DomTreeNode *IDom = DT->getNode(*BB)->getIDom();
611         // VMap must contain entry for IDom, as the iteration order is RPO.
612         DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDom->getBlock()]));
613       }
614     }
615   }
616 
617   {
618     // Identify what other metadata depends on the cloned version. After
619     // cloning, replace the metadata with the corrected version for both
620     // memory instructions and noalias intrinsics.
621     std::string Ext = (Twine("Peel") + Twine(IterNumber)).str();
622     cloneAndAdaptNoAliasScopes(LoopLocalNoAliasDeclScopes, NewBlocks,
623                                Header->getContext(), Ext);
624   }
625 
626   // Recursively create the new Loop objects for nested loops, if any,
627   // to preserve LoopInfo.
628   for (Loop *ChildLoop : *L) {
629     cloneLoop(ChildLoop, ParentLoop, VMap, LI, nullptr);
630   }
631 
632   // Hook-up the control flow for the newly inserted blocks.
633   // The new header is hooked up directly to the "top", which is either
634   // the original loop preheader (for the first iteration) or the previous
635   // iteration's exiting block (for every other iteration)
636   InsertTop->getTerminator()->setSuccessor(0, cast<BasicBlock>(VMap[Header]));
637 
638   // Similarly, for the latch:
639   // The original exiting edge is still hooked up to the loop exit.
640   // The backedge now goes to the "bottom", which is either the loop's real
641   // header (for the last peeled iteration) or the copied header of the next
642   // iteration (for every other iteration)
643   BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
644   BranchInst *LatchBR = cast<BranchInst>(NewLatch->getTerminator());
645   for (unsigned idx = 0, e = LatchBR->getNumSuccessors(); idx < e; ++idx)
646     if (LatchBR->getSuccessor(idx) == Header) {
647       LatchBR->setSuccessor(idx, InsertBot);
648       break;
649     }
650   if (DT)
651     DT->changeImmediateDominator(InsertBot, NewLatch);
652 
653   // The new copy of the loop body starts with a bunch of PHI nodes
654   // that pick an incoming value from either the preheader, or the previous
655   // loop iteration. Since this copy is no longer part of the loop, we
656   // resolve this statically:
657   // For the first iteration, we use the value from the preheader directly.
658   // For any other iteration, we replace the phi with the value generated by
659   // the immediately preceding clone of the loop body (which represents
660   // the previous iteration).
661   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
662     PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
663     if (IterNumber == 0) {
664       VMap[&*I] = NewPHI->getIncomingValueForBlock(PreHeader);
665     } else {
666       Value *LatchVal = NewPHI->getIncomingValueForBlock(Latch);
667       Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
668       if (LatchInst && L->contains(LatchInst))
669         VMap[&*I] = LVMap[LatchInst];
670       else
671         VMap[&*I] = LatchVal;
672     }
673     cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
674   }
675 
676   // Fix up the outgoing values - we need to add a value for the iteration
677   // we've just created. Note that this must happen *after* the incoming
678   // values are adjusted, since the value going out of the latch may also be
679   // a value coming into the header.
680   for (auto Edge : ExitEdges)
681     for (PHINode &PHI : Edge.second->phis()) {
682       Value *LatchVal = PHI.getIncomingValueForBlock(Edge.first);
683       Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
684       if (LatchInst && L->contains(LatchInst))
685         LatchVal = VMap[LatchVal];
686       PHI.addIncoming(LatchVal, cast<BasicBlock>(VMap[Edge.first]));
687       SE.forgetValue(&PHI);
688     }
689 
690   // LastValueMap is updated with the values for the current loop
691   // which are used the next time this function is called.
692   for (auto KV : VMap)
693     LVMap[KV.first] = KV.second;
694 }
695 
696 TargetTransformInfo::PeelingPreferences llvm::gatherPeelingPreferences(
697     Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI,
698     Optional<bool> UserAllowPeeling,
699     Optional<bool> UserAllowProfileBasedPeeling, bool UnrollingSpecficValues) {
700   TargetTransformInfo::PeelingPreferences PP;
701 
702   // Set the default values.
703   PP.PeelCount = 0;
704   PP.AllowPeeling = true;
705   PP.AllowLoopNestsPeeling = false;
706   PP.PeelProfiledIterations = true;
707 
708   // Get the target specifc values.
709   TTI.getPeelingPreferences(L, SE, PP);
710 
711   // User specified values using cl::opt.
712   if (UnrollingSpecficValues) {
713     if (UnrollPeelCount.getNumOccurrences() > 0)
714       PP.PeelCount = UnrollPeelCount;
715     if (UnrollAllowPeeling.getNumOccurrences() > 0)
716       PP.AllowPeeling = UnrollAllowPeeling;
717     if (UnrollAllowLoopNestsPeeling.getNumOccurrences() > 0)
718       PP.AllowLoopNestsPeeling = UnrollAllowLoopNestsPeeling;
719   }
720 
721   // User specifed values provided by argument.
722   if (UserAllowPeeling)
723     PP.AllowPeeling = *UserAllowPeeling;
724   if (UserAllowProfileBasedPeeling)
725     PP.PeelProfiledIterations = *UserAllowProfileBasedPeeling;
726 
727   return PP;
728 }
729 
730 /// Peel off the first \p PeelCount iterations of loop \p L.
731 ///
732 /// Note that this does not peel them off as a single straight-line block.
733 /// Rather, each iteration is peeled off separately, and needs to check the
734 /// exit condition.
735 /// For loops that dynamically execute \p PeelCount iterations or less
736 /// this provides a benefit, since the peeled off iterations, which account
737 /// for the bulk of dynamic execution, can be further simplified by scalar
738 /// optimizations.
739 bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
740                     ScalarEvolution *SE, DominatorTree &DT, AssumptionCache *AC,
741                     bool PreserveLCSSA) {
742   assert(PeelCount > 0 && "Attempt to peel out zero iterations?");
743   assert(canPeel(L) && "Attempt to peel a loop which is not peelable?");
744 
745   LoopBlocksDFS LoopBlocks(L);
746   LoopBlocks.perform(LI);
747 
748   BasicBlock *Header = L->getHeader();
749   BasicBlock *PreHeader = L->getLoopPreheader();
750   BasicBlock *Latch = L->getLoopLatch();
751   SmallVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitEdges;
752   L->getExitEdges(ExitEdges);
753 
754   // Remember dominators of blocks we might reach through exits to change them
755   // later. Immediate dominator of such block might change, because we add more
756   // routes which can lead to the exit: we can reach it from the peeled
757   // iterations too.
758   DenseMap<BasicBlock *, BasicBlock *> NonLoopBlocksIDom;
759   for (auto *BB : L->blocks()) {
760     auto *BBDomNode = DT.getNode(BB);
761     SmallVector<BasicBlock *, 16> ChildrenToUpdate;
762     for (auto *ChildDomNode : BBDomNode->children()) {
763       auto *ChildBB = ChildDomNode->getBlock();
764       if (!L->contains(ChildBB))
765         ChildrenToUpdate.push_back(ChildBB);
766     }
767     // The new idom of the block will be the nearest common dominator
768     // of all copies of the previous idom. This is equivalent to the
769     // nearest common dominator of the previous idom and the first latch,
770     // which dominates all copies of the previous idom.
771     BasicBlock *NewIDom = DT.findNearestCommonDominator(BB, Latch);
772     for (auto *ChildBB : ChildrenToUpdate)
773       NonLoopBlocksIDom[ChildBB] = NewIDom;
774   }
775 
776   Function *F = Header->getParent();
777 
778   // Set up all the necessary basic blocks. It is convenient to split the
779   // preheader into 3 parts - two blocks to anchor the peeled copy of the loop
780   // body, and a new preheader for the "real" loop.
781 
782   // Peeling the first iteration transforms.
783   //
784   // PreHeader:
785   // ...
786   // Header:
787   //   LoopBody
788   //   If (cond) goto Header
789   // Exit:
790   //
791   // into
792   //
793   // InsertTop:
794   //   LoopBody
795   //   If (!cond) goto Exit
796   // InsertBot:
797   // NewPreHeader:
798   // ...
799   // Header:
800   //  LoopBody
801   //  If (cond) goto Header
802   // Exit:
803   //
804   // Each following iteration will split the current bottom anchor in two,
805   // and put the new copy of the loop body between these two blocks. That is,
806   // after peeling another iteration from the example above, we'll split
807   // InsertBot, and get:
808   //
809   // InsertTop:
810   //   LoopBody
811   //   If (!cond) goto Exit
812   // InsertBot:
813   //   LoopBody
814   //   If (!cond) goto Exit
815   // InsertBot.next:
816   // NewPreHeader:
817   // ...
818   // Header:
819   //  LoopBody
820   //  If (cond) goto Header
821   // Exit:
822 
823   BasicBlock *InsertTop = SplitEdge(PreHeader, Header, &DT, LI);
824   BasicBlock *InsertBot =
825       SplitBlock(InsertTop, InsertTop->getTerminator(), &DT, LI);
826   BasicBlock *NewPreHeader =
827       SplitBlock(InsertBot, InsertBot->getTerminator(), &DT, LI);
828 
829   InsertTop->setName(Header->getName() + ".peel.begin");
830   InsertBot->setName(Header->getName() + ".peel.next");
831   NewPreHeader->setName(PreHeader->getName() + ".peel.newph");
832 
833   ValueToValueMapTy LVMap;
834 
835   // If we have branch weight information, we'll want to update it for the
836   // newly created branches.
837   BranchInst *LatchBR =
838       cast<BranchInst>(cast<BasicBlock>(Latch)->getTerminator());
839   uint64_t ExitWeight = 0, FallThroughWeight = 0;
840   initBranchWeights(Header, LatchBR, ExitWeight, FallThroughWeight);
841 
842   // Identify what noalias metadata is inside the loop: if it is inside the
843   // loop, the associated metadata must be cloned for each iteration.
844   SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;
845   identifyNoAliasScopesToClone(L->getBlocks(), LoopLocalNoAliasDeclScopes);
846 
847   // For each peeled-off iteration, make a copy of the loop.
848   for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
849     SmallVector<BasicBlock *, 8> NewBlocks;
850     ValueToValueMapTy VMap;
851 
852     cloneLoopBlocks(L, Iter, InsertTop, InsertBot, ExitEdges, NewBlocks,
853                     LoopBlocks, VMap, LVMap, &DT, LI,
854                     LoopLocalNoAliasDeclScopes, *SE);
855 
856     // Remap to use values from the current iteration instead of the
857     // previous one.
858     remapInstructionsInBlocks(NewBlocks, VMap);
859 
860     // Update IDoms of the blocks reachable through exits.
861     if (Iter == 0)
862       for (auto BBIDom : NonLoopBlocksIDom)
863         DT.changeImmediateDominator(BBIDom.first,
864                                      cast<BasicBlock>(LVMap[BBIDom.second]));
865 #ifdef EXPENSIVE_CHECKS
866     assert(DT.verify(DominatorTree::VerificationLevel::Fast));
867 #endif
868 
869     auto *LatchBRCopy = cast<BranchInst>(VMap[LatchBR]);
870     updateBranchWeights(InsertBot, LatchBRCopy, ExitWeight, FallThroughWeight);
871     // Remove Loop metadata from the latch branch instruction
872     // because it is not the Loop's latch branch anymore.
873     LatchBRCopy->setMetadata(LLVMContext::MD_loop, nullptr);
874 
875     InsertTop = InsertBot;
876     InsertBot = SplitBlock(InsertBot, InsertBot->getTerminator(), &DT, LI);
877     InsertBot->setName(Header->getName() + ".peel.next");
878 
879     F->getBasicBlockList().splice(InsertTop->getIterator(),
880                                   F->getBasicBlockList(),
881                                   NewBlocks[0]->getIterator(), F->end());
882   }
883 
884   // Now adjust the phi nodes in the loop header to get their initial values
885   // from the last peeled-off iteration instead of the preheader.
886   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
887     PHINode *PHI = cast<PHINode>(I);
888     Value *NewVal = PHI->getIncomingValueForBlock(Latch);
889     Instruction *LatchInst = dyn_cast<Instruction>(NewVal);
890     if (LatchInst && L->contains(LatchInst))
891       NewVal = LVMap[LatchInst];
892 
893     PHI->setIncomingValueForBlock(NewPreHeader, NewVal);
894   }
895 
896   fixupBranchWeights(Header, LatchBR, ExitWeight, FallThroughWeight);
897 
898   // Update Metadata for count of peeled off iterations.
899   unsigned AlreadyPeeled = 0;
900   if (auto Peeled = getOptionalIntLoopAttribute(L, PeeledCountMetaData))
901     AlreadyPeeled = *Peeled;
902   addStringMetadataToLoop(L, PeeledCountMetaData, AlreadyPeeled + PeelCount);
903 
904   if (Loop *ParentLoop = L->getParentLoop())
905     L = ParentLoop;
906 
907   // We modified the loop, update SE.
908   SE->forgetTopmostLoop(L);
909 
910 #ifdef EXPENSIVE_CHECKS
911   // Finally DomtTree must be correct.
912   assert(DT.verify(DominatorTree::VerificationLevel::Fast));
913 #endif
914 
915   // FIXME: Incrementally update loop-simplify
916   simplifyLoop(L, &DT, LI, SE, AC, nullptr, PreserveLCSSA);
917 
918   NumPeeled++;
919 
920   return true;
921 }
922