lib/Target/SparcV9/ModuloScheduling/MSchedGraph.h

   1 //===-- MSchedGraph.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 // A graph class for dependencies
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_MSCHEDGRAPH_H
  15 #define LLVM_MSCHEDGRAPH_H
  16
  17 #include "llvm/CodeGen/MachineInstr.h"
  18 #include "llvm/Target/TargetMachine.h"
  19 #include "Support/GraphTraits.h"
  20 #include "Support/STLExtras.h"
  21 #include "Support/iterator"
  22 #include <vector>
  23
  24 namespace llvm {
  25   class MSchedGraph;
  26   class MSchedGraphNode;
  27   template<class IteratorType, class NodeType>
  28   class MSchedGraphNodeIterator;
  29
  30
  31   struct MSchedGraphEdge {
  32     enum DataDepOrderType {
  33       TrueDep, AntiDep, OutputDep, NonDataDep
  34     };
  35
  36     enum MSchedGraphEdgeType {
  37       MemoryDep, ValueDep, MachineRegister
  38     };
  39
  40     MSchedGraphNode *getDest() const { return dest; }
  41     unsigned getIteDiff() { return iteDiff; }
  42     unsigned getDepOrderType() { return depOrderType; }
  43
  44   private:
  45     friend class MSchedGraphNode;
  46     MSchedGraphEdge(MSchedGraphNode *destination, MSchedGraphEdgeType type,
  47                     unsigned deptype, unsigned diff)
  48       : dest(destination), depType(type), depOrderType(deptype), iteDiff(diff) {}
  49
  50     MSchedGraphNode *dest;
  51     MSchedGraphEdgeType depType;
  52     unsigned depOrderType;
  53     unsigned iteDiff;
  54   };
  55
  56   class MSchedGraphNode {
  57
  58     const MachineInstr* Inst; //Machine Instruction
  59     MSchedGraph* Parent; //Graph this node belongs to
  60     unsigned latency; //Latency of Instruction
  61
  62     std::vector<MSchedGraphNode*> Predecessors; //Predecessor Nodes
  63     std::vector<MSchedGraphEdge> Successors;
  64
  65   public:
  66     MSchedGraphNode(const MachineInstr *inst, MSchedGraph *graph,
  67                     unsigned late=0);
  68
  69     //Iterators
  70     typedef std::vector<MSchedGraphNode*>::iterator pred_iterator;
  71     pred_iterator pred_begin() { return Predecessors.begin(); }
  72     pred_iterator pred_end() { return Predecessors.end(); }
  73
  74     typedef std::vector<MSchedGraphNode*>::const_iterator pred_const_iterator;
  75     pred_const_iterator pred_begin() const { return Predecessors.begin(); }
  76     pred_const_iterator pred_end() const { return Predecessors.end(); }
  77
  78     // Successor iterators.
  79     typedef MSchedGraphNodeIterator<std::vector<MSchedGraphEdge>::const_iterator,
  80                                     const MSchedGraphNode> succ_const_iterator;
  81     succ_const_iterator succ_begin() const;
  82     succ_const_iterator succ_end() const;
  83
  84     typedef MSchedGraphNodeIterator<std::vector<MSchedGraphEdge>::iterator,
  85                                     MSchedGraphNode> succ_iterator;
  86     succ_iterator succ_begin();
  87     succ_iterator succ_end();
  88
  89
  90     void addOutEdge(MSchedGraphNode *destination,
  91                     MSchedGraphEdge::MSchedGraphEdgeType type,
  92                     unsigned deptype, unsigned diff=0) {
  93       Successors.push_back(MSchedGraphEdge(destination, type, deptype,diff));
  94       destination->Predecessors.push_back(this);
  95     }
  96     const MachineInstr* getInst() { return Inst; }
  97     MSchedGraph* getParent() { return Parent; }
  98     bool hasPredecessors() { return (Predecessors.size() > 0); }
  99     bool hasSuccessors() { return (Successors.size() > 0); }
 100     int getLatency() { return latency; }
 101     MSchedGraphEdge getInEdge(MSchedGraphNode *pred);
 102
 103     //Debug support
 104     void print(std::ostream &os) const;
 105
 106   };
 107
 108   template<class IteratorType, class NodeType>
 109   class MSchedGraphNodeIterator : public forward_iterator<NodeType*, ptrdiff_t> {
 110     IteratorType I;   // std::vector<MSchedGraphEdge>::iterator or const_iterator
 111   public:
 112     MSchedGraphNodeIterator(IteratorType i) : I(i) {}
 113
 114     bool operator==(const MSchedGraphNodeIterator RHS) const { return I == RHS.I; }
 115     bool operator!=(const MSchedGraphNodeIterator RHS) const { return I != RHS.I; }
 116
 117     const MSchedGraphNodeIterator &operator=(const MSchedGraphNodeIterator &RHS) {
 118       I = RHS.I;
 119       return *this;
 120     }
 121
 122     NodeType* operator*() const {
 123       return I->getDest();
 124     }
 125     NodeType* operator->() const { return operator*(); }
 126
 127     MSchedGraphNodeIterator& operator++() {                // Preincrement
 128       ++I;
 129       return *this;
 130     }
 131     MSchedGraphNodeIterator operator++(int) { // Postincrement
 132       MSchedGraphNodeIterator tmp = *this; ++*this; return tmp;
 133     }
 134
 135     MSchedGraphEdge &getEdge() {
 136       return *I;
 137     }
 138     const MSchedGraphEdge &getEdge() const {
 139       return *I;
 140     }
 141   };
 142
 143   inline MSchedGraphNode::succ_const_iterator MSchedGraphNode::succ_begin() const {
 144     return succ_const_iterator(Successors.begin());
 145   }
 146   inline MSchedGraphNode::succ_const_iterator MSchedGraphNode::succ_end() const {
 147     return succ_const_iterator(Successors.end());
 148   }
 149   inline MSchedGraphNode::succ_iterator MSchedGraphNode::succ_begin() {
 150     return succ_iterator(Successors.begin());
 151   }
 152   inline MSchedGraphNode::succ_iterator MSchedGraphNode::succ_end() {
 153     return succ_iterator(Successors.end());
 154   }
 155
 156   // ostream << operator for MSGraphNode class
 157   inline std::ostream &operator<<(std::ostream &os,
 158                                   const MSchedGraphNode &node) {
 159     node.print(os);
 160     return os;
 161   }
 162
 163
 164
 165   class MSchedGraph {
 166
 167     const MachineBasicBlock *BB; //Machine basic block
 168     const TargetMachine &Target; //Target Machine
 169
 170     //Nodes
 171     std::map<const MachineInstr*, MSchedGraphNode*> GraphMap;
 172
 173     //Add Nodes and Edges to this graph for our BB
 174     typedef std::pair<int, MSchedGraphNode*> OpIndexNodePair;
 175     void buildNodesAndEdges();
 176     void addValueEdges(std::vector<OpIndexNodePair> &NodesInMap,
 177                        MSchedGraphNode *node,
 178                        bool nodeIsUse, bool nodeIsDef, int diff=0);
 179     void addMachRegEdges(std::map<int,
 180                          std::vector<OpIndexNodePair> >& regNumtoNodeMap);
 181     void addMemEdges(const std::vector<MSchedGraphNode*>& memInst);
 182
 183   public:
 184     MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ);
 185     ~MSchedGraph();
 186
 187     //Add Nodes to the Graph
 188     void addNode(const MachineInstr* MI, MSchedGraphNode *node);
 189
 190     //iterators
 191     typedef std::map<const MachineInstr*, MSchedGraphNode*>::iterator iterator;
 192     typedef std::map<const MachineInstr*, MSchedGraphNode*>::const_iterator const_iterator;
 193     typedef std::map<const MachineInstr*, MSchedGraphNode*>::reverse_iterator reverse_iterator;
 194     iterator find(const MachineInstr* I) { return GraphMap.find(I); }
 195     iterator end() { return GraphMap.end(); }
 196     iterator begin() { return GraphMap.begin(); }
 197     reverse_iterator rbegin() { return GraphMap.rbegin(); }
 198     reverse_iterator rend() { return GraphMap.rend(); }
 199
 200   };
 201
 202
 203   static MSchedGraphNode& getSecond(std::pair<const MachineInstr* const,
 204                                          MSchedGraphNode*> &Pair) {
 205     return *Pair.second;
 206   }
 207
 208
 209
 210   // Provide specializations of GraphTraits to be able to use graph
 211   // iterators on the scheduling graph!
 212   //
 213   template <> struct GraphTraits<MSchedGraph*> {
 214     typedef MSchedGraphNode NodeType;
 215     typedef MSchedGraphNode::succ_iterator ChildIteratorType;
 216
 217     static inline ChildIteratorType child_begin(NodeType *N) {
 218       return N->succ_begin();
 219     }
 220     static inline ChildIteratorType child_end(NodeType *N) {
 221       return N->succ_end();
 222     }
 223
 224     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
 225            MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
 226
 227     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
 228     static nodes_iterator nodes_begin(MSchedGraph *G) {
 229       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
 230     }
 231     static nodes_iterator nodes_end(MSchedGraph *G) {
 232       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
 233     }
 234
 235
 236   };
 237
 238   template <> struct GraphTraits<const MSchedGraph*> {
 239     typedef const MSchedGraphNode NodeType;
 240     typedef MSchedGraphNode::succ_const_iterator ChildIteratorType;
 241
 242     static inline ChildIteratorType child_begin(NodeType *N) {
 243       return N->succ_begin();
 244     }
 245     static inline ChildIteratorType child_end(NodeType *N) {
 246       return N->succ_end();
 247     }
 248     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
 249                                                      MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
 250
 251     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
 252     static nodes_iterator nodes_begin(MSchedGraph *G) {
 253       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
 254     }
 255     static nodes_iterator nodes_end(MSchedGraph *G) {
 256       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
 257     }
 258   };
 259
 260   template <> struct GraphTraits<Inverse<MSchedGraph*> > {
 261     typedef MSchedGraphNode NodeType;
 262     typedef MSchedGraphNode::pred_iterator ChildIteratorType;
 263
 264     static inline ChildIteratorType child_begin(NodeType *N) {
 265       return N->pred_begin();
 266     }
 267     static inline ChildIteratorType child_end(NodeType *N) {
 268       return N->pred_end();
 269     }
 270     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
 271            MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
 272
 273     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
 274     static nodes_iterator nodes_begin(MSchedGraph *G) {
 275       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
 276     }
 277     static nodes_iterator nodes_end(MSchedGraph *G) {
 278       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
 279     }
 280   };
 281
 282   template <> struct GraphTraits<Inverse<const MSchedGraph*> > {
 283     typedef const MSchedGraphNode NodeType;
 284     typedef MSchedGraphNode::pred_const_iterator ChildIteratorType;
 285
 286     static inline ChildIteratorType child_begin(NodeType *N) {
 287       return N->pred_begin();
 288     }
 289     static inline ChildIteratorType child_end(NodeType *N) {
 290       return N->pred_end();
 291     }
 292
 293     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
 294                                                      MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
 295
 296     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
 297     static nodes_iterator nodes_begin(MSchedGraph *G) {
 298       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
 299     }
 300     static nodes_iterator nodes_end(MSchedGraph *G) {
 301       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
 302     }
 303   };
 304
 305
 306
 307
 308 }
 309
 310 #endif