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