LLVM  9.0.0svn
LoopUnroll.cpp
Go to the documentation of this file.
1 //===-- UnrollLoop.cpp - 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. It does not define any
10 // actual pass or policy, but provides a single function to perform loop
11 // unrolling.
12 //
13 // The process of unrolling can produce extraneous basic blocks linked with
14 // unconditional branches. This will be corrected in the future.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/Statistic.h"
26 #include "llvm/IR/BasicBlock.h"
27 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/Dominators.h"
30 #include "llvm/IR/IntrinsicInst.h"
31 #include "llvm/IR/LLVMContext.h"
32 #include "llvm/Support/Debug.h"
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "loop-unroll"
43 
44 // TODO: Should these be here or in LoopUnroll?
45 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
46 STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");
47 
48 static cl::opt<bool>
49 UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden,
50  cl::desc("Allow runtime unrolled loops to be unrolled "
51  "with epilog instead of prolog."));
52 
53 static cl::opt<bool>
54 UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden,
55  cl::desc("Verify domtree after unrolling"),
56 #ifdef EXPENSIVE_CHECKS
57  cl::init(true)
58 #else
59  cl::init(false)
60 #endif
61  );
62 
63 /// Convert the instruction operands from referencing the current values into
64 /// those specified by VMap.
66  for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) {
67  Value *Op = I->getOperand(op);
68 
69  // Unwrap arguments of dbg.value intrinsics.
70  bool Wrapped = false;
71  if (auto *V = dyn_cast<MetadataAsValue>(Op))
72  if (auto *Unwrapped = dyn_cast<ValueAsMetadata>(V->getMetadata())) {
73  Op = Unwrapped->getValue();
74  Wrapped = true;
75  }
76 
77  auto wrap = [&](Value *V) {
78  auto &C = I->getContext();
79  return Wrapped ? MetadataAsValue::get(C, ValueAsMetadata::get(V)) : V;
80  };
81 
82  ValueToValueMapTy::iterator It = VMap.find(Op);
83  if (It != VMap.end())
84  I->setOperand(op, wrap(It->second));
85  }
86 
87  if (PHINode *PN = dyn_cast<PHINode>(I)) {
88  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
89  ValueToValueMapTy::iterator It = VMap.find(PN->getIncomingBlock(i));
90  if (It != VMap.end())
91  PN->setIncomingBlock(i, cast<BasicBlock>(It->second));
92  }
93  }
94 }
95 
96 /// Check if unrolling created a situation where we need to insert phi nodes to
97 /// preserve LCSSA form.
98 /// \param Blocks is a vector of basic blocks representing unrolled loop.
99 /// \param L is the outer loop.
100 /// It's possible that some of the blocks are in L, and some are not. In this
101 /// case, if there is a use is outside L, and definition is inside L, we need to
102 /// insert a phi-node, otherwise LCSSA will be broken.
103 /// The function is just a helper function for llvm::UnrollLoop that returns
104 /// true if this situation occurs, indicating that LCSSA needs to be fixed.
105 static bool needToInsertPhisForLCSSA(Loop *L, std::vector<BasicBlock *> Blocks,
106  LoopInfo *LI) {
107  for (BasicBlock *BB : Blocks) {
108  if (LI->getLoopFor(BB) == L)
109  continue;
110  for (Instruction &I : *BB) {
111  for (Use &U : I.operands()) {
112  if (auto Def = dyn_cast<Instruction>(U)) {
113  Loop *DefLoop = LI->getLoopFor(Def->getParent());
114  if (!DefLoop)
115  continue;
116  if (DefLoop->contains(L))
117  return true;
118  }
119  }
120  }
121  }
122  return false;
123 }
124 
125 /// Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary
126 /// and adds a mapping from the original loop to the new loop to NewLoops.
127 /// Returns nullptr if no new loop was created and a pointer to the
128 /// original loop OriginalBB was part of otherwise.
130  BasicBlock *ClonedBB, LoopInfo *LI,
131  NewLoopsMap &NewLoops) {
132  // Figure out which loop New is in.
133  const Loop *OldLoop = LI->getLoopFor(OriginalBB);
134  assert(OldLoop && "Should (at least) be in the loop being unrolled!");
135 
136  Loop *&NewLoop = NewLoops[OldLoop];
137  if (!NewLoop) {
138  // Found a new sub-loop.
139  assert(OriginalBB == OldLoop->getHeader() &&
140  "Header should be first in RPO");
141 
142  NewLoop = LI->AllocateLoop();
143  Loop *NewLoopParent = NewLoops.lookup(OldLoop->getParentLoop());
144 
145  if (NewLoopParent)
146  NewLoopParent->addChildLoop(NewLoop);
147  else
148  LI->addTopLevelLoop(NewLoop);
149 
150  NewLoop->addBasicBlockToLoop(ClonedBB, *LI);
151  return OldLoop;
152  } else {
153  NewLoop->addBasicBlockToLoop(ClonedBB, *LI);
154  return nullptr;
155  }
156 }
157 
158 /// The function chooses which type of unroll (epilog or prolog) is more
159 /// profitabale.
160 /// Epilog unroll is more profitable when there is PHI that starts from
161 /// constant. In this case epilog will leave PHI start from constant,
162 /// but prolog will convert it to non-constant.
163 ///
164 /// loop:
165 /// PN = PHI [I, Latch], [CI, PreHeader]
166 /// I = foo(PN)
167 /// ...
168 ///
169 /// Epilog unroll case.
170 /// loop:
171 /// PN = PHI [I2, Latch], [CI, PreHeader]
172 /// I1 = foo(PN)
173 /// I2 = foo(I1)
174 /// ...
175 /// Prolog unroll case.
176 /// NewPN = PHI [PrologI, Prolog], [CI, PreHeader]
177 /// loop:
178 /// PN = PHI [I2, Latch], [NewPN, PreHeader]
179 /// I1 = foo(PN)
180 /// I2 = foo(I1)
181 /// ...
182 ///
183 static bool isEpilogProfitable(Loop *L) {
184  BasicBlock *PreHeader = L->getLoopPreheader();
185  BasicBlock *Header = L->getHeader();
186  assert(PreHeader && Header);
187  for (const PHINode &PN : Header->phis()) {
188  if (isa<ConstantInt>(PN.getIncomingValueForBlock(PreHeader)))
189  return true;
190  }
191  return false;
192 }
193 
194 /// Perform some cleanup and simplifications on loops after unrolling. It is
195 /// useful to simplify the IV's in the new loop, as well as do a quick
196 /// simplify/dce pass of the instructions.
197 void llvm::simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
199  AssumptionCache *AC) {
200  // Simplify any new induction variables in the partially unrolled loop.
201  if (SE && SimplifyIVs) {
203  simplifyLoopIVs(L, SE, DT, LI, DeadInsts);
204 
205  // Aggressively clean up dead instructions that simplifyLoopIVs already
206  // identified. Any remaining should be cleaned up below.
207  while (!DeadInsts.empty())
208  if (Instruction *Inst =
209  dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val()))
211  }
212 
213  // At this point, the code is well formed. We now do a quick sweep over the
214  // inserted code, doing constant propagation and dead code elimination as we
215  // go.
216  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
217  for (BasicBlock *BB : L->getBlocks()) {
218  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
219  Instruction *Inst = &*I++;
220 
221  if (Value *V = SimplifyInstruction(Inst, {DL, nullptr, DT, AC}))
222  if (LI->replacementPreservesLCSSAForm(Inst, V))
223  Inst->replaceAllUsesWith(V);
224  if (isInstructionTriviallyDead(Inst))
225  BB->getInstList().erase(Inst);
226  }
227  }
228 
229  // TODO: after peeling or unrolling, previously loop variant conditions are
230  // likely to fold to constants, eagerly propagating those here will require
231  // fewer cleanup passes to be run. Alternatively, a LoopEarlyCSE might be
232  // appropriate.
233 }
234 
235 /// Unroll the given loop by Count. The loop must be in LCSSA form. Unrolling
236 /// can only fail when the loop's latch block is not terminated by a conditional
237 /// branch instruction. However, if the trip count (and multiple) are not known,
238 /// loop unrolling will mostly produce more code that is no faster.
239 ///
240 /// TripCount is the upper bound of the iteration on which control exits
241 /// LatchBlock. Control may exit the loop prior to TripCount iterations either
242 /// via an early branch in other loop block or via LatchBlock terminator. This
243 /// is relaxed from the general definition of trip count which is the number of
244 /// times the loop header executes. Note that UnrollLoop assumes that the loop
245 /// counter test is in LatchBlock in order to remove unnecesssary instances of
246 /// the test. If control can exit the loop from the LatchBlock's terminator
247 /// prior to TripCount iterations, flag PreserveCondBr needs to be set.
248 ///
249 /// PreserveCondBr indicates whether the conditional branch of the LatchBlock
250 /// needs to be preserved. It is needed when we use trip count upper bound to
251 /// fully unroll the loop. If PreserveOnlyFirst is also set then only the first
252 /// conditional branch needs to be preserved.
253 ///
254 /// Similarly, TripMultiple divides the number of times that the LatchBlock may
255 /// execute without exiting the loop.
256 ///
257 /// If AllowRuntime is true then UnrollLoop will consider unrolling loops that
258 /// have a runtime (i.e. not compile time constant) trip count. Unrolling these
259 /// loops require a unroll "prologue" that runs "RuntimeTripCount % Count"
260 /// iterations before branching into the unrolled loop. UnrollLoop will not
261 /// runtime-unroll the loop if computing RuntimeTripCount will be expensive and
262 /// AllowExpensiveTripCount is false.
263 ///
264 /// If we want to perform PGO-based loop peeling, PeelCount is set to the
265 /// number of iterations we want to peel off.
266 ///
267 /// The LoopInfo Analysis that is passed will be kept consistent.
268 ///
269 /// This utility preserves LoopInfo. It will also preserve ScalarEvolution and
270 /// DominatorTree if they are non-null.
271 ///
272 /// If RemainderLoop is non-null, it will receive the remainder loop (if
273 /// required and not fully unrolled).
276  AssumptionCache *AC,
278  bool PreserveLCSSA, Loop **RemainderLoop) {
279 
280  BasicBlock *Preheader = L->getLoopPreheader();
281  if (!Preheader) {
282  LLVM_DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n");
284  }
285 
286  BasicBlock *LatchBlock = L->getLoopLatch();
287  if (!LatchBlock) {
288  LLVM_DEBUG(dbgs() << " Can't unroll; loop exit-block-insertion failed.\n");
290  }
291 
292  // Loops with indirectbr cannot be cloned.
293  if (!L->isSafeToClone()) {
294  LLVM_DEBUG(dbgs() << " Can't unroll; Loop body cannot be cloned.\n");
296  }
297 
298  // The current loop unroll pass can only unroll loops with a single latch
299  // that's a conditional branch exiting the loop.
300  // FIXME: The implementation can be extended to work with more complicated
301  // cases, e.g. loops with multiple latches.
302  BasicBlock *Header = L->getHeader();
303  BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator());
304 
305  if (!BI || BI->isUnconditional()) {
306  // The loop-rotate pass can be helpful to avoid this in many cases.
307  LLVM_DEBUG(
308  dbgs()
309  << " Can't unroll; loop not terminated by a conditional branch.\n");
311  }
312 
313  auto CheckSuccessors = [&](unsigned S1, unsigned S2) {
314  return BI->getSuccessor(S1) == Header && !L->contains(BI->getSuccessor(S2));
315  };
316 
317  if (!CheckSuccessors(0, 1) && !CheckSuccessors(1, 0)) {
318  LLVM_DEBUG(dbgs() << "Can't unroll; only loops with one conditional latch"
319  " exiting the loop can be unrolled\n");
321  }
322 
323  if (Header->hasAddressTaken()) {
324  // The loop-rotate pass can be helpful to avoid this in many cases.
325  LLVM_DEBUG(
326  dbgs() << " Won't unroll loop: address of header block is taken.\n");
328  }
329 
330  if (ULO.TripCount != 0)
331  LLVM_DEBUG(dbgs() << " Trip Count = " << ULO.TripCount << "\n");
332  if (ULO.TripMultiple != 1)
333  LLVM_DEBUG(dbgs() << " Trip Multiple = " << ULO.TripMultiple << "\n");
334 
335  // Effectively "DCE" unrolled iterations that are beyond the tripcount
336  // and will never be executed.
337  if (ULO.TripCount != 0 && ULO.Count > ULO.TripCount)
338  ULO.Count = ULO.TripCount;
339 
340  // Don't enter the unroll code if there is nothing to do.
341  if (ULO.TripCount == 0 && ULO.Count < 2 && ULO.PeelCount == 0) {
342  LLVM_DEBUG(dbgs() << "Won't unroll; almost nothing to do\n");
344  }
345 
346  assert(ULO.Count > 0);
347  assert(ULO.TripMultiple > 0);
348  assert(ULO.TripCount == 0 || ULO.TripCount % ULO.TripMultiple == 0);
349 
350  // Are we eliminating the loop control altogether?
351  bool CompletelyUnroll = ULO.Count == ULO.TripCount;
352  SmallVector<BasicBlock *, 4> ExitBlocks;
353  L->getExitBlocks(ExitBlocks);
354  std::vector<BasicBlock*> OriginalLoopBlocks = L->getBlocks();
355 
356  // Go through all exits of L and see if there are any phi-nodes there. We just
357  // conservatively assume that they're inserted to preserve LCSSA form, which
358  // means that complete unrolling might break this form. We need to either fix
359  // it in-place after the transformation, or entirely rebuild LCSSA. TODO: For
360  // now we just recompute LCSSA for the outer loop, but it should be possible
361  // to fix it in-place.
362  bool NeedToFixLCSSA = PreserveLCSSA && CompletelyUnroll &&
363  any_of(ExitBlocks, [](const BasicBlock *BB) {
364  return isa<PHINode>(BB->begin());
365  });
366 
367  // We assume a run-time trip count if the compiler cannot
368  // figure out the loop trip count and the unroll-runtime
369  // flag is specified.
370  bool RuntimeTripCount =
371  (ULO.TripCount == 0 && ULO.Count > 0 && ULO.AllowRuntime);
372 
373  assert((!RuntimeTripCount || !ULO.PeelCount) &&
374  "Did not expect runtime trip-count unrolling "
375  "and peeling for the same loop");
376 
377  bool Peeled = false;
378  if (ULO.PeelCount) {
379  Peeled = peelLoop(L, ULO.PeelCount, LI, SE, DT, AC, PreserveLCSSA);
380 
381  // Successful peeling may result in a change in the loop preheader/trip
382  // counts. If we later unroll the loop, we want these to be updated.
383  if (Peeled) {
384  BasicBlock *ExitingBlock = L->getExitingBlock();
385  assert(ExitingBlock && "Loop without exiting block?");
386  Preheader = L->getLoopPreheader();
387  ULO.TripCount = SE->getSmallConstantTripCount(L, ExitingBlock);
388  ULO.TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock);
389  }
390  }
391 
392  // Loops containing convergent instructions must have a count that divides
393  // their TripMultiple.
394  LLVM_DEBUG(
395  {
396  bool HasConvergent = false;
397  for (auto &BB : L->blocks())
398  for (auto &I : *BB)
399  if (auto CS = CallSite(&I))
400  HasConvergent |= CS.isConvergent();
401  assert((!HasConvergent || ULO.TripMultiple % ULO.Count == 0) &&
402  "Unroll count must divide trip multiple if loop contains a "
403  "convergent operation.");
404  });
405 
406  bool EpilogProfitability =
407  UnrollRuntimeEpilog.getNumOccurrences() ? UnrollRuntimeEpilog
408  : isEpilogProfitable(L);
409 
410  if (RuntimeTripCount && ULO.TripMultiple % ULO.Count != 0 &&
412  EpilogProfitability, ULO.UnrollRemainder,
413  ULO.ForgetAllSCEV, LI, SE, DT, AC,
414  PreserveLCSSA, RemainderLoop)) {
415  if (ULO.Force)
416  RuntimeTripCount = false;
417  else {
418  LLVM_DEBUG(dbgs() << "Won't unroll; remainder loop could not be "
419  "generated when assuming runtime trip count\n");
421  }
422  }
423 
424  // If we know the trip count, we know the multiple...
425  unsigned BreakoutTrip = 0;
426  if (ULO.TripCount != 0) {
427  BreakoutTrip = ULO.TripCount % ULO.Count;
428  ULO.TripMultiple = 0;
429  } else {
430  // Figure out what multiple to use.
431  BreakoutTrip = ULO.TripMultiple =
433  }
434 
435  using namespace ore;
436  // Report the unrolling decision.
437  if (CompletelyUnroll) {
438  LLVM_DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()
439  << " with trip count " << ULO.TripCount << "!\n");
440  if (ORE)
441  ORE->emit([&]() {
442  return OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(),
443  L->getHeader())
444  << "completely unrolled loop with "
445  << NV("UnrollCount", ULO.TripCount) << " iterations";
446  });
447  } else if (ULO.PeelCount) {
448  LLVM_DEBUG(dbgs() << "PEELING loop %" << Header->getName()
449  << " with iteration count " << ULO.PeelCount << "!\n");
450  if (ORE)
451  ORE->emit([&]() {
452  return OptimizationRemark(DEBUG_TYPE, "Peeled", L->getStartLoc(),
453  L->getHeader())
454  << " peeled loop by " << NV("PeelCount", ULO.PeelCount)
455  << " iterations";
456  });
457  } else {
458  auto DiagBuilder = [&]() {
459  OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled", L->getStartLoc(),
460  L->getHeader());
461  return Diag << "unrolled loop by a factor of "
462  << NV("UnrollCount", ULO.Count);
463  };
464 
465  LLVM_DEBUG(dbgs() << "UNROLLING loop %" << Header->getName() << " by "
466  << ULO.Count);
467  if (ULO.TripMultiple == 0 || BreakoutTrip != ULO.TripMultiple) {
468  LLVM_DEBUG(dbgs() << " with a breakout at trip " << BreakoutTrip);
469  if (ORE)
470  ORE->emit([&]() {
471  return DiagBuilder() << " with a breakout at trip "
472  << NV("BreakoutTrip", BreakoutTrip);
473  });
474  } else if (ULO.TripMultiple != 1) {
475  LLVM_DEBUG(dbgs() << " with " << ULO.TripMultiple << " trips per branch");
476  if (ORE)
477  ORE->emit([&]() {
478  return DiagBuilder()
479  << " with " << NV("TripMultiple", ULO.TripMultiple)
480  << " trips per branch";
481  });
482  } else if (RuntimeTripCount) {
483  LLVM_DEBUG(dbgs() << " with run-time trip count");
484  if (ORE)
485  ORE->emit(
486  [&]() { return DiagBuilder() << " with run-time trip count"; });
487  }
488  LLVM_DEBUG(dbgs() << "!\n");
489  }
490 
491  // We are going to make changes to this loop. SCEV may be keeping cached info
492  // about it, in particular about backedge taken count. The changes we make
493  // are guaranteed to invalidate this information for our loop. It is tempting
494  // to only invalidate the loop being unrolled, but it is incorrect as long as
495  // all exiting branches from all inner loops have impact on the outer loops,
496  // and if something changes inside them then any of outer loops may also
497  // change. When we forget outermost loop, we also forget all contained loops
498  // and this is what we need here.
499  if (SE) {
500  if (ULO.ForgetAllSCEV)
501  SE->forgetAllLoops();
502  else
503  SE->forgetTopmostLoop(L);
504  }
505 
506  bool ContinueOnTrue = L->contains(BI->getSuccessor(0));
507  BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue);
508 
509  // For the first iteration of the loop, we should use the precloned values for
510  // PHI nodes. Insert associations now.
511  ValueToValueMapTy LastValueMap;
512  std::vector<PHINode*> OrigPHINode;
513  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
514  OrigPHINode.push_back(cast<PHINode>(I));
515  }
516 
517  std::vector<BasicBlock*> Headers;
518  std::vector<BasicBlock*> Latches;
519  Headers.push_back(Header);
520  Latches.push_back(LatchBlock);
521 
522  // The current on-the-fly SSA update requires blocks to be processed in
523  // reverse postorder so that LastValueMap contains the correct value at each
524  // exit.
525  LoopBlocksDFS DFS(L);
526  DFS.perform(LI);
527 
528  // Stash the DFS iterators before adding blocks to the loop.
529  LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();
530  LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();
531 
532  std::vector<BasicBlock*> UnrolledLoopBlocks = L->getBlocks();
533 
534  // Loop Unrolling might create new loops. While we do preserve LoopInfo, we
535  // might break loop-simplified form for these loops (as they, e.g., would
536  // share the same exit blocks). We'll keep track of loops for which we can
537  // break this so that later we can re-simplify them.
538  SmallSetVector<Loop *, 4> LoopsToSimplify;
539  for (Loop *SubLoop : *L)
540  LoopsToSimplify.insert(SubLoop);
541 
542  if (Header->getParent()->isDebugInfoForProfiling())
543  for (BasicBlock *BB : L->getBlocks())
544  for (Instruction &I : *BB)
545  if (!isa<DbgInfoIntrinsic>(&I))
546  if (const DILocation *DIL = I.getDebugLoc()) {
547  auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(ULO.Count);
548  if (NewDIL)
549  I.setDebugLoc(NewDIL.getValue());
550  else
551  LLVM_DEBUG(dbgs()
552  << "Failed to create new discriminator: "
553  << DIL->getFilename() << " Line: " << DIL->getLine());
554  }
555 
556  for (unsigned It = 1; It != ULO.Count; ++It) {
557  std::vector<BasicBlock*> NewBlocks;
559  NewLoops[L] = L;
560 
561  for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
562  ValueToValueMapTy VMap;
563  BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It));
564  Header->getParent()->getBasicBlockList().push_back(New);
565 
566  assert((*BB != Header || LI->getLoopFor(*BB) == L) &&
567  "Header should not be in a sub-loop");
568  // Tell LI about New.
569  const Loop *OldLoop = addClonedBlockToLoopInfo(*BB, New, LI, NewLoops);
570  if (OldLoop)
571  LoopsToSimplify.insert(NewLoops[OldLoop]);
572 
573  if (*BB == Header)
574  // Loop over all of the PHI nodes in the block, changing them to use
575  // the incoming values from the previous block.
576  for (PHINode *OrigPHI : OrigPHINode) {
577  PHINode *NewPHI = cast<PHINode>(VMap[OrigPHI]);
578  Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock);
579  if (Instruction *InValI = dyn_cast<Instruction>(InVal))
580  if (It > 1 && L->contains(InValI))
581  InVal = LastValueMap[InValI];
582  VMap[OrigPHI] = InVal;
583  New->getInstList().erase(NewPHI);
584  }
585 
586  // Update our running map of newest clones
587  LastValueMap[*BB] = New;
588  for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();
589  VI != VE; ++VI)
590  LastValueMap[VI->first] = VI->second;
591 
592  // Add phi entries for newly created values to all exit blocks.
593  for (BasicBlock *Succ : successors(*BB)) {
594  if (L->contains(Succ))
595  continue;
596  for (PHINode &PHI : Succ->phis()) {
597  Value *Incoming = PHI.getIncomingValueForBlock(*BB);
598  ValueToValueMapTy::iterator It = LastValueMap.find(Incoming);
599  if (It != LastValueMap.end())
600  Incoming = It->second;
601  PHI.addIncoming(Incoming, New);
602  }
603  }
604  // Keep track of new headers and latches as we create them, so that
605  // we can insert the proper branches later.
606  if (*BB == Header)
607  Headers.push_back(New);
608  if (*BB == LatchBlock)
609  Latches.push_back(New);
610 
611  NewBlocks.push_back(New);
612  UnrolledLoopBlocks.push_back(New);
613 
614  // Update DomTree: since we just copy the loop body, and each copy has a
615  // dedicated entry block (copy of the header block), this header's copy
616  // dominates all copied blocks. That means, dominance relations in the
617  // copied body are the same as in the original body.
618  if (DT) {
619  if (*BB == Header)
620  DT->addNewBlock(New, Latches[It - 1]);
621  else {
622  auto BBDomNode = DT->getNode(*BB);
623  auto BBIDom = BBDomNode->getIDom();
624  BasicBlock *OriginalBBIDom = BBIDom->getBlock();
625  DT->addNewBlock(
626  New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)]));
627  }
628  }
629  }
630 
631  // Remap all instructions in the most recent iteration
632  for (BasicBlock *NewBlock : NewBlocks) {
633  for (Instruction &I : *NewBlock) {
634  ::remapInstruction(&I, LastValueMap);
635  if (auto *II = dyn_cast<IntrinsicInst>(&I))
636  if (II->getIntrinsicID() == Intrinsic::assume)
637  AC->registerAssumption(II);
638  }
639  }
640  }
641 
642  // Loop over the PHI nodes in the original block, setting incoming values.
643  for (PHINode *PN : OrigPHINode) {
644  if (CompletelyUnroll) {
645  PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));
646  Header->getInstList().erase(PN);
647  } else if (ULO.Count > 1) {
648  Value *InVal = PN->removeIncomingValue(LatchBlock, false);
649  // If this value was defined in the loop, take the value defined by the
650  // last iteration of the loop.
651  if (Instruction *InValI = dyn_cast<Instruction>(InVal)) {
652  if (L->contains(InValI))
653  InVal = LastValueMap[InVal];
654  }
655  assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch");
656  PN->addIncoming(InVal, Latches.back());
657  }
658  }
659 
660  // Now that all the basic blocks for the unrolled iterations are in place,
661  // set up the branches to connect them.
662  for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
663  // The original branch was replicated in each unrolled iteration.
664  BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator());
665 
666  // The branch destination.
667  unsigned j = (i + 1) % e;
668  BasicBlock *Dest = Headers[j];
669  bool NeedConditional = true;
670 
671  if (RuntimeTripCount && j != 0) {
672  NeedConditional = false;
673  }
674 
675  // For a complete unroll, make the last iteration end with a branch
676  // to the exit block.
677  if (CompletelyUnroll) {
678  if (j == 0)
679  Dest = LoopExit;
680  // If using trip count upper bound to completely unroll, we need to keep
681  // the conditional branch except the last one because the loop may exit
682  // after any iteration.
683  assert(NeedConditional &&
684  "NeedCondition cannot be modified by both complete "
685  "unrolling and runtime unrolling");
686  NeedConditional =
687  (ULO.PreserveCondBr && j && !(ULO.PreserveOnlyFirst && i != 0));
688  } else if (j != BreakoutTrip &&
689  (ULO.TripMultiple == 0 || j % ULO.TripMultiple != 0)) {
690  // If we know the trip count or a multiple of it, we can safely use an
691  // unconditional branch for some iterations.
692  NeedConditional = false;
693  }
694 
695  if (NeedConditional) {
696  // Update the conditional branch's successor for the following
697  // iteration.
698  Term->setSuccessor(!ContinueOnTrue, Dest);
699  } else {
700  // Remove phi operands at this loop exit
701  if (Dest != LoopExit) {
702  BasicBlock *BB = Latches[i];
703  for (BasicBlock *Succ: successors(BB)) {
704  if (Succ == Headers[i])
705  continue;
706  for (PHINode &Phi : Succ->phis())
707  Phi.removeIncomingValue(BB, false);
708  }
709  }
710  // Replace the conditional branch with an unconditional one.
711  BranchInst::Create(Dest, Term);
712  Term->eraseFromParent();
713  }
714  }
715 
716  // Update dominators of blocks we might reach through exits.
717  // Immediate dominator of such block might change, because we add more
718  // routes which can lead to the exit: we can now reach it from the copied
719  // iterations too.
720  if (DT && ULO.Count > 1) {
721  for (auto *BB : OriginalLoopBlocks) {
722  auto *BBDomNode = DT->getNode(BB);
723  SmallVector<BasicBlock *, 16> ChildrenToUpdate;
724  for (auto *ChildDomNode : BBDomNode->getChildren()) {
725  auto *ChildBB = ChildDomNode->getBlock();
726  if (!L->contains(ChildBB))
727  ChildrenToUpdate.push_back(ChildBB);
728  }
729  BasicBlock *NewIDom;
730  if (BB == LatchBlock) {
731  // The latch is special because we emit unconditional branches in
732  // some cases where the original loop contained a conditional branch.
733  // Since the latch is always at the bottom of the loop, if the latch
734  // dominated an exit before unrolling, the new dominator of that exit
735  // must also be a latch. Specifically, the dominator is the first
736  // latch which ends in a conditional branch, or the last latch if
737  // there is no such latch.
738  NewIDom = Latches.back();
739  for (BasicBlock *IterLatch : Latches) {
740  Instruction *Term = IterLatch->getTerminator();
741  if (isa<BranchInst>(Term) && cast<BranchInst>(Term)->isConditional()) {
742  NewIDom = IterLatch;
743  break;
744  }
745  }
746  } else {
747  // The new idom of the block will be the nearest common dominator
748  // of all copies of the previous idom. This is equivalent to the
749  // nearest common dominator of the previous idom and the first latch,
750  // which dominates all copies of the previous idom.
751  NewIDom = DT->findNearestCommonDominator(BB, LatchBlock);
752  }
753  for (auto *ChildBB : ChildrenToUpdate)
754  DT->changeImmediateDominator(ChildBB, NewIDom);
755  }
756  }
757 
758  assert(!DT || !UnrollVerifyDomtree ||
760 
762  // Merge adjacent basic blocks, if possible.
763  for (BasicBlock *Latch : Latches) {
764  BranchInst *Term = cast<BranchInst>(Latch->getTerminator());
765  if (Term->isUnconditional()) {
766  BasicBlock *Dest = Term->getSuccessor(0);
767  BasicBlock *Fold = Dest->getUniquePredecessor();
768  if (MergeBlockIntoPredecessor(Dest, &DTU, LI)) {
769  // Dest has been folded into Fold. Update our worklists accordingly.
770  std::replace(Latches.begin(), Latches.end(), Dest, Fold);
771  UnrolledLoopBlocks.erase(std::remove(UnrolledLoopBlocks.begin(),
772  UnrolledLoopBlocks.end(), Dest),
773  UnrolledLoopBlocks.end());
774  }
775  }
776  }
777 
778  // At this point, the code is well formed. We now simplify the unrolled loop,
779  // doing constant propagation and dead code elimination as we go.
780  simplifyLoopAfterUnroll(L, !CompletelyUnroll && (ULO.Count > 1 || Peeled), LI,
781  SE, DT, AC);
782 
783  NumCompletelyUnrolled += CompletelyUnroll;
784  ++NumUnrolled;
785 
786  Loop *OuterL = L->getParentLoop();
787  // Update LoopInfo if the loop is completely removed.
788  if (CompletelyUnroll)
789  LI->erase(L);
790 
791  // After complete unrolling most of the blocks should be contained in OuterL.
792  // However, some of them might happen to be out of OuterL (e.g. if they
793  // precede a loop exit). In this case we might need to insert PHI nodes in
794  // order to preserve LCSSA form.
795  // We don't need to check this if we already know that we need to fix LCSSA
796  // form.
797  // TODO: For now we just recompute LCSSA for the outer loop in this case, but
798  // it should be possible to fix it in-place.
799  if (PreserveLCSSA && OuterL && CompletelyUnroll && !NeedToFixLCSSA)
800  NeedToFixLCSSA |= ::needToInsertPhisForLCSSA(OuterL, UnrolledLoopBlocks, LI);
801 
802  // If we have a pass and a DominatorTree we should re-simplify impacted loops
803  // to ensure subsequent analyses can rely on this form. We want to simplify
804  // at least one layer outside of the loop that was unrolled so that any
805  // changes to the parent loop exposed by the unrolling are considered.
806  if (DT) {
807  if (OuterL) {
808  // OuterL includes all loops for which we can break loop-simplify, so
809  // it's sufficient to simplify only it (it'll recursively simplify inner
810  // loops too).
811  if (NeedToFixLCSSA) {
812  // LCSSA must be performed on the outermost affected loop. The unrolled
813  // loop's last loop latch is guaranteed to be in the outermost loop
814  // after LoopInfo's been updated by LoopInfo::erase.
815  Loop *LatchLoop = LI->getLoopFor(Latches.back());
816  Loop *FixLCSSALoop = OuterL;
817  if (!FixLCSSALoop->contains(LatchLoop))
818  while (FixLCSSALoop->getParentLoop() != LatchLoop)
819  FixLCSSALoop = FixLCSSALoop->getParentLoop();
820 
821  formLCSSARecursively(*FixLCSSALoop, *DT, LI, SE);
822  } else if (PreserveLCSSA) {
823  assert(OuterL->isLCSSAForm(*DT) &&
824  "Loops should be in LCSSA form after loop-unroll.");
825  }
826 
827  // TODO: That potentially might be compile-time expensive. We should try
828  // to fix the loop-simplified form incrementally.
829  simplifyLoop(OuterL, DT, LI, SE, AC, nullptr, PreserveLCSSA);
830  } else {
831  // Simplify loops for which we might've broken loop-simplify form.
832  for (Loop *SubLoop : LoopsToSimplify)
833  simplifyLoop(SubLoop, DT, LI, SE, AC, nullptr, PreserveLCSSA);
834  }
835  }
836 
837  return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled
839 }
840 
841 /// Given an llvm.loop loop id metadata node, returns the loop hint metadata
842 /// node with the given name (for example, "llvm.loop.unroll.count"). If no
843 /// such metadata node exists, then nullptr is returned.
845  // First operand should refer to the loop id itself.
846  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
847  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
848 
849  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
850  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
851  if (!MD)
852  continue;
853 
854  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
855  if (!S)
856  continue;
857 
858  if (Name.equals(S->getString()))
859  return MD;
860  }
861  return nullptr;
862 }
uint64_t CallInst * C
unsigned getSmallConstantTripCount(const Loop *L)
Returns the maximum trip count of the loop if it is a single-exit loop and we can compute a small max...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:224
unsigned getSmallConstantTripMultiple(const Loop *L)
Returns the largest constant divisor of the trip count of the loop if it is a single-exit loop and we...
DiagnosticInfoOptimizationBase::Argument NV
uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B)
Return the greatest common divisor of the values using Euclid&#39;s algorithm.
Definition: MathExtras.h:562
iterator erase(iterator where)
Definition: ilist.h:265
static bool needToInsertPhisForLCSSA(Loop *L, std::vector< BasicBlock *> Blocks, LoopInfo *LI)
Check if unrolling created a situation where we need to insert phi nodes to preserve LCSSA form...
Definition: LoopUnroll.cpp:105
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr)
Attempts to merge a block into its predecessor, if possible.
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:409
The main scalar evolution driver.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:173
A cache of @llvm.assume calls within a function.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:720
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B...
BasicBlock * getSuccessor(unsigned i) const
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:863
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
#define op(i)
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
static cl::opt< bool > UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog."))
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:385
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:133
static cl::opt< bool > UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), cl::init(false))
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:858
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:815
RPOIterator endRPO() const
Definition: LoopIterator.h:140
BlockT * getHeader() const
Definition: LoopInfo.h:102
void getExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:250
bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, SmallVectorImpl< WeakTrackingVH > &Dead)
SimplifyLoopIVs - Simplify users of induction variables within this loop.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:246
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:909
iterator find(const KeyT &Val)
Definition: ValueMap.h:161
static bool isEpilogProfitable(Loop *L)
The function chooses which type of unroll (epilog or prolog) is more profitabale. ...
Definition: LoopUnroll.cpp:183
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
Debug location.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1061
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
void remapInstruction(Instruction *I, ValueToValueMapTy &VMap)
Convert the instruction operands from referencing the current values into those specified by VMap...
Definition: LoopUnroll.cpp:65
static MetadataAsValue * get(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:105
StringRef getString() const
Definition: Metadata.cpp:463
The loop was fully unrolled into straight-line code.
bool isDebugInfoForProfiling() const
Returns true if we should emit debug info for profiling.
Definition: Metadata.cpp:1508
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Conditional or Unconditional Branch instruction.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node&#39;s...
DomTreeNodeBase * getIDom() const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Value * getIncomingValueForBlock(const BasicBlock *BB) const
bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA)
Peel off the first PeelCount iterations of loop L.
Diagnostic information for applied optimization remarks.
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:1199
const Instruction & back() const
Definition: BasicBlock.h:282
static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New)
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:101
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:434
The loop was partially unrolled – we still have a loop, but with a smaller trip count.
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:569
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
iterator end()
Definition: ValueMap.h:141
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
Definition: BasicBlock.h:391
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:333
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:112
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA, Loop **ResultLoop=nullptr)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:42
static ValueAsMetadata * get(Value *V)
Definition: Metadata.cpp:348
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
LoopT * AllocateLoop(ArgsTy &&... Args)
Definition: LoopInfo.h:822
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
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:129
Store the result of a depth first search within basic blocks contained by a single loop...
Definition: LoopIterator.h:97
void push_back(pointer val)
Definition: ilist.h:311
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...
static void DFS(BasicBlock *Root, SetVector< BasicBlock *> &Set)
MDNode * GetUnrollMetadata(MDNode *LoopID, StringRef Name)
Given an llvm.loop loop id metadata node, returns the loop hint metadata node with the given name (fo...
Definition: LoopUnroll.cpp:844
LLVM_NODISCARD bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:160
LoopT * getParentLoop() const
Definition: LoopInfo.h:103
LLVMAttributeRef wrap(Attribute Attr)
Definition: Attributes.h:198
void registerAssumption(CallInst *CI)
Add an @llvm.assume intrinsic to this function&#39;s cache.
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:333
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:467
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:151
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr)
Unroll the given loop by Count.
Definition: LoopUnroll.cpp:274
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:649
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:324
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:432
bool isUnconditional() const
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:211
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:353
LLVM Value Representation.
Definition: Value.h:72
succ_range successors(Instruction *I)
Definition: CFG.h:259
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
The loop was not modified.
#define DEBUG_TYPE
Definition: LoopUnroll.cpp:42
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
A single uniqued string.
Definition: Metadata.h:603
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form...
Definition: LoopInfo.h:1000
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
#define LLVM_DEBUG(X)
Definition: Debug.h:122
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:158
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
The optimization diagnostic interface.
iterator begin()
Definition: ValueMap.h:140
void forgetTopmostLoop(const Loop *L)
LoopUnrollResult
Represents the result of a UnrollLoop invocation.
Definition: UnrollLoop.h:53
void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC)
Perform some cleanup and simplifications on loops after unrolling.
Definition: LoopUnroll.cpp:197