lib/CodeGen/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/GraphTraits.h"
  19 #include "Support/hash_map"
  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 {
  49   SchedGraphEdge(const SchedGraphEdge &);  // DO NOT IMPLEMENT
  50   void operator=(const SchedGraphEdge &);  // DO NOT IMPLEMENT
  51 public:
  52   enum SchedGraphEdgeDepType {
  53     CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
  54   };
  55   enum DataDepOrderType {
  56     TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
  57   };
  58
  59 private:
  60   SchedGraphNode*       src;
  61   SchedGraphNode*       sink;
  62   SchedGraphEdgeDepType depType;
  63   unsigned int          depOrderType;
  64   int                   minDelay; // cached latency (assumes fixed target arch)
  65
  66   union {
  67     const Value* val;
  68     int          machineRegNum;
  69     ResourceId   resourceId;
  70   };
  71
  72 public:
  73   // For all constructors, if minDelay is unspecified, minDelay is
  74   // set to _src->getLatency().
  75   // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
  76   /*ctor*/              SchedGraphEdge(SchedGraphNode* _src,
  77                                        SchedGraphNode* _sink,
  78                                        SchedGraphEdgeDepType _depType,
  79                                        unsigned int     _depOrderType,
  80                                        int _minDelay = -1);
  81
  82   // constructor for explicit value dependence (may be true/anti/output)
  83   /*ctor*/              SchedGraphEdge(SchedGraphNode* _src,
  84                                        SchedGraphNode* _sink,
  85                                        const Value*    _val,
  86                                        unsigned int     _depOrderType,
  87                                        int _minDelay = -1);
  88
  89   // constructor for machine register dependence
  90   /*ctor*/              SchedGraphEdge(SchedGraphNode* _src,
  91                                        SchedGraphNode* _sink,
  92                                        unsigned int    _regNum,
  93                                        unsigned int     _depOrderType,
  94                                        int _minDelay = -1);
  95
  96   // constructor for any other machine resource dependences.
  97   // DataDepOrderType is always NonDataDep.  It it not an argument to
  98   // avoid overloading ambiguity with previous constructor.
  99   /*ctor*/              SchedGraphEdge(SchedGraphNode* _src,
 100                                        SchedGraphNode* _sink,
 101                                        ResourceId      _resourceId,
 102                                        int _minDelay = -1);
 103
 104   /*dtor*/              ~SchedGraphEdge();
 105
 106   SchedGraphNode*       getSrc          () const { return src; }
 107   SchedGraphNode*       getSink         () const { return sink; }
 108   int                   getMinDelay     () const { return minDelay; }
 109   SchedGraphEdgeDepType getDepType      () const { return depType; }
 110
 111   const Value*          getValue        () const {
 112     assert(depType == ValueDep); return val;
 113   }
 114   int                   getMachineReg   () const {
 115     assert(depType == MachineRegister); return machineRegNum;
 116   }
 117   int                   getResourceId   () const {
 118     assert(depType == MachineResource); return resourceId;
 119   }
 120
 121 public:
 122   //
 123   // Debugging support
 124   //
 125   friend std::ostream& operator<<(std::ostream& os, const SchedGraphEdge& edge);
 126
 127   void          dump    (int indent=0) const;
 128
 129 private:
 130   // disable default ctor
 131   /*ctor*/              SchedGraphEdge();       // DO NOT IMPLEMENT
 132 };
 133
 134
 135
 136 class SchedGraphNode {
 137   unsigned nodeId;
 138   MachineBasicBlock *MBB;
 139   const MachineInstr* minstr;
 140   std::vector<SchedGraphEdge*> inEdges;
 141   std::vector<SchedGraphEdge*> outEdges;
 142   int origIndexInBB;            // original position of machine instr in BB
 143   int latency;
 144
 145   SchedGraphNode(const SchedGraphNode &);  // DO NOT IMPLEMENT
 146   void operator=(const SchedGraphNode &);  // DO NOT IMPLEMENT
 147 public:
 148   typedef std::vector<SchedGraphEdge*>::      iterator         iterator;
 149   typedef std::vector<SchedGraphEdge*>::const_iterator         const_iterator;
 150   typedef std::vector<SchedGraphEdge*>::      reverse_iterator reverse_iterator;
 151   typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
 152
 153 public:
 154   //
 155   // Accessor methods
 156   //
 157   unsigned              getNodeId       () const { return nodeId; }
 158   const MachineInstr*   getMachineInstr () const { return minstr; }
 159   const MachineOpCode   getOpCode       () const { return minstr->getOpCode(); }
 160   int                   getLatency      () const { return latency; }
 161   unsigned              getNumInEdges   () const { return inEdges.size(); }
 162   unsigned              getNumOutEdges  () const { return outEdges.size(); }
 163   bool                  isDummyNode     () const { return (minstr == NULL); }
 164   MachineBasicBlock    &getMachineBasicBlock() const { return *MBB; }
 165   int                   getOrigIndexInBB() const { return origIndexInBB; }
 166
 167   //
 168   // Iterators
 169   //
 170   iterator              beginInEdges    ()       { return inEdges.begin(); }
 171   iterator              endInEdges      ()       { return inEdges.end(); }
 172   iterator              beginOutEdges   ()       { return outEdges.begin(); }
 173   iterator              endOutEdges     ()       { return outEdges.end(); }
 174
 175   const_iterator        beginInEdges    () const { return inEdges.begin(); }
 176   const_iterator        endInEdges      () const { return inEdges.end(); }
 177   const_iterator        beginOutEdges   () const { return outEdges.begin(); }
 178   const_iterator        endOutEdges     () const { return outEdges.end(); }
 179
 180 public:
 181   //
 182   // Debugging support
 183   //
 184   friend std::ostream& operator<<(std::ostream& os, const SchedGraphNode& node);
 185
 186   void          dump    (int indent=0) const;
 187
 188 private:
 189   friend class SchedGraph;              // give access for ctor and dtor
 190   friend class SchedGraphEdge;          // give access for adding edges
 191
 192   void                  addInEdge       (SchedGraphEdge* edge);
 193   void                  addOutEdge      (SchedGraphEdge* edge);
 194
 195   void                  removeInEdge    (const SchedGraphEdge* edge);
 196   void                  removeOutEdge   (const SchedGraphEdge* edge);
 197
 198   // disable default constructor and provide a ctor for single-block graphs
 199   /*ctor*/              SchedGraphNode();       // DO NOT IMPLEMENT
 200   /*ctor*/              SchedGraphNode  (unsigned nodeId,
 201                                          MachineBasicBlock *mbb,
 202                                          int   indexInBB,
 203                                          const TargetMachine& Target);
 204   /*dtor*/              ~SchedGraphNode ();
 205 };
 206
 207
 208
 209 class SchedGraph : private hash_map<const MachineInstr*, SchedGraphNode*> {
 210   MachineBasicBlock &MBB;               // basic blocks for this graph
 211   SchedGraphNode* graphRoot;            // the root and leaf are not inserted
 212   SchedGraphNode* graphLeaf;            //  in the hash_map (see getNumNodes())
 213
 214   typedef hash_map<const MachineInstr*, SchedGraphNode*> map_base;
 215   SchedGraph(const SchedGraph &);       // DO NOT IMPLEMENT
 216   void operator=(const SchedGraph &);   // DO NOT IMPLEMENT
 217 public:
 218   using map_base::iterator;
 219   using map_base::const_iterator;
 220
 221 public:
 222   //
 223   // Accessor methods
 224   //
 225   MachineBasicBlock               &getBasicBlock()  const { return MBB; }
 226   unsigned                         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              (MachineBasicBlock &bb,
 276                                          const TargetMachine& target);
 277   /*dtor*/      ~SchedGraph             ();
 278
 279   inline void   noteGraphNodeForInstr   (const MachineInstr* minstr,
 280                                          SchedGraphNode* node)
 281   {
 282     assert((*this)[minstr] == NULL);
 283     (*this)[minstr] = node;
 284   }
 285
 286   //
 287   // Graph builder
 288   //
 289   void          buildGraph              (const TargetMachine& target);
 290
 291   void          buildNodesForBB         (const TargetMachine& target,
 292                                          MachineBasicBlock &MBB,
 293                                          std::vector<SchedGraphNode*>& memNV,
 294                                          std::vector<SchedGraphNode*>& callNV,
 295                                          RegToRefVecMap& regToRefVecMap,
 296                                          ValueToDefVecMap& valueToDefVecMap);
 297
 298   void          findDefUseInfoAtInstr   (const TargetMachine& target,
 299                                          SchedGraphNode* node,
 300                                          std::vector<SchedGraphNode*>& memNV,
 301                                          std::vector<SchedGraphNode*>& callNV,
 302                                          RegToRefVecMap& regToRefVecMap,
 303                                          ValueToDefVecMap& valueToDefVecMap);
 304
 305   void          addEdgesForInstruction(const MachineInstr& minstr,
 306                                      const ValueToDefVecMap& valueToDefVecMap,
 307                                      const TargetMachine& target);
 308
 309   void          addCDEdges              (const TerminatorInst* term,
 310                                          const TargetMachine& target);
 311
 312   void          addMemEdges         (const std::vector<SchedGraphNode*>& memNV,
 313                                      const TargetMachine& target);
 314
 315   void          addCallDepEdges     (const std::vector<SchedGraphNode*>& callNV,
 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 : private std::vector<SchedGraph*> {
 333 private:
 334   const Function* method;
 335
 336   SchedGraphSet(const SchedGraphSet&);    // DO NOT IMPLEMENT
 337   void operator=(const SchedGraphSet&);   // DO NOT IMPLEMENT
 338 public:
 339   typedef std::vector<SchedGraph*> baseVector;
 340   using baseVector::iterator;
 341   using baseVector::const_iterator;
 342
 343 public:
 344   SchedGraphSet(const Function *F, const TargetMachine &TM);
 345   ~SchedGraphSet();
 346
 347   // Iterators
 348   using baseVector::begin;
 349   using baseVector::end;
 350
 351   // Debugging support
 352   void dump() const;
 353
 354 private:
 355   inline void   addGraph(SchedGraph* graph) {
 356     assert(graph != NULL);
 357     this->push_back(graph);
 358   }
 359
 360   // Graph builder
 361   void buildGraphsForMethod(const Function *F, const TargetMachine &TM);
 362 };
 363
 364
 365 //********************** Sched Graph Iterators *****************************/
 366
 367 // Ok to make it a template because it shd get instantiated at most twice:
 368 // for <SchedGraphNode, SchedGraphNode::iterator> and
 369 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
 370 //
 371 template <class _NodeType, class _EdgeType, class _EdgeIter>
 372 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
 373 protected:
 374   _EdgeIter oi;
 375 public:
 376   typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 377
 378   inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
 379
 380   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 381   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 382
 383   // operator*() differs for pred or succ iterator
 384   inline _NodeType* operator*() const { return (*oi)->getSrc(); }
 385   inline         _NodeType* operator->() const { return operator*(); }
 386
 387   inline _EdgeType* getEdge() const { return *(oi); }
 388
 389   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 390   inline _Self operator++(int) {                        // Postincrement
 391     _Self tmp(*this); ++*this; return tmp;
 392   }
 393
 394   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 395   inline _Self operator--(int) {                        // Postdecrement
 396     _Self tmp = *this; --*this; return tmp;
 397   }
 398 };
 399
 400 template <class _NodeType, class _EdgeType, class _EdgeIter>
 401 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
 402 protected:
 403   _EdgeIter oi;
 404 public:
 405   typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 406
 407   inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
 408
 409   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 410   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 411
 412   inline _NodeType* operator*() const { return (*oi)->getSink(); }
 413   inline         _NodeType* operator->() const { return operator*(); }
 414
 415   inline _EdgeType* getEdge() const { return *(oi); }
 416
 417   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 418   inline _Self operator++(int) {                        // Postincrement
 419     _Self tmp(*this); ++*this; return tmp;
 420   }
 421
 422   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 423   inline _Self operator--(int) {                        // Postdecrement
 424     _Self tmp = *this; --*this; return tmp;
 425   }
 426 };
 427
 428 //
 429 // sg_pred_iterator
 430 // sg_pred_const_iterator
 431 //
 432 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 433     sg_pred_iterator;
 434 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 435     sg_pred_const_iterator;
 436
 437 inline sg_pred_iterator       pred_begin(      SchedGraphNode *N) {
 438   return sg_pred_iterator(N->beginInEdges());
 439 }
 440 inline sg_pred_iterator       pred_end(        SchedGraphNode *N) {
 441   return sg_pred_iterator(N->endInEdges());
 442 }
 443 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
 444   return sg_pred_const_iterator(N->beginInEdges());
 445 }
 446 inline sg_pred_const_iterator pred_end(  const SchedGraphNode *N) {
 447   return sg_pred_const_iterator(N->endInEdges());
 448 }
 449
 450
 451 //
 452 // sg_succ_iterator
 453 // sg_succ_const_iterator
 454 //
 455 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 456     sg_succ_iterator;
 457 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 458     sg_succ_const_iterator;
 459
 460 inline sg_succ_iterator       succ_begin(      SchedGraphNode *N) {
 461   return sg_succ_iterator(N->beginOutEdges());
 462 }
 463 inline sg_succ_iterator       succ_end(        SchedGraphNode *N) {
 464   return sg_succ_iterator(N->endOutEdges());
 465 }
 466 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
 467   return sg_succ_const_iterator(N->beginOutEdges());
 468 }
 469 inline sg_succ_const_iterator succ_end(  const SchedGraphNode *N) {
 470   return sg_succ_const_iterator(N->endOutEdges());
 471 }
 472
 473 // Provide specializations of GraphTraits to be able to use graph iterators on
 474 // the scheduling graph!
 475 //
 476 template <> struct GraphTraits<SchedGraph*> {
 477   typedef SchedGraphNode NodeType;
 478   typedef sg_succ_iterator ChildIteratorType;
 479
 480   static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
 481   static inline ChildIteratorType child_begin(NodeType *N) {
 482     return succ_begin(N);
 483   }
 484   static inline ChildIteratorType child_end(NodeType *N) {
 485     return succ_end(N);
 486   }
 487 };
 488
 489 template <> struct GraphTraits<const SchedGraph*> {
 490   typedef const SchedGraphNode NodeType;
 491   typedef sg_succ_const_iterator ChildIteratorType;
 492
 493   static inline NodeType *getEntryNode(const SchedGraph *SG) {
 494     return SG->getRoot();
 495   }
 496   static inline ChildIteratorType child_begin(NodeType *N) {
 497     return succ_begin(N);
 498   }
 499   static inline ChildIteratorType child_end(NodeType *N) {
 500     return succ_end(N);
 501   }
 502 };
 503
 504
 505 std::ostream &operator<<(std::ostream& os, const SchedGraphEdge& edge);
 506 std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node);
 507
 508 #endif