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 <cmath>
70#include <numeric>
71#include <vector>
72
73namespace llvm {
74class DataLayout;
75class Value;
76} // namespace llvm
77
78using namespace llvm;
79
80#define DEBUG_TYPE "loop-unroll"
81
82// TODO: Should these be here or in LoopUnroll?
83STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
84STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");
85STATISTIC(NumUnrolledNotLatch, "Number of loops unrolled without a conditional "
86 "latch (completely or otherwise)");
87
88static cl::opt<bool>
89UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(Val: false), cl::Hidden,
90 cl::desc("Allow runtime unrolled loops to be unrolled "
91 "with epilog instead of prolog."));
92
93static cl::opt<bool> UnrollUniformWeights(
94 "unroll-uniform-weights", cl::init(Val: false), cl::Hidden,
95 cl::desc("If new branch weights must be found, work harder to keep them "
96 "uniform."));
97
98static cl::opt<bool>
99UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden,
100 cl::desc("Verify domtree after unrolling"),
101#ifdef EXPENSIVE_CHECKS
102 cl::init(true)
103#else
104 cl::init(Val: false)
105#endif
106 );
107
108static cl::opt<bool>
109UnrollVerifyLoopInfo("unroll-verify-loopinfo", cl::Hidden,
110 cl::desc("Verify loopinfo after unrolling"),
111#ifdef EXPENSIVE_CHECKS
112 cl::init(true)
113#else
114 cl::init(Val: false)
115#endif
116 );
117
118static cl::opt<bool> UnrollAddParallelReductions(
119 "unroll-add-parallel-reductions", cl::init(Val: false), cl::Hidden,
120 cl::desc("Allow unrolling to add parallel reduction phis."));
121
122/// Check if unrolling created a situation where we need to insert phi nodes to
123/// preserve LCSSA form.
124/// \param Blocks is a vector of basic blocks representing unrolled loop.
125/// \param L is the outer loop.
126/// It's possible that some of the blocks are in L, and some are not. In this
127/// case, if there is a use is outside L, and definition is inside L, we need to
128/// insert a phi-node, otherwise LCSSA will be broken.
129/// The function is just a helper function for llvm::UnrollLoop that returns
130/// true if this situation occurs, indicating that LCSSA needs to be fixed.
131static bool needToInsertPhisForLCSSA(Loop *L,
132 const std::vector<BasicBlock *> &Blocks,
133 LoopInfo *LI) {
134 for (BasicBlock *BB : Blocks) {
135 if (LI->getLoopFor(BB) == L)
136 continue;
137 for (Instruction &I : *BB) {
138 for (Use &U : I.operands()) {
139 if (const auto *Def = dyn_cast<Instruction>(Val&: U)) {
140 Loop *DefLoop = LI->getLoopFor(BB: Def->getParent());
141 if (!DefLoop)
142 continue;
143 if (DefLoop->contains(L))
144 return true;
145 }
146 }
147 }
148 }
149 return false;
150}
151
152/// Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary
153/// and adds a mapping from the original loop to the new loop to NewLoops.
154/// Returns nullptr if no new loop was created and a pointer to the
155/// original loop OriginalBB was part of otherwise.
156const Loop* llvm::addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
157 BasicBlock *ClonedBB, LoopInfo *LI,
158 NewLoopsMap &NewLoops) {
159 // Figure out which loop New is in.
160 const Loop *OldLoop = LI->getLoopFor(BB: OriginalBB);
161 assert(OldLoop && "Should (at least) be in the loop being unrolled!");
162
163 Loop *&NewLoop = NewLoops[OldLoop];
164 if (!NewLoop) {
165 // Found a new sub-loop.
166 assert(OriginalBB == OldLoop->getHeader() &&
167 "Header should be first in RPO");
168
169 NewLoop = LI->AllocateLoop();
170 Loop *NewLoopParent = NewLoops.lookup(Val: OldLoop->getParentLoop());
171
172 if (NewLoopParent)
173 NewLoopParent->addChildLoop(NewChild: NewLoop);
174 else
175 LI->addTopLevelLoop(New: NewLoop);
176
177 NewLoop->addBasicBlockToLoop(NewBB: ClonedBB, LI&: *LI);
178 return OldLoop;
179 } else {
180 NewLoop->addBasicBlockToLoop(NewBB: ClonedBB, LI&: *LI);
181 return nullptr;
182 }
183}
184
185/// The function chooses which type of unroll (epilog or prolog) is more
186/// profitabale.
187/// Epilog unroll is more profitable when there is PHI that starts from
188/// constant. In this case epilog will leave PHI start from constant,
189/// but prolog will convert it to non-constant.
190///
191/// loop:
192/// PN = PHI [I, Latch], [CI, PreHeader]
193/// I = foo(PN)
194/// ...
195///
196/// Epilog unroll case.
197/// loop:
198/// PN = PHI [I2, Latch], [CI, PreHeader]
199/// I1 = foo(PN)
200/// I2 = foo(I1)
201/// ...
202/// Prolog unroll case.
203/// NewPN = PHI [PrologI, Prolog], [CI, PreHeader]
204/// loop:
205/// PN = PHI [I2, Latch], [NewPN, PreHeader]
206/// I1 = foo(PN)
207/// I2 = foo(I1)
208/// ...
209///
210static bool isEpilogProfitable(Loop *L) {
211 BasicBlock *PreHeader = L->getLoopPreheader();
212 BasicBlock *Header = L->getHeader();
213 assert(PreHeader && Header);
214 for (const PHINode &PN : Header->phis()) {
215 if (isa<ConstantInt>(Val: PN.getIncomingValueForBlock(BB: PreHeader)))
216 return true;
217 }
218 return false;
219}
220
221struct LoadValue {
222 Instruction *DefI = nullptr;
223 unsigned Generation = 0;
224 LoadValue() = default;
225 LoadValue(Instruction *Inst, unsigned Generation)
226 : DefI(Inst), Generation(Generation) {}
227};
228
229class StackNode {
230 ScopedHashTable<const SCEV *, LoadValue>::ScopeTy LoadScope;
231 unsigned CurrentGeneration;
232 unsigned ChildGeneration;
233 DomTreeNode *Node;
234 DomTreeNode::const_iterator ChildIter;
235 DomTreeNode::const_iterator EndIter;
236 bool Processed = false;
237
238public:
239 StackNode(ScopedHashTable<const SCEV *, LoadValue> &AvailableLoads,
240 unsigned cg, DomTreeNode *N, DomTreeNode::const_iterator Child,
241 DomTreeNode::const_iterator End)
242 : LoadScope(AvailableLoads), CurrentGeneration(cg), ChildGeneration(cg),
243 Node(N), ChildIter(Child), EndIter(End) {}
244 // Accessors.
245 unsigned currentGeneration() const { return CurrentGeneration; }
246 unsigned childGeneration() const { return ChildGeneration; }
247 void childGeneration(unsigned generation) { ChildGeneration = generation; }
248 DomTreeNode *node() { return Node; }
249 DomTreeNode::const_iterator childIter() const { return ChildIter; }
250
251 DomTreeNode *nextChild() {
252 DomTreeNode *Child = *ChildIter;
253 ++ChildIter;
254 return Child;
255 }
256
257 DomTreeNode::const_iterator end() const { return EndIter; }
258 bool isProcessed() const { return Processed; }
259 void process() { Processed = true; }
260};
261
262Value *getMatchingValue(LoadValue LV, LoadInst *LI, unsigned CurrentGeneration,
263 BatchAAResults &BAA,
264 function_ref<MemorySSA *()> GetMSSA) {
265 if (!LV.DefI)
266 return nullptr;
267 if (LV.DefI->getType() != LI->getType())
268 return nullptr;
269 if (LV.Generation != CurrentGeneration) {
270 MemorySSA *MSSA = GetMSSA();
271 if (!MSSA)
272 return nullptr;
273 auto *EarlierMA = MSSA->getMemoryAccess(I: LV.DefI);
274 MemoryAccess *LaterDef =
275 MSSA->getWalker()->getClobberingMemoryAccess(I: LI, AA&: BAA);
276 if (!MSSA->dominates(A: LaterDef, B: EarlierMA))
277 return nullptr;
278 }
279 return LV.DefI;
280}
281
282void loadCSE(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI,
283 BatchAAResults &BAA, function_ref<MemorySSA *()> GetMSSA) {
284 ScopedHashTable<const SCEV *, LoadValue> AvailableLoads;
285 SmallVector<std::unique_ptr<StackNode>> NodesToProcess;
286 DomTreeNode *HeaderD = DT.getNode(BB: L->getHeader());
287 NodesToProcess.emplace_back(Args: new StackNode(AvailableLoads, 0, HeaderD,
288 HeaderD->begin(), HeaderD->end()));
289
290 unsigned CurrentGeneration = 0;
291 while (!NodesToProcess.empty()) {
292 StackNode *NodeToProcess = &*NodesToProcess.back();
293
294 CurrentGeneration = NodeToProcess->currentGeneration();
295
296 if (!NodeToProcess->isProcessed()) {
297 // Process the node.
298
299 // If this block has a single predecessor, then the predecessor is the
300 // parent
301 // of the domtree node and all of the live out memory values are still
302 // current in this block. If this block has multiple predecessors, then
303 // they could have invalidated the live-out memory values of our parent
304 // value. For now, just be conservative and invalidate memory if this
305 // block has multiple predecessors.
306 if (!NodeToProcess->node()->getBlock()->getSinglePredecessor())
307 ++CurrentGeneration;
308 for (auto &I : make_early_inc_range(Range&: *NodeToProcess->node()->getBlock())) {
309
310 auto *Load = dyn_cast<LoadInst>(Val: &I);
311 if (!Load || !Load->isSimple()) {
312 if (I.mayWriteToMemory())
313 CurrentGeneration++;
314 continue;
315 }
316
317 const SCEV *PtrSCEV = SE.getSCEV(V: Load->getPointerOperand());
318 LoadValue LV = AvailableLoads.lookup(Key: PtrSCEV);
319 if (Value *M =
320 getMatchingValue(LV, LI: Load, CurrentGeneration, BAA, GetMSSA)) {
321 if (LI.replacementPreservesLCSSAForm(From: Load, To: M)) {
322 combineMetadataForCSE(K: cast<Instruction>(Val: M), J: Load,
323 /*DoesKMove=*/false);
324 Load->replaceAllUsesWith(V: M);
325 Load->eraseFromParent();
326 }
327 } else {
328 AvailableLoads.insert(Key: PtrSCEV, Val: LoadValue(Load, CurrentGeneration));
329 }
330 }
331 NodeToProcess->childGeneration(generation: CurrentGeneration);
332 NodeToProcess->process();
333 } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
334 // Push the next child onto the stack.
335 DomTreeNode *Child = NodeToProcess->nextChild();
336 if (!L->contains(BB: Child->getBlock()))
337 continue;
338 NodesToProcess.emplace_back(
339 Args: new StackNode(AvailableLoads, NodeToProcess->childGeneration(), Child,
340 Child->begin(), Child->end()));
341 } else {
342 // It has been processed, and there are no more children to process,
343 // so delete it and pop it off the stack.
344 NodesToProcess.pop_back();
345 }
346 }
347}
348
349/// Perform some cleanup and simplifications on loops after unrolling. It is
350/// useful to simplify the IV's in the new loop, as well as do a quick
351/// simplify/dce pass of the instructions.
352void llvm::simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
353 ScalarEvolution *SE, DominatorTree *DT,
354 AssumptionCache *AC,
355 const TargetTransformInfo *TTI,
356 ArrayRef<BasicBlock *> Blocks,
357 AAResults *AA) {
358 using namespace llvm::PatternMatch;
359
360 // Simplify any new induction variables in the partially unrolled loop.
361 if (SE && SimplifyIVs) {
362 SmallVector<WeakTrackingVH, 16> DeadInsts;
363 simplifyLoopIVs(L, SE, DT, LI, TTI, Dead&: DeadInsts);
364
365 // Aggressively clean up dead instructions that simplifyLoopIVs already
366 // identified. Any remaining should be cleaned up below.
367 while (!DeadInsts.empty()) {
368 Value *V = DeadInsts.pop_back_val();
369 if (Instruction *Inst = dyn_cast_or_null<Instruction>(Val: V))
370 RecursivelyDeleteTriviallyDeadInstructions(V: Inst);
371 }
372
373 if (AA) {
374 std::unique_ptr<MemorySSA> MSSA = nullptr;
375 BatchAAResults BAA(*AA);
376 loadCSE(L, DT&: *DT, SE&: *SE, LI&: *LI, BAA, GetMSSA: [L, AA, DT, &MSSA]() -> MemorySSA * {
377 if (!MSSA)
378 MSSA.reset(p: new MemorySSA(*L, AA, DT));
379 return &*MSSA;
380 });
381 }
382 }
383
384 // At this point, the code is well formed. Perform constprop, instsimplify,
385 // and dce.
386 SmallVector<WeakTrackingVH, 16> DeadInsts;
387 for (BasicBlock *BB : Blocks) {
388 // Remove repeated debug instructions after loop unrolling.
389 if (BB->getParent()->getSubprogram())
390 RemoveRedundantDbgInstrs(BB);
391
392 for (Instruction &Inst : llvm::make_early_inc_range(Range&: *BB)) {
393 if (Value *V = simplifyInstruction(
394 I: &Inst, Q: {BB->getDataLayout(), nullptr, DT, AC}))
395 if (LI->replacementPreservesLCSSAForm(From: &Inst, To: V))
396 Inst.replaceAllUsesWith(V);
397 if (isInstructionTriviallyDead(I: &Inst))
398 DeadInsts.emplace_back(Args: &Inst);
399
400 // Fold ((add X, C1), C2) to (add X, C1+C2). This is very common in
401 // unrolled loops, and handling this early allows following code to
402 // identify the IV as a "simple recurrence" without first folding away
403 // a long chain of adds.
404 {
405 Value *X;
406 const APInt *C1, *C2;
407 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)))) {
408 auto *InnerI = dyn_cast<Instruction>(Val: Inst.getOperand(i: 0));
409 auto *InnerOBO = cast<OverflowingBinaryOperator>(Val: Inst.getOperand(i: 0));
410 bool SignedOverflow;
411 APInt NewC = C1->sadd_ov(RHS: *C2, Overflow&: SignedOverflow);
412 Inst.setOperand(i: 0, Val: X);
413 Inst.setOperand(i: 1, Val: ConstantInt::get(Ty: Inst.getType(), V: NewC));
414 Inst.setHasNoUnsignedWrap(Inst.hasNoUnsignedWrap() &&
415 InnerOBO->hasNoUnsignedWrap());
416 Inst.setHasNoSignedWrap(Inst.hasNoSignedWrap() &&
417 InnerOBO->hasNoSignedWrap() &&
418 !SignedOverflow);
419 if (InnerI && isInstructionTriviallyDead(I: InnerI))
420 DeadInsts.emplace_back(Args&: InnerI);
421 }
422 }
423 }
424 // We can't do recursive deletion until we're done iterating, as we might
425 // have a phi which (potentially indirectly) uses instructions later in
426 // the block we're iterating through.
427 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);
428 }
429}
430
431// If LoopUnroll has proven OriginalLoopProb is incorrect for some iterations
432// of the original loop, adjust latch probabilities in the unrolled loop to
433// maintain the original total frequency of the original loop body.
434//
435// OriginalLoopProb is practical but imprecise
436// -------------------------------------------
437//
438// The latch branch weights that LLVM originally adds to a loop encode one latch
439// probability, OriginalLoopProb, applied uniformly across the loop's infinite
440// set of theoretically possible iterations. While this uniform latch
441// probability serves as a practical statistic summarizing the trip counts
442// observed during profiling, it is imprecise. Specifically, unless it is zero,
443// it is impossible for it to be the actual probability observed at every
444// individual iteration. To see why, consider that the only way to actually
445// observe at run time that the latch probability remains non-zero is to profile
446// at least one loop execution that has an infinite number of iterations. I do
447// not know how to profile an infinite number of loop iterations, and most loops
448// I work with are always finite.
449//
450// LoopUnroll proves OriginalLoopProb is incorrect
451// ------------------------------------------------
452//
453// LoopUnroll reorganizes the original loop so that loop iterations are no
454// longer all implemented by the same code, and then it analyzes some of those
455// loop iteration implementations independently of others. In particular, it
456// converts some of their conditional latches to unconditional. That is, by
457// examining code structure without any profile data, LoopUnroll proves that the
458// actual latch probability at the end of such an iteration is either 1 or 0.
459// When an individual iteration's actual latch probability is 1 or 0, that means
460// it always behaves the same, so it is impossible to observe it as having any
461// other probability. The original uniform latch probability is rarely 1 or 0
462// because, when applied to all possible iterations, that would yield an
463// estimated trip count of infinity or 1, respectively.
464//
465// Thus, the new probabilities of 1 or 0 are proven corrections to
466// OriginalLoopProb for individual iterations in the original loop. However,
467// LoopUnroll often is able to perform these corrections for only some
468// iterations, leaving other iterations with OriginalLoopProb, and thus
469// corrupting the aggregate effect on the total frequency of the original loop
470// body.
471//
472// Adjusting latch probabilities
473// -----------------------------
474//
475// This function ensures that the total frequency of the original loop body,
476// summed across all its occurrences in the unrolled loop after the
477// aforementioned latch conversions, is the same as in the original loop. To do
478// so, it adjusts probabilities on the remaining conditional latches. However,
479// it cannot derive the new probabilities directly from the original uniform
480// latch probability because the latter has been proven incorrect for some
481// original loop iterations.
482//
483// There are often many sets of latch probabilities that can produce the
484// original total loop body frequency. If there are many remaining conditional
485// latches and !UnrollUniformWeights, this function just quickly hacks a few of
486// their probabilities to restore the original total loop body frequency.
487// Otherwise, it tries harder to determine less arbitrary probabilities.
488static void fixProbContradiction(Loop *L, UnrollLoopOptions ULO,
489 OptimizationRemarkEmitter *ORE,
490 BranchProbability OriginalLoopProb,
491 bool CompletelyUnroll,
492 std::vector<unsigned> &IterCounts,
493 const std::vector<BasicBlock *> &CondLatches,
494 std::vector<BasicBlock *> &CondLatchNexts) {
495 // Runtime unrolling is handled later in LoopUnroll not here.
496 //
497 // There are two scenarios in which LoopUnroll sets ProbUpdateRequired to true
498 // because it needs to update probabilities that were originally
499 // OriginalLoopProb, but only in one scenario has LoopUnroll proven
500 // OriginalLoopProb incorrect for iterations within the original loop:
501 // - If ULO.Runtime, LoopUnroll adds new guards that enforce new reaching
502 // conditions for new loop iteration implementations (e.g., one unrolled
503 // loop iteration executes only if at least ULO.Count original loop
504 // iterations remain). Those reaching conditions dictate how conditional
505 // latches can be converted to unconditional (e.g., within an unrolled loop
506 // iteration, there is no need to recheck the number of remaining original
507 // loop iterations). None of this reorganization alters the set of possible
508 // original loop iteration counts or proves OriginalLoopProb incorrect for
509 // any of the original loop iterations. Thus, LoopUnroll derives
510 // probabilities for the new guards and latches directly from
511 // OriginalLoopProb based on the probabilities that their reaching
512 // conditions would occur in the original loop. Doing so maintains the
513 // total frequency of the original loop body.
514 // - If !ULO.Runtime, LoopUnroll initially adds new loop iteration
515 // implementations, which have the same latch probabilities as in the
516 // original loop because there are no new guards that change their reaching
517 // conditions. Sometimes, LoopUnroll is then done, and so does not set
518 // ProbUpdateRequired to true. Other times, LoopUnroll then proves that
519 // some latches are unconditional, directly contradicting OriginalLoopProb
520 // for the corresponding original loop iterations. That reduces the set of
521 // possible original loop iteration counts, possibly producing a finite set
522 // if it manages to eliminate the backedge. LoopUnroll has to choose a new
523 // set of latch probabilities that produce the same total loop body
524 // frequency.
525 //
526 // This function addresses the second scenario only.
527 if (ULO.Runtime)
528 return;
529
530 // If CondLatches.empty(), there are no latch branches with probabilities we
531 // can adjust. That should mean that the actual trip count is always exactly
532 // the number of remaining unrolled iterations, and so OriginalLoopProb should
533 // have yielded that trip count as the original loop body frequency. Of
534 // course, OriginalLoopProb could be based on inaccurate profile data, but
535 // there is nothing we can do about that here.
536 if (CondLatches.empty())
537 return;
538
539 // If the original latch probability is 1, the original frequency is infinity.
540 // Leaving all remaining probabilities set to 1 might or might not get us
541 // there (e.g., a completely unrolled loop cannot be infinite), but it is the
542 // closest we can come.
543 assert(!OriginalLoopProb.isUnknown() &&
544 "Expected to have loop probability to fix");
545 if (OriginalLoopProb.isOne())
546 return;
547
548 // FreqDesired is the frequency implied by the original loop probability.
549 double FreqDesired = 1 / (1 - OriginalLoopProb.toDouble());
550
551 // Get the probability at CondLatches[I].
552 auto GetProb = [&](unsigned I) {
553 CondBrInst *B = cast<CondBrInst>(Val: CondLatches[I]->getTerminator());
554 bool FirstTargetIsNext = B->getSuccessor(i: 0) == CondLatchNexts[I];
555 return getBranchProbability(B, ForFirstTarget: FirstTargetIsNext).toDouble();
556 };
557
558 // Set the probability at CondLatches[I] to Prob.
559 auto SetProb = [&](unsigned I, double Prob) {
560 CondBrInst *B = cast<CondBrInst>(Val: CondLatches[I]->getTerminator());
561 bool FirstTargetIsNext = B->getSuccessor(i: 0) == CondLatchNexts[I];
562 setBranchProbability(B, P: BranchProbability::getBranchProbability(Prob),
563 ForFirstTarget: FirstTargetIsNext);
564 };
565
566 // Set all probabilities in CondLatches to Prob.
567 auto SetAllProbs = [&](double Prob) {
568 for (unsigned I = 0, E = CondLatches.size(); I < E; ++I)
569 SetProb(I, Prob);
570 };
571
572 // If UnrollUniformWeights or n <= 2, we choose the simplest probability model
573 // we can think of: every remaining conditional branch instruction has the
574 // same probability, Prob, of continuing to the next iteration. This model
575 // has several helpful properties:
576 // - There is only one search parameter, Prob.
577 // - We have no reason to think one latch branch's probability should be
578 // higher or lower than another, and so this model makes them all the same.
579 // In the worst cases, we thus avoid setting just some probabilities to 0 or
580 // 1, which can unrealistically make some code appear unreachable. There
581 // are cases where they *all* must become 0 or 1 to achieve the total
582 // frequency of original loop body, and our model does permit that.
583 // - The frequency, FreqOne, of the original loop body in a single iteration
584 // of the unrolled loop is computed by a simple polynomial, where p=Prob,
585 // n=CondLatches.size(), and c_i=IterCounts[i]:
586 //
587 // FreqOne = Sum(i=0..n)(c_i * p^i)
588 //
589 // - If the backedge has been eliminated:
590 // - FreqOne is the total frequency of the original loop body in the
591 // unrolled loop.
592 // - If Prob == 1, the total frequency of the original loop body is exactly
593 // the number of remaining loop iterations, as expected because every
594 // remaining loop iteration always then executes.
595 // - If the backedge remains:
596 // - Sum(i=0..inf)(FreqOne * p^(n*i)) = FreqOne / (1 - p^n) is the total
597 // frequency of the original loop body in the unrolled loop, regardless of
598 // whether the backedge is conditional or unconditional.
599 // - As Prob approaches 1, the total frequency of the original loop body
600 // approaches infinity, as expected because the loop approaches never
601 // exiting.
602 // - For n <= 2, we can use simple formulas to solve the above polynomial
603 // equations exactly for p without performing a search.
604 // - For n > 2, evaluating each point in the search space, using ComputeFreq
605 // below, requires about as few instructions as we could hope for. That is,
606 // the probability is constant across the conditional branches, so the only
607 // computation is across conditional branches and any backedge, as required
608 // for any model for Prob.
609 // - Prob == 1 produces the maximum possible total frequency for the original
610 // loop body, as described above. Prob == 0 produces the minimum, 0.
611 // Increasing or decreasing Prob monotonically increases or decreases the
612 // frequency, respectively. Thus, for every possible frequency, there
613 // exists some Prob that can produce it, and we can easily use bisection to
614 // search the problem space.
615
616 // When iterating for a solution, we stop early if we find probabilities
617 // that produce a Freq whose relative difference from FreqDesired is small
618 // (FreqPrec). Otherwise, we expect to compute a solution at least that
619 // accurate (but surely far more accurate).
620 const double FreqPrec = 1e-6;
621
622 // Compute the new frequency produced by using Prob throughout CondLatches.
623 auto ComputeFreq = [&](double Prob) {
624 double ProbReaching = 1; // p^0
625 double FreqOne = IterCounts[0]; // c_0*p^0
626 for (unsigned I = 0, E = CondLatches.size(); I < E; ++I) {
627 ProbReaching *= Prob; // p^(I+1)
628 FreqOne += IterCounts[I + 1] * ProbReaching; // c_(I+1)*p^(I+1)
629 }
630 double ProbReachingBackedge = CompletelyUnroll ? 0 : ProbReaching;
631 assert(FreqOne > 0 && "Expected at least one iteration before first latch");
632 if (ProbReachingBackedge == 1)
633 return std::numeric_limits<double>::infinity();
634 return FreqOne / (1 - ProbReachingBackedge);
635 };
636
637 // Compute the probability that, used at CondLaches[0] where
638 // CondLatches.size() == 1, gets as close as possible to FreqDesired.
639 auto ComputeProbForLinear = [&]() {
640 // The polynomial is linear (0 = A*p + B), so just solve it.
641 double A = IterCounts[1] + (CompletelyUnroll ? 0 : FreqDesired);
642 double B = IterCounts[0] - FreqDesired;
643 assert(A > 0 && "Expected iterations after last conditional latch");
644 double Prob = -B / A;
645 // If it computes an invalid Prob, FreqDesired is impossibly low or high.
646 // Otherwise, Prob should produce nearly FreqDesired.
647 assert((Prob < 0 || Prob > 1 ||
648 fabs(ComputeFreq(Prob) - FreqDesired) / FreqDesired < FreqPrec) &&
649 "Expected accurate frequency when linear case is possible");
650 Prob = std::max(a: Prob, b: 0.);
651 Prob = std::min(a: Prob, b: 1.);
652 return Prob;
653 };
654
655 // Compute the probability that, used throughout CondLatches where
656 // CondLatches.size() == 2, gets as close as possible to FreqDesired.
657 auto ComputeProbForQuadratic = [&]() {
658 // The polynomial is quadratic (0 = A*p^2 + B*p + C), so just solve it.
659 double A = IterCounts[2] + (CompletelyUnroll ? 0 : FreqDesired);
660 double B = IterCounts[1];
661 double C = IterCounts[0] - FreqDesired;
662 assert(A > 0 && "Expected iterations after last conditional latch");
663 double Prob = (-B + sqrt(x: B * B - 4 * A * C)) / (2 * A);
664 // If it computes an invalid Prob, FreqDesired is impossibly low or high.
665 // Otherwise, Prob should produce nearly FreqDesired.
666 assert((Prob < 0 || Prob > 1 ||
667 fabs(ComputeFreq(Prob) - FreqDesired) / FreqDesired < FreqPrec) &&
668 "Expected accurate frequency when quadratic case is possible");
669 Prob = std::max(a: Prob, b: 0.);
670 Prob = std::min(a: Prob, b: 1.);
671 return Prob;
672 };
673
674 // Adjust the probability at CondLatches[ComputeIdx] to get as close as
675 // possible to FreqDesired without replacing probabilities elsewhere in
676 // CondLatches. Return the new total frequency.
677 //
678 // Given a CondLatches index I, then for a single unrolled loop iteration:
679 // - ProbBefore or ProbAfter is the probability that control flow can pass
680 // through every CondLatches[J] for J < I or J > I, respectively.
681 // - FreqBefore or FreqAfter is the total frequency accumulated before or
682 // after CondLatches[I], respectively, while the probability at
683 // CondLatches[I] is treated as 1.
684 //
685 // If ComputeIdx == 0, then ComputeProb will set those values for I == 0 and
686 // ignore the current values. If ComputeIdx > 0, then it expects those values
687 // to already be set for I == ComputeIdx - 1, and it will set them for I ==
688 // ComputeIdx.
689 auto AdjustProb = [&](unsigned ComputeIdx, double &ProbBefore,
690 double &ProbAfter, double &FreqBefore,
691 double &FreqAfter) {
692 assert(ComputeIdx < CondLatches.size() &&
693 "Expected valid CondLatches index");
694
695 // Compute or update ProbBefore, ProbAfter, FreqBefore, and FreqAfter.
696 auto ComputeAfter = [&]() {
697 ProbAfter = 1;
698 FreqAfter = IterCounts[ComputeIdx + 1];
699 for (unsigned I = ComputeIdx + 1, E = CondLatches.size(); I < E; ++I) {
700 double Prob = GetProb(I);
701 ProbAfter *= Prob;
702 // After Prob == 0, ProbAfter and FreqAfter won't change, so save time.
703 if (Prob == 0)
704 break;
705 FreqAfter += IterCounts[I + 1] * ProbAfter;
706 }
707 };
708 if (ComputeIdx == 0) {
709 ProbBefore = 1;
710 FreqBefore = IterCounts[0];
711 ComputeAfter();
712 } else {
713 // Rather than iterating all of CondLatches again, we fix up the
714 // previously computed values.
715 double ProbOld = GetProb(ComputeIdx);
716 if (ProbOld > 0) {
717 FreqAfter -= IterCounts[ComputeIdx] * ProbBefore;
718 ProbAfter /= ProbOld;
719 FreqAfter /= ProbOld;
720 } else {
721 // We cannot divide out the old zero probability. We short-circuited
722 // the iteration at that zero in the previous ComputeAfter call, so now
723 // we pick up where we left off.
724 ComputeAfter();
725 }
726 ProbBefore *= GetProb(ComputeIdx - 1);
727 FreqBefore += IterCounts[ComputeIdx] * ProbBefore;
728 }
729
730 // Compute the required probability, and limit it to a valid probability (0
731 // <= p <= 1). See the FreqCompute formula below for how to derive the
732 // ProbCompute formula.
733 double ProbReachingBackedge = CompletelyUnroll ? 0 : ProbBefore * ProbAfter;
734 double ProbComputeNumerator = FreqDesired - FreqBefore;
735 double ProbComputeDenominator =
736 FreqAfter + FreqDesired * ProbReachingBackedge;
737 double ProbCompute = -1; // Init expected to be unused.
738 if (ProbComputeNumerator <= 0) {
739 // FreqBefore has already reached or surpassed FreqDesired, so add no more
740 // frequency. It is possible that ProbComputeDenominator == 0 here
741 // because some latch probability (maybe the original) was set to zero, so
742 // this check avoids setting ProbCompute=1 (in the else if below) and
743 // division by zero where the numerator <= 0 (in the else below).
744 ProbCompute = 0;
745 } else if (ProbComputeDenominator == 0) {
746 // Analytically, this case seems impossible. It would occur if either:
747 // - Both FreqAfter and FreqDesired are zero. But the latter would cause
748 // ProbComputeNumerator < 0, which we catch above, and FreqDesired
749 // should always be >= 1 anyway.
750 // - There are no iterations after CondLatches[ComputeIdx], not even via
751 // a backedge, so that both FreqAfter and ProbReachingBackedge are zero.
752 // But iterations should exist after even the last conditional latch.
753 // - Some latch probability (maybe the original) was set to zero so that
754 // both FreqAfter and ProbReachingBackedge are zero. But that should
755 // not have happened because, according to the above
756 // ProbComputeNumerator check, we have not yet reached FreqDesired
757 // (which, if the original latch probability is zero, is just 1 and thus
758 // always reached or surpassed).
759 //
760 // Numerically, perhaps this case is possible. We interpret it to mean we
761 // need more frequency (ProbComputeNumerator > 0) but have no way to get
762 // any (ProbComputeDenominator is analytically too small to distinguish it
763 // from 0 in floating point), suggesting infinite probability is needed,
764 // but 1 is the maximum valid probability and thus the best we can do.
765 //
766 // TODO: Cover this case in the test suite if you can.
767 ProbCompute = 1;
768 } else {
769 ProbCompute = ProbComputeNumerator / ProbComputeDenominator;
770 ProbCompute = std::max(a: ProbCompute, b: 0.);
771 ProbCompute = std::min(a: ProbCompute, b: 1.);
772 }
773 SetProb(ComputeIdx, ProbCompute);
774
775 // Compute the resulting total frequency.
776 double FreqCompute = -1; // Init expected to be unused.
777 if (ProbReachingBackedge * ProbCompute == 1) {
778 // Analytically, this case seems impossible. It requires that there is a
779 // backedge and that FreqDesired == infinity so that every conditional
780 // latch's probability had to be set to 1. But FreqDesired == infinity
781 // means OriginalLoopProb.isOne(), which we guarded against earlier.
782 //
783 // Numerically, perhaps this case is possible. We interpret it to mean
784 // that analytically the probability has to be so near 1 that, in floating
785 // point, the frequency is computed as infinite.
786 //
787 // TODO: Cover this case in the test suite if you can.
788 FreqCompute = std::numeric_limits<double>::infinity();
789 if (ORE) {
790 ORE->emit(RemarkBuilder: [&]() {
791 return OptimizationRemark(DEBUG_TYPE, "InfiniteFrequency",
792 L->getStartLoc(), L->getHeader());
793 });
794 }
795 } else {
796 assert(FreqBefore > 0 &&
797 "Expected at least one iteration before first latch");
798 // In this equation, if we replace the left-hand side with FreqDesired and
799 // then solve for ProbCompute, we get the ProbCompute formula above.
800 FreqCompute = (FreqBefore + FreqAfter * ProbCompute) /
801 (1 - ProbReachingBackedge * ProbCompute);
802 }
803 assert(FreqCompute > 0 && "Expected valid frequency");
804 return FreqCompute;
805 };
806
807 // Determine and set branch weights.
808 //
809 // Prob < 0 and Prob > 1 cannot be represented as branch weights. We might
810 // compute such a Prob if FreqDesired is impossible (e.g., due to inaccurate
811 // profile data) for the maximum trip count we have determined when completely
812 // unrolling. In that case, so just go with whichever is closest.
813 if (CondLatches.size() == 1) {
814 SetAllProbs(ComputeProbForLinear());
815 } else if (CondLatches.size() == 2) {
816 SetAllProbs(ComputeProbForQuadratic());
817 } else if (!UnrollUniformWeights) {
818 // The polynomial is too complex for a simple formula, and the quick and
819 // dirty fix has been selected. Adjust probabilities starting from the
820 // first latch, which has the most influence on the total frequency, so
821 // starting there should minimize the number of latches that have to be
822 // visited. We do have to iterate because the first latch alone might not
823 // be enough. For example, we might need to set all probabilities to 1 if
824 // the frequency is the unroll factor.
825 double ProbBefore = -1, ProbAfter = -1; // Inits expected to be unused.
826 double FreqBefore = -1, FreqAfter = -1; // Inits expected to be unused.
827 for (unsigned I = 0; I != CondLatches.size(); ++I) {
828 double Freq = AdjustProb(I, ProbBefore, ProbAfter, FreqBefore, FreqAfter);
829 if (fabs(x: Freq - FreqDesired) / FreqDesired < FreqPrec)
830 break;
831 }
832 } else {
833 // The polynomial is too complex for a simple formula, and uniform branch
834 // weights have been selected, so bisect.
835 double ProbMin = -1, ProbMax = -1; // Inits expected to be unused.
836 double ProbPrev = -1; // Inits expected to be unused.
837 auto TryProb = [&](double Prob) {
838 ProbPrev = Prob;
839 double FreqDelta = ComputeFreq(Prob) - FreqDesired;
840 if (fabs(x: FreqDelta) / FreqDesired < FreqPrec)
841 return 0;
842 if (FreqDelta < 0) {
843 ProbMin = Prob;
844 return -1;
845 }
846 ProbMax = Prob;
847 return 1;
848 };
849 // If Prob == 0 is too small and Prob == 1 is too large, bisect between
850 // them. Accuracy (relative difference) is controlled by FreqPrec above.
851 // However, to place a hard upper limit on the search time, we stop
852 // bisecting when Prob stops changing (ProbDelta) by much (ProbPrec). In
853 // this case, we compute an absolute difference not a relative difference,
854 // which could produce more search time for smaller probabilities.
855 if (TryProb(0.) < 0 && TryProb(1.) > 0) {
856 assert(ProbMin == 0 && ProbMax == 1 &&
857 "expected probability bounds to be initialized");
858 const double ProbPrec = 1e-12;
859 double Prob, ProbDelta;
860 do {
861 Prob = (ProbMin + ProbMax) / 2;
862 ProbDelta = Prob - ProbPrev;
863 } while (TryProb(Prob) != 0 && fabs(x: ProbDelta) > ProbPrec);
864 }
865 SetAllProbs(ProbPrev);
866 }
867
868 // FIXME: We have not considered non-latch loop exits:
869 // - Their original probabilities are not considered in our calculation of
870 // FreqDesired.
871 // - Their probabilities are not considered in our probability model used to
872 // determine new probabilities for remaining conditional branches.
873 // - If they are conditional and LoopUnroll converts them to unconditional,
874 // LoopUnroll has proven their original probabilities are incorrect for some
875 // original loop iterations, but that does not cause ProbUpdateRequired to
876 // be set to true.
877 //
878 // To adjust FreqDesired and our probability model correctly for a non-latch
879 // loop exit, we would need to compute the original probability that the exit
880 // is reached from the loop header (in contrast, we currently assume that
881 // probability is 1 in the case of a latch exit) and the probability that the
882 // exit is taken if it is conditional (use the branch's old or new weights for
883 // FreqDesired or the probability model, respectively). Does computing the
884 // reaching probability require a CFG traversal, or is there some existing
885 // library that can do it? Prior discussions suggest some such libraries are
886 // difficult to use within LoopUnroll:
887 // <https://github.com/llvm/llvm-project/pull/164799#issuecomment-3438681519>.
888 // For now, we just let our corrected probabilities be less accurate in that
889 // scenario. Alternatively, we could refuse to correct probabilities at all
890 // in that scenario, but that seems worse.
891}
892
893/// Unroll the given loop by Count. The loop must be in LCSSA form. Unrolling
894/// can only fail when the loop's latch block is not terminated by a conditional
895/// branch instruction. However, if the trip count (and multiple) are not known,
896/// loop unrolling will mostly produce more code that is no faster.
897///
898/// If Runtime is true then UnrollLoop will try to insert a prologue or
899/// epilogue that ensures the latch has a trip multiple of Count. UnrollLoop
900/// will not runtime-unroll the loop if computing the run-time trip count will
901/// be expensive and AllowExpensiveTripCount is false.
902///
903/// The LoopInfo Analysis that is passed will be kept consistent.
904///
905/// This utility preserves LoopInfo. It will also preserve ScalarEvolution and
906/// DominatorTree if they are non-null.
907///
908/// If RemainderLoop is non-null, it will receive the remainder loop (if
909/// required and not fully unrolled).
910LoopUnrollResult
911llvm::UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
912 ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,
913 const TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE,
914 bool PreserveLCSSA, Loop **RemainderLoop, AAResults *AA) {
915 assert(DT && "DomTree is required");
916
917 if (!L->getLoopPreheader()) {
918 LLVM_DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n");
919 return LoopUnrollResult::Unmodified;
920 }
921
922 if (!L->getLoopLatch()) {
923 LLVM_DEBUG(dbgs() << " Can't unroll; loop exit-block-insertion failed.\n");
924 return LoopUnrollResult::Unmodified;
925 }
926
927 // Loops with indirectbr cannot be cloned.
928 if (!L->isSafeToClone()) {
929 LLVM_DEBUG(dbgs() << " Can't unroll; Loop body cannot be cloned.\n");
930 return LoopUnrollResult::Unmodified;
931 }
932
933 if (L->getHeader()->hasAddressTaken()) {
934 // The loop-rotate pass can be helpful to avoid this in many cases.
935 LLVM_DEBUG(
936 dbgs() << " Won't unroll loop: address of header block is taken.\n");
937 return LoopUnrollResult::Unmodified;
938 }
939
940 assert(ULO.Count > 0);
941
942 // All these values should be taken only after peeling because they might have
943 // changed.
944 BasicBlock *Preheader = L->getLoopPreheader();
945 BasicBlock *Header = L->getHeader();
946 BasicBlock *LatchBlock = L->getLoopLatch();
947 SmallVector<BasicBlock *, 4> ExitBlocks;
948 L->getExitBlocks(ExitBlocks);
949
950 const unsigned MaxTripCount = SE->getSmallConstantMaxTripCount(L);
951 const bool MaxOrZero = SE->isBackedgeTakenCountMaxOrZero(L);
952 std::optional<unsigned> OriginalTripCount =
953 llvm::getLoopEstimatedTripCount(L);
954 BranchProbability OriginalLoopProb = llvm::getLoopProbability(L);
955
956 // Effectively "DCE" unrolled iterations that are beyond the max tripcount
957 // and will never be executed.
958 if (MaxTripCount && ULO.Count > MaxTripCount)
959 ULO.Count = MaxTripCount;
960
961 struct ExitInfo {
962 unsigned TripCount;
963 unsigned TripMultiple;
964 unsigned BreakoutTrip;
965 bool ExitOnTrue;
966 BasicBlock *FirstExitingBlock = nullptr;
967 SmallVector<BasicBlock *> ExitingBlocks;
968 };
969 MapVector<BasicBlock *, ExitInfo> ExitInfos;
970 SmallVector<BasicBlock *, 4> ExitingBlocks;
971 L->getExitingBlocks(ExitingBlocks);
972 for (auto *ExitingBlock : ExitingBlocks) {
973 // The folding code is not prepared to deal with non-branch instructions
974 // right now.
975 auto *BI = dyn_cast<CondBrInst>(Val: ExitingBlock->getTerminator());
976 if (!BI)
977 continue;
978
979 ExitInfo &Info = ExitInfos[ExitingBlock];
980 Info.TripCount = SE->getSmallConstantTripCount(L, ExitingBlock);
981 Info.TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock);
982 if (Info.TripCount != 0) {
983 Info.BreakoutTrip = Info.TripCount % ULO.Count;
984 Info.TripMultiple = 0;
985 } else {
986 Info.BreakoutTrip = Info.TripMultiple =
987 (unsigned)std::gcd(m: ULO.Count, n: Info.TripMultiple);
988 }
989 Info.ExitOnTrue = !L->contains(BB: BI->getSuccessor(i: 0));
990 Info.ExitingBlocks.push_back(Elt: ExitingBlock);
991 LLVM_DEBUG(dbgs() << " Exiting block %" << ExitingBlock->getName()
992 << ": TripCount=" << Info.TripCount
993 << ", TripMultiple=" << Info.TripMultiple
994 << ", BreakoutTrip=" << Info.BreakoutTrip << "\n");
995 }
996
997 // Are we eliminating the loop control altogether? Note that we can know
998 // we're eliminating the backedge without knowing exactly which iteration
999 // of the unrolled body exits.
1000 const bool CompletelyUnroll = ULO.Count == MaxTripCount;
1001
1002 const bool PreserveOnlyFirst = CompletelyUnroll && MaxOrZero;
1003
1004 // There's no point in performing runtime unrolling if this unroll count
1005 // results in a full unroll.
1006 if (CompletelyUnroll)
1007 ULO.Runtime = false;
1008
1009 // Go through all exits of L and see if there are any phi-nodes there. We just
1010 // conservatively assume that they're inserted to preserve LCSSA form, which
1011 // means that complete unrolling might break this form. We need to either fix
1012 // it in-place after the transformation, or entirely rebuild LCSSA. TODO: For
1013 // now we just recompute LCSSA for the outer loop, but it should be possible
1014 // to fix it in-place.
1015 bool NeedToFixLCSSA =
1016 PreserveLCSSA && CompletelyUnroll &&
1017 any_of(Range&: ExitBlocks,
1018 P: [](const BasicBlock *BB) { return isa<PHINode>(Val: BB->begin()); });
1019
1020 // The current loop unroll pass can unroll loops that have
1021 // (1) single latch; and
1022 // (2a) latch is unconditional; or
1023 // (2b) latch is conditional and is an exiting block
1024 // FIXME: The implementation can be extended to work with more complicated
1025 // cases, e.g. loops with multiple latches.
1026 Instruction *LatchTerm = LatchBlock->getTerminator();
1027
1028 // A conditional branch which exits the loop, which can be optimized to an
1029 // unconditional branch in the unrolled loop in some cases.
1030 bool LatchIsExiting = L->isLoopExiting(BB: LatchBlock);
1031 if (!isa<UncondBrInst>(Val: LatchTerm) &&
1032 !(isa<CondBrInst>(Val: LatchTerm) && LatchIsExiting)) {
1033 LLVM_DEBUG(
1034 dbgs() << "Can't unroll; a conditional latch must exit the loop");
1035 return LoopUnrollResult::Unmodified;
1036 }
1037
1038 bool EpilogProfitability =
1039 UnrollRuntimeEpilog.getNumOccurrences() ? UnrollRuntimeEpilog
1040 : isEpilogProfitable(L);
1041
1042 if (ULO.Runtime &&
1043 !UnrollRuntimeLoopRemainder(
1044 L, Count: ULO.Count, AllowExpensiveTripCount: ULO.AllowExpensiveTripCount, UseEpilogRemainder: EpilogProfitability,
1045 UnrollRemainder: ULO.UnrollRemainder, ForgetAllSCEV: ULO.ForgetAllSCEV, LI, SE, DT, AC, TTI,
1046 PreserveLCSSA, SCEVExpansionBudget: ULO.SCEVExpansionBudget, RuntimeUnrollMultiExit: ULO.RuntimeUnrollMultiExit,
1047 ResultLoop: RemainderLoop, OriginalTripCount, OriginalLoopProb)) {
1048 if (ULO.Force)
1049 ULO.Runtime = false;
1050 else {
1051 LLVM_DEBUG(dbgs() << "Won't unroll; remainder loop could not be "
1052 "generated when assuming runtime trip count\n");
1053 return LoopUnrollResult::Unmodified;
1054 }
1055 }
1056
1057 using namespace ore;
1058
1059 // Determine whether this loop originated from the vectorizer so we can
1060 // produce more informative remarks.
1061 StringRef LoopKind = getLoopVectorizeKindPrefix(L);
1062
1063 // Report the unrolling decision.
1064 if (CompletelyUnroll) {
1065 LLVM_DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()
1066 << " with trip count " << ULO.Count << "!\n");
1067 if (ORE)
1068 ORE->emit(RemarkBuilder: [&]() {
1069 return OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(),
1070 L->getHeader())
1071 << "completely unrolled " + LoopKind.str() + "loop with "
1072 << NV("UnrollCount", ULO.Count) << " iterations";
1073 });
1074 } else {
1075 LLVM_DEBUG({
1076 dbgs() << "UNROLLING loop %" << Header->getName() << " by " << ULO.Count;
1077 if (ULO.Runtime) {
1078 dbgs() << " with run-time trip count";
1079 if (ULO.UnrollRemainder)
1080 dbgs() << " (remainder unrolled)";
1081 }
1082 dbgs() << "!\n";
1083 });
1084
1085 if (ORE)
1086 ORE->emit(RemarkBuilder: [&]() {
1087 OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled", L->getStartLoc(),
1088 L->getHeader());
1089 Diag << "unrolled " + LoopKind.str() + "loop by a factor of "
1090 << NV("UnrollCount", ULO.Count);
1091 if (ULO.Runtime)
1092 Diag << " with run-time trip count"
1093 << (ULO.UnrollRemainder ? " (remainder unrolled)" : "");
1094 return Diag;
1095 });
1096 }
1097
1098 // We are going to make changes to this loop. SCEV may be keeping cached info
1099 // about it, in particular about backedge taken count. The changes we make
1100 // are guaranteed to invalidate this information for our loop. It is tempting
1101 // to only invalidate the loop being unrolled, but it is incorrect as long as
1102 // all exiting branches from all inner loops have impact on the outer loops,
1103 // and if something changes inside them then any of outer loops may also
1104 // change. When we forget outermost loop, we also forget all contained loops
1105 // and this is what we need here.
1106 if (SE) {
1107 if (ULO.ForgetAllSCEV)
1108 SE->forgetAllLoops();
1109 else {
1110 SE->forgetTopmostLoop(L);
1111 SE->forgetBlockAndLoopDispositions();
1112 }
1113 }
1114
1115 if (!LatchIsExiting)
1116 ++NumUnrolledNotLatch;
1117
1118 // For the first iteration of the loop, we should use the precloned values for
1119 // PHI nodes. Insert associations now.
1120 ValueToValueMapTy LastValueMap;
1121 std::vector<PHINode*> OrigPHINode;
1122 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(Val: I); ++I) {
1123 OrigPHINode.push_back(x: cast<PHINode>(Val&: I));
1124 }
1125
1126 // Collect phi nodes for reductions for which we can introduce multiple
1127 // parallel reduction phis and compute the final reduction result after the
1128 // loop. This requires a single exit block after unrolling. This is ensured by
1129 // restricting to single-block loops where the unrolled iterations are known
1130 // to not exit.
1131 DenseMap<PHINode *, RecurrenceDescriptor> Reductions;
1132 bool CanAddAdditionalAccumulators =
1133 (UnrollAddParallelReductions.getNumOccurrences() > 0
1134 ? UnrollAddParallelReductions
1135 : ULO.AddAdditionalAccumulators) &&
1136 !CompletelyUnroll && L->getNumBlocks() == 1 &&
1137 (ULO.Runtime ||
1138 (ExitInfos.contains(Key: Header) && ((ExitInfos[Header].TripCount != 0 &&
1139 ExitInfos[Header].BreakoutTrip == 0))));
1140
1141 // Limit parallelizing reductions to unroll counts of 4 or less for now.
1142 // TODO: The number of parallel reductions should depend on the number of
1143 // execution units. We also don't have to add a parallel reduction phi per
1144 // unrolled iteration, but could for example add a parallel phi for every 2
1145 // unrolled iterations.
1146 if (CanAddAdditionalAccumulators && ULO.Count <= 4) {
1147 for (PHINode &Phi : Header->phis()) {
1148 auto RdxDesc = canParallelizeReductionWhenUnrolling(Phi, L, SE);
1149 if (!RdxDesc)
1150 continue;
1151
1152 // Only handle duplicate phis for a single reduction for now.
1153 // TODO: Handle any number of reductions
1154 if (!Reductions.empty())
1155 continue;
1156
1157 Reductions[&Phi] = *RdxDesc;
1158 }
1159 }
1160
1161 std::vector<BasicBlock *> Headers;
1162 std::vector<BasicBlock *> Latches;
1163 Headers.push_back(x: Header);
1164 Latches.push_back(x: LatchBlock);
1165
1166 // The current on-the-fly SSA update requires blocks to be processed in
1167 // reverse postorder so that LastValueMap contains the correct value at each
1168 // exit.
1169 LoopBlocksDFS DFS(L);
1170 DFS.perform(LI);
1171
1172 // Stash the DFS iterators before adding blocks to the loop.
1173 LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();
1174 LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();
1175
1176 std::vector<BasicBlock*> UnrolledLoopBlocks = L->getBlocks();
1177
1178 // Snapshot the blocks to be cloned after remainder generation, which may
1179 // delete blocks from L, but before cloning adds new blocks to L.
1180 const std::vector<BasicBlock *> PostRemainderLoopBlocks = L->getBlocks();
1181
1182 // Loop Unrolling might create new loops. While we do preserve LoopInfo, we
1183 // might break loop-simplified form for these loops (as they, e.g., would
1184 // share the same exit blocks). We'll keep track of loops for which we can
1185 // break this so that later we can re-simplify them.
1186 SmallSetVector<Loop *, 4> LoopsToSimplify;
1187 LoopsToSimplify.insert_range(R&: *L);
1188
1189 // When a FSDiscriminator is enabled, we don't need to add the multiply
1190 // factors to the discriminators.
1191 if (Header->getParent()->shouldEmitDebugInfoForProfiling() &&
1192 !EnableFSDiscriminator)
1193 for (BasicBlock *BB : L->getBlocks())
1194 for (Instruction &I : *BB)
1195 if (!isa<PseudoProbeInst>(Val: I))
1196 if (const DILocation *DIL = I.getDebugLoc()) {
1197 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(DF: ULO.Count);
1198 if (NewDIL)
1199 I.setDebugLoc(*NewDIL);
1200 else
1201 LLVM_DEBUG(dbgs()
1202 << "Failed to create new discriminator: "
1203 << DIL->getFilename() << " Line: " << DIL->getLine());
1204 }
1205
1206 // Identify what noalias metadata is inside the loop: if it is inside the
1207 // loop, the associated metadata must be cloned for each iteration.
1208 SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;
1209 identifyNoAliasScopesToClone(BBs: L->getBlocks(), NoAliasDeclScopes&: LoopLocalNoAliasDeclScopes);
1210
1211 // We place the unrolled iterations immediately after the original loop
1212 // latch. This is a reasonable default placement if we don't have block
1213 // frequencies, and if we do, well the layout will be adjusted later.
1214 auto BlockInsertPt = std::next(x: LatchBlock->getIterator());
1215 SmallVector<Instruction *> PartialReductions;
1216 for (unsigned It = 1; It != ULO.Count; ++It) {
1217 SmallVector<BasicBlock *, 8> NewBlocks;
1218 SmallDenseMap<const Loop *, Loop *, 4> NewLoops;
1219 NewLoops[L] = L;
1220
1221 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
1222 ValueToValueMapTy VMap;
1223 BasicBlock *New = CloneBasicBlock(BB: *BB, VMap, NameSuffix: "." + Twine(It));
1224 Header->getParent()->insert(Position: BlockInsertPt, BB: New);
1225
1226 assert((*BB != Header || LI->getLoopFor(*BB) == L) &&
1227 "Header should not be in a sub-loop");
1228 // Tell LI about New.
1229 const Loop *OldLoop = addClonedBlockToLoopInfo(OriginalBB: *BB, ClonedBB: New, LI, NewLoops);
1230 if (OldLoop)
1231 LoopsToSimplify.insert(X: NewLoops[OldLoop]);
1232
1233 if (*BB == Header) {
1234 // Loop over all of the PHI nodes in the block, changing them to use
1235 // the incoming values from the previous block.
1236 for (PHINode *OrigPHI : OrigPHINode) {
1237 PHINode *NewPHI = cast<PHINode>(Val&: VMap[OrigPHI]);
1238 Value *InVal = NewPHI->getIncomingValueForBlock(BB: LatchBlock);
1239
1240 // Use cloned phis as parallel phis for partial reductions, which will
1241 // get combined to the final reduction result after the loop.
1242 if (Reductions.contains(Val: OrigPHI)) {
1243 // Collect partial reduction results.
1244 if (PartialReductions.empty())
1245 PartialReductions.push_back(Elt: cast<Instruction>(Val: InVal));
1246 PartialReductions.push_back(Elt: cast<Instruction>(Val&: VMap[InVal]));
1247
1248 // Update the start value for the cloned phis to use the identity
1249 // value for the reduction.
1250 const RecurrenceDescriptor &RdxDesc = Reductions[OrigPHI];
1251 NewPHI->setIncomingValueForBlock(
1252 BB: L->getLoopPreheader(),
1253 V: getRecurrenceIdentity(K: RdxDesc.getRecurrenceKind(),
1254 Tp: OrigPHI->getType(),
1255 FMF: RdxDesc.getFastMathFlags()));
1256
1257 // Update NewPHI to use the cloned value for the iteration and move
1258 // to header.
1259 NewPHI->replaceUsesOfWith(From: InVal, To: VMap[InVal]);
1260 NewPHI->moveBefore(InsertPos: OrigPHI->getIterator());
1261 continue;
1262 }
1263
1264 if (Instruction *InValI = dyn_cast<Instruction>(Val: InVal))
1265 if (It > 1 && L->contains(Inst: InValI))
1266 InVal = LastValueMap[InValI];
1267 VMap[OrigPHI] = InVal;
1268 NewPHI->eraseFromParent();
1269 }
1270
1271 // Eliminate copies of the loop heart intrinsic, if any.
1272 if (ULO.Heart) {
1273 auto it = VMap.find(Val: ULO.Heart);
1274 assert(it != VMap.end());
1275 Instruction *heartCopy = cast<Instruction>(Val&: it->second);
1276 heartCopy->eraseFromParent();
1277 VMap.erase(I: it);
1278 }
1279 }
1280
1281 // Remap source location atom instance. Do this now, rather than
1282 // when we remap instructions, because remap is called once we've
1283 // cloned all blocks (all the clones would get the same atom
1284 // number).
1285 if (!VMap.AtomMap.empty())
1286 for (Instruction &I : *New)
1287 RemapSourceAtom(I: &I, VM&: VMap);
1288
1289 // Update our running map of newest clones
1290 LastValueMap[*BB] = New;
1291 for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();
1292 VI != VE; ++VI)
1293 LastValueMap[VI->first] = VI->second;
1294
1295 // Add phi entries for newly created values to all exit blocks.
1296 for (BasicBlock *Succ : successors(BB: *BB)) {
1297 if (L->contains(BB: Succ))
1298 continue;
1299 for (PHINode &PHI : Succ->phis()) {
1300 Value *Incoming = PHI.getIncomingValueForBlock(BB: *BB);
1301 ValueToValueMapTy::iterator It = LastValueMap.find(Val: Incoming);
1302 if (It != LastValueMap.end())
1303 Incoming = It->second;
1304 PHI.addIncoming(V: Incoming, BB: New);
1305 SE->forgetLcssaPhiWithNewPredecessor(L, V: &PHI);
1306 }
1307 }
1308 // Keep track of new headers and latches as we create them, so that
1309 // we can insert the proper branches later.
1310 if (*BB == Header)
1311 Headers.push_back(x: New);
1312 if (*BB == LatchBlock)
1313 Latches.push_back(x: New);
1314
1315 // Keep track of the exiting block and its successor block contained in
1316 // the loop for the current iteration.
1317 auto ExitInfoIt = ExitInfos.find(Key: *BB);
1318 if (ExitInfoIt != ExitInfos.end())
1319 ExitInfoIt->second.ExitingBlocks.push_back(Elt: New);
1320
1321 NewBlocks.push_back(Elt: New);
1322 UnrolledLoopBlocks.push_back(x: New);
1323
1324 // Update DomTree: since we just copy the loop body, and each copy has a
1325 // dedicated entry block (copy of the header block), this header's copy
1326 // dominates all copied blocks. That means, dominance relations in the
1327 // copied body are the same as in the original body.
1328 if (*BB == Header)
1329 DT->addNewBlock(BB: New, DomBB: Latches[It - 1]);
1330 else {
1331 auto BBDomNode = DT->getNode(BB: *BB);
1332 auto BBIDom = BBDomNode->getIDom();
1333 BasicBlock *OriginalBBIDom = BBIDom->getBlock();
1334 DT->addNewBlock(
1335 BB: New, DomBB: cast<BasicBlock>(Val&: LastValueMap[cast<Value>(Val: OriginalBBIDom)]));
1336 }
1337 }
1338
1339 // Remap all instructions in the most recent iteration.
1340 // Key Instructions: Nothing to do - we've already remapped the atoms.
1341 remapInstructionsInBlocks(Blocks: NewBlocks, VMap&: LastValueMap);
1342 for (BasicBlock *NewBlock : NewBlocks)
1343 for (Instruction &I : *NewBlock)
1344 if (auto *II = dyn_cast<AssumeInst>(Val: &I))
1345 AC->registerAssumption(CI: II);
1346
1347 {
1348 // Identify what other metadata depends on the cloned version. After
1349 // cloning, replace the metadata with the corrected version for both
1350 // memory instructions and noalias intrinsics.
1351 std::string ext = (Twine("It") + Twine(It)).str();
1352 cloneAndAdaptNoAliasScopes(NoAliasDeclScopes: LoopLocalNoAliasDeclScopes, NewBlocks,
1353 Context&: Header->getContext(), Ext: ext);
1354 }
1355 }
1356
1357 // Loop over the PHI nodes in the original block, setting incoming values.
1358 for (PHINode *PN : OrigPHINode) {
1359 if (CompletelyUnroll) {
1360 // The RAUW below disconnects the original PHI from its users.
1361 // Invalidate cached SCEVs while the def-use chain is still intact.
1362 if (SE)
1363 SE->forgetValue(V: PN);
1364 PN->replaceAllUsesWith(V: PN->getIncomingValueForBlock(BB: Preheader));
1365 PN->eraseFromParent();
1366 } else if (ULO.Count > 1) {
1367 if (Reductions.contains(Val: PN))
1368 continue;
1369
1370 Value *InVal = PN->removeIncomingValue(BB: LatchBlock, DeletePHIIfEmpty: false);
1371 // If this value was defined in the loop, take the value defined by the
1372 // last iteration of the loop.
1373 if (Instruction *InValI = dyn_cast<Instruction>(Val: InVal)) {
1374 if (L->contains(Inst: InValI))
1375 InVal = LastValueMap[InVal];
1376 }
1377 assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch");
1378 PN->addIncoming(V: InVal, BB: Latches.back());
1379 }
1380 }
1381
1382 // Connect latches of the unrolled iterations to the headers of the next
1383 // iteration. Currently they point to the header of the same iteration.
1384 for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
1385 unsigned j = (i + 1) % e;
1386 Latches[i]->getTerminator()->replaceSuccessorWith(OldBB: Headers[i], NewBB: Headers[j]);
1387 }
1388
1389 // Remove loop metadata copied from the original loop latch to branches that
1390 // are no longer latches.
1391 for (unsigned I = 0, E = Latches.size() - (CompletelyUnroll ? 0 : 1); I < E;
1392 ++I)
1393 Latches[I]->getTerminator()->setMetadata(KindID: LLVMContext::MD_loop, Node: nullptr);
1394
1395 // Update dominators of blocks we might reach through exits.
1396 // Immediate dominator of such block might change, because we add more
1397 // routes which can lead to the exit: we can now reach it from the copied
1398 // iterations too.
1399 if (ULO.Count > 1) {
1400 for (auto *BB : PostRemainderLoopBlocks) {
1401 auto *BBDomNode = DT->getNode(BB);
1402 SmallVector<BasicBlock *, 16> ChildrenToUpdate;
1403 for (auto *ChildDomNode : BBDomNode->children()) {
1404 auto *ChildBB = ChildDomNode->getBlock();
1405 if (!L->contains(BB: ChildBB))
1406 ChildrenToUpdate.push_back(Elt: ChildBB);
1407 }
1408 // The new idom of the block will be the nearest common dominator
1409 // of all copies of the previous idom. This is equivalent to the
1410 // nearest common dominator of the previous idom and the first latch,
1411 // which dominates all copies of the previous idom.
1412 BasicBlock *NewIDom = DT->findNearestCommonDominator(A: BB, B: LatchBlock);
1413 for (auto *ChildBB : ChildrenToUpdate)
1414 DT->changeImmediateDominator(BB: ChildBB, NewBB: NewIDom);
1415 }
1416 }
1417
1418 assert(!UnrollVerifyDomtree ||
1419 DT->verify(DominatorTree::VerificationLevel::Fast));
1420
1421 SmallVector<DominatorTree::UpdateType> DTUpdates;
1422 auto SetDest = [&](BasicBlock *Src, bool WillExit, bool ExitOnTrue) {
1423 auto *Term = cast<CondBrInst>(Val: Src->getTerminator());
1424 const unsigned Idx = ExitOnTrue ^ WillExit;
1425 BasicBlock *Dest = Term->getSuccessor(i: Idx);
1426 BasicBlock *DeadSucc = Term->getSuccessor(i: 1-Idx);
1427
1428 // Remove predecessors from all non-Dest successors.
1429 DeadSucc->removePredecessor(Pred: Src, /* KeepOneInputPHIs */ true);
1430
1431 // Replace the conditional branch with an unconditional one.
1432 auto *BI = UncondBrInst::Create(Target: Dest, InsertBefore: Term->getIterator());
1433 BI->setDebugLoc(Term->getDebugLoc());
1434 Term->eraseFromParent();
1435
1436 DTUpdates.emplace_back(Args: DominatorTree::Delete, Args&: Src, Args&: DeadSucc);
1437 };
1438
1439 auto WillExit = [&](const ExitInfo &Info, unsigned i, unsigned j,
1440 bool IsLatch) -> std::optional<bool> {
1441 if (CompletelyUnroll) {
1442 if (PreserveOnlyFirst) {
1443 if (i == 0)
1444 return std::nullopt;
1445 return j == 0;
1446 }
1447 // Complete (but possibly inexact) unrolling
1448 if (j == 0)
1449 return true;
1450 if (Info.TripCount && j != Info.TripCount)
1451 return false;
1452 return std::nullopt;
1453 }
1454
1455 if (ULO.Runtime) {
1456 // If runtime unrolling inserts a prologue, information about non-latch
1457 // exits may be stale.
1458 if (IsLatch && j != 0)
1459 return false;
1460 return std::nullopt;
1461 }
1462
1463 if (j != Info.BreakoutTrip &&
1464 (Info.TripMultiple == 0 || j % Info.TripMultiple != 0)) {
1465 // If we know the trip count or a multiple of it, we can safely use an
1466 // unconditional branch for some iterations.
1467 return false;
1468 }
1469 return std::nullopt;
1470 };
1471
1472 // Fold branches for iterations where we know that they will exit or not
1473 // exit. In the case of an iteration's latch, if we thus find
1474 // *OriginalLoopProb is incorrect, set ProbUpdateRequired to true.
1475 bool ProbUpdateRequired = false;
1476 for (auto &Pair : ExitInfos) {
1477 ExitInfo &Info = Pair.second;
1478 for (unsigned i = 0, e = Info.ExitingBlocks.size(); i != e; ++i) {
1479 // The branch destination.
1480 unsigned j = (i + 1) % e;
1481 bool IsLatch = Pair.first == LatchBlock;
1482 std::optional<bool> KnownWillExit = WillExit(Info, i, j, IsLatch);
1483 if (!KnownWillExit) {
1484 if (!Info.FirstExitingBlock)
1485 Info.FirstExitingBlock = Info.ExitingBlocks[i];
1486 continue;
1487 }
1488
1489 // We don't fold known-exiting branches for non-latch exits here,
1490 // because this ensures that both all loop blocks and all exit blocks
1491 // remain reachable in the CFG.
1492 // TODO: We could fold these branches, but it would require much more
1493 // sophisticated updates to LoopInfo.
1494 if (*KnownWillExit && !IsLatch) {
1495 if (!Info.FirstExitingBlock)
1496 Info.FirstExitingBlock = Info.ExitingBlocks[i];
1497 continue;
1498 }
1499
1500 // For a latch, record any OriginalLoopProb contradiction.
1501 if (!OriginalLoopProb.isUnknown() && IsLatch) {
1502 BranchProbability ActualProb = *KnownWillExit
1503 ? BranchProbability::getZero()
1504 : BranchProbability::getOne();
1505 ProbUpdateRequired |= OriginalLoopProb != ActualProb;
1506 }
1507
1508 SetDest(Info.ExitingBlocks[i], *KnownWillExit, Info.ExitOnTrue);
1509 }
1510 }
1511
1512 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
1513 DomTreeUpdater *DTUToUse = &DTU;
1514 if (ExitingBlocks.size() == 1 && ExitInfos.size() == 1) {
1515 // Manually update the DT if there's a single exiting node. In that case
1516 // there's a single exit node and it is sufficient to update the nodes
1517 // immediately dominated by the original exiting block. They will become
1518 // dominated by the first exiting block that leaves the loop after
1519 // unrolling. Note that the CFG inside the loop does not change, so there's
1520 // no need to update the DT inside the unrolled loop.
1521 DTUToUse = nullptr;
1522 auto &[OriginalExit, Info] = *ExitInfos.begin();
1523 if (!Info.FirstExitingBlock)
1524 Info.FirstExitingBlock = Info.ExitingBlocks.back();
1525 for (auto *C : to_vector(Range: DT->getNode(BB: OriginalExit)->children())) {
1526 if (L->contains(BB: C->getBlock()))
1527 continue;
1528 C->setIDom(DT->getNode(BB: Info.FirstExitingBlock));
1529 }
1530 } else {
1531 DTU.applyUpdates(Updates: DTUpdates);
1532 }
1533
1534 // When completely unrolling, the last latch becomes unreachable.
1535 if (!LatchIsExiting && CompletelyUnroll) {
1536 // There is no need to update the DT here, because there must be a unique
1537 // latch. Hence if the latch is not exiting it must directly branch back to
1538 // the original loop header and does not dominate any nodes.
1539 assert(LatchBlock->getSingleSuccessor() && "Loop with multiple latches?");
1540 changeToUnreachable(I: Latches.back()->getTerminator(), PreserveLCSSA);
1541 }
1542
1543 // After merging adjacent blocks in Latches below:
1544 // - CondLatches will list the blocks from Latches that are still terminated
1545 // with conditional branches.
1546 // - For 1 <= I < CondLatches.size(), IterCounts[I] will store the number of
1547 // the original loop iterations through which control flows from
1548 // CondLatches[I-1] to CondLatches[I].
1549 // - For I == 0 or I == CondLatches.size(), IterCounts[I] will store the
1550 // number of the original loop iterations through which control can flow
1551 // before CondLatches.front() or after CondLatches.back(), respectively,
1552 // without taking the unrolled loop's backedge, if any.
1553 // - CondLatchNexts[I] will store the CondLatches[I] branch target for the
1554 // next of the original loop's iterations (as opposed to the exit target).
1555 assert(ULO.Count == Latches.size() &&
1556 "Expected one latch block per unrolled iteration");
1557 std::vector<unsigned> IterCounts(1, 0);
1558 std::vector<BasicBlock *> CondLatches;
1559 std::vector<BasicBlock *> CondLatchNexts;
1560 IterCounts.reserve(n: Latches.size() + 1);
1561 CondLatches.reserve(n: Latches.size());
1562 CondLatchNexts.reserve(n: Latches.size());
1563
1564 // Merge adjacent basic blocks, if possible.
1565 for (auto [I, Latch] : enumerate(First&: Latches)) {
1566 ++IterCounts.back();
1567 assert((isa<UncondBrInst, CondBrInst>(Latch->getTerminator()) ||
1568 (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) &&
1569 "Need a branch as terminator, except when fully unrolling with "
1570 "unconditional latch");
1571 if (auto *Term = dyn_cast<UncondBrInst>(Val: Latch->getTerminator())) {
1572 BasicBlock *Dest = Term->getSuccessor();
1573 BasicBlock *Fold = Dest->getUniquePredecessor();
1574 if (MergeBlockIntoPredecessor(BB: Dest, /*DTU=*/DTUToUse, LI,
1575 /*MSSAU=*/nullptr, /*MemDep=*/nullptr,
1576 /*PredecessorWithTwoSuccessors=*/false,
1577 DT: DTUToUse ? nullptr : DT)) {
1578 // Dest has been folded into Fold. Update our worklists accordingly.
1579 llvm::replace(Range&: Latches, OldValue: Dest, NewValue: Fold);
1580 llvm::erase(C&: UnrolledLoopBlocks, V: Dest);
1581 }
1582 } else if (isa<CondBrInst>(Val: Latch->getTerminator())) {
1583 IterCounts.push_back(x: 0);
1584 CondLatches.push_back(x: Latch);
1585 CondLatchNexts.push_back(x: Headers[(I + 1) % Latches.size()]);
1586 }
1587 }
1588
1589 // Fix probabilities we contradicted above.
1590 if (ProbUpdateRequired) {
1591 fixProbContradiction(L, ULO, ORE, OriginalLoopProb, CompletelyUnroll,
1592 IterCounts, CondLatches, CondLatchNexts);
1593 }
1594
1595 // If there are partial reductions, create code in the exit block to compute
1596 // the final result and update users of the final result.
1597 if (!PartialReductions.empty()) {
1598 BasicBlock *ExitBlock = L->getExitBlock();
1599 assert(ExitBlock &&
1600 "Can only introduce parallel reduction phis with single exit block");
1601 assert(Reductions.size() == 1 &&
1602 "currently only a single reduction is supported");
1603 Value *FinalRdxValue = PartialReductions.back();
1604 Value *RdxResult = nullptr;
1605 for (PHINode &Phi : ExitBlock->phis()) {
1606 if (Phi.getIncomingValueForBlock(BB: L->getLoopLatch()) != FinalRdxValue)
1607 continue;
1608 if (!RdxResult) {
1609 RdxResult = PartialReductions.front();
1610 IRBuilder Builder(ExitBlock->getFirstNonPHIIt());
1611 Builder.setFastMathFlags(Reductions.begin()->second.getFastMathFlags());
1612 RecurKind RK = Reductions.begin()->second.getRecurrenceKind();
1613 for (Instruction *RdxPart : drop_begin(RangeOrContainer&: PartialReductions)) {
1614 if (RecurrenceDescriptor::isMinMaxRecurrenceKind(Kind: RK))
1615 RdxResult = createMinMaxOp(Builder, RK, Left: RdxResult, Right: RdxPart);
1616 else
1617 RdxResult = Builder.CreateBinOp(
1618 Opc: (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(Kind: RK),
1619 LHS: RdxPart, RHS: RdxResult, Name: "bin.rdx");
1620 }
1621 NeedToFixLCSSA = true;
1622 for (Instruction *RdxPart : PartialReductions)
1623 RdxPart->dropPoisonGeneratingFlags();
1624 }
1625
1626 Phi.replaceAllUsesWith(V: RdxResult);
1627 }
1628 }
1629
1630 if (DTUToUse) {
1631 // Apply updates to the DomTree.
1632 DT = &DTU.getDomTree();
1633 }
1634 assert(!UnrollVerifyDomtree ||
1635 DT->verify(DominatorTree::VerificationLevel::Fast));
1636
1637 Loop *OuterL = L->getParentLoop();
1638 std::vector<BasicBlock *> Blocks;
1639 // Update LoopInfo if the loop is completely removed.
1640 if (CompletelyUnroll) {
1641 Blocks = L->getBlocks();
1642 LI->erase(L);
1643 // We shouldn't try to use `L` anymore.
1644 L = nullptr;
1645 }
1646
1647 // At this point, the code is well formed. We now simplify the unrolled loop,
1648 // doing constant propagation and dead code elimination as we go.
1649 simplifyLoopAfterUnroll(
1650 L, SimplifyIVs: !CompletelyUnroll && ULO.Count > 1, LI, SE, DT, AC, TTI,
1651 Blocks: CompletelyUnroll ? ArrayRef<BasicBlock *>(Blocks) : L->getBlocks(), AA);
1652
1653 NumCompletelyUnrolled += CompletelyUnroll;
1654 ++NumUnrolled;
1655
1656 if (!CompletelyUnroll) {
1657 // Update metadata for the loop's branch weights and estimated trip count:
1658 // - If ULO.Runtime, UnrollRuntimeLoopRemainder sets the guard branch
1659 // weights, latch branch weights, and estimated trip count of the
1660 // remainder loop it creates. It also sets the branch weights for the
1661 // unrolled loop guard it creates. The branch weights for the unrolled
1662 // loop latch are adjusted below. FIXME: Handle prologue loops.
1663 // - Otherwise, if unrolled loop iteration latches become unconditional,
1664 // branch weights are adjusted by the fixProbContradiction call above.
1665 // - Otherwise, the original loop's branch weights are correct for the
1666 // unrolled loop, so do not adjust them.
1667 // - In all cases, the unrolled loop's estimated trip count is set below.
1668 //
1669 // As an example of the last case, consider what happens if the unroll count
1670 // is 4 for a loop with an estimated trip count of 10 when we do not create
1671 // a remainder loop and all iterations' latches remain conditional. Each
1672 // unrolled iteration's latch still has the same probability of exiting the
1673 // loop as it did when in the original loop, and thus it should still have
1674 // the same branch weights. Each unrolled iteration's non-zero probability
1675 // of exiting already appropriately reduces the probability of reaching the
1676 // remaining iterations just as it did in the original loop. Trying to also
1677 // adjust the branch weights of the final unrolled iteration's latch (i.e.,
1678 // the backedge for the unrolled loop as a whole) to reflect its new trip
1679 // count of 3 will erroneously further reduce its block frequencies.
1680 // However, in case an analysis later needs to estimate the trip count of
1681 // the unrolled loop as a whole without considering the branch weights for
1682 // each unrolled iteration's latch within it, we store the new trip count as
1683 // separate metadata.
1684 if (!OriginalLoopProb.isUnknown() && ULO.Runtime && EpilogProfitability) {
1685 assert((CondLatches.size() == 1 &&
1686 (ProbUpdateRequired || OriginalLoopProb.isOne())) &&
1687 "Expected ULO.Runtime to give unrolled loop 1 conditional latch, "
1688 "the backedge, requiring a probability update unless infinite");
1689 // Where p is always the probability of executing at least 1 more
1690 // iteration, the probability for at least n more iterations is p^n.
1691 setLoopProbability(L, P: OriginalLoopProb.pow(N: ULO.Count));
1692 }
1693 if (OriginalTripCount) {
1694 unsigned NewTripCount = *OriginalTripCount / ULO.Count;
1695 if (!ULO.Runtime && *OriginalTripCount % ULO.Count)
1696 ++NewTripCount;
1697 setLoopEstimatedTripCount(L, EstimatedTripCount: NewTripCount);
1698 }
1699 }
1700
1701 // LoopInfo should not be valid, confirm that.
1702 if (UnrollVerifyLoopInfo)
1703 LI->verify();
1704
1705 // After complete unrolling most of the blocks should be contained in OuterL.
1706 // However, some of them might happen to be out of OuterL (e.g. if they
1707 // precede a loop exit). In this case we might need to insert PHI nodes in
1708 // order to preserve LCSSA form.
1709 // We don't need to check this if we already know that we need to fix LCSSA
1710 // form.
1711 // TODO: For now we just recompute LCSSA for the outer loop in this case, but
1712 // it should be possible to fix it in-place.
1713 if (PreserveLCSSA && OuterL && CompletelyUnroll && !NeedToFixLCSSA)
1714 NeedToFixLCSSA |= ::needToInsertPhisForLCSSA(L: OuterL, Blocks: UnrolledLoopBlocks, LI);
1715
1716 // Make sure that loop-simplify form is preserved. We want to simplify
1717 // at least one layer outside of the loop that was unrolled so that any
1718 // changes to the parent loop exposed by the unrolling are considered.
1719 if (OuterL) {
1720 // OuterL includes all loops for which we can break loop-simplify, so
1721 // it's sufficient to simplify only it (it'll recursively simplify inner
1722 // loops too).
1723 if (NeedToFixLCSSA) {
1724 // LCSSA must be performed on the outermost affected loop. The unrolled
1725 // loop's last loop latch is guaranteed to be in the outermost loop
1726 // after LoopInfo's been updated by LoopInfo::erase.
1727 Loop *LatchLoop = LI->getLoopFor(BB: Latches.back());
1728 Loop *FixLCSSALoop = OuterL;
1729 if (!FixLCSSALoop->contains(L: LatchLoop))
1730 while (FixLCSSALoop->getParentLoop() != LatchLoop)
1731 FixLCSSALoop = FixLCSSALoop->getParentLoop();
1732
1733 formLCSSARecursively(L&: *FixLCSSALoop, DT: *DT, LI, SE);
1734 } else if (PreserveLCSSA) {
1735 assert(OuterL->isLCSSAForm(*DT) &&
1736 "Loops should be in LCSSA form after loop-unroll.");
1737 }
1738
1739 // TODO: That potentially might be compile-time expensive. We should try
1740 // to fix the loop-simplified form incrementally.
1741 simplifyLoop(L: OuterL, DT, LI, SE, AC, MSSAU: nullptr, PreserveLCSSA);
1742 } else {
1743 // Simplify loops for which we might've broken loop-simplify form.
1744 for (Loop *SubLoop : LoopsToSimplify)
1745 simplifyLoop(L: SubLoop, DT, LI, SE, AC, MSSAU: nullptr, PreserveLCSSA);
1746 }
1747
1748 return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled
1749 : LoopUnrollResult::PartiallyUnrolled;
1750}
1751
1752/// Given an llvm.loop loop id metadata node, returns the loop hint metadata
1753/// node with the given name (for example, "llvm.loop.unroll.count"). If no
1754/// such metadata node exists, then nullptr is returned.
1755MDNode *llvm::GetUnrollMetadata(MDNode *LoopID, StringRef Name) {
1756 // First operand should refer to the loop id itself.
1757 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1758 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1759
1760 for (MDNode *MD :
1761 make_isa_range<MDNode>(Range: llvm::drop_begin(RangeOrContainer: LoopID->operands()))) {
1762 MDString *S = dyn_cast<MDString>(Val: MD->getOperand(I: 0));
1763 if (!S)
1764 continue;
1765
1766 if (Name == S->getString())
1767 return MD;
1768 }
1769 return nullptr;
1770}
1771
1772// Returns the loop hint metadata node with the given name (for example,
1773// "llvm.loop.unroll.count"). If no such metadata node exists, then nullptr is
1774// returned.
1775MDNode *llvm::getUnrollMetadataForLoop(const Loop *L, StringRef Name) {
1776 if (MDNode *LoopID = L->getLoopID())
1777 return GetUnrollMetadata(LoopID, Name);
1778 return nullptr;
1779}
1780
1781std::optional<RecurrenceDescriptor>
1782llvm::canParallelizeReductionWhenUnrolling(PHINode &Phi, Loop *L,
1783 ScalarEvolution *SE) {
1784 RecurrenceDescriptor RdxDesc;
1785 if (!RecurrenceDescriptor::isReductionPHI(Phi: &Phi, TheLoop: L, RedDes&: RdxDesc,
1786 /*DemandedBits=*/DB: nullptr,
1787 /*AC=*/nullptr, /*DT=*/nullptr, SE))
1788 return std::nullopt;
1789 if (RdxDesc.hasUsesOutsideReductionChain())
1790 return std::nullopt;
1791 RecurKind RK = RdxDesc.getRecurrenceKind();
1792 static const auto ValidRKs = {
1793 RecurKind::Add, RecurKind::Mul, RecurKind::Or,
1794 RecurKind::And, RecurKind::Xor, RecurKind::SMin,
1795 RecurKind::SMax, RecurKind::UMin, RecurKind::UMax,
1796 RecurKind::FAdd, RecurKind::FMul, RecurKind::FMin,
1797 RecurKind::FMax, RecurKind::FMinNum, RecurKind::FMaxNum,
1798 RecurKind::FMinimum, RecurKind::FMaximum, RecurKind::FMinimumNum,
1799 RecurKind::FMaximumNum, RecurKind::FMulAdd};
1800 // Skip unsupported reductions, including sub, any-of and find-last.
1801 // TODO: Handle sub, any-of and find-last reductions.
1802 if (!any_of(Range: ValidRKs, P: equal_to(Arg&: RK)))
1803 return std::nullopt;
1804
1805 if (RdxDesc.hasExactFPMath())
1806 return std::nullopt;
1807
1808 if (RdxDesc.IntermediateStore)
1809 return std::nullopt;
1810
1811 BasicBlock *Latch = L->getLoopLatch();
1812 if (!Latch)
1813 return std::nullopt;
1814 Instruction *LatchInst =
1815 cast<Instruction>(Val: Phi.getIncomingValueForBlock(BB: Latch));
1816 // Don't unroll reductions with constant ops; those can be folded to a
1817 // single induction update. For calls (e.g. fmuladd or min/max
1818 // intrinsics), the called function is itself a Constant operand and is
1819 // not a reduction operand, so restrict the check to the argument list.
1820 auto Ops = isa<CallBase>(Val: LatchInst) ? cast<CallBase>(Val: LatchInst)->args()
1821 : LatchInst->operands();
1822 if (any_of(Range&: Ops, P: IsaPred<Constant>))
1823 return std::nullopt;
1824
1825 if (!is_contained(Range: LatchInst->operands(), Element: &Phi))
1826 return std::nullopt;
1827
1828 return RdxDesc;
1829}
1830