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