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"
25 #include "llvm/Config/llvm-config.h"
26 #include "llvm/IR/CFG.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DebugLoc.h"
29 #include "llvm/IR/Dominators.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/LLVMContext.h"
33 #include "llvm/IR/Metadata.h"
34 #include "llvm/IR/PassManager.h"
36 #include "llvm/Support/Debug.h"
38 #include <algorithm>
39 using namespace llvm;
40 
41 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
44 
45 // Always verify loopinfo if expensive checking is enabled.
46 #ifdef EXPENSIVE_CHECKS
47 bool llvm::VerifyLoopInfo = true;
48 #else
49 bool llvm::VerifyLoopInfo = false;
50 #endif
52  VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
53  cl::Hidden, cl::desc("Verify loop info (time consuming)"));
54 
55 //===----------------------------------------------------------------------===//
56 // Loop implementation
57 //
58 
59 bool Loop::isLoopInvariant(const Value *V) const {
60  if (const Instruction *I = dyn_cast<Instruction>(V))
61  return !contains(I);
62  return true; // All non-instructions are loop invariant
63 }
64 
66  return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
67 }
68 
69 bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt,
70  MemorySSAUpdater *MSSAU) const {
71  if (Instruction *I = dyn_cast<Instruction>(V))
72  return makeLoopInvariant(I, Changed, InsertPt, MSSAU);
73  return true; // All non-instructions are loop-invariant.
74 }
75 
76 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
77  Instruction *InsertPt,
78  MemorySSAUpdater *MSSAU) const {
79  // Test if the value is already loop-invariant.
80  if (isLoopInvariant(I))
81  return true;
83  return false;
84  if (I->mayReadFromMemory())
85  return false;
86  // EH block instructions are immobile.
87  if (I->isEHPad())
88  return false;
89  // Determine the insertion point, unless one was given.
90  if (!InsertPt) {
91  BasicBlock *Preheader = getLoopPreheader();
92  // Without a preheader, hoisting is not feasible.
93  if (!Preheader)
94  return false;
95  InsertPt = Preheader->getTerminator();
96  }
97  // Don't hoist instructions with loop-variant operands.
98  for (Value *Operand : I->operands())
99  if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU))
100  return false;
101 
102  // Hoist.
103  I->moveBefore(InsertPt);
104  if (MSSAU)
105  if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I))
106  MSSAU->moveToPlace(MUD, InsertPt->getParent(), MemorySSA::End);
107 
108  // There is possibility of hoisting this instruction above some arbitrary
109  // condition. Any metadata defined on it can be control dependent on this
110  // condition. Conservatively strip it here so that we don't give any wrong
111  // information to the optimizer.
113 
114  Changed = true;
115  return true;
116 }
117 
119  BasicBlock *&Backedge) const {
120  BasicBlock *H = getHeader();
121 
122  Incoming = nullptr;
123  Backedge = nullptr;
124  pred_iterator PI = pred_begin(H);
125  assert(PI != pred_end(H) && "Loop must have at least one backedge!");
126  Backedge = *PI++;
127  if (PI == pred_end(H))
128  return false; // dead loop
129  Incoming = *PI++;
130  if (PI != pred_end(H))
131  return false; // multiple backedges?
132 
133  if (contains(Incoming)) {
134  if (contains(Backedge))
135  return false;
136  std::swap(Incoming, Backedge);
137  } else if (!contains(Backedge))
138  return false;
139 
140  assert(Incoming && Backedge && "expected non-null incoming and backedges");
141  return true;
142 }
143 
145  BasicBlock *H = getHeader();
146 
147  BasicBlock *Incoming = nullptr, *Backedge = nullptr;
148  if (!getIncomingAndBackEdge(Incoming, Backedge))
149  return nullptr;
150 
151  // Loop over all of the PHI nodes, looking for a canonical indvar.
152  for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
153  PHINode *PN = cast<PHINode>(I);
154  if (ConstantInt *CI =
155  dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
156  if (CI->isZero())
157  if (Instruction *Inc =
158  dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
159  if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
160  if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
161  if (CI->isOne())
162  return PN;
163  }
164  return nullptr;
165 }
166 
167 // Check that 'BB' doesn't have any uses outside of the 'L'
168 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
169  DominatorTree &DT) {
170  for (const Instruction &I : BB) {
171  // Tokens can't be used in PHI nodes and live-out tokens prevent loop
172  // optimizations, so for the purposes of considered LCSSA form, we
173  // can ignore them.
174  if (I.getType()->isTokenTy())
175  continue;
176 
177  for (const Use &U : I.uses()) {
178  const Instruction *UI = cast<Instruction>(U.getUser());
179  const BasicBlock *UserBB = UI->getParent();
180  if (const PHINode *P = dyn_cast<PHINode>(UI))
181  UserBB = P->getIncomingBlock(U);
182 
183  // Check the current block, as a fast-path, before checking whether
184  // the use is anywhere in the loop. Most values are used in the same
185  // block they are defined in. Also, blocks not reachable from the
186  // entry are special; uses in them don't need to go through PHIs.
187  if (UserBB != &BB && !L.contains(UserBB) &&
188  DT.isReachableFromEntry(UserBB))
189  return false;
190  }
191  }
192  return true;
193 }
194 
196  // For each block we check that it doesn't have any uses outside of this loop.
197  return all_of(this->blocks(), [&](const BasicBlock *BB) {
198  return isBlockInLCSSAForm(*this, *BB, DT);
199  });
200 }
201 
203  // For each block we check that it doesn't have any uses outside of its
204  // innermost loop. This process will transitively guarantee that the current
205  // loop and all of the nested loops are in LCSSA form.
206  return all_of(this->blocks(), [&](const BasicBlock *BB) {
207  return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
208  });
209 }
210 
212  // Normal-form loops have a preheader, a single backedge, and all of their
213  // exits have all their predecessors inside the loop.
215 }
216 
217 // Routines that reform the loop CFG and split edges often fail on indirectbr.
218 bool Loop::isSafeToClone() const {
219  // Return false if any loop blocks contain indirectbrs, or there are any calls
220  // to noduplicate functions.
221  for (BasicBlock *BB : this->blocks()) {
222  if (isa<IndirectBrInst>(BB->getTerminator()))
223  return false;
224 
225  for (Instruction &I : *BB)
226  if (auto CS = CallSite(&I))
227  if (CS.cannotDuplicate())
228  return false;
229  }
230  return true;
231 }
232 
234  MDNode *LoopID = nullptr;
235 
236  // Go through the latch blocks and check the terminator for the metadata.
237  SmallVector<BasicBlock *, 4> LatchesBlocks;
238  getLoopLatches(LatchesBlocks);
239  for (BasicBlock *BB : LatchesBlocks) {
240  Instruction *TI = BB->getTerminator();
242 
243  if (!MD)
244  return nullptr;
245 
246  if (!LoopID)
247  LoopID = MD;
248  else if (MD != LoopID)
249  return nullptr;
250  }
251  if (!LoopID || LoopID->getNumOperands() == 0 ||
252  LoopID->getOperand(0) != LoopID)
253  return nullptr;
254  return LoopID;
255 }
256 
257 void Loop::setLoopID(MDNode *LoopID) const {
258  assert((!LoopID || LoopID->getNumOperands() > 0) &&
259  "Loop ID needs at least one operand");
260  assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
261  "Loop ID should refer to itself");
262 
263  SmallVector<BasicBlock *, 4> LoopLatches;
264  getLoopLatches(LoopLatches);
265  for (BasicBlock *BB : LoopLatches)
266  BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
267 }
268 
271 
272  MDNode *DisableUnrollMD =
273  MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
274  MDNode *LoopID = getLoopID();
276  Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
277  setLoopID(NewLoopID);
278 }
279 
281  MDNode *DesiredLoopIdMetadata = getLoopID();
282 
283  if (!DesiredLoopIdMetadata)
284  return false;
285 
286  MDNode *ParallelAccesses =
287  findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
289  ParallelAccessGroups; // For scalable 'contains' check.
290  if (ParallelAccesses) {
291  for (const MDOperand &MD : drop_begin(ParallelAccesses->operands(), 1)) {
292  MDNode *AccGroup = cast<MDNode>(MD.get());
293  assert(isValidAsAccessGroup(AccGroup) &&
294  "List item must be an access group");
295  ParallelAccessGroups.insert(AccGroup);
296  }
297  }
298 
299  // The loop branch contains the parallel loop metadata. In order to ensure
300  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
301  // dependencies (thus converted the loop back to a sequential loop), check
302  // that all the memory instructions in the loop belong to an access group that
303  // is parallel to this loop.
304  for (BasicBlock *BB : this->blocks()) {
305  for (Instruction &I : *BB) {
306  if (!I.mayReadOrWriteMemory())
307  continue;
308 
309  if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
310  auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
311  if (AG->getNumOperands() == 0) {
312  assert(isValidAsAccessGroup(AG) && "Item must be an access group");
313  return ParallelAccessGroups.count(AG);
314  }
315 
316  for (const MDOperand &AccessListItem : AG->operands()) {
317  MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
318  assert(isValidAsAccessGroup(AccGroup) &&
319  "List item must be an access group");
320  if (ParallelAccessGroups.count(AccGroup))
321  return true;
322  }
323  return false;
324  };
325 
326  if (ContainsAccessGroup(AccessGroup))
327  continue;
328  }
329 
330  // The memory instruction can refer to the loop identifier metadata
331  // directly or indirectly through another list metadata (in case of
332  // nested parallel loops). The loop identifier metadata refers to
333  // itself so we can check both cases with the same routine.
334  MDNode *LoopIdMD =
336 
337  if (!LoopIdMD)
338  return false;
339 
340  bool LoopIdMDFound = false;
341  for (const MDOperand &MDOp : LoopIdMD->operands()) {
342  if (MDOp == DesiredLoopIdMetadata) {
343  LoopIdMDFound = true;
344  break;
345  }
346  }
347 
348  if (!LoopIdMDFound)
349  return false;
350  }
351  }
352  return true;
353 }
354 
356 
358  // If we have a debug location in the loop ID, then use it.
359  if (MDNode *LoopID = getLoopID()) {
360  DebugLoc Start;
361  // We use the first DebugLoc in the header as the start location of the loop
362  // and if there is a second DebugLoc in the header we use it as end location
363  // of the loop.
364  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
365  if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
366  if (!Start)
367  Start = DebugLoc(L);
368  else
369  return LocRange(Start, DebugLoc(L));
370  }
371  }
372 
373  if (Start)
374  return LocRange(Start);
375  }
376 
377  // Try the pre-header first.
378  if (BasicBlock *PHeadBB = getLoopPreheader())
379  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
380  return LocRange(DL);
381 
382  // If we have no pre-header or there are no instructions with debug
383  // info in it, try the header.
384  if (BasicBlock *HeadBB = getHeader())
385  return LocRange(HeadBB->getTerminator()->getDebugLoc());
386 
387  return LocRange();
388 }
389 
390 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
391 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
392 
394  print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
395 }
396 #endif
397 
398 //===----------------------------------------------------------------------===//
399 // UnloopUpdater implementation
400 //
401 
402 namespace {
403 /// Find the new parent loop for all blocks within the "unloop" whose last
404 /// backedges has just been removed.
405 class UnloopUpdater {
406  Loop &Unloop;
407  LoopInfo *LI;
408 
410 
411  // Map unloop's immediate subloops to their nearest reachable parents. Nested
412  // loops within these subloops will not change parents. However, an immediate
413  // subloop's new parent will be the nearest loop reachable from either its own
414  // exits *or* any of its nested loop's exits.
415  DenseMap<Loop *, Loop *> SubloopParents;
416 
417  // Flag the presence of an irreducible backedge whose destination is a block
418  // directly contained by the original unloop.
419  bool FoundIB;
420 
421 public:
422  UnloopUpdater(Loop *UL, LoopInfo *LInfo)
423  : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
424 
425  void updateBlockParents();
426 
427  void removeBlocksFromAncestors();
428 
429  void updateSubloopParents();
430 
431 protected:
432  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
433 };
434 } // end anonymous namespace
435 
436 /// Update the parent loop for all blocks that are directly contained within the
437 /// original "unloop".
438 void UnloopUpdater::updateBlockParents() {
439  if (Unloop.getNumBlocks()) {
440  // Perform a post order CFG traversal of all blocks within this loop,
441  // propagating the nearest loop from successors to predecessors.
442  LoopBlocksTraversal Traversal(DFS, LI);
443  for (BasicBlock *POI : Traversal) {
444 
445  Loop *L = LI->getLoopFor(POI);
446  Loop *NL = getNearestLoop(POI, L);
447 
448  if (NL != L) {
449  // For reducible loops, NL is now an ancestor of Unloop.
450  assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
451  "uninitialized successor");
452  LI->changeLoopFor(POI, NL);
453  } else {
454  // Or the current block is part of a subloop, in which case its parent
455  // is unchanged.
456  assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
457  }
458  }
459  }
460  // Each irreducible loop within the unloop induces a round of iteration using
461  // the DFS result cached by Traversal.
462  bool Changed = FoundIB;
463  for (unsigned NIters = 0; Changed; ++NIters) {
464  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
465 
466  // Iterate over the postorder list of blocks, propagating the nearest loop
467  // from successors to predecessors as before.
468  Changed = false;
469  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
470  POE = DFS.endPostorder();
471  POI != POE; ++POI) {
472 
473  Loop *L = LI->getLoopFor(*POI);
474  Loop *NL = getNearestLoop(*POI, L);
475  if (NL != L) {
476  assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
477  "uninitialized successor");
478  LI->changeLoopFor(*POI, NL);
479  Changed = true;
480  }
481  }
482  }
483 }
484 
485 /// Remove unloop's blocks from all ancestors below their new parents.
486 void UnloopUpdater::removeBlocksFromAncestors() {
487  // Remove all unloop's blocks (including those in nested subloops) from
488  // ancestors below the new parent loop.
489  for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
490  BI != BE; ++BI) {
491  Loop *OuterParent = LI->getLoopFor(*BI);
492  if (Unloop.contains(OuterParent)) {
493  while (OuterParent->getParentLoop() != &Unloop)
494  OuterParent = OuterParent->getParentLoop();
495  OuterParent = SubloopParents[OuterParent];
496  }
497  // Remove blocks from former Ancestors except Unloop itself which will be
498  // deleted.
499  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
500  OldParent = OldParent->getParentLoop()) {
501  assert(OldParent && "new loop is not an ancestor of the original");
502  OldParent->removeBlockFromLoop(*BI);
503  }
504  }
505 }
506 
507 /// Update the parent loop for all subloops directly nested within unloop.
508 void UnloopUpdater::updateSubloopParents() {
509  while (!Unloop.empty()) {
510  Loop *Subloop = *std::prev(Unloop.end());
511  Unloop.removeChildLoop(std::prev(Unloop.end()));
512 
513  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
514  if (Loop *Parent = SubloopParents[Subloop])
515  Parent->addChildLoop(Subloop);
516  else
517  LI->addTopLevelLoop(Subloop);
518  }
519 }
520 
521 /// Return the nearest parent loop among this block's successors. If a successor
522 /// is a subloop header, consider its parent to be the nearest parent of the
523 /// subloop's exits.
524 ///
525 /// For subloop blocks, simply update SubloopParents and return NULL.
526 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
527 
528  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
529  // is considered uninitialized.
530  Loop *NearLoop = BBLoop;
531 
532  Loop *Subloop = nullptr;
533  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
534  Subloop = NearLoop;
535  // Find the subloop ancestor that is directly contained within Unloop.
536  while (Subloop->getParentLoop() != &Unloop) {
537  Subloop = Subloop->getParentLoop();
538  assert(Subloop && "subloop is not an ancestor of the original loop");
539  }
540  // Get the current nearest parent of the Subloop exits, initially Unloop.
541  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
542  }
543 
544  succ_iterator I = succ_begin(BB), E = succ_end(BB);
545  if (I == E) {
546  assert(!Subloop && "subloop blocks must have a successor");
547  NearLoop = nullptr; // unloop blocks may now exit the function.
548  }
549  for (; I != E; ++I) {
550  if (*I == BB)
551  continue; // self loops are uninteresting
552 
553  Loop *L = LI->getLoopFor(*I);
554  if (L == &Unloop) {
555  // This successor has not been processed. This path must lead to an
556  // irreducible backedge.
557  assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
558  FoundIB = true;
559  }
560  if (L != &Unloop && Unloop.contains(L)) {
561  // Successor is in a subloop.
562  if (Subloop)
563  continue; // Branching within subloops. Ignore it.
564 
565  // BB branches from the original into a subloop header.
566  assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
567 
568  // Get the current nearest parent of the Subloop's exits.
569  L = SubloopParents[L];
570  // L could be Unloop if the only exit was an irreducible backedge.
571  }
572  if (L == &Unloop) {
573  continue;
574  }
575  // Handle critical edges from Unloop into a sibling loop.
576  if (L && !L->contains(&Unloop)) {
577  L = L->getParentLoop();
578  }
579  // Remember the nearest parent loop among successors or subloop exits.
580  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
581  NearLoop = L;
582  }
583  if (Subloop) {
584  SubloopParents[Subloop] = NearLoop;
585  return BBLoop;
586  }
587  return NearLoop;
588 }
589 
590 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
591 
594  // Check whether the analysis, all analyses on functions, or the function's
595  // CFG have been preserved.
596  auto PAC = PA.getChecker<LoopAnalysis>();
597  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
598  PAC.preservedSet<CFGAnalyses>());
599 }
600 
601 void LoopInfo::erase(Loop *Unloop) {
602  assert(!Unloop->isInvalid() && "Loop has already been erased!");
603 
604  auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
605 
606  // First handle the special case of no parent loop to simplify the algorithm.
607  if (!Unloop->getParentLoop()) {
608  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
609  for (Loop::block_iterator I = Unloop->block_begin(),
610  E = Unloop->block_end();
611  I != E; ++I) {
612 
613  // Don't reparent blocks in subloops.
614  if (getLoopFor(*I) != Unloop)
615  continue;
616 
617  // Blocks no longer have a parent but are still referenced by Unloop until
618  // the Unloop object is deleted.
619  changeLoopFor(*I, nullptr);
620  }
621 
622  // Remove the loop from the top-level LoopInfo object.
623  for (iterator I = begin();; ++I) {
624  assert(I != end() && "Couldn't find loop");
625  if (*I == Unloop) {
626  removeLoop(I);
627  break;
628  }
629  }
630 
631  // Move all of the subloops to the top-level.
632  while (!Unloop->empty())
633  addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
634 
635  return;
636  }
637 
638  // Update the parent loop for all blocks within the loop. Blocks within
639  // subloops will not change parents.
640  UnloopUpdater Updater(Unloop, this);
641  Updater.updateBlockParents();
642 
643  // Remove blocks from former ancestor loops.
644  Updater.removeBlocksFromAncestors();
645 
646  // Add direct subloops as children in their new parent loop.
647  Updater.updateSubloopParents();
648 
649  // Remove unloop from its parent loop.
650  Loop *ParentLoop = Unloop->getParentLoop();
651  for (Loop::iterator I = ParentLoop->begin();; ++I) {
652  assert(I != ParentLoop->end() && "Couldn't find loop");
653  if (*I == Unloop) {
654  ParentLoop->removeChildLoop(I);
655  break;
656  }
657  }
658 }
659 
660 AnalysisKey LoopAnalysis::Key;
661 
663  // FIXME: Currently we create a LoopInfo from scratch for every function.
664  // This may prove to be too wasteful due to deallocating and re-allocating
665  // memory each time for the underlying map and vector datastructures. At some
666  // point it may prove worthwhile to use a freelist and recycle LoopInfo
667  // objects. I don't want to add that kind of complexity until the scope of
668  // the problem is better understood.
669  LoopInfo LI;
671  return LI;
672 }
673 
676  AM.getResult<LoopAnalysis>(F).print(OS);
677  return PreservedAnalyses::all();
678 }
679 
680 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
681 
682  if (forcePrintModuleIR()) {
683  // handling -print-module-scope
684  OS << Banner << " (loop: ";
685  L.getHeader()->printAsOperand(OS, false);
686  OS << ")\n";
687 
688  // printing whole module
689  OS << *L.getHeader()->getModule();
690  return;
691  }
692 
693  OS << Banner;
694 
695  auto *PreHeader = L.getLoopPreheader();
696  if (PreHeader) {
697  OS << "\n; Preheader:";
698  PreHeader->print(OS);
699  OS << "\n; Loop:";
700  }
701 
702  for (auto *Block : L.blocks())
703  if (Block)
704  Block->print(OS);
705  else
706  OS << "Printing <null> block";
707 
708  SmallVector<BasicBlock *, 8> ExitBlocks;
709  L.getExitBlocks(ExitBlocks);
710  if (!ExitBlocks.empty()) {
711  OS << "\n; Exit blocks";
712  for (auto *Block : ExitBlocks)
713  if (Block)
714  Block->print(OS);
715  else
716  OS << "Printing <null> block";
717  }
718 }
719 
721  // No loop metadata node, no loop properties.
722  if (!LoopID)
723  return nullptr;
724 
725  // First operand should refer to the metadata node itself, for legacy reasons.
726  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
727  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
728 
729  // Iterate over the metdata node operands and look for MDString metadata.
730  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
731  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
732  if (!MD || MD->getNumOperands() < 1)
733  continue;
734  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
735  if (!S)
736  continue;
737  // Return the operand node if MDString holds expected metadata.
738  if (Name.equals(S->getString()))
739  return MD;
740  }
741 
742  // Loop property not found.
743  return nullptr;
744 }
745 
747  return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
748 }
749 
751  return Node->getNumOperands() == 0 && Node->isDistinct();
752 }
753 
755  MDNode *OrigLoopID,
756  ArrayRef<StringRef> RemovePrefixes,
757  ArrayRef<MDNode *> AddAttrs) {
758  // First remove any existing loop metadata related to this transformation.
760 
761  // Reserve first location for self reference to the LoopID metadata node.
762  TempMDTuple TempNode = MDNode::getTemporary(Context, None);
763  MDs.push_back(TempNode.get());
764 
765  // Remove metadata for the transformation that has been applied or that became
766  // outdated.
767  if (OrigLoopID) {
768  for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
769  bool IsVectorMetadata = false;
770  Metadata *Op = OrigLoopID->getOperand(i);
771  if (MDNode *MD = dyn_cast<MDNode>(Op)) {
772  const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
773  if (S)
774  IsVectorMetadata =
775  llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
776  return S->getString().startswith(Prefix);
777  });
778  }
779  if (!IsVectorMetadata)
780  MDs.push_back(Op);
781  }
782  }
783 
784  // Add metadata to avoid reapplying a transformation, such as
785  // llvm.loop.unroll.disable and llvm.loop.isvectorized.
786  MDs.append(AddAttrs.begin(), AddAttrs.end());
787 
788  MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
789  // Replace the temporary node with a self-reference.
790  NewLoopID->replaceOperandWith(0, NewLoopID);
791  return NewLoopID;
792 }
793 
794 //===----------------------------------------------------------------------===//
795 // LoopInfo implementation
796 //
797 
798 char LoopInfoWrapperPass::ID = 0;
799 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
800  true, true)
803  true, true)
804 
805 bool LoopInfoWrapperPass::runOnFunction(Function &) {
806  releaseMemory();
807  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
808  return false;
809 }
810 
812  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
813  // function each time verifyAnalysis is called is very expensive. The
814  // -verify-loop-info option can enable this. In order to perform some
815  // checking by default, LoopPass has been taught to call verifyLoop manually
816  // during loop pass sequences.
817  if (VerifyLoopInfo) {
818  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
819  LI.verify(DT);
820  }
821 }
822 
824  AU.setPreservesAll();
826 }
827 
829  LI.print(OS);
830 }
831 
834  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
835  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
836  LI.verify(DT);
837  return PreservedAnalyses::all();
838 }
839 
840 //===----------------------------------------------------------------------===//
841 // LoopBlocksDFS implementation
842 //
843 
844 /// Traverse the loop blocks and store the DFS result.
845 /// Useful for clients that just want the final DFS result and don't need to
846 /// visit blocks during the initial traversal.
848  LoopBlocksTraversal Traversal(*this, LI);
849  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
850  POE = Traversal.end();
851  POI != POE; ++POI)
852  ;
853 }
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:710
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:662
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:674
LLVMContext & Context
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
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:473
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:1195
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:202
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:195
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:754
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:173
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:58
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:65
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: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:311
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
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
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:697
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:669
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:601
static TempMDTuple getTemporary(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1177
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:952
void print(raw_ostream &O, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: LoopInfo.cpp:828
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: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:139
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LoopInfo.cpp:823
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref&#39;ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:720
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:257
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
Definition: LoopInfo.cpp:746
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:847
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:802
StringRef getString() const
Definition: Metadata.cpp:463
Core dominator tree base class.
Definition: LoopInfo.h:61
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:391
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:269
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:393
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:355
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:4289
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:59
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: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:720
Natural Loop Information
Definition: LoopInfo.cpp:802
bool VerifyLoopInfo
Enables verification of loop info.
Definition: LoopInfo.cpp:49
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:144
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:357
void setPreservesAll()
Set by analyses that do not transform their input at all.
static void DFS(BasicBlock *Root, SetVector< BasicBlock *> &Set)
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
bool getIncomingAndBackEdge(BasicBlock *&Incoming, BasicBlock *&Backedge) const
Obtain the unique incoming and back edge.
Definition: LoopInfo.cpp:118
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:592
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:211
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:233
const DebugLoc & getStart() const
Definition: LoopInfo.h:478
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
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: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:332
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:218
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:648
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:91
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
Definition: LoopInfo.cpp:280
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
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:832
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:583
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:977
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: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:680
block_iterator block_begin() const
Definition: LoopInfo.h:154
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:448
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
Definition: LoopInfo.cpp:750
loops
Definition: LoopInfo.cpp:802
const BasicBlock * getParent() const
Definition: Instruction.h:66
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, DominatorTree &DT)
Definition: LoopInfo.cpp:168
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: LoopInfo.cpp:811
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=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:69