LoopInfo.h revision 7dd46b09c0f1b6b93f03a80953046d38697fba82
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 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; 110private: 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/// 133class 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; 138public: 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 181private: 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 190static IncludeFile 191LOOP_INFO_INCLUDE_FILE((void*)&LoopInfo::stub); 192 193// Allow clients to walk the list of nested loops... 194template <> 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 207template <> 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 221