MachineBasicBlock.h revision c07d8d8a26f63dfc54dbd0e1ff776763ec6443ad
151a8d8528135ba4e3e4cf7cd711a9e47b19078a3Chris Lattner//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 2deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 56fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// This file was developed by the LLVM research group and is distributed under 66fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 76fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 96fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 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" 180aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner#include "Support/GraphTraits.h" 1994dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos#include "Support/ilist" 20f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke#include <iosfwd> 21d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 22d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 235e61fa95196b85281eec655787e9c73267532bd1Chris Lattner class MachineFunction; 24d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2594dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos// ilist_traits 2694dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenostemplate <> 275e61fa95196b85281eec655787e9c73267532bd1Chris Lattnerclass ilist_traits<MachineInstr> { 2894dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos // this is only set by the MachineBasicBlock owning the ilist 2994dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos friend class MachineBasicBlock; 3094dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos MachineBasicBlock* parent; 3194dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 3294dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenospublic: 3394dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos ilist_traits<MachineInstr>() : parent(0) { } 3494dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 3594dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos static MachineInstr* getPrev(MachineInstr* N) { return N->prev; } 3694dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos static MachineInstr* getNext(MachineInstr* N) { return N->next; } 3794dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 3894dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos static const MachineInstr* 3994dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos getPrev(const MachineInstr* N) { return N->prev; } 4094dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 4194dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos static const MachineInstr* 4294dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos getNext(const MachineInstr* N) { return N->next; } 4394dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 4494dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos static void setPrev(MachineInstr* N, MachineInstr* prev) { N->prev = prev; } 4594dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos static void setNext(MachineInstr* N, MachineInstr* next) { N->next = next; } 4694dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 47aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos static MachineInstr* createNode(); 48aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos void addNodeToList(MachineInstr* N); 49aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos void removeNodeFromList(MachineInstr* N); 50aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos void transferNodesFromList( 51aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos iplist<MachineInstr, ilist_traits<MachineInstr> >& toList, 52aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos ilist_iterator<MachineInstr> first, 53aad5c0505183a5b7913f1a443a1f0650122551ccAlkis Evlogimenos ilist_iterator<MachineInstr> last); 5494dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos}; 5594dc07728f091c652f0a8059aba6dce5018485eeAlkis Evlogimenos 56aec11f1decda111112c39803cb89dace81cd0568Chris Lattnerclass BasicBlock; 57deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 58d0aa0cdbc6fee00f2b2019633a9b9d00d301ac68Chris Lattnerclass MachineBasicBlock { 59c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenospublic: 60c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos typedef ilist<MachineInstr> Instructions; 61c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos Instructions Insts; 628e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattner MachineBasicBlock *Prev, *Next; 631194e9501984daf0d3237ed1bf18a156173e7fd4Chris Lattner const BasicBlock *BB; 6476456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke std::vector<MachineBasicBlock *> Predecessors; 6576456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke std::vector<MachineBasicBlock *> Successors; 66c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke int Number; 6776456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 68deb9654056939a12981446f6ed1139dca3412746Vikram S. Advepublic: 69c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke MachineBasicBlock(const BasicBlock *bb = 0) : Prev(0), Next(0), BB(bb), 70c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke Number(-1) { 71ab8672c8bb83e722b856eac67863542ea7e0cbb2Alkis Evlogimenos Insts.parent = this; 72ab8672c8bb83e722b856eac67863542ea7e0cbb2Alkis Evlogimenos } 73fce1143bcfa73f61845002fa50473d1a01384202Misha Brukman ~MachineBasicBlock() {} 74deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 75d0aa0cdbc6fee00f2b2019633a9b9d00d301ac68Chris Lattner /// getBasicBlock - Return the LLVM basic block that this instance 76d0aa0cdbc6fee00f2b2019633a9b9d00d301ac68Chris Lattner /// corresponded to originally. 77d0aa0cdbc6fee00f2b2019633a9b9d00d301ac68Chris Lattner /// 781194e9501984daf0d3237ed1bf18a156173e7fd4Chris Lattner const BasicBlock *getBasicBlock() const { return BB; } 795e61fa95196b85281eec655787e9c73267532bd1Chris Lattner 805e61fa95196b85281eec655787e9c73267532bd1Chris Lattner /// getParent - Return the MachineFunction containing this basic block. 815e61fa95196b85281eec655787e9c73267532bd1Chris Lattner /// 825e61fa95196b85281eec655787e9c73267532bd1Chris Lattner const MachineFunction *getParent() const; 83c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke MachineFunction *getParent(); 845e61fa95196b85281eec655787e9c73267532bd1Chris Lattner 85c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos typedef ilist<MachineInstr>::iterator iterator; 86c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos typedef ilist<MachineInstr>::const_iterator const_iterator; 87deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 88deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve typedef std::reverse_iterator<iterator> reverse_iterator; 89deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 90deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve unsigned size() const { return Insts.size(); } 91deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve bool empty() const { return Insts.empty(); } 92deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 93c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineInstr& front() { return Insts.front(); } 94c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineInstr& back() { return Insts.back(); } 95deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 96deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve iterator begin() { return Insts.begin(); } 97deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve const_iterator begin() const { return Insts.begin(); } 98deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve iterator end() { return Insts.end(); } 99deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve const_iterator end() const { return Insts.end(); } 100deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve reverse_iterator rbegin() { return Insts.rbegin(); } 101deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve const_reverse_iterator rbegin() const { return Insts.rbegin(); } 102deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve reverse_iterator rend () { return Insts.rend(); } 103deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve const_reverse_iterator rend () const { return Insts.rend(); } 104deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 10576456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke // Machine-CFG iterators 10676456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 10776456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 10876456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 10976456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 11076456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 11176456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke pred_iterator pred_begin() { return Predecessors.begin (); } 11276456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke const_pred_iterator pred_begin() const { return Predecessors.begin (); } 11376456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke pred_iterator pred_end() { return Predecessors.end (); } 11476456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke const_pred_iterator pred_end() const { return Predecessors.end (); } 1153707241f315b63b2dc380e0a1be5522bfd58b8d5Brian Gaeke unsigned pred_size() const { return Predecessors.size (); } 11676456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke succ_iterator succ_begin() { return Successors.begin (); } 11776456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke const_succ_iterator succ_begin() const { return Successors.begin (); } 11876456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke succ_iterator succ_end() { return Successors.end (); } 11976456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke const_succ_iterator succ_end() const { return Successors.end (); } 1203707241f315b63b2dc380e0a1be5522bfd58b8d5Brian Gaeke unsigned succ_size() const { return Successors.size (); } 12176456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 12276456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke // Machine-CFG mutators 12376456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 12476456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 12576456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// The Predecessors list of succ is automatically updated. 12676456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// 12776456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke void addSuccessor (MachineBasicBlock *succ) { 12861d3d5c06b279cce1f2b68af4de82f635910578aBrian Gaeke Successors.push_back (succ); 12976456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke succ->addPredecessor (this); 13076456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke } 13176456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 13276456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// removeSuccessor - Remove succ from the successors list of this 13376456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 13476456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke /// 13576456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke void removeSuccessor (MachineBasicBlock *succ) { 13676456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke succ->removePredecessor (this); 13776456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke std::vector<MachineBasicBlock *>::iterator goner = 13876456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke std::find (Successors.begin(), Successors.end (), succ); 13976456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke Successors.erase (goner); 14076456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke } 14176456bc40c79fcae4da52d34f96c079d9759257cBrian Gaeke 142743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos /// getFirstTerminator - returns an iterator to the first terminator 143743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos /// instruction of this basic block. If a terminator does not exist, 144743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos /// it returns end() 145743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos iterator getFirstTerminator(); 146743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos 147deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve void push_back(MachineInstr *MI) { Insts.push_back(MI); } 148deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve template<typename IT> 149deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } 150deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } 151deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 15246d6a1aeb549a2e4ccd982a1a2cefda541d79c52Vikram S. Adve // erase - Remove the specified element or range from the instruction list. 153c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos // These functions delete any instructions removed. 154deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve // 15546d6a1aeb549a2e4ccd982a1a2cefda541d79c52Vikram S. Adve iterator erase(iterator I) { return Insts.erase(I); } 156deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } 15783706a5a3a6f19451765b743c5a72b62f74eb71aChris Lattner MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } 158da44b151259525abc9c299f89b9532f3a9883b4eBrian Gaeke void clear() { Insts.clear(); } 1598e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattner 160f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke // Debugging methods. 161f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke void dump() const; 162f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke void print(std::ostream &OS) const; 163f13a3f4dd1eaa89ca9a64a1e820b089facca3366Brian Gaeke 164c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke // MachineBasicBlocks are uniquely numbered at the function level 165c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke // (unless they're not in a MachineFunction yet) 166c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke int getNumber() const { return Number; } 167c07d8d8a26f63dfc54dbd0e1ff776763ec6443adBrian Gaeke 1688e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattnerprivate: // Methods used to maintain doubly linked list of blocks... 1698e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattner friend class ilist_traits<MachineBasicBlock>; 1708e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattner 1718e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattner MachineBasicBlock *getPrev() const { return Prev; } 1728e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattner MachineBasicBlock *getNext() const { return Next; } 1738e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattner void setPrev(MachineBasicBlock *P) { Prev = P; } 1748e7ae9860bd1f29c95e4e10fe151a22aaafafef9Chris Lattner void setNext(MachineBasicBlock *N) { Next = N; } 1758560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke 1768560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke // Machine-CFG mutators 1778560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke 1788560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 1798560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// Don't do this unless you know what you're doing, because it doesn't 1808560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// update pred's successors list. Use pred->addSuccessor instead. 1818560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// 1828560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke void addPredecessor (MachineBasicBlock *pred) { 1838560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke Predecessors.push_back (pred); 1848560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke } 1858560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke 1868560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// removePredecessor - Remove pred as a predecessor of this 1878560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// MachineBasicBlock. Don't do this unless you know what you're 1888560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// doing, because it doesn't update pred's successors list. Use 1898560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// pred->removeSuccessor instead. 1908560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke /// 1918560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke void removePredecessor (MachineBasicBlock *pred) { 1928560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke std::vector<MachineBasicBlock *>::iterator goner = 1938560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke std::find (Predecessors.begin(), Predecessors.end (), pred); 1948560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke Predecessors.erase (goner); 1958560af4f5fe589cf792bd44617c2308c4f087ba8Brian Gaeke } 196deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve}; 197deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 1980aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 1990aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner//===--------------------------------------------------------------------===// 2000aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// GraphTraits specializations for machine basic block graphs (machine-CFGs) 2010aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner//===--------------------------------------------------------------------===// 2020aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 2030aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// Provide specializations of GraphTraits to be able to treat a 2040aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// MachineFunction as a graph of MachineBasicBlocks... 2050aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// 2060aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 2070aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<MachineBasicBlock *> { 2080aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock NodeType; 2090aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::succ_iterator ChildIteratorType; 2100aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 2110aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 2120aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static inline ChildIteratorType child_begin(NodeType *N) { 2130aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_begin(); 2140aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 2150aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static inline ChildIteratorType child_end(NodeType *N) { 2160aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_end(); 2170aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 2180aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 2190aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 2200aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<const MachineBasicBlock *> { 2210aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef const MachineBasicBlock NodeType; 2220aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 2230aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 2240aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 2250aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static inline ChildIteratorType child_begin(NodeType *N) { 2260aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_begin(); 2270aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 2280aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static inline ChildIteratorType child_end(NodeType *N) { 2290aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->succ_end(); 2300aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 2310aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 2320aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 2330aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// Provide specializations of GraphTraits to be able to treat a 2340aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// MachineFunction as a graph of MachineBasicBlocks... and to walk it 2350aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// in inverse order. Inverse order for a function is considered 2360aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// to be when traversing the predecessor edges of a MBB 2370aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// instead of the successor edges. 2380aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner// 2390aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 2400aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock NodeType; 2410aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::pred_iterator ChildIteratorType; 2420aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 2430aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return G.Graph; 2440aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 2450aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static inline ChildIteratorType child_begin(NodeType *N) { 2460aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_begin(); 2470aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 2480aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static inline ChildIteratorType child_end(NodeType *N) { 2490aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_end(); 2500aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 2510aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 2520aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 2530aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattnertemplate <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 2540aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef const MachineBasicBlock NodeType; 2550aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 2560aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 2570aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return G.Graph; 2580aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 2590aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static inline ChildIteratorType child_begin(NodeType *N) { 2600aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_begin(); 2610aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 2620aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner static inline ChildIteratorType child_end(NodeType *N) { 2630aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner return N->pred_end(); 2640aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner } 2650aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner}; 2660aef12a7a96968a80c38144dfc0a7ae6a9152db9Chris Lattner 267d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 268deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve 269deb9654056939a12981446f6ed1139dca3412746Vikram S. Adve#endif 270