LLVM 20.0.0git
LoopUnrollRuntime.cpp
Go to the documentation of this file.
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"
29#include "llvm/IR/BasicBlock.h"
30#include "llvm/IR/Dominators.h"
31#include "llvm/IR/MDBuilder.h"
32#include "llvm/IR/Module.h"
35#include "llvm/Support/Debug.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");
51 "unroll-runtime-multi-exit", cl::init(false), cl::Hidden,
52 cl::desc("Allow runtime unrolling for loops with multiple exits, when "
53 "epilog is generated"));
55 "unroll-runtime-other-exit-predictable", cl::init(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,
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>(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(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(PN.getType(), 2, PN.getName() + ".unr");
119 NewPN->insertBefore(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(&PN)) {
123 // Succ is loop header.
124 NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader),
125 PreHeader);
126 } else {
127 // Succ is LatchExit.
128 NewPN->addIncoming(PoisonValue::get(PN.getType()), PreHeader);
129 }
130
131 Value *V = PN.getIncomingValueForBlock(Latch);
132 if (Instruction *I = dyn_cast<Instruction>(V)) {
133 if (L->contains(I)) {
134 V = VMap.lookup(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, 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(&PN))
145 PN.setIncomingValueForBlock(NewPreHeader, NewPN);
146 else
147 PN.addIncoming(NewPN, PrologExit);
149 }
150 }
151
152 // Make sure that created prolog loop is in simplified form
153 SmallVector<BasicBlock *, 4> PrologExitPreds;
154 Loop *PrologLoop = LI->getLoopFor(PrologLatch);
155 if (PrologLoop) {
156 for (BasicBlock *PredBB : predecessors(PrologExit))
157 if (PrologLoop->contains(PredBB))
158 PrologExitPreds.push_back(PredBB);
159
160 SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI,
161 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(BECount, ConstantInt::get(BECount->getType(), Count - 1));
177 // Split the exit to maintain loop canonicalization guarantees
178 SmallVector<BasicBlock *, 4> Preds(predecessors(OriginalLoopLatchExit));
179 SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI,
180 nullptr, PreserveLCSSA);
181 // Add the branch to the exit block (around the unrolled loop)
182 MDNode *BranchWeights = nullptr;
183 if (hasBranchWeightMD(*Latch->getTerminator())) {
184 // Assume loop is nearly always entered.
185 MDBuilder MDB(B.getContext());
187 }
188 B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader,
189 BranchWeights);
190 InsertPt->eraseFromParent();
191 if (DT) {
192 auto *NewDom = DT->findNearestCommonDominator(OriginalLoopLatchExit,
193 PrologExit);
194 DT->changeImmediateDominator(OriginalLoopLatchExit, 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,
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>(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>(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(PoisonValue::get(PN.getType()), PreHeader);
256 SE.forgetValue(&PN);
257
258 Value *V = PN.getIncomingValueForBlock(Latch);
259 Instruction *I = dyn_cast<Instruction>(V);
260 if (I && L->contains(I))
261 // If value comes from an instruction in the loop add VMap value.
262 V = VMap.lookup(I);
263 // For the instruction out of the loop, constant or undefined value
264 // insert value itself.
265 EpilogPN->addIncoming(V, 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(EpilogPN->getBasicBlockIndex(EpilogPreHeader),
271 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(Latch)) {
283 // Skip this as we already updated phis in exit blocks.
284 if (!L->contains(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(PN.getType(), 2, PN.getName() + ".unr");
290 NewPN->insertBefore(NewExit->getFirstNonPHIIt());
291 // Adding a value to the new PHI node from the unrolling loop preheader.
292 NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader), PreHeader);
293 // Adding a value to the new PHI node from the unrolling loop latch.
294 NewPN->addIncoming(PN.getIncomingValueForBlock(Latch), 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>(VMap[&PN]);
299 VPN->setIncomingValueForBlock(EpilogPreHeader, NewPN);
300 }
301 }
302
303 Instruction *InsertPt = NewExit->getTerminator();
304 IRBuilder<> B(InsertPt);
305 Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");
306 assert(Exit && "Loop must have a single exit block only");
307 // Split the epilogue exit to maintain loop canonicalization guarantees
309 SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI, nullptr,
310 PreserveLCSSA);
311 // Add the branch to the exit block (around the unrolling loop)
312 MDNode *BranchWeights = nullptr;
313 if (hasBranchWeightMD(*Latch->getTerminator())) {
314 // Assume equal distribution in interval [0, Count).
315 MDBuilder MDB(B.getContext());
316 BranchWeights = MDB.createBranchWeights(1, Count - 1);
317 }
318 B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit, BranchWeights);
319 InsertPt->eraseFromParent();
320 if (DT) {
321 auto *NewDom = DT->findNearestCommonDominator(Exit, NewExit);
322 DT->changeImmediateDominator(Exit, NewDom);
323 }
324
325 // Split the main loop exit to maintain canonicalization guarantees.
326 SmallVector<BasicBlock*, 4> NewExitPreds{Latch};
327 SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI, 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, VMap, "." + suffix, F);
359 NewBlocks.push_back(NewBB);
360
361 addClonedBlockToLoopInfo(*BB, 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(0, NewBB);
368 }
369
370 if (DT) {
371 if (Header == *BB) {
372 // The header is dominated by the preheader.
373 DT->addNewBlock(NewBB, InsertTop);
374 } else {
375 // Copy information from original loop to unrolled loop.
376 BasicBlock *IDomBB = DT->getNode(*BB)->getIDom()->getBlock();
377 DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDomBB]));
378 }
379 }
380
381 if (Latch == *BB) {
382 // For the last block, create a loop back to cloned head.
383 VMap.erase((*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>(VMap[Header]);
388 BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());
389 IRBuilder<> Builder(LatchBR);
390 PHINode *NewIdx =
391 PHINode::Create(NewIter->getType(), 2, suffix + ".iter");
392 NewIdx->insertBefore(FirstLoopBB->getFirstNonPHIIt());
393 auto *Zero = ConstantInt::get(NewIdx->getType(), 0);
394 auto *One = ConstantInt::get(NewIdx->getType(), 1);
395 Value *IdxNext =
396 Builder.CreateAdd(NewIdx, One, NewIdx->getName() + ".next");
397 Value *IdxCmp = Builder.CreateICmpNE(IdxNext, NewIter, NewIdx->getName() + ".cmp");
398 MDNode *BranchWeights = nullptr;
399 if (hasBranchWeightMD(*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(BackEdgeWeight, ExitWeight);
416 }
417 Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot, BranchWeights);
418 NewIdx->addIncoming(Zero, InsertTop);
419 NewIdx->addIncoming(IdxNext, 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>(I); ++I) {
427 PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
428 unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
429 NewPHI->setIncomingBlock(idx, InsertTop);
430 BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
431 idx = NewPHI->getBasicBlockIndex(Latch);
432 Value *InVal = NewPHI->getIncomingValue(idx);
433 NewPHI->setIncomingBlock(idx, NewLatch);
434 if (Value *V = VMap.lookup(InVal))
435 NewPHI->setIncomingValue(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(
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.
465 Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,
466 bool UseEpilogRemainder) {
467
468 // Priority goes to UnrollRuntimeMultiExit if it's supplied.
471
472 // The main pain point with multi-exit loop unrolling is that once unrolled,
473 // we will not be able to merge all blocks into a straight line code.
474 // There are branches within the unrolled loop that go to the OtherExits.
475 // The second point is the increase in code size, but this is true
476 // irrespective of multiple exits.
477
478 // Note: Both the heuristics below are coarse grained. We are essentially
479 // enabling unrolling of loops that have a single side exit other than the
480 // normal LatchExit (i.e. exiting into a deoptimize block).
481 // The heuristics considered are:
482 // 1. low number of branches in the unrolled version.
483 // 2. high predictability of these extra branches.
484 // We avoid unrolling loops that have more than two exiting blocks. This
485 // limits the total number of branches in the unrolled loop to be atmost
486 // the unroll factor (since one of the exiting blocks is the latch block).
487 SmallVector<BasicBlock*, 4> ExitingBlocks;
488 L->getExitingBlocks(ExitingBlocks);
489 if (ExitingBlocks.size() > 2)
490 return false;
491
492 // Allow unrolling of loops with no non latch exit blocks.
493 if (OtherExits.size() == 0)
494 return true;
495
496 // The second heuristic is that L has one exit other than the latchexit and
497 // that exit is a deoptimize block. We know that deoptimize blocks are rarely
498 // taken, which also implies the branch leading to the deoptimize block is
499 // highly predictable. When UnrollRuntimeOtherExitPredictable is specified, we
500 // assume the other exit branch is predictable even if it has no deoptimize
501 // call.
502 return (OtherExits.size() == 1 &&
504 OtherExits[0]->getPostdominatingDeoptimizeCall()));
505 // TODO: These can be fine-tuned further to consider code size or deopt states
506 // that are captured by the deoptimize exit block.
507 // Also, we can extend this to support more cases, if we actually
508 // know of kinds of multiexit loops that would benefit from unrolling.
509}
510
511/// Calculate ModVal = (BECount + 1) % Count on the abstract integer domain
512/// accounting for the possibility of unsigned overflow in the 2s complement
513/// domain. Preconditions:
514/// 1) TripCount = BECount + 1 (allowing overflow)
515/// 2) Log2(Count) <= BitWidth(BECount)
517 Value *TripCount, unsigned Count) {
518 // Note that TripCount is BECount + 1.
519 if (isPowerOf2_32(Count))
520 // If the expression is zero, then either:
521 // 1. There are no iterations to be run in the prolog/epilog loop.
522 // OR
523 // 2. The addition computing TripCount overflowed.
524 //
525 // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
526 // the number of iterations that remain to be run in the original loop is a
527 // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (a
528 // precondition of this method).
529 return B.CreateAnd(TripCount, Count - 1, "xtraiter");
530
531 // As (BECount + 1) can potentially unsigned overflow we count
532 // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
533 Constant *CountC = ConstantInt::get(BECount->getType(), Count);
534 Value *ModValTmp = B.CreateURem(BECount, CountC);
535 Value *ModValAdd = B.CreateAdd(ModValTmp,
536 ConstantInt::get(ModValTmp->getType(), 1));
537 // At that point (BECount % Count) + 1 could be equal to Count.
538 // To handle this case we need to take mod by Count one more time.
539 return B.CreateURem(ModValAdd, CountC, "xtraiter");
540}
541
542
543/// Insert code in the prolog/epilog code when unrolling a loop with a
544/// run-time trip-count.
545///
546/// This method assumes that the loop unroll factor is total number
547/// of loop bodies in the loop after unrolling. (Some folks refer
548/// to the unroll factor as the number of *extra* copies added).
549/// We assume also that the loop unroll factor is a power-of-two. So, after
550/// unrolling the loop, the number of loop bodies executed is 2,
551/// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch
552/// instruction in SimplifyCFG.cpp. Then, the backend decides how code for
553/// the switch instruction is generated.
554///
555/// ***Prolog case***
556/// extraiters = tripcount % loopfactor
557/// if (extraiters == 0) jump Loop:
558/// else jump Prol:
559/// Prol: LoopBody;
560/// extraiters -= 1 // Omitted if unroll factor is 2.
561/// if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
562/// if (tripcount < loopfactor) jump End:
563/// Loop:
564/// ...
565/// End:
566///
567/// ***Epilog case***
568/// extraiters = tripcount % loopfactor
569/// if (tripcount < loopfactor) jump LoopExit:
570/// unroll_iters = tripcount - extraiters
571/// Loop: LoopBody; (executes unroll_iter times);
572/// unroll_iter -= 1
573/// if (unroll_iter != 0) jump Loop:
574/// LoopExit:
575/// if (extraiters == 0) jump EpilExit:
576/// Epil: LoopBody; (executes extraiters times)
577/// extraiters -= 1 // Omitted if unroll factor is 2.
578/// if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
579/// EpilExit:
580
582 Loop *L, unsigned Count, bool AllowExpensiveTripCount,
583 bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,
585 const TargetTransformInfo *TTI, bool PreserveLCSSA,
586 unsigned SCEVExpansionBudget, bool RuntimeUnrollMultiExit,
587 Loop **ResultLoop) {
588 LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
589 LLVM_DEBUG(L->dump());
590 LLVM_DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"
591 : dbgs() << "Using prolog remainder.\n");
592
593 // Make sure the loop is in canonical form.
594 if (!L->isLoopSimplifyForm()) {
595 LLVM_DEBUG(dbgs() << "Not in simplify form!\n");
596 return false;
597 }
598
599 // Guaranteed by LoopSimplifyForm.
600 BasicBlock *Latch = L->getLoopLatch();
601 BasicBlock *Header = L->getHeader();
602
603 BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
604
605 if (!LatchBR || LatchBR->isUnconditional()) {
606 // The loop-rotate pass can be helpful to avoid this in many cases.
608 dbgs()
609 << "Loop latch not terminated by a conditional branch.\n");
610 return false;
611 }
612
613 unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 1 : 0;
614 BasicBlock *LatchExit = LatchBR->getSuccessor(ExitIndex);
615
616 if (L->contains(LatchExit)) {
617 // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
618 // targets of the Latch be an exit block out of the loop.
620 dbgs()
621 << "One of the loop latch successors must be the exit block.\n");
622 return false;
623 }
624
625 // These are exit blocks other than the target of the latch exiting block.
627 L->getUniqueNonLatchExitBlocks(OtherExits);
628 // Support only single exit and exiting block unless multi-exit loop
629 // unrolling is enabled.
630 if (!L->getExitingBlock() || OtherExits.size()) {
631 // We rely on LCSSA form being preserved when the exit blocks are transformed.
632 // (Note that only an off-by-default mode of the old PM disables PreserveLCCA.)
633 if (!PreserveLCSSA)
634 return false;
635
636 if (!RuntimeUnrollMultiExit &&
637 !canProfitablyRuntimeUnrollMultiExitLoop(L, OtherExits, LatchExit,
638 UseEpilogRemainder)) {
640 dbgs()
641 << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
642 "enabled!\n");
643 return false;
644 }
645 }
646 // Use Scalar Evolution to compute the trip count. This allows more loops to
647 // be unrolled than relying on induction var simplification.
648 if (!SE)
649 return false;
650
651 // Only unroll loops with a computable trip count.
652 // We calculate the backedge count by using getExitCount on the Latch block,
653 // which is proven to be the only exiting block in this loop. This is same as
654 // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
655 // exiting blocks).
656 const SCEV *BECountSC = SE->getExitCount(L, Latch);
657 if (isa<SCEVCouldNotCompute>(BECountSC)) {
658 LLVM_DEBUG(dbgs() << "Could not compute exit block SCEV\n");
659 return false;
660 }
661
662 unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
663
664 // Add 1 since the backedge count doesn't include the first loop iteration.
665 // (Note that overflow can occur, this is handled explicitly below)
666 const SCEV *TripCountSC =
667 SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
668 if (isa<SCEVCouldNotCompute>(TripCountSC)) {
669 LLVM_DEBUG(dbgs() << "Could not compute trip count SCEV.\n");
670 return false;
671 }
672
673 BasicBlock *PreHeader = L->getLoopPreheader();
674 BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
675 const DataLayout &DL = Header->getDataLayout();
676 SCEVExpander Expander(*SE, DL, "loop-unroll");
677 if (!AllowExpensiveTripCount &&
678 Expander.isHighCostExpansion(TripCountSC, L, SCEVExpansionBudget, TTI,
679 PreHeaderBR)) {
680 LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
681 return false;
682 }
683
684 // This constraint lets us deal with an overflowing trip count easily; see the
685 // comment on ModVal below.
686 if (Log2_32(Count) > BEWidth) {
688 dbgs()
689 << "Count failed constraint on overflow trip count calculation.\n");
690 return false;
691 }
692
693 // Loop structure is the following:
694 //
695 // PreHeader
696 // Header
697 // ...
698 // Latch
699 // LatchExit
700
701 BasicBlock *NewPreHeader;
702 BasicBlock *NewExit = nullptr;
703 BasicBlock *PrologExit = nullptr;
704 BasicBlock *EpilogPreHeader = nullptr;
705 BasicBlock *PrologPreHeader = nullptr;
706
707 if (UseEpilogRemainder) {
708 // If epilog remainder
709 // Split PreHeader to insert a branch around loop for unrolling.
710 NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
711 NewPreHeader->setName(PreHeader->getName() + ".new");
712 // Split LatchExit to create phi nodes from branch above.
713 NewExit = SplitBlockPredecessors(LatchExit, {Latch}, ".unr-lcssa", DT, LI,
714 nullptr, PreserveLCSSA);
715 // NewExit gets its DebugLoc from LatchExit, which is not part of the
716 // original Loop.
717 // Fix this by setting Loop's DebugLoc to NewExit.
718 auto *NewExitTerminator = NewExit->getTerminator();
719 NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());
720 // Split NewExit to insert epilog remainder loop.
721 EpilogPreHeader = SplitBlock(NewExit, NewExitTerminator, DT, LI);
722 EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
723
724 // If the latch exits from multiple level of nested loops, then
725 // by assumption there must be another loop exit which branches to the
726 // outer loop and we must adjust the loop for the newly inserted blocks
727 // to account for the fact that our epilogue is still in the same outer
728 // loop. Note that this leaves loopinfo temporarily out of sync with the
729 // CFG until the actual epilogue loop is inserted.
730 if (auto *ParentL = L->getParentLoop())
731 if (LI->getLoopFor(LatchExit) != ParentL) {
732 LI->removeBlock(NewExit);
733 ParentL->addBasicBlockToLoop(NewExit, *LI);
734 LI->removeBlock(EpilogPreHeader);
735 ParentL->addBasicBlockToLoop(EpilogPreHeader, *LI);
736 }
737
738 } else {
739 // If prolog remainder
740 // Split the original preheader twice to insert prolog remainder loop
741 PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
742 PrologPreHeader->setName(Header->getName() + ".prol.preheader");
743 PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
744 DT, LI);
745 PrologExit->setName(Header->getName() + ".prol.loopexit");
746 // Split PrologExit to get NewPreHeader.
747 NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
748 NewPreHeader->setName(PreHeader->getName() + ".new");
749 }
750 // Loop structure should be the following:
751 // Epilog Prolog
752 //
753 // PreHeader PreHeader
754 // *NewPreHeader *PrologPreHeader
755 // Header *PrologExit
756 // ... *NewPreHeader
757 // Latch Header
758 // *NewExit ...
759 // *EpilogPreHeader Latch
760 // LatchExit LatchExit
761
762 // Calculate conditions for branch around loop for unrolling
763 // in epilog case and around prolog remainder loop in prolog case.
764 // Compute the number of extra iterations required, which is:
765 // extra iterations = run-time trip count % loop unroll factor
766 PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
767 IRBuilder<> B(PreHeaderBR);
768 Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
769 PreHeaderBR);
770 Value *BECount;
771 // If there are other exits before the latch, that may cause the latch exit
772 // branch to never be executed, and the latch exit count may be poison.
773 // In this case, freeze the TripCount and base BECount on the frozen
774 // TripCount. We will introduce two branches using these values, and it's
775 // important that they see a consistent value (which would not be guaranteed
776 // if were frozen independently.)
777 if ((!OtherExits.empty() || !SE->loopHasNoAbnormalExits(L)) &&
778 !isGuaranteedNotToBeUndefOrPoison(TripCount, AC, PreHeaderBR, DT)) {
779 TripCount = B.CreateFreeze(TripCount);
780 BECount =
781 B.CreateAdd(TripCount, Constant::getAllOnesValue(TripCount->getType()));
782 } else {
783 // If we don't need to freeze, use SCEVExpander for BECount as well, to
784 // allow slightly better value reuse.
785 BECount =
786 Expander.expandCodeFor(BECountSC, BECountSC->getType(), PreHeaderBR);
787 }
788
789 Value * const ModVal = CreateTripRemainder(B, BECount, TripCount, Count);
790
791 Value *BranchVal =
792 UseEpilogRemainder ? B.CreateICmpULT(BECount,
793 ConstantInt::get(BECount->getType(),
794 Count - 1)) :
795 B.CreateIsNotNull(ModVal, "lcmp.mod");
796 BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
797 BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
798 // Branch to either remainder (extra iterations) loop or unrolling loop.
799 MDNode *BranchWeights = nullptr;
800 if (hasBranchWeightMD(*Latch->getTerminator())) {
801 // Assume loop is nearly always entered.
802 MDBuilder MDB(B.getContext());
803 BranchWeights = MDB.createBranchWeights(EpilogHeaderWeights);
804 }
805 B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop, BranchWeights);
806 PreHeaderBR->eraseFromParent();
807 if (DT) {
808 if (UseEpilogRemainder)
809 DT->changeImmediateDominator(NewExit, PreHeader);
810 else
811 DT->changeImmediateDominator(PrologExit, PreHeader);
812 }
813 Function *F = Header->getParent();
814 // Get an ordered list of blocks in the loop to help with the ordering of the
815 // cloned blocks in the prolog/epilog code
816 LoopBlocksDFS LoopBlocks(L);
817 LoopBlocks.perform(LI);
818
819 //
820 // For each extra loop iteration, create a copy of the loop's basic blocks
821 // and generate a condition that branches to the copy depending on the
822 // number of 'left over' iterations.
823 //
824 std::vector<BasicBlock *> NewBlocks;
826
827 // Clone all the basic blocks in the loop. If Count is 2, we don't clone
828 // the loop, otherwise we create a cloned loop to execute the extra
829 // iterations. This function adds the appropriate CFG connections.
830 BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;
831 BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
832 Loop *remainderLoop = CloneLoopBlocks(
833 L, ModVal, UseEpilogRemainder, UnrollRemainder, InsertTop, InsertBot,
834 NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI, Count);
835
836 // Insert the cloned blocks into the function.
837 F->splice(InsertBot->getIterator(), F, NewBlocks[0]->getIterator(), F->end());
838
839 // Now the loop blocks are cloned and the other exiting blocks from the
840 // remainder are connected to the original Loop's exit blocks. The remaining
841 // work is to update the phi nodes in the original loop, and take in the
842 // values from the cloned region.
843 for (auto *BB : OtherExits) {
844 // Given we preserve LCSSA form, we know that the values used outside the
845 // loop will be used through these phi nodes at the exit blocks that are
846 // transformed below.
847 for (PHINode &PN : BB->phis()) {
848 unsigned oldNumOperands = PN.getNumIncomingValues();
849 // Add the incoming values from the remainder code to the end of the phi
850 // node.
851 for (unsigned i = 0; i < oldNumOperands; i++){
852 auto *PredBB =PN.getIncomingBlock(i);
853 if (PredBB == Latch)
854 // The latch exit is handled separately, see connectX
855 continue;
856 if (!L->contains(PredBB))
857 // Even if we had dedicated exits, the code above inserted an
858 // extra branch which can reach the latch exit.
859 continue;
860
861 auto *V = PN.getIncomingValue(i);
862 if (Instruction *I = dyn_cast<Instruction>(V))
863 if (L->contains(I))
864 V = VMap.lookup(I);
865 PN.addIncoming(V, cast<BasicBlock>(VMap[PredBB]));
866 }
867 }
868#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
869 for (BasicBlock *SuccBB : successors(BB)) {
870 assert(!(llvm::is_contained(OtherExits, SuccBB) || SuccBB == LatchExit) &&
871 "Breaks the definition of dedicated exits!");
872 }
873#endif
874 }
875
876 // Update the immediate dominator of the exit blocks and blocks that are
877 // reachable from the exit blocks. This is needed because we now have paths
878 // from both the original loop and the remainder code reaching the exit
879 // blocks. While the IDom of these exit blocks were from the original loop,
880 // now the IDom is the preheader (which decides whether the original loop or
881 // remainder code should run).
882 if (DT && !L->getExitingBlock()) {
883 SmallVector<BasicBlock *, 16> ChildrenToUpdate;
884 // NB! We have to examine the dom children of all loop blocks, not just
885 // those which are the IDom of the exit blocks. This is because blocks
886 // reachable from the exit blocks can have their IDom as the nearest common
887 // dominator of the exit blocks.
888 for (auto *BB : L->blocks()) {
889 auto *DomNodeBB = DT->getNode(BB);
890 for (auto *DomChild : DomNodeBB->children()) {
891 auto *DomChildBB = DomChild->getBlock();
892 if (!L->contains(LI->getLoopFor(DomChildBB)))
893 ChildrenToUpdate.push_back(DomChildBB);
894 }
895 }
896 for (auto *BB : ChildrenToUpdate)
897 DT->changeImmediateDominator(BB, PreHeader);
898 }
899
900 // Loop structure should be the following:
901 // Epilog Prolog
902 //
903 // PreHeader PreHeader
904 // NewPreHeader PrologPreHeader
905 // Header PrologHeader
906 // ... ...
907 // Latch PrologLatch
908 // NewExit PrologExit
909 // EpilogPreHeader NewPreHeader
910 // EpilogHeader Header
911 // ... ...
912 // EpilogLatch Latch
913 // LatchExit LatchExit
914
915 // Rewrite the cloned instruction operands to use the values created when the
916 // clone is created.
917 for (BasicBlock *BB : NewBlocks) {
918 Module *M = BB->getModule();
919 for (Instruction &I : *BB) {
920 RemapInstruction(&I, VMap,
922 RemapDbgRecordRange(M, I.getDbgRecordRange(), VMap,
924 }
925 }
926
927 if (UseEpilogRemainder) {
928 // Connect the epilog code to the original loop and update the
929 // PHI functions.
930 ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader, EpilogPreHeader,
931 NewPreHeader, VMap, DT, LI, PreserveLCSSA, *SE, Count);
932
933 // Update counter in loop for unrolling.
934 // Use an incrementing IV. Pre-incr/post-incr is backedge/trip count.
935 // Subtle: TestVal can be 0 if we wrapped when computing the trip count,
936 // thus we must compare the post-increment (wrapping) value.
937 IRBuilder<> B2(NewPreHeader->getTerminator());
938 Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
939 BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
940 PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter");
941 NewIdx->insertBefore(Header->getFirstNonPHIIt());
942 B2.SetInsertPoint(LatchBR);
943 auto *Zero = ConstantInt::get(NewIdx->getType(), 0);
944 auto *One = ConstantInt::get(NewIdx->getType(), 1);
945 Value *IdxNext = B2.CreateAdd(NewIdx, One, NewIdx->getName() + ".next");
946 auto Pred = LatchBR->getSuccessor(0) == Header ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;
947 Value *IdxCmp = B2.CreateICmp(Pred, IdxNext, TestVal, NewIdx->getName() + ".ncmp");
948 NewIdx->addIncoming(Zero, NewPreHeader);
949 NewIdx->addIncoming(IdxNext, Latch);
950 LatchBR->setCondition(IdxCmp);
951 } else {
952 // Connect the prolog code to the original loop and update the
953 // PHI functions.
954 ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,
955 NewPreHeader, VMap, DT, LI, PreserveLCSSA, *SE);
956 }
957
958 // If this loop is nested, then the loop unroller changes the code in the any
959 // of its parent loops, so the Scalar Evolution pass needs to be run again.
960 SE->forgetTopmostLoop(L);
961
962 // Verify that the Dom Tree and Loop Info are correct.
963#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
964 if (DT) {
965 assert(DT->verify(DominatorTree::VerificationLevel::Full));
966 LI->verify(*DT);
967 }
968#endif
969
970 // For unroll factor 2 remainder loop will have 1 iteration.
971 if (Count == 2 && DT && LI && SE) {
972 // TODO: This code could probably be pulled out into a helper function
973 // (e.g. breakLoopBackedgeAndSimplify) and reused in loop-deletion.
974 BasicBlock *RemainderLatch = remainderLoop->getLoopLatch();
975 assert(RemainderLatch);
976 SmallVector<BasicBlock *> RemainderBlocks(remainderLoop->getBlocks());
977 breakLoopBackedge(remainderLoop, *DT, *SE, *LI, nullptr);
978 remainderLoop = nullptr;
979
980 // Simplify loop values after breaking the backedge
981 const DataLayout &DL = L->getHeader()->getDataLayout();
983 for (BasicBlock *BB : RemainderBlocks) {
984 for (Instruction &Inst : llvm::make_early_inc_range(*BB)) {
985 if (Value *V = simplifyInstruction(&Inst, {DL, nullptr, DT, AC}))
986 if (LI->replacementPreservesLCSSAForm(&Inst, V))
987 Inst.replaceAllUsesWith(V);
989 DeadInsts.emplace_back(&Inst);
990 }
991 // We can't do recursive deletion until we're done iterating, as we might
992 // have a phi which (potentially indirectly) uses instructions later in
993 // the block we're iterating through.
995 }
996
997 // Merge latch into exit block.
998 auto *ExitBB = RemainderLatch->getSingleSuccessor();
999 assert(ExitBB && "required after breaking cond br backedge");
1000 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
1001 MergeBlockIntoPredecessor(ExitBB, &DTU, LI);
1002 }
1003
1004 // Canonicalize to LoopSimplifyForm both original and remainder loops. We
1005 // cannot rely on the LoopUnrollPass to do this because it only does
1006 // canonicalization for parent/subloops and not the sibling loops.
1007 if (OtherExits.size() > 0) {
1008 // Generate dedicated exit blocks for the original loop, to preserve
1009 // LoopSimplifyForm.
1010 formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA);
1011 // Generate dedicated exit blocks for the remainder loop if one exists, to
1012 // preserve LoopSimplifyForm.
1013 if (remainderLoop)
1014 formDedicatedExitBlocks(remainderLoop, DT, LI, nullptr, PreserveLCSSA);
1015 }
1016
1017 auto UnrollResult = LoopUnrollResult::Unmodified;
1018 if (remainderLoop && UnrollRemainder) {
1019 LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");
1021 ULO.Count = Count - 1;
1022 ULO.Force = false;
1023 ULO.Runtime = false;
1024 ULO.AllowExpensiveTripCount = false;
1025 ULO.UnrollRemainder = false;
1026 ULO.ForgetAllSCEV = ForgetAllSCEV;
1028 "A loop with a convergence heart does not allow runtime unrolling.");
1029 UnrollResult = UnrollLoop(remainderLoop, ULO, LI, SE, DT, AC, TTI,
1030 /*ORE*/ nullptr, PreserveLCSSA);
1031 }
1032
1033 if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)
1034 *ResultLoop = remainderLoop;
1035 NumRuntimeUnrolled++;
1036 return true;
1037}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DEBUG(...)
Definition: Debug.h:106
Module.h This file contains the declarations for the Module class.
static Loop * CloneLoopBlocks(Loop *L, Value *NewIter, const bool UseEpilogRemainder, const bool UnrollRemainder, BasicBlock *InsertTop, BasicBlock *InsertBot, BasicBlock *Preheader, std::vector< BasicBlock * > &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, unsigned Count)
Create a clone of the blocks in a loop and connect them together.
static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit, BasicBlock *Exit, BasicBlock *PreHeader, BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA, ScalarEvolution &SE, unsigned Count)
Connect the unrolling epilog code to the original loop.
static const uint32_t UnrolledLoopHeaderWeights[]
static Value * CreateTripRemainder(IRBuilder<> &B, Value *BECount, Value *TripCount, unsigned Count)
Calculate ModVal = (BECount + 1) % Count on the abstract integer domain accounting for the possibilit...
static cl::opt< bool > UnrollRuntimeOtherExitPredictable("unroll-runtime-other-exit-predictable", cl::init(false), cl::Hidden, cl::desc("Assume the non latch exit block to be predictable"))
static bool canProfitablyRuntimeUnrollMultiExitLoop(Loop *L, SmallVectorImpl< BasicBlock * > &OtherExits, BasicBlock *LatchExit, bool UseEpilogRemainder)
Returns true if we can profitably unroll the multi-exit loop L.
static const uint32_t EpilogHeaderWeights[]
static cl::opt< bool > UnrollRuntimeMultiExit("unroll-runtime-multi-exit", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolling for loops with multiple exits, when " "epilog is generated"))
static void ConnectProlog(Loop *L, Value *BECount, unsigned Count, BasicBlock *PrologExit, BasicBlock *OriginalLoopLatchExit, BasicBlock *PreHeader, BasicBlock *NewPreHeader, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA, ScalarEvolution &SE)
Connect the unrolling prolog code to the original loop.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file contains the declarations for profiling metadata utility functions.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:166
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:520
InstListType::const_iterator getFirstNonPHIIt() const
Iterator returning form of getFirstNonPHI.
Definition: BasicBlock.cpp:374
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:501
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:240
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
This is an important base class in LLVM.
Definition: Constant.h:42
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:420
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
DomTreeNodeBase * getIDom() const
NodeT * getBlock() const
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
Definition: Dominators.cpp:344
Value * CreateICmpNE(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2274
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1387
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
Definition: IRBuilder.h:1164
LLVMContext & getContext() const
Definition: IRBuilder.h:195
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1370
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:199
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2380
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2705
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:99
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:94
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:489
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:101
void perform(const LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1266
RPOIterator endRPO() const
Definition: LoopIterator.h:140
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:439
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:39
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:526
void setLoopAlreadyUnrolled()
Add llvm.loop.unroll.disable to this loop's loop id metadata.
Definition: LoopInfo.cpp:538
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:502
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
Definition: MDBuilder.cpp:37
Metadata node.
Definition: Metadata.h:1073
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
void setIncomingBlock(unsigned i, BasicBlock *BB)
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1878
This class uses information about analyze scalars to rewrite expressions in canonical form.
bool isHighCostExpansion(ArrayRef< const SCEV * > Exprs, Loop *L, unsigned Budget, const TargetTransformInfo *TTI, const Instruction *At)
Return true for expressions that can't be evaluated at runtime within given Budget.
Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getConstant(ConstantInt *V)
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
void forgetTopmostLoop(const Loop *L)
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
bool empty() const
Definition: SmallVector.h:81
size_t size() const
Definition: SmallVector.h:78
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:573
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:937
void push_back(const T &Elt)
Definition: SmallVector.h:413
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:51
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: ValueMap.h:164
bool erase(const KeyT &Val)
Definition: ValueMap.h:190
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:377
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
int getNumOccurrences() const
Definition: CommandLine.h:399
const ParentTy * getParent() const
Definition: ilist_node.h:32
self_iterator getIterator()
Definition: ilist_node.h:132
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:546
auto successors(const MachineBasicBlock *BB)
std::optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)
Create a new loop identifier for a loop created from a loop transformation.
Definition: LoopUtils.cpp:263
void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataSetTy *IdentityMD=nullptr)
Remap the Values used in the DbgRecords Range using the value map VM.
Definition: ValueMapper.h:299
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:657
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:406
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:341
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:292
CallBase * getLoopConvergenceHeart(const Loop *TheLoop)
Find the convergence heart of the loop.
Definition: LoopInfo.cpp:1132
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition: ValueMapper.h:96
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:78
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataSetTy *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
Definition: ValueMapper.h:277
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Definition: LoopUtils.cpp:725
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
const char *const LLVMLoopUnrollFollowupAll
Definition: UnrollLoop.h:44
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:57
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
const char *const LLVMLoopUnrollFollowupRemainder
Definition: UnrollLoop.h:47
const Loop * addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops)
Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary and adds a mapping from the o...
Definition: LoopUnroll.cpp:148
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1903
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, bool PreserveLCSSA, unsigned SCEVExpansionBudget, bool RuntimeUnrollMultiExit, Loop **ResultLoop=nullptr)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
bool hasBranchWeightMD(const Instruction &I)
Checks if an instructions has Branch Weight Metadata.
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const llvm::TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr, AAResults *AA=nullptr)
Unroll the given loop by Count.
Definition: LoopUnroll.cpp:458