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