*** empty log message ***
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5755 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h
new file mode 100644
index 0000000..07fde3c
--- /dev/null
+++ b/lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h
@@ -0,0 +1,347 @@
+//===- ModuloSchedGraph.h - Represent a collection of data structures ----*- C++ -*-===//
+//
+// This header defines the primative classes that make up a data structure
+// graph.
+//
+//===----------------------------------------------------------------------===//
+
+#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 <iostream>
+using std::pair;
+
+//for debug information selecton
+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 {
+private:
+ //the corresponding instruction
+ const Instruction* inst;
+
+ //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
+ int ASAP, ALAP, depth, height, mov;
+ int schTime;
+ int earlyStart,lateStart;
+
+public:
+
+ //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();}
+
+ //return whether the node is NULL
+ bool isNullNode() const{ return(inst== NULL);}
+
+ //return whether the property of the node has been computed
+ bool getPropertyComputed() {return propertyComputed;}
+
+ //set the 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:
+ friend class ModuloSchedGraph;
+ friend class SchedGraphNode;
+
+ //constructor:
+ //nodeId: the node id, unique within the each BasicBlock
+ //_bb: which BasicBlock the corresponding instruction belongs to
+ //_inst: the corresponding instruction
+ //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);
+
+};
+
+
+
+
+
+//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:
+ public SchedGraphCommon,
+ protected hash_map<const Instruction*, ModuloSchedGraphNode*>
+{
+
+private:
+ //iteration Interval
+ int MII;
+
+ //target machine
+ const TargetMachine& target;
+
+ //the circuits in the dependence graph
+ unsigned circuits[MAXCC][MAXNODE];
+
+ //the order nodes
+ std::vector<ModuloSchedGraphNode*> oNodes;
+
+ 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);
+
+ //the function to compute node property
+ void computeNodeProperty(const BasicBlock* bb);
+
+ //the function to sort nodes
+ void orderNodes();
+
+ //add the resource usage
+ void addResourceUsage(std::vector<pair<int,int> >&, int);
+
+ //debug functions:
+ //dump circuits
+ void dumpCircuits();
+ //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:
+ //help functions
+
+ //get the maxium the delay between two nodes
+ SchedGraphEdge* getMaxDelayEdge(unsigned srcId, unsigned sinkId);
+
+ //FIXME:
+ //get the predessor Set of the set
+ NodeVec predSet(NodeVec set, unsigned, unsigned);
+ NodeVec predSet(NodeVec set);
+
+ //get the predessor set of the 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);
+
+ //return the uniton of the two vectors
+ NodeVec vectorUnion(NodeVec set1,NodeVec set2 );
+
+ //return the consjuction of the two vectors
+ 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;
+public:
+ using map_base::iterator;
+ using map_base::const_iterator;
+
+public:
+
+ //get target machine
+ const TargetMachine& getTarget(){return target;}
+
+ //get the iteration interval
+ const int getMII(){return MII;}
+
+ //get the ordered nodes
+ 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;}
+
+ //return wether the BasicBlock 'bb' contains a loop
+ bool isLoop (const BasicBlock* bb);
+
+ //return this basibBlock contains a loop
+ bool isLoop ();
+
+
+ //return the node for the input instruction
+ ModuloSchedGraphNode* getGraphNodeForInst(const Instruction* inst) const{
+ const_iterator onePair = this->find(inst);
+ return (onePair != this->end())?(*onePair).second: NULL;
+ }
+
+ //Debugging support
+ //dump the graph
+ void dump() const;
+ //dump the basicBlock
+ void dump(const BasicBlock* bb);
+ //dump the basicBlock into 'os' stream
+ void dump(const BasicBlock* bb, std::ostream& os);
+ //dump the node property
+ void dumpNodeProperty() const ;
+
+ private:
+ friend class ModuloSchedGraphSet; //give access to ctor
+
+ public:
+ /*ctr*/
+ ModuloSchedGraph(const BasicBlock* bb, const TargetMachine& _target)
+ :SchedGraphCommon(bb), target(_target){
+ buildGraph(target);
+ }
+
+ /*dtr*/
+ ~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;
+
+
+
+ inline void noteModuloSchedGraphNodeForInst(const Instruction* inst,
+ ModuloSchedGraphNode* node)
+ {
+ assert((*this)[inst] ==NULL);
+ (*this)[inst]=node;
+ }
+
+ //Graph builder
+
+ ModuloSchedGraphNode* getNode (const unsigned nodeId) const;
+
+ //build the graph from the basicBlock
+ void buildGraph (const TargetMachine& target);
+
+ //Build nodes for BasicBlock
+ void buildNodesforBB (const TargetMachine& target,
+ const BasicBlock* bb,
+ NodeVec& memNode,
+ RegToRefVecMap& regToRefVecMap,
+ ValueToDefVecMap& valueToDefVecMap);
+
+ //find definitiona and use information for all nodes
+ void findDefUseInfoAtInstr (const TargetMachine& target,
+ ModuloSchedGraphNode* node,
+ NodeVec& memNode,
+ RegToRefVecMap& regToRefVecMap,
+ ValueToDefVecMap& valueToDefVecMap);
+
+ //add def-use edge
+ void addDefUseEdges (const BasicBlock* bb);
+
+ //add control dependence edges
+ void addCDEdges (const BasicBlock* bb);
+
+ //add memory dependence dges
+ void addMemEdges (const BasicBlock* bb);
+
+ //add dummy edges
+ void addDummyEdges();
+
+ //computer source restrictoin II
+ int computeResII (const BasicBlock* bb);
+
+ //computer recurrence II
+ int computeRecII (const BasicBlock* bb);
+};
+
+///==================================-
+//gragh set
+
+class ModuloSchedGraphSet:
+ public std::vector<ModuloSchedGraph*>
+{
+private:
+ 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
+ using baseVector::begin;
+ using baseVector::end;
+
+
+ //Debugging support
+ void dump() const;
+
+private:
+ inline void addGraph(ModuloSchedGraph* graph){
+ assert(graph !=NULL);
+ this->push_back(graph);
+ }
+
+ //Graph builder
+ void buildGraphsForMethod (const Function *F, const TargetMachine& target);
+};
+
+#endif