LoopInfo.h revision 4e55b7d2c62de7efa0147e0579980de8b1df9123
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 32namespace llvm { 33 34class DominatorSet; 35class LoopInfo; 36class PHINode; 37 class Instruction; 38 39//===----------------------------------------------------------------------===// 40/// Loop class - Instances of this class are used to represent loops that are 41/// detected in the flow graph 42/// 43class Loop { 44 Loop *ParentLoop; 45 std::vector<Loop*> SubLoops; // Loops contained entirely within this one 46 std::vector<BasicBlock*> Blocks; // First entry is the header node 47 std::vector<BasicBlock*> ExitBlocks; // Reachable blocks outside the loop 48 unsigned LoopDepth; // Nesting depth of this loop 49 50 Loop(const Loop &); // DO NOT IMPLEMENT 51 const Loop &operator=(const Loop &); // DO NOT IMPLEMENT 52public: 53 /// Loop ctor - This creates an empty loop. 54 Loop() : ParentLoop(0), LoopDepth(0) { 55 } 56 ~Loop() { 57 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 58 delete SubLoops[i]; 59 } 60 61 unsigned getLoopDepth() const { return LoopDepth; } 62 BasicBlock *getHeader() const { return Blocks.front(); } 63 Loop *getParentLoop() const { return ParentLoop; } 64 65 /// contains - Return true of the specified basic block is in this loop 66 /// 67 bool contains(const BasicBlock *BB) const; 68 69 /// iterator/begin/end - Return the loops contained entirely within this loop. 70 /// 71 typedef std::vector<Loop*>::const_iterator iterator; 72 iterator begin() const { return SubLoops.begin(); } 73 iterator end() const { return SubLoops.end(); } 74 75 /// getBlocks - Get a list of the basic blocks which make up this loop. 76 /// 77 const std::vector<BasicBlock*> &getBlocks() const { return Blocks; } 78 79 /// getExitBlocks - Return all of the successor blocks of this loop. These 80 /// are the blocks _outside of the current loop_ which are branched to. 81 /// 82 const std::vector<BasicBlock*> &getExitBlocks() const { return ExitBlocks; } 83 84 /// isLoopExit - True if terminator in the block can branch to another block 85 /// that is outside of the current loop. The reached block should be in the 86 /// ExitBlocks list. 87 /// 88 bool isLoopExit(const BasicBlock *BB) const; 89 90 /// getNumBackEdges - Calculate the number of back edges to the loop header 91 /// 92 unsigned getNumBackEdges() const; 93 94 /// hasExitBlock - Return true if the current loop has the specified block as 95 /// an exit block... 96 bool hasExitBlock(BasicBlock *BB) const { 97 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 98 if (ExitBlocks[i] == BB) 99 return true; 100 return false; 101 } 102 103 //===--------------------------------------------------------------------===// 104 // APIs for simple analysis of the loop. 105 // 106 // Note that all of these methods can fail on general loops (ie, there may not 107 // be a preheader, etc). For best success, the loop simplification and 108 // induction variable canonicalization pass should be used to normalize loops 109 // for easy analysis. These methods assume canonical loops. 110 111 /// getLoopPreheader - If there is a preheader for this loop, return it. A 112 /// loop has a preheader if there is only one edge to the header of the loop 113 /// from outside of the loop. If this is the case, the block branching to the 114 /// header of the loop is the preheader node. 115 /// 116 /// This method returns null if there is no preheader for the loop. 117 /// 118 BasicBlock *getLoopPreheader() const; 119 120 /// getCanonicalInductionVariable - Check to see if the loop has a canonical 121 /// induction variable: an integer recurrence that starts at 0 and increments 122 /// by one each time through the loop. If so, return the phi node that 123 /// corresponds to it. 124 /// 125 PHINode *getCanonicalInductionVariable() const; 126 127 /// getCanonicalInductionVariableIncrement - Return the LLVM value that holds 128 /// the canonical induction variable value for the "next" iteration of the 129 /// loop. This always succeeds if getCanonicalInductionVariable succeeds. 130 /// 131 Instruction *getCanonicalInductionVariableIncrement() const; 132 133 /// getTripCount - Return a loop-invariant LLVM value indicating the number of 134 /// times the loop will be executed. Note that this means that the backedge 135 /// of the loop executes N-1 times. If the trip-count cannot be determined, 136 /// this returns null. 137 /// 138 Value *getTripCount() const; 139 140 //===--------------------------------------------------------------------===// 141 // APIs for updating loop information after changing the CFG 142 // 143 144 /// addBasicBlockToLoop - This method is used by other analyses to update loop 145 /// information. NewBB is set to be a new member of the current loop. 146 /// Because of this, it is added as a member of all parent loops, and is added 147 /// to the specified LoopInfo object as being in the current basic block. It 148 /// is not valid to replace the loop header with this method. 149 /// 150 void addBasicBlockToLoop(BasicBlock *NewBB, LoopInfo &LI); 151 152 /// changeExitBlock - This method is used to update loop information. All 153 /// instances of the specified Old basic block are removed from the exit list 154 /// and replaced with New. 155 /// 156 void changeExitBlock(BasicBlock *Old, BasicBlock *New); 157 158 /// replaceChildLoopWith - This is used when splitting loops up. It replaces 159 /// the OldChild entry in our children list with NewChild, and updates the 160 /// parent pointer of OldChild to be null and the NewChild to be this loop. 161 /// This updates the loop depth of the new child. 162 void replaceChildLoopWith(Loop *OldChild, Loop *NewChild); 163 164 /// addChildLoop - Add the specified loop to be a child of this loop. This 165 /// updates the loop depth of the new child. 166 /// 167 void addChildLoop(Loop *NewChild); 168 169 /// removeChildLoop - This removes the specified child from being a subloop of 170 /// this loop. The loop is not deleted, as it will presumably be inserted 171 /// into another loop. 172 Loop *removeChildLoop(iterator OldChild); 173 174 /// addExitBlock - Add the specified exit block to the loop. 175 /// 176 void addExitBlock(BasicBlock *BB) { 177 ExitBlocks.push_back(BB); 178 } 179 180 /// addBlockEntry - This adds a basic block directly to the basic block list. 181 /// This should only be used by transformations that create new loops. Other 182 /// transformations should use addBasicBlockToLoop. 183 void addBlockEntry(BasicBlock *BB) { 184 Blocks.push_back(BB); 185 } 186 187 /// removeBlockFromLoop - This removes the specified basic block from the 188 /// current loop, updating the Blocks and ExitBlocks lists as appropriate. 189 /// This does not update the mapping in the LoopInfo class. 190 void removeBlockFromLoop(BasicBlock *BB); 191 192 void print(std::ostream &O, unsigned Depth = 0) const; 193 void dump() const; 194private: 195 friend class LoopInfo; 196 Loop(BasicBlock *BB) : ParentLoop(0) { 197 Blocks.push_back(BB); LoopDepth = 0; 198 } 199 void setLoopDepth(unsigned Level) { 200 LoopDepth = Level; 201 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 202 SubLoops[i]->setLoopDepth(Level+1); 203 } 204}; 205 206 207 208//===----------------------------------------------------------------------===// 209/// LoopInfo - This class builds and contains all of the top level loop 210/// structures in the specified function. 211/// 212class LoopInfo : public FunctionPass { 213 // BBMap - Mapping of basic blocks to the inner most loop they occur in 214 std::map<BasicBlock*, Loop*> BBMap; 215 std::vector<Loop*> TopLevelLoops; 216 friend class Loop; 217public: 218 ~LoopInfo() { releaseMemory(); } 219 220 /// iterator/begin/end - The interface to the top-level loops in the current 221 /// function. 222 /// 223 typedef std::vector<Loop*>::const_iterator iterator; 224 iterator begin() const { return TopLevelLoops.begin(); } 225 iterator end() const { return TopLevelLoops.end(); } 226 227 /// getLoopFor - Return the inner most loop that BB lives in. If a basic 228 /// block is in no loop (for example the entry node), null is returned. 229 /// 230 const Loop *getLoopFor(const BasicBlock *BB) const { 231 std::map<BasicBlock *, Loop*>::const_iterator I=BBMap.find((BasicBlock*)BB); 232 return I != BBMap.end() ? I->second : 0; 233 } 234 235 /// operator[] - same as getLoopFor... 236 /// 237 inline const Loop *operator[](const BasicBlock *BB) const { 238 return getLoopFor(BB); 239 } 240 241 /// getLoopDepth - Return the loop nesting level of the specified block... 242 /// 243 unsigned getLoopDepth(const BasicBlock *BB) const { 244 const Loop *L = getLoopFor(BB); 245 return L ? L->getLoopDepth() : 0; 246 } 247 248 // isLoopHeader - True if the block is a loop header node 249 bool isLoopHeader(BasicBlock *BB) const { 250 return getLoopFor(BB)->getHeader() == BB; 251 } 252 253 /// runOnFunction - Calculate the natural loop information. 254 /// 255 virtual bool runOnFunction(Function &F); 256 257 virtual void releaseMemory(); 258 void print(std::ostream &O) const; 259 260 /// getAnalysisUsage - Requires dominator sets 261 /// 262 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 263 264 /// removeLoop - This removes the specified top-level loop from this loop info 265 /// object. The loop is not deleted, as it will presumably be inserted into 266 /// another loop. 267 Loop *removeLoop(iterator I); 268 269 /// changeLoopFor - Change the top-level loop that contains BB to the 270 /// specified loop. This should be used by transformations that restructure 271 /// the loop hierarchy tree. 272 void changeLoopFor(BasicBlock *BB, Loop *L); 273 274 /// changeTopLevelLoop - Replace the specified loop in the top-level loops 275 /// list with the indicated loop. 276 void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop); 277 278 static void stub(); // Noop 279private: 280 void Calculate(const DominatorSet &DS); 281 Loop *ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS); 282 void MoveSiblingLoopInto(Loop *NewChild, Loop *NewParent); 283 void InsertLoopInto(Loop *L, Loop *Parent); 284}; 285 286 287// Make sure that any clients of this file link in LoopInfo.cpp 288static IncludeFile 289LOOP_INFO_INCLUDE_FILE((void*)&LoopInfo::stub); 290 291// Allow clients to walk the list of nested loops... 292template <> struct GraphTraits<const Loop*> { 293 typedef const Loop NodeType; 294 typedef std::vector<Loop*>::const_iterator ChildIteratorType; 295 296 static NodeType *getEntryNode(const Loop *L) { return L; } 297 static inline ChildIteratorType child_begin(NodeType *N) { 298 return N->begin(); 299 } 300 static inline ChildIteratorType child_end(NodeType *N) { 301 return N->end(); 302 } 303}; 304 305template <> struct GraphTraits<Loop*> { 306 typedef Loop NodeType; 307 typedef std::vector<Loop*>::const_iterator ChildIteratorType; 308 309 static NodeType *getEntryNode(Loop *L) { return L; } 310 static inline ChildIteratorType child_begin(NodeType *N) { 311 return N->begin(); 312 } 313 static inline ChildIteratorType child_end(NodeType *N) { 314 return N->end(); 315 } 316}; 317 318} // End llvm namespace 319 320#endif 321