1e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson//===- llvm/CodeGen/MachineLoopInfo.h - Natural Loop Calculator -*- C++ -*-===// 2e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 3e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// The LLVM Compiler Infrastructure 4e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 7e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 8e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson//===----------------------------------------------------------------------===// 9e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 1060c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trick// This file defines the MachineLoopInfo class that is used to identify natural 11e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// loops and determine the loop depth of various nodes of the CFG. Note that 12e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// natural loops may actually be several loops that share the same header node. 13e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 14e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// This analysis calculates the nesting structure of loops in a function. For 15e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// each natural loop identified, this analysis identifies natural loops 16e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// contained entirely within the loop and the basic blocks the make up the loop. 17e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 18e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// It can calculate on the fly various bits of information, for example: 19e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 20e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// * whether there is a preheader for the loop 21e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// * the number of back edges to the header 22e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// * whether or not a particular block branches out of the loop 23e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// * the successor blocks of the loop 24e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// * the loop depth 25e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// * the trip count 26e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// * etc... 27e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 28e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson//===----------------------------------------------------------------------===// 29e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 30674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_CODEGEN_MACHINELOOPINFO_H 31674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_CODEGEN_MACHINELOOPINFO_H 32e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 33e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson#include "llvm/Analysis/LoopInfo.h" 34255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/CodeGen/MachineFunctionPass.h" 35e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 36e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Andersonnamespace llvm { 37e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 3860c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trick// Implementation in LoopInfoImpl.h 3960c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trick#ifdef __GNUC__ 4060c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trickclass MachineLoop; 4160c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trick__extension__ extern template class LoopBase<MachineBasicBlock, MachineLoop>; 4260c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trick#endif 4360c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trick 44c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohmanclass MachineLoop : public LoopBase<MachineBasicBlock, MachineLoop> { 45c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohmanpublic: 46c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohman MachineLoop(); 4781b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman 4881b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman /// getTopBlock - Return the "top" block in the loop, which is the first 4981b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman /// block in the linear layout, ignoring any parts of the loop not 5081b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman /// contiguous with the part the contains the header. 5181b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman MachineBasicBlock *getTopBlock(); 5281b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman 5381b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman /// getBottomBlock - Return the "bottom" block in the loop, which is the last 5481b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman /// block in the linear layout, ignoring any parts of the loop not 5581b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman /// contiguous with the part the contains the header. 5681b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman MachineBasicBlock *getBottomBlock(); 5781b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman 58dda30cd4af1c5f88fc00fd40b673f8e27c61379dDan Gohman void dump() const; 59dda30cd4af1c5f88fc00fd40b673f8e27c61379dDan Gohman 60c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohmanprivate: 61c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohman friend class LoopInfoBase<MachineBasicBlock, MachineLoop>; 62c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohman explicit MachineLoop(MachineBasicBlock *MBB) 63c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohman : LoopBase<MachineBasicBlock, MachineLoop>(MBB) {} 64c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohman}; 65e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 6660c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trick// Implementation in LoopInfoImpl.h 6760c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trick#ifdef __GNUC__ 6860c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trick__extension__ extern template 6960c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trickclass LoopInfoBase<MachineBasicBlock, MachineLoop>; 7060c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trick#endif 7160c7d5bc2cbeff9eff16716295ffd6a5374dc6bcAndrew Trick 72e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Andersonclass MachineLoopInfo : public MachineFunctionPass { 73c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohman LoopInfoBase<MachineBasicBlock, MachineLoop> LI; 74c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohman friend class LoopBase<MachineBasicBlock, MachineLoop>; 759d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman 76001d3dc976d7cda8a3dd8c7fd4020b0b96033f4eCraig Topper void operator=(const MachineLoopInfo &) LLVM_DELETED_FUNCTION; 77001d3dc976d7cda8a3dd8c7fd4020b0b96033f4eCraig Topper MachineLoopInfo(const MachineLoopInfo &) LLVM_DELETED_FUNCTION; 789d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman 79e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Andersonpublic: 80e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson static char ID; // Pass identification, replacement for typeid 81e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 82081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson MachineLoopInfo() : MachineFunctionPass(ID) { 83081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 84081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 85e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 86853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman LoopInfoBase<MachineBasicBlock, MachineLoop>& getBase() { return LI; } 87853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 88e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// iterator/begin/end - The interface to the top-level loops in the current 89e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// function. 90e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// 91c8d76d5afb023a1c6b439941be3b62789fcc0ed3Dan Gohman typedef LoopInfoBase<MachineBasicBlock, MachineLoop>::iterator iterator; 929d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman inline iterator begin() const { return LI.begin(); } 939d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman inline iterator end() const { return LI.end(); } 949d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman bool empty() const { return LI.empty(); } 95e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 96e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// getLoopFor - Return the inner most loop that BB lives in. If a basic 97e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// block is in no loop (for example the entry node), null is returned. 98e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// 99e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson inline MachineLoop *getLoopFor(const MachineBasicBlock *BB) const { 1009d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman return LI.getLoopFor(BB); 101e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 102e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 103e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// operator[] - same as getLoopFor... 104e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// 105e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson inline const MachineLoop *operator[](const MachineBasicBlock *BB) const { 1069d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman return LI.getLoopFor(BB); 107e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 108e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 109e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// getLoopDepth - Return the loop nesting level of the specified block... 110e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// 111e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson inline unsigned getLoopDepth(const MachineBasicBlock *BB) const { 1129d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman return LI.getLoopDepth(BB); 113e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 114e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 115e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson // isLoopHeader - True if the block is a loop header node 116e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson inline bool isLoopHeader(MachineBasicBlock *BB) const { 1179d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman return LI.isLoopHeader(BB); 118e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 119e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 120e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// runOnFunction - Calculate the natural loop information. 121e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// 122e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson virtual bool runOnMachineFunction(MachineFunction &F); 123e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 1249d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman virtual void releaseMemory() { LI.releaseMemory(); } 125e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 126e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const; 127e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 128e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// removeLoop - This removes the specified top-level loop from this loop info 129e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// object. The loop is not deleted, as it will presumably be inserted into 130e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// another loop. 1319d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman inline MachineLoop *removeLoop(iterator I) { return LI.removeLoop(I); } 132e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 133e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// changeLoopFor - Change the top-level loop that contains BB to the 134e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// specified loop. This should be used by transformations that restructure 135e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// the loop hierarchy tree. 136e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson inline void changeLoopFor(MachineBasicBlock *BB, MachineLoop *L) { 1379d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LI.changeLoopFor(BB, L); 138e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 139e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 140e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// changeTopLevelLoop - Replace the specified loop in the top-level loops 141e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// list with the indicated loop. 142e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson inline void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop) { 1439d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LI.changeTopLevelLoop(OldLoop, NewLoop); 144e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 145e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 146e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// addTopLevelLoop - This adds the specified loop to the collection of 147e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// top-level loops. 148e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson inline void addTopLevelLoop(MachineLoop *New) { 1499d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LI.addTopLevelLoop(New); 150e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 151e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 152e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// removeBlock - This method completely removes BB from all data structures, 153e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// including all of the Loop objects it is nested in and our mapping from 154e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson /// MachineBasicBlocks to loops. 155e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson void removeBlock(MachineBasicBlock *BB) { 1569d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman LI.removeBlock(BB); 157e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 158e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson}; 159e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 160e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 161e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// Allow clients to walk the list of nested loops... 162e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Andersontemplate <> struct GraphTraits<const MachineLoop*> { 163e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson typedef const MachineLoop NodeType; 1649d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman typedef MachineLoopInfo::iterator ChildIteratorType; 165e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 166e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson static NodeType *getEntryNode(const MachineLoop *L) { return L; } 167e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson static inline ChildIteratorType child_begin(NodeType *N) { 168e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson return N->begin(); 169e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 170e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson static inline ChildIteratorType child_end(NodeType *N) { 171e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson return N->end(); 172e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 173e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson}; 174e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 175e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Andersontemplate <> struct GraphTraits<MachineLoop*> { 176e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson typedef MachineLoop NodeType; 1779d59d9f8495b0361c9ffd1dc82888d8e7ba5070eDan Gohman typedef MachineLoopInfo::iterator ChildIteratorType; 178e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 179e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson static NodeType *getEntryNode(MachineLoop *L) { return L; } 180e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson static inline ChildIteratorType child_begin(NodeType *N) { 181e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson return N->begin(); 182e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 183e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson static inline ChildIteratorType child_end(NodeType *N) { 184e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson return N->end(); 185e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson } 186e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson}; 187e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 188e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson} // End llvm namespace 189e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 1900a488b320c3891f427ca2e6d96b1b3fc0fcc9de8Duncan Sands#endif 191