MachineBasicBlock.h revision 3f4f420ab7acb10221ba971543a7eed5489fb626
151a8d8528135ba4e3e4cf7cd711a9e47b19078a3Chris Lattner//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 2ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 7ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 9ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 10e8b5413e5d0c7c0fc5b384e975c4ca87f4c00699Chris Lattner// Collect the sequence of machine instructions for a basic block. 11e8b5413e5d0c7c0fc5b384e975c4ca87f4c00699Chris Lattner// 1251a8d8528135ba4e3e4cf7cd711a9e47b19078a3Chris Lattner//===----------------------------------------------------------------------===// 13deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 14fce1143bcfa73f61845002fa50473d1a01384202Misha Brukman#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 15fce1143bcfa73f61845002fa50473d1a01384202Misha Brukman#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 16deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 17551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/GraphTraits.h" 18255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/CodeGen/MachineInstr.h" 197cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak#include "llvm/Support/DataTypes.h" 2013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen#include <functional> 21d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 22d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 23fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman 24853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohmanclass Pass; 25fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanclass BasicBlock; 26fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanclass MachineFunction; 27a655f088b88cf015fc48721fd9869787d1b8ce13Chris Lattnerclass MCSymbol; 28f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesenclass SlotIndexes; 29a655f088b88cf015fc48721fd9869787d1b8ce13Chris Lattnerclass StringRef; 301cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarclass raw_ostream; 317cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszakclass MachineBranchProbabilityInfo; 32d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3394dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenostemplate <> 348e4018e2de52c534405d7155c7009d0b35afb861Cedric Venetstruct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 358e4018e2de52c534405d7155c7009d0b35afb861Cedric Venetprivate: 367309be6735666143bd9835b275dc8501617a2591Gabor Greif mutable ilist_half_node<MachineInstr> Sentinel; 37fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman 388e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman // this is only set by the MachineBasicBlock owning the LiveList 3994dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos friend class MachineBasicBlock; 408e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineBasicBlock* Parent; 4194dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 428e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohmanpublic: 43c7f6b8c5d40e17bf43fd3a1549d7d89c9da735e1Gabor Greif MachineInstr *createSentinel() const { 44c7f6b8c5d40e17bf43fd3a1549d7d89c9da735e1Gabor Greif return static_cast<MachineInstr*>(&Sentinel); 45c7f6b8c5d40e17bf43fd3a1549d7d89c9da735e1Gabor Greif } 46fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman void destroySentinel(MachineInstr *) const {} 4794dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 48c23b8719ef9d6b1220e854b37d40e9e1c48a82bcGabor Greif MachineInstr *provideInitialHead() const { return createSentinel(); } 49c23b8719ef9d6b1220e854b37d40e9e1c48a82bcGabor Greif MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 50f3841fcbd587c31aa9842b3f33bd57de40c9f443Gabor Greif static void noteHead(MachineInstr*, MachineInstr*) {} 51c23b8719ef9d6b1220e854b37d40e9e1c48a82bcGabor Greif 52aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos void addNodeToList(MachineInstr* N); 53aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos void removeNodeFromList(MachineInstr* N); 54fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman void transferNodesFromList(ilist_traits &SrcTraits, 55fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman ilist_iterator<MachineInstr> first, 56fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman ilist_iterator<MachineInstr> last); 578e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman void deleteNode(MachineInstr *N); 58fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanprivate: 59fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman void createNode(const MachineInstr &); 6094dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos}; 6194dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 62fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanclass MachineBasicBlock : public ilist_node<MachineBasicBlock> { 63fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman typedef ilist<MachineInstr> Instructions; 64c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos Instructions Insts; 651194e9501984daf0d3237ed1bf18a156173e7fd4Chris Lattner const BasicBlock *BB; 66c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke int Number; 67f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner MachineFunction *xParent; 687cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 6913d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// Predecessors/Successors - Keep track of the predecessor / successor 7013d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// basicblocks. 7113d828567812041c1ca1817f4b66fce840903a1fEvan Cheng std::vector<MachineBasicBlock *> Predecessors; 7213d828567812041c1ca1817f4b66fce840903a1fEvan Cheng std::vector<MachineBasicBlock *> Successors; 7313d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 747cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// Weights - Keep track of the weights to the successors. This vector 757cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// has the same order as Successors, or it is empty if we don't use it 767cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// (disable optimization). 777cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak std::vector<uint32_t> Weights; 787cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak typedef std::vector<uint32_t>::iterator weight_iterator; 7925101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak typedef std::vector<uint32_t>::const_iterator const_weight_iterator; 807cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 8113d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// LiveIns - Keep track of the physical registers that are livein of 8213d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// the basicblock. 8313d828567812041c1ca1817f4b66fce840903a1fEvan Cheng std::vector<unsigned> LiveIns; 84fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 85fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// Alignment - Alignment of the basic block. Zero if the basic block does 86fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// not need to be aligned. 878c741b8064f1116d8d8dc435b60b75abdf5c4d57Jakob Stoklund Olesen /// The alignment is specified as log2(bytes). 88fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng unsigned Alignment; 898c741b8064f1116d8d8dc435b60b75abdf5c4d57Jakob Stoklund Olesen 9030b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// IsLandingPad - Indicate that this basic block is entered via an 9130b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// exception handler. 9230b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey bool IsLandingPad; 9313d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 948c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// AddressTaken - Indicate that this basic block is potentially the 958c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// target of an indirect branch. 968c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman bool AddressTaken; 978c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman 982ad047e04dd4c19defade4799834efacb0024551Eli Bendersky /// \brief since getSymbol is a relatively heavy-weight operation, the symbol 992ad047e04dd4c19defade4799834efacb0024551Eli Bendersky /// is only computed once and is cached. 1002ad047e04dd4c19defade4799834efacb0024551Eli Bendersky mutable MCSymbol *CachedMCSymbol; 1012ad047e04dd4c19defade4799834efacb0024551Eli Bendersky 102fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman // Intrusive list support 103fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman MachineBasicBlock() {} 104fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman 1058e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 1068e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 1072c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman ~MachineBasicBlock(); 10817fb34bf8cd10a798c9206eeef3bff151b4d3688Tanya Lattner 1098e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman // MachineBasicBlocks are allocated and owned by MachineFunction. 1108e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman friend class MachineFunction; 111ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman 1128e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohmanpublic: 113d0aa0cdbc6fee00f2b2019633a9b9d00d301ac68Chris Lattner /// getBasicBlock - Return the LLVM basic block that this instance 114324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen /// corresponded to originally. Note that this may be NULL if this instance 115324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen /// does not correspond directly to an LLVM basic block. 116d0aa0cdbc6fee00f2b2019633a9b9d00d301ac68Chris Lattner /// 1171194e9501984daf0d3237ed1bf18a156173e7fd4Chris Lattner const BasicBlock *getBasicBlock() const { return BB; } 1185e61fa95196b85281eec655787e9c73267532bd1Chris Lattner 119324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen /// getName - Return the name of the corresponding LLVM basic block, or 120324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen /// "(null)". 121324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen StringRef getName() const; 122324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen 1238ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick /// getFullName - Return a formatted string to identify this block and its 1248ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick /// parent function. 1258ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick std::string getFullName() const; 1268ceaa660bfec72249976c1f411db7f40cbc438bbAndrew Trick 1278c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// hasAddressTaken - Test whether this block is potentially the target 1288c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// of an indirect branch. 1298c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman bool hasAddressTaken() const { return AddressTaken; } 1308c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman 1318c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// setHasAddressTaken - Set this block to reflect that it potentially 1328c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// is the target of an indirect branch. 1338c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman void setHasAddressTaken() { AddressTaken = true; } 1348c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman 1355e61fa95196b85281eec655787e9c73267532bd1Chris Lattner /// getParent - Return the MachineFunction containing this basic block. 1365e61fa95196b85281eec655787e9c73267532bd1Chris Lattner /// 137f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner const MachineFunction *getParent() const { return xParent; } 138f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner MachineFunction *getParent() { return xParent; } 1395e61fa95196b85281eec655787e9c73267532bd1Chris Lattner 1407c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 1417c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng /// bundle_iterator - MachineBasicBlock iterator that automatically skips over 1427c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng /// MIs that are inside bundles (i.e. walk top level MIs only). 1437c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng template<typename Ty, typename IterTy> 1447c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng class bundle_iterator 1457c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng : public std::iterator<std::bidirectional_iterator_tag, Ty, ptrdiff_t> { 1467c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng IterTy MII; 1477c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 1487c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng public: 14920aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen bundle_iterator(IterTy mii) : MII(mii) {} 1507c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 1517c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng bundle_iterator(Ty &mi) : MII(mi) { 1522e4b639790a166e55a0bf14fac54ca6ce583e459Jakob Stoklund Olesen assert(!mi.isBundledWithPred() && 1537c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng "It's not legal to initialize bundle_iterator with a bundled MI"); 1547c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 1557c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng bundle_iterator(Ty *mi) : MII(mi) { 1562e4b639790a166e55a0bf14fac54ca6ce583e459Jakob Stoklund Olesen assert((!mi || !mi->isBundledWithPred()) && 1577c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng "It's not legal to initialize bundle_iterator with a bundled MI"); 1587c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 159d4786e221c679fced994993d9ee7228572d4b148Andrew Trick // Template allows conversion from const to nonconst. 160d4786e221c679fced994993d9ee7228572d4b148Andrew Trick template<class OtherTy, class OtherIterTy> 161d4786e221c679fced994993d9ee7228572d4b148Andrew Trick bundle_iterator(const bundle_iterator<OtherTy, OtherIterTy> &I) 162d4786e221c679fced994993d9ee7228572d4b148Andrew Trick : MII(I.getInstrIterator()) {} 1637c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng bundle_iterator() : MII(0) {} 1647c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 1657c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng Ty &operator*() const { return *MII; } 1667c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng Ty *operator->() const { return &operator*(); } 1677c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 1687c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng operator Ty*() const { return MII; } 1697c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 1707c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng bool operator==(const bundle_iterator &x) const { 1717c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return MII == x.MII; 1727c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 1737c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng bool operator!=(const bundle_iterator &x) const { 1747c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return !operator==(x); 1757c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 17657cae881e2b6c85a562d3fd2a7f10bf9d7921b40Jim Grosbach 1777c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng // Increment and decrement operators... 1787c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng bundle_iterator &operator--() { // predecrement - Back up 17920aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen do --MII; 1802e4b639790a166e55a0bf14fac54ca6ce583e459Jakob Stoklund Olesen while (MII->isBundledWithPred()); 1817c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return *this; 1827c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 1837c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng bundle_iterator &operator++() { // preincrement - Advance 1842e4b639790a166e55a0bf14fac54ca6ce583e459Jakob Stoklund Olesen while (MII->isBundledWithSucc()) 1852e4b639790a166e55a0bf14fac54ca6ce583e459Jakob Stoklund Olesen ++MII; 1862e4b639790a166e55a0bf14fac54ca6ce583e459Jakob Stoklund Olesen ++MII; 1877c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return *this; 1887c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 1897c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng bundle_iterator operator--(int) { // postdecrement operators... 1907c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng bundle_iterator tmp = *this; 19120aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen --*this; 1927c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return tmp; 1937c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 1947c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng bundle_iterator operator++(int) { // postincrement operators... 1957c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng bundle_iterator tmp = *this; 19620aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen ++*this; 1977c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return tmp; 1987c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 1997c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 200ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng IterTy getInstrIterator() const { 2017c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng return MII; 20257cae881e2b6c85a562d3fd2a7f10bf9d7921b40Jim Grosbach } 2037c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng }; 2047c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 205ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng typedef Instructions::iterator instr_iterator; 206ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng typedef Instructions::const_iterator const_instr_iterator; 207ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng typedef std::reverse_iterator<instr_iterator> reverse_instr_iterator; 2087c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng typedef 209ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng std::reverse_iterator<const_instr_iterator> const_reverse_instr_iterator; 2107c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 2117c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng typedef 212ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng bundle_iterator<MachineInstr,instr_iterator> iterator; 2137c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng typedef 214ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng bundle_iterator<const MachineInstr,const_instr_iterator> const_iterator; 2157c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 2167c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng typedef std::reverse_iterator<iterator> reverse_iterator; 2177c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 218deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 21934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned size() const { return (unsigned)Insts.size(); } 220deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve bool empty() const { return Insts.empty(); } 221deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 222c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineInstr& front() { return Insts.front(); } 223c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineInstr& back() { return Insts.back(); } 2248e8b8a223c2b0e69f44c0639f846260c8011668fDan Gohman const MachineInstr& front() const { return Insts.front(); } 2258e8b8a223c2b0e69f44c0639f846260c8011668fDan Gohman const MachineInstr& back() const { return Insts.back(); } 226deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 227ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng instr_iterator instr_begin() { return Insts.begin(); } 228ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng const_instr_iterator instr_begin() const { return Insts.begin(); } 229ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng instr_iterator instr_end() { return Insts.end(); } 230ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng const_instr_iterator instr_end() const { return Insts.end(); } 231ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng reverse_instr_iterator instr_rbegin() { return Insts.rbegin(); } 232ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); } 233ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng reverse_instr_iterator instr_rend () { return Insts.rend(); } 234ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng const_reverse_instr_iterator instr_rend () const { return Insts.rend(); } 2357c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 23620aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen iterator begin() { return instr_begin(); } 23720aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen const_iterator begin() const { return instr_begin(); } 23820aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen iterator end () { return instr_end(); } 23920aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen const_iterator end () const { return instr_end(); } 24020aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen reverse_iterator rbegin() { return instr_rbegin(); } 24120aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen const_reverse_iterator rbegin() const { return instr_rbegin(); } 24220aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen reverse_iterator rend () { return instr_rend(); } 24320aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen const_reverse_iterator rend () const { return instr_rend(); } 244deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 2457c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 24676456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke // Machine-CFG iterators 24776456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 24876456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 24976456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 25076456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 2516603d7ec67e64b987451975771759ade4e9f19baEvan Cheng typedef std::vector<MachineBasicBlock *>::reverse_iterator 2526603d7ec67e64b987451975771759ade4e9f19baEvan Cheng pred_reverse_iterator; 2536603d7ec67e64b987451975771759ade4e9f19baEvan Cheng typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 2546603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_pred_reverse_iterator; 2556603d7ec67e64b987451975771759ade4e9f19baEvan Cheng typedef std::vector<MachineBasicBlock *>::reverse_iterator 2566603d7ec67e64b987451975771759ade4e9f19baEvan Cheng succ_reverse_iterator; 2576603d7ec67e64b987451975771759ade4e9f19baEvan Cheng typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 2586603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_succ_reverse_iterator; 259ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman 260cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner pred_iterator pred_begin() { return Predecessors.begin(); } 261cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner const_pred_iterator pred_begin() const { return Predecessors.begin(); } 262cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner pred_iterator pred_end() { return Predecessors.end(); } 263cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner const_pred_iterator pred_end() const { return Predecessors.end(); } 2646603d7ec67e64b987451975771759ade4e9f19baEvan Cheng pred_reverse_iterator pred_rbegin() 2656603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Predecessors.rbegin();} 2666603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_pred_reverse_iterator pred_rbegin() const 2676603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Predecessors.rbegin();} 2686603d7ec67e64b987451975771759ade4e9f19baEvan Cheng pred_reverse_iterator pred_rend() 2696603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Predecessors.rend(); } 2706603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_pred_reverse_iterator pred_rend() const 2716603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Predecessors.rend(); } 27234cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned pred_size() const { 27334cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng return (unsigned)Predecessors.size(); 27434cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng } 275cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner bool pred_empty() const { return Predecessors.empty(); } 276cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner succ_iterator succ_begin() { return Successors.begin(); } 277cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner const_succ_iterator succ_begin() const { return Successors.begin(); } 278cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner succ_iterator succ_end() { return Successors.end(); } 279cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner const_succ_iterator succ_end() const { return Successors.end(); } 2806603d7ec67e64b987451975771759ade4e9f19baEvan Cheng succ_reverse_iterator succ_rbegin() 2816603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Successors.rbegin(); } 2826603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_succ_reverse_iterator succ_rbegin() const 2836603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Successors.rbegin(); } 2846603d7ec67e64b987451975771759ade4e9f19baEvan Cheng succ_reverse_iterator succ_rend() 2856603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Successors.rend(); } 2866603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_succ_reverse_iterator succ_rend() const 2876603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Successors.rend(); } 28834cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned succ_size() const { 28934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng return (unsigned)Successors.size(); 29034cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng } 291cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner bool succ_empty() const { return Successors.empty(); } 29276456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 29313d828567812041c1ca1817f4b66fce840903a1fEvan Cheng // LiveIn management methods. 29413d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 29513d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// addLiveIn - Add the specified register as a live in. Note that it 29613d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// is an error to add the same register to the same set more than once. 29713d828567812041c1ca1817f4b66fce840903a1fEvan Cheng void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 29813d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 299f64765244512250b28b1fbe290b1b26d17e41dd4Jakob Stoklund Olesen /// Add PhysReg as live in to this block, and ensure that there is a copy of 300f64765244512250b28b1fbe290b1b26d17e41dd4Jakob Stoklund Olesen /// PhysReg to a virtual register of class RC. Return the virtual register 301f64765244512250b28b1fbe290b1b26d17e41dd4Jakob Stoklund Olesen /// that is a copy of the live in PhysReg. 302f64765244512250b28b1fbe290b1b26d17e41dd4Jakob Stoklund Olesen unsigned addLiveIn(unsigned PhysReg, const TargetRegisterClass *RC); 303f64765244512250b28b1fbe290b1b26d17e41dd4Jakob Stoklund Olesen 304b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng /// removeLiveIn - Remove the specified register from the live in set. 305b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng /// 306b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng void removeLiveIn(unsigned Reg); 307b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 308a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng /// isLiveIn - Return true if the specified register is in the live in set. 309a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng /// 310a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng bool isLiveIn(unsigned Reg) const; 311a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng 31213d828567812041c1ca1817f4b66fce840903a1fEvan Cheng // Iteration support for live in sets. These sets are kept in sorted 31313d828567812041c1ca1817f4b66fce840903a1fEvan Cheng // order by their register number. 31481bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman typedef std::vector<unsigned>::const_iterator livein_iterator; 31581bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman livein_iterator livein_begin() const { return LiveIns.begin(); } 31681bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman livein_iterator livein_end() const { return LiveIns.end(); } 31713d828567812041c1ca1817f4b66fce840903a1fEvan Cheng bool livein_empty() const { return LiveIns.empty(); } 31813d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 319fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// getAlignment - Return alignment of the basic block. 3208c741b8064f1116d8d8dc435b60b75abdf5c4d57Jakob Stoklund Olesen /// The alignment is specified as log2(bytes). 321fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// 322fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng unsigned getAlignment() const { return Alignment; } 323fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 324fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// setAlignment - Set alignment of the basic block. 3258c741b8064f1116d8d8dc435b60b75abdf5c4d57Jakob Stoklund Olesen /// The alignment is specified as log2(bytes). 326fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// 327fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng void setAlignment(unsigned Align) { Alignment = Align; } 328fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 32930b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// isLandingPad - Returns true if the block is a landing pad. That is 33030b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// this basic block is entered via an exception handler. 33130b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey bool isLandingPad() const { return IsLandingPad; } 33230b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey 33330b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// setIsLandingPad - Indicates the block is a landing pad. That is 33430b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// this basic block is entered via an exception handler. 335fbf5f1b72b25de35452d89a4ccd7887f79880be8Bill Wendling void setIsLandingPad(bool V = true) { IsLandingPad = V; } 33630b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey 337cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen /// getLandingPadSuccessor - If this block has a successor that is a landing 338cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen /// pad, return it. Otherwise return NULL. 339cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen const MachineBasicBlock *getLandingPadSuccessor() const; 340cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 34134ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner // Code Layout methods. 34257cae881e2b6c85a562d3fd2a7f10bf9d7921b40Jim Grosbach 34334ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner /// moveBefore/moveAfter - move 'this' block before or after the specified 34434ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner /// block. This only moves the block, it does not modify the CFG or adjust 34534ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner /// potential fall-throughs at the end of the block. 34634ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner void moveBefore(MachineBasicBlock *NewAfter); 34734ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner void moveAfter(MachineBasicBlock *NewBefore); 3487707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach 3497707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach /// updateTerminator - Update the terminator instructions in block to account 3507707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach /// for changes to the layout. If the block previously used a fallthrough, 3517707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach /// it may now need a branch, and if it previously used branching it may now 3527707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach /// be able to use a fallthrough. 3537707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach void updateTerminator(); 3547707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach 35576456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke // Machine-CFG mutators 3567cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 35776456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 3587cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// The Predecessors list of succ is automatically updated. WEIGHT 3597cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// parameter is stored in Weights list and it may be used by 3607cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// MachineBranchProbabilityInfo analysis to calculate branch probability. 36176456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// 3622c5a960b0eae0634da6e1854111b35f475e65335Jakob Stoklund Olesen /// Note that duplicate Machine CFG edges are not allowed. 3632c5a960b0eae0634da6e1854111b35f475e65335Jakob Stoklund Olesen /// 3647cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0); 36576456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 366dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner /// removeSuccessor - Remove successor from the successors list of this 36776456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 36876456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// 3693dfbb558b5e74554104710ed16807fe74ec220a3Chris Lattner void removeSuccessor(MachineBasicBlock *succ); 370dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner 371dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner /// removeSuccessor - Remove specified successor from the successors list of 372dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner /// this MachineBasicBlock. The Predecessors list of succ is automatically 3738a46d342d8cbca7c9c7be6c66007d41329babad0David Greene /// updated. Return the iterator to the element after the one removed. 374dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner /// 3758a46d342d8cbca7c9c7be6c66007d41329babad0David Greene succ_iterator removeSuccessor(succ_iterator I); 3767cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 3777cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// replaceSuccessor - Replace successor OLD with NEW and update weight info. 3787cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// 3797cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New); 3807cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 3817cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 38263307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang /// transferSuccessors - Transfers all the successors from MBB to this 38363307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang /// machine basic block (i.e., copies all the successors fromMBB and 3841edb8e0910db4cda46a81a4abad80a2a755442aaDan Gohman /// remove all the successors from fromMBB). 38563307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang void transferSuccessors(MachineBasicBlock *fromMBB); 38614152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman 38714152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as 38814152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman /// in transferSuccessors, and update PHI operands in the successor blocks 38914152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman /// which refer to fromMBB to refer to this. 39014152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB); 39157cae881e2b6c85a562d3fd2a7f10bf9d7921b40Jim Grosbach 392f192b507a33b2ab2e2f6271bb1ea6ed4fbda69e7Jakob Stoklund Olesen /// isPredecessor - Return true if the specified MBB is a predecessor of this 393f192b507a33b2ab2e2f6271bb1ea6ed4fbda69e7Jakob Stoklund Olesen /// block. 394f192b507a33b2ab2e2f6271bb1ea6ed4fbda69e7Jakob Stoklund Olesen bool isPredecessor(const MachineBasicBlock *MBB) const; 395f192b507a33b2ab2e2f6271bb1ea6ed4fbda69e7Jakob Stoklund Olesen 396cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner /// isSuccessor - Return true if the specified MBB is a successor of this 397cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner /// block. 3986d1b89e74f98470d05666ca9f59a8ec5d04b5eb4Dan Gohman bool isSuccessor(const MachineBasicBlock *MBB) const; 39976456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 4006ade6f55a836129af634074e96f660ff23f59a30Dan Gohman /// isLayoutSuccessor - Return true if the specified MBB will be emitted 4016ade6f55a836129af634074e96f660ff23f59a30Dan Gohman /// immediately after this block, such that if this block exits by 4026ade6f55a836129af634074e96f660ff23f59a30Dan Gohman /// falling through, control will transfer to the specified MBB. Note 4036ade6f55a836129af634074e96f660ff23f59a30Dan Gohman /// that MBB need not be a successor at all, for example if this block 4046ade6f55a836129af634074e96f660ff23f59a30Dan Gohman /// ends with an unconditional branch to some other block. 4056d1b89e74f98470d05666ca9f59a8ec5d04b5eb4Dan Gohman bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 4066ade6f55a836129af634074e96f660ff23f59a30Dan Gohman 40715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson /// canFallThrough - Return true if the block can implicitly transfer 40815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson /// control to the block after it by falling off the end of it. This should 40915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson /// return false if it can reach the block after it, but it uses an explicit 41015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson /// branch to do so (e.g., a table jump). True is a conservative answer. 41115acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool canFallThrough(); 41215acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 4133f4f420ab7acb10221ba971543a7eed5489fb626Robert Wilhelm /// Returns a pointer to the first instruction in this block that is not a 4143f4f420ab7acb10221ba971543a7eed5489fb626Robert Wilhelm /// PHINode instruction. When adding instructions to the beginning of the 415d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman /// basic block, they should be added before the returned value, not before 416d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman /// the first instruction, which might be PHI. 417d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman /// Returns end() is there's no non-PHI instruction. 418d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman iterator getFirstNonPHI(); 419d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman 42092095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is 42192095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen /// not a PHI or a label. This is the correct point to insert copies at the 42292095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen /// beginning of a basic block. 42392095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen iterator SkipPHIsAndLabels(iterator I); 42492095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen 425743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos /// getFirstTerminator - returns an iterator to the first terminator 426743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos /// instruction of this basic block. If a terminator does not exist, 427743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos /// it returns end() 428743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos iterator getFirstTerminator(); 4297c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng const_iterator getFirstTerminator() const; 430743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos 431ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng /// getFirstInstrTerminator - Same getFirstTerminator but it ignores bundles 432ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng /// and return an instr_iterator instead. 433ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng instr_iterator getFirstInstrTerminator(); 4341a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 4354f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen /// getLastNonDebugInstr - returns an iterator to the last non-debug 4364f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen /// instruction in the basic block, or end() 4374f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen iterator getLastNonDebugInstr(); 4387c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng const_iterator getLastNonDebugInstr() const; 439adb877d62e5ac88db037d91bcd2e9f7dc2c4cd7aJakob Stoklund Olesen 440853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// SplitCriticalEdge - Split the critical edge from this block to the 441853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// given successor block, and return the newly created block, or null 442853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// if splitting is not possible. 443853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// 444853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// This function updates LiveVariables, MachineDominatorTree, and 445853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// MachineLoopInfo, as applicable. 446853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P); 447853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 4480bbcd6bfd1a90c2aa7386a88ba9fc9aba47d03a7Brian Gaeke void pop_front() { Insts.pop_front(); } 449f24d879520a615a03f19ced3c7491f7b51934d1cChris Lattner void pop_back() { Insts.pop_back(); } 450deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve void push_back(MachineInstr *MI) { Insts.push_back(MI); } 4517c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 452edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen /// Insert MI into the instruction list before I, possibly inside a bundle. 453edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen /// 454edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen /// If the insertion point is inside a bundle, MI will be added to the bundle, 455edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen /// otherwise MI will not be added to any bundle. That means this function 456edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen /// alone can't be used to prepend or append instructions to bundles. See 457edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen /// MIBundleBuilder::insert() for a more reliable way of doing that. 458edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen instr_iterator insert(instr_iterator I, MachineInstr *M); 459deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 460edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen /// Insert a range of instructions into the instruction list before I. 4617c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng template<typename IT> 4627c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng void insert(iterator I, IT S, IT E) { 463ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng Insts.insert(I.getInstrIterator(), S, E); 4647c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 465edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen 466edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen /// Insert MI into the instruction list before I. 467edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen iterator insert(iterator I, MachineInstr *MI) { 468edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && 469edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen "Cannot insert instruction with bundle flags"); 470edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen return Insts.insert(I.getInstrIterator(), MI); 4717c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 472edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen 473edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen /// Insert MI into the instruction list after I. 474edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen iterator insertAfter(iterator I, MachineInstr *MI) { 475edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && 476edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen "Cannot insert instruction with bundle flags"); 477edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen return Insts.insertAfter(I.getInstrIterator(), MI); 4787c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 4797c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 4809f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// Remove an instruction from the instruction list and delete it. 481ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng /// 4829f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// If the instruction is part of a bundle, the other instructions in the 4839f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// bundle will still be bundled after removing the single instruction. 4849f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen instr_iterator erase(instr_iterator I); 4859f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen 4869f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// Remove an instruction from the instruction list and delete it. 4879f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// 4889f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// If the instruction is part of a bundle, the other instructions in the 4899f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// bundle will still be bundled after removing the single instruction. 490ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng instr_iterator erase_instr(MachineInstr *I) { 4919f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen return erase(instr_iterator(I)); 4927c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 493ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng 4949f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// Remove a range of instructions from the instruction list and delete them. 4957c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng iterator erase(iterator I, iterator E) { 496ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng return Insts.erase(I.getInstrIterator(), E.getInstrIterator()); 497ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng } 4989f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen 4999f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// Remove an instruction or bundle from the instruction list and delete it. 5009f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// 5019f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// If I points to a bundle of instructions, they are all erased. 5029f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen iterator erase(iterator I) { 5039f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen return erase(I, llvm::next(I)); 5049f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen } 5059f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen 5069f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// Remove an instruction from the instruction list and delete it. 5079f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// 5089f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// If I is the head of a bundle of instructions, the whole bundle will be 5099f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// erased. 510ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng iterator erase(MachineInstr *I) { 5119f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen return erase(iterator(I)); 5127c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 5137c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng 5149f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// Remove the unbundled instruction from the instruction list without 5159f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// deleting it. 5169f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// 5179f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// This function can not be used to remove bundled instructions, use 5189f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// remove_instr to remove individual instructions from a bundle. 5199f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen MachineInstr *remove(MachineInstr *I) { 5209f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen assert(!I->isBundled() && "Cannot remove bundled instructions"); 5219f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen return Insts.remove(I); 5229f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen } 5239f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen 5249f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// Remove the possibly bundled instruction from the instruction list 5259f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// without deleting it. 5269f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// 5279f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// If the instruction is part of a bundle, the other instructions in the 5289f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen /// bundle will still be bundled after removing the single instruction. 5299f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen MachineInstr *remove_instr(MachineInstr *I); 5309f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen 531ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng void clear() { 532ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng Insts.clear(); 533ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng } 534ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman 5359b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen /// Take an instruction from MBB 'Other' at the position From, and insert it 5369b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen /// into this MBB right before 'Where'. 5379b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen /// 5389b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen /// If From points to a bundle of instructions, the whole bundle is moved. 5399b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen void splice(iterator Where, MachineBasicBlock *Other, iterator From) { 5409b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen // The range splice() doesn't allow noop moves, but this one does. 5419b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen if (Where != From) 5429b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen splice(Where, Other, From, llvm::next(From)); 543c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman } 544c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 5459b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen /// Take a block of instructions from MBB 'Other' in the range [From, To), 5469b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen /// and insert them into this MBB right before 'Where'. 5479b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen /// 5489b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen /// The instruction at 'Where' must not be included in the range of 5499b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen /// instructions to move. 5509b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen void splice(iterator Where, MachineBasicBlock *Other, 5519b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen iterator From, iterator To) { 5529b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen Insts.splice(Where.getInstrIterator(), Other->Insts, 553ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng From.getInstrIterator(), To.getInstrIterator()); 554f24d879520a615a03f19ced3c7491f7b51934d1cChris Lattner } 5558e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattner 5568e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman /// removeFromParent - This method unlinks 'this' from the containing 5578e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman /// function, and returns it, but does not delete it. 5588e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineBasicBlock *removeFromParent(); 55957cae881e2b6c85a562d3fd2a7f10bf9d7921b40Jim Grosbach 5608e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman /// eraseFromParent - This method unlinks 'this' from the containing 5618e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman /// function and deletes it. 5628e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman void eraseFromParent(); 5638e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 5640370fad74b48388412c52d1325512f2c218487faEvan Cheng /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 5650370fad74b48388412c52d1325512f2c218487faEvan Cheng /// 'Old', change the code and CFG so that it branches to 'New' instead. 5660370fad74b48388412c52d1325512f2c218487faEvan Cheng void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 5670370fad74b48388412c52d1325512f2c218487faEvan Cheng 5682bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 5692bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// the CFG to be inserted. If we have proven that MBB can only branch to 5702bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 5712bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// DestB can be null. Besides DestA and DestB, retain other edges leading 5722bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// to LandingPads (currently there can be only one; we don't check or require 5732bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// that here). Note it is possible that DestA and/or DestB are LandingPads. 5742bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 5752bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MachineBasicBlock *DestB, 5762bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng bool isCond); 5772bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng 57873e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 5793b1906f48d0b541e5be0bc1918c94a454e908bc0Dale Johannesen /// any DBG_VALUE instructions. Return UnknownLoc if there is none. 580ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng DebugLoc findDebugLoc(instr_iterator MBBI); 5817c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng DebugLoc findDebugLoc(iterator MBBI) { 582ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng return findDebugLoc(MBBI.getInstrIterator()); 5837c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng } 58473e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen 585c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy /// Possible outcome of a register liveness query to computeRegisterLiveness() 586c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy enum LivenessQueryResult { 587c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy LQR_Live, ///< Register is known to be live. 588c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy LQR_OverlappingLive, ///< Register itself is not live, but some overlapping 589c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy ///< register is. 590c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy LQR_Dead, ///< Register is known to be dead. 591c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy LQR_Unknown ///< Register liveness not decidable from local 592c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy ///< neighborhood. 593c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy }; 594c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy 595c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy /// computeRegisterLiveness - Return whether (physical) register \c Reg 596c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy /// has been <def>ined and not <kill>ed as of just before \c MI. 597c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy /// 598c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy /// Search is localised to a neighborhood of 599c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy /// \c Neighborhood instructions before (searching for defs or kills) and 600c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy /// Neighborhood instructions after (searching just for defs) MI. 601c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy /// 602c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy /// \c Reg must be a physical register. 603c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI, 604c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy unsigned Reg, MachineInstr *MI, 605c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy unsigned Neighborhood=10); 606c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy 607f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke // Debugging methods. 608f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke void dump() const; 609f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen void print(raw_ostream &OS, SlotIndexes* = 0) const; 610f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke 611da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke /// getNumber - MachineBasicBlocks are uniquely numbered at the function 612da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke /// level, unless they're not in a MachineFunction yet, in which case this 613da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke /// will return -1. 614da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke /// 615c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke int getNumber() const { return Number; } 61620a6d8e63056cc2025e7143a5f7226e079e0bc80Chris Lattner void setNumber(int N) { Number = N; } 617c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke 618f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner /// getSymbol - Return the MCSymbol for this basic block. 619f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner /// 6201b2eb0e8a6aaf034675b17be6d853cb1c666200fChris Lattner MCSymbol *getSymbol() const; 6217cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 6227cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 6237cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszakprivate: 6247cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// getWeightIterator - Return weight iterator corresponding to the I 6257cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// successor iterator. 6267cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak weight_iterator getWeightIterator(succ_iterator I); 62725101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak const_weight_iterator getWeightIterator(const_succ_iterator I) const; 6287cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 6297cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak friend class MachineBranchProbabilityInfo; 6307cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 6317cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// getSuccWeight - Return weight of the edge from this block to MBB. This 6327cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// method should NOT be called directly, but by using getEdgeWeight method 6337cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak /// from MachineBranchProbabilityInfo class. 634990ca5517fd6666d4049b6b8281d9df99da11637Jakob Stoklund Olesen uint32_t getSuccWeight(const_succ_iterator Succ) const; 6357cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 6367cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak 6377cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak // Methods used to maintain doubly linked list of blocks... 638fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman friend struct ilist_traits<MachineBasicBlock>; 6398560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke 6408560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke // Machine-CFG mutators 6418560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke 6428560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 6438560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// Don't do this unless you know what you're doing, because it doesn't 6448560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// update pred's successors list. Use pred->addSuccessor instead. 6458560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// 6463dfbb558b5e74554104710ed16807fe74ec220a3Chris Lattner void addPredecessor(MachineBasicBlock *pred); 6478560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke 6488560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// removePredecessor - Remove pred as a predecessor of this 6498560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// MachineBasicBlock. Don't do this unless you know what you're 6508560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// doing, because it doesn't update pred's successors list. Use 6518560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// pred->removeSuccessor instead. 6528560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// 6533dfbb558b5e74554104710ed16807fe74ec220a3Chris Lattner void removePredecessor(MachineBasicBlock *pred); 654deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve}; 655deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 6561cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarraw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 6570aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 6582a085c34933a6c76e5a86f2680d93c16b0438801Evan Chengvoid WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t); 6592a085c34933a6c76e5a86f2680d93c16b0438801Evan Cheng 66013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen// This is useful when building IndexedMaps keyed on basic block pointers. 66113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesenstruct MBB2NumberFunctor : 66213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen public std::unary_function<const MachineBasicBlock*, unsigned> { 66313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen unsigned operator()(const MachineBasicBlock *MBB) const { 66413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen return MBB->getNumber(); 66513ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen } 66613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen}; 66713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 6680aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner//===--------------------------------------------------------------------===// 6690aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// GraphTraits specializations for machine basic block graphs (machine-CFGs) 6700aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner//===--------------------------------------------------------------------===// 6710aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 6720aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// Provide specializations of GraphTraits to be able to treat a 6730aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// MachineFunction as a graph of MachineBasicBlocks... 6740aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// 6750aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 6760aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<MachineBasicBlock *> { 6770aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock NodeType; 6780aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::succ_iterator ChildIteratorType; 6790aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 6800aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 681ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 6820aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_begin(); 6830aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 684ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 6850aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_end(); 6860aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 6870aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 6880aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 6890aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<const MachineBasicBlock *> { 6900aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef const MachineBasicBlock NodeType; 6910aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 6920aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 6930aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 694ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 6950aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_begin(); 6960aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 697ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 6980aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_end(); 6990aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 7000aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 7010aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 7020aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// Provide specializations of GraphTraits to be able to treat a 7030aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// MachineFunction as a graph of MachineBasicBlocks... and to walk it 7040aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// in inverse order. Inverse order for a function is considered 7050aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// to be when traversing the predecessor edges of a MBB 7060aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// instead of the successor edges. 7070aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// 7080aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 7090aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock NodeType; 7100aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::pred_iterator ChildIteratorType; 7110aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 7120aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return G.Graph; 7130aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 714ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 7150aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_begin(); 7160aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 717ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 7180aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_end(); 7190aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 7200aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 7210aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 7220aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 7230aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef const MachineBasicBlock NodeType; 7240aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 7250aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 726ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman return G.Graph; 7270aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 728ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 7290aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_begin(); 7300aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 731ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 7320aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_end(); 7330aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 7340aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 7350aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 7363bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey 7373bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey 7383bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey/// MachineInstrSpan provides an interface to get an iteration range 7393bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey/// containing the instruction it was initialized with, along with all 7403bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey/// those instructions inserted prior to or following that instruction 7413bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey/// at some point after the MachineInstrSpan is constructed. 7423bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Laceyclass MachineInstrSpan { 7433bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey MachineBasicBlock &MBB; 7443bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey MachineBasicBlock::iterator I, B, E; 7453bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Laceypublic: 7463bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey MachineInstrSpan(MachineBasicBlock::iterator I) 7473bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey : MBB(*I->getParent()), 7483bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey I(I), 7493bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey B(I == MBB.begin() ? MBB.end() : llvm::prior(I)), 7503bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey E(llvm::next(I)) {} 7513bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey 7523bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey MachineBasicBlock::iterator begin() { 7533bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey return B == MBB.end() ? MBB.begin() : llvm::next(B); 7543bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey } 7553bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey MachineBasicBlock::iterator end() { return E; } 7563bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey bool empty() { return begin() == end(); } 7573bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey 7583bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey MachineBasicBlock::iterator getInitial() { return I; } 7593bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey}; 7603bbd96e90be56c39a0b527fc6d5ccd8af4426a03Mark Lacey 761d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 762deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 763deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve#endif 764