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/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 RegToRefVecMap;
  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     const 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                                        const 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          buildNodesforVMInstr    (const TargetMachine& target,
 297                                          const Instruction* instr);
 298
 299   void          addEdgesForInstruction  (const MachineInstr& minstr,
 300                                          RegToRefVecMap& regToRefVecMap,
 301                                          const TargetMachine& target);
 302
 303   void          addCDEdges              (const TerminatorInst* term,
 304                                          const TargetMachine& target);
 305
 306   void          addMemEdges          (const vector<const Instruction*>& memVec,
 307                                       const TargetMachine& target);
 308
 309   void          addMachineRegEdges      (RegToRefVecMap& regToRefVecMap,
 310                                          const TargetMachine& target);
 311
 312   void          addSSAEdge              (SchedGraphNode* node,
 313                                          const Value* val,
 314                                          const TargetMachine& target);
 315
 316   void          addNonSSAEdgesForValue  (const Instruction* instr,
 317                                          const TargetMachine& target);
 318
 319   void          addDummyEdges           ();
 320 };
 321
 322
 323 class SchedGraphSet :
 324   public NonCopyable,
 325   private hash_map<const BasicBlock*, SchedGraph*>
 326 {
 327 private:
 328   const Method* method;
 329
 330 public:
 331   typedef hash_map<const BasicBlock*, SchedGraph*>::iterator iterator;
 332   typedef hash_map<const BasicBlock*, SchedGraph*>::const_iterator const_iterator;
 333
 334 public:
 335   /*ctor*/      SchedGraphSet           (const Method* _method,
 336                                          const TargetMachine& target);
 337   /*dtor*/      ~SchedGraphSet          ();
 338
 339   //
 340   // Accessors
 341   //
 342   SchedGraph*   getGraphForBasicBlock   (const BasicBlock* bb) const {
 343     const_iterator onePair = this->find(bb);
 344     return (onePair != this->end())? (*onePair).second : NULL;
 345   }
 346
 347   //
 348   // Iterators
 349   //
 350   iterator      begin() {
 351     return hash_map<const BasicBlock*, SchedGraph*>::begin();
 352   }
 353   iterator      end() {
 354     return hash_map<const BasicBlock*, SchedGraph*>::end();
 355   }
 356   const_iterator begin() const {
 357     return hash_map<const BasicBlock*, SchedGraph*>::begin();
 358   }
 359   const_iterator end()  const {
 360     return hash_map<const BasicBlock*, SchedGraph*>::end();
 361   }
 362
 363   //
 364   // Debugging support
 365   //
 366   void          dump    () const;
 367
 368 private:
 369   inline void   noteGraphForBlock(const BasicBlock* bb, SchedGraph* graph) {
 370     assert((*this)[bb] == NULL);
 371     (*this)[bb] = graph;
 372   }
 373
 374   //
 375   // Graph builder
 376   //
 377   void          buildGraphsForMethod    (const Method *method,
 378                                          const TargetMachine& target);
 379 };
 380
 381
 382 //********************** Sched Graph Iterators *****************************/
 383
 384 // Ok to make it a template because it shd get instantiated at most twice:
 385 // for <SchedGraphNode, SchedGraphNode::iterator> and
 386 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
 387 //
 388 template <class _NodeType, class _EdgeType, class _EdgeIter>
 389 class PredIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
 390 protected:
 391   _EdgeIter oi;
 392 public:
 393   typedef PredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 394
 395   inline PredIterator(_EdgeIter startEdge) : oi(startEdge) {}
 396
 397   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 398   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 399
 400   // operator*() differs for pred or succ iterator
 401   inline _NodeType* operator*() const { return (*oi)->getSrc(); }
 402   inline         _NodeType* operator->() const { return operator*(); }
 403
 404   inline _EdgeType* getEdge() const { return *(oi); }
 405
 406   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 407   inline _Self operator++(int) {                        // Postincrement
 408     _Self tmp(*this); ++*this; return tmp;
 409   }
 410
 411   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 412   inline _Self operator--(int) {                        // Postdecrement
 413     _Self tmp = *this; --*this; return tmp;
 414   }
 415 };
 416
 417 template <class _NodeType, class _EdgeType, class _EdgeIter>
 418 class SuccIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
 419 protected:
 420   _EdgeIter oi;
 421 public:
 422   typedef SuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 423
 424   inline SuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
 425
 426   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 427   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 428
 429   inline _NodeType* operator*() const { return (*oi)->getSink(); }
 430   inline         _NodeType* operator->() const { return operator*(); }
 431
 432   inline _EdgeType* getEdge() const { return *(oi); }
 433
 434   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 435   inline _Self operator++(int) {                        // Postincrement
 436     _Self tmp(*this); ++*this; return tmp;
 437   }
 438
 439   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 440   inline _Self operator--(int) {                        // Postdecrement
 441     _Self tmp = *this; --*this; return tmp;
 442   }
 443 };
 444
 445 //
 446 // sg_pred_iterator
 447 // sg_pred_const_iterator
 448 //
 449 typedef PredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 450     sg_pred_iterator;
 451 typedef PredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 452     sg_pred_const_iterator;
 453
 454 inline sg_pred_iterator       pred_begin(      SchedGraphNode *N) {
 455   return sg_pred_iterator(N->beginInEdges());
 456 }
 457 inline sg_pred_iterator       pred_end(        SchedGraphNode *N) {
 458   return sg_pred_iterator(N->endInEdges());
 459 }
 460 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
 461   return sg_pred_const_iterator(N->beginInEdges());
 462 }
 463 inline sg_pred_const_iterator pred_end(  const SchedGraphNode *N) {
 464   return sg_pred_const_iterator(N->endInEdges());
 465 }
 466
 467
 468 //
 469 // sg_succ_iterator
 470 // sg_succ_const_iterator
 471 //
 472 typedef SuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 473     sg_succ_iterator;
 474 typedef SuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 475     sg_succ_const_iterator;
 476
 477 inline sg_succ_iterator       succ_begin(      SchedGraphNode *N) {
 478   return sg_succ_iterator(N->beginOutEdges());
 479 }
 480 inline sg_succ_iterator       succ_end(        SchedGraphNode *N) {
 481   return sg_succ_iterator(N->endOutEdges());
 482 }
 483 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
 484   return sg_succ_const_iterator(N->beginOutEdges());
 485 }
 486 inline sg_succ_const_iterator succ_end(  const SchedGraphNode *N) {
 487   return sg_succ_const_iterator(N->endOutEdges());
 488 }
 489
 490 // Provide specializations of GraphTraits to be able to use graph iterators on
 491 // the scheduling graph!
 492 //
 493 template <> struct GraphTraits<SchedGraph*> {
 494   typedef SchedGraphNode NodeType;
 495   typedef sg_succ_iterator ChildIteratorType;
 496
 497   static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
 498   static inline ChildIteratorType child_begin(NodeType *N) {
 499     return succ_begin(N);
 500   }
 501   static inline ChildIteratorType child_end(NodeType *N) {
 502     return succ_end(N);
 503   }
 504 };
 505
 506 template <> struct GraphTraits<const SchedGraph*> {
 507   typedef const SchedGraphNode NodeType;
 508   typedef sg_succ_const_iterator ChildIteratorType;
 509
 510   static inline NodeType *getEntryNode(const SchedGraph *SG) {
 511     return SG->getRoot();
 512   }
 513   static inline ChildIteratorType child_begin(NodeType *N) {
 514     return succ_begin(N);
 515   }
 516   static inline ChildIteratorType child_end(NodeType *N) {
 517     return succ_end(N);
 518   }
 519 };
 520
 521
 522 //************************ External Functions *****************************/
 523
 524
 525 ostream& operator<<(ostream& os, const SchedGraphEdge& edge);
 526
 527 ostream& operator<<(ostream& os, const SchedGraphNode& node);
 528
 529
 530 /***************************************************************************/
 531
 532 #endif