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