LoopInfo.h revision 1db0a400370466e187ae06c96a1586c2c21409dd
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 25class DominatorSet; 26class LoopInfo; 27 28//===----------------------------------------------------------------------===// 29/// Loop class - Instances of this class are used to represent loops that are 30/// detected in the flow graph 31/// 32class 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 41public: 42 43 inline unsigned getLoopDepth() const { return LoopDepth; } 44 inline BasicBlock *getHeader() const { return Blocks.front(); } 45 inline 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) const; 109private: 110 friend class LoopInfo; 111 inline Loop(BasicBlock *BB) : ParentLoop(0) { 112 Blocks.push_back(BB); LoopDepth = 0; 113 } 114 ~Loop() { 115 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 116 delete SubLoops[i]; 117 } 118 119 void setLoopDepth(unsigned Level) { 120 LoopDepth = Level; 121 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 122 SubLoops[i]->setLoopDepth(Level+1); 123 } 124}; 125 126 127 128//===----------------------------------------------------------------------===// 129/// LoopInfo - This class builds and contains all of the top level loop 130/// structures in the specified function. 131/// 132class LoopInfo : public FunctionPass { 133 // BBMap - Mapping of basic blocks to the inner most loop they occur in 134 std::map<BasicBlock*, Loop*> BBMap; 135 std::vector<Loop*> TopLevelLoops; 136 friend class Loop; 137public: 138 ~LoopInfo() { releaseMemory(); } 139 140 const std::vector<Loop*> &getTopLevelLoops() const { return TopLevelLoops; } 141 142 /// getLoopFor - Return the inner most loop that BB lives in. If a basic 143 /// block is in no loop (for example the entry node), null is returned. 144 /// 145 const Loop *getLoopFor(const BasicBlock *BB) const { 146 std::map<BasicBlock *, Loop*>::const_iterator I=BBMap.find((BasicBlock*)BB); 147 return I != BBMap.end() ? I->second : 0; 148 } 149 150 /// operator[] - same as getLoopFor... 151 /// 152 inline const Loop *operator[](const BasicBlock *BB) const { 153 return getLoopFor(BB); 154 } 155 156 /// getLoopDepth - Return the loop nesting level of the specified block... 157 /// 158 unsigned getLoopDepth(const BasicBlock *BB) const { 159 const Loop *L = getLoopFor(BB); 160 return L ? L->getLoopDepth() : 0; 161 } 162 163 // isLoopHeader - True if the block is a loop header node 164 bool isLoopHeader(BasicBlock *BB) const { 165 return getLoopFor(BB)->getHeader() == BB; 166 } 167 168 /// runOnFunction - Calculate the natural loop information. 169 /// 170 virtual bool runOnFunction(Function &F); 171 172 virtual void releaseMemory(); 173 void print(std::ostream &O) const; 174 175 /// getAnalysisUsage - Requires dominator sets 176 /// 177 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 178 179 static void stub(); // Noop 180private: 181 void Calculate(const DominatorSet &DS); 182 Loop *ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS); 183}; 184 185 186// Make sure that any clients of this file link in LoopInfo.cpp 187static IncludeFile 188LOOP_INFO_INCLUDE_FILE((void*)&LoopInfo::stub); 189 190// Allow clients to walk the list of nested loops... 191template <> struct GraphTraits<const Loop*> { 192 typedef const Loop NodeType; 193 typedef std::vector<Loop*>::const_iterator ChildIteratorType; 194 195 static NodeType *getEntryNode(const Loop *L) { return L; } 196 static inline ChildIteratorType child_begin(NodeType *N) { 197 return N->getSubLoops().begin(); 198 } 199 static inline ChildIteratorType child_end(NodeType *N) { 200 return N->getSubLoops().end(); 201 } 202}; 203 204template <> struct GraphTraits<Loop*> { 205 typedef Loop NodeType; 206 typedef std::vector<Loop*>::const_iterator ChildIteratorType; 207 208 static NodeType *getEntryNode(Loop *L) { return L; } 209 static inline ChildIteratorType child_begin(NodeType *N) { 210 return N->getSubLoops().begin(); 211 } 212 static inline ChildIteratorType child_end(NodeType *N) { 213 return N->getSubLoops().end(); 214 } 215}; 216 217#endif 218