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/SmallPtrSet.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DebugLoc.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/Instructions.h"
28 #include "llvm/IR/LLVMContext.h"
29 #include "llvm/IR/Metadata.h"
30 #include "llvm/IR/PassManager.h"
32 #include "llvm/Support/Debug.h"
34 #include <algorithm>
35 using namespace llvm;
36 
37 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
40 
41 // Always verify loopinfo if expensive checking is enabled.
42 #ifdef EXPENSIVE_CHECKS
43 bool llvm::VerifyLoopInfo = true;
44 #else
45 bool llvm::VerifyLoopInfo = false;
46 #endif
47 static cl::opt<bool,true>
48 VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
49  cl::desc("Verify loop info (time consuming)"));
50 
51 //===----------------------------------------------------------------------===//
52 // Loop implementation
53 //
54 
55 bool Loop::isLoopInvariant(const Value *V) const {
56  if (const Instruction *I = dyn_cast<Instruction>(V))
57  return !contains(I);
58  return true; // All non-instructions are loop invariant
59 }
60 
62  return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
63 }
64 
65 bool Loop::makeLoopInvariant(Value *V, bool &Changed,
66  Instruction *InsertPt) const {
67  if (Instruction *I = dyn_cast<Instruction>(V))
68  return makeLoopInvariant(I, Changed, InsertPt);
69  return true; // All non-instructions are loop-invariant.
70 }
71 
72 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
73  Instruction *InsertPt) const {
74  // Test if the value is already loop-invariant.
75  if (isLoopInvariant(I))
76  return true;
78  return false;
79  if (I->mayReadFromMemory())
80  return false;
81  // EH block instructions are immobile.
82  if (I->isEHPad())
83  return false;
84  // Determine the insertion point, unless one was given.
85  if (!InsertPt) {
86  BasicBlock *Preheader = getLoopPreheader();
87  // Without a preheader, hoisting is not feasible.
88  if (!Preheader)
89  return false;
90  InsertPt = Preheader->getTerminator();
91  }
92  // Don't hoist instructions with loop-variant operands.
93  for (Value *Operand : I->operands())
94  if (!makeLoopInvariant(Operand, Changed, InsertPt))
95  return false;
96 
97  // Hoist.
98  I->moveBefore(InsertPt);
99 
100  // There is possibility of hoisting this instruction above some arbitrary
101  // condition. Any metadata defined on it can be control dependent on this
102  // condition. Conservatively strip it here so that we don't give any wrong
103  // information to the optimizer.
105 
106  Changed = true;
107  return true;
108 }
109 
111  BasicBlock *H = getHeader();
112 
113  BasicBlock *Incoming = nullptr, *Backedge = nullptr;
114  pred_iterator PI = pred_begin(H);
115  assert(PI != pred_end(H) &&
116  "Loop must have at least one backedge!");
117  Backedge = *PI++;
118  if (PI == pred_end(H)) return nullptr; // dead loop
119  Incoming = *PI++;
120  if (PI != pred_end(H)) return nullptr; // multiple backedges?
121 
122  if (contains(Incoming)) {
123  if (contains(Backedge))
124  return nullptr;
125  std::swap(Incoming, Backedge);
126  } else if (!contains(Backedge))
127  return nullptr;
128 
129  // Loop over all of the PHI nodes, looking for a canonical indvar.
130  for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
131  PHINode *PN = cast<PHINode>(I);
132  if (ConstantInt *CI =
133  dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
134  if (CI->isZero())
135  if (Instruction *Inc =
136  dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
137  if (Inc->getOpcode() == Instruction::Add &&
138  Inc->getOperand(0) == PN)
139  if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
140  if (CI->isOne())
141  return PN;
142  }
143  return nullptr;
144 }
145 
146 // Check that 'BB' doesn't have any uses outside of the 'L'
147 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
148  DominatorTree &DT) {
149  for (const Instruction &I : BB) {
150  // Tokens can't be used in PHI nodes and live-out tokens prevent loop
151  // optimizations, so for the purposes of considered LCSSA form, we
152  // can ignore them.
153  if (I.getType()->isTokenTy())
154  continue;
155 
156  for (const Use &U : I.uses()) {
157  const Instruction *UI = cast<Instruction>(U.getUser());
158  const BasicBlock *UserBB = UI->getParent();
159  if (const PHINode *P = dyn_cast<PHINode>(UI))
160  UserBB = P->getIncomingBlock(U);
161 
162  // Check the current block, as a fast-path, before checking whether
163  // the use is anywhere in the loop. Most values are used in the same
164  // block they are defined in. Also, blocks not reachable from the
165  // entry are special; uses in them don't need to go through PHIs.
166  if (UserBB != &BB && !L.contains(UserBB) &&
167  DT.isReachableFromEntry(UserBB))
168  return false;
169  }
170  }
171  return true;
172 }
173 
175  // For each block we check that it doesn't have any uses outside of this loop.
176  return all_of(this->blocks(), [&](const BasicBlock *BB) {
177  return isBlockInLCSSAForm(*this, *BB, DT);
178  });
179 }
180 
182  // For each block we check that it doesn't have any uses outside of its
183  // innermost loop. This process will transitively guarantee that the current
184  // loop and all of the nested loops are in LCSSA form.
185  return all_of(this->blocks(), [&](const BasicBlock *BB) {
186  return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
187  });
188 }
189 
191  // Normal-form loops have a preheader, a single backedge, and all of their
192  // exits have all their predecessors inside the loop.
194 }
195 
196 // Routines that reform the loop CFG and split edges often fail on indirectbr.
197 bool Loop::isSafeToClone() const {
198  // Return false if any loop blocks contain indirectbrs, or there are any calls
199  // to noduplicate functions.
200  for (BasicBlock *BB : this->blocks()) {
201  if (isa<IndirectBrInst>(BB->getTerminator()))
202  return false;
203 
204  for (Instruction &I : *BB)
205  if (auto CS = CallSite(&I))
206  if (CS.cannotDuplicate())
207  return false;
208  }
209  return true;
210 }
211 
213  MDNode *LoopID = nullptr;
214  if (BasicBlock *Latch = getLoopLatch()) {
215  LoopID = Latch->getTerminator()->getMetadata(LLVMContext::MD_loop);
216  } else {
217  assert(!getLoopLatch() &&
218  "The loop should have no single latch at this point");
219  // Go through each predecessor of the loop header and check the
220  // terminator for the metadata.
221  BasicBlock *H = getHeader();
222  for (BasicBlock *BB : this->blocks()) {
223  TerminatorInst *TI = BB->getTerminator();
224  MDNode *MD = nullptr;
225 
226  // Check if this terminator branches to the loop header.
227  for (BasicBlock *Successor : TI->successors()) {
228  if (Successor == H) {
230  break;
231  }
232  }
233  if (!MD)
234  return nullptr;
235 
236  if (!LoopID)
237  LoopID = MD;
238  else if (MD != LoopID)
239  return nullptr;
240  }
241  }
242  if (!LoopID || LoopID->getNumOperands() == 0 ||
243  LoopID->getOperand(0) != LoopID)
244  return nullptr;
245  return LoopID;
246 }
247 
248 void Loop::setLoopID(MDNode *LoopID) const {
249  assert(LoopID && "Loop ID should not be null");
250  assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
251  assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");
252 
253  if (BasicBlock *Latch = getLoopLatch()) {
254  Latch->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
255  return;
256  }
257 
258  assert(!getLoopLatch() && "The loop should have no single latch at this point");
259  BasicBlock *H = getHeader();
260  for (BasicBlock *BB : this->blocks()) {
261  TerminatorInst *TI = BB->getTerminator();
262  for (BasicBlock *Successor : TI->successors()) {
263  if (Successor == H)
264  TI->setMetadata(LLVMContext::MD_loop, LoopID);
265  }
266  }
267 }
268 
270  MDNode *DesiredLoopIdMetadata = getLoopID();
271 
272  if (!DesiredLoopIdMetadata)
273  return false;
274 
275  // The loop branch contains the parallel loop metadata. In order to ensure
276  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
277  // dependencies (thus converted the loop back to a sequential loop), check
278  // that all the memory instructions in the loop contain parallelism metadata
279  // that point to the same unique "loop id metadata" the loop branch does.
280  for (BasicBlock *BB : this->blocks()) {
281  for (Instruction &I : *BB) {
282  if (!I.mayReadOrWriteMemory())
283  continue;
284 
285  // The memory instruction can refer to the loop identifier metadata
286  // directly or indirectly through another list metadata (in case of
287  // nested parallel loops). The loop identifier metadata refers to
288  // itself so we can check both cases with the same routine.
289  MDNode *LoopIdMD =
291 
292  if (!LoopIdMD)
293  return false;
294 
295  bool LoopIdMDFound = false;
296  for (const MDOperand &MDOp : LoopIdMD->operands()) {
297  if (MDOp == DesiredLoopIdMetadata) {
298  LoopIdMDFound = true;
299  break;
300  }
301  }
302 
303  if (!LoopIdMDFound)
304  return false;
305  }
306  }
307  return true;
308 }
309 
311  return getLocRange().getStart();
312 }
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 
360 void
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)
412  print(dbgs());
413 }
414 
416  print(dbgs(), /*Depth=*/ 0, /*Verbose=*/ true);
417 }
418 #endif
419 
420 //===----------------------------------------------------------------------===//
421 // UnloopUpdater implementation
422 //
423 
424 namespace {
425 /// Find the new parent loop for all blocks within the "unloop" whose last
426 /// backedges has just been removed.
427 class UnloopUpdater {
428  Loop &Unloop;
429  LoopInfo *LI;
430 
432 
433  // Map unloop's immediate subloops to their nearest reachable parents. Nested
434  // loops within these subloops will not change parents. However, an immediate
435  // subloop's new parent will be the nearest loop reachable from either its own
436  // exits *or* any of its nested loop's exits.
437  DenseMap<Loop*, Loop*> SubloopParents;
438 
439  // Flag the presence of an irreducible backedge whose destination is a block
440  // directly contained by the original unloop.
441  bool FoundIB;
442 
443 public:
444  UnloopUpdater(Loop *UL, LoopInfo *LInfo) :
445  Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
446 
447  void updateBlockParents();
448 
449  void removeBlocksFromAncestors();
450 
451  void updateSubloopParents();
452 
453 protected:
454  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
455 };
456 } // end anonymous namespace
457 
458 /// Update the parent loop for all blocks that are directly contained within the
459 /// original "unloop".
460 void UnloopUpdater::updateBlockParents() {
461  if (Unloop.getNumBlocks()) {
462  // Perform a post order CFG traversal of all blocks within this loop,
463  // propagating the nearest loop from successors to predecessors.
464  LoopBlocksTraversal Traversal(DFS, LI);
465  for (BasicBlock *POI : Traversal) {
466 
467  Loop *L = LI->getLoopFor(POI);
468  Loop *NL = getNearestLoop(POI, L);
469 
470  if (NL != L) {
471  // For reducible loops, NL is now an ancestor of Unloop.
472  assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
473  "uninitialized successor");
474  LI->changeLoopFor(POI, NL);
475  }
476  else {
477  // Or the current block is part of a subloop, in which case its parent
478  // is unchanged.
479  assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
480  }
481  }
482  }
483  // Each irreducible loop within the unloop induces a round of iteration using
484  // the DFS result cached by Traversal.
485  bool Changed = FoundIB;
486  for (unsigned NIters = 0; Changed; ++NIters) {
487  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
488 
489  // Iterate over the postorder list of blocks, propagating the nearest loop
490  // from successors to predecessors as before.
491  Changed = false;
492  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
493  POE = DFS.endPostorder(); POI != POE; ++POI) {
494 
495  Loop *L = LI->getLoopFor(*POI);
496  Loop *NL = getNearestLoop(*POI, L);
497  if (NL != L) {
498  assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
499  "uninitialized successor");
500  LI->changeLoopFor(*POI, NL);
501  Changed = true;
502  }
503  }
504  }
505 }
506 
507 /// Remove unloop's blocks from all ancestors below their new parents.
508 void UnloopUpdater::removeBlocksFromAncestors() {
509  // Remove all unloop's blocks (including those in nested subloops) from
510  // ancestors below the new parent loop.
511  for (Loop::block_iterator BI = Unloop.block_begin(),
512  BE = Unloop.block_end(); BI != BE; ++BI) {
513  Loop *OuterParent = LI->getLoopFor(*BI);
514  if (Unloop.contains(OuterParent)) {
515  while (OuterParent->getParentLoop() != &Unloop)
516  OuterParent = OuterParent->getParentLoop();
517  OuterParent = SubloopParents[OuterParent];
518  }
519  // Remove blocks from former Ancestors except Unloop itself which will be
520  // deleted.
521  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
522  OldParent = OldParent->getParentLoop()) {
523  assert(OldParent && "new loop is not an ancestor of the original");
524  OldParent->removeBlockFromLoop(*BI);
525  }
526  }
527 }
528 
529 /// Update the parent loop for all subloops directly nested within unloop.
530 void UnloopUpdater::updateSubloopParents() {
531  while (!Unloop.empty()) {
532  Loop *Subloop = *std::prev(Unloop.end());
533  Unloop.removeChildLoop(std::prev(Unloop.end()));
534 
535  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
536  if (Loop *Parent = SubloopParents[Subloop])
537  Parent->addChildLoop(Subloop);
538  else
539  LI->addTopLevelLoop(Subloop);
540  }
541 }
542 
543 /// Return the nearest parent loop among this block's successors. If a successor
544 /// is a subloop header, consider its parent to be the nearest parent of the
545 /// subloop's exits.
546 ///
547 /// For subloop blocks, simply update SubloopParents and return NULL.
548 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
549 
550  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
551  // is considered uninitialized.
552  Loop *NearLoop = BBLoop;
553 
554  Loop *Subloop = nullptr;
555  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
556  Subloop = NearLoop;
557  // Find the subloop ancestor that is directly contained within Unloop.
558  while (Subloop->getParentLoop() != &Unloop) {
559  Subloop = Subloop->getParentLoop();
560  assert(Subloop && "subloop is not an ancestor of the original loop");
561  }
562  // Get the current nearest parent of the Subloop exits, initially Unloop.
563  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
564  }
565 
566  succ_iterator I = succ_begin(BB), E = succ_end(BB);
567  if (I == E) {
568  assert(!Subloop && "subloop blocks must have a successor");
569  NearLoop = nullptr; // unloop blocks may now exit the function.
570  }
571  for (; I != E; ++I) {
572  if (*I == BB)
573  continue; // self loops are uninteresting
574 
575  Loop *L = LI->getLoopFor(*I);
576  if (L == &Unloop) {
577  // This successor has not been processed. This path must lead to an
578  // irreducible backedge.
579  assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
580  FoundIB = true;
581  }
582  if (L != &Unloop && Unloop.contains(L)) {
583  // Successor is in a subloop.
584  if (Subloop)
585  continue; // Branching within subloops. Ignore it.
586 
587  // BB branches from the original into a subloop header.
588  assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
589 
590  // Get the current nearest parent of the Subloop's exits.
591  L = SubloopParents[L];
592  // L could be Unloop if the only exit was an irreducible backedge.
593  }
594  if (L == &Unloop) {
595  continue;
596  }
597  // Handle critical edges from Unloop into a sibling loop.
598  if (L && !L->contains(&Unloop)) {
599  L = L->getParentLoop();
600  }
601  // Remember the nearest parent loop among successors or subloop exits.
602  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
603  NearLoop = L;
604  }
605  if (Subloop) {
606  SubloopParents[Subloop] = NearLoop;
607  return BBLoop;
608  }
609  return NearLoop;
610 }
611 
613  analyze(DomTree);
614 }
615 
618  // Check whether the analysis, all analyses on functions, or the function's
619  // CFG have been preserved.
620  auto PAC = PA.getChecker<LoopAnalysis>();
621  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
622  PAC.preservedSet<CFGAnalyses>());
623 }
624 
626  assert(!Unloop->isInvalid() && "Loop has already been removed");
627  Unloop->invalidate();
628  RemovedLoops.push_back(Unloop);
629 
630  // First handle the special case of no parent loop to simplify the algorithm.
631  if (!Unloop->getParentLoop()) {
632  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
633  for (Loop::block_iterator I = Unloop->block_begin(),
634  E = Unloop->block_end();
635  I != E; ++I) {
636 
637  // Don't reparent blocks in subloops.
638  if (getLoopFor(*I) != Unloop)
639  continue;
640 
641  // Blocks no longer have a parent but are still referenced by Unloop until
642  // the Unloop object is deleted.
643  changeLoopFor(*I, nullptr);
644  }
645 
646  // Remove the loop from the top-level LoopInfo object.
647  for (iterator I = begin();; ++I) {
648  assert(I != end() && "Couldn't find loop");
649  if (*I == Unloop) {
650  removeLoop(I);
651  break;
652  }
653  }
654 
655  // Move all of the subloops to the top-level.
656  while (!Unloop->empty())
657  addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
658 
659  return;
660  }
661 
662  // Update the parent loop for all blocks within the loop. Blocks within
663  // subloops will not change parents.
664  UnloopUpdater Updater(Unloop, this);
665  Updater.updateBlockParents();
666 
667  // Remove blocks from former ancestor loops.
668  Updater.removeBlocksFromAncestors();
669 
670  // Add direct subloops as children in their new parent loop.
671  Updater.updateSubloopParents();
672 
673  // Remove unloop from its parent loop.
674  Loop *ParentLoop = Unloop->getParentLoop();
675  for (Loop::iterator I = ParentLoop->begin();; ++I) {
676  assert(I != ParentLoop->end() && "Couldn't find loop");
677  if (*I == Unloop) {
678  ParentLoop->removeChildLoop(I);
679  break;
680  }
681  }
682 }
683 
684 AnalysisKey LoopAnalysis::Key;
685 
687  // FIXME: Currently we create a LoopInfo from scratch for every function.
688  // This may prove to be too wasteful due to deallocating and re-allocating
689  // memory each time for the underlying map and vector datastructures. At some
690  // point it may prove worthwhile to use a freelist and recycle LoopInfo
691  // objects. I don't want to add that kind of complexity until the scope of
692  // the problem is better understood.
693  LoopInfo LI;
695  return LI;
696 }
697 
700  AM.getResult<LoopAnalysis>(F).print(OS);
701  return PreservedAnalyses::all();
702 }
703 
704 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
705  OS << Banner;
706  for (auto *Block : L.blocks())
707  if (Block)
708  Block->print(OS);
709  else
710  OS << "Printing <null> block";
711 }
712 
713 //===----------------------------------------------------------------------===//
714 // LoopInfo implementation
715 //
716 
717 char LoopInfoWrapperPass::ID = 0;
718 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
719  true, true)
722  true, true)
723 
724 bool LoopInfoWrapperPass::runOnFunction(Function &) {
725  releaseMemory();
726  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
727  return false;
728 }
729 
731  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
732  // function each time verifyAnalysis is called is very expensive. The
733  // -verify-loop-info option can enable this. In order to perform some
734  // checking by default, LoopPass has been taught to call verifyLoop manually
735  // during loop pass sequences.
736  if (VerifyLoopInfo) {
737  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
738  LI.verify(DT);
739  }
740 }
741 
743  AU.setPreservesAll();
745 }
746 
748  LI.print(OS);
749 }
750 
753  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
754  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
755  LI.verify(DT);
756  return PreservedAnalyses::all();
757 }
758 
759 //===----------------------------------------------------------------------===//
760 // LoopBlocksDFS implementation
761 //
762 
763 /// Traverse the loop blocks and store the DFS result.
764 /// Useful for clients that just want the final DFS result and don't need to
765 /// visit blocks during the initial traversal.
767  LoopBlocksTraversal Traversal(*this, LI);
768  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
769  POE = Traversal.end(); POI != POE; ++POI) ;
770 }
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:709
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:686
BasicBlock * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:149
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:698
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
bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:181
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:174
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:279
This file contains the declarations for metadata subclasses.
BasicBlock * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:101
BasicBlock * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfo.cpp:402
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:65
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:818
A debug info location.
Definition: DebugLoc.h:34
Metadata node.
Definition: Metadata.h:862
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:232
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:285
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:61
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:608
void print(raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:310
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
std::vector< BasicBlock *>::const_iterator block_iterator
Definition: LoopInfo.h:141
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:585
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
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
std::vector< Loop *>::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:557
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:820
void print(raw_ostream &O, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: LoopInfo.cpp:747
BasicBlock * getHeader() const
Definition: LoopInfo.h:103
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:106
void getExitBlocks(SmallVectorImpl< BasicBlock * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
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:130
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LoopInfo.cpp:742
bool isInvalid()
Return true if this loop is no longer valid.
Definition: LoopInfo.h:157
#define F(x, y, z)
Definition: MD5.cpp:55
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:248
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:190
static cl::opt< bool, true > VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), cl::desc("Verify loop info (time consuming)"))
Debug location.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:766
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:134
void getUniqueExitBlocks(SmallVectorImpl< BasicBlock *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfo.cpp:361
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:109
Natural Loop true
Definition: LoopInfo.cpp:721
Core dominator tree base class.
Definition: LoopInfo.h:60
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
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:415
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:466
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:116
Represent the analysis usage information of a pass.
void invalidate()
Invalidate the loop, indicating that it is no longer a loop.
Definition: LoopInfo.h:154
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:119
op_range operands()
Definition: User.h:222
void markAsRemoved(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:625
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:310
A range representing the start and end location of a loop.
Definition: LoopInfo.h:363
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:55
unsigned first
bool contains(const Loop *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
Iterator for intrusive lists based on ilist_node.
#define E
Definition: LargeTest.cpp:27
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:721
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:110
bool VerifyLoopInfo
Enables verification of loop info.
Definition: LoopInfo.cpp:45
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:110
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:616
LoopT * getParentLoop() const
Definition: LoopInfo.h:104
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:190
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:212
const DebugLoc & getStart() const
Definition: LoopInfo.h:373
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:360
#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:143
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:197
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
bool empty() const
Definition: LoopInfo.h:137
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:269
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:751
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:503
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:845
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:261
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:144
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:704
block_iterator block_begin() const
Definition: LoopInfo.h:142
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:420
loops
Definition: LoopInfo.cpp:721
const BasicBlock * getParent() const
Definition: Instruction.h:66
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, DominatorTree &DT)
Definition: LoopInfo.cpp:147
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: LoopInfo.cpp:730
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:872