lib/Target/SparcV9/InstrSched/SchedGraph.h

   1 //===-- SchedGraph.h - Scheduling Graph --------------------------*- C++ -*--=//
   2 //
   3 // Purpose:
   4 //      Scheduling graph based on SSA graph plus extra dependence edges
   5 //      capturing dependences due to machine resources (machine registers,
   6 //      CC registers, and any others).
   7 //
   8 // Strategy:
   9 //      This graph tries to leverage the SSA graph as much as possible,
  10 //      but captures the extra dependences through a common interface.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CODEGEN_SCHEDGRAPH_H
  15 #define LLVM_CODEGEN_SCHEDGRAPH_H
  16
  17 #include "llvm/CodeGen/MachineInstr.h"
  18 #include "Support/GraphTraits.h"
  19 #include "Support/hash_map"
  20 #include "llvm/Transforms/Scalar.h"
  21 #include "llvm/CodeGen/SchedGraphCommon.h"
  22
  23 class RegToRefVecMap;
  24 class ValueToDefVecMap;
  25 class RefVec;
  26
  27 class SchedGraphNode : public SchedGraphNodeCommon {
  28
  29   int origIndexInBB;            // original position of machine instr in BB
  30   MachineBasicBlock *MBB;
  31   const MachineInstr *MI;
  32
  33
  34   SchedGraphNode (unsigned nodeId, MachineBasicBlock *mbb,
  35                   int   indexInBB, const TargetMachine& Target);
  36   ~SchedGraphNode       ();
  37
  38   friend class SchedGraph;              // give access for ctor and dtor
  39   friend class SchedGraphEdge;          // give access for adding edges
  40
  41 public:
  42   // Accessor methods
  43   const MachineInstr*   getMachineInstr () const { return MI; }
  44   const MachineOpCode   getOpCode       () const { return MI->getOpCode(); }
  45   bool                  isDummyNode     () const { return (MI == NULL); }
  46   MachineBasicBlock    &getMachineBasicBlock() const { return *MBB; }
  47
  48   int               getOrigIndexInBB() const { return origIndexInBB; }
  49 };
  50
  51 class SchedGraph : public SchedGraphCommon {
  52   MachineBasicBlock &MBB;
  53   hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
  54
  55 public:
  56   typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
  57   typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
  58
  59   MachineBasicBlock&               getBasicBlock() const{return MBB;}
  60   const unsigned int               getNumNodes()    const { return GraphMap.size()+2; }
  61   SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
  62     const_iterator onePair = find(MI);
  63     return (onePair != end())? onePair->second : NULL;
  64   }
  65
  66   // Debugging support
  67   void          dump    () const;
  68
  69 protected:
  70   SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
  71   ~SchedGraph();
  72
  73   // Unordered iterators.
  74   // Return values is pair<const MachineIntr*,SchedGraphNode*>.
  75   //
  76   hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
  77     return GraphMap.begin();
  78   }
  79   hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
  80     return GraphMap.end();
  81   }
  82
  83   unsigned size() { return GraphMap.size(); }
  84   iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
  85
  86   SchedGraphNode *&operator[](const MachineInstr *MI) {
  87     return GraphMap[MI];
  88   }
  89
  90 private:
  91   friend class SchedGraphSet;           // give access to ctor
  92
  93
  94
  95   inline void   noteGraphNodeForInstr   (const MachineInstr* minstr,
  96                                          SchedGraphNode* node)
  97   {
  98     assert((*this)[minstr] == NULL);
  99     (*this)[minstr] = node;
 100   }
 101
 102   //
 103   // Graph builder
 104   //
 105   void          buildGraph              (const TargetMachine& target);
 106
 107    void          buildNodesForBB         (const TargetMachine& target,
 108                                          MachineBasicBlock &MBB,
 109                                          std::vector<SchedGraphNode*>& memNV,
 110                                          std::vector<SchedGraphNode*>& callNV,
 111                                          RegToRefVecMap& regToRefVecMap,
 112                                          ValueToDefVecMap& valueToDefVecMap);
 113
 114
 115   void          findDefUseInfoAtInstr   (const TargetMachine& target,
 116                                          SchedGraphNode* node,
 117                                          std::vector<SchedGraphNode*>& memNV,
 118                                          std::vector<SchedGraphNode*>& callNV,
 119                                          RegToRefVecMap& regToRefVecMap,
 120                                          ValueToDefVecMap& valueToDefVecMap);
 121
 122
 123   void          addEdgesForInstruction(const MachineInstr& minstr,
 124                                      const ValueToDefVecMap& valueToDefVecMap,
 125                                      const TargetMachine& target);
 126
 127   void          addCDEdges              (const TerminatorInst* term,
 128                                          const TargetMachine& target);
 129
 130   void          addMemEdges         (const std::vector<SchedGraphNode*>& memNod,
 131                                      const TargetMachine& target);
 132
 133   void          addCallCCEdges      (const std::vector<SchedGraphNode*>& memNod,
 134                                      MachineBasicBlock& bbMvec,
 135                                      const TargetMachine& target);
 136   void          addCallDepEdges     (const std::vector<SchedGraphNode*>& callNV,
 137                                      const TargetMachine& target);
 138
 139   void          addMachineRegEdges      (RegToRefVecMap& regToRefVecMap,
 140                                          const TargetMachine& target);
 141
 142   void          addEdgesForValue        (SchedGraphNode* refNode,
 143                                          const RefVec& defVec,
 144                                          const Value* defValue,
 145                                          bool  refNodeIsDef,
 146                                          bool  refNodeIsDefAndUse,
 147                                          const TargetMachine& target);
 148   void          addDummyEdges();
 149
 150 };
 151
 152
 153
 154 class SchedGraphSet {
 155   const Function* function;
 156   std::vector<SchedGraph*> Graphs;
 157
 158   // Graph builder
 159   void buildGraphsForMethod (const Function *F, const TargetMachine& target);
 160
 161   inline void addGraph(SchedGraph* graph) {
 162     assert(graph != NULL);
 163     Graphs.push_back(graph);
 164   }
 165
 166 public:
 167   SchedGraphSet(const Function * function, const TargetMachine& target);
 168   ~SchedGraphSet();
 169
 170   //iterators
 171   typedef std::vector<SchedGraph*>::const_iterator iterator;
 172   typedef std::vector<SchedGraph*>::const_iterator const_iterator;
 173
 174   std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
 175   std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
 176
 177   // Debugging support
 178   void dump() const;
 179 };
 180
 181
 182
 183 //********************** Sched Graph Iterators *****************************/
 184
 185 // Ok to make it a template because it shd get instantiated at most twice:
 186 // for <SchedGraphNode, SchedGraphNode::iterator> and
 187 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
 188 //
 189 template <class _NodeType, class _EdgeType, class _EdgeIter>
 190 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
 191 protected:
 192   _EdgeIter oi;
 193 public:
 194   typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 195
 196   inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
 197
 198   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 199   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 200
 201   // operator*() differs for pred or succ iterator
 202   inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
 203   inline         _NodeType* operator->() const { return operator*(); }
 204
 205   inline _EdgeType* getEdge() const { return *(oi); }
 206
 207   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 208   inline _Self operator++(int) {                        // Postincrement
 209     _Self tmp(*this); ++*this; return tmp;
 210   }
 211
 212   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 213   inline _Self operator--(int) {                        // Postdecrement
 214     _Self tmp = *this; --*this; return tmp;
 215   }
 216 };
 217
 218 template <class _NodeType, class _EdgeType, class _EdgeIter>
 219 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
 220 protected:
 221   _EdgeIter oi;
 222 public:
 223   typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 224
 225   inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
 226
 227   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 228   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 229
 230   inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
 231   inline         _NodeType* operator->() const { return operator*(); }
 232
 233   inline _EdgeType* getEdge() const { return *(oi); }
 234
 235   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 236   inline _Self operator++(int) {                        // Postincrement
 237     _Self tmp(*this); ++*this; return tmp;
 238   }
 239
 240   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 241   inline _Self operator--(int) {                        // Postdecrement
 242     _Self tmp = *this; --*this; return tmp;
 243   }
 244 };
 245
 246 //
 247 // sg_pred_iterator
 248 // sg_pred_const_iterator
 249 //
 250 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 251     sg_pred_iterator;
 252 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 253     sg_pred_const_iterator;
 254
 255 inline sg_pred_iterator       pred_begin(      SchedGraphNode *N) {
 256   return sg_pred_iterator(N->beginInEdges());
 257 }
 258 inline sg_pred_iterator       pred_end(        SchedGraphNode *N) {
 259   return sg_pred_iterator(N->endInEdges());
 260 }
 261 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
 262   return sg_pred_const_iterator(N->beginInEdges());
 263 }
 264 inline sg_pred_const_iterator pred_end(  const SchedGraphNode *N) {
 265   return sg_pred_const_iterator(N->endInEdges());
 266 }
 267
 268
 269 //
 270 // sg_succ_iterator
 271 // sg_succ_const_iterator
 272 //
 273 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 274     sg_succ_iterator;
 275 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 276     sg_succ_const_iterator;
 277
 278 inline sg_succ_iterator       succ_begin(      SchedGraphNode *N) {
 279   return sg_succ_iterator(N->beginOutEdges());
 280 }
 281 inline sg_succ_iterator       succ_end(        SchedGraphNode *N) {
 282   return sg_succ_iterator(N->endOutEdges());
 283 }
 284 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
 285   return sg_succ_const_iterator(N->beginOutEdges());
 286 }
 287 inline sg_succ_const_iterator succ_end(  const SchedGraphNode *N) {
 288   return sg_succ_const_iterator(N->endOutEdges());
 289 }
 290
 291 // Provide specializations of GraphTraits to be able to use graph iterators on
 292 // the scheduling graph!
 293 //
 294 template <> struct GraphTraits<SchedGraph*> {
 295   typedef SchedGraphNode NodeType;
 296   typedef sg_succ_iterator ChildIteratorType;
 297
 298   static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
 299   static inline ChildIteratorType child_begin(NodeType *N) {
 300     return succ_begin(N);
 301   }
 302   static inline ChildIteratorType child_end(NodeType *N) {
 303     return succ_end(N);
 304   }
 305 };
 306
 307 template <> struct GraphTraits<const SchedGraph*> {
 308   typedef const SchedGraphNode NodeType;
 309   typedef sg_succ_const_iterator ChildIteratorType;
 310
 311   static inline NodeType *getEntryNode(const SchedGraph *SG) {
 312     return (NodeType*)SG->getRoot();
 313   }
 314   static inline ChildIteratorType child_begin(NodeType *N) {
 315     return succ_begin(N);
 316   }
 317   static inline ChildIteratorType child_end(NodeType *N) {
 318     return succ_end(N);
 319   }
 320 };
 321
 322
 323 std::ostream &operator<<(std::ostream& os, const SchedGraphEdge& edge);
 324 std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node);
 325
 326 #endif