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_MACHINELOOPINFO_H 31 #define LLVM_CODEGEN_MACHINELOOPINFO_H 32 33 #include "llvm/Analysis/LoopInfo.h" 34 #include "llvm/CodeGen/MachineBasicBlock.h" 35 #include "llvm/CodeGen/MachineFunctionPass.h" 36 37 namespace llvm { 38 39 // Implementation in LoopInfoImpl.h 40 #ifdef __GNUC__ 41 class MachineLoop; 42 __extension__ extern template class LoopBase<MachineBasicBlock, MachineLoop>; 43 #endif 44 45 class MachineLoop : public LoopBase<MachineBasicBlock, MachineLoop> { 46 public: 47 MachineLoop(); 48 49 /// getTopBlock - Return the "top" block in the loop, which is the first 50 /// block in the linear layout, ignoring any parts of the loop not 51 /// contiguous with the part the contains the header. 52 MachineBasicBlock *getTopBlock(); 53 54 /// getBottomBlock - Return the "bottom" block in the loop, which is the last 55 /// block in the linear layout, ignoring any parts of the loop not 56 /// contiguous with the part the contains the header. 57 MachineBasicBlock *getBottomBlock(); 58 59 void dump() const; 60 61 private: 62 friend class LoopInfoBase<MachineBasicBlock, MachineLoop>; 63 explicit MachineLoop(MachineBasicBlock *MBB) 64 : LoopBase<MachineBasicBlock, MachineLoop>(MBB) {} 65 }; 66 67 // Implementation in LoopInfoImpl.h 68 #ifdef __GNUC__ 69 __extension__ extern template 70 class LoopInfoBase<MachineBasicBlock, MachineLoop>; 71 #endif 72 73 class MachineLoopInfo : public MachineFunctionPass { 74 LoopInfoBase<MachineBasicBlock, MachineLoop> LI; 75 friend class LoopBase<MachineBasicBlock, MachineLoop>; 76 77 void operator=(const MachineLoopInfo &) LLVM_DELETED_FUNCTION; 78 MachineLoopInfo(const MachineLoopInfo &) LLVM_DELETED_FUNCTION; 79 80 public: 81 static char ID; // Pass identification, replacement for typeid 82 83 MachineLoopInfo() : MachineFunctionPass(ID) { 84 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 85 } 86 87 LoopInfoBase<MachineBasicBlock, MachineLoop>& getBase() { return LI; } 88 89 /// iterator/begin/end - The interface to the top-level loops in the current 90 /// function. 91 /// 92 typedef LoopInfoBase<MachineBasicBlock, MachineLoop>::iterator iterator; 93 inline iterator begin() const { return LI.begin(); } 94 inline iterator end() const { return LI.end(); } 95 bool empty() const { return LI.empty(); } 96 97 /// getLoopFor - Return the inner most loop that BB lives in. If a basic 98 /// block is in no loop (for example the entry node), null is returned. 99 /// 100 inline MachineLoop *getLoopFor(const MachineBasicBlock *BB) const { 101 return LI.getLoopFor(BB); 102 } 103 104 /// operator[] - same as getLoopFor... 105 /// 106 inline const MachineLoop *operator[](const MachineBasicBlock *BB) const { 107 return LI.getLoopFor(BB); 108 } 109 110 /// getLoopDepth - Return the loop nesting level of the specified block... 111 /// 112 inline unsigned getLoopDepth(const MachineBasicBlock *BB) const { 113 return LI.getLoopDepth(BB); 114 } 115 116 // isLoopHeader - True if the block is a loop header node 117 inline bool isLoopHeader(MachineBasicBlock *BB) const { 118 return LI.isLoopHeader(BB); 119 } 120 121 /// runOnFunction - Calculate the natural loop information. 122 /// 123 bool runOnMachineFunction(MachineFunction &F) override; 124 125 void releaseMemory() override { LI.releaseMemory(); } 126 127 void getAnalysisUsage(AnalysisUsage &AU) const override; 128 129 /// removeLoop - This removes the specified top-level loop from this loop info 130 /// object. The loop is not deleted, as it will presumably be inserted into 131 /// another loop. 132 inline MachineLoop *removeLoop(iterator I) { return LI.removeLoop(I); } 133 134 /// changeLoopFor - Change the top-level loop that contains BB to the 135 /// specified loop. This should be used by transformations that restructure 136 /// the loop hierarchy tree. 137 inline void changeLoopFor(MachineBasicBlock *BB, MachineLoop *L) { 138 LI.changeLoopFor(BB, L); 139 } 140 141 /// changeTopLevelLoop - Replace the specified loop in the top-level loops 142 /// list with the indicated loop. 143 inline void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop) { 144 LI.changeTopLevelLoop(OldLoop, NewLoop); 145 } 146 147 /// addTopLevelLoop - This adds the specified loop to the collection of 148 /// top-level loops. 149 inline void addTopLevelLoop(MachineLoop *New) { 150 LI.addTopLevelLoop(New); 151 } 152 153 /// removeBlock - This method completely removes BB from all data structures, 154 /// including all of the Loop objects it is nested in and our mapping from 155 /// MachineBasicBlocks to loops. 156 void removeBlock(MachineBasicBlock *BB) { 157 LI.removeBlock(BB); 158 } 159 }; 160 161 162 // Allow clients to walk the list of nested loops... 163 template <> struct GraphTraits<const MachineLoop*> { 164 typedef const MachineLoop NodeType; 165 typedef MachineLoopInfo::iterator ChildIteratorType; 166 167 static NodeType *getEntryNode(const MachineLoop *L) { return L; } 168 static inline ChildIteratorType child_begin(NodeType *N) { 169 return N->begin(); 170 } 171 static inline ChildIteratorType child_end(NodeType *N) { 172 return N->end(); 173 } 174 }; 175 176 template <> struct GraphTraits<MachineLoop*> { 177 typedef MachineLoop NodeType; 178 typedef MachineLoopInfo::iterator ChildIteratorType; 179 180 static NodeType *getEntryNode(MachineLoop *L) { return L; } 181 static inline ChildIteratorType child_begin(NodeType *N) { 182 return N->begin(); 183 } 184 static inline ChildIteratorType child_end(NodeType *N) { 185 return N->end(); 186 } 187 }; 188 189 } // End llvm namespace 190 191 #endif 192