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 MachineBasicBlock *MBB;
30 const MachineInstr *MI;
33 SchedGraphNode(unsigned nodeId, MachineBasicBlock *mbb, int indexInBB,
34 const TargetMachine& Target);
37 friend class SchedGraph; // give access for ctor and dtor
38 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 void print(std::ostream &os) const;
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
93 inline void noteGraphNodeForInstr (const MachineInstr* minstr,
94 SchedGraphNode* node) {
95 assert((*this)[minstr] == NULL);
96 (*this)[minstr] = node;
102 void buildGraph(const TargetMachine& target);
104 void buildNodesForBB(const TargetMachine& target,MachineBasicBlock &MBB,
105 std::vector<SchedGraphNode*>& memNV,
106 std::vector<SchedGraphNode*>& callNV,
107 RegToRefVecMap& regToRefVecMap,
108 ValueToDefVecMap& valueToDefVecMap);
111 void findDefUseInfoAtInstr(const TargetMachine& target, SchedGraphNode* node,
112 std::vector<SchedGraphNode*>& memNV,
113 std::vector<SchedGraphNode*>& callNV,
114 RegToRefVecMap& regToRefVecMap,
115 ValueToDefVecMap& valueToDefVecMap);
117 void addEdgesForInstruction(const MachineInstr& minstr,
118 const ValueToDefVecMap& valueToDefVecMap,
119 const TargetMachine& target);
121 void addCDEdges(const TerminatorInst* term, const TargetMachine& target);
123 void addMemEdges(const std::vector<SchedGraphNode*>& memNod,
124 const TargetMachine& target);
126 void addCallCCEdges(const std::vector<SchedGraphNode*>& memNod,
127 MachineBasicBlock& bbMvec,
128 const TargetMachine& target);
130 void addCallDepEdges(const std::vector<SchedGraphNode*>& callNV,
131 const TargetMachine& target);
133 void addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
134 const TargetMachine& target);
136 void addEdgesForValue(SchedGraphNode* refNode, const RefVec& defVec,
137 const Value* defValue, bool refNodeIsDef,
138 bool refNodeIsDefAndUse,
139 const TargetMachine& target);
141 void addDummyEdges();
147 class SchedGraphSet {
148 const Function* function;
149 std::vector<SchedGraph*> Graphs;
152 void buildGraphsForMethod(const Function *F, const TargetMachine& target);
154 inline void addGraph(SchedGraph* graph) {
155 assert(graph != NULL);
156 Graphs.push_back(graph);
160 SchedGraphSet(const Function *function, const TargetMachine& target);
164 typedef std::vector<SchedGraph*>::const_iterator iterator;
165 typedef std::vector<SchedGraph*>::const_iterator const_iterator;
167 std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
168 std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
176 //********************** Sched Graph Iterators *****************************/
178 // Ok to make it a template because it shd get instantiated at most twice:
179 // for <SchedGraphNode, SchedGraphNode::iterator> and
180 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
182 template <class _NodeType, class _EdgeType, class _EdgeIter>
183 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
187 typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
189 inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
191 inline bool operator==(const _Self& x) const { return oi == x.oi; }
192 inline bool operator!=(const _Self& x) const { return !operator==(x); }
194 // operator*() differs for pred or succ iterator
195 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
196 inline _NodeType* operator->() const { return operator*(); }
198 inline _EdgeType* getEdge() const { return *(oi); }
200 inline _Self &operator++() { ++oi; return *this; } // Preincrement
201 inline _Self operator++(int) { // Postincrement
202 _Self tmp(*this); ++*this; return tmp;
205 inline _Self &operator--() { --oi; return *this; } // Predecrement
206 inline _Self operator--(int) { // Postdecrement
207 _Self tmp = *this; --*this; return tmp;
211 template <class _NodeType, class _EdgeType, class _EdgeIter>
212 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
216 typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
218 inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
220 inline bool operator==(const _Self& x) const { return oi == x.oi; }
221 inline bool operator!=(const _Self& x) const { return !operator==(x); }
223 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
224 inline _NodeType* operator->() const { return operator*(); }
226 inline _EdgeType* getEdge() const { return *(oi); }
228 inline _Self &operator++() { ++oi; return *this; } // Preincrement
229 inline _Self operator++(int) { // Postincrement
230 _Self tmp(*this); ++*this; return tmp;
233 inline _Self &operator--() { --oi; return *this; } // Predecrement
234 inline _Self operator--(int) { // Postdecrement
235 _Self tmp = *this; --*this; return tmp;
241 // sg_pred_const_iterator
243 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
245 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
246 sg_pred_const_iterator;
248 inline sg_pred_iterator pred_begin(SchedGraphNode *N) {
249 return sg_pred_iterator(N->beginInEdges());
251 inline sg_pred_iterator pred_end(SchedGraphNode *N) {
252 return sg_pred_iterator(N->endInEdges());
254 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
255 return sg_pred_const_iterator(N->beginInEdges());
257 inline sg_pred_const_iterator pred_end(const SchedGraphNode *N) {
258 return sg_pred_const_iterator(N->endInEdges());
264 // sg_succ_const_iterator
266 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
268 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
269 sg_succ_const_iterator;
271 inline sg_succ_iterator succ_begin(SchedGraphNode *N) {
272 return sg_succ_iterator(N->beginOutEdges());
274 inline sg_succ_iterator succ_end(SchedGraphNode *N) {
275 return sg_succ_iterator(N->endOutEdges());
277 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
278 return sg_succ_const_iterator(N->beginOutEdges());
280 inline sg_succ_const_iterator succ_end(const SchedGraphNode *N) {
281 return sg_succ_const_iterator(N->endOutEdges());
284 // Provide specializations of GraphTraits to be able to use graph iterators on
285 // the scheduling graph!
287 template <> struct GraphTraits<SchedGraph*> {
288 typedef SchedGraphNode NodeType;
289 typedef sg_succ_iterator ChildIteratorType;
291 static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
292 static inline ChildIteratorType child_begin(NodeType *N) {
293 return succ_begin(N);
295 static inline ChildIteratorType child_end(NodeType *N) {
300 template <> struct GraphTraits<const SchedGraph*> {
301 typedef const SchedGraphNode NodeType;
302 typedef sg_succ_const_iterator ChildIteratorType;
304 static inline NodeType *getEntryNode(const SchedGraph *SG) {
305 return (NodeType*)SG->getRoot();
307 static inline ChildIteratorType child_begin(NodeType *N) {
308 return succ_begin(N);
310 static inline ChildIteratorType child_end(NodeType *N) {