LLVM  6.0.0svn
LoopInfo.cpp
Go to the documentation of this file.
1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the LoopInfo class that is used to identify natural loops
11 // and determine the loop depth of various nodes of the CFG. Note that the
12 // loops identified may actually be several natural loops that share the same
13 // header node... not just a single natural loop.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/ADT/ScopeExit.h"
20 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DebugLoc.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/LLVMContext.h"
30 #include "llvm/IR/Metadata.h"
31 #include "llvm/IR/PassManager.h"
33 #include "llvm/Support/Debug.h"
35 #include <algorithm>
36 using namespace llvm;
37 
38 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
41 
42 // Always verify loopinfo if expensive checking is enabled.
43 #ifdef EXPENSIVE_CHECKS
44 bool llvm::VerifyLoopInfo = true;
45 #else
46 bool llvm::VerifyLoopInfo = false;
47 #endif
49  VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
50  cl::desc("Verify loop info (time consuming)"));
51 
52 //===----------------------------------------------------------------------===//
53 // Loop implementation
54 //
55 
56 bool Loop::isLoopInvariant(const Value *V) const {
57  if (const Instruction *I = dyn_cast<Instruction>(V))
58  return !contains(I);
59  return true; // All non-instructions are loop invariant
60 }
61 
63  return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
64 }
65 
66 bool Loop::makeLoopInvariant(Value *V, bool &Changed,
67  Instruction *InsertPt) const {
68  if (Instruction *I = dyn_cast<Instruction>(V))
69  return makeLoopInvariant(I, Changed, InsertPt);
70  return true; // All non-instructions are loop-invariant.
71 }
72 
73 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
74  Instruction *InsertPt) const {
75  // Test if the value is already loop-invariant.
76  if (isLoopInvariant(I))
77  return true;
79  return false;
80  if (I->mayReadFromMemory())
81  return false;
82  // EH block instructions are immobile.
83  if (I->isEHPad())
84  return false;
85  // Determine the insertion point, unless one was given.
86  if (!InsertPt) {
87  BasicBlock *Preheader = getLoopPreheader();
88  // Without a preheader, hoisting is not feasible.
89  if (!Preheader)
90  return false;
91  InsertPt = Preheader->getTerminator();
92  }
93  // Don't hoist instructions with loop-variant operands.
94  for (Value *Operand : I->operands())
95  if (!makeLoopInvariant(Operand, Changed, InsertPt))
96  return false;
97 
98  // Hoist.
99  I->moveBefore(InsertPt);
100 
101  // There is possibility of hoisting this instruction above some arbitrary
102  // condition. Any metadata defined on it can be control dependent on this
103  // condition. Conservatively strip it here so that we don't give any wrong
104  // information to the optimizer.
106 
107  Changed = true;
108  return true;
109 }
110 
112  BasicBlock *H = getHeader();
113 
114  BasicBlock *Incoming = nullptr, *Backedge = nullptr;
115  pred_iterator PI = pred_begin(H);
116  assert(PI != pred_end(H) && "Loop must have at least one backedge!");
117  Backedge = *PI++;
118  if (PI == pred_end(H))
119  return nullptr; // dead loop
120  Incoming = *PI++;
121  if (PI != pred_end(H))
122  return nullptr; // multiple backedges?
123 
124  if (contains(Incoming)) {
125  if (contains(Backedge))
126  return nullptr;
127  std::swap(Incoming, Backedge);
128  } else if (!contains(Backedge))
129  return nullptr;
130 
131  // Loop over all of the PHI nodes, looking for a canonical indvar.
132  for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
133  PHINode *PN = cast<PHINode>(I);
134  if (ConstantInt *CI =
135  dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
136  if (CI->isZero())
137  if (Instruction *Inc =
138  dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
139  if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
140  if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
141  if (CI->isOne())
142  return PN;
143  }
144  return nullptr;
145 }
146 
147 // Check that 'BB' doesn't have any uses outside of the 'L'
148 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
149  DominatorTree &DT) {
150  for (const Instruction &I : BB) {
151  // Tokens can't be used in PHI nodes and live-out tokens prevent loop
152  // optimizations, so for the purposes of considered LCSSA form, we
153  // can ignore them.
154  if (I.getType()->isTokenTy())
155  continue;
156 
157  for (const Use &U : I.uses()) {
158  const Instruction *UI = cast<Instruction>(U.getUser());
159  const BasicBlock *UserBB = UI->getParent();
160  if (const PHINode *P = dyn_cast<PHINode>(UI))
161  UserBB = P->getIncomingBlock(U);
162 
163  // Check the current block, as a fast-path, before checking whether
164  // the use is anywhere in the loop. Most values are used in the same
165  // block they are defined in. Also, blocks not reachable from the
166  // entry are special; uses in them don't need to go through PHIs.
167  if (UserBB != &BB && !L.contains(UserBB) &&
168  DT.isReachableFromEntry(UserBB))
169  return false;
170  }
171  }
172  return true;
173 }
174 
176  // For each block we check that it doesn't have any uses outside of this loop.
177  return all_of(this->blocks(), [&](const BasicBlock *BB) {
178  return isBlockInLCSSAForm(*this, *BB, DT);
179  });
180 }
181 
183  // For each block we check that it doesn't have any uses outside of its
184  // innermost loop. This process will transitively guarantee that the current
185  // loop and all of the nested loops are in LCSSA form.
186  return all_of(this->blocks(), [&](const BasicBlock *BB) {
187  return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
188  });
189 }
190 
192  // Normal-form loops have a preheader, a single backedge, and all of their
193  // exits have all their predecessors inside the loop.
195 }
196 
197 // Routines that reform the loop CFG and split edges often fail on indirectbr.
198 bool Loop::isSafeToClone() const {
199  // Return false if any loop blocks contain indirectbrs, or there are any calls
200  // to noduplicate functions.
201  for (BasicBlock *BB : this->blocks()) {
202  if (isa<IndirectBrInst>(BB->getTerminator()))
203  return false;
204 
205  for (Instruction &I : *BB)
206  if (auto CS = CallSite(&I))
207  if (CS.cannotDuplicate())
208  return false;
209  }
210  return true;
211 }
212 
214  MDNode *LoopID = nullptr;
215  if (BasicBlock *Latch = getLoopLatch()) {
216  LoopID = Latch->getTerminator()->getMetadata(LLVMContext::MD_loop);
217  } else {
218  assert(!getLoopLatch() &&
219  "The loop should have no single latch at this point");
220  // Go through each predecessor of the loop header and check the
221  // terminator for the metadata.
222  BasicBlock *H = getHeader();
223  for (BasicBlock *BB : this->blocks()) {
224  TerminatorInst *TI = BB->getTerminator();
225  MDNode *MD = nullptr;
226 
227  // Check if this terminator branches to the loop header.
228  for (BasicBlock *Successor : TI->successors()) {
229  if (Successor == H) {
231  break;
232  }
233  }
234  if (!MD)
235  return nullptr;
236 
237  if (!LoopID)
238  LoopID = MD;
239  else if (MD != LoopID)
240  return nullptr;
241  }
242  }
243  if (!LoopID || LoopID->getNumOperands() == 0 ||
244  LoopID->getOperand(0) != LoopID)
245  return nullptr;
246  return LoopID;
247 }
248 
249 void Loop::setLoopID(MDNode *LoopID) const {
250  assert(LoopID && "Loop ID should not be null");
251  assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
252  assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");
253 
254  if (BasicBlock *Latch = getLoopLatch()) {
255  Latch->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
256  return;
257  }
258 
259  assert(!getLoopLatch() &&
260  "The loop should have no single latch at this point");
261  BasicBlock *H = getHeader();
262  for (BasicBlock *BB : this->blocks()) {
263  TerminatorInst *TI = BB->getTerminator();
264  for (BasicBlock *Successor : TI->successors()) {
265  if (Successor == H)
266  TI->setMetadata(LLVMContext::MD_loop, LoopID);
267  }
268  }
269 }
270 
272  MDNode *LoopID = getLoopID();
273  // First remove any existing loop unrolling metadata.
275  // Reserve first location for self reference to the LoopID metadata node.
276  MDs.push_back(nullptr);
277 
278  if (LoopID) {
279  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
280  bool IsUnrollMetadata = false;
281  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
282  if (MD) {
283  const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
284  IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
285  }
286  if (!IsUnrollMetadata)
287  MDs.push_back(LoopID->getOperand(i));
288  }
289  }
290 
291  // Add unroll(disable) metadata to disable future unrolling.
293  SmallVector<Metadata *, 1> DisableOperands;
294  DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
295  MDNode *DisableNode = MDNode::get(Context, DisableOperands);
296  MDs.push_back(DisableNode);
297 
298  MDNode *NewLoopID = MDNode::get(Context, MDs);
299  // Set operand 0 to refer to the loop id itself.
300  NewLoopID->replaceOperandWith(0, NewLoopID);
301  setLoopID(NewLoopID);
302 }
303 
305  MDNode *DesiredLoopIdMetadata = getLoopID();
306 
307  if (!DesiredLoopIdMetadata)
308  return false;
309 
310  // The loop branch contains the parallel loop metadata. In order to ensure
311  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
312  // dependencies (thus converted the loop back to a sequential loop), check
313  // that all the memory instructions in the loop contain parallelism metadata
314  // that point to the same unique "loop id metadata" the loop branch does.
315  for (BasicBlock *BB : this->blocks()) {
316  for (Instruction &I : *BB) {
317  if (!I.mayReadOrWriteMemory())
318  continue;
319 
320  // The memory instruction can refer to the loop identifier metadata
321  // directly or indirectly through another list metadata (in case of
322  // nested parallel loops). The loop identifier metadata refers to
323  // itself so we can check both cases with the same routine.
324  MDNode *LoopIdMD =
326 
327  if (!LoopIdMD)
328  return false;
329 
330  bool LoopIdMDFound = false;
331  for (const MDOperand &MDOp : LoopIdMD->operands()) {
332  if (MDOp == DesiredLoopIdMetadata) {
333  LoopIdMDFound = true;
334  break;
335  }
336  }
337 
338  if (!LoopIdMDFound)
339  return false;
340  }
341  }
342  return true;
343 }
344 
346 
348  // If we have a debug location in the loop ID, then use it.
349  if (MDNode *LoopID = getLoopID()) {
350  DebugLoc Start;
351  // We use the first DebugLoc in the header as the start location of the loop
352  // and if there is a second DebugLoc in the header we use it as end location
353  // of the loop.
354  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
355  if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
356  if (!Start)
357  Start = DebugLoc(L);
358  else
359  return LocRange(Start, DebugLoc(L));
360  }
361  }
362 
363  if (Start)
364  return LocRange(Start);
365  }
366 
367  // Try the pre-header first.
368  if (BasicBlock *PHeadBB = getLoopPreheader())
369  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
370  return LocRange(DL);
371 
372  // If we have no pre-header or there are no instructions with debug
373  // info in it, try the header.
374  if (BasicBlock *HeadBB = getHeader())
375  return LocRange(HeadBB->getTerminator()->getDebugLoc());
376 
377  return LocRange();
378 }
379 
381  // Each predecessor of each exit block of a normal loop is contained
382  // within the loop.
383  SmallVector<BasicBlock *, 4> ExitBlocks;
384  getExitBlocks(ExitBlocks);
385  for (BasicBlock *BB : ExitBlocks)
386  for (BasicBlock *Predecessor : predecessors(BB))
387  if (!contains(Predecessor))
388  return false;
389  // All the requirements are met.
390  return true;
391 }
392 
394  SmallVectorImpl<BasicBlock *> &ExitBlocks) const {
396  "getUniqueExitBlocks assumes the loop has canonical form exits!");
397 
398  SmallVector<BasicBlock *, 32> SwitchExitBlocks;
399  for (BasicBlock *BB : this->blocks()) {
400  SwitchExitBlocks.clear();
401  for (BasicBlock *Successor : successors(BB)) {
402  // If block is inside the loop then it is not an exit block.
403  if (contains(Successor))
404  continue;
405 
407  BasicBlock *FirstPred = *PI;
408 
409  // If current basic block is this exit block's first predecessor
410  // then only insert exit block in to the output ExitBlocks vector.
411  // This ensures that same exit block is not inserted twice into
412  // ExitBlocks vector.
413  if (BB != FirstPred)
414  continue;
415 
416  // If a terminator has more then two successors, for example SwitchInst,
417  // then it is possible that there are multiple edges from current block
418  // to one exit block.
419  if (std::distance(succ_begin(BB), succ_end(BB)) <= 2) {
420  ExitBlocks.push_back(Successor);
421  continue;
422  }
423 
424  // In case of multiple edges from current block to exit block, collect
425  // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
426  // duplicate edges.
427  if (!is_contained(SwitchExitBlocks, Successor)) {
428  SwitchExitBlocks.push_back(Successor);
429  ExitBlocks.push_back(Successor);
430  }
431  }
432  }
433 }
434 
436  SmallVector<BasicBlock *, 8> UniqueExitBlocks;
437  getUniqueExitBlocks(UniqueExitBlocks);
438  if (UniqueExitBlocks.size() == 1)
439  return UniqueExitBlocks[0];
440  return nullptr;
441 }
442 
443 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
444 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
445 
447  print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
448 }
449 #endif
450 
451 //===----------------------------------------------------------------------===//
452 // UnloopUpdater implementation
453 //
454 
455 namespace {
456 /// Find the new parent loop for all blocks within the "unloop" whose last
457 /// backedges has just been removed.
458 class UnloopUpdater {
459  Loop &Unloop;
460  LoopInfo *LI;
461 
463 
464  // Map unloop's immediate subloops to their nearest reachable parents. Nested
465  // loops within these subloops will not change parents. However, an immediate
466  // subloop's new parent will be the nearest loop reachable from either its own
467  // exits *or* any of its nested loop's exits.
468  DenseMap<Loop *, Loop *> SubloopParents;
469 
470  // Flag the presence of an irreducible backedge whose destination is a block
471  // directly contained by the original unloop.
472  bool FoundIB;
473 
474 public:
475  UnloopUpdater(Loop *UL, LoopInfo *LInfo)
476  : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
477 
478  void updateBlockParents();
479 
480  void removeBlocksFromAncestors();
481 
482  void updateSubloopParents();
483 
484 protected:
485  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
486 };
487 } // end anonymous namespace
488 
489 /// Update the parent loop for all blocks that are directly contained within the
490 /// original "unloop".
491 void UnloopUpdater::updateBlockParents() {
492  if (Unloop.getNumBlocks()) {
493  // Perform a post order CFG traversal of all blocks within this loop,
494  // propagating the nearest loop from successors to predecessors.
495  LoopBlocksTraversal Traversal(DFS, LI);
496  for (BasicBlock *POI : Traversal) {
497 
498  Loop *L = LI->getLoopFor(POI);
499  Loop *NL = getNearestLoop(POI, L);
500 
501  if (NL != L) {
502  // For reducible loops, NL is now an ancestor of Unloop.
503  assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
504  "uninitialized successor");
505  LI->changeLoopFor(POI, NL);
506  } else {
507  // Or the current block is part of a subloop, in which case its parent
508  // is unchanged.
509  assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
510  }
511  }
512  }
513  // Each irreducible loop within the unloop induces a round of iteration using
514  // the DFS result cached by Traversal.
515  bool Changed = FoundIB;
516  for (unsigned NIters = 0; Changed; ++NIters) {
517  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
518 
519  // Iterate over the postorder list of blocks, propagating the nearest loop
520  // from successors to predecessors as before.
521  Changed = false;
522  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
523  POE = DFS.endPostorder();
524  POI != POE; ++POI) {
525 
526  Loop *L = LI->getLoopFor(*POI);
527  Loop *NL = getNearestLoop(*POI, L);
528  if (NL != L) {
529  assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
530  "uninitialized successor");
531  LI->changeLoopFor(*POI, NL);
532  Changed = true;
533  }
534  }
535  }
536 }
537 
538 /// Remove unloop's blocks from all ancestors below their new parents.
539 void UnloopUpdater::removeBlocksFromAncestors() {
540  // Remove all unloop's blocks (including those in nested subloops) from
541  // ancestors below the new parent loop.
542  for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
543  BI != BE; ++BI) {
544  Loop *OuterParent = LI->getLoopFor(*BI);
545  if (Unloop.contains(OuterParent)) {
546  while (OuterParent->getParentLoop() != &Unloop)
547  OuterParent = OuterParent->getParentLoop();
548  OuterParent = SubloopParents[OuterParent];
549  }
550  // Remove blocks from former Ancestors except Unloop itself which will be
551  // deleted.
552  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
553  OldParent = OldParent->getParentLoop()) {
554  assert(OldParent && "new loop is not an ancestor of the original");
555  OldParent->removeBlockFromLoop(*BI);
556  }
557  }
558 }
559 
560 /// Update the parent loop for all subloops directly nested within unloop.
561 void UnloopUpdater::updateSubloopParents() {
562  while (!Unloop.empty()) {
563  Loop *Subloop = *std::prev(Unloop.end());
564  Unloop.removeChildLoop(std::prev(Unloop.end()));
565 
566  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
567  if (Loop *Parent = SubloopParents[Subloop])
568  Parent->addChildLoop(Subloop);
569  else
570  LI->addTopLevelLoop(Subloop);
571  }
572 }
573 
574 /// Return the nearest parent loop among this block's successors. If a successor
575 /// is a subloop header, consider its parent to be the nearest parent of the
576 /// subloop's exits.
577 ///
578 /// For subloop blocks, simply update SubloopParents and return NULL.
579 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
580 
581  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
582  // is considered uninitialized.
583  Loop *NearLoop = BBLoop;
584 
585  Loop *Subloop = nullptr;
586  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
587  Subloop = NearLoop;
588  // Find the subloop ancestor that is directly contained within Unloop.
589  while (Subloop->getParentLoop() != &Unloop) {
590  Subloop = Subloop->getParentLoop();
591  assert(Subloop && "subloop is not an ancestor of the original loop");
592  }
593  // Get the current nearest parent of the Subloop exits, initially Unloop.
594  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
595  }
596 
597  succ_iterator I = succ_begin(BB), E = succ_end(BB);
598  if (I == E) {
599  assert(!Subloop && "subloop blocks must have a successor");
600  NearLoop = nullptr; // unloop blocks may now exit the function.
601  }
602  for (; I != E; ++I) {
603  if (*I == BB)
604  continue; // self loops are uninteresting
605 
606  Loop *L = LI->getLoopFor(*I);
607  if (L == &Unloop) {
608  // This successor has not been processed. This path must lead to an
609  // irreducible backedge.
610  assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
611  FoundIB = true;
612  }
613  if (L != &Unloop && Unloop.contains(L)) {
614  // Successor is in a subloop.
615  if (Subloop)
616  continue; // Branching within subloops. Ignore it.
617 
618  // BB branches from the original into a subloop header.
619  assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
620 
621  // Get the current nearest parent of the Subloop's exits.
622  L = SubloopParents[L];
623  // L could be Unloop if the only exit was an irreducible backedge.
624  }
625  if (L == &Unloop) {
626  continue;
627  }
628  // Handle critical edges from Unloop into a sibling loop.
629  if (L && !L->contains(&Unloop)) {
630  L = L->getParentLoop();
631  }
632  // Remember the nearest parent loop among successors or subloop exits.
633  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
634  NearLoop = L;
635  }
636  if (Subloop) {
637  SubloopParents[Subloop] = NearLoop;
638  return BBLoop;
639  }
640  return NearLoop;
641 }
642 
643 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
644 
647  // Check whether the analysis, all analyses on functions, or the function's
648  // CFG have been preserved.
649  auto PAC = PA.getChecker<LoopAnalysis>();
650  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
651  PAC.preservedSet<CFGAnalyses>());
652 }
653 
654 void LoopInfo::erase(Loop *Unloop) {
655  assert(!Unloop->isInvalid() && "Loop has already been erased!");
656 
657  auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
658 
659  // First handle the special case of no parent loop to simplify the algorithm.
660  if (!Unloop->getParentLoop()) {
661  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
662  for (Loop::block_iterator I = Unloop->block_begin(),
663  E = Unloop->block_end();
664  I != E; ++I) {
665 
666  // Don't reparent blocks in subloops.
667  if (getLoopFor(*I) != Unloop)
668  continue;
669 
670  // Blocks no longer have a parent but are still referenced by Unloop until
671  // the Unloop object is deleted.
672  changeLoopFor(*I, nullptr);
673  }
674 
675  // Remove the loop from the top-level LoopInfo object.
676  for (iterator I = begin();; ++I) {
677  assert(I != end() && "Couldn't find loop");
678  if (*I == Unloop) {
679  removeLoop(I);
680  break;
681  }
682  }
683 
684  // Move all of the subloops to the top-level.
685  while (!Unloop->empty())
686  addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
687 
688  return;
689  }
690 
691  // Update the parent loop for all blocks within the loop. Blocks within
692  // subloops will not change parents.
693  UnloopUpdater Updater(Unloop, this);
694  Updater.updateBlockParents();
695 
696  // Remove blocks from former ancestor loops.
697  Updater.removeBlocksFromAncestors();
698 
699  // Add direct subloops as children in their new parent loop.
700  Updater.updateSubloopParents();
701 
702  // Remove unloop from its parent loop.
703  Loop *ParentLoop = Unloop->getParentLoop();
704  for (Loop::iterator I = ParentLoop->begin();; ++I) {
705  assert(I != ParentLoop->end() && "Couldn't find loop");
706  if (*I == Unloop) {
707  ParentLoop->removeChildLoop(I);
708  break;
709  }
710  }
711 }
712 
713 AnalysisKey LoopAnalysis::Key;
714 
716  // FIXME: Currently we create a LoopInfo from scratch for every function.
717  // This may prove to be too wasteful due to deallocating and re-allocating
718  // memory each time for the underlying map and vector datastructures. At some
719  // point it may prove worthwhile to use a freelist and recycle LoopInfo
720  // objects. I don't want to add that kind of complexity until the scope of
721  // the problem is better understood.
722  LoopInfo LI;
724  return LI;
725 }
726 
729  AM.getResult<LoopAnalysis>(F).print(OS);
730  return PreservedAnalyses::all();
731 }
732 
733 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
734  OS << Banner;
735 
736  auto *PreHeader = L.getLoopPreheader();
737  if (PreHeader) {
738  OS << "\n; Preheader:";
739  PreHeader->print(OS);
740  OS << "\n; Loop:";
741  }
742 
743  for (auto *Block : L.blocks())
744  if (Block)
745  Block->print(OS);
746  else
747  OS << "Printing <null> block";
748 
749  SmallVector<BasicBlock *, 8> ExitBlocks;
750  L.getExitBlocks(ExitBlocks);
751  if (!ExitBlocks.empty()) {
752  OS << "\n; Exit blocks";
753  for (auto *Block : ExitBlocks)
754  if (Block)
755  Block->print(OS);
756  else
757  OS << "Printing <null> block";
758  }
759 }
760 
761 //===----------------------------------------------------------------------===//
762 // LoopInfo implementation
763 //
764 
765 char LoopInfoWrapperPass::ID = 0;
766 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
767  true, true)
770  true, true)
771 
772 bool LoopInfoWrapperPass::runOnFunction(Function &) {
773  releaseMemory();
774  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
775  return false;
776 }
777 
779  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
780  // function each time verifyAnalysis is called is very expensive. The
781  // -verify-loop-info option can enable this. In order to perform some
782  // checking by default, LoopPass has been taught to call verifyLoop manually
783  // during loop pass sequences.
784  if (VerifyLoopInfo) {
785  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
786  LI.verify(DT);
787  }
788 }
789 
791  AU.setPreservesAll();
793 }
794 
796  LI.print(OS);
797 }
798 
801  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
802  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
803  LI.verify(DT);
804  return PreservedAnalyses::all();
805 }
806 
807 //===----------------------------------------------------------------------===//
808 // LoopBlocksDFS implementation
809 //
810 
811 /// Traverse the loop blocks and store the DFS result.
812 /// Useful for clients that just want the final DFS result and don't need to
813 /// visit blocks during the initial traversal.
815  LoopBlocksTraversal Traversal(*this, LI);
816  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
817  POE = Traversal.end();
818  POI != POE; ++POI)
819  ;
820 }
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:709
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:715
BasicBlock * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:157
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:727
LLVMContext & Context
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1187
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
static cl::opt< bool, true > VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), cl::desc("Verify loop info (time consuming)"))
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:851
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:446
bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:182
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:175
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:320
This file contains the declarations for metadata subclasses.
BasicBlock * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:106
BasicBlock * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfo.cpp:435
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:47
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:66
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:813
A debug info location.
Definition: DebugLoc.h:34
Metadata node.
Definition: Metadata.h:862
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
F(f)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1067
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:290
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:62
bool isInvalid() const
Return true if this loop is no longer valid.
Definition: LoopInfo.h:187
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:624
void print(raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:325
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:304
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Traverse the blocks in a loop using a depth-first search.
Definition: LoopIterator.h:182
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:678
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
POTIterator begin()
Postorder traversal over the graph.
Definition: LoopIterator.h:198
std::vector< Loop *>::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:650
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:654
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:933
void print(raw_ostream &O, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: LoopInfo.cpp:795
BasicBlock * getHeader() const
Definition: LoopInfo.h:100
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
void getExitBlocks(SmallVectorImpl< BasicBlock * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:63
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfo.cpp:380
std::vector< Loop *>::const_iterator iterator
Definition: LoopInfo.h:139
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:267
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LoopInfo.cpp:790
op_range operands() const
Definition: Metadata.h:1065
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:249
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:194
Debug location.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:814
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
void getUniqueExitBlocks(SmallVectorImpl< BasicBlock *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfo.cpp:393
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
Natural Loop true
Definition: LoopInfo.cpp:769
StringRef getString() const
Definition: Metadata.cpp:456
Core dominator tree base class.
Definition: LoopInfo.h:61
succ_range successors()
Definition: InstrTypes.h:267
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1164
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information", true, true) INITIALIZE_PASS_END(LoopInfoWrapperPass
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
void dump() const
Definition: LoopInfo.cpp:444
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define H(x, y, z)
Definition: MD5.cpp:57
void setLoopAlreadyUnrolled()
Add llvm.loop.unroll.disable to this loop&#39;s loop id metadata.
Definition: LoopInfo.cpp:271
void dumpVerbose() const
Definition: LoopInfo.cpp:446
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:483
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
Represent the analysis usage information of a pass.
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
op_range operands()
Definition: User.h:222
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:345
A range representing the start and end location of a loop.
Definition: LoopInfo.h:442
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:1214
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:56
unsigned first
bool contains(const Loop *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
Iterator for intrusive lists based on ilist_node.
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Natural Loop Information
Definition: LoopInfo.cpp:769
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:110
bool VerifyLoopInfo
Enables verification of loop info.
Definition: LoopInfo.cpp:46
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:923
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:111
Store the result of a depth first search within basic blocks contained by a single loop...
Definition: LoopIterator.h:98
LocRange getLocRange() const
Return the source code span of the loop.
Definition: LoopInfo.cpp:347
void setPreservesAll()
Set by analyses that do not transform their input at all.
static void DFS(BasicBlock *Root, SetVector< BasicBlock *> &Set)
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: LoopInfo.cpp:645
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:191
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:213
const DebugLoc & getStart() const
Definition: LoopInfo.h:452
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:439
#define I(x, y, z)
Definition: MD5.cpp:58
bool mayReadFromMemory() const
Return true if this instruction may read memory.
std::vector< BasicBlock * >::const_iterator POIterator
Postorder list iterators.
Definition: LoopIterator.h:101
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
block_iterator block_end() const
Definition: LoopInfo.h:155
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:198
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
bool empty() const
Definition: LoopInfo.h:146
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
Definition: LoopInfo.cpp:304
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:799
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:88
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:538
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:958
A single uniqued string.
Definition: Metadata.h:602
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
This header defines various interfaces for pass management in LLVM.
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1073
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")
Function to print a loop&#39;s contents as LLVM&#39;s text IR assembly.
Definition: LoopInfo.cpp:733
block_iterator block_begin() const
Definition: LoopInfo.h:154
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:422
loops
Definition: LoopInfo.cpp:769
const BasicBlock * getParent() const
Definition: Instruction.h:66
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, DominatorTree &DT)
Definition: LoopInfo.cpp:148
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: LoopInfo.cpp:778
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:867