LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_MSCHEDGRAPH_H
00015 #define LLVM_MSCHEDGRAPH_H
00016 
00017 #include "llvm/CodeGen/MachineInstr.h"
00018 #include "llvm/Target/TargetMachine.h"
00019 #include "llvm/ADT/GraphTraits.h"
00020 #include "llvm/ADT/STLExtras.h"
00021 #include "llvm/ADT/iterator"
00022 #include <vector>
00023 
00024 
00025 namespace llvm {
00026   class MSchedGraph;
00027   class MSchedGraphNode;
00028   template<class IteratorType, class NodeType>
00029   class MSchedGraphNodeIterator;
00030 
00031 
00032   struct MSchedGraphEdge {
00033     enum DataDepOrderType {
00034       TrueDep, AntiDep, OutputDep, NonDataDep
00035     };
00036     
00037     enum MSchedGraphEdgeType {
00038       MemoryDep, ValueDep, MachineRegister
00039     };
00040 
00041     MSchedGraphNode *getDest() const { return dest; }
00042     unsigned getIteDiff() { return iteDiff; }
00043     unsigned getDepOrderType() { return depOrderType; }
00044 
00045   private:
00046     friend class MSchedGraphNode;
00047     MSchedGraphEdge(MSchedGraphNode *destination, MSchedGraphEdgeType type, 
00048         unsigned deptype, unsigned diff) 
00049       : dest(destination), depType(type), depOrderType(deptype), iteDiff(diff) {}
00050     
00051     MSchedGraphNode *dest;
00052     MSchedGraphEdgeType depType;
00053     unsigned depOrderType;
00054     unsigned iteDiff;
00055   };
00056 
00057   class MSchedGraphNode {
00058    
00059     const MachineInstr* Inst; //Machine Instruction
00060     MSchedGraph* Parent; //Graph this node belongs to
00061     unsigned index; //Index in BB
00062     unsigned latency; //Latency of Instruction
00063     bool isBranchInstr; //Is this node the branch instr or not
00064     
00065 
00066     std::vector<MSchedGraphNode*> Predecessors; //Predecessor Nodes
00067     std::vector<MSchedGraphEdge> Successors;
00068 
00069   public:
00070     MSchedGraphNode(const MachineInstr *inst, MSchedGraph *graph, 
00071         unsigned index, unsigned late=0, bool isBranch=false);
00072 
00073     //Iterators
00074     typedef std::vector<MSchedGraphNode*>::iterator pred_iterator;
00075     pred_iterator pred_begin() { return Predecessors.begin(); }
00076     pred_iterator pred_end() { return Predecessors.end(); }
00077     
00078     typedef std::vector<MSchedGraphNode*>::const_iterator pred_const_iterator;
00079     pred_const_iterator pred_begin() const { return Predecessors.begin(); }
00080     pred_const_iterator pred_end() const { return Predecessors.end(); }
00081 
00082     // Successor iterators.
00083     typedef MSchedGraphNodeIterator<std::vector<MSchedGraphEdge>::const_iterator,
00084             const MSchedGraphNode> succ_const_iterator;
00085     succ_const_iterator succ_begin() const;
00086     succ_const_iterator succ_end() const;
00087 
00088     typedef MSchedGraphNodeIterator<std::vector<MSchedGraphEdge>::iterator,
00089             MSchedGraphNode> succ_iterator;
00090     succ_iterator succ_begin();
00091     succ_iterator succ_end();
00092 
00093     
00094 
00095     void addOutEdge(MSchedGraphNode *destination, 
00096         MSchedGraphEdge::MSchedGraphEdgeType type, 
00097         unsigned deptype, unsigned diff=0) {
00098       Successors.push_back(MSchedGraphEdge(destination, type, deptype,diff));
00099       destination->Predecessors.push_back(this);
00100     }
00101     const MachineInstr* getInst() { return Inst; }
00102     MSchedGraph* getParent() { return Parent; }
00103     bool hasPredecessors() { return (Predecessors.size() > 0); }
00104     bool hasSuccessors() { return (Successors.size() > 0); }
00105     unsigned getLatency() { return latency; }
00106     unsigned getLatency() const { return latency; }
00107     unsigned getIndex() { return index; }
00108     MSchedGraphEdge getInEdge(MSchedGraphNode *pred);
00109     unsigned getInEdgeNum(MSchedGraphNode *pred);
00110 
00111     bool isSuccessor(MSchedGraphNode *);
00112     bool isPredecessor(MSchedGraphNode *);
00113     bool isBranch() { return isBranchInstr; }
00114     //Debug support
00115     void print(std::ostream &os) const;
00116 
00117   };
00118 
00119   template<class IteratorType, class NodeType>
00120   class MSchedGraphNodeIterator : public forward_iterator<NodeType*, ptrdiff_t> {
00121     IteratorType I;   // std::vector<MSchedGraphEdge>::iterator or const_iterator
00122   public:
00123     MSchedGraphNodeIterator(IteratorType i) : I(i) {}
00124 
00125     bool operator==(const MSchedGraphNodeIterator RHS) const { return I == RHS.I; }
00126     bool operator!=(const MSchedGraphNodeIterator RHS) const { return I != RHS.I; }
00127 
00128     const MSchedGraphNodeIterator &operator=(const MSchedGraphNodeIterator &RHS) {
00129       I = RHS.I;
00130       return *this;
00131     }
00132 
00133     NodeType* operator*() const {
00134       return I->getDest();
00135     }
00136     NodeType* operator->() const { return operator*(); }
00137     
00138     MSchedGraphNodeIterator& operator++() {                // Preincrement
00139       ++I;
00140       return *this;
00141     }
00142     MSchedGraphNodeIterator operator++(int) { // Postincrement
00143       MSchedGraphNodeIterator tmp = *this; ++*this; return tmp; 
00144     }
00145 
00146     MSchedGraphEdge &getEdge() {
00147       return *I;
00148     }
00149     const MSchedGraphEdge &getEdge() const {
00150       return *I;
00151     }
00152   };
00153 
00154   inline MSchedGraphNode::succ_const_iterator MSchedGraphNode::succ_begin() const {
00155     return succ_const_iterator(Successors.begin());
00156   }
00157   inline MSchedGraphNode::succ_const_iterator MSchedGraphNode::succ_end() const {
00158     return succ_const_iterator(Successors.end());
00159   }
00160   inline MSchedGraphNode::succ_iterator MSchedGraphNode::succ_begin() {
00161     return succ_iterator(Successors.begin());
00162   }
00163   inline MSchedGraphNode::succ_iterator MSchedGraphNode::succ_end() {
00164     return succ_iterator(Successors.end());
00165   }
00166 
00167   // ostream << operator for MSGraphNode class
00168   inline std::ostream &operator<<(std::ostream &os, 
00169           const MSchedGraphNode &node) {
00170     node.print(os);
00171     return os;
00172   }
00173 
00174 
00175 
00176   class MSchedGraph {
00177     
00178     const MachineBasicBlock *BB; //Machine basic block
00179     const TargetMachine &Target; //Target Machine
00180         
00181     //Nodes
00182     std::map<const MachineInstr*, MSchedGraphNode*> GraphMap;
00183 
00184     //Add Nodes and Edges to this graph for our BB
00185     typedef std::pair<int, MSchedGraphNode*> OpIndexNodePair;
00186     void buildNodesAndEdges();
00187     void addValueEdges(std::vector<OpIndexNodePair> &NodesInMap, 
00188            MSchedGraphNode *node,
00189            bool nodeIsUse, bool nodeIsDef, int diff=0);
00190     void addMachRegEdges(std::map<int, 
00191        std::vector<OpIndexNodePair> >& regNumtoNodeMap);
00192     void addMemEdges(const std::vector<MSchedGraphNode*>& memInst);
00193 
00194   public:
00195     MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ);
00196     ~MSchedGraph();
00197     
00198     //Add Nodes to the Graph
00199     void addNode(const MachineInstr* MI, MSchedGraphNode *node);
00200     
00201     //iterators 
00202     typedef std::map<const MachineInstr*, MSchedGraphNode*>::iterator iterator;
00203     typedef std::map<const MachineInstr*, MSchedGraphNode*>::const_iterator const_iterator;
00204     typedef std::map<const MachineInstr*, MSchedGraphNode*>::reverse_iterator reverse_iterator;
00205     iterator find(const MachineInstr* I) { return GraphMap.find(I); }
00206     iterator end() { return GraphMap.end(); }
00207     iterator begin() { return GraphMap.begin(); }
00208     reverse_iterator rbegin() { return GraphMap.rbegin(); }
00209     reverse_iterator rend() { return GraphMap.rend(); }
00210     const TargetMachine* getTarget() { return &Target; }
00211   };
00212 
00213   
00214   static MSchedGraphNode& getSecond(std::pair<const MachineInstr* const,
00215            MSchedGraphNode*> &Pair) {
00216     return *Pair.second;
00217   }
00218 
00219 
00220 
00221   // Provide specializations of GraphTraits to be able to use graph
00222   // iterators on the scheduling graph!
00223   //
00224   template <> struct GraphTraits<MSchedGraph*> {
00225     typedef MSchedGraphNode NodeType;
00226     typedef MSchedGraphNode::succ_iterator ChildIteratorType;
00227     
00228     static inline ChildIteratorType child_begin(NodeType *N) { 
00229       return N->succ_begin(); 
00230     }
00231     static inline ChildIteratorType child_end(NodeType *N) { 
00232       return N->succ_end();
00233     }
00234 
00235     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00236            MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
00237 
00238     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
00239     static nodes_iterator nodes_begin(MSchedGraph *G) {
00240       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
00241     }
00242     static nodes_iterator nodes_end(MSchedGraph *G) {
00243       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
00244     }
00245     
00246 
00247   };
00248   
00249   template <> struct GraphTraits<const MSchedGraph*> {
00250     typedef const MSchedGraphNode NodeType;
00251     typedef MSchedGraphNode::succ_const_iterator ChildIteratorType;
00252     
00253     static inline ChildIteratorType child_begin(NodeType *N) { 
00254       return N->succ_begin(); 
00255     }
00256     static inline ChildIteratorType child_end(NodeType *N) { 
00257       return N->succ_end();
00258     }
00259     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00260                  MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
00261     
00262     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
00263     static nodes_iterator nodes_begin(MSchedGraph *G) {
00264       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
00265     }
00266     static nodes_iterator nodes_end(MSchedGraph *G) {
00267       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
00268     }
00269   };
00270   
00271   template <> struct GraphTraits<Inverse<MSchedGraph*> > {
00272     typedef MSchedGraphNode NodeType;
00273     typedef MSchedGraphNode::pred_iterator ChildIteratorType;
00274     
00275     static inline ChildIteratorType child_begin(NodeType *N) { 
00276       return N->pred_begin();
00277     }
00278     static inline ChildIteratorType child_end(NodeType *N) { 
00279       return N->pred_end();
00280     }
00281     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00282            MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
00283 
00284     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
00285     static nodes_iterator nodes_begin(MSchedGraph *G) {
00286       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
00287     }
00288     static nodes_iterator nodes_end(MSchedGraph *G) {
00289       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
00290     }
00291   };
00292   
00293   template <> struct GraphTraits<Inverse<const MSchedGraph*> > {
00294     typedef const MSchedGraphNode NodeType;
00295     typedef MSchedGraphNode::pred_const_iterator ChildIteratorType;
00296     
00297     static inline ChildIteratorType child_begin(NodeType *N) { 
00298       return N->pred_begin();
00299     }
00300     static inline ChildIteratorType child_end(NodeType *N) { 
00301       return N->pred_end();
00302     }
00303 
00304     typedef std::pointer_to_unary_function<std::pair<const MachineInstr* const,
00305                  MSchedGraphNode*>&, MSchedGraphNode&> DerefFun;
00306     
00307     typedef mapped_iterator<MSchedGraph::iterator, DerefFun> nodes_iterator;
00308     static nodes_iterator nodes_begin(MSchedGraph *G) {
00309       return map_iterator(((MSchedGraph*)G)->begin(), DerefFun(getSecond));
00310     }
00311     static nodes_iterator nodes_end(MSchedGraph *G) {
00312       return map_iterator(((MSchedGraph*)G)->end(), DerefFun(getSecond));
00313     }
00314   };
00315 
00316 
00317 }
00318 
00319 #endif