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/HashExtras.h"
  15 #include "Support/GraphTraits.h"
  16 #include "Support/hash_map"
  17 #include "../InstrSched/SchedGraphCommon.h"
  18 #include <iostream>
  19
  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
  24 //
  25 class ModuloSchedGraphNode:public SchedGraphNodeCommon {
  26 private:
  27   // the corresponding instruction
  28   const Instruction *inst;
  29
  30   // whether this node's property(ASAP,ALAP, ...) has been computed
  31   bool propertyComputed;
  32
  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;
  42   int schTime;
  43   int earlyStart, lateStart;
  44
  45 public:
  46
  47   //get the instruction
  48   const Instruction *getInst() const {
  49     return inst;
  50   }
  51   //get the instruction op-code name
  52   const char *getInstOpcodeName() const {
  53     return inst->getOpcodeName();
  54   }
  55   //get the instruction op-code
  56   const unsigned getInstOpcode() const {
  57     return inst->getOpcode();
  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   //iteration Interval
 142   int MII;
 143
 144   //target machine
 145   const TargetMachine & target;
 146
 147   //the circuits in the dependence graph
 148   unsigned circuits[MAXCC][MAXNODE];
 149
 150   //the order nodes
 151   std::vector<ModuloSchedGraphNode*> oNodes;
 152
 153   typedef std::vector<ModuloSchedGraphNode*> NodeVec;
 154
 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);
 161
 162   //the function to compute node property
 163   void computeNodeProperty(const BasicBlock *bb);
 164
 165   //the function to sort nodes
 166   void orderNodes();
 167
 168   //add the resource usage
 169 void addResourceUsage(std::vector<std::pair<int,int> > &, int);
 170
 171   //debug functions:
 172   //dump circuits
 173   void dumpCircuits();
 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> > &);
 178
 179 public:
 180   //help functions
 181
 182   //get the maxium the delay between two nodes
 183   SchedGraphEdge *getMaxDelayEdge(unsigned srcId, unsigned sinkId);
 184
 185   //FIXME:
 186   //get the predessor Set of the set
 187   NodeVec predSet(NodeVec set, unsigned, unsigned);
 188   NodeVec predSet(NodeVec set);
 189
 190   //get the predessor set of the node
 191   NodeVec predSet(ModuloSchedGraphNode *node, unsigned, unsigned);
 192   NodeVec predSet(ModuloSchedGraphNode *node);
 193
 194   //get the successor set of the set
 195   NodeVec succSet(NodeVec set, unsigned, unsigned);
 196   NodeVec succSet(NodeVec set);
 197
 198   //get the succssor set of the node
 199   NodeVec succSet(ModuloSchedGraphNode *node, unsigned, unsigned);
 200   NodeVec succSet(ModuloSchedGraphNode *node);
 201
 202   //return the uniton of the two vectors
 203   NodeVec vectorUnion(NodeVec set1, NodeVec set2);
 204
 205   //return the consjuction of the two vectors
 206   NodeVec vectorConj(NodeVec set1, NodeVec set2);
 207
 208   //return all nodes in  set1 but not  set2
 209   NodeVec vectorSub(NodeVec set1, NodeVec set2);
 210
 211   typedef hash_map<const Instruction*,ModuloSchedGraphNode*> map_base;
 212
 213 public:
 214   using map_base::iterator;
 215   using map_base::const_iterator;
 216
 217 public:
 218
 219   //get target machine
 220   const TargetMachine & getTarget() {
 221     return target;
 222   }
 223   //get the iteration interval
 224   const int getMII() {
 225     return MII;
 226   }
 227
 228   //get the ordered nodes
 229   const NodeVec & getONodes() {
 230     return oNodes;
 231   }
 232
 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 {
 236     return size() + 2;
 237   }
 238   //return wether the BasicBlock 'bb' contains a loop
 239   bool isLoop(const BasicBlock * bb);
 240
 241   //return this basibBlock contains a loop
 242   bool isLoop();
 243
 244   //return the node for the input instruction
 245   ModuloSchedGraphNode *getGraphNodeForInst(const Instruction * inst) const {
 246     const_iterator onePair = this->find(inst);
 247     return (onePair != this->end()) ? (*onePair).second : NULL;
 248   }
 249
 250   // Debugging support
 251   //dump the graph
 252   void dump() const;
 253
 254   // dump the basicBlock
 255   void dump(const BasicBlock * bb);
 256
 257   //dump the basicBlock into 'os' stream
 258   void dump(const BasicBlock * bb, std::ostream & os);
 259
 260   //dump the node property
 261   void dumpNodeProperty() const;
 262
 263 private:
 264   friend class ModuloSchedGraphSet;     //give access to ctor
 265
 266 public:
 267   ModuloSchedGraph(const BasicBlock *bb, const TargetMachine &_target)
 268     :SchedGraphCommon(bb), target(_target)
 269   {
 270     buildGraph(target);
 271   }
 272
 273   ~ModuloSchedGraph() {
 274     for (const_iterator I = begin(); I != end(); ++I)
 275       delete I->second;
 276   }
 277
 278   // Unorder iterators
 279   // return values are pair<const Instruction*, ModuloSchedGraphNode*>
 280   using map_base::begin;
 281   using map_base::end;
 282
 283   void noteModuloSchedGraphNodeForInst(const Instruction *inst,
 284                                        ModuloSchedGraphNode *node)
 285   {
 286     assert((*this)[inst] == NULL);
 287     (*this)[inst] = node;
 288   }
 289
 290   //Graph builder
 291
 292   ModuloSchedGraphNode *getNode(const unsigned nodeId) const;
 293
 294   //build the graph from the basicBlock
 295   void buildGraph(const TargetMachine & target);
 296
 297   //Build nodes for BasicBlock
 298   void buildNodesforBB(const TargetMachine &target,
 299                        const BasicBlock *bb,
 300                        NodeVec &memNode,
 301                        RegToRefVecMap &regToRefVecMap,
 302                        ValueToDefVecMap &valueToDefVecMap);
 303
 304   //find definitiona and use information for all nodes
 305   void findDefUseInfoAtInstr(const TargetMachine &target,
 306                              ModuloSchedGraphNode *node,
 307                              NodeVec &memNode,
 308                              RegToRefVecMap &regToRefVecMap,
 309                              ValueToDefVecMap &valueToDefVecMap);
 310
 311   //add def-use edge
 312   void addDefUseEdges(const BasicBlock *bb);
 313
 314   //add control dependence edges
 315   void addCDEdges(const BasicBlock *bb);
 316
 317   //add memory dependence dges
 318   void addMemEdges(const BasicBlock *bb);
 319
 320   //add dummy edges
 321   void addDummyEdges();
 322
 323   //computer source restrictoin II
 324   int computeResII(const BasicBlock *bb);
 325
 326   //computer recurrence II
 327   int computeRecII(const BasicBlock *bb);
 328 };
 329
 330 //==================================-
 331 // Graph set
 332
 333 class ModuloSchedGraphSet : public std::vector<ModuloSchedGraph*> {
 334 private:
 335   const Function *method;
 336
 337 public:
 338   typedef std::vector<ModuloSchedGraph*> baseVector;
 339   using baseVector::iterator;
 340   using baseVector::const_iterator;
 341
 342 public:
 343   ModuloSchedGraphSet(const Function *function, const TargetMachine &target);
 344   ~ModuloSchedGraphSet();
 345
 346   // Iterators
 347   using baseVector::begin;
 348   using baseVector::end;
 349
 350   // Debugging support
 351   void dump() const;
 352
 353 private:
 354   void addGraph(ModuloSchedGraph *graph) {
 355     assert(graph != NULL);
 356     this->push_back(graph);
 357   }
 358
 359   // Graph builder
 360   void buildGraphsForMethod(const Function *F,
 361                             const TargetMachine &target);
 362 };
 363
 364 #endif