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