lib/CodeGen/InstrSched/SchedGraph.h

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