X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FMachineBasicBlock.h;h=1be1b742bf88fdb8c2418017969f7d5f02b1b910;hb=c651e4c51e11feb58e6c12fee8a8f85631269f2f;hp=a95103f35fd8105352aca93c0a705396aee8a344;hpb=e8b5413e5d0c7c0fc5b384e975c4ca87f4c00699;p=oota-llvm.git diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index a95103f35fd..1be1b742bf8 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -1,46 +1,113 @@ -//===-- llvm/CodeGen/MachineCodeForBasicBlock.h -----------------*- C++ -*--=// -// +//===-- 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. // -//===---------------------------------------------------------------------===// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H +#define LLVM_CODEGEN_MACHINEBASICBLOCK_H -#ifndef LLVM_CODEGEN_MACHINECODEFORBASICBLOCK_H -#define LLVM_CODEGEN_MACHINECODEFORBASICBLOCK_H +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/ilist" +#include "llvm/Support/Streams.h" -#include "llvm/BasicBlock.h" -class MachineInstr; +namespace llvm { + class MachineFunction; -extern AnnotationID MCFBB_AID; +// ilist_traits +template <> +struct ilist_traits { +protected: + // this is only set by the MachineBasicBlock owning the ilist + friend class MachineBasicBlock; + MachineBasicBlock* parent; -class MachineCodeForBasicBlock : public Annotation { - std::vector Insts; public: - MachineCodeForBasicBlock(); - ~MachineCodeForBasicBlock() {} - - // Static methods to retrieve or destroy the MachineCodeForBasicBlock - // object for a given basic block. - static MachineCodeForBasicBlock& get(const BasicBlock *bb) { - return *(MachineCodeForBasicBlock*)bb->getOrCreateAnnotation(MCFBB_AID); - } + ilist_traits() : parent(0) { } + + static MachineInstr* getPrev(MachineInstr* N) { return N->prev; } + static MachineInstr* getNext(MachineInstr* N) { return N->next; } + + static const MachineInstr* + getPrev(const MachineInstr* N) { return N->prev; } + + static const MachineInstr* + getNext(const MachineInstr* N) { return N->next; } + + static void setPrev(MachineInstr* N, MachineInstr* prev) { N->prev = prev; } + static void setNext(MachineInstr* N, MachineInstr* next) { N->next = next; } + + 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 { + 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; - static void destroy(const BasicBlock *bb) { - bb->deleteAnnotation(MCFBB_AID); + /// IsLandingPad - Indicate that this basic block is entered via an + /// exception handler. + bool IsLandingPad; + +public: + explicit MachineBasicBlock(const BasicBlock *bb = 0) : Prev(0), Next(0), + BB(bb), Number(-1), + Parent(0), + IsLandingPad(false) { + Insts.parent = this; } - - typedef std::vector::iterator iterator; - typedef std::vector::const_iterator const_iterator; + + ~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; typedef std::reverse_iterator reverse_iterator; unsigned size() const { return Insts.size(); } bool empty() const { return Insts.empty(); } - MachineInstr * operator[](unsigned i) const { return Insts[i]; } - MachineInstr *&operator[](unsigned i) { return Insts[i]; } - - MachineInstr *front() const { return Insts.front(); } - MachineInstr *back() const { return Insts.back(); } + MachineInstr& front() { return Insts.front(); } + MachineInstr& back() { return Insts.back(); } iterator begin() { return Insts.begin(); } const_iterator begin() const { return Insts.begin(); } @@ -51,23 +118,221 @@ 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); } iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } // erase - Remove the specified element or range from the instruction list. - // These functions do not delete any instructions removed. + // These functions delete any instructions removed. // iterator erase(iterator I) { return Insts.erase(I); } iterator erase(iterator I, iterator E) { return Insts.erase(I, E); } + 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 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... +// - MachineInstr *pop_back() { - MachineInstr *R = back(); - Insts.pop_back(); - return R; +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 #endif