MachineBasicBlock.h revision adb877d62e5ac88db037d91bcd2e9f7dc2c4cd7a
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 17c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 18551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/GraphTraits.h" 1913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen#include <functional> 20d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 21d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 22fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman 23853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohmanclass Pass; 24fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanclass BasicBlock; 25fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanclass MachineFunction; 26a655f088b88cf015fc48721fd9869787d1b8ce13Chris Lattnerclass MCSymbol; 27f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesenclass SlotIndexes; 28a655f088b88cf015fc48721fd9869787d1b8ce13Chris Lattnerclass StringRef; 291cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarclass raw_ostream; 30d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3194dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenostemplate <> 328e4018e2de52c534405d7155c7009d0b35afb861Cedric Venetstruct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 338e4018e2de52c534405d7155c7009d0b35afb861Cedric Venetprivate: 347309be6735666143bd9835b275dc8501617a2591Gabor Greif mutable ilist_half_node<MachineInstr> Sentinel; 35fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman 368e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman // this is only set by the MachineBasicBlock owning the LiveList 3794dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos friend class MachineBasicBlock; 388e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineBasicBlock* Parent; 3994dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 408e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohmanpublic: 41c7f6b8c5d40e17bf43fd3a1549d7d89c9da735e1Gabor Greif MachineInstr *createSentinel() const { 42c7f6b8c5d40e17bf43fd3a1549d7d89c9da735e1Gabor Greif return static_cast<MachineInstr*>(&Sentinel); 43c7f6b8c5d40e17bf43fd3a1549d7d89c9da735e1Gabor Greif } 44fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman void destroySentinel(MachineInstr *) const {} 4594dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 46c23b8719ef9d6b1220e854b37d40e9e1c48a82bcGabor Greif MachineInstr *provideInitialHead() const { return createSentinel(); } 47c23b8719ef9d6b1220e854b37d40e9e1c48a82bcGabor Greif MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 48f3841fcbd587c31aa9842b3f33bd57de40c9f443Gabor Greif static void noteHead(MachineInstr*, MachineInstr*) {} 49c23b8719ef9d6b1220e854b37d40e9e1c48a82bcGabor Greif 50aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos void addNodeToList(MachineInstr* N); 51aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos void removeNodeFromList(MachineInstr* N); 52fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman void transferNodesFromList(ilist_traits &SrcTraits, 53fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman ilist_iterator<MachineInstr> first, 54fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman ilist_iterator<MachineInstr> last); 558e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman void deleteNode(MachineInstr *N); 56fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanprivate: 57fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman void createNode(const MachineInstr &); 5894dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos}; 5994dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 60fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanclass MachineBasicBlock : public ilist_node<MachineBasicBlock> { 61fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman typedef ilist<MachineInstr> Instructions; 62c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos Instructions Insts; 631194e9501984daf0d3237ed1bf18a156173e7fd4Chris Lattner const BasicBlock *BB; 64c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke int Number; 65f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner MachineFunction *xParent; 66f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner 6713d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// Predecessors/Successors - Keep track of the predecessor / successor 6813d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// basicblocks. 6913d828567812041c1ca1817f4b66fce840903a1fEvan Cheng std::vector<MachineBasicBlock *> Predecessors; 7013d828567812041c1ca1817f4b66fce840903a1fEvan Cheng std::vector<MachineBasicBlock *> Successors; 7113d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 7213d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// LiveIns - Keep track of the physical registers that are livein of 7313d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// the basicblock. 7413d828567812041c1ca1817f4b66fce840903a1fEvan Cheng std::vector<unsigned> LiveIns; 75fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 76fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// Alignment - Alignment of the basic block. Zero if the basic block does 77fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// not need to be aligned. 78fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng unsigned Alignment; 7930b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey 8030b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// IsLandingPad - Indicate that this basic block is entered via an 8130b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// exception handler. 8230b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey bool IsLandingPad; 8313d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 848c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// AddressTaken - Indicate that this basic block is potentially the 858c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// target of an indirect branch. 868c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman bool AddressTaken; 878c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman 88fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman // Intrusive list support 89fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman MachineBasicBlock() {} 90fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman 918e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 928e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 932c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman ~MachineBasicBlock(); 9417fb34bf8cd10a798c9206eeef3bff151b4d3688Tanya Lattner 958e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman // MachineBasicBlocks are allocated and owned by MachineFunction. 968e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman friend class MachineFunction; 97ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman 988e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohmanpublic: 99d0aa0cdbc6fee00f2b2019633a9b9d00d301ac68Chris Lattner /// getBasicBlock - Return the LLVM basic block that this instance 100324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen /// corresponded to originally. Note that this may be NULL if this instance 101324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen /// does not correspond directly to an LLVM basic block. 102d0aa0cdbc6fee00f2b2019633a9b9d00d301ac68Chris Lattner /// 1031194e9501984daf0d3237ed1bf18a156173e7fd4Chris Lattner const BasicBlock *getBasicBlock() const { return BB; } 1045e61fa95196b85281eec655787e9c73267532bd1Chris Lattner 105324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen /// getName - Return the name of the corresponding LLVM basic block, or 106324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen /// "(null)". 107324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen StringRef getName() const; 108324da7647cfc3025e0c987176f0a300f9f780e6fJakob Stoklund Olesen 1098c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// hasAddressTaken - Test whether this block is potentially the target 1108c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// of an indirect branch. 1118c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman bool hasAddressTaken() const { return AddressTaken; } 1128c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman 1138c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// setHasAddressTaken - Set this block to reflect that it potentially 1148c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman /// is the target of an indirect branch. 1158c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman void setHasAddressTaken() { AddressTaken = true; } 1168c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman 1175e61fa95196b85281eec655787e9c73267532bd1Chris Lattner /// getParent - Return the MachineFunction containing this basic block. 1185e61fa95196b85281eec655787e9c73267532bd1Chris Lattner /// 119f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner const MachineFunction *getParent() const { return xParent; } 120f20c1a497fe3922ac718429d65a5fe396890575eChris Lattner MachineFunction *getParent() { return xParent; } 1215e61fa95196b85281eec655787e9c73267532bd1Chris Lattner 1228e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman typedef Instructions::iterator iterator; 1238e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman typedef Instructions::const_iterator const_iterator; 124deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 125deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve typedef std::reverse_iterator<iterator> reverse_iterator; 126deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 12734cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned size() const { return (unsigned)Insts.size(); } 128deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve bool empty() const { return Insts.empty(); } 129deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 130c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineInstr& front() { return Insts.front(); } 131c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineInstr& back() { return Insts.back(); } 1328e8b8a223c2b0e69f44c0639f846260c8011668fDan Gohman const MachineInstr& front() const { return Insts.front(); } 1338e8b8a223c2b0e69f44c0639f846260c8011668fDan Gohman const MachineInstr& back() const { return Insts.back(); } 134deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 135deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve iterator begin() { return Insts.begin(); } 136deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve const_iterator begin() const { return Insts.begin(); } 137deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve iterator end() { return Insts.end(); } 138deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve const_iterator end() const { return Insts.end(); } 139deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve reverse_iterator rbegin() { return Insts.rbegin(); } 140deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve const_reverse_iterator rbegin() const { return Insts.rbegin(); } 141deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve reverse_iterator rend () { return Insts.rend(); } 142deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve const_reverse_iterator rend () const { return Insts.rend(); } 143deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 14476456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke // Machine-CFG iterators 14576456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 14676456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 14776456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 14876456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 1496603d7ec67e64b987451975771759ade4e9f19baEvan Cheng typedef std::vector<MachineBasicBlock *>::reverse_iterator 1506603d7ec67e64b987451975771759ade4e9f19baEvan Cheng pred_reverse_iterator; 1516603d7ec67e64b987451975771759ade4e9f19baEvan Cheng typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 1526603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_pred_reverse_iterator; 1536603d7ec67e64b987451975771759ade4e9f19baEvan Cheng typedef std::vector<MachineBasicBlock *>::reverse_iterator 1546603d7ec67e64b987451975771759ade4e9f19baEvan Cheng succ_reverse_iterator; 1556603d7ec67e64b987451975771759ade4e9f19baEvan Cheng typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 1566603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_succ_reverse_iterator; 157ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman 158cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner pred_iterator pred_begin() { return Predecessors.begin(); } 159cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner const_pred_iterator pred_begin() const { return Predecessors.begin(); } 160cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner pred_iterator pred_end() { return Predecessors.end(); } 161cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner const_pred_iterator pred_end() const { return Predecessors.end(); } 1626603d7ec67e64b987451975771759ade4e9f19baEvan Cheng pred_reverse_iterator pred_rbegin() 1636603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Predecessors.rbegin();} 1646603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_pred_reverse_iterator pred_rbegin() const 1656603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Predecessors.rbegin();} 1666603d7ec67e64b987451975771759ade4e9f19baEvan Cheng pred_reverse_iterator pred_rend() 1676603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Predecessors.rend(); } 1686603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_pred_reverse_iterator pred_rend() const 1696603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Predecessors.rend(); } 17034cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned pred_size() const { 17134cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng return (unsigned)Predecessors.size(); 17234cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng } 173cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner bool pred_empty() const { return Predecessors.empty(); } 174cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner succ_iterator succ_begin() { return Successors.begin(); } 175cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner const_succ_iterator succ_begin() const { return Successors.begin(); } 176cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner succ_iterator succ_end() { return Successors.end(); } 177cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner const_succ_iterator succ_end() const { return Successors.end(); } 1786603d7ec67e64b987451975771759ade4e9f19baEvan Cheng succ_reverse_iterator succ_rbegin() 1796603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Successors.rbegin(); } 1806603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_succ_reverse_iterator succ_rbegin() const 1816603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Successors.rbegin(); } 1826603d7ec67e64b987451975771759ade4e9f19baEvan Cheng succ_reverse_iterator succ_rend() 1836603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Successors.rend(); } 1846603d7ec67e64b987451975771759ade4e9f19baEvan Cheng const_succ_reverse_iterator succ_rend() const 1856603d7ec67e64b987451975771759ade4e9f19baEvan Cheng { return Successors.rend(); } 18634cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned succ_size() const { 18734cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng return (unsigned)Successors.size(); 18834cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng } 189cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner bool succ_empty() const { return Successors.empty(); } 19076456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 19113d828567812041c1ca1817f4b66fce840903a1fEvan Cheng // LiveIn management methods. 19213d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 19313d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// addLiveIn - Add the specified register as a live in. Note that it 19413d828567812041c1ca1817f4b66fce840903a1fEvan Cheng /// is an error to add the same register to the same set more than once. 19513d828567812041c1ca1817f4b66fce840903a1fEvan Cheng void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 19613d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 197b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng /// removeLiveIn - Remove the specified register from the live in set. 198b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng /// 199b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng void removeLiveIn(unsigned Reg); 200b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 201a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng /// isLiveIn - Return true if the specified register is in the live in set. 202a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng /// 203a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng bool isLiveIn(unsigned Reg) const; 204a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng 20513d828567812041c1ca1817f4b66fce840903a1fEvan Cheng // Iteration support for live in sets. These sets are kept in sorted 20613d828567812041c1ca1817f4b66fce840903a1fEvan Cheng // order by their register number. 20781bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman typedef std::vector<unsigned>::const_iterator livein_iterator; 20881bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman livein_iterator livein_begin() const { return LiveIns.begin(); } 20981bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman livein_iterator livein_end() const { return LiveIns.end(); } 21013d828567812041c1ca1817f4b66fce840903a1fEvan Cheng bool livein_empty() const { return LiveIns.empty(); } 21113d828567812041c1ca1817f4b66fce840903a1fEvan Cheng 212fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// getAlignment - Return alignment of the basic block. 213fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// 214fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng unsigned getAlignment() const { return Alignment; } 215fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 216fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// setAlignment - Set alignment of the basic block. 217fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng /// 218fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng void setAlignment(unsigned Align) { Alignment = Align; } 219fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng 22030b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// isLandingPad - Returns true if the block is a landing pad. That is 22130b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// this basic block is entered via an exception handler. 22230b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey bool isLandingPad() const { return IsLandingPad; } 22330b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey 22430b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// setIsLandingPad - Indicates the block is a landing pad. That is 22530b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey /// this basic block is entered via an exception handler. 22630b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey void setIsLandingPad() { IsLandingPad = true; } 22730b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey 228cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen /// getLandingPadSuccessor - If this block has a successor that is a landing 229cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen /// pad, return it. Otherwise return NULL. 230cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen const MachineBasicBlock *getLandingPadSuccessor() const; 231cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 23234ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner // Code Layout methods. 23334ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner 23434ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner /// moveBefore/moveAfter - move 'this' block before or after the specified 23534ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner /// block. This only moves the block, it does not modify the CFG or adjust 23634ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner /// potential fall-throughs at the end of the block. 23734ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner void moveBefore(MachineBasicBlock *NewAfter); 23834ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner void moveAfter(MachineBasicBlock *NewBefore); 2397707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach 2407707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach /// updateTerminator - Update the terminator instructions in block to account 2417707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach /// for changes to the layout. If the block previously used a fallthrough, 2427707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach /// it may now need a branch, and if it previously used branching it may now 2437707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach /// be able to use a fallthrough. 2447707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach void updateTerminator(); 2457707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach 24676456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke // Machine-CFG mutators 24734ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner 24876456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 24976456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// The Predecessors list of succ is automatically updated. 25076456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// 2513dfbb558b5e74554104710ed16807fe74ec220a3Chris Lattner void addSuccessor(MachineBasicBlock *succ); 25276456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 253dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner /// removeSuccessor - Remove successor from the successors list of this 25476456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 25576456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// 2563dfbb558b5e74554104710ed16807fe74ec220a3Chris Lattner void removeSuccessor(MachineBasicBlock *succ); 257dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner 258dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner /// removeSuccessor - Remove specified successor from the successors list of 259dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner /// this MachineBasicBlock. The Predecessors list of succ is automatically 2608a46d342d8cbca7c9c7be6c66007d41329babad0David Greene /// updated. Return the iterator to the element after the one removed. 261dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner /// 2628a46d342d8cbca7c9c7be6c66007d41329babad0David Greene succ_iterator removeSuccessor(succ_iterator I); 263cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner 26463307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang /// transferSuccessors - Transfers all the successors from MBB to this 26563307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang /// machine basic block (i.e., copies all the successors fromMBB and 2661edb8e0910db4cda46a81a4abad80a2a755442aaDan Gohman /// remove all the successors from fromMBB). 26763307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang void transferSuccessors(MachineBasicBlock *fromMBB); 26814152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman 26914152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as 27014152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman /// in transferSuccessors, and update PHI operands in the successor blocks 27114152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman /// which refer to fromMBB to refer to this. 27214152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB); 27363307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang 274cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner /// isSuccessor - Return true if the specified MBB is a successor of this 275cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner /// block. 2766d1b89e74f98470d05666ca9f59a8ec5d04b5eb4Dan Gohman bool isSuccessor(const MachineBasicBlock *MBB) const; 27776456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 2786ade6f55a836129af634074e96f660ff23f59a30Dan Gohman /// isLayoutSuccessor - Return true if the specified MBB will be emitted 2796ade6f55a836129af634074e96f660ff23f59a30Dan Gohman /// immediately after this block, such that if this block exits by 2806ade6f55a836129af634074e96f660ff23f59a30Dan Gohman /// falling through, control will transfer to the specified MBB. Note 2816ade6f55a836129af634074e96f660ff23f59a30Dan Gohman /// that MBB need not be a successor at all, for example if this block 2826ade6f55a836129af634074e96f660ff23f59a30Dan Gohman /// ends with an unconditional branch to some other block. 2836d1b89e74f98470d05666ca9f59a8ec5d04b5eb4Dan Gohman bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 2846ade6f55a836129af634074e96f660ff23f59a30Dan Gohman 28515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson /// canFallThrough - Return true if the block can implicitly transfer 28615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson /// control to the block after it by falling off the end of it. This should 28715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson /// return false if it can reach the block after it, but it uses an explicit 28815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson /// branch to do so (e.g., a table jump). True is a conservative answer. 28915acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson bool canFallThrough(); 29015acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson 291d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman /// Returns a pointer to the first instructon in this block that is not a 292d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman /// PHINode instruction. When adding instruction to the beginning of the 293d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman /// basic block, they should be added before the returned value, not before 294d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman /// the first instruction, which might be PHI. 295d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman /// Returns end() is there's no non-PHI instruction. 296d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman iterator getFirstNonPHI(); 297d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman 29892095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is 29992095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen /// not a PHI or a label. This is the correct point to insert copies at the 30092095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen /// beginning of a basic block. 30192095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen iterator SkipPHIsAndLabels(iterator I); 30292095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen 303743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos /// getFirstTerminator - returns an iterator to the first terminator 304743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos /// instruction of this basic block. If a terminator does not exist, 305743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos /// it returns end() 306743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos iterator getFirstTerminator(); 307743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos 3084f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen /// getLastNonDebugInstr - returns an iterator to the last non-debug 3094f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen /// instruction in the basic block, or end() 3104f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen iterator getLastNonDebugInstr(); 3114f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen 312adb877d62e5ac88db037d91bcd2e9f7dc2c4cd7aJakob Stoklund Olesen const_iterator getLastNonDebugInstr() const { 313adb877d62e5ac88db037d91bcd2e9f7dc2c4cd7aJakob Stoklund Olesen return const_cast<MachineBasicBlock*>(this)->getLastNonDebugInstr(); 314adb877d62e5ac88db037d91bcd2e9f7dc2c4cd7aJakob Stoklund Olesen } 315adb877d62e5ac88db037d91bcd2e9f7dc2c4cd7aJakob Stoklund Olesen 316853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// SplitCriticalEdge - Split the critical edge from this block to the 317853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// given successor block, and return the newly created block, or null 318853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// if splitting is not possible. 319853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// 320853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// This function updates LiveVariables, MachineDominatorTree, and 321853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman /// MachineLoopInfo, as applicable. 322853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P); 323853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman 3240bbcd6bfd1a90c2aa7386a88ba9fc9aba47d03a7Brian Gaeke void pop_front() { Insts.pop_front(); } 325f24d879520a615a03f19ced3c7491f7b51934d1cChris Lattner void pop_back() { Insts.pop_back(); } 326deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve void push_back(MachineInstr *MI) { Insts.push_back(MI); } 327deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve template<typename IT> 328deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } 329deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } 330704b07613eb16b7ffb8c8cbc94482bf7425ccd77Devang Patel iterator insertAfter(iterator I, MachineInstr *M) { 331704b07613eb16b7ffb8c8cbc94482bf7425ccd77Devang Patel return Insts.insertAfter(I, M); 332704b07613eb16b7ffb8c8cbc94482bf7425ccd77Devang Patel } 333deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 33446d6a1aeb549a2e4ccd982a1a2cefda541d79c52Vikram S. Adve // erase - Remove the specified element or range from the instruction list. 335c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos // These functions delete any instructions removed. 336deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve // 33746d6a1aeb549a2e4ccd982a1a2cefda541d79c52Vikram S. Adve iterator erase(iterator I) { return Insts.erase(I); } 338deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } 33983706a5a3a6f19451765b743c5a72b62f74eb71aChris Lattner MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } 340da44b151259525abc9c299f89b9532f3a9883b4eBrian Gaeke void clear() { Insts.clear(); } 341ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman 342c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman /// splice - Take an instruction from MBB 'Other' at the position From, 343c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman /// and insert it into this MBB right before 'where'. 344c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman void splice(iterator where, MachineBasicBlock *Other, iterator From) { 345c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman Insts.splice(where, Other->Insts, From); 346c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman } 347c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 348f24d879520a615a03f19ced3c7491f7b51934d1cChris Lattner /// splice - Take a block of instructions from MBB 'Other' in the range [From, 349f24d879520a615a03f19ced3c7491f7b51934d1cChris Lattner /// To), and insert them into this MBB right before 'where'. 350f24d879520a615a03f19ced3c7491f7b51934d1cChris Lattner void splice(iterator where, MachineBasicBlock *Other, iterator From, 351f24d879520a615a03f19ced3c7491f7b51934d1cChris Lattner iterator To) { 352f24d879520a615a03f19ced3c7491f7b51934d1cChris Lattner Insts.splice(where, Other->Insts, From, To); 353f24d879520a615a03f19ced3c7491f7b51934d1cChris Lattner } 3548e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattner 3558e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman /// removeFromParent - This method unlinks 'this' from the containing 3568e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman /// function, and returns it, but does not delete it. 3578e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MachineBasicBlock *removeFromParent(); 3588e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 3598e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman /// eraseFromParent - This method unlinks 'this' from the containing 3608e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman /// function and deletes it. 3618e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman void eraseFromParent(); 3628e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman 3630370fad74b48388412c52d1325512f2c218487faEvan Cheng /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 3640370fad74b48388412c52d1325512f2c218487faEvan Cheng /// 'Old', change the code and CFG so that it branches to 'New' instead. 3650370fad74b48388412c52d1325512f2c218487faEvan Cheng void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 3660370fad74b48388412c52d1325512f2c218487faEvan Cheng 3672bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 3682bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// the CFG to be inserted. If we have proven that MBB can only branch to 3692bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 3702bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// DestB can be null. Besides DestA and DestB, retain other edges leading 3712bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// to LandingPads (currently there can be only one; we don't check or require 3722bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng /// that here). Note it is possible that DestA and/or DestB are LandingPads. 3732bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 3742bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng MachineBasicBlock *DestB, 3752bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng bool isCond); 3762bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng 37773e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 3783b1906f48d0b541e5be0bc1918c94a454e908bc0Dale Johannesen /// any DBG_VALUE instructions. Return UnknownLoc if there is none. 37973e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen DebugLoc findDebugLoc(MachineBasicBlock::iterator &MBBI); 38073e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen 381f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke // Debugging methods. 382f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke void dump() const; 383f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen void print(raw_ostream &OS, SlotIndexes* = 0) const; 384f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke 385da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke /// getNumber - MachineBasicBlocks are uniquely numbered at the function 386da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke /// level, unless they're not in a MachineFunction yet, in which case this 387da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke /// will return -1. 388da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke /// 389c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke int getNumber() const { return Number; } 39020a6d8e63056cc2025e7143a5f7226e079e0bc80Chris Lattner void setNumber(int N) { Number = N; } 391c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke 392f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner /// getSymbol - Return the MCSymbol for this basic block. 393f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner /// 3941b2eb0e8a6aaf034675b17be6d853cb1c666200fChris Lattner MCSymbol *getSymbol() const; 395f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner 3968e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattnerprivate: // Methods used to maintain doubly linked list of blocks... 397fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman friend struct ilist_traits<MachineBasicBlock>; 3988560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke 3998560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke // Machine-CFG mutators 4008560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke 4018560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 4028560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// Don't do this unless you know what you're doing, because it doesn't 4038560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// update pred's successors list. Use pred->addSuccessor instead. 4048560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// 4053dfbb558b5e74554104710ed16807fe74ec220a3Chris Lattner void addPredecessor(MachineBasicBlock *pred); 4068560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke 4078560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// removePredecessor - Remove pred as a predecessor of this 4088560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// MachineBasicBlock. Don't do this unless you know what you're 4098560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// doing, because it doesn't update pred's successors list. Use 4108560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// pred->removeSuccessor instead. 4118560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// 4123dfbb558b5e74554104710ed16807fe74ec220a3Chris Lattner void removePredecessor(MachineBasicBlock *pred); 413deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve}; 414deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 4151cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarraw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 4160aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 4172a085c34933a6c76e5a86f2680d93c16b0438801Evan Chengvoid WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t); 4182a085c34933a6c76e5a86f2680d93c16b0438801Evan Cheng 41913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen// This is useful when building IndexedMaps keyed on basic block pointers. 42013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesenstruct MBB2NumberFunctor : 42113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen public std::unary_function<const MachineBasicBlock*, unsigned> { 42213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen unsigned operator()(const MachineBasicBlock *MBB) const { 42313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen return MBB->getNumber(); 42413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen } 42513ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen}; 42613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 4270aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner//===--------------------------------------------------------------------===// 4280aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// GraphTraits specializations for machine basic block graphs (machine-CFGs) 4290aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner//===--------------------------------------------------------------------===// 4300aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 4310aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// Provide specializations of GraphTraits to be able to treat a 4320aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// MachineFunction as a graph of MachineBasicBlocks... 4330aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// 4340aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 4350aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<MachineBasicBlock *> { 4360aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock NodeType; 4370aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::succ_iterator ChildIteratorType; 4380aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 4390aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 440ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 4410aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_begin(); 4420aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 443ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 4440aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_end(); 4450aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 4460aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 4470aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 4480aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<const MachineBasicBlock *> { 4490aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef const MachineBasicBlock NodeType; 4500aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 4510aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 4520aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 453ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 4540aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_begin(); 4550aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 456ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 4570aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_end(); 4580aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 4590aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 4600aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 4610aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// Provide specializations of GraphTraits to be able to treat a 4620aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// MachineFunction as a graph of MachineBasicBlocks... and to walk it 4630aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// in inverse order. Inverse order for a function is considered 4640aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// to be when traversing the predecessor edges of a MBB 4650aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// instead of the successor edges. 4660aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// 4670aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 4680aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock NodeType; 4690aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::pred_iterator ChildIteratorType; 4700aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 4710aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return G.Graph; 4720aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 473ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 4740aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_begin(); 4750aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 476ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 4770aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_end(); 4780aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 4790aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 4800aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 4810aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 4820aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef const MachineBasicBlock NodeType; 4830aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 4840aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 485ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman return G.Graph; 4860aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 487ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_begin(NodeType *N) { 4880aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_begin(); 4890aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 490ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman static inline ChildIteratorType child_end(NodeType *N) { 4910aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_end(); 4920aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 4930aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 4940aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 495d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 496deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 497deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve#endif 498