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