LLVM  6.0.0svn
LoopInfo.cpp
Go to the documentation of this file.
1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the LoopInfo class that is used to identify natural loops
11 // and determine the loop depth of various nodes of the CFG. Note that the
12 // loops identified may actually be several natural loops that share the same
13 // header node... not just a single natural loop.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/ADT/ScopeExit.h"
20 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DebugLoc.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/LLVMContext.h"
30 #include "llvm/IR/Metadata.h"
31 #include "llvm/IR/PassManager.h"
33 #include "llvm/Support/Debug.h"
35 #include <algorithm>
36 using namespace llvm;
37 
38 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
41 
42 // Always verify loopinfo if expensive checking is enabled.
43 #ifdef EXPENSIVE_CHECKS
44 bool llvm::VerifyLoopInfo = true;
45 #else
46 bool llvm::VerifyLoopInfo = false;
47 #endif
49  VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
50  cl::desc("Verify loop info (time consuming)"));
51 
52 //===----------------------------------------------------------------------===//
53 // Loop implementation
54 //
55 
56 bool Loop::isLoopInvariant(const Value *V) const {
57  if (const Instruction *I = dyn_cast<Instruction>(V))
58  return !contains(I);
59  return true; // All non-instructions are loop invariant
60 }
61 
63  return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
64 }
65 
66 bool Loop::makeLoopInvariant(Value *V, bool &Changed,
67  Instruction *InsertPt) const {
68  if (Instruction *I = dyn_cast<Instruction>(V))
69  return makeLoopInvariant(I, Changed, InsertPt);
70  return true; // All non-instructions are loop-invariant.
71 }
72 
73 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
74  Instruction *InsertPt) const {
75  // Test if the value is already loop-invariant.
76  if (isLoopInvariant(I))
77  return true;
79  return false;
80  if (I->mayReadFromMemory())
81  return false;
82  // EH block instructions are immobile.
83  if (I->isEHPad())
84  return false;
85  // Determine the insertion point, unless one was given.
86  if (!InsertPt) {
87  BasicBlock *Preheader = getLoopPreheader();
88  // Without a preheader, hoisting is not feasible.
89  if (!Preheader)
90  return false;
91  InsertPt = Preheader->getTerminator();
92  }
93  // Don't hoist instructions with loop-variant operands.
94  for (Value *Operand : I->operands())
95  if (!makeLoopInvariant(Operand, Changed, InsertPt))
96  return false;
97 
98  // Hoist.
99  I->moveBefore(InsertPt);
100 
101  // There is possibility of hoisting this instruction above some arbitrary
102  // condition. Any metadata defined on it can be control dependent on this
103  // condition. Conservatively strip it here so that we don't give any wrong
104  // information to the optimizer.
106 
107  Changed = true;
108  return true;
109 }
110 
112  BasicBlock *H = getHeader();
113 
114  BasicBlock *Incoming = nullptr, *Backedge = nullptr;
115  pred_iterator PI = pred_begin(H);
116  assert(PI != pred_end(H) && "Loop must have at least one backedge!");
117  Backedge = *PI++;
118  if (PI == pred_end(H))
119  return nullptr; // dead loop
120  Incoming = *PI++;
121  if (PI != pred_end(H))
122  return nullptr; // multiple backedges?
123 
124  if (contains(Incoming)) {
125  if (contains(Backedge))
126  return nullptr;
127  std::swap(Incoming, Backedge);
128  } else if (!contains(Backedge))
129  return nullptr;
130 
131  // Loop over all of the PHI nodes, looking for a canonical indvar.
132  for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
133  PHINode *PN = cast<PHINode>(I);
134  if (ConstantInt *CI =
135  dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
136  if (CI->isZero())
137  if (Instruction *Inc =
138  dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
139  if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
140  if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
141  if (CI->isOne())
142  return PN;
143  }
144  return nullptr;
145 }
146 
147 // Check that 'BB' doesn't have any uses outside of the 'L'
148 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
149  DominatorTree &DT) {
150  for (const Instruction &I : BB) {
151  // Tokens can't be used in PHI nodes and live-out tokens prevent loop
152  // optimizations, so for the purposes of considered LCSSA form, we
153  // can ignore them.
154  if (I.getType()->isTokenTy())
155  continue;
156 
157  for (const Use &U : I.uses()) {
158  const Instruction *UI = cast<Instruction>(U.getUser());
159  const BasicBlock *UserBB = UI->getParent();
160  if (const PHINode *P = dyn_cast<PHINode>(UI))
161  UserBB = P->getIncomingBlock(U);
162 
163  // Check the current block, as a fast-path, before checking whether
164  // the use is anywhere in the loop. Most values are used in the same
165  // block they are defined in. Also, blocks not reachable from the
166  // entry are special; uses in them don't need to go through PHIs.
167  if (UserBB != &BB && !L.contains(UserBB) &&
168  DT.isReachableFromEntry(UserBB))
169  return false;
170  }
171  }
172  return true;
173 }
174 
176  // For each block we check that it doesn't have any uses outside of this loop.
177  return all_of(this->blocks(), [&](const BasicBlock *BB) {
178  return isBlockInLCSSAForm(*this, *BB, DT);
179  });
180 }
181 
183  // For each block we check that it doesn't have any uses outside of its
184  // innermost loop. This process will transitively guarantee that the current
185  // loop and all of the nested loops are in LCSSA form.
186  return all_of(this->blocks(), [&](const BasicBlock *BB) {
187  return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
188  });
189 }
190 
192  // Normal-form loops have a preheader, a single backedge, and all of their
193  // exits have all their predecessors inside the loop.
195 }
196 
197 // Routines that reform the loop CFG and split edges often fail on indirectbr.
198 bool Loop::isSafeToClone() const {
199  // Return false if any loop blocks contain indirectbrs, or there are any calls
200  // to noduplicate functions.
201  for (BasicBlock *BB : this->blocks()) {
202  if (isa<IndirectBrInst>(BB->getTerminator()))
203  return false;
204 
205  for (Instruction &I : *BB)
206  if (auto CS = CallSite(&I))
207  if (CS.cannotDuplicate())
208  return false;
209  }
210  return true;
211 }
212 
214  MDNode *LoopID = nullptr;
215  if (BasicBlock *Latch = getLoopLatch()) {
216  LoopID = Latch->getTerminator()->getMetadata(LLVMContext::MD_loop);
217  } else {
218  assert(!getLoopLatch() &&
219  "The loop should have no single latch at this point");
220  // Go through each predecessor of the loop header and check the
221  // terminator for the metadata.
222  BasicBlock *H = getHeader();
223  for (BasicBlock *BB : this->blocks()) {
224  TerminatorInst *TI = BB->getTerminator();
225  MDNode *MD = nullptr;
226 
227  // Check if this terminator branches to the loop header.
228  for (BasicBlock *Successor : TI->successors()) {
229  if (Successor == H) {
231  break;
232  }
233  }
234  if (!MD)
235  return nullptr;
236 
237  if (!LoopID)
238  LoopID = MD;
239  else if (MD != LoopID)
240  return nullptr;
241  }
242  }
243  if (!LoopID || LoopID->getNumOperands() == 0 ||
244  LoopID->getOperand(0) != LoopID)
245  return nullptr;
246  return LoopID;
247 }
248 
249 void Loop::setLoopID(MDNode *LoopID) const {
250  assert(LoopID && "Loop ID should not be null");
251  assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
252  assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");
253 
254  if (BasicBlock *Latch = getLoopLatch()) {
255  Latch->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
256  return;
257  }
258 
259  assert(!getLoopLatch() &&
260  "The loop should have no single latch at this point");
261  BasicBlock *H = getHeader();
262  for (BasicBlock *BB : this->blocks()) {
263  TerminatorInst *TI = BB->getTerminator();
264  for (BasicBlock *Successor : TI->successors()) {
265  if (Successor == H)
266  TI->setMetadata(LLVMContext::MD_loop, LoopID);
267  }
268  }
269 }
270 
272  MDNode *DesiredLoopIdMetadata = getLoopID();
273 
274  if (!DesiredLoopIdMetadata)
275  return false;
276 
277  // The loop branch contains the parallel loop metadata. In order to ensure
278  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
279  // dependencies (thus converted the loop back to a sequential loop), check
280  // that all the memory instructions in the loop contain parallelism metadata
281  // that point to the same unique "loop id metadata" the loop branch does.
282  for (BasicBlock *BB : this->blocks()) {
283  for (Instruction &I : *BB) {
284  if (!I.mayReadOrWriteMemory())
285  continue;
286 
287  // The memory instruction can refer to the loop identifier metadata
288  // directly or indirectly through another list metadata (in case of
289  // nested parallel loops). The loop identifier metadata refers to
290  // itself so we can check both cases with the same routine.
291  MDNode *LoopIdMD =
293 
294  if (!LoopIdMD)
295  return false;
296 
297  bool LoopIdMDFound = false;
298  for (const MDOperand &MDOp : LoopIdMD->operands()) {
299  if (MDOp == DesiredLoopIdMetadata) {
300  LoopIdMDFound = true;
301  break;
302  }
303  }
304 
305  if (!LoopIdMDFound)
306  return false;
307  }
308  }
309  return true;
310 }
311 
313 
315  // If we have a debug location in the loop ID, then use it.
316  if (MDNode *LoopID = getLoopID()) {
317  DebugLoc Start;
318  // We use the first DebugLoc in the header as the start location of the loop
319  // and if there is a second DebugLoc in the header we use it as end location
320  // of the loop.
321  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
322  if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
323  if (!Start)
324  Start = DebugLoc(L);
325  else
326  return LocRange(Start, DebugLoc(L));
327  }
328  }
329 
330  if (Start)
331  return LocRange(Start);
332  }
333 
334  // Try the pre-header first.
335  if (BasicBlock *PHeadBB = getLoopPreheader())
336  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
337  return LocRange(DL);
338 
339  // If we have no pre-header or there are no instructions with debug
340  // info in it, try the header.
341  if (BasicBlock *HeadBB = getHeader())
342  return LocRange(HeadBB->getTerminator()->getDebugLoc());
343 
344  return LocRange();
345 }
346 
348  // Each predecessor of each exit block of a normal loop is contained
349  // within the loop.
350  SmallVector<BasicBlock *, 4> ExitBlocks;
351  getExitBlocks(ExitBlocks);
352  for (BasicBlock *BB : ExitBlocks)
353  for (BasicBlock *Predecessor : predecessors(BB))
354  if (!contains(Predecessor))
355  return false;
356  // All the requirements are met.
357  return true;
358 }
359 
361  SmallVectorImpl<BasicBlock *> &ExitBlocks) const {
363  "getUniqueExitBlocks assumes the loop has canonical form exits!");
364 
365  SmallVector<BasicBlock *, 32> SwitchExitBlocks;
366  for (BasicBlock *BB : this->blocks()) {
367  SwitchExitBlocks.clear();
368  for (BasicBlock *Successor : successors(BB)) {
369  // If block is inside the loop then it is not an exit block.
370  if (contains(Successor))
371  continue;
372 
374  BasicBlock *FirstPred = *PI;
375 
376  // If current basic block is this exit block's first predecessor
377  // then only insert exit block in to the output ExitBlocks vector.
378  // This ensures that same exit block is not inserted twice into
379  // ExitBlocks vector.
380  if (BB != FirstPred)
381  continue;
382 
383  // If a terminator has more then two successors, for example SwitchInst,
384  // then it is possible that there are multiple edges from current block
385  // to one exit block.
386  if (std::distance(succ_begin(BB), succ_end(BB)) <= 2) {
387  ExitBlocks.push_back(Successor);
388  continue;
389  }
390 
391  // In case of multiple edges from current block to exit block, collect
392  // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
393  // duplicate edges.
394  if (!is_contained(SwitchExitBlocks, Successor)) {
395  SwitchExitBlocks.push_back(Successor);
396  ExitBlocks.push_back(Successor);
397  }
398  }
399  }
400 }
401 
403  SmallVector<BasicBlock *, 8> UniqueExitBlocks;
404  getUniqueExitBlocks(UniqueExitBlocks);
405  if (UniqueExitBlocks.size() == 1)
406  return UniqueExitBlocks[0];
407  return nullptr;
408 }
409 
410 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
411 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
412 
414  print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
415 }
416 #endif
417 
418 //===----------------------------------------------------------------------===//
419 // UnloopUpdater implementation
420 //
421 
422 namespace {
423 /// Find the new parent loop for all blocks within the "unloop" whose last
424 /// backedges has just been removed.
425 class UnloopUpdater {
426  Loop &Unloop;
427  LoopInfo *LI;
428 
430 
431  // Map unloop's immediate subloops to their nearest reachable parents. Nested
432  // loops within these subloops will not change parents. However, an immediate
433  // subloop's new parent will be the nearest loop reachable from either its own
434  // exits *or* any of its nested loop's exits.
435  DenseMap<Loop *, Loop *> SubloopParents;
436 
437  // Flag the presence of an irreducible backedge whose destination is a block
438  // directly contained by the original unloop.
439  bool FoundIB;
440 
441 public:
442  UnloopUpdater(Loop *UL, LoopInfo *LInfo)
443  : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
444 
445  void updateBlockParents();
446 
447  void removeBlocksFromAncestors();
448 
449  void updateSubloopParents();
450 
451 protected:
452  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
453 };
454 } // end anonymous namespace
455 
456 /// Update the parent loop for all blocks that are directly contained within the
457 /// original "unloop".
458 void UnloopUpdater::updateBlockParents() {
459  if (Unloop.getNumBlocks()) {
460  // Perform a post order CFG traversal of all blocks within this loop,
461  // propagating the nearest loop from successors to predecessors.
462  LoopBlocksTraversal Traversal(DFS, LI);
463  for (BasicBlock *POI : Traversal) {
464 
465  Loop *L = LI->getLoopFor(POI);
466  Loop *NL = getNearestLoop(POI, L);
467 
468  if (NL != L) {
469  // For reducible loops, NL is now an ancestor of Unloop.
470  assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
471  "uninitialized successor");
472  LI->changeLoopFor(POI, NL);
473  } else {
474  // Or the current block is part of a subloop, in which case its parent
475  // is unchanged.
476  assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
477  }
478  }
479  }
480  // Each irreducible loop within the unloop induces a round of iteration using
481  // the DFS result cached by Traversal.
482  bool Changed = FoundIB;
483  for (unsigned NIters = 0; Changed; ++NIters) {
484  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
485 
486  // Iterate over the postorder list of blocks, propagating the nearest loop
487  // from successors to predecessors as before.
488  Changed = false;
489  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
490  POE = DFS.endPostorder();
491  POI != POE; ++POI) {
492 
493  Loop *L = LI->getLoopFor(*POI);
494  Loop *NL = getNearestLoop(*POI, L);
495  if (NL != L) {
496  assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
497  "uninitialized successor");
498  LI->changeLoopFor(*POI, NL);
499  Changed = true;
500  }
501  }
502  }
503 }
504 
505 /// Remove unloop's blocks from all ancestors below their new parents.
506 void UnloopUpdater::removeBlocksFromAncestors() {
507  // Remove all unloop's blocks (including those in nested subloops) from
508  // ancestors below the new parent loop.
509  for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
510  BI != BE; ++BI) {
511  Loop *OuterParent = LI->getLoopFor(*BI);
512  if (Unloop.contains(OuterParent)) {
513  while (OuterParent->getParentLoop() != &Unloop)
514  OuterParent = OuterParent->getParentLoop();
515  OuterParent = SubloopParents[OuterParent];
516  }
517  // Remove blocks from former Ancestors except Unloop itself which will be
518  // deleted.
519  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
520  OldParent = OldParent->getParentLoop()) {
521  assert(OldParent && "new loop is not an ancestor of the original");
522  OldParent->removeBlockFromLoop(*BI);
523  }
524  }
525 }
526 
527 /// Update the parent loop for all subloops directly nested within unloop.
528 void UnloopUpdater::updateSubloopParents() {
529  while (!Unloop.empty()) {
530  Loop *Subloop = *std::prev(Unloop.end());
531  Unloop.removeChildLoop(std::prev(Unloop.end()));
532 
533  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
534  if (Loop *Parent = SubloopParents[Subloop])
535  Parent->addChildLoop(Subloop);
536  else
537  LI->addTopLevelLoop(Subloop);
538  }
539 }
540 
541 /// Return the nearest parent loop among this block's successors. If a successor
542 /// is a subloop header, consider its parent to be the nearest parent of the
543 /// subloop's exits.
544 ///
545 /// For subloop blocks, simply update SubloopParents and return NULL.
546 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
547 
548  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
549  // is considered uninitialized.
550  Loop *NearLoop = BBLoop;
551 
552  Loop *Subloop = nullptr;
553  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
554  Subloop = NearLoop;
555  // Find the subloop ancestor that is directly contained within Unloop.
556  while (Subloop->getParentLoop() != &Unloop) {
557  Subloop = Subloop->getParentLoop();
558  assert(Subloop && "subloop is not an ancestor of the original loop");
559  }
560  // Get the current nearest parent of the Subloop exits, initially Unloop.
561  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
562  }
563 
564  succ_iterator I = succ_begin(BB), E = succ_end(BB);
565  if (I == E) {
566  assert(!Subloop && "subloop blocks must have a successor");
567  NearLoop = nullptr; // unloop blocks may now exit the function.
568  }
569  for (; I != E; ++I) {
570  if (*I == BB)
571  continue; // self loops are uninteresting
572 
573  Loop *L = LI->getLoopFor(*I);
574  if (L == &Unloop) {
575  // This successor has not been processed. This path must lead to an
576  // irreducible backedge.
577  assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
578  FoundIB = true;
579  }
580  if (L != &Unloop && Unloop.contains(L)) {
581  // Successor is in a subloop.
582  if (Subloop)
583  continue; // Branching within subloops. Ignore it.
584 
585  // BB branches from the original into a subloop header.
586  assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
587 
588  // Get the current nearest parent of the Subloop's exits.
589  L = SubloopParents[L];
590  // L could be Unloop if the only exit was an irreducible backedge.
591  }
592  if (L == &Unloop) {
593  continue;
594  }
595  // Handle critical edges from Unloop into a sibling loop.
596  if (L && !L->contains(&Unloop)) {
597  L = L->getParentLoop();
598  }
599  // Remember the nearest parent loop among successors or subloop exits.
600  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
601  NearLoop = L;
602  }
603  if (Subloop) {
604  SubloopParents[Subloop] = NearLoop;
605  return BBLoop;
606  }
607  return NearLoop;
608 }
609 
610 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
611 
614  // Check whether the analysis, all analyses on functions, or the function's
615  // CFG have been preserved.
616  auto PAC = PA.getChecker<LoopAnalysis>();
617  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
618  PAC.preservedSet<CFGAnalyses>());
619 }
620 
621 void LoopInfo::erase(Loop *Unloop) {
622  assert(!Unloop->isInvalid() && "Loop has already been erased!");
623  RemovedLoops.push_back(Unloop);
624 
625  auto InvalidateOnExit =
626  make_scope_exit([&]() { BaseT::clearLoop(*Unloop); });
627 
628  // First handle the special case of no parent loop to simplify the algorithm.
629  if (!Unloop->getParentLoop()) {
630  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
631  for (Loop::block_iterator I = Unloop->block_begin(),
632  E = Unloop->block_end();
633  I != E; ++I) {
634 
635  // Don't reparent blocks in subloops.
636  if (getLoopFor(*I) != Unloop)
637  continue;
638 
639  // Blocks no longer have a parent but are still referenced by Unloop until
640  // the Unloop object is deleted.
641  changeLoopFor(*I, nullptr);
642  }
643 
644  // Remove the loop from the top-level LoopInfo object.
645  for (iterator I = begin();; ++I) {
646  assert(I != end() && "Couldn't find loop");
647  if (*I == Unloop) {
648  removeLoop(I);
649  break;
650  }
651  }
652 
653  // Move all of the subloops to the top-level.
654  while (!Unloop->empty())
655  addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
656 
657  return;
658  }
659 
660  // Update the parent loop for all blocks within the loop. Blocks within
661  // subloops will not change parents.
662  UnloopUpdater Updater(Unloop, this);
663  Updater.updateBlockParents();
664 
665  // Remove blocks from former ancestor loops.
666  Updater.removeBlocksFromAncestors();
667 
668  // Add direct subloops as children in their new parent loop.
669  Updater.updateSubloopParents();
670 
671  // Remove unloop from its parent loop.
672  Loop *ParentLoop = Unloop->getParentLoop();
673  for (Loop::iterator I = ParentLoop->begin();; ++I) {
674  assert(I != ParentLoop->end() && "Couldn't find loop");
675  if (*I == Unloop) {
676  ParentLoop->removeChildLoop(I);
677  break;
678  }
679  }
680 }
681 
682 AnalysisKey LoopAnalysis::Key;
683 
685  // FIXME: Currently we create a LoopInfo from scratch for every function.
686  // This may prove to be too wasteful due to deallocating and re-allocating
687  // memory each time for the underlying map and vector datastructures. At some
688  // point it may prove worthwhile to use a freelist and recycle LoopInfo
689  // objects. I don't want to add that kind of complexity until the scope of
690  // the problem is better understood.
691  LoopInfo LI;
693  return LI;
694 }
695 
698  AM.getResult<LoopAnalysis>(F).print(OS);
699  return PreservedAnalyses::all();
700 }
701 
702 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
703  OS << Banner;
704  for (auto *Block : L.blocks())
705  if (Block)
706  Block->print(OS);
707  else
708  OS << "Printing <null> block";
709 }
710 
711 //===----------------------------------------------------------------------===//
712 // LoopInfo implementation
713 //
714 
715 char LoopInfoWrapperPass::ID = 0;
716 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
717  true, true)
720  true, true)
721 
722 bool LoopInfoWrapperPass::runOnFunction(Function &) {
723  releaseMemory();
724  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
725  return false;
726 }
727 
729  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
730  // function each time verifyAnalysis is called is very expensive. The
731  // -verify-loop-info option can enable this. In order to perform some
732  // checking by default, LoopPass has been taught to call verifyLoop manually
733  // during loop pass sequences.
734  if (VerifyLoopInfo) {
735  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
736  LI.verify(DT);
737  }
738 }
739 
741  AU.setPreservesAll();
743 }
744 
746  LI.print(OS);
747 }
748 
751  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
752  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
753  LI.verify(DT);
754  return PreservedAnalyses::all();
755 }
756 
757 //===----------------------------------------------------------------------===//
758 // LoopBlocksDFS implementation
759 //
760 
761 /// Traverse the loop blocks and store the DFS result.
762 /// Useful for clients that just want the final DFS result and don't need to
763 /// visit blocks during the initial traversal.
765  LoopBlocksTraversal Traversal(*this, LI);
766  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
767  POE = Traversal.end();
768  POI != POE; ++POI)
769  ;
770 }
void push_back(const T &Elt)
Definition: SmallVector.h:212
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:709
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:684
BasicBlock * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:157
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:696
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1187
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
static cl::opt< bool, true > VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), cl::desc("Verify loop info (time consuming)"))
bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:182
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:175
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:303
This file contains the declarations for metadata subclasses.
BasicBlock * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:106
BasicBlock * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfo.cpp:402
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:47
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=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:66
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:816
A debug info location.
Definition: DebugLoc.h:34
Metadata node.
Definition: Metadata.h:862
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
F(f)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1067
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:290
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:62
bool isInvalid() const
Return true if this loop is no longer valid.
Definition: LoopInfo.h:176
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:624
void print(raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:325
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:304
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Traverse the blocks in a loop using a depth-first search.
Definition: LoopIterator.h:182
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:631
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
POTIterator begin()
Postorder traversal over the graph.
Definition: LoopIterator.h:198
std::vector< Loop *>::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:603
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:621
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:871
void print(raw_ostream &O, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: LoopInfo.cpp:745
BasicBlock * getHeader() const
Definition: LoopInfo.h:107
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:103
void getExitBlocks(SmallVectorImpl< BasicBlock * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:63
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfo.cpp:347
std::vector< Loop *>::const_iterator iterator
Definition: LoopInfo.h:146
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LoopInfo.cpp:740
op_range operands() const
Definition: Metadata.h:1065
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:249
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:194
Debug location.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:764
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
void getUniqueExitBlocks(SmallVectorImpl< BasicBlock *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfo.cpp:360
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
Natural Loop true
Definition: LoopInfo.cpp:719
Core dominator tree base class.
Definition: LoopInfo.h:59
succ_range successors()
Definition: InstrTypes.h:267
#define P(N)
INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information", true, true) INITIALIZE_PASS_END(LoopInfoWrapperPass
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
void dump() const
Definition: LoopInfo.cpp:411
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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 dumpVerbose() const
Definition: LoopInfo.cpp:413
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:483
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:113
Represent the analysis usage information of a pass.
std::vector< BasicBlock *>::const_iterator block_iterator
Definition: LoopInfo.h:160
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
op_range operands()
Definition: User.h:222
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:312
A range representing the start and end location of a loop.
Definition: LoopInfo.h:407
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1214
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:56
unsigned first
bool contains(const Loop *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:117
Iterator for intrusive lists based on ilist_node.
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Natural Loop Information
Definition: LoopInfo.cpp:719
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:110
bool VerifyLoopInfo
Enables verification of loop info.
Definition: LoopInfo.cpp:46
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:923
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:111
Store the result of a depth first search within basic blocks contained by a single loop...
Definition: LoopIterator.h:98
LocRange getLocRange() const
Return the source code span of the loop.
Definition: LoopInfo.cpp:314
void setPreservesAll()
Set by analyses that do not transform their input at all.
static void DFS(BasicBlock *Root, SetVector< BasicBlock *> &Set)
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: LoopInfo.cpp:612
LoopT * getParentLoop() const
Definition: LoopInfo.h:108
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:191
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:213
const DebugLoc & getStart() const
Definition: LoopInfo.h:417
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:404
#define I(x, y, z)
Definition: MD5.cpp:58
bool mayReadFromMemory() const
Return true if this instruction may read memory.
std::vector< BasicBlock * >::const_iterator POIterator
Postorder list iterators.
Definition: LoopIterator.h:101
block_iterator block_end() const
Definition: LoopInfo.h:162
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:198
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
bool empty() const
Definition: LoopInfo.h:153
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 isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
Definition: LoopInfo.cpp:271
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
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:749
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:88
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:507
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:896
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
const TerminatorInst * 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:120
This header defines various interfaces for pass management in LLVM.
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1073
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:163
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:702
block_iterator block_begin() const
Definition: LoopInfo.h:161
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:422
loops
Definition: LoopInfo.cpp:719
const BasicBlock * getParent() const
Definition: Instruction.h:66
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, DominatorTree &DT)
Definition: LoopInfo.cpp:148
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: LoopInfo.cpp:728
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:870