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  assert(isLoopSimplifyForm() && "Only valid for loop in simplify form");
364  BasicBlock *Preheader = getLoopPreheader();
365  BasicBlock *Latch = getLoopLatch();
366  assert(Preheader && Latch &&
367  "Expecting a loop with valid preheader and latch");
368  assert(isLoopExiting(Latch) && "Only valid for rotated loop");
369 
370  Instruction *LatchTI = Latch->getTerminator();
371  if (!LatchTI || LatchTI->getNumSuccessors() != 2)
372  return nullptr;
373 
374  BasicBlock *ExitFromLatch = (LatchTI->getSuccessor(0) == getHeader())
375  ? LatchTI->getSuccessor(1)
376  : LatchTI->getSuccessor(0);
377  BasicBlock *ExitFromLatchSucc = ExitFromLatch->getUniqueSuccessor();
378  if (!ExitFromLatchSucc)
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  return (GuardOtherSucc == ExitFromLatchSucc) ? GuardBI : nullptr;
395 }
396 
398  InductionDescriptor IndDesc;
399  if (!getInductionDescriptor(SE, IndDesc))
400  return false;
401 
402  ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());
403  if (!Init || !Init->isZero())
404  return false;
405 
406  if (IndDesc.getInductionOpcode() != Instruction::Add)
407  return false;
408 
409  ConstantInt *Step = IndDesc.getConstIntStepValue();
410  if (!Step || !Step->isOne())
411  return false;
412 
413  return true;
414 }
415 
416 // Check that 'BB' doesn't have any uses outside of the 'L'
417 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
418  DominatorTree &DT) {
419  for (const Instruction &I : BB) {
420  // Tokens can't be used in PHI nodes and live-out tokens prevent loop
421  // optimizations, so for the purposes of considered LCSSA form, we
422  // can ignore them.
423  if (I.getType()->isTokenTy())
424  continue;
425 
426  for (const Use &U : I.uses()) {
427  const Instruction *UI = cast<Instruction>(U.getUser());
428  const BasicBlock *UserBB = UI->getParent();
429  if (const PHINode *P = dyn_cast<PHINode>(UI))
430  UserBB = P->getIncomingBlock(U);
431 
432  // Check the current block, as a fast-path, before checking whether
433  // the use is anywhere in the loop. Most values are used in the same
434  // block they are defined in. Also, blocks not reachable from the
435  // entry are special; uses in them don't need to go through PHIs.
436  if (UserBB != &BB && !L.contains(UserBB) &&
437  DT.isReachableFromEntry(UserBB))
438  return false;
439  }
440  }
441  return true;
442 }
443 
445  // For each block we check that it doesn't have any uses outside of this loop.
446  return all_of(this->blocks(), [&](const BasicBlock *BB) {
447  return isBlockInLCSSAForm(*this, *BB, DT);
448  });
449 }
450 
452  // For each block we check that it doesn't have any uses outside of its
453  // innermost loop. This process will transitively guarantee that the current
454  // loop and all of the nested loops are in LCSSA form.
455  return all_of(this->blocks(), [&](const BasicBlock *BB) {
456  return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
457  });
458 }
459 
461  // Normal-form loops have a preheader, a single backedge, and all of their
462  // exits have all their predecessors inside the loop.
464 }
465 
466 // Routines that reform the loop CFG and split edges often fail on indirectbr.
467 bool Loop::isSafeToClone() const {
468  // Return false if any loop blocks contain indirectbrs, or there are any calls
469  // to noduplicate functions.
470  // FIXME: it should be ok to clone CallBrInst's if we correctly update the
471  // operand list to reflect the newly cloned labels.
472  for (BasicBlock *BB : this->blocks()) {
473  if (isa<IndirectBrInst>(BB->getTerminator()) ||
474  isa<CallBrInst>(BB->getTerminator()))
475  return false;
476 
477  for (Instruction &I : *BB)
478  if (auto CS = CallSite(&I))
479  if (CS.cannotDuplicate())
480  return false;
481  }
482  return true;
483 }
484 
486  MDNode *LoopID = nullptr;
487 
488  // Go through the latch blocks and check the terminator for the metadata.
489  SmallVector<BasicBlock *, 4> LatchesBlocks;
490  getLoopLatches(LatchesBlocks);
491  for (BasicBlock *BB : LatchesBlocks) {
492  Instruction *TI = BB->getTerminator();
493  MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
494 
495  if (!MD)
496  return nullptr;
497 
498  if (!LoopID)
499  LoopID = MD;
500  else if (MD != LoopID)
501  return nullptr;
502  }
503  if (!LoopID || LoopID->getNumOperands() == 0 ||
504  LoopID->getOperand(0) != LoopID)
505  return nullptr;
506  return LoopID;
507 }
508 
509 void Loop::setLoopID(MDNode *LoopID) const {
510  assert((!LoopID || LoopID->getNumOperands() > 0) &&
511  "Loop ID needs at least one operand");
512  assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
513  "Loop ID should refer to itself");
514 
515  SmallVector<BasicBlock *, 4> LoopLatches;
516  getLoopLatches(LoopLatches);
517  for (BasicBlock *BB : LoopLatches)
518  BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
519 }
520 
523 
524  MDNode *DisableUnrollMD =
525  MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
526  MDNode *LoopID = getLoopID();
528  Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
529  setLoopID(NewLoopID);
530 }
531 
533  MDNode *DesiredLoopIdMetadata = getLoopID();
534 
535  if (!DesiredLoopIdMetadata)
536  return false;
537 
538  MDNode *ParallelAccesses =
539  findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
541  ParallelAccessGroups; // For scalable 'contains' check.
542  if (ParallelAccesses) {
543  for (const MDOperand &MD : drop_begin(ParallelAccesses->operands(), 1)) {
544  MDNode *AccGroup = cast<MDNode>(MD.get());
545  assert(isValidAsAccessGroup(AccGroup) &&
546  "List item must be an access group");
547  ParallelAccessGroups.insert(AccGroup);
548  }
549  }
550 
551  // The loop branch contains the parallel loop metadata. In order to ensure
552  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
553  // dependencies (thus converted the loop back to a sequential loop), check
554  // that all the memory instructions in the loop belong to an access group that
555  // is parallel to this loop.
556  for (BasicBlock *BB : this->blocks()) {
557  for (Instruction &I : *BB) {
558  if (!I.mayReadOrWriteMemory())
559  continue;
560 
561  if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
562  auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
563  if (AG->getNumOperands() == 0) {
564  assert(isValidAsAccessGroup(AG) && "Item must be an access group");
565  return ParallelAccessGroups.count(AG);
566  }
567 
568  for (const MDOperand &AccessListItem : AG->operands()) {
569  MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
570  assert(isValidAsAccessGroup(AccGroup) &&
571  "List item must be an access group");
572  if (ParallelAccessGroups.count(AccGroup))
573  return true;
574  }
575  return false;
576  };
577 
578  if (ContainsAccessGroup(AccessGroup))
579  continue;
580  }
581 
582  // The memory instruction can refer to the loop identifier metadata
583  // directly or indirectly through another list metadata (in case of
584  // nested parallel loops). The loop identifier metadata refers to
585  // itself so we can check both cases with the same routine.
586  MDNode *LoopIdMD =
587  I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
588 
589  if (!LoopIdMD)
590  return false;
591 
592  bool LoopIdMDFound = false;
593  for (const MDOperand &MDOp : LoopIdMD->operands()) {
594  if (MDOp == DesiredLoopIdMetadata) {
595  LoopIdMDFound = true;
596  break;
597  }
598  }
599 
600  if (!LoopIdMDFound)
601  return false;
602  }
603  }
604  return true;
605 }
606 
608 
610  // If we have a debug location in the loop ID, then use it.
611  if (MDNode *LoopID = getLoopID()) {
612  DebugLoc Start;
613  // We use the first DebugLoc in the header as the start location of the loop
614  // and if there is a second DebugLoc in the header we use it as end location
615  // of the loop.
616  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
617  if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
618  if (!Start)
619  Start = DebugLoc(L);
620  else
621  return LocRange(Start, DebugLoc(L));
622  }
623  }
624 
625  if (Start)
626  return LocRange(Start);
627  }
628 
629  // Try the pre-header first.
630  if (BasicBlock *PHeadBB = getLoopPreheader())
631  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
632  return LocRange(DL);
633 
634  // If we have no pre-header or there are no instructions with debug
635  // info in it, try the header.
636  if (BasicBlock *HeadBB = getHeader())
637  return LocRange(HeadBB->getTerminator()->getDebugLoc());
638 
639  return LocRange();
640 }
641 
642 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
643 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
644 
646  print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
647 }
648 #endif
649 
650 //===----------------------------------------------------------------------===//
651 // UnloopUpdater implementation
652 //
653 
654 namespace {
655 /// Find the new parent loop for all blocks within the "unloop" whose last
656 /// backedges has just been removed.
657 class UnloopUpdater {
658  Loop &Unloop;
659  LoopInfo *LI;
660 
662 
663  // Map unloop's immediate subloops to their nearest reachable parents. Nested
664  // loops within these subloops will not change parents. However, an immediate
665  // subloop's new parent will be the nearest loop reachable from either its own
666  // exits *or* any of its nested loop's exits.
667  DenseMap<Loop *, Loop *> SubloopParents;
668 
669  // Flag the presence of an irreducible backedge whose destination is a block
670  // directly contained by the original unloop.
671  bool FoundIB;
672 
673 public:
674  UnloopUpdater(Loop *UL, LoopInfo *LInfo)
675  : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
676 
677  void updateBlockParents();
678 
679  void removeBlocksFromAncestors();
680 
681  void updateSubloopParents();
682 
683 protected:
684  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
685 };
686 } // end anonymous namespace
687 
688 /// Update the parent loop for all blocks that are directly contained within the
689 /// original "unloop".
690 void UnloopUpdater::updateBlockParents() {
691  if (Unloop.getNumBlocks()) {
692  // Perform a post order CFG traversal of all blocks within this loop,
693  // propagating the nearest loop from successors to predecessors.
694  LoopBlocksTraversal Traversal(DFS, LI);
695  for (BasicBlock *POI : Traversal) {
696 
697  Loop *L = LI->getLoopFor(POI);
698  Loop *NL = getNearestLoop(POI, L);
699 
700  if (NL != L) {
701  // For reducible loops, NL is now an ancestor of Unloop.
702  assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
703  "uninitialized successor");
704  LI->changeLoopFor(POI, NL);
705  } else {
706  // Or the current block is part of a subloop, in which case its parent
707  // is unchanged.
708  assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
709  }
710  }
711  }
712  // Each irreducible loop within the unloop induces a round of iteration using
713  // the DFS result cached by Traversal.
714  bool Changed = FoundIB;
715  for (unsigned NIters = 0; Changed; ++NIters) {
716  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
717 
718  // Iterate over the postorder list of blocks, propagating the nearest loop
719  // from successors to predecessors as before.
720  Changed = false;
721  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
722  POE = DFS.endPostorder();
723  POI != POE; ++POI) {
724 
725  Loop *L = LI->getLoopFor(*POI);
726  Loop *NL = getNearestLoop(*POI, L);
727  if (NL != L) {
728  assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
729  "uninitialized successor");
730  LI->changeLoopFor(*POI, NL);
731  Changed = true;
732  }
733  }
734  }
735 }
736 
737 /// Remove unloop's blocks from all ancestors below their new parents.
738 void UnloopUpdater::removeBlocksFromAncestors() {
739  // Remove all unloop's blocks (including those in nested subloops) from
740  // ancestors below the new parent loop.
741  for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
742  BI != BE; ++BI) {
743  Loop *OuterParent = LI->getLoopFor(*BI);
744  if (Unloop.contains(OuterParent)) {
745  while (OuterParent->getParentLoop() != &Unloop)
746  OuterParent = OuterParent->getParentLoop();
747  OuterParent = SubloopParents[OuterParent];
748  }
749  // Remove blocks from former Ancestors except Unloop itself which will be
750  // deleted.
751  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
752  OldParent = OldParent->getParentLoop()) {
753  assert(OldParent && "new loop is not an ancestor of the original");
754  OldParent->removeBlockFromLoop(*BI);
755  }
756  }
757 }
758 
759 /// Update the parent loop for all subloops directly nested within unloop.
760 void UnloopUpdater::updateSubloopParents() {
761  while (!Unloop.empty()) {
762  Loop *Subloop = *std::prev(Unloop.end());
763  Unloop.removeChildLoop(std::prev(Unloop.end()));
764 
765  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
766  if (Loop *Parent = SubloopParents[Subloop])
767  Parent->addChildLoop(Subloop);
768  else
769  LI->addTopLevelLoop(Subloop);
770  }
771 }
772 
773 /// Return the nearest parent loop among this block's successors. If a successor
774 /// is a subloop header, consider its parent to be the nearest parent of the
775 /// subloop's exits.
776 ///
777 /// For subloop blocks, simply update SubloopParents and return NULL.
778 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
779 
780  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
781  // is considered uninitialized.
782  Loop *NearLoop = BBLoop;
783 
784  Loop *Subloop = nullptr;
785  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
786  Subloop = NearLoop;
787  // Find the subloop ancestor that is directly contained within Unloop.
788  while (Subloop->getParentLoop() != &Unloop) {
789  Subloop = Subloop->getParentLoop();
790  assert(Subloop && "subloop is not an ancestor of the original loop");
791  }
792  // Get the current nearest parent of the Subloop exits, initially Unloop.
793  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
794  }
795 
796  succ_iterator I = succ_begin(BB), E = succ_end(BB);
797  if (I == E) {
798  assert(!Subloop && "subloop blocks must have a successor");
799  NearLoop = nullptr; // unloop blocks may now exit the function.
800  }
801  for (; I != E; ++I) {
802  if (*I == BB)
803  continue; // self loops are uninteresting
804 
805  Loop *L = LI->getLoopFor(*I);
806  if (L == &Unloop) {
807  // This successor has not been processed. This path must lead to an
808  // irreducible backedge.
809  assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
810  FoundIB = true;
811  }
812  if (L != &Unloop && Unloop.contains(L)) {
813  // Successor is in a subloop.
814  if (Subloop)
815  continue; // Branching within subloops. Ignore it.
816 
817  // BB branches from the original into a subloop header.
818  assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
819 
820  // Get the current nearest parent of the Subloop's exits.
821  L = SubloopParents[L];
822  // L could be Unloop if the only exit was an irreducible backedge.
823  }
824  if (L == &Unloop) {
825  continue;
826  }
827  // Handle critical edges from Unloop into a sibling loop.
828  if (L && !L->contains(&Unloop)) {
829  L = L->getParentLoop();
830  }
831  // Remember the nearest parent loop among successors or subloop exits.
832  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
833  NearLoop = L;
834  }
835  if (Subloop) {
836  SubloopParents[Subloop] = NearLoop;
837  return BBLoop;
838  }
839  return NearLoop;
840 }
841 
842 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
843 
846  // Check whether the analysis, all analyses on functions, or the function's
847  // CFG have been preserved.
848  auto PAC = PA.getChecker<LoopAnalysis>();
849  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
850  PAC.preservedSet<CFGAnalyses>());
851 }
852 
853 void LoopInfo::erase(Loop *Unloop) {
854  assert(!Unloop->isInvalid() && "Loop has already been erased!");
855 
856  auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
857 
858  // First handle the special case of no parent loop to simplify the algorithm.
859  if (!Unloop->getParentLoop()) {
860  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
861  for (Loop::block_iterator I = Unloop->block_begin(),
862  E = Unloop->block_end();
863  I != E; ++I) {
864 
865  // Don't reparent blocks in subloops.
866  if (getLoopFor(*I) != Unloop)
867  continue;
868 
869  // Blocks no longer have a parent but are still referenced by Unloop until
870  // the Unloop object is deleted.
871  changeLoopFor(*I, nullptr);
872  }
873 
874  // Remove the loop from the top-level LoopInfo object.
875  for (iterator I = begin();; ++I) {
876  assert(I != end() && "Couldn't find loop");
877  if (*I == Unloop) {
878  removeLoop(I);
879  break;
880  }
881  }
882 
883  // Move all of the subloops to the top-level.
884  while (!Unloop->empty())
885  addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
886 
887  return;
888  }
889 
890  // Update the parent loop for all blocks within the loop. Blocks within
891  // subloops will not change parents.
892  UnloopUpdater Updater(Unloop, this);
893  Updater.updateBlockParents();
894 
895  // Remove blocks from former ancestor loops.
896  Updater.removeBlocksFromAncestors();
897 
898  // Add direct subloops as children in their new parent loop.
899  Updater.updateSubloopParents();
900 
901  // Remove unloop from its parent loop.
902  Loop *ParentLoop = Unloop->getParentLoop();
903  for (Loop::iterator I = ParentLoop->begin();; ++I) {
904  assert(I != ParentLoop->end() && "Couldn't find loop");
905  if (*I == Unloop) {
906  ParentLoop->removeChildLoop(I);
907  break;
908  }
909  }
910 }
911 
912 AnalysisKey LoopAnalysis::Key;
913 
915  // FIXME: Currently we create a LoopInfo from scratch for every function.
916  // This may prove to be too wasteful due to deallocating and re-allocating
917  // memory each time for the underlying map and vector datastructures. At some
918  // point it may prove worthwhile to use a freelist and recycle LoopInfo
919  // objects. I don't want to add that kind of complexity until the scope of
920  // the problem is better understood.
921  LoopInfo LI;
923  return LI;
924 }
925 
928  AM.getResult<LoopAnalysis>(F).print(OS);
929  return PreservedAnalyses::all();
930 }
931 
932 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
933 
934  if (forcePrintModuleIR()) {
935  // handling -print-module-scope
936  OS << Banner << " (loop: ";
937  L.getHeader()->printAsOperand(OS, false);
938  OS << ")\n";
939 
940  // printing whole module
941  OS << *L.getHeader()->getModule();
942  return;
943  }
944 
945  OS << Banner;
946 
947  auto *PreHeader = L.getLoopPreheader();
948  if (PreHeader) {
949  OS << "\n; Preheader:";
950  PreHeader->print(OS);
951  OS << "\n; Loop:";
952  }
953 
954  for (auto *Block : L.blocks())
955  if (Block)
956  Block->print(OS);
957  else
958  OS << "Printing <null> block";
959 
960  SmallVector<BasicBlock *, 8> ExitBlocks;
961  L.getExitBlocks(ExitBlocks);
962  if (!ExitBlocks.empty()) {
963  OS << "\n; Exit blocks";
964  for (auto *Block : ExitBlocks)
965  if (Block)
966  Block->print(OS);
967  else
968  OS << "Printing <null> block";
969  }
970 }
971 
973  // No loop metadata node, no loop properties.
974  if (!LoopID)
975  return nullptr;
976 
977  // First operand should refer to the metadata node itself, for legacy reasons.
978  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
979  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
980 
981  // Iterate over the metdata node operands and look for MDString metadata.
982  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
983  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
984  if (!MD || MD->getNumOperands() < 1)
985  continue;
986  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
987  if (!S)
988  continue;
989  // Return the operand node if MDString holds expected metadata.
990  if (Name.equals(S->getString()))
991  return MD;
992  }
993 
994  // Loop property not found.
995  return nullptr;
996 }
997 
999  return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
1000 }
1001 
1003  return Node->getNumOperands() == 0 && Node->isDistinct();
1004 }
1005 
1007  MDNode *OrigLoopID,
1008  ArrayRef<StringRef> RemovePrefixes,
1009  ArrayRef<MDNode *> AddAttrs) {
1010  // First remove any existing loop metadata related to this transformation.
1012 
1013  // Reserve first location for self reference to the LoopID metadata node.
1014  TempMDTuple TempNode = MDNode::getTemporary(Context, None);
1015  MDs.push_back(TempNode.get());
1016 
1017  // Remove metadata for the transformation that has been applied or that became
1018  // outdated.
1019  if (OrigLoopID) {
1020  for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
1021  bool IsVectorMetadata = false;
1022  Metadata *Op = OrigLoopID->getOperand(i);
1023  if (MDNode *MD = dyn_cast<MDNode>(Op)) {
1024  const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1025  if (S)
1026  IsVectorMetadata =
1027  llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
1028  return S->getString().startswith(Prefix);
1029  });
1030  }
1031  if (!IsVectorMetadata)
1032  MDs.push_back(Op);
1033  }
1034  }
1035 
1036  // Add metadata to avoid reapplying a transformation, such as
1037  // llvm.loop.unroll.disable and llvm.loop.isvectorized.
1038  MDs.append(AddAttrs.begin(), AddAttrs.end());
1039 
1040  MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
1041  // Replace the temporary node with a self-reference.
1042  NewLoopID->replaceOperandWith(0, NewLoopID);
1043  return NewLoopID;
1044 }
1045 
1046 //===----------------------------------------------------------------------===//
1047 // LoopInfo implementation
1048 //
1049 
1050 char LoopInfoWrapperPass::ID = 0;
1051 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1052  true, true)
1055  true, true)
1056 
1057 bool LoopInfoWrapperPass::runOnFunction(Function &) {
1058  releaseMemory();
1059  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
1060  return false;
1061 }
1062 
1064  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
1065  // function each time verifyAnalysis is called is very expensive. The
1066  // -verify-loop-info option can enable this. In order to perform some
1067  // checking by default, LoopPass has been taught to call verifyLoop manually
1068  // during loop pass sequences.
1069  if (VerifyLoopInfo) {
1070  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1071  LI.verify(DT);
1072  }
1073 }
1074 
1076  AU.setPreservesAll();
1078 }
1079 
1081  LI.print(OS);
1082 }
1083 
1086  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1087  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1088  LI.verify(DT);
1089  return PreservedAnalyses::all();
1090 }
1091 
1092 //===----------------------------------------------------------------------===//
1093 // LoopBlocksDFS implementation
1094 //
1095 
1096 /// Traverse the loop blocks and store the DFS result.
1097 /// Useful for clients that just want the final DFS result and don't need to
1098 /// visit blocks during the initial traversal.
1100  LoopBlocksTraversal Traversal(*this, LI);
1101  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
1102  POE = Traversal.end();
1103  POI != POE; ++POI)
1104  ;
1105 }
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:710
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:914
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:926
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:476
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
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
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:451
ConstantInt * getConstIntStepValue() const
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:444
LLVM_NODISCARD bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:270
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:1006
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:384
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:1165
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:198
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:928
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:900
void getLoopLatches(SmallVectorImpl< BasicBlock * > &LoopLatches) const
Return all loop latch blocks of this loop.
Definition: LoopInfo.h:314
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:853
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:677
static TempMDTuple getTemporary(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1177
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1183
void print(raw_ostream &O, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: LoopInfo.cpp:1080
BranchInst * getLoopGuardBranch() const
Return the loop guard branch, if it exists.
Definition: LoopInfo.cpp:362
BasicBlock * getHeader() const
Definition: LoopInfo.h:105
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:144
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:1075
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:509
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:246
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
Definition: LoopInfo.cpp:998
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:244
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:1099
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
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:1054
StringRef getString() const
Definition: Metadata.cpp:463
Core dominator tree base class.
Definition: LoopInfo.h:66
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:643
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
bool isLoopExiting(const BasicBlock *BB) const
True if terminator in the block can branch to another block that is outside of the current loop...
Definition: LoopInfo.h:208
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:521
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:645
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:1172
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:607
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:512
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:4355
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:115
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:972
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:1054
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:609
void setPreservesAll()
Set by analyses that do not transform their input at all.
iterator_range< user_iterator > users()
Definition: Value.h:419
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:174
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: LoopInfo.cpp:844
LoopT * getParentLoop() const
Definition: LoopInfo.h:106
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:460
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:485
const DebugLoc & getStart() const
Definition: LoopInfo.h:522
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:509
#define I(x, y, z)
Definition: MD5.cpp:58
Below are some utilities to get the loop guard, loop bounds and induction variable, and to check if a given phinode is an auxiliary induction variable, if the loop is guarded, and if the loop is canonical.
Definition: LoopInfo.h:614
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:160
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:467
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:151
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:397
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
Definition: LoopInfo.cpp:532
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:73
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:1084
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:593
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:1208
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:161
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:932
block_iterator block_begin() const
Definition: LoopInfo.h:159
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:1002
loops
Definition: LoopInfo.cpp:1054
const BasicBlock * getParent() const
Definition: Instruction.h:66
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, DominatorTree &DT)
Definition: LoopInfo.cpp:417
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: LoopInfo.cpp:1063
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:276
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