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