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