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 "Support/GraphTraits.h"
  23 #include <set>
  24
  25 class DominatorSet;
  26 class LoopInfo;
  27
  28 //===----------------------------------------------------------------------===//
  29 /// Loop class - Instances of this class are used to represent loops that are
  30 /// detected in the flow graph
  31 ///
  32 class Loop {
  33   Loop *ParentLoop;
  34   std::vector<Loop*> SubLoops;       // Loops contained entirely within this one
  35   std::vector<BasicBlock*> Blocks;   // First entry is the header node
  36   std::vector<BasicBlock*> ExitBlocks; // Reachable blocks outside the loop
  37   unsigned LoopDepth;                // Nesting depth of this loop
  38
  39   Loop(const Loop &);                  // DO NOT IMPLEMENT
  40   const Loop &operator=(const Loop &); // DO NOT IMPLEMENT
  41 public:
  42
  43   unsigned getLoopDepth() const { return LoopDepth; }
  44   BasicBlock *getHeader() const { return Blocks.front(); }
  45   Loop *getParentLoop() const { return ParentLoop; }
  46
  47   /// contains - Return true of the specified basic block is in this loop
  48   bool contains(const BasicBlock *BB) const;
  49
  50   /// getSubLoops - Return the loops contained entirely within this loop
  51   ///
  52   const std::vector<Loop*> &getSubLoops() const { return SubLoops; }
  53
  54   /// getBlocks - Get a list of the basic blocks which make up this loop.
  55   ///
  56   const std::vector<BasicBlock*> &getBlocks() const { return Blocks; }
  57
  58   /// getExitBlocks - Return all of the successor blocks of this loop.  These
  59   /// are the blocks _outside of the current loop_ which are branched to.
  60   ///
  61   const std::vector<BasicBlock*> &getExitBlocks() const { return ExitBlocks; }
  62
  63   /// isLoopExit - True if terminator in the block can branch to another block
  64   /// that is outside of the current loop.  The reached block should be in the
  65   /// ExitBlocks list.
  66   ///
  67   bool isLoopExit(const BasicBlock *BB) const;
  68
  69   /// getNumBackEdges - Calculate the number of back edges to the loop header
  70   ///
  71   unsigned getNumBackEdges() const;
  72
  73   /// hasExitBlock - Return true if the current loop has the specified block as
  74   /// an exit block...
  75   bool hasExitBlock(BasicBlock *BB) const {
  76     for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
  77       if (ExitBlocks[i] == BB)
  78         return true;
  79     return false;
  80   }
  81
  82   /// getLoopPreheader - If there is a preheader for this loop, return it.  A
  83   /// loop has a preheader if there is only one edge to the header of the loop
  84   /// from outside of the loop.  If this is the case, the block branching to the
  85   /// header of the loop is the preheader node.  The "preheaders" pass can be
  86   /// "Required" to ensure that there is always a preheader node for every loop.
  87   ///
  88   /// This method returns null if there is no preheader for the loop (either
  89   /// because the loop is dead or because multiple blocks branch to the header
  90   /// node of this loop).
  91   ///
  92   BasicBlock *getLoopPreheader() const;
  93
  94   /// addBasicBlockToLoop - This method is used by other analyses to update loop
  95   /// information.  NewBB is set to be a new member of the current loop.
  96   /// Because of this, it is added as a member of all parent loops, and is added
  97   /// to the specified LoopInfo object as being in the current basic block.  It
  98   /// is not valid to replace the loop header with this method.
  99   ///
 100   void addBasicBlockToLoop(BasicBlock *NewBB, LoopInfo &LI);
 101
 102   /// changeExitBlock - This method is used to update loop information.  All
 103   /// instances of the specified Old basic block are removed from the exit list
 104   /// and replaced with New.
 105   ///
 106   void changeExitBlock(BasicBlock *Old, BasicBlock *New);
 107
 108   void print(std::ostream &O, unsigned Depth = 0) const;
 109   void dump() const;
 110 private:
 111   friend class LoopInfo;
 112   inline Loop(BasicBlock *BB) : ParentLoop(0) {
 113     Blocks.push_back(BB); LoopDepth = 0;
 114   }
 115   ~Loop() {
 116     for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
 117       delete SubLoops[i];
 118   }
 119
 120   void setLoopDepth(unsigned Level) {
 121     LoopDepth = Level;
 122     for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
 123       SubLoops[i]->setLoopDepth(Level+1);
 124   }
 125 };
 126
 127
 128
 129 //===----------------------------------------------------------------------===//
 130 /// LoopInfo - This class builds and contains all of the top level loop
 131 /// structures in the specified function.
 132 ///
 133 class LoopInfo : public FunctionPass {
 134   // BBMap - Mapping of basic blocks to the inner most loop they occur in
 135   std::map<BasicBlock*, Loop*> BBMap;
 136   std::vector<Loop*> TopLevelLoops;
 137   friend class Loop;
 138 public:
 139   ~LoopInfo() { releaseMemory(); }
 140
 141   const std::vector<Loop*> &getTopLevelLoops() const { return TopLevelLoops; }
 142
 143   /// getLoopFor - Return the inner most loop that BB lives in.  If a basic
 144   /// block is in no loop (for example the entry node), null is returned.
 145   ///
 146   const Loop *getLoopFor(const BasicBlock *BB) const {
 147     std::map<BasicBlock *, Loop*>::const_iterator I=BBMap.find((BasicBlock*)BB);
 148     return I != BBMap.end() ? I->second : 0;
 149   }
 150
 151   /// operator[] - same as getLoopFor...
 152   ///
 153   inline const Loop *operator[](const BasicBlock *BB) const {
 154     return getLoopFor(BB);
 155   }
 156
 157   /// getLoopDepth - Return the loop nesting level of the specified block...
 158   ///
 159   unsigned getLoopDepth(const BasicBlock *BB) const {
 160     const Loop *L = getLoopFor(BB);
 161     return L ? L->getLoopDepth() : 0;
 162   }
 163
 164   // isLoopHeader - True if the block is a loop header node
 165   bool isLoopHeader(BasicBlock *BB) const {
 166     return getLoopFor(BB)->getHeader() == BB;
 167   }
 168
 169   /// runOnFunction - Calculate the natural loop information.
 170   ///
 171   virtual bool runOnFunction(Function &F);
 172
 173   virtual void releaseMemory();
 174   void print(std::ostream &O) const;
 175
 176   /// getAnalysisUsage - Requires dominator sets
 177   ///
 178   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 179
 180   static void stub();  // Noop
 181 private:
 182   void Calculate(const DominatorSet &DS);
 183   Loop *ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS);
 184   void MoveSiblingLoopInto(Loop *NewChild, Loop *NewParent);
 185   void InsertLoopInto(Loop *L, Loop *Parent);
 186 };
 187
 188
 189 // Make sure that any clients of this file link in LoopInfo.cpp
 190 static IncludeFile
 191 LOOP_INFO_INCLUDE_FILE((void*)&LoopInfo::stub);
 192
 193 // Allow clients to walk the list of nested loops...
 194 template <> struct GraphTraits<const Loop*> {
 195   typedef const Loop NodeType;
 196   typedef std::vector<Loop*>::const_iterator ChildIteratorType;
 197
 198   static NodeType *getEntryNode(const Loop *L) { return L; }
 199   static inline ChildIteratorType child_begin(NodeType *N) {
 200     return N->getSubLoops().begin();
 201   }
 202   static inline ChildIteratorType child_end(NodeType *N) {
 203     return N->getSubLoops().end();
 204   }
 205 };
 206
 207 template <> struct GraphTraits<Loop*> {
 208   typedef Loop NodeType;
 209   typedef std::vector<Loop*>::const_iterator ChildIteratorType;
 210
 211   static NodeType *getEntryNode(Loop *L) { return L; }
 212   static inline ChildIteratorType child_begin(NodeType *N) {
 213     return N->getSubLoops().begin();
 214   }
 215   static inline ChildIteratorType child_end(NodeType *N) {
 216     return N->getSubLoops().end();
 217   }
 218 };
 219
 220 #endif