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