LLVM API Documentation
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