LLVM API Documentation

MachineLoopInfo.h

Go to the documentation of this file.
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