lib/CodeGen/InstrSched/SchedGraph.h

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