include/llvm/Analysis/LoopInfo.h

   1 //===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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 natural
  12 // loops may actually be several loops that share the same header node.
  13 //
  14 // This analysis calculates the nesting structure of loops in a function.  For
  15 // each natural loop identified, this analysis identifies natural loops
  16 // contained entirely within the loop and the basic blocks the make up the loop.
  17 //
  18 // It can calculate on the fly various bits of information, for example:
  19 //
  20 //  * whether there is a preheader for the loop
  21 //  * the number of back edges to the header
  22 //  * whether or not a particular block branches out of the loop
  23 //  * the successor blocks of the loop
  24 //  * the loop depth
  25 //  * the trip count
  26 //  * etc...
  27 //
  28 //===----------------------------------------------------------------------===//
  29
  30 #ifndef LLVM_ANALYSIS_LOOP_INFO_H
  31 #define LLVM_ANALYSIS_LOOP_INFO_H
  32
  33 #include "llvm/Pass.h"
  34 #include "llvm/Constants.h"
  35 #include "llvm/Instructions.h"
  36 #include "llvm/ADT/GraphTraits.h"
  37 #include "llvm/ADT/SmallPtrSet.h"
  38 #include "llvm/ADT/SmallVector.h"
  39 #include "llvm/Support/CFG.h"
  40 #include "llvm/Support/Streams.h"
  41 #include <algorithm>
  42 #include <ostream>
  43
  44 template<typename T>
  45 static void RemoveFromVector(std::vector<T*> &V, T *N) {
  46   typename std::vector<T*>::iterator I = std::find(V.begin(), V.end(), N);
  47   assert(I != V.end() && "N is not in this list!");
  48   V.erase(I);
  49 }
  50
  51 namespace llvm {
  52
  53 class DominatorTree;
  54 class LoopInfo;
  55 class PHINode;
  56 class Instruction;
  57
  58 //===----------------------------------------------------------------------===//
  59 /// LoopBase class - Instances of this class are used to represent loops that are
  60 /// detected in the flow graph
  61 ///
  62 template<class BlockT>
  63 class LoopBase {
  64   LoopBase<BlockT> *ParentLoop;
  65   std::vector<LoopBase<BlockT>*> SubLoops;       // Loops contained entirely within this one
  66   std::vector<BlockT*> Blocks;   // First entry is the header node
  67
  68   LoopBase(const LoopBase<BlockT> &);                  // DO NOT IMPLEMENT
  69   const LoopBase<BlockT> &operator=(const LoopBase<BlockT> &); // DO NOT IMPLEMENT
  70 public:
  71   /// Loop ctor - This creates an empty loop.
  72   LoopBase() : ParentLoop(0) {}
  73   ~LoopBase() {
  74     for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
  75       delete SubLoops[i];
  76   }
  77
  78   unsigned getLoopDepth() const {
  79     unsigned D = 0;
  80     for (const LoopBase<BlockT> *CurLoop = this; CurLoop;
  81          CurLoop = CurLoop->ParentLoop)
  82       ++D;
  83     return D;
  84   }
  85   BlockT *getHeader() const { return Blocks.front(); }
  86   LoopBase<BlockT> *getParentLoop() const { return ParentLoop; }
  87
  88   /// contains - Return true of the specified basic block is in this loop
  89   ///
  90   bool contains(const BlockT *BB) const {
  91     return std::find(Blocks.begin(), Blocks.end(), BB) != Blocks.end();
  92   }
  93
  94   /// iterator/begin/end - Return the loops contained entirely within this loop.
  95   ///
  96   const std::vector<LoopBase<BlockT>*> &getSubLoops() const { return SubLoops; }
  97   typedef typename std::vector<LoopBase<BlockT>*>::const_iterator iterator;
  98   iterator begin() const { return SubLoops.begin(); }
  99   iterator end() const { return SubLoops.end(); }
 100   bool empty() const { return SubLoops.empty(); }
 101
 102   /// getBlocks - Get a list of the basic blocks which make up this loop.
 103   ///
 104   const std::vector<BlockT*> &getBlocks() const { return Blocks; }
 105   typedef typename std::vector<BlockT*>::const_iterator block_iterator;
 106   block_iterator block_begin() const { return Blocks.begin(); }
 107   block_iterator block_end() const { return Blocks.end(); }
 108
 109   /// isLoopExit - True if terminator in the block can branch to another block
 110   /// that is outside of the current loop.
 111   ///
 112   bool isLoopExit(const BlockT *BB) const {
 113     for (succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
 114          SI != SE; ++SI) {
 115       if (!contains(*SI))
 116         return true;
 117     }
 118     return false;
 119   }
 120
 121   /// getNumBackEdges - Calculate the number of back edges to the loop header
 122   ///
 123   unsigned getNumBackEdges() const {
 124     unsigned NumBackEdges = 0;
 125     BlockT *H = getHeader();
 126
 127     for (pred_iterator I = pred_begin(H), E = pred_end(H); I != E; ++I)
 128       if (contains(*I))
 129         ++NumBackEdges;
 130
 131     return NumBackEdges;
 132   }
 133
 134   /// isLoopInvariant - Return true if the specified value is loop invariant
 135   ///
 136   bool isLoopInvariant(Value *V) const {
 137     if (Instruction *I = dyn_cast<Instruction>(V))
 138       return !contains(I->getParent());
 139     return true;  // All non-instructions are loop invariant
 140   }
 141
 142   //===--------------------------------------------------------------------===//
 143   // APIs for simple analysis of the loop.
 144   //
 145   // Note that all of these methods can fail on general loops (ie, there may not
 146   // be a preheader, etc).  For best success, the loop simplification and
 147   // induction variable canonicalization pass should be used to normalize loops
 148   // for easy analysis.  These methods assume canonical loops.
 149
 150   /// getExitingBlocks - Return all blocks inside the loop that have successors
 151   /// outside of the loop.  These are the blocks _inside of the current loop_
 152   /// which branch out.  The returned list is always unique.
 153   ///
 154   void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
 155     // Sort the blocks vector so that we can use binary search to do quick
 156     // lookups.
 157     SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
 158     std::sort(LoopBBs.begin(), LoopBBs.end());
 159
 160     for (typename std::vector<BlockT*>::const_iterator BI = Blocks.begin(),
 161          BE = Blocks.end(); BI != BE; ++BI)
 162       for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I)
 163         if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {
 164           // Not in current loop? It must be an exit block.
 165           ExitingBlocks.push_back(*BI);
 166           break;
 167         }
 168   }
 169
 170   /// getExitBlocks - Return all of the successor blocks of this loop.  These
 171   /// are the blocks _outside of the current loop_ which are branched to.
 172   ///
 173   void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
 174     // Sort the blocks vector so that we can use binary search to do quick
 175     // lookups.
 176     SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
 177     std::sort(LoopBBs.begin(), LoopBBs.end());
 178
 179     for (typename std::vector<BlockT*>::const_iterator BI = Blocks.begin(),
 180          BE = Blocks.end(); BI != BE; ++BI)
 181       for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I)
 182         if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
 183           // Not in current loop? It must be an exit block.
 184           ExitBlocks.push_back(*I);
 185   }
 186
 187   /// getUniqueExitBlocks - Return all unique successor blocks of this loop.
 188   /// These are the blocks _outside of the current loop_ which are branched to.
 189   /// This assumes that loop is in canonical form.
 190   ///
 191   void getUniqueExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
 192     // Sort the blocks vector so that we can use binary search to do quick
 193     // lookups.
 194     SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
 195     std::sort(LoopBBs.begin(), LoopBBs.end());
 196
 197     std::vector<BlockT*> switchExitBlocks;
 198
 199     for (typename std::vector<BlockT*>::const_iterator BI = Blocks.begin(),
 200          BE = Blocks.end(); BI != BE; ++BI) {
 201
 202       BlockT *current = *BI;
 203       switchExitBlocks.clear();
 204
 205       for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) {
 206         if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
 207       // If block is inside the loop then it is not a exit block.
 208           continue;
 209
 210         pred_iterator PI = pred_begin(*I);
 211         BlockT *firstPred = *PI;
 212
 213         // If current basic block is this exit block's first predecessor
 214         // then only insert exit block in to the output ExitBlocks vector.
 215         // This ensures that same exit block is not inserted twice into
 216         // ExitBlocks vector.
 217         if (current != firstPred)
 218           continue;
 219
 220         // If a terminator has more then two successors, for example SwitchInst,
 221         // then it is possible that there are multiple edges from current block
 222         // to one exit block.
 223         if (current->getTerminator()->getNumSuccessors() <= 2) {
 224           ExitBlocks.push_back(*I);
 225           continue;
 226         }
 227
 228         // In case of multiple edges from current block to exit block, collect
 229         // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
 230         // duplicate edges.
 231         if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I)
 232             == switchExitBlocks.end()) {
 233           switchExitBlocks.push_back(*I);
 234           ExitBlocks.push_back(*I);
 235         }
 236       }
 237     }
 238   }
 239
 240   /// getLoopPreheader - If there is a preheader for this loop, return it.  A
 241   /// loop has a preheader if there is only one edge to the header of the loop
 242   /// from outside of the loop.  If this is the case, the block branching to the
 243   /// header of the loop is the preheader node.
 244   ///
 245   /// This method returns null if there is no preheader for the loop.
 246   ///
 247   BlockT *getLoopPreheader() const {
 248     // Keep track of nodes outside the loop branching to the header...
 249     BlockT *Out = 0;
 250
 251     // Loop over the predecessors of the header node...
 252     BlockT *Header = getHeader();
 253     for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
 254          PI != PE; ++PI)
 255       if (!contains(*PI)) {     // If the block is not in the loop...
 256         if (Out && Out != *PI)
 257           return 0;             // Multiple predecessors outside the loop
 258         Out = *PI;
 259       }
 260
 261     // Make sure there is only one exit out of the preheader.
 262     assert(Out && "Header of loop has no predecessors from outside loop?");
 263     succ_iterator SI = succ_begin(Out);
 264     ++SI;
 265     if (SI != succ_end(Out))
 266       return 0;  // Multiple exits from the block, must not be a preheader.
 267
 268     // If there is exactly one preheader, return it.  If there was zero, then Out
 269     // is still null.
 270     return Out;
 271   }
 272
 273   /// getLoopLatch - If there is a latch block for this loop, return it.  A
 274   /// latch block is the canonical backedge for a loop.  A loop header in normal
 275   /// form has two edges into it: one from a preheader and one from a latch
 276   /// block.
 277   BlockT *getLoopLatch() const {
 278     BlockT *Header = getHeader();
 279     pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
 280     if (PI == PE) return 0;  // no preds?
 281
 282     BlockT *Latch = 0;
 283     if (contains(*PI))
 284       Latch = *PI;
 285     ++PI;
 286     if (PI == PE) return 0;  // only one pred?
 287
 288     if (contains(*PI)) {
 289       if (Latch) return 0;  // multiple backedges
 290       Latch = *PI;
 291     }
 292     ++PI;
 293     if (PI != PE) return 0;  // more than two preds
 294
 295     return Latch;
 296   }
 297
 298   /// getCanonicalInductionVariable - Check to see if the loop has a canonical
 299   /// induction variable: an integer recurrence that starts at 0 and increments
 300   /// by one each time through the loop.  If so, return the phi node that
 301   /// corresponds to it.
 302   ///
 303   PHINode *getCanonicalInductionVariable() const {
 304     BlockT *H = getHeader();
 305
 306     BlockT *Incoming = 0, *Backedge = 0;
 307     pred_iterator PI = pred_begin(H);
 308     assert(PI != pred_end(H) && "Loop must have at least one backedge!");
 309     Backedge = *PI++;
 310     if (PI == pred_end(H)) return 0;  // dead loop
 311     Incoming = *PI++;
 312     if (PI != pred_end(H)) return 0;  // multiple backedges?
 313
 314     if (contains(Incoming)) {
 315       if (contains(Backedge))
 316         return 0;
 317       std::swap(Incoming, Backedge);
 318     } else if (!contains(Backedge))
 319       return 0;
 320
 321     // Loop over all of the PHI nodes, looking for a canonical indvar.
 322     for (typename BlockT::iterator I = H->begin(); isa<PHINode>(I); ++I) {
 323       PHINode *PN = cast<PHINode>(I);
 324       if (Instruction *Inc =
 325           dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
 326         if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
 327           if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
 328             if (CI->equalsInt(1))
 329               return PN;
 330     }
 331     return 0;
 332   }
 333
 334   /// getCanonicalInductionVariableIncrement - Return the LLVM value that holds
 335   /// the canonical induction variable value for the "next" iteration of the
 336   /// loop.  This always succeeds if getCanonicalInductionVariable succeeds.
 337   ///
 338   Instruction *getCanonicalInductionVariableIncrement() const {
 339     if (PHINode *PN = getCanonicalInductionVariable()) {
 340       bool P1InLoop = contains(PN->getIncomingBlock(1));
 341       return cast<Instruction>(PN->getIncomingValue(P1InLoop));
 342     }
 343     return 0;
 344   }
 345
 346   /// getTripCount - Return a loop-invariant LLVM value indicating the number of
 347   /// times the loop will be executed.  Note that this means that the backedge
 348   /// of the loop executes N-1 times.  If the trip-count cannot be determined,
 349   /// this returns null.
 350   ///
 351   Value *getTripCount() const {
 352     // Canonical loops will end with a 'cmp ne I, V', where I is the incremented
 353     // canonical induction variable and V is the trip count of the loop.
 354     Instruction *Inc = getCanonicalInductionVariableIncrement();
 355     if (Inc == 0) return 0;
 356     PHINode *IV = cast<PHINode>(Inc->getOperand(0));
 357
 358     BlockT *BackedgeBlock =
 359             IV->getIncomingBlock(contains(IV->getIncomingBlock(1)));
 360
 361     if (BranchInst *BI = dyn_cast<BranchInst>(BackedgeBlock->getTerminator()))
 362       if (BI->isConditional()) {
 363         if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
 364           if (ICI->getOperand(0) == Inc)
 365             if (BI->getSuccessor(0) == getHeader()) {
 366               if (ICI->getPredicate() == ICmpInst::ICMP_NE)
 367                 return ICI->getOperand(1);
 368             } else if (ICI->getPredicate() == ICmpInst::ICMP_EQ) {
 369               return ICI->getOperand(1);
 370             }
 371         }
 372       }
 373
 374     return 0;
 375   }
 376
 377   /// isLCSSAForm - Return true if the Loop is in LCSSA form
 378   bool isLCSSAForm() const {
 379     // Sort the blocks vector so that we can use binary search to do quick
 380     // lookups.
 381     SmallPtrSet<BlockT*, 16> LoopBBs(block_begin(), block_end());
 382
 383     for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) {
 384       BlockT *BB = *BI;
 385       for (typename BlockT::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 386         for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
 387              ++UI) {
 388           BlockT *UserBB = cast<Instruction>(*UI)->getParent();
 389           if (PHINode *P = dyn_cast<PHINode>(*UI)) {
 390             unsigned OperandNo = UI.getOperandNo();
 391             UserBB = P->getIncomingBlock(OperandNo/2);
 392           }
 393
 394           // Check the current block, as a fast-path.  Most values are used in the
 395           // same block they are defined in.
 396           if (UserBB != BB && !LoopBBs.count(UserBB))
 397             return false;
 398         }
 399     }
 400
 401     return true;
 402   }
 403
 404   //===--------------------------------------------------------------------===//
 405   // APIs for updating loop information after changing the CFG
 406   //
 407
 408   /// addBasicBlockToLoop - This method is used by other analyses to update loop
 409   /// information.  NewBB is set to be a new member of the current loop.
 410   /// Because of this, it is added as a member of all parent loops, and is added
 411   /// to the specified LoopInfo object as being in the current basic block.  It
 412   /// is not valid to replace the loop header with this method.
 413   ///
 414   void addBasicBlockToLoop(BlockT *NewBB, LoopInfo &LI);
 415
 416   /// replaceChildLoopWith - This is used when splitting loops up.  It replaces
 417   /// the OldChild entry in our children list with NewChild, and updates the
 418   /// parent pointer of OldChild to be null and the NewChild to be this loop.
 419   /// This updates the loop depth of the new child.
 420   void replaceChildLoopWith(LoopBase<BlockT> *OldChild,
 421                             LoopBase<BlockT> *NewChild) {
 422     assert(OldChild->ParentLoop == this && "This loop is already broken!");
 423     assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
 424     typename std::vector<LoopBase<BlockT>*>::iterator I =
 425                           std::find(SubLoops.begin(), SubLoops.end(), OldChild);
 426     assert(I != SubLoops.end() && "OldChild not in loop!");
 427     *I = NewChild;
 428     OldChild->ParentLoop = 0;
 429     NewChild->ParentLoop = this;
 430   }
 431
 432   /// addChildLoop - Add the specified loop to be a child of this loop.  This
 433   /// updates the loop depth of the new child.
 434   ///
 435   void addChildLoop(LoopBase<BlockT> *NewChild) {
 436     assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
 437     NewChild->ParentLoop = this;
 438     SubLoops.push_back(NewChild);
 439   }
 440
 441   /// removeChildLoop - This removes the specified child from being a subloop of
 442   /// this loop.  The loop is not deleted, as it will presumably be inserted
 443   /// into another loop.
 444   LoopBase<BlockT> *removeChildLoop(iterator I) {
 445     assert(I != SubLoops.end() && "Cannot remove end iterator!");
 446     LoopBase<BlockT> *Child = *I;
 447     assert(Child->ParentLoop == this && "Child is not a child of this loop!");
 448     SubLoops.erase(SubLoops.begin()+(I-begin()));
 449     Child->ParentLoop = 0;
 450     return Child;
 451   }
 452
 453   /// addBlockEntry - This adds a basic block directly to the basic block list.
 454   /// This should only be used by transformations that create new loops.  Other
 455   /// transformations should use addBasicBlockToLoop.
 456   void addBlockEntry(BlockT *BB) {
 457     Blocks.push_back(BB);
 458   }
 459
 460   /// moveToHeader - This method is used to move BB (which must be part of this
 461   /// loop) to be the loop header of the loop (the block that dominates all
 462   /// others).
 463   void moveToHeader(BlockT *BB) {
 464     if (Blocks[0] == BB) return;
 465     for (unsigned i = 0; ; ++i) {
 466       assert(i != Blocks.size() && "Loop does not contain BB!");
 467       if (Blocks[i] == BB) {
 468         Blocks[i] = Blocks[0];
 469         Blocks[0] = BB;
 470         return;
 471       }
 472     }
 473   }
 474
 475   /// removeBlockFromLoop - This removes the specified basic block from the
 476   /// current loop, updating the Blocks as appropriate.  This does not update
 477   /// the mapping in the LoopInfo class.
 478   void removeBlockFromLoop(BlockT *BB) {
 479     RemoveFromVector(Blocks, BB);
 480   }
 481
 482   /// verifyLoop - Verify loop structure
 483   void verifyLoop() const {
 484 #ifndef NDEBUG
 485     assert (getHeader() && "Loop header is missing");
 486     assert (getLoopPreheader() && "Loop preheader is missing");
 487     assert (getLoopLatch() && "Loop latch is missing");
 488     for (typename std::vector<LoopBase<BlockT>*>::const_iterator I =
 489          SubLoops.begin(), E = SubLoops.end(); I != E; ++I)
 490       (*I)->verifyLoop();
 491 #endif
 492   }
 493
 494   void print(std::ostream &OS, unsigned Depth = 0) const {
 495     OS << std::string(Depth*2, ' ') << "Loop Containing: ";
 496
 497     for (unsigned i = 0; i < getBlocks().size(); ++i) {
 498       if (i) OS << ",";
 499       WriteAsOperand(OS, getBlocks()[i], false);
 500     }
 501     OS << "\n";
 502
 503     for (iterator I = begin(), E = end(); I != E; ++I)
 504       (*I)->print(OS, Depth+2);
 505   }
 506
 507   void print(std::ostream *O, unsigned Depth = 0) const {
 508     if (O) print(*O, Depth);
 509   }
 510
 511   void dump() const {
 512     print(cerr);
 513   }
 514
 515 private:
 516   friend class LoopInfo;
 517   LoopBase(BlockT *BB) : ParentLoop(0) {
 518     Blocks.push_back(BB);
 519   }
 520 };
 521
 522 typedef LoopBase<BasicBlock> Loop;
 523
 524
 525 //===----------------------------------------------------------------------===//
 526 /// LoopInfo - This class builds and contains all of the top level loop
 527 /// structures in the specified function.
 528 ///
 529 class LoopInfo : public FunctionPass {
 530   // BBMap - Mapping of basic blocks to the inner most loop they occur in
 531   std::map<BasicBlock*, Loop*> BBMap;
 532   std::vector<Loop*> TopLevelLoops;
 533   friend class LoopBase<BasicBlock>;
 534 public:
 535   static char ID; // Pass identification, replacement for typeid
 536
 537   LoopInfo() : FunctionPass(intptr_t(&ID)) {}
 538   ~LoopInfo() { releaseMemory(); }
 539
 540   /// iterator/begin/end - The interface to the top-level loops in the current
 541   /// function.
 542   ///
 543   typedef std::vector<Loop*>::const_iterator iterator;
 544   iterator begin() const { return TopLevelLoops.begin(); }
 545   iterator end() const { return TopLevelLoops.end(); }
 546
 547   /// getLoopFor - Return the inner most loop that BB lives in.  If a basic
 548   /// block is in no loop (for example the entry node), null is returned.
 549   ///
 550   Loop *getLoopFor(const BasicBlock *BB) const {
 551     std::map<BasicBlock *, Loop*>::const_iterator I=
 552       BBMap.find(const_cast<BasicBlock*>(BB));
 553     return I != BBMap.end() ? I->second : 0;
 554   }
 555
 556   /// operator[] - same as getLoopFor...
 557   ///
 558   const Loop *operator[](const BasicBlock *BB) const {
 559     return getLoopFor(BB);
 560   }
 561
 562   /// getLoopDepth - Return the loop nesting level of the specified block...
 563   ///
 564   unsigned getLoopDepth(const BasicBlock *BB) const {
 565     const Loop *L = getLoopFor(BB);
 566     return L ? L->getLoopDepth() : 0;
 567   }
 568
 569   // isLoopHeader - True if the block is a loop header node
 570   bool isLoopHeader(BasicBlock *BB) const {
 571     const Loop *L = getLoopFor(BB);
 572     return L && L->getHeader() == BB;
 573   }
 574
 575   /// runOnFunction - Calculate the natural loop information.
 576   ///
 577   virtual bool runOnFunction(Function &F);
 578
 579   virtual void releaseMemory();
 580
 581   void print(std::ostream &O, const Module* = 0) const;
 582   void print(std::ostream *O, const Module* M = 0) const {
 583     if (O) print(*O, M);
 584   }
 585
 586   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 587
 588   /// removeLoop - This removes the specified top-level loop from this loop info
 589   /// object.  The loop is not deleted, as it will presumably be inserted into
 590   /// another loop.
 591   Loop *removeLoop(iterator I);
 592
 593   /// changeLoopFor - Change the top-level loop that contains BB to the
 594   /// specified loop.  This should be used by transformations that restructure
 595   /// the loop hierarchy tree.
 596   void changeLoopFor(BasicBlock *BB, Loop *L);
 597
 598   /// changeTopLevelLoop - Replace the specified loop in the top-level loops
 599   /// list with the indicated loop.
 600   void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop);
 601
 602   /// addTopLevelLoop - This adds the specified loop to the collection of
 603   /// top-level loops.
 604   void addTopLevelLoop(Loop *New) {
 605     assert(New->getParentLoop() == 0 && "Loop already in subloop!");
 606     TopLevelLoops.push_back(New);
 607   }
 608
 609   /// removeBlock - This method completely removes BB from all data structures,
 610   /// including all of the Loop objects it is nested in and our mapping from
 611   /// BasicBlocks to loops.
 612   void removeBlock(BasicBlock *BB);
 613
 614 private:
 615   void Calculate(DominatorTree &DT);
 616   Loop *ConsiderForLoop(BasicBlock *BB, DominatorTree &DT);
 617   void MoveSiblingLoopInto(Loop *NewChild, Loop *NewParent);
 618   void InsertLoopInto(Loop *L, Loop *Parent);
 619 };
 620
 621
 622 // Allow clients to walk the list of nested loops...
 623 template <> struct GraphTraits<const Loop*> {
 624   typedef const Loop NodeType;
 625   typedef std::vector<Loop*>::const_iterator ChildIteratorType;
 626
 627   static NodeType *getEntryNode(const Loop *L) { return L; }
 628   static inline ChildIteratorType child_begin(NodeType *N) {
 629     return N->begin();
 630   }
 631   static inline ChildIteratorType child_end(NodeType *N) {
 632     return N->end();
 633   }
 634 };
 635
 636 template <> struct GraphTraits<Loop*> {
 637   typedef Loop NodeType;
 638   typedef std::vector<Loop*>::const_iterator ChildIteratorType;
 639
 640   static NodeType *getEntryNode(Loop *L) { return L; }
 641   static inline ChildIteratorType child_begin(NodeType *N) {
 642     return N->begin();
 643   }
 644   static inline ChildIteratorType child_end(NodeType *N) {
 645     return N->end();
 646   }
 647 };
 648
 649 template<class BlockT>
 650 void LoopBase<BlockT>::addBasicBlockToLoop(BlockT *NewBB, LoopInfo &LI) {
 651   assert((Blocks.empty() || LI[getHeader()] == this) &&
 652          "Incorrect LI specified for this loop!");
 653   assert(NewBB && "Cannot add a null basic block to the loop!");
 654   assert(LI[NewBB] == 0 && "BasicBlock already in the loop!");
 655
 656   // Add the loop mapping to the LoopInfo object...
 657   LI.BBMap[NewBB] = this;
 658
 659   // Add the basic block to this loop and all parent loops...
 660   LoopBase<BlockT> *L = this;
 661   while (L) {
 662     L->Blocks.push_back(NewBB);
 663     L = L->getParentLoop();
 664   }
 665 }
 666
 667 } // End llvm namespace
 668
 669 // Make sure that any clients of this file link in LoopInfo.cpp
 670 FORCE_DEFINING_FILE_TO_BE_LINKED(LoopInfo)
 671
 672 #endif