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()) {}
163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    bundle_iterator() : MII(nullptr) {}
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
222dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  MachineInstr       &instr_front()       { return Insts.front(); }
223dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  MachineInstr       &instr_back()        { return Insts.back();  }
224dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  const MachineInstr &instr_front() const { return Insts.front(); }
225dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  const MachineInstr &instr_back()  const { return Insts.back();  }
226dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines
227dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  MachineInstr       &front()             { return Insts.front(); }
228dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  MachineInstr       &back()              { return *--end();      }
229dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  const MachineInstr &front()       const { return Insts.front(); }
230dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  const MachineInstr &back()        const { return *--end();      }
231deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve
232ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  instr_iterator                instr_begin()       { return Insts.begin();  }
233ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  const_instr_iterator          instr_begin() const { return Insts.begin();  }
234ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  instr_iterator                  instr_end()       { return Insts.end();    }
235ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  const_instr_iterator            instr_end() const { return Insts.end();    }
236ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  reverse_instr_iterator       instr_rbegin()       { return Insts.rbegin(); }
237ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); }
238ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  reverse_instr_iterator       instr_rend  ()       { return Insts.rend();   }
239ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  const_reverse_instr_iterator instr_rend  () const { return Insts.rend();   }
2407c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng
24120aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen  iterator                begin()       { return instr_begin();  }
24220aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen  const_iterator          begin() const { return instr_begin();  }
24320aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen  iterator                end  ()       { return instr_end();    }
24420aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen  const_iterator          end  () const { return instr_end();    }
24520aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen  reverse_iterator       rbegin()       { return instr_rbegin(); }
24620aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen  const_reverse_iterator rbegin() const { return instr_rbegin(); }
24720aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen  reverse_iterator       rend  ()       { return instr_rend();   }
24820aedcdfa35f4b6494d4990cf6dd4459d7172c49Jakob Stoklund Olesen  const_reverse_iterator rend  () const { return instr_rend();   }
249deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve
250dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  inline iterator_range<iterator> terminators() {
251dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    return iterator_range<iterator>(getFirstTerminator(), end());
252dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  }
253dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  inline iterator_range<const_iterator> terminators() const {
254dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    return iterator_range<const_iterator>(getFirstTerminator(), end());
255dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  }
2567c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng
25776456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke  // Machine-CFG iterators
25876456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke  typedef std::vector<MachineBasicBlock *>::iterator       pred_iterator;
25976456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke  typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator;
26076456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke  typedef std::vector<MachineBasicBlock *>::iterator       succ_iterator;
26176456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke  typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator;
2626603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  typedef std::vector<MachineBasicBlock *>::reverse_iterator
2636603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                                         pred_reverse_iterator;
2646603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  typedef std::vector<MachineBasicBlock *>::const_reverse_iterator
2656603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                                   const_pred_reverse_iterator;
2666603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  typedef std::vector<MachineBasicBlock *>::reverse_iterator
2676603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                                         succ_reverse_iterator;
2686603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  typedef std::vector<MachineBasicBlock *>::const_reverse_iterator
2696603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                                   const_succ_reverse_iterator;
270cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  pred_iterator        pred_begin()       { return Predecessors.begin(); }
271cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  const_pred_iterator  pred_begin() const { return Predecessors.begin(); }
272cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  pred_iterator        pred_end()         { return Predecessors.end();   }
273cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  const_pred_iterator  pred_end()   const { return Predecessors.end();   }
2746603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  pred_reverse_iterator        pred_rbegin()
2756603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                          { return Predecessors.rbegin();}
2766603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  const_pred_reverse_iterator  pred_rbegin() const
2776603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                          { return Predecessors.rbegin();}
2786603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  pred_reverse_iterator        pred_rend()
2796603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                          { return Predecessors.rend();  }
2806603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  const_pred_reverse_iterator  pred_rend()   const
2816603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                          { return Predecessors.rend();  }
28234cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng  unsigned             pred_size()  const {
28334cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng    return (unsigned)Predecessors.size();
28434cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng  }
285cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  bool                 pred_empty() const { return Predecessors.empty(); }
286cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  succ_iterator        succ_begin()       { return Successors.begin();   }
287cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  const_succ_iterator  succ_begin() const { return Successors.begin();   }
288cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  succ_iterator        succ_end()         { return Successors.end();     }
289cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  const_succ_iterator  succ_end()   const { return Successors.end();     }
2906603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  succ_reverse_iterator        succ_rbegin()
2916603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                          { return Successors.rbegin();  }
2926603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  const_succ_reverse_iterator  succ_rbegin() const
2936603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                          { return Successors.rbegin();  }
2946603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  succ_reverse_iterator        succ_rend()
2956603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                          { return Successors.rend();    }
2966603d7ec67e64b987451975771759ade4e9f19baEvan Cheng  const_succ_reverse_iterator  succ_rend()   const
2976603d7ec67e64b987451975771759ade4e9f19baEvan Cheng                                          { return Successors.rend();    }
29834cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng  unsigned             succ_size()  const {
29934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng    return (unsigned)Successors.size();
30034cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng  }
301cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  bool                 succ_empty() const { return Successors.empty();   }
30276456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke
303dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  inline iterator_range<pred_iterator> predecessors() {
304dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    return iterator_range<pred_iterator>(pred_begin(), pred_end());
305dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  }
306dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  inline iterator_range<const_pred_iterator> predecessors() const {
307dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    return iterator_range<const_pred_iterator>(pred_begin(), pred_end());
308dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  }
309dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  inline iterator_range<succ_iterator> successors() {
310dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    return iterator_range<succ_iterator>(succ_begin(), succ_end());
311dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  }
312dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  inline iterator_range<const_succ_iterator> successors() const {
313dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    return iterator_range<const_succ_iterator>(succ_begin(), succ_end());
314dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  }
315dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines
31613d828567812041c1ca1817f4b66fce840903a1fEvan Cheng  // LiveIn management methods.
31713d828567812041c1ca1817f4b66fce840903a1fEvan Cheng
31813d828567812041c1ca1817f4b66fce840903a1fEvan Cheng  /// addLiveIn - Add the specified register as a live in.  Note that it
31913d828567812041c1ca1817f4b66fce840903a1fEvan Cheng  /// is an error to add the same register to the same set more than once.
32013d828567812041c1ca1817f4b66fce840903a1fEvan Cheng  void addLiveIn(unsigned Reg)  { LiveIns.push_back(Reg); }
32113d828567812041c1ca1817f4b66fce840903a1fEvan Cheng
322f64765244512250b28b1fbe290b1b26d17e41dd4Jakob Stoklund Olesen  /// Add PhysReg as live in to this block, and ensure that there is a copy of
323f64765244512250b28b1fbe290b1b26d17e41dd4Jakob Stoklund Olesen  /// PhysReg to a virtual register of class RC. Return the virtual register
324f64765244512250b28b1fbe290b1b26d17e41dd4Jakob Stoklund Olesen  /// that is a copy of the live in PhysReg.
325f64765244512250b28b1fbe290b1b26d17e41dd4Jakob Stoklund Olesen  unsigned addLiveIn(unsigned PhysReg, const TargetRegisterClass *RC);
326f64765244512250b28b1fbe290b1b26d17e41dd4Jakob Stoklund Olesen
327b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng  /// removeLiveIn - Remove the specified register from the live in set.
328b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng  ///
329b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng  void removeLiveIn(unsigned Reg);
330b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng
331a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng  /// isLiveIn - Return true if the specified register is in the live in set.
332a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng  ///
333a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng  bool isLiveIn(unsigned Reg) const;
334a971dbdde27fd4ff53dbebdd4aaf87826d081aa2Evan Cheng
33513d828567812041c1ca1817f4b66fce840903a1fEvan Cheng  // Iteration support for live in sets.  These sets are kept in sorted
33613d828567812041c1ca1817f4b66fce840903a1fEvan Cheng  // order by their register number.
33781bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman  typedef std::vector<unsigned>::const_iterator livein_iterator;
33881bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman  livein_iterator livein_begin() const { return LiveIns.begin(); }
33981bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman  livein_iterator livein_end()   const { return LiveIns.end(); }
34013d828567812041c1ca1817f4b66fce840903a1fEvan Cheng  bool            livein_empty() const { return LiveIns.empty(); }
34113d828567812041c1ca1817f4b66fce840903a1fEvan Cheng
342fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng  /// getAlignment - Return alignment of the basic block.
3438c741b8064f1116d8d8dc435b60b75abdf5c4d57Jakob Stoklund Olesen  /// The alignment is specified as log2(bytes).
344fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng  ///
345fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng  unsigned getAlignment() const { return Alignment; }
346fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng
347fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng  /// setAlignment - Set alignment of the basic block.
3488c741b8064f1116d8d8dc435b60b75abdf5c4d57Jakob Stoklund Olesen  /// The alignment is specified as log2(bytes).
349fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng  ///
350fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng  void setAlignment(unsigned Align) { Alignment = Align; }
351fb8075d03f5c87bd57dcc9c5f2304f6b13c55aadEvan Cheng
35230b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey  /// isLandingPad - Returns true if the block is a landing pad. That is
35330b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey  /// this basic block is entered via an exception handler.
35430b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey  bool isLandingPad() const { return IsLandingPad; }
35530b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey
35630b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey  /// setIsLandingPad - Indicates the block is a landing pad.  That is
35730b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey  /// this basic block is entered via an exception handler.
358fbf5f1b72b25de35452d89a4ccd7887f79880be8Bill Wendling  void setIsLandingPad(bool V = true) { IsLandingPad = V; }
35930b8e51addc23fb317c03d093a25828d3d5be45aJim Laskey
360cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen  /// getLandingPadSuccessor - If this block has a successor that is a landing
361cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen  /// pad, return it. Otherwise return NULL.
362cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen  const MachineBasicBlock *getLandingPadSuccessor() const;
363cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen
36434ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner  // Code Layout methods.
36557cae881e2b6c85a562d3fd2a7f10bf9d7921b40Jim Grosbach
36634ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner  /// moveBefore/moveAfter - move 'this' block before or after the specified
36734ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner  /// block.  This only moves the block, it does not modify the CFG or adjust
36834ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner  /// potential fall-throughs at the end of the block.
36934ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner  void moveBefore(MachineBasicBlock *NewAfter);
37034ea07692f4cd7c007f1c5062bcebb6d03131077Chris Lattner  void moveAfter(MachineBasicBlock *NewBefore);
3717707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach
3727707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach  /// updateTerminator - Update the terminator instructions in block to account
3737707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach  /// for changes to the layout. If the block previously used a fallthrough,
3747707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach  /// it may now need a branch, and if it previously used branching it may now
3757707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach  /// be able to use a fallthrough.
3767707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach  void updateTerminator();
3777707a0df5b00c8326a581205639d6b2871f182e9Jim Grosbach
37876456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke  // Machine-CFG mutators
3797cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak
38076456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke  /// addSuccessor - Add succ as a successor of this MachineBasicBlock.
3817cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  /// The Predecessors list of succ is automatically updated. WEIGHT
3827cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  /// parameter is stored in Weights list and it may be used by
3837cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  /// MachineBranchProbabilityInfo analysis to calculate branch probability.
38476456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke  ///
3852c5a960b0eae0634da6e1854111b35f475e65335Jakob Stoklund Olesen  /// Note that duplicate Machine CFG edges are not allowed.
3862c5a960b0eae0634da6e1854111b35f475e65335Jakob Stoklund Olesen  ///
3877cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0);
38876456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke
38936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines  /// Set successor weight of a given iterator.
39036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines  void setSuccWeight(succ_iterator I, uint32_t weight);
39136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines
392dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner  /// removeSuccessor - Remove successor from the successors list of this
39376456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke  /// MachineBasicBlock. The Predecessors list of succ is automatically updated.
39476456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke  ///
3953dfbb558b5e74554104710ed16807fe74ec220a3Chris Lattner  void removeSuccessor(MachineBasicBlock *succ);
396dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner
397dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner  /// removeSuccessor - Remove specified successor from the successors list of
398dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner  /// this MachineBasicBlock. The Predecessors list of succ is automatically
3998a46d342d8cbca7c9c7be6c66007d41329babad0David Greene  /// updated.  Return the iterator to the element after the one removed.
400dc4a4922d32b470acd68498d41e3b8130cf1e74eChris Lattner  ///
4018a46d342d8cbca7c9c7be6c66007d41329babad0David Greene  succ_iterator removeSuccessor(succ_iterator I);
4027cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak
4037cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  /// replaceSuccessor - Replace successor OLD with NEW and update weight info.
4047cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  ///
4057cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New);
4067cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak
4077cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak
40863307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang  /// transferSuccessors - Transfers all the successors from MBB to this
40963307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang  /// machine basic block (i.e., copies all the successors fromMBB and
4101edb8e0910db4cda46a81a4abad80a2a755442aaDan Gohman  /// remove all the successors from fromMBB).
41163307c335aa08b0d6a75f81d64d79af7e90eb78bMon P Wang  void transferSuccessors(MachineBasicBlock *fromMBB);
41214152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman
41314152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman  /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as
41414152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman  /// in transferSuccessors, and update PHI operands in the successor blocks
41514152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman  /// which refer to fromMBB to refer to this.
41614152b480d09c7ca912af7c06d00b0ff3912e4f5Dan Gohman  void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB);
41757cae881e2b6c85a562d3fd2a7f10bf9d7921b40Jim Grosbach
418f192b507a33b2ab2e2f6271bb1ea6ed4fbda69e7Jakob Stoklund Olesen  /// isPredecessor - Return true if the specified MBB is a predecessor of this
419f192b507a33b2ab2e2f6271bb1ea6ed4fbda69e7Jakob Stoklund Olesen  /// block.
420f192b507a33b2ab2e2f6271bb1ea6ed4fbda69e7Jakob Stoklund Olesen  bool isPredecessor(const MachineBasicBlock *MBB) const;
421f192b507a33b2ab2e2f6271bb1ea6ed4fbda69e7Jakob Stoklund Olesen
422cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  /// isSuccessor - Return true if the specified MBB is a successor of this
423cd5bad37112ba22f4c546e5443714570b4104bb6Chris Lattner  /// block.
4246d1b89e74f98470d05666ca9f59a8ec5d04b5eb4Dan Gohman  bool isSuccessor(const MachineBasicBlock *MBB) const;
42576456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke
4266ade6f55a836129af634074e96f660ff23f59a30Dan Gohman  /// isLayoutSuccessor - Return true if the specified MBB will be emitted
4276ade6f55a836129af634074e96f660ff23f59a30Dan Gohman  /// immediately after this block, such that if this block exits by
4286ade6f55a836129af634074e96f660ff23f59a30Dan Gohman  /// falling through, control will transfer to the specified MBB. Note
4296ade6f55a836129af634074e96f660ff23f59a30Dan Gohman  /// that MBB need not be a successor at all, for example if this block
4306ade6f55a836129af634074e96f660ff23f59a30Dan Gohman  /// ends with an unconditional branch to some other block.
4316d1b89e74f98470d05666ca9f59a8ec5d04b5eb4Dan Gohman  bool isLayoutSuccessor(const MachineBasicBlock *MBB) const;
4326ade6f55a836129af634074e96f660ff23f59a30Dan Gohman
43315acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson  /// canFallThrough - Return true if the block can implicitly transfer
43415acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson  /// control to the block after it by falling off the end of it.  This should
43515acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson  /// return false if it can reach the block after it, but it uses an explicit
43615acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson  /// branch to do so (e.g., a table jump).  True is a conservative answer.
43715acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson  bool canFallThrough();
43815acadde5f87703da5f36721a19c09a7e3f97f53Bob Wilson
4393f4f420ab7acb10221ba971543a7eed5489fb626Robert Wilhelm  /// Returns a pointer to the first instruction in this block that is not a
4403f4f420ab7acb10221ba971543a7eed5489fb626Robert Wilhelm  /// PHINode instruction. When adding instructions to the beginning of the
441d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman  /// basic block, they should be added before the returned value, not before
442d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman  /// the first instruction, which might be PHI.
443d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman  /// Returns end() is there's no non-PHI instruction.
444d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman  iterator getFirstNonPHI();
445d463a7446402f0771465fe66fe0a7d9f72534902Dan Gohman
44692095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen  /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is
44792095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen  /// not a PHI or a label. This is the correct point to insert copies at the
44892095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen  /// beginning of a basic block.
44992095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen  iterator SkipPHIsAndLabels(iterator I);
45092095e7b3f1eef7b4f2eb0cf037e6b7a01478dabJakob Stoklund Olesen
451743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos  /// getFirstTerminator - returns an iterator to the first terminator
452743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos  /// instruction of this basic block. If a terminator does not exist,
453743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos  /// it returns end()
454743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos  iterator getFirstTerminator();
4557c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  const_iterator getFirstTerminator() const;
456743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos
457ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  /// getFirstInstrTerminator - Same getFirstTerminator but it ignores bundles
458ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  /// and return an instr_iterator instead.
459ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  instr_iterator getFirstInstrTerminator();
4601a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen
4614f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen  /// getLastNonDebugInstr - returns an iterator to the last non-debug
4624f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen  /// instruction in the basic block, or end()
4634f28c1c71450c711e96aa283de53739d8b4504cdJakob Stoklund Olesen  iterator getLastNonDebugInstr();
4647c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  const_iterator getLastNonDebugInstr() const;
465adb877d62e5ac88db037d91bcd2e9f7dc2c4cd7aJakob Stoklund Olesen
466853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman  /// SplitCriticalEdge - Split the critical edge from this block to the
467853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman  /// given successor block, and return the newly created block, or null
468853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman  /// if splitting is not possible.
469853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman  ///
470853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman  /// This function updates LiveVariables, MachineDominatorTree, and
471853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman  /// MachineLoopInfo, as applicable.
472853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman  MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P);
473853d3fb8d24fab2258e9cd5dce3ec8ff4189eedaDan Gohman
4740bbcd6bfd1a90c2aa7386a88ba9fc9aba47d03a7Brian Gaeke  void pop_front() { Insts.pop_front(); }
475f24d879520a615a03f19ced3c7491f7b51934d1cChris Lattner  void pop_back() { Insts.pop_back(); }
476deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve  void push_back(MachineInstr *MI) { Insts.push_back(MI); }
4777c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng
478edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  /// Insert MI into the instruction list before I, possibly inside a bundle.
479edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  ///
480edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  /// If the insertion point is inside a bundle, MI will be added to the bundle,
481edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  /// otherwise MI will not be added to any bundle. That means this function
482edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  /// alone can't be used to prepend or append instructions to bundles. See
483edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  /// MIBundleBuilder::insert() for a more reliable way of doing that.
484edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  instr_iterator insert(instr_iterator I, MachineInstr *M);
485deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve
486edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  /// Insert a range of instructions into the instruction list before I.
4877c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  template<typename IT>
4887c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  void insert(iterator I, IT S, IT E) {
489ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng    Insts.insert(I.getInstrIterator(), S, E);
4907c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  }
491edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen
492edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  /// Insert MI into the instruction list before I.
493edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  iterator insert(iterator I, MachineInstr *MI) {
494edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen    assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
495edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen           "Cannot insert instruction with bundle flags");
496edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen    return Insts.insert(I.getInstrIterator(), MI);
4977c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  }
498edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen
499edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  /// Insert MI into the instruction list after I.
500edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen  iterator insertAfter(iterator I, MachineInstr *MI) {
501edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen    assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
502edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen           "Cannot insert instruction with bundle flags");
503edc3503ca5a4ab9133dd825dce4abd46bc4a3e08Jakob Stoklund Olesen    return Insts.insertAfter(I.getInstrIterator(), MI);
5047c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  }
5057c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng
5069f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// Remove an instruction from the instruction list and delete it.
507ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  ///
5089f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// If the instruction is part of a bundle, the other instructions in the
5099f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// bundle will still be bundled after removing the single instruction.
5109f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  instr_iterator erase(instr_iterator I);
5119f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen
5129f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// Remove an instruction from the instruction list and delete it.
5139f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  ///
5149f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// If the instruction is part of a bundle, the other instructions in the
5159f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// bundle will still be bundled after removing the single instruction.
516ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  instr_iterator erase_instr(MachineInstr *I) {
5179f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen    return erase(instr_iterator(I));
5187c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  }
519ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng
5209f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// Remove a range of instructions from the instruction list and delete them.
5217c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  iterator erase(iterator I, iterator E) {
522ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng    return Insts.erase(I.getInstrIterator(), E.getInstrIterator());
523ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  }
5249f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen
5259f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// Remove an instruction or bundle from the instruction list and delete it.
5269f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  ///
5279f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// If I points to a bundle of instructions, they are all erased.
5289f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  iterator erase(iterator I) {
52936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines    return erase(I, std::next(I));
5309f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  }
5319f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen
5329f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// Remove an instruction from the instruction list and delete it.
5339f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  ///
5349f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// If I is the head of a bundle of instructions, the whole bundle will be
5359f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// erased.
536ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  iterator erase(MachineInstr *I) {
5379f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen    return erase(iterator(I));
5387c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  }
5397c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng
5409f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// Remove the unbundled instruction from the instruction list without
5419f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// deleting it.
5429f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  ///
5439f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// This function can not be used to remove bundled instructions, use
5449f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// remove_instr to remove individual instructions from a bundle.
5459f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  MachineInstr *remove(MachineInstr *I) {
5469f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen    assert(!I->isBundled() && "Cannot remove bundled instructions");
5479f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen    return Insts.remove(I);
5489f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  }
5499f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen
5509f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// Remove the possibly bundled instruction from the instruction list
5519f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// without deleting it.
5529f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  ///
5539f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// If the instruction is part of a bundle, the other instructions in the
5549f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  /// bundle will still be bundled after removing the single instruction.
5559f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen  MachineInstr *remove_instr(MachineInstr *I);
5569f4692d2953b47e9037ccfe5709a6e75de3911d4Jakob Stoklund Olesen
557ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  void clear() {
558ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng    Insts.clear();
559ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  }
560ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman
5619b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen  /// Take an instruction from MBB 'Other' at the position From, and insert it
5629b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen  /// into this MBB right before 'Where'.
5639b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen  ///
5649b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen  /// If From points to a bundle of instructions, the whole bundle is moved.
5659b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen  void splice(iterator Where, MachineBasicBlock *Other, iterator From) {
5669b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen    // The range splice() doesn't allow noop moves, but this one does.
5679b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen    if (Where != From)
56836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines      splice(Where, Other, From, std::next(From));
569c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman  }
570c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman
5719b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen  /// Take a block of instructions from MBB 'Other' in the range [From, To),
5729b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen  /// and insert them into this MBB right before 'Where'.
5739b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen  ///
5749b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen  /// The instruction at 'Where' must not be included in the range of
5759b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen  /// instructions to move.
5769b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen  void splice(iterator Where, MachineBasicBlock *Other,
5779b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen              iterator From, iterator To) {
5789b04104a5e9fb51b24b7aeb55912d319802049b2Jakob Stoklund Olesen    Insts.splice(Where.getInstrIterator(), Other->Insts,
579ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng                 From.getInstrIterator(), To.getInstrIterator());
580f24d879520a615a03f19ced3c7491f7b51934d1cChris Lattner  }
5818e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattner
5828e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman  /// removeFromParent - This method unlinks 'this' from the containing
5838e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman  /// function, and returns it, but does not delete it.
5848e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman  MachineBasicBlock *removeFromParent();
58557cae881e2b6c85a562d3fd2a7f10bf9d7921b40Jim Grosbach
5868e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman  /// eraseFromParent - This method unlinks 'this' from the containing
5878e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman  /// function and deletes it.
5888e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman  void eraseFromParent();
5898e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman
5900370fad74b48388412c52d1325512f2c218487faEvan Cheng  /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to
5910370fad74b48388412c52d1325512f2c218487faEvan Cheng  /// 'Old', change the code and CFG so that it branches to 'New' instead.
5920370fad74b48388412c52d1325512f2c218487faEvan Cheng  void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New);
5930370fad74b48388412c52d1325512f2c218487faEvan Cheng
5942bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng  /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in
5952bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng  /// the CFG to be inserted.  If we have proven that MBB can only branch to
5962bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng  /// DestA and DestB, remove any other MBB successors from the CFG. DestA and
5972bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng  /// DestB can be null. Besides DestA and DestB, retain other edges leading
5982bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng  /// to LandingPads (currently there can be only one; we don't check or require
5992bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng  /// that here). Note it is possible that DestA and/or DestB are LandingPads.
6002bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng  bool CorrectExtraCFGEdges(MachineBasicBlock *DestA,
6012bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng                            MachineBasicBlock *DestB,
6022bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng                            bool isCond);
6032bdb7d0cc88881857073b36f4a09ebe2f2008c24Evan Cheng
60473e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen  /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping
6053b1906f48d0b541e5be0bc1918c94a454e908bc0Dale Johannesen  /// any DBG_VALUE instructions.  Return UnknownLoc if there is none.
606ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng  DebugLoc findDebugLoc(instr_iterator MBBI);
6077c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  DebugLoc findDebugLoc(iterator MBBI) {
608ddfd1377d2e4154d44dc3ad217735adc15af2e3fEvan Cheng    return findDebugLoc(MBBI.getInstrIterator());
6097c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng  }
61073e884bb3e971b1e794ba2501df15138f73b8b1aDale Johannesen
611c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy  /// Possible outcome of a register liveness query to computeRegisterLiveness()
612c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy  enum LivenessQueryResult {
613c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy    LQR_Live,            ///< Register is known to be live.
614c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy    LQR_OverlappingLive, ///< Register itself is not live, but some overlapping
615c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy                         ///< register is.
616c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy    LQR_Dead,            ///< Register is known to be dead.
617c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy    LQR_Unknown          ///< Register liveness not decidable from local
618c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy                         ///< neighborhood.
619c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy  };
620c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy
621c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy  /// computeRegisterLiveness - Return whether (physical) register \c Reg
622c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy  /// has been <def>ined and not <kill>ed as of just before \c MI.
623cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines  ///
624c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy  /// Search is localised to a neighborhood of
625c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy  /// \c Neighborhood instructions before (searching for defs or kills) and
626c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy  /// Neighborhood instructions after (searching just for defs) MI.
627c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy  ///
628c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy  /// \c Reg must be a physical register.
629c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy  LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI,
630c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy                                              unsigned Reg, MachineInstr *MI,
631c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy                                              unsigned Neighborhood=10);
632c4f70d437df505e128e0debdf0c5f4ab5010e1b5James Molloy
633f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke  // Debugging methods.
634f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke  void dump() const;
635dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines  void print(raw_ostream &OS, SlotIndexes* = nullptr) const;
636f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke
63736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines  // Printing method used by LoopInfo.
638cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines  void printAsOperand(raw_ostream &OS, bool PrintType = true) const;
63936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines
640da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke  /// getNumber - MachineBasicBlocks are uniquely numbered at the function
641da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke  /// level, unless they're not in a MachineFunction yet, in which case this
642da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke  /// will return -1.
643da86bdc75c8d36cb7b1f4e785a3749d7c8f8e638Brian Gaeke  ///
644c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke  int getNumber() const { return Number; }
64520a6d8e63056cc2025e7143a5f7226e079e0bc80Chris Lattner  void setNumber(int N) { Number = N; }
646c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke
647f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner  /// getSymbol - Return the MCSymbol for this basic block.
648f71cb015c1386ff8adc9ef0aa03fc0f0fc4a6e3eChris Lattner  ///
6491b2eb0e8a6aaf034675b17be6d853cb1c666200fChris Lattner  MCSymbol *getSymbol() const;
6507cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak
6517cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak
6527cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszakprivate:
6537cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  /// getWeightIterator - Return weight iterator corresponding to the I
6547cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  /// successor iterator.
6557cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  weight_iterator getWeightIterator(succ_iterator I);
65625101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub Staszak  const_weight_iterator getWeightIterator(const_succ_iterator I) const;
6577cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak
6587cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  friend class MachineBranchProbabilityInfo;
6597cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak
6607cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  /// getSuccWeight - Return weight of the edge from this block to MBB. This
6617cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  /// method should NOT be called directly, but by using getEdgeWeight method
6627cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  /// from MachineBranchProbabilityInfo class.
663990ca5517fd6666d4049b6b8281d9df99da11637Jakob Stoklund Olesen  uint32_t getSuccWeight(const_succ_iterator Succ) const;
6647cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak
6657cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak
6667cc2b07437a1243c33324549a1904fefc5f1845eJakub Staszak  // Methods used to maintain doubly linked list of blocks...
667fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman  friend struct ilist_traits<MachineBasicBlock>;
6688560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke
6698560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke  // Machine-CFG mutators
6708560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke
6718560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke  /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock.
6728560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke  /// Don't do this unless you know what you're doing, because it doesn't
6738560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke  /// update pred's successors list. Use pred->addSuccessor instead.
6748560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke  ///
6753dfbb558b5e74554104710ed16807fe74ec220a3Chris Lattner  void addPredecessor(MachineBasicBlock *pred);
6768560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke
6778560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke  /// removePredecessor - Remove pred as a predecessor of this
6788560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke  /// MachineBasicBlock. Don't do this unless you know what you're
6798560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke  /// doing, because it doesn't update pred's successors list. Use
6808560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke  /// pred->removeSuccessor instead.
6818560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke  ///
6823dfbb558b5e74554104710ed16807fe74ec220a3Chris Lattner  void removePredecessor(MachineBasicBlock *pred);
683deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve};
684deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve
6851cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarraw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB);
6860aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner
68713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen// This is useful when building IndexedMaps keyed on basic block pointers.
68813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesenstruct MBB2NumberFunctor :
68913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen  public std::unary_function<const MachineBasicBlock*, unsigned> {
69013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen  unsigned operator()(const MachineBasicBlock *MBB) const {
69113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen    return MBB->getNumber();
69213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen  }
69313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen};
69413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen
6950aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner//===--------------------------------------------------------------------===//
6960aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// GraphTraits specializations for machine basic block graphs (machine-CFGs)
6970aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner//===--------------------------------------------------------------------===//
6980aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner
6990aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// Provide specializations of GraphTraits to be able to treat a
7000aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// MachineFunction as a graph of MachineBasicBlocks...
7010aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner//
7020aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner
7030aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<MachineBasicBlock *> {
7040aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner  typedef MachineBasicBlock NodeType;
7050aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner  typedef MachineBasicBlock::succ_iterator ChildIteratorType;
7060aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner
7070aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner  static