lib/CodeGen/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 class RegToRefVecMap;
  24 class ValueToDefVecMap;
  25 class RefVec;
  26
  27 class SchedGraphNode : public SchedGraphNodeCommon {
  28
  29   MachineBasicBlock *MBB;
  30   const MachineInstr *MI;
  31
  32
  33   SchedGraphNode(unsigned nodeId, MachineBasicBlock *mbb, int indexInBB,
  34                  const TargetMachine& Target);
  35   ~SchedGraphNode();
  36
  37   friend class SchedGraph;              // give access for ctor and dtor
  38   friend class SchedGraphEdge;          // give access for adding edges
  39
  40 public:
  41
  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   void print(std::ostream &os) const;
  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   inline void   noteGraphNodeForInstr   (const MachineInstr* minstr,
  94                                          SchedGraphNode* node) {
  95     assert((*this)[minstr] == NULL);
  96     (*this)[minstr] = node;
  97   }
  98
  99   //
 100   // Graph builder
 101   //
 102   void buildGraph(const TargetMachine& target);
 103
 104   void  buildNodesForBB(const TargetMachine& target,MachineBasicBlock &MBB,
 105                         std::vector<SchedGraphNode*>& memNV,
 106                         std::vector<SchedGraphNode*>& callNV,
 107                         RegToRefVecMap& regToRefVecMap,
 108                         ValueToDefVecMap& valueToDefVecMap);
 109
 110
 111   void findDefUseInfoAtInstr(const TargetMachine& target, SchedGraphNode* node,
 112                              std::vector<SchedGraphNode*>& memNV,
 113                              std::vector<SchedGraphNode*>& callNV,
 114                              RegToRefVecMap& regToRefVecMap,
 115                              ValueToDefVecMap& valueToDefVecMap);
 116
 117   void addEdgesForInstruction(const MachineInstr& minstr,
 118                               const ValueToDefVecMap& valueToDefVecMap,
 119                               const TargetMachine& target);
 120
 121   void addCDEdges(const TerminatorInst* term, const TargetMachine& target);
 122
 123   void addMemEdges(const std::vector<SchedGraphNode*>& memNod,
 124                    const TargetMachine& target);
 125
 126   void addCallCCEdges(const std::vector<SchedGraphNode*>& memNod,
 127                       MachineBasicBlock& bbMvec,
 128                       const TargetMachine& target);
 129
 130   void addCallDepEdges(const std::vector<SchedGraphNode*>& callNV,
 131                        const TargetMachine& target);
 132
 133   void addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
 134                           const TargetMachine& target);
 135
 136   void addEdgesForValue(SchedGraphNode* refNode, const RefVec& defVec,
 137                         const Value* defValue, bool  refNodeIsDef,
 138                         bool  refNodeIsDefAndUse,
 139                         const TargetMachine& target);
 140
 141   void addDummyEdges();
 142
 143 };
 144
 145
 146
 147 class SchedGraphSet {
 148   const Function* function;
 149   std::vector<SchedGraph*> Graphs;
 150
 151   // Graph builder
 152   void buildGraphsForMethod(const Function *F, const TargetMachine& target);
 153
 154   inline void addGraph(SchedGraph* graph) {
 155     assert(graph != NULL);
 156     Graphs.push_back(graph);
 157   }
 158
 159 public:
 160   SchedGraphSet(const Function *function, const TargetMachine& target);
 161   ~SchedGraphSet();
 162
 163   //iterators
 164   typedef std::vector<SchedGraph*>::const_iterator iterator;
 165   typedef std::vector<SchedGraph*>::const_iterator const_iterator;
 166
 167   std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
 168   std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
 169
 170   // Debugging support
 171   void dump() const;
 172 };
 173
 174
 175
 176 //********************** Sched Graph Iterators *****************************/
 177
 178 // Ok to make it a template because it shd get instantiated at most twice:
 179 // for <SchedGraphNode, SchedGraphNode::iterator> and
 180 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
 181 //
 182 template <class _NodeType, class _EdgeType, class _EdgeIter>
 183 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
 184 protected:
 185   _EdgeIter oi;
 186 public:
 187   typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 188
 189   inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
 190
 191   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 192   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 193
 194   // operator*() differs for pred or succ iterator
 195   inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
 196   inline _NodeType* operator->() const { return operator*(); }
 197
 198   inline _EdgeType* getEdge() const { return *(oi); }
 199
 200   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 201   inline _Self operator++(int) {                        // Postincrement
 202     _Self tmp(*this); ++*this; return tmp;
 203   }
 204
 205   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 206   inline _Self operator--(int) {                        // Postdecrement
 207     _Self tmp = *this; --*this; return tmp;
 208   }
 209 };
 210
 211 template <class _NodeType, class _EdgeType, class _EdgeIter>
 212 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
 213 protected:
 214   _EdgeIter oi;
 215 public:
 216   typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
 217
 218   inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
 219
 220   inline bool operator==(const _Self& x) const { return oi == x.oi; }
 221   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 222
 223   inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
 224   inline _NodeType* operator->() const { return operator*(); }
 225
 226   inline _EdgeType* getEdge() const { return *(oi); }
 227
 228   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
 229   inline _Self operator++(int) {                        // Postincrement
 230     _Self tmp(*this); ++*this; return tmp;
 231   }
 232
 233   inline _Self &operator--() { --oi; return *this; }    // Predecrement
 234   inline _Self operator--(int) {                        // Postdecrement
 235     _Self tmp = *this; --*this; return tmp;
 236   }
 237 };
 238
 239 //
 240 // sg_pred_iterator
 241 // sg_pred_const_iterator
 242 //
 243 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 244     sg_pred_iterator;
 245 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 246     sg_pred_const_iterator;
 247
 248 inline sg_pred_iterator pred_begin(SchedGraphNode *N) {
 249   return sg_pred_iterator(N->beginInEdges());
 250 }
 251 inline sg_pred_iterator pred_end(SchedGraphNode *N) {
 252   return sg_pred_iterator(N->endInEdges());
 253 }
 254 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
 255   return sg_pred_const_iterator(N->beginInEdges());
 256 }
 257 inline sg_pred_const_iterator pred_end(const SchedGraphNode *N) {
 258   return sg_pred_const_iterator(N->endInEdges());
 259 }
 260
 261
 262 //
 263 // sg_succ_iterator
 264 // sg_succ_const_iterator
 265 //
 266 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 267     sg_succ_iterator;
 268 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 269     sg_succ_const_iterator;
 270
 271 inline sg_succ_iterator succ_begin(SchedGraphNode *N) {
 272   return sg_succ_iterator(N->beginOutEdges());
 273 }
 274 inline sg_succ_iterator succ_end(SchedGraphNode *N) {
 275   return sg_succ_iterator(N->endOutEdges());
 276 }
 277 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
 278   return sg_succ_const_iterator(N->beginOutEdges());
 279 }
 280 inline sg_succ_const_iterator succ_end(const SchedGraphNode *N) {
 281   return sg_succ_const_iterator(N->endOutEdges());
 282 }
 283
 284 // Provide specializations of GraphTraits to be able to use graph iterators on
 285 // the scheduling graph!
 286 //
 287 template <> struct GraphTraits<SchedGraph*> {
 288   typedef SchedGraphNode NodeType;
 289   typedef sg_succ_iterator ChildIteratorType;
 290
 291   static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
 292   static inline ChildIteratorType child_begin(NodeType *N) {
 293     return succ_begin(N);
 294   }
 295   static inline ChildIteratorType child_end(NodeType *N) {
 296     return succ_end(N);
 297   }
 298 };
 299
 300 template <> struct GraphTraits<const SchedGraph*> {
 301   typedef const SchedGraphNode NodeType;
 302   typedef sg_succ_const_iterator ChildIteratorType;
 303
 304   static inline NodeType *getEntryNode(const SchedGraph *SG) {
 305     return (NodeType*)SG->getRoot();
 306   }
 307   static inline ChildIteratorType child_begin(NodeType *N) {
 308     return succ_begin(N);
 309   }
 310   static inline ChildIteratorType child_end(NodeType *N) {
 311     return succ_end(N);
 312   }
 313 };
 314
 315 #endif