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