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"
18#include "llvm/ADT/DepthFirstIterator.h"
19#include "llvm/ADT/SmallPtrSet.h"
20#include "llvm/Analysis/LoopInfoImpl.h"
21#include "llvm/Analysis/LoopIterator.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/IR/CFG.h"
24#include "llvm/IR/Constants.h"
25#include "llvm/IR/DebugLoc.h"
26#include "llvm/IR/Dominators.h"
27#include "llvm/IR/Instructions.h"
28#include "llvm/IR/LLVMContext.h"
29#include "llvm/IR/Metadata.h"
30#include "llvm/IR/PassManager.h"
31#include "llvm/Support/CommandLine.h"
32#include "llvm/Support/Debug.h"
33#include "llvm/Support/raw_ostream.h"
34#include <algorithm>
35using namespace llvm;
36
37// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
38template class llvm::LoopBase<BasicBlock, Loop>;
39template class llvm::LoopInfoBase<BasicBlock, Loop>;
40
41// Always verify loopinfo if expensive checking is enabled.
42#ifdef EXPENSIVE_CHECKS
43static bool VerifyLoopInfo = true;
44#else
45static bool VerifyLoopInfo = false;
46#endif
47static cl::opt<bool,true>
48VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
49                cl::desc("Verify loop info (time consuming)"));
50
51//===----------------------------------------------------------------------===//
52// Loop implementation
53//
54
55bool Loop::isLoopInvariant(const Value *V) const {
56  if (const Instruction *I = dyn_cast<Instruction>(V))
57    return !contains(I);
58  return true;  // All non-instructions are loop invariant
59}
60
61bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
62  return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
63}
64
65bool Loop::makeLoopInvariant(Value *V, bool &Changed,
66                             Instruction *InsertPt) const {
67  if (Instruction *I = dyn_cast<Instruction>(V))
68    return makeLoopInvariant(I, Changed, InsertPt);
69  return true;  // All non-instructions are loop-invariant.
70}
71
72bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
73                             Instruction *InsertPt) const {
74  // Test if the value is already loop-invariant.
75  if (isLoopInvariant(I))
76    return true;
77  if (!isSafeToSpeculativelyExecute(I))
78    return false;
79  if (I->mayReadFromMemory())
80    return false;
81  // EH block instructions are immobile.
82  if (I->isEHPad())
83    return false;
84  // Determine the insertion point, unless one was given.
85  if (!InsertPt) {
86    BasicBlock *Preheader = getLoopPreheader();
87    // Without a preheader, hoisting is not feasible.
88    if (!Preheader)
89      return false;
90    InsertPt = Preheader->getTerminator();
91  }
92  // Don't hoist instructions with loop-variant operands.
93  for (Value *Operand : I->operands())
94    if (!makeLoopInvariant(Operand, Changed, InsertPt))
95      return false;
96
97  // Hoist.
98  I->moveBefore(InsertPt);
99
100  // There is possibility of hoisting this instruction above some arbitrary
101  // condition. Any metadata defined on it can be control dependent on this
102  // condition. Conservatively strip it here so that we don't give any wrong
103  // information to the optimizer.
104  I->dropUnknownNonDebugMetadata();
105
106  Changed = true;
107  return true;
108}
109
110PHINode *Loop::getCanonicalInductionVariable() const {
111  BasicBlock *H = getHeader();
112
113  BasicBlock *Incoming = nullptr, *Backedge = nullptr;
114  pred_iterator PI = pred_begin(H);
115  assert(PI != pred_end(H) &&
116         "Loop must have at least one backedge!");
117  Backedge = *PI++;
118  if (PI == pred_end(H)) return nullptr;  // dead loop
119  Incoming = *PI++;
120  if (PI != pred_end(H)) return nullptr;  // multiple backedges?
121
122  if (contains(Incoming)) {
123    if (contains(Backedge))
124      return nullptr;
125    std::swap(Incoming, Backedge);
126  } else if (!contains(Backedge))
127    return nullptr;
128
129  // Loop over all of the PHI nodes, looking for a canonical indvar.
130  for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
131    PHINode *PN = cast<PHINode>(I);
132    if (ConstantInt *CI =
133        dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
134      if (CI->isNullValue())
135        if (Instruction *Inc =
136            dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
137          if (Inc->getOpcode() == Instruction::Add &&
138                Inc->getOperand(0) == PN)
139            if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
140              if (CI->equalsInt(1))
141                return PN;
142  }
143  return nullptr;
144}
145
146bool Loop::isLCSSAForm(DominatorTree &DT) const {
147  for (BasicBlock *BB : this->blocks()) {
148    for (Instruction &I : *BB) {
149      // Tokens can't be used in PHI nodes and live-out tokens prevent loop
150      // optimizations, so for the purposes of considered LCSSA form, we
151      // can ignore them.
152      if (I.getType()->isTokenTy())
153        continue;
154
155      for (Use &U : I.uses()) {
156        Instruction *UI = cast<Instruction>(U.getUser());
157        BasicBlock *UserBB = UI->getParent();
158        if (PHINode *P = dyn_cast<PHINode>(UI))
159          UserBB = P->getIncomingBlock(U);
160
161        // Check the current block, as a fast-path, before checking whether
162        // the use is anywhere in the loop.  Most values are used in the same
163        // block they are defined in.  Also, blocks not reachable from the
164        // entry are special; uses in them don't need to go through PHIs.
165        if (UserBB != BB &&
166            !contains(UserBB) &&
167            DT.isReachableFromEntry(UserBB))
168          return false;
169      }
170    }
171  }
172
173  return true;
174}
175
176bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT) const {
177  if (!isLCSSAForm(DT))
178    return false;
179
180  return std::all_of(begin(), end(), [&](const Loop *L) {
181    return L->isRecursivelyLCSSAForm(DT);
182  });
183}
184
185bool Loop::isLoopSimplifyForm() const {
186  // Normal-form loops have a preheader, a single backedge, and all of their
187  // exits have all their predecessors inside the loop.
188  return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
189}
190
191// Routines that reform the loop CFG and split edges often fail on indirectbr.
192bool Loop::isSafeToClone() const {
193  // Return false if any loop blocks contain indirectbrs, or there are any calls
194  // to noduplicate functions.
195  for (BasicBlock *BB : this->blocks()) {
196    if (isa<IndirectBrInst>(BB->getTerminator()))
197      return false;
198
199    for (Instruction &I : *BB)
200      if (auto CS = CallSite(&I))
201        if (CS.cannotDuplicate())
202          return false;
203  }
204  return true;
205}
206
207MDNode *Loop::getLoopID() const {
208  MDNode *LoopID = nullptr;
209  if (isLoopSimplifyForm()) {
210    LoopID = getLoopLatch()->getTerminator()->getMetadata(LLVMContext::MD_loop);
211  } else {
212    // Go through each predecessor of the loop header and check the
213    // terminator for the metadata.
214    BasicBlock *H = getHeader();
215    for (BasicBlock *BB : this->blocks()) {
216      TerminatorInst *TI = BB->getTerminator();
217      MDNode *MD = nullptr;
218
219      // Check if this terminator branches to the loop header.
220      for (BasicBlock *Successor : TI->successors()) {
221        if (Successor == H) {
222          MD = TI->getMetadata(LLVMContext::MD_loop);
223          break;
224        }
225      }
226      if (!MD)
227        return nullptr;
228
229      if (!LoopID)
230        LoopID = MD;
231      else if (MD != LoopID)
232        return nullptr;
233    }
234  }
235  if (!LoopID || LoopID->getNumOperands() == 0 ||
236      LoopID->getOperand(0) != LoopID)
237    return nullptr;
238  return LoopID;
239}
240
241void Loop::setLoopID(MDNode *LoopID) const {
242  assert(LoopID && "Loop ID should not be null");
243  assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
244  assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");
245
246  if (isLoopSimplifyForm()) {
247    getLoopLatch()->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
248    return;
249  }
250
251  BasicBlock *H = getHeader();
252  for (BasicBlock *BB : this->blocks()) {
253    TerminatorInst *TI = BB->getTerminator();
254    for (BasicBlock *Successor : TI->successors()) {
255      if (Successor == H)
256        TI->setMetadata(LLVMContext::MD_loop, LoopID);
257    }
258  }
259}
260
261bool Loop::isAnnotatedParallel() const {
262  MDNode *DesiredLoopIdMetadata = getLoopID();
263
264  if (!DesiredLoopIdMetadata)
265      return false;
266
267  // The loop branch contains the parallel loop metadata. In order to ensure
268  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
269  // dependencies (thus converted the loop back to a sequential loop), check
270  // that all the memory instructions in the loop contain parallelism metadata
271  // that point to the same unique "loop id metadata" the loop branch does.
272  for (BasicBlock *BB : this->blocks()) {
273    for (Instruction &I : *BB) {
274      if (!I.mayReadOrWriteMemory())
275        continue;
276
277      // The memory instruction can refer to the loop identifier metadata
278      // directly or indirectly through another list metadata (in case of
279      // nested parallel loops). The loop identifier metadata refers to
280      // itself so we can check both cases with the same routine.
281      MDNode *LoopIdMD =
282          I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
283
284      if (!LoopIdMD)
285        return false;
286
287      bool LoopIdMDFound = false;
288      for (const MDOperand &MDOp : LoopIdMD->operands()) {
289        if (MDOp == DesiredLoopIdMetadata) {
290          LoopIdMDFound = true;
291          break;
292        }
293      }
294
295      if (!LoopIdMDFound)
296        return false;
297    }
298  }
299  return true;
300}
301
302DebugLoc Loop::getStartLoc() const {
303  // If we have a debug location in the loop ID, then use it.
304  if (MDNode *LoopID = getLoopID())
305    for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i)
306      if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i)))
307        return DebugLoc(L);
308
309  // Try the pre-header first.
310  if (BasicBlock *PHeadBB = getLoopPreheader())
311    if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
312      return DL;
313
314  // If we have no pre-header or there are no instructions with debug
315  // info in it, try the header.
316  if (BasicBlock *HeadBB = getHeader())
317    return HeadBB->getTerminator()->getDebugLoc();
318
319  return DebugLoc();
320}
321
322bool Loop::hasDedicatedExits() const {
323  // Each predecessor of each exit block of a normal loop is contained
324  // within the loop.
325  SmallVector<BasicBlock *, 4> ExitBlocks;
326  getExitBlocks(ExitBlocks);
327  for (BasicBlock *BB : ExitBlocks)
328    for (BasicBlock *Predecessor : predecessors(BB))
329      if (!contains(Predecessor))
330        return false;
331  // All the requirements are met.
332  return true;
333}
334
335void
336Loop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const {
337  assert(hasDedicatedExits() &&
338         "getUniqueExitBlocks assumes the loop has canonical form exits!");
339
340  SmallVector<BasicBlock *, 32> SwitchExitBlocks;
341  for (BasicBlock *BB : this->blocks()) {
342    SwitchExitBlocks.clear();
343    for (BasicBlock *Successor : successors(BB)) {
344      // If block is inside the loop then it is not an exit block.
345      if (contains(Successor))
346        continue;
347
348      pred_iterator PI = pred_begin(Successor);
349      BasicBlock *FirstPred = *PI;
350
351      // If current basic block is this exit block's first predecessor
352      // then only insert exit block in to the output ExitBlocks vector.
353      // This ensures that same exit block is not inserted twice into
354      // ExitBlocks vector.
355      if (BB != FirstPred)
356        continue;
357
358      // If a terminator has more then two successors, for example SwitchInst,
359      // then it is possible that there are multiple edges from current block
360      // to one exit block.
361      if (std::distance(succ_begin(BB), succ_end(BB)) <= 2) {
362        ExitBlocks.push_back(Successor);
363        continue;
364      }
365
366      // In case of multiple edges from current block to exit block, collect
367      // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
368      // duplicate edges.
369      if (std::find(SwitchExitBlocks.begin(), SwitchExitBlocks.end(), Successor)
370          == SwitchExitBlocks.end()) {
371        SwitchExitBlocks.push_back(Successor);
372        ExitBlocks.push_back(Successor);
373      }
374    }
375  }
376}
377
378BasicBlock *Loop::getUniqueExitBlock() const {
379  SmallVector<BasicBlock *, 8> UniqueExitBlocks;
380  getUniqueExitBlocks(UniqueExitBlocks);
381  if (UniqueExitBlocks.size() == 1)
382    return UniqueExitBlocks[0];
383  return nullptr;
384}
385
386#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
387LLVM_DUMP_METHOD void Loop::dump() const {
388  print(dbgs());
389}
390#endif
391
392//===----------------------------------------------------------------------===//
393// UnloopUpdater implementation
394//
395
396namespace {
397/// Find the new parent loop for all blocks within the "unloop" whose last
398/// backedges has just been removed.
399class UnloopUpdater {
400  Loop &Unloop;
401  LoopInfo *LI;
402
403  LoopBlocksDFS DFS;
404
405  // Map unloop's immediate subloops to their nearest reachable parents. Nested
406  // loops within these subloops will not change parents. However, an immediate
407  // subloop's new parent will be the nearest loop reachable from either its own
408  // exits *or* any of its nested loop's exits.
409  DenseMap<Loop*, Loop*> SubloopParents;
410
411  // Flag the presence of an irreducible backedge whose destination is a block
412  // directly contained by the original unloop.
413  bool FoundIB;
414
415public:
416  UnloopUpdater(Loop *UL, LoopInfo *LInfo) :
417    Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
418
419  void updateBlockParents();
420
421  void removeBlocksFromAncestors();
422
423  void updateSubloopParents();
424
425protected:
426  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
427};
428} // end anonymous namespace
429
430/// Update the parent loop for all blocks that are directly contained within the
431/// original "unloop".
432void UnloopUpdater::updateBlockParents() {
433  if (Unloop.getNumBlocks()) {
434    // Perform a post order CFG traversal of all blocks within this loop,
435    // propagating the nearest loop from sucessors to predecessors.
436    LoopBlocksTraversal Traversal(DFS, LI);
437    for (BasicBlock *POI : Traversal) {
438
439      Loop *L = LI->getLoopFor(POI);
440      Loop *NL = getNearestLoop(POI, L);
441
442      if (NL != L) {
443        // For reducible loops, NL is now an ancestor of Unloop.
444        assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
445               "uninitialized successor");
446        LI->changeLoopFor(POI, NL);
447      }
448      else {
449        // Or the current block is part of a subloop, in which case its parent
450        // is unchanged.
451        assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
452      }
453    }
454  }
455  // Each irreducible loop within the unloop induces a round of iteration using
456  // the DFS result cached by Traversal.
457  bool Changed = FoundIB;
458  for (unsigned NIters = 0; Changed; ++NIters) {
459    assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
460
461    // Iterate over the postorder list of blocks, propagating the nearest loop
462    // from successors to predecessors as before.
463    Changed = false;
464    for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
465           POE = DFS.endPostorder(); POI != POE; ++POI) {
466
467      Loop *L = LI->getLoopFor(*POI);
468      Loop *NL = getNearestLoop(*POI, L);
469      if (NL != L) {
470        assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
471               "uninitialized successor");
472        LI->changeLoopFor(*POI, NL);
473        Changed = true;
474      }
475    }
476  }
477}
478
479/// Remove unloop's blocks from all ancestors below their new parents.
480void UnloopUpdater::removeBlocksFromAncestors() {
481  // Remove all unloop's blocks (including those in nested subloops) from
482  // ancestors below the new parent loop.
483  for (Loop::block_iterator BI = Unloop.block_begin(),
484         BE = Unloop.block_end(); BI != BE; ++BI) {
485    Loop *OuterParent = LI->getLoopFor(*BI);
486    if (Unloop.contains(OuterParent)) {
487      while (OuterParent->getParentLoop() != &Unloop)
488        OuterParent = OuterParent->getParentLoop();
489      OuterParent = SubloopParents[OuterParent];
490    }
491    // Remove blocks from former Ancestors except Unloop itself which will be
492    // deleted.
493    for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
494         OldParent = OldParent->getParentLoop()) {
495      assert(OldParent && "new loop is not an ancestor of the original");
496      OldParent->removeBlockFromLoop(*BI);
497    }
498  }
499}
500
501/// Update the parent loop for all subloops directly nested within unloop.
502void UnloopUpdater::updateSubloopParents() {
503  while (!Unloop.empty()) {
504    Loop *Subloop = *std::prev(Unloop.end());
505    Unloop.removeChildLoop(std::prev(Unloop.end()));
506
507    assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
508    if (Loop *Parent = SubloopParents[Subloop])
509      Parent->addChildLoop(Subloop);
510    else
511      LI->addTopLevelLoop(Subloop);
512  }
513}
514
515/// Return the nearest parent loop among this block's successors. If a successor
516/// is a subloop header, consider its parent to be the nearest parent of the
517/// subloop's exits.
518///
519/// For subloop blocks, simply update SubloopParents and return NULL.
520Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
521
522  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
523  // is considered uninitialized.
524  Loop *NearLoop = BBLoop;
525
526  Loop *Subloop = nullptr;
527  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
528    Subloop = NearLoop;
529    // Find the subloop ancestor that is directly contained within Unloop.
530    while (Subloop->getParentLoop() != &Unloop) {
531      Subloop = Subloop->getParentLoop();
532      assert(Subloop && "subloop is not an ancestor of the original loop");
533    }
534    // Get the current nearest parent of the Subloop exits, initially Unloop.
535    NearLoop =
536      SubloopParents.insert(std::make_pair(Subloop, &Unloop)).first->second;
537  }
538
539  succ_iterator I = succ_begin(BB), E = succ_end(BB);
540  if (I == E) {
541    assert(!Subloop && "subloop blocks must have a successor");
542    NearLoop = nullptr; // unloop blocks may now exit the function.
543  }
544  for (; I != E; ++I) {
545    if (*I == BB)
546      continue; // self loops are uninteresting
547
548    Loop *L = LI->getLoopFor(*I);
549    if (L == &Unloop) {
550      // This successor has not been processed. This path must lead to an
551      // irreducible backedge.
552      assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
553      FoundIB = true;
554    }
555    if (L != &Unloop && Unloop.contains(L)) {
556      // Successor is in a subloop.
557      if (Subloop)
558        continue; // Branching within subloops. Ignore it.
559
560      // BB branches from the original into a subloop header.
561      assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
562
563      // Get the current nearest parent of the Subloop's exits.
564      L = SubloopParents[L];
565      // L could be Unloop if the only exit was an irreducible backedge.
566    }
567    if (L == &Unloop) {
568      continue;
569    }
570    // Handle critical edges from Unloop into a sibling loop.
571    if (L && !L->contains(&Unloop)) {
572      L = L->getParentLoop();
573    }
574    // Remember the nearest parent loop among successors or subloop exits.
575    if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
576      NearLoop = L;
577  }
578  if (Subloop) {
579    SubloopParents[Subloop] = NearLoop;
580    return BBLoop;
581  }
582  return NearLoop;
583}
584
585LoopInfo::LoopInfo(const DominatorTreeBase<BasicBlock> &DomTree) {
586  analyze(DomTree);
587}
588
589void LoopInfo::markAsRemoved(Loop *Unloop) {
590  assert(!Unloop->isInvalid() && "Loop has already been removed");
591  Unloop->invalidate();
592  RemovedLoops.push_back(Unloop);
593
594  // First handle the special case of no parent loop to simplify the algorithm.
595  if (!Unloop->getParentLoop()) {
596    // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
597    for (Loop::block_iterator I = Unloop->block_begin(),
598                              E = Unloop->block_end();
599         I != E; ++I) {
600
601      // Don't reparent blocks in subloops.
602      if (getLoopFor(*I) != Unloop)
603        continue;
604
605      // Blocks no longer have a parent but are still referenced by Unloop until
606      // the Unloop object is deleted.
607      changeLoopFor(*I, nullptr);
608    }
609
610    // Remove the loop from the top-level LoopInfo object.
611    for (iterator I = begin();; ++I) {
612      assert(I != end() && "Couldn't find loop");
613      if (*I == Unloop) {
614        removeLoop(I);
615        break;
616      }
617    }
618
619    // Move all of the subloops to the top-level.
620    while (!Unloop->empty())
621      addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
622
623    return;
624  }
625
626  // Update the parent loop for all blocks within the loop. Blocks within
627  // subloops will not change parents.
628  UnloopUpdater Updater(Unloop, this);
629  Updater.updateBlockParents();
630
631  // Remove blocks from former ancestor loops.
632  Updater.removeBlocksFromAncestors();
633
634  // Add direct subloops as children in their new parent loop.
635  Updater.updateSubloopParents();
636
637  // Remove unloop from its parent loop.
638  Loop *ParentLoop = Unloop->getParentLoop();
639  for (Loop::iterator I = ParentLoop->begin();; ++I) {
640    assert(I != ParentLoop->end() && "Couldn't find loop");
641    if (*I == Unloop) {
642      ParentLoop->removeChildLoop(I);
643      break;
644    }
645  }
646}
647
648char LoopAnalysis::PassID;
649
650LoopInfo LoopAnalysis::run(Function &F, AnalysisManager<Function> &AM) {
651  // FIXME: Currently we create a LoopInfo from scratch for every function.
652  // This may prove to be too wasteful due to deallocating and re-allocating
653  // memory each time for the underlying map and vector datastructures. At some
654  // point it may prove worthwhile to use a freelist and recycle LoopInfo
655  // objects. I don't want to add that kind of complexity until the scope of
656  // the problem is better understood.
657  LoopInfo LI;
658  LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));
659  return LI;
660}
661
662PreservedAnalyses LoopPrinterPass::run(Function &F,
663                                       AnalysisManager<Function> &AM) {
664  AM.getResult<LoopAnalysis>(F).print(OS);
665  return PreservedAnalyses::all();
666}
667
668PrintLoopPass::PrintLoopPass() : OS(dbgs()) {}
669PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner)
670    : OS(OS), Banner(Banner) {}
671
672PreservedAnalyses PrintLoopPass::run(Loop &L, AnalysisManager<Loop> &) {
673  OS << Banner;
674  for (auto *Block : L.blocks())
675    if (Block)
676      Block->print(OS);
677    else
678      OS << "Printing <null> block";
679  return PreservedAnalyses::all();
680}
681
682//===----------------------------------------------------------------------===//
683// LoopInfo implementation
684//
685
686char LoopInfoWrapperPass::ID = 0;
687INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
688                      true, true)
689INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
690INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",
691                    true, true)
692
693bool LoopInfoWrapperPass::runOnFunction(Function &) {
694  releaseMemory();
695  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
696  return false;
697}
698
699void LoopInfoWrapperPass::verifyAnalysis() const {
700  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
701  // function each time verifyAnalysis is called is very expensive. The
702  // -verify-loop-info option can enable this. In order to perform some
703  // checking by default, LoopPass has been taught to call verifyLoop manually
704  // during loop pass sequences.
705  if (VerifyLoopInfo)
706    LI.verify();
707}
708
709void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
710  AU.setPreservesAll();
711  AU.addRequired<DominatorTreeWrapperPass>();
712}
713
714void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
715  LI.print(OS);
716}
717
718//===----------------------------------------------------------------------===//
719// LoopBlocksDFS implementation
720//
721
722/// Traverse the loop blocks and store the DFS result.
723/// Useful for clients that just want the final DFS result and don't need to
724/// visit blocks during the initial traversal.
725void LoopBlocksDFS::perform(LoopInfo *LI) {
726  LoopBlocksTraversal Traversal(*this, LI);
727  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
728         POE = Traversal.end(); POI != POE; ++POI) ;
729}
730