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