X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FInstrSched%2FSchedGraph.h;h=53ded6377d031c7fdc4b3b529cfa573f3ffe5ed2;hb=551ccae044b0ff658fe629dd67edd5ffe75d10e8;hp=11edf0d879149a6e76d828652cf746d475b7835c;hpb=9efc4d6aaaa0153c94a661c44198d514d4f83282;p=oota-llvm.git diff --git a/lib/CodeGen/InstrSched/SchedGraph.h b/lib/CodeGen/InstrSched/SchedGraph.h index 11edf0d8791..53ded6377d0 100644 --- a/lib/CodeGen/InstrSched/SchedGraph.h +++ b/lib/CodeGen/InstrSched/SchedGraph.h @@ -1,284 +1,104 @@ -//===-- SchedGraph.h - Scheduling Graph --------------------------*- C++ -*--=// +//===-- SchedGraph.h - Scheduling Graph -------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure // -// Purpose: -// Scheduling graph based on SSA graph plus extra dependence edges -// capturing dependences due to machine resources (machine registers, -// CC registers, and any others). +// 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. // -// Strategy: -// This graph tries to leverage the SSA graph as much as possible, -// but captures the extra dependences through a common interface. +//===----------------------------------------------------------------------===// +// +// This is a scheduling graph based on SSA graph plus extra dependence edges +// capturing dependences due to machine resources (machine registers, CC +// registers, and any others). +// +// This graph tries to leverage the SSA graph as much as possible, but captures +// the extra dependences through a common interface. // //===----------------------------------------------------------------------===// #ifndef LLVM_CODEGEN_SCHEDGRAPH_H #define LLVM_CODEGEN_SCHEDGRAPH_H +#include "llvm/CodeGen/SchedGraphCommon.h" #include "llvm/CodeGen/MachineInstr.h" -#include "Support/HashExtras.h" -#include "Support/GraphTraits.h" - -class Value; -class Instruction; -class TerminatorInst; -class BasicBlock; -class Function; -class TargetMachine; -class SchedGraphEdge; -class SchedGraphNode; -class SchedGraph; +#include "llvm/Transforms/Scalar.h" +#include "llvm/ADT/hash_map" +#include "llvm/ADT/GraphTraits.h" + +namespace llvm { + class RegToRefVecMap; class ValueToDefVecMap; class RefVec; -class MachineInstr; -class MachineBasicBlock; +class SchedGraphNode : public SchedGraphNodeCommon { -/******************** Exported Data Types and Constants ********************/ + MachineBasicBlock *MBB; + const MachineInstr *MI; -typedef int ResourceId; -const ResourceId InvalidRID = -1; -const ResourceId MachineCCRegsRID = -2; // use +ve numbers for actual regs -const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs -const ResourceId MachineFPRegsRID = -4; // use +ve numbers for actual regs + SchedGraphNode(unsigned nodeId, MachineBasicBlock *mbb, int indexInBB, + const TargetMachine& Target); + ~SchedGraphNode(); -//*********************** Public Class Declarations ************************/ + friend class SchedGraph; // give access for ctor and dtor + friend class SchedGraphEdge; // give access for adding edges -class SchedGraphEdge { - SchedGraphEdge(const SchedGraphEdge &); // DO NOT IMPLEMENT - void operator=(const SchedGraphEdge &); // DO NOT IMPLEMENT public: - enum SchedGraphEdgeDepType { - CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource - }; - enum DataDepOrderType { - TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8 - }; - -private: - SchedGraphNode* src; - SchedGraphNode* sink; - SchedGraphEdgeDepType depType; - unsigned int depOrderType; - int minDelay; // cached latency (assumes fixed target arch) - - union { - const Value* val; - int machineRegNum; - ResourceId resourceId; - }; - -public: - // For all constructors, if minDelay is unspecified, minDelay is - // set to _src->getLatency(). - // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument - /*ctor*/ SchedGraphEdge(SchedGraphNode* _src, - SchedGraphNode* _sink, - SchedGraphEdgeDepType _depType, - unsigned int _depOrderType, - int _minDelay = -1); - - // constructor for explicit value dependence (may be true/anti/output) - /*ctor*/ SchedGraphEdge(SchedGraphNode* _src, - SchedGraphNode* _sink, - const Value* _val, - unsigned int _depOrderType, - int _minDelay = -1); - - // constructor for machine register dependence - /*ctor*/ SchedGraphEdge(SchedGraphNode* _src, - SchedGraphNode* _sink, - unsigned int _regNum, - unsigned int _depOrderType, - int _minDelay = -1); - - // constructor for any other machine resource dependences. - // DataDepOrderType is always NonDataDep. It it not an argument to - // avoid overloading ambiguity with previous constructor. - /*ctor*/ SchedGraphEdge(SchedGraphNode* _src, - SchedGraphNode* _sink, - ResourceId _resourceId, - int _minDelay = -1); - - /*dtor*/ ~SchedGraphEdge(); - - SchedGraphNode* getSrc () const { return src; } - SchedGraphNode* getSink () const { return sink; } - int getMinDelay () const { return minDelay; } - SchedGraphEdgeDepType getDepType () const { return depType; } - - const Value* getValue () const { - assert(depType == ValueDep); return val; - } - int getMachineReg () const { - assert(depType == MachineRegister); return machineRegNum; - } - int getResourceId () const { - assert(depType == MachineResource); return resourceId; - } - -public: - // - // Debugging support - // - friend std::ostream& operator<<(std::ostream& os, const SchedGraphEdge& edge); - - void dump (int indent=0) const; - -private: - // disable default ctor - /*ctor*/ SchedGraphEdge(); // DO NOT IMPLEMENT -}; - - -class SchedGraphNode { - unsigned nodeId; - MachineBasicBlock *MBB; - const MachineInstr* minstr; - std::vector inEdges; - std::vector outEdges; - int origIndexInBB; // original position of machine instr in BB - int latency; - - SchedGraphNode(const SchedGraphNode &); // DO NOT IMPLEMENT - void operator=(const SchedGraphNode &); // DO NOT IMPLEMENT -public: - typedef std::vector:: iterator iterator; - typedef std::vector::const_iterator const_iterator; - typedef std::vector:: reverse_iterator reverse_iterator; - typedef std::vector::const_reverse_iterator const_reverse_iterator; - -public: - // // Accessor methods - // - unsigned getNodeId () const { return nodeId; } - const MachineInstr* getMachineInstr () const { return minstr; } - const MachineOpCode getOpCode () const { return minstr->getOpCode(); } - int getLatency () const { return latency; } - unsigned getNumInEdges () const { return inEdges.size(); } - unsigned getNumOutEdges () const { return outEdges.size(); } - bool isDummyNode () const { return (minstr == NULL); } - MachineBasicBlock &getMachineBasicBlock() const { return *MBB; } - int getOrigIndexInBB() const { return origIndexInBB; } - - // - // Iterators - // - iterator beginInEdges () { return inEdges.begin(); } - iterator endInEdges () { return inEdges.end(); } - iterator beginOutEdges () { return outEdges.begin(); } - iterator endOutEdges () { return outEdges.end(); } - - const_iterator beginInEdges () const { return inEdges.begin(); } - const_iterator endInEdges () const { return inEdges.end(); } - const_iterator beginOutEdges () const { return outEdges.begin(); } - const_iterator endOutEdges () const { return outEdges.end(); } - -public: - // - // Debugging support - // - friend std::ostream& operator<<(std::ostream& os, const SchedGraphNode& node); - - void dump (int indent=0) const; - -private: - friend class SchedGraph; // give access for ctor and dtor - friend class SchedGraphEdge; // give access for adding edges - - void addInEdge (SchedGraphEdge* edge); - void addOutEdge (SchedGraphEdge* edge); - - void removeInEdge (const SchedGraphEdge* edge); - void removeOutEdge (const SchedGraphEdge* edge); - - // disable default constructor and provide a ctor for single-block graphs - /*ctor*/ SchedGraphNode(); // DO NOT IMPLEMENT - /*ctor*/ SchedGraphNode (unsigned nodeId, - MachineBasicBlock *mbb, - int indexInBB, - const TargetMachine& Target); - /*dtor*/ ~SchedGraphNode (); -}; - + const MachineInstr* getMachineInstr() const { return MI; } + const MachineOpCode getOpcode() const { return MI->getOpcode(); } + bool isDummyNode() const { return (MI == NULL); } + MachineBasicBlock &getMachineBasicBlock() const { return *MBB; } + void print(std::ostream &os) const; +}; -class SchedGraph : private hash_map { - MachineBasicBlock &MBB; // basic blocks for this graph - SchedGraphNode* graphRoot; // the root and leaf are not inserted - SchedGraphNode* graphLeaf; // in the hash_map (see getNumNodes()) - - typedef hash_map map_base; - SchedGraph(const SchedGraph &); // DO NOT IMPLEMENT - void operator=(const SchedGraph &); // DO NOT IMPLEMENT -public: - using map_base::iterator; - using map_base::const_iterator; +class SchedGraph : public SchedGraphCommon { + MachineBasicBlock &MBB; + hash_map GraphMap; public: - // - // Accessor methods - // - MachineBasicBlock &getBasicBlock() const { return MBB; } - unsigned getNumNodes() const { return size()+2; } - SchedGraphNode* getRoot() const { return graphRoot; } - SchedGraphNode* getLeaf() const { return graphLeaf; } - - SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const { - const_iterator onePair = this->find(minstr); - return (onePair != this->end())? (*onePair).second : NULL; + typedef hash_map::const_iterator iterator; + typedef hash_map::const_iterator const_iterator; + + MachineBasicBlock& getBasicBlock() const{return MBB;} + const unsigned int getNumNodes() const { return GraphMap.size()+2; } + SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const { + const_iterator onePair = find(MI); + return (onePair != end())? onePair->second : NULL; } - // - // Delete nodes or edges from the graph. - // - void eraseNode (SchedGraphNode* node); - - void eraseIncomingEdges (SchedGraphNode* node, - bool addDummyEdges = true); - - void eraseOutgoingEdges (SchedGraphNode* node, - bool addDummyEdges = true); - - void eraseIncidentEdges (SchedGraphNode* node, - bool addDummyEdges = true); + // Debugging support + void dump() const; - // - // Unordered iterators. - // Return values is pair. - // - using map_base::begin; - using map_base::end; +protected: + SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM); + ~SchedGraph(); - // - // Ordered iterators. + // Unordered iterators. // Return values is pair. // - // void postord_init(); - // postorder_iterator postord_begin(); - // postorder_iterator postord_end(); - // const_postorder_iterator postord_begin() const; - // const_postorder_iterator postord_end() const; + hash_map::const_iterator begin() const { + return GraphMap.begin(); + } + hash_map::const_iterator end() const { + return GraphMap.end(); + } + + unsigned size() { return GraphMap.size(); } + iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); } - // - // Debugging support - // - void dump () const; + SchedGraphNode *&operator[](const MachineInstr *MI) { + return GraphMap[MI]; + } private: friend class SchedGraphSet; // give access to ctor - - // disable default constructor and provide a ctor for single-block graphs - /*ctor*/ SchedGraph (MachineBasicBlock &bb, - const TargetMachine& target); - /*dtor*/ ~SchedGraph (); - + inline void noteGraphNodeForInstr (const MachineInstr* minstr, - SchedGraphNode* node) - { + SchedGraphNode* node) { assert((*this)[minstr] == NULL); (*this)[minstr] = node; } @@ -286,144 +106,80 @@ private: // // Graph builder // - void buildGraph (const TargetMachine& target); + void buildGraph(const TargetMachine& target); - void buildNodesForBB (const TargetMachine& target, - MachineBasicBlock &MBB, - std::vector& memNV, - std::vector& callNV, - RegToRefVecMap& regToRefVecMap, - ValueToDefVecMap& valueToDefVecMap); + void buildNodesForBB(const TargetMachine& target,MachineBasicBlock &MBB, + std::vector& memNV, + std::vector& callNV, + RegToRefVecMap& regToRefVecMap, + ValueToDefVecMap& valueToDefVecMap); + - void findDefUseInfoAtInstr (const TargetMachine& target, - SchedGraphNode* node, - std::vector& memNV, - std::vector& callNV, - RegToRefVecMap& regToRefVecMap, - ValueToDefVecMap& valueToDefVecMap); + void findDefUseInfoAtInstr(const TargetMachine& target, SchedGraphNode* node, + std::vector& memNV, + std::vector& callNV, + RegToRefVecMap& regToRefVecMap, + ValueToDefVecMap& valueToDefVecMap); - void addEdgesForInstruction(const MachineInstr& minstr, - const ValueToDefVecMap& valueToDefVecMap, - const TargetMachine& target); + void addEdgesForInstruction(const MachineInstr& minstr, + const ValueToDefVecMap& valueToDefVecMap, + const TargetMachine& target); - void addCDEdges (const TerminatorInst* term, - const TargetMachine& target); + void addCDEdges(const TerminatorInst* term, const TargetMachine& target); - void addMemEdges (const std::vector& memNV, - const TargetMachine& target); + void addMemEdges(const std::vector& memNod, + const TargetMachine& target); - void addCallDepEdges (const std::vector& callNV, - const TargetMachine& target); - - void addMachineRegEdges (RegToRefVecMap& regToRefVecMap, - const TargetMachine& target); + void addCallCCEdges(const std::vector& memNod, + MachineBasicBlock& bbMvec, + const TargetMachine& target); + + void addCallDepEdges(const std::vector& callNV, + const TargetMachine& target); - void addEdgesForValue (SchedGraphNode* refNode, - const RefVec& defVec, - const Value* defValue, - bool refNodeIsDef, - bool refNodeIsDefAndUse, - const TargetMachine& target); + void addMachineRegEdges(RegToRefVecMap& regToRefVecMap, + const TargetMachine& target); - void addDummyEdges (); + void addEdgesForValue(SchedGraphNode* refNode, const RefVec& defVec, + const Value* defValue, bool refNodeIsDef, + bool refNodeIsDefAndUse, + const TargetMachine& target); + + void addDummyEdges(); + }; -class SchedGraphSet : private std::vector { -private: - const Function* method; - SchedGraphSet(const SchedGraphSet&); // DO NOT IMPLEMENT - void operator=(const SchedGraphSet&); // DO NOT IMPLEMENT -public: - typedef std::vector baseVector; - using baseVector::iterator; - using baseVector::const_iterator; - +class SchedGraphSet { + const Function* function; + std::vector Graphs; + + // Graph builder + void buildGraphsForMethod(const Function *F, const TargetMachine& target); + + inline void addGraph(SchedGraph* graph) { + assert(graph != NULL); + Graphs.push_back(graph); + } + public: - SchedGraphSet(const Function *F, const TargetMachine &TM); + SchedGraphSet(const Function *function, const TargetMachine& target); ~SchedGraphSet(); - // Iterators - using baseVector::begin; - using baseVector::end; - + //iterators + typedef std::vector::const_iterator iterator; + typedef std::vector::const_iterator const_iterator; + + std::vector::const_iterator begin() const { return Graphs.begin(); } + std::vector::const_iterator end() const { return Graphs.end(); } + // Debugging support void dump() const; - -private: - inline void addGraph(SchedGraph* graph) { - assert(graph != NULL); - this->push_back(graph); - } - - // Graph builder - void buildGraphsForMethod(const Function *F, const TargetMachine &TM); }; -//********************** Sched Graph Iterators *****************************/ - -// Ok to make it a template because it shd get instantiated at most twice: -// for and -// for . -// -template -class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> { -protected: - _EdgeIter oi; -public: - typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self; - - inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {} - - inline bool operator==(const _Self& x) const { return oi == x.oi; } - inline bool operator!=(const _Self& x) const { return !operator==(x); } - - // operator*() differs for pred or succ iterator - inline _NodeType* operator*() const { return (*oi)->getSrc(); } - inline _NodeType* operator->() const { return operator*(); } - - inline _EdgeType* getEdge() const { return *(oi); } - - inline _Self &operator++() { ++oi; return *this; } // Preincrement - inline _Self operator++(int) { // Postincrement - _Self tmp(*this); ++*this; return tmp; - } - - inline _Self &operator--() { --oi; return *this; } // Predecrement - inline _Self operator--(int) { // Postdecrement - _Self tmp = *this; --*this; return tmp; - } -}; -template -class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> { -protected: - _EdgeIter oi; -public: - typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self; - - inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {} - - inline bool operator==(const _Self& x) const { return oi == x.oi; } - inline bool operator!=(const _Self& x) const { return !operator==(x); } - - inline _NodeType* operator*() const { return (*oi)->getSink(); } - inline _NodeType* operator->() const { return operator*(); } - - inline _EdgeType* getEdge() const { return *(oi); } - - inline _Self &operator++() { ++oi; return *this; } // Preincrement - inline _Self operator++(int) { // Postincrement - _Self tmp(*this); ++*this; return tmp; - } - - inline _Self &operator--() { --oi; return *this; } // Predecrement - inline _Self operator--(int) { // Postdecrement - _Self tmp = *this; --*this; return tmp; - } -}; // // sg_pred_iterator @@ -434,16 +190,16 @@ typedef SGPredIterator typedef SGPredIterator sg_pred_const_iterator; -inline sg_pred_iterator pred_begin( SchedGraphNode *N) { +inline sg_pred_iterator pred_begin(SchedGraphNode *N) { return sg_pred_iterator(N->beginInEdges()); } -inline sg_pred_iterator pred_end( SchedGraphNode *N) { +inline sg_pred_iterator pred_end(SchedGraphNode *N) { return sg_pred_iterator(N->endInEdges()); } inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) { return sg_pred_const_iterator(N->beginInEdges()); } -inline sg_pred_const_iterator pred_end( const SchedGraphNode *N) { +inline sg_pred_const_iterator pred_end(const SchedGraphNode *N) { return sg_pred_const_iterator(N->endInEdges()); } @@ -457,16 +213,16 @@ typedef SGSuccIterator typedef SGSuccIterator sg_succ_const_iterator; -inline sg_succ_iterator succ_begin( SchedGraphNode *N) { +inline sg_succ_iterator succ_begin(SchedGraphNode *N) { return sg_succ_iterator(N->beginOutEdges()); } -inline sg_succ_iterator succ_end( SchedGraphNode *N) { +inline sg_succ_iterator succ_end(SchedGraphNode *N) { return sg_succ_iterator(N->endOutEdges()); } inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) { return sg_succ_const_iterator(N->beginOutEdges()); } -inline sg_succ_const_iterator succ_end( const SchedGraphNode *N) { +inline sg_succ_const_iterator succ_end(const SchedGraphNode *N) { return sg_succ_const_iterator(N->endOutEdges()); } @@ -477,7 +233,7 @@ template <> struct GraphTraits { typedef SchedGraphNode NodeType; typedef sg_succ_iterator ChildIteratorType; - static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); } + static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); } static inline ChildIteratorType child_begin(NodeType *N) { return succ_begin(N); } @@ -491,7 +247,7 @@ template <> struct GraphTraits { typedef sg_succ_const_iterator ChildIteratorType; static inline NodeType *getEntryNode(const SchedGraph *SG) { - return SG->getRoot(); + return (NodeType*)SG->getRoot(); } static inline ChildIteratorType child_begin(NodeType *N) { return succ_begin(N); @@ -501,8 +257,6 @@ template <> struct GraphTraits { } }; - -std::ostream &operator<<(std::ostream& os, const SchedGraphEdge& edge); -std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node); +} // End llvm namespace #endif