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