LLVM  6.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/Statistic.h"
25 #include "llvm/ADT/SmallSet.h"
28 #include "llvm/Analysis/LoopPass.h"
31 #include "llvm/IR/BasicBlock.h"
32 #include "llvm/IR/Dominators.h"
33 #include "llvm/IR/Metadata.h"
34 #include "llvm/IR/Module.h"
35 #include "llvm/Support/Debug.h"
37 #include "llvm/Transforms/Scalar.h"
42 #include <algorithm>
43 
44 using namespace llvm;
45 
46 #define DEBUG_TYPE "loop-unroll"
47 
48 STATISTIC(NumRuntimeUnrolled,
49  "Number of loops unrolled with run-time trip counts");
51  "unroll-runtime-multi-exit", cl::init(false), cl::Hidden,
52  cl::desc("Allow runtime unrolling for loops with multiple exits, when "
53  "epilog is generated"));
54 
55 /// Connect the unrolling prolog code to the original loop.
56 /// The unrolling prolog code contains code to execute the
57 /// 'extra' iterations if the run-time trip count modulo the
58 /// unroll count is non-zero.
59 ///
60 /// This function performs the following:
61 /// - Create PHI nodes at prolog end block to combine values
62 /// that exit the prolog code and jump around the prolog.
63 /// - Add a PHI operand to a PHI node at the loop exit block
64 /// for values that exit the prolog and go around the loop.
65 /// - Branch around the original loop if the trip count is less
66 /// than the unroll factor.
67 ///
68 static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
69  BasicBlock *PrologExit,
70  BasicBlock *OriginalLoopLatchExit,
71  BasicBlock *PreHeader, BasicBlock *NewPreHeader,
73  LoopInfo *LI, bool PreserveLCSSA) {
74  BasicBlock *Latch = L->getLoopLatch();
75  assert(Latch && "Loop must have a latch");
76  BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);
77 
78  // Create a PHI node for each outgoing value from the original loop
79  // (which means it is an outgoing value from the prolog code too).
80  // The new PHI node is inserted in the prolog end basic block.
81  // The new PHI node value is added as an operand of a PHI node in either
82  // the loop header or the loop exit block.
83  for (BasicBlock *Succ : successors(Latch)) {
84  for (Instruction &BBI : *Succ) {
85  PHINode *PN = dyn_cast<PHINode>(&BBI);
86  // Exit when we passed all PHI nodes.
87  if (!PN)
88  break;
89  // Add a new PHI node to the prolog end block and add the
90  // appropriate incoming values.
91  PHINode *NewPN = PHINode::Create(PN->getType(), 2, PN->getName() + ".unr",
92  PrologExit->getFirstNonPHI());
93  // Adding a value to the new PHI node from the original loop preheader.
94  // This is the value that skips all the prolog code.
95  if (L->contains(PN)) {
96  NewPN->addIncoming(PN->getIncomingValueForBlock(NewPreHeader),
97  PreHeader);
98  } else {
99  NewPN->addIncoming(UndefValue::get(PN->getType()), PreHeader);
100  }
101 
102  Value *V = PN->getIncomingValueForBlock(Latch);
103  if (Instruction *I = dyn_cast<Instruction>(V)) {
104  if (L->contains(I)) {
105  V = VMap.lookup(I);
106  }
107  }
108  // Adding a value to the new PHI node from the last prolog block
109  // that was created.
110  NewPN->addIncoming(V, PrologLatch);
111 
112  // Update the existing PHI node operand with the value from the
113  // new PHI node. How this is done depends on if the existing
114  // PHI node is in the original loop block, or the exit block.
115  if (L->contains(PN)) {
116  PN->setIncomingValue(PN->getBasicBlockIndex(NewPreHeader), NewPN);
117  } else {
118  PN->addIncoming(NewPN, PrologExit);
119  }
120  }
121  }
122 
123  // Make sure that created prolog loop is in simplified form
124  SmallVector<BasicBlock *, 4> PrologExitPreds;
125  Loop *PrologLoop = LI->getLoopFor(PrologLatch);
126  if (PrologLoop) {
127  for (BasicBlock *PredBB : predecessors(PrologExit))
128  if (PrologLoop->contains(PredBB))
129  PrologExitPreds.push_back(PredBB);
130 
131  SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI,
132  PreserveLCSSA);
133  }
134 
135  // Create a branch around the original loop, which is taken if there are no
136  // iterations remaining to be executed after running the prologue.
137  Instruction *InsertPt = PrologExit->getTerminator();
138  IRBuilder<> B(InsertPt);
139 
140  assert(Count != 0 && "nonsensical Count!");
141 
142  // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)
143  // This means %xtraiter is (BECount + 1) and all of the iterations of this
144  // loop were executed by the prologue. Note that if BECount <u (Count - 1)
145  // then (BECount + 1) cannot unsigned-overflow.
146  Value *BrLoopExit =
147  B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1));
148  // Split the exit to maintain loop canonicalization guarantees
149  SmallVector<BasicBlock *, 4> Preds(predecessors(OriginalLoopLatchExit));
150  SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI,
151  PreserveLCSSA);
152  // Add the branch to the exit block (around the unrolled loop)
153  B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader);
154  InsertPt->eraseFromParent();
155  if (DT)
156  DT->changeImmediateDominator(OriginalLoopLatchExit, PrologExit);
157 }
158 
159 /// Connect the unrolling epilog code to the original loop.
160 /// The unrolling epilog code contains code to execute the
161 /// 'extra' iterations if the run-time trip count modulo the
162 /// unroll count is non-zero.
163 ///
164 /// This function performs the following:
165 /// - Update PHI nodes at the unrolling loop exit and epilog loop exit
166 /// - Create PHI nodes at the unrolling loop exit to combine
167 /// values that exit the unrolling loop code and jump around it.
168 /// - Update PHI operands in the epilog loop by the new PHI nodes
169 /// - Branch around the epilog loop if extra iters (ModVal) is zero.
170 ///
171 static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,
172  BasicBlock *Exit, BasicBlock *PreHeader,
173  BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader,
174  ValueToValueMapTy &VMap, DominatorTree *DT,
175  LoopInfo *LI, bool PreserveLCSSA) {
176  BasicBlock *Latch = L->getLoopLatch();
177  assert(Latch && "Loop must have a latch");
178  BasicBlock *EpilogLatch = cast<BasicBlock>(VMap[Latch]);
179 
180  // Loop structure should be the following:
181  //
182  // PreHeader
183  // NewPreHeader
184  // Header
185  // ...
186  // Latch
187  // NewExit (PN)
188  // EpilogPreHeader
189  // EpilogHeader
190  // ...
191  // EpilogLatch
192  // Exit (EpilogPN)
193 
194  // Update PHI nodes at NewExit and Exit.
195  for (Instruction &BBI : *NewExit) {
196  PHINode *PN = dyn_cast<PHINode>(&BBI);
197  // Exit when we passed all PHI nodes.
198  if (!PN)
199  break;
200  // PN should be used in another PHI located in Exit block as
201  // Exit was split by SplitBlockPredecessors into Exit and NewExit
202  // Basicaly it should look like:
203  // NewExit:
204  // PN = PHI [I, Latch]
205  // ...
206  // Exit:
207  // EpilogPN = PHI [PN, EpilogPreHeader]
208  //
209  // There is EpilogPreHeader incoming block instead of NewExit as
210  // NewExit was spilt 1 more time to get EpilogPreHeader.
211  assert(PN->hasOneUse() && "The phi should have 1 use");
212  PHINode *EpilogPN = cast<PHINode> (PN->use_begin()->getUser());
213  assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block");
214 
215  // Add incoming PreHeader from branch around the Loop
216  PN->addIncoming(UndefValue::get(PN->getType()), PreHeader);
217 
218  Value *V = PN->getIncomingValueForBlock(Latch);
220  if (I && L->contains(I))
221  // If value comes from an instruction in the loop add VMap value.
222  V = VMap.lookup(I);
223  // For the instruction out of the loop, constant or undefined value
224  // insert value itself.
225  EpilogPN->addIncoming(V, EpilogLatch);
226 
227  assert(EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 &&
228  "EpilogPN should have EpilogPreHeader incoming block");
229  // Change EpilogPreHeader incoming block to NewExit.
230  EpilogPN->setIncomingBlock(EpilogPN->getBasicBlockIndex(EpilogPreHeader),
231  NewExit);
232  // Now PHIs should look like:
233  // NewExit:
234  // PN = PHI [I, Latch], [undef, PreHeader]
235  // ...
236  // Exit:
237  // EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]
238  }
239 
240  // Create PHI nodes at NewExit (from the unrolling loop Latch and PreHeader).
241  // Update corresponding PHI nodes in epilog loop.
242  for (BasicBlock *Succ : successors(Latch)) {
243  // Skip this as we already updated phis in exit blocks.
244  if (!L->contains(Succ))
245  continue;
246  for (Instruction &BBI : *Succ) {
247  PHINode *PN = dyn_cast<PHINode>(&BBI);
248  // Exit when we passed all PHI nodes.
249  if (!PN)
250  break;
251  // Add new PHI nodes to the loop exit block and update epilog
252  // PHIs with the new PHI values.
253  PHINode *NewPN = PHINode::Create(PN->getType(), 2, PN->getName() + ".unr",
254  NewExit->getFirstNonPHI());
255  // Adding a value to the new PHI node from the unrolling loop preheader.
256  NewPN->addIncoming(PN->getIncomingValueForBlock(NewPreHeader), PreHeader);
257  // Adding a value to the new PHI node from the unrolling loop latch.
258  NewPN->addIncoming(PN->getIncomingValueForBlock(Latch), Latch);
259 
260  // Update the existing PHI node operand with the value from the new PHI
261  // node. Corresponding instruction in epilog loop should be PHI.
262  PHINode *VPN = cast<PHINode>(VMap[&BBI]);
263  VPN->setIncomingValue(VPN->getBasicBlockIndex(EpilogPreHeader), NewPN);
264  }
265  }
266 
267  Instruction *InsertPt = NewExit->getTerminator();
268  IRBuilder<> B(InsertPt);
269  Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");
270  assert(Exit && "Loop must have a single exit block only");
271  // Split the epilogue exit to maintain loop canonicalization guarantees
273  SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI,
274  PreserveLCSSA);
275  // Add the branch to the exit block (around the unrolling loop)
276  B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
277  InsertPt->eraseFromParent();
278  if (DT)
279  DT->changeImmediateDominator(Exit, NewExit);
280 
281  // Split the main loop exit to maintain canonicalization guarantees.
282  SmallVector<BasicBlock*, 4> NewExitPreds{Latch};
283  SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI,
284  PreserveLCSSA);
285 }
286 
287 /// Create a clone of the blocks in a loop and connect them together.
288 /// If CreateRemainderLoop is false, loop structure will not be cloned,
289 /// otherwise a new loop will be created including all cloned blocks, and the
290 /// iterator of it switches to count NewIter down to 0.
291 /// The cloned blocks should be inserted between InsertTop and InsertBot.
292 /// If loop structure is cloned InsertTop should be new preheader, InsertBot
293 /// new loop exit.
294 /// Return the new cloned loop that is created when CreateRemainderLoop is true.
295 static Loop *
296 CloneLoopBlocks(Loop *L, Value *NewIter, const bool CreateRemainderLoop,
297  const bool UseEpilogRemainder, BasicBlock *InsertTop,
298  BasicBlock *InsertBot, BasicBlock *Preheader,
299  std::vector<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
300  ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI) {
301  StringRef suffix = UseEpilogRemainder ? "epil" : "prol";
302  BasicBlock *Header = L->getHeader();
303  BasicBlock *Latch = L->getLoopLatch();
304  Function *F = Header->getParent();
305  LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
306  LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
307  Loop *ParentLoop = L->getParentLoop();
308  NewLoopsMap NewLoops;
309  NewLoops[ParentLoop] = ParentLoop;
310  if (!CreateRemainderLoop)
311  NewLoops[L] = ParentLoop;
312 
313  // For each block in the original loop, create a new copy,
314  // and update the value map with the newly created values.
315  for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
316  BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, "." + suffix, F);
317  NewBlocks.push_back(NewBB);
318 
319  // If we're unrolling the outermost loop, there's no remainder loop,
320  // and this block isn't in a nested loop, then the new block is not
321  // in any loop. Otherwise, add it to loopinfo.
322  if (CreateRemainderLoop || LI->getLoopFor(*BB) != L || ParentLoop)
323  addClonedBlockToLoopInfo(*BB, NewBB, LI, NewLoops);
324 
325  VMap[*BB] = NewBB;
326  if (Header == *BB) {
327  // For the first block, add a CFG connection to this newly
328  // created block.
329  InsertTop->getTerminator()->setSuccessor(0, NewBB);
330  }
331 
332  if (DT) {
333  if (Header == *BB) {
334  // The header is dominated by the preheader.
335  DT->addNewBlock(NewBB, InsertTop);
336  } else {
337  // Copy information from original loop to unrolled loop.
338  BasicBlock *IDomBB = DT->getNode(*BB)->getIDom()->getBlock();
339  DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDomBB]));
340  }
341  }
342 
343  if (Latch == *BB) {
344  // For the last block, if CreateRemainderLoop is false, create a direct
345  // jump to InsertBot. If not, create a loop back to cloned head.
346  VMap.erase((*BB)->getTerminator());
347  BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]);
348  BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());
349  IRBuilder<> Builder(LatchBR);
350  if (!CreateRemainderLoop) {
351  Builder.CreateBr(InsertBot);
352  } else {
353  PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2,
354  suffix + ".iter",
355  FirstLoopBB->getFirstNonPHI());
356  Value *IdxSub =
357  Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
358  NewIdx->getName() + ".sub");
359  Value *IdxCmp =
360  Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp");
361  Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot);
362  NewIdx->addIncoming(NewIter, InsertTop);
363  NewIdx->addIncoming(IdxSub, NewBB);
364  }
365  LatchBR->eraseFromParent();
366  }
367  }
368 
369  // Change the incoming values to the ones defined in the preheader or
370  // cloned loop.
371  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
372  PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
373  if (!CreateRemainderLoop) {
374  if (UseEpilogRemainder) {
375  unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
376  NewPHI->setIncomingBlock(idx, InsertTop);
377  NewPHI->removeIncomingValue(Latch, false);
378  } else {
379  VMap[&*I] = NewPHI->getIncomingValueForBlock(Preheader);
380  cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
381  }
382  } else {
383  unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
384  NewPHI->setIncomingBlock(idx, InsertTop);
385  BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
386  idx = NewPHI->getBasicBlockIndex(Latch);
387  Value *InVal = NewPHI->getIncomingValue(idx);
388  NewPHI->setIncomingBlock(idx, NewLatch);
389  if (Value *V = VMap.lookup(InVal))
390  NewPHI->setIncomingValue(idx, V);
391  }
392  }
393  if (CreateRemainderLoop) {
394  Loop *NewLoop = NewLoops[L];
395  assert(NewLoop && "L should have been cloned");
396  // Add unroll disable metadata to disable future unrolling for this loop.
398  // Reserve first location for self reference to the LoopID metadata node.
399  MDs.push_back(nullptr);
400  MDNode *LoopID = NewLoop->getLoopID();
401  if (LoopID) {
402  // First remove any existing loop unrolling metadata.
403  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
404  bool IsUnrollMetadata = false;
405  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
406  if (MD) {
407  const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
408  IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
409  }
410  if (!IsUnrollMetadata)
411  MDs.push_back(LoopID->getOperand(i));
412  }
413  }
414 
415  LLVMContext &Context = NewLoop->getHeader()->getContext();
416  SmallVector<Metadata *, 1> DisableOperands;
417  DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
418  MDNode *DisableNode = MDNode::get(Context, DisableOperands);
419  MDs.push_back(DisableNode);
420 
421  MDNode *NewLoopID = MDNode::get(Context, MDs);
422  // Set operand 0 to refer to the loop id itself.
423  NewLoopID->replaceOperandWith(0, NewLoopID);
424  NewLoop->setLoopID(NewLoopID);
425  return NewLoop;
426  }
427  else
428  return nullptr;
429 }
430 
431 /// Returns true if we can safely unroll a multi-exit/exiting loop. OtherExits
432 /// is populated with all the loop exit blocks other than the LatchExit block.
433 static bool
435  BasicBlock *LatchExit, bool PreserveLCSSA,
436  bool UseEpilogRemainder) {
437 
438  // We currently have some correctness constrains in unrolling a multi-exit
439  // loop. Check for these below.
440 
441  // We rely on LCSSA form being preserved when the exit blocks are transformed.
442  if (!PreserveLCSSA)
443  return false;
445  L->getUniqueExitBlocks(Exits);
446  for (auto *BB : Exits)
447  if (BB != LatchExit)
448  OtherExits.push_back(BB);
449 
450  // TODO: Support multiple exiting blocks jumping to the `LatchExit` when
451  // UnrollRuntimeMultiExit is true. This will need updating the logic in
452  // connectEpilog/connectProlog.
453  if (!LatchExit->getSinglePredecessor()) {
454  DEBUG(dbgs() << "Bailout for multi-exit handling when latch exit has >1 "
455  "predecessor.\n");
456  return false;
457  }
458  // FIXME: We bail out of multi-exit unrolling when epilog loop is generated
459  // and L is an inner loop. This is because in presence of multiple exits, the
460  // outer loop is incorrect: we do not add the EpilogPreheader and exit to the
461  // outer loop. This is automatically handled in the prolog case, so we do not
462  // have that bug in prolog generation.
463  if (UseEpilogRemainder && L->getParentLoop())
464  return false;
465 
466  // All constraints have been satisfied.
467  return true;
468 }
469 
470 /// Returns true if we can profitably unroll the multi-exit loop L. Currently,
471 /// we return true only if UnrollRuntimeMultiExit is set to true.
473  Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,
474  bool PreserveLCSSA, bool UseEpilogRemainder) {
475 
476 #if !defined(NDEBUG)
477  SmallVector<BasicBlock *, 8> OtherExitsDummyCheck;
478  assert(canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck, LatchExit,
479  PreserveLCSSA, UseEpilogRemainder) &&
480  "Should be safe to unroll before checking profitability!");
481 #endif
482  // Priority goes to UnrollRuntimeMultiExit if it's supplied.
483  return UnrollRuntimeMultiExit.getNumOccurrences() ? UnrollRuntimeMultiExit
484  : false;
485 }
486 
487 /// Insert code in the prolog/epilog code when unrolling a loop with a
488 /// run-time trip-count.
489 ///
490 /// This method assumes that the loop unroll factor is total number
491 /// of loop bodies in the loop after unrolling. (Some folks refer
492 /// to the unroll factor as the number of *extra* copies added).
493 /// We assume also that the loop unroll factor is a power-of-two. So, after
494 /// unrolling the loop, the number of loop bodies executed is 2,
495 /// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch
496 /// instruction in SimplifyCFG.cpp. Then, the backend decides how code for
497 /// the switch instruction is generated.
498 ///
499 /// ***Prolog case***
500 /// extraiters = tripcount % loopfactor
501 /// if (extraiters == 0) jump Loop:
502 /// else jump Prol:
503 /// Prol: LoopBody;
504 /// extraiters -= 1 // Omitted if unroll factor is 2.
505 /// if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
506 /// if (tripcount < loopfactor) jump End:
507 /// Loop:
508 /// ...
509 /// End:
510 ///
511 /// ***Epilog case***
512 /// extraiters = tripcount % loopfactor
513 /// if (tripcount < loopfactor) jump LoopExit:
514 /// unroll_iters = tripcount - extraiters
515 /// Loop: LoopBody; (executes unroll_iter times);
516 /// unroll_iter -= 1
517 /// if (unroll_iter != 0) jump Loop:
518 /// LoopExit:
519 /// if (extraiters == 0) jump EpilExit:
520 /// Epil: LoopBody; (executes extraiters times)
521 /// extraiters -= 1 // Omitted if unroll factor is 2.
522 /// if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
523 /// EpilExit:
524 
525 bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
526  bool AllowExpensiveTripCount,
527  bool UseEpilogRemainder,
528  LoopInfo *LI, ScalarEvolution *SE,
529  DominatorTree *DT, bool PreserveLCSSA) {
530  DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
531  DEBUG(L->dump());
532 
533  // Make sure the loop is in canonical form.
534  if (!L->isLoopSimplifyForm()) {
535  DEBUG(dbgs() << "Not in simplify form!\n");
536  return false;
537  }
538 
539  // Guaranteed by LoopSimplifyForm.
540  BasicBlock *Latch = L->getLoopLatch();
541  BasicBlock *Header = L->getHeader();
542 
543  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
544  unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 1 : 0;
545  BasicBlock *LatchExit = LatchBR->getSuccessor(ExitIndex);
546  // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
547  // targets of the Latch be an exit block out of the loop. This needs
548  // to be guaranteed by the callers of UnrollRuntimeLoopRemainder.
549  assert(!L->contains(LatchExit) &&
550  "one of the loop latch successors should be the exit block!");
551  // These are exit blocks other than the target of the latch exiting block.
552  SmallVector<BasicBlock *, 4> OtherExits;
553  bool isMultiExitUnrollingEnabled =
554  canSafelyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
555  UseEpilogRemainder) &&
556  canProfitablyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
557  UseEpilogRemainder);
558  // Support only single exit and exiting block unless multi-exit loop unrolling is enabled.
559  if (!isMultiExitUnrollingEnabled &&
560  (!L->getExitingBlock() || OtherExits.size())) {
561  DEBUG(
562  dbgs()
563  << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
564  "enabled!\n");
565  return false;
566  }
567  // Use Scalar Evolution to compute the trip count. This allows more loops to
568  // be unrolled than relying on induction var simplification.
569  if (!SE)
570  return false;
571 
572  // Only unroll loops with a computable trip count, and the trip count needs
573  // to be an int value (allowing a pointer type is a TODO item).
574  // We calculate the backedge count by using getExitCount on the Latch block,
575  // which is proven to be the only exiting block in this loop. This is same as
576  // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
577  // exiting blocks).
578  const SCEV *BECountSC = SE->getExitCount(L, Latch);
579  if (isa<SCEVCouldNotCompute>(BECountSC) ||
580  !BECountSC->getType()->isIntegerTy()) {
581  DEBUG(dbgs() << "Could not compute exit block SCEV\n");
582  return false;
583  }
584 
585  unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
586 
587  // Add 1 since the backedge count doesn't include the first loop iteration.
588  const SCEV *TripCountSC =
589  SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
590  if (isa<SCEVCouldNotCompute>(TripCountSC)) {
591  DEBUG(dbgs() << "Could not compute trip count SCEV.\n");
592  return false;
593  }
594 
595  BasicBlock *PreHeader = L->getLoopPreheader();
596  BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
597  const DataLayout &DL = Header->getModule()->getDataLayout();
598  SCEVExpander Expander(*SE, DL, "loop-unroll");
599  if (!AllowExpensiveTripCount &&
600  Expander.isHighCostExpansion(TripCountSC, L, PreHeaderBR)) {
601  DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
602  return false;
603  }
604 
605  // This constraint lets us deal with an overflowing trip count easily; see the
606  // comment on ModVal below.
607  if (Log2_32(Count) > BEWidth) {
608  DEBUG(dbgs()
609  << "Count failed constraint on overflow trip count calculation.\n");
610  return false;
611  }
612 
613  // Loop structure is the following:
614  //
615  // PreHeader
616  // Header
617  // ...
618  // Latch
619  // LatchExit
620 
621  BasicBlock *NewPreHeader;
622  BasicBlock *NewExit = nullptr;
623  BasicBlock *PrologExit = nullptr;
624  BasicBlock *EpilogPreHeader = nullptr;
625  BasicBlock *PrologPreHeader = nullptr;
626 
627  if (UseEpilogRemainder) {
628  // If epilog remainder
629  // Split PreHeader to insert a branch around loop for unrolling.
630  NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
631  NewPreHeader->setName(PreHeader->getName() + ".new");
632  // Split LatchExit to create phi nodes from branch above.
633  SmallVector<BasicBlock*, 4> Preds(predecessors(LatchExit));
634  NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa",
635  DT, LI, PreserveLCSSA);
636  // Split NewExit to insert epilog remainder loop.
637  EpilogPreHeader = SplitBlock(NewExit, NewExit->getTerminator(), DT, LI);
638  EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
639  } else {
640  // If prolog remainder
641  // Split the original preheader twice to insert prolog remainder loop
642  PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
643  PrologPreHeader->setName(Header->getName() + ".prol.preheader");
644  PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
645  DT, LI);
646  PrologExit->setName(Header->getName() + ".prol.loopexit");
647  // Split PrologExit to get NewPreHeader.
648  NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
649  NewPreHeader->setName(PreHeader->getName() + ".new");
650  }
651  // Loop structure should be the following:
652  // Epilog Prolog
653  //
654  // PreHeader PreHeader
655  // *NewPreHeader *PrologPreHeader
656  // Header *PrologExit
657  // ... *NewPreHeader
658  // Latch Header
659  // *NewExit ...
660  // *EpilogPreHeader Latch
661  // LatchExit LatchExit
662 
663  // Calculate conditions for branch around loop for unrolling
664  // in epilog case and around prolog remainder loop in prolog case.
665  // Compute the number of extra iterations required, which is:
666  // extra iterations = run-time trip count % loop unroll factor
667  PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
668  Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
669  PreHeaderBR);
670  Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
671  PreHeaderBR);
672  IRBuilder<> B(PreHeaderBR);
673  Value *ModVal;
674  // Calculate ModVal = (BECount + 1) % Count.
675  // Note that TripCount is BECount + 1.
676  if (isPowerOf2_32(Count)) {
677  // When Count is power of 2 we don't BECount for epilog case, however we'll
678  // need it for a branch around unrolling loop for prolog case.
679  ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");
680  // 1. There are no iterations to be run in the prolog/epilog loop.
681  // OR
682  // 2. The addition computing TripCount overflowed.
683  //
684  // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
685  // the number of iterations that remain to be run in the original loop is a
686  // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (we
687  // explicitly check this above).
688  } else {
689  // As (BECount + 1) can potentially unsigned overflow we count
690  // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
691  Value *ModValTmp = B.CreateURem(BECount,
692  ConstantInt::get(BECount->getType(),
693  Count));
694  Value *ModValAdd = B.CreateAdd(ModValTmp,
695  ConstantInt::get(ModValTmp->getType(), 1));
696  // At that point (BECount % Count) + 1 could be equal to Count.
697  // To handle this case we need to take mod by Count one more time.
698  ModVal = B.CreateURem(ModValAdd,
699  ConstantInt::get(BECount->getType(), Count),
700  "xtraiter");
701  }
702  Value *BranchVal =
703  UseEpilogRemainder ? B.CreateICmpULT(BECount,
704  ConstantInt::get(BECount->getType(),
705  Count - 1)) :
706  B.CreateIsNotNull(ModVal, "lcmp.mod");
707  BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
708  BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
709  // Branch to either remainder (extra iterations) loop or unrolling loop.
710  B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
711  PreHeaderBR->eraseFromParent();
712  if (DT) {
713  if (UseEpilogRemainder)
714  DT->changeImmediateDominator(NewExit, PreHeader);
715  else
716  DT->changeImmediateDominator(PrologExit, PreHeader);
717  }
718  Function *F = Header->getParent();
719  // Get an ordered list of blocks in the loop to help with the ordering of the
720  // cloned blocks in the prolog/epilog code
721  LoopBlocksDFS LoopBlocks(L);
722  LoopBlocks.perform(LI);
723 
724  //
725  // For each extra loop iteration, create a copy of the loop's basic blocks
726  // and generate a condition that branches to the copy depending on the
727  // number of 'left over' iterations.
728  //
729  std::vector<BasicBlock *> NewBlocks;
730  ValueToValueMapTy VMap;
731 
732  // For unroll factor 2 remainder loop will have 1 iterations.
733  // Do not create 1 iteration loop.
734  bool CreateRemainderLoop = (Count != 2);
735 
736  // Clone all the basic blocks in the loop. If Count is 2, we don't clone
737  // the loop, otherwise we create a cloned loop to execute the extra
738  // iterations. This function adds the appropriate CFG connections.
739  BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;
740  BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
741  Loop *remainderLoop = CloneLoopBlocks(
742  L, ModVal, CreateRemainderLoop, UseEpilogRemainder, InsertTop, InsertBot,
743  NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
744 
745  // Insert the cloned blocks into the function.
746  F->getBasicBlockList().splice(InsertBot->getIterator(),
747  F->getBasicBlockList(),
748  NewBlocks[0]->getIterator(),
749  F->end());
750 
751  // Now the loop blocks are cloned and the other exiting blocks from the
752  // remainder are connected to the original Loop's exit blocks. The remaining
753  // work is to update the phi nodes in the original loop, and take in the
754  // values from the cloned region. Also update the dominator info for
755  // OtherExits and their immediate successors, since we have new edges into
756  // OtherExits.
757  SmallSet<BasicBlock*, 8> ImmediateSuccessorsOfExitBlocks;
758  for (auto *BB : OtherExits) {
759  for (auto &II : *BB) {
760 
761  // Given we preserve LCSSA form, we know that the values used outside the
762  // loop will be used through these phi nodes at the exit blocks that are
763  // transformed below.
764  if (!isa<PHINode>(II))
765  break;
766  PHINode *Phi = cast<PHINode>(&II);
767  unsigned oldNumOperands = Phi->getNumIncomingValues();
768  // Add the incoming values from the remainder code to the end of the phi
769  // node.
770  for (unsigned i =0; i < oldNumOperands; i++){
771  Value *newVal = VMap[Phi->getIncomingValue(i)];
772  // newVal can be a constant or derived from values outside the loop, and
773  // hence need not have a VMap value.
774  if (!newVal)
775  newVal = Phi->getIncomingValue(i);
776  Phi->addIncoming(newVal,
777  cast<BasicBlock>(VMap[Phi->getIncomingBlock(i)]));
778  }
779  }
780 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
781  for (BasicBlock *SuccBB : successors(BB)) {
782  assert(!(any_of(OtherExits,
783  [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) ||
784  SuccBB == LatchExit) &&
785  "Breaks the definition of dedicated exits!");
786  }
787 #endif
788  // Update the dominator info because the immediate dominator is no longer the
789  // header of the original Loop. BB has edges both from L and remainder code.
790  // Since the preheader determines which loop is run (L or directly jump to
791  // the remainder code), we set the immediate dominator as the preheader.
792  if (DT) {
793  DT->changeImmediateDominator(BB, PreHeader);
794  // Also update the IDom for immediate successors of BB. If the current
795  // IDom is the header, update the IDom to be the preheader because that is
796  // the nearest common dominator of all predecessors of SuccBB. We need to
797  // check for IDom being the header because successors of exit blocks can
798  // have edges from outside the loop, and we should not incorrectly update
799  // the IDom in that case.
800  for (BasicBlock *SuccBB: successors(BB))
801  if (ImmediateSuccessorsOfExitBlocks.insert(SuccBB).second) {
802  if (DT->getNode(SuccBB)->getIDom()->getBlock() == Header) {
803  assert(!SuccBB->getSinglePredecessor() &&
804  "BB should be the IDom then!");
805  DT->changeImmediateDominator(SuccBB, PreHeader);
806  }
807  }
808  }
809  }
810 
811  // Loop structure should be the following:
812  // Epilog Prolog
813  //
814  // PreHeader PreHeader
815  // NewPreHeader PrologPreHeader
816  // Header PrologHeader
817  // ... ...
818  // Latch PrologLatch
819  // NewExit PrologExit
820  // EpilogPreHeader NewPreHeader
821  // EpilogHeader Header
822  // ... ...
823  // EpilogLatch Latch
824  // LatchExit LatchExit
825 
826  // Rewrite the cloned instruction operands to use the values created when the
827  // clone is created.
828  for (BasicBlock *BB : NewBlocks) {
829  for (Instruction &I : *BB) {
830  RemapInstruction(&I, VMap,
832  }
833  }
834 
835  if (UseEpilogRemainder) {
836  // Connect the epilog code to the original loop and update the
837  // PHI functions.
838  ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader,
839  EpilogPreHeader, NewPreHeader, VMap, DT, LI,
840  PreserveLCSSA);
841 
842  // Update counter in loop for unrolling.
843  // I should be multiply of Count.
844  IRBuilder<> B2(NewPreHeader->getTerminator());
845  Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
846  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
847  B2.SetInsertPoint(LatchBR);
848  PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
849  Header->getFirstNonPHI());
850  Value *IdxSub =
851  B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
852  NewIdx->getName() + ".nsub");
853  Value *IdxCmp;
854  if (LatchBR->getSuccessor(0) == Header)
855  IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
856  else
857  IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
858  NewIdx->addIncoming(TestVal, NewPreHeader);
859  NewIdx->addIncoming(IdxSub, Latch);
860  LatchBR->setCondition(IdxCmp);
861  } else {
862  // Connect the prolog code to the original loop and update the
863  // PHI functions.
864  ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,
865  NewPreHeader, VMap, DT, LI, PreserveLCSSA);
866  }
867 
868  // If this loop is nested, then the loop unroller changes the code in the
869  // parent loop, so the Scalar Evolution pass needs to be run again.
870  if (Loop *ParentLoop = L->getParentLoop())
871  SE->forgetLoop(ParentLoop);
872 
873  // Canonicalize to LoopSimplifyForm both original and remainder loops. We
874  // cannot rely on the LoopUnrollPass to do this because it only does
875  // canonicalization for parent/subloops and not the sibling loops.
876  if (OtherExits.size() > 0) {
877  // Generate dedicated exit blocks for the original loop, to preserve
878  // LoopSimplifyForm.
879  formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA);
880  // Generate dedicated exit blocks for the remainder loop if one exists, to
881  // preserve LoopSimplifyForm.
882  if (remainderLoop)
883  formDedicatedExitBlocks(remainderLoop, DT, LI, PreserveLCSSA);
884  }
885 
886  NumRuntimeUnrolled++;
887  return true;
888 }
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
DomTreeNodeBase< NodeT > * getNode(NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
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:775
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:149
LLVMContext & Context
Value * CreateIsNotNull(Value *Arg, const Twine &Name="")
Return an i1 value testing if Arg is not null.
Definition: IRBuilder.h:1784
const SCEV * getConstant(ConstantInt *V)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1558
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:851
iterator end()
Definition: Function.h:582
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:446
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:101
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.
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:862
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1067
static Loop * CloneLoopBlocks(Loop *L, Value *NewIter, const bool CreateRemainderLoop, const bool UseEpilogRemainder, 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.
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr it the function does no...
Definition: BasicBlock.cpp:116
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:361
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:585
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:664
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:889
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:284
RPOIterator endRPO() const
Definition: LoopIterator.h:141
BlockT * getHeader() const
Definition: LoopInfo.h:103
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:267
#define F(x, y, z)
Definition: MD5.cpp:55
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:248
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:167
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:766
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:133
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:65
void getUniqueExitBlocks(SmallVectorImpl< BasicBlock *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfo.cpp:361
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.
StringRef getString() const
Definition: Metadata.cpp:456
NodeT * getBlock() const
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1164
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:404
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:171
void setSuccessor(unsigned idx, BasicBlock *B)
Update the specified successor to point at the provided block.
void dump() const
Definition: LoopInfo.cpp:411
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:217
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:421
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
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
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
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.
size_t size() const
Definition: BasicBlock.h:262
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:342
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:825
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
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock *> Preds, const char *Suffix, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
self_iterator getIterator()
Definition: ilist_node.h:82
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1320
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
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.
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.
#define B
Definition: LargeTest.cpp:24
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:864
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:560
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:110
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Value * CreateURem(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:987
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
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:531
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)
CloneBasicBlock - Return a copy of the specified basic block, but without embedding the block into a ...
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:243
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:83
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, bool PreserveLCSSA)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
LoopT * getParentLoop() const
Definition: LoopInfo.h:104
use_iterator use_begin()
Definition: Value.h:334
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:190
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:212
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:360
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
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:108
#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:557
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1063
void setCondition(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:137
bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA)
Ensure that all exit blocks of the loop are dedicated exits.
Definition: LoopUtils.cpp:940
#define DEBUG(X)
Definition: Debug.h:118
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the edge connecting specified block.
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:408
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
A single uniqued string.
Definition: Metadata.h:602
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...
const TerminatorInst * 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:120
void setIncomingValue(unsigned i, Value *V)
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1073
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
bool erase(const KeyT &Val)
Definition: ValueMap.h:193