LLVM  9.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  Instruction *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 || LoopID->getNumOperands() > 0) &&
241  "Loop ID needs at least one operand");
242  assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
243  "Loop ID should refer to itself");
244 
245  BasicBlock *H = getHeader();
246  for (BasicBlock *BB : this->blocks()) {
247  Instruction *TI = BB->getTerminator();
248  for (BasicBlock *Successor : successors(TI)) {
249  if (Successor == H) {
250  TI->setMetadata(LLVMContext::MD_loop, LoopID);
251  break;
252  }
253  }
254  }
255 }
256 
258  MDNode *LoopID = getLoopID();
259  // First remove any existing loop unrolling metadata.
261  // Reserve first location for self reference to the LoopID metadata node.
262  MDs.push_back(nullptr);
263 
264  if (LoopID) {
265  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
266  bool IsUnrollMetadata = false;
267  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
268  if (MD) {
269  const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
270  IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
271  }
272  if (!IsUnrollMetadata)
273  MDs.push_back(LoopID->getOperand(i));
274  }
275  }
276 
277  // Add unroll(disable) metadata to disable future unrolling.
279  SmallVector<Metadata *, 1> DisableOperands;
280  DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
281  MDNode *DisableNode = MDNode::get(Context, DisableOperands);
282  MDs.push_back(DisableNode);
283 
284  MDNode *NewLoopID = MDNode::get(Context, MDs);
285  // Set operand 0 to refer to the loop id itself.
286  NewLoopID->replaceOperandWith(0, NewLoopID);
287  setLoopID(NewLoopID);
288 }
289 
291  MDNode *DesiredLoopIdMetadata = getLoopID();
292 
293  if (!DesiredLoopIdMetadata)
294  return false;
295 
296  MDNode *ParallelAccesses =
297  findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
299  ParallelAccessGroups; // For scalable 'contains' check.
300  if (ParallelAccesses) {
301  for (const MDOperand &MD : drop_begin(ParallelAccesses->operands(), 1)) {
302  MDNode *AccGroup = cast<MDNode>(MD.get());
303  assert(isValidAsAccessGroup(AccGroup) &&
304  "List item must be an access group");
305  ParallelAccessGroups.insert(AccGroup);
306  }
307  }
308 
309  // The loop branch contains the parallel loop metadata. In order to ensure
310  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
311  // dependencies (thus converted the loop back to a sequential loop), check
312  // that all the memory instructions in the loop belong to an access group that
313  // is parallel to this loop.
314  for (BasicBlock *BB : this->blocks()) {
315  for (Instruction &I : *BB) {
316  if (!I.mayReadOrWriteMemory())
317  continue;
318 
319  if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
320  auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
321  if (AG->getNumOperands() == 0) {
322  assert(isValidAsAccessGroup(AG) && "Item must be an access group");
323  return ParallelAccessGroups.count(AG);
324  }
325 
326  for (const MDOperand &AccessListItem : AG->operands()) {
327  MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
328  assert(isValidAsAccessGroup(AccGroup) &&
329  "List item must be an access group");
330  if (ParallelAccessGroups.count(AccGroup))
331  return true;
332  }
333  return false;
334  };
335 
336  if (ContainsAccessGroup(AccessGroup))
337  continue;
338  }
339 
340  // The memory instruction can refer to the loop identifier metadata
341  // directly or indirectly through another list metadata (in case of
342  // nested parallel loops). The loop identifier metadata refers to
343  // itself so we can check both cases with the same routine.
344  MDNode *LoopIdMD =
346 
347  if (!LoopIdMD)
348  return false;
349 
350  bool LoopIdMDFound = false;
351  for (const MDOperand &MDOp : LoopIdMD->operands()) {
352  if (MDOp == DesiredLoopIdMetadata) {
353  LoopIdMDFound = true;
354  break;
355  }
356  }
357 
358  if (!LoopIdMDFound)
359  return false;
360  }
361  }
362  return true;
363 }
364 
366 
368  // If we have a debug location in the loop ID, then use it.
369  if (MDNode *LoopID = getLoopID()) {
370  DebugLoc Start;
371  // We use the first DebugLoc in the header as the start location of the loop
372  // and if there is a second DebugLoc in the header we use it as end location
373  // of the loop.
374  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
375  if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
376  if (!Start)
377  Start = DebugLoc(L);
378  else
379  return LocRange(Start, DebugLoc(L));
380  }
381  }
382 
383  if (Start)
384  return LocRange(Start);
385  }
386 
387  // Try the pre-header first.
388  if (BasicBlock *PHeadBB = getLoopPreheader())
389  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
390  return LocRange(DL);
391 
392  // If we have no pre-header or there are no instructions with debug
393  // info in it, try the header.
394  if (BasicBlock *HeadBB = getHeader())
395  return LocRange(HeadBB->getTerminator()->getDebugLoc());
396 
397  return LocRange();
398 }
399 
400 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
401 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
402 
404  print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
405 }
406 #endif
407 
408 //===----------------------------------------------------------------------===//
409 // UnloopUpdater implementation
410 //
411 
412 namespace {
413 /// Find the new parent loop for all blocks within the "unloop" whose last
414 /// backedges has just been removed.
415 class UnloopUpdater {
416  Loop &Unloop;
417  LoopInfo *LI;
418 
420 
421  // Map unloop's immediate subloops to their nearest reachable parents. Nested
422  // loops within these subloops will not change parents. However, an immediate
423  // subloop's new parent will be the nearest loop reachable from either its own
424  // exits *or* any of its nested loop's exits.
425  DenseMap<Loop *, Loop *> SubloopParents;
426 
427  // Flag the presence of an irreducible backedge whose destination is a block
428  // directly contained by the original unloop.
429  bool FoundIB;
430 
431 public:
432  UnloopUpdater(Loop *UL, LoopInfo *LInfo)
433  : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
434 
435  void updateBlockParents();
436 
437  void removeBlocksFromAncestors();
438 
439  void updateSubloopParents();
440 
441 protected:
442  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
443 };
444 } // end anonymous namespace
445 
446 /// Update the parent loop for all blocks that are directly contained within the
447 /// original "unloop".
448 void UnloopUpdater::updateBlockParents() {
449  if (Unloop.getNumBlocks()) {
450  // Perform a post order CFG traversal of all blocks within this loop,
451  // propagating the nearest loop from successors to predecessors.
452  LoopBlocksTraversal Traversal(DFS, LI);
453  for (BasicBlock *POI : Traversal) {
454 
455  Loop *L = LI->getLoopFor(POI);
456  Loop *NL = getNearestLoop(POI, L);
457 
458  if (NL != L) {
459  // For reducible loops, NL is now an ancestor of Unloop.
460  assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
461  "uninitialized successor");
462  LI->changeLoopFor(POI, NL);
463  } else {
464  // Or the current block is part of a subloop, in which case its parent
465  // is unchanged.
466  assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
467  }
468  }
469  }
470  // Each irreducible loop within the unloop induces a round of iteration using
471  // the DFS result cached by Traversal.
472  bool Changed = FoundIB;
473  for (unsigned NIters = 0; Changed; ++NIters) {
474  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
475 
476  // Iterate over the postorder list of blocks, propagating the nearest loop
477  // from successors to predecessors as before.
478  Changed = false;
479  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
480  POE = DFS.endPostorder();
481  POI != POE; ++POI) {
482 
483  Loop *L = LI->getLoopFor(*POI);
484  Loop *NL = getNearestLoop(*POI, L);
485  if (NL != L) {
486  assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
487  "uninitialized successor");
488  LI->changeLoopFor(*POI, NL);
489  Changed = true;
490  }
491  }
492  }
493 }
494 
495 /// Remove unloop's blocks from all ancestors below their new parents.
496 void UnloopUpdater::removeBlocksFromAncestors() {
497  // Remove all unloop's blocks (including those in nested subloops) from
498  // ancestors below the new parent loop.
499  for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
500  BI != BE; ++BI) {
501  Loop *OuterParent = LI->getLoopFor(*BI);
502  if (Unloop.contains(OuterParent)) {
503  while (OuterParent->getParentLoop() != &Unloop)
504  OuterParent = OuterParent->getParentLoop();
505  OuterParent = SubloopParents[OuterParent];
506  }
507  // Remove blocks from former Ancestors except Unloop itself which will be
508  // deleted.
509  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
510  OldParent = OldParent->getParentLoop()) {
511  assert(OldParent && "new loop is not an ancestor of the original");
512  OldParent->removeBlockFromLoop(*BI);
513  }
514  }
515 }
516 
517 /// Update the parent loop for all subloops directly nested within unloop.
518 void UnloopUpdater::updateSubloopParents() {
519  while (!Unloop.empty()) {
520  Loop *Subloop = *std::prev(Unloop.end());
521  Unloop.removeChildLoop(std::prev(Unloop.end()));
522 
523  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
524  if (Loop *Parent = SubloopParents[Subloop])
525  Parent->addChildLoop(Subloop);
526  else
527  LI->addTopLevelLoop(Subloop);
528  }
529 }
530 
531 /// Return the nearest parent loop among this block's successors. If a successor
532 /// is a subloop header, consider its parent to be the nearest parent of the
533 /// subloop's exits.
534 ///
535 /// For subloop blocks, simply update SubloopParents and return NULL.
536 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
537 
538  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
539  // is considered uninitialized.
540  Loop *NearLoop = BBLoop;
541 
542  Loop *Subloop = nullptr;
543  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
544  Subloop = NearLoop;
545  // Find the subloop ancestor that is directly contained within Unloop.
546  while (Subloop->getParentLoop() != &Unloop) {
547  Subloop = Subloop->getParentLoop();
548  assert(Subloop && "subloop is not an ancestor of the original loop");
549  }
550  // Get the current nearest parent of the Subloop exits, initially Unloop.
551  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
552  }
553 
554  succ_iterator I = succ_begin(BB), E = succ_end(BB);
555  if (I == E) {
556  assert(!Subloop && "subloop blocks must have a successor");
557  NearLoop = nullptr; // unloop blocks may now exit the function.
558  }
559  for (; I != E; ++I) {
560  if (*I == BB)
561  continue; // self loops are uninteresting
562 
563  Loop *L = LI->getLoopFor(*I);
564  if (L == &Unloop) {
565  // This successor has not been processed. This path must lead to an
566  // irreducible backedge.
567  assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
568  FoundIB = true;
569  }
570  if (L != &Unloop && Unloop.contains(L)) {
571  // Successor is in a subloop.
572  if (Subloop)
573  continue; // Branching within subloops. Ignore it.
574 
575  // BB branches from the original into a subloop header.
576  assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
577 
578  // Get the current nearest parent of the Subloop's exits.
579  L = SubloopParents[L];
580  // L could be Unloop if the only exit was an irreducible backedge.
581  }
582  if (L == &Unloop) {
583  continue;
584  }
585  // Handle critical edges from Unloop into a sibling loop.
586  if (L && !L->contains(&Unloop)) {
587  L = L->getParentLoop();
588  }
589  // Remember the nearest parent loop among successors or subloop exits.
590  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
591  NearLoop = L;
592  }
593  if (Subloop) {
594  SubloopParents[Subloop] = NearLoop;
595  return BBLoop;
596  }
597  return NearLoop;
598 }
599 
600 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
601 
604  // Check whether the analysis, all analyses on functions, or the function's
605  // CFG have been preserved.
606  auto PAC = PA.getChecker<LoopAnalysis>();
607  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
608  PAC.preservedSet<CFGAnalyses>());
609 }
610 
611 void LoopInfo::erase(Loop *Unloop) {
612  assert(!Unloop->isInvalid() && "Loop has already been erased!");
613 
614  auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
615 
616  // First handle the special case of no parent loop to simplify the algorithm.
617  if (!Unloop->getParentLoop()) {
618  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
619  for (Loop::block_iterator I = Unloop->block_begin(),
620  E = Unloop->block_end();
621  I != E; ++I) {
622 
623  // Don't reparent blocks in subloops.
624  if (getLoopFor(*I) != Unloop)
625  continue;
626 
627  // Blocks no longer have a parent but are still referenced by Unloop until
628  // the Unloop object is deleted.
629  changeLoopFor(*I, nullptr);
630  }
631 
632  // Remove the loop from the top-level LoopInfo object.
633  for (iterator I = begin();; ++I) {
634  assert(I != end() && "Couldn't find loop");
635  if (*I == Unloop) {
636  removeLoop(I);
637  break;
638  }
639  }
640 
641  // Move all of the subloops to the top-level.
642  while (!Unloop->empty())
643  addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
644 
645  return;
646  }
647 
648  // Update the parent loop for all blocks within the loop. Blocks within
649  // subloops will not change parents.
650  UnloopUpdater Updater(Unloop, this);
651  Updater.updateBlockParents();
652 
653  // Remove blocks from former ancestor loops.
654  Updater.removeBlocksFromAncestors();
655 
656  // Add direct subloops as children in their new parent loop.
657  Updater.updateSubloopParents();
658 
659  // Remove unloop from its parent loop.
660  Loop *ParentLoop = Unloop->getParentLoop();
661  for (Loop::iterator I = ParentLoop->begin();; ++I) {
662  assert(I != ParentLoop->end() && "Couldn't find loop");
663  if (*I == Unloop) {
664  ParentLoop->removeChildLoop(I);
665  break;
666  }
667  }
668 }
669 
670 AnalysisKey LoopAnalysis::Key;
671 
673  // FIXME: Currently we create a LoopInfo from scratch for every function.
674  // This may prove to be too wasteful due to deallocating and re-allocating
675  // memory each time for the underlying map and vector datastructures. At some
676  // point it may prove worthwhile to use a freelist and recycle LoopInfo
677  // objects. I don't want to add that kind of complexity until the scope of
678  // the problem is better understood.
679  LoopInfo LI;
681  return LI;
682 }
683 
686  AM.getResult<LoopAnalysis>(F).print(OS);
687  return PreservedAnalyses::all();
688 }
689 
690 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
691 
692  if (forcePrintModuleIR()) {
693  // handling -print-module-scope
694  OS << Banner << " (loop: ";
695  L.getHeader()->printAsOperand(OS, false);
696  OS << ")\n";
697 
698  // printing whole module
699  OS << *L.getHeader()->getModule();
700  return;
701  }
702 
703  OS << Banner;
704 
705  auto *PreHeader = L.getLoopPreheader();
706  if (PreHeader) {
707  OS << "\n; Preheader:";
708  PreHeader->print(OS);
709  OS << "\n; Loop:";
710  }
711 
712  for (auto *Block : L.blocks())
713  if (Block)
714  Block->print(OS);
715  else
716  OS << "Printing <null> block";
717 
718  SmallVector<BasicBlock *, 8> ExitBlocks;
719  L.getExitBlocks(ExitBlocks);
720  if (!ExitBlocks.empty()) {
721  OS << "\n; Exit blocks";
722  for (auto *Block : ExitBlocks)
723  if (Block)
724  Block->print(OS);
725  else
726  OS << "Printing <null> block";
727  }
728 }
729 
731  // No loop metadata node, no loop properties.
732  if (!LoopID)
733  return nullptr;
734 
735  // First operand should refer to the metadata node itself, for legacy reasons.
736  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
737  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
738 
739  // Iterate over the metdata node operands and look for MDString metadata.
740  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
741  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
742  if (!MD || MD->getNumOperands() < 1)
743  continue;
744  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
745  if (!S)
746  continue;
747  // Return the operand node if MDString holds expected metadata.
748  if (Name.equals(S->getString()))
749  return MD;
750  }
751 
752  // Loop property not found.
753  return nullptr;
754 }
755 
757  return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
758 }
759 
761  return Node->getNumOperands() == 0 && Node->isDistinct();
762 }
763 
764 //===----------------------------------------------------------------------===//
765 // LoopInfo implementation
766 //
767 
768 char LoopInfoWrapperPass::ID = 0;
769 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
770  true, true)
773  true, true)
774 
775 bool LoopInfoWrapperPass::runOnFunction(Function &) {
776  releaseMemory();
777  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
778  return false;
779 }
780 
782  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
783  // function each time verifyAnalysis is called is very expensive. The
784  // -verify-loop-info option can enable this. In order to perform some
785  // checking by default, LoopPass has been taught to call verifyLoop manually
786  // during loop pass sequences.
787  if (VerifyLoopInfo) {
788  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
789  LI.verify(DT);
790  }
791 }
792 
794  AU.setPreservesAll();
796 }
797 
799  LI.print(OS);
800 }
801 
804  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
805  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
806  LI.verify(DT);
807  return PreservedAnalyses::all();
808 }
809 
810 //===----------------------------------------------------------------------===//
811 // LoopBlocksDFS implementation
812 //
813 
814 /// Traverse the loop blocks and store the DFS result.
815 /// Useful for clients that just want the final DFS result and don't need to
816 /// visit blocks during the initial traversal.
818  LoopBlocksTraversal Traversal(*this, LI);
819  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
820  POE = Traversal.end();
821  POI != POE; ++POI)
822  ;
823 }
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:711
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:672
bool forcePrintModuleIR()
forcePrintModuleIR - returns true if IR printing passes should
bool isDistinct() const
Definition: Metadata.h:943
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:684
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
This class represents lattice values for constants.
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:465
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
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:1186
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
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
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:704
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:269
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
amdgpu Simplify well known AMD library false Value Value const Twine & Name
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:690
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:662
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:611
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:945
void print(raw_ostream &O, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: LoopInfo.cpp:798
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:793
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 * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
Definition: LoopInfo.cpp:756
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:221
Debug location.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:817
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:772
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
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
void dump() const
Definition: LoopInfo.cpp:401
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:257
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
void dumpVerbose() const
Definition: LoopInfo.cpp:403
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:554
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
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
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:365
iterator_range< decltype(adl_begin(std::declval< T >)))> drop_begin(T &&t, int n)
A range representing the start and end location of a loop.
Definition: LoopInfo.h:468
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:4225
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.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
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
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Definition: LoopInfo.cpp:730
Natural Loop Information
Definition: LoopInfo.cpp:772
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:367
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
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:169
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: LoopInfo.cpp:602
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:478
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:465
#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:290
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:264
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:802
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:573
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:970
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
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
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:690
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:439
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
Definition: LoopInfo.cpp:760
loops
Definition: LoopInfo.cpp:772
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:781