LLVM  13.0.0git
LoopInfo.cpp
Go to the documentation of this file.
1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
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 defines the LoopInfo class that is used to identify natural loops
10 // and determine the loop depth of various nodes of the CFG. Note that the
11 // loops identified may actually be several natural loops that share the same
12 // header node... not just a single natural loop.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/ADT/ScopeExit.h"
19 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/Config/llvm-config.h"
28 #include "llvm/IR/CFG.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/DebugLoc.h"
31 #include "llvm/IR/Dominators.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/LLVMContext.h"
35 #include "llvm/IR/Metadata.h"
36 #include "llvm/IR/PassManager.h"
37 #include "llvm/IR/PrintPasses.h"
38 #include "llvm/InitializePasses.h"
40 #include "llvm/Support/Debug.h"
42 #include <algorithm>
43 using namespace llvm;
44 
45 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
48 
49 // Always verify loopinfo if expensive checking is enabled.
50 #ifdef EXPENSIVE_CHECKS
51 bool llvm::VerifyLoopInfo = true;
52 #else
53 bool llvm::VerifyLoopInfo = false;
54 #endif
56  VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
57  cl::Hidden, cl::desc("Verify loop info (time consuming)"));
58 
59 //===----------------------------------------------------------------------===//
60 // Loop implementation
61 //
62 
63 bool Loop::isLoopInvariant(const Value *V) const {
64  if (const Instruction *I = dyn_cast<Instruction>(V))
65  return !contains(I);
66  return true; // All non-instructions are loop invariant
67 }
68 
70  return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
71 }
72 
73 bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt,
74  MemorySSAUpdater *MSSAU) const {
75  if (Instruction *I = dyn_cast<Instruction>(V))
76  return makeLoopInvariant(I, Changed, InsertPt, MSSAU);
77  return true; // All non-instructions are loop-invariant.
78 }
79 
80 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
81  Instruction *InsertPt,
82  MemorySSAUpdater *MSSAU) const {
83  // Test if the value is already loop-invariant.
84  if (isLoopInvariant(I))
85  return true;
87  return false;
88  if (I->mayReadFromMemory())
89  return false;
90  // EH block instructions are immobile.
91  if (I->isEHPad())
92  return false;
93  // Determine the insertion point, unless one was given.
94  if (!InsertPt) {
95  BasicBlock *Preheader = getLoopPreheader();
96  // Without a preheader, hoisting is not feasible.
97  if (!Preheader)
98  return false;
99  InsertPt = Preheader->getTerminator();
100  }
101  // Don't hoist instructions with loop-variant operands.
102  for (Value *Operand : I->operands())
103  if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU))
104  return false;
105 
106  // Hoist.
107  I->moveBefore(InsertPt);
108  if (MSSAU)
109  if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I))
110  MSSAU->moveToPlace(MUD, InsertPt->getParent(),
112 
113  // There is possibility of hoisting this instruction above some arbitrary
114  // condition. Any metadata defined on it can be control dependent on this
115  // condition. Conservatively strip it here so that we don't give any wrong
116  // information to the optimizer.
117  I->dropUnknownNonDebugMetadata();
118 
119  Changed = true;
120  return true;
121 }
122 
124  BasicBlock *&Backedge) const {
125  BasicBlock *H = getHeader();
126 
127  Incoming = nullptr;
128  Backedge = nullptr;
129  pred_iterator PI = pred_begin(H);
130  assert(PI != pred_end(H) && "Loop must have at least one backedge!");
131  Backedge = *PI++;
132  if (PI == pred_end(H))
133  return false; // dead loop
134  Incoming = *PI++;
135  if (PI != pred_end(H))
136  return false; // multiple backedges?
137 
138  if (contains(Incoming)) {
139  if (contains(Backedge))
140  return false;
141  std::swap(Incoming, Backedge);
142  } else if (!contains(Backedge))
143  return false;
144 
145  assert(Incoming && Backedge && "expected non-null incoming and backedges");
146  return true;
147 }
148 
150  BasicBlock *H = getHeader();
151 
152  BasicBlock *Incoming = nullptr, *Backedge = nullptr;
153  if (!getIncomingAndBackEdge(Incoming, Backedge))
154  return nullptr;
155 
156  // Loop over all of the PHI nodes, looking for a canonical indvar.
157  for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
158  PHINode *PN = cast<PHINode>(I);
159  if (ConstantInt *CI =
160  dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
161  if (CI->isZero())
162  if (Instruction *Inc =
163  dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
164  if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
165  if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
166  if (CI->isOne())
167  return PN;
168  }
169  return nullptr;
170 }
171 
172 /// Get the latch condition instruction.
173 static ICmpInst *getLatchCmpInst(const Loop &L) {
174  if (BasicBlock *Latch = L.getLoopLatch())
175  if (BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator()))
176  if (BI->isConditional())
177  return dyn_cast<ICmpInst>(BI->getCondition());
178 
179  return nullptr;
180 }
181 
182 /// Return the final value of the loop induction variable if found.
183 static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar,
184  const Instruction &StepInst) {
185  ICmpInst *LatchCmpInst = getLatchCmpInst(L);
186  if (!LatchCmpInst)
187  return nullptr;
188 
189  Value *Op0 = LatchCmpInst->getOperand(0);
190  Value *Op1 = LatchCmpInst->getOperand(1);
191  if (Op0 == &IndVar || Op0 == &StepInst)
192  return Op1;
193 
194  if (Op1 == &IndVar || Op1 == &StepInst)
195  return Op0;
196 
197  return nullptr;
198 }
199 
201  PHINode &IndVar,
202  ScalarEvolution &SE) {
203  InductionDescriptor IndDesc;
204  if (!InductionDescriptor::isInductionPHI(&IndVar, &L, &SE, IndDesc))
205  return None;
206 
207  Value *InitialIVValue = IndDesc.getStartValue();
208  Instruction *StepInst = IndDesc.getInductionBinOp();
209  if (!InitialIVValue || !StepInst)
210  return None;
211 
212  const SCEV *Step = IndDesc.getStep();
213  Value *StepInstOp1 = StepInst->getOperand(1);
214  Value *StepInstOp0 = StepInst->getOperand(0);
215  Value *StepValue = nullptr;
216  if (SE.getSCEV(StepInstOp1) == Step)
217  StepValue = StepInstOp1;
218  else if (SE.getSCEV(StepInstOp0) == Step)
219  StepValue = StepInstOp0;
220 
221  Value *FinalIVValue = findFinalIVValue(L, IndVar, *StepInst);
222  if (!FinalIVValue)
223  return None;
224 
225  return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue,
226  SE);
227 }
228 
230 
232  BasicBlock *Latch = L.getLoopLatch();
233  assert(Latch && "Expecting valid latch");
234 
235  BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator());
236  assert(BI && BI->isConditional() && "Expecting conditional latch branch");
237 
238  ICmpInst *LatchCmpInst = dyn_cast<ICmpInst>(BI->getCondition());
239  assert(LatchCmpInst &&
240  "Expecting the latch compare instruction to be a CmpInst");
241 
242  // Need to inverse the predicate when first successor is not the loop
243  // header
244  ICmpInst::Predicate Pred = (BI->getSuccessor(0) == L.getHeader())
245  ? LatchCmpInst->getPredicate()
246  : LatchCmpInst->getInversePredicate();
247 
248  if (LatchCmpInst->getOperand(0) == &getFinalIVValue())
249  Pred = ICmpInst::getSwappedPredicate(Pred);
250 
251  // Need to flip strictness of the predicate when the latch compare instruction
252  // is not using StepInst
253  if (LatchCmpInst->getOperand(0) == &getStepInst() ||
254  LatchCmpInst->getOperand(1) == &getStepInst())
255  return Pred;
256 
257  // Cannot flip strictness of NE and EQ
258  if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
260 
261  Direction D = getDirection();
262  if (D == Direction::Increasing)
263  return ICmpInst::ICMP_SLT;
264 
265  if (D == Direction::Decreasing)
266  return ICmpInst::ICMP_SGT;
267 
268  // If cannot determine the direction, then unable to find the canonical
269  // predicate
271 }
272 
274  if (const SCEVAddRecExpr *StepAddRecExpr =
275  dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&getStepInst())))
276  if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) {
277  if (SE.isKnownPositive(StepRecur))
278  return Direction::Increasing;
279  if (SE.isKnownNegative(StepRecur))
280  return Direction::Decreasing;
281  }
282 
283  return Direction::Unknown;
284 }
285 
287  if (PHINode *IndVar = getInductionVariable(SE))
288  return LoopBounds::getBounds(*this, *IndVar, SE);
289 
290  return None;
291 }
292 
294  if (!isLoopSimplifyForm())
295  return nullptr;
296 
297  BasicBlock *Header = getHeader();
298  assert(Header && "Expected a valid loop header");
299  ICmpInst *CmpInst = getLatchCmpInst(*this);
300  if (!CmpInst)
301  return nullptr;
302 
303  Instruction *LatchCmpOp0 = dyn_cast<Instruction>(CmpInst->getOperand(0));
304  Instruction *LatchCmpOp1 = dyn_cast<Instruction>(CmpInst->getOperand(1));
305 
306  for (PHINode &IndVar : Header->phis()) {
307  InductionDescriptor IndDesc;
308  if (!InductionDescriptor::isInductionPHI(&IndVar, this, &SE, IndDesc))
309  continue;
310 
311  Instruction *StepInst = IndDesc.getInductionBinOp();
312 
313  // case 1:
314  // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
315  // StepInst = IndVar + step
316  // cmp = StepInst < FinalValue
317  if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1)
318  return &IndVar;
319 
320  // case 2:
321  // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
322  // StepInst = IndVar + step
323  // cmp = IndVar < FinalValue
324  if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1)
325  return &IndVar;
326  }
327 
328  return nullptr;
329 }
330 
332  InductionDescriptor &IndDesc) const {
333  if (PHINode *IndVar = getInductionVariable(SE))
334  return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc);
335 
336  return false;
337 }
338 
340  ScalarEvolution &SE) const {
341  // Located in the loop header
342  BasicBlock *Header = getHeader();
343  if (AuxIndVar.getParent() != Header)
344  return false;
345 
346  // No uses outside of the loop
347  for (User *U : AuxIndVar.users())
348  if (const Instruction *I = dyn_cast<Instruction>(U))
349  if (!contains(I))
350  return false;
351 
352  InductionDescriptor IndDesc;
353  if (!InductionDescriptor::isInductionPHI(&AuxIndVar, this, &SE, IndDesc))
354  return false;
355 
356  // The step instruction opcode should be add or sub.
357  if (IndDesc.getInductionOpcode() != Instruction::Add &&
358  IndDesc.getInductionOpcode() != Instruction::Sub)
359  return false;
360 
361  // Incremented by a loop invariant step for each loop iteration
362  return SE.isLoopInvariant(IndDesc.getStep(), this);
363 }
364 
366  if (!isLoopSimplifyForm())
367  return nullptr;
368 
369  BasicBlock *Preheader = getLoopPreheader();
370  assert(Preheader && getLoopLatch() &&
371  "Expecting a loop with valid preheader and latch");
372 
373  // Loop should be in rotate form.
374  if (!isRotatedForm())
375  return nullptr;
376 
377  // Disallow loops with more than one unique exit block, as we do not verify
378  // that GuardOtherSucc post dominates all exit blocks.
379  BasicBlock *ExitFromLatch = getUniqueExitBlock();
380  if (!ExitFromLatch)
381  return nullptr;
382 
383  BasicBlock *ExitFromLatchSucc = ExitFromLatch->getUniqueSuccessor();
384  if (!ExitFromLatchSucc)
385  return nullptr;
386 
387  BasicBlock *GuardBB = Preheader->getUniquePredecessor();
388  if (!GuardBB)
389  return nullptr;
390 
391  assert(GuardBB->getTerminator() && "Expecting valid guard terminator");
392 
393  BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());
394  if (!GuardBI || GuardBI->isUnconditional())
395  return nullptr;
396 
397  BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader)
398  ? GuardBI->getSuccessor(1)
399  : GuardBI->getSuccessor(0);
400  return (GuardOtherSucc == ExitFromLatchSucc) ? GuardBI : nullptr;
401 }
402 
404  InductionDescriptor IndDesc;
405  if (!getInductionDescriptor(SE, IndDesc))
406  return false;
407 
408  ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());
409  if (!Init || !Init->isZero())
410  return false;
411 
412  if (IndDesc.getInductionOpcode() != Instruction::Add)
413  return false;
414 
415  ConstantInt *Step = IndDesc.getConstIntStepValue();
416  if (!Step || !Step->isOne())
417  return false;
418 
419  return true;
420 }
421 
422 // Check that 'BB' doesn't have any uses outside of the 'L'
423 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
424  const DominatorTree &DT) {
425  for (const Instruction &I : BB) {
426  // Tokens can't be used in PHI nodes and live-out tokens prevent loop
427  // optimizations, so for the purposes of considered LCSSA form, we
428  // can ignore them.
429  if (I.getType()->isTokenTy())
430  continue;
431 
432  for (const Use &U : I.uses()) {
433  const Instruction *UI = cast<Instruction>(U.getUser());
434  const BasicBlock *UserBB = UI->getParent();
435 
436  // For practical purposes, we consider that the use in a PHI
437  // occurs in the respective predecessor block. For more info,
438  // see the `phi` doc in LangRef and the LCSSA doc.
439  if (const PHINode *P = dyn_cast<PHINode>(UI))
440  UserBB = P->getIncomingBlock(U);
441 
442  // Check the current block, as a fast-path, before checking whether
443  // the use is anywhere in the loop. Most values are used in the same
444  // block they are defined in. Also, blocks not reachable from the
445  // entry are special; uses in them don't need to go through PHIs.
446  if (UserBB != &BB && !L.contains(UserBB) &&
447  DT.isReachableFromEntry(UserBB))
448  return false;
449  }
450  }
451  return true;
452 }
453 
454 bool Loop::isLCSSAForm(const DominatorTree &DT) const {
455  // For each block we check that it doesn't have any uses outside of this loop.
456  return all_of(this->blocks(), [&](const BasicBlock *BB) {
457  return isBlockInLCSSAForm(*this, *BB, DT);
458  });
459 }
460 
462  const LoopInfo &LI) const {
463  // For each block we check that it doesn't have any uses outside of its
464  // innermost loop. This process will transitively guarantee that the current
465  // loop and all of the nested loops are in LCSSA form.
466  return all_of(this->blocks(), [&](const BasicBlock *BB) {
467  return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
468  });
469 }
470 
472  // Normal-form loops have a preheader, a single backedge, and all of their
473  // exits have all their predecessors inside the loop.
475 }
476 
477 // Routines that reform the loop CFG and split edges often fail on indirectbr.
478 bool Loop::isSafeToClone() const {
479  // Return false if any loop blocks contain indirectbrs, or there are any calls
480  // to noduplicate functions.
481  // FIXME: it should be ok to clone CallBrInst's if we correctly update the
482  // operand list to reflect the newly cloned labels.
483  for (BasicBlock *BB : this->blocks()) {
484  if (isa<IndirectBrInst>(BB->getTerminator()) ||
485  isa<CallBrInst>(BB->getTerminator()))
486  return false;
487 
488  for (Instruction &I : *BB)
489  if (auto *CB = dyn_cast<CallBase>(&I))
490  if (CB->cannotDuplicate())
491  return false;
492  }
493  return true;
494 }
495 
497  MDNode *LoopID = nullptr;
498 
499  // Go through the latch blocks and check the terminator for the metadata.
500  SmallVector<BasicBlock *, 4> LatchesBlocks;
501  getLoopLatches(LatchesBlocks);
502  for (BasicBlock *BB : LatchesBlocks) {
503  Instruction *TI = BB->getTerminator();
504  MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
505 
506  if (!MD)
507  return nullptr;
508 
509  if (!LoopID)
510  LoopID = MD;
511  else if (MD != LoopID)
512  return nullptr;
513  }
514  if (!LoopID || LoopID->getNumOperands() == 0 ||
515  LoopID->getOperand(0) != LoopID)
516  return nullptr;
517  return LoopID;
518 }
519 
520 void Loop::setLoopID(MDNode *LoopID) const {
521  assert((!LoopID || LoopID->getNumOperands() > 0) &&
522  "Loop ID needs at least one operand");
523  assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
524  "Loop ID should refer to itself");
525 
526  SmallVector<BasicBlock *, 4> LoopLatches;
527  getLoopLatches(LoopLatches);
528  for (BasicBlock *BB : LoopLatches)
529  BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
530 }
531 
534 
535  MDNode *DisableUnrollMD =
536  MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
537  MDNode *LoopID = getLoopID();
539  Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
540  setLoopID(NewLoopID);
541 }
542 
545 
546  MDNode *MustProgress = findOptionMDForLoop(this, "llvm.loop.mustprogress");
547 
548  if (MustProgress)
549  return;
550 
551  MDNode *MustProgressMD =
552  MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress"));
553  MDNode *LoopID = getLoopID();
554  MDNode *NewLoopID =
555  makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD});
556  setLoopID(NewLoopID);
557 }
558 
560  MDNode *DesiredLoopIdMetadata = getLoopID();
561 
562  if (!DesiredLoopIdMetadata)
563  return false;
564 
565  MDNode *ParallelAccesses =
566  findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
568  ParallelAccessGroups; // For scalable 'contains' check.
569  if (ParallelAccesses) {
570  for (const MDOperand &MD : drop_begin(ParallelAccesses->operands())) {
571  MDNode *AccGroup = cast<MDNode>(MD.get());
572  assert(isValidAsAccessGroup(AccGroup) &&
573  "List item must be an access group");
574  ParallelAccessGroups.insert(AccGroup);
575  }
576  }
577 
578  // The loop branch contains the parallel loop metadata. In order to ensure
579  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
580  // dependencies (thus converted the loop back to a sequential loop), check
581  // that all the memory instructions in the loop belong to an access group that
582  // is parallel to this loop.
583  for (BasicBlock *BB : this->blocks()) {
584  for (Instruction &I : *BB) {
585  if (!I.mayReadOrWriteMemory())
586  continue;
587 
588  if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
589  auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
590  if (AG->getNumOperands() == 0) {
591  assert(isValidAsAccessGroup(AG) && "Item must be an access group");
592  return ParallelAccessGroups.count(AG);
593  }
594 
595  for (const MDOperand &AccessListItem : AG->operands()) {
596  MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
597  assert(isValidAsAccessGroup(AccGroup) &&
598  "List item must be an access group");
599  if (ParallelAccessGroups.count(AccGroup))
600  return true;
601  }
602  return false;
603  };
604 
605  if (ContainsAccessGroup(AccessGroup))
606  continue;
607  }
608 
609  // The memory instruction can refer to the loop identifier metadata
610  // directly or indirectly through another list metadata (in case of
611  // nested parallel loops). The loop identifier metadata refers to
612  // itself so we can check both cases with the same routine.
613  MDNode *LoopIdMD =
614  I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
615 
616  if (!LoopIdMD)
617  return false;
618 
619  if (!llvm::is_contained(LoopIdMD->operands(), DesiredLoopIdMetadata))
620  return false;
621  }
622  }
623  return true;
624 }
625 
627 
629  // If we have a debug location in the loop ID, then use it.
630  if (MDNode *LoopID = getLoopID()) {
631  DebugLoc Start;
632  // We use the first DebugLoc in the header as the start location of the loop
633  // and if there is a second DebugLoc in the header we use it as end location
634  // of the loop.
635  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
636  if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
637  if (!Start)
638  Start = DebugLoc(L);
639  else
640  return LocRange(Start, DebugLoc(L));
641  }
642  }
643 
644  if (Start)
645  return LocRange(Start);
646  }
647 
648  // Try the pre-header first.
649  if (BasicBlock *PHeadBB = getLoopPreheader())
650  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
651  return LocRange(DL);
652 
653  // If we have no pre-header or there are no instructions with debug
654  // info in it, try the header.
655  if (BasicBlock *HeadBB = getHeader())
656  return LocRange(HeadBB->getTerminator()->getDebugLoc());
657 
658  return LocRange();
659 }
660 
661 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
662 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
663 
665  print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
666 }
667 #endif
668 
669 //===----------------------------------------------------------------------===//
670 // UnloopUpdater implementation
671 //
672 
673 namespace {
674 /// Find the new parent loop for all blocks within the "unloop" whose last
675 /// backedges has just been removed.
676 class UnloopUpdater {
677  Loop &Unloop;
678  LoopInfo *LI;
679 
680  LoopBlocksDFS DFS;
681 
682  // Map unloop's immediate subloops to their nearest reachable parents. Nested
683  // loops within these subloops will not change parents. However, an immediate
684  // subloop's new parent will be the nearest loop reachable from either its own
685  // exits *or* any of its nested loop's exits.
686  DenseMap<Loop *, Loop *> SubloopParents;
687 
688  // Flag the presence of an irreducible backedge whose destination is a block
689  // directly contained by the original unloop.
690  bool FoundIB;
691 
692 public:
693  UnloopUpdater(Loop *UL, LoopInfo *LInfo)
694  : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
695 
696  void updateBlockParents();
697 
698  void removeBlocksFromAncestors();
699 
700  void updateSubloopParents();
701 
702 protected:
703  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
704 };
705 } // end anonymous namespace
706 
707 /// Update the parent loop for all blocks that are directly contained within the
708 /// original "unloop".
709 void UnloopUpdater::updateBlockParents() {
710  if (Unloop.getNumBlocks()) {
711  // Perform a post order CFG traversal of all blocks within this loop,
712  // propagating the nearest loop from successors to predecessors.
713  LoopBlocksTraversal Traversal(DFS, LI);
714  for (BasicBlock *POI : Traversal) {
715 
716  Loop *L = LI->getLoopFor(POI);
717  Loop *NL = getNearestLoop(POI, L);
718 
719  if (NL != L) {
720  // For reducible loops, NL is now an ancestor of Unloop.
721  assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
722  "uninitialized successor");
723  LI->changeLoopFor(POI, NL);
724  } else {
725  // Or the current block is part of a subloop, in which case its parent
726  // is unchanged.
727  assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
728  }
729  }
730  }
731  // Each irreducible loop within the unloop induces a round of iteration using
732  // the DFS result cached by Traversal.
733  bool Changed = FoundIB;
734  for (unsigned NIters = 0; Changed; ++NIters) {
735  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
736 
737  // Iterate over the postorder list of blocks, propagating the nearest loop
738  // from successors to predecessors as before.
739  Changed = false;
740  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
741  POE = DFS.endPostorder();
742  POI != POE; ++POI) {
743 
744  Loop *L = LI->getLoopFor(*POI);
745  Loop *NL = getNearestLoop(*POI, L);
746  if (NL != L) {
747  assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
748  "uninitialized successor");
749  LI->changeLoopFor(*POI, NL);
750  Changed = true;
751  }
752  }
753  }
754 }
755 
756 /// Remove unloop's blocks from all ancestors below their new parents.
757 void UnloopUpdater::removeBlocksFromAncestors() {
758  // Remove all unloop's blocks (including those in nested subloops) from
759  // ancestors below the new parent loop.
760  for (BasicBlock *BB : Unloop.blocks()) {
761  Loop *OuterParent = LI->getLoopFor(BB);
762  if (Unloop.contains(OuterParent)) {
763  while (OuterParent->getParentLoop() != &Unloop)
764  OuterParent = OuterParent->getParentLoop();
765  OuterParent = SubloopParents[OuterParent];
766  }
767  // Remove blocks from former Ancestors except Unloop itself which will be
768  // deleted.
769  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
770  OldParent = OldParent->getParentLoop()) {
771  assert(OldParent && "new loop is not an ancestor of the original");
772  OldParent->removeBlockFromLoop(BB);
773  }
774  }
775 }
776 
777 /// Update the parent loop for all subloops directly nested within unloop.
778 void UnloopUpdater::updateSubloopParents() {
779  while (!Unloop.isInnermost()) {
780  Loop *Subloop = *std::prev(Unloop.end());
781  Unloop.removeChildLoop(std::prev(Unloop.end()));
782 
783  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
784  if (Loop *Parent = SubloopParents[Subloop])
785  Parent->addChildLoop(Subloop);
786  else
787  LI->addTopLevelLoop(Subloop);
788  }
789 }
790 
791 /// Return the nearest parent loop among this block's successors. If a successor
792 /// is a subloop header, consider its parent to be the nearest parent of the
793 /// subloop's exits.
794 ///
795 /// For subloop blocks, simply update SubloopParents and return NULL.
796 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
797 
798  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
799  // is considered uninitialized.
800  Loop *NearLoop = BBLoop;
801 
802  Loop *Subloop = nullptr;
803  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
804  Subloop = NearLoop;
805  // Find the subloop ancestor that is directly contained within Unloop.
806  while (Subloop->getParentLoop() != &Unloop) {
807  Subloop = Subloop->getParentLoop();
808  assert(Subloop && "subloop is not an ancestor of the original loop");
809  }
810  // Get the current nearest parent of the Subloop exits, initially Unloop.
811  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
812  }
813 
815  if (I == E) {
816  assert(!Subloop && "subloop blocks must have a successor");
817  NearLoop = nullptr; // unloop blocks may now exit the function.
818  }
819  for (; I != E; ++I) {
820  if (*I == BB)
821  continue; // self loops are uninteresting
822 
823  Loop *L = LI->getLoopFor(*I);
824  if (L == &Unloop) {
825  // This successor has not been processed. This path must lead to an
826  // irreducible backedge.
827  assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
828  FoundIB = true;
829  }
830  if (L != &Unloop && Unloop.contains(L)) {
831  // Successor is in a subloop.
832  if (Subloop)
833  continue; // Branching within subloops. Ignore it.
834 
835  // BB branches from the original into a subloop header.
836  assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
837 
838  // Get the current nearest parent of the Subloop's exits.
839  L = SubloopParents[L];
840  // L could be Unloop if the only exit was an irreducible backedge.
841  }
842  if (L == &Unloop) {
843  continue;
844  }
845  // Handle critical edges from Unloop into a sibling loop.
846  if (L && !L->contains(&Unloop)) {
847  L = L->getParentLoop();
848  }
849  // Remember the nearest parent loop among successors or subloop exits.
850  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
851  NearLoop = L;
852  }
853  if (Subloop) {
854  SubloopParents[Subloop] = NearLoop;
855  return BBLoop;
856  }
857  return NearLoop;
858 }
859 
860 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
861 
864  // Check whether the analysis, all analyses on functions, or the function's
865  // CFG have been preserved.
866  auto PAC = PA.getChecker<LoopAnalysis>();
867  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
868  PAC.preservedSet<CFGAnalyses>());
869 }
870 
871 void LoopInfo::erase(Loop *Unloop) {
872  assert(!Unloop->isInvalid() && "Loop has already been erased!");
873 
874  auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
875 
876  // First handle the special case of no parent loop to simplify the algorithm.
877  if (Unloop->isOutermost()) {
878  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
879  for (BasicBlock *BB : Unloop->blocks()) {
880  // Don't reparent blocks in subloops.
881  if (getLoopFor(BB) != Unloop)
882  continue;
883 
884  // Blocks no longer have a parent but are still referenced by Unloop until
885  // the Unloop object is deleted.
886  changeLoopFor(BB, nullptr);
887  }
888 
889  // Remove the loop from the top-level LoopInfo object.
890  for (iterator I = begin();; ++I) {
891  assert(I != end() && "Couldn't find loop");
892  if (*I == Unloop) {
893  removeLoop(I);
894  break;
895  }
896  }
897 
898  // Move all of the subloops to the top-level.
899  while (!Unloop->isInnermost())
900  addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
901 
902  return;
903  }
904 
905  // Update the parent loop for all blocks within the loop. Blocks within
906  // subloops will not change parents.
907  UnloopUpdater Updater(Unloop, this);
908  Updater.updateBlockParents();
909 
910  // Remove blocks from former ancestor loops.
911  Updater.removeBlocksFromAncestors();
912 
913  // Add direct subloops as children in their new parent loop.
914  Updater.updateSubloopParents();
915 
916  // Remove unloop from its parent loop.
917  Loop *ParentLoop = Unloop->getParentLoop();
918  for (Loop::iterator I = ParentLoop->begin();; ++I) {
919  assert(I != ParentLoop->end() && "Couldn't find loop");
920  if (*I == Unloop) {
921  ParentLoop->removeChildLoop(I);
922  break;
923  }
924  }
925 }
926 
927 bool
929  const BasicBlock *ExitBB) const {
930  if (V->getType()->isTokenTy())
931  // We can't form PHIs of token type, so the definition of LCSSA excludes
932  // values of that type.
933  return false;
934 
935  const Instruction *I = dyn_cast<Instruction>(V);
936  if (!I)
937  return false;
938  const Loop *L = getLoopFor(I->getParent());
939  if (!L)
940  return false;
941  if (L->contains(ExitBB))
942  // Could be an exit bb of a subloop and contained in defining loop
943  return false;
944 
945  // We found a (new) out-of-loop use location, for a value defined in-loop.
946  // (Note that because of LCSSA, we don't have to account for values defined
947  // in sibling loops. Such values will have LCSSA phis of their own in the
948  // common parent loop.)
949  return true;
950 }
951 
952 AnalysisKey LoopAnalysis::Key;
953 
955  // FIXME: Currently we create a LoopInfo from scratch for every function.
956  // This may prove to be too wasteful due to deallocating and re-allocating
957  // memory each time for the underlying map and vector datastructures. At some
958  // point it may prove worthwhile to use a freelist and recycle LoopInfo
959  // objects. I don't want to add that kind of complexity until the scope of
960  // the problem is better understood.
961  LoopInfo LI;
963  return LI;
964 }
965 
968  AM.getResult<LoopAnalysis>(F).print(OS);
969  return PreservedAnalyses::all();
970 }
971 
972 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
973 
974  if (forcePrintModuleIR()) {
975  // handling -print-module-scope
976  OS << Banner << " (loop: ";
977  L.getHeader()->printAsOperand(OS, false);
978  OS << ")\n";
979 
980  // printing whole module
981  OS << *L.getHeader()->getModule();
982  return;
983  }
984 
985  OS << Banner;
986 
987  auto *PreHeader = L.getLoopPreheader();
988  if (PreHeader) {
989  OS << "\n; Preheader:";
990  PreHeader->print(OS);
991  OS << "\n; Loop:";
992  }
993 
994  for (auto *Block : L.blocks())
995  if (Block)
996  Block->print(OS);
997  else
998  OS << "Printing <null> block";
999 
1000  SmallVector<BasicBlock *, 8> ExitBlocks;
1001  L.getExitBlocks(ExitBlocks);
1002  if (!ExitBlocks.empty()) {
1003  OS << "\n; Exit blocks";
1004  for (auto *Block : ExitBlocks)
1005  if (Block)
1006  Block->print(OS);
1007  else
1008  OS << "Printing <null> block";
1009  }
1010 }
1011 
1013  // No loop metadata node, no loop properties.
1014  if (!LoopID)
1015  return nullptr;
1016 
1017  // First operand should refer to the metadata node itself, for legacy reasons.
1018  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1019  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1020 
1021  // Iterate over the metdata node operands and look for MDString metadata.
1022  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
1023  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
1024  if (!MD || MD->getNumOperands() < 1)
1025  continue;
1026  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1027  if (!S)
1028  continue;
1029  // Return the operand node if MDString holds expected metadata.
1030  if (Name.equals(S->getString()))
1031  return MD;
1032  }
1033 
1034  // Loop property not found.
1035  return nullptr;
1036 }
1037 
1039  return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
1040 }
1041 
1043  return Node->getNumOperands() == 0 && Node->isDistinct();
1044 }
1045 
1047  MDNode *OrigLoopID,
1048  ArrayRef<StringRef> RemovePrefixes,
1049  ArrayRef<MDNode *> AddAttrs) {
1050  // First remove any existing loop metadata related to this transformation.
1052 
1053  // Reserve first location for self reference to the LoopID metadata node.
1054  MDs.push_back(nullptr);
1055 
1056  // Remove metadata for the transformation that has been applied or that became
1057  // outdated.
1058  if (OrigLoopID) {
1059  for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
1060  bool IsVectorMetadata = false;
1061  Metadata *Op = OrigLoopID->getOperand(i);
1062  if (MDNode *MD = dyn_cast<MDNode>(Op)) {
1063  const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1064  if (S)
1065  IsVectorMetadata =
1066  llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
1067  return S->getString().startswith(Prefix);
1068  });
1069  }
1070  if (!IsVectorMetadata)
1071  MDs.push_back(Op);
1072  }
1073  }
1074 
1075  // Add metadata to avoid reapplying a transformation, such as
1076  // llvm.loop.unroll.disable and llvm.loop.isvectorized.
1077  MDs.append(AddAttrs.begin(), AddAttrs.end());
1078 
1079  MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
1080  // Replace the temporary node with a self-reference.
1081  NewLoopID->replaceOperandWith(0, NewLoopID);
1082  return NewLoopID;
1083 }
1084 
1085 //===----------------------------------------------------------------------===//
1086 // LoopInfo implementation
1087 //
1088 
1091 }
1092 
1093 char LoopInfoWrapperPass::ID = 0;
1094 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1095  true, true)
1099 
1101  releaseMemory();
1102  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
1103  return false;
1104 }
1105 
1107  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
1108  // function each time verifyAnalysis is called is very expensive. The
1109  // -verify-loop-info option can enable this. In order to perform some
1110  // checking by default, LoopPass has been taught to call verifyLoop manually
1111  // during loop pass sequences.
1112  if (VerifyLoopInfo) {
1113  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1114  LI.verify(DT);
1115  }
1116 }
1117 
1119  AU.setPreservesAll();
1121 }
1122 
1124  LI.print(OS);
1125 }
1126 
1129  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1130  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1131  LI.verify(DT);
1132  return PreservedAnalyses::all();
1133 }
1134 
1135 //===----------------------------------------------------------------------===//
1136 // LoopBlocksDFS implementation
1137 //
1138 
1139 /// Traverse the loop blocks and store the DFS result.
1140 /// Useful for clients that just want the final DFS result and don't need to
1141 /// visit blocks during the initial traversal.
1143  LoopBlocksTraversal Traversal(*this, LI);
1144  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
1145  POE = Traversal.end();
1146  POI != POE; ++POI)
1147  ;
1148 }
llvm::SuccIterator
Definition: CFG.h:139
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::initializeLoopInfoWrapperPassPass
void initializeLoopInfoWrapperPassPass(PassRegistry &)
llvm::LoopBlocksTraversal
Traverse the blocks in a loop using a depth-first search.
Definition: LoopIterator.h:200
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:63
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:839
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:499
llvm
Definition: AllocatorList.h:23
llvm::LoopVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:1127
llvm::LoopBase< BasicBlock, Loop >::getUniqueExitBlock
BasicBlock * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:138
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:743
llvm::LoopBase::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:275
Metadata.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4523
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
llvm::cl::Prefix
@ Prefix
Definition: CommandLine.h:161
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:61
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:456
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::LoopBase< BasicBlock, Loop >::contains
bool contains(const Loop *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::LoopInfo::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: LoopInfo.cpp:862
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:686
LoopInfoImpl.h
llvm::LoopBase< BasicBlock, Loop >
llvm::Loop::getStartLoc
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:626
llvm::VerifyLoopInfo
bool VerifyLoopInfo
Enables verification of loop info.
Definition: LoopInfo.cpp:53
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:93
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
llvm::Loop::getLoopGuardBranch
BranchInst * getLoopGuardBranch() const
Return the loop guard branch, if it exists.
Definition: LoopInfo.cpp:365
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:744
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:823
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::LoopInfoBase::print
void print(raw_ostream &OS) const
Definition: LoopInfoImpl.h:617
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::InductionDescriptor::getInductionOpcode
Instruction::BinaryOps getInductionOpcode() const
Returns binary opcode of the induction operator.
Definition: IVDescriptors.h:326
llvm::Loop::dumpVerbose
void dumpVerbose() const
Definition: LoopInfo.cpp:664
llvm::CmpInst::getFlippedStrictnessPredicate
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Definition: InstrTypes.h:905
Information
Natural Loop Information
Definition: LoopInfo.cpp:1097
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1558
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:749
startswith
static bool startswith(StringRef Magic, const char(&S)[N])
Definition: Magic.cpp:30
NL
#define NL
Definition: DetailedRecordsBackend.cpp:32
llvm::InductionDescriptor::getInductionBinOp
BinaryOperator * getInductionBinOp() const
Definition: IVDescriptors.h:284
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1257
findFinalIVValue
static Value * findFinalIVValue(const Loop &L, const PHINode &IndVar, const Instruction &StepInst)
Return the final value of the loop induction variable if found.
Definition: LoopInfo.cpp:183
llvm::LoopInfo::LoopInfo
LoopInfo()
Definition: LoopInfo.h:1088
llvm::Loop::isCanonical
bool isCanonical(ScalarEvolution &SE) const
Return true if the loop induction variable starts at zero and increments by one each time through the...
Definition: LoopInfo.cpp:403
llvm::Optional
Definition: APInt.h:33
llvm::LoopBase< BasicBlock, Loop >::begin
iterator begin() const
Definition: LoopInfo.h:154
getLatchCmpInst
static ICmpInst * getLatchCmpInst(const Loop &L)
Get the latch condition instruction.
Definition: LoopInfo.cpp:173
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::LoopBlocksTraversal::end
POTIterator end()
Definition: LoopIterator.h:221
llvm::findOptionMDForLoopID
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Definition: LoopInfo.cpp:1012
loops
loops
Definition: LoopInfo.cpp:1097
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
DepthFirstIterator.h
llvm::LoopInfoWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LoopInfo.cpp:1118
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1198
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::MDNode::operands
op_range operands() const
Definition: Metadata.h:1100
llvm::BasicBlock::getUniqueSuccessor
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:302
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1108
llvm::Loop::LoopBounds::getBounds
static Optional< Loop::LoopBounds > getBounds(const Loop &L, PHINode &IndVar, ScalarEvolution &SE)
Return the LoopBounds object if.
Definition: LoopInfo.cpp:200
llvm::makePostTransformationMetadata
llvm::MDNode * makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, llvm::ArrayRef< llvm::StringRef > RemovePrefixes, llvm::ArrayRef< llvm::MDNode * > AddAttrs)
Create a new LoopID after the loop has been transformed.
Definition: LoopInfo.cpp:1046
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information", true, true) INITIALIZE_PASS_END(LoopInfoWrapperPass
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1505
llvm::LoopBase< BasicBlock, Loop >::getLoopLatches
void getLoopLatches(SmallVectorImpl< BasicBlock * > &LoopLatches) const
Return all loop latch blocks of this loop.
Definition: LoopInfo.h:334
llvm::Loop::getInductionDescriptor
bool getInductionDescriptor(ScalarEvolution &SE, InductionDescriptor &IndDesc) const
Get the loop induction descriptor for the loop induction variable.
Definition: LoopInfo.cpp:331
llvm::InductionDescriptor
A struct for saving information about induction variables.
Definition: IVDescriptors.h:267
llvm::Loop::setLoopAlreadyUnrolled
void setLoopAlreadyUnrolled()
Add llvm.loop.unroll.disable to this loop's loop id metadata.
Definition: LoopInfo.cpp:532
llvm::LoopInfoBase::analyze
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:545
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::LoopInfoWrapperPass::LoopInfoWrapperPass
LoopInfoWrapperPass()
Definition: LoopInfo.cpp:1089
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:648
llvm::User
Definition: User.h:44
llvm::Loop::isAnnotatedParallel
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
Definition: LoopInfo.cpp:559
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopBase< BasicBlock, Loop >::end
iterator end() const
Definition: LoopInfo.h:155
llvm::LoopBase< BasicBlock, Loop >::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
false
Definition: StackSlotColoring.cpp:142
llvm::MemorySSAUpdater::moveToPlace
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1200
llvm::LoopBlocksTraversal::begin
POTIterator begin()
Postorder traversal over the graph.
Definition: LoopIterator.h:216
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2755
llvm::make_scope_exit
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:58
llvm::Type::isTokenTy
bool isTokenTy() const
Return true if this is 'token'.
Definition: Type.h:199
llvm::printLoop
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")
Function to print a loop's contents as LLVM's text IR assembly.
Definition: LoopInfo.cpp:972
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
IRPrintingPasses.h
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
DebugLoc.h
SmallPtrSet.h
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::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:670
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
IVDescriptors.h
PrintPasses.h
llvm::None
const NoneType None
Definition: None.h:23
LoopIterator.h
llvm::Loop::LoopBounds::Direction
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:697
llvm::Loop::getLocRange
LocRange getLocRange() const
Return the source code span of the loop.
Definition: LoopInfo.cpp:628
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:277
CFG.h
LoopInfo.h
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3086
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:3885
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:712
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1102
llvm::LoopBlocksDFS
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
llvm::InductionDescriptor::getStartValue
Value * getStartValue() const
Definition: IVDescriptors.h:281
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:471
llvm::cl::opt
Definition: CommandLine.h:1419
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1178
isBlockInLCSSAForm
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, const DominatorTree &DT)
Definition: LoopInfo.cpp:423
llvm::pdb::Unknown
@ Unknown
Definition: PDBTypes.h:395
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:56
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:249
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:58
llvm::DenseMap
Definition: DenseMap.h:714
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::Loop::getIncomingAndBackEdge
bool getIncomingAndBackEdge(BasicBlock *&Incoming, BasicBlock *&Backedge) const
Obtain the unique incoming and back edge.
Definition: LoopInfo.cpp:123
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:963
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:721
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
llvm::Loop::LoopBounds::getDirection
Direction getDirection() const
Get the direction of the loop.
Definition: LoopInfo.cpp:273
llvm::LoopBase< BasicBlock, Loop >::getLoopPreheader
BasicBlock * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1570
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1142
llvm::MDString::get
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:467
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::Loop::LocRange
A range representing the start and end location of a loop.
Definition: LoopInfo.h:532
llvm::LoopBase< BasicBlock, Loop >::hasDedicatedExits
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:92
llvm::InductionDescriptor::getConstIntStepValue
ConstantInt * getConstIntStepValue() const
Definition: IVDescriptors.cpp:976
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:958
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:328
llvm::po_iterator
Definition: PostOrderIterator.h:95
llvm::CmpInst::BAD_ICMP_PREDICATE
@ BAD_ICMP_PREDICATE
Definition: InstrTypes.h:755
llvm::LoopInfo::erase
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:871
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::MDNode
Metadata node.
Definition: Metadata.h:897
llvm::LoopInfoWrapperPass::print
void print(raw_ostream &O, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: LoopInfo.cpp:1123
llvm::LoopBlocksDFS::POIterator
std::vector< BasicBlock * >::const_iterator POIterator
Postorder list iterators.
Definition: LoopIterator.h:100
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::Value::printAsOperand
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:4691
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3083
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:751
llvm::LoopBase::removeChildLoop
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:404
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopInfo
Definition: LoopInfo.h:1079
llvm::LoopBase< BasicBlock, Loop >::print
void print(raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:384
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:1512
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::Loop::makeLoopInvariant
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=nullptr) const
If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivi...
Definition: LoopInfo.cpp:73
llvm::Loop::getCanonicalInductionVariable
PHINode * getCanonicalInductionVariable() const
Check to see if the loop has a canonical induction variable: an integer recurrence that starts at 0 a...
Definition: LoopInfo.cpp:149
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::InductionDescriptor::getStep
const SCEV * getStep() const
Definition: IVDescriptors.h:283
llvm::LoopBase::isOutermost
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
Definition: LoopInfo.h:168
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:272
llvm::LoopInfoWrapperPass::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: LoopInfo.cpp:1106
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
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::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
llvm::findOptionMDForLoop
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
Definition: LoopInfo.cpp:1038
llvm::Loop::hasLoopInvariantOperands
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:69
llvm::PredIterator
Definition: CFG.h:43
llvm::MDNode::getDistinct
static MDTuple * getDistinct(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1206
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:148
llvm::Init
Definition: Record.h:271
llvm::LoopAnalysis::run
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:954
llvm::Loop::getBounds
Optional< LoopBounds > getBounds(ScalarEvolution &SE) const
Return the struct LoopBounds collected if all struct members are found, else None.
Definition: LoopInfo.cpp:286
llvm::ScalarEvolution::isLoopInvariant
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
Definition: ScalarEvolution.cpp:12480
llvm::Loop::LocRange::getStart
const DebugLoc & getStart() const
Definition: LoopInfo.h:542
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
true
Natural Loop true
Definition: LoopInfo.cpp:1098
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::LoopBase::isInnermost
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
Definition: LoopInfo.h:165
llvm::InductionDescriptor::isInductionPHI
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
Definition: IVDescriptors.cpp:1184
llvm::Loop::LoopBounds
Below are some utilities to get the loop guard, loop bounds and induction variable,...
Definition: LoopInfo.h:634
llvm::isValidAsAccessGroup
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
Definition: LoopInfo.cpp:1042
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
H
#define H(x, y, z)
Definition: MD5.cpp:58
llvm::Loop::setLoopID
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:520
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:454
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::Loop::isAuxiliaryInductionVariable
bool isAuxiliaryInductionVariable(PHINode &AuxIndVar, ScalarEvolution &SE) const
Return true if the given PHINode AuxIndVar is.
Definition: LoopInfo.cpp:339
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:151
llvm::LoopInfoBase< BasicBlock, Loop >
llvm::Loop::LoopBounds::getCanonicalPredicate
ICmpInst::Predicate getCanonicalPredicate() const
Return the canonical predicate for the latch compare instruction, if able to be calcuated.
Definition: LoopInfo.cpp:231
llvm::LoopBase::isInvalid
bool isInvalid() const
Return true if this loop is no longer valid.
Definition: LoopInfo.h:215
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::Loop::getLoopID
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:496
llvm::MemorySSA::BeforeTerminator
@ BeforeTerminator
Definition: MemorySSA.h:791
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
llvm::LoopBase< BasicBlock, Loop >::getHeader
BasicBlock * getHeader() const
Definition: LoopInfo.h:104
PassManager.h
llvm::Loop::isRecursivelyLCSSAForm
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:461
llvm::Loop::dump
void dump() const
Definition: LoopInfo.cpp:662
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:184
llvm::Loop::setLoopMustProgress
void setLoopMustProgress()
Add llvm.loop.mustprogress to this loop's loop id metadata.
Definition: LoopInfo.cpp:543
llvm::MDNode::replaceOperandWith
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:871
ScalarEvolutionExpressions.h
llvm::pred_begin
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
MemorySSA.h
Instructions.h
llvm::LoopBase< BasicBlock, Loop >::iterator
std::vector< Loop * >::const_iterator iterator
Definition: LoopInfo.h:151
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::Loop::isSafeToClone
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:478
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:799
VerifyLoopInfoX
static cl::opt< bool, true > VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), cl::Hidden, cl::desc("Verify loop info (time consuming)"))
llvm::PHINode
Definition: Instructions.h:2572
llvm::LoopInfoBase< BasicBlock, Loop >::iterator
std::vector< Loop * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:935
ScopeExit.h
llvm::forcePrintModuleIR
bool forcePrintModuleIR()
Definition: PrintPasses.cpp:81
llvm::AnalysisUsage::addRequiredTransitive
AnalysisUsage & addRequiredTransitive()
Definition: PassAnalysisSupport.h:81
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:313
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:43
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::ConstantInt::isOne
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:198
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::Loop::getInductionVariable
PHINode * getInductionVariable(ScalarEvolution &SE) const
Return the loop induction variable if found, else return nullptr.
Definition: LoopInfo.cpp:293
LLVMContext.h
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::Loop::isRotatedForm
bool isRotatedForm() const
Return true if the loop is in rotated form.
Definition: LoopInfo.h:784
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:411
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3005
raw_ostream.h
llvm::MDString
A single uniqued string.
Definition: Metadata.h:611
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::LoopPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:966
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:434
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:152
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3084
llvm::MDOperand
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:744
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3098
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1232
llvm::LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA
bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, const BasicBlock *ExitBB) const
Definition: LoopInfo.cpp:928
llvm::LoopInfoWrapperPass::ID
static char ID
Definition: LoopInfo.h:1261
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38