1 //===-- UnrollLoopRuntime.cpp - Runtime Loop unrolling utilities ----------===//
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
7 //===----------------------------------------------------------------------===//
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
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.
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
21 //===----------------------------------------------------------------------===//
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Analysis/AliasAnalysis.h"
26 #include "llvm/Analysis/LoopIterator.h"
27 #include "llvm/Analysis/ScalarEvolution.h"
28 #include "llvm/Analysis/ScalarEvolutionExpander.h"
29 #include "llvm/IR/BasicBlock.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/IR/Metadata.h"
32 #include "llvm/IR/Module.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/raw_ostream.h"
35 #include "llvm/Transforms/Utils.h"
36 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
37 #include "llvm/Transforms/Utils/Cloning.h"
38 #include "llvm/Transforms/Utils/LoopUtils.h"
39 #include "llvm/Transforms/Utils/UnrollLoop.h"
44 #define DEBUG_TYPE "loop-unroll"
46 STATISTIC(NumRuntimeUnrolled
,
47 "Number of loops unrolled with run-time trip counts");
48 static cl::opt
<bool> UnrollRuntimeMultiExit(
49 "unroll-runtime-multi-exit", cl::init(false), cl::Hidden
,
50 cl::desc("Allow runtime unrolling for loops with multiple exits, when "
51 "epilog is generated"));
53 /// Connect the unrolling prolog code to the original loop.
54 /// The unrolling prolog code contains code to execute the
55 /// 'extra' iterations if the run-time trip count modulo the
56 /// unroll count is non-zero.
58 /// This function performs the following:
59 /// - Create PHI nodes at prolog end block to combine values
60 /// that exit the prolog code and jump around the prolog.
61 /// - Add a PHI operand to a PHI node at the loop exit block
62 /// for values that exit the prolog and go around the loop.
63 /// - Branch around the original loop if the trip count is less
64 /// than the unroll factor.
66 static void ConnectProlog(Loop
*L
, Value
*BECount
, unsigned Count
,
67 BasicBlock
*PrologExit
,
68 BasicBlock
*OriginalLoopLatchExit
,
69 BasicBlock
*PreHeader
, BasicBlock
*NewPreHeader
,
70 ValueToValueMapTy
&VMap
, DominatorTree
*DT
,
71 LoopInfo
*LI
, bool PreserveLCSSA
) {
72 // Loop structure should be the following:
83 BasicBlock
*Latch
= L
->getLoopLatch();
84 assert(Latch
&& "Loop must have a latch");
85 BasicBlock
*PrologLatch
= cast
<BasicBlock
>(VMap
[Latch
]);
87 // Create a PHI node for each outgoing value from the original loop
88 // (which means it is an outgoing value from the prolog code too).
89 // The new PHI node is inserted in the prolog end basic block.
90 // The new PHI node value is added as an operand of a PHI node in either
91 // the loop header or the loop exit block.
92 for (BasicBlock
*Succ
: successors(Latch
)) {
93 for (PHINode
&PN
: Succ
->phis()) {
94 // Add a new PHI node to the prolog end block and add the
95 // appropriate incoming values.
96 // TODO: This code assumes that the PrologExit (or the LatchExit block for
97 // prolog loop) contains only one predecessor from the loop, i.e. the
98 // PrologLatch. When supporting multiple-exiting block loops, we can have
99 // two or more blocks that have the LatchExit as the target in the
101 PHINode
*NewPN
= PHINode::Create(PN
.getType(), 2, PN
.getName() + ".unr",
102 PrologExit
->getFirstNonPHI());
103 // Adding a value to the new PHI node from the original loop preheader.
104 // This is the value that skips all the prolog code.
105 if (L
->contains(&PN
)) {
106 // Succ is loop header.
107 NewPN
->addIncoming(PN
.getIncomingValueForBlock(NewPreHeader
),
110 // Succ is LatchExit.
111 NewPN
->addIncoming(UndefValue::get(PN
.getType()), PreHeader
);
114 Value
*V
= PN
.getIncomingValueForBlock(Latch
);
115 if (Instruction
*I
= dyn_cast
<Instruction
>(V
)) {
116 if (L
->contains(I
)) {
120 // Adding a value to the new PHI node from the last prolog block
122 NewPN
->addIncoming(V
, PrologLatch
);
124 // Update the existing PHI node operand with the value from the
125 // new PHI node. How this is done depends on if the existing
126 // PHI node is in the original loop block, or the exit block.
127 if (L
->contains(&PN
)) {
128 PN
.setIncomingValue(PN
.getBasicBlockIndex(NewPreHeader
), NewPN
);
130 PN
.addIncoming(NewPN
, PrologExit
);
135 // Make sure that created prolog loop is in simplified form
136 SmallVector
<BasicBlock
*, 4> PrologExitPreds
;
137 Loop
*PrologLoop
= LI
->getLoopFor(PrologLatch
);
139 for (BasicBlock
*PredBB
: predecessors(PrologExit
))
140 if (PrologLoop
->contains(PredBB
))
141 PrologExitPreds
.push_back(PredBB
);
143 SplitBlockPredecessors(PrologExit
, PrologExitPreds
, ".unr-lcssa", DT
, LI
,
144 nullptr, PreserveLCSSA
);
147 // Create a branch around the original loop, which is taken if there are no
148 // iterations remaining to be executed after running the prologue.
149 Instruction
*InsertPt
= PrologExit
->getTerminator();
150 IRBuilder
<> B(InsertPt
);
152 assert(Count
!= 0 && "nonsensical Count!");
154 // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)
155 // This means %xtraiter is (BECount + 1) and all of the iterations of this
156 // loop were executed by the prologue. Note that if BECount <u (Count - 1)
157 // then (BECount + 1) cannot unsigned-overflow.
159 B
.CreateICmpULT(BECount
, ConstantInt::get(BECount
->getType(), Count
- 1));
160 // Split the exit to maintain loop canonicalization guarantees
161 SmallVector
<BasicBlock
*, 4> Preds(predecessors(OriginalLoopLatchExit
));
162 SplitBlockPredecessors(OriginalLoopLatchExit
, Preds
, ".unr-lcssa", DT
, LI
,
163 nullptr, PreserveLCSSA
);
164 // Add the branch to the exit block (around the unrolled loop)
165 B
.CreateCondBr(BrLoopExit
, OriginalLoopLatchExit
, NewPreHeader
);
166 InsertPt
->eraseFromParent();
168 DT
->changeImmediateDominator(OriginalLoopLatchExit
, PrologExit
);
171 /// Connect the unrolling epilog code to the original loop.
172 /// The unrolling epilog code contains code to execute the
173 /// 'extra' iterations if the run-time trip count modulo the
174 /// unroll count is non-zero.
176 /// This function performs the following:
177 /// - Update PHI nodes at the unrolling loop exit and epilog loop exit
178 /// - Create PHI nodes at the unrolling loop exit to combine
179 /// values that exit the unrolling loop code and jump around it.
180 /// - Update PHI operands in the epilog loop by the new PHI nodes
181 /// - Branch around the epilog loop if extra iters (ModVal) is zero.
183 static void ConnectEpilog(Loop
*L
, Value
*ModVal
, BasicBlock
*NewExit
,
184 BasicBlock
*Exit
, BasicBlock
*PreHeader
,
185 BasicBlock
*EpilogPreHeader
, BasicBlock
*NewPreHeader
,
186 ValueToValueMapTy
&VMap
, DominatorTree
*DT
,
187 LoopInfo
*LI
, bool PreserveLCSSA
) {
188 BasicBlock
*Latch
= L
->getLoopLatch();
189 assert(Latch
&& "Loop must have a latch");
190 BasicBlock
*EpilogLatch
= cast
<BasicBlock
>(VMap
[Latch
]);
192 // Loop structure should be the following:
206 // Update PHI nodes at NewExit and Exit.
207 for (PHINode
&PN
: NewExit
->phis()) {
208 // PN should be used in another PHI located in Exit block as
209 // Exit was split by SplitBlockPredecessors into Exit and NewExit
210 // Basicaly it should look like:
212 // PN = PHI [I, Latch]
215 // EpilogPN = PHI [PN, EpilogPreHeader]
217 // There is EpilogPreHeader incoming block instead of NewExit as
218 // NewExit was spilt 1 more time to get EpilogPreHeader.
219 assert(PN
.hasOneUse() && "The phi should have 1 use");
220 PHINode
*EpilogPN
= cast
<PHINode
>(PN
.use_begin()->getUser());
221 assert(EpilogPN
->getParent() == Exit
&& "EpilogPN should be in Exit block");
223 // Add incoming PreHeader from branch around the Loop
224 PN
.addIncoming(UndefValue::get(PN
.getType()), PreHeader
);
226 Value
*V
= PN
.getIncomingValueForBlock(Latch
);
227 Instruction
*I
= dyn_cast
<Instruction
>(V
);
228 if (I
&& L
->contains(I
))
229 // If value comes from an instruction in the loop add VMap value.
231 // For the instruction out of the loop, constant or undefined value
232 // insert value itself.
233 EpilogPN
->addIncoming(V
, EpilogLatch
);
235 assert(EpilogPN
->getBasicBlockIndex(EpilogPreHeader
) >= 0 &&
236 "EpilogPN should have EpilogPreHeader incoming block");
237 // Change EpilogPreHeader incoming block to NewExit.
238 EpilogPN
->setIncomingBlock(EpilogPN
->getBasicBlockIndex(EpilogPreHeader
),
240 // Now PHIs should look like:
242 // PN = PHI [I, Latch], [undef, PreHeader]
245 // EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]
248 // Create PHI nodes at NewExit (from the unrolling loop Latch and PreHeader).
249 // Update corresponding PHI nodes in epilog loop.
250 for (BasicBlock
*Succ
: successors(Latch
)) {
251 // Skip this as we already updated phis in exit blocks.
252 if (!L
->contains(Succ
))
254 for (PHINode
&PN
: Succ
->phis()) {
255 // Add new PHI nodes to the loop exit block and update epilog
256 // PHIs with the new PHI values.
257 PHINode
*NewPN
= PHINode::Create(PN
.getType(), 2, PN
.getName() + ".unr",
258 NewExit
->getFirstNonPHI());
259 // Adding a value to the new PHI node from the unrolling loop preheader.
260 NewPN
->addIncoming(PN
.getIncomingValueForBlock(NewPreHeader
), PreHeader
);
261 // Adding a value to the new PHI node from the unrolling loop latch.
262 NewPN
->addIncoming(PN
.getIncomingValueForBlock(Latch
), Latch
);
264 // Update the existing PHI node operand with the value from the new PHI
265 // node. Corresponding instruction in epilog loop should be PHI.
266 PHINode
*VPN
= cast
<PHINode
>(VMap
[&PN
]);
267 VPN
->setIncomingValue(VPN
->getBasicBlockIndex(EpilogPreHeader
), NewPN
);
271 Instruction
*InsertPt
= NewExit
->getTerminator();
272 IRBuilder
<> B(InsertPt
);
273 Value
*BrLoopExit
= B
.CreateIsNotNull(ModVal
, "lcmp.mod");
274 assert(Exit
&& "Loop must have a single exit block only");
275 // Split the epilogue exit to maintain loop canonicalization guarantees
276 SmallVector
<BasicBlock
*, 4> Preds(predecessors(Exit
));
277 SplitBlockPredecessors(Exit
, Preds
, ".epilog-lcssa", DT
, LI
, nullptr,
279 // Add the branch to the exit block (around the unrolling loop)
280 B
.CreateCondBr(BrLoopExit
, EpilogPreHeader
, Exit
);
281 InsertPt
->eraseFromParent();
283 DT
->changeImmediateDominator(Exit
, NewExit
);
285 // Split the main loop exit to maintain canonicalization guarantees.
286 SmallVector
<BasicBlock
*, 4> NewExitPreds
{Latch
};
287 SplitBlockPredecessors(NewExit
, NewExitPreds
, ".loopexit", DT
, LI
, nullptr,
291 /// Create a clone of the blocks in a loop and connect them together.
292 /// If CreateRemainderLoop is false, loop structure will not be cloned,
293 /// otherwise a new loop will be created including all cloned blocks, and the
294 /// iterator of it switches to count NewIter down to 0.
295 /// The cloned blocks should be inserted between InsertTop and InsertBot.
296 /// If loop structure is cloned InsertTop should be new preheader, InsertBot
298 /// Return the new cloned loop that is created when CreateRemainderLoop is true.
300 CloneLoopBlocks(Loop
*L
, Value
*NewIter
, const bool CreateRemainderLoop
,
301 const bool UseEpilogRemainder
, const bool UnrollRemainder
,
302 BasicBlock
*InsertTop
,
303 BasicBlock
*InsertBot
, BasicBlock
*Preheader
,
304 std::vector
<BasicBlock
*> &NewBlocks
, LoopBlocksDFS
&LoopBlocks
,
305 ValueToValueMapTy
&VMap
, DominatorTree
*DT
, LoopInfo
*LI
) {
306 StringRef suffix
= UseEpilogRemainder
? "epil" : "prol";
307 BasicBlock
*Header
= L
->getHeader();
308 BasicBlock
*Latch
= L
->getLoopLatch();
309 Function
*F
= Header
->getParent();
310 LoopBlocksDFS::RPOIterator BlockBegin
= LoopBlocks
.beginRPO();
311 LoopBlocksDFS::RPOIterator BlockEnd
= LoopBlocks
.endRPO();
312 Loop
*ParentLoop
= L
->getParentLoop();
313 NewLoopsMap NewLoops
;
314 NewLoops
[ParentLoop
] = ParentLoop
;
315 if (!CreateRemainderLoop
)
316 NewLoops
[L
] = ParentLoop
;
318 // For each block in the original loop, create a new copy,
319 // and update the value map with the newly created values.
320 for (LoopBlocksDFS::RPOIterator BB
= BlockBegin
; BB
!= BlockEnd
; ++BB
) {
321 BasicBlock
*NewBB
= CloneBasicBlock(*BB
, VMap
, "." + suffix
, F
);
322 NewBlocks
.push_back(NewBB
);
324 // If we're unrolling the outermost loop, there's no remainder loop,
325 // and this block isn't in a nested loop, then the new block is not
326 // in any loop. Otherwise, add it to loopinfo.
327 if (CreateRemainderLoop
|| LI
->getLoopFor(*BB
) != L
|| ParentLoop
)
328 addClonedBlockToLoopInfo(*BB
, NewBB
, LI
, NewLoops
);
332 // For the first block, add a CFG connection to this newly
334 InsertTop
->getTerminator()->setSuccessor(0, NewBB
);
339 // The header is dominated by the preheader.
340 DT
->addNewBlock(NewBB
, InsertTop
);
342 // Copy information from original loop to unrolled loop.
343 BasicBlock
*IDomBB
= DT
->getNode(*BB
)->getIDom()->getBlock();
344 DT
->addNewBlock(NewBB
, cast
<BasicBlock
>(VMap
[IDomBB
]));
349 // For the last block, if CreateRemainderLoop is false, create a direct
350 // jump to InsertBot. If not, create a loop back to cloned head.
351 VMap
.erase((*BB
)->getTerminator());
352 BasicBlock
*FirstLoopBB
= cast
<BasicBlock
>(VMap
[Header
]);
353 BranchInst
*LatchBR
= cast
<BranchInst
>(NewBB
->getTerminator());
354 IRBuilder
<> Builder(LatchBR
);
355 if (!CreateRemainderLoop
) {
356 Builder
.CreateBr(InsertBot
);
358 PHINode
*NewIdx
= PHINode::Create(NewIter
->getType(), 2,
360 FirstLoopBB
->getFirstNonPHI());
362 Builder
.CreateSub(NewIdx
, ConstantInt::get(NewIdx
->getType(), 1),
363 NewIdx
->getName() + ".sub");
365 Builder
.CreateIsNotNull(IdxSub
, NewIdx
->getName() + ".cmp");
366 Builder
.CreateCondBr(IdxCmp
, FirstLoopBB
, InsertBot
);
367 NewIdx
->addIncoming(NewIter
, InsertTop
);
368 NewIdx
->addIncoming(IdxSub
, NewBB
);
370 LatchBR
->eraseFromParent();
374 // Change the incoming values to the ones defined in the preheader or
376 for (BasicBlock::iterator I
= Header
->begin(); isa
<PHINode
>(I
); ++I
) {
377 PHINode
*NewPHI
= cast
<PHINode
>(VMap
[&*I
]);
378 if (!CreateRemainderLoop
) {
379 if (UseEpilogRemainder
) {
380 unsigned idx
= NewPHI
->getBasicBlockIndex(Preheader
);
381 NewPHI
->setIncomingBlock(idx
, InsertTop
);
382 NewPHI
->removeIncomingValue(Latch
, false);
384 VMap
[&*I
] = NewPHI
->getIncomingValueForBlock(Preheader
);
385 cast
<BasicBlock
>(VMap
[Header
])->getInstList().erase(NewPHI
);
388 unsigned idx
= NewPHI
->getBasicBlockIndex(Preheader
);
389 NewPHI
->setIncomingBlock(idx
, InsertTop
);
390 BasicBlock
*NewLatch
= cast
<BasicBlock
>(VMap
[Latch
]);
391 idx
= NewPHI
->getBasicBlockIndex(Latch
);
392 Value
*InVal
= NewPHI
->getIncomingValue(idx
);
393 NewPHI
->setIncomingBlock(idx
, NewLatch
);
394 if (Value
*V
= VMap
.lookup(InVal
))
395 NewPHI
->setIncomingValue(idx
, V
);
398 if (CreateRemainderLoop
) {
399 Loop
*NewLoop
= NewLoops
[L
];
400 MDNode
*LoopID
= NewLoop
->getLoopID();
401 assert(NewLoop
&& "L should have been cloned");
403 // Only add loop metadata if the loop is not going to be completely
408 Optional
<MDNode
*> NewLoopID
= makeFollowupLoopID(
409 LoopID
, {LLVMLoopUnrollFollowupAll
, LLVMLoopUnrollFollowupRemainder
});
410 if (NewLoopID
.hasValue()) {
411 NewLoop
->setLoopID(NewLoopID
.getValue());
413 // Do not setLoopAlreadyUnrolled if loop attributes have been defined
418 // Add unroll disable metadata to disable future unrolling for this loop.
419 NewLoop
->setLoopAlreadyUnrolled();
426 /// Returns true if we can safely unroll a multi-exit/exiting loop. OtherExits
427 /// is populated with all the loop exit blocks other than the LatchExit block.
429 canSafelyUnrollMultiExitLoop(Loop
*L
, SmallVectorImpl
<BasicBlock
*> &OtherExits
,
430 BasicBlock
*LatchExit
, bool PreserveLCSSA
,
431 bool UseEpilogRemainder
) {
433 // We currently have some correctness constrains in unrolling a multi-exit
434 // loop. Check for these below.
436 // We rely on LCSSA form being preserved when the exit blocks are transformed.
439 SmallVector
<BasicBlock
*, 4> Exits
;
440 L
->getUniqueExitBlocks(Exits
);
441 for (auto *BB
: Exits
)
443 OtherExits
.push_back(BB
);
445 // TODO: Support multiple exiting blocks jumping to the `LatchExit` when
446 // UnrollRuntimeMultiExit is true. This will need updating the logic in
447 // connectEpilog/connectProlog.
448 if (!LatchExit
->getSinglePredecessor()) {
450 dbgs() << "Bailout for multi-exit handling when latch exit has >1 "
454 // FIXME: We bail out of multi-exit unrolling when epilog loop is generated
455 // and L is an inner loop. This is because in presence of multiple exits, the
456 // outer loop is incorrect: we do not add the EpilogPreheader and exit to the
457 // outer loop. This is automatically handled in the prolog case, so we do not
458 // have that bug in prolog generation.
459 if (UseEpilogRemainder
&& L
->getParentLoop())
462 // All constraints have been satisfied.
466 /// Returns true if we can profitably unroll the multi-exit loop L. Currently,
467 /// we return true only if UnrollRuntimeMultiExit is set to true.
468 static bool canProfitablyUnrollMultiExitLoop(
469 Loop
*L
, SmallVectorImpl
<BasicBlock
*> &OtherExits
, BasicBlock
*LatchExit
,
470 bool PreserveLCSSA
, bool UseEpilogRemainder
) {
473 SmallVector
<BasicBlock
*, 8> OtherExitsDummyCheck
;
474 assert(canSafelyUnrollMultiExitLoop(L
, OtherExitsDummyCheck
, LatchExit
,
475 PreserveLCSSA
, UseEpilogRemainder
) &&
476 "Should be safe to unroll before checking profitability!");
479 // Priority goes to UnrollRuntimeMultiExit if it's supplied.
480 if (UnrollRuntimeMultiExit
.getNumOccurrences())
481 return UnrollRuntimeMultiExit
;
483 // The main pain point with multi-exit loop unrolling is that once unrolled,
484 // we will not be able to merge all blocks into a straight line code.
485 // There are branches within the unrolled loop that go to the OtherExits.
486 // The second point is the increase in code size, but this is true
487 // irrespective of multiple exits.
489 // Note: Both the heuristics below are coarse grained. We are essentially
490 // enabling unrolling of loops that have a single side exit other than the
491 // normal LatchExit (i.e. exiting into a deoptimize block).
492 // The heuristics considered are:
493 // 1. low number of branches in the unrolled version.
494 // 2. high predictability of these extra branches.
495 // We avoid unrolling loops that have more than two exiting blocks. This
496 // limits the total number of branches in the unrolled loop to be atmost
497 // the unroll factor (since one of the exiting blocks is the latch block).
498 SmallVector
<BasicBlock
*, 4> ExitingBlocks
;
499 L
->getExitingBlocks(ExitingBlocks
);
500 if (ExitingBlocks
.size() > 2)
503 // The second heuristic is that L has one exit other than the latchexit and
504 // that exit is a deoptimize block. We know that deoptimize blocks are rarely
505 // taken, which also implies the branch leading to the deoptimize block is
506 // highly predictable.
507 return (OtherExits
.size() == 1 &&
508 OtherExits
[0]->getTerminatingDeoptimizeCall());
509 // TODO: These can be fine-tuned further to consider code size or deopt states
510 // that are captured by the deoptimize exit block.
511 // Also, we can extend this to support more cases, if we actually
512 // know of kinds of multiexit loops that would benefit from unrolling.
515 /// Insert code in the prolog/epilog code when unrolling a loop with a
516 /// run-time trip-count.
518 /// This method assumes that the loop unroll factor is total number
519 /// of loop bodies in the loop after unrolling. (Some folks refer
520 /// to the unroll factor as the number of *extra* copies added).
521 /// We assume also that the loop unroll factor is a power-of-two. So, after
522 /// unrolling the loop, the number of loop bodies executed is 2,
523 /// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch
524 /// instruction in SimplifyCFG.cpp. Then, the backend decides how code for
525 /// the switch instruction is generated.
527 /// ***Prolog case***
528 /// extraiters = tripcount % loopfactor
529 /// if (extraiters == 0) jump Loop:
532 /// extraiters -= 1 // Omitted if unroll factor is 2.
533 /// if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
534 /// if (tripcount < loopfactor) jump End:
539 /// ***Epilog case***
540 /// extraiters = tripcount % loopfactor
541 /// if (tripcount < loopfactor) jump LoopExit:
542 /// unroll_iters = tripcount - extraiters
543 /// Loop: LoopBody; (executes unroll_iter times);
545 /// if (unroll_iter != 0) jump Loop:
547 /// if (extraiters == 0) jump EpilExit:
548 /// Epil: LoopBody; (executes extraiters times)
549 /// extraiters -= 1 // Omitted if unroll factor is 2.
550 /// if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
553 bool llvm::UnrollRuntimeLoopRemainder(Loop
*L
, unsigned Count
,
554 bool AllowExpensiveTripCount
,
555 bool UseEpilogRemainder
,
556 bool UnrollRemainder
, LoopInfo
*LI
,
557 ScalarEvolution
*SE
, DominatorTree
*DT
,
558 AssumptionCache
*AC
, bool PreserveLCSSA
,
560 LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
561 LLVM_DEBUG(L
->dump());
562 LLVM_DEBUG(UseEpilogRemainder
? dbgs() << "Using epilog remainder.\n"
563 : dbgs() << "Using prolog remainder.\n");
565 // Make sure the loop is in canonical form.
566 if (!L
->isLoopSimplifyForm()) {
567 LLVM_DEBUG(dbgs() << "Not in simplify form!\n");
571 // Guaranteed by LoopSimplifyForm.
572 BasicBlock
*Latch
= L
->getLoopLatch();
573 BasicBlock
*Header
= L
->getHeader();
575 BranchInst
*LatchBR
= cast
<BranchInst
>(Latch
->getTerminator());
577 if (!LatchBR
|| LatchBR
->isUnconditional()) {
578 // The loop-rotate pass can be helpful to avoid this in many cases.
581 << "Loop latch not terminated by a conditional branch.\n");
585 unsigned ExitIndex
= LatchBR
->getSuccessor(0) == Header
? 1 : 0;
586 BasicBlock
*LatchExit
= LatchBR
->getSuccessor(ExitIndex
);
588 if (L
->contains(LatchExit
)) {
589 // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
590 // targets of the Latch be an exit block out of the loop.
593 << "One of the loop latch successors must be the exit block.\n");
597 // These are exit blocks other than the target of the latch exiting block.
598 SmallVector
<BasicBlock
*, 4> OtherExits
;
599 bool isMultiExitUnrollingEnabled
=
600 canSafelyUnrollMultiExitLoop(L
, OtherExits
, LatchExit
, PreserveLCSSA
,
601 UseEpilogRemainder
) &&
602 canProfitablyUnrollMultiExitLoop(L
, OtherExits
, LatchExit
, PreserveLCSSA
,
604 // Support only single exit and exiting block unless multi-exit loop unrolling is enabled.
605 if (!isMultiExitUnrollingEnabled
&&
606 (!L
->getExitingBlock() || OtherExits
.size())) {
609 << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
613 // Use Scalar Evolution to compute the trip count. This allows more loops to
614 // be unrolled than relying on induction var simplification.
618 // Only unroll loops with a computable trip count, and the trip count needs
619 // to be an int value (allowing a pointer type is a TODO item).
620 // We calculate the backedge count by using getExitCount on the Latch block,
621 // which is proven to be the only exiting block in this loop. This is same as
622 // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
624 const SCEV
*BECountSC
= SE
->getExitCount(L
, Latch
);
625 if (isa
<SCEVCouldNotCompute
>(BECountSC
) ||
626 !BECountSC
->getType()->isIntegerTy()) {
627 LLVM_DEBUG(dbgs() << "Could not compute exit block SCEV\n");
631 unsigned BEWidth
= cast
<IntegerType
>(BECountSC
->getType())->getBitWidth();
633 // Add 1 since the backedge count doesn't include the first loop iteration.
634 const SCEV
*TripCountSC
=
635 SE
->getAddExpr(BECountSC
, SE
->getConstant(BECountSC
->getType(), 1));
636 if (isa
<SCEVCouldNotCompute
>(TripCountSC
)) {
637 LLVM_DEBUG(dbgs() << "Could not compute trip count SCEV.\n");
641 BasicBlock
*PreHeader
= L
->getLoopPreheader();
642 BranchInst
*PreHeaderBR
= cast
<BranchInst
>(PreHeader
->getTerminator());
643 const DataLayout
&DL
= Header
->getModule()->getDataLayout();
644 SCEVExpander
Expander(*SE
, DL
, "loop-unroll");
645 if (!AllowExpensiveTripCount
&&
646 Expander
.isHighCostExpansion(TripCountSC
, L
, PreHeaderBR
)) {
647 LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
651 // This constraint lets us deal with an overflowing trip count easily; see the
652 // comment on ModVal below.
653 if (Log2_32(Count
) > BEWidth
) {
656 << "Count failed constraint on overflow trip count calculation.\n");
660 // Loop structure is the following:
668 BasicBlock
*NewPreHeader
;
669 BasicBlock
*NewExit
= nullptr;
670 BasicBlock
*PrologExit
= nullptr;
671 BasicBlock
*EpilogPreHeader
= nullptr;
672 BasicBlock
*PrologPreHeader
= nullptr;
674 if (UseEpilogRemainder
) {
675 // If epilog remainder
676 // Split PreHeader to insert a branch around loop for unrolling.
677 NewPreHeader
= SplitBlock(PreHeader
, PreHeader
->getTerminator(), DT
, LI
);
678 NewPreHeader
->setName(PreHeader
->getName() + ".new");
679 // Split LatchExit to create phi nodes from branch above.
680 SmallVector
<BasicBlock
*, 4> Preds(predecessors(LatchExit
));
681 NewExit
= SplitBlockPredecessors(LatchExit
, Preds
, ".unr-lcssa", DT
, LI
,
682 nullptr, PreserveLCSSA
);
683 // NewExit gets its DebugLoc from LatchExit, which is not part of the
685 // Fix this by setting Loop's DebugLoc to NewExit.
686 auto *NewExitTerminator
= NewExit
->getTerminator();
687 NewExitTerminator
->setDebugLoc(Header
->getTerminator()->getDebugLoc());
688 // Split NewExit to insert epilog remainder loop.
689 EpilogPreHeader
= SplitBlock(NewExit
, NewExitTerminator
, DT
, LI
);
690 EpilogPreHeader
->setName(Header
->getName() + ".epil.preheader");
692 // If prolog remainder
693 // Split the original preheader twice to insert prolog remainder loop
694 PrologPreHeader
= SplitEdge(PreHeader
, Header
, DT
, LI
);
695 PrologPreHeader
->setName(Header
->getName() + ".prol.preheader");
696 PrologExit
= SplitBlock(PrologPreHeader
, PrologPreHeader
->getTerminator(),
698 PrologExit
->setName(Header
->getName() + ".prol.loopexit");
699 // Split PrologExit to get NewPreHeader.
700 NewPreHeader
= SplitBlock(PrologExit
, PrologExit
->getTerminator(), DT
, LI
);
701 NewPreHeader
->setName(PreHeader
->getName() + ".new");
703 // Loop structure should be the following:
706 // PreHeader PreHeader
707 // *NewPreHeader *PrologPreHeader
708 // Header *PrologExit
712 // *EpilogPreHeader Latch
713 // LatchExit LatchExit
715 // Calculate conditions for branch around loop for unrolling
716 // in epilog case and around prolog remainder loop in prolog case.
717 // Compute the number of extra iterations required, which is:
718 // extra iterations = run-time trip count % loop unroll factor
719 PreHeaderBR
= cast
<BranchInst
>(PreHeader
->getTerminator());
720 Value
*TripCount
= Expander
.expandCodeFor(TripCountSC
, TripCountSC
->getType(),
722 Value
*BECount
= Expander
.expandCodeFor(BECountSC
, BECountSC
->getType(),
724 IRBuilder
<> B(PreHeaderBR
);
726 // Calculate ModVal = (BECount + 1) % Count.
727 // Note that TripCount is BECount + 1.
728 if (isPowerOf2_32(Count
)) {
729 // When Count is power of 2 we don't BECount for epilog case, however we'll
730 // need it for a branch around unrolling loop for prolog case.
731 ModVal
= B
.CreateAnd(TripCount
, Count
- 1, "xtraiter");
732 // 1. There are no iterations to be run in the prolog/epilog loop.
734 // 2. The addition computing TripCount overflowed.
736 // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
737 // the number of iterations that remain to be run in the original loop is a
738 // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (we
739 // explicitly check this above).
741 // As (BECount + 1) can potentially unsigned overflow we count
742 // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
743 Value
*ModValTmp
= B
.CreateURem(BECount
,
744 ConstantInt::get(BECount
->getType(),
746 Value
*ModValAdd
= B
.CreateAdd(ModValTmp
,
747 ConstantInt::get(ModValTmp
->getType(), 1));
748 // At that point (BECount % Count) + 1 could be equal to Count.
749 // To handle this case we need to take mod by Count one more time.
750 ModVal
= B
.CreateURem(ModValAdd
,
751 ConstantInt::get(BECount
->getType(), Count
),
755 UseEpilogRemainder
? B
.CreateICmpULT(BECount
,
756 ConstantInt::get(BECount
->getType(),
758 B
.CreateIsNotNull(ModVal
, "lcmp.mod");
759 BasicBlock
*RemainderLoop
= UseEpilogRemainder
? NewExit
: PrologPreHeader
;
760 BasicBlock
*UnrollingLoop
= UseEpilogRemainder
? NewPreHeader
: PrologExit
;
761 // Branch to either remainder (extra iterations) loop or unrolling loop.
762 B
.CreateCondBr(BranchVal
, RemainderLoop
, UnrollingLoop
);
763 PreHeaderBR
->eraseFromParent();
765 if (UseEpilogRemainder
)
766 DT
->changeImmediateDominator(NewExit
, PreHeader
);
768 DT
->changeImmediateDominator(PrologExit
, PreHeader
);
770 Function
*F
= Header
->getParent();
771 // Get an ordered list of blocks in the loop to help with the ordering of the
772 // cloned blocks in the prolog/epilog code
773 LoopBlocksDFS
LoopBlocks(L
);
774 LoopBlocks
.perform(LI
);
777 // For each extra loop iteration, create a copy of the loop's basic blocks
778 // and generate a condition that branches to the copy depending on the
779 // number of 'left over' iterations.
781 std::vector
<BasicBlock
*> NewBlocks
;
782 ValueToValueMapTy VMap
;
784 // For unroll factor 2 remainder loop will have 1 iterations.
785 // Do not create 1 iteration loop.
786 bool CreateRemainderLoop
= (Count
!= 2);
788 // Clone all the basic blocks in the loop. If Count is 2, we don't clone
789 // the loop, otherwise we create a cloned loop to execute the extra
790 // iterations. This function adds the appropriate CFG connections.
791 BasicBlock
*InsertBot
= UseEpilogRemainder
? LatchExit
: PrologExit
;
792 BasicBlock
*InsertTop
= UseEpilogRemainder
? EpilogPreHeader
: PrologPreHeader
;
793 Loop
*remainderLoop
= CloneLoopBlocks(
794 L
, ModVal
, CreateRemainderLoop
, UseEpilogRemainder
, UnrollRemainder
,
795 InsertTop
, InsertBot
,
796 NewPreHeader
, NewBlocks
, LoopBlocks
, VMap
, DT
, LI
);
798 // Insert the cloned blocks into the function.
799 F
->getBasicBlockList().splice(InsertBot
->getIterator(),
800 F
->getBasicBlockList(),
801 NewBlocks
[0]->getIterator(),
804 // Now the loop blocks are cloned and the other exiting blocks from the
805 // remainder are connected to the original Loop's exit blocks. The remaining
806 // work is to update the phi nodes in the original loop, and take in the
807 // values from the cloned region.
808 for (auto *BB
: OtherExits
) {
809 for (auto &II
: *BB
) {
811 // Given we preserve LCSSA form, we know that the values used outside the
812 // loop will be used through these phi nodes at the exit blocks that are
813 // transformed below.
814 if (!isa
<PHINode
>(II
))
816 PHINode
*Phi
= cast
<PHINode
>(&II
);
817 unsigned oldNumOperands
= Phi
->getNumIncomingValues();
818 // Add the incoming values from the remainder code to the end of the phi
820 for (unsigned i
=0; i
< oldNumOperands
; i
++){
821 Value
*newVal
= VMap
.lookup(Phi
->getIncomingValue(i
));
822 // newVal can be a constant or derived from values outside the loop, and
823 // hence need not have a VMap value. Also, since lookup already generated
824 // a default "null" VMap entry for this value, we need to populate that
825 // VMap entry correctly, with the mapped entry being itself.
827 newVal
= Phi
->getIncomingValue(i
);
828 VMap
[Phi
->getIncomingValue(i
)] = Phi
->getIncomingValue(i
);
830 Phi
->addIncoming(newVal
,
831 cast
<BasicBlock
>(VMap
[Phi
->getIncomingBlock(i
)]));
834 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
835 for (BasicBlock
*SuccBB
: successors(BB
)) {
836 assert(!(any_of(OtherExits
,
837 [SuccBB
](BasicBlock
*EB
) { return EB
== SuccBB
; }) ||
838 SuccBB
== LatchExit
) &&
839 "Breaks the definition of dedicated exits!");
844 // Update the immediate dominator of the exit blocks and blocks that are
845 // reachable from the exit blocks. This is needed because we now have paths
846 // from both the original loop and the remainder code reaching the exit
847 // blocks. While the IDom of these exit blocks were from the original loop,
848 // now the IDom is the preheader (which decides whether the original loop or
849 // remainder code should run).
850 if (DT
&& !L
->getExitingBlock()) {
851 SmallVector
<BasicBlock
*, 16> ChildrenToUpdate
;
852 // NB! We have to examine the dom children of all loop blocks, not just
853 // those which are the IDom of the exit blocks. This is because blocks
854 // reachable from the exit blocks can have their IDom as the nearest common
855 // dominator of the exit blocks.
856 for (auto *BB
: L
->blocks()) {
857 auto *DomNodeBB
= DT
->getNode(BB
);
858 for (auto *DomChild
: DomNodeBB
->getChildren()) {
859 auto *DomChildBB
= DomChild
->getBlock();
860 if (!L
->contains(LI
->getLoopFor(DomChildBB
)))
861 ChildrenToUpdate
.push_back(DomChildBB
);
864 for (auto *BB
: ChildrenToUpdate
)
865 DT
->changeImmediateDominator(BB
, PreHeader
);
868 // Loop structure should be the following:
871 // PreHeader PreHeader
872 // NewPreHeader PrologPreHeader
873 // Header PrologHeader
876 // NewExit PrologExit
877 // EpilogPreHeader NewPreHeader
878 // EpilogHeader Header
881 // LatchExit LatchExit
883 // Rewrite the cloned instruction operands to use the values created when the
885 for (BasicBlock
*BB
: NewBlocks
) {
886 for (Instruction
&I
: *BB
) {
887 RemapInstruction(&I
, VMap
,
888 RF_NoModuleLevelChanges
| RF_IgnoreMissingLocals
);
892 if (UseEpilogRemainder
) {
893 // Connect the epilog code to the original loop and update the
895 ConnectEpilog(L
, ModVal
, NewExit
, LatchExit
, PreHeader
,
896 EpilogPreHeader
, NewPreHeader
, VMap
, DT
, LI
,
899 // Update counter in loop for unrolling.
900 // I should be multiply of Count.
901 IRBuilder
<> B2(NewPreHeader
->getTerminator());
902 Value
*TestVal
= B2
.CreateSub(TripCount
, ModVal
, "unroll_iter");
903 BranchInst
*LatchBR
= cast
<BranchInst
>(Latch
->getTerminator());
904 B2
.SetInsertPoint(LatchBR
);
905 PHINode
*NewIdx
= PHINode::Create(TestVal
->getType(), 2, "niter",
906 Header
->getFirstNonPHI());
908 B2
.CreateSub(NewIdx
, ConstantInt::get(NewIdx
->getType(), 1),
909 NewIdx
->getName() + ".nsub");
911 if (LatchBR
->getSuccessor(0) == Header
)
912 IdxCmp
= B2
.CreateIsNotNull(IdxSub
, NewIdx
->getName() + ".ncmp");
914 IdxCmp
= B2
.CreateIsNull(IdxSub
, NewIdx
->getName() + ".ncmp");
915 NewIdx
->addIncoming(TestVal
, NewPreHeader
);
916 NewIdx
->addIncoming(IdxSub
, Latch
);
917 LatchBR
->setCondition(IdxCmp
);
919 // Connect the prolog code to the original loop and update the
921 ConnectProlog(L
, BECount
, Count
, PrologExit
, LatchExit
, PreHeader
,
922 NewPreHeader
, VMap
, DT
, LI
, PreserveLCSSA
);
925 // If this loop is nested, then the loop unroller changes the code in the any
926 // of its parent loops, so the Scalar Evolution pass needs to be run again.
927 SE
->forgetTopmostLoop(L
);
929 // Verify that the Dom Tree is correct.
930 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
932 assert(DT
->verify(DominatorTree::VerificationLevel::Full
));
935 // Canonicalize to LoopSimplifyForm both original and remainder loops. We
936 // cannot rely on the LoopUnrollPass to do this because it only does
937 // canonicalization for parent/subloops and not the sibling loops.
938 if (OtherExits
.size() > 0) {
939 // Generate dedicated exit blocks for the original loop, to preserve
941 formDedicatedExitBlocks(L
, DT
, LI
, PreserveLCSSA
);
942 // Generate dedicated exit blocks for the remainder loop if one exists, to
943 // preserve LoopSimplifyForm.
945 formDedicatedExitBlocks(remainderLoop
, DT
, LI
, PreserveLCSSA
);
948 auto UnrollResult
= LoopUnrollResult::Unmodified
;
949 if (remainderLoop
&& UnrollRemainder
) {
950 LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");
952 UnrollLoop(remainderLoop
, /*Count*/ Count
- 1, /*TripCount*/ Count
- 1,
953 /*Force*/ false, /*AllowRuntime*/ false,
954 /*AllowExpensiveTripCount*/ false, /*PreserveCondBr*/ true,
955 /*PreserveOnlyFirst*/ false, /*TripMultiple*/ 1,
956 /*PeelCount*/ 0, /*UnrollRemainder*/ false, LI
, SE
, DT
, AC
,
957 /*ORE*/ nullptr, PreserveLCSSA
);
960 if (ResultLoop
&& UnrollResult
!= LoopUnrollResult::FullyUnrolled
)
961 *ResultLoop
= remainderLoop
;
962 NumRuntimeUnrolled
++;