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/Support/NonCopyable.h"
  23 #include "llvm/Support/HashExtras.h"
  24 #include "llvm/Support/GraphTraits.h"
  25 #include "llvm/Target/MachineInstrInfo.h"
  26 #include "llvm/CodeGen/MachineInstr.h"
  27 #include <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, DefUseDep, 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 =TrueDep,
  86                                        int _minDelay = -1);
  87
  88   // constructor for explicit def-use or memory def-use edge
  89   /*ctor*/              SchedGraphEdge(SchedGraphNode* _src,
  90                                        SchedGraphNode* _sink,
  91                                        const Value*    _val,
  92                                        unsigned int     _depOrderType =TrueDep,
  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 =TrueDep,
 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 == DefUseDep || depType == MemoryDep); 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 ostream& operator<<(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   vector<SchedGraphEdge*> inEdges;
 148   vector<SchedGraphEdge*> outEdges;
 149   int origIndexInBB;            // original position of machine instr in BB
 150   int latency;
 151
 152 public:
 153   typedef vector<SchedGraphEdge*>::      iterator               iterator;
 154   typedef vector<SchedGraphEdge*>::const_iterator         const_iterator;
 155   typedef vector<SchedGraphEdge*>::      reverse_iterator reverse_iterator;
 156   typedef 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 ostream& operator<<(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 hash_map<const MachineInstr*, SchedGraphNode*>
 218 {
 219 private:
 220   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 public:
 225   typedef hash_map<const MachineInstr*, SchedGraphNode*>::iterator iterator;
 226   typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
 227
 228 public:
 229   //
 230   // Accessor methods
 231   //
 232   const vector<const BasicBlock*>& getBasicBlocks() const { return bbVec; }
 233   const unsigned int               getNumNodes()    const { return size()+2; }
 234   SchedGraphNode*                  getRoot()        const { return graphRoot; }
 235   SchedGraphNode*                  getLeaf()        const { return graphLeaf; }
 236
 237   SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
 238     const_iterator onePair = this->find(minstr);
 239     return (onePair != this->end())? (*onePair).second : NULL;
 240   }
 241
 242   //
 243   // Delete nodes or edges from the graph.
 244   //
 245   void          eraseNode               (SchedGraphNode* node);
 246
 247   void          eraseIncomingEdges      (SchedGraphNode* node,
 248                                          bool addDummyEdges = true);
 249
 250   void          eraseOutgoingEdges      (SchedGraphNode* node,
 251                                          bool addDummyEdges = true);
 252
 253   void          eraseIncidentEdges      (SchedGraphNode* node,
 254                                          bool addDummyEdges = true);
 255
 256   //
 257   // Unordered iterators.
 258   // Return values is pair<const MachineIntr*,SchedGraphNode*>.
 259   //
 260   iterator      begin() {
 261     return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
 262   }
 263   iterator      end() {
 264     return hash_map<const MachineInstr*, SchedGraphNode*>::end();
 265   }
 266   const_iterator begin() const {
 267     return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
 268   }
 269   const_iterator end()  const {
 270     return hash_map<const MachineInstr*, SchedGraphNode*>::end();
 271   }
 272
 273   //
 274   // Ordered iterators.
 275   // Return values is pair<const MachineIntr*,SchedGraphNode*>.
 276   //
 277   // void                          postord_init();
 278   // postorder_iterator    postord_begin();
 279   // postorder_iterator    postord_end();
 280   // const_postorder_iterator postord_begin() const;
 281   // const_postorder_iterator postord_end() const;
 282
 283   //
 284   // Debugging support
 285   //
 286   void          dump    () const;
 287
 288 private:
 289   friend class SchedGraphSet;           // give access to ctor
 290
 291   // disable default constructor and provide a ctor for single-block graphs
 292   /*ctor*/      SchedGraph              ();     // DO NOT IMPLEMENT
 293   /*ctor*/      SchedGraph              (const BasicBlock* bb,
 294                                          const TargetMachine& target);
 295   /*dtor*/      ~SchedGraph             ();
 296
 297   inline void   noteGraphNodeForInstr   (const MachineInstr* minstr,
 298                                          SchedGraphNode* node)
 299   {
 300     assert((*this)[minstr] == NULL);
 301     (*this)[minstr] = node;
 302   }
 303
 304   //
 305   // Graph builder
 306   //
 307   void          buildGraph              (const TargetMachine& target);
 308
 309   void          buildNodesforBB         (const TargetMachine& target,
 310                                          const BasicBlock* bb,
 311                                          vector<SchedGraphNode*>& memNodeVec,
 312                                          RegToRefVecMap& regToRefVecMap,
 313                                          ValueToDefVecMap& valueToDefVecMap);
 314
 315   void          findDefUseInfoAtInstr   (const TargetMachine& target,
 316                                          SchedGraphNode* node,
 317                                          vector<SchedGraphNode*>& memNodeVec,
 318                                          RegToRefVecMap& regToRefVecMap,
 319                                          ValueToDefVecMap& valueToDefVecMap);
 320
 321   void          addEdgesForInstruction(const MachineInstr& minstr,
 322                                      const ValueToDefVecMap& valueToDefVecMap,
 323                                      const TargetMachine& target);
 324
 325   void          addCDEdges              (const TerminatorInst* term,
 326                                          const TargetMachine& target);
 327
 328   void          addMemEdges         (const vector<SchedGraphNode*>& memNodeVec,
 329                                      const TargetMachine& target);
 330
 331   void          addCallCCEdges      (const vector<SchedGraphNode*>& memNodeVec,
 332                                      MachineCodeForBasicBlock& bbMvec,
 333                                      const TargetMachine& target);
 334
 335   void          addMachineRegEdges      (RegToRefVecMap& regToRefVecMap,
 336                                          const TargetMachine& target);
 337
 338   void          addSSAEdge              (SchedGraphNode* node,
 339                                          const RefVec& defVec,
 340                                          const Value* defValue,
 341                                          const TargetMachine& target);
 342
 343   void          addNonSSAEdgesForValue  (const Instruction* instr,
 344                                          const TargetMachine& target);
 345
 346   void          addDummyEdges           ();
 347 };
 348
 349
 350 class SchedGraphSet :
 351   public NonCopyable,
 352   private hash_map<const BasicBlock*, SchedGraph*>
 353 {
 354 private:
 355   const Method* method;
 356
 357 public:
 358   typedef hash_map<const BasicBlock*, SchedGraph*>::iterator iterator;
 359   typedef hash_map<const BasicBlock*, SchedGraph*>::const_iterator const_iterator;
 360
 361 public:
 362   /*ctor*/      SchedGraphSet           (const Method* _method,
 363                                          const TargetMachine& target);
 364   /*dtor*/      ~SchedGraphSet          ();
 365
 366   //
 367   // Accessors
 368   //
 369   SchedGraph*   getGraphForBasicBlock   (const BasicBlock* bb) const {
 370     const_iterator onePair = this->find(bb);
 371     return (onePair != this->end())? (*onePair).second : NULL;
 372   }
 373
 374   //
 375   // Iterators
 376   //
 377   iterator      begin() {
 378     return hash_map<const BasicBlock*, SchedGraph*>::begin();
 379   }
 380   iterator      end() {
 381     return hash_map<const BasicBlock*, SchedGraph*>::end();
 382   }
 383   const_iterator begin() const {
 384     return hash_map<const BasicBlock*, SchedGraph*>::begin();
 385   }
 386   const_iterator end()  const {
 387     return hash_map<const BasicBlock*, SchedGraph*>::end();
 388   }
 389
 390   //
 391   // Debugging support
 392   //
 393   void          dump    () const;
 394
 395 private:
 396   inline void   noteGraphForBlock(const BasicBlock* bb, SchedGraph* graph) {
 397     assert((*this)[bb] == NULL);
 398     (*this)[bb] = graph;
 399   }
 400
 401   //
 402   // Graph builder
 403   //
 404   void          buildGraphsForMethod    (const Method *method,
 405                                          const TargetMachine& target);
 406 };
 407
 408
 409 //********************** Sched Graph Iterators *****************************/
 410
 411 // Ok to make it a template because it shd get instantiated at most twice:
 412 // for <SchedGraphNode, SchedGraphNode::iterator> and
 413 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
 414 //
 415 template <class _NodeType, class _EdgeType, class _EdgeIter>
 416 class PredIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
 417 protected:
 418   _EdgeIter oi;
 419 public:
 420   typedef PredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 421
 422   inline PredIterator(_EdgeIter startEdge) : oi(startEdge) {}
 423
 424   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 425   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 426
 427   // operator*() differs for pred or succ iterator
 428   inline _NodeType* operator*() const { return (*oi)->getSrc(); }
 429   inline         _NodeType* operator->() const { return operator*(); }
 430
 431   inline _EdgeType* getEdge() const { return *(oi); }
 432
 433   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 434   inline _Self operator++(int) {                        // Postincrement
 435     _Self tmp(*this); ++*this; return tmp;
 436   }
 437
 438   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 439   inline _Self operator--(int) {                        // Postdecrement
 440     _Self tmp = *this; --*this; return tmp;
 441   }
 442 };
 443
 444 template <class _NodeType, class _EdgeType, class _EdgeIter>
 445 class SuccIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
 446 protected:
 447   _EdgeIter oi;
 448 public:
 449   typedef SuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 450
 451   inline SuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
 452
 453   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 454   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 455
 456   inline _NodeType* operator*() const { return (*oi)->getSink(); }
 457   inline         _NodeType* operator->() const { return operator*(); }
 458
 459   inline _EdgeType* getEdge() const { return *(oi); }
 460
 461   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 462   inline _Self operator++(int) {                        // Postincrement
 463     _Self tmp(*this); ++*this; return tmp;
 464   }
 465
 466   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 467   inline _Self operator--(int) {                        // Postdecrement
 468     _Self tmp = *this; --*this; return tmp;
 469   }
 470 };
 471
 472 //
 473 // sg_pred_iterator
 474 // sg_pred_const_iterator
 475 //
 476 typedef PredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 477     sg_pred_iterator;
 478 typedef PredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 479     sg_pred_const_iterator;
 480
 481 inline sg_pred_iterator       pred_begin(      SchedGraphNode *N) {
 482   return sg_pred_iterator(N->beginInEdges());
 483 }
 484 inline sg_pred_iterator       pred_end(        SchedGraphNode *N) {
 485   return sg_pred_iterator(N->endInEdges());
 486 }
 487 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
 488   return sg_pred_const_iterator(N->beginInEdges());
 489 }
 490 inline sg_pred_const_iterator pred_end(  const SchedGraphNode *N) {
 491   return sg_pred_const_iterator(N->endInEdges());
 492 }
 493
 494
 495 //
 496 // sg_succ_iterator
 497 // sg_succ_const_iterator
 498 //
 499 typedef SuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 500     sg_succ_iterator;
 501 typedef SuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 502     sg_succ_const_iterator;
 503
 504 inline sg_succ_iterator       succ_begin(      SchedGraphNode *N) {
 505   return sg_succ_iterator(N->beginOutEdges());
 506 }
 507 inline sg_succ_iterator       succ_end(        SchedGraphNode *N) {
 508   return sg_succ_iterator(N->endOutEdges());
 509 }
 510 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
 511   return sg_succ_const_iterator(N->beginOutEdges());
 512 }
 513 inline sg_succ_const_iterator succ_end(  const SchedGraphNode *N) {
 514   return sg_succ_const_iterator(N->endOutEdges());
 515 }
 516
 517 // Provide specializations of GraphTraits to be able to use graph iterators on
 518 // the scheduling graph!
 519 //
 520 template <> struct GraphTraits<SchedGraph*> {
 521   typedef SchedGraphNode NodeType;
 522   typedef sg_succ_iterator ChildIteratorType;
 523
 524   static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
 525   static inline ChildIteratorType child_begin(NodeType *N) {
 526     return succ_begin(N);
 527   }
 528   static inline ChildIteratorType child_end(NodeType *N) {
 529     return succ_end(N);
 530   }
 531 };
 532
 533 template <> struct GraphTraits<const SchedGraph*> {
 534   typedef const SchedGraphNode NodeType;
 535   typedef sg_succ_const_iterator ChildIteratorType;
 536
 537   static inline NodeType *getEntryNode(const SchedGraph *SG) {
 538     return SG->getRoot();
 539   }
 540   static inline ChildIteratorType child_begin(NodeType *N) {
 541     return succ_begin(N);
 542   }
 543   static inline ChildIteratorType child_end(NodeType *N) {
 544     return succ_end(N);
 545   }
 546 };
 547
 548
 549 //************************ External Functions *****************************/
 550
 551
 552 ostream& operator<<(ostream& os, const SchedGraphEdge& edge);
 553
 554 ostream& operator<<(ostream& os, const SchedGraphNode& node);
 555
 556
 557 /***************************************************************************/
 558
 559 #endif