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