LLVM  14.0.0git
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"
28 #include "llvm/IR/BasicBlock.h"
29 #include "llvm/IR/Dominators.h"
30 #include "llvm/IR/MDBuilder.h"
31 #include "llvm/IR/Metadata.h"
32 #include "llvm/IR/Module.h"
34 #include "llvm/Support/Debug.h"
36 #include "llvm/Transforms/Utils.h"
43 #include <algorithm>
44 
45 using namespace llvm;
46 
47 #define DEBUG_TYPE "loop-unroll"
48 
49 STATISTIC(NumRuntimeUnrolled,
50  "Number of loops unrolled with run-time trip counts");
52  "unroll-runtime-multi-exit", cl::init(false), cl::Hidden,
53  cl::desc("Allow runtime unrolling for loops with multiple exits, when "
54  "epilog is generated"));
56  "unroll-runtime-other-exit-predictable", cl::init(false), cl::Hidden,
57  cl::desc("Assume the non latch exit block to be predictable"));
58 
59 /// Connect the unrolling prolog code to the original loop.
60 /// The unrolling prolog code contains code to execute the
61 /// 'extra' iterations if the run-time trip count modulo the
62 /// unroll count is non-zero.
63 ///
64 /// This function performs the following:
65 /// - Create PHI nodes at prolog end block to combine values
66 /// that exit the prolog code and jump around the prolog.
67 /// - Add a PHI operand to a PHI node at the loop exit block
68 /// for values that exit the prolog and go around the loop.
69 /// - Branch around the original loop if the trip count is less
70 /// than the unroll factor.
71 ///
72 static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
73  BasicBlock *PrologExit,
74  BasicBlock *OriginalLoopLatchExit,
75  BasicBlock *PreHeader, BasicBlock *NewPreHeader,
77  LoopInfo *LI, bool PreserveLCSSA) {
78  // Loop structure should be the following:
79  // Preheader
80  // PrologHeader
81  // ...
82  // PrologLatch
83  // PrologExit
84  // NewPreheader
85  // Header
86  // ...
87  // Latch
88  // LatchExit
89  BasicBlock *Latch = L->getLoopLatch();
90  assert(Latch && "Loop must have a latch");
91  BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);
92 
93  // Create a PHI node for each outgoing value from the original loop
94  // (which means it is an outgoing value from the prolog code too).
95  // The new PHI node is inserted in the prolog end basic block.
96  // The new PHI node value is added as an operand of a PHI node in either
97  // the loop header or the loop exit block.
98  for (BasicBlock *Succ : successors(Latch)) {
99  for (PHINode &PN : Succ->phis()) {
100  // Add a new PHI node to the prolog end block and add the
101  // appropriate incoming values.
102  // TODO: This code assumes that the PrologExit (or the LatchExit block for
103  // prolog loop) contains only one predecessor from the loop, i.e. the
104  // PrologLatch. When supporting multiple-exiting block loops, we can have
105  // two or more blocks that have the LatchExit as the target in the
106  // original loop.
107  PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
108  PrologExit->getFirstNonPHI());
109  // Adding a value to the new PHI node from the original loop preheader.
110  // This is the value that skips all the prolog code.
111  if (L->contains(&PN)) {
112  // Succ is loop header.
113  NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader),
114  PreHeader);
115  } else {
116  // Succ is LatchExit.
117  NewPN->addIncoming(UndefValue::get(PN.getType()), PreHeader);
118  }
119 
120  Value *V = PN.getIncomingValueForBlock(Latch);
121  if (Instruction *I = dyn_cast<Instruction>(V)) {
122  if (L->contains(I)) {
123  V = VMap.lookup(I);
124  }
125  }
126  // Adding a value to the new PHI node from the last prolog block
127  // that was created.
128  NewPN->addIncoming(V, PrologLatch);
129 
130  // Update the existing PHI node operand with the value from the
131  // new PHI node. How this is done depends on if the existing
132  // PHI node is in the original loop block, or the exit block.
133  if (L->contains(&PN))
134  PN.setIncomingValueForBlock(NewPreHeader, NewPN);
135  else
136  PN.addIncoming(NewPN, PrologExit);
137  }
138  }
139 
140  // Make sure that created prolog loop is in simplified form
141  SmallVector<BasicBlock *, 4> PrologExitPreds;
142  Loop *PrologLoop = LI->getLoopFor(PrologLatch);
143  if (PrologLoop) {
144  for (BasicBlock *PredBB : predecessors(PrologExit))
145  if (PrologLoop->contains(PredBB))
146  PrologExitPreds.push_back(PredBB);
147 
148  SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI,
149  nullptr, PreserveLCSSA);
150  }
151 
152  // Create a branch around the original loop, which is taken if there are no
153  // iterations remaining to be executed after running the prologue.
154  Instruction *InsertPt = PrologExit->getTerminator();
155  IRBuilder<> B(InsertPt);
156 
157  assert(Count != 0 && "nonsensical Count!");
158 
159  // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)
160  // This means %xtraiter is (BECount + 1) and all of the iterations of this
161  // loop were executed by the prologue. Note that if BECount <u (Count - 1)
162  // then (BECount + 1) cannot unsigned-overflow.
163  Value *BrLoopExit =
164  B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1));
165  // Split the exit to maintain loop canonicalization guarantees
166  SmallVector<BasicBlock *, 4> Preds(predecessors(OriginalLoopLatchExit));
167  SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI,
168  nullptr, PreserveLCSSA);
169  // Add the branch to the exit block (around the unrolled loop)
170  B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader);
171  InsertPt->eraseFromParent();
172  if (DT) {
173  auto *NewDom = DT->findNearestCommonDominator(OriginalLoopLatchExit,
174  PrologExit);
175  DT->changeImmediateDominator(OriginalLoopLatchExit, NewDom);
176  }
177 }
178 
179 /// Connect the unrolling epilog code to the original loop.
180 /// The unrolling epilog code contains code to execute the
181 /// 'extra' iterations if the run-time trip count modulo the
182 /// unroll count is non-zero.
183 ///
184 /// This function performs the following:
185 /// - Update PHI nodes at the unrolling loop exit and epilog loop exit
186 /// - Create PHI nodes at the unrolling loop exit to combine
187 /// values that exit the unrolling loop code and jump around it.
188 /// - Update PHI operands in the epilog loop by the new PHI nodes
189 /// - Branch around the epilog loop if extra iters (ModVal) is zero.
190 ///
191 static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,
192  BasicBlock *Exit, BasicBlock *PreHeader,
193  BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader,
194  ValueToValueMapTy &VMap, DominatorTree *DT,
195  LoopInfo *LI, bool PreserveLCSSA) {
196  BasicBlock *Latch = L->getLoopLatch();
197  assert(Latch && "Loop must have a latch");
198  BasicBlock *EpilogLatch = cast<BasicBlock>(VMap[Latch]);
199 
200  // Loop structure should be the following:
201  //
202  // PreHeader
203  // NewPreHeader
204  // Header
205  // ...
206  // Latch
207  // NewExit (PN)
208  // EpilogPreHeader
209  // EpilogHeader
210  // ...
211  // EpilogLatch
212  // Exit (EpilogPN)
213 
214  // Update PHI nodes at NewExit and Exit.
215  for (PHINode &PN : NewExit->phis()) {
216  // PN should be used in another PHI located in Exit block as
217  // Exit was split by SplitBlockPredecessors into Exit and NewExit
218  // Basicaly it should look like:
219  // NewExit:
220  // PN = PHI [I, Latch]
221  // ...
222  // Exit:
223  // EpilogPN = PHI [PN, EpilogPreHeader], [X, Exit2], [Y, Exit2.epil]
224  //
225  // Exits from non-latch blocks point to the original exit block and the
226  // epilogue edges have already been added.
227  //
228  // There is EpilogPreHeader incoming block instead of NewExit as
229  // NewExit was spilt 1 more time to get EpilogPreHeader.
230  assert(PN.hasOneUse() && "The phi should have 1 use");
231  PHINode *EpilogPN = cast<PHINode>(PN.use_begin()->getUser());
232  assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block");
233 
234  // Add incoming PreHeader from branch around the Loop
235  PN.addIncoming(UndefValue::get(PN.getType()), PreHeader);
236 
237  Value *V = PN.getIncomingValueForBlock(Latch);
238  Instruction *I = dyn_cast<Instruction>(V);
239  if (I && L->contains(I))
240  // If value comes from an instruction in the loop add VMap value.
241  V = VMap.lookup(I);
242  // For the instruction out of the loop, constant or undefined value
243  // insert value itself.
244  EpilogPN->addIncoming(V, EpilogLatch);
245 
246  assert(EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 &&
247  "EpilogPN should have EpilogPreHeader incoming block");
248  // Change EpilogPreHeader incoming block to NewExit.
249  EpilogPN->setIncomingBlock(EpilogPN->getBasicBlockIndex(EpilogPreHeader),
250  NewExit);
251  // Now PHIs should look like:
252  // NewExit:
253  // PN = PHI [I, Latch], [undef, PreHeader]
254  // ...
255  // Exit:
256  // EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]
257  }
258 
259  // Create PHI nodes at NewExit (from the unrolling loop Latch and PreHeader).
260  // Update corresponding PHI nodes in epilog loop.
261  for (BasicBlock *Succ : successors(Latch)) {
262  // Skip this as we already updated phis in exit blocks.
263  if (!L->contains(Succ))
264  continue;
265  for (PHINode &PN : Succ->phis()) {
266  // Add new PHI nodes to the loop exit block and update epilog
267  // PHIs with the new PHI values.
268  PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
269  NewExit->getFirstNonPHI());
270  // Adding a value to the new PHI node from the unrolling loop preheader.
271  NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader), PreHeader);
272  // Adding a value to the new PHI node from the unrolling loop latch.
273  NewPN->addIncoming(PN.getIncomingValueForBlock(Latch), Latch);
274 
275  // Update the existing PHI node operand with the value from the new PHI
276  // node. Corresponding instruction in epilog loop should be PHI.
277  PHINode *VPN = cast<PHINode>(VMap[&PN]);
278  VPN->setIncomingValueForBlock(EpilogPreHeader, NewPN);
279  }
280  }
281 
282  Instruction *InsertPt = NewExit->getTerminator();
283  IRBuilder<> B(InsertPt);
284  Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");
285  assert(Exit && "Loop must have a single exit block only");
286  // Split the epilogue exit to maintain loop canonicalization guarantees
288  SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI, nullptr,
289  PreserveLCSSA);
290  // Add the branch to the exit block (around the unrolling loop)
291  B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
292  InsertPt->eraseFromParent();
293  if (DT) {
294  auto *NewDom = DT->findNearestCommonDominator(Exit, NewExit);
295  DT->changeImmediateDominator(Exit, NewDom);
296  }
297 
298  // Split the main loop exit to maintain canonicalization guarantees.
299  SmallVector<BasicBlock*, 4> NewExitPreds{Latch};
300  SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI, nullptr,
301  PreserveLCSSA);
302 }
303 
304 /// Create a clone of the blocks in a loop and connect them together. A new
305 /// loop will be created including all cloned blocks, and the iterator of the
306 /// new loop switched to count NewIter down to 0.
307 /// The cloned blocks should be inserted between InsertTop and InsertBot.
308 /// InsertTop should be new preheader, InsertBot new loop exit.
309 /// Returns the new cloned loop that is created.
310 static Loop *
311 CloneLoopBlocks(Loop *L, Value *NewIter, const bool UseEpilogRemainder,
312  const bool UnrollRemainder,
313  BasicBlock *InsertTop,
314  BasicBlock *InsertBot, BasicBlock *Preheader,
315  std::vector<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
316  ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI) {
317  StringRef suffix = UseEpilogRemainder ? "epil" : "prol";
318  BasicBlock *Header = L->getHeader();
319  BasicBlock *Latch = L->getLoopLatch();
320  Function *F = Header->getParent();
321  LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
322  LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
323  Loop *ParentLoop = L->getParentLoop();
324  NewLoopsMap NewLoops;
325  NewLoops[ParentLoop] = ParentLoop;
326 
327  // For each block in the original loop, create a new copy,
328  // and update the value map with the newly created values.
329  for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
330  BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, "." + suffix, F);
331  NewBlocks.push_back(NewBB);
332 
333  addClonedBlockToLoopInfo(*BB, NewBB, LI, NewLoops);
334 
335  VMap[*BB] = NewBB;
336  if (Header == *BB) {
337  // For the first block, add a CFG connection to this newly
338  // created block.
339  InsertTop->getTerminator()->setSuccessor(0, NewBB);
340  }
341 
342  if (DT) {
343  if (Header == *BB) {
344  // The header is dominated by the preheader.
345  DT->addNewBlock(NewBB, InsertTop);
346  } else {
347  // Copy information from original loop to unrolled loop.
348  BasicBlock *IDomBB = DT->getNode(*BB)->getIDom()->getBlock();
349  DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDomBB]));
350  }
351  }
352 
353  if (Latch == *BB) {
354  // For the last block, create a loop back to cloned head.
355  VMap.erase((*BB)->getTerminator());
356  BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]);
357  BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());
358  IRBuilder<> Builder(LatchBR);
359  PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2,
360  suffix + ".iter",
361  FirstLoopBB->getFirstNonPHI());
362  Value *IdxSub =
363  Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
364  NewIdx->getName() + ".sub");
365  Value *IdxCmp =
366  Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp");
367  Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot);
368  NewIdx->addIncoming(NewIter, InsertTop);
369  NewIdx->addIncoming(IdxSub, NewBB);
370  LatchBR->eraseFromParent();
371  }
372  }
373 
374  // Change the incoming values to the ones defined in the preheader or
375  // cloned loop.
376  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
377  PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
378  unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
379  NewPHI->setIncomingBlock(idx, InsertTop);
380  BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
381  idx = NewPHI->getBasicBlockIndex(Latch);
382  Value *InVal = NewPHI->getIncomingValue(idx);
383  NewPHI->setIncomingBlock(idx, NewLatch);
384  if (Value *V = VMap.lookup(InVal))
385  NewPHI->setIncomingValue(idx, V);
386  }
387 
388  Loop *NewLoop = NewLoops[L];
389  assert(NewLoop && "L should have been cloned");
390  MDNode *LoopID = NewLoop->getLoopID();
391 
392  // Only add loop metadata if the loop is not going to be completely
393  // unrolled.
394  if (UnrollRemainder)
395  return NewLoop;
396 
399  if (NewLoopID.hasValue()) {
400  NewLoop->setLoopID(NewLoopID.getValue());
401 
402  // Do not setLoopAlreadyUnrolled if loop attributes have been defined
403  // explicitly.
404  return NewLoop;
405  }
406 
407  // Add unroll disable metadata to disable future unrolling for this loop.
408  NewLoop->setLoopAlreadyUnrolled();
409  return NewLoop;
410 }
411 
412 /// Returns true if we can safely unroll a multi-exit/exiting loop. OtherExits
413 /// is populated with all the loop exit blocks other than the LatchExit block.
414 static bool canSafelyUnrollMultiExitLoop(Loop *L, BasicBlock *LatchExit,
415  bool PreserveLCSSA,
416  bool UseEpilogRemainder) {
417 
418  // We currently have some correctness constrains in unrolling a multi-exit
419  // loop. Check for these below.
420 
421  // We rely on LCSSA form being preserved when the exit blocks are transformed.
422  // (Note that only an off-by-default mode of the old PM disables PreserveLCCA.)
423  if (!PreserveLCSSA)
424  return false;
425 
426  // All constraints have been satisfied.
427  return true;
428 }
429 
430 /// Returns true if we can profitably unroll the multi-exit loop L. Currently,
431 /// we return true only if UnrollRuntimeMultiExit is set to true.
433  Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,
434  bool PreserveLCSSA, bool UseEpilogRemainder) {
435 
436 #if !defined(NDEBUG)
437  assert(canSafelyUnrollMultiExitLoop(L, LatchExit, PreserveLCSSA,
438  UseEpilogRemainder) &&
439  "Should be safe to unroll before checking profitability!");
440 #endif
441 
442  // Priority goes to UnrollRuntimeMultiExit if it's supplied.
444  return UnrollRuntimeMultiExit;
445 
446  // TODO: We used to bail out for correctness (now fixed). Under what
447  // circumstances is this case profitable to allow?
448  if (!LatchExit->getSinglePredecessor())
449  return false;
450 
451  // TODO: We used to bail out for correctness (now fixed). Under what
452  // circumstances is this case profitable to allow?
453  if (UseEpilogRemainder && L->getParentLoop())
454  return false;
455 
456  // The main pain point with multi-exit loop unrolling is that once unrolled,
457  // we will not be able to merge all blocks into a straight line code.
458  // There are branches within the unrolled loop that go to the OtherExits.
459  // The second point is the increase in code size, but this is true
460  // irrespective of multiple exits.
461 
462  // Note: Both the heuristics below are coarse grained. We are essentially
463  // enabling unrolling of loops that have a single side exit other than the
464  // normal LatchExit (i.e. exiting into a deoptimize block).
465  // The heuristics considered are:
466  // 1. low number of branches in the unrolled version.
467  // 2. high predictability of these extra branches.
468  // We avoid unrolling loops that have more than two exiting blocks. This
469  // limits the total number of branches in the unrolled loop to be atmost
470  // the unroll factor (since one of the exiting blocks is the latch block).
471  SmallVector<BasicBlock*, 4> ExitingBlocks;
472  L->getExitingBlocks(ExitingBlocks);
473  if (ExitingBlocks.size() > 2)
474  return false;
475 
476  // Allow unrolling of loops with no non latch exit blocks.
477  if (OtherExits.size() == 0)
478  return true;
479 
480  // The second heuristic is that L has one exit other than the latchexit and
481  // that exit is a deoptimize block. We know that deoptimize blocks are rarely
482  // taken, which also implies the branch leading to the deoptimize block is
483  // highly predictable. When UnrollRuntimeOtherExitPredictable is specified, we
484  // assume the other exit branch is predictable even if it has no deoptimize
485  // call.
486  return (OtherExits.size() == 1 &&
488  OtherExits[0]->getTerminatingDeoptimizeCall()));
489  // TODO: These can be fine-tuned further to consider code size or deopt states
490  // that are captured by the deoptimize exit block.
491  // Also, we can extend this to support more cases, if we actually
492  // know of kinds of multiexit loops that would benefit from unrolling.
493 }
494 
495 // Assign the maximum possible trip count as the back edge weight for the
496 // remainder loop if the original loop comes with a branch weight.
498  Loop *RemainderLoop,
499  uint64_t UnrollFactor) {
500  uint64_t TrueWeight, FalseWeight;
501  BranchInst *LatchBR =
502  cast<BranchInst>(OrigLoop->getLoopLatch()->getTerminator());
503  if (!LatchBR->extractProfMetadata(TrueWeight, FalseWeight))
504  return;
505  uint64_t ExitWeight = LatchBR->getSuccessor(0) == OrigLoop->getHeader()
506  ? FalseWeight
507  : TrueWeight;
508  assert(UnrollFactor > 1);
509  uint64_t BackEdgeWeight = (UnrollFactor - 1) * ExitWeight;
510  BasicBlock *Header = RemainderLoop->getHeader();
511  BasicBlock *Latch = RemainderLoop->getLoopLatch();
512  auto *RemainderLatchBR = cast<BranchInst>(Latch->getTerminator());
513  unsigned HeaderIdx = (RemainderLatchBR->getSuccessor(0) == Header ? 0 : 1);
514  MDBuilder MDB(RemainderLatchBR->getContext());
515  MDNode *WeightNode =
516  HeaderIdx ? MDB.createBranchWeights(ExitWeight, BackEdgeWeight)
517  : MDB.createBranchWeights(BackEdgeWeight, ExitWeight);
518  RemainderLatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
519 }
520 
521 /// Calculate ModVal = (BECount + 1) % Count on the abstract integer domain
522 /// accounting for the possibility of unsigned overflow in the 2s complement
523 /// domain. Preconditions:
524 /// 1) TripCount = BECount + 1 (allowing overflow)
525 /// 2) Log2(Count) <= BitWidth(BECount)
527  Value *TripCount, unsigned Count) {
528  // Note that TripCount is BECount + 1.
529  if (isPowerOf2_32(Count))
530  // If the expression is zero, then either:
531  // 1. There are no iterations to be run in the prolog/epilog loop.
532  // OR
533  // 2. The addition computing TripCount overflowed.
534  //
535  // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
536  // the number of iterations that remain to be run in the original loop is a
537  // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (a
538  // precondition of this method).
539  return B.CreateAnd(TripCount, Count - 1, "xtraiter");
540 
541  // As (BECount + 1) can potentially unsigned overflow we count
542  // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
543  Constant *CountC = ConstantInt::get(BECount->getType(), Count);
544  Value *ModValTmp = B.CreateURem(BECount, CountC);
545  Value *ModValAdd = B.CreateAdd(ModValTmp,
546  ConstantInt::get(ModValTmp->getType(), 1));
547  // At that point (BECount % Count) + 1 could be equal to Count.
548  // To handle this case we need to take mod by Count one more time.
549  return B.CreateURem(ModValAdd, CountC, "xtraiter");
550 }
551 
552 
553 /// Insert code in the prolog/epilog code when unrolling a loop with a
554 /// run-time trip-count.
555 ///
556 /// This method assumes that the loop unroll factor is total number
557 /// of loop bodies in the loop after unrolling. (Some folks refer
558 /// to the unroll factor as the number of *extra* copies added).
559 /// We assume also that the loop unroll factor is a power-of-two. So, after
560 /// unrolling the loop, the number of loop bodies executed is 2,
561 /// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch
562 /// instruction in SimplifyCFG.cpp. Then, the backend decides how code for
563 /// the switch instruction is generated.
564 ///
565 /// ***Prolog case***
566 /// extraiters = tripcount % loopfactor
567 /// if (extraiters == 0) jump Loop:
568 /// else jump Prol:
569 /// Prol: LoopBody;
570 /// extraiters -= 1 // Omitted if unroll factor is 2.
571 /// if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
572 /// if (tripcount < loopfactor) jump End:
573 /// Loop:
574 /// ...
575 /// End:
576 ///
577 /// ***Epilog case***
578 /// extraiters = tripcount % loopfactor
579 /// if (tripcount < loopfactor) jump LoopExit:
580 /// unroll_iters = tripcount - extraiters
581 /// Loop: LoopBody; (executes unroll_iter times);
582 /// unroll_iter -= 1
583 /// if (unroll_iter != 0) jump Loop:
584 /// LoopExit:
585 /// if (extraiters == 0) jump EpilExit:
586 /// Epil: LoopBody; (executes extraiters times)
587 /// extraiters -= 1 // Omitted if unroll factor is 2.
588 /// if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
589 /// EpilExit:
590 
592  Loop *L, unsigned Count, bool AllowExpensiveTripCount,
593  bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,
595  const TargetTransformInfo *TTI, bool PreserveLCSSA, Loop **ResultLoop) {
596  LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");
597  LLVM_DEBUG(L->dump());
598  LLVM_DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"
599  : dbgs() << "Using prolog remainder.\n");
600 
601  // Make sure the loop is in canonical form.
602  if (!L->isLoopSimplifyForm()) {
603  LLVM_DEBUG(dbgs() << "Not in simplify form!\n");
604  return false;
605  }
606 
607  // Guaranteed by LoopSimplifyForm.
608  BasicBlock *Latch = L->getLoopLatch();
609  BasicBlock *Header = L->getHeader();
610 
611  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
612 
613  if (!LatchBR || LatchBR->isUnconditional()) {
614  // The loop-rotate pass can be helpful to avoid this in many cases.
615  LLVM_DEBUG(
616  dbgs()
617  << "Loop latch not terminated by a conditional branch.\n");
618  return false;
619  }
620 
621  unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 1 : 0;
622  BasicBlock *LatchExit = LatchBR->getSuccessor(ExitIndex);
623 
624  if (L->contains(LatchExit)) {
625  // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
626  // targets of the Latch be an exit block out of the loop.
627  LLVM_DEBUG(
628  dbgs()
629  << "One of the loop latch successors must be the exit block.\n");
630  return false;
631  }
632 
633  // These are exit blocks other than the target of the latch exiting block.
634  SmallVector<BasicBlock *, 4> OtherExits;
635  L->getUniqueNonLatchExitBlocks(OtherExits);
636  bool isMultiExitUnrollingEnabled =
637  canSafelyUnrollMultiExitLoop(L, LatchExit, PreserveLCSSA,
638  UseEpilogRemainder) &&
639  canProfitablyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
640  UseEpilogRemainder);
641  // Support only single exit and exiting block unless multi-exit loop unrolling is enabled.
642  if (!isMultiExitUnrollingEnabled &&
643  (!L->getExitingBlock() || OtherExits.size())) {
644  LLVM_DEBUG(
645  dbgs()
646  << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
647  "enabled!\n");
648  return false;
649  }
650  // Use Scalar Evolution to compute the trip count. This allows more loops to
651  // be unrolled than relying on induction var simplification.
652  if (!SE)
653  return false;
654 
655  // Only unroll loops with a computable trip count, and the trip count needs
656  // to be an int value (allowing a pointer type is a TODO item).
657  // We calculate the backedge count by using getExitCount on the Latch block,
658  // which is proven to be the only exiting block in this loop. This is same as
659  // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
660  // exiting blocks).
661  const SCEV *BECountSC = SE->getExitCount(L, Latch);
662  if (isa<SCEVCouldNotCompute>(BECountSC) ||
663  !BECountSC->getType()->isIntegerTy()) {
664  LLVM_DEBUG(dbgs() << "Could not compute exit block SCEV\n");
665  return false;
666  }
667 
668  unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
669 
670  // Add 1 since the backedge count doesn't include the first loop iteration.
671  // (Note that overflow can occur, this is handled explicitly below)
672  const SCEV *TripCountSC =
673  SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
674  if (isa<SCEVCouldNotCompute>(TripCountSC)) {
675  LLVM_DEBUG(dbgs() << "Could not compute trip count SCEV.\n");
676  return false;
677  }
678 
679  BasicBlock *PreHeader = L->getLoopPreheader();
680  BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
681  const DataLayout &DL = Header->getModule()->getDataLayout();
682  SCEVExpander Expander(*SE, DL, "loop-unroll");
683  if (!AllowExpensiveTripCount &&
684  Expander.isHighCostExpansion(TripCountSC, L, SCEVCheapExpansionBudget,
685  TTI, PreHeaderBR)) {
686  LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");
687  return false;
688  }
689 
690  // This constraint lets us deal with an overflowing trip count easily; see the
691  // comment on ModVal below.
692  if (Log2_32(Count) > BEWidth) {
693  LLVM_DEBUG(
694  dbgs()
695  << "Count failed constraint on overflow trip count calculation.\n");
696  return false;
697  }
698 
699  // Loop structure is the following:
700  //
701  // PreHeader
702  // Header
703  // ...
704  // Latch
705  // LatchExit
706 
707  BasicBlock *NewPreHeader;
708  BasicBlock *NewExit = nullptr;
709  BasicBlock *PrologExit = nullptr;
710  BasicBlock *EpilogPreHeader = nullptr;
711  BasicBlock *PrologPreHeader = nullptr;
712 
713  if (UseEpilogRemainder) {
714  // If epilog remainder
715  // Split PreHeader to insert a branch around loop for unrolling.
716  NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
717  NewPreHeader->setName(PreHeader->getName() + ".new");
718  // Split LatchExit to create phi nodes from branch above.
719  NewExit = SplitBlockPredecessors(LatchExit, {Latch}, ".unr-lcssa", DT, LI,
720  nullptr, PreserveLCSSA);
721  // NewExit gets its DebugLoc from LatchExit, which is not part of the
722  // original Loop.
723  // Fix this by setting Loop's DebugLoc to NewExit.
724  auto *NewExitTerminator = NewExit->getTerminator();
725  NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());
726  // Split NewExit to insert epilog remainder loop.
727  EpilogPreHeader = SplitBlock(NewExit, NewExitTerminator, DT, LI);
728  EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
729 
730  // If the latch exits from multiple level of nested loops, then
731  // by assumption there must be another loop exit which branches to the
732  // outer loop and we must adjust the loop for the newly inserted blocks
733  // to account for the fact that our epilogue is still in the same outer
734  // loop. Note that this leaves loopinfo temporarily out of sync with the
735  // CFG until the actual epilogue loop is inserted.
736  if (auto *ParentL = L->getParentLoop())
737  if (LI->getLoopFor(LatchExit) != ParentL) {
738  LI->removeBlock(NewExit);
739  ParentL->addBasicBlockToLoop(NewExit, *LI);
740  LI->removeBlock(EpilogPreHeader);
741  ParentL->addBasicBlockToLoop(EpilogPreHeader, *LI);
742  }
743 
744  } else {
745  // If prolog remainder
746  // Split the original preheader twice to insert prolog remainder loop
747  PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
748  PrologPreHeader->setName(Header->getName() + ".prol.preheader");
749  PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
750  DT, LI);
751  PrologExit->setName(Header->getName() + ".prol.loopexit");
752  // Split PrologExit to get NewPreHeader.
753  NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
754  NewPreHeader->setName(PreHeader->getName() + ".new");
755  }
756  // Loop structure should be the following:
757  // Epilog Prolog
758  //
759  // PreHeader PreHeader
760  // *NewPreHeader *PrologPreHeader
761  // Header *PrologExit
762  // ... *NewPreHeader
763  // Latch Header
764  // *NewExit ...
765  // *EpilogPreHeader Latch
766  // LatchExit LatchExit
767 
768  // Calculate conditions for branch around loop for unrolling
769  // in epilog case and around prolog remainder loop in prolog case.
770  // Compute the number of extra iterations required, which is:
771  // extra iterations = run-time trip count % loop unroll factor
772  PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
773  Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
774  PreHeaderBR);
775  Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
776  PreHeaderBR);
777  IRBuilder<> B(PreHeaderBR);
778  Value * const ModVal = CreateTripRemainder(B, BECount, TripCount, Count);
779 
780  Value *BranchVal =
781  UseEpilogRemainder ? B.CreateICmpULT(BECount,
782  ConstantInt::get(BECount->getType(),
783  Count - 1)) :
784  B.CreateIsNotNull(ModVal, "lcmp.mod");
785  BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
786  BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
787  // Branch to either remainder (extra iterations) loop or unrolling loop.
788  B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
789  PreHeaderBR->eraseFromParent();
790  if (DT) {
791  if (UseEpilogRemainder)
792  DT->changeImmediateDominator(NewExit, PreHeader);
793  else
794  DT->changeImmediateDominator(PrologExit, PreHeader);
795  }
796  Function *F = Header->getParent();
797  // Get an ordered list of blocks in the loop to help with the ordering of the
798  // cloned blocks in the prolog/epilog code
799  LoopBlocksDFS LoopBlocks(L);
800  LoopBlocks.perform(LI);
801 
802  //
803  // For each extra loop iteration, create a copy of the loop's basic blocks
804  // and generate a condition that branches to the copy depending on the
805  // number of 'left over' iterations.
806  //
807  std::vector<BasicBlock *> NewBlocks;
808  ValueToValueMapTy VMap;
809 
810  // Clone all the basic blocks in the loop. If Count is 2, we don't clone
811  // the loop, otherwise we create a cloned loop to execute the extra
812  // iterations. This function adds the appropriate CFG connections.
813  BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;
814  BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
815  Loop *remainderLoop = CloneLoopBlocks(
816  L, ModVal, UseEpilogRemainder, UnrollRemainder, InsertTop, InsertBot,
817  NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
818 
819  // Assign the maximum possible trip count as the back edge weight for the
820  // remainder loop if the original loop comes with a branch weight.
821  if (remainderLoop && !UnrollRemainder)
822  updateLatchBranchWeightsForRemainderLoop(L, remainderLoop, Count);
823 
824  // Insert the cloned blocks into the function.
825  F->getBasicBlockList().splice(InsertBot->getIterator(),
826  F->getBasicBlockList(),
827  NewBlocks[0]->getIterator(),
828  F->end());
829 
830  // Now the loop blocks are cloned and the other exiting blocks from the
831  // remainder are connected to the original Loop's exit blocks. The remaining
832  // work is to update the phi nodes in the original loop, and take in the
833  // values from the cloned region.
834  for (auto *BB : OtherExits) {
835  // Given we preserve LCSSA form, we know that the values used outside the
836  // loop will be used through these phi nodes at the exit blocks that are
837  // transformed below.
838  for (PHINode &PN : BB->phis()) {
839  unsigned oldNumOperands = PN.getNumIncomingValues();
840  // Add the incoming values from the remainder code to the end of the phi
841  // node.
842  for (unsigned i = 0; i < oldNumOperands; i++){
843  auto *PredBB =PN.getIncomingBlock(i);
844  if (PredBB == Latch)
845  // The latch exit is handled seperately, see connectX
846  continue;
847  if (!L->contains(PredBB))
848  // Even if we had dedicated exits, the code above inserted an
849  // extra branch which can reach the latch exit.
850  continue;
851 
852  auto *V = PN.getIncomingValue(i);
853  if (Instruction *I = dyn_cast<Instruction>(V))
854  if (L->contains(I))
855  V = VMap.lookup(I);
856  PN.addIncoming(V, cast<BasicBlock>(VMap[PredBB]));
857  }
858  }
859 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
860  for (BasicBlock *SuccBB : successors(BB)) {
861  assert(!(any_of(OtherExits,
862  [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) ||
863  SuccBB == LatchExit) &&
864  "Breaks the definition of dedicated exits!");
865  }
866 #endif
867  }
868 
869  // Update the immediate dominator of the exit blocks and blocks that are
870  // reachable from the exit blocks. This is needed because we now have paths
871  // from both the original loop and the remainder code reaching the exit
872  // blocks. While the IDom of these exit blocks were from the original loop,
873  // now the IDom is the preheader (which decides whether the original loop or
874  // remainder code should run).
875  if (DT && !L->getExitingBlock()) {
876  SmallVector<BasicBlock *, 16> ChildrenToUpdate;
877  // NB! We have to examine the dom children of all loop blocks, not just
878  // those which are the IDom of the exit blocks. This is because blocks
879  // reachable from the exit blocks can have their IDom as the nearest common
880  // dominator of the exit blocks.
881  for (auto *BB : L->blocks()) {
882  auto *DomNodeBB = DT->getNode(BB);
883  for (auto *DomChild : DomNodeBB->children()) {
884  auto *DomChildBB = DomChild->getBlock();
885  if (!L->contains(LI->getLoopFor(DomChildBB)))
886  ChildrenToUpdate.push_back(DomChildBB);
887  }
888  }
889  for (auto *BB : ChildrenToUpdate)
890  DT->changeImmediateDominator(BB, PreHeader);
891  }
892 
893  // Loop structure should be the following:
894  // Epilog Prolog
895  //
896  // PreHeader PreHeader
897  // NewPreHeader PrologPreHeader
898  // Header PrologHeader
899  // ... ...
900  // Latch PrologLatch
901  // NewExit PrologExit
902  // EpilogPreHeader NewPreHeader
903  // EpilogHeader Header
904  // ... ...
905  // EpilogLatch Latch
906  // LatchExit LatchExit
907 
908  // Rewrite the cloned instruction operands to use the values created when the
909  // clone is created.
910  for (BasicBlock *BB : NewBlocks) {
911  for (Instruction &I : *BB) {
912  RemapInstruction(&I, VMap,
914  }
915  }
916 
917  if (UseEpilogRemainder) {
918  // Connect the epilog code to the original loop and update the
919  // PHI functions.
920  ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader,
921  EpilogPreHeader, NewPreHeader, VMap, DT, LI,
922  PreserveLCSSA);
923 
924  // Update counter in loop for unrolling.
925  // I should be multiply of Count.
926  IRBuilder<> B2(NewPreHeader->getTerminator());
927  Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
928  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
929  B2.SetInsertPoint(LatchBR);
930  PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
931  Header->getFirstNonPHI());
932  Value *IdxSub =
933  B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
934  NewIdx->getName() + ".nsub");
935  Value *IdxCmp;
936  if (LatchBR->getSuccessor(0) == Header)
937  IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
938  else
939  IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
940  NewIdx->addIncoming(TestVal, NewPreHeader);
941  NewIdx->addIncoming(IdxSub, Latch);
942  LatchBR->setCondition(IdxCmp);
943  } else {
944  // Connect the prolog code to the original loop and update the
945  // PHI functions.
946  ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,
947  NewPreHeader, VMap, DT, LI, PreserveLCSSA);
948  }
949 
950  // If this loop is nested, then the loop unroller changes the code in the any
951  // of its parent loops, so the Scalar Evolution pass needs to be run again.
952  SE->forgetTopmostLoop(L);
953 
954  // Verify that the Dom Tree and Loop Info are correct.
955 #if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
956  if (DT) {
958  LI->verify(*DT);
959  }
960 #endif
961 
962  // For unroll factor 2 remainder loop will have 1 iteration.
963  if (Count == 2 && DT && LI && SE) {
964  // TODO: This code could probably be pulled out into a helper function
965  // (e.g. breakLoopBackedgeAndSimplify) and reused in loop-deletion.
966  BasicBlock *RemainderLatch = remainderLoop->getLoopLatch();
967  assert(RemainderLatch);
968  SmallVector<BasicBlock*> RemainderBlocks(remainderLoop->getBlocks().begin(),
969  remainderLoop->getBlocks().end());
970  breakLoopBackedge(remainderLoop, *DT, *SE, *LI, nullptr);
971  remainderLoop = nullptr;
972 
973  // Simplify loop values after breaking the backedge
974  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
976  for (BasicBlock *BB : RemainderBlocks) {
977  for (Instruction &Inst : llvm::make_early_inc_range(*BB)) {
978  if (Value *V = SimplifyInstruction(&Inst, {DL, nullptr, DT, AC}))
979  if (LI->replacementPreservesLCSSAForm(&Inst, V))
980  Inst.replaceAllUsesWith(V);
981  if (isInstructionTriviallyDead(&Inst))
982  DeadInsts.emplace_back(&Inst);
983  }
984  // We can't do recursive deletion until we're done iterating, as we might
985  // have a phi which (potentially indirectly) uses instructions later in
986  // the block we're iterating through.
988  }
989 
990  // Merge latch into exit block.
991  auto *ExitBB = RemainderLatch->getSingleSuccessor();
992  assert(ExitBB && "required after breaking cond br backedge");
994  MergeBlockIntoPredecessor(ExitBB, &DTU, LI);
995  }
996 
997  // Canonicalize to LoopSimplifyForm both original and remainder loops. We
998  // cannot rely on the LoopUnrollPass to do this because it only does
999  // canonicalization for parent/subloops and not the sibling loops.
1000  if (OtherExits.size() > 0) {
1001  // Generate dedicated exit blocks for the original loop, to preserve
1002  // LoopSimplifyForm.
1003  formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA);
1004  // Generate dedicated exit blocks for the remainder loop if one exists, to
1005  // preserve LoopSimplifyForm.
1006  if (remainderLoop)
1007  formDedicatedExitBlocks(remainderLoop, DT, LI, nullptr, PreserveLCSSA);
1008  }
1009 
1010  auto UnrollResult = LoopUnrollResult::Unmodified;
1011  if (remainderLoop && UnrollRemainder) {
1012  LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");
1013  UnrollResult =
1014  UnrollLoop(remainderLoop,
1015  {/*Count*/ Count - 1, /*Force*/ false, /*Runtime*/ false,
1016  /*AllowExpensiveTripCount*/ false,
1017  /*UnrollRemainder*/ false, ForgetAllSCEV},
1018  LI, SE, DT, AC, TTI, /*ORE*/ nullptr, PreserveLCSSA);
1019  }
1020 
1021  if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)
1022  *ResultLoop = remainderLoop;
1023  NumRuntimeUnrolled++;
1024  return true;
1025 }
UnrollRuntimeMultiExit
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"))
i
i
Definition: README.txt:29
llvm::RecursivelyDeleteTriviallyDeadInstructions
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:511
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm::IRBuilderBase::SetInsertPoint
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:184
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::DominatorTreeBase::findNearestCommonDominator
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
Definition: GenericDomTree.h:468
llvm::addClonedBlockToLoopInfo
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:136
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
Metadata.h
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
ScalarEvolutionExpander.h
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:63
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:689
Statistic.h
llvm::LLVMLoopUnrollFollowupRemainder
const char *const LLVMLoopUnrollFollowupRemainder
Definition: UnrollLoop.h:44
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::IRBuilder<>
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
llvm::makeFollowupLoopID
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:271
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::SCEVExpander::expandCodeFor
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
Definition: ScalarEvolutionExpander.h:275
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
ConnectProlog
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.
Definition: LoopUnrollRuntime.cpp:72
ScalarEvolution.h
Module.h
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:294
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::Optional
Definition: APInt.h:33
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
llvm::isPowerOf2_32
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:491
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::JumpTable::Full
@ Full
Definition: TargetOptions.h:50
llvm::PHINode::setIncomingValue
void setIncomingValue(unsigned i, Value *V)
Definition: Instructions.h:2724
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::LoopBlocksDFS::beginRPO
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:288
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
canSafelyUnrollMultiExitLoop
static bool canSafelyUnrollMultiExitLoop(Loop *L, BasicBlock *LatchExit, bool PreserveLCSSA, bool UseEpilogRemainder)
Returns true if we can safely unroll a multi-exit/exiting loop.
Definition: LoopUnrollRuntime.cpp:414
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::RemapInstruction
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:253
llvm::Loop::setLoopAlreadyUnrolled
void setLoopAlreadyUnrolled()
Add llvm.loop.unroll.disable to this loop's loop id metadata.
Definition: LoopInfo.cpp:539
llvm::SCEVExpander::isHighCostExpansion
bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget, const TargetTransformInfo *TTI, const Instruction *At)
Return true for expressions that can't be evaluated at runtime within given Budget.
Definition: ScalarEvolutionExpander.h:238
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2721
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::MDBuilder::createBranchWeights
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
Definition: MDBuilder.cpp:37
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
llvm::LoopInfo::replacementPreservesLCSSAForm
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:1115
llvm::Log2_32
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:596
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:171
llvm::Instruction
Definition: Instruction.h:45
llvm::LoopBlocksDFS::endRPO
RPOIterator endRPO() const
Definition: LoopIterator.h:140
UnrollRuntimeOtherExitPredictable
static cl::opt< bool > UnrollRuntimeOtherExitPredictable("unroll-runtime-other-exit-predictable", cl::init(false), cl::Hidden, cl::desc("Assume the non latch exit block to be predictable"))
llvm::BranchInst::setCondition
void setCondition(Value *V)
Definition: Instructions.h:3146
llvm::SimplifyInstruction
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6291
MDBuilder.h
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:364
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1771
llvm::cl::Option::getNumOccurrences
int getNumOccurrences() const
Definition: CommandLine.h:404
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::ConstantInt::get
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:900
LoopUtils.h
SmallPtrSet.h
llvm::SplitBlockPredecessors
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, 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...
Definition: BasicBlockUtils.cpp:1148
llvm::BasicBlock::getModule
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:144
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: GenericDomTree.h:655
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:212
Utils.h
llvm::Instruction::extractProfMetadata
bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) const
Retrieve the raw weight values of a conditional branch or select.
Definition: Metadata.cpp:1396
llvm::RF_NoModuleLevelChanges
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:72
LoopIterator.h
llvm::LoopUnrollResult::FullyUnrolled
@ FullyUnrolled
The loop was fully unrolled into straight-line code.
llvm::breakLoopBackedge
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Definition: LoopUtils.cpp:704
CreateTripRemainder
static Value * CreateTripRemainder(IRBuilder<> &B, Value *BECount, Value *TripCount, unsigned Count)
Calculate ModVal = (BECount + 1) % Count on the abstract integer domain accounting for the possibilit...
Definition: LoopUnrollRuntime.cpp:526
llvm::LLVMLoopUnrollFollowupAll
const char *const LLVMLoopUnrollFollowupAll
Definition: UnrollLoop.h:41
llvm::LoopBlocksDFS::RPOIterator
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:101
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:201
llvm::LoopBlocksDFS
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:478
llvm::CloneBasicBlock
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...
Definition: CloneFunction.cpp:43
BasicBlock.h
llvm::cl::opt< bool >
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::UnrollLoop
LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const llvm::TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr)
Unroll the given loop by Count.
Definition: LoopUnroll.cpp:258
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
uint64_t
llvm::PHINode::setIncomingBlock
void setIncomingBlock(unsigned i, BasicBlock *BB)
Definition: Instructions.h:2760
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2775
llvm::ValueMap::erase
bool erase(const KeyT &Val)
Definition: ValueMap.h:191
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
Cloning.h
llvm::IRBuilderBase::CreateIsNotNull
Value * CreateIsNotNull(Value *Arg, const Twine &Name="")
Return an i1 value testing if Arg is not null.
Definition: IRBuilder.h:2538
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:572
llvm::PHINode::getBasicBlockIndex
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Definition: Instructions.h:2803
llvm::SCEVCheapExpansionBudget
cl::opt< unsigned > SCEVCheapExpansionBudget
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1220
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PHINode::setIncomingValueForBlock
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
Definition: Instructions.h:2817
updateLatchBranchWeightsForRemainderLoop
static void updateLatchBranchWeightsForRemainderLoop(Loop *OrigLoop, Loop *RemainderLoop, uint64_t UnrollFactor)
Definition: LoopUnrollRuntime.cpp:497
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:163
llvm::ScalarEvolution::forgetTopmostLoop
void forgetTopmostLoop(const Loop *L)
Definition: ScalarEvolution.cpp:7509
llvm::MDNode
Metadata node.
Definition: Metadata.h:901
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3138
llvm::UnrollRuntimeLoopRemainder
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, bool PreserveLCSSA, Loop **ResultLoop=nullptr)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
Definition: LoopUnrollRuntime.cpp:591
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:398
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::MergeBlockIntoPredecessor
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
Definition: BasicBlockUtils.cpp:173
llvm::any_of
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:1554
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::Instruction::setSuccessor
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Definition: Instruction.cpp:789
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:446
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::BasicBlock::getTerminator
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:148
llvm::LoopBase::getUniqueNonLatchExitBlocks
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:129
llvm::DominatorTreeBase::addNewBlock
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
Definition: GenericDomTree.h:619
llvm::RF_IgnoreMissingLocals
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition: ValueMapper.h:90
llvm::SplitEdge
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
Definition: BasicBlockUtils.cpp:493
llvm::formDedicatedExitBlocks
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:62
llvm::Loop::setLoopID
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:527
llvm::IRBuilderBase::CreateIsNull
Value * CreateIsNull(Value *Arg, const Twine &Name="")
Return an i1 value testing if Arg is null.
Definition: IRBuilder.h:2532
llvm::PHINode::Create
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...
Definition: Instructions.h:2667
llvm::Loop::getLoopID
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:503
canProfitablyUnrollMultiExitLoop
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.
Definition: LoopUnrollRuntime.cpp:432
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::Loop::dump
void dump() const
Definition: LoopInfo.cpp:669
llvm::MDBuilder
Definition: MDBuilder.h:35
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:370
Dominators.h
UnrollLoop.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
InstructionSimplify.h
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
llvm::PHINode
Definition: Instructions.h:2625
llvm::SmallVectorImpl< BasicBlock * >
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:401
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:379
llvm::ScalarEvolution::getAddExpr
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.
Definition: ScalarEvolution.cpp:2419
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::ValueMap::lookup
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
CloneLoopBlocks
static Loop * CloneLoopBlocks(Loop *L, Value *NewIter, 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.
Definition: LoopUnrollRuntime.cpp:311
llvm::IRBuilderBase::CreateSub
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1229
llvm::cl::desc
Definition: CommandLine.h:414
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3060
llvm::LoopUnrollResult::Unmodified
@ Unmodified
The loop was not modified.
raw_ostream.h
BasicBlockUtils.h
llvm::SplitBlock
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
Definition: BasicBlockUtils.cpp:814
ConnectEpilog
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.
Definition: LoopUnrollRuntime.cpp:191
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::ScalarEvolution::getExitCount
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
Definition: ScalarEvolution.cpp:7265
Debug.h
llvm::Optional::getValue
constexpr const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:282
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3153
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908