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"
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, int indexInBB,
35 const TargetMachine& Target);
38 friend class SchedGraph; // give access for ctor and dtor
39 friend class SchedGraphEdge; // give access for adding edges
44 const MachineInstr* getMachineInstr() const { return MI; }
45 const MachineOpCode getOpCode() const { return MI->getOpCode(); }
46 bool isDummyNode() const { return (MI == NULL); }
47 MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
49 int getOrigIndexInBB() const { return origIndexInBB; }
50 void print(std::ostream &os) const;
53 class SchedGraph : public SchedGraphCommon {
54 MachineBasicBlock &MBB;
55 hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
58 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
59 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
61 MachineBasicBlock& getBasicBlock() const{return MBB;}
62 const unsigned int getNumNodes() const { return GraphMap.size()+2; }
63 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
64 const_iterator onePair = find(MI);
65 return (onePair != end())? onePair->second : NULL;
72 SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
75 // Unordered iterators.
76 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
78 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
79 return GraphMap.begin();
81 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
82 return GraphMap.end();
85 unsigned size() { return GraphMap.size(); }
86 iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
88 SchedGraphNode *&operator[](const MachineInstr *MI) {
93 friend class SchedGraphSet; // give access to ctor
95 inline void noteGraphNodeForInstr (const MachineInstr* minstr,
96 SchedGraphNode* node) {
97 assert((*this)[minstr] == NULL);
98 (*this)[minstr] = node;
104 void buildGraph(const TargetMachine& target);
106 void buildNodesForBB(const TargetMachine& target,MachineBasicBlock &MBB,
107 std::vector<SchedGraphNode*>& memNV,
108 std::vector<SchedGraphNode*>& callNV,
109 RegToRefVecMap& regToRefVecMap,
110 ValueToDefVecMap& valueToDefVecMap);
113 void findDefUseInfoAtInstr(const TargetMachine& target, SchedGraphNode* node,
114 std::vector<SchedGraphNode*>& memNV,
115 std::vector<SchedGraphNode*>& callNV,
116 RegToRefVecMap& regToRefVecMap,
117 ValueToDefVecMap& valueToDefVecMap);
119 void addEdgesForInstruction(const MachineInstr& minstr,
120 const ValueToDefVecMap& valueToDefVecMap,
121 const TargetMachine& target);
123 void addCDEdges(const TerminatorInst* term, const TargetMachine& target);
125 void addMemEdges(const std::vector<SchedGraphNode*>& memNod,
126 const TargetMachine& target);
128 void addCallCCEdges(const std::vector<SchedGraphNode*>& memNod,
129 MachineBasicBlock& bbMvec,
130 const TargetMachine& target);
132 void addCallDepEdges(const std::vector<SchedGraphNode*>& callNV,
133 const TargetMachine& target);
135 void addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
136 const TargetMachine& target);
138 void addEdgesForValue(SchedGraphNode* refNode, const RefVec& defVec,
139 const Value* defValue, bool refNodeIsDef,
140 bool refNodeIsDefAndUse,
141 const TargetMachine& target);
143 void addDummyEdges();
149 class SchedGraphSet {
150 const Function* function;
151 std::vector<SchedGraph*> Graphs;
154 void buildGraphsForMethod(const Function *F, const TargetMachine& target);
156 inline void addGraph(SchedGraph* graph) {
157 assert(graph != NULL);
158 Graphs.push_back(graph);
162 SchedGraphSet(const Function *function, const TargetMachine& target);
166 typedef std::vector<SchedGraph*>::const_iterator iterator;
167 typedef std::vector<SchedGraph*>::const_iterator const_iterator;
169 std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
170 std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
178 //********************** Sched Graph Iterators *****************************/
180 // Ok to make it a template because it shd get instantiated at most twice:
181 // for <SchedGraphNode, SchedGraphNode::iterator> and
182 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
184 template <class _NodeType, class _EdgeType, class _EdgeIter>
185 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
189 typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
191 inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
193 inline bool operator==(const _Self& x) const { return oi == x.oi; }
194 inline bool operator!=(const _Self& x) const { return !operator==(x); }
196 // operator*() differs for pred or succ iterator
197 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
198 inline _NodeType* operator->() const { return operator*(); }
200 inline _EdgeType* getEdge() const { return *(oi); }
202 inline _Self &operator++() { ++oi; return *this; } // Preincrement
203 inline _Self operator++(int) { // Postincrement
204 _Self tmp(*this); ++*this; return tmp;
207 inline _Self &operator--() { --oi; return *this; } // Predecrement
208 inline _Self operator--(int) { // Postdecrement
209 _Self tmp = *this; --*this; return tmp;
213 template <class _NodeType, class _EdgeType, class _EdgeIter>
214 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
218 typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
220 inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
222 inline bool operator==(const _Self& x) const { return oi == x.oi; }
223 inline bool operator!=(const _Self& x) const { return !operator==(x); }
225 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
226 inline _NodeType* operator->() const { return operator*(); }
228 inline _EdgeType* getEdge() const { return *(oi); }
230 inline _Self &operator++() { ++oi; return *this; } // Preincrement
231 inline _Self operator++(int) { // Postincrement
232 _Self tmp(*this); ++*this; return tmp;
235 inline _Self &operator--() { --oi; return *this; } // Predecrement
236 inline _Self operator--(int) { // Postdecrement
237 _Self tmp = *this; --*this; return tmp;
243 // sg_pred_const_iterator
245 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
247 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
248 sg_pred_const_iterator;
250 inline sg_pred_iterator pred_begin(SchedGraphNode *N) {
251 return sg_pred_iterator(N->beginInEdges());
253 inline sg_pred_iterator pred_end(SchedGraphNode *N) {
254 return sg_pred_iterator(N->endInEdges());
256 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
257 return sg_pred_const_iterator(N->beginInEdges());
259 inline sg_pred_const_iterator pred_end(const SchedGraphNode *N) {
260 return sg_pred_const_iterator(N->endInEdges());
266 // sg_succ_const_iterator
268 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
270 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
271 sg_succ_const_iterator;
273 inline sg_succ_iterator succ_begin(SchedGraphNode *N) {
274 return sg_succ_iterator(N->beginOutEdges());
276 inline sg_succ_iterator succ_end(SchedGraphNode *N) {
277 return sg_succ_iterator(N->endOutEdges());
279 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
280 return sg_succ_const_iterator(N->beginOutEdges());
282 inline sg_succ_const_iterator succ_end(const SchedGraphNode *N) {
283 return sg_succ_const_iterator(N->endOutEdges());
286 // Provide specializations of GraphTraits to be able to use graph iterators on
287 // the scheduling graph!
289 template <> struct GraphTraits<SchedGraph*> {
290 typedef SchedGraphNode NodeType;
291 typedef sg_succ_iterator ChildIteratorType;
293 static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
294 static inline ChildIteratorType child_begin(NodeType *N) {
295 return succ_begin(N);
297 static inline ChildIteratorType child_end(NodeType *N) {
302 template <> struct GraphTraits<const SchedGraph*> {
303 typedef const SchedGraphNode NodeType;
304 typedef sg_succ_const_iterator ChildIteratorType;
306 static inline NodeType *getEntryNode(const SchedGraph *SG) {
307 return (NodeType*)SG->getRoot();
309 static inline ChildIteratorType child_begin(NodeType *N) {
310 return succ_begin(N);
312 static inline ChildIteratorType child_end(NodeType *N) {