1 //===-- SchedGraph.h - Scheduling Graph --------------------------*- C++ -*--=//
4 // Scheduling graph based on SSA graph plus extra dependence edges
5 // capturing dependences due to machine resources (machine registers,
6 // CC registers, and any others).
9 // This graph tries to leverage the SSA graph as much as possible,
10 // but captures the extra dependences through a common interface.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CODEGEN_SCHEDGRAPH_H
15 #define LLVM_CODEGEN_SCHEDGRAPH_H
17 #include "llvm/CodeGen/MachineInstr.h"
18 #include "Support/GraphTraits.h"
19 #include "Support/hash_map"
20 #include "llvm/Transforms/Scalar.h"
21 #include "llvm/CodeGen/SchedGraphCommon.h"
24 class ValueToDefVecMap;
27 class SchedGraphNode : public SchedGraphNodeCommon {
29 int origIndexInBB; // original position of machine instr in BB
30 MachineBasicBlock *MBB;
31 const MachineInstr *MI;
34 SchedGraphNode (unsigned nodeId, MachineBasicBlock *mbb,
35 int indexInBB, const TargetMachine& Target);
38 friend class SchedGraph; // give access for ctor and dtor
39 friend class SchedGraphEdge; // give access for adding edges
43 const MachineInstr* getMachineInstr () const { return MI; }
44 const MachineOpCode getOpCode () const { return MI->getOpCode(); }
45 bool isDummyNode () const { return (MI == NULL); }
46 MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
48 int getOrigIndexInBB() const { return origIndexInBB; }
51 class SchedGraph : public SchedGraphCommon {
52 MachineBasicBlock &MBB;
53 hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
56 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
57 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
59 MachineBasicBlock& getBasicBlock() const{return MBB;}
60 const unsigned int getNumNodes() const { return GraphMap.size()+2; }
61 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
62 const_iterator onePair = find(MI);
63 return (onePair != end())? onePair->second : NULL;
70 SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
73 // Unordered iterators.
74 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
76 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
77 return GraphMap.begin();
79 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
80 return GraphMap.end();
83 unsigned size() { return GraphMap.size(); }
84 iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
86 SchedGraphNode *&operator[](const MachineInstr *MI) {
91 friend class SchedGraphSet; // give access to ctor
95 inline void noteGraphNodeForInstr (const MachineInstr* minstr,
98 assert((*this)[minstr] == NULL);
99 (*this)[minstr] = node;
105 void buildGraph (const TargetMachine& target);
107 void buildNodesForBB (const TargetMachine& target,
108 MachineBasicBlock &MBB,
109 std::vector<SchedGraphNode*>& memNV,
110 std::vector<SchedGraphNode*>& callNV,
111 RegToRefVecMap& regToRefVecMap,
112 ValueToDefVecMap& valueToDefVecMap);
115 void findDefUseInfoAtInstr (const TargetMachine& target,
116 SchedGraphNode* node,
117 std::vector<SchedGraphNode*>& memNV,
118 std::vector<SchedGraphNode*>& callNV,
119 RegToRefVecMap& regToRefVecMap,
120 ValueToDefVecMap& valueToDefVecMap);
123 void addEdgesForInstruction(const MachineInstr& minstr,
124 const ValueToDefVecMap& valueToDefVecMap,
125 const TargetMachine& target);
127 void addCDEdges (const TerminatorInst* term,
128 const TargetMachine& target);
130 void addMemEdges (const std::vector<SchedGraphNode*>& memNod,
131 const TargetMachine& target);
133 void addCallCCEdges (const std::vector<SchedGraphNode*>& memNod,
134 MachineBasicBlock& bbMvec,
135 const TargetMachine& target);
136 void addCallDepEdges (const std::vector<SchedGraphNode*>& callNV,
137 const TargetMachine& target);
139 void addMachineRegEdges (RegToRefVecMap& regToRefVecMap,
140 const TargetMachine& target);
142 void addEdgesForValue (SchedGraphNode* refNode,
143 const RefVec& defVec,
144 const Value* defValue,
146 bool refNodeIsDefAndUse,
147 const TargetMachine& target);
148 void addDummyEdges();
154 class SchedGraphSet {
155 const Function* function;
156 std::vector<SchedGraph*> Graphs;
159 void buildGraphsForMethod (const Function *F, const TargetMachine& target);
161 inline void addGraph(SchedGraph* graph) {
162 assert(graph != NULL);
163 Graphs.push_back(graph);
167 SchedGraphSet(const Function * function, const TargetMachine& target);
171 typedef std::vector<SchedGraph*>::const_iterator iterator;
172 typedef std::vector<SchedGraph*>::const_iterator const_iterator;
174 std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
175 std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
183 //********************** Sched Graph Iterators *****************************/
185 // Ok to make it a template because it shd get instantiated at most twice:
186 // for <SchedGraphNode, SchedGraphNode::iterator> and
187 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
189 template <class _NodeType, class _EdgeType, class _EdgeIter>
190 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
194 typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
196 inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
198 inline bool operator==(const _Self& x) const { return oi == x.oi; }
199 inline bool operator!=(const _Self& x) const { return !operator==(x); }
201 // operator*() differs for pred or succ iterator
202 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
203 inline _NodeType* operator->() const { return operator*(); }
205 inline _EdgeType* getEdge() const { return *(oi); }
207 inline _Self &operator++() { ++oi; return *this; } // Preincrement
208 inline _Self operator++(int) { // Postincrement
209 _Self tmp(*this); ++*this; return tmp;
212 inline _Self &operator--() { --oi; return *this; } // Predecrement
213 inline _Self operator--(int) { // Postdecrement
214 _Self tmp = *this; --*this; return tmp;
218 template <class _NodeType, class _EdgeType, class _EdgeIter>
219 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
223 typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
225 inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
227 inline bool operator==(const _Self& x) const { return oi == x.oi; }
228 inline bool operator!=(const _Self& x) const { return !operator==(x); }
230 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
231 inline _NodeType* operator->() const { return operator*(); }
233 inline _EdgeType* getEdge() const { return *(oi); }
235 inline _Self &operator++() { ++oi; return *this; } // Preincrement
236 inline _Self operator++(int) { // Postincrement
237 _Self tmp(*this); ++*this; return tmp;
240 inline _Self &operator--() { --oi; return *this; } // Predecrement
241 inline _Self operator--(int) { // Postdecrement
242 _Self tmp = *this; --*this; return tmp;
248 // sg_pred_const_iterator
250 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
252 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
253 sg_pred_const_iterator;
255 inline sg_pred_iterator pred_begin( SchedGraphNode *N) {
256 return sg_pred_iterator(N->beginInEdges());
258 inline sg_pred_iterator pred_end( SchedGraphNode *N) {
259 return sg_pred_iterator(N->endInEdges());
261 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
262 return sg_pred_const_iterator(N->beginInEdges());
264 inline sg_pred_const_iterator pred_end( const SchedGraphNode *N) {
265 return sg_pred_const_iterator(N->endInEdges());
271 // sg_succ_const_iterator
273 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
275 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
276 sg_succ_const_iterator;
278 inline sg_succ_iterator succ_begin( SchedGraphNode *N) {
279 return sg_succ_iterator(N->beginOutEdges());
281 inline sg_succ_iterator succ_end( SchedGraphNode *N) {
282 return sg_succ_iterator(N->endOutEdges());
284 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
285 return sg_succ_const_iterator(N->beginOutEdges());
287 inline sg_succ_const_iterator succ_end( const SchedGraphNode *N) {
288 return sg_succ_const_iterator(N->endOutEdges());
291 // Provide specializations of GraphTraits to be able to use graph iterators on
292 // the scheduling graph!
294 template <> struct GraphTraits<SchedGraph*> {
295 typedef SchedGraphNode NodeType;
296 typedef sg_succ_iterator ChildIteratorType;
298 static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
299 static inline ChildIteratorType child_begin(NodeType *N) {
300 return succ_begin(N);
302 static inline ChildIteratorType child_end(NodeType *N) {
307 template <> struct GraphTraits<const SchedGraph*> {
308 typedef const SchedGraphNode NodeType;
309 typedef sg_succ_const_iterator ChildIteratorType;
311 static inline NodeType *getEntryNode(const SchedGraph *SG) {
312 return (NodeType*)SG->getRoot();
314 static inline ChildIteratorType child_begin(NodeType *N) {
315 return succ_begin(N);
317 static inline ChildIteratorType child_end(NodeType *N) {
323 std::ostream &operator<<(std::ostream& os, const SchedGraphEdge& edge);
324 std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node);