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