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. 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