LLVM  8.0.0svn
LoopUnrollRuntime.cpp
Go to the documentation of this file.
1 //===-- UnrollLoopRuntime.cpp - Runtime Loop unrolling utilities ----------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements some loop unrolling utilities for loops with run-time
11 // trip counts. See LoopUnroll.cpp for unrolling loops with compile-time
12 // trip counts.
13 //
14 // The functions in this file are used to generate extra code when the
15 // run-time trip count modulo the unroll factor is not 0. When this is the
16 // case, we need to generate code to execute these 'left over' iterations.
17 //
18 // The current strategy generates an if-then-else sequence prior to the
19 // unrolled loop to execute the 'left over' iterations before or after the
20 // unrolled loop.
21 //
22 //===----------------------------------------------------------------------===//
23 
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/ADT/Statistic.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/Metadata.h"
33 #include "llvm/IR/Module.h"
34 #include "llvm/Support/Debug.h"
36 #include "llvm/Transforms/Utils.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");
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,
72  LoopInfo *LI, bool PreserveLCSSA) {
73  BasicBlock *Latch = L->getLoopLatch();
74  assert(Latch && "Loop must have a latch");
75  BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);
76 
77  // Create a PHI node for each outgoing value from the original loop
78  // (which means it is an outgoing value from the prolog code too).
79  // The new PHI node is inserted in the prolog end basic block.
80  // The new PHI node value is added as an operand of a PHI node in either
81  // the loop header or the loop exit block.
82  for (BasicBlock *Succ : successors(Latch)) {
83  for (PHINode &PN : Succ->phis()) {
84  // Add a new PHI node to the prolog end block and add the
85  // appropriate incoming values.
86  PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
87  PrologExit->getFirstNonPHI());
88  // Adding a value to the new PHI node from the original loop preheader.
89  // This is the value that skips all the prolog code.
90  if (L->contains(&PN)) {
91  NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader),
92  PreHeader);
93  } else {
94  NewPN->addIncoming(UndefValue::get(PN.getType()), PreHeader);
95  }
96 
97  Value *V = PN.getIncomingValueForBlock(Latch);
98  if (Instruction *I = dyn_cast<Instruction>(V)) {
99  if (L->contains(I)) {
100  V = VMap.lookup(I);
101  }
102  }
103  // Adding a value to the new PHI node from the last prolog block
104  // that was created.
105  NewPN->addIncoming(V, PrologLatch);
106 
107  // Update the existing PHI node operand with the value from the
108  // new PHI node. How this is done depends on if the existing
109  // PHI node is in the original loop block, or the exit block.
110  if (L->contains(&PN)) {
111  PN.setIncomingValue(PN.getBasicBlockIndex(NewPreHeader), NewPN);
112  } else {
113  PN.addIncoming(NewPN, PrologExit);
114  }
115  }
116  }
117 
118  // Make sure that created prolog loop is in simplified form
119  SmallVector<BasicBlock *, 4> PrologExitPreds;
120  Loop *PrologLoop = LI->getLoopFor(PrologLatch);
121  if (PrologLoop) {
122  for (BasicBlock *PredBB : predecessors(PrologExit))
123  if (PrologLoop->contains(PredBB))
124  PrologExitPreds.push_back(PredBB);
125 
126  SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI,
127  nullptr, PreserveLCSSA);
128  }
129 
130  // Create a branch around the original loop, which is taken if there are no
131  // iterations remaining to be executed after running the prologue.
132  Instruction *InsertPt = PrologExit->getTerminator();
133  IRBuilder<> B(InsertPt);
134 
135  assert(Count != 0 && "nonsensical Count!");
136 
137  // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)
138  // This means %xtraiter is (BECount + 1) and all of the iterations of this
139  // loop were executed by the prologue. Note that if BECount <u (Count - 1)
140  // then (BECount + 1) cannot unsigned-overflow.
141  Value *BrLoopExit =
142  B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1));
143  // Split the exit to maintain loop canonicalization guarantees
144  SmallVector<BasicBlock *, 4> Preds(predecessors(OriginalLoopLatchExit));
145  SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI,
146  nullptr, PreserveLCSSA);
147  // Add the branch to the exit block (around the unrolled loop)
148  B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader);
149  InsertPt->eraseFromParent();
150  if (DT)
151  DT->changeImmediateDominator(OriginalLoopLatchExit, PrologExit);
152 }
153 
154 /// Connect the unrolling epilog code to the original loop.
155 /// The unrolling epilog code contains code to execute the
156 /// 'extra' iterations if the run-time trip count modulo the
157 /// unroll count is non-zero.
158 ///
159 /// This function performs the following:
160 /// - Update PHI nodes at the unrolling loop exit and epilog loop exit
161 /// - Create PHI nodes at the unrolling loop exit to combine
162 /// values that exit the unrolling loop code and jump around it.
163 /// - Update PHI operands in the epilog loop by the new PHI nodes
164 /// - Branch around the epilog loop if extra iters (ModVal) is zero.
165 ///
166 static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,
167  BasicBlock *Exit, BasicBlock *PreHeader,
168  BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader,
169  ValueToValueMapTy &VMap, DominatorTree *DT,
170  LoopInfo *LI, bool PreserveLCSSA) {
171  BasicBlock *Latch = L->getLoopLatch();
172  assert(Latch && "Loop must have a latch");
173  BasicBlock *EpilogLatch = cast<BasicBlock>(VMap[Latch]);
174 
175  // Loop structure should be the following:
176  //
177  // PreHeader
178  // NewPreHeader
179  // Header
180  // ...
181  // Latch
182  // NewExit (PN)
183  // EpilogPreHeader
184  // EpilogHeader
185  // ...
186  // EpilogLatch
187  // Exit (EpilogPN)
188 
189  // Update PHI nodes at NewExit and Exit.
190  for (PHINode &PN : NewExit->phis()) {
191  // PN should be used in another PHI located in Exit block as
192  // Exit was split by SplitBlockPredecessors into Exit and NewExit
193  // Basicaly it should look like:
194  // NewExit:
195  // PN = PHI [I, Latch]
196  // ...
197  // Exit:
198  // EpilogPN = PHI [PN, EpilogPreHeader]
199  //
200  // There is EpilogPreHeader incoming block instead of NewExit as
201  // NewExit was spilt 1 more time to get EpilogPreHeader.
202  assert(PN.hasOneUse() && "The phi should have 1 use");
203  PHINode *EpilogPN = cast<PHINode>(PN.use_begin()->getUser());
204  assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block");
205 
206  // Add incoming PreHeader from branch around the Loop
207  PN.addIncoming(UndefValue::get(PN.getType()), PreHeader);
208 
209  Value *V = PN.getIncomingValueForBlock(Latch);
211  if (I && L->contains(I))
212  // If value comes from an instruction in the loop add VMap value.
213  V = VMap.lookup(I);
214  // For the instruction out of the loop, constant or undefined value
215  // insert value itself.
216  EpilogPN->addIncoming(V, EpilogLatch);
217 
218  assert(EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 &&
219  "EpilogPN should have EpilogPreHeader incoming block");
220  // Change EpilogPreHeader incoming block to NewExit.
221  EpilogPN->setIncomingBlock(EpilogPN->getBasicBlockIndex(EpilogPreHeader),
222  NewExit);
223  // Now PHIs should look like:
224  // NewExit:
225  // PN = PHI [I, Latch], [undef, PreHeader]
226  // ...
227  // Exit:
228  // EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]
229  }
230 
231  // Create PHI nodes at NewExit (from the unrolling loop Latch and PreHeader).
232  // Update corresponding PHI nodes in epilog loop.
233  for (BasicBlock *Succ : successors(Latch)) {
234  // Skip this as we already updated phis in exit blocks.
235  if (!L->contains(Succ))
236  continue;
237  for (PHINode &PN : Succ->phis()) {
238  // Add new PHI nodes to the loop exit block and update epilog
239  // PHIs with the new PHI values.
240  PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
241  NewExit->getFirstNonPHI());
242  // Adding a value to the new PHI node from the unrolling loop preheader.
243  NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader), PreHeader);
244  // Adding a value to the new PHI node from the unrolling loop latch.
245  NewPN->addIncoming(PN.getIncomingValueForBlock(Latch), Latch);
246 
247  // Update the existing PHI node operand with the value from the new PHI
248  // node. Corresponding instruction in epilog loop should be PHI.
249  PHINode *VPN = cast<PHINode>(VMap[&PN]);
250  VPN->setIncomingValue(VPN->getBasicBlockIndex(EpilogPreHeader), NewPN);
251  }
252  }
253 
254  Instruction *InsertPt = NewExit->getTerminator();
255  IRBuilder<> B(InsertPt);
256  Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");
257  assert(Exit && "Loop must have a single exit block only");
258  // Split the epilogue exit to maintain loop canonicalization guarantees
260  SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI, nullptr,
261  PreserveLCSSA);
262  // Add the branch to the exit block (around the unrolling loop)
263  B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
264  InsertPt->eraseFromParent();
265  if (DT)
266  DT->changeImmediateDominator(Exit, NewExit);
267 
268  // Split the main loop exit to maintain canonicalization guarantees.
269  SmallVector<BasicBlock*, 4> NewExitPreds{Latch};
270  SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI, nullptr,
271  PreserveLCSSA);
272 }
273 
274 /// Create a clone of the blocks in a loop and connect them together.
275 /// If CreateRemainderLoop is false, loop structure will not be cloned,
276 /// otherwise a new loop will be created including all cloned blocks, and the
277 /// iterator of it switches to count NewIter down to 0.
278 /// The cloned blocks should be inserted between InsertTop and InsertBot.
279 /// If loop structure is cloned InsertTop should be new preheader, InsertBot
280 /// new loop exit.
281 /// Return the new cloned loop that is created when CreateRemainderLoop is true.
282 static Loop *
283 CloneLoopBlocks(Loop *L, Value *NewIter, const bool CreateRemainderLoop,
284  const bool UseEpilogRemainder, const bool UnrollRemainder,
285  BasicBlock *InsertTop,
286  BasicBlock *InsertBot, BasicBlock *Preheader,
287  std::vector<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
288  ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI) {
289  StringRef suffix = UseEpilogRemainder ? "epil" : "prol";
290  BasicBlock *Header = L->getHeader();
291  BasicBlock *Latch = L->getLoopLatch();
292  Function *F = Header->getParent();
293  LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
294  LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
295  Loop *ParentLoop = L->getParentLoop();
296  NewLoopsMap NewLoops;
297  NewLoops[ParentLoop] = ParentLoop;
298  if (!CreateRemainderLoop)
299  NewLoops[L] = ParentLoop;
300 
301  // For each block in the original loop, create a new copy,
302  // and update the value map with the newly created values.
303  for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
304  BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, "." + suffix, F);
305  NewBlocks.push_back(NewBB);
306 
307  // If we're unrolling the outermost loop, there's no remainder loop,
308  // and this block isn't in a nested loop, then the new block is not
309  // in any loop. Otherwise, add it to loopinfo.
310  if (CreateRemainderLoop || LI->getLoopFor(*BB) != L || ParentLoop)
311  addClonedBlockToLoopInfo(*BB, NewBB, LI, NewLoops);
312 
313  VMap[*BB] = NewBB;
314  if (Header == *BB) {
315  // For the first block, add a CFG connection to this newly
316  // created block.
317  InsertTop->getTerminator()->setSuccessor(0, NewBB);
318  }
319 
320  if (DT) {
321  if (Header == *BB) {
322  // The header is dominated by the preheader.
323  DT->addNewBlock(NewBB, InsertTop);
324  } else {
325  // Copy information from original loop to unrolled loop.
326  BasicBlock *IDomBB = DT->getNode(*BB)->getIDom()->getBlock();
327  DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDomBB]));
328  }
329  }
330 
331  if (Latch == *BB) {
332  // For the last block, if CreateRemainderLoop is false, create a direct
333  // jump to InsertBot. If not, create a loop back to cloned head.
334  VMap.erase((*BB)->getTerminator());
335  BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]);
336  BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());
337  IRBuilder<> Builder(LatchBR);
338  if (!CreateRemainderLoop) {
339  Builder.CreateBr(InsertBot);
340  } else {
341  PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2,
342  suffix + ".iter",
343  FirstLoopBB->getFirstNonPHI());
344  Value *IdxSub =
345  Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
346  NewIdx->getName() + ".sub");
347  Value *IdxCmp =
348  Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp");
349  Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot);
350  NewIdx->addIncoming(NewIter, InsertTop);
351  NewIdx->addIncoming(IdxSub, NewBB);
352  }
353  LatchBR->eraseFromParent();
354  }
355  }
356 
357  // Change the incoming values to the ones defined in the preheader or
358  // cloned loop.
359  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
360  PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
361  if (!CreateRemainderLoop) {
362  if (UseEpilogRemainder) {
363  unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
364  NewPHI->setIncomingBlock(idx, InsertTop);
365  NewPHI->removeIncomingValue(Latch, false);
366  } else {
367  VMap[&*I] = NewPHI->getIncomingValueForBlock(Preheader);
368  cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
369  }
370  } else {
371  unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
372  NewPHI->setIncomingBlock(idx, InsertTop);
373  BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
374  idx = NewPHI->getBasicBlockIndex(Latch);
375  Value *InVal = NewPHI->getIncomingValue(idx);
376  NewPHI->setIncomingBlock(idx, NewLatch);
377  if (Value *V = VMap.lookup(InVal))
378  NewPHI->setIncomingValue(idx, V);
379  }
380  }
381  if (CreateRemainderLoop) {
382  Loop *NewLoop = NewLoops[L];
383  MDNode *LoopID = NewLoop->getLoopID();
384  assert(NewLoop && "L should have been cloned");
385 
386  // Only add loop metadata if the loop is not going to be completely
387  // unrolled.
388  if (UnrollRemainder)
389  return NewLoop;
390 
393  if (NewLoopID.hasValue()) {
394  NewLoop->setLoopID(NewLoopID.getValue());
395 
396  // Do not setLoopAlreadyUnrolled if loop attributes have been defined
397  // explicitly.
398  return NewLoop;
399  }
400 
401  // Add unroll disable metadata to disable future unrolling for this loop.
402  NewLoop->setLoopAlreadyUnrolled();
403  return NewLoop;
404  }
405  else
406  return nullptr;
407 }
408 
409 /// Returns true if we can safely unroll a multi-exit/exiting loop. OtherExits
410 /// is populated with all the loop exit blocks other than the LatchExit block.
411 static bool
413  BasicBlock *LatchExit, bool PreserveLCSSA,
414  bool UseEpilogRemainder) {
415 
416  // We currently have some correctness constrains in unrolling a multi-exit
417  // loop. Check for these below.
418 
419  // We rely on LCSSA form being preserved when the exit blocks are transformed.
420  if (!PreserveLCSSA)
421  return false;
423  L->getUniqueExitBlocks(Exits);
424  for (auto *BB : Exits)
425  if (BB != LatchExit)
426  OtherExits.push_back(BB);
427 
428  // TODO: Support multiple exiting blocks jumping to the `LatchExit` when
429  // UnrollRuntimeMultiExit is true. This will need updating the logic in
430  // connectEpilog/connectProlog.
431  if (!LatchExit->getSinglePredecessor()) {
432  LLVM_DEBUG(
433  dbgs() << "Bailout for multi-exit handling when latch exit has >1 "
434  "predecessor.\n");
435  return false;
436  }
437  // FIXME: We bail out of multi-exit unrolling when epilog loop is generated
438  // and L is an inner loop. This is because in presence of multiple exits, the
439  // outer loop is incorrect: we do not add the EpilogPreheader and exit to the
440  // outer loop. This is automatically handled in the prolog case, so we do not
441  // have that bug in prolog generation.
442  if (UseEpilogRemainder && L->getParentLoop())
443  return false;
444 
445  // All constraints have been satisfied.
446  return true;
447 }
448 
449 /// Returns true if we can profitably unroll the multi-exit loop L. Currently,
450 /// we return true only if UnrollRuntimeMultiExit is set to true.
452  Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,
453  bool PreserveLCSSA, bool UseEpilogRemainder) {
454 
455 #if !defined(NDEBUG)
456  SmallVector<BasicBlock *, 8> OtherExitsDummyCheck;
457  assert(canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck, LatchExit,
458  PreserveLCSSA, UseEpilogRemainder) &&
459  "Should be safe to unroll before checking profitability!");
460 #endif
461 
462  // Priority goes to UnrollRuntimeMultiExit if it's supplied.
463  if (UnrollRuntimeMultiExit.getNumOccurrences())
464  return UnrollRuntimeMultiExit;
465 
466  // The main pain point with multi-exit loop unrolling is that once unrolled,
467  // we will not be able to merge all blocks into a straight line code.
468  // There are branches within the unrolled loop that go to the OtherExits.
469  // The second point is the increase in code size, but this is true
470  // irrespective of multiple exits.
471 
472  // Note: Both the heuristics below are coarse grained. We are essentially
473  // enabling unrolling of loops that have a single side exit other than the
474  // normal LatchExit (i.e. exiting into a deoptimize block).
475  // The heuristics considered are:
476  // 1. low number of branches in the unrolled version.
477  // 2. high predictability of these extra branches.
478  // We avoid unrolling loops that have more than two exiting blocks. This
479  // limits the total number of branches in the unrolled loop to be atmost
480  // the unroll factor (since one of the exiting blocks is the latch block).
481  SmallVector<BasicBlock*, 4> ExitingBlocks;
482  L->getExitingBlocks(ExitingBlocks);
483  if (ExitingBlocks.size() > 2)
484  return false;
485 
486  // The second heuristic is that L has one exit other than the latchexit and
487  // that exit is a deoptimize block. We know that deoptimize blocks are rarely
488  // taken, which also implies the branch leading to the deoptimize block is
489  // highly predictable.
490  return (OtherExits.size() == 1 &&
491  OtherExits[0]->getTerminatingDeoptimizeCall());
492  // TODO: These can be fine-tuned further to consider code size or deopt states
493  // that are captured by the deoptimize exit block.
494  // Also, we can extend this to support more cases, if we actually
495  // know of kinds of multiexit loops that would benefit from unrolling.
496 }
497 
498 /// Insert code in the prolog/epilog code when unrolling a loop with a
499 /// run-time trip-count.
500 ///
501 /// This method assumes that the loop unroll factor is total number
502 /// of loop bodies in the loop after unrolling. (Some folks refer
503 /// to the unroll factor as the number of *extra* copies added).
504 /// We assume also that the loop unroll factor is a power-of-two. So, after
505 /// unrolling the loop, the number of loop bodies executed is 2,
506 /// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch
507 /// instruction in SimplifyCFG.cpp. Then, the backend decides how code for
508 /// the switch instruction is generated.
509 ///
510 /// ***Prolog case***
511 /// extraiters = tripcount % loopfactor
512 /// if (extraiters == 0) jump Loop:
513 /// else jump Prol:
514 /// Prol: LoopBody;
515 /// extraiters -= 1 // Omitted if unroll factor is 2.
516 /// if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
517 /// if (tripcount < loopfactor) jump End:
518 /// Loop:
519 /// ...
520 /// End:
521 ///
522 /// ***Epilog case***
523 /// extraiters = tripcount % loopfactor
524 /// if (tripcount < loopfactor) jump LoopExit:
525 /// unroll_iters = tripcount - extraiters
526 /// Loop: LoopBody; (executes unroll_iter times);
527 /// unroll_iter -= 1
528 /// if (unroll_iter != 0) jump Loop:
529 /// LoopExit:
530 /// if (extraiters == 0) jump EpilExit:
531 /// Epil: LoopBody; (executes extraiters times)
532 /// extraiters -= 1 // Omitted if unroll factor is 2.
533 /// if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
534 /// EpilExit:
535 
536 bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
537  bool AllowExpensiveTripCount,
538  bool UseEpilogRemainder,
539  bool UnrollRemainder, LoopInfo *LI,
541  AssumptionCache *AC, bool PreserveLCSSA,
542  Loop **ResultLoop) {
543  LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
544  LLVM_DEBUG(L->dump());
545  LLVM_DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"
546  : dbgs() << "Using prolog remainder.\n");
547 
548  // Make sure the loop is in canonical form.
549  if (!L->isLoopSimplifyForm()) {
550  LLVM_DEBUG(dbgs() << "Not in simplify form!\n");
551  return false;
552  }
553 
554  // Guaranteed by LoopSimplifyForm.
555  BasicBlock *Latch = L->getLoopLatch();
556  BasicBlock *Header = L->getHeader();
557 
558  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
559 
560  if (!LatchBR || LatchBR->isUnconditional()) {
561  // The loop-rotate pass can be helpful to avoid this in many cases.
562  LLVM_DEBUG(
563  dbgs()
564  << "Loop latch not terminated by a conditional branch.\n");
565  return false;
566  }
567 
568  unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 1 : 0;
569  BasicBlock *LatchExit = LatchBR->getSuccessor(ExitIndex);
570 
571  if (L->contains(LatchExit)) {
572  // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
573  // targets of the Latch be an exit block out of the loop.
574  LLVM_DEBUG(
575  dbgs()
576  << "One of the loop latch successors must be the exit block.\n");
577  return false;
578  }
579 
580  // These are exit blocks other than the target of the latch exiting block.
581  SmallVector<BasicBlock *, 4> OtherExits;
582  bool isMultiExitUnrollingEnabled =
583  canSafelyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
584  UseEpilogRemainder) &&
585  canProfitablyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
586  UseEpilogRemainder);
587  // Support only single exit and exiting block unless multi-exit loop unrolling is enabled.
588  if (!isMultiExitUnrollingEnabled &&
589  (!L->getExitingBlock() || OtherExits.size())) {
590  LLVM_DEBUG(
591  dbgs()
592  << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
593  "enabled!\n");
594  return false;
595  }
596  // Use Scalar Evolution to compute the trip count. This allows more loops to
597  // be unrolled than relying on induction var simplification.
598  if (!SE)
599  return false;
600 
601  // Only unroll loops with a computable trip count, and the trip count needs
602  // to be an int value (allowing a pointer type is a TODO item).
603  // We calculate the backedge count by using getExitCount on the Latch block,
604  // which is proven to be the only exiting block in this loop. This is same as
605  // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
606  // exiting blocks).
607  const SCEV *BECountSC = SE->getExitCount(L, Latch);
608  if (isa<SCEVCouldNotCompute>(BECountSC) ||
609  !BECountSC->getType()->isIntegerTy()) {
610  LLVM_DEBUG(dbgs() << "Could not compute exit block SCEV\n");
611  return false;
612  }
613 
614  unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
615 
616  // Add 1 since the backedge count doesn't include the first loop iteration.
617  const SCEV *TripCountSC =
618  SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
619  if (isa<SCEVCouldNotCompute>(TripCountSC)) {
620  LLVM_DEBUG(dbgs() << "Could not compute trip count SCEV.\n");
621  return false;
622  }
623 
624  BasicBlock *PreHeader = L->getLoopPreheader();
625  BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
626  const DataLayout &DL = Header->getModule()->getDataLayout();
627  SCEVExpander Expander(*SE, DL, "loop-unroll");
628  if (!AllowExpensiveTripCount &&
629  Expander.isHighCostExpansion(TripCountSC, L, PreHeaderBR)) {
630  LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
631  return false;
632  }
633 
634  // This constraint lets us deal with an overflowing trip count easily; see the
635  // comment on ModVal below.
636  if (Log2_32(Count) > BEWidth) {
637  LLVM_DEBUG(
638  dbgs()
639  << "Count failed constraint on overflow trip count calculation.\n");
640  return false;
641  }
642 
643  // Loop structure is the following:
644  //
645  // PreHeader
646  // Header
647  // ...
648  // Latch
649  // LatchExit
650 
651  BasicBlock *NewPreHeader;
652  BasicBlock *NewExit = nullptr;
653  BasicBlock *PrologExit = nullptr;
654  BasicBlock *EpilogPreHeader = nullptr;
655  BasicBlock *PrologPreHeader = nullptr;
656 
657  if (UseEpilogRemainder) {
658  // If epilog remainder
659  // Split PreHeader to insert a branch around loop for unrolling.
660  NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
661  NewPreHeader->setName(PreHeader->getName() + ".new");
662  // Split LatchExit to create phi nodes from branch above.
663  SmallVector<BasicBlock*, 4> Preds(predecessors(LatchExit));
664  NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa", DT, LI,
665  nullptr, PreserveLCSSA);
666  // NewExit gets its DebugLoc from LatchExit, which is not part of the
667  // original Loop.
668  // Fix this by setting Loop's DebugLoc to NewExit.
669  auto *NewExitTerminator = NewExit->getTerminator();
670  NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());
671  // Split NewExit to insert epilog remainder loop.
672  EpilogPreHeader = SplitBlock(NewExit, NewExitTerminator, DT, LI);
673  EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
674  } else {
675  // If prolog remainder
676  // Split the original preheader twice to insert prolog remainder loop
677  PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
678  PrologPreHeader->setName(Header->getName() + ".prol.preheader");
679  PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
680  DT, LI);
681  PrologExit->setName(Header->getName() + ".prol.loopexit");
682  // Split PrologExit to get NewPreHeader.
683  NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
684  NewPreHeader->setName(PreHeader->getName() + ".new");
685  }
686  // Loop structure should be the following:
687  // Epilog Prolog
688  //
689  // PreHeader PreHeader
690  // *NewPreHeader *PrologPreHeader
691  // Header *PrologExit
692  // ... *NewPreHeader
693  // Latch Header
694  // *NewExit ...
695  // *EpilogPreHeader Latch
696  // LatchExit LatchExit
697 
698  // Calculate conditions for branch around loop for unrolling
699  // in epilog case and around prolog remainder loop in prolog case.
700  // Compute the number of extra iterations required, which is:
701  // extra iterations = run-time trip count % loop unroll factor
702  PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
703  Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
704  PreHeaderBR);
705  Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
706  PreHeaderBR);
707  IRBuilder<> B(PreHeaderBR);
708  Value *ModVal;
709  // Calculate ModVal = (BECount + 1) % Count.
710  // Note that TripCount is BECount + 1.
711  if (isPowerOf2_32(Count)) {
712  // When Count is power of 2 we don't BECount for epilog case, however we'll
713  // need it for a branch around unrolling loop for prolog case.
714  ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");
715  // 1. There are no iterations to be run in the prolog/epilog loop.
716  // OR
717  // 2. The addition computing TripCount overflowed.
718  //
719  // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
720  // the number of iterations that remain to be run in the original loop is a
721  // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (we
722  // explicitly check this above).
723  } else {
724  // As (BECount + 1) can potentially unsigned overflow we count
725  // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
726  Value *ModValTmp = B.CreateURem(BECount,
727  ConstantInt::get(BECount->getType(),
728  Count));
729  Value *ModValAdd = B.CreateAdd(ModValTmp,
730  ConstantInt::get(ModValTmp->getType(), 1));
731  // At that point (BECount % Count) + 1 could be equal to Count.
732  // To handle this case we need to take mod by Count one more time.
733  ModVal = B.CreateURem(ModValAdd,
734  ConstantInt::get(BECount->getType(), Count),
735  "xtraiter");
736  }
737  Value *BranchVal =
738  UseEpilogRemainder ? B.CreateICmpULT(BECount,
739  ConstantInt::get(BECount->getType(),
740  Count - 1)) :
741  B.CreateIsNotNull(ModVal, "lcmp.mod");
742  BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
743  BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
744  // Branch to either remainder (extra iterations) loop or unrolling loop.
745  B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
746  PreHeaderBR->eraseFromParent();
747  if (DT) {
748  if (UseEpilogRemainder)
749  DT->changeImmediateDominator(NewExit, PreHeader);
750  else
751  DT->changeImmediateDominator(PrologExit, PreHeader);
752  }
753  Function *F = Header->getParent();
754  // Get an ordered list of blocks in the loop to help with the ordering of the
755  // cloned blocks in the prolog/epilog code
756  LoopBlocksDFS LoopBlocks(L);
757  LoopBlocks.perform(LI);
758 
759  //
760  // For each extra loop iteration, create a copy of the loop's basic blocks
761  // and generate a condition that branches to the copy depending on the
762  // number of 'left over' iterations.
763  //
764  std::vector<BasicBlock *> NewBlocks;
765  ValueToValueMapTy VMap;
766 
767  // For unroll factor 2 remainder loop will have 1 iterations.
768  // Do not create 1 iteration loop.
769  bool CreateRemainderLoop = (Count != 2);
770 
771  // Clone all the basic blocks in the loop. If Count is 2, we don't clone
772  // the loop, otherwise we create a cloned loop to execute the extra
773  // iterations. This function adds the appropriate CFG connections.
774  BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;
775  BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
776  Loop *remainderLoop = CloneLoopBlocks(
777  L, ModVal, CreateRemainderLoop, UseEpilogRemainder, UnrollRemainder,
778  InsertTop, InsertBot,
779  NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
780 
781  // Insert the cloned blocks into the function.
782  F->getBasicBlockList().splice(InsertBot->getIterator(),
783  F->getBasicBlockList(),
784  NewBlocks[0]->getIterator(),
785  F->end());
786 
787  // Now the loop blocks are cloned and the other exiting blocks from the
788  // remainder are connected to the original Loop's exit blocks. The remaining
789  // work is to update the phi nodes in the original loop, and take in the
790  // values from the cloned region. Also update the dominator info for
791  // OtherExits and their immediate successors, since we have new edges into
792  // OtherExits.
793  SmallPtrSet<BasicBlock*, 8> ImmediateSuccessorsOfExitBlocks;
794  for (auto *BB : OtherExits) {
795  for (auto &II : *BB) {
796 
797  // Given we preserve LCSSA form, we know that the values used outside the
798  // loop will be used through these phi nodes at the exit blocks that are
799  // transformed below.
800  if (!isa<PHINode>(II))
801  break;
802  PHINode *Phi = cast<PHINode>(&II);
803  unsigned oldNumOperands = Phi->getNumIncomingValues();
804  // Add the incoming values from the remainder code to the end of the phi
805  // node.
806  for (unsigned i =0; i < oldNumOperands; i++){
807  Value *newVal = VMap.lookup(Phi->getIncomingValue(i));
808  // newVal can be a constant or derived from values outside the loop, and
809  // hence need not have a VMap value. Also, since lookup already generated
810  // a default "null" VMap entry for this value, we need to populate that
811  // VMap entry correctly, with the mapped entry being itself.
812  if (!newVal) {
813  newVal = Phi->getIncomingValue(i);
814  VMap[Phi->getIncomingValue(i)] = Phi->getIncomingValue(i);
815  }
816  Phi->addIncoming(newVal,
817  cast<BasicBlock>(VMap[Phi->getIncomingBlock(i)]));
818  }
819  }
820 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
821  for (BasicBlock *SuccBB : successors(BB)) {
822  assert(!(any_of(OtherExits,
823  [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) ||
824  SuccBB == LatchExit) &&
825  "Breaks the definition of dedicated exits!");
826  }
827 #endif
828  // Update the dominator info because the immediate dominator is no longer the
829  // header of the original Loop. BB has edges both from L and remainder code.
830  // Since the preheader determines which loop is run (L or directly jump to
831  // the remainder code), we set the immediate dominator as the preheader.
832  if (DT) {
833  DT->changeImmediateDominator(BB, PreHeader);
834  // Also update the IDom for immediate successors of BB. If the current
835  // IDom is the header, update the IDom to be the preheader because that is
836  // the nearest common dominator of all predecessors of SuccBB. We need to
837  // check for IDom being the header because successors of exit blocks can
838  // have edges from outside the loop, and we should not incorrectly update
839  // the IDom in that case.
840  for (BasicBlock *SuccBB: successors(BB))
841  if (ImmediateSuccessorsOfExitBlocks.insert(SuccBB).second) {
842  if (DT->getNode(SuccBB)->getIDom()->getBlock() == Header) {
843  assert(!SuccBB->getSinglePredecessor() &&
844  "BB should be the IDom then!");
845  DT->changeImmediateDominator(SuccBB, PreHeader);
846  }
847  }
848  }
849  }
850 
851  // Loop structure should be the following:
852  // Epilog Prolog
853  //
854  // PreHeader PreHeader
855  // NewPreHeader PrologPreHeader
856  // Header PrologHeader
857  // ... ...
858  // Latch PrologLatch
859  // NewExit PrologExit
860  // EpilogPreHeader NewPreHeader
861  // EpilogHeader Header
862  // ... ...
863  // EpilogLatch Latch
864  // LatchExit LatchExit
865 
866  // Rewrite the cloned instruction operands to use the values created when the
867  // clone is created.
868  for (BasicBlock *BB : NewBlocks) {
869  for (Instruction &I : *BB) {
870  RemapInstruction(&I, VMap,
872  }
873  }
874 
875  if (UseEpilogRemainder) {
876  // Connect the epilog code to the original loop and update the
877  // PHI functions.
878  ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader,
879  EpilogPreHeader, NewPreHeader, VMap, DT, LI,
880  PreserveLCSSA);
881 
882  // Update counter in loop for unrolling.
883  // I should be multiply of Count.
884  IRBuilder<> B2(NewPreHeader->getTerminator());
885  Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
886  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
887  B2.SetInsertPoint(LatchBR);
888  PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
889  Header->getFirstNonPHI());
890  Value *IdxSub =
891  B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
892  NewIdx->getName() + ".nsub");
893  Value *IdxCmp;
894  if (LatchBR->getSuccessor(0) == Header)
895  IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
896  else
897  IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
898  NewIdx->addIncoming(TestVal, NewPreHeader);
899  NewIdx->addIncoming(IdxSub, Latch);
900  LatchBR->setCondition(IdxCmp);
901  } else {
902  // Connect the prolog code to the original loop and update the
903  // PHI functions.
904  ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,
905  NewPreHeader, VMap, DT, LI, PreserveLCSSA);
906  }
907 
908  // If this loop is nested, then the loop unroller changes the code in the any
909  // of its parent loops, so the Scalar Evolution pass needs to be run again.
910  SE->forgetTopmostLoop(L);
911 
912  // Canonicalize to LoopSimplifyForm both original and remainder loops. We
913  // cannot rely on the LoopUnrollPass to do this because it only does
914  // canonicalization for parent/subloops and not the sibling loops.
915  if (OtherExits.size() > 0) {
916  // Generate dedicated exit blocks for the original loop, to preserve
917  // LoopSimplifyForm.
918  formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA);
919  // Generate dedicated exit blocks for the remainder loop if one exists, to
920  // preserve LoopSimplifyForm.
921  if (remainderLoop)
922  formDedicatedExitBlocks(remainderLoop, DT, LI, PreserveLCSSA);
923  }
924 
925  auto UnrollResult = LoopUnrollResult::Unmodified;
926  if (remainderLoop && UnrollRemainder) {
927  LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");
928  UnrollResult =
929  UnrollLoop(remainderLoop, /*Count*/ Count - 1, /*TripCount*/ Count - 1,
930  /*Force*/ false, /*AllowRuntime*/ false,
931  /*AllowExpensiveTripCount*/ false, /*PreserveCondBr*/ true,
932  /*PreserveOnlyFirst*/ false, /*TripMultiple*/ 1,
933  /*PeelCount*/ 0, /*UnrollRemainder*/ false, LI, SE, DT, AC,
934  /*ORE*/ nullptr, PreserveLCSSA);
935  }
936 
937  if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)
938  *ResultLoop = remainderLoop;
939  NumRuntimeUnrolled++;
940  return true;
941 }
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional &#39;br Cond, TrueDest, FalseDest&#39; instruction.
Definition: IRBuilder.h:854
static bool canSafelyUnrollMultiExitLoop(Loop *L, SmallVectorImpl< BasicBlock *> &OtherExits, BasicBlock *LatchExit, bool PreserveLCSSA, bool UseEpilogRemainder)
Returns true if we can safely unroll a multi-exit/exiting loop.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:225
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA, Loop **ResultLoop=nullptr)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
Value * CreateIsNotNull(Value *Arg, const Twine &Name="")
Return an i1 value testing if Arg is not null.
Definition: IRBuilder.h:2008
const SCEV * getConstant(ConstantInt *V)
This class represents lattice values for constants.
Definition: AllocatorList.h:24
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1764
iterator end()
Definition: Function.h:658
The main scalar evolution driver.
This file contains the declarations for metadata subclasses.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:174
bool isHighCostExpansion(const SCEV *Expr, Loop *L, const Instruction *At=nullptr)
Return true for expressions that may incur non-trivial cost to evaluate at runtime.
A cache of @llvm.assume calls within a function.
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:864
F(f)
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
LoopUnrollResult UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force, bool AllowRuntime, bool AllowExpensiveTripCount, bool PreserveCondBr, bool PreserveOnlyFirst, unsigned TripMultiple, unsigned PeelCount, bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr)
Unroll the given loop by Count.
Definition: LoopUnroll.cpp:335
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:269
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the edge connecting specified block.
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:134
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:365
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:684
static Loop * CloneLoopBlocks(Loop *L, Value *NewIter, const bool CreateRemainderLoop, const bool UseEpilogRemainder, const bool UnrollRemainder, BasicBlock *InsertTop, BasicBlock *InsertBot, BasicBlock *Preheader, std::vector< BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI)
Create a clone of the blocks in a loop and connect them together.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:743
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:974
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:286
RPOIterator endRPO() const
Definition: LoopIterator.h:141
BlockT * getHeader() const
Definition: LoopInfo.h:100
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:239
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:161
const char *const LLVMLoopUnrollFollowupRemainder
Definition: UnrollLoop.h:43
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: ValueMap.h:171
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:749
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:73
static void ConnectProlog(Loop *L, Value *BECount, unsigned Count, BasicBlock *PrologExit, BasicBlock *OriginalLoopLatchExit, BasicBlock *PreHeader, BasicBlock *NewPreHeader, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
Connect the unrolling prolog code to the original loop.
The loop was fully unrolled into straight-line code.
NodeT * getBlock() const
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:419
static cl::opt< bool > UnrollRuntimeMultiExit("unroll-runtime-multi-exit", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolling for loops with multiple exits, when " "epilog is generated"))
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:190
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:308
void dump() const
Definition: LoopInfo.cpp:367
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:236
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:429
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Conditional or Unconditional Branch instruction.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node&#39;s...
DomTreeNodeBase * getIDom() const
Value * getIncomingValueForBlock(const BasicBlock *BB) const
void setLoopAlreadyUnrolled()
Add llvm.loop.unroll.disable to this loop&#39;s loop id metadata.
Definition: LoopInfo.cpp:257
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
const SCEV * getAddExpr(SmallVectorImpl< const SCEV *> &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
static bool canProfitablyUnrollMultiExitLoop(Loop *L, SmallVectorImpl< BasicBlock *> &OtherExits, BasicBlock *LatchExit, bool PreserveLCSSA, bool UseEpilogRemainder)
Returns true if we can profitably unroll the multi-exit loop L.
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:329
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1187
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:102
self_iterator getIterator()
Definition: ilist_node.h:82
void getExitingBlocks(SmallVectorImpl< BlockT *> &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:35
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1415
size_t size() const
Definition: SmallVector.h:53
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit, BasicBlock *Exit, BasicBlock *PreHeader, BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
Connect the unrolling epilog code to the original loop.
const char *const LLVMLoopUnrollFollowupAll
Definition: UnrollLoop.h:40
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
Iterator for intrusive lists based on ilist_node.
Type * getType() const
Return the LLVM type of this SCEV expression.
void setIncomingBlock(unsigned i, BasicBlock *BB)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Module.h This file contains the declarations for the Module class.
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:622
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:125
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Value * CreateURem(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1053
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
Optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)
Create a new loop identifier for a loop created from a loop transformation.
Definition: LoopUtils.cpp:277
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:539
const Loop * addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops)
Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary and adds a mapping from the o...
Definition: LoopUnroll.cpp:190
Store the result of a depth first search within basic blocks contained by a single loop...
Definition: LoopIterator.h:98
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM...
Definition: ValueMapper.h:251
This class uses information about analyze scalars to rewrite expressions in canonical form...
If this flag is set, the remapper ignores missing function-local entries (Argument, Instruction, BasicBlock) that are not in the value map.
Definition: ValueMapper.h:91
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
bool hasValue() const
Definition: Optional.h:165
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:193
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:215
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:311
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:215
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#define I(x, y, z)
Definition: MD5.cpp:58
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:633
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:325
bool isUnconditional() const
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1124
void setCondition(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(Instruction *I)
Definition: CFG.h:264
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:137
The loop was not modified.
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:49
void getUniqueExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:100
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
const SCEV * getExitCount(const Loop *L, BasicBlock *ExitingBlock)
Get the expression for the number of loop iterations for which this loop is guaranteed not to exit vi...
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:123
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:50
bool erase(const KeyT &Val)
Definition: ValueMap.h:197
void forgetTopmostLoop(const Loop *L)