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