MachineBasicBlock.h revision 324da7647cfc3025e0c987176f0a300f9f780e6f
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Collect the sequence of machine instructions for a basic block. 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/CodeGen/MachineInstr.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/GraphTraits.h" 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace llvm { 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class BasicBlock; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class MachineFunction; 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class raw_ostream; 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <> 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)private: 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mutable ilist_half_node<MachineInstr> Sentinel; 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this is only set by the MachineBasicBlock owning the LiveList 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class MachineBasicBlock; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock* Parent; 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *createSentinel() const { 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return static_cast<MachineInstr*>(&Sentinel); 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void destroySentinel(MachineInstr *) const {} 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *provideInitialHead() const { return createSentinel(); } 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static void noteHead(MachineInstr*, MachineInstr*) {} 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void addNodeToList(MachineInstr* N); 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void removeNodeFromList(MachineInstr* N); 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void transferNodesFromList(ilist_traits &SrcTraits, 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ilist_iterator<MachineInstr> first, 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ilist_iterator<MachineInstr> last); 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void deleteNode(MachineInstr *N); 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)private: 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void createNode(const MachineInstr &); 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class MachineBasicBlock : public ilist_node<MachineBasicBlock> { 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef ilist<MachineInstr> Instructions; 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Instructions Insts; 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const BasicBlock *BB; 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int Number; 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) MachineFunction *xParent; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Predecessors/Successors - Keep track of the predecessor / successor 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// basicblocks. 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<MachineBasicBlock *> Predecessors; 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<MachineBasicBlock *> Successors; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// LiveIns - Keep track of the physical registers that are livein of 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// the basicblock. 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<unsigned> LiveIns; 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Alignment - Alignment of the basic block. Zero if the basic block does 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// not need to be aligned. 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned Alignment; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// IsLandingPad - Indicate that this basic block is entered via an 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// exception handler. 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsLandingPad; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// AddressTaken - Indicate that this basic block is potentially the 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// target of an indirect branch. 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool AddressTaken; 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Intrusive list support 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock() {} 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~MachineBasicBlock(); 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // MachineBasicBlocks are allocated and owned by MachineFunction. 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class MachineFunction; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getBasicBlock - Return the LLVM basic block that this instance 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// corresponded to originally. Note that this may be NULL if this instance 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// does not correspond directly to an LLVM basic block. 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BasicBlock *getBasicBlock() const { return BB; } 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getName - Return the name of the corresponding LLVM basic block, or 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// "(null)". 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StringRef getName() const; 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// hasAddressTaken - Test whether this block is potentially the target 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// of an indirect branch. 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool hasAddressTaken() const { return AddressTaken; } 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// setHasAddressTaken - Set this block to reflect that it potentially 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// is the target of an indirect branch. 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void setHasAddressTaken() { AddressTaken = true; } 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// getParent - Return the MachineFunction containing this basic block. 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const MachineFunction *getParent() const { return xParent; } 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) MachineFunction *getParent() { return xParent; } 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef Instructions::iterator iterator; 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef Instructions::const_iterator const_iterator; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::reverse_iterator<iterator> reverse_iterator; 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned size() const { return (unsigned)Insts.size(); } 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool empty() const { return Insts.empty(); } 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr& front() { return Insts.front(); } 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr& back() { return Insts.back(); } 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const MachineInstr& front() const { return Insts.front(); } 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const MachineInstr& back() const { return Insts.back(); } 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator begin() { return Insts.begin(); } 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_iterator begin() const { return Insts.begin(); } 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator end() { return Insts.end(); } 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_iterator end() const { return Insts.end(); } 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reverse_iterator rbegin() { return Insts.rbegin(); } 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_reverse_iterator rbegin() const { return Insts.rbegin(); } 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reverse_iterator rend () { return Insts.rend(); } 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_reverse_iterator rend () const { return Insts.rend(); } 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Machine-CFG iterators 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::reverse_iterator 1452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pred_reverse_iterator; 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_pred_reverse_iterator; 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::vector<MachineBasicBlock *>::reverse_iterator 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) succ_reverse_iterator; 1502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 1512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_succ_reverse_iterator; 1522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pred_iterator pred_begin() { return Predecessors.begin(); } 1542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_pred_iterator pred_begin() const { return Predecessors.begin(); } 1552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pred_iterator pred_end() { return Predecessors.end(); } 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_pred_iterator pred_end() const { return Predecessors.end(); } 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pred_reverse_iterator pred_rbegin() 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Predecessors.rbegin();} 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_pred_reverse_iterator pred_rbegin() const 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Predecessors.rbegin();} 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pred_reverse_iterator pred_rend() 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Predecessors.rend(); } 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_pred_reverse_iterator pred_rend() const 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Predecessors.rend(); } 165 unsigned pred_size() const { 166 return (unsigned)Predecessors.size(); 167 } 168 bool pred_empty() const { return Predecessors.empty(); } 169 succ_iterator succ_begin() { return Successors.begin(); } 170 const_succ_iterator succ_begin() const { return Successors.begin(); } 171 succ_iterator succ_end() { return Successors.end(); } 172 const_succ_iterator succ_end() const { return Successors.end(); } 173 succ_reverse_iterator succ_rbegin() 174 { return Successors.rbegin(); } 175 const_succ_reverse_iterator succ_rbegin() const 176 { return Successors.rbegin(); } 177 succ_reverse_iterator succ_rend() 178 { return Successors.rend(); } 179 const_succ_reverse_iterator succ_rend() const 180 { return Successors.rend(); } 181 unsigned succ_size() const { 182 return (unsigned)Successors.size(); 183 } 184 bool succ_empty() const { return Successors.empty(); } 185 186 // LiveIn management methods. 187 188 /// addLiveIn - Add the specified register as a live in. Note that it 189 /// is an error to add the same register to the same set more than once. 190 void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 191 192 /// removeLiveIn - Remove the specified register from the live in set. 193 /// 194 void removeLiveIn(unsigned Reg); 195 196 /// isLiveIn - Return true if the specified register is in the live in set. 197 /// 198 bool isLiveIn(unsigned Reg) const; 199 200 // Iteration support for live in sets. These sets are kept in sorted 201 // order by their register number. 202 typedef std::vector<unsigned>::iterator livein_iterator; 203 typedef std::vector<unsigned>::const_iterator const_livein_iterator; 204 livein_iterator livein_begin() { return LiveIns.begin(); } 205 const_livein_iterator livein_begin() const { return LiveIns.begin(); } 206 livein_iterator livein_end() { return LiveIns.end(); } 207 const_livein_iterator livein_end() const { return LiveIns.end(); } 208 bool livein_empty() const { return LiveIns.empty(); } 209 210 /// getAlignment - Return alignment of the basic block. 211 /// 212 unsigned getAlignment() const { return Alignment; } 213 214 /// setAlignment - Set alignment of the basic block. 215 /// 216 void setAlignment(unsigned Align) { Alignment = Align; } 217 218 /// isLandingPad - Returns true if the block is a landing pad. That is 219 /// this basic block is entered via an exception handler. 220 bool isLandingPad() const { return IsLandingPad; } 221 222 /// setIsLandingPad - Indicates the block is a landing pad. That is 223 /// this basic block is entered via an exception handler. 224 void setIsLandingPad() { IsLandingPad = true; } 225 226 // Code Layout methods. 227 228 /// moveBefore/moveAfter - move 'this' block before or after the specified 229 /// block. This only moves the block, it does not modify the CFG or adjust 230 /// potential fall-throughs at the end of the block. 231 void moveBefore(MachineBasicBlock *NewAfter); 232 void moveAfter(MachineBasicBlock *NewBefore); 233 234 /// updateTerminator - Update the terminator instructions in block to account 235 /// for changes to the layout. If the block previously used a fallthrough, 236 /// it may now need a branch, and if it previously used branching it may now 237 /// be able to use a fallthrough. 238 void updateTerminator(); 239 240 // Machine-CFG mutators 241 242 /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 243 /// The Predecessors list of succ is automatically updated. 244 /// 245 void addSuccessor(MachineBasicBlock *succ); 246 247 /// removeSuccessor - Remove successor from the successors list of this 248 /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 249 /// 250 void removeSuccessor(MachineBasicBlock *succ); 251 252 /// removeSuccessor - Remove specified successor from the successors list of 253 /// this MachineBasicBlock. The Predecessors list of succ is automatically 254 /// updated. Return the iterator to the element after the one removed. 255 /// 256 succ_iterator removeSuccessor(succ_iterator I); 257 258 /// transferSuccessors - Transfers all the successors from MBB to this 259 /// machine basic block (i.e., copies all the successors fromMBB and 260 /// remove all the successors from fromMBB). 261 void transferSuccessors(MachineBasicBlock *fromMBB); 262 263 /// isSuccessor - Return true if the specified MBB is a successor of this 264 /// block. 265 bool isSuccessor(const MachineBasicBlock *MBB) const; 266 267 /// isLayoutSuccessor - Return true if the specified MBB will be emitted 268 /// immediately after this block, such that if this block exits by 269 /// falling through, control will transfer to the specified MBB. Note 270 /// that MBB need not be a successor at all, for example if this block 271 /// ends with an unconditional branch to some other block. 272 bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 273 274 /// getFirstTerminator - returns an iterator to the first terminator 275 /// instruction of this basic block. If a terminator does not exist, 276 /// it returns end() 277 iterator getFirstTerminator(); 278 279 /// isOnlyReachableViaFallthough - Return true if this basic block has 280 /// exactly one predecessor and the control transfer mechanism between 281 /// the predecessor and this block is a fall-through. 282 bool isOnlyReachableByFallthrough() const; 283 284 void pop_front() { Insts.pop_front(); } 285 void pop_back() { Insts.pop_back(); } 286 void push_back(MachineInstr *MI) { Insts.push_back(MI); } 287 template<typename IT> 288 void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } 289 iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } 290 291 // erase - Remove the specified element or range from the instruction list. 292 // These functions delete any instructions removed. 293 // 294 iterator erase(iterator I) { return Insts.erase(I); } 295 iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } 296 MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } 297 void clear() { Insts.clear(); } 298 299 /// splice - Take an instruction from MBB 'Other' at the position From, 300 /// and insert it into this MBB right before 'where'. 301 void splice(iterator where, MachineBasicBlock *Other, iterator From) { 302 Insts.splice(where, Other->Insts, From); 303 } 304 305 /// splice - Take a block of instructions from MBB 'Other' in the range [From, 306 /// To), and insert them into this MBB right before 'where'. 307 void splice(iterator where, MachineBasicBlock *Other, iterator From, 308 iterator To) { 309 Insts.splice(where, Other->Insts, From, To); 310 } 311 312 /// removeFromParent - This method unlinks 'this' from the containing 313 /// function, and returns it, but does not delete it. 314 MachineBasicBlock *removeFromParent(); 315 316 /// eraseFromParent - This method unlinks 'this' from the containing 317 /// function and deletes it. 318 void eraseFromParent(); 319 320 /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 321 /// 'Old', change the code and CFG so that it branches to 'New' instead. 322 void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 323 324 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 325 /// the CFG to be inserted. If we have proven that MBB can only branch to 326 /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 327 /// DestB can be null. Besides DestA and DestB, retain other edges leading 328 /// to LandingPads (currently there can be only one; we don't check or require 329 /// that here). Note it is possible that DestA and/or DestB are LandingPads. 330 bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 331 MachineBasicBlock *DestB, 332 bool isCond); 333 334 // Debugging methods. 335 void dump() const; 336 void print(raw_ostream &OS) const; 337 338 /// getNumber - MachineBasicBlocks are uniquely numbered at the function 339 /// level, unless they're not in a MachineFunction yet, in which case this 340 /// will return -1. 341 /// 342 int getNumber() const { return Number; } 343 void setNumber(int N) { Number = N; } 344 345private: // Methods used to maintain doubly linked list of blocks... 346 friend struct ilist_traits<MachineBasicBlock>; 347 348 // Machine-CFG mutators 349 350 /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 351 /// Don't do this unless you know what you're doing, because it doesn't 352 /// update pred's successors list. Use pred->addSuccessor instead. 353 /// 354 void addPredecessor(MachineBasicBlock *pred); 355 356 /// removePredecessor - Remove pred as a predecessor of this 357 /// MachineBasicBlock. Don't do this unless you know what you're 358 /// doing, because it doesn't update pred's successors list. Use 359 /// pred->removeSuccessor instead. 360 /// 361 void removePredecessor(MachineBasicBlock *pred); 362}; 363 364raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 365 366void WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t); 367 368//===--------------------------------------------------------------------===// 369// GraphTraits specializations for machine basic block graphs (machine-CFGs) 370//===--------------------------------------------------------------------===// 371 372// Provide specializations of GraphTraits to be able to treat a 373// MachineFunction as a graph of MachineBasicBlocks... 374// 375 376template <> struct GraphTraits<MachineBasicBlock *> { 377 typedef MachineBasicBlock NodeType; 378 typedef MachineBasicBlock::succ_iterator ChildIteratorType; 379 380 static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 381 static inline ChildIteratorType child_begin(NodeType *N) { 382 return N->succ_begin(); 383 } 384 static inline ChildIteratorType child_end(NodeType *N) { 385 return N->succ_end(); 386 } 387}; 388 389template <> struct GraphTraits<const MachineBasicBlock *> { 390 typedef const MachineBasicBlock NodeType; 391 typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 392 393 static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 394 static inline ChildIteratorType child_begin(NodeType *N) { 395 return N->succ_begin(); 396 } 397 static inline ChildIteratorType child_end(NodeType *N) { 398 return N->succ_end(); 399 } 400}; 401 402// Provide specializations of GraphTraits to be able to treat a 403// MachineFunction as a graph of MachineBasicBlocks... and to walk it 404// in inverse order. Inverse order for a function is considered 405// to be when traversing the predecessor edges of a MBB 406// instead of the successor edges. 407// 408template <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 409 typedef MachineBasicBlock NodeType; 410 typedef MachineBasicBlock::pred_iterator ChildIteratorType; 411 static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 412 return G.Graph; 413 } 414 static inline ChildIteratorType child_begin(NodeType *N) { 415 return N->pred_begin(); 416 } 417 static inline ChildIteratorType child_end(NodeType *N) { 418 return N->pred_end(); 419 } 420}; 421 422template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 423 typedef const MachineBasicBlock NodeType; 424 typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 425 static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 426 return G.Graph; 427 } 428 static inline ChildIteratorType child_begin(NodeType *N) { 429 return N->pred_begin(); 430 } 431 static inline ChildIteratorType child_end(NodeType *N) { 432 return N->pred_end(); 433 } 434}; 435 436} // End llvm namespace 437 438#endif 439