LLVM API Documentation
00001 //===-- SchedGraph.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 // This is a scheduling graph based on SSA graph plus extra dependence edges 00011 // capturing dependences due to machine resources (machine registers, CC 00012 // registers, and any others). 00013 // 00014 // This graph tries to leverage the SSA graph as much as possible, but captures 00015 // the extra dependences through a common interface. 00016 // 00017 //===----------------------------------------------------------------------===// 00018 00019 #ifndef LLVM_CODEGEN_SCHEDGRAPH_H 00020 #define LLVM_CODEGEN_SCHEDGRAPH_H 00021 00022 #include "llvm/CodeGen/SchedGraphCommon.h" 00023 #include "llvm/CodeGen/MachineInstr.h" 00024 #include "llvm/Transforms/Scalar.h" 00025 #include "llvm/ADT/hash_map" 00026 #include "llvm/ADT/GraphTraits.h" 00027 00028 namespace llvm { 00029 00030 class RegToRefVecMap; 00031 class ValueToDefVecMap; 00032 class RefVec; 00033 00034 class SchedGraphNode : public SchedGraphNodeCommon { 00035 00036 MachineBasicBlock *MBB; 00037 const MachineInstr *MI; 00038 00039 00040 SchedGraphNode(unsigned nodeId, MachineBasicBlock *mbb, int indexInBB, 00041 const TargetMachine& Target); 00042 ~SchedGraphNode(); 00043 00044 friend class SchedGraph; // give access for ctor and dtor 00045 friend class SchedGraphEdge; // give access for adding edges 00046 00047 public: 00048 00049 // Accessor methods 00050 const MachineInstr* getMachineInstr() const { return MI; } 00051 const MachineOpCode getOpcode() const { return MI->getOpcode(); } 00052 bool isDummyNode() const { return (MI == NULL); } 00053 MachineBasicBlock &getMachineBasicBlock() const { return *MBB; } 00054 00055 void print(std::ostream &os) const; 00056 }; 00057 00058 class SchedGraph : public SchedGraphCommon { 00059 MachineBasicBlock &MBB; 00060 hash_map<const MachineInstr*, SchedGraphNode*> GraphMap; 00061 00062 public: 00063 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator; 00064 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator; 00065 00066 MachineBasicBlock& getBasicBlock() const{return MBB;} 00067 const unsigned int getNumNodes() const { return GraphMap.size()+2; } 00068 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const { 00069 const_iterator onePair = find(MI); 00070 return (onePair != end())? onePair->second : NULL; 00071 } 00072 00073 // Debugging support 00074 void dump() const; 00075 00076 protected: 00077 SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM); 00078 ~SchedGraph(); 00079 00080 // Unordered iterators. 00081 // Return values is pair<const MachineIntr*,SchedGraphNode*>. 00082 // 00083 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const { 00084 return GraphMap.begin(); 00085 } 00086 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const { 00087 return GraphMap.end(); 00088 } 00089 00090 unsigned size() { return GraphMap.size(); } 00091 iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); } 00092 00093 SchedGraphNode *&operator[](const MachineInstr *MI) { 00094 return GraphMap[MI]; 00095 } 00096 00097 private: 00098 friend class SchedGraphSet; // give access to ctor 00099 00100 inline void noteGraphNodeForInstr (const MachineInstr* minstr, 00101 SchedGraphNode* node) { 00102 assert((*this)[minstr] == NULL); 00103 (*this)[minstr] = node; 00104 } 00105 00106 // 00107 // Graph builder 00108 // 00109 void buildGraph(const TargetMachine& target); 00110 00111 void buildNodesForBB(const TargetMachine& target,MachineBasicBlock &MBB, 00112 std::vector<SchedGraphNode*>& memNV, 00113 std::vector<SchedGraphNode*>& callNV, 00114 RegToRefVecMap& regToRefVecMap, 00115 ValueToDefVecMap& valueToDefVecMap); 00116 00117 00118 void findDefUseInfoAtInstr(const TargetMachine& target, SchedGraphNode* node, 00119 std::vector<SchedGraphNode*>& memNV, 00120 std::vector<SchedGraphNode*>& callNV, 00121 RegToRefVecMap& regToRefVecMap, 00122 ValueToDefVecMap& valueToDefVecMap); 00123 00124 void addEdgesForInstruction(const MachineInstr& minstr, 00125 const ValueToDefVecMap& valueToDefVecMap, 00126 const TargetMachine& target); 00127 00128 void addCDEdges(const TerminatorInst* term, const TargetMachine& target); 00129 00130 void addMemEdges(const std::vector<SchedGraphNode*>& memNod, 00131 const TargetMachine& target); 00132 00133 void addCallCCEdges(const std::vector<SchedGraphNode*>& memNod, 00134 MachineBasicBlock& bbMvec, 00135 const TargetMachine& target); 00136 00137 void addCallDepEdges(const std::vector<SchedGraphNode*>& callNV, 00138 const TargetMachine& target); 00139 00140 void addMachineRegEdges(RegToRefVecMap& regToRefVecMap, 00141 const TargetMachine& target); 00142 00143 void addEdgesForValue(SchedGraphNode* refNode, const RefVec& defVec, 00144 const Value* defValue, bool refNodeIsDef, 00145 bool refNodeIsDefAndUse, 00146 const TargetMachine& target); 00147 00148 void addDummyEdges(); 00149 00150 }; 00151 00152 00153 00154 class SchedGraphSet { 00155 const Function* function; 00156 std::vector<SchedGraph*> Graphs; 00157 00158 // Graph builder 00159 void buildGraphsForMethod(const Function *F, const TargetMachine& target); 00160 00161 inline void addGraph(SchedGraph* graph) { 00162 assert(graph != NULL); 00163 Graphs.push_back(graph); 00164 } 00165 00166 public: 00167 SchedGraphSet(const Function *function, const TargetMachine& target); 00168 ~SchedGraphSet(); 00169 00170 //iterators 00171 typedef std::vector<SchedGraph*>::const_iterator iterator; 00172 typedef std::vector<SchedGraph*>::const_iterator const_iterator; 00173 00174 std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); } 00175 std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); } 00176 00177 // Debugging support 00178 void dump() const; 00179 }; 00180 00181 00182 00183 00184 // 00185 // sg_pred_iterator 00186 // sg_pred_const_iterator 00187 // 00188 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator> 00189 sg_pred_iterator; 00190 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator> 00191 sg_pred_const_iterator; 00192 00193 inline sg_pred_iterator pred_begin(SchedGraphNode *N) { 00194 return sg_pred_iterator(N->beginInEdges()); 00195 } 00196 inline sg_pred_iterator pred_end(SchedGraphNode *N) { 00197 return sg_pred_iterator(N->endInEdges()); 00198 } 00199 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) { 00200 return sg_pred_const_iterator(N->beginInEdges()); 00201 } 00202 inline sg_pred_const_iterator pred_end(const SchedGraphNode *N) { 00203 return sg_pred_const_iterator(N->endInEdges()); 00204 } 00205 00206 00207 // 00208 // sg_succ_iterator 00209 // sg_succ_const_iterator 00210 // 00211 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator> 00212 sg_succ_iterator; 00213 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator> 00214 sg_succ_const_iterator; 00215 00216 inline sg_succ_iterator succ_begin(SchedGraphNode *N) { 00217 return sg_succ_iterator(N->beginOutEdges()); 00218 } 00219 inline sg_succ_iterator succ_end(SchedGraphNode *N) { 00220 return sg_succ_iterator(N->endOutEdges()); 00221 } 00222 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) { 00223 return sg_succ_const_iterator(N->beginOutEdges()); 00224 } 00225 inline sg_succ_const_iterator succ_end(const SchedGraphNode *N) { 00226 return sg_succ_const_iterator(N->endOutEdges()); 00227 } 00228 00229 // Provide specializations of GraphTraits to be able to use graph iterators on 00230 // the scheduling graph! 00231 // 00232 template <> struct GraphTraits<SchedGraph*> { 00233 typedef SchedGraphNode NodeType; 00234 typedef sg_succ_iterator ChildIteratorType; 00235 00236 static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); } 00237 static inline ChildIteratorType child_begin(NodeType *N) { 00238 return succ_begin(N); 00239 } 00240 static inline ChildIteratorType child_end(NodeType *N) { 00241 return succ_end(N); 00242 } 00243 }; 00244 00245 template <> struct GraphTraits<const SchedGraph*> { 00246 typedef const SchedGraphNode NodeType; 00247 typedef sg_succ_const_iterator ChildIteratorType; 00248 00249 static inline NodeType *getEntryNode(const SchedGraph *SG) { 00250 return (NodeType*)SG->getRoot(); 00251 } 00252 static inline ChildIteratorType child_begin(NodeType *N) { 00253 return succ_begin(N); 00254 } 00255 static inline ChildIteratorType child_end(NodeType *N) { 00256 return succ_end(N); 00257 } 00258 }; 00259 00260 } // End llvm namespace 00261 00262 #endif