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