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