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