MachineBasicBlock.h revision 198090
1193323Sed//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// Collect the sequence of machine instructions for a basic block. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 15193323Sed#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 16193323Sed 17193323Sed#include "llvm/CodeGen/MachineInstr.h" 18193323Sed#include "llvm/ADT/GraphTraits.h" 19193323Sed 20193323Sednamespace llvm { 21193323Sed 22193323Sedclass BasicBlock; 23193323Sedclass MachineFunction; 24198090Srdivackyclass raw_ostream; 25193323Sed 26193323Sedtemplate <> 27193323Sedstruct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 28193323Sedprivate: 29198090Srdivacky mutable ilist_half_node<MachineInstr> Sentinel; 30193323Sed 31193323Sed // this is only set by the MachineBasicBlock owning the LiveList 32193323Sed friend class MachineBasicBlock; 33193323Sed MachineBasicBlock* Parent; 34193323Sed 35193323Sedpublic: 36193323Sed MachineInstr *createSentinel() const { 37193323Sed return static_cast<MachineInstr*>(&Sentinel); 38193323Sed } 39193323Sed void destroySentinel(MachineInstr *) const {} 40193323Sed 41193323Sed MachineInstr *provideInitialHead() const { return createSentinel(); } 42193323Sed MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 43193323Sed static void noteHead(MachineInstr*, MachineInstr*) {} 44193323Sed 45193323Sed void addNodeToList(MachineInstr* N); 46193323Sed void removeNodeFromList(MachineInstr* N); 47193323Sed void transferNodesFromList(ilist_traits &SrcTraits, 48193323Sed ilist_iterator<MachineInstr> first, 49193323Sed ilist_iterator<MachineInstr> last); 50193323Sed void deleteNode(MachineInstr *N); 51193323Sedprivate: 52193323Sed void createNode(const MachineInstr &); 53193323Sed}; 54193323Sed 55193323Sedclass MachineBasicBlock : public ilist_node<MachineBasicBlock> { 56193323Sed typedef ilist<MachineInstr> Instructions; 57193323Sed Instructions Insts; 58193323Sed const BasicBlock *BB; 59193323Sed int Number; 60193323Sed MachineFunction *xParent; 61193323Sed 62193323Sed /// Predecessors/Successors - Keep track of the predecessor / successor 63193323Sed /// basicblocks. 64193323Sed std::vector<MachineBasicBlock *> Predecessors; 65193323Sed std::vector<MachineBasicBlock *> Successors; 66193323Sed 67193323Sed /// LiveIns - Keep track of the physical registers that are livein of 68193323Sed /// the basicblock. 69193323Sed std::vector<unsigned> LiveIns; 70193323Sed 71193323Sed /// Alignment - Alignment of the basic block. Zero if the basic block does 72193323Sed /// not need to be aligned. 73193323Sed unsigned Alignment; 74193323Sed 75193323Sed /// IsLandingPad - Indicate that this basic block is entered via an 76193323Sed /// exception handler. 77193323Sed bool IsLandingPad; 78193323Sed 79193323Sed // Intrusive list support 80193323Sed MachineBasicBlock() {} 81193323Sed 82193323Sed explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 83193323Sed 84193323Sed ~MachineBasicBlock(); 85193323Sed 86193323Sed // MachineBasicBlocks are allocated and owned by MachineFunction. 87193323Sed friend class MachineFunction; 88193323Sed 89193323Sedpublic: 90193323Sed /// getBasicBlock - Return the LLVM basic block that this instance 91193323Sed /// corresponded to originally. 92193323Sed /// 93193323Sed const BasicBlock *getBasicBlock() const { return BB; } 94193323Sed 95193323Sed /// getParent - Return the MachineFunction containing this basic block. 96193323Sed /// 97193323Sed const MachineFunction *getParent() const { return xParent; } 98193323Sed MachineFunction *getParent() { return xParent; } 99193323Sed 100193323Sed typedef Instructions::iterator iterator; 101193323Sed typedef Instructions::const_iterator const_iterator; 102193323Sed typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 103193323Sed typedef std::reverse_iterator<iterator> reverse_iterator; 104193323Sed 105193323Sed unsigned size() const { return (unsigned)Insts.size(); } 106193323Sed bool empty() const { return Insts.empty(); } 107193323Sed 108193323Sed MachineInstr& front() { return Insts.front(); } 109193323Sed MachineInstr& back() { return Insts.back(); } 110193323Sed const MachineInstr& front() const { return Insts.front(); } 111193323Sed const MachineInstr& back() const { return Insts.back(); } 112193323Sed 113193323Sed iterator begin() { return Insts.begin(); } 114193323Sed const_iterator begin() const { return Insts.begin(); } 115193323Sed iterator end() { return Insts.end(); } 116193323Sed const_iterator end() const { return Insts.end(); } 117193323Sed reverse_iterator rbegin() { return Insts.rbegin(); } 118193323Sed const_reverse_iterator rbegin() const { return Insts.rbegin(); } 119193323Sed reverse_iterator rend () { return Insts.rend(); } 120193323Sed const_reverse_iterator rend () const { return Insts.rend(); } 121193323Sed 122193323Sed // Machine-CFG iterators 123193323Sed typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 124193323Sed typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 125193323Sed typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 126193323Sed typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 127193323Sed typedef std::vector<MachineBasicBlock *>::reverse_iterator 128193323Sed pred_reverse_iterator; 129193323Sed typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 130193323Sed const_pred_reverse_iterator; 131193323Sed typedef std::vector<MachineBasicBlock *>::reverse_iterator 132193323Sed succ_reverse_iterator; 133193323Sed typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 134193323Sed const_succ_reverse_iterator; 135193323Sed 136193323Sed pred_iterator pred_begin() { return Predecessors.begin(); } 137193323Sed const_pred_iterator pred_begin() const { return Predecessors.begin(); } 138193323Sed pred_iterator pred_end() { return Predecessors.end(); } 139193323Sed const_pred_iterator pred_end() const { return Predecessors.end(); } 140193323Sed pred_reverse_iterator pred_rbegin() 141193323Sed { return Predecessors.rbegin();} 142193323Sed const_pred_reverse_iterator pred_rbegin() const 143193323Sed { return Predecessors.rbegin();} 144193323Sed pred_reverse_iterator pred_rend() 145193323Sed { return Predecessors.rend(); } 146193323Sed const_pred_reverse_iterator pred_rend() const 147193323Sed { return Predecessors.rend(); } 148193323Sed unsigned pred_size() const { 149193323Sed return (unsigned)Predecessors.size(); 150193323Sed } 151193323Sed bool pred_empty() const { return Predecessors.empty(); } 152193323Sed succ_iterator succ_begin() { return Successors.begin(); } 153193323Sed const_succ_iterator succ_begin() const { return Successors.begin(); } 154193323Sed succ_iterator succ_end() { return Successors.end(); } 155193323Sed const_succ_iterator succ_end() const { return Successors.end(); } 156193323Sed succ_reverse_iterator succ_rbegin() 157193323Sed { return Successors.rbegin(); } 158193323Sed const_succ_reverse_iterator succ_rbegin() const 159193323Sed { return Successors.rbegin(); } 160193323Sed succ_reverse_iterator succ_rend() 161193323Sed { return Successors.rend(); } 162193323Sed const_succ_reverse_iterator succ_rend() const 163193323Sed { return Successors.rend(); } 164193323Sed unsigned succ_size() const { 165193323Sed return (unsigned)Successors.size(); 166193323Sed } 167193323Sed bool succ_empty() const { return Successors.empty(); } 168193323Sed 169193323Sed // LiveIn management methods. 170193323Sed 171193323Sed /// addLiveIn - Add the specified register as a live in. Note that it 172193323Sed /// is an error to add the same register to the same set more than once. 173193323Sed void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 174193323Sed 175193323Sed /// removeLiveIn - Remove the specified register from the live in set. 176193323Sed /// 177193323Sed void removeLiveIn(unsigned Reg); 178193323Sed 179193323Sed /// isLiveIn - Return true if the specified register is in the live in set. 180193323Sed /// 181193323Sed bool isLiveIn(unsigned Reg) const; 182193323Sed 183193323Sed // Iteration support for live in sets. These sets are kept in sorted 184193323Sed // order by their register number. 185193323Sed typedef std::vector<unsigned>::iterator livein_iterator; 186193323Sed typedef std::vector<unsigned>::const_iterator const_livein_iterator; 187193323Sed livein_iterator livein_begin() { return LiveIns.begin(); } 188193323Sed const_livein_iterator livein_begin() const { return LiveIns.begin(); } 189193323Sed livein_iterator livein_end() { return LiveIns.end(); } 190193323Sed const_livein_iterator livein_end() const { return LiveIns.end(); } 191193323Sed bool livein_empty() const { return LiveIns.empty(); } 192193323Sed 193193323Sed /// getAlignment - Return alignment of the basic block. 194193323Sed /// 195193323Sed unsigned getAlignment() const { return Alignment; } 196193323Sed 197193323Sed /// setAlignment - Set alignment of the basic block. 198193323Sed /// 199193323Sed void setAlignment(unsigned Align) { Alignment = Align; } 200193323Sed 201193323Sed /// isLandingPad - Returns true if the block is a landing pad. That is 202193323Sed /// this basic block is entered via an exception handler. 203193323Sed bool isLandingPad() const { return IsLandingPad; } 204193323Sed 205193323Sed /// setIsLandingPad - Indicates the block is a landing pad. That is 206193323Sed /// this basic block is entered via an exception handler. 207193323Sed void setIsLandingPad() { IsLandingPad = true; } 208193323Sed 209193323Sed // Code Layout methods. 210193323Sed 211193323Sed /// moveBefore/moveAfter - move 'this' block before or after the specified 212193323Sed /// block. This only moves the block, it does not modify the CFG or adjust 213193323Sed /// potential fall-throughs at the end of the block. 214193323Sed void moveBefore(MachineBasicBlock *NewAfter); 215193323Sed void moveAfter(MachineBasicBlock *NewBefore); 216193323Sed 217193323Sed // Machine-CFG mutators 218193323Sed 219193323Sed /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 220193323Sed /// The Predecessors list of succ is automatically updated. 221193323Sed /// 222193323Sed void addSuccessor(MachineBasicBlock *succ); 223193323Sed 224193323Sed /// removeSuccessor - Remove successor from the successors list of this 225193323Sed /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 226193323Sed /// 227193323Sed void removeSuccessor(MachineBasicBlock *succ); 228193323Sed 229193323Sed /// removeSuccessor - Remove specified successor from the successors list of 230193323Sed /// this MachineBasicBlock. The Predecessors list of succ is automatically 231193323Sed /// updated. Return the iterator to the element after the one removed. 232193323Sed /// 233193323Sed succ_iterator removeSuccessor(succ_iterator I); 234193323Sed 235193323Sed /// transferSuccessors - Transfers all the successors from MBB to this 236193323Sed /// machine basic block (i.e., copies all the successors fromMBB and 237193323Sed /// remove all the successors fromBB). 238193323Sed void transferSuccessors(MachineBasicBlock *fromMBB); 239193323Sed 240193323Sed /// isSuccessor - Return true if the specified MBB is a successor of this 241193323Sed /// block. 242193323Sed bool isSuccessor(const MachineBasicBlock *MBB) const; 243193323Sed 244193323Sed /// isLayoutSuccessor - Return true if the specified MBB will be emitted 245193323Sed /// immediately after this block, such that if this block exits by 246193323Sed /// falling through, control will transfer to the specified MBB. Note 247193323Sed /// that MBB need not be a successor at all, for example if this block 248193323Sed /// ends with an unconditional branch to some other block. 249193323Sed bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 250193323Sed 251193323Sed /// getFirstTerminator - returns an iterator to the first terminator 252193323Sed /// instruction of this basic block. If a terminator does not exist, 253193323Sed /// it returns end() 254193323Sed iterator getFirstTerminator(); 255193323Sed 256193323Sed /// isOnlyReachableViaFallthough - Return true if this basic block has 257193323Sed /// exactly one predecessor and the control transfer mechanism between 258193323Sed /// the predecessor and this block is a fall-through. 259193323Sed bool isOnlyReachableByFallthrough() const; 260193323Sed 261193323Sed void pop_front() { Insts.pop_front(); } 262193323Sed void pop_back() { Insts.pop_back(); } 263193323Sed void push_back(MachineInstr *MI) { Insts.push_back(MI); } 264193323Sed template<typename IT> 265193323Sed void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } 266193323Sed iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } 267193323Sed 268193323Sed // erase - Remove the specified element or range from the instruction list. 269193323Sed // These functions delete any instructions removed. 270193323Sed // 271193323Sed iterator erase(iterator I) { return Insts.erase(I); } 272193323Sed iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } 273193323Sed MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } 274193323Sed void clear() { Insts.clear(); } 275193323Sed 276193323Sed /// splice - Take an instruction from MBB 'Other' at the position From, 277193323Sed /// and insert it into this MBB right before 'where'. 278193323Sed void splice(iterator where, MachineBasicBlock *Other, iterator From) { 279193323Sed Insts.splice(where, Other->Insts, From); 280193323Sed } 281193323Sed 282193323Sed /// splice - Take a block of instructions from MBB 'Other' in the range [From, 283193323Sed /// To), and insert them into this MBB right before 'where'. 284193323Sed void splice(iterator where, MachineBasicBlock *Other, iterator From, 285193323Sed iterator To) { 286193323Sed Insts.splice(where, Other->Insts, From, To); 287193323Sed } 288193323Sed 289193323Sed /// removeFromParent - This method unlinks 'this' from the containing 290193323Sed /// function, and returns it, but does not delete it. 291193323Sed MachineBasicBlock *removeFromParent(); 292193323Sed 293193323Sed /// eraseFromParent - This method unlinks 'this' from the containing 294193323Sed /// function and deletes it. 295193323Sed void eraseFromParent(); 296193323Sed 297193323Sed /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 298193323Sed /// 'Old', change the code and CFG so that it branches to 'New' instead. 299193323Sed void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 300193323Sed 301193323Sed /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 302193323Sed /// the CFG to be inserted. If we have proven that MBB can only branch to 303193323Sed /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 304193323Sed /// DestB can be null. Besides DestA and DestB, retain other edges leading 305193323Sed /// to LandingPads (currently there can be only one; we don't check or require 306193323Sed /// that here). Note it is possible that DestA and/or DestB are LandingPads. 307193323Sed bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 308193323Sed MachineBasicBlock *DestB, 309193323Sed bool isCond); 310193323Sed 311193323Sed // Debugging methods. 312193323Sed void dump() const; 313198090Srdivacky void print(raw_ostream &OS) const; 314193323Sed 315193323Sed /// getNumber - MachineBasicBlocks are uniquely numbered at the function 316193323Sed /// level, unless they're not in a MachineFunction yet, in which case this 317193323Sed /// will return -1. 318193323Sed /// 319193323Sed int getNumber() const { return Number; } 320193323Sed void setNumber(int N) { Number = N; } 321193323Sed 322193323Sedprivate: // Methods used to maintain doubly linked list of blocks... 323193323Sed friend struct ilist_traits<MachineBasicBlock>; 324193323Sed 325193323Sed // Machine-CFG mutators 326193323Sed 327193323Sed /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 328193323Sed /// Don't do this unless you know what you're doing, because it doesn't 329193323Sed /// update pred's successors list. Use pred->addSuccessor instead. 330193323Sed /// 331193323Sed void addPredecessor(MachineBasicBlock *pred); 332193323Sed 333193323Sed /// removePredecessor - Remove pred as a predecessor of this 334193323Sed /// MachineBasicBlock. Don't do this unless you know what you're 335193323Sed /// doing, because it doesn't update pred's successors list. Use 336193323Sed /// pred->removeSuccessor instead. 337193323Sed /// 338193323Sed void removePredecessor(MachineBasicBlock *pred); 339193323Sed}; 340193323Sed 341198090Srdivackyraw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 342193323Sed 343193323Sed//===--------------------------------------------------------------------===// 344193323Sed// GraphTraits specializations for machine basic block graphs (machine-CFGs) 345193323Sed//===--------------------------------------------------------------------===// 346193323Sed 347193323Sed// Provide specializations of GraphTraits to be able to treat a 348193323Sed// MachineFunction as a graph of MachineBasicBlocks... 349193323Sed// 350193323Sed 351193323Sedtemplate <> struct GraphTraits<MachineBasicBlock *> { 352193323Sed typedef MachineBasicBlock NodeType; 353193323Sed typedef MachineBasicBlock::succ_iterator ChildIteratorType; 354193323Sed 355193323Sed static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 356193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 357193323Sed return N->succ_begin(); 358193323Sed } 359193323Sed static inline ChildIteratorType child_end(NodeType *N) { 360193323Sed return N->succ_end(); 361193323Sed } 362193323Sed}; 363193323Sed 364193323Sedtemplate <> struct GraphTraits<const MachineBasicBlock *> { 365193323Sed typedef const MachineBasicBlock NodeType; 366193323Sed typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 367193323Sed 368193323Sed static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 369193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 370193323Sed return N->succ_begin(); 371193323Sed } 372193323Sed static inline ChildIteratorType child_end(NodeType *N) { 373193323Sed return N->succ_end(); 374193323Sed } 375193323Sed}; 376193323Sed 377193323Sed// Provide specializations of GraphTraits to be able to treat a 378193323Sed// MachineFunction as a graph of MachineBasicBlocks... and to walk it 379193323Sed// in inverse order. Inverse order for a function is considered 380193323Sed// to be when traversing the predecessor edges of a MBB 381193323Sed// instead of the successor edges. 382193323Sed// 383193323Sedtemplate <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 384193323Sed typedef MachineBasicBlock NodeType; 385193323Sed typedef MachineBasicBlock::pred_iterator ChildIteratorType; 386193323Sed static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 387193323Sed return G.Graph; 388193323Sed } 389193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 390193323Sed return N->pred_begin(); 391193323Sed } 392193323Sed static inline ChildIteratorType child_end(NodeType *N) { 393193323Sed return N->pred_end(); 394193323Sed } 395193323Sed}; 396193323Sed 397193323Sedtemplate <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 398193323Sed typedef const MachineBasicBlock NodeType; 399193323Sed typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 400193323Sed static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 401193323Sed return G.Graph; 402193323Sed } 403193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 404193323Sed return N->pred_begin(); 405193323Sed } 406193323Sed static inline ChildIteratorType child_end(NodeType *N) { 407193323Sed return N->pred_end(); 408193323Sed } 409193323Sed}; 410193323Sed 411193323Sed} // End llvm namespace 412193323Sed 413193323Sed#endif 414