X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FMachineBasicBlock.h;h=1be1b742bf88fdb8c2418017969f7d5f02b1b910;hb=c651e4c51e11feb58e6c12fee8a8f85631269f2f;hp=df2a15a05f472dfbcb32f4d0fc7d52ea3554ac9b;hpb=3707241f315b63b2dc380e0a1be5522bfd58b8d5;p=oota-llvm.git diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index df2a15a05f4..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,15 +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 { +struct ilist_traits { +protected: // this is only set by the MachineBasicBlock owning the ilist friend class MachineBasicBlock; MachineBasicBlock* parent; @@ -43,7 +45,8 @@ public: static void setPrev(MachineInstr* N, MachineInstr* prev) { N->prev = prev; } static void setNext(MachineInstr* N, MachineInstr* next) { N->next = next; } - static MachineInstr* createNode(); + static MachineInstr* createSentinel(); + static void destroySentinel(MachineInstr *MI) { delete MI; } void addNodeToList(MachineInstr* N); void removeNodeFromList(MachineInstr* N); void transferNodesFromList( @@ -55,20 +58,36 @@ public: 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. /// @@ -76,7 +95,8 @@ public: /// getParent - Return the MachineFunction containing this basic block. /// - const MachineFunction *getParent() const; + const MachineFunction *getParent() const { return Parent; } + MachineFunction *getParent() { return Parent; } typedef ilist::iterator iterator; typedef ilist::const_iterator const_iterator; @@ -103,41 +123,81 @@ public: 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 (); } - 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 (); } + 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) { - assert (std::find (Successors.begin (), Successors.end (), succ) - == Successors.end () - && "Trying to addSuccessor a MBB which is already my successor"); - Successors.push_back (succ); - succ->addPredecessor (this); - } + void addSuccessor(MachineBasicBlock *succ); - /// removeSuccessor - Remove succ from the successors list of this + /// removeSuccessor - Remove successor from the successors list of this /// MachineBasicBlock. The Predecessors list of succ is automatically updated. /// - void removeSuccessor (MachineBasicBlock *succ) { - succ->removePredecessor (this); - std::vector::iterator goner = - std::find (Successors.begin(), Successors.end (), succ); - assert (goner != Successors.end () - && "Trying to removeSuccessor a MBB which isn't my successor"); - Successors.erase (goner); + 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 @@ -145,6 +205,8 @@ public: /// 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); } @@ -158,12 +220,27 @@ public: 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; } @@ -176,24 +253,83 @@ private: // Methods used to maintain doubly linked list of blocks... /// 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) { - assert(std::find (Predecessors.begin (), Predecessors.end (), pred) - == Predecessors.end () - && "Trying to addPredecessor a MBB which is already my predecessor"); - Predecessors.push_back (pred); - } + 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::vector::iterator goner = - std::find (Predecessors.begin(), Predecessors.end (), pred); - assert (goner != Predecessors.end () - && "Trying to removePredecessor a MBB which isn't my predecessor"); - Predecessors.erase (goner); + 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(); } };