lib/Target/SparcV9/InstrSched/SchedGraph.h

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