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/GraphTraits.h"
15 #include "Support/hash_map"
16 #include "../InstrSched/SchedGraphCommon.h"
19 //===----------------------------------------------------------------------===//
20 // ModuloSchedGraphNode - Implement a data structure based on the
21 // SchedGraphNodeCommon this class stores informtion needed later to order the
22 // nodes in modulo scheduling
24 class ModuloSchedGraphNode:public SchedGraphNodeCommon {
26 // the corresponding instruction
27 const Instruction *inst;
29 // whether this node's property(ASAP,ALAP, ...) has been computed
30 bool propertyComputed;
32 // ASAP: the earliest time the node could be scheduled
33 // ALAP: the latest time the node couldbe scheduled
34 // depth: the depth of the node
35 // height: the height of the node
36 // mov: the mobility function, computed as ALAP - ASAP
37 // scheTime: the scheduled time if this node has been scheduled
38 // earlyStart: the earliest time to be tried to schedule the node
39 // lateStart: the latest time to be tried to schedule the node
40 int ASAP, ALAP, depth, height, mov;
42 int earlyStart, lateStart;
47 const Instruction *getInst() const {
50 //get the instruction op-code name
51 const char *getInstOpcodeName() const {
52 return inst->getOpcodeName();
54 //get the instruction op-code
55 const unsigned getInstOpcode() const {
56 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*> {
148 const TargetMachine & target;
150 //the circuits in the dependence graph
151 unsigned circuits[MAXCC][MAXNODE];
154 std::vector<ModuloSchedGraphNode*> oNodes;
156 typedef std::vector<ModuloSchedGraphNode*> NodeVec;
158 //the function to compute properties
159 void computeNodeASAP(const BasicBlock * in_bb);
160 void computeNodeALAP(const BasicBlock * in_bb);
161 void computeNodeMov(const BasicBlock * in_bb);
162 void computeNodeDepth(const BasicBlock * in_bb);
163 void computeNodeHeight(const BasicBlock * in_bb);
165 //the function to compute node property
166 void computeNodeProperty(const BasicBlock * in_bb);
168 //the function to sort nodes
171 //add the resource usage
172 void addResourceUsage(std::vector<std::pair<int,int> > &, int);
177 //dump the input set of nodes
178 void dumpSet(std::vector<ModuloSchedGraphNode*> set);
179 //dump the input resource usage table
180 void dumpResourceUsage(std::vector<std::pair<int,int> > &);
185 //get the maxium the delay between two nodes
186 SchedGraphEdge *getMaxDelayEdge(unsigned srcId, unsigned sinkId);
189 //get the predessor Set of the set
190 NodeVec predSet(NodeVec set, unsigned, unsigned);
191 NodeVec predSet(NodeVec set);
193 //get the predessor set of the node
194 NodeVec predSet(ModuloSchedGraphNode *node, unsigned, unsigned);
195 NodeVec predSet(ModuloSchedGraphNode *node);
197 //get the successor set of the set
198 NodeVec succSet(NodeVec set, unsigned, unsigned);
199 NodeVec succSet(NodeVec set);
201 //get the succssor set of the node
202 NodeVec succSet(ModuloSchedGraphNode *node, unsigned, unsigned);
203 NodeVec succSet(ModuloSchedGraphNode *node);
205 //return the uniton of the two vectors
206 NodeVec vectorUnion(NodeVec set1, NodeVec set2);
208 //return the consjuction of the two vectors
209 NodeVec vectorConj(NodeVec set1, NodeVec set2);
211 //return all nodes in set1 but not set2
212 NodeVec vectorSub(NodeVec set1, NodeVec set2);
214 typedef hash_map<const Instruction*,ModuloSchedGraphNode*> map_base;
217 using map_base::iterator;
218 using map_base::const_iterator;
223 const TargetMachine & getTarget() {
227 //get the basic block
228 BasicBlock* getBasicBlock() const {
233 //get the iteration interval
238 //get the ordered nodes
239 const NodeVec & getONodes() {
243 //get the number of nodes (including the root and leaf)
244 //note: actually root and leaf is not used
245 const unsigned int getNumNodes() const {
249 //return wether the BasicBlock 'bb' contains a loop
250 bool isLoop(const BasicBlock *bb);
252 //return the node for the input instruction
253 ModuloSchedGraphNode *getGraphNodeForInst(const Instruction *inst) const {
254 const_iterator onePair = this->find(inst);
255 return (onePair != this->end()) ? (*onePair).second : NULL;
262 // dump the basicBlock
263 void dump(const BasicBlock *bb);
265 //dump the basicBlock into 'os' stream
266 void dump(const BasicBlock *bb, std::ostream &os);
268 //dump the node property
269 void dumpNodeProperty() const;
272 friend class ModuloSchedGraphSet; //give access to ctor
275 ModuloSchedGraph(BasicBlock * in_bb,
276 const TargetMachine & in_target)
277 :SchedGraphCommon(), bb(in_bb),target(in_target)
282 ~ModuloSchedGraph() {
283 for (const_iterator I = begin(); I != end(); ++I)
288 // return values are pair<const Instruction*, ModuloSchedGraphNode*>
289 using map_base::begin;
292 void addHash(const Instruction *inst,
293 ModuloSchedGraphNode *node){
295 assert((*this)[inst] == NULL);
296 (*this)[inst] = node;
301 ModuloSchedGraphNode *getNode(const unsigned nodeId) const;
303 // Build the graph from the basicBlock
304 void buildGraph(const TargetMachine &target);
306 // Build nodes for BasicBlock
307 void buildNodesforBB(const TargetMachine &target,
308 const BasicBlock *bb);
310 //find definitiona and use information for all nodes
311 void findDefUseInfoAtInstr(const TargetMachine &target,
312 ModuloSchedGraphNode *node,
314 RegToRefVecMap ®ToRefVecMap,
315 ValueToDefVecMap &valueToDefVecMap);
318 void addDefUseEdges(const BasicBlock *bb);
320 //add control dependence edges
321 void addCDEdges(const BasicBlock *bb);
323 //add memory dependence dges
324 void addMemEdges(const BasicBlock *bb);
326 //computer source restrictoin II
327 int computeResII(const BasicBlock *bb);
329 //computer recurrence II
330 int computeRecII(const BasicBlock *bb);
333 //==================================-
336 class ModuloSchedGraphSet : public std::vector<ModuloSchedGraph*> {
338 const Function *method;
341 typedef std::vector<ModuloSchedGraph*> baseVector;
342 using baseVector::iterator;
343 using baseVector::const_iterator;
346 ModuloSchedGraphSet(const Function *function, const TargetMachine &target);
347 ~ModuloSchedGraphSet();
350 using baseVector::begin;
351 using baseVector::end;
357 void addGraph(ModuloSchedGraph *graph) {
358 assert(graph != NULL);
359 this->push_back(graph);
363 void buildGraphsForMethod(const Function *F,
364 const TargetMachine &target);