lib/Target/SparcV9/InstrSched/SchedGraph.h

   1 //===-- SchedGraph.h - Scheduling Graph --------------------------*- C++ -*--=//
   2 //
   3 // Purpose:
   4 //      Scheduling graph based on SSA graph plus extra dependence edges
   5 //      capturing dependences due to machine resources (machine registers,
   6 //      CC registers, and any others).
   7 //
   8 // Strategy:
   9 //      This graph tries to leverage the SSA graph as much as possible,
  10 //      but captures the extra dependences through a common interface.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CODEGEN_SCHEDGRAPH_H
  15 #define LLVM_CODEGEN_SCHEDGRAPH_H
  16
  17 #include "llvm/CodeGen/MachineInstr.h"
  18 #include "Support/GraphTraits.h"
  19
  20 class Value;
  21 class Instruction;
  22 class TerminatorInst;
  23 class BasicBlock;
  24 class Function;
  25 class TargetMachine;
  26 class SchedGraphEdge;
  27 class SchedGraphNode;
  28 class SchedGraph;
  29 class RegToRefVecMap;
  30 class ValueToDefVecMap;
  31 class RefVec;
  32 class MachineInstr;
  33 class MachineBasicBlock;
  34
  35
  36 /******************** Exported Data Types and Constants ********************/
  37
  38 typedef int ResourceId;
  39 const ResourceId InvalidRID        = -1;
  40 const ResourceId MachineCCRegsRID  = -2; // use +ve numbers for actual regs
  41 const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
  42 const ResourceId MachineFPRegsRID  = -4; // use +ve numbers for actual regs
  43
  44
  45 //*********************** Public Class Declarations ************************/
  46
  47 class SchedGraphEdge {
  48   SchedGraphEdge(const SchedGraphEdge &);  // DO NOT IMPLEMENT
  49   void operator=(const SchedGraphEdge &);  // DO NOT IMPLEMENT
  50 public:
  51   enum SchedGraphEdgeDepType {
  52     CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
  53   };
  54   enum DataDepOrderType {
  55     TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
  56   };
  57
  58 private:
  59   SchedGraphNode*       src;
  60   SchedGraphNode*       sink;
  61   SchedGraphEdgeDepType depType;
  62   unsigned int          depOrderType;
  63   int                   minDelay; // cached latency (assumes fixed target arch)
  64
  65   union {
  66     const Value* val;
  67     int          machineRegNum;
  68     ResourceId   resourceId;
  69   };
  70
  71 public:
  72   // For all constructors, if minDelay is unspecified, minDelay is
  73   // set to _src->getLatency().
  74   // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
  75   /*ctor*/              SchedGraphEdge(SchedGraphNode* _src,
  76                                        SchedGraphNode* _sink,
  77                                        SchedGraphEdgeDepType _depType,
  78                                        unsigned int     _depOrderType,
  79                                        int _minDelay = -1);
  80
  81   // constructor for explicit value dependence (may be true/anti/output)
  82   /*ctor*/              SchedGraphEdge(SchedGraphNode* _src,
  83                                        SchedGraphNode* _sink,
  84                                        const Value*    _val,
  85                                        unsigned int     _depOrderType,
  86                                        int _minDelay = -1);
  87
  88   // constructor for machine register dependence
  89   /*ctor*/              SchedGraphEdge(SchedGraphNode* _src,
  90                                        SchedGraphNode* _sink,
  91                                        unsigned int    _regNum,
  92                                        unsigned int     _depOrderType,
  93                                        int _minDelay = -1);
  94
  95   // constructor for any other machine resource dependences.
  96   // DataDepOrderType is always NonDataDep.  It it not an argument to
  97   // avoid overloading ambiguity with previous constructor.
  98   /*ctor*/              SchedGraphEdge(SchedGraphNode* _src,
  99                                        SchedGraphNode* _sink,
 100                                        ResourceId      _resourceId,
 101                                        int _minDelay = -1);
 102
 103   /*dtor*/              ~SchedGraphEdge();
 104
 105   SchedGraphNode*       getSrc          () const { return src; }
 106   SchedGraphNode*       getSink         () const { return sink; }
 107   int                   getMinDelay     () const { return minDelay; }
 108   SchedGraphEdgeDepType getDepType      () const { return depType; }
 109
 110   const Value*          getValue        () const {
 111     assert(depType == ValueDep); return val;
 112   }
 113   int                   getMachineReg   () const {
 114     assert(depType == MachineRegister); return machineRegNum;
 115   }
 116   int                   getResourceId   () const {
 117     assert(depType == MachineResource); return resourceId;
 118   }
 119
 120 public:
 121   //
 122   // Debugging support
 123   //
 124   friend std::ostream& operator<<(std::ostream& os, const SchedGraphEdge& edge);
 125
 126   void          dump    (int indent=0) const;
 127
 128 private:
 129   // disable default ctor
 130   /*ctor*/              SchedGraphEdge();       // DO NOT IMPLEMENT
 131 };
 132
 133
 134
 135 class SchedGraphNode {
 136   unsigned nodeId;
 137   MachineBasicBlock *MBB;
 138   const MachineInstr* minstr;
 139   std::vector<SchedGraphEdge*> inEdges;
 140   std::vector<SchedGraphEdge*> outEdges;
 141   int origIndexInBB;            // original position of machine instr in BB
 142   int latency;
 143
 144   SchedGraphNode(const SchedGraphNode &);  // DO NOT IMPLEMENT
 145   void operator=(const SchedGraphNode &);  // DO NOT IMPLEMENT
 146 public:
 147   typedef std::vector<SchedGraphEdge*>::      iterator         iterator;
 148   typedef std::vector<SchedGraphEdge*>::const_iterator         const_iterator;
 149   typedef std::vector<SchedGraphEdge*>::      reverse_iterator reverse_iterator;
 150   typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
 151
 152 public:
 153   //
 154   // Accessor methods
 155   //
 156   unsigned              getNodeId       () const { return nodeId; }
 157   const MachineInstr*   getMachineInstr () const { return minstr; }
 158   const MachineOpCode   getOpCode       () const { return minstr->getOpCode(); }
 159   int                   getLatency      () const { return latency; }
 160   unsigned              getNumInEdges   () const { return inEdges.size(); }
 161   unsigned              getNumOutEdges  () const { return outEdges.size(); }
 162   bool                  isDummyNode     () const { return (minstr == NULL); }
 163   MachineBasicBlock    &getMachineBasicBlock() const { return *MBB; }
 164   int                   getOrigIndexInBB() const { return origIndexInBB; }
 165
 166   //
 167   // Iterators
 168   //
 169   iterator              beginInEdges    ()       { return inEdges.begin(); }
 170   iterator              endInEdges      ()       { return inEdges.end(); }
 171   iterator              beginOutEdges   ()       { return outEdges.begin(); }
 172   iterator              endOutEdges     ()       { return outEdges.end(); }
 173
 174   const_iterator        beginInEdges    () const { return inEdges.begin(); }
 175   const_iterator        endInEdges      () const { return inEdges.end(); }
 176   const_iterator        beginOutEdges   () const { return outEdges.begin(); }
 177   const_iterator        endOutEdges     () const { return outEdges.end(); }
 178
 179 public:
 180   //
 181   // Debugging support
 182   //
 183   friend std::ostream& operator<<(std::ostream& os, const SchedGraphNode& node);
 184
 185   void          dump    (int indent=0) const;
 186
 187 private:
 188   friend class SchedGraph;              // give access for ctor and dtor
 189   friend class SchedGraphEdge;          // give access for adding edges
 190
 191   void                  addInEdge       (SchedGraphEdge* edge);
 192   void                  addOutEdge      (SchedGraphEdge* edge);
 193
 194   void                  removeInEdge    (const SchedGraphEdge* edge);
 195   void                  removeOutEdge   (const SchedGraphEdge* edge);
 196
 197   // disable default constructor and provide a ctor for single-block graphs
 198   /*ctor*/              SchedGraphNode();       // DO NOT IMPLEMENT
 199   /*ctor*/              SchedGraphNode  (unsigned nodeId,
 200                                          MachineBasicBlock *mbb,
 201                                          int   indexInBB,
 202                                          const TargetMachine& Target);
 203   /*dtor*/              ~SchedGraphNode ();
 204 };
 205
 206
 207
 208 class SchedGraph : private hash_map<const MachineInstr*, SchedGraphNode*> {
 209   MachineBasicBlock &MBB;               // basic blocks for this graph
 210   SchedGraphNode* graphRoot;            // the root and leaf are not inserted
 211   SchedGraphNode* graphLeaf;            //  in the hash_map (see getNumNodes())
 212
 213   typedef hash_map<const MachineInstr*, SchedGraphNode*> map_base;
 214   SchedGraph(const SchedGraph &);       // DO NOT IMPLEMENT
 215   void operator=(const SchedGraph &);   // DO NOT IMPLEMENT
 216 public:
 217   using map_base::iterator;
 218   using map_base::const_iterator;
 219
 220 public:
 221   //
 222   // Accessor methods
 223   //
 224   MachineBasicBlock               &getBasicBlock()  const { return MBB; }
 225   unsigned                         getNumNodes()    const { return size()+2; }
 226   SchedGraphNode*                  getRoot()        const { return graphRoot; }
 227   SchedGraphNode*                  getLeaf()        const { return graphLeaf; }
 228
 229   SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
 230     const_iterator onePair = this->find(minstr);
 231     return (onePair != this->end())? (*onePair).second : NULL;
 232   }
 233
 234   //
 235   // Delete nodes or edges from the graph.
 236   //
 237   void          eraseNode               (SchedGraphNode* node);
 238
 239   void          eraseIncomingEdges      (SchedGraphNode* node,
 240                                          bool addDummyEdges = true);
 241
 242   void          eraseOutgoingEdges      (SchedGraphNode* node,
 243                                          bool addDummyEdges = true);
 244
 245   void          eraseIncidentEdges      (SchedGraphNode* node,
 246                                          bool addDummyEdges = true);
 247
 248   //
 249   // Unordered iterators.
 250   // Return values is pair<const MachineIntr*,SchedGraphNode*>.
 251   //
 252   using map_base::begin;
 253   using map_base::end;
 254
 255   //
 256   // Ordered iterators.
 257   // Return values is pair<const MachineIntr*,SchedGraphNode*>.
 258   //
 259   // void                          postord_init();
 260   // postorder_iterator    postord_begin();
 261   // postorder_iterator    postord_end();
 262   // const_postorder_iterator postord_begin() const;
 263   // const_postorder_iterator postord_end() const;
 264
 265   //
 266   // Debugging support
 267   //
 268   void          dump    () const;
 269
 270 private:
 271   friend class SchedGraphSet;           // give access to ctor
 272
 273   // disable default constructor and provide a ctor for single-block graphs
 274   /*ctor*/      SchedGraph              (MachineBasicBlock &bb,
 275                                          const TargetMachine& target);
 276   /*dtor*/      ~SchedGraph             ();
 277
 278   inline void   noteGraphNodeForInstr   (const MachineInstr* minstr,
 279                                          SchedGraphNode* node)
 280   {
 281     assert((*this)[minstr] == NULL);
 282     (*this)[minstr] = node;
 283   }
 284
 285   //
 286   // Graph builder
 287   //
 288   void          buildGraph              (const TargetMachine& target);
 289
 290   void          buildNodesForBB         (const TargetMachine& target,
 291                                          MachineBasicBlock &MBB,
 292                                          std::vector<SchedGraphNode*>& memNV,
 293                                          std::vector<SchedGraphNode*>& callNV,
 294                                          RegToRefVecMap& regToRefVecMap,
 295                                          ValueToDefVecMap& valueToDefVecMap);
 296
 297   void          findDefUseInfoAtInstr   (const TargetMachine& target,
 298                                          SchedGraphNode* node,
 299                                          std::vector<SchedGraphNode*>& memNV,
 300                                          std::vector<SchedGraphNode*>& callNV,
 301                                          RegToRefVecMap& regToRefVecMap,
 302                                          ValueToDefVecMap& valueToDefVecMap);
 303
 304   void          addEdgesForInstruction(const MachineInstr& minstr,
 305                                      const ValueToDefVecMap& valueToDefVecMap,
 306                                      const TargetMachine& target);
 307
 308   void          addCDEdges              (const TerminatorInst* term,
 309                                          const TargetMachine& target);
 310
 311   void          addMemEdges         (const std::vector<SchedGraphNode*>& memNV,
 312                                      const TargetMachine& target);
 313
 314   void          addCallDepEdges     (const std::vector<SchedGraphNode*>& callNV,
 315                                      const TargetMachine& target);
 316
 317   void          addMachineRegEdges      (RegToRefVecMap& regToRefVecMap,
 318                                          const TargetMachine& target);
 319
 320   void          addEdgesForValue        (SchedGraphNode* refNode,
 321                                          const RefVec& defVec,
 322                                          const Value* defValue,
 323                                          bool  refNodeIsDef,
 324                                          bool  refNodeIsDefAndUse,
 325                                          const TargetMachine& target);
 326
 327   void          addDummyEdges           ();
 328 };
 329
 330
 331 class SchedGraphSet : private std::vector<SchedGraph*> {
 332 private:
 333   const Function* method;
 334
 335   SchedGraphSet(const SchedGraphSet&);    // DO NOT IMPLEMENT
 336   void operator=(const SchedGraphSet&);   // DO NOT IMPLEMENT
 337 public:
 338   typedef std::vector<SchedGraph*> baseVector;
 339   using baseVector::iterator;
 340   using baseVector::const_iterator;
 341
 342 public:
 343   SchedGraphSet(const Function *F, const TargetMachine &TM);
 344   ~SchedGraphSet();
 345
 346   // Iterators
 347   using baseVector::begin;
 348   using baseVector::end;
 349
 350   // Debugging support
 351   void dump() const;
 352
 353 private:
 354   inline void   addGraph(SchedGraph* graph) {
 355     assert(graph != NULL);
 356     this->push_back(graph);
 357   }
 358
 359   // Graph builder
 360   void buildGraphsForMethod(const Function *F, const TargetMachine &TM);
 361 };
 362
 363
 364 //********************** Sched Graph Iterators *****************************/
 365
 366 // Ok to make it a template because it shd get instantiated at most twice:
 367 // for <SchedGraphNode, SchedGraphNode::iterator> and
 368 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
 369 //
 370 template <class _NodeType, class _EdgeType, class _EdgeIter>
 371 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
 372 protected:
 373   _EdgeIter oi;
 374 public:
 375   typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 376
 377   inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
 378
 379   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 380   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 381
 382   // operator*() differs for pred or succ iterator
 383   inline _NodeType* operator*() const { return (*oi)->getSrc(); }
 384   inline         _NodeType* operator->() const { return operator*(); }
 385
 386   inline _EdgeType* getEdge() const { return *(oi); }
 387
 388   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 389   inline _Self operator++(int) {                        // Postincrement
 390     _Self tmp(*this); ++*this; return tmp;
 391   }
 392
 393   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 394   inline _Self operator--(int) {                        // Postdecrement
 395     _Self tmp = *this; --*this; return tmp;
 396   }
 397 };
 398
 399 template <class _NodeType, class _EdgeType, class _EdgeIter>
 400 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
 401 protected:
 402   _EdgeIter oi;
 403 public:
 404   typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 405
 406   inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
 407
 408   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 409   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 410
 411   inline _NodeType* operator*() const { return (*oi)->getSink(); }
 412   inline         _NodeType* operator->() const { return operator*(); }
 413
 414   inline _EdgeType* getEdge() const { return *(oi); }
 415
 416   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 417   inline _Self operator++(int) {                        // Postincrement
 418     _Self tmp(*this); ++*this; return tmp;
 419   }
 420
 421   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 422   inline _Self operator--(int) {                        // Postdecrement
 423     _Self tmp = *this; --*this; return tmp;
 424   }
 425 };
 426
 427 //
 428 // sg_pred_iterator
 429 // sg_pred_const_iterator
 430 //
 431 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 432     sg_pred_iterator;
 433 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 434     sg_pred_const_iterator;
 435
 436 inline sg_pred_iterator       pred_begin(      SchedGraphNode *N) {
 437   return sg_pred_iterator(N->beginInEdges());
 438 }
 439 inline sg_pred_iterator       pred_end(        SchedGraphNode *N) {
 440   return sg_pred_iterator(N->endInEdges());
 441 }
 442 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
 443   return sg_pred_const_iterator(N->beginInEdges());
 444 }
 445 inline sg_pred_const_iterator pred_end(  const SchedGraphNode *N) {
 446   return sg_pred_const_iterator(N->endInEdges());
 447 }
 448
 449
 450 //
 451 // sg_succ_iterator
 452 // sg_succ_const_iterator
 453 //
 454 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 455     sg_succ_iterator;
 456 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 457     sg_succ_const_iterator;
 458
 459 inline sg_succ_iterator       succ_begin(      SchedGraphNode *N) {
 460   return sg_succ_iterator(N->beginOutEdges());
 461 }
 462 inline sg_succ_iterator       succ_end(        SchedGraphNode *N) {
 463   return sg_succ_iterator(N->endOutEdges());
 464 }
 465 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
 466   return sg_succ_const_iterator(N->beginOutEdges());
 467 }
 468 inline sg_succ_const_iterator succ_end(  const SchedGraphNode *N) {
 469   return sg_succ_const_iterator(N->endOutEdges());
 470 }
 471
 472 // Provide specializations of GraphTraits to be able to use graph iterators on
 473 // the scheduling graph!
 474 //
 475 template <> struct GraphTraits<SchedGraph*> {
 476   typedef SchedGraphNode NodeType;
 477   typedef sg_succ_iterator ChildIteratorType;
 478
 479   static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
 480   static inline ChildIteratorType child_begin(NodeType *N) {
 481     return succ_begin(N);
 482   }
 483   static inline ChildIteratorType child_end(NodeType *N) {
 484     return succ_end(N);
 485   }
 486 };
 487
 488 template <> struct GraphTraits<const SchedGraph*> {
 489   typedef const SchedGraphNode NodeType;
 490   typedef sg_succ_const_iterator ChildIteratorType;
 491
 492   static inline NodeType *getEntryNode(const SchedGraph *SG) {
 493     return SG->getRoot();
 494   }
 495   static inline ChildIteratorType child_begin(NodeType *N) {
 496     return succ_begin(N);
 497   }
 498   static inline ChildIteratorType child_end(NodeType *N) {
 499     return succ_end(N);
 500   }
 501 };
 502
 503
 504 std::ostream &operator<<(std::ostream& os, const SchedGraphEdge& edge);
 505 std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node);
 506
 507 #endif