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