MachineBasicBlock.h revision 14152b480d09c7ca912af7c06d00b0ff3912e4f5
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 5c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 10c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Collect the sequence of machine instructions for a basic block. 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/CodeGen/MachineInstr.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/GraphTraits.h" 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 20c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)namespace llvm { 21c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class Pass; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class BasicBlock; 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class MachineFunction; 25c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)class MCSymbol; 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class StringRef; 27eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochclass raw_ostream; 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <> 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)private: 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mutable ilist_half_node<MachineInstr> Sentinel; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this is only set by the MachineBasicBlock owning the LiveList 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class MachineBasicBlock; 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock* Parent; 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *createSentinel() const { 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return static_cast<MachineInstr*>(&Sentinel); 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void destroySentinel(MachineInstr *) const {} 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *provideInitialHead() const { return createSentinel(); } 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static void noteHead(MachineInstr*, MachineInstr*) {} 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void addNodeToList(MachineInstr* N); 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void removeNodeFromList(MachineInstr* N); 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void transferNodesFromList(ilist_traits &SrcTraits, 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ilist_iterator<MachineInstr> first, 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ilist_iterator<MachineInstr> last); 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void deleteNode(MachineInstr *N); 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)private: 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void createNode(const MachineInstr &); 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class MachineBasicBlock : public ilist_node<MachineBasicBlock> { 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef ilist<MachineInstr> Instructions; 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Instructions Insts; 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const BasicBlock *BB; 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int Number; 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) MachineFunction *xParent; 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// Predecessors/Successors - Keep track of the predecessor / successor 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// basicblocks. 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<MachineBasicBlock *> Predecessors; 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<MachineBasicBlock *> Successors; 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// LiveIns - Keep track of the physical registers that are livein of 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// the basicblock. 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<unsigned> LiveIns; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Alignment - Alignment of the basic block. Zero if the basic block does 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// not need to be aligned. 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned Alignment; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// IsLandingPad - Indicate that this basic block is entered via an 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// exception handler. 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsLandingPad; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// AddressTaken - Indicate that this basic block is potentially the 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// target of an indirect branch. 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool AddressTaken; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Intrusive list support 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock() {} 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~MachineBasicBlock(); 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // MachineBasicBlocks are allocated and owned by MachineFunction. 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class MachineFunction; 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getBasicBlock - Return the LLVM basic block that this instance 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// corresponded to originally. Note that this may be NULL if this instance 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// does not correspond directly to an LLVM basic block. 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const BasicBlock *getBasicBlock() const { return BB; } 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getName - Return the name of the corresponding LLVM basic block, or 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// "(null)". 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StringRef getName() const; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// hasAddressTaken - Test whether this block is potentially the target 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// of an indirect branch. 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool hasAddressTaken() const { return AddressTaken; } 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// setHasAddressTaken - Set this block to reflect that it potentially 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// is the target of an indirect branch. 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void setHasAddressTaken() { AddressTaken = true; } 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getParent - Return the MachineFunction containing this basic block. 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const MachineFunction *getParent() const { return xParent; } 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineFunction *getParent() { return xParent; } 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef Instructions::iterator iterator; 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef Instructions::const_iterator const_iterator; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::reverse_iterator<iterator> reverse_iterator; 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned size() const { return (unsigned)Insts.size(); } 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool empty() const { return Insts.empty(); } 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr& front() { return Insts.front(); } 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr& back() { return Insts.back(); } 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const MachineInstr& front() const { return Insts.front(); } 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const MachineInstr& back() const { return Insts.back(); } 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator begin() { return Insts.begin(); } 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_iterator begin() const { return Insts.begin(); } 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator end() { return Insts.end(); } 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_iterator end() const { return Insts.end(); } 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reverse_iterator rbegin() { return Insts.rbegin(); } 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_reverse_iterator rbegin() const { return Insts.rbegin(); } 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reverse_iterator rend () { return Insts.rend(); } 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_reverse_iterator rend () const { return Insts.rend(); } 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Machine-CFG iterators 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::reverse_iterator 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pred_reverse_iterator; 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_pred_reverse_iterator; 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::reverse_iterator 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) succ_reverse_iterator; 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_succ_reverse_iterator; 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pred_iterator pred_begin() { return Predecessors.begin(); } 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_pred_iterator pred_begin() const { return Predecessors.begin(); } 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pred_iterator pred_end() { return Predecessors.end(); } 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_pred_iterator pred_end() const { return Predecessors.end(); } 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pred_reverse_iterator pred_rbegin() 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Predecessors.rbegin();} 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_pred_reverse_iterator pred_rbegin() const 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Predecessors.rbegin();} 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pred_reverse_iterator pred_rend() 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Predecessors.rend(); } 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_pred_reverse_iterator pred_rend() const 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Predecessors.rend(); } 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned pred_size() const { 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (unsigned)Predecessors.size(); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool pred_empty() const { return Predecessors.empty(); } 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) succ_iterator succ_begin() { return Successors.begin(); } 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_succ_iterator succ_begin() const { return Successors.begin(); } 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) succ_iterator succ_end() { return Successors.end(); } 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_succ_iterator succ_end() const { return Successors.end(); } 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) succ_reverse_iterator succ_rbegin() 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Successors.rbegin(); } 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_succ_reverse_iterator succ_rbegin() const 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Successors.rbegin(); } 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) succ_reverse_iterator succ_rend() 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Successors.rend(); } 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_succ_reverse_iterator succ_rend() const 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { return Successors.rend(); } 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned succ_size() const { 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (unsigned)Successors.size(); 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool succ_empty() const { return Successors.empty(); } 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // LiveIn management methods. 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// addLiveIn - Add the specified register as a live in. Note that it 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// is an error to add the same register to the same set more than once. 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// removeLiveIn - Remove the specified register from the live in set. 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void removeLiveIn(unsigned Reg); 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// isLiveIn - Return true if the specified register is in the live in set. 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool isLiveIn(unsigned Reg) const; 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Iteration support for live in sets. These sets are kept in sorted 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // order by their register number. 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::vector<unsigned>::const_iterator livein_iterator; 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) livein_iterator livein_begin() const { return LiveIns.begin(); } 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) livein_iterator livein_end() const { return LiveIns.end(); } 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool livein_empty() const { return LiveIns.empty(); } 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getAlignment - Return alignment of the basic block. 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned getAlignment() const { return Alignment; } 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// setAlignment - Set alignment of the basic block. 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void setAlignment(unsigned Align) { Alignment = Align; } 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// isLandingPad - Returns true if the block is a landing pad. That is 2192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// this basic block is entered via an exception handler. 2202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool isLandingPad() const { return IsLandingPad; } 2212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// setIsLandingPad - Indicates the block is a landing pad. That is 2232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// this basic block is entered via an exception handler. 2242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void setIsLandingPad() { IsLandingPad = true; } 2252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Code Layout methods. 2272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// moveBefore/moveAfter - move 'this' block before or after the specified 2292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// block. This only moves the block, it does not modify the CFG or adjust 2302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) /// potential fall-throughs at the end of the block. 2312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void moveBefore(MachineBasicBlock *NewAfter); 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void moveAfter(MachineBasicBlock *NewBefore); 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// updateTerminator - Update the terminator instructions in block to account 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// for changes to the layout. If the block previously used a fallthrough, 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// it may now need a branch, and if it previously used branching it may now 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// be able to use a fallthrough. 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void updateTerminator(); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Machine-CFG mutators 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// The Predecessors list of succ is automatically updated. 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void addSuccessor(MachineBasicBlock *succ); 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// removeSuccessor - Remove successor from the successors list of this 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void removeSuccessor(MachineBasicBlock *succ); 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// removeSuccessor - Remove specified successor from the successors list of 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// this MachineBasicBlock. The Predecessors list of succ is automatically 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// updated. Return the iterator to the element after the one removed. 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) succ_iterator removeSuccessor(succ_iterator I); 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// transferSuccessors - Transfers all the successors from MBB to this 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// machine basic block (i.e., copies all the successors fromMBB and 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// remove all the successors from fromMBB). 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void transferSuccessors(MachineBasicBlock *fromMBB); 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// in transferSuccessors, and update PHI operands in the successor blocks 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// which refer to fromMBB to refer to this. 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB); 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// isSuccessor - Return true if the specified MBB is a successor of this 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// block. 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool isSuccessor(const MachineBasicBlock *MBB) const; 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// isLayoutSuccessor - Return true if the specified MBB will be emitted 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// immediately after this block, such that if this block exits by 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// falling through, control will transfer to the specified MBB. Note 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// that MBB need not be a successor at all, for example if this block 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// ends with an unconditional branch to some other block. 2771320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// canFallThrough - Return true if the block can implicitly transfer 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// control to the block after it by falling off the end of it. This should 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// return false if it can reach the block after it, but it uses an explicit 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// branch to do so (e.g., a table jump). True is a conservative answer. 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool canFallThrough(); 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getFirstTerminator - returns an iterator to the first terminator 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// instruction of this basic block. If a terminator does not exist, 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// it returns end() 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator getFirstTerminator(); 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// SplitCriticalEdge - Split the critical edge from this block to the 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// given successor block, and return the newly created block, or null 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// if splitting is not possible. 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// This function updates LiveVariables, MachineDominatorTree, and 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// MachineLoopInfo, as applicable. 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P); 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void pop_front() { Insts.pop_front(); } 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void pop_back() { Insts.pop_back(); } 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void push_back(MachineInstr *MI) { Insts.push_back(MI); } 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template<typename IT> 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // erase - Remove the specified element or range from the instruction list. 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // These functions delete any instructions removed. 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator erase(iterator I) { return Insts.erase(I); } 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void clear() { Insts.clear(); } 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// splice - Take an instruction from MBB 'Other' at the position From, 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// and insert it into this MBB right before 'where'. 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void splice(iterator where, MachineBasicBlock *Other, iterator From) { 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Insts.splice(where, Other->Insts, From); 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// splice - Take a block of instructions from MBB 'Other' in the range [From, 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// To), and insert them into this MBB right before 'where'. 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void splice(iterator where, MachineBasicBlock *Other, iterator From, 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator To) { 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Insts.splice(where, Other->Insts, From, To); 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// removeFromParent - This method unlinks 'this' from the containing 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// function, and returns it, but does not delete it. 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *removeFromParent(); 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// eraseFromParent - This method unlinks 'this' from the containing 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// function and deletes it. 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void eraseFromParent(); 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 'Old', change the code and CFG so that it branches to 'New' instead. 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// the CFG to be inserted. If we have proven that MBB can only branch to 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// DestB can be null. Besides DestA and DestB, retain other edges leading 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// to LandingPads (currently there can be only one; we don't check or require 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// that here). Note it is possible that DestA and/or DestB are LandingPads. 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MachineBasicBlock *DestB, 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool isCond); 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// any DBG_VALUE instructions. Return UnknownLoc if there is none. 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugLoc findDebugLoc(MachineBasicBlock::iterator &MBBI); 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Debugging methods. 353116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch void dump() const; 354116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch void print(raw_ostream &OS) const; 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getNumber - MachineBasicBlocks are uniquely numbered at the function 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// level, unless they're not in a MachineFunction yet, in which case this 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// will return -1. 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int getNumber() const { return Number; } 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void setNumber(int N) { Number = N; } 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// getSymbol - Return the MCSymbol for this basic block. 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MCSymbol *getSymbol() const; 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)private: // Methods used to maintain doubly linked list of blocks... 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend struct ilist_traits<MachineBasicBlock>; 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Machine-CFG mutators 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Don't do this unless you know what you're doing, because it doesn't 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// update pred's successors list. Use pred->addSuccessor instead. 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void addPredecessor(MachineBasicBlock *pred); 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// removePredecessor - Remove pred as a predecessor of this 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// MachineBasicBlock. Don't do this unless you know what you're 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// doing, because it doesn't update pred's successors list. Use 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// pred->removeSuccessor instead. 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void removePredecessor(MachineBasicBlock *pred); 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t); 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===--------------------------------------------------------------------===// 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// GraphTraits specializations for machine basic block graphs (machine-CFGs) 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===--------------------------------------------------------------------===// 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Provide specializations of GraphTraits to be able to treat a 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// MachineFunction as a graph of MachineBasicBlocks... 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <> struct GraphTraits<MachineBasicBlock *> { 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MachineBasicBlock NodeType; 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MachineBasicBlock::succ_iterator ChildIteratorType; 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline ChildIteratorType child_begin(NodeType *N) { 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N->succ_begin(); 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline ChildIteratorType child_end(NodeType *N) { 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N->succ_end(); 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <> struct GraphTraits<const MachineBasicBlock *> { 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef const MachineBasicBlock NodeType; 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline ChildIteratorType child_begin(NodeType *N) { 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N->succ_begin(); 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline ChildIteratorType child_end(NodeType *N) { 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N->succ_end(); 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Provide specializations of GraphTraits to be able to treat a 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// MachineFunction as a graph of MachineBasicBlocks... and to walk it 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in inverse order. Inverse order for a function is considered 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// to be when traversing the predecessor edges of a MBB 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// instead of the successor edges. 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MachineBasicBlock NodeType; 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MachineBasicBlock::pred_iterator ChildIteratorType; 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return G.Graph; 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline ChildIteratorType child_begin(NodeType *N) { 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N->pred_begin(); 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline ChildIteratorType child_end(NodeType *N) { 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N->pred_end(); 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef const MachineBasicBlock NodeType; 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return G.Graph; 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline ChildIteratorType child_begin(NodeType *N) { 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N->pred_begin(); 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static inline ChildIteratorType child_end(NodeType *N) { 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N->pred_end(); 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // End llvm namespace 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)