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