LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

MachineBasicBlock.h

Go to the documentation of this file.
00001 //===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 // 
00010 // Collect the sequence of machine instructions for a basic block.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
00015 #define LLVM_CODEGEN_MACHINEBASICBLOCK_H
00016 
00017 #include "llvm/CodeGen/MachineInstr.h"
00018 #include "llvm/ADT/GraphTraits.h"
00019 #include "llvm/ADT/ilist"
00020 #include <iosfwd>
00021 
00022 namespace llvm {
00023   class MachineFunction;
00024 
00025 // ilist_traits
00026 template <>
00027 struct ilist_traits<MachineInstr> {
00028 protected:
00029   // this is only set by the MachineBasicBlock owning the ilist
00030   friend class MachineBasicBlock;
00031   MachineBasicBlock* parent;
00032 
00033 public:
00034   ilist_traits<MachineInstr>() : parent(0) { }
00035 
00036   static MachineInstr* getPrev(MachineInstr* N) { return N->prev; }
00037   static MachineInstr* getNext(MachineInstr* N) { return N->next; }
00038 
00039   static const MachineInstr*
00040   getPrev(const MachineInstr* N) { return N->prev; }
00041 
00042   static const MachineInstr*
00043   getNext(const MachineInstr* N) { return N->next; }
00044 
00045   static void setPrev(MachineInstr* N, MachineInstr* prev) { N->prev = prev; }
00046   static void setNext(MachineInstr* N, MachineInstr* next) { N->next = next; }
00047 
00048   static MachineInstr* createNode();
00049   void addNodeToList(MachineInstr* N);
00050   void removeNodeFromList(MachineInstr* N);
00051   void transferNodesFromList(
00052       iplist<MachineInstr, ilist_traits<MachineInstr> >& toList,
00053       ilist_iterator<MachineInstr> first,
00054       ilist_iterator<MachineInstr> last);
00055 };
00056 
00057 class BasicBlock;
00058 
00059 class MachineBasicBlock {
00060 public:
00061   typedef ilist<MachineInstr> Instructions;
00062   Instructions Insts;
00063   MachineBasicBlock *Prev, *Next;
00064   const BasicBlock *BB;
00065   std::vector<MachineBasicBlock *> Predecessors;
00066   std::vector<MachineBasicBlock *> Successors;
00067   int Number;
00068   MachineFunction *Parent;
00069 
00070 public:
00071   MachineBasicBlock(const BasicBlock *bb = 0) : Prev(0), Next(0), BB(bb),
00072                                                 Number(-1), Parent(0) {
00073     Insts.parent = this;
00074   }
00075 
00076   ~MachineBasicBlock();
00077   
00078   /// getBasicBlock - Return the LLVM basic block that this instance
00079   /// corresponded to originally.
00080   ///
00081   const BasicBlock *getBasicBlock() const { return BB; }
00082 
00083   /// getParent - Return the MachineFunction containing this basic block.
00084   ///
00085   const MachineFunction *getParent() const { return Parent; }
00086   MachineFunction *getParent() { return Parent; }
00087 
00088   typedef ilist<MachineInstr>::iterator                       iterator;
00089   typedef ilist<MachineInstr>::const_iterator           const_iterator;
00090   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00091   typedef std::reverse_iterator<iterator>             reverse_iterator;
00092 
00093   unsigned size() const { return Insts.size(); }
00094   bool empty() const { return Insts.empty(); }
00095 
00096   MachineInstr& front() { return Insts.front(); }
00097   MachineInstr& back()  { return Insts.back(); }
00098 
00099   iterator                begin()       { return Insts.begin();  }
00100   const_iterator          begin() const { return Insts.begin();  }
00101   iterator                  end()       { return Insts.end();    }
00102   const_iterator            end() const { return Insts.end();    }
00103   reverse_iterator       rbegin()       { return Insts.rbegin(); }
00104   const_reverse_iterator rbegin() const { return Insts.rbegin(); }
00105   reverse_iterator       rend  ()       { return Insts.rend();   }
00106   const_reverse_iterator rend  () const { return Insts.rend();   }
00107 
00108   // Machine-CFG iterators
00109   typedef std::vector<MachineBasicBlock *>::iterator       pred_iterator;
00110   typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator;
00111   typedef std::vector<MachineBasicBlock *>::iterator       succ_iterator;
00112   typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator;
00113   
00114   pred_iterator        pred_begin()       { return Predecessors.begin (); }
00115   const_pred_iterator  pred_begin() const { return Predecessors.begin (); }
00116   pred_iterator        pred_end()         { return Predecessors.end ();   }
00117   const_pred_iterator  pred_end()   const { return Predecessors.end ();   }
00118   unsigned             pred_size()  const { return Predecessors.size ();  }
00119   bool                 pred_empty() const { return Predecessors.empty();  }
00120   succ_iterator        succ_begin()       { return Successors.begin ();   }
00121   const_succ_iterator  succ_begin() const { return Successors.begin ();   }
00122   succ_iterator        succ_end()         { return Successors.end ();     }
00123   const_succ_iterator  succ_end()   const { return Successors.end ();     }
00124   unsigned             succ_size()  const { return Successors.size ();    }
00125   bool                 succ_empty() const { return Successors.empty();    }
00126 
00127   // Machine-CFG mutators
00128 
00129   /// addSuccessor - Add succ as a successor of this MachineBasicBlock.
00130   /// The Predecessors list of succ is automatically updated.
00131   ///
00132   void addSuccessor(MachineBasicBlock *succ);
00133 
00134   /// removeSuccessor - Remove successor from the successors list of this
00135   /// MachineBasicBlock. The Predecessors list of succ is automatically updated.
00136   ///
00137   void removeSuccessor(MachineBasicBlock *succ);
00138 
00139   /// removeSuccessor - Remove specified successor from the successors list of
00140   /// this MachineBasicBlock. The Predecessors list of succ is automatically
00141   /// updated.
00142   ///
00143   void removeSuccessor(succ_iterator I);
00144 
00145   /// getFirstTerminator - returns an iterator to the first terminator
00146   /// instruction of this basic block. If a terminator does not exist,
00147   /// it returns end()
00148   iterator getFirstTerminator();
00149 
00150   void pop_front() { Insts.pop_front(); }
00151   void pop_back() { Insts.pop_back(); }
00152   void push_back(MachineInstr *MI) { Insts.push_back(MI); }
00153   template<typename IT>
00154   void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); }
00155   iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); }
00156 
00157   // erase - Remove the specified element or range from the instruction list.
00158   // These functions delete any instructions removed.
00159   //
00160   iterator erase(iterator I)             { return Insts.erase(I); }
00161   iterator erase(iterator I, iterator E) { return Insts.erase(I, E); }
00162   MachineInstr *remove(MachineInstr *I)  { return Insts.remove(I); }
00163   void clear()                           { Insts.clear(); }
00164   
00165   /// splice - Take a block of instructions from MBB 'Other' in the range [From,
00166   /// To), and insert them into this MBB right before 'where'.
00167   void splice(iterator where, MachineBasicBlock *Other, iterator From,
00168               iterator To) {
00169     Insts.splice(where, Other->Insts, From, To);
00170   }
00171 
00172   // Debugging methods.
00173   void dump() const;
00174   void print(std::ostream &OS) const;
00175 
00176   /// getNumber - MachineBasicBlocks are uniquely numbered at the function
00177   /// level, unless they're not in a MachineFunction yet, in which case this
00178   /// will return -1.
00179   ///
00180   int getNumber() const { return Number; }
00181 
00182 private:   // Methods used to maintain doubly linked list of blocks...
00183   friend struct ilist_traits<MachineBasicBlock>;
00184 
00185   MachineBasicBlock *getPrev() const { return Prev; }
00186   MachineBasicBlock *getNext() const { return Next; }
00187   void setPrev(MachineBasicBlock *P) { Prev = P; }
00188   void setNext(MachineBasicBlock *N) { Next = N; }
00189 
00190   // Machine-CFG mutators
00191 
00192   /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock.
00193   /// Don't do this unless you know what you're doing, because it doesn't
00194   /// update pred's successors list. Use pred->addSuccessor instead.
00195   ///
00196   void addPredecessor(MachineBasicBlock *pred);
00197 
00198   /// removePredecessor - Remove pred as a predecessor of this
00199   /// MachineBasicBlock. Don't do this unless you know what you're
00200   /// doing, because it doesn't update pred's successors list. Use
00201   /// pred->removeSuccessor instead.
00202   ///
00203   void removePredecessor(MachineBasicBlock *pred);
00204 };
00205 
00206 
00207 
00208 //===--------------------------------------------------------------------===//
00209 // GraphTraits specializations for machine basic block graphs (machine-CFGs)
00210 //===--------------------------------------------------------------------===//
00211 
00212 // Provide specializations of GraphTraits to be able to treat a
00213 // MachineFunction as a graph of MachineBasicBlocks...
00214 //
00215 
00216 template <> struct GraphTraits<MachineBasicBlock *> {
00217   typedef MachineBasicBlock NodeType;
00218   typedef MachineBasicBlock::succ_iterator ChildIteratorType;
00219 
00220   static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; }
00221   static inline ChildIteratorType child_begin(NodeType *N) { 
00222     return N->succ_begin();
00223   }
00224   static inline ChildIteratorType child_end(NodeType *N) { 
00225     return N->succ_end();
00226   }
00227 };
00228 
00229 template <> struct GraphTraits<const MachineBasicBlock *> {
00230   typedef const MachineBasicBlock NodeType;
00231   typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
00232 
00233   static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; }
00234   static inline ChildIteratorType child_begin(NodeType *N) { 
00235     return N->succ_begin();
00236   }
00237   static inline ChildIteratorType child_end(NodeType *N) { 
00238     return N->succ_end();
00239   }
00240 };
00241 
00242 // Provide specializations of GraphTraits to be able to treat a
00243 // MachineFunction as a graph of MachineBasicBlocks... and to walk it
00244 // in inverse order.  Inverse order for a function is considered
00245 // to be when traversing the predecessor edges of a MBB
00246 // instead of the successor edges.
00247 //
00248 template <> struct GraphTraits<Inverse<MachineBasicBlock*> > {
00249   typedef MachineBasicBlock NodeType;
00250   typedef MachineBasicBlock::pred_iterator ChildIteratorType;
00251   static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) {
00252     return G.Graph;
00253   }
00254   static inline ChildIteratorType child_begin(NodeType *N) { 
00255     return N->pred_begin();
00256   }
00257   static inline ChildIteratorType child_end(NodeType *N) { 
00258     return N->pred_end();
00259   }
00260 };
00261 
00262 template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > {
00263   typedef const MachineBasicBlock NodeType;
00264   typedef MachineBasicBlock::const_pred_iterator ChildIteratorType;
00265   static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) {
00266     return G.Graph; 
00267   }
00268   static inline ChildIteratorType child_begin(NodeType *N) { 
00269     return N->pred_begin();
00270   }
00271   static inline ChildIteratorType child_end(NodeType *N) { 
00272     return N->pred_end();
00273   }
00274 };
00275 
00276 } // End llvm namespace
00277 
00278 #endif