1 //===-- UnrollLoop.cpp - Loop unrolling 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. It does not define any
10 // actual pass or policy, but provides a single function to perform loop
11 // unrolling.
12 //
13 // The process of unrolling can produce extraneous basic blocks linked with
14 // unconditional branches. This will be corrected in the future.
15 //
16 //===----------------------------------------------------------------------===//
17
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SetVector.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/ADT/StringRef.h"
26 #include "llvm/ADT/Twine.h"
27 #include "llvm/ADT/ilist_iterator.h"
28 #include "llvm/ADT/iterator_range.h"
29 #include "llvm/Analysis/AssumptionCache.h"
30 #include "llvm/Analysis/DomTreeUpdater.h"
31 #include "llvm/Analysis/InstructionSimplify.h"
32 #include "llvm/Analysis/LoopInfo.h"
33 #include "llvm/Analysis/LoopIterator.h"
34 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
35 #include "llvm/Analysis/ScalarEvolution.h"
36 #include "llvm/IR/BasicBlock.h"
37 #include "llvm/IR/CFG.h"
38 #include "llvm/IR/Constants.h"
39 #include "llvm/IR/DebugInfoMetadata.h"
40 #include "llvm/IR/DebugLoc.h"
41 #include "llvm/IR/DiagnosticInfo.h"
42 #include "llvm/IR/Dominators.h"
43 #include "llvm/IR/Function.h"
44 #include "llvm/IR/Instruction.h"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/IntrinsicInst.h"
47 #include "llvm/IR/Metadata.h"
48 #include "llvm/IR/Module.h"
49 #include "llvm/IR/Use.h"
50 #include "llvm/IR/User.h"
51 #include "llvm/IR/ValueHandle.h"
52 #include "llvm/IR/ValueMap.h"
53 #include "llvm/Support/Casting.h"
54 #include "llvm/Support/CommandLine.h"
55 #include "llvm/Support/Debug.h"
56 #include "llvm/Support/GenericDomTree.h"
57 #include "llvm/Support/MathExtras.h"
58 #include "llvm/Support/raw_ostream.h"
59 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
60 #include "llvm/Transforms/Utils/Cloning.h"
61 #include "llvm/Transforms/Utils/Local.h"
62 #include "llvm/Transforms/Utils/LoopPeel.h"
63 #include "llvm/Transforms/Utils/LoopSimplify.h"
64 #include "llvm/Transforms/Utils/LoopUtils.h"
65 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
66 #include "llvm/Transforms/Utils/UnrollLoop.h"
67 #include "llvm/Transforms/Utils/ValueMapper.h"
68 #include <algorithm>
69 #include <assert.h>
70 #include <type_traits>
71 #include <vector>
72
73 namespace llvm {
74 class DataLayout;
75 class Value;
76 } // namespace llvm
77
78 using namespace llvm;
79
80 #define DEBUG_TYPE "loop-unroll"
81
82 // TODO: Should these be here or in LoopUnroll?
83 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
84 STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");
85 STATISTIC(NumUnrolledNotLatch, "Number of loops unrolled without a conditional "
86 "latch (completely or otherwise)");
87
88 static cl::opt<bool>
89 UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden,
90 cl::desc("Allow runtime unrolled loops to be unrolled "
91 "with epilog instead of prolog."));
92
93 static cl::opt<bool>
94 UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden,
95 cl::desc("Verify domtree after unrolling"),
96 #ifdef EXPENSIVE_CHECKS
97 cl::init(true)
98 #else
99 cl::init(false)
100 #endif
101 );
102
103 /// Check if unrolling created a situation where we need to insert phi nodes to
104 /// preserve LCSSA form.
105 /// \param Blocks is a vector of basic blocks representing unrolled loop.
106 /// \param L is the outer loop.
107 /// It's possible that some of the blocks are in L, and some are not. In this
108 /// case, if there is a use is outside L, and definition is inside L, we need to
109 /// insert a phi-node, otherwise LCSSA will be broken.
110 /// The function is just a helper function for llvm::UnrollLoop that returns
111 /// true if this situation occurs, indicating that LCSSA needs to be fixed.
needToInsertPhisForLCSSA(Loop * L,const std::vector<BasicBlock * > & Blocks,LoopInfo * LI)112 static bool needToInsertPhisForLCSSA(Loop *L,
113 const std::vector<BasicBlock *> &Blocks,
114 LoopInfo *LI) {
115 for (BasicBlock *BB : Blocks) {
116 if (LI->getLoopFor(BB) == L)
117 continue;
118 for (Instruction &I : *BB) {
119 for (Use &U : I.operands()) {
120 if (const auto *Def = dyn_cast<Instruction>(U)) {
121 Loop *DefLoop = LI->getLoopFor(Def->getParent());
122 if (!DefLoop)
123 continue;
124 if (DefLoop->contains(L))
125 return true;
126 }
127 }
128 }
129 }
130 return false;
131 }
132
133 /// Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary
134 /// and adds a mapping from the original loop to the new loop to NewLoops.
135 /// Returns nullptr if no new loop was created and a pointer to the
136 /// original loop OriginalBB was part of otherwise.
addClonedBlockToLoopInfo(BasicBlock * OriginalBB,BasicBlock * ClonedBB,LoopInfo * LI,NewLoopsMap & NewLoops)137 const Loop* llvm::addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
138 BasicBlock *ClonedBB, LoopInfo *LI,
139 NewLoopsMap &NewLoops) {
140 // Figure out which loop New is in.
141 const Loop *OldLoop = LI->getLoopFor(OriginalBB);
142 assert(OldLoop && "Should (at least) be in the loop being unrolled!");
143
144 Loop *&NewLoop = NewLoops[OldLoop];
145 if (!NewLoop) {
146 // Found a new sub-loop.
147 assert(OriginalBB == OldLoop->getHeader() &&
148 "Header should be first in RPO");
149
150 NewLoop = LI->AllocateLoop();
151 Loop *NewLoopParent = NewLoops.lookup(OldLoop->getParentLoop());
152
153 if (NewLoopParent)
154 NewLoopParent->addChildLoop(NewLoop);
155 else
156 LI->addTopLevelLoop(NewLoop);
157
158 NewLoop->addBasicBlockToLoop(ClonedBB, *LI);
159 return OldLoop;
160 } else {
161 NewLoop->addBasicBlockToLoop(ClonedBB, *LI);
162 return nullptr;
163 }
164 }
165
166 /// The function chooses which type of unroll (epilog or prolog) is more
167 /// profitabale.
168 /// Epilog unroll is more profitable when there is PHI that starts from
169 /// constant. In this case epilog will leave PHI start from constant,
170 /// but prolog will convert it to non-constant.
171 ///
172 /// loop:
173 /// PN = PHI [I, Latch], [CI, PreHeader]
174 /// I = foo(PN)
175 /// ...
176 ///
177 /// Epilog unroll case.
178 /// loop:
179 /// PN = PHI [I2, Latch], [CI, PreHeader]
180 /// I1 = foo(PN)
181 /// I2 = foo(I1)
182 /// ...
183 /// Prolog unroll case.
184 /// NewPN = PHI [PrologI, Prolog], [CI, PreHeader]
185 /// loop:
186 /// PN = PHI [I2, Latch], [NewPN, PreHeader]
187 /// I1 = foo(PN)
188 /// I2 = foo(I1)
189 /// ...
190 ///
isEpilogProfitable(Loop * L)191 static bool isEpilogProfitable(Loop *L) {
192 BasicBlock *PreHeader = L->getLoopPreheader();
193 BasicBlock *Header = L->getHeader();
194 assert(PreHeader && Header);
195 for (const PHINode &PN : Header->phis()) {
196 if (isa<ConstantInt>(PN.getIncomingValueForBlock(PreHeader)))
197 return true;
198 }
199 return false;
200 }
201
202 /// Perform some cleanup and simplifications on loops after unrolling. It is
203 /// useful to simplify the IV's in the new loop, as well as do a quick
204 /// simplify/dce pass of the instructions.
simplifyLoopAfterUnroll(Loop * L,bool SimplifyIVs,LoopInfo * LI,ScalarEvolution * SE,DominatorTree * DT,AssumptionCache * AC,const TargetTransformInfo * TTI)205 void llvm::simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
206 ScalarEvolution *SE, DominatorTree *DT,
207 AssumptionCache *AC,
208 const TargetTransformInfo *TTI) {
209 // Simplify any new induction variables in the partially unrolled loop.
210 if (SE && SimplifyIVs) {
211 SmallVector<WeakTrackingVH, 16> DeadInsts;
212 simplifyLoopIVs(L, SE, DT, LI, TTI, DeadInsts);
213
214 // Aggressively clean up dead instructions that simplifyLoopIVs already
215 // identified. Any remaining should be cleaned up below.
216 while (!DeadInsts.empty()) {
217 Value *V = DeadInsts.pop_back_val();
218 if (Instruction *Inst = dyn_cast_or_null<Instruction>(V))
219 RecursivelyDeleteTriviallyDeadInstructions(Inst);
220 }
221 }
222
223 // At this point, the code is well formed. Perform constprop, instsimplify,
224 // and dce.
225 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
226 SmallVector<WeakTrackingVH, 16> DeadInsts;
227 for (BasicBlock *BB : L->getBlocks()) {
228 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
229 Instruction *Inst = &*I++;
230 if (Value *V = SimplifyInstruction(Inst, {DL, nullptr, DT, AC}))
231 if (LI->replacementPreservesLCSSAForm(Inst, V))
232 Inst->replaceAllUsesWith(V);
233 if (isInstructionTriviallyDead(Inst))
234 DeadInsts.emplace_back(Inst);
235 }
236 // We can't do recursive deletion until we're done iterating, as we might
237 // have a phi which (potentially indirectly) uses instructions later in
238 // the block we're iterating through.
239 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);
240 }
241 }
242
243 /// Unroll the given loop by Count. The loop must be in LCSSA form. Unrolling
244 /// can only fail when the loop's latch block is not terminated by a conditional
245 /// branch instruction. However, if the trip count (and multiple) are not known,
246 /// loop unrolling will mostly produce more code that is no faster.
247 ///
248 /// TripCount is the upper bound of the iteration on which control exits
249 /// LatchBlock. Control may exit the loop prior to TripCount iterations either
250 /// via an early branch in other loop block or via LatchBlock terminator. This
251 /// is relaxed from the general definition of trip count which is the number of
252 /// times the loop header executes. Note that UnrollLoop assumes that the loop
253 /// counter test is in LatchBlock in order to remove unnecesssary instances of
254 /// the test. If control can exit the loop from the LatchBlock's terminator
255 /// prior to TripCount iterations, flag PreserveCondBr needs to be set.
256 ///
257 /// PreserveCondBr indicates whether the conditional branch of the LatchBlock
258 /// needs to be preserved. It is needed when we use trip count upper bound to
259 /// fully unroll the loop. If PreserveOnlyFirst is also set then only the first
260 /// conditional branch needs to be preserved.
261 ///
262 /// Similarly, TripMultiple divides the number of times that the LatchBlock may
263 /// execute without exiting the loop.
264 ///
265 /// If AllowRuntime is true then UnrollLoop will consider unrolling loops that
266 /// have a runtime (i.e. not compile time constant) trip count. Unrolling these
267 /// loops require a unroll "prologue" that runs "RuntimeTripCount % Count"
268 /// iterations before branching into the unrolled loop. UnrollLoop will not
269 /// runtime-unroll the loop if computing RuntimeTripCount will be expensive and
270 /// AllowExpensiveTripCount is false.
271 ///
272 /// If we want to perform PGO-based loop peeling, PeelCount is set to the
273 /// number of iterations we want to peel off.
274 ///
275 /// The LoopInfo Analysis that is passed will be kept consistent.
276 ///
277 /// This utility preserves LoopInfo. It will also preserve ScalarEvolution and
278 /// DominatorTree if they are non-null.
279 ///
280 /// If RemainderLoop is non-null, it will receive the remainder loop (if
281 /// required and not fully unrolled).
UnrollLoop(Loop * L,UnrollLoopOptions ULO,LoopInfo * LI,ScalarEvolution * SE,DominatorTree * DT,AssumptionCache * AC,const TargetTransformInfo * TTI,OptimizationRemarkEmitter * ORE,bool PreserveLCSSA,Loop ** RemainderLoop)282 LoopUnrollResult llvm::UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
283 ScalarEvolution *SE, DominatorTree *DT,
284 AssumptionCache *AC,
285 const TargetTransformInfo *TTI,
286 OptimizationRemarkEmitter *ORE,
287 bool PreserveLCSSA, Loop **RemainderLoop) {
288
289 if (!L->getLoopPreheader()) {
290 LLVM_DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n");
291 return LoopUnrollResult::Unmodified;
292 }
293
294 if (!L->getLoopLatch()) {
295 LLVM_DEBUG(dbgs() << " Can't unroll; loop exit-block-insertion failed.\n");
296 return LoopUnrollResult::Unmodified;
297 }
298
299 // Loops with indirectbr cannot be cloned.
300 if (!L->isSafeToClone()) {
301 LLVM_DEBUG(dbgs() << " Can't unroll; Loop body cannot be cloned.\n");
302 return LoopUnrollResult::Unmodified;
303 }
304
305 if (L->getHeader()->hasAddressTaken()) {
306 // The loop-rotate pass can be helpful to avoid this in many cases.
307 LLVM_DEBUG(
308 dbgs() << " Won't unroll loop: address of header block is taken.\n");
309 return LoopUnrollResult::Unmodified;
310 }
311
312 if (ULO.TripCount != 0)
313 LLVM_DEBUG(dbgs() << " Trip Count = " << ULO.TripCount << "\n");
314 if (ULO.TripMultiple != 1)
315 LLVM_DEBUG(dbgs() << " Trip Multiple = " << ULO.TripMultiple << "\n");
316
317 // Effectively "DCE" unrolled iterations that are beyond the tripcount
318 // and will never be executed.
319 if (ULO.TripCount != 0 && ULO.Count > ULO.TripCount)
320 ULO.Count = ULO.TripCount;
321
322 // Don't enter the unroll code if there is nothing to do.
323 if (ULO.TripCount == 0 && ULO.Count < 2 && ULO.PeelCount == 0) {
324 LLVM_DEBUG(dbgs() << "Won't unroll; almost nothing to do\n");
325 return LoopUnrollResult::Unmodified;
326 }
327
328 assert(ULO.Count > 0);
329 assert(ULO.TripMultiple > 0);
330 assert(ULO.TripCount == 0 || ULO.TripCount % ULO.TripMultiple == 0);
331
332 // Are we eliminating the loop control altogether?
333 bool CompletelyUnroll = ULO.Count == ULO.TripCount;
334
335 // We assume a run-time trip count if the compiler cannot
336 // figure out the loop trip count and the unroll-runtime
337 // flag is specified.
338 bool RuntimeTripCount =
339 (ULO.TripCount == 0 && ULO.Count > 0 && ULO.AllowRuntime);
340
341 assert((!RuntimeTripCount || !ULO.PeelCount) &&
342 "Did not expect runtime trip-count unrolling "
343 "and peeling for the same loop");
344
345 bool Peeled = false;
346 if (ULO.PeelCount) {
347 Peeled = peelLoop(L, ULO.PeelCount, LI, SE, DT, AC, PreserveLCSSA);
348
349 // Successful peeling may result in a change in the loop preheader/trip
350 // counts. If we later unroll the loop, we want these to be updated.
351 if (Peeled) {
352 // According to our guards and profitability checks the only
353 // meaningful exit should be latch block. Other exits go to deopt,
354 // so we do not worry about them.
355 BasicBlock *ExitingBlock = L->getLoopLatch();
356 assert(ExitingBlock && "Loop without exiting block?");
357 assert(L->isLoopExiting(ExitingBlock) && "Latch is not exiting?");
358 ULO.TripCount = SE->getSmallConstantTripCount(L, ExitingBlock);
359 ULO.TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock);
360 }
361 }
362
363 // All these values should be taken only after peeling because they might have
364 // changed.
365 BasicBlock *Preheader = L->getLoopPreheader();
366 BasicBlock *Header = L->getHeader();
367 BasicBlock *LatchBlock = L->getLoopLatch();
368 SmallVector<BasicBlock *, 4> ExitBlocks;
369 L->getExitBlocks(ExitBlocks);
370 std::vector<BasicBlock *> OriginalLoopBlocks = L->getBlocks();
371
372 // Go through all exits of L and see if there are any phi-nodes there. We just
373 // conservatively assume that they're inserted to preserve LCSSA form, which
374 // means that complete unrolling might break this form. We need to either fix
375 // it in-place after the transformation, or entirely rebuild LCSSA. TODO: For
376 // now we just recompute LCSSA for the outer loop, but it should be possible
377 // to fix it in-place.
378 bool NeedToFixLCSSA =
379 PreserveLCSSA && CompletelyUnroll &&
380 any_of(ExitBlocks,
381 [](const BasicBlock *BB) { return isa<PHINode>(BB->begin()); });
382
383 // The current loop unroll pass can unroll loops that have
384 // (1) single latch; and
385 // (2a) latch is unconditional; or
386 // (2b) latch is conditional and is an exiting block
387 // FIXME: The implementation can be extended to work with more complicated
388 // cases, e.g. loops with multiple latches.
389 BranchInst *LatchBI = dyn_cast<BranchInst>(LatchBlock->getTerminator());
390
391 // A conditional branch which exits the loop, which can be optimized to an
392 // unconditional branch in the unrolled loop in some cases.
393 BranchInst *ExitingBI = nullptr;
394 bool LatchIsExiting = L->isLoopExiting(LatchBlock);
395 if (LatchIsExiting)
396 ExitingBI = LatchBI;
397 else if (BasicBlock *ExitingBlock = L->getExitingBlock())
398 ExitingBI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
399 if (!LatchBI || (LatchBI->isConditional() && !LatchIsExiting)) {
400 // If the peeling guard is changed this assert may be relaxed or even
401 // deleted.
402 assert(!Peeled && "Peeling guard changed!");
403 LLVM_DEBUG(
404 dbgs() << "Can't unroll; a conditional latch must exit the loop");
405 return LoopUnrollResult::Unmodified;
406 }
407 LLVM_DEBUG({
408 if (ExitingBI)
409 dbgs() << " Exiting Block = " << ExitingBI->getParent()->getName()
410 << "\n";
411 else
412 dbgs() << " No single exiting block\n";
413 });
414
415 // Loops containing convergent instructions must have a count that divides
416 // their TripMultiple.
417 LLVM_DEBUG(
418 {
419 bool HasConvergent = false;
420 for (auto &BB : L->blocks())
421 for (auto &I : *BB)
422 if (auto *CB = dyn_cast<CallBase>(&I))
423 HasConvergent |= CB->isConvergent();
424 assert((!HasConvergent || ULO.TripMultiple % ULO.Count == 0) &&
425 "Unroll count must divide trip multiple if loop contains a "
426 "convergent operation.");
427 });
428
429 bool EpilogProfitability =
430 UnrollRuntimeEpilog.getNumOccurrences() ? UnrollRuntimeEpilog
431 : isEpilogProfitable(L);
432
433 if (RuntimeTripCount && ULO.TripMultiple % ULO.Count != 0 &&
434 !UnrollRuntimeLoopRemainder(L, ULO.Count, ULO.AllowExpensiveTripCount,
435 EpilogProfitability, ULO.UnrollRemainder,
436 ULO.ForgetAllSCEV, LI, SE, DT, AC, TTI,
437 PreserveLCSSA, RemainderLoop)) {
438 if (ULO.Force)
439 RuntimeTripCount = false;
440 else {
441 LLVM_DEBUG(dbgs() << "Won't unroll; remainder loop could not be "
442 "generated when assuming runtime trip count\n");
443 return LoopUnrollResult::Unmodified;
444 }
445 }
446
447 // If we know the trip count, we know the multiple...
448 unsigned BreakoutTrip = 0;
449 if (ULO.TripCount != 0) {
450 BreakoutTrip = ULO.TripCount % ULO.Count;
451 ULO.TripMultiple = 0;
452 } else {
453 // Figure out what multiple to use.
454 BreakoutTrip = ULO.TripMultiple =
455 (unsigned)GreatestCommonDivisor64(ULO.Count, ULO.TripMultiple);
456 }
457
458 using namespace ore;
459 // Report the unrolling decision.
460 if (CompletelyUnroll) {
461 LLVM_DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()
462 << " with trip count " << ULO.TripCount << "!\n");
463 if (ORE)
464 ORE->emit([&]() {
465 return OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(),
466 L->getHeader())
467 << "completely unrolled loop with "
468 << NV("UnrollCount", ULO.TripCount) << " iterations";
469 });
470 } else if (ULO.PeelCount) {
471 LLVM_DEBUG(dbgs() << "PEELING loop %" << Header->getName()
472 << " with iteration count " << ULO.PeelCount << "!\n");
473 if (ORE)
474 ORE->emit([&]() {
475 return OptimizationRemark(DEBUG_TYPE, "Peeled", L->getStartLoc(),
476 L->getHeader())
477 << " peeled loop by " << NV("PeelCount", ULO.PeelCount)
478 << " iterations";
479 });
480 } else {
481 auto DiagBuilder = [&]() {
482 OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled", L->getStartLoc(),
483 L->getHeader());
484 return Diag << "unrolled loop by a factor of "
485 << NV("UnrollCount", ULO.Count);
486 };
487
488 LLVM_DEBUG(dbgs() << "UNROLLING loop %" << Header->getName() << " by "
489 << ULO.Count);
490 if (ULO.TripMultiple == 0 || BreakoutTrip != ULO.TripMultiple) {
491 LLVM_DEBUG(dbgs() << " with a breakout at trip " << BreakoutTrip);
492 if (ORE)
493 ORE->emit([&]() {
494 return DiagBuilder() << " with a breakout at trip "
495 << NV("BreakoutTrip", BreakoutTrip);
496 });
497 } else if (ULO.TripMultiple != 1) {
498 LLVM_DEBUG(dbgs() << " with " << ULO.TripMultiple << " trips per branch");
499 if (ORE)
500 ORE->emit([&]() {
501 return DiagBuilder()
502 << " with " << NV("TripMultiple", ULO.TripMultiple)
503 << " trips per branch";
504 });
505 } else if (RuntimeTripCount) {
506 LLVM_DEBUG(dbgs() << " with run-time trip count");
507 if (ORE)
508 ORE->emit(
509 [&]() { return DiagBuilder() << " with run-time trip count"; });
510 }
511 LLVM_DEBUG(dbgs() << "!\n");
512 }
513
514 // We are going to make changes to this loop. SCEV may be keeping cached info
515 // about it, in particular about backedge taken count. The changes we make
516 // are guaranteed to invalidate this information for our loop. It is tempting
517 // to only invalidate the loop being unrolled, but it is incorrect as long as
518 // all exiting branches from all inner loops have impact on the outer loops,
519 // and if something changes inside them then any of outer loops may also
520 // change. When we forget outermost loop, we also forget all contained loops
521 // and this is what we need here.
522 if (SE) {
523 if (ULO.ForgetAllSCEV)
524 SE->forgetAllLoops();
525 else
526 SE->forgetTopmostLoop(L);
527 }
528
529 if (!LatchIsExiting)
530 ++NumUnrolledNotLatch;
531 Optional<bool> ContinueOnTrue = None;
532 BasicBlock *LoopExit = nullptr;
533 if (ExitingBI) {
534 ContinueOnTrue = L->contains(ExitingBI->getSuccessor(0));
535 LoopExit = ExitingBI->getSuccessor(*ContinueOnTrue);
536 }
537
538 // For the first iteration of the loop, we should use the precloned values for
539 // PHI nodes. Insert associations now.
540 ValueToValueMapTy LastValueMap;
541 std::vector<PHINode*> OrigPHINode;
542 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
543 OrigPHINode.push_back(cast<PHINode>(I));
544 }
545
546 std::vector<BasicBlock *> Headers;
547 std::vector<BasicBlock *> ExitingBlocks;
548 std::vector<BasicBlock *> ExitingSucc;
549 std::vector<BasicBlock *> Latches;
550 Headers.push_back(Header);
551 Latches.push_back(LatchBlock);
552 if (ExitingBI) {
553 ExitingBlocks.push_back(ExitingBI->getParent());
554 ExitingSucc.push_back(ExitingBI->getSuccessor(!(*ContinueOnTrue)));
555 }
556
557 // The current on-the-fly SSA update requires blocks to be processed in
558 // reverse postorder so that LastValueMap contains the correct value at each
559 // exit.
560 LoopBlocksDFS DFS(L);
561 DFS.perform(LI);
562
563 // Stash the DFS iterators before adding blocks to the loop.
564 LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();
565 LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();
566
567 std::vector<BasicBlock*> UnrolledLoopBlocks = L->getBlocks();
568
569 // Loop Unrolling might create new loops. While we do preserve LoopInfo, we
570 // might break loop-simplified form for these loops (as they, e.g., would
571 // share the same exit blocks). We'll keep track of loops for which we can
572 // break this so that later we can re-simplify them.
573 SmallSetVector<Loop *, 4> LoopsToSimplify;
574 for (Loop *SubLoop : *L)
575 LoopsToSimplify.insert(SubLoop);
576
577 // When a FSDiscriminator is enabled, we don't need to add the multiply
578 // factors to the discriminators.
579 if (Header->getParent()->isDebugInfoForProfiling() && !EnableFSDiscriminator)
580 for (BasicBlock *BB : L->getBlocks())
581 for (Instruction &I : *BB)
582 if (!isa<DbgInfoIntrinsic>(&I))
583 if (const DILocation *DIL = I.getDebugLoc()) {
584 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(ULO.Count);
585 if (NewDIL)
586 I.setDebugLoc(NewDIL.getValue());
587 else
588 LLVM_DEBUG(dbgs()
589 << "Failed to create new discriminator: "
590 << DIL->getFilename() << " Line: " << DIL->getLine());
591 }
592
593 // Identify what noalias metadata is inside the loop: if it is inside the
594 // loop, the associated metadata must be cloned for each iteration.
595 SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;
596 identifyNoAliasScopesToClone(L->getBlocks(), LoopLocalNoAliasDeclScopes);
597
598 for (unsigned It = 1; It != ULO.Count; ++It) {
599 SmallVector<BasicBlock *, 8> NewBlocks;
600 SmallDenseMap<const Loop *, Loop *, 4> NewLoops;
601 NewLoops[L] = L;
602
603 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
604 ValueToValueMapTy VMap;
605 BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It));
606 Header->getParent()->getBasicBlockList().push_back(New);
607
608 assert((*BB != Header || LI->getLoopFor(*BB) == L) &&
609 "Header should not be in a sub-loop");
610 // Tell LI about New.
611 const Loop *OldLoop = addClonedBlockToLoopInfo(*BB, New, LI, NewLoops);
612 if (OldLoop)
613 LoopsToSimplify.insert(NewLoops[OldLoop]);
614
615 if (*BB == Header)
616 // Loop over all of the PHI nodes in the block, changing them to use
617 // the incoming values from the previous block.
618 for (PHINode *OrigPHI : OrigPHINode) {
619 PHINode *NewPHI = cast<PHINode>(VMap[OrigPHI]);
620 Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock);
621 if (Instruction *InValI = dyn_cast<Instruction>(InVal))
622 if (It > 1 && L->contains(InValI))
623 InVal = LastValueMap[InValI];
624 VMap[OrigPHI] = InVal;
625 New->getInstList().erase(NewPHI);
626 }
627
628 // Update our running map of newest clones
629 LastValueMap[*BB] = New;
630 for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();
631 VI != VE; ++VI)
632 LastValueMap[VI->first] = VI->second;
633
634 // Add phi entries for newly created values to all exit blocks.
635 for (BasicBlock *Succ : successors(*BB)) {
636 if (L->contains(Succ))
637 continue;
638 for (PHINode &PHI : Succ->phis()) {
639 Value *Incoming = PHI.getIncomingValueForBlock(*BB);
640 ValueToValueMapTy::iterator It = LastValueMap.find(Incoming);
641 if (It != LastValueMap.end())
642 Incoming = It->second;
643 PHI.addIncoming(Incoming, New);
644 }
645 }
646 // Keep track of new headers and latches as we create them, so that
647 // we can insert the proper branches later.
648 if (*BB == Header)
649 Headers.push_back(New);
650 if (*BB == LatchBlock)
651 Latches.push_back(New);
652
653 // Keep track of the exiting block and its successor block contained in
654 // the loop for the current iteration.
655 if (ExitingBI) {
656 if (*BB == ExitingBlocks[0])
657 ExitingBlocks.push_back(New);
658 if (*BB == ExitingSucc[0])
659 ExitingSucc.push_back(New);
660 }
661
662 NewBlocks.push_back(New);
663 UnrolledLoopBlocks.push_back(New);
664
665 // Update DomTree: since we just copy the loop body, and each copy has a
666 // dedicated entry block (copy of the header block), this header's copy
667 // dominates all copied blocks. That means, dominance relations in the
668 // copied body are the same as in the original body.
669 if (DT) {
670 if (*BB == Header)
671 DT->addNewBlock(New, Latches[It - 1]);
672 else {
673 auto BBDomNode = DT->getNode(*BB);
674 auto BBIDom = BBDomNode->getIDom();
675 BasicBlock *OriginalBBIDom = BBIDom->getBlock();
676 DT->addNewBlock(
677 New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)]));
678 }
679 }
680 }
681
682 // Remap all instructions in the most recent iteration
683 remapInstructionsInBlocks(NewBlocks, LastValueMap);
684 for (BasicBlock *NewBlock : NewBlocks)
685 for (Instruction &I : *NewBlock)
686 if (auto *II = dyn_cast<AssumeInst>(&I))
687 AC->registerAssumption(II);
688
689 {
690 // Identify what other metadata depends on the cloned version. After
691 // cloning, replace the metadata with the corrected version for both
692 // memory instructions and noalias intrinsics.
693 std::string ext = (Twine("It") + Twine(It)).str();
694 cloneAndAdaptNoAliasScopes(LoopLocalNoAliasDeclScopes, NewBlocks,
695 Header->getContext(), ext);
696 }
697 }
698
699 // Loop over the PHI nodes in the original block, setting incoming values.
700 for (PHINode *PN : OrigPHINode) {
701 if (CompletelyUnroll) {
702 PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));
703 Header->getInstList().erase(PN);
704 } else if (ULO.Count > 1) {
705 Value *InVal = PN->removeIncomingValue(LatchBlock, false);
706 // If this value was defined in the loop, take the value defined by the
707 // last iteration of the loop.
708 if (Instruction *InValI = dyn_cast<Instruction>(InVal)) {
709 if (L->contains(InValI))
710 InVal = LastValueMap[InVal];
711 }
712 assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch");
713 PN->addIncoming(InVal, Latches.back());
714 }
715 }
716
717 auto setDest = [](BasicBlock *Src, BasicBlock *Dest, BasicBlock *BlockInLoop,
718 bool NeedConditional, Optional<bool> ContinueOnTrue,
719 bool IsDestLoopExit) {
720 auto *Term = cast<BranchInst>(Src->getTerminator());
721 if (NeedConditional) {
722 // Update the conditional branch's successor for the following
723 // iteration.
724 assert(ContinueOnTrue.hasValue() &&
725 "Expecting valid ContinueOnTrue when NeedConditional is true");
726 Term->setSuccessor(!(*ContinueOnTrue), Dest);
727 } else {
728 // Remove phi operands at this loop exit
729 if (!IsDestLoopExit) {
730 BasicBlock *BB = Src;
731 for (BasicBlock *Succ : successors(BB)) {
732 // Preserve the incoming value from BB if we are jumping to the block
733 // in the current loop.
734 if (Succ == BlockInLoop)
735 continue;
736 for (PHINode &Phi : Succ->phis())
737 Phi.removeIncomingValue(BB, false);
738 }
739 }
740 // Replace the conditional branch with an unconditional one.
741 BranchInst::Create(Dest, Term);
742 Term->eraseFromParent();
743 }
744 };
745
746 // Connect latches of the unrolled iterations to the headers of the next
747 // iteration. If the latch is also the exiting block, the conditional branch
748 // may have to be preserved.
749 for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
750 // The branch destination.
751 unsigned j = (i + 1) % e;
752 BasicBlock *Dest = Headers[j];
753 bool NeedConditional = LatchIsExiting;
754
755 if (LatchIsExiting) {
756 if (RuntimeTripCount && j != 0)
757 NeedConditional = false;
758
759 // For a complete unroll, make the last iteration end with a branch
760 // to the exit block.
761 if (CompletelyUnroll) {
762 if (j == 0)
763 Dest = LoopExit;
764 // If using trip count upper bound to completely unroll, we need to
765 // keep the conditional branch except the last one because the loop
766 // may exit after any iteration.
767 assert(NeedConditional &&
768 "NeedCondition cannot be modified by both complete "
769 "unrolling and runtime unrolling");
770 NeedConditional =
771 (ULO.PreserveCondBr && j && !(ULO.PreserveOnlyFirst && i != 0));
772 } else if (j != BreakoutTrip &&
773 (ULO.TripMultiple == 0 || j % ULO.TripMultiple != 0)) {
774 // If we know the trip count or a multiple of it, we can safely use an
775 // unconditional branch for some iterations.
776 NeedConditional = false;
777 }
778 }
779
780 setDest(Latches[i], Dest, Headers[i], NeedConditional, ContinueOnTrue,
781 Dest == LoopExit);
782 }
783
784 if (!LatchIsExiting) {
785 // If the latch is not exiting, we may be able to simplify the conditional
786 // branches in the unrolled exiting blocks.
787 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
788 // The branch destination.
789 unsigned j = (i + 1) % e;
790 bool NeedConditional = true;
791
792 if (RuntimeTripCount && j != 0)
793 NeedConditional = false;
794
795 if (CompletelyUnroll)
796 // We cannot drop the conditional branch for the last condition, as we
797 // may have to execute the loop body depending on the condition.
798 NeedConditional = j == 0 || ULO.PreserveCondBr;
799 else if (j != BreakoutTrip &&
800 (ULO.TripMultiple == 0 || j % ULO.TripMultiple != 0))
801 // If we know the trip count or a multiple of it, we can safely use an
802 // unconditional branch for some iterations.
803 NeedConditional = false;
804
805 // Conditional branches from non-latch exiting block have successors
806 // either in the same loop iteration or outside the loop. The branches are
807 // already correct.
808 if (NeedConditional)
809 continue;
810 setDest(ExitingBlocks[i], ExitingSucc[i], ExitingSucc[i], NeedConditional,
811 None, false);
812 }
813
814 // When completely unrolling, the last latch becomes unreachable.
815 if (CompletelyUnroll) {
816 BranchInst *Term = cast<BranchInst>(Latches.back()->getTerminator());
817 new UnreachableInst(Term->getContext(), Term);
818 Term->eraseFromParent();
819 }
820 }
821
822 // Update dominators of blocks we might reach through exits.
823 // Immediate dominator of such block might change, because we add more
824 // routes which can lead to the exit: we can now reach it from the copied
825 // iterations too.
826 if (DT && ULO.Count > 1) {
827 for (auto *BB : OriginalLoopBlocks) {
828 auto *BBDomNode = DT->getNode(BB);
829 SmallVector<BasicBlock *, 16> ChildrenToUpdate;
830 for (auto *ChildDomNode : BBDomNode->children()) {
831 auto *ChildBB = ChildDomNode->getBlock();
832 if (!L->contains(ChildBB))
833 ChildrenToUpdate.push_back(ChildBB);
834 }
835 BasicBlock *NewIDom;
836 if (ExitingBI && BB == ExitingBlocks[0]) {
837 // The latch is special because we emit unconditional branches in
838 // some cases where the original loop contained a conditional branch.
839 // Since the latch is always at the bottom of the loop, if the latch
840 // dominated an exit before unrolling, the new dominator of that exit
841 // must also be a latch. Specifically, the dominator is the first
842 // latch which ends in a conditional branch, or the last latch if
843 // there is no such latch.
844 // For loops exiting from non latch exiting block, we limit the
845 // branch simplification to single exiting block loops.
846 NewIDom = ExitingBlocks.back();
847 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
848 Instruction *Term = ExitingBlocks[i]->getTerminator();
849 if (isa<BranchInst>(Term) && cast<BranchInst>(Term)->isConditional()) {
850 NewIDom =
851 DT->findNearestCommonDominator(ExitingBlocks[i], Latches[i]);
852 break;
853 }
854 }
855 } else {
856 // The new idom of the block will be the nearest common dominator
857 // of all copies of the previous idom. This is equivalent to the
858 // nearest common dominator of the previous idom and the first latch,
859 // which dominates all copies of the previous idom.
860 NewIDom = DT->findNearestCommonDominator(BB, LatchBlock);
861 }
862 for (auto *ChildBB : ChildrenToUpdate)
863 DT->changeImmediateDominator(ChildBB, NewIDom);
864 }
865 }
866
867 assert(!DT || !UnrollVerifyDomtree ||
868 DT->verify(DominatorTree::VerificationLevel::Fast));
869
870 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
871 // Merge adjacent basic blocks, if possible.
872 for (BasicBlock *Latch : Latches) {
873 BranchInst *Term = dyn_cast<BranchInst>(Latch->getTerminator());
874 assert((Term ||
875 (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) &&
876 "Need a branch as terminator, except when fully unrolling with "
877 "unconditional latch");
878 if (Term && Term->isUnconditional()) {
879 BasicBlock *Dest = Term->getSuccessor(0);
880 BasicBlock *Fold = Dest->getUniquePredecessor();
881 if (MergeBlockIntoPredecessor(Dest, &DTU, LI)) {
882 // Dest has been folded into Fold. Update our worklists accordingly.
883 std::replace(Latches.begin(), Latches.end(), Dest, Fold);
884 llvm::erase_value(UnrolledLoopBlocks, Dest);
885 }
886 }
887 }
888 // Apply updates to the DomTree.
889 DT = &DTU.getDomTree();
890
891 // At this point, the code is well formed. We now simplify the unrolled loop,
892 // doing constant propagation and dead code elimination as we go.
893 simplifyLoopAfterUnroll(L, !CompletelyUnroll && (ULO.Count > 1 || Peeled), LI,
894 SE, DT, AC, TTI);
895
896 NumCompletelyUnrolled += CompletelyUnroll;
897 ++NumUnrolled;
898
899 Loop *OuterL = L->getParentLoop();
900 // Update LoopInfo if the loop is completely removed.
901 if (CompletelyUnroll)
902 LI->erase(L);
903
904 // After complete unrolling most of the blocks should be contained in OuterL.
905 // However, some of them might happen to be out of OuterL (e.g. if they
906 // precede a loop exit). In this case we might need to insert PHI nodes in
907 // order to preserve LCSSA form.
908 // We don't need to check this if we already know that we need to fix LCSSA
909 // form.
910 // TODO: For now we just recompute LCSSA for the outer loop in this case, but
911 // it should be possible to fix it in-place.
912 if (PreserveLCSSA && OuterL && CompletelyUnroll && !NeedToFixLCSSA)
913 NeedToFixLCSSA |= ::needToInsertPhisForLCSSA(OuterL, UnrolledLoopBlocks, LI);
914
915 // If we have a pass and a DominatorTree we should re-simplify impacted loops
916 // to ensure subsequent analyses can rely on this form. We want to simplify
917 // at least one layer outside of the loop that was unrolled so that any
918 // changes to the parent loop exposed by the unrolling are considered.
919 if (DT) {
920 if (OuterL) {
921 // OuterL includes all loops for which we can break loop-simplify, so
922 // it's sufficient to simplify only it (it'll recursively simplify inner
923 // loops too).
924 if (NeedToFixLCSSA) {
925 // LCSSA must be performed on the outermost affected loop. The unrolled
926 // loop's last loop latch is guaranteed to be in the outermost loop
927 // after LoopInfo's been updated by LoopInfo::erase.
928 Loop *LatchLoop = LI->getLoopFor(Latches.back());
929 Loop *FixLCSSALoop = OuterL;
930 if (!FixLCSSALoop->contains(LatchLoop))
931 while (FixLCSSALoop->getParentLoop() != LatchLoop)
932 FixLCSSALoop = FixLCSSALoop->getParentLoop();
933
934 formLCSSARecursively(*FixLCSSALoop, *DT, LI, SE);
935 } else if (PreserveLCSSA) {
936 assert(OuterL->isLCSSAForm(*DT) &&
937 "Loops should be in LCSSA form after loop-unroll.");
938 }
939
940 // TODO: That potentially might be compile-time expensive. We should try
941 // to fix the loop-simplified form incrementally.
942 simplifyLoop(OuterL, DT, LI, SE, AC, nullptr, PreserveLCSSA);
943 } else {
944 // Simplify loops for which we might've broken loop-simplify form.
945 for (Loop *SubLoop : LoopsToSimplify)
946 simplifyLoop(SubLoop, DT, LI, SE, AC, nullptr, PreserveLCSSA);
947 }
948 }
949
950 return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled
951 : LoopUnrollResult::PartiallyUnrolled;
952 }
953
954 /// Given an llvm.loop loop id metadata node, returns the loop hint metadata
955 /// node with the given name (for example, "llvm.loop.unroll.count"). If no
956 /// such metadata node exists, then nullptr is returned.
GetUnrollMetadata(MDNode * LoopID,StringRef Name)957 MDNode *llvm::GetUnrollMetadata(MDNode *LoopID, StringRef Name) {
958 // First operand should refer to the loop id itself.
959 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
960 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
961
962 for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
963 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
964 if (!MD)
965 continue;
966
967 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
968 if (!S)
969 continue;
970
971 if (Name.equals(S->getString()))
972 return MD;
973 }
974 return nullptr;
975 }
976