diff options
Diffstat (limited to 'lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h')
| -rw-r--r-- | lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h | 363 |
1 files changed, 190 insertions, 173 deletions
diff --git a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h index c411d14e78..0947d32cb3 100644 --- a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h +++ b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h @@ -1,4 +1,4 @@ -//===- ModuloSchedGraph.h - Represent a collection of data structures ----*- C++ -*-===// +//===- ModuloSchedGraph.h - Modulo Scheduling Graph and Set -*- C++ -*-----===// // // This header defines the primative classes that make up a data structure // graph. @@ -7,82 +7,111 @@ #ifndef LLVM_CODEGEN_MODULO_SCHED_GRAPH_H #define LLVM_CODEGEN_MODULO_SCHED_GRAPH_H - -#include "Support/HashExtras.h" -#include "Support/GraphTraits.h" -#include "../InstrSched/SchedGraphCommon.h" + #include "llvm/Instruction.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" +#include "Support/HashExtras.h" +#include "Support/GraphTraits.h" +#include "../InstrSched/SchedGraphCommon.h" #include <iostream> -using std::pair; //for debug information selecton -enum ModuloSchedDebugLevel_t{ +enum ModuloSchedDebugLevel_t { ModuloSched_NoDebugInfo, ModuloSched_Disable, ModuloSched_PrintSchedule, ModuloSched_PrintScheduleProcess, }; -//===============------------------------------------------------------------------------ -///ModuloSchedGraphNode - Implement a data structure based on the SchedGraphNodeCommon -///this class stores informtion needed later to order the nodes in modulo scheduling -/// -class ModuloSchedGraphNode: public SchedGraphNodeCommon { +//===----------------------------------------------------------------------===// +// ModuloSchedGraphNode - Implement a data structure based on the +// SchedGraphNodeCommon this class stores informtion needed later to order the +// nodes in modulo scheduling +// +class ModuloSchedGraphNode:public SchedGraphNodeCommon { private: - //the corresponding instruction - const Instruction* inst; + // the corresponding instruction + const Instruction *inst; - //whether this node's property(ASAP,ALAP, ...) has been computed + // whether this node's property(ASAP,ALAP, ...) has been computed bool propertyComputed; - //ASAP: the earliest time the node could be scheduled - //ALAP: the latest time the node couldbe scheduled - //depth: the depth of the node - //height: the height of the node - //mov: the mobility function, computed as ALAP - ASAP - //scheTime: the scheduled time if this node has been scheduled - //earlyStart: the earliest time to be tried to schedule the node - //lateStart: the latest time to be tried to schedule the node + // ASAP: the earliest time the node could be scheduled + // ALAP: the latest time the node couldbe scheduled + // depth: the depth of the node + // height: the height of the node + // mov: the mobility function, computed as ALAP - ASAP + // scheTime: the scheduled time if this node has been scheduled + // earlyStart: the earliest time to be tried to schedule the node + // lateStart: the latest time to be tried to schedule the node int ASAP, ALAP, depth, height, mov; int schTime; - int earlyStart,lateStart; + int earlyStart, lateStart; public: - - //get the instruction - const Instruction* getInst() const { return inst;} + //get the instruction + const Instruction *getInst() const { + return inst; + } //get the instruction op-code name - const char* getInstOpcodeName() const{ return inst->getOpcodeName();} - - //get the instruction op-code - const unsigned getInstOpcode() const { return inst->getOpcode();} - + const char *getInstOpcodeName() const { + return inst->getOpcodeName(); + } + //get the instruction op-code + const unsigned getInstOpcode() const { + return inst->getOpcode(); + } //return whether the node is NULL - bool isNullNode() const{ return(inst== NULL);} - + bool isNullNode() const { + return (inst == NULL); + } //return whether the property of the node has been computed - bool getPropertyComputed() {return propertyComputed;} - + bool getPropertyComputed() { + return propertyComputed; + } //set the propertyComputed - void setPropertyComputed(bool _propertyComputed) {propertyComputed = _propertyComputed;} - + void setPropertyComputed(bool _propertyComputed) { + propertyComputed = _propertyComputed; + } + //get the corresponding property - int getASAP(){ return ASAP;} - int getALAP(){ return ALAP;} - int getMov() { return mov;} - int getDepth(){return depth;} - int getHeight(){return height;} - int getSchTime(){return schTime;} - int getEarlyStart(){return earlyStart;} - int getLateStart() { return lateStart;} - void setEarlyStart(int _earlyStart) {earlyStart= _earlyStart;} - void setLateStart(int _lateStart) {lateStart= _lateStart;} - void setSchTime(int _time){schTime=_time;} - - private: + int getASAP() { + return ASAP; + } + int getALAP() { + return ALAP; + } + int getMov() { + return mov; + } + int getDepth() { + return depth; + } + int getHeight() { + return height; + } + int getSchTime() { + return schTime; + } + int getEarlyStart() { + return earlyStart; + } + int getLateStart() { + return lateStart; + } + void setEarlyStart(int _earlyStart) { + earlyStart = _earlyStart; + } + void setLateStart(int _lateStart) { + lateStart = _lateStart; + } + void setSchTime(int _time) { + schTime = _time; + } + +private: friend class ModuloSchedGraph; friend class SchedGraphNode; @@ -93,43 +122,34 @@ public: //indexInBB: the corresponding instruction's index in the BasicBlock //target: the targetMachine ModuloSchedGraphNode(unsigned int _nodeId, - const BasicBlock* _bb, - const Instruction* _inst, - int indexInBB, - const TargetMachine& target); - - - friend std::ostream& operator<<(std::ostream& os,const ModuloSchedGraphNode& edge); - -}; - + const BasicBlock * _bb, + const Instruction * _inst, + int indexInBB, const TargetMachine &target); + friend std::ostream & operator<<(std::ostream & os, + const ModuloSchedGraphNode & edge); +}; //FIXME: these two value should not be used #define MAXNODE 100 #define MAXCC 100 - - //===----------------------------------------------------------------------===// /// ModuloSchedGraph- the data structure to store dependence between nodes /// it catches data dependence and constrol dependence /// -/// - -class ModuloSchedGraph: +class ModuloSchedGraph : public SchedGraphCommon, - protected hash_map<const Instruction*, ModuloSchedGraphNode*> -{ - -private: + protected hash_map<const Instruction*,ModuloSchedGraphNode*> { + +private: //iteration Interval int MII; - + //target machine - const TargetMachine& target; + const TargetMachine & target; //the circuits in the dependence graph unsigned circuits[MAXCC][MAXNODE]; @@ -140,20 +160,20 @@ private: typedef std::vector<ModuloSchedGraphNode*> NodeVec; //the function to compute properties - void computeNodeASAP(const BasicBlock* bb); - void computeNodeALAP(const BasicBlock* bb); - void computeNodeMov(const BasicBlock* bb); - void computeNodeDepth(const BasicBlock* bb); - void computeNodeHeight(const BasicBlock* bb); + void computeNodeASAP(const BasicBlock * bb); + void computeNodeALAP(const BasicBlock * bb); + void computeNodeMov(const BasicBlock * bb); + void computeNodeDepth(const BasicBlock * bb); + void computeNodeHeight(const BasicBlock * bb); //the function to compute node property - void computeNodeProperty(const BasicBlock* bb); + void computeNodeProperty(const BasicBlock * bb); //the function to sort nodes void orderNodes(); - + //add the resource usage - void addResourceUsage(std::vector<pair<int,int> >&, int); +void addResourceUsage(std::vector<pair<int,int>>&, int); //debug functions: //dump circuits @@ -161,13 +181,13 @@ private: //dump the input set of nodes void dumpSet(std::vector<ModuloSchedGraphNode*> set); //dump the input resource usage table - void dumpResourceUsage(std::vector<pair<int,int> >&); - - public: + void dumpResourceUsage(std::vector<pair<int,int>> &); + +public: //help functions - + //get the maxium the delay between two nodes - SchedGraphEdge* getMaxDelayEdge(unsigned srcId, unsigned sinkId); + SchedGraphEdge *getMaxDelayEdge(unsigned srcId, unsigned sinkId); //FIXME: //get the predessor Set of the set @@ -175,174 +195,171 @@ private: NodeVec predSet(NodeVec set); //get the predessor set of the node - NodeVec predSet(ModuloSchedGraphNode* node, unsigned,unsigned); - NodeVec predSet(ModuloSchedGraphNode* node); + NodeVec predSet(ModuloSchedGraphNode * node, unsigned, unsigned); + NodeVec predSet(ModuloSchedGraphNode * node); //get the successor set of the set NodeVec succSet(NodeVec set, unsigned, unsigned); NodeVec succSet(NodeVec set); - + //get the succssor set of the node - NodeVec succSet(ModuloSchedGraphNode* node,unsigned, unsigned); - NodeVec succSet(ModuloSchedGraphNode* node); + NodeVec succSet(ModuloSchedGraphNode * node, unsigned, unsigned); + NodeVec succSet(ModuloSchedGraphNode * node); //return the uniton of the two vectors - NodeVec vectorUnion(NodeVec set1,NodeVec set2 ); + NodeVec vectorUnion(NodeVec set1, NodeVec set2); //return the consjuction of the two vectors - NodeVec vectorConj(NodeVec set1,NodeVec set2 ); - + NodeVec vectorConj(NodeVec set1, NodeVec set2); + //return all nodes in set1 but not set2 NodeVec vectorSub(NodeVec set1, NodeVec set2); - typedef hash_map<const Instruction*, ModuloSchedGraphNode*> map_base; + typedef hash_map<const Instruction*,ModuloSchedGraphNode*> map_base; + public: using map_base::iterator; using map_base::const_iterator; - + public: //get target machine - const TargetMachine& getTarget(){return target;} - + const TargetMachine & getTarget() { + return target; + } //get the iteration interval - const int getMII(){return MII;} + const int getMII() { + return MII; + } //get the ordered nodes - const NodeVec& getONodes(){return oNodes;} + const NodeVec & getONodes() { + return oNodes; + } //get the number of nodes (including the root and leaf) //note: actually root and leaf is not used - const unsigned int getNumNodes() const {return size()+2;} - + const unsigned int getNumNodes() const { + return size() + 2; + } //return wether the BasicBlock 'bb' contains a loop - bool isLoop (const BasicBlock* bb); + bool isLoop(const BasicBlock * bb); //return this basibBlock contains a loop - bool isLoop (); - + bool isLoop(); + //return the node for the input instruction - ModuloSchedGraphNode* getGraphNodeForInst(const Instruction* inst) const{ + ModuloSchedGraphNode *getGraphNodeForInst(const Instruction * inst) const { const_iterator onePair = this->find(inst); - return (onePair != this->end())?(*onePair).second: NULL; + return (onePair != this->end()) ? (*onePair).second : NULL; } - - //Debugging support - //dump the graph - void dump() const; + //Debugging support//dump the graph void dump() const; //dump the basicBlock - void dump(const BasicBlock* bb); + void dump(const BasicBlock * bb); //dump the basicBlock into 'os' stream - void dump(const BasicBlock* bb, std::ostream& os); + void dump(const BasicBlock * bb, std::ostream & os); //dump the node property - void dumpNodeProperty() const ; - - private: - friend class ModuloSchedGraphSet; //give access to ctor + void dumpNodeProperty() const; - public: - /*ctr*/ - ModuloSchedGraph(const BasicBlock* bb, const TargetMachine& _target) - :SchedGraphCommon(bb), target(_target){ +private: + friend class ModuloSchedGraphSet; //give access to ctor + +public: + ModuloSchedGraph(const BasicBlock *bb, const TargetMachine &_target) + :SchedGraphCommon(bb), target(_target) { buildGraph(target); } - /*dtr*/ - ~ModuloSchedGraph(){ - for(const_iterator I=begin(); I!=end(); ++I) + ~ModuloSchedGraph() { + for (const_iterator I = begin(); I != end(); ++I) delete I->second; } - + //unorder iterators //return values are pair<const Instruction*, ModuloSchedGraphNode*> using map_base::begin; using map_base::end; + void noteModuloSchedGraphNodeForInst(const Instruction *inst, + ModuloSchedGraphNode *node) + { + assert((*this)[inst] == NULL); + (*this)[inst] = node; + } - - inline void noteModuloSchedGraphNodeForInst(const Instruction* inst, - ModuloSchedGraphNode* node) - { - assert((*this)[inst] ==NULL); - (*this)[inst]=node; - } - //Graph builder - - ModuloSchedGraphNode* getNode (const unsigned nodeId) const; + + ModuloSchedGraphNode *getNode(const unsigned nodeId) const; //build the graph from the basicBlock - void buildGraph (const TargetMachine& target); + void buildGraph(const TargetMachine & target); //Build nodes for BasicBlock - void buildNodesforBB (const TargetMachine& target, - const BasicBlock* bb, - NodeVec& memNode, - RegToRefVecMap& regToRefVecMap, - ValueToDefVecMap& valueToDefVecMap); + void buildNodesforBB(const TargetMachine &target, + const BasicBlock *bb, + NodeVec &memNode, + RegToRefVecMap ®ToRefVecMap, + ValueToDefVecMap &valueToDefVecMap); //find definitiona and use information for all nodes - void findDefUseInfoAtInstr (const TargetMachine& target, - ModuloSchedGraphNode* node, - NodeVec& memNode, - RegToRefVecMap& regToRefVecMap, - ValueToDefVecMap& valueToDefVecMap); + void findDefUseInfoAtInstr(const TargetMachine &target, + ModuloSchedGraphNode *node, + NodeVec &memNode, + RegToRefVecMap ®ToRefVecMap, + ValueToDefVecMap &valueToDefVecMap); //add def-use edge - void addDefUseEdges (const BasicBlock* bb); + void addDefUseEdges(const BasicBlock *bb); //add control dependence edges - void addCDEdges (const BasicBlock* bb); + void addCDEdges(const BasicBlock *bb); //add memory dependence dges - void addMemEdges (const BasicBlock* bb); + void addMemEdges(const BasicBlock *bb); //add dummy edges void addDummyEdges(); //computer source restrictoin II - int computeResII (const BasicBlock* bb); + int computeResII(const BasicBlock *bb); //computer recurrence II - int computeRecII (const BasicBlock* bb); + int computeRecII(const BasicBlock *bb); }; -///==================================- -//gragh set +//==================================- +// Graph set -class ModuloSchedGraphSet: - public std::vector<ModuloSchedGraph*> -{ +class ModuloSchedGraphSet : public std::vector<ModuloSchedGraph*> { private: - const Function* method; - + const Function *method; + public: typedef std::vector<ModuloSchedGraph*> baseVector; using baseVector::iterator; using baseVector::const_iterator; - + public: - /*ctor*/ ModuloSchedGraphSet (const Function* function, const TargetMachine& target); - - /*dtor*/ ~ModuloSchedGraphSet (); - - //iterators + ModuloSchedGraphSet(const Function *function, const TargetMachine &target); + ~ModuloSchedGraphSet(); + + // Iterators using baseVector::begin; using baseVector::end; +// Debugging support +void dump() const; - //Debugging support - void dump() const; - private: - inline void addGraph(ModuloSchedGraph* graph){ - assert(graph !=NULL); + void addGraph(ModuloSchedGraph *graph) { + assert(graph != NULL); this->push_back(graph); } - - //Graph builder - void buildGraphsForMethod (const Function *F, const TargetMachine& target); -}; -#endif + // Graph builder + void buildGraphsForMethod(const Function *F, + const TargetMachine &target); +} + +#endif |