Revert r354244 "[DAGCombiner] Eliminate dead stores to stack."
[llvm-complete.git] / lib / Transforms / Utils / LoopUnrollRuntime.cpp
bloba9d41945b27c1c4a2db6caa4033cfc2955ea18de
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.
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
19 // unrolled loop.
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"
40 #include <algorithm>
42 using namespace llvm;
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.
57 ///
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.
65 ///
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:
73 // Preheader
74 // PrologHeader
75 // ...
76 // PrologLatch
77 // PrologExit
78 // NewPreheader
79 // Header
80 // ...
81 // Latch
82 // LatchExit
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
100 // original loop.
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),
108 PreHeader);
109 } else {
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)) {
117 V = VMap.lookup(I);
120 // Adding a value to the new PHI node from the last prolog block
121 // that was created.
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);
129 } else {
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);
138 if (PrologLoop) {
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.
158 Value *BrLoopExit =
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();
167 if (DT)
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:
194 // PreHeader
195 // NewPreHeader
196 // Header
197 // ...
198 // Latch
199 // NewExit (PN)
200 // EpilogPreHeader
201 // EpilogHeader
202 // ...
203 // EpilogLatch
204 // Exit (EpilogPN)
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:
211 // NewExit:
212 // PN = PHI [I, Latch]
213 // ...
214 // Exit:
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.
230 V = VMap.lookup(I);
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),
239 NewExit);
240 // Now PHIs should look like:
241 // NewExit:
242 // PN = PHI [I, Latch], [undef, PreHeader]
243 // ...
244 // Exit:
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))
253 continue;
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,
278 PreserveLCSSA);
279 // Add the branch to the exit block (around the unrolling loop)
280 B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
281 InsertPt->eraseFromParent();
282 if (DT)
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,
288 PreserveLCSSA);
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
297 /// new loop exit.
298 /// Return the new cloned loop that is created when CreateRemainderLoop is true.
299 static Loop *
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);
330 VMap[*BB] = NewBB;
331 if (Header == *BB) {
332 // For the first block, add a CFG connection to this newly
333 // created block.
334 InsertTop->getTerminator()->setSuccessor(0, NewBB);
337 if (DT) {
338 if (Header == *BB) {
339 // The header is dominated by the preheader.
340 DT->addNewBlock(NewBB, InsertTop);
341 } else {
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]));
348 if (Latch == *BB) {
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);
357 } else {
358 PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2,
359 suffix + ".iter",
360 FirstLoopBB->getFirstNonPHI());
361 Value *IdxSub =
362 Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
363 NewIdx->getName() + ".sub");
364 Value *IdxCmp =
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
375 // cloned loop.
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);
383 } else {
384 VMap[&*I] = NewPHI->getIncomingValueForBlock(Preheader);
385 cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
387 } else {
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
404 // unrolled.
405 if (UnrollRemainder)
406 return NewLoop;
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
414 // explicitly.
415 return NewLoop;
418 // Add unroll disable metadata to disable future unrolling for this loop.
419 NewLoop->setLoopAlreadyUnrolled();
420 return NewLoop;
422 else
423 return nullptr;
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.
428 static bool
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.
437 if (!PreserveLCSSA)
438 return false;
439 SmallVector<BasicBlock *, 4> Exits;
440 L->getUniqueExitBlocks(Exits);
441 for (auto *BB : Exits)
442 if (BB != LatchExit)
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()) {
449 LLVM_DEBUG(
450 dbgs() << "Bailout for multi-exit handling when latch exit has >1 "
451 "predecessor.\n");
452 return false;
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())
460 return false;
462 // All constraints have been satisfied.
463 return true;
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) {
472 #if !defined(NDEBUG)
473 SmallVector<BasicBlock *, 8> OtherExitsDummyCheck;
474 assert(canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck, LatchExit,
475 PreserveLCSSA, UseEpilogRemainder) &&
476 "Should be safe to unroll before checking profitability!");
477 #endif
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)
501 return false;
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:
530 /// else jump Prol:
531 /// Prol: LoopBody;
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:
535 /// Loop:
536 /// ...
537 /// 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);
544 /// unroll_iter -= 1
545 /// if (unroll_iter != 0) jump Loop:
546 /// LoopExit:
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.
551 /// EpilExit:
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,
559 Loop **ResultLoop) {
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");
568 return false;
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.
579 LLVM_DEBUG(
580 dbgs()
581 << "Loop latch not terminated by a conditional branch.\n");
582 return false;
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.
591 LLVM_DEBUG(
592 dbgs()
593 << "One of the loop latch successors must be the exit block.\n");
594 return false;
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,
603 UseEpilogRemainder);
604 // Support only single exit and exiting block unless multi-exit loop unrolling is enabled.
605 if (!isMultiExitUnrollingEnabled &&
606 (!L->getExitingBlock() || OtherExits.size())) {
607 LLVM_DEBUG(
608 dbgs()
609 << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
610 "enabled!\n");
611 return false;
613 // Use Scalar Evolution to compute the trip count. This allows more loops to
614 // be unrolled than relying on induction var simplification.
615 if (!SE)
616 return false;
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
623 // exiting blocks).
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");
628 return false;
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");
638 return false;
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");
648 return false;
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) {
654 LLVM_DEBUG(
655 dbgs()
656 << "Count failed constraint on overflow trip count calculation.\n");
657 return false;
660 // Loop structure is the following:
662 // PreHeader
663 // Header
664 // ...
665 // Latch
666 // LatchExit
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
684 // original Loop.
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");
691 } else {
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(),
697 DT, LI);
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:
704 // Epilog Prolog
706 // PreHeader PreHeader
707 // *NewPreHeader *PrologPreHeader
708 // Header *PrologExit
709 // ... *NewPreHeader
710 // Latch Header
711 // *NewExit ...
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(),
721 PreHeaderBR);
722 Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
723 PreHeaderBR);
724 IRBuilder<> B(PreHeaderBR);
725 Value *ModVal;
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.
733 // OR
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).
740 } else {
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(),
745 Count));
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),
752 "xtraiter");
754 Value *BranchVal =
755 UseEpilogRemainder ? B.CreateICmpULT(BECount,
756 ConstantInt::get(BECount->getType(),
757 Count - 1)) :
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();
764 if (DT) {
765 if (UseEpilogRemainder)
766 DT->changeImmediateDominator(NewExit, PreHeader);
767 else
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(),
802 F->end());
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))
815 break;
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
819 // node.
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.
826 if (!newVal) {
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!");
841 #endif
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:
869 // Epilog Prolog
871 // PreHeader PreHeader
872 // NewPreHeader PrologPreHeader
873 // Header PrologHeader
874 // ... ...
875 // Latch PrologLatch
876 // NewExit PrologExit
877 // EpilogPreHeader NewPreHeader
878 // EpilogHeader Header
879 // ... ...
880 // EpilogLatch Latch
881 // LatchExit LatchExit
883 // Rewrite the cloned instruction operands to use the values created when the
884 // clone is created.
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
894 // PHI functions.
895 ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader,
896 EpilogPreHeader, NewPreHeader, VMap, DT, LI,
897 PreserveLCSSA);
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());
907 Value *IdxSub =
908 B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
909 NewIdx->getName() + ".nsub");
910 Value *IdxCmp;
911 if (LatchBR->getSuccessor(0) == Header)
912 IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
913 else
914 IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
915 NewIdx->addIncoming(TestVal, NewPreHeader);
916 NewIdx->addIncoming(IdxSub, Latch);
917 LatchBR->setCondition(IdxCmp);
918 } else {
919 // Connect the prolog code to the original loop and update the
920 // PHI functions.
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)
931 if (DT)
932 assert(DT->verify(DominatorTree::VerificationLevel::Full));
933 #endif
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
940 // LoopSimplifyForm.
941 formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA);
942 // Generate dedicated exit blocks for the remainder loop if one exists, to
943 // preserve LoopSimplifyForm.
944 if (remainderLoop)
945 formDedicatedExitBlocks(remainderLoop, DT, LI, PreserveLCSSA);
948 auto UnrollResult = LoopUnrollResult::Unmodified;
949 if (remainderLoop && UnrollRemainder) {
950 LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");
951 UnrollResult =
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++;
963 return true;