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