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