1 //===- ModuloSchedGraph.h - Modulo Scheduling Graph and Set -*- C++ -*-----===//
3 // This header defines the primative classes that make up a data structure
6 //===----------------------------------------------------------------------===//
8 #ifndef LLVM_CODEGEN_MODULO_SCHED_GRAPH_H
9 #define LLVM_CODEGEN_MODULO_SCHED_GRAPH_H
11 #include "llvm/Instruction.h"
12 #include "llvm/Target/TargetMachine.h"
13 #include "llvm/Target/TargetInstrInfo.h"
14 #include "Support/HashExtras.h"
15 #include "Support/GraphTraits.h"
16 #include "Support/hash_map"
17 #include "../InstrSched/SchedGraphCommon.h"
20 //===----------------------------------------------------------------------===//
21 // ModuloSchedGraphNode - Implement a data structure based on the
22 // SchedGraphNodeCommon this class stores informtion needed later to order the
23 // nodes in modulo scheduling
25 class ModuloSchedGraphNode:public SchedGraphNodeCommon {
27 // the corresponding instruction
28 const Instruction *inst;
30 // whether this node's property(ASAP,ALAP, ...) has been computed
31 bool propertyComputed;
33 // ASAP: the earliest time the node could be scheduled
34 // ALAP: the latest time the node couldbe scheduled
35 // depth: the depth of the node
36 // height: the height of the node
37 // mov: the mobility function, computed as ALAP - ASAP
38 // scheTime: the scheduled time if this node has been scheduled
39 // earlyStart: the earliest time to be tried to schedule the node
40 // lateStart: the latest time to be tried to schedule the node
41 int ASAP, ALAP, depth, height, mov;
43 int earlyStart, lateStart;
48 const Instruction *getInst() const {
51 //get the instruction op-code name
52 const char *getInstOpcodeName() const {
53 return inst->getOpcodeName();
55 //get the instruction op-code
56 const unsigned getInstOpcode() const {
57 return inst->getOpcode();
59 //return whether the node is NULL
60 bool isNullNode() const {
61 return (inst == NULL);
63 //return whether the property of the node has been computed
64 bool getPropertyComputed() {
65 return propertyComputed;
67 //set the propertyComputed
68 void setPropertyComputed(bool _propertyComputed) {
69 propertyComputed = _propertyComputed;
72 //get the corresponding property
97 void setEarlyStart(int _earlyStart) {
98 earlyStart = _earlyStart;
100 void setLateStart(int _lateStart) {
101 lateStart = _lateStart;
103 void setSchTime(int _time) {
108 friend class ModuloSchedGraph;
109 friend class SchedGraphNode;
112 //nodeId: the node id, unique within the each BasicBlock
113 //_bb: which BasicBlock the corresponding instruction belongs to
114 //_inst: the corresponding instruction
115 //indexInBB: the corresponding instruction's index in the BasicBlock
116 //target: the targetMachine
117 ModuloSchedGraphNode(unsigned int _nodeId,
118 const BasicBlock * _bb,
119 const Instruction * _inst,
120 int indexInBB, const TargetMachine &target);
123 friend std::ostream & operator<<(std::ostream & os,
124 const ModuloSchedGraphNode & edge);
128 //FIXME: these two value should not be used
132 //===----------------------------------------------------------------------===//
133 /// ModuloSchedGraph- the data structure to store dependence between nodes
134 /// it catches data dependence and constrol dependence
136 class ModuloSchedGraph :
137 public SchedGraphCommon,
138 protected hash_map<const Instruction*,ModuloSchedGraphNode*> {
145 const TargetMachine & target;
147 //the circuits in the dependence graph
148 unsigned circuits[MAXCC][MAXNODE];
151 std::vector<ModuloSchedGraphNode*> oNodes;
153 typedef std::vector<ModuloSchedGraphNode*> NodeVec;
155 //the function to compute properties
156 void computeNodeASAP(const BasicBlock *bb);
157 void computeNodeALAP(const BasicBlock *bb);
158 void computeNodeMov(const BasicBlock *bb);
159 void computeNodeDepth(const BasicBlock *bb);
160 void computeNodeHeight(const BasicBlock *bb);
162 //the function to compute node property
163 void computeNodeProperty(const BasicBlock *bb);
165 //the function to sort nodes
168 //add the resource usage
169 void addResourceUsage(std::vector<std::pair<int,int> > &, int);
174 //dump the input set of nodes
175 void dumpSet(std::vector<ModuloSchedGraphNode*> set);
176 //dump the input resource usage table
177 void dumpResourceUsage(std::vector<std::pair<int,int> > &);
182 //get the maxium the delay between two nodes
183 SchedGraphEdge *getMaxDelayEdge(unsigned srcId, unsigned sinkId);
186 //get the predessor Set of the set
187 NodeVec predSet(NodeVec set, unsigned, unsigned);
188 NodeVec predSet(NodeVec set);
190 //get the predessor set of the node
191 NodeVec predSet(ModuloSchedGraphNode *node, unsigned, unsigned);
192 NodeVec predSet(ModuloSchedGraphNode *node);
194 //get the successor set of the set
195 NodeVec succSet(NodeVec set, unsigned, unsigned);
196 NodeVec succSet(NodeVec set);
198 //get the succssor set of the node
199 NodeVec succSet(ModuloSchedGraphNode *node, unsigned, unsigned);
200 NodeVec succSet(ModuloSchedGraphNode *node);
202 //return the uniton of the two vectors
203 NodeVec vectorUnion(NodeVec set1, NodeVec set2);
205 //return the consjuction of the two vectors
206 NodeVec vectorConj(NodeVec set1, NodeVec set2);
208 //return all nodes in set1 but not set2
209 NodeVec vectorSub(NodeVec set1, NodeVec set2);
211 typedef hash_map<const Instruction*,ModuloSchedGraphNode*> map_base;
214 using map_base::iterator;
215 using map_base::const_iterator;
220 const TargetMachine & getTarget() {
223 //get the iteration interval
228 //get the ordered nodes
229 const NodeVec & getONodes() {
233 //get the number of nodes (including the root and leaf)
234 //note: actually root and leaf is not used
235 const unsigned int getNumNodes() const {
239 //return wether the BasicBlock 'bb' contains a loop
240 bool isLoop(const BasicBlock *bb);
242 //return this basibBlock contains a loop
245 //return the node for the input instruction
246 ModuloSchedGraphNode *getGraphNodeForInst(const Instruction *inst) const {
247 const_iterator onePair = this->find(inst);
248 return (onePair != this->end()) ? (*onePair).second : NULL;
255 // dump the basicBlock
256 void dump(const BasicBlock *bb);
258 //dump the basicBlock into 'os' stream
259 void dump(const BasicBlock *bb, std::ostream &os);
261 //dump the node property
262 void dumpNodeProperty() const;
265 friend class ModuloSchedGraphSet; //give access to ctor
268 ModuloSchedGraph(const BasicBlock *bb, const TargetMachine &_target)
269 :SchedGraphCommon(bb), target(_target)
274 ~ModuloSchedGraph() {
275 for (const_iterator I = begin(); I != end(); ++I)
280 // return values are pair<const Instruction*, ModuloSchedGraphNode*>
281 using map_base::begin;
284 void noteModuloSchedGraphNodeForInst(const Instruction *inst,
285 ModuloSchedGraphNode *node)
287 assert((*this)[inst] == NULL);
288 (*this)[inst] = node;
292 ModuloSchedGraphNode *getNode(const unsigned nodeId) const;
294 // Build the graph from the basicBlock
295 void buildGraph(const TargetMachine &target);
297 // Build nodes for BasicBlock
298 void buildNodesforBB(const TargetMachine &target,
299 const BasicBlock *bb,
301 RegToRefVecMap ®ToRefVecMap,
302 ValueToDefVecMap &valueToDefVecMap);
304 //find definitiona and use information for all nodes
305 void findDefUseInfoAtInstr(const TargetMachine &target,
306 ModuloSchedGraphNode *node,
308 RegToRefVecMap ®ToRefVecMap,
309 ValueToDefVecMap &valueToDefVecMap);
312 void addDefUseEdges(const BasicBlock *bb);
314 //add control dependence edges
315 void addCDEdges(const BasicBlock *bb);
317 //add memory dependence dges
318 void addMemEdges(const BasicBlock *bb);
321 void addDummyEdges();
323 //computer source restrictoin II
324 int computeResII(const BasicBlock *bb);
326 //computer recurrence II
327 int computeRecII(const BasicBlock *bb);
330 //==================================-
333 class ModuloSchedGraphSet : public std::vector<ModuloSchedGraph*> {
335 const Function *method;
338 typedef std::vector<ModuloSchedGraph*> baseVector;
339 using baseVector::iterator;
340 using baseVector::const_iterator;
343 ModuloSchedGraphSet(const Function *function, const TargetMachine &target);
344 ~ModuloSchedGraphSet();
347 using baseVector::begin;
348 using baseVector::end;
354 void addGraph(ModuloSchedGraph *graph) {
355 assert(graph != NULL);
356 this->push_back(graph);
360 void buildGraphsForMethod(const Function *F,
361 const TargetMachine &target);