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