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   typedef vector<SchedGraphEdge*>::      reverse_iterator reverse_iterator;
 145   typedef vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
 146
 147 public:
 148   //
 149   // Accessor methods
 150   //
 151   unsigned int          getNodeId       () const { return nodeId; }
 152   const Instruction*    getInstr        () const { return instr; }
 153   const MachineInstr*   getMachineInstr () const { return minstr; }
 154   int                   getLatency      () const { return latency; }
 155   unsigned int          getNumInEdges   () const { return inEdges.size(); }
 156   unsigned int          getNumOutEdges  () const { return outEdges.size(); }
 157   bool                  isDummyNode     () const { return (minstr == NULL); }
 158
 159   //
 160   // Iterators
 161   //
 162   iterator              beginInEdges    ()       { return inEdges.begin(); }
 163   iterator              endInEdges      ()       { return inEdges.end(); }
 164   iterator              beginOutEdges   ()       { return outEdges.begin(); }
 165   iterator              endOutEdges     ()       { return outEdges.end(); }
 166
 167   const_iterator        beginInEdges    () const { return inEdges.begin(); }
 168   const_iterator        endInEdges      () const { return inEdges.end(); }
 169   const_iterator        beginOutEdges   () const { return outEdges.begin(); }
 170   const_iterator        endOutEdges     () const { return outEdges.end(); }
 171
 172 public:
 173   //
 174   // Debugging support
 175   //
 176   friend ostream& operator<<(ostream& os, const SchedGraphNode& node);
 177
 178   void          dump    (int indent=0) const;
 179
 180 private:
 181   friend class SchedGraph;              // give access for ctor and dtor
 182   friend class SchedGraphEdge;          // give access for adding edges
 183
 184   void                  addInEdge       (SchedGraphEdge* edge);
 185   void                  addOutEdge      (SchedGraphEdge* edge);
 186
 187   void                  removeInEdge    (const SchedGraphEdge* edge);
 188   void                  removeOutEdge   (const SchedGraphEdge* edge);
 189
 190   // disable default constructor and provide a ctor for single-block graphs
 191   /*ctor*/              SchedGraphNode();       // DO NOT IMPLEMENT
 192   /*ctor*/              SchedGraphNode  (unsigned int _nodeId,
 193                                          const Instruction* _instr,
 194                                          const MachineInstr* _minstr,
 195                                          const TargetMachine& _target);
 196   /*dtor*/              ~SchedGraphNode ();
 197 };
 198
 199
 200
 201 class SchedGraph :
 202   public NonCopyable,
 203   private hash_map<const MachineInstr*, SchedGraphNode*>
 204 {
 205 private:
 206   vector<const BasicBlock*> bbVec;      // basic blocks included in the graph
 207   SchedGraphNode* graphRoot;            // the root and leaf are not inserted
 208   SchedGraphNode* graphLeaf;            //  in the hash_map (see getNumNodes())
 209
 210 public:
 211   typedef hash_map<const MachineInstr*, SchedGraphNode*>::iterator iterator;
 212   typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
 213
 214 public:
 215   //
 216   // Accessor methods
 217   //
 218   const vector<const BasicBlock*>& getBasicBlocks() const { return bbVec; }
 219   const unsigned int               getNumNodes()    const { return size()+2; }
 220   SchedGraphNode*                  getRoot()        const { return graphRoot; }
 221   SchedGraphNode*                  getLeaf()        const { return graphLeaf; }
 222
 223   SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
 224     const_iterator onePair = this->find(minstr);
 225     return (onePair != this->end())? (*onePair).second : NULL;
 226   }
 227
 228   //
 229   // Delete nodes or edges from the graph.
 230   //
 231   void          eraseNode               (SchedGraphNode* node);
 232
 233   void          eraseIncomingEdges      (SchedGraphNode* node,
 234                                          bool addDummyEdges = true);
 235
 236   void          eraseOutgoingEdges      (SchedGraphNode* node,
 237                                          bool addDummyEdges = true);
 238
 239   void          eraseIncidentEdges      (SchedGraphNode* node,
 240                                          bool addDummyEdges = true);
 241
 242   //
 243   // Unordered iterators.
 244   // Return values is pair<const MachineIntr*,SchedGraphNode*>.
 245   //
 246   iterator      begin() {
 247     return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
 248   }
 249   iterator      end() {
 250     return hash_map<const MachineInstr*, SchedGraphNode*>::end();
 251   }
 252   const_iterator begin() const {
 253     return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
 254   }
 255   const_iterator end()  const {
 256     return hash_map<const MachineInstr*, SchedGraphNode*>::end();
 257   }
 258
 259   //
 260   // Ordered iterators.
 261   // Return values is pair<const MachineIntr*,SchedGraphNode*>.
 262   //
 263   // void                          postord_init();
 264   // postorder_iterator    postord_begin();
 265   // postorder_iterator    postord_end();
 266   // const_postorder_iterator postord_begin() const;
 267   // const_postorder_iterator postord_end() const;
 268
 269   //
 270   // Debugging support
 271   //
 272   void          dump    () const;
 273
 274 private:
 275   friend class SchedGraphSet;           // give access to ctor
 276
 277   // disable default constructor and provide a ctor for single-block graphs
 278   /*ctor*/      SchedGraph              ();     // DO NOT IMPLEMENT
 279   /*ctor*/      SchedGraph              (const BasicBlock* bb,
 280                                          const TargetMachine& target);
 281   /*dtor*/      ~SchedGraph             ();
 282
 283   inline void   noteGraphNodeForInstr   (const MachineInstr* minstr,
 284                                          SchedGraphNode* node)
 285   {
 286     assert((*this)[minstr] == NULL);
 287     (*this)[minstr] = node;
 288   }
 289
 290   //
 291   // Graph builder
 292   //
 293   void          buildGraph              (const TargetMachine& target);
 294
 295   void          addEdgesForInstruction  (SchedGraphNode* node,
 296                                          NodeToRegRefMap& regToRefVecMap,
 297                                          const TargetMachine& target);
 298
 299   void          addCDEdges              (const TerminatorInst* term,
 300                                          const TargetMachine& target);
 301
 302   void          addMemEdges          (const vector<const Instruction*>& memVec,
 303                                       const TargetMachine& target);
 304
 305   void          addMachineRegEdges      (NodeToRegRefMap& regToRefVecMap,
 306                                          const TargetMachine& target);
 307
 308   void          addSSAEdge              (SchedGraphNode* node,
 309                                          Value* val,
 310                                          const TargetMachine& target);
 311
 312   void          addDummyEdges           ();
 313 };
 314
 315
 316 class SchedGraphSet :
 317   public NonCopyable,
 318   private hash_map<const BasicBlock*, SchedGraph*>
 319 {
 320 private:
 321   const Method* method;
 322
 323 public:
 324   typedef hash_map<const BasicBlock*, SchedGraph*>::iterator iterator;
 325   typedef hash_map<const BasicBlock*, SchedGraph*>::const_iterator const_iterator;
 326
 327 public:
 328   /*ctor*/      SchedGraphSet           (const Method* _method,
 329                                          const TargetMachine& target);
 330   /*dtor*/      ~SchedGraphSet          ();
 331
 332   //
 333   // Accessors
 334   //
 335   SchedGraph*   getGraphForBasicBlock   (const BasicBlock* bb) const {
 336     const_iterator onePair = this->find(bb);
 337     return (onePair != this->end())? (*onePair).second : NULL;
 338   }
 339
 340   //
 341   // Iterators
 342   //
 343   iterator      begin() {
 344     return hash_map<const BasicBlock*, SchedGraph*>::begin();
 345   }
 346   iterator      end() {
 347     return hash_map<const BasicBlock*, SchedGraph*>::end();
 348   }
 349   const_iterator begin() const {
 350     return hash_map<const BasicBlock*, SchedGraph*>::begin();
 351   }
 352   const_iterator end()  const {
 353     return hash_map<const BasicBlock*, SchedGraph*>::end();
 354   }
 355
 356   //
 357   // Debugging support
 358   //
 359   void          dump    () const;
 360
 361 private:
 362   inline void   noteGraphForBlock(const BasicBlock* bb, SchedGraph* graph) {
 363     assert((*this)[bb] == NULL);
 364     (*this)[bb] = graph;
 365   }
 366
 367   //
 368   // Graph builder
 369   //
 370   void          buildGraphsForMethod    (const Method *method,
 371                                          const TargetMachine& target);
 372 };
 373
 374
 375 //********************** Sched Graph Iterators *****************************/
 376
 377 // Ok to make it a template because it shd get instantiated at most twice:
 378 // for <SchedGraphNode, SchedGraphNode::iterator> and
 379 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
 380 //
 381 template <class _NodeType, class _EdgeType, class _EdgeIter>
 382 class PredIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
 383 protected:
 384   _EdgeIter oi;
 385 public:
 386   typedef PredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 387
 388   inline PredIterator(_EdgeIter startEdge) : oi(startEdge) {}
 389
 390   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 391   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 392
 393   // operator*() differs for pred or succ iterator
 394   inline _NodeType* operator*() const { return (*oi)->getSrc(); }
 395   inline         _NodeType* operator->() const { return operator*(); }
 396
 397   inline _EdgeType* getEdge() const { return *(oi); }
 398
 399   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 400   inline _Self operator++(int) {                        // Postincrement
 401     _Self tmp(*this); ++*this; return tmp;
 402   }
 403
 404   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 405   inline _Self operator--(int) {                        // Postdecrement
 406     _Self tmp = *this; --*this; return tmp;
 407   }
 408 };
 409
 410 template <class _NodeType, class _EdgeType, class _EdgeIter>
 411 class SuccIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
 412 protected:
 413   _EdgeIter oi;
 414 public:
 415   typedef SuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 416
 417   inline SuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
 418
 419   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 420   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 421
 422   inline _NodeType* operator*() const { return (*oi)->getSink(); }
 423   inline         _NodeType* operator->() const { return operator*(); }
 424
 425   inline _EdgeType* getEdge() const { return *(oi); }
 426
 427   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 428   inline _Self operator++(int) {                        // Postincrement
 429     _Self tmp(*this); ++*this; return tmp;
 430   }
 431
 432   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 433   inline _Self operator--(int) {                        // Postdecrement
 434     _Self tmp = *this; --*this; return tmp;
 435   }
 436 };
 437
 438 //
 439 // sg_pred_iterator
 440 // sg_pred_const_iterator
 441 //
 442 typedef PredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 443     sg_pred_iterator;
 444 typedef PredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 445     sg_pred_const_iterator;
 446
 447 inline sg_pred_iterator       pred_begin(      SchedGraphNode *N) {
 448   return sg_pred_iterator(N->beginInEdges());
 449 }
 450 inline sg_pred_iterator       pred_end(        SchedGraphNode *N) {
 451   return sg_pred_iterator(N->endInEdges());
 452 }
 453 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
 454   return sg_pred_const_iterator(N->beginInEdges());
 455 }
 456 inline sg_pred_const_iterator pred_end(  const SchedGraphNode *N) {
 457   return sg_pred_const_iterator(N->endInEdges());
 458 }
 459
 460
 461 //
 462 // sg_succ_iterator
 463 // sg_succ_const_iterator
 464 //
 465 typedef SuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 466     sg_succ_iterator;
 467 typedef SuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 468     sg_succ_const_iterator;
 469
 470 inline sg_succ_iterator       succ_begin(      SchedGraphNode *N) {
 471   return sg_succ_iterator(N->beginOutEdges());
 472 }
 473 inline sg_succ_iterator       succ_end(        SchedGraphNode *N) {
 474   return sg_succ_iterator(N->endOutEdges());
 475 }
 476 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
 477   return sg_succ_const_iterator(N->beginOutEdges());
 478 }
 479 inline sg_succ_const_iterator succ_end(  const SchedGraphNode *N) {
 480   return sg_succ_const_iterator(N->endOutEdges());
 481 }
 482
 483 //
 484 // po_iterator
 485 // po_const_iterator
 486 //
 487 typedef cfg::POIterator<SchedGraphNode, sg_succ_iterator> sg_po_iterator;
 488 typedef cfg::POIterator<const SchedGraphNode,
 489                         sg_succ_const_iterator> sg_po_const_iterator;
 490
 491
 492 //************************ External Functions *****************************/
 493
 494
 495 ostream& operator<<(ostream& os, const SchedGraphEdge& edge);
 496
 497 ostream& operator<<(ostream& os, const SchedGraphNode& node);
 498
 499
 500 /***************************************************************************/
 501
 502 #endif