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. This graph only contains true, anti, and
  11 // output data dependencies for a given MachineBasicBlock. Dependencies
  12 // across iterations are also computed. Unless data dependence analysis
  13 // is provided, a conservative approach of adding dependencies between all
  14 // loads and stores is taken.
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef LLVM_MSCHEDGRAPH_H
  18 #define LLVM_MSCHEDGRAPH_H
  19 #include "DependenceAnalyzer.h"
  20 #include "llvm/Analysis/AliasAnalysis.h"
  21 #include "llvm/CodeGen/MachineInstr.h"
  22 #include "llvm/Target/TargetMachine.h"
  23 #include "llvm/Target/TargetData.h"
  24 #include "llvm/ADT/GraphTraits.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/ADT/iterator"
  27 #include <vector>
  28
  29 namespace llvm {
  30
  31   class MSchedGraph;
  32   class MSchedGraphNode;
  33   template<class IteratorType, class NodeType>
  34   class MSchedGraphNodeIterator;
  35
  36   //MSchedGraphEdge encapsulates the data dependence between nodes. It
  37   //identifies the dependence type, on what, and the iteration
  38   //difference
  39   struct MSchedGraphEdge {
  40     enum DataDepOrderType {
  41       TrueDep, AntiDep, OutputDep, NonDataDep
  42     };
  43
  44     enum MSchedGraphEdgeType {
  45       MemoryDep, ValueDep, MachineRegister, BranchDep
  46     };
  47
  48     //Get or set edge data
  49     MSchedGraphNode *getDest() const { return dest; }
  50     unsigned getIteDiff() { return iteDiff; }
  51     unsigned getDepOrderType() { return depOrderType; }
  52     void setDest(MSchedGraphNode *newDest) { dest = newDest; }
  53
  54   private:
  55     friend class MSchedGraphNode;
  56     MSchedGraphEdge(MSchedGraphNode *destination, MSchedGraphEdgeType type,
  57                     unsigned deptype, unsigned diff)
  58       : dest(destination), depType(type), depOrderType(deptype), iteDiff(diff) {}
  59
  60     MSchedGraphNode *dest;
  61     MSchedGraphEdgeType depType;
  62     unsigned depOrderType;
  63     unsigned iteDiff;
  64   };
  65
  66   //MSchedGraphNode represents a machine instruction and its
  67   //corresponding latency. Each node also contains a list of its
  68   //predecessors and sucessors.
  69   class MSchedGraphNode {
  70
  71     const MachineInstr* Inst; //Machine Instruction
  72     MSchedGraph* Parent; //Graph this node belongs to
  73     unsigned index; //Index in BB
  74     unsigned latency; //Latency of Instruction
  75     bool isBranchInstr; //Is this node the branch instr or not
  76
  77     std::vector<MSchedGraphNode*> Predecessors; //Predecessor Nodes
  78     std::vector<MSchedGraphEdge> Successors; //Successor edges
  79
  80   public:
  81     MSchedGraphNode(const MachineInstr *inst, MSchedGraph *graph,
  82                     unsigned index, unsigned late=0, bool isBranch=false);
  83
  84     MSchedGraphNode(const MSchedGraphNode &N);
  85
  86     //Iterators - Predecessor and Succussor
  87     typedef std::vector<MSchedGraphNode*>::iterator pred_iterator;
  88     pred_iterator pred_begin() { return Predecessors.begin(); }
  89     pred_iterator pred_end() { return Predecessors.end(); }
  90     unsigned pred_size() { return Predecessors.size(); }
  91
  92     typedef std::vector<MSchedGraphNode*>::const_iterator pred_const_iterator;
  93     pred_const_iterator pred_begin() const { return Predecessors.begin(); }
  94     pred_const_iterator pred_end() const { return Predecessors.end(); }
  95
  96     typedef MSchedGraphNodeIterator<std::vector<MSchedGraphEdge>::const_iterator,
  97                                     const MSchedGraphNode> succ_const_iterator;
  98     succ_const_iterator succ_begin() const;
  99     succ_const_iterator succ_end() const;
 100
 101     typedef MSchedGraphNodeIterator<std::vector<MSchedGraphEdge>::iterator,
 102                                     MSchedGraphNode> succ_iterator;
 103     succ_iterator succ_begin();
 104     succ_iterator succ_end();
 105     unsigned succ_size() { return Successors.size(); }
 106
 107     //Get or set predecessor nodes, or successor edges
 108     void setPredecessor(unsigned index, MSchedGraphNode *dest) {
 109       Predecessors[index] = dest;
 110     }
 111
 112     MSchedGraphNode* getPredecessor(unsigned index) {
 113       return Predecessors[index];
 114     }
 115
 116     MSchedGraphEdge* getSuccessor(unsigned index) {
 117       return &Successors[index];
 118     }
 119
 120     void deleteSuccessor(MSchedGraphNode *node) {
 121       for (unsigned i = 0; i != Successors.size(); ++i)
 122         if (Successors[i].getDest() == node) {
 123           Successors.erase(Successors.begin()+i);
 124           node->Predecessors.erase(std::find(node->Predecessors.begin(),
 125                                              node->Predecessors.end(), this));
 126           --i; //Decrease index var since we deleted a node
 127         }
 128     }
 129
 130     void addOutEdge(MSchedGraphNode *destination,
 131                     MSchedGraphEdge::MSchedGraphEdgeType type,
 132                     unsigned deptype, unsigned diff=0) {
 133       Successors.push_back(MSchedGraphEdge(destination, type, deptype,diff));
 134       destination->Predecessors.push_back(this);
 135     }
 136
 137     //General methods to get and set data for the node
 138     const MachineInstr* getInst() { return Inst; }
 139     MSchedGraph* getParent() { return Parent; }
 140     bool hasPredecessors() { return (Predecessors.size() > 0); }
 141     bool hasSuccessors() { return (Successors.size() > 0); }
 142     unsigned getLatency() { return latency; }
 143     unsigned getLatency() const { return latency; }
 144     unsigned getIndex() { return index; }
 145     unsigned getIteDiff(MSchedGraphNode *succ);
 146     MSchedGraphEdge getInEdge(MSchedGraphNode *pred);
 147     unsigned getInEdgeNum(MSchedGraphNode *pred);
 148     bool isSuccessor(MSchedGraphNode *);
 149     bool isPredecessor(MSchedGraphNode *);
 150     bool isBranch() { return isBranchInstr; }
 151
 152     //Debug support
 153     void print(std::ostream &os) const;
 154     void setParent(MSchedGraph *p) { Parent = p; }
 155   };
 156
 157   //Node iterator for graph generation
 158   template<class IteratorType, class NodeType>
 159   class MSchedGraphNodeIterator : public forward_iterator<NodeType*, ptrdiff_t> {
 160     IteratorType I;   // std::vector<MSchedGraphEdge>::iterator or const_iterator
 161   public:
 162     MSchedGraphNodeIterator(IteratorType i) : I(i) {}
 163
 164     bool operator==(const MSchedGraphNodeIterator RHS) const { return I == RHS.I; }
 165     bool operator!=(const MSchedGraphNodeIterator RHS) const { return I != RHS.I; }
 166
 167     const MSchedGraphNodeIterator &operator=(const MSchedGraphNodeIterator &RHS) {
 168       I = RHS.I;
 169       return *this;
 170     }
 171
 172     NodeType* operator*() const {
 173       return I->getDest();
 174     }
 175     NodeType* operator->() const { return operator*(); }
 176
 177     MSchedGraphNodeIterator& operator++() {                // Preincrement
 178       ++I;
 179       return *this;
 180     }
 181     MSchedGraphNodeIterator operator++(int) { // Postincrement
 182       MSchedGraphNodeIterator tmp = *this; ++*this; return tmp;
 183     }
 184
 185     MSchedGraphEdge &getEdge() {
 186       return *I;
 187     }
 188     const MSchedGraphEdge &getEdge() const {
 189       return *I;
 190     }
 191   };
 192
 193   inline MSchedGraphNode::succ_const_iterator MSchedGraphNode::succ_begin() const {
 194     return succ_const_iterator(Successors.begin());
 195   }
 196   inline MSchedGraphNode::succ_const_iterator MSchedGraphNode::succ_end() const {
 197     return succ_const_iterator(Successors.end());
 198   }
 199   inline MSchedGraphNode::succ_iterator MSchedGraphNode::succ_begin() {
 200     return succ_iterator(Successors.begin());
 201   }
 202   inline MSchedGraphNode::succ_iterator MSchedGraphNode::succ_end() {
 203     return succ_iterator(Successors.end());
 204   }
 205
 206   // ostream << operator for MSGraphNode class
 207   inline std::ostream &operator<<(std::ostream &os,
 208                                   const MSchedGraphNode &node) {
 209     node.print(os);
 210     return os;
 211   }
 212
 213
 214   // Provide specializations of GraphTraits to be able to use graph
 215   // iterators on the scheduling graph!
 216   //
 217   template <> struct GraphTraits<MSchedGraphNode*> {
 218     typedef MSchedGraphNode NodeType;
 219     typedef MSchedGraphNode::succ_iterator ChildIteratorType;
 220
 221     static inline ChildIteratorType child_begin(NodeType *N) {
 222       return N->succ_begin();
 223     }
 224     static inline ChildIteratorType child_end(NodeType *N) {
 225       return N->succ_end();
 226     }
 227
 228     static NodeType *getEntryNode(NodeType* N) { return N; }
 229   };
 230
 231
 232
 233   //Graph class to represent dependence graph
 234   class MSchedGraph {
 235
 236     std::vector<const MachineBasicBlock *> BBs; //Machine basic block
 237     const TargetMachine &Target; //Target Machine
 238
 239     //Nodes
 240     std::map<const MachineInstr*, MSchedGraphNode*> GraphMap;
 241
 242     //Add Nodes and Edges to this graph for our BB
 243     typedef std::pair<int, MSchedGraphNode*> OpIndexNodePair;
 244     void buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ignoreInstrs, DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm);
 245     void addValueEdges(std::vector<OpIndexNodePair> &NodesInMap,
 246                        MSchedGraphNode *node,
 247                        bool nodeIsUse, bool nodeIsDef, std::vector<const MachineInstr*> &phiInstrs, int diff=0);
 248     void addMachRegEdges(std::map<int,
 249                          std::vector<OpIndexNodePair> >& regNumtoNodeMap);
 250     void addMemEdges(const std::vector<MSchedGraphNode*>& memInst,
 251                      DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm);
 252     void addBranchEdges();
 253
 254   public:
 255     MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ,
 256                 std::map<const MachineInstr*, unsigned> &ignoreInstrs,
 257                 DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm);
 258
 259     //Copy constructor with maps to link old nodes to new nodes
 260     MSchedGraph(const MSchedGraph &G, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes);
 261
 262     MSchedGraph(std::vector<const MachineBasicBlock*> &bbs,
 263                 const TargetMachine &targ,
 264                 std::map<const MachineInstr*, unsigned> &ignoreInstrs,
 265                 DependenceAnalyzer &DA,
 266                 std::map<MachineInstr*, Instruction*> &machineTollvm);
 267
 268     //Print graph
 269     void print(std::ostream &os) const;
 270
 271     //Deconstructor!
 272     ~MSchedGraph();
 273
 274     //Add or delete nodes from the Graph
 275     void addNode(const MachineInstr* MI, MSchedGraphNode *node);
 276     void deleteNode(MSchedGraphNode *node);
 277     int totalDelay();
 278
 279     //iterators
 280     typedef std::map<const MachineInstr*, MSchedGraphNode*>::iterator iterator;
 281     typedef std::map<const MachineInstr*, MSchedGraphNode*>::const_iterator const_iterator;
 282     typedef std::map<const MachineInstr*, MSchedGraphNode*>::reverse_iterator reverse_iterator;
 283     iterator find(const MachineInstr* I) { return GraphMap.find(I); }
 284     iterator end() { return GraphMap.end(); }
 285     iterator begin() { return GraphMap.begin(); }
 286     unsigned size() { return GraphMap.size(); }
 287     reverse_iterator rbegin() { return GraphMap.rbegin(); }
 288     reverse_iterator rend() { return GraphMap.rend(); }
 289
 290     //Get Target or original machine basic block
 291     const TargetMachine* getTarget() { return &Target; }
 292     std::vector<const MachineBasicBlock*> getBBs() { return BBs; }
 293   };
 294
 295
 296
 297
 298
 299   // Provide specializations of GraphTraits to be able to use graph
 300   // iterators on the scheduling graph
 301   static MSchedGraphNode& getSecond(std::pair<const MachineInstr* const,
 302                                     MSchedGraphNode*> &Pair) {
 303     return *Pair.second;
 304   }
 305
 306   template <> struct GraphTraits<MSchedGraph*> {
 307     typedef MSchedGraphNode NodeType;
 308     typedef MSchedGraphNode::succ_iterator ChildIteratorType;
 309
 310     static inline ChildIteratorType child_begin(NodeType *N) {
 311       return N->succ_begin();
 312     }
 313     static inline ChildIteratorType child_end(NodeType *N) {
 314       return N->succ_end();
 315     }
 316
 317     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
 318            MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
 319
 320     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
 321     static nodes_iterator nodes_begin(MSchedGraph *G) {
 322       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
 323     }
 324     static nodes_iterator nodes_end(MSchedGraph *G) {
 325       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
 326     }
 327
 328   };
 329
 330   template <> struct GraphTraits<const MSchedGraph*> {
 331     typedef const MSchedGraphNode NodeType;
 332     typedef MSchedGraphNode::succ_const_iterator ChildIteratorType;
 333
 334     static inline ChildIteratorType child_begin(NodeType *N) {
 335       return N->succ_begin();
 336     }
 337     static inline ChildIteratorType child_end(NodeType *N) {
 338       return N->succ_end();
 339     }
 340     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
 341                                                      MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
 342
 343     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
 344     static nodes_iterator nodes_begin(MSchedGraph *G) {
 345       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
 346     }
 347     static nodes_iterator nodes_end(MSchedGraph *G) {
 348       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
 349     }
 350   };
 351
 352   template <> struct GraphTraits<Inverse<MSchedGraph*> > {
 353     typedef MSchedGraphNode NodeType;
 354     typedef MSchedGraphNode::pred_iterator ChildIteratorType;
 355
 356     static inline ChildIteratorType child_begin(NodeType *N) {
 357       return N->pred_begin();
 358     }
 359     static inline ChildIteratorType child_end(NodeType *N) {
 360       return N->pred_end();
 361     }
 362     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
 363            MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
 364
 365     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
 366     static nodes_iterator nodes_begin(MSchedGraph *G) {
 367       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
 368     }
 369     static nodes_iterator nodes_end(MSchedGraph *G) {
 370       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
 371     }
 372   };
 373
 374   template <> struct GraphTraits<Inverse<const MSchedGraph*> > {
 375     typedef const MSchedGraphNode NodeType;
 376     typedef MSchedGraphNode::pred_const_iterator ChildIteratorType;
 377
 378     static inline ChildIteratorType child_begin(NodeType *N) {
 379       return N->pred_begin();
 380     }
 381     static inline ChildIteratorType child_end(NodeType *N) {
 382       return N->pred_end();
 383     }
 384
 385     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
 386                                                      MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
 387
 388     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
 389     static nodes_iterator nodes_begin(MSchedGraph *G) {
 390       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
 391     }
 392     static nodes_iterator nodes_end(MSchedGraph *G) {
 393       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
 394     }
 395   };
 396 }
 397
 398 #endif