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 37namespace llvm { 38 39// Implementation in LoopInfoImpl.h 40#ifdef __GNUC__ 41class MachineLoop; 42__extension__ extern template class LoopBase<MachineBasicBlock, MachineLoop>; 43#endif 44 45class MachineLoop : public LoopBase<MachineBasicBlock, MachineLoop> { 46public: 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 61private: 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 70class LoopInfoBase<MachineBasicBlock, MachineLoop>; 71#endif 72 73class 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 80public: 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... 163template <> 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 176template <> 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