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