xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp (revision c1d255d3ffdbe447de3ab875bf4e7d7accc5bfc5)
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/SmallPtrSet.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Analysis/LoopIterator.h"
26 #include "llvm/Analysis/ScalarEvolution.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/MDBuilder.h"
30 #include "llvm/IR/Metadata.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/Support/CommandLine.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/ScalarEvolutionExpander.h"
40 #include "llvm/Transforms/Utils/UnrollLoop.h"
41 #include <algorithm>
42 
43 using namespace llvm;
44 
45 #define DEBUG_TYPE "loop-unroll"
46 
47 STATISTIC(NumRuntimeUnrolled,
48           "Number of loops unrolled with run-time trip counts");
49 static cl::opt<bool> UnrollRuntimeMultiExit(
50     "unroll-runtime-multi-exit", cl::init(false), cl::Hidden,
51     cl::desc("Allow runtime unrolling for loops with multiple exits, when "
52              "epilog is generated"));
53 
54 /// Connect the unrolling prolog code to the original loop.
55 /// The unrolling prolog code contains code to execute the
56 /// 'extra' iterations if the run-time trip count modulo the
57 /// unroll count is non-zero.
58 ///
59 /// This function performs the following:
60 /// - Create PHI nodes at prolog end block to combine values
61 ///   that exit the prolog code and jump around the prolog.
62 /// - Add a PHI operand to a PHI node at the loop exit block
63 ///   for values that exit the prolog and go around the loop.
64 /// - Branch around the original loop if the trip count is less
65 ///   than the unroll factor.
66 ///
67 static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
68                           BasicBlock *PrologExit,
69                           BasicBlock *OriginalLoopLatchExit,
70                           BasicBlock *PreHeader, BasicBlock *NewPreHeader,
71                           ValueToValueMapTy &VMap, DominatorTree *DT,
72                           LoopInfo *LI, bool PreserveLCSSA) {
73   // Loop structure should be the following:
74   // Preheader
75   //  PrologHeader
76   //  ...
77   //  PrologLatch
78   //  PrologExit
79   //   NewPreheader
80   //    Header
81   //    ...
82   //    Latch
83   //      LatchExit
84   BasicBlock *Latch = L->getLoopLatch();
85   assert(Latch && "Loop must have a latch");
86   BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);
87 
88   // Create a PHI node for each outgoing value from the original loop
89   // (which means it is an outgoing value from the prolog code too).
90   // The new PHI node is inserted in the prolog end basic block.
91   // The new PHI node value is added as an operand of a PHI node in either
92   // the loop header or the loop exit block.
93   for (BasicBlock *Succ : successors(Latch)) {
94     for (PHINode &PN : Succ->phis()) {
95       // Add a new PHI node to the prolog end block and add the
96       // appropriate incoming values.
97       // TODO: This code assumes that the PrologExit (or the LatchExit block for
98       // prolog loop) contains only one predecessor from the loop, i.e. the
99       // PrologLatch. When supporting multiple-exiting block loops, we can have
100       // two or more blocks that have the LatchExit as the target in the
101       // original loop.
102       PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
103                                        PrologExit->getFirstNonPHI());
104       // Adding a value to the new PHI node from the original loop preheader.
105       // This is the value that skips all the prolog code.
106       if (L->contains(&PN)) {
107         // Succ is loop header.
108         NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader),
109                            PreHeader);
110       } else {
111         // Succ is LatchExit.
112         NewPN->addIncoming(UndefValue::get(PN.getType()), PreHeader);
113       }
114 
115       Value *V = PN.getIncomingValueForBlock(Latch);
116       if (Instruction *I = dyn_cast<Instruction>(V)) {
117         if (L->contains(I)) {
118           V = VMap.lookup(I);
119         }
120       }
121       // Adding a value to the new PHI node from the last prolog block
122       // that was created.
123       NewPN->addIncoming(V, PrologLatch);
124 
125       // Update the existing PHI node operand with the value from the
126       // new PHI node.  How this is done depends on if the existing
127       // PHI node is in the original loop block, or the exit block.
128       if (L->contains(&PN))
129         PN.setIncomingValueForBlock(NewPreHeader, NewPN);
130       else
131         PN.addIncoming(NewPN, PrologExit);
132     }
133   }
134 
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);
142 
143     SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI,
144                            nullptr, PreserveLCSSA);
145   }
146 
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);
151 
152   assert(Count != 0 && "nonsensical Count!");
153 
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);
169 }
170 
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.
175 ///
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.
182 ///
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]);
191 
192   // Loop structure should be the following:
193   //
194   // PreHeader
195   // NewPreHeader
196   //   Header
197   //   ...
198   //   Latch
199   // NewExit (PN)
200   // EpilogPreHeader
201   //   EpilogHeader
202   //   ...
203   //   EpilogLatch
204   // Exit (EpilogPN)
205 
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]
216     //
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");
222 
223     // Add incoming PreHeader from branch around the Loop
224     PN.addIncoming(UndefValue::get(PN.getType()), PreHeader);
225 
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);
234 
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]
246   }
247 
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);
263 
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->setIncomingValueForBlock(EpilogPreHeader, NewPN);
268     }
269   }
270 
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);
284 
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);
289 }
290 
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;
317 
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);
323 
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);
329 
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);
335     }
336 
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]));
345       }
346     }
347 
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);
369       }
370       LatchBR->eraseFromParent();
371     }
372   }
373 
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);
386       }
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);
396     }
397   }
398   if (CreateRemainderLoop) {
399     Loop *NewLoop = NewLoops[L];
400     assert(NewLoop && "L should have been cloned");
401     MDNode *LoopID = NewLoop->getLoopID();
402 
403     // Only add loop metadata if the loop is not going to be completely
404     // unrolled.
405     if (UnrollRemainder)
406       return NewLoop;
407 
408     Optional<MDNode *> NewLoopID = makeFollowupLoopID(
409         LoopID, {LLVMLoopUnrollFollowupAll, LLVMLoopUnrollFollowupRemainder});
410     if (NewLoopID.hasValue()) {
411       NewLoop->setLoopID(NewLoopID.getValue());
412 
413       // Do not setLoopAlreadyUnrolled if loop attributes have been defined
414       // explicitly.
415       return NewLoop;
416     }
417 
418     // Add unroll disable metadata to disable future unrolling for this loop.
419     NewLoop->setLoopAlreadyUnrolled();
420     return NewLoop;
421   }
422   else
423     return nullptr;
424 }
425 
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 canSafelyUnrollMultiExitLoop(Loop *L, BasicBlock *LatchExit,
429                                          bool PreserveLCSSA,
430                                          bool UseEpilogRemainder) {
431 
432   // We currently have some correctness constrains in unrolling a multi-exit
433   // loop. Check for these below.
434 
435   // We rely on LCSSA form being preserved when the exit blocks are transformed.
436   if (!PreserveLCSSA)
437     return false;
438 
439   // TODO: Support multiple exiting blocks jumping to the `LatchExit` when
440   // UnrollRuntimeMultiExit is true. This will need updating the logic in
441   // connectEpilog/connectProlog.
442   if (!LatchExit->getSinglePredecessor()) {
443     LLVM_DEBUG(
444         dbgs() << "Bailout for multi-exit handling when latch exit has >1 "
445                   "predecessor.\n");
446     return false;
447   }
448   // FIXME: We bail out of multi-exit unrolling when epilog loop is generated
449   // and L is an inner loop. This is because in presence of multiple exits, the
450   // outer loop is incorrect: we do not add the EpilogPreheader and exit to the
451   // outer loop. This is automatically handled in the prolog case, so we do not
452   // have that bug in prolog generation.
453   if (UseEpilogRemainder && L->getParentLoop())
454     return false;
455 
456   // All constraints have been satisfied.
457   return true;
458 }
459 
460 /// Returns true if we can profitably unroll the multi-exit loop L. Currently,
461 /// we return true only if UnrollRuntimeMultiExit is set to true.
462 static bool canProfitablyUnrollMultiExitLoop(
463     Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,
464     bool PreserveLCSSA, bool UseEpilogRemainder) {
465 
466 #if !defined(NDEBUG)
467   assert(canSafelyUnrollMultiExitLoop(L, LatchExit, PreserveLCSSA,
468                                       UseEpilogRemainder) &&
469          "Should be safe to unroll before checking profitability!");
470 #endif
471 
472   // Priority goes to UnrollRuntimeMultiExit if it's supplied.
473   if (UnrollRuntimeMultiExit.getNumOccurrences())
474     return UnrollRuntimeMultiExit;
475 
476   // The main pain point with multi-exit loop unrolling is that once unrolled,
477   // we will not be able to merge all blocks into a straight line code.
478   // There are branches within the unrolled loop that go to the OtherExits.
479   // The second point is the increase in code size, but this is true
480   // irrespective of multiple exits.
481 
482   // Note: Both the heuristics below are coarse grained. We are essentially
483   // enabling unrolling of loops that have a single side exit other than the
484   // normal LatchExit (i.e. exiting into a deoptimize block).
485   // The heuristics considered are:
486   // 1. low number of branches in the unrolled version.
487   // 2. high predictability of these extra branches.
488   // We avoid unrolling loops that have more than two exiting blocks. This
489   // limits the total number of branches in the unrolled loop to be atmost
490   // the unroll factor (since one of the exiting blocks is the latch block).
491   SmallVector<BasicBlock*, 4> ExitingBlocks;
492   L->getExitingBlocks(ExitingBlocks);
493   if (ExitingBlocks.size() > 2)
494     return false;
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.
500   return (OtherExits.size() == 1 &&
501           OtherExits[0]->getTerminatingDeoptimizeCall());
502   // TODO: These can be fine-tuned further to consider code size or deopt states
503   // that are captured by the deoptimize exit block.
504   // Also, we can extend this to support more cases, if we actually
505   // know of kinds of multiexit loops that would benefit from unrolling.
506 }
507 
508 // Assign the maximum possible trip count as the back edge weight for the
509 // remainder loop if the original loop comes with a branch weight.
510 static void updateLatchBranchWeightsForRemainderLoop(Loop *OrigLoop,
511                                                      Loop *RemainderLoop,
512                                                      uint64_t UnrollFactor) {
513   uint64_t TrueWeight, FalseWeight;
514   BranchInst *LatchBR =
515       cast<BranchInst>(OrigLoop->getLoopLatch()->getTerminator());
516   if (LatchBR->extractProfMetadata(TrueWeight, FalseWeight)) {
517     uint64_t ExitWeight = LatchBR->getSuccessor(0) == OrigLoop->getHeader()
518                               ? FalseWeight
519                               : TrueWeight;
520     assert(UnrollFactor > 1);
521     uint64_t BackEdgeWeight = (UnrollFactor - 1) * ExitWeight;
522     BasicBlock *Header = RemainderLoop->getHeader();
523     BasicBlock *Latch = RemainderLoop->getLoopLatch();
524     auto *RemainderLatchBR = cast<BranchInst>(Latch->getTerminator());
525     unsigned HeaderIdx = (RemainderLatchBR->getSuccessor(0) == Header ? 0 : 1);
526     MDBuilder MDB(RemainderLatchBR->getContext());
527     MDNode *WeightNode =
528         HeaderIdx ? MDB.createBranchWeights(ExitWeight, BackEdgeWeight)
529                   : MDB.createBranchWeights(BackEdgeWeight, ExitWeight);
530     RemainderLatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
531   }
532 }
533 
534 /// Insert code in the prolog/epilog code when unrolling a loop with a
535 /// run-time trip-count.
536 ///
537 /// This method assumes that the loop unroll factor is total number
538 /// of loop bodies in the loop after unrolling. (Some folks refer
539 /// to the unroll factor as the number of *extra* copies added).
540 /// We assume also that the loop unroll factor is a power-of-two. So, after
541 /// unrolling the loop, the number of loop bodies executed is 2,
542 /// 4, 8, etc.  Note - LLVM converts the if-then-sequence to a switch
543 /// instruction in SimplifyCFG.cpp.  Then, the backend decides how code for
544 /// the switch instruction is generated.
545 ///
546 /// ***Prolog case***
547 ///        extraiters = tripcount % loopfactor
548 ///        if (extraiters == 0) jump Loop:
549 ///        else jump Prol:
550 /// Prol:  LoopBody;
551 ///        extraiters -= 1                 // Omitted if unroll factor is 2.
552 ///        if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
553 ///        if (tripcount < loopfactor) jump End:
554 /// Loop:
555 /// ...
556 /// End:
557 ///
558 /// ***Epilog case***
559 ///        extraiters = tripcount % loopfactor
560 ///        if (tripcount < loopfactor) jump LoopExit:
561 ///        unroll_iters = tripcount - extraiters
562 /// Loop:  LoopBody; (executes unroll_iter times);
563 ///        unroll_iter -= 1
564 ///        if (unroll_iter != 0) jump Loop:
565 /// LoopExit:
566 ///        if (extraiters == 0) jump EpilExit:
567 /// Epil:  LoopBody; (executes extraiters times)
568 ///        extraiters -= 1                 // Omitted if unroll factor is 2.
569 ///        if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
570 /// EpilExit:
571 
572 bool llvm::UnrollRuntimeLoopRemainder(
573     Loop *L, unsigned Count, bool AllowExpensiveTripCount,
574     bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,
575     LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,
576     const TargetTransformInfo *TTI, bool PreserveLCSSA, Loop **ResultLoop) {
577   LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
578   LLVM_DEBUG(L->dump());
579   LLVM_DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"
580                                 : dbgs() << "Using prolog remainder.\n");
581 
582   // Make sure the loop is in canonical form.
583   if (!L->isLoopSimplifyForm()) {
584     LLVM_DEBUG(dbgs() << "Not in simplify form!\n");
585     return false;
586   }
587 
588   // Guaranteed by LoopSimplifyForm.
589   BasicBlock *Latch = L->getLoopLatch();
590   BasicBlock *Header = L->getHeader();
591 
592   BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
593 
594   if (!LatchBR || LatchBR->isUnconditional()) {
595     // The loop-rotate pass can be helpful to avoid this in many cases.
596     LLVM_DEBUG(
597         dbgs()
598         << "Loop latch not terminated by a conditional branch.\n");
599     return false;
600   }
601 
602   unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 1 : 0;
603   BasicBlock *LatchExit = LatchBR->getSuccessor(ExitIndex);
604 
605   if (L->contains(LatchExit)) {
606     // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
607     // targets of the Latch be an exit block out of the loop.
608     LLVM_DEBUG(
609         dbgs()
610         << "One of the loop latch successors must be the exit block.\n");
611     return false;
612   }
613 
614   // These are exit blocks other than the target of the latch exiting block.
615   SmallVector<BasicBlock *, 4> OtherExits;
616   L->getUniqueNonLatchExitBlocks(OtherExits);
617   bool isMultiExitUnrollingEnabled =
618       canSafelyUnrollMultiExitLoop(L, LatchExit, PreserveLCSSA,
619                                    UseEpilogRemainder) &&
620       canProfitablyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
621                                        UseEpilogRemainder);
622   // Support only single exit and exiting block unless multi-exit loop unrolling is enabled.
623   if (!isMultiExitUnrollingEnabled &&
624       (!L->getExitingBlock() || OtherExits.size())) {
625     LLVM_DEBUG(
626         dbgs()
627         << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
628            "enabled!\n");
629     return false;
630   }
631   // Use Scalar Evolution to compute the trip count. This allows more loops to
632   // be unrolled than relying on induction var simplification.
633   if (!SE)
634     return false;
635 
636   // Only unroll loops with a computable trip count, and the trip count needs
637   // to be an int value (allowing a pointer type is a TODO item).
638   // We calculate the backedge count by using getExitCount on the Latch block,
639   // which is proven to be the only exiting block in this loop. This is same as
640   // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
641   // exiting blocks).
642   const SCEV *BECountSC = SE->getExitCount(L, Latch);
643   if (isa<SCEVCouldNotCompute>(BECountSC) ||
644       !BECountSC->getType()->isIntegerTy()) {
645     LLVM_DEBUG(dbgs() << "Could not compute exit block SCEV\n");
646     return false;
647   }
648 
649   unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
650 
651   // Add 1 since the backedge count doesn't include the first loop iteration.
652   const SCEV *TripCountSC =
653       SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
654   if (isa<SCEVCouldNotCompute>(TripCountSC)) {
655     LLVM_DEBUG(dbgs() << "Could not compute trip count SCEV.\n");
656     return false;
657   }
658 
659   BasicBlock *PreHeader = L->getLoopPreheader();
660   BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
661   const DataLayout &DL = Header->getModule()->getDataLayout();
662   SCEVExpander Expander(*SE, DL, "loop-unroll");
663   if (!AllowExpensiveTripCount &&
664       Expander.isHighCostExpansion(TripCountSC, L, SCEVCheapExpansionBudget,
665                                    TTI, PreHeaderBR)) {
666     LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
667     return false;
668   }
669 
670   // This constraint lets us deal with an overflowing trip count easily; see the
671   // comment on ModVal below.
672   if (Log2_32(Count) > BEWidth) {
673     LLVM_DEBUG(
674         dbgs()
675         << "Count failed constraint on overflow trip count calculation.\n");
676     return false;
677   }
678 
679   // Loop structure is the following:
680   //
681   // PreHeader
682   //   Header
683   //   ...
684   //   Latch
685   // LatchExit
686 
687   BasicBlock *NewPreHeader;
688   BasicBlock *NewExit = nullptr;
689   BasicBlock *PrologExit = nullptr;
690   BasicBlock *EpilogPreHeader = nullptr;
691   BasicBlock *PrologPreHeader = nullptr;
692 
693   if (UseEpilogRemainder) {
694     // If epilog remainder
695     // Split PreHeader to insert a branch around loop for unrolling.
696     NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
697     NewPreHeader->setName(PreHeader->getName() + ".new");
698     // Split LatchExit to create phi nodes from branch above.
699     SmallVector<BasicBlock*, 4> Preds(predecessors(LatchExit));
700     NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa", DT, LI,
701                                      nullptr, PreserveLCSSA);
702     // NewExit gets its DebugLoc from LatchExit, which is not part of the
703     // original Loop.
704     // Fix this by setting Loop's DebugLoc to NewExit.
705     auto *NewExitTerminator = NewExit->getTerminator();
706     NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());
707     // Split NewExit to insert epilog remainder loop.
708     EpilogPreHeader = SplitBlock(NewExit, NewExitTerminator, DT, LI);
709     EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
710   } else {
711     // If prolog remainder
712     // Split the original preheader twice to insert prolog remainder loop
713     PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
714     PrologPreHeader->setName(Header->getName() + ".prol.preheader");
715     PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
716                             DT, LI);
717     PrologExit->setName(Header->getName() + ".prol.loopexit");
718     // Split PrologExit to get NewPreHeader.
719     NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
720     NewPreHeader->setName(PreHeader->getName() + ".new");
721   }
722   // Loop structure should be the following:
723   //  Epilog             Prolog
724   //
725   // PreHeader         PreHeader
726   // *NewPreHeader     *PrologPreHeader
727   //   Header          *PrologExit
728   //   ...             *NewPreHeader
729   //   Latch             Header
730   // *NewExit            ...
731   // *EpilogPreHeader    Latch
732   // LatchExit              LatchExit
733 
734   // Calculate conditions for branch around loop for unrolling
735   // in epilog case and around prolog remainder loop in prolog case.
736   // Compute the number of extra iterations required, which is:
737   //  extra iterations = run-time trip count % loop unroll factor
738   PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
739   Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
740                                             PreHeaderBR);
741   Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
742                                           PreHeaderBR);
743   IRBuilder<> B(PreHeaderBR);
744   Value *ModVal;
745   // Calculate ModVal = (BECount + 1) % Count.
746   // Note that TripCount is BECount + 1.
747   if (isPowerOf2_32(Count)) {
748     // When Count is power of 2 we don't BECount for epilog case, however we'll
749     // need it for a branch around unrolling loop for prolog case.
750     ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");
751     //  1. There are no iterations to be run in the prolog/epilog loop.
752     // OR
753     //  2. The addition computing TripCount overflowed.
754     //
755     // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
756     // the number of iterations that remain to be run in the original loop is a
757     // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (we
758     // explicitly check this above).
759   } else {
760     // As (BECount + 1) can potentially unsigned overflow we count
761     // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
762     Value *ModValTmp = B.CreateURem(BECount,
763                                     ConstantInt::get(BECount->getType(),
764                                                      Count));
765     Value *ModValAdd = B.CreateAdd(ModValTmp,
766                                    ConstantInt::get(ModValTmp->getType(), 1));
767     // At that point (BECount % Count) + 1 could be equal to Count.
768     // To handle this case we need to take mod by Count one more time.
769     ModVal = B.CreateURem(ModValAdd,
770                           ConstantInt::get(BECount->getType(), Count),
771                           "xtraiter");
772   }
773   Value *BranchVal =
774       UseEpilogRemainder ? B.CreateICmpULT(BECount,
775                                            ConstantInt::get(BECount->getType(),
776                                                             Count - 1)) :
777                            B.CreateIsNotNull(ModVal, "lcmp.mod");
778   BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
779   BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
780   // Branch to either remainder (extra iterations) loop or unrolling loop.
781   B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
782   PreHeaderBR->eraseFromParent();
783   if (DT) {
784     if (UseEpilogRemainder)
785       DT->changeImmediateDominator(NewExit, PreHeader);
786     else
787       DT->changeImmediateDominator(PrologExit, PreHeader);
788   }
789   Function *F = Header->getParent();
790   // Get an ordered list of blocks in the loop to help with the ordering of the
791   // cloned blocks in the prolog/epilog code
792   LoopBlocksDFS LoopBlocks(L);
793   LoopBlocks.perform(LI);
794 
795   //
796   // For each extra loop iteration, create a copy of the loop's basic blocks
797   // and generate a condition that branches to the copy depending on the
798   // number of 'left over' iterations.
799   //
800   std::vector<BasicBlock *> NewBlocks;
801   ValueToValueMapTy VMap;
802 
803   // For unroll factor 2 remainder loop will have 1 iterations.
804   // Do not create 1 iteration loop.
805   bool CreateRemainderLoop = (Count != 2);
806 
807   // Clone all the basic blocks in the loop. If Count is 2, we don't clone
808   // the loop, otherwise we create a cloned loop to execute the extra
809   // iterations. This function adds the appropriate CFG connections.
810   BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;
811   BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
812   Loop *remainderLoop = CloneLoopBlocks(
813       L, ModVal, CreateRemainderLoop, UseEpilogRemainder, UnrollRemainder,
814       InsertTop, InsertBot,
815       NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
816 
817   // Assign the maximum possible trip count as the back edge weight for the
818   // remainder loop if the original loop comes with a branch weight.
819   if (remainderLoop && !UnrollRemainder)
820     updateLatchBranchWeightsForRemainderLoop(L, remainderLoop, Count);
821 
822   // Insert the cloned blocks into the function.
823   F->getBasicBlockList().splice(InsertBot->getIterator(),
824                                 F->getBasicBlockList(),
825                                 NewBlocks[0]->getIterator(),
826                                 F->end());
827 
828   // Now the loop blocks are cloned and the other exiting blocks from the
829   // remainder are connected to the original Loop's exit blocks. The remaining
830   // work is to update the phi nodes in the original loop, and take in the
831   // values from the cloned region.
832   for (auto *BB : OtherExits) {
833    for (auto &II : *BB) {
834 
835      // Given we preserve LCSSA form, we know that the values used outside the
836      // loop will be used through these phi nodes at the exit blocks that are
837      // transformed below.
838      if (!isa<PHINode>(II))
839        break;
840      PHINode *Phi = cast<PHINode>(&II);
841      unsigned oldNumOperands = Phi->getNumIncomingValues();
842      // Add the incoming values from the remainder code to the end of the phi
843      // node.
844      for (unsigned i =0; i < oldNumOperands; i++){
845        Value *newVal = VMap.lookup(Phi->getIncomingValue(i));
846        // newVal can be a constant or derived from values outside the loop, and
847        // hence need not have a VMap value. Also, since lookup already generated
848        // a default "null" VMap entry for this value, we need to populate that
849        // VMap entry correctly, with the mapped entry being itself.
850        if (!newVal) {
851          newVal = Phi->getIncomingValue(i);
852          VMap[Phi->getIncomingValue(i)] = Phi->getIncomingValue(i);
853        }
854        Phi->addIncoming(newVal,
855                            cast<BasicBlock>(VMap[Phi->getIncomingBlock(i)]));
856      }
857    }
858 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
859     for (BasicBlock *SuccBB : successors(BB)) {
860       assert(!(any_of(OtherExits,
861                       [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) ||
862                SuccBB == LatchExit) &&
863              "Breaks the definition of dedicated exits!");
864     }
865 #endif
866   }
867 
868   // Update the immediate dominator of the exit blocks and blocks that are
869   // reachable from the exit blocks. This is needed because we now have paths
870   // from both the original loop and the remainder code reaching the exit
871   // blocks. While the IDom of these exit blocks were from the original loop,
872   // now the IDom is the preheader (which decides whether the original loop or
873   // remainder code should run).
874   if (DT && !L->getExitingBlock()) {
875     SmallVector<BasicBlock *, 16> ChildrenToUpdate;
876     // NB! We have to examine the dom children of all loop blocks, not just
877     // those which are the IDom of the exit blocks. This is because blocks
878     // reachable from the exit blocks can have their IDom as the nearest common
879     // dominator of the exit blocks.
880     for (auto *BB : L->blocks()) {
881       auto *DomNodeBB = DT->getNode(BB);
882       for (auto *DomChild : DomNodeBB->children()) {
883         auto *DomChildBB = DomChild->getBlock();
884         if (!L->contains(LI->getLoopFor(DomChildBB)))
885           ChildrenToUpdate.push_back(DomChildBB);
886       }
887     }
888     for (auto *BB : ChildrenToUpdate)
889       DT->changeImmediateDominator(BB, PreHeader);
890   }
891 
892   // Loop structure should be the following:
893   //  Epilog             Prolog
894   //
895   // PreHeader         PreHeader
896   // NewPreHeader      PrologPreHeader
897   //   Header            PrologHeader
898   //   ...               ...
899   //   Latch             PrologLatch
900   // NewExit           PrologExit
901   // EpilogPreHeader   NewPreHeader
902   //   EpilogHeader      Header
903   //   ...               ...
904   //   EpilogLatch       Latch
905   // LatchExit              LatchExit
906 
907   // Rewrite the cloned instruction operands to use the values created when the
908   // clone is created.
909   for (BasicBlock *BB : NewBlocks) {
910     for (Instruction &I : *BB) {
911       RemapInstruction(&I, VMap,
912                        RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
913     }
914   }
915 
916   if (UseEpilogRemainder) {
917     // Connect the epilog code to the original loop and update the
918     // PHI functions.
919     ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader,
920                   EpilogPreHeader, NewPreHeader, VMap, DT, LI,
921                   PreserveLCSSA);
922 
923     // Update counter in loop for unrolling.
924     // I should be multiply of Count.
925     IRBuilder<> B2(NewPreHeader->getTerminator());
926     Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
927     BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
928     B2.SetInsertPoint(LatchBR);
929     PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
930                                       Header->getFirstNonPHI());
931     Value *IdxSub =
932         B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
933                      NewIdx->getName() + ".nsub");
934     Value *IdxCmp;
935     if (LatchBR->getSuccessor(0) == Header)
936       IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
937     else
938       IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
939     NewIdx->addIncoming(TestVal, NewPreHeader);
940     NewIdx->addIncoming(IdxSub, Latch);
941     LatchBR->setCondition(IdxCmp);
942   } else {
943     // Connect the prolog code to the original loop and update the
944     // PHI functions.
945     ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,
946                   NewPreHeader, VMap, DT, LI, PreserveLCSSA);
947   }
948 
949   // If this loop is nested, then the loop unroller changes the code in the any
950   // of its parent loops, so the Scalar Evolution pass needs to be run again.
951   SE->forgetTopmostLoop(L);
952 
953   // Verify that the Dom Tree is correct.
954 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
955   if (DT)
956     assert(DT->verify(DominatorTree::VerificationLevel::Full));
957 #endif
958 
959   // Canonicalize to LoopSimplifyForm both original and remainder loops. We
960   // cannot rely on the LoopUnrollPass to do this because it only does
961   // canonicalization for parent/subloops and not the sibling loops.
962   if (OtherExits.size() > 0) {
963     // Generate dedicated exit blocks for the original loop, to preserve
964     // LoopSimplifyForm.
965     formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA);
966     // Generate dedicated exit blocks for the remainder loop if one exists, to
967     // preserve LoopSimplifyForm.
968     if (remainderLoop)
969       formDedicatedExitBlocks(remainderLoop, DT, LI, nullptr, PreserveLCSSA);
970   }
971 
972   auto UnrollResult = LoopUnrollResult::Unmodified;
973   if (remainderLoop && UnrollRemainder) {
974     LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");
975     UnrollResult =
976         UnrollLoop(remainderLoop,
977                    {/*Count*/ Count - 1, /*TripCount*/ Count - 1,
978                     /*Force*/ false, /*AllowRuntime*/ false,
979                     /*AllowExpensiveTripCount*/ false, /*PreserveCondBr*/ true,
980                     /*PreserveOnlyFirst*/ false, /*TripMultiple*/ 1,
981                     /*PeelCount*/ 0, /*UnrollRemainder*/ false, ForgetAllSCEV},
982                    LI, SE, DT, AC, TTI, /*ORE*/ nullptr, PreserveLCSSA);
983   }
984 
985   if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)
986     *ResultLoop = remainderLoop;
987   NumRuntimeUnrolled++;
988   return true;
989 }
990