MachineBasicBlock.h revision 198892
110217Sphk//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 210217Sphk// 310217Sphk// The LLVM Compiler Infrastructure 410217Sphk// 510217Sphk// This file is distributed under the University of Illinois Open Source 610217Sphk// License. See LICENSE.TXT for details. 710217Sphk// 810217Sphk//===----------------------------------------------------------------------===// 910217Sphk// 1010217Sphk// Collect the sequence of machine instructions for a basic block. 1110217Sphk// 1210217Sphk//===----------------------------------------------------------------------===// 1310217Sphk 1410217Sphk#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 1510217Sphk#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 1610217Sphk 1710217Sphk#include "llvm/CodeGen/MachineInstr.h" 1810217Sphk#include "llvm/ADT/GraphTraits.h" 1910217Sphk 2010217Sphknamespace llvm { 2110217Sphk 2210217Sphkclass BasicBlock; 2310217Sphkclass MachineFunction; 2410217Sphkclass raw_ostream; 2510217Sphk 2610217Sphktemplate <> 2710217Sphkstruct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 2810217Sphkprivate: 2910217Sphk mutable ilist_half_node<MachineInstr> Sentinel; 3010217Sphk 3110217Sphk // this is only set by the MachineBasicBlock owning the LiveList 3210217Sphk friend class MachineBasicBlock; 3310217Sphk MachineBasicBlock* Parent; 3410217Sphk 3510217Sphkpublic: 3610217Sphk MachineInstr *createSentinel() const { 3710217Sphk return static_cast<MachineInstr*>(&Sentinel); 3810217Sphk } 3910217Sphk void destroySentinel(MachineInstr *) const {} 4010217Sphk 4110217Sphk MachineInstr *provideInitialHead() const { return createSentinel(); } 4210217Sphk MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 4310217Sphk static void noteHead(MachineInstr*, MachineInstr*) {} 4410217Sphk 4510217Sphk void addNodeToList(MachineInstr* N); 4610217Sphk void removeNodeFromList(MachineInstr* N); 4710217Sphk void transferNodesFromList(ilist_traits &SrcTraits, 4810217Sphk ilist_iterator<MachineInstr> first, 4910217Sphk ilist_iterator<MachineInstr> last); 5010217Sphk void deleteNode(MachineInstr *N); 5110217Sphkprivate: 5210217Sphk void createNode(const MachineInstr &); 5310217Sphk}; 5410217Sphk 5510217Sphkclass MachineBasicBlock : public ilist_node<MachineBasicBlock> { 5610217Sphk typedef ilist<MachineInstr> Instructions; 5710217Sphk Instructions Insts; 5810217Sphk const BasicBlock *BB; 5910217Sphk int Number; 6010217Sphk MachineFunction *xParent; 6110217Sphk 6210217Sphk /// Predecessors/Successors - Keep track of the predecessor / successor 6310217Sphk /// basicblocks. 6410217Sphk std::vector<MachineBasicBlock *> Predecessors; 6510217Sphk std::vector<MachineBasicBlock *> Successors; 6610217Sphk 6710217Sphk /// LiveIns - Keep track of the physical registers that are livein of 6810217Sphk /// the basicblock. 6910217Sphk std::vector<unsigned> LiveIns; 7010217Sphk 7110217Sphk /// Alignment - Alignment of the basic block. Zero if the basic block does 7210217Sphk /// not need to be aligned. 7310217Sphk unsigned Alignment; 7410217Sphk 7510217Sphk /// IsLandingPad - Indicate that this basic block is entered via an 7610217Sphk /// exception handler. 7710217Sphk bool IsLandingPad; 7810217Sphk 7910217Sphk /// AddressTaken - Indicate that this basic block is potentially the 8010217Sphk /// target of an indirect branch. 8110217Sphk bool AddressTaken; 8210217Sphk 8310217Sphk // Intrusive list support 8410217Sphk MachineBasicBlock() {} 8510217Sphk 8610217Sphk explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 8710217Sphk 8810217Sphk ~MachineBasicBlock(); 8910217Sphk 9010217Sphk // MachineBasicBlocks are allocated and owned by MachineFunction. 9110217Sphk friend class MachineFunction; 9210217Sphk 9310217Sphkpublic: 9410217Sphk /// getBasicBlock - Return the LLVM basic block that this instance 9510217Sphk /// corresponded to originally. 9610217Sphk /// 9710217Sphk const BasicBlock *getBasicBlock() const { return BB; } 9810217Sphk 9910217Sphk /// hasAddressTaken - Test whether this block is potentially the target 10010217Sphk /// of an indirect branch. 10110217Sphk bool hasAddressTaken() const { return AddressTaken; } 10210217Sphk 10310217Sphk /// setHasAddressTaken - Set this block to reflect that it potentially 10410217Sphk /// is the target of an indirect branch. 10510217Sphk void setHasAddressTaken() { AddressTaken = true; } 10610217Sphk 10710217Sphk /// getParent - Return the MachineFunction containing this basic block. 10810217Sphk /// 10910217Sphk const MachineFunction *getParent() const { return xParent; } 11010217Sphk MachineFunction *getParent() { return xParent; } 11110217Sphk 11210217Sphk typedef Instructions::iterator iterator; 11310217Sphk typedef Instructions::const_iterator const_iterator; 11410217Sphk typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 11510217Sphk typedef std::reverse_iterator<iterator> reverse_iterator; 11610217Sphk 11710217Sphk unsigned size() const { return (unsigned)Insts.size(); } 11810217Sphk bool empty() const { return Insts.empty(); } 11910217Sphk 12010217Sphk MachineInstr& front() { return Insts.front(); } 12110217Sphk MachineInstr& back() { return Insts.back(); } 12210217Sphk const MachineInstr& front() const { return Insts.front(); } 12310217Sphk const MachineInstr& back() const { return Insts.back(); } 12410217Sphk 12510217Sphk iterator begin() { return Insts.begin(); } 12610217Sphk const_iterator begin() const { return Insts.begin(); } 12710217Sphk iterator end() { return Insts.end(); } 12810217Sphk const_iterator end() const { return Insts.end(); } 12910217Sphk reverse_iterator rbegin() { return Insts.rbegin(); } 13010217Sphk const_reverse_iterator rbegin() const { return Insts.rbegin(); } 13110217Sphk reverse_iterator rend () { return Insts.rend(); } 13210217Sphk const_reverse_iterator rend () const { return Insts.rend(); } 13310217Sphk 13410217Sphk // Machine-CFG iterators 13510217Sphk typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 13610217Sphk typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 13710217Sphk typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 13810217Sphk typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 13910217Sphk typedef std::vector<MachineBasicBlock *>::reverse_iterator 14010217Sphk pred_reverse_iterator; 14110217Sphk typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 14210217Sphk const_pred_reverse_iterator; 14310217Sphk typedef std::vector<MachineBasicBlock *>::reverse_iterator 14410217Sphk succ_reverse_iterator; 14510217Sphk typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 14610217Sphk const_succ_reverse_iterator; 14710217Sphk 14810217Sphk pred_iterator pred_begin() { return Predecessors.begin(); } 14910217Sphk const_pred_iterator pred_begin() const { return Predecessors.begin(); } 15010217Sphk pred_iterator pred_end() { return Predecessors.end(); } 15110217Sphk const_pred_iterator pred_end() const { return Predecessors.end(); } 15210217Sphk pred_reverse_iterator pred_rbegin() 15310217Sphk { return Predecessors.rbegin();} 15410217Sphk const_pred_reverse_iterator pred_rbegin() const 15510217Sphk { return Predecessors.rbegin();} 15610217Sphk pred_reverse_iterator pred_rend() 15710217Sphk { return Predecessors.rend(); } 15810217Sphk const_pred_reverse_iterator pred_rend() const 15910217Sphk { return Predecessors.rend(); } 16010217Sphk unsigned pred_size() const { 16110217Sphk return (unsigned)Predecessors.size(); 16210217Sphk } 16310217Sphk bool pred_empty() const { return Predecessors.empty(); } 16410217Sphk succ_iterator succ_begin() { return Successors.begin(); } 16510217Sphk const_succ_iterator succ_begin() const { return Successors.begin(); } 16610217Sphk succ_iterator succ_end() { return Successors.end(); } 16710217Sphk const_succ_iterator succ_end() const { return Successors.end(); } 16810217Sphk succ_reverse_iterator succ_rbegin() 16910217Sphk { return Successors.rbegin(); } 17010217Sphk const_succ_reverse_iterator succ_rbegin() const 17110217Sphk { return Successors.rbegin(); } 17210217Sphk succ_reverse_iterator succ_rend() 17310217Sphk { return Successors.rend(); } 17410217Sphk const_succ_reverse_iterator succ_rend() const 17510217Sphk { return Successors.rend(); } 17610217Sphk unsigned succ_size() const { 17710217Sphk return (unsigned)Successors.size(); 17810217Sphk } 17910217Sphk bool succ_empty() const { return Successors.empty(); } 18010217Sphk 18110217Sphk // LiveIn management methods. 18210217Sphk 18310217Sphk /// addLiveIn - Add the specified register as a live in. Note that it 18410217Sphk /// is an error to add the same register to the same set more than once. 18510217Sphk void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 18610217Sphk 18710217Sphk /// removeLiveIn - Remove the specified register from the live in set. 18810217Sphk /// 18910217Sphk void removeLiveIn(unsigned Reg); 19010217Sphk 19110217Sphk /// isLiveIn - Return true if the specified register is in the live in set. 19210217Sphk /// 19310217Sphk bool isLiveIn(unsigned Reg) const; 19410217Sphk 19510217Sphk // Iteration support for live in sets. These sets are kept in sorted 19610217Sphk // order by their register number. 19710217Sphk typedef std::vector<unsigned>::iterator livein_iterator; 19810217Sphk typedef std::vector<unsigned>::const_iterator const_livein_iterator; 19910217Sphk livein_iterator livein_begin() { return LiveIns.begin(); } 20010217Sphk const_livein_iterator livein_begin() const { return LiveIns.begin(); } 20110217Sphk livein_iterator livein_end() { return LiveIns.end(); } 20210217Sphk const_livein_iterator livein_end() const { return LiveIns.end(); } 20310217Sphk bool livein_empty() const { return LiveIns.empty(); } 20410217Sphk 20510217Sphk /// getAlignment - Return alignment of the basic block. 20610217Sphk /// 20710217Sphk unsigned getAlignment() const { return Alignment; } 20810217Sphk 20910217Sphk /// setAlignment - Set alignment of the basic block. 21010217Sphk /// 21110217Sphk void setAlignment(unsigned Align) { Alignment = Align; } 21210217Sphk 21310217Sphk /// isLandingPad - Returns true if the block is a landing pad. That is 21410217Sphk /// this basic block is entered via an exception handler. 21510217Sphk bool isLandingPad() const { return IsLandingPad; } 21610217Sphk 21710217Sphk /// setIsLandingPad - Indicates the block is a landing pad. That is 21810217Sphk /// this basic block is entered via an exception handler. 21910217Sphk void setIsLandingPad() { IsLandingPad = true; } 22010217Sphk 22110217Sphk // Code Layout methods. 22210217Sphk 22310217Sphk /// moveBefore/moveAfter - move 'this' block before or after the specified 22410217Sphk /// block. This only moves the block, it does not modify the CFG or adjust 22510217Sphk /// potential fall-throughs at the end of the block. 22610217Sphk void moveBefore(MachineBasicBlock *NewAfter); 22710217Sphk void moveAfter(MachineBasicBlock *NewBefore); 22810217Sphk 22910217Sphk // Machine-CFG mutators 23010217Sphk 23110217Sphk /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 23210217Sphk /// The Predecessors list of succ is automatically updated. 23310217Sphk /// 23410217Sphk void addSuccessor(MachineBasicBlock *succ); 23510217Sphk 23610217Sphk /// removeSuccessor - Remove successor from the successors list of this 23710217Sphk /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 23810217Sphk /// 23910217Sphk void removeSuccessor(MachineBasicBlock *succ); 24010217Sphk 24110217Sphk /// removeSuccessor - Remove specified successor from the successors list of 24210217Sphk /// this MachineBasicBlock. The Predecessors list of succ is automatically 24310217Sphk /// updated. Return the iterator to the element after the one removed. 24410217Sphk /// 24510217Sphk succ_iterator removeSuccessor(succ_iterator I); 24610217Sphk 24710217Sphk /// transferSuccessors - Transfers all the successors from MBB to this 24810217Sphk /// machine basic block (i.e., copies all the successors fromMBB and 24910217Sphk /// remove all the successors fromBB). 25010217Sphk void transferSuccessors(MachineBasicBlock *fromMBB); 25110217Sphk 25210217Sphk /// isSuccessor - Return true if the specified MBB is a successor of this 25310217Sphk /// block. 25410217Sphk bool isSuccessor(const MachineBasicBlock *MBB) const; 25510217Sphk 25610217Sphk /// isLayoutSuccessor - Return true if the specified MBB will be emitted 25710217Sphk /// immediately after this block, such that if this block exits by 25810217Sphk /// falling through, control will transfer to the specified MBB. Note 25910217Sphk /// that MBB need not be a successor at all, for example if this block 26010217Sphk /// ends with an unconditional branch to some other block. 26110217Sphk bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 26210217Sphk 26310217Sphk /// getFirstTerminator - returns an iterator to the first terminator 26410217Sphk /// instruction of this basic block. If a terminator does not exist, 26510217Sphk /// it returns end() 26610217Sphk iterator getFirstTerminator(); 26710217Sphk 26810217Sphk /// isOnlyReachableViaFallthough - Return true if this basic block has 26910217Sphk /// exactly one predecessor and the control transfer mechanism between 27010217Sphk /// the predecessor and this block is a fall-through. 27110217Sphk bool isOnlyReachableByFallthrough() const; 27210217Sphk 27310217Sphk void pop_front() { Insts.pop_front(); } 27410217Sphk void pop_back() { Insts.pop_back(); } 27510217Sphk void push_back(MachineInstr *MI) { Insts.push_back(MI); } 27610217Sphk template<typename IT> 27710217Sphk void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } 27810217Sphk iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } 27910217Sphk 28010217Sphk // erase - Remove the specified element or range from the instruction list. 28110217Sphk // These functions delete any instructions removed. 28210217Sphk // 28310217Sphk iterator erase(iterator I) { return Insts.erase(I); } 28410217Sphk iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } 28510217Sphk MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } 28610217Sphk void clear() { Insts.clear(); } 28710217Sphk 28810217Sphk /// splice - Take an instruction from MBB 'Other' at the position From, 28910217Sphk /// and insert it into this MBB right before 'where'. 29010217Sphk void splice(iterator where, MachineBasicBlock *Other, iterator From) { 29110217Sphk Insts.splice(where, Other->Insts, From); 29210217Sphk } 29310217Sphk 29410217Sphk /// splice - Take a block of instructions from MBB 'Other' in the range [From, 29510217Sphk /// To), and insert them into this MBB right before 'where'. 29610217Sphk void splice(iterator where, MachineBasicBlock *Other, iterator From, 29710217Sphk iterator To) { 29810217Sphk Insts.splice(where, Other->Insts, From, To); 29910217Sphk } 30010217Sphk 30110217Sphk /// removeFromParent - This method unlinks 'this' from the containing 30210217Sphk /// function, and returns it, but does not delete it. 30310217Sphk MachineBasicBlock *removeFromParent(); 30410217Sphk 30510217Sphk /// eraseFromParent - This method unlinks 'this' from the containing 30610217Sphk /// function and deletes it. 30710217Sphk void eraseFromParent(); 30810217Sphk 30910217Sphk /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 31010217Sphk /// 'Old', change the code and CFG so that it branches to 'New' instead. 31110217Sphk void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 31210217Sphk 31310217Sphk /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 31410217Sphk /// the CFG to be inserted. If we have proven that MBB can only branch to 31510217Sphk /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 31610217Sphk /// DestB can be null. Besides DestA and DestB, retain other edges leading 31710217Sphk /// to LandingPads (currently there can be only one; we don't check or require 31810217Sphk /// that here). Note it is possible that DestA and/or DestB are LandingPads. 31910217Sphk bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 32010217Sphk MachineBasicBlock *DestB, 32110217Sphk bool isCond); 32210217Sphk 32310217Sphk // Debugging methods. 32410217Sphk void dump() const; 32510217Sphk void print(raw_ostream &OS) const; 32610217Sphk 32710217Sphk /// getNumber - MachineBasicBlocks are uniquely numbered at the function 32810217Sphk /// level, unless they're not in a MachineFunction yet, in which case this 32910217Sphk /// will return -1. 33010217Sphk /// 33110217Sphk int getNumber() const { return Number; } 33210217Sphk void setNumber(int N) { Number = N; } 33310217Sphk 33410217Sphkprivate: // Methods used to maintain doubly linked list of blocks... 33510217Sphk friend struct ilist_traits<MachineBasicBlock>; 33610217Sphk 33710217Sphk // Machine-CFG mutators 33810217Sphk 33910217Sphk /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 34010217Sphk /// Don't do this unless you know what you're doing, because it doesn't 34110217Sphk /// update pred's successors list. Use pred->addSuccessor instead. 34210217Sphk /// 34310217Sphk void addPredecessor(MachineBasicBlock *pred); 34410217Sphk 34510217Sphk /// removePredecessor - Remove pred as a predecessor of this 34610217Sphk /// MachineBasicBlock. Don't do this unless you know what you're 34710217Sphk /// doing, because it doesn't update pred's successors list. Use 34810217Sphk /// pred->removeSuccessor instead. 34910217Sphk /// 35010217Sphk void removePredecessor(MachineBasicBlock *pred); 35110217Sphk}; 35210217Sphk 35310217Sphkraw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 35410217Sphk 35510217Sphk//===--------------------------------------------------------------------===// 35610217Sphk// GraphTraits specializations for machine basic block graphs (machine-CFGs) 35710217Sphk//===--------------------------------------------------------------------===// 35810217Sphk 35910217Sphk// Provide specializations of GraphTraits to be able to treat a 36010217Sphk// MachineFunction as a graph of MachineBasicBlocks... 36110217Sphk// 36210217Sphk 36310217Sphktemplate <> struct GraphTraits<MachineBasicBlock *> { 36410217Sphk typedef MachineBasicBlock NodeType; 36510217Sphk typedef MachineBasicBlock::succ_iterator ChildIteratorType; 36610217Sphk 36710217Sphk static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 36810217Sphk static inline ChildIteratorType child_begin(NodeType *N) { 36910217Sphk return N->succ_begin(); 37010217Sphk } 37110217Sphk static inline ChildIteratorType child_end(NodeType *N) { 37210217Sphk return N->succ_end(); 37310217Sphk } 37410217Sphk}; 37510217Sphk 37610217Sphktemplate <> struct GraphTraits<const MachineBasicBlock *> { 37710217Sphk typedef const MachineBasicBlock NodeType; 37810217Sphk typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 37910217Sphk 38010217Sphk static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 38110217Sphk static inline ChildIteratorType child_begin(NodeType *N) { 38210217Sphk return N->succ_begin(); 38310217Sphk } 38410217Sphk static inline ChildIteratorType child_end(NodeType *N) { 38510217Sphk return N->succ_end(); 38610217Sphk } 38710217Sphk}; 38810217Sphk 38910217Sphk// Provide specializations of GraphTraits to be able to treat a 39010217Sphk// MachineFunction as a graph of MachineBasicBlocks... and to walk it 39110217Sphk// in inverse order. Inverse order for a function is considered 39210217Sphk// to be when traversing the predecessor edges of a MBB 39310217Sphk// instead of the successor edges. 39410217Sphk// 39510217Sphktemplate <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 39610217Sphk typedef MachineBasicBlock NodeType; 39710217Sphk typedef MachineBasicBlock::pred_iterator ChildIteratorType; 39810217Sphk static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 39910217Sphk return G.Graph; 40010217Sphk } 40110217Sphk static inline ChildIteratorType child_begin(NodeType *N) { 40210217Sphk return N->pred_begin(); 40310217Sphk } 40410217Sphk static inline ChildIteratorType child_end(NodeType *N) { 40510217Sphk return N->pred_end(); 40610217Sphk } 40710217Sphk}; 40810217Sphk 40910217Sphktemplate <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 41010217Sphk typedef const MachineBasicBlock NodeType; 41110217Sphk typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 41210217Sphk static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 41310217Sphk return G.Graph; 41410217Sphk } 41510217Sphk static inline ChildIteratorType child_begin(NodeType *N) { 41610217Sphk return N->pred_begin(); 41710217Sphk } 41810217Sphk static inline ChildIteratorType child_end(NodeType *N) { 41910217Sphk return N->pred_end(); 42010217Sphk } 42110217Sphk}; 42210217Sphk 42310217Sphk} // End llvm namespace 42410217Sphk 42510217Sphk#endif 42610217Sphk