diff options
26 files changed, 729 insertions, 48 deletions
diff --git a/include/llvm/CodeGen/InstrSelection.h b/include/llvm/CodeGen/InstrSelection.h index 0a8a92706d..e07ebd7a33 100644 --- a/include/llvm/CodeGen/InstrSelection.h +++ b/include/llvm/CodeGen/InstrSelection.h @@ -13,7 +13,6 @@ #define LLVM_CODEGEN_INSTR_SELECTION_H #include "llvm/Instruction.h" -#include <vector> class Method; class InstrForest; class MachineInstr; diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h index 9903f09c01..29e832dd58 100644 --- a/include/llvm/CodeGen/MachineInstr.h +++ b/include/llvm/CodeGen/MachineInstr.h @@ -19,7 +19,7 @@ #include "llvm/CodeGen/InstrForest.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/NonCopyable.h" -#include "llvm/Target/Machine.h" +#include "llvm/Target/InstInfo.h" template<class _MI, class _V> class ValOpIterator; diff --git a/include/llvm/ConstPoolVals.h b/include/llvm/ConstPoolVals.h index 09260b5cea..71ca6a7a96 100644 --- a/include/llvm/ConstPoolVals.h +++ b/include/llvm/ConstPoolVals.h @@ -10,7 +10,6 @@ #include "llvm/User.h" #include "llvm/Support/DataTypes.h" -#include <vector> class ArrayType; class StructType; diff --git a/include/llvm/DerivedTypes.h b/include/llvm/DerivedTypes.h index e024ed3edc..3f93459b23 100644 --- a/include/llvm/DerivedTypes.h +++ b/include/llvm/DerivedTypes.h @@ -12,7 +12,6 @@ #define LLVM_DERIVED_TYPES_H #include "llvm/Type.h" -#include <vector> class DerivedType : public Type { // AbstractTypeUsers - Implement a list of the users that need to be notified diff --git a/include/llvm/InstrTypes.h b/include/llvm/InstrTypes.h index 1f771e6350..75c4943e44 100644 --- a/include/llvm/InstrTypes.h +++ b/include/llvm/InstrTypes.h @@ -10,8 +10,6 @@ #define LLVM_INSTRUCTION_TYPES_H #include "llvm/Instruction.h" -#include <list> -#include <vector> class Method; class SymTabValue; diff --git a/include/llvm/Instruction.h b/include/llvm/Instruction.h index 2bb590bc5e..3bbb8e7031 100644 --- a/include/llvm/Instruction.h +++ b/include/llvm/Instruction.h @@ -13,7 +13,7 @@ class Type; class BasicBlock; class Method; -class MachineInstr; // do not include header file MachineInstr.h +class MachineInstr; class MachineCodeForVMInstr; class Instruction : public User { diff --git a/include/llvm/SymbolTable.h b/include/llvm/SymbolTable.h index a53608f1d9..18ccf136c0 100644 --- a/include/llvm/SymbolTable.h +++ b/include/llvm/SymbolTable.h @@ -17,7 +17,6 @@ #define LLVM_SYMBOL_TABLE_H #include "llvm/Value.h" -#include <vector> #include <map> class Value; diff --git a/include/llvm/Target/Data.h b/include/llvm/Target/Data.h index 55739503e7..aa0afbcb7d 100644 --- a/include/llvm/Target/Data.h +++ b/include/llvm/Target/Data.h @@ -14,7 +14,6 @@ #define LLVM_TARGET_DATA_H #include "llvm/Type.h" -#include <vector> class StructType; class StructLayout; diff --git a/include/llvm/Target/RegInfo.h b/include/llvm/Target/RegInfo.h index 726baabf24..bb1b029b28 100644 --- a/include/llvm/Target/RegInfo.h +++ b/include/llvm/Target/RegInfo.h @@ -8,9 +8,14 @@ #ifndef LLVM_TARGET_REGINFO_H #define LLVM_TARGET_REGINFO_H -class LiveRangeInfo; -class Method; +#include "llvm/Support/NonCopyable.h" +#include <hash_map> +#include <string> + +class Value; class Instruction; +class Method; +class LiveRangeInfo; class LiveRange; class AddedInstrns; class MachineInstr; diff --git a/include/llvm/User.h b/include/llvm/User.h index d914b1fc1d..535dd1e88a 100644 --- a/include/llvm/User.h +++ b/include/llvm/User.h @@ -13,7 +13,6 @@ #define LLVM_USER_H #include "llvm/Value.h" -#include <vector> class User : public Value { User(const User &); // Do not implement diff --git a/include/llvm/Value.h b/include/llvm/Value.h index dd97d3577d..d2bf4cd5f1 100644 --- a/include/llvm/Value.h +++ b/include/llvm/Value.h @@ -8,7 +8,7 @@ #ifndef LLVM_VALUE_H #define LLVM_VALUE_H -#include <list> +#include <vector> #include "llvm/Annotation.h" #include "llvm/AbstractTypeUser.h" @@ -44,7 +44,7 @@ public: }; private: - list<User *> Uses; + vector<User *> Uses; string Name; PATypeHandle<Type> Ty; ValueTy VTy; @@ -130,10 +130,10 @@ public: virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy); //---------------------------------------------------------------------- - // Methods for handling the list of uses of this DEF. + // Methods for handling the vector of uses of this Value. // - typedef list<User*>::iterator use_iterator; - typedef list<User*>::const_iterator use_const_iterator; + typedef vector<User*>::iterator use_iterator; + typedef vector<User*>::const_iterator use_const_iterator; inline unsigned use_size() const { return Uses.size(); } inline bool use_empty() const { return Uses.empty(); } diff --git a/include/llvm/iOther.h b/include/llvm/iOther.h index 97f3262581..e723d4e975 100644 --- a/include/llvm/iOther.h +++ b/include/llvm/iOther.h @@ -10,7 +10,6 @@ #include "llvm/InstrTypes.h" #include "llvm/Method.h" -#include <vector> //===----------------------------------------------------------------------===// // PHINode Class diff --git a/lib/CodeGen/InstrSched/InstrScheduling.cpp b/lib/CodeGen/InstrSched/InstrScheduling.cpp index 494da31cf5..382dc3b60b 100644 --- a/lib/CodeGen/InstrSched/InstrScheduling.cpp +++ b/lib/CodeGen/InstrSched/InstrScheduling.cpp @@ -9,7 +9,7 @@ //*************************************************************************** #include "llvm/CodeGen/InstrScheduling.h" -#include "llvm/CodeGen/SchedPriorities.h" +#include "SchedPriorities.h" #include "llvm/Analysis/LiveVar/BBLiveVar.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/Support/CommandLine.h" diff --git a/lib/CodeGen/InstrSched/SchedGraph.cpp b/lib/CodeGen/InstrSched/SchedGraph.cpp index 1ad2b0fb45..5f0de8b932 100644 --- a/lib/CodeGen/InstrSched/SchedGraph.cpp +++ b/lib/CodeGen/InstrSched/SchedGraph.cpp @@ -11,11 +11,11 @@ * 7/20/01 - Vikram Adve - Created ***************************************************************************/ +#include "SchedGraph.h" #include "llvm/InstrTypes.h" #include "llvm/Instruction.h" #include "llvm/BasicBlock.h" #include "llvm/Method.h" -#include "llvm/CodeGen/SchedGraph.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/Target/InstInfo.h" #include "llvm/Support/StringExtras.h" diff --git a/include/llvm/CodeGen/SchedGraph.h b/lib/CodeGen/InstrSched/SchedGraph.h index e12d90ffcd..e12d90ffcd 100644 --- a/include/llvm/CodeGen/SchedGraph.h +++ b/lib/CodeGen/InstrSched/SchedGraph.h diff --git a/lib/CodeGen/InstrSched/SchedPriorities.cpp b/lib/CodeGen/InstrSched/SchedPriorities.cpp index c09f9fc24e..a4396c2d25 100644 --- a/lib/CodeGen/InstrSched/SchedPriorities.cpp +++ b/lib/CodeGen/InstrSched/SchedPriorities.cpp @@ -18,7 +18,7 @@ * 7/30/01 - Vikram Adve - Created ***************************************************************************/ -#include "llvm/CodeGen/SchedPriorities.h" +#include "SchedPriorities.h" SchedPriorities::SchedPriorities(const Method* method, diff --git a/include/llvm/CodeGen/SchedPriorities.h b/lib/CodeGen/InstrSched/SchedPriorities.h index 45f19b4654..1765dba5b8 100644 --- a/include/llvm/CodeGen/SchedPriorities.h +++ b/lib/CodeGen/InstrSched/SchedPriorities.h @@ -21,9 +21,9 @@ #ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H #define LLVM_CODEGEN_SCHEDPRIORITIES_H +#include "SchedGraph.h" #include "llvm/CodeGen/InstrScheduling.h" #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h" -#include "llvm/CodeGen/SchedGraph.h" #include "llvm/Target/SchedInfo.h" class Method; diff --git a/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp b/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp index 494da31cf5..382dc3b60b 100644 --- a/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp +++ b/lib/Target/SparcV9/InstrSched/InstrScheduling.cpp @@ -9,7 +9,7 @@ //*************************************************************************** #include "llvm/CodeGen/InstrScheduling.h" -#include "llvm/CodeGen/SchedPriorities.h" +#include "SchedPriorities.h" #include "llvm/Analysis/LiveVar/BBLiveVar.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/Support/CommandLine.h" diff --git a/lib/Target/SparcV9/InstrSched/SchedGraph.cpp b/lib/Target/SparcV9/InstrSched/SchedGraph.cpp index 1ad2b0fb45..5f0de8b932 100644 --- a/lib/Target/SparcV9/InstrSched/SchedGraph.cpp +++ b/lib/Target/SparcV9/InstrSched/SchedGraph.cpp @@ -11,11 +11,11 @@ * 7/20/01 - Vikram Adve - Created ***************************************************************************/ +#include "SchedGraph.h" #include "llvm/InstrTypes.h" #include "llvm/Instruction.h" #include "llvm/BasicBlock.h" #include "llvm/Method.h" -#include "llvm/CodeGen/SchedGraph.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/Target/InstInfo.h" #include "llvm/Support/StringExtras.h" diff --git a/lib/Target/SparcV9/InstrSched/SchedGraph.h b/lib/Target/SparcV9/InstrSched/SchedGraph.h new file mode 100644 index 0000000000..e12d90ffcd --- /dev/null +++ b/lib/Target/SparcV9/InstrSched/SchedGraph.h @@ -0,0 +1,495 @@ +/* -*-C++-*- + **************************************************************************** + * File: + * SchedGraph.h + * + * Purpose: + * Scheduling graph based on SSA graph plus extra dependence edges + * capturing dependences due to machine resources (machine registers, + * CC registers, and any others). + * + * Strategy: + * This graph tries to leverage the SSA graph as much as possible, + * but captures the extra dependences through a common interface. + * + * History: + * 7/20/01 - Vikram Adve - Created + ***************************************************************************/ + +#ifndef LLVM_CODEGEN_SCHEDGRAPH_H +#define LLVM_CODEGEN_SCHEDGRAPH_H + +#include "llvm/CFGdecls.h" // just for graph iterators +#include "llvm/Support/NonCopyable.h" +#include "llvm/Support/HashExtras.h" +#include <hash_map> + +class Value; +class Instruction; +class BasicBlock; +class Method; +class TargetMachine; +class SchedGraphEdge; +class SchedGraphNode; +class SchedGraph; +class NodeToRegRefMap; + +/******************** Exported Data Types and Constants ********************/ + +typedef int ResourceId; +const ResourceId InvalidResourceId = -1; + + +//*********************** Public Class Declarations ************************/ + +class SchedGraphEdge: public NonCopyable { +public: + enum SchedGraphEdgeDepType { + CtrlDep, MemoryDep, DefUseDep, MachineRegister, MachineResource + }; + enum DataDepOrderType { + TrueDep, AntiDep, OutputDep, NonDataDep + }; + +protected: + SchedGraphNode* src; + SchedGraphNode* sink; + SchedGraphEdgeDepType depType; + DataDepOrderType depOrderType; + int minDelay; // cached latency (assumes fixed target arch) + + union { + 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, + DataDepOrderType _depOrderType =TrueDep, + int _minDelay = -1); + + // constructor for explicit def-use or memory def-use edge + /*ctor*/ SchedGraphEdge(SchedGraphNode* _src, + SchedGraphNode* _sink, + Value* _val, + DataDepOrderType _depOrderType =TrueDep, + int _minDelay = -1); + + // constructor for machine register dependence + /*ctor*/ SchedGraphEdge(SchedGraphNode* _src, + SchedGraphNode* _sink, + unsigned int _regNum, + DataDepOrderType _depOrderType =TrueDep, + 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 == DefUseDep || depType == MemoryDep); return val; + } + int getMachineReg () const { + assert(depType == MachineRegister); return machineRegNum; + } + int getResourceId () const { + assert(depType == MachineResource); return resourceId; + } + +public: + // + // Debugging support + // + friend ostream& operator<<(ostream& os, const SchedGraphEdge& edge); + + void dump (int indent=0) const; + +private: + // disable default ctor + /*ctor*/ SchedGraphEdge(); // DO NOT IMPLEMENT +}; + + + +class SchedGraphNode: public NonCopyable { +private: + unsigned int nodeId; + const Instruction* instr; + const MachineInstr* minstr; + vector<SchedGraphEdge*> inEdges; + vector<SchedGraphEdge*> outEdges; + int latency; + +public: + typedef vector<SchedGraphEdge*>::iterator iterator; + typedef vector<SchedGraphEdge*>::const_iterator const_iterator; + +public: + // + // Accessor methods + // + unsigned int getNodeId () const { return nodeId; } + const Instruction* getInstr () const { return instr; } + const MachineInstr* getMachineInstr () const { return minstr; } + int getLatency () const { return latency; } + unsigned int getNumInEdges () const { return inEdges.size(); } + unsigned int getNumOutEdges () const { return outEdges.size(); } + bool isDummyNode () const { return (minstr == NULL); } + + // + // 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(); } + + // + // Limited modifier methods + // + void eraseAllEdges (); + +public: + // + // Debugging support + // + friend ostream& operator<<(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 int _nodeId, + const Instruction* _instr, + const MachineInstr* _minstr, + const TargetMachine& _target); + /*dtor*/ ~SchedGraphNode (); +}; + + + +class SchedGraph : + public NonCopyable, + private hash_map<const MachineInstr*, SchedGraphNode*> +{ +private: + vector<const BasicBlock*> bbVec; // basic blocks included in the graph + SchedGraphNode* graphRoot; // the root and leaf are not inserted + SchedGraphNode* graphLeaf; // in the hash_map (see getNumNodes()) + +public: + typedef hash_map<const MachineInstr*, SchedGraphNode*>::iterator iterator; + typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator; + +public: + // + // Accessor methods + // + const vector<const BasicBlock*>& getBasicBlocks() const { return bbVec; } + const unsigned int 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; + } + + // + // Delete a node from the graph. + // + void eraseNode(SchedGraphNode* node); + + // + // Unordered iterators. + // Return values is pair<const MachineIntr*,SchedGraphNode*>. + // + iterator begin() { + return hash_map<const MachineInstr*, SchedGraphNode*>::begin(); + } + iterator end() { + return hash_map<const MachineInstr*, SchedGraphNode*>::end(); + } + const_iterator begin() const { + return hash_map<const MachineInstr*, SchedGraphNode*>::begin(); + } + const_iterator end() const { + return hash_map<const MachineInstr*, SchedGraphNode*>::end(); + } + + // + // Ordered iterators. + // Return values is pair<const MachineIntr*,SchedGraphNode*>. + // + // void postord_init(); + // postorder_iterator postord_begin(); + // postorder_iterator postord_end(); + // const_postorder_iterator postord_begin() const; + // const_postorder_iterator postord_end() const; + + // + // Debugging support + // + void dump () const; + +private: + friend class SchedGraphSet; // give access to ctor + + // disable default constructor and provide a ctor for single-block graphs + /*ctor*/ SchedGraph (); // DO NOT IMPLEMENT + /*ctor*/ SchedGraph (const BasicBlock* bb, + const TargetMachine& target); + /*dtor*/ ~SchedGraph (); + + inline void noteGraphNodeForInstr (const MachineInstr* minstr, + SchedGraphNode* node) + { + assert((*this)[minstr] == NULL); + (*this)[minstr] = node; + } + + // + // Graph builder + // + void buildGraph (const TargetMachine& target); + + void addEdgesForInstruction (SchedGraphNode* node, + NodeToRegRefMap& regToRefVecMap, + const TargetMachine& target); + + void addCDEdges (const TerminatorInst* term, + const TargetMachine& target); + + void addMemEdges (const vector<const Instruction*>& memVec, + const TargetMachine& target); + + void addMachineRegEdges (NodeToRegRefMap& regToRefVecMap, + const TargetMachine& target); + + void addSSAEdge (SchedGraphNode* node, + Value* val, + const TargetMachine& target); + + void addDummyEdges (); +}; + + +class SchedGraphSet : + public NonCopyable, + private hash_map<const BasicBlock*, SchedGraph*> +{ +private: + const Method* method; + +public: + typedef hash_map<const BasicBlock*, SchedGraph*>::iterator iterator; + typedef hash_map<const BasicBlock*, SchedGraph*>::const_iterator const_iterator; + +public: + /*ctor*/ SchedGraphSet (const Method* _method, + const TargetMachine& target); + /*dtor*/ ~SchedGraphSet (); + + // + // Accessors + // + SchedGraph* getGraphForBasicBlock (const BasicBlock* bb) const { + const_iterator onePair = this->find(bb); + return (onePair != this->end())? (*onePair).second : NULL; + } + + // + // Iterators + // + iterator begin() { + return hash_map<const BasicBlock*, SchedGraph*>::begin(); + } + iterator end() { + return hash_map<const BasicBlock*, SchedGraph*>::end(); + } + const_iterator begin() const { + return hash_map<const BasicBlock*, SchedGraph*>::begin(); + } + const_iterator end() const { + return hash_map<const BasicBlock*, SchedGraph*>::end(); + } + + // + // Debugging support + // + void dump () const; + +private: + inline void noteGraphForBlock(const BasicBlock* bb, SchedGraph* graph) { + assert((*this)[bb] == NULL); + (*this)[bb] = graph; + } + + // + // Graph builder + // + void buildGraphsForMethod (const Method *method, + const TargetMachine& target); +}; + + +//********************** Sched Graph Iterators *****************************/ + +// Ok to make it a template because it shd get instantiated at most twice: +// for <SchedGraphNode, SchedGraphNode::iterator> and +// for <const SchedGraphNode, SchedGraphNode::const_iterator>. +// +template <class _NodeType, class _EdgeType, class _EdgeIter> +class PredIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> { +protected: + _EdgeIter oi; +public: + typedef PredIterator<_NodeType, _EdgeType, _EdgeIter> _Self; + + inline PredIterator(_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 _NodeType, class _EdgeType, class _EdgeIter> +class SuccIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> { +protected: + _EdgeIter oi; +public: + typedef SuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self; + + inline SuccIterator(_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 +// sg_pred_const_iterator +// +typedef PredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator> + sg_pred_iterator; +typedef PredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator> + sg_pred_const_iterator; + +inline sg_pred_iterator pred_begin( SchedGraphNode *N) { + return sg_pred_iterator(N->beginInEdges()); +} +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) { + return sg_pred_const_iterator(N->endInEdges()); +} + + +// +// sg_succ_iterator +// sg_succ_const_iterator +// +typedef SuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator> + sg_succ_iterator; +typedef SuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator> + sg_succ_const_iterator; + +inline sg_succ_iterator succ_begin( SchedGraphNode *N) { + return sg_succ_iterator(N->beginOutEdges()); +} +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) { + return sg_succ_const_iterator(N->endOutEdges()); +} + +// +// po_iterator +// po_const_iterator +// +typedef cfg::POIterator<SchedGraphNode, sg_succ_iterator> sg_po_iterator; +typedef cfg::POIterator<const SchedGraphNode, + sg_succ_const_iterator> sg_po_const_iterator; + + +//************************ External Functions *****************************/ + + +ostream& operator<<(ostream& os, const SchedGraphEdge& edge); + +ostream& operator<<(ostream& os, const SchedGraphNode& node); + + +/***************************************************************************/ + +#endif diff --git a/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp b/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp index c09f9fc24e..a4396c2d25 100644 --- a/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp +++ b/lib/Target/SparcV9/InstrSched/SchedPriorities.cpp @@ -18,7 +18,7 @@ * 7/30/01 - Vikram Adve - Created ***************************************************************************/ -#include "llvm/CodeGen/SchedPriorities.h" +#include "SchedPriorities.h" SchedPriorities::SchedPriorities(const Method* method, diff --git a/lib/Target/SparcV9/InstrSched/SchedPriorities.h b/lib/Target/SparcV9/InstrSched/SchedPriorities.h new file mode 100644 index 0000000000..1765dba5b8 --- /dev/null +++ b/lib/Target/SparcV9/InstrSched/SchedPriorities.h @@ -0,0 +1,203 @@ +/* -*-C++-*- + **************************************************************************** + * File: + * SchedPriorities.h + * + * Purpose: + * Encapsulate heuristics for instruction scheduling. + * + * Strategy: + * Priority ordering rules: + * (1) Max delay, which is the order of the heap S.candsAsHeap. + * (2) Instruction that frees up a register. + * (3) Instruction that has the maximum number of dependent instructions. + * Note that rules 2 and 3 are only used if issue conflicts prevent + * choosing a higher priority instruction by rule 1. + * + * History: + * 7/30/01 - Vikram Adve - Created + ***************************************************************************/ + +#ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H +#define LLVM_CODEGEN_SCHEDPRIORITIES_H + +#include "SchedGraph.h" +#include "llvm/CodeGen/InstrScheduling.h" +#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h" +#include "llvm/Target/SchedInfo.h" + +class Method; +class MachineInstr; +class SchedulingManager; + + +struct NodeDelayPair { + const SchedGraphNode* node; + cycles_t delay; + NodeDelayPair(const SchedGraphNode* n, cycles_t d) : node(n), delay(d) {} + inline bool operator< (const NodeDelayPair& np) { return delay < np.delay; } +}; + +inline bool +NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2) +{ + return (np1->delay < np2->delay); +} + +class NodeHeap: public list<NodeDelayPair*>, public NonCopyable { +public: + typedef list<NodeDelayPair*>::iterator iterator; + typedef list<NodeDelayPair*>::const_iterator const_iterator; + +public: + /*ctor*/ NodeHeap () : list<NodeDelayPair*>(), _size(0) {} + /*dtor*/ ~NodeHeap () {} + + inline unsigned int size () const { return _size; } + + const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; } + cycles_t getDelay(const_iterator i) const { return (*i)->delay;} + + inline void makeHeap() { + // make_heap(begin(), end(), NDPLessThan); + } + + inline iterator findNode(const SchedGraphNode* node) { + for (iterator I=begin(); I != end(); ++I) + if (getNode(I) == node) + return I; + return end(); + } + + inline void removeNode (const SchedGraphNode* node) { + iterator ndpPtr = findNode(node); + if (ndpPtr != end()) + { + delete *ndpPtr; + erase(ndpPtr); + --_size; + } + }; + + void insert(const SchedGraphNode* node, cycles_t delay) { + NodeDelayPair* ndp = new NodeDelayPair(node, delay); + if (_size == 0 || front()->delay < delay) + push_front(ndp); + else + { + iterator I=begin(); + for ( ; I != end() && getDelay(I) >= delay; ++I) + ; + list<NodeDelayPair*>::insert(I, ndp); + } + _size++; + } +private: + unsigned int _size; +}; + + +class SchedPriorities: public NonCopyable { +public: + /*ctor*/ SchedPriorities (const Method* method, + const SchedGraph* _graph); + + // This must be called before scheduling begins. + void initialize (); + + cycles_t getTime () const { return curTime; } + cycles_t getEarliestReadyTime () const { return earliestReadyTime; } + unsigned getNumReady () const { return candsAsHeap.size(); } + bool nodeIsReady (const SchedGraphNode* node) const { + return (candsAsSet.find(node) != candsAsSet.end()); + } + + void issuedReadyNodeAt (cycles_t curTime, + const SchedGraphNode* node); + + void insertReady (const SchedGraphNode* node); + + void updateTime (cycles_t /*unused*/); + + const SchedGraphNode* getNextHighest (const SchedulingManager& S, + cycles_t curTime); + // choose next highest priority instr + +private: + typedef NodeHeap::iterator candIndex; + +private: + cycles_t curTime; + const SchedGraph* graph; + MethodLiveVarInfo methodLiveVarInfo; + hash_map<const MachineInstr*, bool> lastUseMap; + vector<cycles_t> nodeDelayVec; + vector<cycles_t> earliestForNode; + cycles_t earliestReadyTime; + NodeHeap candsAsHeap; // candidate nodes, ready to go + hash_set<const SchedGraphNode*> candsAsSet; // same entries as candsAsHeap, + // but as set for fast lookup + vector<candIndex> mcands; // holds pointers into cands + candIndex nextToTry; // next cand after the last + // one tried in this cycle + + int chooseByRule1 (vector<candIndex>& mcands); + int chooseByRule2 (vector<candIndex>& mcands); + int chooseByRule3 (vector<candIndex>& mcands); + + void findSetWithMaxDelay (vector<candIndex>& mcands, + const SchedulingManager& S); + + void computeDelays (const SchedGraph* graph); + + void initializeReadyHeap (const SchedGraph* graph); + + bool instructionHasLastUse (MethodLiveVarInfo& methodLiveVarInfo, + const SchedGraphNode* graphNode); + + // NOTE: The next two return references to the actual vector entries. + // Use with care. + cycles_t& getNodeDelayRef (const SchedGraphNode* node) { + assert(node->getNodeId() < nodeDelayVec.size()); + return nodeDelayVec[node->getNodeId()]; + } + cycles_t& getEarliestForNodeRef (const SchedGraphNode* node) { + assert(node->getNodeId() < earliestForNode.size()); + return earliestForNode[node->getNodeId()]; + } +}; + + +inline void +SchedPriorities::insertReady(const SchedGraphNode* node) +{ + candsAsHeap.insert(node, nodeDelayVec[node->getNodeId()]); + candsAsSet.insert(node); + mcands.clear(); // ensure reset choices is called before any more choices + earliestReadyTime = min(earliestReadyTime, + earliestForNode[node->getNodeId()]); + + if (SchedDebugLevel >= Sched_PrintSchedTrace) + { + cout << " Cycle " << this->getTime() << ": " + << " Node " << node->getNodeId() << " is ready; " + << " Delay = " << this->getNodeDelayRef(node) << "; Instruction: " + << endl; + cout << " " << *node->getMachineInstr() << endl; + } +} + +inline void SchedPriorities::updateTime(cycles_t c) { + curTime = c; + nextToTry = candsAsHeap.begin(); + mcands.clear(); +} + +inline ostream& operator<< (ostream& os, const NodeDelayPair* nd) { + return os << "Delay for node " << nd->node->getNodeId() + << " = " << nd->delay << endl; +} + +/***************************************************************************/ + +#endif diff --git a/lib/Target/SparcV9/SparcV9Internals.h b/lib/Target/SparcV9/SparcV9Internals.h index f9a344b37a..e4f0a8bd10 100644 --- a/lib/Target/SparcV9/SparcV9Internals.h +++ b/lib/Target/SparcV9/SparcV9Internals.h @@ -8,11 +8,10 @@ #ifndef SPARC_INTERNALS_H #define SPARC_INTERNALS_H -#include "llvm/Target/Machine.h" #include "SparcRegInfo.h" - -#include <sys/types.h> +#include "llvm/Target/SchedInfo.h" #include "llvm/Type.h" +#include <sys/types.h> class UltraSparc; @@ -39,17 +38,6 @@ enum SparcInstrSchedClass { SPARC_NUM_SCHED_CLASSES = SPARC_INV }; -// inline operator int (const SparcInstrSchedClass& si) { -// return (int) si; -// } -// -// inline operator SparcInstrSchedClass (int i) { -// return (SparcInstrSchedClass) si; -// } -// -// inline operator const SparcInstrSchedClass (int i) { -// return (const SparcInstrSchedClass) si; -// } //--------------------------------------------------------------------------- // enum SparcMachineOpCode. @@ -60,7 +48,6 @@ enum SparcInstrSchedClass { // //--------------------------------------------------------------------------- - enum SparcMachineOpCode { NOP, diff --git a/lib/Target/SparcV9/SparcV9RegInfo.h b/lib/Target/SparcV9/SparcV9RegInfo.h index 3ebef550f0..67aa3a62ea 100644 --- a/lib/Target/SparcV9/SparcV9RegInfo.h +++ b/lib/Target/SparcV9/SparcV9RegInfo.h @@ -7,7 +7,7 @@ #ifndef SPARC_INT_REG_CLASS_H #define SPARC_INT_REG_CLASS_H -#include "llvm/Target/Machine.h" +#include "llvm/Target/RegInfo.h" //----------------------------------------------------------------------------- // Integer Register Class diff --git a/lib/Target/SparcV9/SparcV9TargetMachine.cpp b/lib/Target/SparcV9/SparcV9TargetMachine.cpp index cf09734e81..f1be4060be 100644 --- a/lib/Target/SparcV9/SparcV9TargetMachine.cpp +++ b/lib/Target/SparcV9/SparcV9TargetMachine.cpp @@ -8,12 +8,16 @@ // 7/15/01 - Vikram Adve - Created //**************************************************************************/ -#include "llvm/CodeGen/Sparc.h" +#include "llvm/Target/Sparc.h" #include "SparcInternals.h" #include "llvm/Method.h" #include "llvm/CodeGen/InstrScheduling.h" #include "llvm/CodeGen/InstrSelection.h" +// allocateSparcTargetMachine - Allocate and return a subclass of TargetMachine +// that implements the Sparc backend. (the llvm/CodeGen/Sparc.h interface) +// +TargetMachine *allocateSparcTargetMachine() { return new UltraSparc(); } //--------------------------------------------------------------------------- @@ -115,7 +119,3 @@ bool UltraSparc::compileMethod(Method *M) { return false; } -// allocateSparcTargetMachine - Allocate and return a subclass of TargetMachine -// that implements the Sparc backend. -// -TargetMachine *allocateSparcTargetMachine() { return new UltraSparc(); } diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp index e48341ef51..a41262d0c6 100644 --- a/lib/VMCore/Value.cpp +++ b/lib/VMCore/Value.cpp @@ -1,6 +1,6 @@ //===-- Value.cpp - Implement the Value class -----------------------------===// // -// This file implements the Value class. +// This file implements the Value, User, and SymTabValue classes. // //===----------------------------------------------------------------------===// @@ -44,7 +44,7 @@ void Value::replaceAllUsesWith(Value *D) { assert(D && "Value::replaceAllUsesWith(<null>) is invalid!"); assert(D != this && "V->replaceAllUsesWith(V) is NOT valid!"); while (!Uses.empty()) { - User *Use = Uses.front(); + User *Use = Uses.back(); #ifndef NDEBUG unsigned NumUses = Uses.size(); #endif |