LLVM  15.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) {
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 (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) 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);
462  });
463 }
464 
466  const LoopInfo &LI) 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);
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  // FIXME: it should be ok to clone CallBrInst's if we correctly update the
486  // operand list to reflect the newly cloned labels.
487  for (BasicBlock *BB : this->blocks()) {
488  if (isa<IndirectBrInst>(BB->getTerminator()) ||
489  isa<CallBrInst>(BB->getTerminator()))
490  return false;
491 
492  for (Instruction &I : *BB)
493  if (auto *CB = dyn_cast<CallBase>(&I))
494  if (CB->cannotDuplicate())
495  return false;
496  }
497  return true;
498 }
499 
501  MDNode *LoopID = nullptr;
502 
503  // Go through the latch blocks and check the terminator for the metadata.
504  SmallVector<BasicBlock *, 4> LatchesBlocks;
505  getLoopLatches(LatchesBlocks);
506  for (BasicBlock *BB : LatchesBlocks) {
507  Instruction *TI = BB->getTerminator();
508  MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
509 
510  if (!MD)
511  return nullptr;
512 
513  if (!LoopID)
514  LoopID = MD;
515  else if (MD != LoopID)
516  return nullptr;
517  }
518  if (!LoopID || LoopID->getNumOperands() == 0 ||
519  LoopID->getOperand(0) != LoopID)
520  return nullptr;
521  return LoopID;
522 }
523 
524 void Loop::setLoopID(MDNode *LoopID) const {
525  assert((!LoopID || LoopID->getNumOperands() > 0) &&
526  "Loop ID needs at least one operand");
527  assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
528  "Loop ID should refer to itself");
529 
530  SmallVector<BasicBlock *, 4> LoopLatches;
531  getLoopLatches(LoopLatches);
532  for (BasicBlock *BB : LoopLatches)
533  BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
534 }
535 
538 
539  MDNode *DisableUnrollMD =
540  MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
541  MDNode *LoopID = getLoopID();
543  Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
544  setLoopID(NewLoopID);
545 }
546 
549 
550  MDNode *MustProgress = findOptionMDForLoop(this, "llvm.loop.mustprogress");
551 
552  if (MustProgress)
553  return;
554 
555  MDNode *MustProgressMD =
556  MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress"));
557  MDNode *LoopID = getLoopID();
558  MDNode *NewLoopID =
559  makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD});
560  setLoopID(NewLoopID);
561 }
562 
564  MDNode *DesiredLoopIdMetadata = getLoopID();
565 
566  if (!DesiredLoopIdMetadata)
567  return false;
568 
569  MDNode *ParallelAccesses =
570  findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
572  ParallelAccessGroups; // For scalable 'contains' check.
573  if (ParallelAccesses) {
574  for (const MDOperand &MD : drop_begin(ParallelAccesses->operands())) {
575  MDNode *AccGroup = cast<MDNode>(MD.get());
576  assert(isValidAsAccessGroup(AccGroup) &&
577  "List item must be an access group");
578  ParallelAccessGroups.insert(AccGroup);
579  }
580  }
581 
582  // The loop branch contains the parallel loop metadata. In order to ensure
583  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
584  // dependencies (thus converted the loop back to a sequential loop), check
585  // that all the memory instructions in the loop belong to an access group that
586  // is parallel to this loop.
587  for (BasicBlock *BB : this->blocks()) {
588  for (Instruction &I : *BB) {
589  if (!I.mayReadOrWriteMemory())
590  continue;
591 
592  if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
593  auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
594  if (AG->getNumOperands() == 0) {
595  assert(isValidAsAccessGroup(AG) && "Item must be an access group");
596  return ParallelAccessGroups.count(AG);
597  }
598 
599  for (const MDOperand &AccessListItem : AG->operands()) {
600  MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
601  assert(isValidAsAccessGroup(AccGroup) &&
602  "List item must be an access group");
603  if (ParallelAccessGroups.count(AccGroup))
604  return true;
605  }
606  return false;
607  };
608 
609  if (ContainsAccessGroup(AccessGroup))
610  continue;
611  }
612 
613  // The memory instruction can refer to the loop identifier metadata
614  // directly or indirectly through another list metadata (in case of
615  // nested parallel loops). The loop identifier metadata refers to
616  // itself so we can check both cases with the same routine.
617  MDNode *LoopIdMD =
618  I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
619 
620  if (!LoopIdMD)
621  return false;
622 
623  if (!llvm::is_contained(LoopIdMD->operands(), DesiredLoopIdMetadata))
624  return false;
625  }
626  }
627  return true;
628 }
629 
631 
633  // If we have a debug location in the loop ID, then use it.
634  if (MDNode *LoopID = getLoopID()) {
635  DebugLoc Start;
636  // We use the first DebugLoc in the header as the start location of the loop
637  // and if there is a second DebugLoc in the header we use it as end location
638  // of the loop.
639  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
640  if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
641  if (!Start)
642  Start = DebugLoc(L);
643  else
644  return LocRange(Start, DebugLoc(L));
645  }
646  }
647 
648  if (Start)
649  return LocRange(Start);
650  }
651 
652  // Try the pre-header first.
653  if (BasicBlock *PHeadBB = getLoopPreheader())
654  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
655  return LocRange(DL);
656 
657  // If we have no pre-header or there are no instructions with debug
658  // info in it, try the header.
659  if (BasicBlock *HeadBB = getHeader())
660  return LocRange(HeadBB->getTerminator()->getDebugLoc());
661 
662  return LocRange();
663 }
664 
665 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
666 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
667 
669  print(dbgs(), /*Verbose=*/true);
670 }
671 #endif
672 
673 //===----------------------------------------------------------------------===//
674 // UnloopUpdater implementation
675 //
676 
677 namespace {
678 /// Find the new parent loop for all blocks within the "unloop" whose last
679 /// backedges has just been removed.
680 class UnloopUpdater {
681  Loop &Unloop;
682  LoopInfo *LI;
683 
684  LoopBlocksDFS DFS;
685 
686  // Map unloop's immediate subloops to their nearest reachable parents. Nested
687  // loops within these subloops will not change parents. However, an immediate
688  // subloop's new parent will be the nearest loop reachable from either its own
689  // exits *or* any of its nested loop's exits.
690  DenseMap<Loop *, Loop *> SubloopParents;
691 
692  // Flag the presence of an irreducible backedge whose destination is a block
693  // directly contained by the original unloop.
694  bool FoundIB = false;
695 
696 public:
697  UnloopUpdater(Loop *UL, LoopInfo *LInfo) : Unloop(*UL), LI(LInfo), DFS(UL) {}
698 
699  void updateBlockParents();
700 
701  void removeBlocksFromAncestors();
702 
703  void updateSubloopParents();
704 
705 protected:
706  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
707 };
708 } // end anonymous namespace
709 
710 /// Update the parent loop for all blocks that are directly contained within the
711 /// original "unloop".
712 void UnloopUpdater::updateBlockParents() {
713  if (Unloop.getNumBlocks()) {
714  // Perform a post order CFG traversal of all blocks within this loop,
715  // propagating the nearest loop from successors to predecessors.
716  LoopBlocksTraversal Traversal(DFS, LI);
717  for (BasicBlock *POI : Traversal) {
718 
719  Loop *L = LI->getLoopFor(POI);
720  Loop *NL = getNearestLoop(POI, L);
721 
722  if (NL != L) {
723  // For reducible loops, NL is now an ancestor of Unloop.
724  assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
725  "uninitialized successor");
726  LI->changeLoopFor(POI, NL);
727  } else {
728  // Or the current block is part of a subloop, in which case its parent
729  // is unchanged.
730  assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
731  }
732  }
733  }
734  // Each irreducible loop within the unloop induces a round of iteration using
735  // the DFS result cached by Traversal.
736  bool Changed = FoundIB;
737  for (unsigned NIters = 0; Changed; ++NIters) {
738  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
739  (void) NIters;
740 
741  // Iterate over the postorder list of blocks, propagating the nearest loop
742  // from successors to predecessors as before.
743  Changed = false;
744  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
745  POE = DFS.endPostorder();
746  POI != POE; ++POI) {
747 
748  Loop *L = LI->getLoopFor(*POI);
749  Loop *NL = getNearestLoop(*POI, L);
750  if (NL != L) {
751  assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
752  "uninitialized successor");
753  LI->changeLoopFor(*POI, NL);
754  Changed = true;
755  }
756  }
757  }
758 }
759 
760 /// Remove unloop's blocks from all ancestors below their new parents.
761 void UnloopUpdater::removeBlocksFromAncestors() {
762  // Remove all unloop's blocks (including those in nested subloops) from
763  // ancestors below the new parent loop.
764  for (BasicBlock *BB : Unloop.blocks()) {
765  Loop *OuterParent = LI->getLoopFor(BB);
766  if (Unloop.contains(OuterParent)) {
767  while (OuterParent->getParentLoop() != &Unloop)
768  OuterParent = OuterParent->getParentLoop();
769  OuterParent = SubloopParents[OuterParent];
770  }
771  // Remove blocks from former Ancestors except Unloop itself which will be
772  // deleted.
773  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
774  OldParent = OldParent->getParentLoop()) {
775  assert(OldParent && "new loop is not an ancestor of the original");
776  OldParent->removeBlockFromLoop(BB);
777  }
778  }
779 }
780 
781 /// Update the parent loop for all subloops directly nested within unloop.
782 void UnloopUpdater::updateSubloopParents() {
783  while (!Unloop.isInnermost()) {
784  Loop *Subloop = *std::prev(Unloop.end());
785  Unloop.removeChildLoop(std::prev(Unloop.end()));
786 
787  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
788  if (Loop *Parent = SubloopParents[Subloop])
789  Parent->addChildLoop(Subloop);
790  else
791  LI->addTopLevelLoop(Subloop);
792  }
793 }
794 
795 /// Return the nearest parent loop among this block's successors. If a successor
796 /// is a subloop header, consider its parent to be the nearest parent of the
797 /// subloop's exits.
798 ///
799 /// For subloop blocks, simply update SubloopParents and return NULL.
800 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
801 
802  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
803  // is considered uninitialized.
804  Loop *NearLoop = BBLoop;
805 
806  Loop *Subloop = nullptr;
807  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
808  Subloop = NearLoop;
809  // Find the subloop ancestor that is directly contained within Unloop.
810  while (Subloop->getParentLoop() != &Unloop) {
811  Subloop = Subloop->getParentLoop();
812  assert(Subloop && "subloop is not an ancestor of the original loop");
813  }
814  // Get the current nearest parent of the Subloop exits, initially Unloop.
815  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
816  }
817 
819  if (I == E) {
820  assert(!Subloop && "subloop blocks must have a successor");
821  NearLoop = nullptr; // unloop blocks may now exit the function.
822  }
823  for (; I != E; ++I) {
824  if (*I == BB)
825  continue; // self loops are uninteresting
826 
827  Loop *L = LI->getLoopFor(*I);
828  if (L == &Unloop) {
829  // This successor has not been processed. This path must lead to an
830  // irreducible backedge.
831  assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
832  FoundIB = true;
833  }
834  if (L != &Unloop && Unloop.contains(L)) {
835  // Successor is in a subloop.
836  if (Subloop)
837  continue; // Branching within subloops. Ignore it.
838 
839  // BB branches from the original into a subloop header.
840  assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
841 
842  // Get the current nearest parent of the Subloop's exits.
843  L = SubloopParents[L];
844  // L could be Unloop if the only exit was an irreducible backedge.
845  }
846  if (L == &Unloop) {
847  continue;
848  }
849  // Handle critical edges from Unloop into a sibling loop.
850  if (L && !L->contains(&Unloop)) {
851  L = L->getParentLoop();
852  }
853  // Remember the nearest parent loop among successors or subloop exits.
854  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
855  NearLoop = L;
856  }
857  if (Subloop) {
858  SubloopParents[Subloop] = NearLoop;
859  return BBLoop;
860  }
861  return NearLoop;
862 }
863 
864 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
865 
868  // Check whether the analysis, all analyses on functions, or the function's
869  // CFG have been preserved.
870  auto PAC = PA.getChecker<LoopAnalysis>();
871  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
872  PAC.preservedSet<CFGAnalyses>());
873 }
874 
875 void LoopInfo::erase(Loop *Unloop) {
876  assert(!Unloop->isInvalid() && "Loop has already been erased!");
877 
878  auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
879 
880  // First handle the special case of no parent loop to simplify the algorithm.
881  if (Unloop->isOutermost()) {
882  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
883  for (BasicBlock *BB : Unloop->blocks()) {
884  // Don't reparent blocks in subloops.
885  if (getLoopFor(BB) != Unloop)
886  continue;
887 
888  // Blocks no longer have a parent but are still referenced by Unloop until
889  // the Unloop object is deleted.
890  changeLoopFor(BB, nullptr);
891  }
892 
893  // Remove the loop from the top-level LoopInfo object.
894  for (iterator I = begin();; ++I) {
895  assert(I != end() && "Couldn't find loop");
896  if (*I == Unloop) {
897  removeLoop(I);
898  break;
899  }
900  }
901 
902  // Move all of the subloops to the top-level.
903  while (!Unloop->isInnermost())
904  addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
905 
906  return;
907  }
908 
909  // Update the parent loop for all blocks within the loop. Blocks within
910  // subloops will not change parents.
911  UnloopUpdater Updater(Unloop, this);
912  Updater.updateBlockParents();
913 
914  // Remove blocks from former ancestor loops.
915  Updater.removeBlocksFromAncestors();
916 
917  // Add direct subloops as children in their new parent loop.
918  Updater.updateSubloopParents();
919 
920  // Remove unloop from its parent loop.
921  Loop *ParentLoop = Unloop->getParentLoop();
922  for (Loop::iterator I = ParentLoop->begin();; ++I) {
923  assert(I != ParentLoop->end() && "Couldn't find loop");
924  if (*I == Unloop) {
925  ParentLoop->removeChildLoop(I);
926  break;
927  }
928  }
929 }
930 
931 bool
933  const BasicBlock *ExitBB) const {
934  if (V->getType()->isTokenTy())
935  // We can't form PHIs of token type, so the definition of LCSSA excludes
936  // values of that type.
937  return false;
938 
939  const Instruction *I = dyn_cast<Instruction>(V);
940  if (!I)
941  return false;
942  const Loop *L = getLoopFor(I->getParent());
943  if (!L)
944  return false;
945  if (L->contains(ExitBB))
946  // Could be an exit bb of a subloop and contained in defining loop
947  return false;
948 
949  // We found a (new) out-of-loop use location, for a value defined in-loop.
950  // (Note that because of LCSSA, we don't have to account for values defined
951  // in sibling loops. Such values will have LCSSA phis of their own in the
952  // common parent loop.)
953  return true;
954 }
955 
956 AnalysisKey LoopAnalysis::Key;
957 
959  // FIXME: Currently we create a LoopInfo from scratch for every function.
960  // This may prove to be too wasteful due to deallocating and re-allocating
961  // memory each time for the underlying map and vector datastructures. At some
962  // point it may prove worthwhile to use a freelist and recycle LoopInfo
963  // objects. I don't want to add that kind of complexity until the scope of
964  // the problem is better understood.
965  LoopInfo LI;
967  return LI;
968 }
969 
972  AM.getResult<LoopAnalysis>(F).print(OS);
973  return PreservedAnalyses::all();
974 }
975 
976 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
977 
978  if (forcePrintModuleIR()) {
979  // handling -print-module-scope
980  OS << Banner << " (loop: ";
981  L.getHeader()->printAsOperand(OS, false);
982  OS << ")\n";
983 
984  // printing whole module
985  OS << *L.getHeader()->getModule();
986  return;
987  }
988 
989  OS << Banner;
990 
991  auto *PreHeader = L.getLoopPreheader();
992  if (PreHeader) {
993  OS << "\n; Preheader:";
994  PreHeader->print(OS);
995  OS << "\n; Loop:";
996  }
997 
998  for (auto *Block : L.blocks())
999  if (Block)
1000  Block->print(OS);
1001  else
1002  OS << "Printing <null> block";
1003 
1004  SmallVector<BasicBlock *, 8> ExitBlocks;
1005  L.getExitBlocks(ExitBlocks);
1006  if (!ExitBlocks.empty()) {
1007  OS << "\n; Exit blocks";
1008  for (auto *Block : ExitBlocks)
1009  if (Block)
1010  Block->print(OS);
1011  else
1012  OS << "Printing <null> block";
1013  }
1014 }
1015 
1017  // No loop metadata node, no loop properties.
1018  if (!LoopID)
1019  return nullptr;
1020 
1021  // First operand should refer to the metadata node itself, for legacy reasons.
1022  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1023  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1024 
1025  // Iterate over the metdata node operands and look for MDString metadata.
1026  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
1027  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
1028  if (!MD || MD->getNumOperands() < 1)
1029  continue;
1030  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1031  if (!S)
1032  continue;
1033  // Return the operand node if MDString holds expected metadata.
1034  if (Name.equals(S->getString()))
1035  return MD;
1036  }
1037 
1038  // Loop property not found.
1039  return nullptr;
1040 }
1041 
1043  return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
1044 }
1045 
1046 /// Find string metadata for loop
1047 ///
1048 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1049 /// operand or null otherwise. If the string metadata is not found return
1050 /// Optional's not-a-value.
1052  StringRef Name) {
1053  MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1054  if (!MD)
1055  return None;
1056  switch (MD->getNumOperands()) {
1057  case 1:
1058  return nullptr;
1059  case 2:
1060  return &MD->getOperand(1);
1061  default:
1062  llvm_unreachable("loop metadata has 0 or 1 operand");
1063  }
1064 }
1065 
1067  StringRef Name) {
1068  MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1069  if (!MD)
1070  return None;
1071  switch (MD->getNumOperands()) {
1072  case 1:
1073  // When the value is absent it is interpreted as 'attribute set'.
1074  return true;
1075  case 2:
1076  if (ConstantInt *IntMD =
1077  mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
1078  return IntMD->getZExtValue();
1079  return true;
1080  }
1081  llvm_unreachable("unexpected number of options");
1082 }
1083 
1085  return getOptionalBoolLoopAttribute(TheLoop, Name).getValueOr(false);
1086 }
1087 
1089  StringRef Name) {
1090  const MDOperand *AttrMD =
1091  findStringMetadataForLoop(TheLoop, Name).getValueOr(nullptr);
1092  if (!AttrMD)
1093  return None;
1094 
1095  ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
1096  if (!IntMD)
1097  return None;
1098 
1099  return IntMD->getSExtValue();
1100 }
1101 
1103  int Default) {
1104  return getOptionalIntLoopAttribute(TheLoop, Name).getValueOr(Default);
1105 }
1106 
1107 bool llvm::isFinite(const Loop *L) {
1108  return L->getHeader()->getParent()->willReturn();
1109 }
1110 
1111 static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
1112 
1113 bool llvm::hasMustProgress(const Loop *L) {
1115 }
1116 
1117 bool llvm::isMustProgress(const Loop *L) {
1118  return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L);
1119 }
1120 
1122  return Node->getNumOperands() == 0 && Node->isDistinct();
1123 }
1124 
1126  MDNode *OrigLoopID,
1127  ArrayRef<StringRef> RemovePrefixes,
1128  ArrayRef<MDNode *> AddAttrs) {
1129  // First remove any existing loop metadata related to this transformation.
1131 
1132  // Reserve first location for self reference to the LoopID metadata node.
1133  MDs.push_back(nullptr);
1134 
1135  // Remove metadata for the transformation that has been applied or that became
1136  // outdated.
1137  if (OrigLoopID) {
1138  for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
1139  bool IsVectorMetadata = false;
1140  Metadata *Op = OrigLoopID->getOperand(i);
1141  if (MDNode *MD = dyn_cast<MDNode>(Op)) {
1142  const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1143  if (S)
1144  IsVectorMetadata =
1145  llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
1146  return S->getString().startswith(Prefix);
1147  });
1148  }
1149  if (!IsVectorMetadata)
1150  MDs.push_back(Op);
1151  }
1152  }
1153 
1154  // Add metadata to avoid reapplying a transformation, such as
1155  // llvm.loop.unroll.disable and llvm.loop.isvectorized.
1156  MDs.append(AddAttrs.begin(), AddAttrs.end());
1157 
1158  MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
1159  // Replace the temporary node with a self-reference.
1160  NewLoopID->replaceOperandWith(0, NewLoopID);
1161  return NewLoopID;
1162 }
1163 
1164 //===----------------------------------------------------------------------===//
1165 // LoopInfo implementation
1166 //
1167 
1170 }
1171 
1172 char LoopInfoWrapperPass::ID = 0;
1173 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1174  true, true)
1178 
1180  releaseMemory();
1181  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
1182  return false;
1183 }
1184 
1186  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
1187  // function each time verifyAnalysis is called is very expensive. The
1188  // -verify-loop-info option can enable this. In order to perform some
1189  // checking by default, LoopPass has been taught to call verifyLoop manually
1190  // during loop pass sequences.
1191  if (VerifyLoopInfo) {
1192  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1193  LI.verify(DT);
1194  }
1195 }
1196 
1198  AU.setPreservesAll();
1200 }
1201 
1203  LI.print(OS);
1204 }
1205 
1208  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1209  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1210  LI.verify(DT);
1211  return PreservedAnalyses::all();
1212 }
1213 
1214 //===----------------------------------------------------------------------===//
1215 // LoopBlocksDFS implementation
1216 //
1217 
1218 /// Traverse the loop blocks and store the DFS result.
1219 /// Useful for clients that just want the final DFS result and don't need to
1220 /// visit blocks during the initial traversal.
1222  LoopBlocksTraversal Traversal(*this, LI);
1223  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
1224  POE = Traversal.end();
1225  POI != POE; ++POI)
1226  ;
1227 }
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:494
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:1206
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:280
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::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:4576
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:780
llvm::cl::Prefix
@ Prefix
Definition: CommandLine.h:160
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:447
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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:866
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:689
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:630
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:620
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
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:668
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:1102
Information
Natural Loop Information
Definition: LoopInfo.cpp:1176
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1551
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:1271
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:154
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:1016
loops
loops
Definition: LoopInfo.cpp:1176
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:1197
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1300
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::MDNode::operands
op_range operands() const
Definition: Metadata.h:1202
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1210
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:1125
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:1607
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: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:536
llvm::LoopInfoBase::analyze
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:547
llvm::getOptionalIntLoopAttribute
llvm::Optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
Definition: LoopInfo.cpp:1088
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:1168
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:667
llvm::User
Definition: User.h:44
llvm::Loop::isAnnotatedParallel
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
Definition: LoopInfo.cpp:563
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::Optional::getValueOr
constexpr T getValueOr(U &&value) const &
Definition: Optional.h:289
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
llvm::getOptionalBoolLoopAttribute
Optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
Definition: LoopInfo.cpp:1066
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:2849
llvm::make_scope_exit
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
llvm::Type::isTokenTy
bool isTokenTy() const
Return true if this is 'token'.
Definition: Type.h:188
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:976
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:355
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
LLVMLoopMustProgress
static const char * LLVMLoopMustProgress
Definition: LoopInfo.cpp:1111
llvm::isMustProgress
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
Definition: LoopInfo.cpp:1117
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::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:667
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:704
llvm::Loop::getLocRange
LocRange getLocRange() const
Return the source code span of the loop.
Definition: LoopInfo.cpp:632
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:279
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:3180
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4407
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:1204
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:1051
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:1392
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:621
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1186
isBlockInLCSSAForm
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, const DominatorTree &DT)
Definition: LoopInfo.cpp:427
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:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:716
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:970
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:731
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:1672
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1221
llvm::MDString::get
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:499
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:533
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:1107
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:875
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:937
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:1202
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:4662
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3177
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: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:1086
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:1614
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
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:168
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:269
llvm::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:1185
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:1042
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:1308
llvm::Init
Definition: Record.h:281
llvm::LoopAnalysis::run
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:958
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:13248
llvm::Loop::LocRange::getStart
const DebugLoc & getStart() const
Definition: LoopInfo.h:543
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:1177
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:1504
llvm::Loop::LoopBounds
Below are some utilities to get the loop guard, loop bounds and induction variable,...
Definition: LoopInfo.h:641
llvm::isValidAsAccessGroup
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
Definition: LoopInfo.cpp:1121
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:524
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:458
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:344
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: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:500
llvm::MemorySSA::BeforeTerminator
@ BeforeTerminator
Definition: MemorySSA.h:802
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::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:465
llvm::Loop::dump
void dump() const
Definition: LoopInfo.cpp:666
llvm::Function::mustProgress
bool mustProgress() const
Determine if the function is required to make forward progress.
Definition: Function.h:614
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:547
llvm::MDNode::replaceOperandWith
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:909
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:1113
llvm::LoopBase< BasicBlock, Loop >::iterator
std::vector< Loop * >::const_iterator iterator
Definition: LoopInfo.h:151
Dominators.h
llvm::getBooleanLoopAttribute
bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)
Returns true if Name is applied to TheLoop and enabled.
Definition: LoopInfo.cpp:1084
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:2664
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:942
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: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:383
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:791
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:405
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3099
raw_ostream.h
llvm::MDString
A single uniqued string.
Definition: Metadata.h:612
InitializePasses.h
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:970
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:3178
llvm::MDOperand
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:773
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3192
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1246
llvm::LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA
bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, const BasicBlock *ExitBB) const
Definition: LoopInfo.cpp:932
llvm::LoopInfoWrapperPass::ID
static char ID
Definition: LoopInfo.h:1275
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