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