lib/CodeGen/ModuloScheduling/ModuloSchedGraph.h

   1 //===- ModuloSchedGraph.h - Modulo Scheduling Graph and Set -*- C++ -*-----===//
   2 //
   3 // This header defines the primative classes that make up a data structure
   4 // graph.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #ifndef LLVM_CODEGEN_MODULO_SCHED_GRAPH_H
   9 #define LLVM_CODEGEN_MODULO_SCHED_GRAPH_H
  10
  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"
  17 #include <iostream>
  18
  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
  23 //
  24 class ModuloSchedGraphNode:public SchedGraphNodeCommon {
  25 private:
  26   // the corresponding instruction
  27   const Instruction *inst;
  28
  29   // whether this node's property(ASAP,ALAP, ...) has been computed
  30   bool propertyComputed;
  31
  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;
  41   int schTime;
  42   int earlyStart, lateStart;
  43
  44 public:
  45
  46   //get the instruction
  47   const Instruction *getInst() const {
  48     return inst;
  49   }
  50   //get the instruction op-code name
  51   const char *getInstOpcodeName() const {
  52     return inst->getOpcodeName();
  53   }
  54   //get the instruction op-code
  55   const unsigned getInstOpcode() const {
  56     return inst->getOpcode();
  57   }
  58
  59   //return whether the node is NULL
  60   bool isNullNode() const {
  61     return (inst == NULL);
  62   }
  63   //return whether the property of the node has been computed
  64   bool getPropertyComputed() {
  65     return propertyComputed;
  66   }
  67   //set the propertyComputed
  68   void setPropertyComputed(bool _propertyComputed) {
  69     propertyComputed = _propertyComputed;
  70   }
  71
  72   //get the corresponding property
  73   int getASAP() {
  74     return ASAP;
  75   }
  76   int getALAP() {
  77     return ALAP;
  78   }
  79   int getMov() {
  80     return mov;
  81   }
  82   int getDepth() {
  83     return depth;
  84   }
  85   int getHeight() {
  86     return height;
  87   }
  88   int getSchTime() {
  89     return schTime;
  90   }
  91   int getEarlyStart() {
  92     return earlyStart;
  93   }
  94   int getLateStart() {
  95     return lateStart;
  96   }
  97   void setEarlyStart(int _earlyStart) {
  98     earlyStart = _earlyStart;
  99   }
 100   void setLateStart(int _lateStart) {
 101     lateStart = _lateStart;
 102   }
 103   void setSchTime(int _time) {
 104     schTime = _time;
 105   }
 106
 107 private:
 108   friend class ModuloSchedGraph;
 109   friend class SchedGraphNode;
 110
 111   //constructor:
 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);
 121
 122
 123   friend std::ostream & operator<<(std::ostream & os,
 124                                    const ModuloSchedGraphNode & edge);
 125
 126 };
 127
 128 //FIXME: these two value should not be used
 129 #define MAXNODE 100
 130 #define MAXCC   100
 131
 132 //===----------------------------------------------------------------------===//
 133 /// ModuloSchedGraph- the data structure to store dependence between nodes
 134 /// it catches data dependence and constrol dependence
 135 ///
 136 class ModuloSchedGraph :
 137   public SchedGraphCommon,
 138   protected hash_map<const Instruction*,ModuloSchedGraphNode*> {
 139
 140 private:
 141
 142   BasicBlock* bb;
 143
 144   //iteration Interval
 145   int MII;
 146
 147   //target machine
 148   const TargetMachine & target;
 149
 150   //the circuits in the dependence graph
 151   unsigned circuits[MAXCC][MAXNODE];
 152
 153   //the order nodes
 154   std::vector<ModuloSchedGraphNode*> oNodes;
 155
 156   typedef std::vector<ModuloSchedGraphNode*> NodeVec;
 157
 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);
 164
 165   //the function to compute node property
 166   void computeNodeProperty(const BasicBlock * in_bb);
 167
 168   //the function to sort nodes
 169   void orderNodes();
 170
 171   //add the resource usage
 172 void addResourceUsage(std::vector<std::pair<int,int> > &, int);
 173
 174   //debug functions:
 175   //dump circuits
 176   void dumpCircuits();
 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> > &);
 181
 182 public:
 183   //help functions
 184
 185   //get the maxium the delay between two nodes
 186   SchedGraphEdge *getMaxDelayEdge(unsigned srcId, unsigned sinkId);
 187
 188   //FIXME:
 189   //get the predessor Set of the set
 190   NodeVec predSet(NodeVec set, unsigned, unsigned);
 191   NodeVec predSet(NodeVec set);
 192
 193   //get the predessor set of the node
 194   NodeVec predSet(ModuloSchedGraphNode *node, unsigned, unsigned);
 195   NodeVec predSet(ModuloSchedGraphNode *node);
 196
 197   //get the successor set of the set
 198   NodeVec succSet(NodeVec set, unsigned, unsigned);
 199   NodeVec succSet(NodeVec set);
 200
 201   //get the succssor set of the node
 202   NodeVec succSet(ModuloSchedGraphNode *node, unsigned, unsigned);
 203   NodeVec succSet(ModuloSchedGraphNode *node);
 204
 205   //return the uniton of the two vectors
 206   NodeVec vectorUnion(NodeVec set1, NodeVec set2);
 207
 208   //return the consjuction of the two vectors
 209   NodeVec vectorConj(NodeVec set1, NodeVec set2);
 210
 211   //return all nodes in  set1 but not  set2
 212   NodeVec vectorSub(NodeVec set1, NodeVec set2);
 213
 214   typedef hash_map<const Instruction*,ModuloSchedGraphNode*> map_base;
 215
 216 public:
 217   using map_base::iterator;
 218   using map_base::const_iterator;
 219
 220 public:
 221
 222   //get target machine
 223   const TargetMachine & getTarget() {
 224     return target;
 225   }
 226
 227   //get the basic block
 228   BasicBlock* getBasicBlock() const {
 229     return bb;
 230   }
 231
 232
 233   //get the iteration interval
 234   const int getMII() {
 235     return MII;
 236   }
 237
 238   //get the ordered nodes
 239   const NodeVec & getONodes() {
 240     return oNodes;
 241   }
 242
 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 {
 246     return size() + 2;
 247   }
 248
 249   //return wether the BasicBlock 'bb' contains a loop
 250   bool isLoop(const BasicBlock *bb);
 251
 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;
 256   }
 257
 258   // Debugging support
 259   //dump the graph
 260   void dump() const;
 261
 262   // dump the basicBlock
 263   void dump(const BasicBlock *bb);
 264
 265   //dump the basicBlock into 'os' stream
 266   void dump(const BasicBlock *bb, std::ostream &os);
 267
 268   //dump the node property
 269   void dumpNodeProperty() const;
 270
 271 private:
 272   friend class ModuloSchedGraphSet;     //give access to ctor
 273
 274 public:
 275   ModuloSchedGraph(BasicBlock * in_bb,
 276                    const TargetMachine & in_target)
 277     :SchedGraphCommon(), bb(in_bb),target(in_target)
 278   {
 279     buildGraph(target);
 280   }
 281
 282   ~ModuloSchedGraph() {
 283     for (const_iterator I = begin(); I != end(); ++I)
 284       delete I->second;
 285   }
 286
 287   // Unorder iterators
 288   // return values are pair<const Instruction*, ModuloSchedGraphNode*>
 289   using map_base::begin;
 290   using map_base::end;
 291
 292   void addHash(const Instruction *inst,
 293                ModuloSchedGraphNode *node){
 294
 295     assert((*this)[inst] == NULL);
 296     (*this)[inst] = node;
 297
 298   }
 299
 300   // Graph builder
 301   ModuloSchedGraphNode *getNode(const unsigned nodeId) const;
 302
 303   // Build the graph from the basicBlock
 304   void buildGraph(const TargetMachine &target);
 305
 306   // Build nodes for BasicBlock
 307   void buildNodesforBB(const TargetMachine &target,
 308                        const BasicBlock *bb);
 309
 310   //find definitiona and use information for all nodes
 311   void findDefUseInfoAtInstr(const TargetMachine &target,
 312                              ModuloSchedGraphNode *node,
 313                              NodeVec &memNode,
 314                              RegToRefVecMap &regToRefVecMap,
 315                              ValueToDefVecMap &valueToDefVecMap);
 316
 317   //add def-use edge
 318   void addDefUseEdges(const BasicBlock *bb);
 319
 320   //add control dependence edges
 321   void addCDEdges(const BasicBlock *bb);
 322
 323   //add memory dependence dges
 324   void addMemEdges(const BasicBlock *bb);
 325
 326   //computer source restrictoin II
 327   int computeResII(const BasicBlock *bb);
 328
 329   //computer recurrence II
 330   int computeRecII(const BasicBlock *bb);
 331 };
 332
 333 //==================================-
 334 // Graph set
 335
 336 class ModuloSchedGraphSet : public std::vector<ModuloSchedGraph*> {
 337 private:
 338   const Function *method;
 339
 340 public:
 341   typedef std::vector<ModuloSchedGraph*> baseVector;
 342   using baseVector::iterator;
 343   using baseVector::const_iterator;
 344
 345 public:
 346   ModuloSchedGraphSet(const Function *function, const TargetMachine &target);
 347   ~ModuloSchedGraphSet();
 348
 349   // Iterators
 350   using baseVector::begin;
 351   using baseVector::end;
 352
 353   // Debugging support
 354   void dump() const;
 355
 356 private:
 357   void addGraph(ModuloSchedGraph *graph) {
 358     assert(graph != NULL);
 359     this->push_back(graph);
 360   }
 361
 362   // Graph builder
 363   void buildGraphsForMethod(const Function *F,
 364                             const TargetMachine &target);
 365 };
 366
 367 #endif