include/llvm/Analysis/LoopInfo.h

   1 //===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator --------*- C++ -*--=//
   2 //
   3 // This file defines the LoopInfo class that is used to identify natural loops
   4 // and determine the loop depth of various nodes of the CFG.  Note that natural
   5 // loops may actually be several loops that share the same header node...
   6 //
   7 // This analysis calculates the nesting structure of loops in a function.  For
   8 // each natural loop identified, this analysis identifies natural loops
   9 // contained entirely within the function, the basic blocks the make up the
  10 // loop, the nesting depth of the loop, and the successor blocks of the loop.
  11 //
  12 // It can calculate on the fly a variety of different bits of information, such
  13 // as whether there is a preheader for the loop, the number of back edges to the
  14 // header, and whether or not a particular block branches out of the loop.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #ifndef LLVM_ANALYSIS_LOOP_INFO_H
  19 #define LLVM_ANALYSIS_LOOP_INFO_H
  20
  21 #include "llvm/Pass.h"
  22 #include <set>
  23
  24 class DominatorSet;
  25 class LoopInfo;
  26
  27 //===----------------------------------------------------------------------===//
  28 /// Loop class - Instances of this class are used to represent loops that are
  29 /// detected in the flow graph
  30 ///
  31 class Loop {
  32   Loop *ParentLoop;
  33   std::vector<Loop*> SubLoops;       // Loops contained entirely within this one
  34   std::vector<BasicBlock *> Blocks;  // First entry is the header node
  35   std::vector<BasicBlock *> ExitBlocks; // Reachable blocks outside the loop
  36   unsigned LoopDepth;                // Nesting depth of this loop
  37
  38   Loop(const Loop &);                  // DO NOT IMPLEMENT
  39   const Loop &operator=(const Loop &); // DO NOT IMPLEMENT
  40 public:
  41
  42   inline unsigned getLoopDepth() const { return LoopDepth; }
  43   inline BasicBlock *getHeader() const { return Blocks.front(); }
  44   inline Loop *getParentLoop() const { return ParentLoop; }
  45
  46   /// contains - Return true of the specified basic block is in this loop
  47   bool contains(const BasicBlock *BB) const;
  48
  49   /// getSubLoops - Return the loops contained entirely within this loop
  50   ///
  51   const std::vector<Loop*> &getSubLoops() const { return SubLoops; }
  52
  53   /// getBlocks - Get a list of the basic blocks which make up this loop.
  54   ///
  55   const std::vector<BasicBlock*> &getBlocks() const { return Blocks; }
  56
  57   /// getExitBlocks - Return all of the successor blocks of this loop.  These
  58   /// are the blocks _outside of the current loop_ which are branched to.
  59   ///
  60   const std::vector<BasicBlock*> &getExitBlocks() const { return ExitBlocks; }
  61
  62   /// isLoopExit - True if terminator in the block can branch to another block
  63   /// that is outside of the current loop.  The reached block should be in the
  64   /// ExitBlocks list.
  65   ///
  66   bool isLoopExit(const BasicBlock *BB) const;
  67
  68   /// getNumBackEdges - Calculate the number of back edges to the loop header
  69   ///
  70   unsigned getNumBackEdges() const;
  71
  72   /// hasExitBlock - Return true if the current loop has the specified block as
  73   /// an exit block...
  74   bool hasExitBlock(BasicBlock *BB) const {
  75     for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
  76       if (ExitBlocks[i] == BB)
  77         return true;
  78     return false;
  79   }
  80
  81   /// getLoopPreheader - If there is a preheader for this loop, return it.  A
  82   /// loop has a preheader if there is only one edge to the header of the loop
  83   /// from outside of the loop.  If this is the case, the block branching to the
  84   /// header of the loop is the preheader node.  The "preheaders" pass can be
  85   /// "Required" to ensure that there is always a preheader node for every loop.
  86   ///
  87   /// This method returns null if there is no preheader for the loop (either
  88   /// because the loop is dead or because multiple blocks branch to the header
  89   /// node of this loop).
  90   ///
  91   BasicBlock *getLoopPreheader() const;
  92
  93   /// addBasicBlockToLoop - This method is used by other analyses to update loop
  94   /// information.  NewBB is set to be a new member of the current loop.
  95   /// Because of this, it is added as a member of all parent loops, and is added
  96   /// to the specified LoopInfo object as being in the current basic block.  It
  97   /// is not valid to replace the loop header with this method.
  98   ///
  99   void addBasicBlockToLoop(BasicBlock *NewBB, LoopInfo &LI);
 100
 101   /// changeExitBlock - This method is used to update loop information.  All
 102   /// instances of the specified Old basic block are removed from the exit list
 103   /// and replaced with New.
 104   ///
 105   void changeExitBlock(BasicBlock *Old, BasicBlock *New);
 106
 107   void print(std::ostream &O) const;
 108 private:
 109   friend class LoopInfo;
 110   inline Loop(BasicBlock *BB) : ParentLoop(0) {
 111     Blocks.push_back(BB); LoopDepth = 0;
 112   }
 113   ~Loop() {
 114     for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
 115       delete SubLoops[i];
 116   }
 117
 118   void setLoopDepth(unsigned Level) {
 119     LoopDepth = Level;
 120     for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
 121       SubLoops[i]->setLoopDepth(Level+1);
 122   }
 123 };
 124
 125
 126
 127 //===----------------------------------------------------------------------===//
 128 /// LoopInfo - This class builds and contains all of the top level loop
 129 /// structures in the specified function.
 130 ///
 131 class LoopInfo : public FunctionPass {
 132   // BBMap - Mapping of basic blocks to the inner most loop they occur in
 133   std::map<BasicBlock*, Loop*> BBMap;
 134   std::vector<Loop*> TopLevelLoops;
 135   friend class Loop;
 136 public:
 137   ~LoopInfo() { releaseMemory(); }
 138
 139   const std::vector<Loop*> &getTopLevelLoops() const { return TopLevelLoops; }
 140
 141   /// getLoopFor - Return the inner most loop that BB lives in.  If a basic
 142   /// block is in no loop (for example the entry node), null is returned.
 143   ///
 144   const Loop *getLoopFor(const BasicBlock *BB) const {
 145     std::map<BasicBlock *, Loop*>::const_iterator I=BBMap.find((BasicBlock*)BB);
 146     return I != BBMap.end() ? I->second : 0;
 147   }
 148
 149   /// operator[] - same as getLoopFor...
 150   ///
 151   inline const Loop *operator[](const BasicBlock *BB) const {
 152     return getLoopFor(BB);
 153   }
 154
 155   /// getLoopDepth - Return the loop nesting level of the specified block...
 156   ///
 157   unsigned getLoopDepth(const BasicBlock *BB) const {
 158     const Loop *L = getLoopFor(BB);
 159     return L ? L->getLoopDepth() : 0;
 160   }
 161
 162   // isLoopHeader - True if the block is a loop header node
 163   bool isLoopHeader(BasicBlock *BB) const {
 164     return getLoopFor(BB)->getHeader() == BB;
 165   }
 166
 167   /// runOnFunction - Calculate the natural loop information.
 168   ///
 169   virtual bool runOnFunction(Function &F);
 170
 171   virtual void releaseMemory();
 172   void print(std::ostream &O) const;
 173
 174   /// getAnalysisUsage - Requires dominator sets
 175   ///
 176   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 177
 178   static void stub();  // Noop
 179 private:
 180   void Calculate(const DominatorSet &DS);
 181   Loop *ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS);
 182 };
 183
 184
 185 // Make sure that any clients of this file link in LoopInfo.cpp
 186 static IncludeFile
 187 LOOP_INFO_INCLUDE_FILE((void*)&LoopInfo::stub);
 188
 189 #endif