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