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