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