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