MachineLoopInfo.h revision 239462
119370Spst//===- llvm/CodeGen/MachineLoopInfo.h - Natural Loop Calculator -*- C++ -*-===// 298944Sobrien// 398944Sobrien// The LLVM Compiler Infrastructure 419370Spst// 598944Sobrien// This file is distributed under the University of Illinois Open Source 619370Spst// License. See LICENSE.TXT for details. 798944Sobrien// 898944Sobrien//===----------------------------------------------------------------------===// 998944Sobrien// 1098944Sobrien// This file defines the MachineLoopInfo class that is used to identify natural 1119370Spst// loops and determine the loop depth of various nodes of the CFG. Note that 1298944Sobrien// natural loops may actually be several loops that share the same header node. 1398944Sobrien// 1498944Sobrien// This analysis calculates the nesting structure of loops in a function. For 1598944Sobrien// each natural loop identified, this analysis identifies natural loops 1619370Spst// contained entirely within the loop and the basic blocks the make up the loop. 1798944Sobrien// 1898944Sobrien// It can calculate on the fly various bits of information, for example: 1998944Sobrien// 2098944Sobrien// * whether there is a preheader for the loop 2119370Spst// * the number of back edges to the header 2219370Spst// * whether or not a particular block branches out of the loop 2319370Spst// * the successor blocks of the loop 2419370Spst// * the loop depth 2519370Spst// * the trip count 2619370Spst// * etc... 2719370Spst// 2819370Spst//===----------------------------------------------------------------------===// 2919370Spst 3019370Spst#ifndef LLVM_CODEGEN_MACHINE_LOOP_INFO_H 3146283Sdfr#define LLVM_CODEGEN_MACHINE_LOOP_INFO_H 3219370Spst 3346283Sdfr#include "llvm/CodeGen/MachineFunctionPass.h" 3498944Sobrien#include "llvm/Analysis/LoopInfo.h" 3598944Sobrien 3698944Sobriennamespace llvm { 3746283Sdfr 3898944Sobrien// Implementation in LoopInfoImpl.h 3998944Sobrien#ifdef __GNUC__ 4098944Sobrienclass MachineLoop; 4198944Sobrien__extension__ extern template class LoopBase<MachineBasicBlock, MachineLoop>; 4298944Sobrien#endif 4346283Sdfr 4419370Spstclass MachineLoop : public LoopBase<MachineBasicBlock, MachineLoop> { 4519370Spstpublic: 4619370Spst MachineLoop(); 4719370Spst 4846283Sdfr /// getTopBlock - Return the "top" block in the loop, which is the first 4998944Sobrien /// block in the linear layout, ignoring any parts of the loop not 5098944Sobrien /// contiguous with the part the contains the header. 5119370Spst MachineBasicBlock *getTopBlock(); 5219370Spst 5319370Spst /// getBottomBlock - Return the "bottom" block in the loop, which is the last 5419370Spst /// block in the linear layout, ignoring any parts of the loop not 5519370Spst /// contiguous with the part the contains the header. 5619370Spst MachineBasicBlock *getBottomBlock(); 5719370Spst 5819370Spst void dump() const; 5919370Spst 6019370Spstprivate: 6119370Spst friend class LoopInfoBase<MachineBasicBlock, MachineLoop>; 6219370Spst explicit MachineLoop(MachineBasicBlock *MBB) 6319370Spst : LoopBase<MachineBasicBlock, MachineLoop>(MBB) {} 6419370Spst}; 6519370Spst 6619370Spst// Implementation in LoopInfoImpl.h 6719370Spst#ifdef __GNUC__ 6819370Spst__extension__ extern template 6919370Spstclass LoopInfoBase<MachineBasicBlock, MachineLoop>; 7019370Spst#endif 7119370Spst 7219370Spstclass MachineLoopInfo : public MachineFunctionPass { 7319370Spst LoopInfoBase<MachineBasicBlock, MachineLoop> LI; 7419370Spst friend class LoopBase<MachineBasicBlock, MachineLoop>; 7519370Spst 7619370Spst void operator=(const MachineLoopInfo &); // do not implement 7719370Spst MachineLoopInfo(const MachineLoopInfo &); // do not implement 7819370Spst 7919370Spstpublic: 8019370Spst static char ID; // Pass identification, replacement for typeid 8119370Spst 8219370Spst MachineLoopInfo() : MachineFunctionPass(ID) { 8319370Spst initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 8419370Spst } 8519370Spst 8619370Spst LoopInfoBase<MachineBasicBlock, MachineLoop>& getBase() { return LI; } 8719370Spst 8819370Spst /// iterator/begin/end - The interface to the top-level loops in the current 8919370Spst /// function. 9019370Spst /// 9119370Spst typedef LoopInfoBase<MachineBasicBlock, MachineLoop>::iterator iterator; 9219370Spst inline iterator begin() const { return LI.begin(); } 9319370Spst inline iterator end() const { return LI.end(); } 9446283Sdfr bool empty() const { return LI.empty(); } 9598944Sobrien 9698944Sobrien /// getLoopFor - Return the inner most loop that BB lives in. If a basic 9719370Spst /// block is in no loop (for example the entry node), null is returned. 9819370Spst /// 9919370Spst inline MachineLoop *getLoopFor(const MachineBasicBlock *BB) const { 10019370Spst return LI.getLoopFor(BB); 10119370Spst } 10246283Sdfr 10319370Spst /// operator[] - same as getLoopFor... 10419370Spst /// 10519370Spst inline const MachineLoop *operator[](const MachineBasicBlock *BB) const { 10619370Spst return LI.getLoopFor(BB); 10719370Spst } 10819370Spst 10919370Spst /// getLoopDepth - Return the loop nesting level of the specified block... 11019370Spst /// 11119370Spst inline unsigned getLoopDepth(const MachineBasicBlock *BB) const { 11219370Spst return LI.getLoopDepth(BB); 11319370Spst } 11419370Spst 11519370Spst // isLoopHeader - True if the block is a loop header node 11619370Spst inline bool isLoopHeader(MachineBasicBlock *BB) const { 11719370Spst return LI.isLoopHeader(BB); 11819370Spst } 11919370Spst 12019370Spst /// runOnFunction - Calculate the natural loop information. 12119370Spst /// 12219370Spst virtual bool runOnMachineFunction(MachineFunction &F); 12319370Spst 12419370Spst virtual void releaseMemory() { LI.releaseMemory(); } 12519370Spst 12619370Spst virtual void getAnalysisUsage(AnalysisUsage &AU) const; 12719370Spst 12819370Spst /// removeLoop - This removes the specified top-level loop from this loop info 12998944Sobrien /// object. The loop is not deleted, as it will presumably be inserted into 13019370Spst /// another loop. 13119370Spst inline MachineLoop *removeLoop(iterator I) { return LI.removeLoop(I); } 13219370Spst 13319370Spst /// changeLoopFor - Change the top-level loop that contains BB to the 13419370Spst /// specified loop. This should be used by transformations that restructure 13519370Spst /// the loop hierarchy tree. 13698944Sobrien inline void changeLoopFor(MachineBasicBlock *BB, MachineLoop *L) { 13719370Spst LI.changeLoopFor(BB, L); 13819370Spst } 13946283Sdfr 14098944Sobrien /// changeTopLevelLoop - Replace the specified loop in the top-level loops 14198944Sobrien /// list with the indicated loop. 14219370Spst inline void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop) { 14398944Sobrien LI.changeTopLevelLoop(OldLoop, NewLoop); 14446283Sdfr } 14519370Spst 14619370Spst /// addTopLevelLoop - This adds the specified loop to the collection of 14719370Spst /// top-level loops. 14819370Spst inline void addTopLevelLoop(MachineLoop *New) { 14919370Spst LI.addTopLevelLoop(New); 15019370Spst } 15119370Spst 15219370Spst /// removeBlock - This method completely removes BB from all data structures, 15319370Spst /// including all of the Loop objects it is nested in and our mapping from 15419370Spst /// MachineBasicBlocks to loops. 15519370Spst void removeBlock(MachineBasicBlock *BB) { 15619370Spst LI.removeBlock(BB); 15719370Spst } 15819370Spst}; 15919370Spst 16019370Spst 16119370Spst// Allow clients to walk the list of nested loops... 16219370Spsttemplate <> struct GraphTraits<const MachineLoop*> { 16319370Spst typedef const MachineLoop NodeType; 16419370Spst typedef MachineLoopInfo::iterator ChildIteratorType; 16519370Spst 16619370Spst static NodeType *getEntryNode(const MachineLoop *L) { return L; } 16719370Spst static inline ChildIteratorType child_begin(NodeType *N) { 16819370Spst return N->begin(); 16919370Spst } 17019370Spst static inline ChildIteratorType child_end(NodeType *N) { 17119370Spst return N->end(); 17219370Spst } 17319370Spst}; 17419370Spst 17519370Spsttemplate <> struct GraphTraits<MachineLoop*> { 17619370Spst typedef MachineLoop NodeType; 17719370Spst typedef MachineLoopInfo::iterator ChildIteratorType; 17819370Spst 17919370Spst static NodeType *getEntryNode(MachineLoop *L) { return L; } 18019370Spst static inline ChildIteratorType child_begin(NodeType *N) { 18119370Spst return N->begin(); 18219370Spst } 18319370Spst static inline ChildIteratorType child_end(NodeType *N) { 18419370Spst return N->end(); 18519370Spst } 18619370Spst}; 18719370Spst 18819370Spst} // End llvm namespace 18919370Spst 19046283Sdfr#endif 19119370Spst