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