MachineBasicBlock.h revision 221345
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" 19221345Sdim#include <functional> 20193323Sed 21193323Sednamespace llvm { 22193323Sed 23210299Sedclass Pass; 24193323Sedclass BasicBlock; 25193323Sedclass MachineFunction; 26203954Srdivackyclass MCSymbol; 27218893Sdimclass SlotIndexes; 28203954Srdivackyclass StringRef; 29198090Srdivackyclass raw_ostream; 30193323Sed 31193323Sedtemplate <> 32193323Sedstruct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 33193323Sedprivate: 34198090Srdivacky mutable ilist_half_node<MachineInstr> Sentinel; 35193323Sed 36193323Sed // this is only set by the MachineBasicBlock owning the LiveList 37193323Sed friend class MachineBasicBlock; 38193323Sed MachineBasicBlock* Parent; 39193323Sed 40193323Sedpublic: 41193323Sed MachineInstr *createSentinel() const { 42193323Sed return static_cast<MachineInstr*>(&Sentinel); 43193323Sed } 44193323Sed void destroySentinel(MachineInstr *) const {} 45193323Sed 46193323Sed MachineInstr *provideInitialHead() const { return createSentinel(); } 47193323Sed MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 48193323Sed static void noteHead(MachineInstr*, MachineInstr*) {} 49193323Sed 50193323Sed void addNodeToList(MachineInstr* N); 51193323Sed void removeNodeFromList(MachineInstr* N); 52193323Sed void transferNodesFromList(ilist_traits &SrcTraits, 53193323Sed ilist_iterator<MachineInstr> first, 54193323Sed ilist_iterator<MachineInstr> last); 55193323Sed void deleteNode(MachineInstr *N); 56193323Sedprivate: 57193323Sed void createNode(const MachineInstr &); 58193323Sed}; 59193323Sed 60193323Sedclass MachineBasicBlock : public ilist_node<MachineBasicBlock> { 61193323Sed typedef ilist<MachineInstr> Instructions; 62193323Sed Instructions Insts; 63193323Sed const BasicBlock *BB; 64193323Sed int Number; 65193323Sed MachineFunction *xParent; 66193323Sed 67193323Sed /// Predecessors/Successors - Keep track of the predecessor / successor 68193323Sed /// basicblocks. 69193323Sed std::vector<MachineBasicBlock *> Predecessors; 70193323Sed std::vector<MachineBasicBlock *> Successors; 71193323Sed 72193323Sed /// LiveIns - Keep track of the physical registers that are livein of 73193323Sed /// the basicblock. 74193323Sed std::vector<unsigned> LiveIns; 75193323Sed 76193323Sed /// Alignment - Alignment of the basic block. Zero if the basic block does 77193323Sed /// not need to be aligned. 78193323Sed unsigned Alignment; 79193323Sed 80193323Sed /// IsLandingPad - Indicate that this basic block is entered via an 81193323Sed /// exception handler. 82193323Sed bool IsLandingPad; 83193323Sed 84198892Srdivacky /// AddressTaken - Indicate that this basic block is potentially the 85198892Srdivacky /// target of an indirect branch. 86198892Srdivacky bool AddressTaken; 87198892Srdivacky 88193323Sed // Intrusive list support 89193323Sed MachineBasicBlock() {} 90193323Sed 91193323Sed explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 92193323Sed 93193323Sed ~MachineBasicBlock(); 94193323Sed 95193323Sed // MachineBasicBlocks are allocated and owned by MachineFunction. 96193323Sed friend class MachineFunction; 97193323Sed 98193323Sedpublic: 99193323Sed /// getBasicBlock - Return the LLVM basic block that this instance 100199989Srdivacky /// corresponded to originally. Note that this may be NULL if this instance 101199989Srdivacky /// does not correspond directly to an LLVM basic block. 102193323Sed /// 103193323Sed const BasicBlock *getBasicBlock() const { return BB; } 104193323Sed 105199989Srdivacky /// getName - Return the name of the corresponding LLVM basic block, or 106199989Srdivacky /// "(null)". 107199989Srdivacky StringRef getName() const; 108199989Srdivacky 109198892Srdivacky /// hasAddressTaken - Test whether this block is potentially the target 110198892Srdivacky /// of an indirect branch. 111198892Srdivacky bool hasAddressTaken() const { return AddressTaken; } 112198892Srdivacky 113198892Srdivacky /// setHasAddressTaken - Set this block to reflect that it potentially 114198892Srdivacky /// is the target of an indirect branch. 115198892Srdivacky void setHasAddressTaken() { AddressTaken = true; } 116198892Srdivacky 117193323Sed /// getParent - Return the MachineFunction containing this basic block. 118193323Sed /// 119193323Sed const MachineFunction *getParent() const { return xParent; } 120193323Sed MachineFunction *getParent() { return xParent; } 121193323Sed 122193323Sed typedef Instructions::iterator iterator; 123193323Sed typedef Instructions::const_iterator const_iterator; 124193323Sed typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 125193323Sed typedef std::reverse_iterator<iterator> reverse_iterator; 126193323Sed 127193323Sed unsigned size() const { return (unsigned)Insts.size(); } 128193323Sed bool empty() const { return Insts.empty(); } 129193323Sed 130193323Sed MachineInstr& front() { return Insts.front(); } 131193323Sed MachineInstr& back() { return Insts.back(); } 132193323Sed const MachineInstr& front() const { return Insts.front(); } 133193323Sed const MachineInstr& back() const { return Insts.back(); } 134193323Sed 135193323Sed iterator begin() { return Insts.begin(); } 136193323Sed const_iterator begin() const { return Insts.begin(); } 137193323Sed iterator end() { return Insts.end(); } 138193323Sed const_iterator end() const { return Insts.end(); } 139193323Sed reverse_iterator rbegin() { return Insts.rbegin(); } 140193323Sed const_reverse_iterator rbegin() const { return Insts.rbegin(); } 141193323Sed reverse_iterator rend () { return Insts.rend(); } 142193323Sed const_reverse_iterator rend () const { return Insts.rend(); } 143193323Sed 144193323Sed // Machine-CFG iterators 145193323Sed typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 146193323Sed typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 147193323Sed typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 148193323Sed typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 149193323Sed typedef std::vector<MachineBasicBlock *>::reverse_iterator 150193323Sed pred_reverse_iterator; 151193323Sed typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 152193323Sed const_pred_reverse_iterator; 153193323Sed typedef std::vector<MachineBasicBlock *>::reverse_iterator 154193323Sed succ_reverse_iterator; 155193323Sed typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 156193323Sed const_succ_reverse_iterator; 157193323Sed 158193323Sed pred_iterator pred_begin() { return Predecessors.begin(); } 159193323Sed const_pred_iterator pred_begin() const { return Predecessors.begin(); } 160193323Sed pred_iterator pred_end() { return Predecessors.end(); } 161193323Sed const_pred_iterator pred_end() const { return Predecessors.end(); } 162193323Sed pred_reverse_iterator pred_rbegin() 163193323Sed { return Predecessors.rbegin();} 164193323Sed const_pred_reverse_iterator pred_rbegin() const 165193323Sed { return Predecessors.rbegin();} 166193323Sed pred_reverse_iterator pred_rend() 167193323Sed { return Predecessors.rend(); } 168193323Sed const_pred_reverse_iterator pred_rend() const 169193323Sed { return Predecessors.rend(); } 170193323Sed unsigned pred_size() const { 171193323Sed return (unsigned)Predecessors.size(); 172193323Sed } 173193323Sed bool pred_empty() const { return Predecessors.empty(); } 174193323Sed succ_iterator succ_begin() { return Successors.begin(); } 175193323Sed const_succ_iterator succ_begin() const { return Successors.begin(); } 176193323Sed succ_iterator succ_end() { return Successors.end(); } 177193323Sed const_succ_iterator succ_end() const { return Successors.end(); } 178193323Sed succ_reverse_iterator succ_rbegin() 179193323Sed { return Successors.rbegin(); } 180193323Sed const_succ_reverse_iterator succ_rbegin() const 181193323Sed { return Successors.rbegin(); } 182193323Sed succ_reverse_iterator succ_rend() 183193323Sed { return Successors.rend(); } 184193323Sed const_succ_reverse_iterator succ_rend() const 185193323Sed { return Successors.rend(); } 186193323Sed unsigned succ_size() const { 187193323Sed return (unsigned)Successors.size(); 188193323Sed } 189193323Sed bool succ_empty() const { return Successors.empty(); } 190193323Sed 191193323Sed // LiveIn management methods. 192193323Sed 193193323Sed /// addLiveIn - Add the specified register as a live in. Note that it 194193323Sed /// is an error to add the same register to the same set more than once. 195193323Sed void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 196193323Sed 197193323Sed /// removeLiveIn - Remove the specified register from the live in set. 198193323Sed /// 199193323Sed void removeLiveIn(unsigned Reg); 200193323Sed 201193323Sed /// isLiveIn - Return true if the specified register is in the live in set. 202193323Sed /// 203193323Sed bool isLiveIn(unsigned Reg) const; 204193323Sed 205193323Sed // Iteration support for live in sets. These sets are kept in sorted 206193323Sed // order by their register number. 207207618Srdivacky typedef std::vector<unsigned>::const_iterator livein_iterator; 208207618Srdivacky livein_iterator livein_begin() const { return LiveIns.begin(); } 209207618Srdivacky livein_iterator livein_end() const { return LiveIns.end(); } 210193323Sed bool livein_empty() const { return LiveIns.empty(); } 211193323Sed 212193323Sed /// getAlignment - Return alignment of the basic block. 213193323Sed /// 214193323Sed unsigned getAlignment() const { return Alignment; } 215193323Sed 216193323Sed /// setAlignment - Set alignment of the basic block. 217193323Sed /// 218193323Sed void setAlignment(unsigned Align) { Alignment = Align; } 219193323Sed 220193323Sed /// isLandingPad - Returns true if the block is a landing pad. That is 221193323Sed /// this basic block is entered via an exception handler. 222193323Sed bool isLandingPad() const { return IsLandingPad; } 223193323Sed 224193323Sed /// setIsLandingPad - Indicates the block is a landing pad. That is 225193323Sed /// this basic block is entered via an exception handler. 226193323Sed void setIsLandingPad() { IsLandingPad = true; } 227193323Sed 228218893Sdim /// getLandingPadSuccessor - If this block has a successor that is a landing 229218893Sdim /// pad, return it. Otherwise return NULL. 230218893Sdim const MachineBasicBlock *getLandingPadSuccessor() const; 231218893Sdim 232193323Sed // Code Layout methods. 233193323Sed 234193323Sed /// moveBefore/moveAfter - move 'this' block before or after the specified 235193323Sed /// block. This only moves the block, it does not modify the CFG or adjust 236193323Sed /// potential fall-throughs at the end of the block. 237193323Sed void moveBefore(MachineBasicBlock *NewAfter); 238193323Sed void moveAfter(MachineBasicBlock *NewBefore); 239199481Srdivacky 240199481Srdivacky /// updateTerminator - Update the terminator instructions in block to account 241199481Srdivacky /// for changes to the layout. If the block previously used a fallthrough, 242199481Srdivacky /// it may now need a branch, and if it previously used branching it may now 243199481Srdivacky /// be able to use a fallthrough. 244199481Srdivacky void updateTerminator(); 245199481Srdivacky 246193323Sed // Machine-CFG mutators 247193323Sed 248193323Sed /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 249193323Sed /// The Predecessors list of succ is automatically updated. 250193323Sed /// 251193323Sed void addSuccessor(MachineBasicBlock *succ); 252193323Sed 253193323Sed /// removeSuccessor - Remove successor from the successors list of this 254193323Sed /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 255193323Sed /// 256193323Sed void removeSuccessor(MachineBasicBlock *succ); 257193323Sed 258193323Sed /// removeSuccessor - Remove specified successor from the successors list of 259193323Sed /// this MachineBasicBlock. The Predecessors list of succ is automatically 260193323Sed /// updated. Return the iterator to the element after the one removed. 261193323Sed /// 262193323Sed succ_iterator removeSuccessor(succ_iterator I); 263193323Sed 264193323Sed /// transferSuccessors - Transfers all the successors from MBB to this 265193323Sed /// machine basic block (i.e., copies all the successors fromMBB and 266199481Srdivacky /// remove all the successors from fromMBB). 267193323Sed void transferSuccessors(MachineBasicBlock *fromMBB); 268210299Sed 269210299Sed /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as 270210299Sed /// in transferSuccessors, and update PHI operands in the successor blocks 271210299Sed /// which refer to fromMBB to refer to this. 272210299Sed void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB); 273193323Sed 274193323Sed /// isSuccessor - Return true if the specified MBB is a successor of this 275193323Sed /// block. 276193323Sed bool isSuccessor(const MachineBasicBlock *MBB) const; 277193323Sed 278193323Sed /// isLayoutSuccessor - Return true if the specified MBB will be emitted 279193323Sed /// immediately after this block, such that if this block exits by 280193323Sed /// falling through, control will transfer to the specified MBB. Note 281193323Sed /// that MBB need not be a successor at all, for example if this block 282193323Sed /// ends with an unconditional branch to some other block. 283193323Sed bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 284193323Sed 285199989Srdivacky /// canFallThrough - Return true if the block can implicitly transfer 286199989Srdivacky /// control to the block after it by falling off the end of it. This should 287199989Srdivacky /// return false if it can reach the block after it, but it uses an explicit 288199989Srdivacky /// branch to do so (e.g., a table jump). True is a conservative answer. 289199989Srdivacky bool canFallThrough(); 290199989Srdivacky 291210299Sed /// Returns a pointer to the first instructon in this block that is not a 292210299Sed /// PHINode instruction. When adding instruction to the beginning of the 293210299Sed /// basic block, they should be added before the returned value, not before 294210299Sed /// the first instruction, which might be PHI. 295210299Sed /// Returns end() is there's no non-PHI instruction. 296210299Sed iterator getFirstNonPHI(); 297210299Sed 298218893Sdim /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is 299218893Sdim /// not a PHI or a label. This is the correct point to insert copies at the 300218893Sdim /// beginning of a basic block. 301218893Sdim iterator SkipPHIsAndLabels(iterator I); 302218893Sdim 303193323Sed /// getFirstTerminator - returns an iterator to the first terminator 304193323Sed /// instruction of this basic block. If a terminator does not exist, 305193323Sed /// it returns end() 306193323Sed iterator getFirstTerminator(); 307193323Sed 308221345Sdim const_iterator getFirstTerminator() const { 309221345Sdim return const_cast<MachineBasicBlock*>(this)->getFirstTerminator(); 310221345Sdim } 311221345Sdim 312218893Sdim /// getLastNonDebugInstr - returns an iterator to the last non-debug 313218893Sdim /// instruction in the basic block, or end() 314218893Sdim iterator getLastNonDebugInstr(); 315218893Sdim 316221345Sdim const_iterator getLastNonDebugInstr() const { 317221345Sdim return const_cast<MachineBasicBlock*>(this)->getLastNonDebugInstr(); 318221345Sdim } 319221345Sdim 320210299Sed /// SplitCriticalEdge - Split the critical edge from this block to the 321210299Sed /// given successor block, and return the newly created block, or null 322210299Sed /// if splitting is not possible. 323210299Sed /// 324210299Sed /// This function updates LiveVariables, MachineDominatorTree, and 325210299Sed /// MachineLoopInfo, as applicable. 326210299Sed MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P); 327210299Sed 328193323Sed void pop_front() { Insts.pop_front(); } 329193323Sed void pop_back() { Insts.pop_back(); } 330193323Sed void push_back(MachineInstr *MI) { Insts.push_back(MI); } 331193323Sed template<typename IT> 332193323Sed void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } 333193323Sed iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } 334218893Sdim iterator insertAfter(iterator I, MachineInstr *M) { 335218893Sdim return Insts.insertAfter(I, M); 336218893Sdim } 337193323Sed 338193323Sed // erase - Remove the specified element or range from the instruction list. 339193323Sed // These functions delete any instructions removed. 340193323Sed // 341193323Sed iterator erase(iterator I) { return Insts.erase(I); } 342193323Sed iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } 343193323Sed MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } 344193323Sed void clear() { Insts.clear(); } 345193323Sed 346193323Sed /// splice - Take an instruction from MBB 'Other' at the position From, 347193323Sed /// and insert it into this MBB right before 'where'. 348193323Sed void splice(iterator where, MachineBasicBlock *Other, iterator From) { 349193323Sed Insts.splice(where, Other->Insts, From); 350193323Sed } 351193323Sed 352193323Sed /// splice - Take a block of instructions from MBB 'Other' in the range [From, 353193323Sed /// To), and insert them into this MBB right before 'where'. 354193323Sed void splice(iterator where, MachineBasicBlock *Other, iterator From, 355193323Sed iterator To) { 356193323Sed Insts.splice(where, Other->Insts, From, To); 357193323Sed } 358193323Sed 359193323Sed /// removeFromParent - This method unlinks 'this' from the containing 360193323Sed /// function, and returns it, but does not delete it. 361193323Sed MachineBasicBlock *removeFromParent(); 362193323Sed 363193323Sed /// eraseFromParent - This method unlinks 'this' from the containing 364193323Sed /// function and deletes it. 365193323Sed void eraseFromParent(); 366193323Sed 367193323Sed /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 368193323Sed /// 'Old', change the code and CFG so that it branches to 'New' instead. 369193323Sed void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 370193323Sed 371193323Sed /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 372193323Sed /// the CFG to be inserted. If we have proven that MBB can only branch to 373193323Sed /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 374193323Sed /// DestB can be null. Besides DestA and DestB, retain other edges leading 375193323Sed /// to LandingPads (currently there can be only one; we don't check or require 376193323Sed /// that here). Note it is possible that DestA and/or DestB are LandingPads. 377193323Sed bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 378193323Sed MachineBasicBlock *DestB, 379193323Sed bool isCond); 380193323Sed 381202878Srdivacky /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 382203954Srdivacky /// any DBG_VALUE instructions. Return UnknownLoc if there is none. 383202878Srdivacky DebugLoc findDebugLoc(MachineBasicBlock::iterator &MBBI); 384202878Srdivacky 385193323Sed // Debugging methods. 386193323Sed void dump() const; 387218893Sdim void print(raw_ostream &OS, SlotIndexes* = 0) const; 388193323Sed 389193323Sed /// getNumber - MachineBasicBlocks are uniquely numbered at the function 390193323Sed /// level, unless they're not in a MachineFunction yet, in which case this 391193323Sed /// will return -1. 392193323Sed /// 393193323Sed int getNumber() const { return Number; } 394193323Sed void setNumber(int N) { Number = N; } 395193323Sed 396203954Srdivacky /// getSymbol - Return the MCSymbol for this basic block. 397203954Srdivacky /// 398205218Srdivacky MCSymbol *getSymbol() const; 399203954Srdivacky 400193323Sedprivate: // Methods used to maintain doubly linked list of blocks... 401193323Sed friend struct ilist_traits<MachineBasicBlock>; 402193323Sed 403193323Sed // Machine-CFG mutators 404193323Sed 405193323Sed /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 406193323Sed /// Don't do this unless you know what you're doing, because it doesn't 407193323Sed /// update pred's successors list. Use pred->addSuccessor instead. 408193323Sed /// 409193323Sed void addPredecessor(MachineBasicBlock *pred); 410193323Sed 411193323Sed /// removePredecessor - Remove pred as a predecessor of this 412193323Sed /// MachineBasicBlock. Don't do this unless you know what you're 413193323Sed /// doing, because it doesn't update pred's successors list. Use 414193323Sed /// pred->removeSuccessor instead. 415193323Sed /// 416193323Sed void removePredecessor(MachineBasicBlock *pred); 417193323Sed}; 418193323Sed 419198090Srdivackyraw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 420193323Sed 421199481Srdivackyvoid WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t); 422199481Srdivacky 423221345Sdim// This is useful when building IndexedMaps keyed on basic block pointers. 424221345Sdimstruct MBB2NumberFunctor : 425221345Sdim public std::unary_function<const MachineBasicBlock*, unsigned> { 426221345Sdim unsigned operator()(const MachineBasicBlock *MBB) const { 427221345Sdim return MBB->getNumber(); 428221345Sdim } 429221345Sdim}; 430221345Sdim 431193323Sed//===--------------------------------------------------------------------===// 432193323Sed// GraphTraits specializations for machine basic block graphs (machine-CFGs) 433193323Sed//===--------------------------------------------------------------------===// 434193323Sed 435193323Sed// Provide specializations of GraphTraits to be able to treat a 436193323Sed// MachineFunction as a graph of MachineBasicBlocks... 437193323Sed// 438193323Sed 439193323Sedtemplate <> struct GraphTraits<MachineBasicBlock *> { 440193323Sed typedef MachineBasicBlock NodeType; 441193323Sed typedef MachineBasicBlock::succ_iterator ChildIteratorType; 442193323Sed 443193323Sed static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 444193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 445193323Sed return N->succ_begin(); 446193323Sed } 447193323Sed static inline ChildIteratorType child_end(NodeType *N) { 448193323Sed return N->succ_end(); 449193323Sed } 450193323Sed}; 451193323Sed 452193323Sedtemplate <> struct GraphTraits<const MachineBasicBlock *> { 453193323Sed typedef const MachineBasicBlock NodeType; 454193323Sed typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 455193323Sed 456193323Sed static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 457193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 458193323Sed return N->succ_begin(); 459193323Sed } 460193323Sed static inline ChildIteratorType child_end(NodeType *N) { 461193323Sed return N->succ_end(); 462193323Sed } 463193323Sed}; 464193323Sed 465193323Sed// Provide specializations of GraphTraits to be able to treat a 466193323Sed// MachineFunction as a graph of MachineBasicBlocks... and to walk it 467193323Sed// in inverse order. Inverse order for a function is considered 468193323Sed// to be when traversing the predecessor edges of a MBB 469193323Sed// instead of the successor edges. 470193323Sed// 471193323Sedtemplate <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 472193323Sed typedef MachineBasicBlock NodeType; 473193323Sed typedef MachineBasicBlock::pred_iterator ChildIteratorType; 474193323Sed static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 475193323Sed return G.Graph; 476193323Sed } 477193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 478193323Sed return N->pred_begin(); 479193323Sed } 480193323Sed static inline ChildIteratorType child_end(NodeType *N) { 481193323Sed return N->pred_end(); 482193323Sed } 483193323Sed}; 484193323Sed 485193323Sedtemplate <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 486193323Sed typedef const MachineBasicBlock NodeType; 487193323Sed typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 488193323Sed static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 489193323Sed return G.Graph; 490193323Sed } 491193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 492193323Sed return N->pred_begin(); 493193323Sed } 494193323Sed static inline ChildIteratorType child_end(NodeType *N) { 495193323Sed return N->pred_end(); 496193323Sed } 497193323Sed}; 498193323Sed 499193323Sed} // End llvm namespace 500193323Sed 501193323Sed#endif 502