LoopInfo.h revision 97f51a3024a72ef8500e95b90e6361e6783160fd
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 the 5// loops identified may actually be several natural loops that share the same 6// header node... not just a single natural loop. 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef LLVM_ANALYSIS_LOOP_INFO_H 11#define LLVM_ANALYSIS_LOOP_INFO_H 12 13#include "llvm/Pass.h" 14#include <set> 15 16class DominatorSet; 17class LoopInfo; 18 19//===----------------------------------------------------------------------===// 20// Loop class - Instances of this class are used to represent loops that are 21// detected in the flow graph 22// 23class Loop { 24 Loop *ParentLoop; 25 std::vector<BasicBlock *> Blocks; // First entry is the header node 26 std::vector<Loop*> SubLoops; // Loops contained entirely within this one 27 unsigned LoopDepth; // Nesting depth of this loop 28 29 Loop(const Loop &); // DO NOT IMPLEMENT 30 const Loop &operator=(const Loop &); // DO NOT IMPLEMENT 31public: 32 33 inline unsigned getLoopDepth() const { return LoopDepth; } 34 inline BasicBlock *getHeader() const { return Blocks.front(); } 35 36 // contains - Return true of the specified basic block is in this loop 37 bool contains(const BasicBlock *BB) const; 38 39 // getSubLoops - Return the loops contained entirely within this loop 40 inline const std::vector<Loop*> &getSubLoops() const { return SubLoops; } 41 inline const std::vector<BasicBlock*> &getBlocks() const { return Blocks; } 42 43 void print(std::ostream &O) const; 44private: 45 friend class LoopInfo; 46 inline Loop(BasicBlock *BB) { Blocks.push_back(BB); LoopDepth = 0; } 47 ~Loop() { 48 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 49 delete SubLoops[i]; 50 } 51 52 void setLoopDepth(unsigned Level) { 53 LoopDepth = Level; 54 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 55 SubLoops[i]->setLoopDepth(Level+1); 56 } 57}; 58 59 60 61//===----------------------------------------------------------------------===// 62// LoopInfo - This class builds and contains all of the top level loop 63// structures in the specified function. 64// 65class LoopInfo : public FunctionPass { 66 // BBMap - Mapping of basic blocks to the inner most loop they occur in 67 std::map<BasicBlock*, Loop*> BBMap; 68 std::vector<Loop*> TopLevelLoops; 69public: 70 static AnalysisID ID; // LoopInfo Analysis ID 71 72 // LoopInfo ctor - Calculate the natural loop information for a CFG 73 ~LoopInfo() { releaseMemory(); } 74 75 const std::vector<Loop*> &getTopLevelLoops() const { return TopLevelLoops; } 76 77 // getLoopFor - Return the inner most loop that BB lives in. If a basic block 78 // is in no loop (for example the entry node), null is returned. 79 // 80 const Loop *getLoopFor(const BasicBlock *BB) const { 81 std::map<BasicBlock *, Loop*>::const_iterator I=BBMap.find((BasicBlock*)BB); 82 return I != BBMap.end() ? I->second : 0; 83 } 84 inline const Loop *operator[](const BasicBlock *BB) const { 85 return getLoopFor(BB); 86 } 87 88 // getLoopDepth - Return the loop nesting level of the specified block... 89 unsigned getLoopDepth(const BasicBlock *BB) const { 90 const Loop *L = getLoopFor(BB); 91 return L ? L->getLoopDepth() : 0; 92 } 93 94#if 0 95 // isLoopHeader - True if the block is a loop header node 96 bool isLoopHeader(BasicBlock *BB) const { 97 return getLoopFor(BB)->getHeader() == BB; 98 } 99 // isLoopEnd - True if block jumps to loop entry 100 bool isLoopEnd(BasicBlock *BB) const; 101 // isLoopExit - True if block is the loop exit 102 bool isLoopExit(BasicBlock *BB) const; 103#endif 104 105 // runOnFunction - Pass framework implementation 106 virtual bool runOnFunction(Function &F); 107 108 virtual void releaseMemory(); 109 void print(std::ostream &O) const; 110 111 // getAnalysisUsage - Provide loop info, require dominator set 112 // 113 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 114 115private: 116 void Calculate(const DominatorSet &DS); 117 Loop *ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS); 118}; 119 120#endif 121