MachineLoopInfo.h revision d68a07650cdb2e18f18f362ba533459aa10e01b6
1//===- llvm/CodeGen/MachineLoopInfo.h - Natural Loop Calculator -*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the MachineLoopInfo class that is used to identify natural 11// loops and determine the loop depth of various nodes of the CFG. Note that 12// natural 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_CODEGEN_MACHINE_LOOP_INFO_H 31#define LLVM_CODEGEN_MACHINE_LOOP_INFO_H 32 33#include "llvm/CodeGen/MachineFunctionPass.h" 34#include "llvm/Analysis/LoopInfo.h" 35 36namespace llvm { 37 38// Provide overrides for Loop methods that don't make sense for machine loops. 39template<> inline 40PHINode *LoopBase<MachineBasicBlock>::getCanonicalInductionVariable() const { 41 assert(0 && "getCanonicalInductionVariable not supported for machine loops!"); 42 return 0; 43} 44 45template<> inline Instruction* 46LoopBase<MachineBasicBlock>::getCanonicalInductionVariableIncrement() const { 47 assert(0 && 48 "getCanonicalInductionVariableIncrement not supported for machine loops!"); 49 return 0; 50} 51 52template<> 53inline bool LoopBase<MachineBasicBlock>::isLoopInvariant(Value *V) const { 54 assert(0 && "isLoopInvariant not supported for machine loops!"); 55 return false; 56} 57 58template<> 59inline Value *LoopBase<MachineBasicBlock>::getTripCount() const { 60 assert(0 && "getTripCount not supported for machine loops!"); 61 return 0; 62} 63 64template<> 65inline bool LoopBase<MachineBasicBlock>::isLCSSAForm() const { 66 assert(0 && "isLCSSAForm not supported for machine loops"); 67 return false; 68} 69 70typedef LoopBase<MachineBasicBlock> MachineLoop; 71 72class MachineLoopInfo : public MachineFunctionPass { 73 LoopInfoBase<MachineBasicBlock>* LI; 74 friend class LoopBase<MachineBasicBlock>; 75 76 LoopInfoBase<MachineBasicBlock>& getBase() { return *LI; } 77public: 78 static char ID; // Pass identification, replacement for typeid 79 80 MachineLoopInfo() : MachineFunctionPass(intptr_t(&ID)) { 81 LI = new LoopInfoBase<MachineBasicBlock>(); 82 } 83 84 ~MachineLoopInfo() { delete LI; } 85 86 /// iterator/begin/end - The interface to the top-level loops in the current 87 /// function. 88 /// 89 typedef std::vector<MachineLoop*>::const_iterator iterator; 90 inline iterator begin() const { return LI->begin(); } 91 inline iterator end() const { return LI->end(); } 92 bool empty() const { return LI->empty(); } 93 94 /// getLoopFor - Return the inner most loop that BB lives in. If a basic 95 /// block is in no loop (for example the entry node), null is returned. 96 /// 97 inline MachineLoop *getLoopFor(const MachineBasicBlock *BB) const { 98 return LI->getLoopFor(BB); 99 } 100 101 /// operator[] - same as getLoopFor... 102 /// 103 inline const MachineLoop *operator[](const MachineBasicBlock *BB) const { 104 return LI->getLoopFor(BB); 105 } 106 107 /// getLoopDepth - Return the loop nesting level of the specified block... 108 /// 109 inline unsigned getLoopDepth(const MachineBasicBlock *BB) const { 110 return LI->getLoopDepth(BB); 111 } 112 113 // isLoopHeader - True if the block is a loop header node 114 inline bool isLoopHeader(MachineBasicBlock *BB) const { 115 return LI->isLoopHeader(BB); 116 } 117 118 /// runOnFunction - Calculate the natural loop information. 119 /// 120 virtual bool runOnMachineFunction(MachineFunction &F); 121 122 virtual void releaseMemory() { LI->releaseMemory(); } 123 124 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 125 126 /// removeLoop - This removes the specified top-level loop from this loop info 127 /// object. The loop is not deleted, as it will presumably be inserted into 128 /// another loop. 129 inline MachineLoop *removeLoop(iterator I) { return LI->removeLoop(I); } 130 131 /// changeLoopFor - Change the top-level loop that contains BB to the 132 /// specified loop. This should be used by transformations that restructure 133 /// the loop hierarchy tree. 134 inline void changeLoopFor(MachineBasicBlock *BB, MachineLoop *L) { 135 LI->changeLoopFor(BB, L); 136 } 137 138 /// changeTopLevelLoop - Replace the specified loop in the top-level loops 139 /// list with the indicated loop. 140 inline void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop) { 141 LI->changeTopLevelLoop(OldLoop, NewLoop); 142 } 143 144 /// addTopLevelLoop - This adds the specified loop to the collection of 145 /// top-level loops. 146 inline void addTopLevelLoop(MachineLoop *New) { 147 LI->addTopLevelLoop(New); 148 } 149 150 /// removeBlock - This method completely removes BB from all data structures, 151 /// including all of the Loop objects it is nested in and our mapping from 152 /// MachineBasicBlocks to loops. 153 void removeBlock(MachineBasicBlock *BB) { 154 LI->removeBlock(BB); 155 } 156}; 157 158 159// Allow clients to walk the list of nested loops... 160template <> struct GraphTraits<const MachineLoop*> { 161 typedef const MachineLoop NodeType; 162 typedef std::vector<MachineLoop*>::const_iterator ChildIteratorType; 163 164 static NodeType *getEntryNode(const MachineLoop *L) { return L; } 165 static inline ChildIteratorType child_begin(NodeType *N) { 166 return N->begin(); 167 } 168 static inline ChildIteratorType child_end(NodeType *N) { 169 return N->end(); 170 } 171}; 172 173template <> struct GraphTraits<MachineLoop*> { 174 typedef MachineLoop NodeType; 175 typedef std::vector<MachineLoop*>::const_iterator ChildIteratorType; 176 177 static NodeType *getEntryNode(MachineLoop *L) { return L; } 178 static inline ChildIteratorType child_begin(NodeType *N) { 179 return N->begin(); 180 } 181 static inline ChildIteratorType child_end(NodeType *N) { 182 return N->end(); 183 } 184}; 185 186} // End llvm namespace 187 188#endif 189