LLVM API Documentation
00001 //===- llvm/CodeGen/MachineLoopInfo.h - Natural Loop Calculator -*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines the MachineLoopInfo class that is used to identify natural 00011 // loops and determine the loop depth of various nodes of the CFG. Note that 00012 // natural loops may actually be several loops that share the same header node. 00013 // 00014 // This analysis calculates the nesting structure of loops in a function. For 00015 // each natural loop identified, this analysis identifies natural loops 00016 // contained entirely within the loop and the basic blocks the make up the loop. 00017 // 00018 // It can calculate on the fly various bits of information, for example: 00019 // 00020 // * whether there is a preheader for the loop 00021 // * the number of back edges to the header 00022 // * whether or not a particular block branches out of the loop 00023 // * the successor blocks of the loop 00024 // * the loop depth 00025 // * the trip count 00026 // * etc... 00027 // 00028 //===----------------------------------------------------------------------===// 00029 00030 #ifndef LLVM_CODEGEN_MACHINE_LOOP_INFO_H 00031 #define LLVM_CODEGEN_MACHINE_LOOP_INFO_H 00032 00033 #include "llvm/CodeGen/MachineFunctionPass.h" 00034 #include "llvm/Analysis/LoopInfo.h" 00035 00036 namespace llvm { 00037 00038 class MachineLoop : public LoopBase<MachineBasicBlock, MachineLoop> { 00039 public: 00040 MachineLoop(); 00041 private: 00042 friend class LoopInfoBase<MachineBasicBlock, MachineLoop>; 00043 explicit MachineLoop(MachineBasicBlock *MBB) 00044 : LoopBase<MachineBasicBlock, MachineLoop>(MBB) {} 00045 }; 00046 00047 class MachineLoopInfo : public MachineFunctionPass { 00048 LoopInfoBase<MachineBasicBlock, MachineLoop> LI; 00049 friend class LoopBase<MachineBasicBlock, MachineLoop>; 00050 00051 void operator=(const MachineLoopInfo &); // do not implement 00052 MachineLoopInfo(const MachineLoopInfo &); // do not implement 00053 00054 LoopInfoBase<MachineBasicBlock, MachineLoop>& getBase() { return LI; } 00055 00056 public: 00057 static char ID; // Pass identification, replacement for typeid 00058 00059 MachineLoopInfo() : MachineFunctionPass(&ID) {} 00060 00061 /// iterator/begin/end - The interface to the top-level loops in the current 00062 /// function. 00063 /// 00064 typedef LoopInfoBase<MachineBasicBlock, MachineLoop>::iterator iterator; 00065 inline iterator begin() const { return LI.begin(); } 00066 inline iterator end() const { return LI.end(); } 00067 bool empty() const { return LI.empty(); } 00068 00069 /// getLoopFor - Return the inner most loop that BB lives in. If a basic 00070 /// block is in no loop (for example the entry node), null is returned. 00071 /// 00072 inline MachineLoop *getLoopFor(const MachineBasicBlock *BB) const { 00073 return LI.getLoopFor(BB); 00074 } 00075 00076 /// operator[] - same as getLoopFor... 00077 /// 00078 inline const MachineLoop *operator[](const MachineBasicBlock *BB) const { 00079 return LI.getLoopFor(BB); 00080 } 00081 00082 /// getLoopDepth - Return the loop nesting level of the specified block... 00083 /// 00084 inline unsigned getLoopDepth(const MachineBasicBlock *BB) const { 00085 return LI.getLoopDepth(BB); 00086 } 00087 00088 // isLoopHeader - True if the block is a loop header node 00089 inline bool isLoopHeader(MachineBasicBlock *BB) const { 00090 return LI.isLoopHeader(BB); 00091 } 00092 00093 /// runOnFunction - Calculate the natural loop information. 00094 /// 00095 virtual bool runOnMachineFunction(MachineFunction &F); 00096 00097 virtual void releaseMemory() { LI.releaseMemory(); } 00098 00099 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00100 00101 /// removeLoop - This removes the specified top-level loop from this loop info 00102 /// object. The loop is not deleted, as it will presumably be inserted into 00103 /// another loop. 00104 inline MachineLoop *removeLoop(iterator I) { return LI.removeLoop(I); } 00105 00106 /// changeLoopFor - Change the top-level loop that contains BB to the 00107 /// specified loop. This should be used by transformations that restructure 00108 /// the loop hierarchy tree. 00109 inline void changeLoopFor(MachineBasicBlock *BB, MachineLoop *L) { 00110 LI.changeLoopFor(BB, L); 00111 } 00112 00113 /// changeTopLevelLoop - Replace the specified loop in the top-level loops 00114 /// list with the indicated loop. 00115 inline void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop) { 00116 LI.changeTopLevelLoop(OldLoop, NewLoop); 00117 } 00118 00119 /// addTopLevelLoop - This adds the specified loop to the collection of 00120 /// top-level loops. 00121 inline void addTopLevelLoop(MachineLoop *New) { 00122 LI.addTopLevelLoop(New); 00123 } 00124 00125 /// removeBlock - This method completely removes BB from all data structures, 00126 /// including all of the Loop objects it is nested in and our mapping from 00127 /// MachineBasicBlocks to loops. 00128 void removeBlock(MachineBasicBlock *BB) { 00129 LI.removeBlock(BB); 00130 } 00131 }; 00132 00133 00134 // Allow clients to walk the list of nested loops... 00135 template <> struct GraphTraits<const MachineLoop*> { 00136 typedef const MachineLoop NodeType; 00137 typedef MachineLoopInfo::iterator ChildIteratorType; 00138 00139 static NodeType *getEntryNode(const MachineLoop *L) { return L; } 00140 static inline ChildIteratorType child_begin(NodeType *N) { 00141 return N->begin(); 00142 } 00143 static inline ChildIteratorType child_end(NodeType *N) { 00144 return N->end(); 00145 } 00146 }; 00147 00148 template <> struct GraphTraits<MachineLoop*> { 00149 typedef MachineLoop NodeType; 00150 typedef MachineLoopInfo::iterator ChildIteratorType; 00151 00152 static NodeType *getEntryNode(MachineLoop *L) { return L; } 00153 static inline ChildIteratorType child_begin(NodeType *N) { 00154 return N->begin(); 00155 } 00156 static inline ChildIteratorType child_end(NodeType *N) { 00157 return N->end(); 00158 } 00159 }; 00160 00161 } // End llvm namespace 00162 00163 #endif