LLVM  10.0.0svn
LoopInfo.cpp
Go to the documentation of this file.
1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the LoopInfo class that is used to identify natural loops
10 // and determine the loop depth of various nodes of the CFG. Note that the
11 // loops identified may actually be several natural loops that share the same
12 // header node... not just a single natural loop.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/ADT/ScopeExit.h"
19 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/Config/llvm-config.h"
28 #include "llvm/IR/CFG.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/DebugLoc.h"
31 #include "llvm/IR/Dominators.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/LLVMContext.h"
35 #include "llvm/IR/Metadata.h"
36 #include "llvm/IR/PassManager.h"
38 #include "llvm/Support/Debug.h"
40 #include <algorithm>
41 using namespace llvm;
42 
43 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
46 
47 // Always verify loopinfo if expensive checking is enabled.
48 #ifdef EXPENSIVE_CHECKS
49 bool llvm::VerifyLoopInfo = true;
50 #else
51 bool llvm::VerifyLoopInfo = false;
52 #endif
54  VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
55  cl::Hidden, cl::desc("Verify loop info (time consuming)"));
56 
57 //===----------------------------------------------------------------------===//
58 // Loop implementation
59 //
60 
61 bool Loop::isLoopInvariant(const Value *V) const {
62  if (const Instruction *I = dyn_cast<Instruction>(V))
63  return !contains(I);
64  return true; // All non-instructions are loop invariant
65 }
66 
68  return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
69 }
70 
71 bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt,
72  MemorySSAUpdater *MSSAU) const {
73  if (Instruction *I = dyn_cast<Instruction>(V))
74  return makeLoopInvariant(I, Changed, InsertPt, MSSAU);
75  return true; // All non-instructions are loop-invariant.
76 }
77 
78 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
79  Instruction *InsertPt,
80  MemorySSAUpdater *MSSAU) const {
81  // Test if the value is already loop-invariant.
82  if (isLoopInvariant(I))
83  return true;
85  return false;
86  if (I->mayReadFromMemory())
87  return false;
88  // EH block instructions are immobile.
89  if (I->isEHPad())
90  return false;
91  // Determine the insertion point, unless one was given.
92  if (!InsertPt) {
93  BasicBlock *Preheader = getLoopPreheader();
94  // Without a preheader, hoisting is not feasible.
95  if (!Preheader)
96  return false;
97  InsertPt = Preheader->getTerminator();
98  }
99  // Don't hoist instructions with loop-variant operands.
100  for (Value *Operand : I->operands())
101  if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU))
102  return false;
103 
104  // Hoist.
105  I->moveBefore(InsertPt);
106  if (MSSAU)
107  if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I))
108  MSSAU->moveToPlace(MUD, InsertPt->getParent(), MemorySSA::End);
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.
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.
170 static ICmpInst *getLatchCmpInst(const Loop &L) {
171  if (BasicBlock *Latch = L.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 = getLatchCmpInst(L);
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");
296  ICmpInst *CmpInst = getLatchCmpInst(*this);
297  if (!CmpInst)
298  return nullptr;
299 
300  Instruction *LatchCmpOp0 = dyn_cast<Instruction>(CmpInst->getOperand(0));
301  Instruction *LatchCmpOp1 = dyn_cast<Instruction>(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  Instruction *StepInst = IndDesc.getInductionBinOp();
309 
310  // case 1:
311  // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
312  // StepInst = IndVar + step
313  // cmp = StepInst < FinalValue
314  if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1)
315  return &IndVar;
316 
317  // case 2:
318  // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
319  // StepInst = IndVar + step
320  // cmp = IndVar < FinalValue
321  if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1)
322  return &IndVar;
323  }
324 
325  return nullptr;
326 }
327 
329  InductionDescriptor &IndDesc) const {
330  if (PHINode *IndVar = getInductionVariable(SE))
331  return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc);
332 
333  return false;
334 }
335 
337  ScalarEvolution &SE) const {
338  // Located in the loop header
339  BasicBlock *Header = getHeader();
340  if (AuxIndVar.getParent() != Header)
341  return false;
342 
343  // No uses outside of the loop
344  for (User *U : AuxIndVar.users())
345  if (const Instruction *I = dyn_cast<Instruction>(U))
346  if (!contains(I))
347  return false;
348 
349  InductionDescriptor IndDesc;
350  if (!InductionDescriptor::isInductionPHI(&AuxIndVar, this, &SE, IndDesc))
351  return false;
352 
353  // The step instruction opcode should be add or sub.
354  if (IndDesc.getInductionOpcode() != Instruction::Add &&
355  IndDesc.getInductionOpcode() != Instruction::Sub)
356  return false;
357 
358  // Incremented by a loop invariant step for each loop iteration
359  return SE.isLoopInvariant(IndDesc.getStep(), this);
360 }
361 
363  InductionDescriptor IndDesc;
364  if (!getInductionDescriptor(SE, IndDesc))
365  return false;
366 
367  ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());
368  if (!Init || !Init->isZero())
369  return false;
370 
371  if (IndDesc.getInductionOpcode() != Instruction::Add)
372  return false;
373 
374  ConstantInt *Step = IndDesc.getConstIntStepValue();
375  if (!Step || !Step->isOne())
376  return false;
377 
378  return true;
379 }
380 
381 // Check that 'BB' doesn't have any uses outside of the 'L'
382 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
383  DominatorTree &DT) {
384  for (const Instruction &I : BB) {
385  // Tokens can't be used in PHI nodes and live-out tokens prevent loop
386  // optimizations, so for the purposes of considered LCSSA form, we
387  // can ignore them.
388  if (I.getType()->isTokenTy())
389  continue;
390 
391  for (const Use &U : I.uses()) {
392  const Instruction *UI = cast<Instruction>(U.getUser());
393  const BasicBlock *UserBB = UI->getParent();
394  if (const PHINode *P = dyn_cast<PHINode>(UI))
395  UserBB = P->getIncomingBlock(U);
396 
397  // Check the current block, as a fast-path, before checking whether
398  // the use is anywhere in the loop. Most values are used in the same
399  // block they are defined in. Also, blocks not reachable from the
400  // entry are special; uses in them don't need to go through PHIs.
401  if (UserBB != &BB && !L.contains(UserBB) &&
402  DT.isReachableFromEntry(UserBB))
403  return false;
404  }
405  }
406  return true;
407 }
408 
410  // For each block we check that it doesn't have any uses outside of this loop.
411  return all_of(this->blocks(), [&](const BasicBlock *BB) {
412  return isBlockInLCSSAForm(*this, *BB, DT);
413  });
414 }
415 
417  // For each block we check that it doesn't have any uses outside of its
418  // innermost loop. This process will transitively guarantee that the current
419  // loop and all of the nested loops are in LCSSA form.
420  return all_of(this->blocks(), [&](const BasicBlock *BB) {
421  return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
422  });
423 }
424 
426  // Normal-form loops have a preheader, a single backedge, and all of their
427  // exits have all their predecessors inside the loop.
429 }
430 
431 // Routines that reform the loop CFG and split edges often fail on indirectbr.
432 bool Loop::isSafeToClone() const {
433  // Return false if any loop blocks contain indirectbrs, or there are any calls
434  // to noduplicate functions.
435  // FIXME: it should be ok to clone CallBrInst's if we correctly update the
436  // operand list to reflect the newly cloned labels.
437  for (BasicBlock *BB : this->blocks()) {
438  if (isa<IndirectBrInst>(BB->getTerminator()) ||
439  isa<CallBrInst>(BB->getTerminator()))
440  return false;
441 
442  for (Instruction &I : *BB)
443  if (auto CS = CallSite(&I))
444  if (CS.cannotDuplicate())
445  return false;
446  }
447  return true;
448 }
449 
451  MDNode *LoopID = nullptr;
452 
453  // Go through the latch blocks and check the terminator for the metadata.
454  SmallVector<BasicBlock *, 4> LatchesBlocks;
455  getLoopLatches(LatchesBlocks);
456  for (BasicBlock *BB : LatchesBlocks) {
457  Instruction *TI = BB->getTerminator();
459 
460  if (!MD)
461  return nullptr;
462 
463  if (!LoopID)
464  LoopID = MD;
465  else if (MD != LoopID)
466  return nullptr;
467  }
468  if (!LoopID || LoopID->getNumOperands() == 0 ||
469  LoopID->getOperand(0) != LoopID)
470  return nullptr;
471  return LoopID;
472 }
473 
474 void Loop::setLoopID(MDNode *LoopID) const {
475  assert((!LoopID || LoopID->getNumOperands() > 0) &&
476  "Loop ID needs at least one operand");
477  assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
478  "Loop ID should refer to itself");
479 
480  SmallVector<BasicBlock *, 4> LoopLatches;
481  getLoopLatches(LoopLatches);
482  for (BasicBlock *BB : LoopLatches)
483  BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
484 }
485 
488 
489  MDNode *DisableUnrollMD =
490  MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
491  MDNode *LoopID = getLoopID();
493  Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
494  setLoopID(NewLoopID);
495 }
496 
498  MDNode *DesiredLoopIdMetadata = getLoopID();
499 
500  if (!DesiredLoopIdMetadata)
501  return false;
502 
503  MDNode *ParallelAccesses =
504  findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
506  ParallelAccessGroups; // For scalable 'contains' check.
507  if (ParallelAccesses) {
508  for (const MDOperand &MD : drop_begin(ParallelAccesses->operands(), 1)) {
509  MDNode *AccGroup = cast<MDNode>(MD.get());
510  assert(isValidAsAccessGroup(AccGroup) &&
511  "List item must be an access group");
512  ParallelAccessGroups.insert(AccGroup);
513  }
514  }
515 
516  // The loop branch contains the parallel loop metadata. In order to ensure
517  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
518  // dependencies (thus converted the loop back to a sequential loop), check
519  // that all the memory instructions in the loop belong to an access group that
520  // is parallel to this loop.
521  for (BasicBlock *BB : this->blocks()) {
522  for (Instruction &I : *BB) {
523  if (!I.mayReadOrWriteMemory())
524  continue;
525 
526  if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
527  auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
528  if (AG->getNumOperands() == 0) {
529  assert(isValidAsAccessGroup(AG) && "Item must be an access group");
530  return ParallelAccessGroups.count(AG);
531  }
532 
533  for (const MDOperand &AccessListItem : AG->operands()) {
534  MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
535  assert(isValidAsAccessGroup(AccGroup) &&
536  "List item must be an access group");
537  if (ParallelAccessGroups.count(AccGroup))
538  return true;
539  }
540  return false;
541  };
542 
543  if (ContainsAccessGroup(AccessGroup))
544  continue;
545  }
546 
547  // The memory instruction can refer to the loop identifier metadata
548  // directly or indirectly through another list metadata (in case of
549  // nested parallel loops). The loop identifier metadata refers to
550  // itself so we can check both cases with the same routine.
551  MDNode *LoopIdMD =
553 
554  if (!LoopIdMD)
555  return false;
556 
557  bool LoopIdMDFound = false;
558  for (const MDOperand &MDOp : LoopIdMD->operands()) {
559  if (MDOp == DesiredLoopIdMetadata) {
560  LoopIdMDFound = true;
561  break;
562  }
563  }
564 
565  if (!LoopIdMDFound)
566  return false;
567  }
568  }
569  return true;
570 }
571 
573 
575  // If we have a debug location in the loop ID, then use it.
576  if (MDNode *LoopID = getLoopID()) {
577  DebugLoc Start;
578  // We use the first DebugLoc in the header as the start location of the loop
579  // and if there is a second DebugLoc in the header we use it as end location
580  // of the loop.
581  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
582  if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
583  if (!Start)
584  Start = DebugLoc(L);
585  else
586  return LocRange(Start, DebugLoc(L));
587  }
588  }
589 
590  if (Start)
591  return LocRange(Start);
592  }
593 
594  // Try the pre-header first.
595  if (BasicBlock *PHeadBB = getLoopPreheader())
596  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
597  return LocRange(DL);
598 
599  // If we have no pre-header or there are no instructions with debug
600  // info in it, try the header.
601  if (BasicBlock *HeadBB = getHeader())
602  return LocRange(HeadBB->getTerminator()->getDebugLoc());
603 
604  return LocRange();
605 }
606 
607 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
608 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
609 
611  print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
612 }
613 #endif
614 
615 //===----------------------------------------------------------------------===//
616 // UnloopUpdater implementation
617 //
618 
619 namespace {
620 /// Find the new parent loop for all blocks within the "unloop" whose last
621 /// backedges has just been removed.
622 class UnloopUpdater {
623  Loop &Unloop;
624  LoopInfo *LI;
625 
627 
628  // Map unloop's immediate subloops to their nearest reachable parents. Nested
629  // loops within these subloops will not change parents. However, an immediate
630  // subloop's new parent will be the nearest loop reachable from either its own
631  // exits *or* any of its nested loop's exits.
632  DenseMap<Loop *, Loop *> SubloopParents;
633 
634  // Flag the presence of an irreducible backedge whose destination is a block
635  // directly contained by the original unloop.
636  bool FoundIB;
637 
638 public:
639  UnloopUpdater(Loop *UL, LoopInfo *LInfo)
640  : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
641 
642  void updateBlockParents();
643 
644  void removeBlocksFromAncestors();
645 
646  void updateSubloopParents();
647 
648 protected:
649  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
650 };
651 } // end anonymous namespace
652 
653 /// Update the parent loop for all blocks that are directly contained within the
654 /// original "unloop".
655 void UnloopUpdater::updateBlockParents() {
656  if (Unloop.getNumBlocks()) {
657  // Perform a post order CFG traversal of all blocks within this loop,
658  // propagating the nearest loop from successors to predecessors.
659  LoopBlocksTraversal Traversal(DFS, LI);
660  for (BasicBlock *POI : Traversal) {
661 
662  Loop *L = LI->getLoopFor(POI);
663  Loop *NL = getNearestLoop(POI, L);
664 
665  if (NL != L) {
666  // For reducible loops, NL is now an ancestor of Unloop.
667  assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
668  "uninitialized successor");
669  LI->changeLoopFor(POI, NL);
670  } else {
671  // Or the current block is part of a subloop, in which case its parent
672  // is unchanged.
673  assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
674  }
675  }
676  }
677  // Each irreducible loop within the unloop induces a round of iteration using
678  // the DFS result cached by Traversal.
679  bool Changed = FoundIB;
680  for (unsigned NIters = 0; Changed; ++NIters) {
681  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
682 
683  // Iterate over the postorder list of blocks, propagating the nearest loop
684  // from successors to predecessors as before.
685  Changed = false;
686  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
687  POE = DFS.endPostorder();
688  POI != POE; ++POI) {
689 
690  Loop *L = LI->getLoopFor(*POI);
691  Loop *NL = getNearestLoop(*POI, L);
692  if (NL != L) {
693  assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
694  "uninitialized successor");
695  LI->changeLoopFor(*POI, NL);
696  Changed = true;
697  }
698  }
699  }
700 }
701 
702 /// Remove unloop's blocks from all ancestors below their new parents.
703 void UnloopUpdater::removeBlocksFromAncestors() {
704  // Remove all unloop's blocks (including those in nested subloops) from
705  // ancestors below the new parent loop.
706  for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
707  BI != BE; ++BI) {
708  Loop *OuterParent = LI->getLoopFor(*BI);
709  if (Unloop.contains(OuterParent)) {
710  while (OuterParent->getParentLoop() != &Unloop)
711  OuterParent = OuterParent->getParentLoop();
712  OuterParent = SubloopParents[OuterParent];
713  }
714  // Remove blocks from former Ancestors except Unloop itself which will be
715  // deleted.
716  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
717  OldParent = OldParent->getParentLoop()) {
718  assert(OldParent && "new loop is not an ancestor of the original");
719  OldParent->removeBlockFromLoop(*BI);
720  }
721  }
722 }
723 
724 /// Update the parent loop for all subloops directly nested within unloop.
725 void UnloopUpdater::updateSubloopParents() {
726  while (!Unloop.empty()) {
727  Loop *Subloop = *std::prev(Unloop.end());
728  Unloop.removeChildLoop(std::prev(Unloop.end()));
729 
730  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
731  if (Loop *Parent = SubloopParents[Subloop])
732  Parent->addChildLoop(Subloop);
733  else
734  LI->addTopLevelLoop(Subloop);
735  }
736 }
737 
738 /// Return the nearest parent loop among this block's successors. If a successor
739 /// is a subloop header, consider its parent to be the nearest parent of the
740 /// subloop's exits.
741 ///
742 /// For subloop blocks, simply update SubloopParents and return NULL.
743 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
744 
745  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
746  // is considered uninitialized.
747  Loop *NearLoop = BBLoop;
748 
749  Loop *Subloop = nullptr;
750  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
751  Subloop = NearLoop;
752  // Find the subloop ancestor that is directly contained within Unloop.
753  while (Subloop->getParentLoop() != &Unloop) {
754  Subloop = Subloop->getParentLoop();
755  assert(Subloop && "subloop is not an ancestor of the original loop");
756  }
757  // Get the current nearest parent of the Subloop exits, initially Unloop.
758  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
759  }
760 
761  succ_iterator I = succ_begin(BB), E = succ_end(BB);
762  if (I == E) {
763  assert(!Subloop && "subloop blocks must have a successor");
764  NearLoop = nullptr; // unloop blocks may now exit the function.
765  }
766  for (; I != E; ++I) {
767  if (*I == BB)
768  continue; // self loops are uninteresting
769 
770  Loop *L = LI->getLoopFor(*I);
771  if (L == &Unloop) {
772  // This successor has not been processed. This path must lead to an
773  // irreducible backedge.
774  assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
775  FoundIB = true;
776  }
777  if (L != &Unloop && Unloop.contains(L)) {
778  // Successor is in a subloop.
779  if (Subloop)
780  continue; // Branching within subloops. Ignore it.
781 
782  // BB branches from the original into a subloop header.
783  assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
784 
785  // Get the current nearest parent of the Subloop's exits.
786  L = SubloopParents[L];
787  // L could be Unloop if the only exit was an irreducible backedge.
788  }
789  if (L == &Unloop) {
790  continue;
791  }
792  // Handle critical edges from Unloop into a sibling loop.
793  if (L && !L->contains(&Unloop)) {
794  L = L->getParentLoop();
795  }
796  // Remember the nearest parent loop among successors or subloop exits.
797  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
798  NearLoop = L;
799  }
800  if (Subloop) {
801  SubloopParents[Subloop] = NearLoop;
802  return BBLoop;
803  }
804  return NearLoop;
805 }
806 
807 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
808 
811  // Check whether the analysis, all analyses on functions, or the function's
812  // CFG have been preserved.
813  auto PAC = PA.getChecker<LoopAnalysis>();
814  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
815  PAC.preservedSet<CFGAnalyses>());
816 }
817 
818 void LoopInfo::erase(Loop *Unloop) {
819  assert(!Unloop->isInvalid() && "Loop has already been erased!");
820 
821  auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
822 
823  // First handle the special case of no parent loop to simplify the algorithm.
824  if (!Unloop->getParentLoop()) {
825  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
826  for (Loop::block_iterator I = Unloop->block_begin(),
827  E = Unloop->block_end();
828  I != E; ++I) {
829 
830  // Don't reparent blocks in subloops.
831  if (getLoopFor(*I) != Unloop)
832  continue;
833 
834  // Blocks no longer have a parent but are still referenced by Unloop until
835  // the Unloop object is deleted.
836  changeLoopFor(*I, nullptr);
837  }
838 
839  // Remove the loop from the top-level LoopInfo object.
840  for (iterator I = begin();; ++I) {
841  assert(I != end() && "Couldn't find loop");
842  if (*I == Unloop) {
843  removeLoop(I);
844  break;
845  }
846  }
847 
848  // Move all of the subloops to the top-level.
849  while (!Unloop->empty())
850  addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
851 
852  return;
853  }
854 
855  // Update the parent loop for all blocks within the loop. Blocks within
856  // subloops will not change parents.
857  UnloopUpdater Updater(Unloop, this);
858  Updater.updateBlockParents();
859 
860  // Remove blocks from former ancestor loops.
861  Updater.removeBlocksFromAncestors();
862 
863  // Add direct subloops as children in their new parent loop.
864  Updater.updateSubloopParents();
865 
866  // Remove unloop from its parent loop.
867  Loop *ParentLoop = Unloop->getParentLoop();
868  for (Loop::iterator I = ParentLoop->begin();; ++I) {
869  assert(I != ParentLoop->end() && "Couldn't find loop");
870  if (*I == Unloop) {
871  ParentLoop->removeChildLoop(I);
872  break;
873  }
874  }
875 }
876 
877 AnalysisKey LoopAnalysis::Key;
878 
880  // FIXME: Currently we create a LoopInfo from scratch for every function.
881  // This may prove to be too wasteful due to deallocating and re-allocating
882  // memory each time for the underlying map and vector datastructures. At some
883  // point it may prove worthwhile to use a freelist and recycle LoopInfo
884  // objects. I don't want to add that kind of complexity until the scope of
885  // the problem is better understood.
886  LoopInfo LI;
888  return LI;
889 }
890 
893  AM.getResult<LoopAnalysis>(F).print(OS);
894  return PreservedAnalyses::all();
895 }
896 
897 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
898 
899  if (forcePrintModuleIR()) {
900  // handling -print-module-scope
901  OS << Banner << " (loop: ";
902  L.getHeader()->printAsOperand(OS, false);
903  OS << ")\n";
904 
905  // printing whole module
906  OS << *L.getHeader()->getModule();
907  return;
908  }
909 
910  OS << Banner;
911 
912  auto *PreHeader = L.getLoopPreheader();
913  if (PreHeader) {
914  OS << "\n; Preheader:";
915  PreHeader->print(OS);
916  OS << "\n; Loop:";
917  }
918 
919  for (auto *Block : L.blocks())
920  if (Block)
921  Block->print(OS);
922  else
923  OS << "Printing <null> block";
924 
925  SmallVector<BasicBlock *, 8> ExitBlocks;
926  L.getExitBlocks(ExitBlocks);
927  if (!ExitBlocks.empty()) {
928  OS << "\n; Exit blocks";
929  for (auto *Block : ExitBlocks)
930  if (Block)
931  Block->print(OS);
932  else
933  OS << "Printing <null> block";
934  }
935 }
936 
938  // No loop metadata node, no loop properties.
939  if (!LoopID)
940  return nullptr;
941 
942  // First operand should refer to the metadata node itself, for legacy reasons.
943  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
944  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
945 
946  // Iterate over the metdata node operands and look for MDString metadata.
947  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
948  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
949  if (!MD || MD->getNumOperands() < 1)
950  continue;
951  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
952  if (!S)
953  continue;
954  // Return the operand node if MDString holds expected metadata.
955  if (Name.equals(S->getString()))
956  return MD;
957  }
958 
959  // Loop property not found.
960  return nullptr;
961 }
962 
964  return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
965 }
966 
968  return Node->getNumOperands() == 0 && Node->isDistinct();
969 }
970 
972  MDNode *OrigLoopID,
973  ArrayRef<StringRef> RemovePrefixes,
974  ArrayRef<MDNode *> AddAttrs) {
975  // First remove any existing loop metadata related to this transformation.
977 
978  // Reserve first location for self reference to the LoopID metadata node.
979  TempMDTuple TempNode = MDNode::getTemporary(Context, None);
980  MDs.push_back(TempNode.get());
981 
982  // Remove metadata for the transformation that has been applied or that became
983  // outdated.
984  if (OrigLoopID) {
985  for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
986  bool IsVectorMetadata = false;
987  Metadata *Op = OrigLoopID->getOperand(i);
988  if (MDNode *MD = dyn_cast<MDNode>(Op)) {
989  const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
990  if (S)
991  IsVectorMetadata =
992  llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
993  return S->getString().startswith(Prefix);
994  });
995  }
996  if (!IsVectorMetadata)
997  MDs.push_back(Op);
998  }
999  }
1000 
1001  // Add metadata to avoid reapplying a transformation, such as
1002  // llvm.loop.unroll.disable and llvm.loop.isvectorized.
1003  MDs.append(AddAttrs.begin(), AddAttrs.end());
1004 
1005  MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
1006  // Replace the temporary node with a self-reference.
1007  NewLoopID->replaceOperandWith(0, NewLoopID);
1008  return NewLoopID;
1009 }
1010 
1011 //===----------------------------------------------------------------------===//
1012 // LoopInfo implementation
1013 //
1014 
1015 char LoopInfoWrapperPass::ID = 0;
1016 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1017  true, true)
1020  true, true)
1021 
1022 bool LoopInfoWrapperPass::runOnFunction(Function &) {
1023  releaseMemory();
1024  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
1025  return false;
1026 }
1027 
1029  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
1030  // function each time verifyAnalysis is called is very expensive. The
1031  // -verify-loop-info option can enable this. In order to perform some
1032  // checking by default, LoopPass has been taught to call verifyLoop manually
1033  // during loop pass sequences.
1034  if (VerifyLoopInfo) {
1035  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1036  LI.verify(DT);
1037  }
1038 }
1039 
1041  AU.setPreservesAll();
1043 }
1044 
1046  LI.print(OS);
1047 }
1048 
1051  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1052  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1053  LI.verify(DT);
1054  return PreservedAnalyses::all();
1055 }
1056 
1057 //===----------------------------------------------------------------------===//
1058 // LoopBlocksDFS implementation
1059 //
1060 
1061 /// Traverse the loop blocks and store the DFS result.
1062 /// Useful for clients that just want the final DFS result and don't need to
1063 /// visit blocks during the initial traversal.
1065  LoopBlocksTraversal Traversal(*this, LI);
1066  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
1067  POE = Traversal.end();
1068  POI != POE; ++POI)
1069  ;
1070 }
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:710
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:879
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:722
bool forcePrintModuleIR()
forcePrintModuleIR - returns true if IR printing passes should
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
BinaryOperator * getInductionBinOp() const
bool isDistinct() const
Definition: Metadata.h:942
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:211
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:891
LLVMContext & Context
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
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.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1195
iterator begin() const
Definition: ArrayRef.h:136
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:858
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:453
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:85
bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:416
ConstantInt * getConstIntStepValue() const
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:409
LLVM_NODISCARD bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:256
Instruction::BinaryOps getInductionOpcode() const
Returns binary opcode of the induction operator.
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:971
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:381
The main scalar evolution driver.
This file contains the declarations for metadata subclasses.
BasicBlock * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:160
Direction getDirection() const
Get the direction of the loop.
Definition: LoopInfo.cpp:270
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:58
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
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:1192
BasicBlock * getSuccessor(unsigned i) const
A debug info location.
Definition: DebugLoc.h:33
Metadata node.
Definition: Metadata.h:863
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
Value * getStartValue() const
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:299
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:67
bool isInvalid() const
Return true if this loop is no longer valid.
Definition: LoopInfo.h:195
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:683
void print(raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:379
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:311
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:133
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Traverse the blocks in a loop using a depth-first search.
Definition: LoopIterator.h:200
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
static cl::opt< bool, true > VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), cl::Hidden, cl::desc("Verify loop info (time consuming)"))
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:897
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
PHINode * getInductionVariable(ScalarEvolution &SE) const
Return the loop induction variable if found, else return nullptr.
Definition: LoopInfo.cpp:290
bool isAuxiliaryInductionVariable(PHINode &AuxIndVar, ScalarEvolution &SE) const
Return true if the given PHINode AuxIndVar is.
Definition: LoopInfo.cpp:336
POTIterator begin()
Postorder traversal over the graph.
Definition: LoopIterator.h:216
std::vector< Loop *>::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:869
void getLoopLatches(SmallVectorImpl< BasicBlock * > &LoopLatches) const
Return all loop latch blocks of this loop.
Definition: LoopInfo.h:311
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:818
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:671
static TempMDTuple getTemporary(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1177
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1152
void print(raw_ostream &O, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: LoopInfo.cpp:1045
BasicBlock * getHeader() const
Definition: LoopInfo.h:102
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:102
void getExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
std::vector< Loop *>::const_iterator iterator
Definition: LoopInfo.h:141
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:200
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LoopInfo.cpp:1040
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref&#39;ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:720
This node represents a polynomial recurrence on the trip count of the specified loop.
op_range operands() const
Definition: Metadata.h:1066
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:474
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
Definition: LoopInfo.cpp:963
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:234
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
ICmpInst::Predicate getCanonicalPredicate() const
Return the canonical predicate for the latch compare instruction, if able to be calcuated.
Definition: LoopInfo.cpp:228
Debug location.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1064
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
Natural Loop true
Definition: LoopInfo.cpp:1019
StringRef getString() const
Definition: Metadata.cpp:463
Core dominator tree base class.
Definition: LoopInfo.h:63
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1165
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
Optional< LoopBounds > getBounds(ScalarEvolution &SE) const
Return the struct LoopBounds collected if all struct members are found, else None.
Definition: LoopInfo.cpp:283
INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information", true, true) INITIALIZE_PASS_END(LoopInfoWrapperPass
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
void dump() const
Definition: LoopInfo.cpp:608
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
Conditional or Unconditional Branch instruction.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static MDTuple * getDistinct(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1173
const SCEV * getStep() const
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define H(x, y, z)
Definition: MD5.cpp:57
void setLoopAlreadyUnrolled()
Add llvm.loop.unroll.disable to this loop&#39;s loop id metadata.
Definition: LoopInfo.cpp:486
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:370
void dumpVerbose() const
Definition: LoopInfo.cpp:610
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:540
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:112
Represent the analysis usage information of a pass.
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:1199
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
op_range operands()
Definition: User.h:237
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:572
iterator_range< decltype(adl_begin(std::declval< T >)))> drop_begin(T &&t, int n)
A range representing the start and end location of a loop.
Definition: LoopInfo.h:509
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:4351
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:61
signed greater than
Definition: InstrTypes.h:759
unsigned first
bool contains(const Loop *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:112
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
A struct for saving information about induction variables.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
iterator end() const
Definition: ArrayRef.h:137
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Definition: LoopInfo.cpp:937
signed less than
Definition: InstrTypes.h:761
static Optional< Loop::LoopBounds > getBounds(const Loop &L, PHINode &IndVar, ScalarEvolution &SE)
Return the LoopBounds object if.
Definition: LoopInfo.cpp:197
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
bool isConditional() const
Natural Loop Information
Definition: LoopInfo.cpp:1019
bool VerifyLoopInfo
Enables verification of loop info.
Definition: LoopInfo.cpp:51
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Definition: InstrTypes.h:862
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
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
Store the result of a depth first search within basic blocks contained by a single loop...
Definition: LoopIterator.h:97
LocRange getLocRange() const
Return the source code span of the loop.
Definition: LoopInfo.cpp:574
void setPreservesAll()
Set by analyses that do not transform their input at all.
iterator_range< user_iterator > users()
Definition: Value.h:399
static void DFS(BasicBlock *Root, SetVector< BasicBlock *> &Set)
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
bool getIncomingAndBackEdge(BasicBlock *&Incoming, BasicBlock *&Backedge) const
Obtain the unique incoming and back edge.
Definition: LoopInfo.cpp:120
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:387
LLVM_NODISCARD bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:160
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: LoopInfo.cpp:809
LoopT * getParentLoop() const
Definition: LoopInfo.h:103
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:425
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:450
const DebugLoc & getStart() const
Definition: LoopInfo.h:519
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:506
#define I(x, y, z)
Definition: MD5.cpp:58
Below are some utilities to get loop bounds and induction variable, and check if a given phinode is a...
Definition: LoopInfo.h:608
bool mayReadFromMemory() const
Return true if this instruction may read memory.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:192
std::vector< BasicBlock * >::const_iterator POIterator
Postorder list iterators.
Definition: LoopIterator.h:100
static ICmpInst * getLatchCmpInst(const Loop &L)
Get the latch condition instruction.
Definition: LoopInfo.cpp:170
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
block_iterator block_end() const
Definition: LoopInfo.h:157
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:324
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:432
AnalysisUsage & addRequiredTransitive()
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:648
This file defines passes to print out IR in various granularities.
bool empty() const
Definition: LoopInfo.h:148
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
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:362
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
Definition: LoopInfo.cpp:497
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
LLVM Value Representation.
Definition: Value.h:72
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:1049
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:86
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:583
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1177
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:847
A single uniqued string.
Definition: Metadata.h:603
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
This header defines various interfaces for pass management in LLVM.
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
bool getInductionDescriptor(ScalarEvolution &SE, InductionDescriptor &IndDesc) const
Get the loop induction descriptor for the loop induction variable.
Definition: LoopInfo.cpp:328
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:158
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")
Function to print a loop&#39;s contents as LLVM&#39;s text IR assembly.
Definition: LoopInfo.cpp:897
block_iterator block_begin() const
Definition: LoopInfo.h:156
Root of the metadata hierarchy.
Definition: Metadata.h:57
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:448
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
Definition: LoopInfo.cpp:967
loops
Definition: LoopInfo.cpp:1019
const BasicBlock * getParent() const
Definition: Instruction.h:66
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, DominatorTree &DT)
Definition: LoopInfo.cpp:382
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: LoopInfo.cpp:1028
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:71