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/SchedGraphCommon.h"
18 #include "llvm/CodeGen/MachineInstr.h"
19 #include "llvm/Transforms/Scalar.h"
20 #include "Support/hash_map"
21 #include "Support/GraphTraits.h"
25 class ValueToDefVecMap;
28 class SchedGraphNode : public SchedGraphNodeCommon {
30 int origIndexInBB; // original position of machine instr in BB
31 MachineBasicBlock *MBB;
32 const MachineInstr *MI;
35 SchedGraphNode(unsigned nodeId, MachineBasicBlock *mbb, int indexInBB,
36 const TargetMachine& Target);
39 friend class SchedGraph; // give access for ctor and dtor
40 friend class SchedGraphEdge; // give access for adding edges
45 const MachineInstr* getMachineInstr() const { return MI; }
46 const MachineOpCode getOpCode() const { return MI->getOpCode(); }
47 bool isDummyNode() const { return (MI == NULL); }
48 MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
50 int getOrigIndexInBB() const { return origIndexInBB; }
51 void print(std::ostream &os) const;
54 class SchedGraph : public SchedGraphCommon {
55 MachineBasicBlock &MBB;
56 hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
59 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
60 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
62 MachineBasicBlock& getBasicBlock() const{return MBB;}
63 const unsigned int getNumNodes() const { return GraphMap.size()+2; }
64 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
65 const_iterator onePair = find(MI);
66 return (onePair != end())? onePair->second : NULL;
73 SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
76 // Unordered iterators.
77 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
79 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
80 return GraphMap.begin();
82 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
83 return GraphMap.end();
86 unsigned size() { return GraphMap.size(); }
87 iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
89 SchedGraphNode *&operator[](const MachineInstr *MI) {
94 friend class SchedGraphSet; // give access to ctor
96 inline void noteGraphNodeForInstr (const MachineInstr* minstr,
97 SchedGraphNode* node) {
98 assert((*this)[minstr] == NULL);
99 (*this)[minstr] = node;
105 void buildGraph(const TargetMachine& target);
107 void buildNodesForBB(const TargetMachine& target,MachineBasicBlock &MBB,
108 std::vector<SchedGraphNode*>& memNV,
109 std::vector<SchedGraphNode*>& callNV,
110 RegToRefVecMap& regToRefVecMap,
111 ValueToDefVecMap& valueToDefVecMap);
114 void findDefUseInfoAtInstr(const TargetMachine& target, SchedGraphNode* node,
115 std::vector<SchedGraphNode*>& memNV,
116 std::vector<SchedGraphNode*>& callNV,
117 RegToRefVecMap& regToRefVecMap,
118 ValueToDefVecMap& valueToDefVecMap);
120 void addEdgesForInstruction(const MachineInstr& minstr,
121 const ValueToDefVecMap& valueToDefVecMap,
122 const TargetMachine& target);
124 void addCDEdges(const TerminatorInst* term, const TargetMachine& target);
126 void addMemEdges(const std::vector<SchedGraphNode*>& memNod,
127 const TargetMachine& target);
129 void addCallCCEdges(const std::vector<SchedGraphNode*>& memNod,
130 MachineBasicBlock& bbMvec,
131 const TargetMachine& target);
133 void addCallDepEdges(const std::vector<SchedGraphNode*>& callNV,
134 const TargetMachine& target);
136 void addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
137 const TargetMachine& target);
139 void addEdgesForValue(SchedGraphNode* refNode, const RefVec& defVec,
140 const Value* defValue, bool refNodeIsDef,
141 bool refNodeIsDefAndUse,
142 const TargetMachine& target);
144 void addDummyEdges();
150 class SchedGraphSet {
151 const Function* function;
152 std::vector<SchedGraph*> Graphs;
155 void buildGraphsForMethod(const Function *F, const TargetMachine& target);
157 inline void addGraph(SchedGraph* graph) {
158 assert(graph != NULL);
159 Graphs.push_back(graph);
163 SchedGraphSet(const Function *function, const TargetMachine& target);
167 typedef std::vector<SchedGraph*>::const_iterator iterator;
168 typedef std::vector<SchedGraph*>::const_iterator const_iterator;
170 std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
171 std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
179 //********************** Sched Graph Iterators *****************************/
181 // Ok to make it a template because it shd get instantiated at most twice:
182 // for <SchedGraphNode, SchedGraphNode::iterator> and
183 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
185 template <class _NodeType, class _EdgeType, class _EdgeIter>
186 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
190 typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
192 inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
194 inline bool operator==(const _Self& x) const { return oi == x.oi; }
195 inline bool operator!=(const _Self& x) const { return !operator==(x); }
197 // operator*() differs for pred or succ iterator
198 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
199 inline _NodeType* operator->() const { return operator*(); }
201 inline _EdgeType* getEdge() const { return *(oi); }
203 inline _Self &operator++() { ++oi; return *this; } // Preincrement
204 inline _Self operator++(int) { // Postincrement
205 _Self tmp(*this); ++*this; return tmp;
208 inline _Self &operator--() { --oi; return *this; } // Predecrement
209 inline _Self operator--(int) { // Postdecrement
210 _Self tmp = *this; --*this; return tmp;
214 template <class _NodeType, class _EdgeType, class _EdgeIter>
215 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
219 typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
221 inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
223 inline bool operator==(const _Self& x) const { return oi == x.oi; }
224 inline bool operator!=(const _Self& x) const { return !operator==(x); }
226 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
227 inline _NodeType* operator->() const { return operator*(); }
229 inline _EdgeType* getEdge() const { return *(oi); }
231 inline _Self &operator++() { ++oi; return *this; } // Preincrement
232 inline _Self operator++(int) { // Postincrement
233 _Self tmp(*this); ++*this; return tmp;
236 inline _Self &operator--() { --oi; return *this; } // Predecrement
237 inline _Self operator--(int) { // Postdecrement
238 _Self tmp = *this; --*this; return tmp;
244 // sg_pred_const_iterator
246 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
248 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
249 sg_pred_const_iterator;
251 inline sg_pred_iterator pred_begin(SchedGraphNode *N) {
252 return sg_pred_iterator(N->beginInEdges());
254 inline sg_pred_iterator pred_end(SchedGraphNode *N) {
255 return sg_pred_iterator(N->endInEdges());
257 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
258 return sg_pred_const_iterator(N->beginInEdges());
260 inline sg_pred_const_iterator pred_end(const SchedGraphNode *N) {
261 return sg_pred_const_iterator(N->endInEdges());
267 // sg_succ_const_iterator
269 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
271 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
272 sg_succ_const_iterator;
274 inline sg_succ_iterator succ_begin(SchedGraphNode *N) {
275 return sg_succ_iterator(N->beginOutEdges());
277 inline sg_succ_iterator succ_end(SchedGraphNode *N) {
278 return sg_succ_iterator(N->endOutEdges());
280 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
281 return sg_succ_const_iterator(N->beginOutEdges());
283 inline sg_succ_const_iterator succ_end(const SchedGraphNode *N) {
284 return sg_succ_const_iterator(N->endOutEdges());
287 // Provide specializations of GraphTraits to be able to use graph iterators on
288 // the scheduling graph!
290 template <> struct GraphTraits<SchedGraph*> {
291 typedef SchedGraphNode NodeType;
292 typedef sg_succ_iterator ChildIteratorType;
294 static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
295 static inline ChildIteratorType child_begin(NodeType *N) {
296 return succ_begin(N);
298 static inline ChildIteratorType child_end(NodeType *N) {
303 template <> struct GraphTraits<const SchedGraph*> {
304 typedef const SchedGraphNode NodeType;
305 typedef sg_succ_const_iterator ChildIteratorType;
307 static inline NodeType *getEntryNode(const SchedGraph *SG) {
308 return (NodeType*)SG->getRoot();
310 static inline ChildIteratorType child_begin(NodeType *N) {
311 return succ_begin(N);
313 static inline ChildIteratorType child_end(NodeType *N) {