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