LLVM API Documentation
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