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