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