1//===-- UnrollLoopRuntime.cpp - Runtime 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 for loops with run-time
10// trip counts. See LoopUnroll.cpp for unrolling loops with compile-time
11// trip counts.
12//
13// The functions in this file are used to generate extra code when the
14// run-time trip count modulo the unroll factor is not 0. When this is the
15// case, we need to generate code to execute these 'left over' iterations.
16//
17// The current strategy generates an if-then-else sequence prior to the
18// unrolled loop to execute the 'left over' iterations before or after the
19// unrolled loop.
20//
21//===----------------------------------------------------------------------===//
22
23#include "llvm/ADT/Statistic.h"
24#include "llvm/Analysis/DomTreeUpdater.h"
25#include "llvm/Analysis/InstructionSimplify.h"
26#include "llvm/Analysis/LoopIterator.h"
27#include "llvm/Analysis/ScalarEvolution.h"
28#include "llvm/Analysis/ValueTracking.h"
29#include "llvm/IR/BasicBlock.h"
30#include "llvm/IR/Dominators.h"
31#include "llvm/IR/MDBuilder.h"
32#include "llvm/IR/Module.h"
33#include "llvm/IR/ProfDataUtils.h"
34#include "llvm/Support/CommandLine.h"
35#include "llvm/Support/Debug.h"
36#include "llvm/Support/raw_ostream.h"
37#include "llvm/Transforms/Utils/BasicBlockUtils.h"
38#include "llvm/Transforms/Utils/Cloning.h"
39#include "llvm/Transforms/Utils/Local.h"
40#include "llvm/Transforms/Utils/LoopUtils.h"
41#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
42#include "llvm/Transforms/Utils/UnrollLoop.h"
43
44using namespace llvm;
45
46#define DEBUG_TYPE "loop-unroll"
47
48STATISTIC(NumRuntimeUnrolled,
49 "Number of loops unrolled with run-time trip counts");
50static cl::opt<bool> UnrollRuntimeMultiExit(
51 "unroll-runtime-multi-exit", cl::init(Val: false), cl::Hidden,
52 cl::desc("Allow runtime unrolling for loops with multiple exits, when "
53 "epilog is generated"));
54static cl::opt<bool> UnrollRuntimeOtherExitPredictable(
55 "unroll-runtime-other-exit-predictable", cl::init(Val: false), cl::Hidden,
56 cl::desc("Assume the non latch exit block to be predictable"));
57
58// Probability that the loop trip count is so small that after the prolog
59// we do not enter the unrolled loop at all.
60// It is unlikely that the loop trip count is smaller than the unroll factor;
61// other than that, the choice of constant is not tuned yet.
62static const uint32_t UnrolledLoopHeaderWeights[] = {1, 127};
63// Probability that the loop trip count is so small that we skip the unrolled
64// loop completely and immediately enter the epilogue loop.
65// It is unlikely that the loop trip count is smaller than the unroll factor;
66// other than that, the choice of constant is not tuned yet.
67static const uint32_t EpilogHeaderWeights[] = {1, 127};
68
69/// Connect the unrolling prolog code to the original loop.
70/// The unrolling prolog code contains code to execute the
71/// 'extra' iterations if the run-time trip count modulo the
72/// unroll count is non-zero.
73///
74/// This function performs the following:
75/// - Create PHI nodes at prolog end block to combine values
76/// that exit the prolog code and jump around the prolog.
77/// - Add a PHI operand to a PHI node at the loop exit block
78/// for values that exit the prolog and go around the loop.
79/// - Branch around the original loop if the trip count is less
80/// than the unroll factor.
81///
82static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
83 BasicBlock *PrologExit,
84 BasicBlock *OriginalLoopLatchExit,
85 BasicBlock *PreHeader, BasicBlock *NewPreHeader,
86 ValueToValueMapTy &VMap, DominatorTree *DT,
87 LoopInfo *LI, bool PreserveLCSSA,
88 ScalarEvolution &SE) {
89 // Loop structure should be the following:
90 // Preheader
91 // PrologHeader
92 // ...
93 // PrologLatch
94 // PrologExit
95 // NewPreheader
96 // Header
97 // ...
98 // Latch
99 // LatchExit
100 BasicBlock *Latch = L->getLoopLatch();
101 assert(Latch && "Loop must have a latch");
102 BasicBlock *PrologLatch = cast<BasicBlock>(Val&: VMap[Latch]);
103
104 // Create a PHI node for each outgoing value from the original loop
105 // (which means it is an outgoing value from the prolog code too).
106 // The new PHI node is inserted in the prolog end basic block.
107 // The new PHI node value is added as an operand of a PHI node in either
108 // the loop header or the loop exit block.
109 for (BasicBlock *Succ : successors(BB: Latch)) {
110 for (PHINode &PN : Succ->phis()) {
111 // Add a new PHI node to the prolog end block and add the
112 // appropriate incoming values.
113 // TODO: This code assumes that the PrologExit (or the LatchExit block for
114 // prolog loop) contains only one predecessor from the loop, i.e. the
115 // PrologLatch. When supporting multiple-exiting block loops, we can have
116 // two or more blocks that have the LatchExit as the target in the
117 // original loop.
118 PHINode *NewPN = PHINode::Create(Ty: PN.getType(), NumReservedValues: 2, NameStr: PN.getName() + ".unr");
119 NewPN->insertBefore(InsertPos: PrologExit->getFirstNonPHIIt());
120 // Adding a value to the new PHI node from the original loop preheader.
121 // This is the value that skips all the prolog code.
122 if (L->contains(Inst: &PN)) {
123 // Succ is loop header.
124 NewPN->addIncoming(V: PN.getIncomingValueForBlock(BB: NewPreHeader),
125 BB: PreHeader);
126 } else {
127 // Succ is LatchExit.
128 NewPN->addIncoming(V: PoisonValue::get(T: PN.getType()), BB: PreHeader);
129 }
130
131 Value *V = PN.getIncomingValueForBlock(BB: Latch);
132 if (Instruction *I = dyn_cast<Instruction>(Val: V)) {
133 if (L->contains(Inst: I)) {
134 V = VMap.lookup(Val: I);
135 }
136 }
137 // Adding a value to the new PHI node from the last prolog block
138 // that was created.
139 NewPN->addIncoming(V, BB: PrologLatch);
140
141 // Update the existing PHI node operand with the value from the
142 // new PHI node. How this is done depends on if the existing
143 // PHI node is in the original loop block, or the exit block.
144 if (L->contains(Inst: &PN))
145 PN.setIncomingValueForBlock(BB: NewPreHeader, V: NewPN);
146 else
147 PN.addIncoming(V: NewPN, BB: PrologExit);
148 SE.forgetLcssaPhiWithNewPredecessor(L, V: &PN);
149 }
150 }
151
152 // Make sure that created prolog loop is in simplified form
153 SmallVector<BasicBlock *, 4> PrologExitPreds;
154 Loop *PrologLoop = LI->getLoopFor(BB: PrologLatch);
155 if (PrologLoop) {
156 for (BasicBlock *PredBB : predecessors(BB: PrologExit))
157 if (PrologLoop->contains(BB: PredBB))
158 PrologExitPreds.push_back(Elt: PredBB);
159
160 SplitBlockPredecessors(BB: PrologExit, Preds: PrologExitPreds, Suffix: ".unr-lcssa", DT, LI,
161 MSSAU: nullptr, PreserveLCSSA);
162 }
163
164 // Create a branch around the original loop, which is taken if there are no
165 // iterations remaining to be executed after running the prologue.
166 Instruction *InsertPt = PrologExit->getTerminator();
167 IRBuilder<> B(InsertPt);
168
169 assert(Count != 0 && "nonsensical Count!");
170
171 // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)
172 // This means %xtraiter is (BECount + 1) and all of the iterations of this
173 // loop were executed by the prologue. Note that if BECount <u (Count - 1)
174 // then (BECount + 1) cannot unsigned-overflow.
175 Value *BrLoopExit =
176 B.CreateICmpULT(LHS: BECount, RHS: ConstantInt::get(Ty: BECount->getType(), V: Count - 1));
177 // Split the exit to maintain loop canonicalization guarantees
178 SmallVector<BasicBlock *, 4> Preds(predecessors(BB: OriginalLoopLatchExit));
179 SplitBlockPredecessors(BB: OriginalLoopLatchExit, Preds, Suffix: ".unr-lcssa", DT, LI,
180 MSSAU: nullptr, PreserveLCSSA);
181 // Add the branch to the exit block (around the unrolled loop)
182 MDNode *BranchWeights = nullptr;
183 if (hasBranchWeightMD(I: *Latch->getTerminator())) {
184 // Assume loop is nearly always entered.
185 MDBuilder MDB(B.getContext());
186 BranchWeights = MDB.createBranchWeights(Weights: UnrolledLoopHeaderWeights);
187 }
188 B.CreateCondBr(Cond: BrLoopExit, True: OriginalLoopLatchExit, False: NewPreHeader,
189 BranchWeights);
190 InsertPt->eraseFromParent();
191 if (DT) {
192 auto *NewDom = DT->findNearestCommonDominator(A: OriginalLoopLatchExit,
193 B: PrologExit);
194 DT->changeImmediateDominator(BB: OriginalLoopLatchExit, NewBB: NewDom);
195 }
196}
197
198/// Assume, due to our position in the remainder loop or its guard, anywhere
199/// from 0 to \p N more iterations can possibly execute. Among such cases in
200/// the original loop (with loop probability \p OriginalLoopProb), what is the
201/// probability of executing at least one more iteration?
202static BranchProbability
203probOfNextInRemainder(BranchProbability OriginalLoopProb, unsigned N) {
204 // OriginalLoopProb == 1 would produce a division by zero in the calculation
205 // below. The problem is that case indicates an always infinite loop, but a
206 // remainder loop cannot be calculated at run time if the original loop is
207 // infinite as infinity % UnrollCount is undefined. We then choose
208 // probabilities indicating that all remainder loop iterations will always
209 // execute.
210 //
211 // Currently, the remainder loop here is an epilogue, which cannot be reached
212 // if the original loop is infinite, so the aforementioned choice is
213 // arbitrary.
214 //
215 // FIXME: Branch weights still need to be fixed in the case of prologues
216 // (issue #135812). In that case, the aforementioned choice seems reasonable
217 // for the goal of maintaining the original loop's block frequencies. That
218 // is, an infinite loop's initial iterations are not skipped, and the prologue
219 // loop body might have unique blocks that execute a finite number of times
220 // if, for example, the original loop body contains conditionals like i <
221 // UnrollCount.
222 if (OriginalLoopProb.isOne())
223 return OriginalLoopProb;
224
225 // Each of these variables holds the original loop's probability that the
226 // number of iterations it will execute is some m in the specified range.
227 BranchProbability ProbOne = OriginalLoopProb; // 1 <= m
228 BranchProbability ProbTooMany = ProbOne.pow(N: N + 1); // N + 1 <= m
229 BranchProbability ProbNotTooMany = ProbTooMany.getCompl(); // 0 <= m <= N
230 BranchProbability ProbOneNotTooMany = ProbOne - ProbTooMany; // 1 <= m <= N
231 return ProbOneNotTooMany / ProbNotTooMany;
232}
233
234/// Connect the unrolling epilog code to the original loop.
235/// The unrolling epilog code contains code to execute the
236/// 'extra' iterations if the run-time trip count modulo the
237/// unroll count is non-zero.
238///
239/// This function performs the following:
240/// - Update PHI nodes at the epilog loop exit
241/// - Create PHI nodes at the unrolling loop exit and epilog preheader to
242/// combine values that exit the unrolling loop code and jump around it.
243/// - Update PHI operands in the epilog loop by the new PHI nodes
244/// - At the unrolling loop exit, branch around the epilog loop if extra iters
245// (ModVal) is zero.
246/// - At the epilog preheader, add an llvm.assume call that extra iters is
247/// non-zero. If the unrolling loop exit is the predecessor, the above new
248/// branch guarantees that assumption. If the unrolling loop preheader is the
249/// predecessor, then the required first iteration from the original loop has
250/// yet to be executed, so it must be executed in the epilog loop. If we
251/// later unroll the epilog loop, that llvm.assume call somehow enables
252/// ScalarEvolution to compute a epilog loop maximum trip count, which enables
253/// eliminating the branch at the end of the final unrolled epilog iteration.
254///
255static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,
256 BasicBlock *Exit, BasicBlock *PreHeader,
257 BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader,
258 ValueToValueMapTy &VMap, DominatorTree *DT,
259 LoopInfo *LI, bool PreserveLCSSA, ScalarEvolution &SE,
260 unsigned Count, AssumptionCache &AC,
261 BranchProbability OriginalLoopProb) {
262 BasicBlock *Latch = L->getLoopLatch();
263 assert(Latch && "Loop must have a latch");
264 BasicBlock *EpilogLatch = cast<BasicBlock>(Val&: VMap[Latch]);
265
266 // Loop structure should be the following:
267 //
268 // PreHeader
269 // NewPreHeader
270 // Header
271 // ...
272 // Latch
273 // NewExit (PN)
274 // EpilogPreHeader
275 // EpilogHeader
276 // ...
277 // EpilogLatch
278 // Exit (EpilogPN)
279
280 // Update PHI nodes at Exit.
281 for (PHINode &PN : NewExit->phis()) {
282 // PN should be used in another PHI located in Exit block as
283 // Exit was split by SplitBlockPredecessors into Exit and NewExit
284 // Basically it should look like:
285 // NewExit:
286 // PN = PHI [I, Latch]
287 // ...
288 // Exit:
289 // EpilogPN = PHI [PN, EpilogPreHeader], [X, Exit2], [Y, Exit2.epil]
290 //
291 // Exits from non-latch blocks point to the original exit block and the
292 // epilogue edges have already been added.
293 //
294 // There is EpilogPreHeader incoming block instead of NewExit as
295 // NewExit was split 1 more time to get EpilogPreHeader.
296 assert(PN.hasOneUse() && "The phi should have 1 use");
297 PHINode *EpilogPN = cast<PHINode>(Val: PN.use_begin()->getUser());
298 assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block");
299
300 Value *V = PN.getIncomingValueForBlock(BB: Latch);
301 Instruction *I = dyn_cast<Instruction>(Val: V);
302 if (I && L->contains(Inst: I))
303 // If value comes from an instruction in the loop add VMap value.
304 V = VMap.lookup(Val: I);
305 // For the instruction out of the loop, constant or undefined value
306 // insert value itself.
307 EpilogPN->addIncoming(V, BB: EpilogLatch);
308
309 assert(EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 &&
310 "EpilogPN should have EpilogPreHeader incoming block");
311 // Change EpilogPreHeader incoming block to NewExit.
312 EpilogPN->setIncomingBlock(i: EpilogPN->getBasicBlockIndex(BB: EpilogPreHeader),
313 BB: NewExit);
314 // Now PHIs should look like:
315 // NewExit:
316 // PN = PHI [I, Latch]
317 // ...
318 // Exit:
319 // EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]
320 }
321
322 // Create PHI nodes at NewExit (from the unrolling loop Latch) and at
323 // EpilogPreHeader (from PreHeader and NewExit). Update corresponding PHI
324 // nodes in epilog loop.
325 for (BasicBlock *Succ : successors(BB: Latch)) {
326 // Skip this as we already updated phis in exit blocks.
327 if (!L->contains(BB: Succ))
328 continue;
329
330 // Succ here appears to always be just L->getHeader(). Otherwise, how do we
331 // know its corresponding epilog block (from VMap) is EpilogHeader and thus
332 // EpilogPreHeader is the right incoming block for VPN, as set below?
333 // TODO: Can we thus avoid the enclosing loop over successors?
334 assert(Succ == L->getHeader() &&
335 "Expect the only in-loop successor of latch to be the loop header");
336
337 for (PHINode &PN : Succ->phis()) {
338 // Add new PHI nodes to the loop exit block.
339 PHINode *NewPN0 = PHINode::Create(Ty: PN.getType(), /*NumReservedValues=*/1,
340 NameStr: PN.getName() + ".unr");
341 NewPN0->insertBefore(InsertPos: NewExit->getFirstNonPHIIt());
342 // Add value to the new PHI node from the unrolling loop latch.
343 NewPN0->addIncoming(V: PN.getIncomingValueForBlock(BB: Latch), BB: Latch);
344
345 // Add new PHI nodes to EpilogPreHeader.
346 PHINode *NewPN1 = PHINode::Create(Ty: PN.getType(), /*NumReservedValues=*/2,
347 NameStr: PN.getName() + ".epil.init");
348 NewPN1->insertBefore(InsertPos: EpilogPreHeader->getFirstNonPHIIt());
349 // Add value to the new PHI node from the unrolling loop preheader.
350 NewPN1->addIncoming(V: PN.getIncomingValueForBlock(BB: NewPreHeader), BB: PreHeader);
351 // Add value to the new PHI node from the epilog loop guard.
352 NewPN1->addIncoming(V: NewPN0, BB: NewExit);
353
354 // Update the existing PHI node operand with the value from the new PHI
355 // node. Corresponding instruction in epilog loop should be PHI.
356 PHINode *VPN = cast<PHINode>(Val&: VMap[&PN]);
357 VPN->setIncomingValueForBlock(BB: EpilogPreHeader, V: NewPN1);
358 }
359 }
360
361 // In NewExit, branch around the epilog loop if no extra iters.
362 Instruction *InsertPt = NewExit->getTerminator();
363 IRBuilder<> B(InsertPt);
364 Value *BrLoopExit = B.CreateIsNotNull(Arg: ModVal, Name: "lcmp.mod");
365 assert(Exit && "Loop must have a single exit block only");
366 // Split the epilogue exit to maintain loop canonicalization guarantees
367 SmallVector<BasicBlock*, 4> Preds(predecessors(BB: Exit));
368 SplitBlockPredecessors(BB: Exit, Preds, Suffix: ".epilog-lcssa", DT, LI, MSSAU: nullptr,
369 PreserveLCSSA);
370 // Add the branch to the exit block (around the epilog loop)
371 MDNode *BranchWeights = nullptr;
372 if (OriginalLoopProb.isUnknown() &&
373 hasBranchWeightMD(I: *Latch->getTerminator())) {
374 // Assume equal distribution in interval [0, Count).
375 MDBuilder MDB(B.getContext());
376 BranchWeights = MDB.createBranchWeights(TrueWeight: 1, FalseWeight: Count - 1);
377 }
378 CondBrInst *RemainderLoopGuard =
379 B.CreateCondBr(Cond: BrLoopExit, True: EpilogPreHeader, False: Exit, BranchWeights);
380 if (!OriginalLoopProb.isUnknown()) {
381 setBranchProbability(B: RemainderLoopGuard,
382 P: probOfNextInRemainder(OriginalLoopProb, N: Count - 1),
383 /*ForFirstTarget=*/true);
384 }
385 InsertPt->eraseFromParent();
386 if (DT) {
387 auto *NewDom = DT->findNearestCommonDominator(A: Exit, B: NewExit);
388 DT->changeImmediateDominator(BB: Exit, NewBB: NewDom);
389 }
390
391 // In EpilogPreHeader, assume extra iters is non-zero.
392 IRBuilder<> B2(EpilogPreHeader, EpilogPreHeader->getFirstNonPHIIt());
393 Value *ModIsNotNull = B2.CreateIsNotNull(Arg: ModVal, Name: "lcmp.mod");
394 AssumeInst *AI = cast<AssumeInst>(Val: B2.CreateAssumption(Cond: ModIsNotNull));
395 AC.registerAssumption(CI: AI);
396}
397
398/// Create a clone of the blocks in a loop and connect them together. A new
399/// loop will be created including all cloned blocks, and the iterator of the
400/// new loop switched to count NewIter down to 0.
401/// The cloned blocks should be inserted between InsertTop and InsertBot.
402/// InsertTop should be new preheader, InsertBot new loop exit.
403/// Returns the new cloned loop that is created.
404static Loop *CloneLoopBlocks(Loop *L, Value *NewIter,
405 const bool UseEpilogRemainder,
406 const bool UnrollRemainder, BasicBlock *InsertTop,
407 BasicBlock *InsertBot, BasicBlock *Preheader,
408 std::vector<BasicBlock *> &NewBlocks,
409 LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap,
410 DominatorTree *DT, LoopInfo *LI, unsigned Count,
411 std::optional<unsigned> OriginalTripCount,
412 BranchProbability OriginalLoopProb) {
413 StringRef suffix = UseEpilogRemainder ? "epil" : "prol";
414 BasicBlock *Header = L->getHeader();
415 BasicBlock *Latch = L->getLoopLatch();
416 Function *F = Header->getParent();
417 LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
418 LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
419 Loop *ParentLoop = L->getParentLoop();
420 NewLoopsMap NewLoops;
421 NewLoops[ParentLoop] = ParentLoop;
422
423 // For each block in the original loop, create a new copy,
424 // and update the value map with the newly created values.
425 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
426 BasicBlock *NewBB = CloneBasicBlock(BB: *BB, VMap, NameSuffix: "." + suffix, F);
427 NewBlocks.push_back(x: NewBB);
428
429 addClonedBlockToLoopInfo(OriginalBB: *BB, ClonedBB: NewBB, LI, NewLoops);
430
431 VMap[*BB] = NewBB;
432 if (Header == *BB) {
433 // For the first block, add a CFG connection to this newly
434 // created block.
435 InsertTop->getTerminator()->setSuccessor(Idx: 0, BB: NewBB);
436 }
437
438 if (DT) {
439 if (Header == *BB) {
440 // The header is dominated by the preheader.
441 DT->addNewBlock(BB: NewBB, DomBB: InsertTop);
442 } else {
443 // Copy information from original loop to unrolled loop.
444 BasicBlock *IDomBB = DT->getNode(BB: *BB)->getIDom()->getBlock();
445 DT->addNewBlock(BB: NewBB, DomBB: cast<BasicBlock>(Val&: VMap[IDomBB]));
446 }
447 }
448
449 if (Latch == *BB) {
450 // For the last block, create a loop back to cloned head.
451 VMap.erase(Val: (*BB)->getTerminator());
452 // Use an incrementing IV. Pre-incr/post-incr is backedge/trip count.
453 // Subtle: NewIter can be 0 if we wrapped when computing the trip count,
454 // thus we must compare the post-increment (wrapping) value.
455 BasicBlock *FirstLoopBB = cast<BasicBlock>(Val&: VMap[Header]);
456 CondBrInst *LatchBR = cast<CondBrInst>(Val: NewBB->getTerminator());
457 IRBuilder<> Builder(LatchBR);
458 PHINode *NewIdx =
459 PHINode::Create(Ty: NewIter->getType(), NumReservedValues: 2, NameStr: suffix + ".iter");
460 NewIdx->insertBefore(InsertPos: FirstLoopBB->getFirstNonPHIIt());
461 auto *Zero = ConstantInt::get(Ty: NewIdx->getType(), V: 0);
462 auto *One = ConstantInt::get(Ty: NewIdx->getType(), V: 1);
463 Value *IdxNext =
464 Builder.CreateAdd(LHS: NewIdx, RHS: One, Name: NewIdx->getName() + ".next");
465 Value *IdxCmp = Builder.CreateICmpNE(LHS: IdxNext, RHS: NewIter, Name: NewIdx->getName() + ".cmp");
466 MDNode *BranchWeights = nullptr;
467 if ((OriginalLoopProb.isUnknown() || !UseEpilogRemainder) &&
468 hasBranchWeightMD(I: *LatchBR)) {
469 uint32_t ExitWeight;
470 uint32_t BackEdgeWeight;
471 if (Count >= 3) {
472 // Note: We do not enter this loop for zero-remainders. The check
473 // is at the end of the loop. We assume equal distribution between
474 // possible remainders in [1, Count).
475 ExitWeight = 1;
476 BackEdgeWeight = (Count - 2) / 2;
477 } else {
478 // Unnecessary backedge, should never be taken. The conditional
479 // jump should be optimized away later.
480 ExitWeight = 1;
481 BackEdgeWeight = 0;
482 }
483 MDBuilder MDB(Builder.getContext());
484 BranchWeights = MDB.createBranchWeights(TrueWeight: BackEdgeWeight, FalseWeight: ExitWeight);
485 }
486 CondBrInst *RemainderLoopLatch =
487 Builder.CreateCondBr(Cond: IdxCmp, True: FirstLoopBB, False: InsertBot, BranchWeights);
488 if (!OriginalLoopProb.isUnknown() && UseEpilogRemainder) {
489 // Compute the total frequency of the original loop body from the
490 // remainder iterations. Once we've reached them, the first of them
491 // always executes, so its frequency and probability are 1.
492 double FreqRemIters = 1;
493 if (Count > 2) {
494 BranchProbability ProbReaching = BranchProbability::getOne();
495 for (unsigned N = Count - 2; N >= 1; --N) {
496 ProbReaching *= probOfNextInRemainder(OriginalLoopProb, N);
497 FreqRemIters += ProbReaching.toDouble();
498 }
499 }
500 // Solve for the loop probability that would produce that frequency.
501 // Sum(i=0..inf)(Prob^i) = 1/(1-Prob) = FreqRemIters.
502 BranchProbability Prob =
503 BranchProbability::getBranchProbability(Prob: 1 - 1 / FreqRemIters);
504 setBranchProbability(B: RemainderLoopLatch, P: Prob, /*ForFirstTarget=*/true);
505 }
506 NewIdx->addIncoming(V: Zero, BB: InsertTop);
507 NewIdx->addIncoming(V: IdxNext, BB: NewBB);
508 LatchBR->eraseFromParent();
509 }
510 }
511
512 // Change the incoming values to the ones defined in the preheader or
513 // cloned loop.
514 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(Val: I); ++I) {
515 PHINode *NewPHI = cast<PHINode>(Val&: VMap[&*I]);
516 unsigned idx = NewPHI->getBasicBlockIndex(BB: Preheader);
517 NewPHI->setIncomingBlock(i: idx, BB: InsertTop);
518 BasicBlock *NewLatch = cast<BasicBlock>(Val&: VMap[Latch]);
519 idx = NewPHI->getBasicBlockIndex(BB: Latch);
520 Value *InVal = NewPHI->getIncomingValue(i: idx);
521 NewPHI->setIncomingBlock(i: idx, BB: NewLatch);
522 if (Value *V = VMap.lookup(Val: InVal))
523 NewPHI->setIncomingValue(i: idx, V);
524 }
525
526 Loop *NewLoop = NewLoops[L];
527 assert(NewLoop && "L should have been cloned");
528
529 if (OriginalTripCount && UseEpilogRemainder)
530 setLoopEstimatedTripCount(L: NewLoop, EstimatedTripCount: *OriginalTripCount % Count);
531
532 // Add unroll disable metadata to disable future unrolling for this loop.
533 if (!UnrollRemainder)
534 NewLoop->setLoopAlreadyUnrolled();
535 return NewLoop;
536}
537
538/// Returns true if we can profitably unroll the multi-exit loop L.
539static bool canProfitablyRuntimeUnrollMultiExitLoop(
540 Loop *L, const TargetTransformInfo *TTI,
541 SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,
542 bool UseEpilogRemainder) {
543
544 // The main pain point with multi-exit loop unrolling is that once unrolled,
545 // we will not be able to merge all blocks into a straight line code.
546 // There are branches within the unrolled loop that go to the OtherExits.
547 // The second point is the increase in code size, but this is true
548 // irrespective of multiple exits.
549
550 // Note: Both the heuristics below are coarse grained. We are essentially
551 // enabling unrolling of loops that have a single side exit other than the
552 // normal LatchExit (i.e. exiting into a deoptimize block).
553 // The heuristics considered are:
554 // 1. low number of branches in the unrolled version.
555 // 2. high predictability of these extra branches.
556 // We avoid unrolling loops that have more than two exiting blocks. This
557 // limits the total number of branches in the unrolled loop to be atmost
558 // the unroll factor (since one of the exiting blocks is the latch block).
559 SmallVector<BasicBlock*, 4> ExitingBlocks;
560 L->getExitingBlocks(ExitingBlocks);
561 if (ExitingBlocks.size() > 2)
562 return false;
563
564 // Allow unrolling of loops with no non latch exit blocks.
565 if (OtherExits.size() == 0)
566 return true;
567
568 if (OtherExits.size() != 1)
569 return false;
570
571 // When UnrollRuntimeOtherExitPredictable is specified, we assume the other
572 // exit branch is predictable even if it has no deoptimize call.
573 if (UnrollRuntimeOtherExitPredictable)
574 return true;
575
576 // The second heuristic is that L has one exit other than the latchexit and
577 // that exit is highly unlikely.
578 if (TTI) {
579 BasicBlock *LatchBB = L->getLoopLatch();
580 assert(LatchBB && "Expected loop to have a latch");
581 BasicBlock *NonLatchExitingBlock =
582 (ExitingBlocks[0] == LatchBB) ? ExitingBlocks[1] : ExitingBlocks[0];
583 auto BranchProb =
584 llvm::getBranchProbability(Src: NonLatchExitingBlock, Dst: OtherExits[0]);
585 // If BranchProbability could not be extracted (returns unknown), then
586 // don't return and do the check for deopt block.
587 if (!BranchProb.isUnknown()) {
588 auto Threshold = TTI->getPredictableBranchThreshold().getCompl();
589 return BranchProb < Threshold;
590 }
591 }
592
593 // We know that deoptimize blocks are rarely taken, which also implies the
594 // branch leading to the deoptimize block is highly unlikely.
595 return OtherExits[0]->getPostdominatingDeoptimizeCall();
596 // TODO: These can be fine-tuned further to consider code size or deopt states
597 // that are captured by the deoptimize exit block.
598 // Also, we can extend this to support more cases, if we actually
599 // know of kinds of multiexit loops that would benefit from unrolling.
600}
601
602/// Calculate ModVal = (BECount + 1) % Count on the abstract integer domain
603/// accounting for the possibility of unsigned overflow in the 2s complement
604/// domain. Preconditions:
605/// 1) TripCount = BECount + 1 (allowing overflow)
606/// 2) Log2(Count) <= BitWidth(BECount)
607static Value *CreateTripRemainder(IRBuilder<> &B, Value *BECount,
608 Value *TripCount, unsigned Count) {
609 // Note that TripCount is BECount + 1.
610 if (isPowerOf2_32(Value: Count))
611 // If the expression is zero, then either:
612 // 1. There are no iterations to be run in the prolog/epilog loop.
613 // OR
614 // 2. The addition computing TripCount overflowed.
615 //
616 // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
617 // the number of iterations that remain to be run in the original loop is a
618 // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (a
619 // precondition of this method).
620 return B.CreateAnd(LHS: TripCount, RHS: Count - 1, Name: "xtraiter");
621
622 // As (BECount + 1) can potentially unsigned overflow we count
623 // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
624 Constant *CountC = ConstantInt::get(Ty: BECount->getType(), V: Count);
625 Value *ModValTmp = B.CreateURem(LHS: BECount, RHS: CountC);
626 Value *ModValAdd = B.CreateAdd(LHS: ModValTmp,
627 RHS: ConstantInt::get(Ty: ModValTmp->getType(), V: 1));
628 // At that point (BECount % Count) + 1 could be equal to Count.
629 // To handle this case we need to take mod by Count one more time.
630 return B.CreateURem(LHS: ModValAdd, RHS: CountC, Name: "xtraiter");
631}
632
633
634/// Insert code in the prolog/epilog code when unrolling a loop with a
635/// run-time trip-count.
636///
637/// This method assumes that the loop unroll factor is total number
638/// of loop bodies in the loop after unrolling. (Some folks refer
639/// to the unroll factor as the number of *extra* copies added).
640/// We assume also that the loop unroll factor is a power-of-two. So, after
641/// unrolling the loop, the number of loop bodies executed is 2,
642/// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch
643/// instruction in SimplifyCFG.cpp. Then, the backend decides how code for
644/// the switch instruction is generated.
645///
646/// ***Prolog case***
647/// extraiters = tripcount % loopfactor
648/// if (extraiters == 0) jump Loop:
649/// else jump Prol:
650/// Prol: LoopBody;
651/// extraiters -= 1 // Omitted if unroll factor is 2.
652/// if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
653/// if (tripcount < loopfactor) jump End:
654/// Loop:
655/// ...
656/// End:
657///
658/// ***Epilog case***
659/// extraiters = tripcount % loopfactor
660/// if (tripcount < loopfactor) jump LoopExit:
661/// unroll_iters = tripcount - extraiters
662/// Loop: LoopBody; (executes unroll_iter times);
663/// unroll_iter -= 1
664/// if (unroll_iter != 0) jump Loop:
665/// LoopExit:
666/// if (extraiters == 0) jump EpilExit:
667/// Epil: LoopBody; (executes extraiters times)
668/// extraiters -= 1 // Omitted if unroll factor is 2.
669/// if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
670/// EpilExit:
671
672bool llvm::UnrollRuntimeLoopRemainder(
673 Loop *L, unsigned Count, bool AllowExpensiveTripCount,
674 bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,
675 LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,
676 const TargetTransformInfo *TTI, bool PreserveLCSSA,
677 unsigned SCEVExpansionBudget, bool RuntimeUnrollMultiExit,
678 Loop **ResultLoop, std::optional<unsigned> OriginalTripCount,
679 BranchProbability OriginalLoopProb) {
680 LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
681 LLVM_DEBUG(L->dump());
682 LLVM_DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"
683 : dbgs() << "Using prolog remainder.\n");
684
685 // Make sure the loop is in canonical form.
686 if (!L->isLoopSimplifyForm()) {
687 LLVM_DEBUG(dbgs() << "Not in simplify form!\n");
688 return false;
689 }
690
691 // Guaranteed by LoopSimplifyForm.
692 BasicBlock *Latch = L->getLoopLatch();
693 BasicBlock *Header = L->getHeader();
694
695 CondBrInst *LatchBR = dyn_cast<CondBrInst>(Val: Latch->getTerminator());
696
697 if (!LatchBR) {
698 // The loop-rotate pass can be helpful to avoid this in many cases.
699 LLVM_DEBUG(
700 dbgs()
701 << "Loop latch not terminated by a conditional branch.\n");
702 return false;
703 }
704
705 unsigned ExitIndex = LatchBR->getSuccessor(i: 0) == Header ? 1 : 0;
706 BasicBlock *LatchExit = LatchBR->getSuccessor(i: ExitIndex);
707
708 if (L->contains(BB: LatchExit)) {
709 // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
710 // targets of the Latch be an exit block out of the loop.
711 LLVM_DEBUG(
712 dbgs()
713 << "One of the loop latch successors must be the exit block.\n");
714 return false;
715 }
716
717 // These are exit blocks other than the target of the latch exiting block.
718 SmallVector<BasicBlock *, 4> OtherExits;
719 L->getUniqueNonLatchExitBlocks(ExitBlocks&: OtherExits);
720 // Support only single exit and exiting block unless multi-exit loop
721 // unrolling is enabled.
722 if (!L->getExitingBlock() || OtherExits.size()) {
723 // We rely on LCSSA form being preserved when the exit blocks are transformed.
724 // (Note that only an off-by-default mode of the old PM disables PreserveLCCA.)
725 if (!PreserveLCSSA)
726 return false;
727
728 // Priority goes to UnrollRuntimeMultiExit if it's supplied.
729 if (UnrollRuntimeMultiExit.getNumOccurrences()) {
730 if (!UnrollRuntimeMultiExit)
731 return false;
732 } else {
733 // Otherwise perform multi-exit unrolling, if either the target indicates
734 // it is profitable or the general profitability heuristics apply.
735 if (!RuntimeUnrollMultiExit &&
736 !canProfitablyRuntimeUnrollMultiExitLoop(
737 L, TTI, OtherExits, LatchExit, UseEpilogRemainder)) {
738 LLVM_DEBUG(dbgs() << "Multiple exit/exiting blocks in loop and "
739 "multi-exit unrolling not enabled!\n");
740 return false;
741 }
742 }
743 }
744 // Use Scalar Evolution to compute the trip count. This allows more loops to
745 // be unrolled than relying on induction var simplification.
746 if (!SE)
747 return false;
748
749 // Only unroll loops with a computable trip count.
750 // We calculate the backedge count by using getExitCount on the Latch block,
751 // which is proven to be the only exiting block in this loop. This is same as
752 // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
753 // exiting blocks).
754 const SCEV *BECountSC = SE->getExitCount(L, ExitingBlock: Latch);
755 if (isa<SCEVCouldNotCompute>(Val: BECountSC)) {
756 LLVM_DEBUG(dbgs() << "Could not compute exit block SCEV\n");
757 return false;
758 }
759
760 unsigned BEWidth = cast<IntegerType>(Val: BECountSC->getType())->getBitWidth();
761
762 // Add 1 since the backedge count doesn't include the first loop iteration.
763 // (Note that overflow can occur, this is handled explicitly below)
764 const SCEV *TripCountSC =
765 SE->getAddExpr(LHS: BECountSC, RHS: SE->getConstant(Ty: BECountSC->getType(), V: 1));
766 if (isa<SCEVCouldNotCompute>(Val: TripCountSC)) {
767 LLVM_DEBUG(dbgs() << "Could not compute trip count SCEV.\n");
768 return false;
769 }
770
771 BasicBlock *PreHeader = L->getLoopPreheader();
772 Instruction *PreHeaderBR = PreHeader->getTerminator();
773 SCEVExpander Expander(*SE, "loop-unroll");
774 if (!AllowExpensiveTripCount &&
775 Expander.isHighCostExpansion(Exprs: TripCountSC, L, Budget: SCEVExpansionBudget, TTI,
776 At: PreHeaderBR)) {
777 LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
778 return false;
779 }
780
781 // This constraint lets us deal with an overflowing trip count easily; see the
782 // comment on ModVal below.
783 if (Log2_32(Value: Count) > BEWidth) {
784 LLVM_DEBUG(
785 dbgs()
786 << "Count failed constraint on overflow trip count calculation.\n");
787 return false;
788 }
789
790 // Loop structure is the following:
791 //
792 // PreHeader
793 // Header
794 // ...
795 // Latch
796 // LatchExit
797
798 BasicBlock *NewPreHeader;
799 BasicBlock *NewExit = nullptr;
800 BasicBlock *PrologExit = nullptr;
801 BasicBlock *EpilogPreHeader = nullptr;
802 BasicBlock *PrologPreHeader = nullptr;
803
804 if (UseEpilogRemainder) {
805 // If epilog remainder
806 // Split PreHeader to insert a branch around loop for unrolling.
807 NewPreHeader = SplitBlock(Old: PreHeader, SplitPt: PreHeader->getTerminator(), DT, LI);
808 NewPreHeader->setName(PreHeader->getName() + ".new");
809 // Split LatchExit to create phi nodes from branch above.
810 NewExit = SplitBlockPredecessors(BB: LatchExit, Preds: {Latch}, Suffix: ".unr-lcssa", DT, LI,
811 MSSAU: nullptr, PreserveLCSSA);
812 // NewExit gets its DebugLoc from LatchExit, which is not part of the
813 // original Loop.
814 // Fix this by setting Loop's DebugLoc to NewExit.
815 auto *NewExitTerminator = NewExit->getTerminator();
816 NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());
817 // Split NewExit to insert epilog remainder loop.
818 EpilogPreHeader = SplitBlock(Old: NewExit, SplitPt: NewExitTerminator, DT, LI);
819 EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
820
821 // If the latch exits from multiple level of nested loops, then
822 // by assumption there must be another loop exit which branches to the
823 // outer loop and we must adjust the loop for the newly inserted blocks
824 // to account for the fact that our epilogue is still in the same outer
825 // loop. Note that this leaves loopinfo temporarily out of sync with the
826 // CFG until the actual epilogue loop is inserted.
827 if (auto *ParentL = L->getParentLoop())
828 if (LI->getLoopFor(BB: LatchExit) != ParentL) {
829 LI->removeBlock(BB: NewExit);
830 ParentL->addBasicBlockToLoop(NewBB: NewExit, LI&: *LI);
831 LI->removeBlock(BB: EpilogPreHeader);
832 ParentL->addBasicBlockToLoop(NewBB: EpilogPreHeader, LI&: *LI);
833 }
834
835 } else {
836 // If prolog remainder
837 // Split the original preheader twice to insert prolog remainder loop
838 PrologPreHeader = SplitEdge(From: PreHeader, To: Header, DT, LI);
839 PrologPreHeader->setName(Header->getName() + ".prol.preheader");
840 PrologExit = SplitBlock(Old: PrologPreHeader, SplitPt: PrologPreHeader->getTerminator(),
841 DT, LI);
842 PrologExit->setName(Header->getName() + ".prol.loopexit");
843 // Split PrologExit to get NewPreHeader.
844 NewPreHeader = SplitBlock(Old: PrologExit, SplitPt: PrologExit->getTerminator(), DT, LI);
845 NewPreHeader->setName(PreHeader->getName() + ".new");
846 }
847 // Loop structure should be the following:
848 // Epilog Prolog
849 //
850 // PreHeader PreHeader
851 // *NewPreHeader *PrologPreHeader
852 // Header *PrologExit
853 // ... *NewPreHeader
854 // Latch Header
855 // *NewExit ...
856 // *EpilogPreHeader Latch
857 // LatchExit LatchExit
858
859 // Calculate conditions for branch around loop for unrolling
860 // in epilog case and around prolog remainder loop in prolog case.
861 // Compute the number of extra iterations required, which is:
862 // extra iterations = run-time trip count % loop unroll factor
863 PreHeaderBR = PreHeader->getTerminator();
864 IRBuilder<> B(PreHeaderBR);
865 Value *TripCount = Expander.expandCodeFor(SH: TripCountSC, Ty: TripCountSC->getType(),
866 I: PreHeaderBR);
867 Value *BECount;
868 // If there are other exits before the latch, that may cause the latch exit
869 // branch to never be executed, and the latch exit count may be poison.
870 // In this case, freeze the TripCount and base BECount on the frozen
871 // TripCount. We will introduce two branches using these values, and it's
872 // important that they see a consistent value (which would not be guaranteed
873 // if were frozen independently.)
874 if ((!OtherExits.empty() || !SE->loopHasNoAbnormalExits(L)) &&
875 !isGuaranteedNotToBeUndefOrPoison(V: TripCount, AC, CtxI: PreHeaderBR, DT)) {
876 TripCount = B.CreateFreeze(V: TripCount);
877 BECount =
878 B.CreateAdd(LHS: TripCount, RHS: Constant::getAllOnesValue(Ty: TripCount->getType()));
879 } else {
880 // If we don't need to freeze, use SCEVExpander for BECount as well, to
881 // allow slightly better value reuse.
882 BECount =
883 Expander.expandCodeFor(SH: BECountSC, Ty: BECountSC->getType(), I: PreHeaderBR);
884 }
885
886 Value * const ModVal = CreateTripRemainder(B, BECount, TripCount, Count);
887
888 Value *BranchVal =
889 UseEpilogRemainder ? B.CreateICmpULT(LHS: BECount,
890 RHS: ConstantInt::get(Ty: BECount->getType(),
891 V: Count - 1)) :
892 B.CreateIsNotNull(Arg: ModVal, Name: "lcmp.mod");
893 BasicBlock *RemainderLoop =
894 UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
895 BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
896 // Branch to either remainder (extra iterations) loop or unrolling loop.
897 MDNode *BranchWeights = nullptr;
898 if ((OriginalLoopProb.isUnknown() || !UseEpilogRemainder) &&
899 hasBranchWeightMD(I: *Latch->getTerminator())) {
900 // Assume loop is nearly always entered.
901 MDBuilder MDB(B.getContext());
902 BranchWeights = MDB.createBranchWeights(Weights: EpilogHeaderWeights);
903 }
904 CondBrInst *UnrollingLoopGuard =
905 B.CreateCondBr(Cond: BranchVal, True: RemainderLoop, False: UnrollingLoop, BranchWeights);
906 if (!OriginalLoopProb.isUnknown() && UseEpilogRemainder) {
907 // The original loop's first iteration always happens. Compute the
908 // probability of the original loop executing Count-1 iterations after that
909 // to complete the first iteration of the unrolled loop.
910 BranchProbability ProbOne = OriginalLoopProb;
911 BranchProbability ProbRest = ProbOne.pow(N: Count - 1);
912 setBranchProbability(B: UnrollingLoopGuard, P: ProbRest,
913 /*ForFirstTarget=*/false);
914 }
915 PreHeaderBR->eraseFromParent();
916 if (DT) {
917 if (UseEpilogRemainder)
918 DT->changeImmediateDominator(BB: EpilogPreHeader, NewBB: PreHeader);
919 else
920 DT->changeImmediateDominator(BB: PrologExit, NewBB: PreHeader);
921 }
922 Function *F = Header->getParent();
923 // Get an ordered list of blocks in the loop to help with the ordering of the
924 // cloned blocks in the prolog/epilog code
925 LoopBlocksDFS LoopBlocks(L);
926 LoopBlocks.perform(LI);
927
928 //
929 // For each extra loop iteration, create a copy of the loop's basic blocks
930 // and generate a condition that branches to the copy depending on the
931 // number of 'left over' iterations.
932 //
933 std::vector<BasicBlock *> NewBlocks;
934 ValueToValueMapTy VMap;
935
936 // Clone all the basic blocks in the loop. If Count is 2, we don't clone
937 // the loop, otherwise we create a cloned loop to execute the extra
938 // iterations. This function adds the appropriate CFG connections.
939 BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;
940 BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
941 Loop *remainderLoop =
942 CloneLoopBlocks(L, NewIter: ModVal, UseEpilogRemainder, UnrollRemainder, InsertTop,
943 InsertBot, Preheader: NewPreHeader, NewBlocks, LoopBlocks, VMap, DT,
944 LI, Count, OriginalTripCount, OriginalLoopProb);
945
946 // Insert the cloned blocks into the function.
947 F->splice(ToIt: InsertBot->getIterator(), FromF: F, FromBeginIt: NewBlocks[0]->getIterator(), FromEndIt: F->end());
948
949 // Now the loop blocks are cloned and the other exiting blocks from the
950 // remainder are connected to the original Loop's exit blocks. The remaining
951 // work is to update the phi nodes in the original loop, and take in the
952 // values from the cloned region.
953 for (auto *BB : OtherExits) {
954 // Given we preserve LCSSA form, we know that the values used outside the
955 // loop will be used through these phi nodes at the exit blocks that are
956 // transformed below.
957 for (PHINode &PN : BB->phis()) {
958 unsigned oldNumOperands = PN.getNumIncomingValues();
959 // Add the incoming values from the remainder code to the end of the phi
960 // node.
961 for (unsigned i = 0; i < oldNumOperands; i++){
962 auto *PredBB =PN.getIncomingBlock(i);
963 if (PredBB == Latch)
964 // The latch exit is handled separately, see connectX
965 continue;
966 if (!L->contains(BB: PredBB))
967 // Even if we had dedicated exits, the code above inserted an
968 // extra branch which can reach the latch exit.
969 continue;
970
971 auto *V = PN.getIncomingValue(i);
972 if (Instruction *I = dyn_cast<Instruction>(Val: V))
973 if (L->contains(Inst: I))
974 V = VMap.lookup(Val: I);
975 PN.addIncoming(V, BB: cast<BasicBlock>(Val&: VMap[PredBB]));
976 }
977 }
978#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
979 for (BasicBlock *SuccBB : successors(BB)) {
980 assert(!(llvm::is_contained(OtherExits, SuccBB) || SuccBB == LatchExit) &&
981 "Breaks the definition of dedicated exits!");
982 }
983#endif
984 }
985
986 // Update the immediate dominator of the exit blocks and blocks that are
987 // reachable from the exit blocks. This is needed because we now have paths
988 // from both the original loop and the remainder code reaching the exit
989 // blocks. While the IDom of these exit blocks were from the original loop,
990 // now the IDom is the preheader (which decides whether the original loop or
991 // remainder code should run) unless the block still has just the original
992 // predecessor (such as NewExit in the case of an epilog remainder).
993 if (DT && !L->getExitingBlock()) {
994 SmallVector<BasicBlock *, 16> ChildrenToUpdate;
995 // NB! We have to examine the dom children of all loop blocks, not just
996 // those which are the IDom of the exit blocks. This is because blocks
997 // reachable from the exit blocks can have their IDom as the nearest common
998 // dominator of the exit blocks.
999 for (auto *BB : L->blocks()) {
1000 auto *DomNodeBB = DT->getNode(BB);
1001 for (auto *DomChild : DomNodeBB->children()) {
1002 auto *DomChildBB = DomChild->getBlock();
1003 if (!L->contains(L: LI->getLoopFor(BB: DomChildBB)) &&
1004 DomChildBB->getUniquePredecessor() != BB)
1005 ChildrenToUpdate.push_back(Elt: DomChildBB);
1006 }
1007 }
1008 for (auto *BB : ChildrenToUpdate)
1009 DT->changeImmediateDominator(BB, NewBB: PreHeader);
1010 }
1011
1012 // Loop structure should be the following:
1013 // Epilog Prolog
1014 //
1015 // PreHeader PreHeader
1016 // NewPreHeader PrologPreHeader
1017 // Header PrologHeader
1018 // ... ...
1019 // Latch PrologLatch
1020 // NewExit PrologExit
1021 // EpilogPreHeader NewPreHeader
1022 // EpilogHeader Header
1023 // ... ...
1024 // EpilogLatch Latch
1025 // LatchExit LatchExit
1026
1027 // Rewrite the cloned instruction operands to use the values created when the
1028 // clone is created.
1029 for (BasicBlock *BB : NewBlocks) {
1030 Module *M = BB->getModule();
1031 for (Instruction &I : *BB) {
1032 RemapInstruction(I: &I, VM&: VMap,
1033 Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1034 RemapDbgRecordRange(M, Range: I.getDbgRecordRange(), VM&: VMap,
1035 Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1036 }
1037 }
1038
1039 if (UseEpilogRemainder) {
1040 // Connect the epilog code to the original loop and update the
1041 // PHI functions.
1042 ConnectEpilog(L, ModVal, NewExit, Exit: LatchExit, PreHeader, EpilogPreHeader,
1043 NewPreHeader, VMap, DT, LI, PreserveLCSSA, SE&: *SE, Count, AC&: *AC,
1044 OriginalLoopProb);
1045
1046 // Update counter in loop for unrolling.
1047 // Use an incrementing IV. Pre-incr/post-incr is backedge/trip count.
1048 // Subtle: TestVal can be 0 if we wrapped when computing the trip count,
1049 // thus we must compare the post-increment (wrapping) value.
1050 IRBuilder<> B2(NewPreHeader->getTerminator());
1051 Value *TestVal = B2.CreateSub(LHS: TripCount, RHS: ModVal, Name: "unroll_iter");
1052 CondBrInst *LatchBR = cast<CondBrInst>(Val: Latch->getTerminator());
1053 PHINode *NewIdx = PHINode::Create(Ty: TestVal->getType(), NumReservedValues: 2, NameStr: "niter");
1054 NewIdx->insertBefore(InsertPos: Header->getFirstNonPHIIt());
1055 B2.SetInsertPoint(LatchBR);
1056 auto *Zero = ConstantInt::get(Ty: NewIdx->getType(), V: 0);
1057 auto *One = ConstantInt::get(Ty: NewIdx->getType(), V: 1);
1058 Value *IdxNext = B2.CreateAdd(LHS: NewIdx, RHS: One, Name: NewIdx->getName() + ".next");
1059 auto Pred = LatchBR->getSuccessor(i: 0) == Header ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;
1060 Value *IdxCmp = B2.CreateICmp(P: Pred, LHS: IdxNext, RHS: TestVal, Name: NewIdx->getName() + ".ncmp");
1061 NewIdx->addIncoming(V: Zero, BB: NewPreHeader);
1062 NewIdx->addIncoming(V: IdxNext, BB: Latch);
1063 LatchBR->setCondition(IdxCmp);
1064 } else {
1065 // Connect the prolog code to the original loop and update the
1066 // PHI functions.
1067 ConnectProlog(L, BECount, Count, PrologExit, OriginalLoopLatchExit: LatchExit, PreHeader,
1068 NewPreHeader, VMap, DT, LI, PreserveLCSSA, SE&: *SE);
1069 }
1070
1071 // If this loop is nested, then the loop unroller changes the code in the any
1072 // of its parent loops, so the Scalar Evolution pass needs to be run again.
1073 SE->forgetTopmostLoop(L);
1074
1075 // Verify that the Dom Tree and Loop Info are correct.
1076#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
1077 if (DT) {
1078 assert(DT->verify(DominatorTree::VerificationLevel::Full));
1079 LI->verify();
1080 }
1081#endif
1082
1083 // For unroll factor 2 remainder loop will have 1 iteration.
1084 if (Count == 2 && DT && LI && SE) {
1085 // TODO: This code could probably be pulled out into a helper function
1086 // (e.g. breakLoopBackedgeAndSimplify) and reused in loop-deletion.
1087 BasicBlock *RemainderLatch = remainderLoop->getLoopLatch();
1088 assert(RemainderLatch);
1089 SmallVector<BasicBlock *> RemainderBlocks(remainderLoop->getBlocks());
1090 breakLoopBackedge(L: remainderLoop, DT&: *DT, SE&: *SE, LI&: *LI, MSSA: nullptr);
1091 remainderLoop = nullptr;
1092
1093 // Simplify loop values after breaking the backedge
1094 const DataLayout &DL = L->getHeader()->getDataLayout();
1095 SmallVector<WeakTrackingVH, 16> DeadInsts;
1096 for (BasicBlock *BB : RemainderBlocks) {
1097 for (Instruction &Inst : llvm::make_early_inc_range(Range&: *BB)) {
1098 if (Value *V = simplifyInstruction(I: &Inst, Q: {DL, nullptr, DT, AC}))
1099 if (LI->replacementPreservesLCSSAForm(From: &Inst, To: V))
1100 Inst.replaceAllUsesWith(V);
1101 if (isInstructionTriviallyDead(I: &Inst))
1102 DeadInsts.emplace_back(Args: &Inst);
1103 }
1104 // We can't do recursive deletion until we're done iterating, as we might
1105 // have a phi which (potentially indirectly) uses instructions later in
1106 // the block we're iterating through.
1107 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);
1108 }
1109
1110 // Merge latch into exit block.
1111 auto *ExitBB = RemainderLatch->getSingleSuccessor();
1112 assert(ExitBB && "required after breaking cond br backedge");
1113 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
1114 MergeBlockIntoPredecessor(BB: ExitBB, DTU: &DTU, LI);
1115 }
1116
1117 // Canonicalize to LoopSimplifyForm both original and remainder loops. We
1118 // cannot rely on the LoopUnrollPass to do this because it only does
1119 // canonicalization for parent/subloops and not the sibling loops.
1120 if (OtherExits.size() > 0) {
1121 // Generate dedicated exit blocks for the original loop, to preserve
1122 // LoopSimplifyForm.
1123 formDedicatedExitBlocks(L, DT, LI, MSSAU: nullptr, PreserveLCSSA);
1124 // Generate dedicated exit blocks for the remainder loop if one exists, to
1125 // preserve LoopSimplifyForm.
1126 if (remainderLoop)
1127 formDedicatedExitBlocks(L: remainderLoop, DT, LI, MSSAU: nullptr, PreserveLCSSA);
1128 }
1129
1130 auto UnrollResult = LoopUnrollResult::Unmodified;
1131 if (remainderLoop && UnrollRemainder) {
1132 LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");
1133 UnrollLoopOptions ULO;
1134 ULO.Count = Count - 1;
1135 ULO.Force = false;
1136 ULO.Runtime = false;
1137 ULO.AllowExpensiveTripCount = false;
1138 ULO.UnrollRemainder = false;
1139 ULO.ForgetAllSCEV = ForgetAllSCEV;
1140 assert(!getLoopConvergenceHeart(L) &&
1141 "A loop with a convergence heart does not allow runtime unrolling.");
1142 UnrollResult = UnrollLoop(L: remainderLoop, ULO, LI, SE, DT, AC, TTI,
1143 /*ORE*/ nullptr, PreserveLCSSA);
1144 }
1145
1146 if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)
1147 *ResultLoop = remainderLoop;
1148 NumRuntimeUnrolled++;
1149 return true;
1150}
1151