lib/Target/SparcV9/InstrSched/SchedGraph.h

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