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