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