LLVM API Documentation

MSchedGraph.h

Go to the documentation of this file.
00001 //===-- MSchedGraph.h - Scheduling Graph ------------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // A graph class for dependencies. This graph only contains true, anti, and
00011 // output data dependencies for a given MachineBasicBlock. Dependencies
00012 // across iterations are also computed. Unless data dependence analysis
00013 // is provided, a conservative approach of adding dependencies between all
00014 // loads and stores is taken.
00015 //===----------------------------------------------------------------------===//
00016 
00017 #ifndef LLVM_MSCHEDGRAPH_H
00018 #define LLVM_MSCHEDGRAPH_H
00019 #include "DependenceAnalyzer.h"
00020 #include "llvm/Analysis/AliasAnalysis.h"
00021 #include "llvm/CodeGen/MachineInstr.h"
00022 #include "llvm/Target/TargetMachine.h"
00023 #include "llvm/Target/TargetData.h"
00024 #include "llvm/ADT/GraphTraits.h"
00025 #include "llvm/ADT/STLExtras.h"
00026 #include "llvm/ADT/iterator"
00027 #include <vector>
00028 
00029 namespace llvm {
00030 
00031   class MSchedGraph;
00032   class MSchedGraphNode;
00033   template<class IteratorType, class NodeType>
00034   class MSchedGraphNodeIterator;
00035 
00036   //MSchedGraphEdge encapsulates the data dependence between nodes. It
00037   //identifies the dependence type, on what, and the iteration
00038   //difference
00039   struct MSchedGraphEdge {
00040     enum DataDepOrderType {
00041       TrueDep, AntiDep, OutputDep, NonDataDep
00042     };
00043 
00044     enum MSchedGraphEdgeType {
00045       MemoryDep, ValueDep, MachineRegister, BranchDep
00046     };
00047 
00048     //Get or set edge data
00049     MSchedGraphNode *getDest() const { return dest; }
00050     unsigned getIteDiff() { return iteDiff; }
00051     unsigned getDepOrderType() { return depOrderType; }
00052     void setDest(MSchedGraphNode *newDest) { dest = newDest; }
00053 
00054   private:
00055     friend class MSchedGraphNode;
00056     MSchedGraphEdge(MSchedGraphNode *destination, MSchedGraphEdgeType type,
00057                     unsigned deptype, unsigned diff)
00058       : dest(destination), depType(type), depOrderType(deptype), iteDiff(diff) {}
00059 
00060     MSchedGraphNode *dest;
00061     MSchedGraphEdgeType depType;
00062     unsigned depOrderType;
00063     unsigned iteDiff;
00064   };
00065 
00066   //MSchedGraphNode represents a machine instruction and its
00067   //corresponding latency. Each node also contains a list of its
00068   //predecessors and sucessors.
00069   class MSchedGraphNode {
00070 
00071     const MachineInstr* Inst; //Machine Instruction
00072     MSchedGraph* Parent; //Graph this node belongs to
00073     unsigned index; //Index in BB
00074     unsigned latency; //Latency of Instruction
00075     bool isBranchInstr; //Is this node the branch instr or not
00076 
00077     std::vector<MSchedGraphNode*> Predecessors; //Predecessor Nodes
00078     std::vector<MSchedGraphEdge> Successors; //Successor edges
00079 
00080   public:
00081     MSchedGraphNode(const MachineInstr *inst, MSchedGraph *graph,
00082                     unsigned index, unsigned late=0, bool isBranch=false);
00083 
00084     MSchedGraphNode(const MSchedGraphNode &N);
00085 
00086     //Iterators - Predecessor and Succussor
00087     typedef std::vector<MSchedGraphNode*>::iterator pred_iterator;
00088     pred_iterator pred_begin() { return Predecessors.begin(); }
00089     pred_iterator pred_end() { return Predecessors.end(); }
00090     unsigned pred_size() { return Predecessors.size(); }
00091 
00092     typedef std::vector<MSchedGraphNode*>::const_iterator pred_const_iterator;
00093     pred_const_iterator pred_begin() const { return Predecessors.begin(); }
00094     pred_const_iterator pred_end() const { return Predecessors.end(); }
00095 
00096     typedef MSchedGraphNodeIterator<std::vector<MSchedGraphEdge>::const_iterator,
00097                                     const MSchedGraphNode> succ_const_iterator;
00098     succ_const_iterator succ_begin() const;
00099     succ_const_iterator succ_end() const;
00100 
00101     typedef MSchedGraphNodeIterator<std::vector<MSchedGraphEdge>::iterator,
00102                                     MSchedGraphNode> succ_iterator;
00103     succ_iterator succ_begin();
00104     succ_iterator succ_end();
00105     unsigned succ_size() { return Successors.size(); }
00106 
00107     //Get or set predecessor nodes, or successor edges
00108     void setPredecessor(unsigned index, MSchedGraphNode *dest) {
00109       Predecessors[index] = dest;
00110     }
00111 
00112     MSchedGraphNode* getPredecessor(unsigned index) {
00113       return Predecessors[index];
00114     }
00115 
00116     MSchedGraphEdge* getSuccessor(unsigned index) {
00117       return &Successors[index];
00118     }
00119 
00120     void deleteSuccessor(MSchedGraphNode *node) {
00121       for (unsigned i = 0; i != Successors.size(); ++i)
00122         if (Successors[i].getDest() == node) {
00123           Successors.erase(Successors.begin()+i);
00124           node->Predecessors.erase(std::find(node->Predecessors.begin(),
00125                                              node->Predecessors.end(), this));
00126           --i; //Decrease index var since we deleted a node
00127         }
00128     }
00129 
00130     void addOutEdge(MSchedGraphNode *destination,
00131                     MSchedGraphEdge::MSchedGraphEdgeType type,
00132                     unsigned deptype, unsigned diff=0) {
00133       Successors.push_back(MSchedGraphEdge(destination, type, deptype,diff));
00134       destination->Predecessors.push_back(this);
00135     }
00136 
00137     //General methods to get and set data for the node
00138     const MachineInstr* getInst() { return Inst; }
00139     MSchedGraph* getParent() { return Parent; }
00140     bool hasPredecessors() { return (Predecessors.size() > 0); }
00141     bool hasSuccessors() { return (Successors.size() > 0); }
00142     unsigned getLatency() { return latency; }
00143     unsigned getLatency() const { return latency; }
00144     unsigned getIndex() { return index; }
00145     unsigned getIteDiff(MSchedGraphNode *succ);
00146     MSchedGraphEdge getInEdge(MSchedGraphNode *pred);
00147     unsigned getInEdgeNum(MSchedGraphNode *pred);
00148     bool isSuccessor(MSchedGraphNode *);
00149     bool isPredecessor(MSchedGraphNode *);
00150     bool isBranch() { return isBranchInstr; }
00151 
00152     //Debug support
00153     void print(std::ostream &os) const;
00154     void setParent(MSchedGraph *p) { Parent = p; }
00155   };
00156 
00157   //Node iterator for graph generation
00158   template<class IteratorType, class NodeType>
00159   class MSchedGraphNodeIterator : public forward_iterator<NodeType*, ptrdiff_t> {
00160     IteratorType I;   // std::vector<MSchedGraphEdge>::iterator or const_iterator
00161   public:
00162     MSchedGraphNodeIterator(IteratorType i) : I(i) {}
00163 
00164     bool operator==(const MSchedGraphNodeIterator RHS) const { return I == RHS.I; }
00165     bool operator!=(const MSchedGraphNodeIterator RHS) const { return I != RHS.I; }
00166 
00167     const MSchedGraphNodeIterator &operator=(const MSchedGraphNodeIterator &RHS) {
00168       I = RHS.I;
00169       return *this;
00170     }
00171 
00172     NodeType* operator*() const {
00173       return I->getDest();
00174     }
00175     NodeType* operator->() const { return operator*(); }
00176 
00177     MSchedGraphNodeIterator& operator++() {                // Preincrement
00178       ++I;
00179       return *this;
00180     }
00181     MSchedGraphNodeIterator operator++(int) { // Postincrement
00182       MSchedGraphNodeIterator tmp = *this; ++*this; return tmp;
00183     }
00184 
00185     MSchedGraphEdge &getEdge() {
00186       return *I;
00187     }
00188     const MSchedGraphEdge &getEdge() const {
00189       return *I;
00190     }
00191   };
00192 
00193   inline MSchedGraphNode::succ_const_iterator MSchedGraphNode::succ_begin() const {
00194     return succ_const_iterator(Successors.begin());
00195   }
00196   inline MSchedGraphNode::succ_const_iterator MSchedGraphNode::succ_end() const {
00197     return succ_const_iterator(Successors.end());
00198   }
00199   inline MSchedGraphNode::succ_iterator MSchedGraphNode::succ_begin() {
00200     return succ_iterator(Successors.begin());
00201   }
00202   inline MSchedGraphNode::succ_iterator MSchedGraphNode::succ_end() {
00203     return succ_iterator(Successors.end());
00204   }
00205 
00206   // ostream << operator for MSGraphNode class
00207   inline std::ostream &operator<<(std::ostream &os,
00208                                   const MSchedGraphNode &node) {
00209     node.print(os);
00210     return os;
00211   }
00212 
00213 
00214   // Provide specializations of GraphTraits to be able to use graph
00215   // iterators on the scheduling graph!
00216   //
00217   template <> struct GraphTraits<MSchedGraphNode*> {
00218     typedef MSchedGraphNode NodeType;
00219     typedef MSchedGraphNode::succ_iterator ChildIteratorType;
00220 
00221     static inline ChildIteratorType child_begin(NodeType *N) {
00222       return N->succ_begin();
00223     }
00224     static inline ChildIteratorType child_end(NodeType *N) {
00225       return N->succ_end();
00226     }
00227 
00228     static NodeType *getEntryNode(NodeType* N) { return N; }
00229   };
00230 
00231 
00232 
00233   //Graph class to represent dependence graph
00234   class MSchedGraph {
00235 
00236     std::vector<const MachineBasicBlock *> BBs; //Machine basic block
00237     const TargetMachine &Target; //Target Machine
00238 
00239     //Nodes
00240     std::map<const MachineInstr*, MSchedGraphNode*> GraphMap;
00241 
00242     //Add Nodes and Edges to this graph for our BB
00243     typedef std::pair<int, MSchedGraphNode*> OpIndexNodePair;
00244     void buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ignoreInstrs, DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm);
00245     void addValueEdges(std::vector<OpIndexNodePair> &NodesInMap,
00246                        MSchedGraphNode *node,
00247                        bool nodeIsUse, bool nodeIsDef, std::vector<const MachineInstr*> &phiInstrs, int diff=0);
00248     void addMachRegEdges(std::map<int,
00249                          std::vector<OpIndexNodePair> >& regNumtoNodeMap);
00250     void addMemEdges(const std::vector<MSchedGraphNode*>& memInst,
00251                      DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm);
00252     void addBranchEdges();
00253 
00254   public:
00255     MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ,
00256                 std::map<const MachineInstr*, unsigned> &ignoreInstrs,
00257                 DependenceAnalyzer &DA, std::map<MachineInstr*, Instruction*> &machineTollvm);
00258 
00259     //Copy constructor with maps to link old nodes to new nodes
00260     MSchedGraph(const MSchedGraph &G, std::map<MSchedGraphNode*, MSchedGraphNode*> &newNodes);
00261 
00262     MSchedGraph(std::vector<const MachineBasicBlock*> &bbs,
00263                 const TargetMachine &targ,
00264                 std::map<const MachineInstr*, unsigned> &ignoreInstrs,
00265                 DependenceAnalyzer &DA,
00266                 std::map<MachineInstr*, Instruction*> &machineTollvm);
00267 
00268     //Print graph
00269     void print(std::ostream &os) const;
00270 
00271     //Deconstructor!
00272     ~MSchedGraph();
00273 
00274     //Add or delete nodes from the Graph
00275     void addNode(const MachineInstr* MI, MSchedGraphNode *node);
00276     void deleteNode(MSchedGraphNode *node);
00277     int totalDelay();
00278 
00279     //iterators
00280     typedef std::map<const MachineInstr*, MSchedGraphNode*>::iterator iterator;
00281     typedef std::map<const MachineInstr*, MSchedGraphNode*>::const_iterator const_iterator;
00282     typedef std::map<const MachineInstr*, MSchedGraphNode*>::reverse_iterator reverse_iterator;
00283     iterator find(const MachineInstr* I) { return GraphMap.find(I); }
00284     iterator end() { return GraphMap.end(); }
00285     iterator begin() { return GraphMap.begin(); }
00286     unsigned size() { return GraphMap.size(); }
00287     reverse_iterator rbegin() { return GraphMap.rbegin(); }
00288     reverse_iterator rend() { return GraphMap.rend(); }
00289 
00290     //Get Target or original machine basic block
00291     const TargetMachine* getTarget() { return &Target; }
00292     std::vector<const MachineBasicBlock*> getBBs() { return BBs; }
00293   };
00294 
00295 
00296 
00297 
00298 
00299   // Provide specializations of GraphTraits to be able to use graph
00300   // iterators on the scheduling graph
00301   static MSchedGraphNode& getSecond(std::pair<const MachineInstr* const,
00302                                     MSchedGraphNode*> &Pair) {
00303     return *Pair.second;
00304   }
00305 
00306   template <> struct GraphTraits<MSchedGraph*> {
00307     typedef MSchedGraphNode NodeType;
00308     typedef MSchedGraphNode::succ_iterator ChildIteratorType;
00309 
00310     static inline ChildIteratorType child_begin(NodeType *N) {
00311       return N->succ_begin();
00312     }
00313     static inline ChildIteratorType child_end(NodeType *N) {
00314       return N->succ_end();
00315     }
00316 
00317     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00318            MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
00319 
00320     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
00321     static nodes_iterator nodes_begin(MSchedGraph *G) {
00322       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
00323     }
00324     static nodes_iterator nodes_end(MSchedGraph *G) {
00325       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
00326     }
00327 
00328   };
00329 
00330   template <> struct GraphTraits<const MSchedGraph*> {
00331     typedef const MSchedGraphNode NodeType;
00332     typedef MSchedGraphNode::succ_const_iterator ChildIteratorType;
00333 
00334     static inline ChildIteratorType child_begin(NodeType *N) {
00335       return N->succ_begin();
00336     }
00337     static inline ChildIteratorType child_end(NodeType *N) {
00338       return N->succ_end();
00339     }
00340     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00341                                                      MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
00342 
00343     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
00344     static nodes_iterator nodes_begin(MSchedGraph *G) {
00345       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
00346     }
00347     static nodes_iterator nodes_end(MSchedGraph *G) {
00348       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
00349     }
00350   };
00351 
00352   template <> struct GraphTraits<Inverse<MSchedGraph*> > {
00353     typedef MSchedGraphNode NodeType;
00354     typedef MSchedGraphNode::pred_iterator ChildIteratorType;
00355 
00356     static inline ChildIteratorType child_begin(NodeType *N) {
00357       return N->pred_begin();
00358     }
00359     static inline ChildIteratorType child_end(NodeType *N) {
00360       return N->pred_end();
00361     }
00362     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00363            MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
00364 
00365     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
00366     static nodes_iterator nodes_begin(MSchedGraph *G) {
00367       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
00368     }
00369     static nodes_iterator nodes_end(MSchedGraph *G) {
00370       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
00371     }
00372   };
00373 
00374   template <> struct GraphTraits<Inverse<const MSchedGraph*> > {
00375     typedef const MSchedGraphNode NodeType;
00376     typedef MSchedGraphNode::pred_const_iterator ChildIteratorType;
00377 
00378     static inline ChildIteratorType child_begin(NodeType *N) {
00379       return N->pred_begin();
00380     }
00381     static inline ChildIteratorType child_end(NodeType *N) {
00382       return N->pred_end();
00383     }
00384 
00385     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00386                                                      MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
00387 
00388     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
00389     static nodes_iterator nodes_begin(MSchedGraph *G) {
00390       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
00391     }
00392     static nodes_iterator nodes_end(MSchedGraph *G) {
00393       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
00394     }
00395   };
00396 }
00397 
00398 #endif