LLVM API Documentation

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