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