LLVM  9.0.0svn
LoopInfo.cpp
Go to the documentation of this file.
1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the LoopInfo class that is used to identify natural loops
10 // and determine the loop depth of various nodes of the CFG. Note that the
11 // loops identified may actually be several natural loops that share the same
12 // header node... not just a single natural loop.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/ADT/ScopeExit.h"
19 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/Config/llvm-config.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DebugLoc.h"
27 #include "llvm/IR/Dominators.h"
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 
217  // Go through the latch blocks and check the terminator for the metadata.
218  SmallVector<BasicBlock *, 4> LatchesBlocks;
219  getLoopLatches(LatchesBlocks);
220  for (BasicBlock *BB : LatchesBlocks) {
221  Instruction *TI = BB->getTerminator();
223 
224  if (!MD)
225  return nullptr;
226 
227  if (!LoopID)
228  LoopID = MD;
229  else if (MD != LoopID)
230  return nullptr;
231  }
232  if (!LoopID || LoopID->getNumOperands() == 0 ||
233  LoopID->getOperand(0) != LoopID)
234  return nullptr;
235  return LoopID;
236 }
237 
238 void Loop::setLoopID(MDNode *LoopID) const {
239  assert((!LoopID || LoopID->getNumOperands() > 0) &&
240  "Loop ID needs at least one operand");
241  assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
242  "Loop ID should refer to itself");
243 
244  BasicBlock *H = getHeader();
245  for (BasicBlock *BB : this->blocks()) {
246  Instruction *TI = BB->getTerminator();
247  for (BasicBlock *Successor : successors(TI)) {
248  if (Successor == H) {
249  TI->setMetadata(LLVMContext::MD_loop, LoopID);
250  break;
251  }
252  }
253  }
254 }
255 
257  MDNode *LoopID = getLoopID();
258  // First remove any existing loop unrolling metadata.
260  // Reserve first location for self reference to the LoopID metadata node.
261  MDs.push_back(nullptr);
262 
263  if (LoopID) {
264  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
265  bool IsUnrollMetadata = false;
266  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
267  if (MD) {
268  const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
269  IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
270  }
271  if (!IsUnrollMetadata)
272  MDs.push_back(LoopID->getOperand(i));
273  }
274  }
275 
276  // Add unroll(disable) metadata to disable future unrolling.
278  SmallVector<Metadata *, 1> DisableOperands;
279  DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
280  MDNode *DisableNode = MDNode::get(Context, DisableOperands);
281  MDs.push_back(DisableNode);
282 
283  MDNode *NewLoopID = MDNode::get(Context, MDs);
284  // Set operand 0 to refer to the loop id itself.
285  NewLoopID->replaceOperandWith(0, NewLoopID);
286  setLoopID(NewLoopID);
287 }
288 
290  MDNode *DesiredLoopIdMetadata = getLoopID();
291 
292  if (!DesiredLoopIdMetadata)
293  return false;
294 
295  MDNode *ParallelAccesses =
296  findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
298  ParallelAccessGroups; // For scalable 'contains' check.
299  if (ParallelAccesses) {
300  for (const MDOperand &MD : drop_begin(ParallelAccesses->operands(), 1)) {
301  MDNode *AccGroup = cast<MDNode>(MD.get());
302  assert(isValidAsAccessGroup(AccGroup) &&
303  "List item must be an access group");
304  ParallelAccessGroups.insert(AccGroup);
305  }
306  }
307 
308  // The loop branch contains the parallel loop metadata. In order to ensure
309  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
310  // dependencies (thus converted the loop back to a sequential loop), check
311  // that all the memory instructions in the loop belong to an access group that
312  // is parallel to this loop.
313  for (BasicBlock *BB : this->blocks()) {
314  for (Instruction &I : *BB) {
315  if (!I.mayReadOrWriteMemory())
316  continue;
317 
318  if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
319  auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
320  if (AG->getNumOperands() == 0) {
321  assert(isValidAsAccessGroup(AG) && "Item must be an access group");
322  return ParallelAccessGroups.count(AG);
323  }
324 
325  for (const MDOperand &AccessListItem : AG->operands()) {
326  MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
327  assert(isValidAsAccessGroup(AccGroup) &&
328  "List item must be an access group");
329  if (ParallelAccessGroups.count(AccGroup))
330  return true;
331  }
332  return false;
333  };
334 
335  if (ContainsAccessGroup(AccessGroup))
336  continue;
337  }
338 
339  // The memory instruction can refer to the loop identifier metadata
340  // directly or indirectly through another list metadata (in case of
341  // nested parallel loops). The loop identifier metadata refers to
342  // itself so we can check both cases with the same routine.
343  MDNode *LoopIdMD =
345 
346  if (!LoopIdMD)
347  return false;
348 
349  bool LoopIdMDFound = false;
350  for (const MDOperand &MDOp : LoopIdMD->operands()) {
351  if (MDOp == DesiredLoopIdMetadata) {
352  LoopIdMDFound = true;
353  break;
354  }
355  }
356 
357  if (!LoopIdMDFound)
358  return false;
359  }
360  }
361  return true;
362 }
363 
365 
367  // If we have a debug location in the loop ID, then use it.
368  if (MDNode *LoopID = getLoopID()) {
369  DebugLoc Start;
370  // We use the first DebugLoc in the header as the start location of the loop
371  // and if there is a second DebugLoc in the header we use it as end location
372  // of the loop.
373  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
374  if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
375  if (!Start)
376  Start = DebugLoc(L);
377  else
378  return LocRange(Start, DebugLoc(L));
379  }
380  }
381 
382  if (Start)
383  return LocRange(Start);
384  }
385 
386  // Try the pre-header first.
387  if (BasicBlock *PHeadBB = getLoopPreheader())
388  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
389  return LocRange(DL);
390 
391  // If we have no pre-header or there are no instructions with debug
392  // info in it, try the header.
393  if (BasicBlock *HeadBB = getHeader())
394  return LocRange(HeadBB->getTerminator()->getDebugLoc());
395 
396  return LocRange();
397 }
398 
399 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
400 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
401 
403  print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
404 }
405 #endif
406 
407 //===----------------------------------------------------------------------===//
408 // UnloopUpdater implementation
409 //
410 
411 namespace {
412 /// Find the new parent loop for all blocks within the "unloop" whose last
413 /// backedges has just been removed.
414 class UnloopUpdater {
415  Loop &Unloop;
416  LoopInfo *LI;
417 
419 
420  // Map unloop's immediate subloops to their nearest reachable parents. Nested
421  // loops within these subloops will not change parents. However, an immediate
422  // subloop's new parent will be the nearest loop reachable from either its own
423  // exits *or* any of its nested loop's exits.
424  DenseMap<Loop *, Loop *> SubloopParents;
425 
426  // Flag the presence of an irreducible backedge whose destination is a block
427  // directly contained by the original unloop.
428  bool FoundIB;
429 
430 public:
431  UnloopUpdater(Loop *UL, LoopInfo *LInfo)
432  : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
433 
434  void updateBlockParents();
435 
436  void removeBlocksFromAncestors();
437 
438  void updateSubloopParents();
439 
440 protected:
441  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
442 };
443 } // end anonymous namespace
444 
445 /// Update the parent loop for all blocks that are directly contained within the
446 /// original "unloop".
447 void UnloopUpdater::updateBlockParents() {
448  if (Unloop.getNumBlocks()) {
449  // Perform a post order CFG traversal of all blocks within this loop,
450  // propagating the nearest loop from successors to predecessors.
451  LoopBlocksTraversal Traversal(DFS, LI);
452  for (BasicBlock *POI : Traversal) {
453 
454  Loop *L = LI->getLoopFor(POI);
455  Loop *NL = getNearestLoop(POI, L);
456 
457  if (NL != L) {
458  // For reducible loops, NL is now an ancestor of Unloop.
459  assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
460  "uninitialized successor");
461  LI->changeLoopFor(POI, NL);
462  } else {
463  // Or the current block is part of a subloop, in which case its parent
464  // is unchanged.
465  assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
466  }
467  }
468  }
469  // Each irreducible loop within the unloop induces a round of iteration using
470  // the DFS result cached by Traversal.
471  bool Changed = FoundIB;
472  for (unsigned NIters = 0; Changed; ++NIters) {
473  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
474 
475  // Iterate over the postorder list of blocks, propagating the nearest loop
476  // from successors to predecessors as before.
477  Changed = false;
478  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
479  POE = DFS.endPostorder();
480  POI != POE; ++POI) {
481 
482  Loop *L = LI->getLoopFor(*POI);
483  Loop *NL = getNearestLoop(*POI, L);
484  if (NL != L) {
485  assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
486  "uninitialized successor");
487  LI->changeLoopFor(*POI, NL);
488  Changed = true;
489  }
490  }
491  }
492 }
493 
494 /// Remove unloop's blocks from all ancestors below their new parents.
495 void UnloopUpdater::removeBlocksFromAncestors() {
496  // Remove all unloop's blocks (including those in nested subloops) from
497  // ancestors below the new parent loop.
498  for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
499  BI != BE; ++BI) {
500  Loop *OuterParent = LI->getLoopFor(*BI);
501  if (Unloop.contains(OuterParent)) {
502  while (OuterParent->getParentLoop() != &Unloop)
503  OuterParent = OuterParent->getParentLoop();
504  OuterParent = SubloopParents[OuterParent];
505  }
506  // Remove blocks from former Ancestors except Unloop itself which will be
507  // deleted.
508  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
509  OldParent = OldParent->getParentLoop()) {
510  assert(OldParent && "new loop is not an ancestor of the original");
511  OldParent->removeBlockFromLoop(*BI);
512  }
513  }
514 }
515 
516 /// Update the parent loop for all subloops directly nested within unloop.
517 void UnloopUpdater::updateSubloopParents() {
518  while (!Unloop.empty()) {
519  Loop *Subloop = *std::prev(Unloop.end());
520  Unloop.removeChildLoop(std::prev(Unloop.end()));
521 
522  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
523  if (Loop *Parent = SubloopParents[Subloop])
524  Parent->addChildLoop(Subloop);
525  else
526  LI->addTopLevelLoop(Subloop);
527  }
528 }
529 
530 /// Return the nearest parent loop among this block's successors. If a successor
531 /// is a subloop header, consider its parent to be the nearest parent of the
532 /// subloop's exits.
533 ///
534 /// For subloop blocks, simply update SubloopParents and return NULL.
535 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
536 
537  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
538  // is considered uninitialized.
539  Loop *NearLoop = BBLoop;
540 
541  Loop *Subloop = nullptr;
542  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
543  Subloop = NearLoop;
544  // Find the subloop ancestor that is directly contained within Unloop.
545  while (Subloop->getParentLoop() != &Unloop) {
546  Subloop = Subloop->getParentLoop();
547  assert(Subloop && "subloop is not an ancestor of the original loop");
548  }
549  // Get the current nearest parent of the Subloop exits, initially Unloop.
550  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
551  }
552 
553  succ_iterator I = succ_begin(BB), E = succ_end(BB);
554  if (I == E) {
555  assert(!Subloop && "subloop blocks must have a successor");
556  NearLoop = nullptr; // unloop blocks may now exit the function.
557  }
558  for (; I != E; ++I) {
559  if (*I == BB)
560  continue; // self loops are uninteresting
561 
562  Loop *L = LI->getLoopFor(*I);
563  if (L == &Unloop) {
564  // This successor has not been processed. This path must lead to an
565  // irreducible backedge.
566  assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
567  FoundIB = true;
568  }
569  if (L != &Unloop && Unloop.contains(L)) {
570  // Successor is in a subloop.
571  if (Subloop)
572  continue; // Branching within subloops. Ignore it.
573 
574  // BB branches from the original into a subloop header.
575  assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
576 
577  // Get the current nearest parent of the Subloop's exits.
578  L = SubloopParents[L];
579  // L could be Unloop if the only exit was an irreducible backedge.
580  }
581  if (L == &Unloop) {
582  continue;
583  }
584  // Handle critical edges from Unloop into a sibling loop.
585  if (L && !L->contains(&Unloop)) {
586  L = L->getParentLoop();
587  }
588  // Remember the nearest parent loop among successors or subloop exits.
589  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
590  NearLoop = L;
591  }
592  if (Subloop) {
593  SubloopParents[Subloop] = NearLoop;
594  return BBLoop;
595  }
596  return NearLoop;
597 }
598 
599 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
600 
603  // Check whether the analysis, all analyses on functions, or the function's
604  // CFG have been preserved.
605  auto PAC = PA.getChecker<LoopAnalysis>();
606  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
607  PAC.preservedSet<CFGAnalyses>());
608 }
609 
610 void LoopInfo::erase(Loop *Unloop) {
611  assert(!Unloop->isInvalid() && "Loop has already been erased!");
612 
613  auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
614 
615  // First handle the special case of no parent loop to simplify the algorithm.
616  if (!Unloop->getParentLoop()) {
617  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
618  for (Loop::block_iterator I = Unloop->block_begin(),
619  E = Unloop->block_end();
620  I != E; ++I) {
621 
622  // Don't reparent blocks in subloops.
623  if (getLoopFor(*I) != Unloop)
624  continue;
625 
626  // Blocks no longer have a parent but are still referenced by Unloop until
627  // the Unloop object is deleted.
628  changeLoopFor(*I, nullptr);
629  }
630 
631  // Remove the loop from the top-level LoopInfo object.
632  for (iterator I = begin();; ++I) {
633  assert(I != end() && "Couldn't find loop");
634  if (*I == Unloop) {
635  removeLoop(I);
636  break;
637  }
638  }
639 
640  // Move all of the subloops to the top-level.
641  while (!Unloop->empty())
642  addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
643 
644  return;
645  }
646 
647  // Update the parent loop for all blocks within the loop. Blocks within
648  // subloops will not change parents.
649  UnloopUpdater Updater(Unloop, this);
650  Updater.updateBlockParents();
651 
652  // Remove blocks from former ancestor loops.
653  Updater.removeBlocksFromAncestors();
654 
655  // Add direct subloops as children in their new parent loop.
656  Updater.updateSubloopParents();
657 
658  // Remove unloop from its parent loop.
659  Loop *ParentLoop = Unloop->getParentLoop();
660  for (Loop::iterator I = ParentLoop->begin();; ++I) {
661  assert(I != ParentLoop->end() && "Couldn't find loop");
662  if (*I == Unloop) {
663  ParentLoop->removeChildLoop(I);
664  break;
665  }
666  }
667 }
668 
669 AnalysisKey LoopAnalysis::Key;
670 
672  // FIXME: Currently we create a LoopInfo from scratch for every function.
673  // This may prove to be too wasteful due to deallocating and re-allocating
674  // memory each time for the underlying map and vector datastructures. At some
675  // point it may prove worthwhile to use a freelist and recycle LoopInfo
676  // objects. I don't want to add that kind of complexity until the scope of
677  // the problem is better understood.
678  LoopInfo LI;
680  return LI;
681 }
682 
685  AM.getResult<LoopAnalysis>(F).print(OS);
686  return PreservedAnalyses::all();
687 }
688 
689 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
690 
691  if (forcePrintModuleIR()) {
692  // handling -print-module-scope
693  OS << Banner << " (loop: ";
694  L.getHeader()->printAsOperand(OS, false);
695  OS << ")\n";
696 
697  // printing whole module
698  OS << *L.getHeader()->getModule();
699  return;
700  }
701 
702  OS << Banner;
703 
704  auto *PreHeader = L.getLoopPreheader();
705  if (PreHeader) {
706  OS << "\n; Preheader:";
707  PreHeader->print(OS);
708  OS << "\n; Loop:";
709  }
710 
711  for (auto *Block : L.blocks())
712  if (Block)
713  Block->print(OS);
714  else
715  OS << "Printing <null> block";
716 
717  SmallVector<BasicBlock *, 8> ExitBlocks;
718  L.getExitBlocks(ExitBlocks);
719  if (!ExitBlocks.empty()) {
720  OS << "\n; Exit blocks";
721  for (auto *Block : ExitBlocks)
722  if (Block)
723  Block->print(OS);
724  else
725  OS << "Printing <null> block";
726  }
727 }
728 
730  // No loop metadata node, no loop properties.
731  if (!LoopID)
732  return nullptr;
733 
734  // First operand should refer to the metadata node itself, for legacy reasons.
735  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
736  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
737 
738  // Iterate over the metdata node operands and look for MDString metadata.
739  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
740  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
741  if (!MD || MD->getNumOperands() < 1)
742  continue;
743  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
744  if (!S)
745  continue;
746  // Return the operand node if MDString holds expected metadata.
747  if (Name.equals(S->getString()))
748  return MD;
749  }
750 
751  // Loop property not found.
752  return nullptr;
753 }
754 
756  return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
757 }
758 
760  return Node->getNumOperands() == 0 && Node->isDistinct();
761 }
762 
763 //===----------------------------------------------------------------------===//
764 // LoopInfo implementation
765 //
766 
767 char LoopInfoWrapperPass::ID = 0;
768 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
769  true, true)
772  true, true)
773 
774 bool LoopInfoWrapperPass::runOnFunction(Function &) {
775  releaseMemory();
776  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
777  return false;
778 }
779 
781  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
782  // function each time verifyAnalysis is called is very expensive. The
783  // -verify-loop-info option can enable this. In order to perform some
784  // checking by default, LoopPass has been taught to call verifyLoop manually
785  // during loop pass sequences.
786  if (VerifyLoopInfo) {
787  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
788  LI.verify(DT);
789  }
790 }
791 
793  AU.setPreservesAll();
795 }
796 
798  LI.print(OS);
799 }
800 
803  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
804  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
805  LI.verify(DT);
806  return PreservedAnalyses::all();
807 }
808 
809 //===----------------------------------------------------------------------===//
810 // LoopBlocksDFS implementation
811 //
812 
813 /// Traverse the loop blocks and store the DFS result.
814 /// Useful for clients that just want the final DFS result and don't need to
815 /// visit blocks during the initial traversal.
817  LoopBlocksTraversal Traversal(*this, LI);
818  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
819  POE = Traversal.end();
820  POI != POE; ++POI)
821  ;
822 }
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:710
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:671
bool forcePrintModuleIR()
forcePrintModuleIR - returns true if IR printing passes should
bool isDistinct() const
Definition: Metadata.h:942
BasicBlock * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:224
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:683
LLVMContext & Context
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:464
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:1198
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:858
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:453
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:85
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:339
This file contains the declarations for metadata subclasses.
BasicBlock * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:173
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:58
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:1185
A debug info location.
Definition: DebugLoc.h:33
Metadata node.
Definition: Metadata.h:863
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
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:137
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:299
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:192
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:703
void print(raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:392
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
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:133
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Traverse the blocks in a loop using a depth-first search.
Definition: LoopIterator.h:200
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:689
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
POTIterator begin()
Postorder traversal over the graph.
Definition: LoopIterator.h:216
std::vector< Loop *>::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:661
void getLoopLatches(SmallVectorImpl< BasicBlock * > &LoopLatches) const
Return all loop latch blocks of this loop.
Definition: LoopInfo.h:303
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:610
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:944
void print(raw_ostream &O, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: LoopInfo.cpp:797
BasicBlock * getHeader() const
Definition: LoopInfo.h:99
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:102
void getExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
std::vector< Loop *>::const_iterator iterator
Definition: LoopInfo.h:138
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:266
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LoopInfo.cpp:792
op_range operands() const
Definition: Metadata.h:1066
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:238
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
Definition: LoopInfo.cpp:755
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:220
Debug location.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:816
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
Natural Loop true
Definition: LoopInfo.cpp:771
StringRef getString() const
Definition: Metadata.cpp:463
Core dominator tree base class.
Definition: LoopInfo.h:60
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1165
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:153
void dump() const
Definition: LoopInfo.cpp:400
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
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:256
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:370
void dumpVerbose() const
Definition: LoopInfo.cpp:402
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:553
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:112
Represent the analysis usage information of a pass.
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
op_range operands()
Definition: User.h:237
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
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:364
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:467
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:4224
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:1225
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:109
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:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:845
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Definition: LoopInfo.cpp:729
Natural Loop Information
Definition: LoopInfo.cpp:771
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:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
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:97
LocRange getLocRange() const
Return the source code span of the loop.
Definition: LoopInfo.cpp:366
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
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:168
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: LoopInfo.cpp:601
LoopT * getParentLoop() const
Definition: LoopInfo.h:100
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: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:477
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:464
#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:100
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:322
block_iterator block_end() const
Definition: LoopInfo.h:154
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:641
This file defines passes to print out IR in various granularities.
bool empty() const
Definition: LoopInfo.h:145
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:289
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:72
succ_range successors(Instruction *I)
Definition: CFG.h:259
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:801
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:86
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:572
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:969
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
A single uniqued string.
Definition: Metadata.h:603
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
This header defines various interfaces for pass management in LLVM.
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:155
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:689
block_iterator block_begin() const
Definition: LoopInfo.h:153
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:438
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
Definition: LoopInfo.cpp:759
loops
Definition: LoopInfo.cpp:771
const BasicBlock * getParent() const
Definition: Instruction.h:66
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:780