lib/Target/SparcV9/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 "llvm/ADT/hash_map"
  26 #include "llvm/ADT/GraphTraits.h"
  27
  28 namespace llvm {
  29
  30 class RegToRefVecMap;
  31 class ValueToDefVecMap;
  32 class RefVec;
  33
  34 class SchedGraphNode : public SchedGraphNodeCommon {
  35
  36   MachineBasicBlock *MBB;
  37   const MachineInstr *MI;
  38
  39
  40   SchedGraphNode(unsigned nodeId, MachineBasicBlock *mbb, int indexInBB,
  41                  const TargetMachine& Target);
  42   ~SchedGraphNode();
  43
  44   friend class SchedGraph;              // give access for ctor and dtor
  45   friend class SchedGraphEdge;          // give access for adding edges
  46
  47 public:
  48
  49   // Accessor methods
  50   const MachineInstr* getMachineInstr() const { return MI; }
  51   const MachineOpCode getOpcode() const { return MI->getOpcode(); }
  52   bool isDummyNode() const { return (MI == NULL); }
  53   MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
  54
  55   void print(std::ostream &os) const;
  56 };
  57
  58 class SchedGraph : public SchedGraphCommon {
  59   MachineBasicBlock &MBB;
  60   hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
  61
  62 public:
  63   typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
  64   typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
  65
  66   MachineBasicBlock& getBasicBlock() const{return MBB;}
  67   const unsigned int getNumNodes() const { return GraphMap.size()+2; }
  68   SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
  69     const_iterator onePair = find(MI);
  70     return (onePair != end())? onePair->second : NULL;
  71   }
  72
  73   // Debugging support
  74   void dump() const;
  75
  76 protected:
  77   SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
  78   ~SchedGraph();
  79
  80   // Unordered iterators.
  81   // Return values is pair<const MachineIntr*,SchedGraphNode*>.
  82   //
  83   hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
  84     return GraphMap.begin();
  85   }
  86   hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
  87     return GraphMap.end();
  88   }
  89
  90   unsigned size() { return GraphMap.size(); }
  91   iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
  92
  93   SchedGraphNode *&operator[](const MachineInstr *MI) {
  94     return GraphMap[MI];
  95   }
  96
  97 private:
  98   friend class SchedGraphSet;           // give access to ctor
  99
 100   inline void   noteGraphNodeForInstr   (const MachineInstr* minstr,
 101                                          SchedGraphNode* node) {
 102     assert((*this)[minstr] == NULL);
 103     (*this)[minstr] = node;
 104   }
 105
 106   //
 107   // Graph builder
 108   //
 109   void buildGraph(const TargetMachine& target);
 110
 111   void  buildNodesForBB(const TargetMachine& target,MachineBasicBlock &MBB,
 112                         std::vector<SchedGraphNode*>& memNV,
 113                         std::vector<SchedGraphNode*>& callNV,
 114                         RegToRefVecMap& regToRefVecMap,
 115                         ValueToDefVecMap& valueToDefVecMap);
 116
 117
 118   void findDefUseInfoAtInstr(const TargetMachine& target, SchedGraphNode* node,
 119                              std::vector<SchedGraphNode*>& memNV,
 120                              std::vector<SchedGraphNode*>& callNV,
 121                              RegToRefVecMap& regToRefVecMap,
 122                              ValueToDefVecMap& valueToDefVecMap);
 123
 124   void addEdgesForInstruction(const MachineInstr& minstr,
 125                               const ValueToDefVecMap& valueToDefVecMap,
 126                               const TargetMachine& target);
 127
 128   void addCDEdges(const TerminatorInst* term, const TargetMachine& target);
 129
 130   void addMemEdges(const std::vector<SchedGraphNode*>& memNod,
 131                    const TargetMachine& target);
 132
 133   void addCallCCEdges(const std::vector<SchedGraphNode*>& memNod,
 134                       MachineBasicBlock& bbMvec,
 135                       const TargetMachine& target);
 136
 137   void addCallDepEdges(const std::vector<SchedGraphNode*>& callNV,
 138                        const TargetMachine& target);
 139
 140   void addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
 141                           const TargetMachine& target);
 142
 143   void addEdgesForValue(SchedGraphNode* refNode, const RefVec& defVec,
 144                         const Value* defValue, bool  refNodeIsDef,
 145                         bool  refNodeIsDefAndUse,
 146                         const TargetMachine& target);
 147
 148   void addDummyEdges();
 149
 150 };
 151
 152
 153
 154 class SchedGraphSet {
 155   const Function* function;
 156   std::vector<SchedGraph*> Graphs;
 157
 158   // Graph builder
 159   void buildGraphsForMethod(const Function *F, const TargetMachine& target);
 160
 161   inline void addGraph(SchedGraph* graph) {
 162     assert(graph != NULL);
 163     Graphs.push_back(graph);
 164   }
 165
 166 public:
 167   SchedGraphSet(const Function *function, const TargetMachine& target);
 168   ~SchedGraphSet();
 169
 170   //iterators
 171   typedef std::vector<SchedGraph*>::const_iterator iterator;
 172   typedef std::vector<SchedGraph*>::const_iterator const_iterator;
 173
 174   std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
 175   std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
 176
 177   // Debugging support
 178   void dump() const;
 179 };
 180
 181
 182
 183
 184 //
 185 // sg_pred_iterator
 186 // sg_pred_const_iterator
 187 //
 188 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 189     sg_pred_iterator;
 190 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 191     sg_pred_const_iterator;
 192
 193 inline sg_pred_iterator pred_begin(SchedGraphNode *N) {
 194   return sg_pred_iterator(N->beginInEdges());
 195 }
 196 inline sg_pred_iterator pred_end(SchedGraphNode *N) {
 197   return sg_pred_iterator(N->endInEdges());
 198 }
 199 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
 200   return sg_pred_const_iterator(N->beginInEdges());
 201 }
 202 inline sg_pred_const_iterator pred_end(const SchedGraphNode *N) {
 203   return sg_pred_const_iterator(N->endInEdges());
 204 }
 205
 206
 207 //
 208 // sg_succ_iterator
 209 // sg_succ_const_iterator
 210 //
 211 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
 212     sg_succ_iterator;
 213 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
 214     sg_succ_const_iterator;
 215
 216 inline sg_succ_iterator succ_begin(SchedGraphNode *N) {
 217   return sg_succ_iterator(N->beginOutEdges());
 218 }
 219 inline sg_succ_iterator succ_end(SchedGraphNode *N) {
 220   return sg_succ_iterator(N->endOutEdges());
 221 }
 222 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
 223   return sg_succ_const_iterator(N->beginOutEdges());
 224 }
 225 inline sg_succ_const_iterator succ_end(const SchedGraphNode *N) {
 226   return sg_succ_const_iterator(N->endOutEdges());
 227 }
 228
 229 // Provide specializations of GraphTraits to be able to use graph iterators on
 230 // the scheduling graph!
 231 //
 232 template <> struct GraphTraits<SchedGraph*> {
 233   typedef SchedGraphNode NodeType;
 234   typedef sg_succ_iterator ChildIteratorType;
 235
 236   static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
 237   static inline ChildIteratorType child_begin(NodeType *N) {
 238     return succ_begin(N);
 239   }
 240   static inline ChildIteratorType child_end(NodeType *N) {
 241     return succ_end(N);
 242   }
 243 };
 244
 245 template <> struct GraphTraits<const SchedGraph*> {
 246   typedef const SchedGraphNode NodeType;
 247   typedef sg_succ_const_iterator ChildIteratorType;
 248
 249   static inline NodeType *getEntryNode(const SchedGraph *SG) {
 250     return (NodeType*)SG->getRoot();
 251   }
 252   static inline ChildIteratorType child_begin(NodeType *N) {
 253     return succ_begin(N);
 254   }
 255   static inline ChildIteratorType child_end(NodeType *N) {
 256     return succ_end(N);
 257   }
 258 };
 259
 260 } // End llvm namespace
 261
 262 #endif