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