X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FMachineBasicBlock.h;h=1be1b742bf88fdb8c2418017969f7d5f02b1b910;hb=c651e4c51e11feb58e6c12fee8a8f85631269f2f;hp=2ab162437528c07001235ee2169f0776c312b2a7;hpb=f13a3f4dd1eaa89ca9a64a1e820b089facca3366;p=oota-llvm.git diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index 2ab16243752..1be1b742bf8 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -1,12 +1,12 @@ //===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// -// +// // The LLVM Compiler Infrastructure // // This file was developed by the LLVM research group and is distributed under // the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// //===----------------------------------------------------------------------===// -// +// // Collect the sequence of machine instructions for a basic block. // //===----------------------------------------------------------------------===// @@ -15,17 +15,17 @@ #define LLVM_CODEGEN_MACHINEBASICBLOCK_H #include "llvm/CodeGen/MachineInstr.h" -#include "Support/ilist" -#include +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/ilist" +#include "llvm/Support/Streams.h" namespace llvm { + class MachineFunction; // ilist_traits template <> -class ilist_traits -{ - typedef ilist_traits self; - +struct ilist_traits { +protected: // this is only set by the MachineBasicBlock owning the ilist friend class MachineBasicBlock; MachineBasicBlock* parent; @@ -45,46 +45,59 @@ public: static void setPrev(MachineInstr* N, MachineInstr* prev) { N->prev = prev; } static void setNext(MachineInstr* N, MachineInstr* next) { N->next = next; } - static MachineInstr* createNode() { return new MachineInstr(0, 0); } - - void addNodeToList(MachineInstr* N) { - assert(N->parent == 0 && "machine instruction already in a basic block"); - N->parent = parent; - } - - void removeNodeFromList(MachineInstr* N) { - assert(N->parent != 0 && "machine instruction not in a basic block"); - N->parent = 0; - } - - void transferNodesFromList(iplist& toList, - ilist_iterator first, - ilist_iterator last) { - if (parent != toList.parent) - for (; first != last; ++first) - first->parent = toList.parent; - } + static MachineInstr* createSentinel(); + static void destroySentinel(MachineInstr *MI) { delete MI; } + void addNodeToList(MachineInstr* N); + void removeNodeFromList(MachineInstr* N); + void transferNodesFromList( + iplist >& toList, + ilist_iterator first, + ilist_iterator last); }; class BasicBlock; class MachineBasicBlock { -public: typedef ilist Instructions; Instructions Insts; MachineBasicBlock *Prev, *Next; const BasicBlock *BB; + int Number; + MachineFunction *Parent; + + /// Predecessors/Successors - Keep track of the predecessor / successor + /// basicblocks. + std::vector Predecessors; + std::vector Successors; + + /// LiveIns - Keep track of the physical registers that are livein of + /// the basicblock. + std::vector LiveIns; + + /// IsLandingPad - Indicate that this basic block is entered via an + /// exception handler. + bool IsLandingPad; + public: - MachineBasicBlock(const BasicBlock *bb = 0) : Prev(0), Next(0), BB(bb) { + explicit MachineBasicBlock(const BasicBlock *bb = 0) : Prev(0), Next(0), + BB(bb), Number(-1), + Parent(0), + IsLandingPad(false) { Insts.parent = this; } - ~MachineBasicBlock() {} - + + ~MachineBasicBlock(); + /// getBasicBlock - Return the LLVM basic block that this instance /// corresponded to originally. /// const BasicBlock *getBasicBlock() const { return BB; } - + + /// getParent - Return the MachineFunction containing this basic block. + /// + const MachineFunction *getParent() const { return Parent; } + MachineFunction *getParent() { return Parent; } + typedef ilist::iterator iterator; typedef ilist::const_iterator const_iterator; typedef std::reverse_iterator const_reverse_iterator; @@ -93,17 +106,6 @@ public: unsigned size() const { return Insts.size(); } bool empty() const { return Insts.empty(); } - const MachineInstr& operator[](unsigned i) const { - const_iterator it = Insts.begin(); - std::advance(it, i); - return *it; - } - MachineInstr& operator[](unsigned i) { - iterator it = Insts.begin(); - std::advance(it, i); - return *it; - } - MachineInstr& front() { return Insts.front(); } MachineInstr& back() { return Insts.back(); } @@ -116,6 +118,95 @@ public: reverse_iterator rend () { return Insts.rend(); } const_reverse_iterator rend () const { return Insts.rend(); } + // Machine-CFG iterators + typedef std::vector::iterator pred_iterator; + typedef std::vector::const_iterator const_pred_iterator; + typedef std::vector::iterator succ_iterator; + typedef std::vector::const_iterator const_succ_iterator; + + pred_iterator pred_begin() { return Predecessors.begin(); } + const_pred_iterator pred_begin() const { return Predecessors.begin(); } + pred_iterator pred_end() { return Predecessors.end(); } + const_pred_iterator pred_end() const { return Predecessors.end(); } + unsigned pred_size() const { return Predecessors.size(); } + bool pred_empty() const { return Predecessors.empty(); } + succ_iterator succ_begin() { return Successors.begin(); } + const_succ_iterator succ_begin() const { return Successors.begin(); } + succ_iterator succ_end() { return Successors.end(); } + const_succ_iterator succ_end() const { return Successors.end(); } + unsigned succ_size() const { return Successors.size(); } + bool succ_empty() const { return Successors.empty(); } + + // LiveIn management methods. + + /// addLiveIn - Add the specified register as a live in. Note that it + /// is an error to add the same register to the same set more than once. + void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } + + /// removeLiveIn - Remove the specified register from the live in set. + /// + void removeLiveIn(unsigned Reg); + + // Iteration support for live in sets. These sets are kept in sorted + // order by their register number. + typedef std::vector::iterator livein_iterator; + typedef std::vector::const_iterator const_livein_iterator; + livein_iterator livein_begin() { return LiveIns.begin(); } + const_livein_iterator livein_begin() const { return LiveIns.begin(); } + livein_iterator livein_end() { return LiveIns.end(); } + const_livein_iterator livein_end() const { return LiveIns.end(); } + bool livein_empty() const { return LiveIns.empty(); } + + /// isLandingPad - Returns true if the block is a landing pad. That is + /// this basic block is entered via an exception handler. + bool isLandingPad() const { return IsLandingPad; } + + /// setIsLandingPad - Indicates the block is a landing pad. That is + /// this basic block is entered via an exception handler. + void setIsLandingPad() { IsLandingPad = true; } + + // Code Layout methods. + + /// moveBefore/moveAfter - move 'this' block before or after the specified + /// block. This only moves the block, it does not modify the CFG or adjust + /// potential fall-throughs at the end of the block. + void moveBefore(MachineBasicBlock *NewAfter); + void moveAfter(MachineBasicBlock *NewBefore); + + // Machine-CFG mutators + + /// addSuccessor - Add succ as a successor of this MachineBasicBlock. + /// The Predecessors list of succ is automatically updated. + /// + void addSuccessor(MachineBasicBlock *succ); + + /// removeSuccessor - Remove successor from the successors list of this + /// MachineBasicBlock. The Predecessors list of succ is automatically updated. + /// + void removeSuccessor(MachineBasicBlock *succ); + + /// removeSuccessor - Remove specified successor from the successors list of + /// this MachineBasicBlock. The Predecessors list of succ is automatically + /// updated. + /// + void removeSuccessor(succ_iterator I); + + /// isSuccessor - Return true if the specified MBB is a successor of this + /// block. + bool isSuccessor(MachineBasicBlock *MBB) const { + for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I) + if (*I == MBB) + return true; + return false; + } + + /// getFirstTerminator - returns an iterator to the first terminator + /// instruction of this basic block. If a terminator does not exist, + /// it returns end() + iterator getFirstTerminator(); + + void pop_front() { Insts.pop_front(); } + void pop_back() { Insts.pop_back(); } void push_back(MachineInstr *MI) { Insts.push_back(MI); } template void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } @@ -126,19 +217,120 @@ public: // iterator erase(iterator I) { return Insts.erase(I); } iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } - MachineInstr* remove(iterator &I) { return Insts.remove(I); } + MachineInstr *remove(MachineInstr *I) { return Insts.remove(I); } + void clear() { Insts.clear(); } + + /// splice - Take a block of instructions from MBB 'Other' in the range [From, + /// To), and insert them into this MBB right before 'where'. + void splice(iterator where, MachineBasicBlock *Other, iterator From, + iterator To) { + Insts.splice(where, Other->Insts, From, To); + } // Debugging methods. void dump() const; void print(std::ostream &OS) const; + void print(std::ostream *OS) const { if (OS) print(*OS); } + + /// getNumber - MachineBasicBlocks are uniquely numbered at the function + /// level, unless they're not in a MachineFunction yet, in which case this + /// will return -1. + /// + int getNumber() const { return Number; } + void setNumber(int N) { Number = N; } private: // Methods used to maintain doubly linked list of blocks... - friend class ilist_traits; + friend struct ilist_traits; MachineBasicBlock *getPrev() const { return Prev; } MachineBasicBlock *getNext() const { return Next; } void setPrev(MachineBasicBlock *P) { Prev = P; } void setNext(MachineBasicBlock *N) { Next = N; } + + // Machine-CFG mutators + + /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. + /// Don't do this unless you know what you're doing, because it doesn't + /// update pred's successors list. Use pred->addSuccessor instead. + /// + void addPredecessor(MachineBasicBlock *pred); + + /// removePredecessor - Remove pred as a predecessor of this + /// MachineBasicBlock. Don't do this unless you know what you're + /// doing, because it doesn't update pred's successors list. Use + /// pred->removeSuccessor instead. + /// + void removePredecessor(MachineBasicBlock *pred); +}; + +std::ostream& operator<<(std::ostream &OS, const MachineBasicBlock &MBB); + +//===--------------------------------------------------------------------===// +// GraphTraits specializations for machine basic block graphs (machine-CFGs) +//===--------------------------------------------------------------------===// + +// Provide specializations of GraphTraits to be able to treat a +// MachineFunction as a graph of MachineBasicBlocks... +// + +template <> struct GraphTraits { + typedef MachineBasicBlock NodeType; + typedef MachineBasicBlock::succ_iterator ChildIteratorType; + + static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->succ_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->succ_end(); + } +}; + +template <> struct GraphTraits { + typedef const MachineBasicBlock NodeType; + typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; + + static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->succ_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->succ_end(); + } +}; + +// Provide specializations of GraphTraits to be able to treat a +// MachineFunction as a graph of MachineBasicBlocks... and to walk it +// in inverse order. Inverse order for a function is considered +// to be when traversing the predecessor edges of a MBB +// instead of the successor edges. +// +template <> struct GraphTraits > { + typedef MachineBasicBlock NodeType; + typedef MachineBasicBlock::pred_iterator ChildIteratorType; + static NodeType *getEntryNode(Inverse G) { + return G.Graph; + } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->pred_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->pred_end(); + } +}; + +template <> struct GraphTraits > { + typedef const MachineBasicBlock NodeType; + typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; + static NodeType *getEntryNode(Inverse G) { + return G.Graph; + } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->pred_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->pred_end(); + } }; } // End llvm namespace