LLVM  14.0.0git
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/ArrayRef.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SetVector.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/ADT/StringRef.h"
26 #include "llvm/ADT/Twine.h"
32 #include "llvm/Analysis/LoopInfo.h"
36 #include "llvm/IR/BasicBlock.h"
37 #include "llvm/IR/CFG.h"
38 #include "llvm/IR/Constants.h"
40 #include "llvm/IR/DebugLoc.h"
41 #include "llvm/IR/DiagnosticInfo.h"
42 #include "llvm/IR/Dominators.h"
43 #include "llvm/IR/Function.h"
44 #include "llvm/IR/Instruction.h"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/IntrinsicInst.h"
47 #include "llvm/IR/Metadata.h"
48 #include "llvm/IR/Module.h"
49 #include "llvm/IR/Use.h"
50 #include "llvm/IR/User.h"
51 #include "llvm/IR/ValueHandle.h"
52 #include "llvm/IR/ValueMap.h"
53 #include "llvm/Support/Casting.h"
55 #include "llvm/Support/Debug.h"
67 #include <algorithm>
68 #include <assert.h>
69 #include <type_traits>
70 #include <vector>
71 
72 namespace llvm {
73 class DataLayout;
74 class Value;
75 } // namespace llvm
76 
77 using namespace llvm;
78 
79 #define DEBUG_TYPE "loop-unroll"
80 
81 // TODO: Should these be here or in LoopUnroll?
82 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
83 STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");
84 STATISTIC(NumUnrolledNotLatch, "Number of loops unrolled without a conditional "
85  "latch (completely or otherwise)");
86 
87 static cl::opt<bool>
88 UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden,
89  cl::desc("Allow runtime unrolled loops to be unrolled "
90  "with epilog instead of prolog."));
91 
92 static cl::opt<bool>
93 UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden,
94  cl::desc("Verify domtree after unrolling"),
95 #ifdef EXPENSIVE_CHECKS
96  cl::init(true)
97 #else
98  cl::init(false)
99 #endif
100  );
101 
102 /// Check if unrolling created a situation where we need to insert phi nodes to
103 /// preserve LCSSA form.
104 /// \param Blocks is a vector of basic blocks representing unrolled loop.
105 /// \param L is the outer loop.
106 /// It's possible that some of the blocks are in L, and some are not. In this
107 /// case, if there is a use is outside L, and definition is inside L, we need to
108 /// insert a phi-node, otherwise LCSSA will be broken.
109 /// The function is just a helper function for llvm::UnrollLoop that returns
110 /// true if this situation occurs, indicating that LCSSA needs to be fixed.
112  const std::vector<BasicBlock *> &Blocks,
113  LoopInfo *LI) {
114  for (BasicBlock *BB : Blocks) {
115  if (LI->getLoopFor(BB) == L)
116  continue;
117  for (Instruction &I : *BB) {
118  for (Use &U : I.operands()) {
119  if (const auto *Def = dyn_cast<Instruction>(U)) {
120  Loop *DefLoop = LI->getLoopFor(Def->getParent());
121  if (!DefLoop)
122  continue;
123  if (DefLoop->contains(L))
124  return true;
125  }
126  }
127  }
128  }
129  return false;
130 }
131 
132 /// Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary
133 /// and adds a mapping from the original loop to the new loop to NewLoops.
134 /// Returns nullptr if no new loop was created and a pointer to the
135 /// original loop OriginalBB was part of otherwise.
137  BasicBlock *ClonedBB, LoopInfo *LI,
138  NewLoopsMap &NewLoops) {
139  // Figure out which loop New is in.
140  const Loop *OldLoop = LI->getLoopFor(OriginalBB);
141  assert(OldLoop && "Should (at least) be in the loop being unrolled!");
142 
143  Loop *&NewLoop = NewLoops[OldLoop];
144  if (!NewLoop) {
145  // Found a new sub-loop.
146  assert(OriginalBB == OldLoop->getHeader() &&
147  "Header should be first in RPO");
148 
149  NewLoop = LI->AllocateLoop();
150  Loop *NewLoopParent = NewLoops.lookup(OldLoop->getParentLoop());
151 
152  if (NewLoopParent)
153  NewLoopParent->addChildLoop(NewLoop);
154  else
155  LI->addTopLevelLoop(NewLoop);
156 
157  NewLoop->addBasicBlockToLoop(ClonedBB, *LI);
158  return OldLoop;
159  } else {
160  NewLoop->addBasicBlockToLoop(ClonedBB, *LI);
161  return nullptr;
162  }
163 }
164 
165 /// The function chooses which type of unroll (epilog or prolog) is more
166 /// profitabale.
167 /// Epilog unroll is more profitable when there is PHI that starts from
168 /// constant. In this case epilog will leave PHI start from constant,
169 /// but prolog will convert it to non-constant.
170 ///
171 /// loop:
172 /// PN = PHI [I, Latch], [CI, PreHeader]
173 /// I = foo(PN)
174 /// ...
175 ///
176 /// Epilog unroll case.
177 /// loop:
178 /// PN = PHI [I2, Latch], [CI, PreHeader]
179 /// I1 = foo(PN)
180 /// I2 = foo(I1)
181 /// ...
182 /// Prolog unroll case.
183 /// NewPN = PHI [PrologI, Prolog], [CI, PreHeader]
184 /// loop:
185 /// PN = PHI [I2, Latch], [NewPN, PreHeader]
186 /// I1 = foo(PN)
187 /// I2 = foo(I1)
188 /// ...
189 ///
190 static bool isEpilogProfitable(Loop *L) {
191  BasicBlock *PreHeader = L->getLoopPreheader();
192  BasicBlock *Header = L->getHeader();
193  assert(PreHeader && Header);
194  for (const PHINode &PN : Header->phis()) {
195  if (isa<ConstantInt>(PN.getIncomingValueForBlock(PreHeader)))
196  return true;
197  }
198  return false;
199 }
200 
201 /// Perform some cleanup and simplifications on loops after unrolling. It is
202 /// useful to simplify the IV's in the new loop, as well as do a quick
203 /// simplify/dce pass of the instructions.
204 void llvm::simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
206  AssumptionCache *AC,
207  const TargetTransformInfo *TTI) {
208  // Simplify any new induction variables in the partially unrolled loop.
209  if (SE && SimplifyIVs) {
211  simplifyLoopIVs(L, SE, DT, LI, TTI, DeadInsts);
212 
213  // Aggressively clean up dead instructions that simplifyLoopIVs already
214  // identified. Any remaining should be cleaned up below.
215  while (!DeadInsts.empty()) {
216  Value *V = DeadInsts.pop_back_val();
217  if (Instruction *Inst = dyn_cast_or_null<Instruction>(V))
219  }
220  }
221 
222  // At this point, the code is well formed. Perform constprop, instsimplify,
223  // and dce.
224  const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
226  for (BasicBlock *BB : L->getBlocks()) {
227  for (Instruction &Inst : llvm::make_early_inc_range(*BB)) {
228  if (Value *V = SimplifyInstruction(&Inst, {DL, nullptr, DT, AC}))
229  if (LI->replacementPreservesLCSSAForm(&Inst, V))
230  Inst.replaceAllUsesWith(V);
231  if (isInstructionTriviallyDead(&Inst))
232  DeadInsts.emplace_back(&Inst);
233  }
234  // We can't do recursive deletion until we're done iterating, as we might
235  // have a phi which (potentially indirectly) uses instructions later in
236  // the block we're iterating through.
238  }
239 }
240 
241 /// Unroll the given loop by Count. The loop must be in LCSSA form. Unrolling
242 /// can only fail when the loop's latch block is not terminated by a conditional
243 /// branch instruction. However, if the trip count (and multiple) are not known,
244 /// loop unrolling will mostly produce more code that is no faster.
245 ///
246 /// If Runtime is true then UnrollLoop will try to insert a prologue or
247 /// epilogue that ensures the latch has a trip multiple of Count. UnrollLoop
248 /// will not runtime-unroll the loop if computing the run-time trip count will
249 /// be expensive and AllowExpensiveTripCount is false.
250 ///
251 /// The LoopInfo Analysis that is passed will be kept consistent.
252 ///
253 /// This utility preserves LoopInfo. It will also preserve ScalarEvolution and
254 /// DominatorTree if they are non-null.
255 ///
256 /// If RemainderLoop is non-null, it will receive the remainder loop (if
257 /// required and not fully unrolled).
260  AssumptionCache *AC,
261  const TargetTransformInfo *TTI,
263  bool PreserveLCSSA, Loop **RemainderLoop) {
264  assert(DT && "DomTree is required");
265 
266  if (!L->getLoopPreheader()) {
267  LLVM_DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n");
269  }
270 
271  if (!L->getLoopLatch()) {
272  LLVM_DEBUG(dbgs() << " Can't unroll; loop exit-block-insertion failed.\n");
274  }
275 
276  // Loops with indirectbr cannot be cloned.
277  if (!L->isSafeToClone()) {
278  LLVM_DEBUG(dbgs() << " Can't unroll; Loop body cannot be cloned.\n");
280  }
281 
282  if (L->getHeader()->hasAddressTaken()) {
283  // The loop-rotate pass can be helpful to avoid this in many cases.
284  LLVM_DEBUG(
285  dbgs() << " Won't unroll loop: address of header block is taken.\n");
287  }
288 
289  assert(ULO.Count > 0);
290 
291  // All these values should be taken only after peeling because they might have
292  // changed.
293  BasicBlock *Preheader = L->getLoopPreheader();
294  BasicBlock *Header = L->getHeader();
295  BasicBlock *LatchBlock = L->getLoopLatch();
296  SmallVector<BasicBlock *, 4> ExitBlocks;
297  L->getExitBlocks(ExitBlocks);
298  std::vector<BasicBlock *> OriginalLoopBlocks = L->getBlocks();
299 
300  const unsigned MaxTripCount = SE->getSmallConstantMaxTripCount(L);
301  const bool MaxOrZero = SE->isBackedgeTakenCountMaxOrZero(L);
302 
303  // Effectively "DCE" unrolled iterations that are beyond the max tripcount
304  // and will never be executed.
305  if (MaxTripCount && ULO.Count > MaxTripCount)
306  ULO.Count = MaxTripCount;
307 
308  struct ExitInfo {
309  unsigned TripCount;
310  unsigned TripMultiple;
311  unsigned BreakoutTrip;
312  bool ExitOnTrue;
313  SmallVector<BasicBlock *> ExitingBlocks;
314  };
316  SmallVector<BasicBlock *, 4> ExitingBlocks;
317  L->getExitingBlocks(ExitingBlocks);
318  for (auto *ExitingBlock : ExitingBlocks) {
319  // The folding code is not prepared to deal with non-branch instructions
320  // right now.
321  auto *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
322  if (!BI)
323  continue;
324 
325  ExitInfo &Info = ExitInfos.try_emplace(ExitingBlock).first->second;
326  Info.TripCount = SE->getSmallConstantTripCount(L, ExitingBlock);
327  Info.TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock);
328  if (Info.TripCount != 0) {
329  Info.BreakoutTrip = Info.TripCount % ULO.Count;
330  Info.TripMultiple = 0;
331  } else {
332  Info.BreakoutTrip = Info.TripMultiple =
333  (unsigned)GreatestCommonDivisor64(ULO.Count, Info.TripMultiple);
334  }
335  Info.ExitOnTrue = !L->contains(BI->getSuccessor(0));
336  Info.ExitingBlocks.push_back(ExitingBlock);
337  LLVM_DEBUG(dbgs() << " Exiting block %" << ExitingBlock->getName()
338  << ": TripCount=" << Info.TripCount
339  << ", TripMultiple=" << Info.TripMultiple
340  << ", BreakoutTrip=" << Info.BreakoutTrip << "\n");
341  }
342 
343  // Are we eliminating the loop control altogether? Note that we can know
344  // we're eliminating the backedge without knowing exactly which iteration
345  // of the unrolled body exits.
346  const bool CompletelyUnroll = ULO.Count == MaxTripCount;
347 
348  const bool PreserveOnlyFirst = CompletelyUnroll && MaxOrZero;
349 
350  // There's no point in performing runtime unrolling if this unroll count
351  // results in a full unroll.
352  if (CompletelyUnroll)
353  ULO.Runtime = false;
354 
355  // Go through all exits of L and see if there are any phi-nodes there. We just
356  // conservatively assume that they're inserted to preserve LCSSA form, which
357  // means that complete unrolling might break this form. We need to either fix
358  // it in-place after the transformation, or entirely rebuild LCSSA. TODO: For
359  // now we just recompute LCSSA for the outer loop, but it should be possible
360  // to fix it in-place.
361  bool NeedToFixLCSSA =
362  PreserveLCSSA && CompletelyUnroll &&
363  any_of(ExitBlocks,
364  [](const BasicBlock *BB) { return isa<PHINode>(BB->begin()); });
365 
366  // The current loop unroll pass can unroll loops that have
367  // (1) single latch; and
368  // (2a) latch is unconditional; or
369  // (2b) latch is conditional and is an exiting block
370  // FIXME: The implementation can be extended to work with more complicated
371  // cases, e.g. loops with multiple latches.
372  BranchInst *LatchBI = dyn_cast<BranchInst>(LatchBlock->getTerminator());
373 
374  // A conditional branch which exits the loop, which can be optimized to an
375  // unconditional branch in the unrolled loop in some cases.
376  bool LatchIsExiting = L->isLoopExiting(LatchBlock);
377  if (!LatchBI || (LatchBI->isConditional() && !LatchIsExiting)) {
378  LLVM_DEBUG(
379  dbgs() << "Can't unroll; a conditional latch must exit the loop");
381  }
382 
383  // Loops containing convergent instructions cannot use runtime unrolling,
384  // as the prologue/epilogue may add additional control-dependencies to
385  // convergent operations.
386  LLVM_DEBUG(
387  {
388  bool HasConvergent = false;
389  for (auto &BB : L->blocks())
390  for (auto &I : *BB)
391  if (auto *CB = dyn_cast<CallBase>(&I))
392  HasConvergent |= CB->isConvergent();
393  assert((!HasConvergent || !ULO.Runtime) &&
394  "Can't runtime unroll if loop contains a convergent operation.");
395  });
396 
397  bool EpilogProfitability =
399  : isEpilogProfitable(L);
400 
401  if (ULO.Runtime &&
403  EpilogProfitability, ULO.UnrollRemainder,
404  ULO.ForgetAllSCEV, LI, SE, DT, AC, TTI,
405  PreserveLCSSA, RemainderLoop)) {
406  if (ULO.Force)
407  ULO.Runtime = false;
408  else {
409  LLVM_DEBUG(dbgs() << "Won't unroll; remainder loop could not be "
410  "generated when assuming runtime trip count\n");
412  }
413  }
414 
415  using namespace ore;
416  // Report the unrolling decision.
417  if (CompletelyUnroll) {
418  LLVM_DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()
419  << " with trip count " << ULO.Count << "!\n");
420  if (ORE)
421  ORE->emit([&]() {
422  return OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(),
423  L->getHeader())
424  << "completely unrolled loop with "
425  << NV("UnrollCount", ULO.Count) << " iterations";
426  });
427  } else {
428  LLVM_DEBUG(dbgs() << "UNROLLING loop %" << Header->getName() << " by "
429  << ULO.Count);
430  if (ULO.Runtime)
431  LLVM_DEBUG(dbgs() << " with run-time trip count");
432  LLVM_DEBUG(dbgs() << "!\n");
433 
434  if (ORE)
435  ORE->emit([&]() {
436  OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled", L->getStartLoc(),
437  L->getHeader());
438  Diag << "unrolled loop by a factor of " << NV("UnrollCount", ULO.Count);
439  if (ULO.Runtime)
440  Diag << " with run-time trip count";
441  return Diag;
442  });
443  }
444 
445  // We are going to make changes to this loop. SCEV may be keeping cached info
446  // about it, in particular about backedge taken count. The changes we make
447  // are guaranteed to invalidate this information for our loop. It is tempting
448  // to only invalidate the loop being unrolled, but it is incorrect as long as
449  // all exiting branches from all inner loops have impact on the outer loops,
450  // and if something changes inside them then any of outer loops may also
451  // change. When we forget outermost loop, we also forget all contained loops
452  // and this is what we need here.
453  if (SE) {
454  if (ULO.ForgetAllSCEV)
455  SE->forgetAllLoops();
456  else
457  SE->forgetTopmostLoop(L);
458  }
459 
460  if (!LatchIsExiting)
461  ++NumUnrolledNotLatch;
462 
463  // For the first iteration of the loop, we should use the precloned values for
464  // PHI nodes. Insert associations now.
465  ValueToValueMapTy LastValueMap;
466  std::vector<PHINode*> OrigPHINode;
467  for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
468  OrigPHINode.push_back(cast<PHINode>(I));
469  }
470 
471  std::vector<BasicBlock *> Headers;
472  std::vector<BasicBlock *> Latches;
473  Headers.push_back(Header);
474  Latches.push_back(LatchBlock);
475 
476  // The current on-the-fly SSA update requires blocks to be processed in
477  // reverse postorder so that LastValueMap contains the correct value at each
478  // exit.
479  LoopBlocksDFS DFS(L);
480  DFS.perform(LI);
481 
482  // Stash the DFS iterators before adding blocks to the loop.
483  LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();
484  LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();
485 
486  std::vector<BasicBlock*> UnrolledLoopBlocks = L->getBlocks();
487 
488  // Loop Unrolling might create new loops. While we do preserve LoopInfo, we
489  // might break loop-simplified form for these loops (as they, e.g., would
490  // share the same exit blocks). We'll keep track of loops for which we can
491  // break this so that later we can re-simplify them.
492  SmallSetVector<Loop *, 4> LoopsToSimplify;
493  for (Loop *SubLoop : *L)
494  LoopsToSimplify.insert(SubLoop);
495 
496  // When a FSDiscriminator is enabled, we don't need to add the multiply
497  // factors to the discriminators.
499  for (BasicBlock *BB : L->getBlocks())
500  for (Instruction &I : *BB)
501  if (!isa<DbgInfoIntrinsic>(&I))
502  if (const DILocation *DIL = I.getDebugLoc()) {
503  auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(ULO.Count);
504  if (NewDIL)
505  I.setDebugLoc(NewDIL.getValue());
506  else
507  LLVM_DEBUG(dbgs()
508  << "Failed to create new discriminator: "
509  << DIL->getFilename() << " Line: " << DIL->getLine());
510  }
511 
512  // Identify what noalias metadata is inside the loop: if it is inside the
513  // loop, the associated metadata must be cloned for each iteration.
514  SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;
515  identifyNoAliasScopesToClone(L->getBlocks(), LoopLocalNoAliasDeclScopes);
516 
517  for (unsigned It = 1; It != ULO.Count; ++It) {
520  NewLoops[L] = L;
521 
522  for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
523  ValueToValueMapTy VMap;
524  BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It));
525  Header->getParent()->getBasicBlockList().push_back(New);
526 
527  assert((*BB != Header || LI->getLoopFor(*BB) == L) &&
528  "Header should not be in a sub-loop");
529  // Tell LI about New.
530  const Loop *OldLoop = addClonedBlockToLoopInfo(*BB, New, LI, NewLoops);
531  if (OldLoop)
532  LoopsToSimplify.insert(NewLoops[OldLoop]);
533 
534  if (*BB == Header)
535  // Loop over all of the PHI nodes in the block, changing them to use
536  // the incoming values from the previous block.
537  for (PHINode *OrigPHI : OrigPHINode) {
538  PHINode *NewPHI = cast<PHINode>(VMap[OrigPHI]);
539  Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock);
540  if (Instruction *InValI = dyn_cast<Instruction>(InVal))
541  if (It > 1 && L->contains(InValI))
542  InVal = LastValueMap[InValI];
543  VMap[OrigPHI] = InVal;
544  New->getInstList().erase(NewPHI);
545  }
546 
547  // Update our running map of newest clones
548  LastValueMap[*BB] = New;
549  for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();
550  VI != VE; ++VI)
551  LastValueMap[VI->first] = VI->second;
552 
553  // Add phi entries for newly created values to all exit blocks.
554  for (BasicBlock *Succ : successors(*BB)) {
555  if (L->contains(Succ))
556  continue;
557  for (PHINode &PHI : Succ->phis()) {
558  Value *Incoming = PHI.getIncomingValueForBlock(*BB);
559  ValueToValueMapTy::iterator It = LastValueMap.find(Incoming);
560  if (It != LastValueMap.end())
561  Incoming = It->second;
562  PHI.addIncoming(Incoming, New);
563  }
564  }
565  // Keep track of new headers and latches as we create them, so that
566  // we can insert the proper branches later.
567  if (*BB == Header)
568  Headers.push_back(New);
569  if (*BB == LatchBlock)
570  Latches.push_back(New);
571 
572  // Keep track of the exiting block and its successor block contained in
573  // the loop for the current iteration.
574  auto ExitInfoIt = ExitInfos.find(*BB);
575  if (ExitInfoIt != ExitInfos.end())
576  ExitInfoIt->second.ExitingBlocks.push_back(New);
577 
578  NewBlocks.push_back(New);
579  UnrolledLoopBlocks.push_back(New);
580 
581  // Update DomTree: since we just copy the loop body, and each copy has a
582  // dedicated entry block (copy of the header block), this header's copy
583  // dominates all copied blocks. That means, dominance relations in the
584  // copied body are the same as in the original body.
585  if (*BB == Header)
586  DT->addNewBlock(New, Latches[It - 1]);
587  else {
588  auto BBDomNode = DT->getNode(*BB);
589  auto BBIDom = BBDomNode->getIDom();
590  BasicBlock *OriginalBBIDom = BBIDom->getBlock();
591  DT->addNewBlock(
592  New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)]));
593  }
594  }
595 
596  // Remap all instructions in the most recent iteration
597  remapInstructionsInBlocks(NewBlocks, LastValueMap);
598  for (BasicBlock *NewBlock : NewBlocks)
599  for (Instruction &I : *NewBlock)
600  if (auto *II = dyn_cast<AssumeInst>(&I))
601  AC->registerAssumption(II);
602 
603  {
604  // Identify what other metadata depends on the cloned version. After
605  // cloning, replace the metadata with the corrected version for both
606  // memory instructions and noalias intrinsics.
607  std::string ext = (Twine("It") + Twine(It)).str();
608  cloneAndAdaptNoAliasScopes(LoopLocalNoAliasDeclScopes, NewBlocks,
609  Header->getContext(), ext);
610  }
611  }
612 
613  // Loop over the PHI nodes in the original block, setting incoming values.
614  for (PHINode *PN : OrigPHINode) {
615  if (CompletelyUnroll) {
616  PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));
617  Header->getInstList().erase(PN);
618  } else if (ULO.Count > 1) {
619  Value *InVal = PN->removeIncomingValue(LatchBlock, false);
620  // If this value was defined in the loop, take the value defined by the
621  // last iteration of the loop.
622  if (Instruction *InValI = dyn_cast<Instruction>(InVal)) {
623  if (L->contains(InValI))
624  InVal = LastValueMap[InVal];
625  }
626  assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch");
627  PN->addIncoming(InVal, Latches.back());
628  }
629  }
630 
631  // Connect latches of the unrolled iterations to the headers of the next
632  // iteration. Currently they point to the header of the same iteration.
633  for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
634  unsigned j = (i + 1) % e;
635  Latches[i]->getTerminator()->replaceSuccessorWith(Headers[i], Headers[j]);
636  }
637 
638  // Update dominators of blocks we might reach through exits.
639  // Immediate dominator of such block might change, because we add more
640  // routes which can lead to the exit: we can now reach it from the copied
641  // iterations too.
642  if (ULO.Count > 1) {
643  for (auto *BB : OriginalLoopBlocks) {
644  auto *BBDomNode = DT->getNode(BB);
645  SmallVector<BasicBlock *, 16> ChildrenToUpdate;
646  for (auto *ChildDomNode : BBDomNode->children()) {
647  auto *ChildBB = ChildDomNode->getBlock();
648  if (!L->contains(ChildBB))
649  ChildrenToUpdate.push_back(ChildBB);
650  }
651  // The new idom of the block will be the nearest common dominator
652  // of all copies of the previous idom. This is equivalent to the
653  // nearest common dominator of the previous idom and the first latch,
654  // which dominates all copies of the previous idom.
655  BasicBlock *NewIDom = DT->findNearestCommonDominator(BB, LatchBlock);
656  for (auto *ChildBB : ChildrenToUpdate)
657  DT->changeImmediateDominator(ChildBB, NewIDom);
658  }
659  }
660 
663 
665 
666  auto SetDest = [&](BasicBlock *Src, bool WillExit, bool ExitOnTrue) {
667  auto *Term = cast<BranchInst>(Src->getTerminator());
668  const unsigned Idx = ExitOnTrue ^ WillExit;
669  BasicBlock *Dest = Term->getSuccessor(Idx);
670  BasicBlock *DeadSucc = Term->getSuccessor(1-Idx);
671 
672  // Remove predecessors from all non-Dest successors.
673  DeadSucc->removePredecessor(Src, /* KeepOneInputPHIs */ true);
674 
675  // Replace the conditional branch with an unconditional one.
676  BranchInst::Create(Dest, Term);
677  Term->eraseFromParent();
678 
679  DTU.applyUpdates({{DominatorTree::Delete, Src, DeadSucc}});
680  };
681 
682  auto WillExit = [&](const ExitInfo &Info, unsigned i, unsigned j,
683  bool IsLatch) -> Optional<bool> {
684  if (CompletelyUnroll) {
685  if (PreserveOnlyFirst) {
686  if (i == 0)
687  return None;
688  return j == 0;
689  }
690  // Complete (but possibly inexact) unrolling
691  if (j == 0)
692  return true;
693  if (Info.TripCount && j != Info.TripCount)
694  return false;
695  return None;
696  }
697 
698  if (ULO.Runtime) {
699  // If runtime unrolling inserts a prologue, information about non-latch
700  // exits may be stale.
701  if (IsLatch && j != 0)
702  return false;
703  return None;
704  }
705 
706  if (j != Info.BreakoutTrip &&
707  (Info.TripMultiple == 0 || j % Info.TripMultiple != 0)) {
708  // If we know the trip count or a multiple of it, we can safely use an
709  // unconditional branch for some iterations.
710  return false;
711  }
712  return None;
713  };
714 
715  // Fold branches for iterations where we know that they will exit or not
716  // exit.
717  for (const auto &Pair : ExitInfos) {
718  const ExitInfo &Info = Pair.second;
719  for (unsigned i = 0, e = Info.ExitingBlocks.size(); i != e; ++i) {
720  // The branch destination.
721  unsigned j = (i + 1) % e;
722  bool IsLatch = Pair.first == LatchBlock;
723  Optional<bool> KnownWillExit = WillExit(Info, i, j, IsLatch);
724  if (!KnownWillExit)
725  continue;
726 
727  // We don't fold known-exiting branches for non-latch exits here,
728  // because this ensures that both all loop blocks and all exit blocks
729  // remain reachable in the CFG.
730  // TODO: We could fold these branches, but it would require much more
731  // sophisticated updates to LoopInfo.
732  if (*KnownWillExit && !IsLatch)
733  continue;
734 
735  SetDest(Info.ExitingBlocks[i], *KnownWillExit, Info.ExitOnTrue);
736  }
737  }
738 
739  // When completely unrolling, the last latch becomes unreachable.
740  if (!LatchIsExiting && CompletelyUnroll)
741  changeToUnreachable(Latches.back()->getTerminator(), PreserveLCSSA, &DTU);
742 
743  // Merge adjacent basic blocks, if possible.
744  for (BasicBlock *Latch : Latches) {
745  BranchInst *Term = dyn_cast<BranchInst>(Latch->getTerminator());
746  assert((Term ||
747  (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) &&
748  "Need a branch as terminator, except when fully unrolling with "
749  "unconditional latch");
750  if (Term && Term->isUnconditional()) {
751  BasicBlock *Dest = Term->getSuccessor(0);
752  BasicBlock *Fold = Dest->getUniquePredecessor();
753  if (MergeBlockIntoPredecessor(Dest, &DTU, LI)) {
754  // Dest has been folded into Fold. Update our worklists accordingly.
755  std::replace(Latches.begin(), Latches.end(), Dest, Fold);
756  llvm::erase_value(UnrolledLoopBlocks, Dest);
757  }
758  }
759  }
760  // Apply updates to the DomTree.
761  DT = &DTU.getDomTree();
762 
763  // At this point, the code is well formed. We now simplify the unrolled loop,
764  // doing constant propagation and dead code elimination as we go.
765  simplifyLoopAfterUnroll(L, !CompletelyUnroll && ULO.Count > 1, LI, SE, DT, AC,
766  TTI);
767 
768  NumCompletelyUnrolled += CompletelyUnroll;
769  ++NumUnrolled;
770 
771  Loop *OuterL = L->getParentLoop();
772  // Update LoopInfo if the loop is completely removed.
773  if (CompletelyUnroll)
774  LI->erase(L);
775 
776  // After complete unrolling most of the blocks should be contained in OuterL.
777  // However, some of them might happen to be out of OuterL (e.g. if they
778  // precede a loop exit). In this case we might need to insert PHI nodes in
779  // order to preserve LCSSA form.
780  // We don't need to check this if we already know that we need to fix LCSSA
781  // form.
782  // TODO: For now we just recompute LCSSA for the outer loop in this case, but
783  // it should be possible to fix it in-place.
784  if (PreserveLCSSA && OuterL && CompletelyUnroll && !NeedToFixLCSSA)
785  NeedToFixLCSSA |= ::needToInsertPhisForLCSSA(OuterL, UnrolledLoopBlocks, LI);
786 
787  // Make sure that loop-simplify form is preserved. We want to simplify
788  // at least one layer outside of the loop that was unrolled so that any
789  // changes to the parent loop exposed by the unrolling are considered.
790  if (OuterL) {
791  // OuterL includes all loops for which we can break loop-simplify, so
792  // it's sufficient to simplify only it (it'll recursively simplify inner
793  // loops too).
794  if (NeedToFixLCSSA) {
795  // LCSSA must be performed on the outermost affected loop. The unrolled
796  // loop's last loop latch is guaranteed to be in the outermost loop
797  // after LoopInfo's been updated by LoopInfo::erase.
798  Loop *LatchLoop = LI->getLoopFor(Latches.back());
799  Loop *FixLCSSALoop = OuterL;
800  if (!FixLCSSALoop->contains(LatchLoop))
801  while (FixLCSSALoop->getParentLoop() != LatchLoop)
802  FixLCSSALoop = FixLCSSALoop->getParentLoop();
803 
804  formLCSSARecursively(*FixLCSSALoop, *DT, LI, SE);
805  } else if (PreserveLCSSA) {
806  assert(OuterL->isLCSSAForm(*DT) &&
807  "Loops should be in LCSSA form after loop-unroll.");
808  }
809 
810  // TODO: That potentially might be compile-time expensive. We should try
811  // to fix the loop-simplified form incrementally.
812  simplifyLoop(OuterL, DT, LI, SE, AC, nullptr, PreserveLCSSA);
813  } else {
814  // Simplify loops for which we might've broken loop-simplify form.
815  for (Loop *SubLoop : LoopsToSimplify)
816  simplifyLoop(SubLoop, DT, LI, SE, AC, nullptr, PreserveLCSSA);
817  }
818 
819  return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled
821 }
822 
823 /// Given an llvm.loop loop id metadata node, returns the loop hint metadata
824 /// node with the given name (for example, "llvm.loop.unroll.count"). If no
825 /// such metadata node exists, then nullptr is returned.
827  // First operand should refer to the loop id itself.
828  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
829  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
830 
831  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
832  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
833  if (!MD)
834  continue;
835 
836  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
837  if (!S)
838  continue;
839 
840  if (Name.equals(S->getString()))
841  return MD;
842  }
843  return nullptr;
844 }
i
i
Definition: README.txt:29
llvm::RecursivelyDeleteTriviallyDeadInstructions
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:511
AssumptionCache.h
MathExtras.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::DominatorTreeBase::findNearestCommonDominator
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
Definition: GenericDomTree.h:468
LoopSimplify.h
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::addClonedBlockToLoopInfo
const Loop * addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops)
Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary and adds a mapping from the o...
Definition: LoopUnroll.cpp:136
llvm::LoopBase::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
llvm::AssumptionCache::registerAssumption
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
Definition: AssumptionCache.cpp:217
Optional.h
ValueMapper.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
Metadata.h
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
IntrinsicInst.h
DebugInfoMetadata.h
llvm::ValueMap::end
iterator end()
Definition: ValueMap.h:136
llvm::Function::getBasicBlockList
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:710
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:230
llvm::ScalarEvolution::getSmallConstantTripMultiple
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
Definition: ScalarEvolution.cpp:7215
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::DenseMapBase::lookup
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:197
StringRef.h
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::UnrollLoopOptions::AllowExpensiveTripCount
bool AllowExpensiveTripCount
Definition: UnrollLoop.h:71
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::UnrollLoopOptions::Runtime
bool Runtime
Definition: UnrollLoop.h:70
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::Loop::getStartLoc
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:633
DomTreeUpdater.h
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
llvm::UnrollLoopOptions::Force
bool Force
Definition: UnrollLoop.h:69
Local.h
OptimizationRemarkEmitter.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::EnableFSDiscriminator
cl::opt< bool > EnableFSDiscriminator
Definition: TargetPassConfig.cpp:385
DEBUG_TYPE
#define DEBUG_TYPE
Definition: LoopUnroll.cpp:79
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1580
ScalarEvolution.h
DenseMap.h
Module.h
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::GreatestCommonDivisor64
uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B)
Definition: MathExtras.h:630
llvm::Optional< bool >
llvm::formLCSSARecursively
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:403
UnrollRuntimeEpilog
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."))
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:105
replace
static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New)
Definition: ConstantMerge.cpp:116
Use.h
endif
__FakeVCSRevision h endif() endif() set(generated_files "$
Definition: CMakeLists.txt:16
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
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1118
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
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::GetUnrollMetadata
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:826
Constants.h
Twine.h
llvm::LoopBase::addChildLoop
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:395
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::remapInstructionsInBlocks
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock * > &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
Definition: CloneFunction.cpp:787
llvm::LoopInfoBase::addTopLevelLoop
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1024
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
llvm::LoopInfo::replacementPreservesLCSSAForm
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:1115
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2818
llvm::simplifyLoopAfterUnroll
void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI)
Perform some cleanup and simplifications on loops after unrolling.
Definition: LoopUnroll.cpp:204
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:171
llvm::Instruction
Definition: Instruction.h:45
llvm::LoopBlocksDFS::endRPO
RPOIterator endRPO() const
Definition: LoopIterator.h:140
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:6293
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
isEpilogProfitable
static bool isEpilogProfitable(Loop *L)
The function chooses which type of unroll (epilog or prolog) is more profitabale.
Definition: LoopUnroll.cpp:190
llvm::cl::Option::getNumOccurrences
int getNumOccurrences() const
Definition: CommandLine.h:404
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
LoopUtils.h
DebugLoc.h
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::ValueMap::begin
iterator begin()
Definition: ValueMap.h:135
llvm::BasicBlock::getModule
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:144
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: GenericDomTree.h:655
llvm::None
const NoneType None
Definition: None.h:23
LoopIterator.h
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::erase_value
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:1740
llvm::LoopUnrollResult::FullyUnrolled
@ FullyUnrolled
The loop was fully unrolled into straight-line code.
CFG.h
LoopInfo.h
llvm::LoopInfoBase::AllocateLoop
LoopT * AllocateLoop(ArgsTy &&... Args)
Definition: LoopInfo.h:931
llvm::LoopBlocksDFS::RPOIterator
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:101
llvm::ScalarEvolution::getSmallConstantTripCount
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
Definition: ScalarEvolution.cpp:7179
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1112
llvm::LoopBlocksDFS
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
llvm::cloneAndAdaptNoAliasScopes
void cloneAndAdaptNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, ArrayRef< BasicBlock * > NewBlocks, LLVMContext &Context, StringRef Ext)
Clone the specified noalias decl scopes.
Definition: CloneFunction.cpp:991
llvm::BasicBlock::hasAddressTaken
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:448
llvm::CloneBasicBlock
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
Definition: CloneFunction.cpp:43
BasicBlock.h
llvm::cl::opt< bool >
VI
@ VI
Definition: SIInstrInfo.cpp:7679
llvm::UnrollLoop
LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const llvm::TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr)
Unroll the given loop by Count.
Definition: LoopUnroll.cpp:258
llvm::Function::isDebugInfoForProfiling
bool isDebugInfoForProfiling() const
Returns true if we should emit debug info for profiling.
Definition: Metadata.cpp:1545
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DomTreeUpdater::getDomTree
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Definition: DomTreeUpdater.cpp:303
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3124
llvm::DenseMap
Definition: DenseMap.h:714
llvm::ScalarEvolution::getSmallConstantMaxTripCount
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
Definition: ScalarEvolution.cpp:7195
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LoopUnrollResult::PartiallyUnrolled
@ PartiallyUnrolled
The loop was partially unrolled – we still have a loop, but with a smaller trip count.
Cloning.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:576
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::LoopUnrollResult
LoopUnrollResult
Represents the result of a UnrollLoop invocation.
Definition: UnrollLoop.h:53
ArrayRef.h
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1220
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ValueMapIterator::ValueTypeProxy::second
ValueT & second
Definition: ValueMap.h:346
llvm::UnrollLoopOptions::ForgetAllSCEV
bool ForgetAllSCEV
Definition: UnrollLoop.h:73
llvm::OptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Definition: OptimizationRemarkEmitter.cpp:77
iterator_range.h
llvm::LoopInfo::erase
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:878
llvm::ScalarEvolution::forgetTopmostLoop
void forgetTopmostLoop(const Loop *L)
Definition: ScalarEvolution.cpp:7509
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::UnrollRuntimeLoopRemainder
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, bool PreserveLCSSA, Loop **ResultLoop=nullptr)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
Definition: LoopUnrollRuntime.cpp:591
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:398
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::MergeBlockIntoPredecessor
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
Definition: BasicBlockUtils.cpp:173
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1558
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::identifyNoAliasScopesToClone
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
Definition: CloneFunction.cpp:1028
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:272
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
needToInsertPhisForLCSSA
static bool needToInsertPhisForLCSSA(Loop *L, const 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:111
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::ValueMap< const Value *, WeakTrackingVH >
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
ValueHandle.h
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:148
ValueMap.h
llvm::DominatorTreeBase::addNewBlock
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
Definition: GenericDomTree.h:619
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
j
return j(j<< 16)
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::ValueMapIterator
Definition: ValueMap.h:49
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:461
llvm::UnrollLoopOptions::Count
unsigned Count
Definition: UnrollLoop.h:68
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::simplifyLoopIVs
bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, const TargetTransformInfo *TTI, SmallVectorImpl< WeakTrackingVH > &Dead)
SimplifyLoopIVs - Simplify users of induction variables within this loop.
Definition: SimplifyIndVar.cpp:928
GenericDomTree.h
llvm::UnrollLoopOptions::UnrollRemainder
bool UnrollRemainder
Definition: UnrollLoop.h:72
llvm::ScalarEvolution::isBackedgeTakenCountMaxOrZero
bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
Definition: ScalarEvolution.cpp:7297
Casting.h
DiagnosticInfo.h
Function.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::ValueMap::find
iterator find(const KeyT &Val)
Definition: ValueMap.h:156
llvm::simplifyLoop
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
Definition: LoopSimplify.cpp:719
llvm::changeToUnreachable
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:2101
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:363
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:684
Instructions.h
SmallVector.h
User.h
llvm::ScalarEvolution::forgetAllLoops
void forgetAllLoops()
Definition: ScalarEvolution.cpp:7430
llvm::LoopBase::addBasicBlockToLoop
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:242
Dominators.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::try_emplace
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:222
UnrollLoop.h
llvm::Loop::isSafeToClone
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:485
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:2633
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:321
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:401
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::LoopBase::isLoopExiting
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
Definition: LoopInfo.h:225
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::cl::desc
Definition: CommandLine.h:414
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3068
llvm::LoopUnrollResult::Unmodified
@ Unmodified
The loop was not modified.
raw_ostream.h
BasicBlockUtils.h
llvm::UnrollLoopOptions
Definition: UnrollLoop.h:67
llvm::MDString
A single uniqued string.
Definition: Metadata.h:611
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
ilist_iterator.h
UnrollVerifyDomtree
static cl::opt< bool > UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), cl::init(false))
SimplifyIndVar.h
SetVector.h
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908