MachineBasicBlock.h revision da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638
1//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Collect the sequence of machine instructions for a basic block. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 15#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 16 17#include "llvm/CodeGen/MachineInstr.h" 18#include "Support/GraphTraits.h" 19#include "Support/ilist" 20#include <iosfwd> 21 22namespace llvm { 23 class MachineFunction; 24 25// ilist_traits 26template <> 27class ilist_traits<MachineInstr> { 28 // this is only set by the MachineBasicBlock owning the ilist 29 friend class MachineBasicBlock; 30 MachineBasicBlock* parent; 31 32public: 33 ilist_traits<MachineInstr>() : parent(0) { } 34 35 static MachineInstr* getPrev(MachineInstr* N) { return N->prev; } 36 static MachineInstr* getNext(MachineInstr* N) { return N->next; } 37 38 static const MachineInstr* 39 getPrev(const MachineInstr* N) { return N->prev; } 40 41 static const MachineInstr* 42 getNext(const MachineInstr* N) { return N->next; } 43 44 static void setPrev(MachineInstr* N, MachineInstr* prev) { N->prev = prev; } 45 static void setNext(MachineInstr* N, MachineInstr* next) { N->next = next; } 46 47 static MachineInstr* createNode(); 48 void addNodeToList(MachineInstr* N); 49 void removeNodeFromList(MachineInstr* N); 50 void transferNodesFromList( 51 iplist<MachineInstr, ilist_traits<MachineInstr> >& toList, 52 ilist_iterator<MachineInstr> first, 53 ilist_iterator<MachineInstr> last); 54}; 55 56class BasicBlock; 57 58class MachineBasicBlock { 59public: 60 typedef ilist<MachineInstr> Instructions; 61 Instructions Insts; 62 MachineBasicBlock *Prev, *Next; 63 const BasicBlock *BB; 64 std::vector<MachineBasicBlock *> Predecessors; 65 std::vector<MachineBasicBlock *> Successors; 66 int Number; 67 68public: 69 MachineBasicBlock(const BasicBlock *bb = 0) : Prev(0), Next(0), BB(bb), 70 Number(-1) { 71 Insts.parent = this; 72 } 73 ~MachineBasicBlock() {} 74 75 /// getBasicBlock - Return the LLVM basic block that this instance 76 /// corresponded to originally. 77 /// 78 const BasicBlock *getBasicBlock() const { return BB; } 79 80 /// getParent - Return the MachineFunction containing this basic block. 81 /// 82 const MachineFunction *getParent() const; 83 MachineFunction *getParent(); 84 85 typedef ilist<MachineInstr>::iterator iterator; 86 typedef ilist<MachineInstr>::const_iterator const_iterator; 87 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 88 typedef std::reverse_iterator<iterator> reverse_iterator; 89 90 unsigned size() const { return Insts.size(); } 91 bool empty() const { return Insts.empty(); } 92 93 MachineInstr& front() { return Insts.front(); } 94 MachineInstr& back() { return Insts.back(); } 95 96 iterator begin() { return Insts.begin(); } 97 const_iterator begin() const { return Insts.begin(); } 98 iterator end() { return Insts.end(); } 99 const_iterator end() const { return Insts.end(); } 100 reverse_iterator rbegin() { return Insts.rbegin(); } 101 const_reverse_iterator rbegin() const { return Insts.rbegin(); } 102 reverse_iterator rend () { return Insts.rend(); } 103 const_reverse_iterator rend () const { return Insts.rend(); } 104 105 // Machine-CFG iterators 106 typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 107 typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 108 typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 109 typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 110 111 pred_iterator pred_begin() { return Predecessors.begin (); } 112 const_pred_iterator pred_begin() const { return Predecessors.begin (); } 113 pred_iterator pred_end() { return Predecessors.end (); } 114 const_pred_iterator pred_end() const { return Predecessors.end (); } 115 unsigned pred_size() const { return Predecessors.size (); } 116 succ_iterator succ_begin() { return Successors.begin (); } 117 const_succ_iterator succ_begin() const { return Successors.begin (); } 118 succ_iterator succ_end() { return Successors.end (); } 119 const_succ_iterator succ_end() const { return Successors.end (); } 120 unsigned succ_size() const { return Successors.size (); } 121 122 // Machine-CFG mutators 123 124 /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 125 /// The Predecessors list of succ is automatically updated. 126 /// 127 void addSuccessor (MachineBasicBlock *succ) { 128 Successors.push_back (succ); 129 succ->addPredecessor (this); 130 } 131 132 /// removeSuccessor - Remove succ from the successors list of this 133 /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 134 /// 135 void removeSuccessor (MachineBasicBlock *succ) { 136 succ->removePredecessor (this); 137 std::vector<MachineBasicBlock *>::iterator goner = 138 std::find (Successors.begin(), Successors.end (), succ); 139 Successors.erase (goner); 140 } 141 142 /// getFirstTerminator - returns an iterator to the first terminator 143 /// instruction of this basic block. If a terminator does not exist, 144 /// it returns end() 145 iterator getFirstTerminator(); 146 147 void push_back(MachineInstr *MI) { Insts.push_back(MI); } 148 template<typename IT> 149 void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } 150 iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } 151 152 // erase - Remove the specified element or range from the instruction list. 153 // These functions delete any instructions removed. 154 // 155 iterator erase(iterator I) { return Insts.erase(I); } 156 iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } 157 MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } 158 void clear() { Insts.clear(); } 159 160 // Debugging methods. 161 void dump() const; 162 void print(std::ostream &OS) const; 163 164 /// getNumber - MachineBasicBlocks are uniquely numbered at the function 165 /// level, unless they're not in a MachineFunction yet, in which case this 166 /// will return -1. 167 /// 168 int getNumber() const { return Number; } 169 170private: // Methods used to maintain doubly linked list of blocks... 171 friend class ilist_traits<MachineBasicBlock>; 172 173 MachineBasicBlock *getPrev() const { return Prev; } 174 MachineBasicBlock *getNext() const { return Next; } 175 void setPrev(MachineBasicBlock *P) { Prev = P; } 176 void setNext(MachineBasicBlock *N) { Next = N; } 177 178 // Machine-CFG mutators 179 180 /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 181 /// Don't do this unless you know what you're doing, because it doesn't 182 /// update pred's successors list. Use pred->addSuccessor instead. 183 /// 184 void addPredecessor (MachineBasicBlock *pred) { 185 Predecessors.push_back (pred); 186 } 187 188 /// removePredecessor - Remove pred as a predecessor of this 189 /// MachineBasicBlock. Don't do this unless you know what you're 190 /// doing, because it doesn't update pred's successors list. Use 191 /// pred->removeSuccessor instead. 192 /// 193 void removePredecessor (MachineBasicBlock *pred) { 194 std::vector<MachineBasicBlock *>::iterator goner = 195 std::find (Predecessors.begin(), Predecessors.end (), pred); 196 Predecessors.erase (goner); 197 } 198}; 199 200 201//===--------------------------------------------------------------------===// 202// GraphTraits specializations for machine basic block graphs (machine-CFGs) 203//===--------------------------------------------------------------------===// 204 205// Provide specializations of GraphTraits to be able to treat a 206// MachineFunction as a graph of MachineBasicBlocks... 207// 208 209template <> struct GraphTraits<MachineBasicBlock *> { 210 typedef MachineBasicBlock NodeType; 211 typedef MachineBasicBlock::succ_iterator ChildIteratorType; 212 213 static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 214 static inline ChildIteratorType child_begin(NodeType *N) { 215 return N->succ_begin(); 216 } 217 static inline ChildIteratorType child_end(NodeType *N) { 218 return N->succ_end(); 219 } 220}; 221 222template <> struct GraphTraits<const MachineBasicBlock *> { 223 typedef const MachineBasicBlock NodeType; 224 typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 225 226 static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 227 static inline ChildIteratorType child_begin(NodeType *N) { 228 return N->succ_begin(); 229 } 230 static inline ChildIteratorType child_end(NodeType *N) { 231 return N->succ_end(); 232 } 233}; 234 235// Provide specializations of GraphTraits to be able to treat a 236// MachineFunction as a graph of MachineBasicBlocks... and to walk it 237// in inverse order. Inverse order for a function is considered 238// to be when traversing the predecessor edges of a MBB 239// instead of the successor edges. 240// 241template <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 242 typedef MachineBasicBlock NodeType; 243 typedef MachineBasicBlock::pred_iterator ChildIteratorType; 244 static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 245 return G.Graph; 246 } 247 static inline ChildIteratorType child_begin(NodeType *N) { 248 return N->pred_begin(); 249 } 250 static inline ChildIteratorType child_end(NodeType *N) { 251 return N->pred_end(); 252 } 253}; 254 255template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 256 typedef const MachineBasicBlock NodeType; 257 typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 258 static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 259 return G.Graph; 260 } 261 static inline ChildIteratorType child_begin(NodeType *N) { 262 return N->pred_begin(); 263 } 264 static inline ChildIteratorType child_end(NodeType *N) { 265 return N->pred_end(); 266 } 267}; 268 269} // End llvm namespace 270 271#endif 272