MachineBasicBlock.h revision 218893
1316958Sdchagin//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 259243Sobrien// 359243Sobrien// The LLVM Compiler Infrastructure 459243Sobrien// 559243Sobrien// This file is distributed under the University of Illinois Open Source 659243Sobrien// License. See LICENSE.TXT for details. 759243Sobrien// 859243Sobrien//===----------------------------------------------------------------------===// 959243Sobrien// 1059243Sobrien// Collect the sequence of machine instructions for a basic block. 1159243Sobrien// 1259243Sobrien//===----------------------------------------------------------------------===// 1359243Sobrien 1459243Sobrien#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 1559243Sobrien#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 1659243Sobrien 17100616Smp#include "llvm/CodeGen/MachineInstr.h" 1859243Sobrien#include "llvm/ADT/GraphTraits.h" 1959243Sobrien 2059243Sobriennamespace llvm { 2159243Sobrien 2259243Sobrienclass Pass; 2359243Sobrienclass BasicBlock; 2459243Sobrienclass MachineFunction; 2559243Sobrienclass MCSymbol; 2659243Sobrienclass SlotIndexes; 2759243Sobrienclass StringRef; 2859243Sobrienclass raw_ostream; 2959243Sobrien 3059243Sobrientemplate <> 3159243Sobrienstruct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 3259243Sobrienprivate: 3359243Sobrien mutable ilist_half_node<MachineInstr> Sentinel; 3459243Sobrien 35316958Sdchagin // this is only set by the MachineBasicBlock owning the LiveList 3659243Sobrien friend class MachineBasicBlock; 3759243Sobrien MachineBasicBlock* Parent; 3859243Sobrien 3959243Sobrienpublic: 40167465Smp MachineInstr *createSentinel() const { 41167465Smp return static_cast<MachineInstr*>(&Sentinel); 42167465Smp } 43167465Smp void destroySentinel(MachineInstr *) const {} 44167465Smp 45167465Smp MachineInstr *provideInitialHead() const { return createSentinel(); } 46167465Smp MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 47167465Smp static void noteHead(MachineInstr*, MachineInstr*) {} 48167465Smp 4959243Sobrien void addNodeToList(MachineInstr* N); 5059243Sobrien void removeNodeFromList(MachineInstr* N); 5159243Sobrien void transferNodesFromList(ilist_traits &SrcTraits, 5259243Sobrien ilist_iterator<MachineInstr> first, 5359243Sobrien ilist_iterator<MachineInstr> last); 5459243Sobrien void deleteNode(MachineInstr *N); 5559243Sobrienprivate: 5659243Sobrien void createNode(const MachineInstr &); 57167465Smp}; 5859243Sobrien 5959243Sobrienclass MachineBasicBlock : public ilist_node<MachineBasicBlock> { 60145479Smp typedef ilist<MachineInstr> Instructions; 6159243Sobrien Instructions Insts; 6259243Sobrien const BasicBlock *BB; 6359243Sobrien int Number; 6459243Sobrien MachineFunction *xParent; 6559243Sobrien 6659243Sobrien /// Predecessors/Successors - Keep track of the predecessor / successor 6759243Sobrien /// basicblocks. 6859243Sobrien std::vector<MachineBasicBlock *> Predecessors; 6959243Sobrien std::vector<MachineBasicBlock *> Successors; 7059243Sobrien 7159243Sobrien /// LiveIns - Keep track of the physical registers that are livein of 7259243Sobrien /// the basicblock. 7359243Sobrien std::vector<unsigned> LiveIns; 74145479Smp 7559243Sobrien /// Alignment - Alignment of the basic block. Zero if the basic block does 7659243Sobrien /// not need to be aligned. 7759243Sobrien unsigned Alignment; 7859243Sobrien 7959243Sobrien /// IsLandingPad - Indicate that this basic block is entered via an 8059243Sobrien /// exception handler. 8159243Sobrien bool IsLandingPad; 8259243Sobrien 8359243Sobrien /// AddressTaken - Indicate that this basic block is potentially the 84145479Smp /// target of an indirect branch. 8559243Sobrien bool AddressTaken; 8659243Sobrien 8759243Sobrien // Intrusive list support 8859243Sobrien MachineBasicBlock() {} 8959243Sobrien 9059243Sobrien explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 9159243Sobrien 9259243Sobrien ~MachineBasicBlock(); 9359243Sobrien 9459243Sobrien // MachineBasicBlocks are allocated and owned by MachineFunction. 9559243Sobrien friend class MachineFunction; 9659243Sobrien 9759243Sobrienpublic: 9859243Sobrien /// getBasicBlock - Return the LLVM basic block that this instance 99145479Smp /// corresponded to originally. Note that this may be NULL if this instance 10059243Sobrien /// does not correspond directly to an LLVM basic block. 10159243Sobrien /// 10259243Sobrien const BasicBlock *getBasicBlock() const { return BB; } 10359243Sobrien 10459243Sobrien /// getName - Return the name of the corresponding LLVM basic block, or 10559243Sobrien /// "(null)". 10659243Sobrien StringRef getName() const; 10759243Sobrien 10859243Sobrien /// hasAddressTaken - Test whether this block is potentially the target 10959243Sobrien /// of an indirect branch. 11059243Sobrien bool hasAddressTaken() const { return AddressTaken; } 11159243Sobrien 11259243Sobrien /// setHasAddressTaken - Set this block to reflect that it potentially 11359243Sobrien /// is the target of an indirect branch. 11459243Sobrien void setHasAddressTaken() { AddressTaken = true; } 11559243Sobrien 11659243Sobrien /// getParent - Return the MachineFunction containing this basic block. 11759243Sobrien /// 11859243Sobrien const MachineFunction *getParent() const { return xParent; } 11959243Sobrien MachineFunction *getParent() { return xParent; } 12059243Sobrien 12159243Sobrien typedef Instructions::iterator iterator; 12259243Sobrien typedef Instructions::const_iterator const_iterator; 12359243Sobrien typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 12459243Sobrien typedef std::reverse_iterator<iterator> reverse_iterator; 12559243Sobrien 12659243Sobrien unsigned size() const { return (unsigned)Insts.size(); } 12759243Sobrien bool empty() const { return Insts.empty(); } 12859243Sobrien 12959243Sobrien MachineInstr& front() { return Insts.front(); } 13059243Sobrien MachineInstr& back() { return Insts.back(); } 131167465Smp const MachineInstr& front() const { return Insts.front(); } 13259243Sobrien const MachineInstr& back() const { return Insts.back(); } 13359243Sobrien 13459243Sobrien iterator begin() { return Insts.begin(); } 135145479Smp const_iterator begin() const { return Insts.begin(); } 13659243Sobrien iterator end() { return Insts.end(); } 13759243Sobrien const_iterator end() const { return Insts.end(); } 13859243Sobrien reverse_iterator rbegin() { return Insts.rbegin(); } 13959243Sobrien const_reverse_iterator rbegin() const { return Insts.rbegin(); } 14059243Sobrien reverse_iterator rend () { return Insts.rend(); } 14159243Sobrien const_reverse_iterator rend () const { return Insts.rend(); } 14259243Sobrien 14359243Sobrien // Machine-CFG iterators 144167465Smp typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 14559243Sobrien typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 146145479Smp typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 147145479Smp typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 148145479Smp typedef std::vector<MachineBasicBlock *>::reverse_iterator 149167465Smp pred_reverse_iterator; 150145479Smp typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 151145479Smp const_pred_reverse_iterator; 152145479Smp typedef std::vector<MachineBasicBlock *>::reverse_iterator 15359243Sobrien succ_reverse_iterator; 15459243Sobrien typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 155145479Smp const_succ_reverse_iterator; 156167465Smp 15759243Sobrien pred_iterator pred_begin() { return Predecessors.begin(); } 158167465Smp const_pred_iterator pred_begin() const { return Predecessors.begin(); } 15959243Sobrien pred_iterator pred_end() { return Predecessors.end(); } 16059243Sobrien const_pred_iterator pred_end() const { return Predecessors.end(); } 16159243Sobrien pred_reverse_iterator pred_rbegin() 16259243Sobrien { return Predecessors.rbegin();} 16359243Sobrien const_pred_reverse_iterator pred_rbegin() const 16459243Sobrien { return Predecessors.rbegin();} 16559243Sobrien pred_reverse_iterator pred_rend() 16659243Sobrien { return Predecessors.rend(); } 16759243Sobrien const_pred_reverse_iterator pred_rend() const 168167465Smp { return Predecessors.rend(); } 16959243Sobrien unsigned pred_size() const { 17059243Sobrien return (unsigned)Predecessors.size(); 17159243Sobrien } 17259243Sobrien bool pred_empty() const { return Predecessors.empty(); } 17359243Sobrien succ_iterator succ_begin() { return Successors.begin(); } 17459243Sobrien const_succ_iterator succ_begin() const { return Successors.begin(); } 17559243Sobrien succ_iterator succ_end() { return Successors.end(); } 176167465Smp const_succ_iterator succ_end() const { return Successors.end(); } 17759243Sobrien succ_reverse_iterator succ_rbegin() 17859243Sobrien { return Successors.rbegin(); } 17959243Sobrien const_succ_reverse_iterator succ_rbegin() const 18059243Sobrien { return Successors.rbegin(); } 181167465Smp succ_reverse_iterator succ_rend() 18259243Sobrien { return Successors.rend(); } 18359243Sobrien const_succ_reverse_iterator succ_rend() const 18459243Sobrien { return Successors.rend(); } 18559243Sobrien unsigned succ_size() const { 18659243Sobrien return (unsigned)Successors.size(); 187167465Smp } 188167465Smp bool succ_empty() const { return Successors.empty(); } 18959243Sobrien 190167465Smp // LiveIn management methods. 191167465Smp 19259243Sobrien /// addLiveIn - Add the specified register as a live in. Note that it 19359243Sobrien /// is an error to add the same register to the same set more than once. 194145479Smp void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 195167465Smp 196167465Smp /// removeLiveIn - Remove the specified register from the live in set. 19759243Sobrien /// 19859243Sobrien void removeLiveIn(unsigned Reg); 19959243Sobrien 20059243Sobrien /// isLiveIn - Return true if the specified register is in the live in set. 20159243Sobrien /// 20259243Sobrien bool isLiveIn(unsigned Reg) const; 203167465Smp 204167465Smp // Iteration support for live in sets. These sets are kept in sorted 20559243Sobrien // order by their register number. 206167465Smp typedef std::vector<unsigned>::const_iterator livein_iterator; 20759243Sobrien livein_iterator livein_begin() const { return LiveIns.begin(); } 20859243Sobrien livein_iterator livein_end() const { return LiveIns.end(); } 20959243Sobrien bool livein_empty() const { return LiveIns.empty(); } 21059243Sobrien 21159243Sobrien /// getAlignment - Return alignment of the basic block. 21259243Sobrien /// 21359243Sobrien unsigned getAlignment() const { return Alignment; } 21459243Sobrien 21559243Sobrien /// setAlignment - Set alignment of the basic block. 21659243Sobrien /// 21759243Sobrien void setAlignment(unsigned Align) { Alignment = Align; } 21859243Sobrien 21959243Sobrien /// isLandingPad - Returns true if the block is a landing pad. That is 22059243Sobrien /// this basic block is entered via an exception handler. 22159243Sobrien bool isLandingPad() const { return IsLandingPad; } 22259243Sobrien 22359243Sobrien /// setIsLandingPad - Indicates the block is a landing pad. That is 224167465Smp /// this basic block is entered via an exception handler. 22559243Sobrien void setIsLandingPad() { IsLandingPad = true; } 22659243Sobrien 22759243Sobrien /// getLandingPadSuccessor - If this block has a successor that is a landing 22859243Sobrien /// pad, return it. Otherwise return NULL. 22959243Sobrien const MachineBasicBlock *getLandingPadSuccessor() const; 230167465Smp 23159243Sobrien // Code Layout methods. 232145479Smp 23359243Sobrien /// moveBefore/moveAfter - move 'this' block before or after the specified 23459243Sobrien /// block. This only moves the block, it does not modify the CFG or adjust 235167465Smp /// potential fall-throughs at the end of the block. 236167465Smp void moveBefore(MachineBasicBlock *NewAfter); 237167465Smp void moveAfter(MachineBasicBlock *NewBefore); 238167465Smp 23959243Sobrien /// updateTerminator - Update the terminator instructions in block to account 24059243Sobrien /// for changes to the layout. If the block previously used a fallthrough, 241167465Smp /// it may now need a branch, and if it previously used branching it may now 24259243Sobrien /// be able to use a fallthrough. 24359243Sobrien void updateTerminator(); 244167465Smp 24559243Sobrien // Machine-CFG mutators 246167465Smp 24759243Sobrien /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 24859243Sobrien /// The Predecessors list of succ is automatically updated. 24959243Sobrien /// 25059243Sobrien void addSuccessor(MachineBasicBlock *succ); 251167465Smp 25259243Sobrien /// removeSuccessor - Remove successor from the successors list of this 253145479Smp /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 25459243Sobrien /// 25559243Sobrien void removeSuccessor(MachineBasicBlock *succ); 25659243Sobrien 25759243Sobrien /// removeSuccessor - Remove specified successor from the successors list of 25859243Sobrien /// this MachineBasicBlock. The Predecessors list of succ is automatically 25959243Sobrien /// updated. Return the iterator to the element after the one removed. 26059243Sobrien /// 26159243Sobrien succ_iterator removeSuccessor(succ_iterator I); 26259243Sobrien 26359243Sobrien /// transferSuccessors - Transfers all the successors from MBB to this 26459243Sobrien /// machine basic block (i.e., copies all the successors fromMBB and 26559243Sobrien /// remove all the successors from fromMBB). 266167465Smp void transferSuccessors(MachineBasicBlock *fromMBB); 26759243Sobrien 26859243Sobrien /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as 26959243Sobrien /// in transferSuccessors, and update PHI operands in the successor blocks 27059243Sobrien /// which refer to fromMBB to refer to this. 27159243Sobrien void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB); 272167465Smp 27359243Sobrien /// isSuccessor - Return true if the specified MBB is a successor of this 274167465Smp /// block. 27559243Sobrien bool isSuccessor(const MachineBasicBlock *MBB) const; 276167465Smp 27759243Sobrien /// isLayoutSuccessor - Return true if the specified MBB will be emitted 278167465Smp /// immediately after this block, such that if this block exits by 279167465Smp /// falling through, control will transfer to the specified MBB. Note 28059243Sobrien /// that MBB need not be a successor at all, for example if this block 28159243Sobrien /// ends with an unconditional branch to some other block. 28259243Sobrien bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 28359243Sobrien 28459243Sobrien /// canFallThrough - Return true if the block can implicitly transfer 28569408Sache /// control to the block after it by falling off the end of it. This should 286167465Smp /// return false if it can reach the block after it, but it uses an explicit 28769408Sache /// branch to do so (e.g., a table jump). True is a conservative answer. 288167465Smp bool canFallThrough(); 289167465Smp 29069408Sache /// Returns a pointer to the first instructon in this block that is not a 29159243Sobrien /// PHINode instruction. When adding instruction to the beginning of the 29259243Sobrien /// basic block, they should be added before the returned value, not before 29359243Sobrien /// the first instruction, which might be PHI. 29459243Sobrien /// Returns end() is there's no non-PHI instruction. 29559243Sobrien iterator getFirstNonPHI(); 29659243Sobrien 29769408Sache /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is 29859243Sobrien /// not a PHI or a label. This is the correct point to insert copies at the 29969408Sache /// beginning of a basic block. 300167465Smp iterator SkipPHIsAndLabels(iterator I); 301167465Smp 30259243Sobrien /// getFirstTerminator - returns an iterator to the first terminator 30359243Sobrien /// instruction of this basic block. If a terminator does not exist, 30459243Sobrien /// it returns end() 305167465Smp iterator getFirstTerminator(); 306167465Smp 30759243Sobrien /// getLastNonDebugInstr - returns an iterator to the last non-debug 30859243Sobrien /// instruction in the basic block, or end() 30959243Sobrien iterator getLastNonDebugInstr(); 31069408Sache 311167465Smp /// SplitCriticalEdge - Split the critical edge from this block to the 31269408Sache /// given successor block, and return the newly created block, or null 313167465Smp /// if splitting is not possible. 314167465Smp /// 31569408Sache /// This function updates LiveVariables, MachineDominatorTree, and 31659243Sobrien /// MachineLoopInfo, as applicable. 31759243Sobrien MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P); 31859243Sobrien 31969408Sache void pop_front() { Insts.pop_front(); } 320167465Smp void pop_back() { Insts.pop_back(); } 32169408Sache void push_back(MachineInstr *MI) { Insts.push_back(MI); } 322167465Smp template<typename IT> 32369408Sache void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } 324167465Smp iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } 32559243Sobrien iterator insertAfter(iterator I, MachineInstr *M) { 32659243Sobrien return Insts.insertAfter(I, M); 32759243Sobrien } 32859243Sobrien 329167465Smp // erase - Remove the specified element or range from the instruction list. 330167465Smp // These functions delete any instructions removed. 33159243Sobrien // 33269408Sache iterator erase(iterator I) { return Insts.erase(I); } 333167465Smp iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } 33469408Sache MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } 335167465Smp void clear() { Insts.clear(); } 33669408Sache 33759243Sobrien /// splice - Take an instruction from MBB 'Other' at the position From, 33859243Sobrien /// and insert it into this MBB right before 'where'. 33969408Sache void splice(iterator where, MachineBasicBlock *Other, iterator From) { 34059243Sobrien Insts.splice(where, Other->Insts, From); 34159243Sobrien } 34259243Sobrien 34359243Sobrien /// splice - Take a block of instructions from MBB 'Other' in the range [From, 34459243Sobrien /// To), and insert them into this MBB right before 'where'. 34559243Sobrien void splice(iterator where, MachineBasicBlock *Other, iterator From, 346167465Smp iterator To) { 34759243Sobrien Insts.splice(where, Other->Insts, From, To); 34859243Sobrien } 34959243Sobrien 35059243Sobrien /// removeFromParent - This method unlinks 'this' from the containing 35169408Sache /// function, and returns it, but does not delete it. 35259243Sobrien MachineBasicBlock *removeFromParent(); 35359243Sobrien 35459243Sobrien /// eraseFromParent - This method unlinks 'this' from the containing 35559243Sobrien /// function and deletes it. 35659243Sobrien void eraseFromParent(); 35759243Sobrien 35859243Sobrien /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 359167465Smp /// 'Old', change the code and CFG so that it branches to 'New' instead. 36059243Sobrien void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 36159243Sobrien 362167465Smp /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 363167465Smp /// the CFG to be inserted. If we have proven that MBB can only branch to 364167465Smp /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 365167465Smp /// DestB can be null. Besides DestA and DestB, retain other edges leading 366167465Smp /// to LandingPads (currently there can be only one; we don't check or require 367167465Smp /// that here). Note it is possible that DestA and/or DestB are LandingPads. 36859243Sobrien bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 369167465Smp MachineBasicBlock *DestB, 370167465Smp bool isCond); 371167465Smp 372167465Smp /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 373167465Smp /// any DBG_VALUE instructions. Return UnknownLoc if there is none. 37459243Sobrien DebugLoc findDebugLoc(MachineBasicBlock::iterator &MBBI); 37559243Sobrien 37659243Sobrien // Debugging methods. 37759243Sobrien void dump() const; 378167465Smp void print(raw_ostream &OS, SlotIndexes* = 0) const; 37959243Sobrien 380167465Smp /// getNumber - MachineBasicBlocks are uniquely numbered at the function 38159243Sobrien /// level, unless they're not in a MachineFunction yet, in which case this 382145479Smp /// will return -1. 38359243Sobrien /// 38459243Sobrien int getNumber() const { return Number; } 385195609Smp void setNumber(int N) { Number = N; } 38659243Sobrien 38759243Sobrien /// getSymbol - Return the MCSymbol for this basic block. 38859243Sobrien /// 389167465Smp MCSymbol *getSymbol() const; 39059243Sobrien 39159243Sobrienprivate: // Methods used to maintain doubly linked list of blocks... 392167465Smp friend struct ilist_traits<MachineBasicBlock>; 393167465Smp 39459243Sobrien // Machine-CFG mutators 395167465Smp 396167465Smp /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 39759243Sobrien /// Don't do this unless you know what you're doing, because it doesn't 39859243Sobrien /// update pred's successors list. Use pred->addSuccessor instead. 399167465Smp /// 40059243Sobrien void addPredecessor(MachineBasicBlock *pred); 401167465Smp 402167465Smp /// removePredecessor - Remove pred as a predecessor of this 403167465Smp /// MachineBasicBlock. Don't do this unless you know what you're 404167465Smp /// doing, because it doesn't update pred's successors list. Use 405167465Smp /// pred->removeSuccessor instead. 40659243Sobrien /// 40759243Sobrien void removePredecessor(MachineBasicBlock *pred); 40859243Sobrien}; 40959243Sobrien 410167465Smpraw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 41159243Sobrien 41259243Sobrienvoid WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t); 41359243Sobrien 41459243Sobrien//===--------------------------------------------------------------------===// 41559243Sobrien// GraphTraits specializations for machine basic block graphs (machine-CFGs) 41659243Sobrien//===--------------------------------------------------------------------===// 41759243Sobrien 418195609Smp// Provide specializations of GraphTraits to be able to treat a 41959243Sobrien// MachineFunction as a graph of MachineBasicBlocks... 42059243Sobrien// 42159243Sobrien 42259243Sobrientemplate <> struct GraphTraits<MachineBasicBlock *> { 42359243Sobrien typedef MachineBasicBlock NodeType; 42459243Sobrien typedef MachineBasicBlock::succ_iterator ChildIteratorType; 42559243Sobrien 42659243Sobrien static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 42759243Sobrien static inline ChildIteratorType child_begin(NodeType *N) { 428195609Smp return N->succ_begin(); 42959243Sobrien } 43059243Sobrien static inline ChildIteratorType child_end(NodeType *N) { 43159243Sobrien return N->succ_end(); 43259243Sobrien } 43359243Sobrien}; 43459243Sobrien 43559243Sobrientemplate <> struct GraphTraits<const MachineBasicBlock *> { 43659243Sobrien typedef const MachineBasicBlock NodeType; 437195609Smp typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 43859243Sobrien 439195609Smp static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 44059243Sobrien static inline ChildIteratorType child_begin(NodeType *N) { 44159243Sobrien return N->succ_begin(); 44259243Sobrien } 44359243Sobrien static inline ChildIteratorType child_end(NodeType *N) { 444167465Smp return N->succ_end(); 44559243Sobrien } 446145479Smp}; 44759243Sobrien 44859243Sobrien// Provide specializations of GraphTraits to be able to treat a 449167465Smp// MachineFunction as a graph of MachineBasicBlocks... and to walk it 45059243Sobrien// in inverse order. Inverse order for a function is considered 45159243Sobrien// to be when traversing the predecessor edges of a MBB 45259243Sobrien// instead of the successor edges. 45359243Sobrien// 45459243Sobrientemplate <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 45559243Sobrien typedef MachineBasicBlock NodeType; 45659243Sobrien typedef MachineBasicBlock::pred_iterator ChildIteratorType; 45759243Sobrien static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 45859243Sobrien return G.Graph; 45959243Sobrien } 460167465Smp static inline ChildIteratorType child_begin(NodeType *N) { 461167465Smp return N->pred_begin(); 46259243Sobrien } 46359243Sobrien static inline ChildIteratorType child_end(NodeType *N) { 464167465Smp return N->pred_end(); 465167465Smp } 46659243Sobrien}; 46759243Sobrien 46859243Sobrientemplate <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 46959243Sobrien typedef const MachineBasicBlock NodeType; 47059243Sobrien typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 471167465Smp static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 472167465Smp return G.Graph; 47359243Sobrien } 474167465Smp static inline ChildIteratorType child_begin(NodeType *N) { 475167465Smp return N->pred_begin(); 476167465Smp } 477167465Smp static inline ChildIteratorType child_end(NodeType *N) { 478167465Smp return N->pred_end(); 47959243Sobrien } 480167465Smp}; 48159243Sobrien 48259243Sobrien} // End llvm namespace 48359243Sobrien 484167465Smp#endif 485167465Smp