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/MapVector.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/ScopedHashTable.h"
23#include "llvm/ADT/SetVector.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/ADT/StringRef.h"
27#include "llvm/ADT/Twine.h"
28#include "llvm/Analysis/AliasAnalysis.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/MemorySSA.h"
35#include "llvm/Analysis/OptimizationRemarkEmitter.h"
36#include "llvm/Analysis/ScalarEvolution.h"
37#include "llvm/IR/BasicBlock.h"
38#include "llvm/IR/CFG.h"
39#include "llvm/IR/Constants.h"
40#include "llvm/IR/DebugInfoMetadata.h"
41#include "llvm/IR/DebugLoc.h"
42#include "llvm/IR/DiagnosticInfo.h"
43#include "llvm/IR/Dominators.h"
44#include "llvm/IR/Function.h"
45#include "llvm/IR/IRBuilder.h"
46#include "llvm/IR/Instruction.h"
47#include "llvm/IR/Instructions.h"
48#include "llvm/IR/IntrinsicInst.h"
49#include "llvm/IR/Metadata.h"
50#include "llvm/IR/PatternMatch.h"
51#include "llvm/IR/Use.h"
52#include "llvm/IR/User.h"
53#include "llvm/IR/ValueHandle.h"
54#include "llvm/IR/ValueMap.h"
55#include "llvm/Support/Casting.h"
56#include "llvm/Support/CommandLine.h"
57#include "llvm/Support/Debug.h"
58#include "llvm/Support/GenericDomTree.h"
59#include "llvm/Support/raw_ostream.h"
60#include "llvm/Transforms/Utils/BasicBlockUtils.h"
61#include "llvm/Transforms/Utils/Cloning.h"
62#include "llvm/Transforms/Utils/Local.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 <assert.h>
69#include <numeric>
70#include <vector>
71
72namespace llvm {
73class DataLayout;
74class Value;
75} // namespace llvm
76
77using namespace llvm;
78
79#define DEBUG_TYPE "loop-unroll"
80
81// TODO: Should these be here or in LoopUnroll?
82STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
83STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");
84STATISTIC(NumUnrolledNotLatch, "Number of loops unrolled without a conditional "
85 "latch (completely or otherwise)");
86
87static cl::opt<bool>
88UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(Val: false), cl::Hidden,
89 cl::desc("Allow runtime unrolled loops to be unrolled "
90 "with epilog instead of prolog."));
91
92static cl::opt<bool>
93UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden,
94 cl::desc("Verify domtree after unrolling"),
95#ifdef EXPENSIVE_CHECKS
96 cl::init(true)
97#else
98 cl::init(Val: false)
99#endif
100 );
101
102static cl::opt<bool>
103UnrollVerifyLoopInfo("unroll-verify-loopinfo", cl::Hidden,
104 cl::desc("Verify loopinfo after unrolling"),
105#ifdef EXPENSIVE_CHECKS
106 cl::init(true)
107#else
108 cl::init(Val: false)
109#endif
110 );
111
112static cl::opt<bool> UnrollAddParallelReductions(
113 "unroll-add-parallel-reductions", cl::init(Val: false), cl::Hidden,
114 cl::desc("Allow unrolling to add parallel reduction phis."));
115
116/// Check if unrolling created a situation where we need to insert phi nodes to
117/// preserve LCSSA form.
118/// \param Blocks is a vector of basic blocks representing unrolled loop.
119/// \param L is the outer loop.
120/// It's possible that some of the blocks are in L, and some are not. In this
121/// case, if there is a use is outside L, and definition is inside L, we need to
122/// insert a phi-node, otherwise LCSSA will be broken.
123/// The function is just a helper function for llvm::UnrollLoop that returns
124/// true if this situation occurs, indicating that LCSSA needs to be fixed.
125static bool needToInsertPhisForLCSSA(Loop *L,
126 const std::vector<BasicBlock *> &Blocks,
127 LoopInfo *LI) {
128 for (BasicBlock *BB : Blocks) {
129 if (LI->getLoopFor(BB) == L)
130 continue;
131 for (Instruction &I : *BB) {
132 for (Use &U : I.operands()) {
133 if (const auto *Def = dyn_cast<Instruction>(Val&: U)) {
134 Loop *DefLoop = LI->getLoopFor(BB: Def->getParent());
135 if (!DefLoop)
136 continue;
137 if (DefLoop->contains(L))
138 return true;
139 }
140 }
141 }
142 }
143 return false;
144}
145
146/// Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary
147/// and adds a mapping from the original loop to the new loop to NewLoops.
148/// Returns nullptr if no new loop was created and a pointer to the
149/// original loop OriginalBB was part of otherwise.
150const Loop* llvm::addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
151 BasicBlock *ClonedBB, LoopInfo *LI,
152 NewLoopsMap &NewLoops) {
153 // Figure out which loop New is in.
154 const Loop *OldLoop = LI->getLoopFor(BB: OriginalBB);
155 assert(OldLoop && "Should (at least) be in the loop being unrolled!");
156
157 Loop *&NewLoop = NewLoops[OldLoop];
158 if (!NewLoop) {
159 // Found a new sub-loop.
160 assert(OriginalBB == OldLoop->getHeader() &&
161 "Header should be first in RPO");
162
163 NewLoop = LI->AllocateLoop();
164 Loop *NewLoopParent = NewLoops.lookup(Val: OldLoop->getParentLoop());
165
166 if (NewLoopParent)
167 NewLoopParent->addChildLoop(NewChild: NewLoop);
168 else
169 LI->addTopLevelLoop(New: NewLoop);
170
171 NewLoop->addBasicBlockToLoop(NewBB: ClonedBB, LI&: *LI);
172 return OldLoop;
173 } else {
174 NewLoop->addBasicBlockToLoop(NewBB: ClonedBB, LI&: *LI);
175 return nullptr;
176 }
177}
178
179/// The function chooses which type of unroll (epilog or prolog) is more
180/// profitabale.
181/// Epilog unroll is more profitable when there is PHI that starts from
182/// constant. In this case epilog will leave PHI start from constant,
183/// but prolog will convert it to non-constant.
184///
185/// loop:
186/// PN = PHI [I, Latch], [CI, PreHeader]
187/// I = foo(PN)
188/// ...
189///
190/// Epilog unroll case.
191/// loop:
192/// PN = PHI [I2, Latch], [CI, PreHeader]
193/// I1 = foo(PN)
194/// I2 = foo(I1)
195/// ...
196/// Prolog unroll case.
197/// NewPN = PHI [PrologI, Prolog], [CI, PreHeader]
198/// loop:
199/// PN = PHI [I2, Latch], [NewPN, PreHeader]
200/// I1 = foo(PN)
201/// I2 = foo(I1)
202/// ...
203///
204static bool isEpilogProfitable(Loop *L) {
205 BasicBlock *PreHeader = L->getLoopPreheader();
206 BasicBlock *Header = L->getHeader();
207 assert(PreHeader && Header);
208 for (const PHINode &PN : Header->phis()) {
209 if (isa<ConstantInt>(Val: PN.getIncomingValueForBlock(BB: PreHeader)))
210 return true;
211 }
212 return false;
213}
214
215struct LoadValue {
216 Instruction *DefI = nullptr;
217 unsigned Generation = 0;
218 LoadValue() = default;
219 LoadValue(Instruction *Inst, unsigned Generation)
220 : DefI(Inst), Generation(Generation) {}
221};
222
223class StackNode {
224 ScopedHashTable<const SCEV *, LoadValue>::ScopeTy LoadScope;
225 unsigned CurrentGeneration;
226 unsigned ChildGeneration;
227 DomTreeNode *Node;
228 DomTreeNode::const_iterator ChildIter;
229 DomTreeNode::const_iterator EndIter;
230 bool Processed = false;
231
232public:
233 StackNode(ScopedHashTable<const SCEV *, LoadValue> &AvailableLoads,
234 unsigned cg, DomTreeNode *N, DomTreeNode::const_iterator Child,
235 DomTreeNode::const_iterator End)
236 : LoadScope(AvailableLoads), CurrentGeneration(cg), ChildGeneration(cg),
237 Node(N), ChildIter(Child), EndIter(End) {}
238 // Accessors.
239 unsigned currentGeneration() const { return CurrentGeneration; }
240 unsigned childGeneration() const { return ChildGeneration; }
241 void childGeneration(unsigned generation) { ChildGeneration = generation; }
242 DomTreeNode *node() { return Node; }
243 DomTreeNode::const_iterator childIter() const { return ChildIter; }
244
245 DomTreeNode *nextChild() {
246 DomTreeNode *Child = *ChildIter;
247 ++ChildIter;
248 return Child;
249 }
250
251 DomTreeNode::const_iterator end() const { return EndIter; }
252 bool isProcessed() const { return Processed; }
253 void process() { Processed = true; }
254};
255
256Value *getMatchingValue(LoadValue LV, LoadInst *LI, unsigned CurrentGeneration,
257 BatchAAResults &BAA,
258 function_ref<MemorySSA *()> GetMSSA) {
259 if (!LV.DefI)
260 return nullptr;
261 if (LV.DefI->getType() != LI->getType())
262 return nullptr;
263 if (LV.Generation != CurrentGeneration) {
264 MemorySSA *MSSA = GetMSSA();
265 if (!MSSA)
266 return nullptr;
267 auto *EarlierMA = MSSA->getMemoryAccess(I: LV.DefI);
268 MemoryAccess *LaterDef =
269 MSSA->getWalker()->getClobberingMemoryAccess(I: LI, AA&: BAA);
270 if (!MSSA->dominates(A: LaterDef, B: EarlierMA))
271 return nullptr;
272 }
273 return LV.DefI;
274}
275
276void loadCSE(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI,
277 BatchAAResults &BAA, function_ref<MemorySSA *()> GetMSSA) {
278 ScopedHashTable<const SCEV *, LoadValue> AvailableLoads;
279 SmallVector<std::unique_ptr<StackNode>> NodesToProcess;
280 DomTreeNode *HeaderD = DT.getNode(BB: L->getHeader());
281 NodesToProcess.emplace_back(Args: new StackNode(AvailableLoads, 0, HeaderD,
282 HeaderD->begin(), HeaderD->end()));
283
284 unsigned CurrentGeneration = 0;
285 while (!NodesToProcess.empty()) {
286 StackNode *NodeToProcess = &*NodesToProcess.back();
287
288 CurrentGeneration = NodeToProcess->currentGeneration();
289
290 if (!NodeToProcess->isProcessed()) {
291 // Process the node.
292
293 // If this block has a single predecessor, then the predecessor is the
294 // parent
295 // of the domtree node and all of the live out memory values are still
296 // current in this block. If this block has multiple predecessors, then
297 // they could have invalidated the live-out memory values of our parent
298 // value. For now, just be conservative and invalidate memory if this
299 // block has multiple predecessors.
300 if (!NodeToProcess->node()->getBlock()->getSinglePredecessor())
301 ++CurrentGeneration;
302 for (auto &I : make_early_inc_range(Range&: *NodeToProcess->node()->getBlock())) {
303
304 auto *Load = dyn_cast<LoadInst>(Val: &I);
305 if (!Load || !Load->isSimple()) {
306 if (I.mayWriteToMemory())
307 CurrentGeneration++;
308 continue;
309 }
310
311 const SCEV *PtrSCEV = SE.getSCEV(V: Load->getPointerOperand());
312 LoadValue LV = AvailableLoads.lookup(Key: PtrSCEV);
313 if (Value *M =
314 getMatchingValue(LV, LI: Load, CurrentGeneration, BAA, GetMSSA)) {
315 if (LI.replacementPreservesLCSSAForm(From: Load, To: M)) {
316 Load->replaceAllUsesWith(V: M);
317 Load->eraseFromParent();
318 }
319 } else {
320 AvailableLoads.insert(Key: PtrSCEV, Val: LoadValue(Load, CurrentGeneration));
321 }
322 }
323 NodeToProcess->childGeneration(generation: CurrentGeneration);
324 NodeToProcess->process();
325 } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
326 // Push the next child onto the stack.
327 DomTreeNode *Child = NodeToProcess->nextChild();
328 if (!L->contains(BB: Child->getBlock()))
329 continue;
330 NodesToProcess.emplace_back(
331 Args: new StackNode(AvailableLoads, NodeToProcess->childGeneration(), Child,
332 Child->begin(), Child->end()));
333 } else {
334 // It has been processed, and there are no more children to process,
335 // so delete it and pop it off the stack.
336 NodesToProcess.pop_back();
337 }
338 }
339}
340
341/// Perform some cleanup and simplifications on loops after unrolling. It is
342/// useful to simplify the IV's in the new loop, as well as do a quick
343/// simplify/dce pass of the instructions.
344void llvm::simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
345 ScalarEvolution *SE, DominatorTree *DT,
346 AssumptionCache *AC,
347 const TargetTransformInfo *TTI,
348 AAResults *AA) {
349 using namespace llvm::PatternMatch;
350
351 // Simplify any new induction variables in the partially unrolled loop.
352 if (SE && SimplifyIVs) {
353 SmallVector<WeakTrackingVH, 16> DeadInsts;
354 simplifyLoopIVs(L, SE, DT, LI, TTI, Dead&: DeadInsts);
355
356 // Aggressively clean up dead instructions that simplifyLoopIVs already
357 // identified. Any remaining should be cleaned up below.
358 while (!DeadInsts.empty()) {
359 Value *V = DeadInsts.pop_back_val();
360 if (Instruction *Inst = dyn_cast_or_null<Instruction>(Val: V))
361 RecursivelyDeleteTriviallyDeadInstructions(V: Inst);
362 }
363
364 if (AA) {
365 std::unique_ptr<MemorySSA> MSSA = nullptr;
366 BatchAAResults BAA(*AA);
367 loadCSE(L, DT&: *DT, SE&: *SE, LI&: *LI, BAA, GetMSSA: [L, AA, DT, &MSSA]() -> MemorySSA * {
368 if (!MSSA)
369 MSSA.reset(p: new MemorySSA(*L, AA, DT));
370 return &*MSSA;
371 });
372 }
373 }
374
375 // At this point, the code is well formed. Perform constprop, instsimplify,
376 // and dce.
377 const DataLayout &DL = L->getHeader()->getDataLayout();
378 SmallVector<WeakTrackingVH, 16> DeadInsts;
379 for (BasicBlock *BB : L->getBlocks()) {
380 // Remove repeated debug instructions after loop unrolling.
381 if (BB->getParent()->getSubprogram())
382 RemoveRedundantDbgInstrs(BB);
383
384 for (Instruction &Inst : llvm::make_early_inc_range(Range&: *BB)) {
385 if (Value *V = simplifyInstruction(I: &Inst, Q: {DL, nullptr, DT, AC}))
386 if (LI->replacementPreservesLCSSAForm(From: &Inst, To: V))
387 Inst.replaceAllUsesWith(V);
388 if (isInstructionTriviallyDead(I: &Inst))
389 DeadInsts.emplace_back(Args: &Inst);
390
391 // Fold ((add X, C1), C2) to (add X, C1+C2). This is very common in
392 // unrolled loops, and handling this early allows following code to
393 // identify the IV as a "simple recurrence" without first folding away
394 // a long chain of adds.
395 {
396 Value *X;
397 const APInt *C1, *C2;
398 if (match(V: &Inst, P: m_Add(L: m_Add(L: m_Value(V&: X), R: m_APInt(Res&: C1)), R: m_APInt(Res&: C2)))) {
399 auto *InnerI = dyn_cast<Instruction>(Val: Inst.getOperand(i: 0));
400 auto *InnerOBO = cast<OverflowingBinaryOperator>(Val: Inst.getOperand(i: 0));
401 bool SignedOverflow;
402 APInt NewC = C1->sadd_ov(RHS: *C2, Overflow&: SignedOverflow);
403 Inst.setOperand(i: 0, Val: X);
404 Inst.setOperand(i: 1, Val: ConstantInt::get(Ty: Inst.getType(), V: NewC));
405 Inst.setHasNoUnsignedWrap(Inst.hasNoUnsignedWrap() &&
406 InnerOBO->hasNoUnsignedWrap());
407 Inst.setHasNoSignedWrap(Inst.hasNoSignedWrap() &&
408 InnerOBO->hasNoSignedWrap() &&
409 !SignedOverflow);
410 if (InnerI && isInstructionTriviallyDead(I: InnerI))
411 DeadInsts.emplace_back(Args&: InnerI);
412 }
413 }
414 }
415 // We can't do recursive deletion until we're done iterating, as we might
416 // have a phi which (potentially indirectly) uses instructions later in
417 // the block we're iterating through.
418 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);
419 }
420}
421
422// Loops containing convergent instructions that are uncontrolled or controlled
423// from outside the loop must have a count that divides their TripMultiple.
424LLVM_ATTRIBUTE_USED
425static bool canHaveUnrollRemainder(const Loop *L) {
426 if (getLoopConvergenceHeart(TheLoop: L))
427 return false;
428
429 // Check for uncontrolled convergent operations.
430 for (auto &BB : L->blocks()) {
431 for (auto &I : *BB) {
432 if (isa<ConvergenceControlInst>(Val: I))
433 return true;
434 if (auto *CB = dyn_cast<CallBase>(Val: &I))
435 if (CB->isConvergent())
436 return CB->getConvergenceControlToken();
437 }
438 }
439 return true;
440}
441
442/// Unroll the given loop by Count. The loop must be in LCSSA form. Unrolling
443/// can only fail when the loop's latch block is not terminated by a conditional
444/// branch instruction. However, if the trip count (and multiple) are not known,
445/// loop unrolling will mostly produce more code that is no faster.
446///
447/// If Runtime is true then UnrollLoop will try to insert a prologue or
448/// epilogue that ensures the latch has a trip multiple of Count. UnrollLoop
449/// will not runtime-unroll the loop if computing the run-time trip count will
450/// be expensive and AllowExpensiveTripCount is false.
451///
452/// The LoopInfo Analysis that is passed will be kept consistent.
453///
454/// This utility preserves LoopInfo. It will also preserve ScalarEvolution and
455/// DominatorTree if they are non-null.
456///
457/// If RemainderLoop is non-null, it will receive the remainder loop (if
458/// required and not fully unrolled).
459LoopUnrollResult
460llvm::UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
461 ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,
462 const TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE,
463 bool PreserveLCSSA, Loop **RemainderLoop, AAResults *AA) {
464 assert(DT && "DomTree is required");
465
466 if (!L->getLoopPreheader()) {
467 LLVM_DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n");
468 return LoopUnrollResult::Unmodified;
469 }
470
471 if (!L->getLoopLatch()) {
472 LLVM_DEBUG(dbgs() << " Can't unroll; loop exit-block-insertion failed.\n");
473 return LoopUnrollResult::Unmodified;
474 }
475
476 // Loops with indirectbr cannot be cloned.
477 if (!L->isSafeToClone()) {
478 LLVM_DEBUG(dbgs() << " Can't unroll; Loop body cannot be cloned.\n");
479 return LoopUnrollResult::Unmodified;
480 }
481
482 if (L->getHeader()->hasAddressTaken()) {
483 // The loop-rotate pass can be helpful to avoid this in many cases.
484 LLVM_DEBUG(
485 dbgs() << " Won't unroll loop: address of header block is taken.\n");
486 return LoopUnrollResult::Unmodified;
487 }
488
489 assert(ULO.Count > 0);
490
491 // All these values should be taken only after peeling because they might have
492 // changed.
493 BasicBlock *Preheader = L->getLoopPreheader();
494 BasicBlock *Header = L->getHeader();
495 BasicBlock *LatchBlock = L->getLoopLatch();
496 SmallVector<BasicBlock *, 4> ExitBlocks;
497 L->getExitBlocks(ExitBlocks);
498 std::vector<BasicBlock *> OriginalLoopBlocks = L->getBlocks();
499
500 const unsigned MaxTripCount = SE->getSmallConstantMaxTripCount(L);
501 const bool MaxOrZero = SE->isBackedgeTakenCountMaxOrZero(L);
502 std::optional<unsigned> OriginalTripCount =
503 llvm::getLoopEstimatedTripCount(L);
504 BranchProbability OriginalLoopProb = llvm::getLoopProbability(L);
505
506 // Effectively "DCE" unrolled iterations that are beyond the max tripcount
507 // and will never be executed.
508 if (MaxTripCount && ULO.Count > MaxTripCount)
509 ULO.Count = MaxTripCount;
510
511 struct ExitInfo {
512 unsigned TripCount;
513 unsigned TripMultiple;
514 unsigned BreakoutTrip;
515 bool ExitOnTrue;
516 BasicBlock *FirstExitingBlock = nullptr;
517 SmallVector<BasicBlock *> ExitingBlocks;
518 };
519 MapVector<BasicBlock *, ExitInfo> ExitInfos;
520 SmallVector<BasicBlock *, 4> ExitingBlocks;
521 L->getExitingBlocks(ExitingBlocks);
522 for (auto *ExitingBlock : ExitingBlocks) {
523 // The folding code is not prepared to deal with non-branch instructions
524 // right now.
525 auto *BI = dyn_cast<CondBrInst>(Val: ExitingBlock->getTerminator());
526 if (!BI)
527 continue;
528
529 ExitInfo &Info = ExitInfos[ExitingBlock];
530 Info.TripCount = SE->getSmallConstantTripCount(L, ExitingBlock);
531 Info.TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock);
532 if (Info.TripCount != 0) {
533 Info.BreakoutTrip = Info.TripCount % ULO.Count;
534 Info.TripMultiple = 0;
535 } else {
536 Info.BreakoutTrip = Info.TripMultiple =
537 (unsigned)std::gcd(m: ULO.Count, n: Info.TripMultiple);
538 }
539 Info.ExitOnTrue = !L->contains(BB: BI->getSuccessor(i: 0));
540 Info.ExitingBlocks.push_back(Elt: ExitingBlock);
541 LLVM_DEBUG(dbgs() << " Exiting block %" << ExitingBlock->getName()
542 << ": TripCount=" << Info.TripCount
543 << ", TripMultiple=" << Info.TripMultiple
544 << ", BreakoutTrip=" << Info.BreakoutTrip << "\n");
545 }
546
547 // Are we eliminating the loop control altogether? Note that we can know
548 // we're eliminating the backedge without knowing exactly which iteration
549 // of the unrolled body exits.
550 const bool CompletelyUnroll = ULO.Count == MaxTripCount;
551
552 const bool PreserveOnlyFirst = CompletelyUnroll && MaxOrZero;
553
554 // There's no point in performing runtime unrolling if this unroll count
555 // results in a full unroll.
556 if (CompletelyUnroll)
557 ULO.Runtime = false;
558
559 // Go through all exits of L and see if there are any phi-nodes there. We just
560 // conservatively assume that they're inserted to preserve LCSSA form, which
561 // means that complete unrolling might break this form. We need to either fix
562 // it in-place after the transformation, or entirely rebuild LCSSA. TODO: For
563 // now we just recompute LCSSA for the outer loop, but it should be possible
564 // to fix it in-place.
565 bool NeedToFixLCSSA =
566 PreserveLCSSA && CompletelyUnroll &&
567 any_of(Range&: ExitBlocks,
568 P: [](const BasicBlock *BB) { return isa<PHINode>(Val: BB->begin()); });
569
570 // The current loop unroll pass can unroll loops that have
571 // (1) single latch; and
572 // (2a) latch is unconditional; or
573 // (2b) latch is conditional and is an exiting block
574 // FIXME: The implementation can be extended to work with more complicated
575 // cases, e.g. loops with multiple latches.
576 Instruction *LatchTerm = LatchBlock->getTerminator();
577
578 // A conditional branch which exits the loop, which can be optimized to an
579 // unconditional branch in the unrolled loop in some cases.
580 bool LatchIsExiting = L->isLoopExiting(BB: LatchBlock);
581 if (!isa<UncondBrInst>(Val: LatchTerm) &&
582 !(isa<CondBrInst>(Val: LatchTerm) && LatchIsExiting)) {
583 LLVM_DEBUG(
584 dbgs() << "Can't unroll; a conditional latch must exit the loop");
585 return LoopUnrollResult::Unmodified;
586 }
587
588 assert((!ULO.Runtime || canHaveUnrollRemainder(L)) &&
589 "Can't runtime unroll if loop contains a convergent operation.");
590
591 bool EpilogProfitability =
592 UnrollRuntimeEpilog.getNumOccurrences() ? UnrollRuntimeEpilog
593 : isEpilogProfitable(L);
594
595 if (ULO.Runtime &&
596 !UnrollRuntimeLoopRemainder(
597 L, Count: ULO.Count, AllowExpensiveTripCount: ULO.AllowExpensiveTripCount, UseEpilogRemainder: EpilogProfitability,
598 UnrollRemainder: ULO.UnrollRemainder, ForgetAllSCEV: ULO.ForgetAllSCEV, LI, SE, DT, AC, TTI,
599 PreserveLCSSA, SCEVExpansionBudget: ULO.SCEVExpansionBudget, RuntimeUnrollMultiExit: ULO.RuntimeUnrollMultiExit,
600 ResultLoop: RemainderLoop, OriginalTripCount, OriginalLoopProb)) {
601 if (ULO.Force)
602 ULO.Runtime = false;
603 else {
604 LLVM_DEBUG(dbgs() << "Won't unroll; remainder loop could not be "
605 "generated when assuming runtime trip count\n");
606 return LoopUnrollResult::Unmodified;
607 }
608 }
609
610 using namespace ore;
611 // Report the unrolling decision.
612 if (CompletelyUnroll) {
613 LLVM_DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()
614 << " with trip count " << ULO.Count << "!\n");
615 if (ORE)
616 ORE->emit(RemarkBuilder: [&]() {
617 return OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(),
618 L->getHeader())
619 << "completely unrolled loop with "
620 << NV("UnrollCount", ULO.Count) << " iterations";
621 });
622 } else {
623 LLVM_DEBUG(dbgs() << "UNROLLING loop %" << Header->getName() << " by "
624 << ULO.Count);
625 if (ULO.Runtime)
626 LLVM_DEBUG(dbgs() << " with run-time trip count");
627 LLVM_DEBUG(dbgs() << "!\n");
628
629 if (ORE)
630 ORE->emit(RemarkBuilder: [&]() {
631 OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled", L->getStartLoc(),
632 L->getHeader());
633 Diag << "unrolled loop by a factor of " << NV("UnrollCount", ULO.Count);
634 if (ULO.Runtime)
635 Diag << " with run-time trip count";
636 return Diag;
637 });
638 }
639
640 // We are going to make changes to this loop. SCEV may be keeping cached info
641 // about it, in particular about backedge taken count. The changes we make
642 // are guaranteed to invalidate this information for our loop. It is tempting
643 // to only invalidate the loop being unrolled, but it is incorrect as long as
644 // all exiting branches from all inner loops have impact on the outer loops,
645 // and if something changes inside them then any of outer loops may also
646 // change. When we forget outermost loop, we also forget all contained loops
647 // and this is what we need here.
648 if (SE) {
649 if (ULO.ForgetAllSCEV)
650 SE->forgetAllLoops();
651 else {
652 SE->forgetTopmostLoop(L);
653 SE->forgetBlockAndLoopDispositions();
654 }
655 }
656
657 if (!LatchIsExiting)
658 ++NumUnrolledNotLatch;
659
660 // For the first iteration of the loop, we should use the precloned values for
661 // PHI nodes. Insert associations now.
662 ValueToValueMapTy LastValueMap;
663 std::vector<PHINode*> OrigPHINode;
664 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(Val: I); ++I) {
665 OrigPHINode.push_back(x: cast<PHINode>(Val&: I));
666 }
667
668 // Collect phi nodes for reductions for which we can introduce multiple
669 // parallel reduction phis and compute the final reduction result after the
670 // loop. This requires a single exit block after unrolling. This is ensured by
671 // restricting to single-block loops where the unrolled iterations are known
672 // to not exit.
673 DenseMap<PHINode *, RecurrenceDescriptor> Reductions;
674 bool CanAddAdditionalAccumulators =
675 (UnrollAddParallelReductions.getNumOccurrences() > 0
676 ? UnrollAddParallelReductions
677 : ULO.AddAdditionalAccumulators) &&
678 !CompletelyUnroll && L->getNumBlocks() == 1 &&
679 (ULO.Runtime ||
680 (ExitInfos.contains(Key: Header) && ((ExitInfos[Header].TripCount != 0 &&
681 ExitInfos[Header].BreakoutTrip == 0))));
682
683 // Limit parallelizing reductions to unroll counts of 4 or less for now.
684 // TODO: The number of parallel reductions should depend on the number of
685 // execution units. We also don't have to add a parallel reduction phi per
686 // unrolled iteration, but could for example add a parallel phi for every 2
687 // unrolled iterations.
688 if (CanAddAdditionalAccumulators && ULO.Count <= 4) {
689 for (PHINode &Phi : Header->phis()) {
690 auto RdxDesc = canParallelizeReductionWhenUnrolling(Phi, L, SE);
691 if (!RdxDesc)
692 continue;
693
694 // Only handle duplicate phis for a single reduction for now.
695 // TODO: Handle any number of reductions
696 if (!Reductions.empty())
697 continue;
698
699 Reductions[&Phi] = *RdxDesc;
700 }
701 }
702
703 std::vector<BasicBlock *> Headers;
704 std::vector<BasicBlock *> Latches;
705 Headers.push_back(x: Header);
706 Latches.push_back(x: LatchBlock);
707
708 // The current on-the-fly SSA update requires blocks to be processed in
709 // reverse postorder so that LastValueMap contains the correct value at each
710 // exit.
711 LoopBlocksDFS DFS(L);
712 DFS.perform(LI);
713
714 // Stash the DFS iterators before adding blocks to the loop.
715 LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();
716 LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();
717
718 std::vector<BasicBlock*> UnrolledLoopBlocks = L->getBlocks();
719
720 // Loop Unrolling might create new loops. While we do preserve LoopInfo, we
721 // might break loop-simplified form for these loops (as they, e.g., would
722 // share the same exit blocks). We'll keep track of loops for which we can
723 // break this so that later we can re-simplify them.
724 SmallSetVector<Loop *, 4> LoopsToSimplify;
725 LoopsToSimplify.insert_range(R&: *L);
726
727 // When a FSDiscriminator is enabled, we don't need to add the multiply
728 // factors to the discriminators.
729 if (Header->getParent()->shouldEmitDebugInfoForProfiling() &&
730 !EnableFSDiscriminator)
731 for (BasicBlock *BB : L->getBlocks())
732 for (Instruction &I : *BB)
733 if (!I.isDebugOrPseudoInst())
734 if (const DILocation *DIL = I.getDebugLoc()) {
735 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(DF: ULO.Count);
736 if (NewDIL)
737 I.setDebugLoc(*NewDIL);
738 else
739 LLVM_DEBUG(dbgs()
740 << "Failed to create new discriminator: "
741 << DIL->getFilename() << " Line: " << DIL->getLine());
742 }
743
744 // Identify what noalias metadata is inside the loop: if it is inside the
745 // loop, the associated metadata must be cloned for each iteration.
746 SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;
747 identifyNoAliasScopesToClone(BBs: L->getBlocks(), NoAliasDeclScopes&: LoopLocalNoAliasDeclScopes);
748
749 // We place the unrolled iterations immediately after the original loop
750 // latch. This is a reasonable default placement if we don't have block
751 // frequencies, and if we do, well the layout will be adjusted later.
752 auto BlockInsertPt = std::next(x: LatchBlock->getIterator());
753 SmallVector<Instruction *> PartialReductions;
754 for (unsigned It = 1; It != ULO.Count; ++It) {
755 SmallVector<BasicBlock *, 8> NewBlocks;
756 SmallDenseMap<const Loop *, Loop *, 4> NewLoops;
757 NewLoops[L] = L;
758
759 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
760 ValueToValueMapTy VMap;
761 BasicBlock *New = CloneBasicBlock(BB: *BB, VMap, NameSuffix: "." + Twine(It));
762 Header->getParent()->insert(Position: BlockInsertPt, BB: New);
763
764 assert((*BB != Header || LI->getLoopFor(*BB) == L) &&
765 "Header should not be in a sub-loop");
766 // Tell LI about New.
767 const Loop *OldLoop = addClonedBlockToLoopInfo(OriginalBB: *BB, ClonedBB: New, LI, NewLoops);
768 if (OldLoop)
769 LoopsToSimplify.insert(X: NewLoops[OldLoop]);
770
771 if (*BB == Header) {
772 // Loop over all of the PHI nodes in the block, changing them to use
773 // the incoming values from the previous block.
774 for (PHINode *OrigPHI : OrigPHINode) {
775 PHINode *NewPHI = cast<PHINode>(Val&: VMap[OrigPHI]);
776 Value *InVal = NewPHI->getIncomingValueForBlock(BB: LatchBlock);
777
778 // Use cloned phis as parallel phis for partial reductions, which will
779 // get combined to the final reduction result after the loop.
780 if (Reductions.contains(Val: OrigPHI)) {
781 // Collect partial reduction results.
782 if (PartialReductions.empty())
783 PartialReductions.push_back(Elt: cast<Instruction>(Val: InVal));
784 PartialReductions.push_back(Elt: cast<Instruction>(Val&: VMap[InVal]));
785
786 // Update the start value for the cloned phis to use the identity
787 // value for the reduction.
788 const RecurrenceDescriptor &RdxDesc = Reductions[OrigPHI];
789 NewPHI->setIncomingValueForBlock(
790 BB: L->getLoopPreheader(),
791 V: getRecurrenceIdentity(K: RdxDesc.getRecurrenceKind(),
792 Tp: OrigPHI->getType(),
793 FMF: RdxDesc.getFastMathFlags()));
794
795 // Update NewPHI to use the cloned value for the iteration and move
796 // to header.
797 NewPHI->replaceUsesOfWith(From: InVal, To: VMap[InVal]);
798 NewPHI->moveBefore(InsertPos: OrigPHI->getIterator());
799 continue;
800 }
801
802 if (Instruction *InValI = dyn_cast<Instruction>(Val: InVal))
803 if (It > 1 && L->contains(Inst: InValI))
804 InVal = LastValueMap[InValI];
805 VMap[OrigPHI] = InVal;
806 NewPHI->eraseFromParent();
807 }
808
809 // Eliminate copies of the loop heart intrinsic, if any.
810 if (ULO.Heart) {
811 auto it = VMap.find(Val: ULO.Heart);
812 assert(it != VMap.end());
813 Instruction *heartCopy = cast<Instruction>(Val&: it->second);
814 heartCopy->eraseFromParent();
815 VMap.erase(I: it);
816 }
817 }
818
819 // Remap source location atom instance. Do this now, rather than
820 // when we remap instructions, because remap is called once we've
821 // cloned all blocks (all the clones would get the same atom
822 // number).
823 if (!VMap.AtomMap.empty())
824 for (Instruction &I : *New)
825 RemapSourceAtom(I: &I, VM&: VMap);
826
827 // Update our running map of newest clones
828 LastValueMap[*BB] = New;
829 for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();
830 VI != VE; ++VI)
831 LastValueMap[VI->first] = VI->second;
832
833 // Add phi entries for newly created values to all exit blocks.
834 for (BasicBlock *Succ : successors(BB: *BB)) {
835 if (L->contains(BB: Succ))
836 continue;
837 for (PHINode &PHI : Succ->phis()) {
838 Value *Incoming = PHI.getIncomingValueForBlock(BB: *BB);
839 ValueToValueMapTy::iterator It = LastValueMap.find(Val: Incoming);
840 if (It != LastValueMap.end())
841 Incoming = It->second;
842 PHI.addIncoming(V: Incoming, BB: New);
843 SE->forgetLcssaPhiWithNewPredecessor(L, V: &PHI);
844 }
845 }
846 // Keep track of new headers and latches as we create them, so that
847 // we can insert the proper branches later.
848 if (*BB == Header)
849 Headers.push_back(x: New);
850 if (*BB == LatchBlock)
851 Latches.push_back(x: New);
852
853 // Keep track of the exiting block and its successor block contained in
854 // the loop for the current iteration.
855 auto ExitInfoIt = ExitInfos.find(Key: *BB);
856 if (ExitInfoIt != ExitInfos.end())
857 ExitInfoIt->second.ExitingBlocks.push_back(Elt: New);
858
859 NewBlocks.push_back(Elt: New);
860 UnrolledLoopBlocks.push_back(x: New);
861
862 // Update DomTree: since we just copy the loop body, and each copy has a
863 // dedicated entry block (copy of the header block), this header's copy
864 // dominates all copied blocks. That means, dominance relations in the
865 // copied body are the same as in the original body.
866 if (*BB == Header)
867 DT->addNewBlock(BB: New, DomBB: Latches[It - 1]);
868 else {
869 auto BBDomNode = DT->getNode(BB: *BB);
870 auto BBIDom = BBDomNode->getIDom();
871 BasicBlock *OriginalBBIDom = BBIDom->getBlock();
872 DT->addNewBlock(
873 BB: New, DomBB: cast<BasicBlock>(Val&: LastValueMap[cast<Value>(Val: OriginalBBIDom)]));
874 }
875 }
876
877 // Remap all instructions in the most recent iteration.
878 // Key Instructions: Nothing to do - we've already remapped the atoms.
879 remapInstructionsInBlocks(Blocks: NewBlocks, VMap&: LastValueMap);
880 for (BasicBlock *NewBlock : NewBlocks)
881 for (Instruction &I : *NewBlock)
882 if (auto *II = dyn_cast<AssumeInst>(Val: &I))
883 AC->registerAssumption(CI: II);
884
885 {
886 // Identify what other metadata depends on the cloned version. After
887 // cloning, replace the metadata with the corrected version for both
888 // memory instructions and noalias intrinsics.
889 std::string ext = (Twine("It") + Twine(It)).str();
890 cloneAndAdaptNoAliasScopes(NoAliasDeclScopes: LoopLocalNoAliasDeclScopes, NewBlocks,
891 Context&: Header->getContext(), Ext: ext);
892 }
893 }
894
895 // Loop over the PHI nodes in the original block, setting incoming values.
896 for (PHINode *PN : OrigPHINode) {
897 if (CompletelyUnroll) {
898 PN->replaceAllUsesWith(V: PN->getIncomingValueForBlock(BB: Preheader));
899 PN->eraseFromParent();
900 } else if (ULO.Count > 1) {
901 if (Reductions.contains(Val: PN))
902 continue;
903
904 Value *InVal = PN->removeIncomingValue(BB: LatchBlock, DeletePHIIfEmpty: false);
905 // If this value was defined in the loop, take the value defined by the
906 // last iteration of the loop.
907 if (Instruction *InValI = dyn_cast<Instruction>(Val: InVal)) {
908 if (L->contains(Inst: InValI))
909 InVal = LastValueMap[InVal];
910 }
911 assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch");
912 PN->addIncoming(V: InVal, BB: Latches.back());
913 }
914 }
915
916 // Connect latches of the unrolled iterations to the headers of the next
917 // iteration. Currently they point to the header of the same iteration.
918 for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
919 unsigned j = (i + 1) % e;
920 Latches[i]->getTerminator()->replaceSuccessorWith(OldBB: Headers[i], NewBB: Headers[j]);
921 }
922
923 // Remove loop metadata copied from the original loop latch to branches that
924 // are no longer latches.
925 for (unsigned I = 0, E = Latches.size() - (CompletelyUnroll ? 0 : 1); I < E;
926 ++I)
927 Latches[I]->getTerminator()->setMetadata(KindID: LLVMContext::MD_loop, Node: nullptr);
928
929 // Update dominators of blocks we might reach through exits.
930 // Immediate dominator of such block might change, because we add more
931 // routes which can lead to the exit: we can now reach it from the copied
932 // iterations too.
933 if (ULO.Count > 1) {
934 for (auto *BB : OriginalLoopBlocks) {
935 auto *BBDomNode = DT->getNode(BB);
936 SmallVector<BasicBlock *, 16> ChildrenToUpdate;
937 for (auto *ChildDomNode : BBDomNode->children()) {
938 auto *ChildBB = ChildDomNode->getBlock();
939 if (!L->contains(BB: ChildBB))
940 ChildrenToUpdate.push_back(Elt: ChildBB);
941 }
942 // The new idom of the block will be the nearest common dominator
943 // of all copies of the previous idom. This is equivalent to the
944 // nearest common dominator of the previous idom and the first latch,
945 // which dominates all copies of the previous idom.
946 BasicBlock *NewIDom = DT->findNearestCommonDominator(A: BB, B: LatchBlock);
947 for (auto *ChildBB : ChildrenToUpdate)
948 DT->changeImmediateDominator(BB: ChildBB, NewBB: NewIDom);
949 }
950 }
951
952 assert(!UnrollVerifyDomtree ||
953 DT->verify(DominatorTree::VerificationLevel::Fast));
954
955 SmallVector<DominatorTree::UpdateType> DTUpdates;
956 auto SetDest = [&](BasicBlock *Src, bool WillExit, bool ExitOnTrue) {
957 auto *Term = cast<CondBrInst>(Val: Src->getTerminator());
958 const unsigned Idx = ExitOnTrue ^ WillExit;
959 BasicBlock *Dest = Term->getSuccessor(i: Idx);
960 BasicBlock *DeadSucc = Term->getSuccessor(i: 1-Idx);
961
962 // Remove predecessors from all non-Dest successors.
963 DeadSucc->removePredecessor(Pred: Src, /* KeepOneInputPHIs */ true);
964
965 // Replace the conditional branch with an unconditional one.
966 auto *BI = UncondBrInst::Create(Target: Dest, InsertBefore: Term->getIterator());
967 BI->setDebugLoc(Term->getDebugLoc());
968 Term->eraseFromParent();
969
970 DTUpdates.emplace_back(Args: DominatorTree::Delete, Args&: Src, Args&: DeadSucc);
971 };
972
973 auto WillExit = [&](const ExitInfo &Info, unsigned i, unsigned j,
974 bool IsLatch) -> std::optional<bool> {
975 if (CompletelyUnroll) {
976 if (PreserveOnlyFirst) {
977 if (i == 0)
978 return std::nullopt;
979 return j == 0;
980 }
981 // Complete (but possibly inexact) unrolling
982 if (j == 0)
983 return true;
984 if (Info.TripCount && j != Info.TripCount)
985 return false;
986 return std::nullopt;
987 }
988
989 if (ULO.Runtime) {
990 // If runtime unrolling inserts a prologue, information about non-latch
991 // exits may be stale.
992 if (IsLatch && j != 0)
993 return false;
994 return std::nullopt;
995 }
996
997 if (j != Info.BreakoutTrip &&
998 (Info.TripMultiple == 0 || j % Info.TripMultiple != 0)) {
999 // If we know the trip count or a multiple of it, we can safely use an
1000 // unconditional branch for some iterations.
1001 return false;
1002 }
1003 return std::nullopt;
1004 };
1005
1006 // Fold branches for iterations where we know that they will exit or not
1007 // exit.
1008 for (auto &Pair : ExitInfos) {
1009 ExitInfo &Info = Pair.second;
1010 for (unsigned i = 0, e = Info.ExitingBlocks.size(); i != e; ++i) {
1011 // The branch destination.
1012 unsigned j = (i + 1) % e;
1013 bool IsLatch = Pair.first == LatchBlock;
1014 std::optional<bool> KnownWillExit = WillExit(Info, i, j, IsLatch);
1015 if (!KnownWillExit) {
1016 if (!Info.FirstExitingBlock)
1017 Info.FirstExitingBlock = Info.ExitingBlocks[i];
1018 continue;
1019 }
1020
1021 // We don't fold known-exiting branches for non-latch exits here,
1022 // because this ensures that both all loop blocks and all exit blocks
1023 // remain reachable in the CFG.
1024 // TODO: We could fold these branches, but it would require much more
1025 // sophisticated updates to LoopInfo.
1026 if (*KnownWillExit && !IsLatch) {
1027 if (!Info.FirstExitingBlock)
1028 Info.FirstExitingBlock = Info.ExitingBlocks[i];
1029 continue;
1030 }
1031
1032 SetDest(Info.ExitingBlocks[i], *KnownWillExit, Info.ExitOnTrue);
1033 }
1034 }
1035
1036 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
1037 DomTreeUpdater *DTUToUse = &DTU;
1038 if (ExitingBlocks.size() == 1 && ExitInfos.size() == 1) {
1039 // Manually update the DT if there's a single exiting node. In that case
1040 // there's a single exit node and it is sufficient to update the nodes
1041 // immediately dominated by the original exiting block. They will become
1042 // dominated by the first exiting block that leaves the loop after
1043 // unrolling. Note that the CFG inside the loop does not change, so there's
1044 // no need to update the DT inside the unrolled loop.
1045 DTUToUse = nullptr;
1046 auto &[OriginalExit, Info] = *ExitInfos.begin();
1047 if (!Info.FirstExitingBlock)
1048 Info.FirstExitingBlock = Info.ExitingBlocks.back();
1049 for (auto *C : to_vector(Range: DT->getNode(BB: OriginalExit)->children())) {
1050 if (L->contains(BB: C->getBlock()))
1051 continue;
1052 C->setIDom(DT->getNode(BB: Info.FirstExitingBlock));
1053 }
1054 } else {
1055 DTU.applyUpdates(Updates: DTUpdates);
1056 }
1057
1058 // When completely unrolling, the last latch becomes unreachable.
1059 if (!LatchIsExiting && CompletelyUnroll) {
1060 // There is no need to update the DT here, because there must be a unique
1061 // latch. Hence if the latch is not exiting it must directly branch back to
1062 // the original loop header and does not dominate any nodes.
1063 assert(LatchBlock->getSingleSuccessor() && "Loop with multiple latches?");
1064 changeToUnreachable(I: Latches.back()->getTerminator(), PreserveLCSSA);
1065 }
1066
1067 // Merge adjacent basic blocks, if possible.
1068 for (BasicBlock *Latch : Latches) {
1069 assert((isa<UncondBrInst, CondBrInst>(Latch->getTerminator()) ||
1070 (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) &&
1071 "Need a branch as terminator, except when fully unrolling with "
1072 "unconditional latch");
1073 if (auto *Term = dyn_cast<UncondBrInst>(Val: Latch->getTerminator())) {
1074 BasicBlock *Dest = Term->getSuccessor();
1075 BasicBlock *Fold = Dest->getUniquePredecessor();
1076 if (MergeBlockIntoPredecessor(BB: Dest, /*DTU=*/DTUToUse, LI,
1077 /*MSSAU=*/nullptr, /*MemDep=*/nullptr,
1078 /*PredecessorWithTwoSuccessors=*/false,
1079 DT: DTUToUse ? nullptr : DT)) {
1080 // Dest has been folded into Fold. Update our worklists accordingly.
1081 llvm::replace(Range&: Latches, OldValue: Dest, NewValue: Fold);
1082 llvm::erase(C&: UnrolledLoopBlocks, V: Dest);
1083 }
1084 }
1085 }
1086
1087 // If there are partial reductions, create code in the exit block to compute
1088 // the final result and update users of the final result.
1089 if (!PartialReductions.empty()) {
1090 BasicBlock *ExitBlock = L->getExitBlock();
1091 assert(ExitBlock &&
1092 "Can only introduce parallel reduction phis with single exit block");
1093 assert(Reductions.size() == 1 &&
1094 "currently only a single reduction is supported");
1095 Value *FinalRdxValue = PartialReductions.back();
1096 Value *RdxResult = nullptr;
1097 for (PHINode &Phi : ExitBlock->phis()) {
1098 if (Phi.getIncomingValueForBlock(BB: L->getLoopLatch()) != FinalRdxValue)
1099 continue;
1100 if (!RdxResult) {
1101 RdxResult = PartialReductions.front();
1102 IRBuilder Builder(ExitBlock, ExitBlock->getFirstNonPHIIt());
1103 Builder.setFastMathFlags(Reductions.begin()->second.getFastMathFlags());
1104 RecurKind RK = Reductions.begin()->second.getRecurrenceKind();
1105 for (Instruction *RdxPart : drop_begin(RangeOrContainer&: PartialReductions)) {
1106 RdxResult = Builder.CreateBinOp(
1107 Opc: (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind: RK),
1108 LHS: RdxPart, RHS: RdxResult, Name: "bin.rdx");
1109 }
1110 NeedToFixLCSSA = true;
1111 for (Instruction *RdxPart : PartialReductions)
1112 RdxPart->dropPoisonGeneratingFlags();
1113 }
1114
1115 Phi.replaceAllUsesWith(V: RdxResult);
1116 }
1117 }
1118
1119 if (DTUToUse) {
1120 // Apply updates to the DomTree.
1121 DT = &DTU.getDomTree();
1122 }
1123 assert(!UnrollVerifyDomtree ||
1124 DT->verify(DominatorTree::VerificationLevel::Fast));
1125
1126 // At this point, the code is well formed. We now simplify the unrolled loop,
1127 // doing constant propagation and dead code elimination as we go.
1128 simplifyLoopAfterUnroll(L, SimplifyIVs: !CompletelyUnroll && ULO.Count > 1, LI, SE, DT, AC,
1129 TTI, AA);
1130
1131 NumCompletelyUnrolled += CompletelyUnroll;
1132 ++NumUnrolled;
1133
1134 Loop *OuterL = L->getParentLoop();
1135 // Update LoopInfo if the loop is completely removed.
1136 if (CompletelyUnroll) {
1137 LI->erase(L);
1138 // We shouldn't try to use `L` anymore.
1139 L = nullptr;
1140 } else {
1141 // Update metadata for the loop's branch weights and estimated trip count:
1142 // - If ULO.Runtime, UnrollRuntimeLoopRemainder sets the guard branch
1143 // weights, latch branch weights, and estimated trip count of the
1144 // remainder loop it creates. It also sets the branch weights for the
1145 // unrolled loop guard it creates. The branch weights for the unrolled
1146 // loop latch are adjusted below. FIXME: Handle prologue loops.
1147 // - Otherwise, if unrolled loop iteration latches become unconditional,
1148 // branch weights are adjusted above. FIXME: Actually handle such
1149 // unconditional latches.
1150 // - Otherwise, the original loop's branch weights are correct for the
1151 // unrolled loop, so do not adjust them.
1152 // - In all cases, the unrolled loop's estimated trip count is set below.
1153 //
1154 // As an example of the last case, consider what happens if the unroll count
1155 // is 4 for a loop with an estimated trip count of 10 when we do not create
1156 // a remainder loop and all iterations' latches remain conditional. Each
1157 // unrolled iteration's latch still has the same probability of exiting the
1158 // loop as it did when in the original loop, and thus it should still have
1159 // the same branch weights. Each unrolled iteration's non-zero probability
1160 // of exiting already appropriately reduces the probability of reaching the
1161 // remaining iterations just as it did in the original loop. Trying to also
1162 // adjust the branch weights of the final unrolled iteration's latch (i.e.,
1163 // the backedge for the unrolled loop as a whole) to reflect its new trip
1164 // count of 3 will erroneously further reduce its block frequencies.
1165 // However, in case an analysis later needs to estimate the trip count of
1166 // the unrolled loop as a whole without considering the branch weights for
1167 // each unrolled iteration's latch within it, we store the new trip count as
1168 // separate metadata.
1169 if (!OriginalLoopProb.isUnknown() && ULO.Runtime && EpilogProfitability) {
1170 // Where p is always the probability of executing at least 1 more
1171 // iteration, the probability for at least n more iterations is p^n.
1172 setLoopProbability(L, P: OriginalLoopProb.pow(N: ULO.Count));
1173 }
1174 if (OriginalTripCount) {
1175 unsigned NewTripCount = *OriginalTripCount / ULO.Count;
1176 if (!ULO.Runtime && *OriginalTripCount % ULO.Count)
1177 ++NewTripCount;
1178 setLoopEstimatedTripCount(L, EstimatedTripCount: NewTripCount);
1179 }
1180 }
1181
1182 // LoopInfo should not be valid, confirm that.
1183 if (UnrollVerifyLoopInfo)
1184 LI->verify(DomTree: *DT);
1185
1186 // After complete unrolling most of the blocks should be contained in OuterL.
1187 // However, some of them might happen to be out of OuterL (e.g. if they
1188 // precede a loop exit). In this case we might need to insert PHI nodes in
1189 // order to preserve LCSSA form.
1190 // We don't need to check this if we already know that we need to fix LCSSA
1191 // form.
1192 // TODO: For now we just recompute LCSSA for the outer loop in this case, but
1193 // it should be possible to fix it in-place.
1194 if (PreserveLCSSA && OuterL && CompletelyUnroll && !NeedToFixLCSSA)
1195 NeedToFixLCSSA |= ::needToInsertPhisForLCSSA(L: OuterL, Blocks: UnrolledLoopBlocks, LI);
1196
1197 // Make sure that loop-simplify form is preserved. We want to simplify
1198 // at least one layer outside of the loop that was unrolled so that any
1199 // changes to the parent loop exposed by the unrolling are considered.
1200 if (OuterL) {
1201 // OuterL includes all loops for which we can break loop-simplify, so
1202 // it's sufficient to simplify only it (it'll recursively simplify inner
1203 // loops too).
1204 if (NeedToFixLCSSA) {
1205 // LCSSA must be performed on the outermost affected loop. The unrolled
1206 // loop's last loop latch is guaranteed to be in the outermost loop
1207 // after LoopInfo's been updated by LoopInfo::erase.
1208 Loop *LatchLoop = LI->getLoopFor(BB: Latches.back());
1209 Loop *FixLCSSALoop = OuterL;
1210 if (!FixLCSSALoop->contains(L: LatchLoop))
1211 while (FixLCSSALoop->getParentLoop() != LatchLoop)
1212 FixLCSSALoop = FixLCSSALoop->getParentLoop();
1213
1214 formLCSSARecursively(L&: *FixLCSSALoop, DT: *DT, LI, SE);
1215 } else if (PreserveLCSSA) {
1216 assert(OuterL->isLCSSAForm(*DT) &&
1217 "Loops should be in LCSSA form after loop-unroll.");
1218 }
1219
1220 // TODO: That potentially might be compile-time expensive. We should try
1221 // to fix the loop-simplified form incrementally.
1222 simplifyLoop(L: OuterL, DT, LI, SE, AC, MSSAU: nullptr, PreserveLCSSA);
1223 } else {
1224 // Simplify loops for which we might've broken loop-simplify form.
1225 for (Loop *SubLoop : LoopsToSimplify)
1226 simplifyLoop(L: SubLoop, DT, LI, SE, AC, MSSAU: nullptr, PreserveLCSSA);
1227 }
1228
1229 return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled
1230 : LoopUnrollResult::PartiallyUnrolled;
1231}
1232
1233/// Given an llvm.loop loop id metadata node, returns the loop hint metadata
1234/// node with the given name (for example, "llvm.loop.unroll.count"). If no
1235/// such metadata node exists, then nullptr is returned.
1236MDNode *llvm::GetUnrollMetadata(MDNode *LoopID, StringRef Name) {
1237 // First operand should refer to the loop id itself.
1238 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1239 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1240
1241 for (const MDOperand &MDO : llvm::drop_begin(RangeOrContainer: LoopID->operands())) {
1242 MDNode *MD = dyn_cast<MDNode>(Val: MDO);
1243 if (!MD)
1244 continue;
1245
1246 MDString *S = dyn_cast<MDString>(Val: MD->getOperand(I: 0));
1247 if (!S)
1248 continue;
1249
1250 if (Name == S->getString())
1251 return MD;
1252 }
1253 return nullptr;
1254}
1255
1256// Returns the loop hint metadata node with the given name (for example,
1257// "llvm.loop.unroll.count"). If no such metadata node exists, then nullptr is
1258// returned.
1259MDNode *llvm::getUnrollMetadataForLoop(const Loop *L, StringRef Name) {
1260 if (MDNode *LoopID = L->getLoopID())
1261 return GetUnrollMetadata(LoopID, Name);
1262 return nullptr;
1263}
1264
1265std::optional<RecurrenceDescriptor>
1266llvm::canParallelizeReductionWhenUnrolling(PHINode &Phi, Loop *L,
1267 ScalarEvolution *SE) {
1268 RecurrenceDescriptor RdxDesc;
1269 if (!RecurrenceDescriptor::isReductionPHI(Phi: &Phi, TheLoop: L, RedDes&: RdxDesc,
1270 /*DemandedBits=*/DB: nullptr,
1271 /*AC=*/nullptr, /*DT=*/nullptr, SE))
1272 return std::nullopt;
1273 if (RdxDesc.hasUsesOutsideReductionChain())
1274 return std::nullopt;
1275 RecurKind RK = RdxDesc.getRecurrenceKind();
1276 // Skip unsupported reductions.
1277 // TODO: Handle additional reductions, including FP and min-max
1278 // reductions.
1279 if (RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind: RK) ||
1280 RecurrenceDescriptor::isFindRecurrenceKind(Kind: RK) ||
1281 RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind: RK))
1282 return std::nullopt;
1283
1284 if (RdxDesc.hasExactFPMath())
1285 return std::nullopt;
1286
1287 if (RdxDesc.IntermediateStore)
1288 return std::nullopt;
1289
1290 // Don't unroll reductions with constant ops; those can be folded to a
1291 // single induction update.
1292 if (any_of(Range: cast<Instruction>(Val: Phi.getIncomingValueForBlock(BB: L->getLoopLatch()))
1293 ->operands(),
1294 P: IsaPred<Constant>))
1295 return std::nullopt;
1296
1297 BasicBlock *Latch = L->getLoopLatch();
1298 if (!Latch ||
1299 !is_contained(
1300 Range: cast<Instruction>(Val: Phi.getIncomingValueForBlock(BB: Latch))->operands(),
1301 Element: &Phi))
1302 return std::nullopt;
1303
1304 return RdxDesc;
1305}
1306