LLVM API Documentation
00001 //===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- 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 // 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/CodeGen/Dump.h" 00020 00021 namespace llvm { 00022 00023 class BasicBlock; 00024 class MachineFunction; 00025 class raw_ostream; 00026 00027 template <> 00028 struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 00029 private: 00030 mutable ilist_node<MachineInstr> Sentinel; 00031 00032 // this is only set by the MachineBasicBlock owning the LiveList 00033 friend class MachineBasicBlock; 00034 MachineBasicBlock* Parent; 00035 00036 public: 00037 MachineInstr *createSentinel() const { 00038 return static_cast<MachineInstr*>(&Sentinel); 00039 } 00040 void destroySentinel(MachineInstr *) const {} 00041 00042 MachineInstr *provideInitialHead() const { return createSentinel(); } 00043 MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 00044 static void noteHead(MachineInstr*, MachineInstr*) {} 00045 00046 void addNodeToList(MachineInstr* N); 00047 void removeNodeFromList(MachineInstr* N); 00048 void transferNodesFromList(ilist_traits &SrcTraits, 00049 ilist_iterator<MachineInstr> first, 00050 ilist_iterator<MachineInstr> last); 00051 void deleteNode(MachineInstr *N); 00052 private: 00053 void createNode(const MachineInstr &); 00054 }; 00055 00056 class MachineBasicBlock : public ilist_node<MachineBasicBlock> { 00057 typedef ilist<MachineInstr> Instructions; 00058 Instructions Insts; 00059 const BasicBlock *BB; 00060 int Number; 00061 MachineFunction *xParent; 00062 00063 /// Predecessors/Successors - Keep track of the predecessor / successor 00064 /// basicblocks. 00065 std::vector<MachineBasicBlock *> Predecessors; 00066 std::vector<MachineBasicBlock *> Successors; 00067 00068 /// LiveIns - Keep track of the physical registers that are livein of 00069 /// the basicblock. 00070 std::vector<unsigned> LiveIns; 00071 00072 /// Alignment - Alignment of the basic block. Zero if the basic block does 00073 /// not need to be aligned. 00074 unsigned Alignment; 00075 00076 /// IsLandingPad - Indicate that this basic block is entered via an 00077 /// exception handler. 00078 bool IsLandingPad; 00079 00080 // Intrusive list support 00081 MachineBasicBlock() {} 00082 00083 explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 00084 00085 ~MachineBasicBlock(); 00086 00087 // MachineBasicBlocks are allocated and owned by MachineFunction. 00088 friend class MachineFunction; 00089 00090 public: 00091 /// getBasicBlock - Return the LLVM basic block that this instance 00092 /// corresponded to originally. 00093 /// 00094 const BasicBlock *getBasicBlock() const { return BB; } 00095 00096 /// getParent - Return the MachineFunction containing this basic block. 00097 /// 00098 const MachineFunction *getParent() const { return xParent; } 00099 MachineFunction *getParent() { return xParent; } 00100 00101 typedef Instructions::iterator iterator; 00102 typedef Instructions::const_iterator const_iterator; 00103 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00104 typedef std::reverse_iterator<iterator> reverse_iterator; 00105 00106 unsigned size() const { return (unsigned)Insts.size(); } 00107 bool empty() const { return Insts.empty(); } 00108 00109 MachineInstr& front() { return Insts.front(); } 00110 MachineInstr& back() { return Insts.back(); } 00111 const MachineInstr& front() const { return Insts.front(); } 00112 const MachineInstr& back() const { return Insts.back(); } 00113 00114 iterator begin() { return Insts.begin(); } 00115 const_iterator begin() const { return Insts.begin(); } 00116 iterator end() { return Insts.end(); } 00117 const_iterator end() const { return Insts.end(); } 00118 reverse_iterator rbegin() { return Insts.rbegin(); } 00119 const_reverse_iterator rbegin() const { return Insts.rbegin(); } 00120 reverse_iterator rend () { return Insts.rend(); } 00121 const_reverse_iterator rend () const { return Insts.rend(); } 00122 00123 // Machine-CFG iterators 00124 typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 00125 typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 00126 typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 00127 typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 00128 typedef std::vector<MachineBasicBlock *>::reverse_iterator 00129 pred_reverse_iterator; 00130 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 00131 const_pred_reverse_iterator; 00132 typedef std::vector<MachineBasicBlock *>::reverse_iterator 00133 succ_reverse_iterator; 00134 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 00135 const_succ_reverse_iterator; 00136 00137 pred_iterator pred_begin() { return Predecessors.begin(); } 00138 const_pred_iterator pred_begin() const { return Predecessors.begin(); } 00139 pred_iterator pred_end() { return Predecessors.end(); } 00140 const_pred_iterator pred_end() const { return Predecessors.end(); } 00141 pred_reverse_iterator pred_rbegin() 00142 { return Predecessors.rbegin();} 00143 const_pred_reverse_iterator pred_rbegin() const 00144 { return Predecessors.rbegin();} 00145 pred_reverse_iterator pred_rend() 00146 { return Predecessors.rend(); } 00147 const_pred_reverse_iterator pred_rend() const 00148 { return Predecessors.rend(); } 00149 unsigned pred_size() const { 00150 return (unsigned)Predecessors.size(); 00151 } 00152 bool pred_empty() const { return Predecessors.empty(); } 00153 succ_iterator succ_begin() { return Successors.begin(); } 00154 const_succ_iterator succ_begin() const { return Successors.begin(); } 00155 succ_iterator succ_end() { return Successors.end(); } 00156 const_succ_iterator succ_end() const { return Successors.end(); } 00157 succ_reverse_iterator succ_rbegin() 00158 { return Successors.rbegin(); } 00159 const_succ_reverse_iterator succ_rbegin() const 00160 { return Successors.rbegin(); } 00161 succ_reverse_iterator succ_rend() 00162 { return Successors.rend(); } 00163 const_succ_reverse_iterator succ_rend() const 00164 { return Successors.rend(); } 00165 unsigned succ_size() const { 00166 return (unsigned)Successors.size(); 00167 } 00168 bool succ_empty() const { return Successors.empty(); } 00169 00170 // LiveIn management methods. 00171 00172 /// addLiveIn - Add the specified register as a live in. Note that it 00173 /// is an error to add the same register to the same set more than once. 00174 void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 00175 00176 /// removeLiveIn - Remove the specified register from the live in set. 00177 /// 00178 void removeLiveIn(unsigned Reg); 00179 00180 /// isLiveIn - Return true if the specified register is in the live in set. 00181 /// 00182 bool isLiveIn(unsigned Reg) const; 00183 00184 // Iteration support for live in sets. These sets are kept in sorted 00185 // order by their register number. 00186 typedef std::vector<unsigned>::iterator livein_iterator; 00187 typedef std::vector<unsigned>::const_iterator const_livein_iterator; 00188 livein_iterator livein_begin() { return LiveIns.begin(); } 00189 const_livein_iterator livein_begin() const { return LiveIns.begin(); } 00190 livein_iterator livein_end() { return LiveIns.end(); } 00191 const_livein_iterator livein_end() const { return LiveIns.end(); } 00192 bool livein_empty() const { return LiveIns.empty(); } 00193 00194 /// getAlignment - Return alignment of the basic block. 00195 /// 00196 unsigned getAlignment() const { return Alignment; } 00197 00198 /// setAlignment - Set alignment of the basic block. 00199 /// 00200 void setAlignment(unsigned Align) { Alignment = Align; } 00201 00202 /// isLandingPad - Returns true if the block is a landing pad. That is 00203 /// this basic block is entered via an exception handler. 00204 bool isLandingPad() const { return IsLandingPad; } 00205 00206 /// setIsLandingPad - Indicates the block is a landing pad. That is 00207 /// this basic block is entered via an exception handler. 00208 void setIsLandingPad() { IsLandingPad = true; } 00209 00210 // Code Layout methods. 00211 00212 /// moveBefore/moveAfter - move 'this' block before or after the specified 00213 /// block. This only moves the block, it does not modify the CFG or adjust 00214 /// potential fall-throughs at the end of the block. 00215 void moveBefore(MachineBasicBlock *NewAfter); 00216 void moveAfter(MachineBasicBlock *NewBefore); 00217 00218 // Machine-CFG mutators 00219 00220 /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 00221 /// The Predecessors list of succ is automatically updated. 00222 /// 00223 void addSuccessor(MachineBasicBlock *succ); 00224 00225 /// removeSuccessor - Remove successor from the successors list of this 00226 /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 00227 /// 00228 void removeSuccessor(MachineBasicBlock *succ); 00229 00230 /// removeSuccessor - Remove specified successor from the successors list of 00231 /// this MachineBasicBlock. The Predecessors list of succ is automatically 00232 /// updated. Return the iterator to the element after the one removed. 00233 /// 00234 succ_iterator removeSuccessor(succ_iterator I); 00235 00236 /// transferSuccessors - Transfers all the successors from MBB to this 00237 /// machine basic block (i.e., copies all the successors fromMBB and 00238 /// remove all the successors fromBB). 00239 void transferSuccessors(MachineBasicBlock *fromMBB); 00240 00241 /// isSuccessor - Return true if the specified MBB is a successor of this 00242 /// block. 00243 bool isSuccessor(const MachineBasicBlock *MBB) const; 00244 00245 /// isLayoutSuccessor - Return true if the specified MBB will be emitted 00246 /// immediately after this block, such that if this block exits by 00247 /// falling through, control will transfer to the specified MBB. Note 00248 /// that MBB need not be a successor at all, for example if this block 00249 /// ends with an unconditional branch to some other block. 00250 bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 00251 00252 /// getFirstTerminator - returns an iterator to the first terminator 00253 /// instruction of this basic block. If a terminator does not exist, 00254 /// it returns end() 00255 iterator getFirstTerminator(); 00256 00257 /// isOnlyReachableViaFallthough - Return true if this basic block has 00258 /// exactly one predecessor and the control transfer mechanism between 00259 /// the predecessor and this block is a fall-through. 00260 bool isOnlyReachableByFallthrough() const; 00261 00262 void pop_front() { Insts.pop_front(); } 00263 void pop_back() { Insts.pop_back(); } 00264 void push_back(MachineInstr *MI) { Insts.push_back(MI); } 00265 template<typename IT> 00266 void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } 00267 iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } 00268 00269 // erase - Remove the specified element or range from the instruction list. 00270 // These functions delete any instructions removed. 00271 // 00272 iterator erase(iterator I) { return Insts.erase(I); } 00273 iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } 00274 MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } 00275 void clear() { Insts.clear(); } 00276 00277 /// splice - Take an instruction from MBB 'Other' at the position From, 00278 /// and insert it into this MBB right before 'where'. 00279 void splice(iterator where, MachineBasicBlock *Other, iterator From) { 00280 Insts.splice(where, Other->Insts, From); 00281 } 00282 00283 /// splice - Take a block of instructions from MBB 'Other' in the range [From, 00284 /// To), and insert them into this MBB right before 'where'. 00285 void splice(iterator where, MachineBasicBlock *Other, iterator From, 00286 iterator To) { 00287 Insts.splice(where, Other->Insts, From, To); 00288 } 00289 00290 /// removeFromParent - This method unlinks 'this' from the containing 00291 /// function, and returns it, but does not delete it. 00292 MachineBasicBlock *removeFromParent(); 00293 00294 /// eraseFromParent - This method unlinks 'this' from the containing 00295 /// function and deletes it. 00296 void eraseFromParent(); 00297 00298 /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 00299 /// 'Old', change the code and CFG so that it branches to 'New' instead. 00300 void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 00301 00302 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 00303 /// the CFG to be inserted. If we have proven that MBB can only branch to 00304 /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 00305 /// DestB can be null. Besides DestA and DestB, retain other edges leading 00306 /// to LandingPads (currently there can be only one; we don't check or require 00307 /// that here). Note it is possible that DestA and/or DestB are LandingPads. 00308 bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 00309 MachineBasicBlock *DestB, 00310 bool isCond); 00311 00312 // Debugging methods. 00313 void dump() const; 00314 void print(std::ostream &OS, 00315 const PrefixPrinter &prefix = PrefixPrinter()) const; 00316 void print(std::ostream *OS, 00317 const PrefixPrinter &prefix = PrefixPrinter()) const { 00318 if (OS) print(*OS, prefix); 00319 } 00320 void print(raw_ostream &OS, 00321 const PrefixPrinter &prefix = PrefixPrinter()) const; 00322 void print(raw_ostream *OS, 00323 const PrefixPrinter &prefix = PrefixPrinter()) const { 00324 if (OS) print(*OS, prefix); 00325 } 00326 00327 /// getNumber - MachineBasicBlocks are uniquely numbered at the function 00328 /// level, unless they're not in a MachineFunction yet, in which case this 00329 /// will return -1. 00330 /// 00331 int getNumber() const { return Number; } 00332 void setNumber(int N) { Number = N; } 00333 00334 private: // Methods used to maintain doubly linked list of blocks... 00335 friend struct ilist_traits<MachineBasicBlock>; 00336 00337 // Machine-CFG mutators 00338 00339 /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 00340 /// Don't do this unless you know what you're doing, because it doesn't 00341 /// update pred's successors list. Use pred->addSuccessor instead. 00342 /// 00343 void addPredecessor(MachineBasicBlock *pred); 00344 00345 /// removePredecessor - Remove pred as a predecessor of this 00346 /// MachineBasicBlock. Don't do this unless you know what you're 00347 /// doing, because it doesn't update pred's successors list. Use 00348 /// pred->removeSuccessor instead. 00349 /// 00350 void removePredecessor(MachineBasicBlock *pred); 00351 }; 00352 00353 std::ostream& operator<<(std::ostream &OS, const MachineBasicBlock &MBB); 00354 raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 00355 00356 //===--------------------------------------------------------------------===// 00357 // GraphTraits specializations for machine basic block graphs (machine-CFGs) 00358 //===--------------------------------------------------------------------===// 00359 00360 // Provide specializations of GraphTraits to be able to treat a 00361 // MachineFunction as a graph of MachineBasicBlocks... 00362 // 00363 00364 template <> struct GraphTraits<MachineBasicBlock *> { 00365 typedef MachineBasicBlock NodeType; 00366 typedef MachineBasicBlock::succ_iterator ChildIteratorType; 00367 00368 static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 00369 static inline ChildIteratorType child_begin(NodeType *N) { 00370 return N->succ_begin(); 00371 } 00372 static inline ChildIteratorType child_end(NodeType *N) { 00373 return N->succ_end(); 00374 } 00375 }; 00376 00377 template <> struct GraphTraits<const MachineBasicBlock *> { 00378 typedef const MachineBasicBlock NodeType; 00379 typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 00380 00381 static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 00382 static inline ChildIteratorType child_begin(NodeType *N) { 00383 return N->succ_begin(); 00384 } 00385 static inline ChildIteratorType child_end(NodeType *N) { 00386 return N->succ_end(); 00387 } 00388 }; 00389 00390 // Provide specializations of GraphTraits to be able to treat a 00391 // MachineFunction as a graph of MachineBasicBlocks... and to walk it 00392 // in inverse order. Inverse order for a function is considered 00393 // to be when traversing the predecessor edges of a MBB 00394 // instead of the successor edges. 00395 // 00396 template <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 00397 typedef MachineBasicBlock NodeType; 00398 typedef MachineBasicBlock::pred_iterator ChildIteratorType; 00399 static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 00400 return G.Graph; 00401 } 00402 static inline ChildIteratorType child_begin(NodeType *N) { 00403 return N->pred_begin(); 00404 } 00405 static inline ChildIteratorType child_end(NodeType *N) { 00406 return N->pred_end(); 00407 } 00408 }; 00409 00410 template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 00411 typedef const MachineBasicBlock NodeType; 00412 typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 00413 static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 00414 return G.Graph; 00415 } 00416 static inline ChildIteratorType child_begin(NodeType *N) { 00417 return N->pred_begin(); 00418 } 00419 static inline ChildIteratorType child_end(NodeType *N) { 00420 return N->pred_end(); 00421 } 00422 }; 00423 00424 } // End llvm namespace 00425 00426 #endif