1 //===-- SchedGraph.h - Scheduling Graph -------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This is a scheduling graph based on SSA graph plus extra dependence edges
11 // capturing dependences due to machine resources (machine registers, CC
12 // registers, and any others).
14 // This graph tries to leverage the SSA graph as much as possible, but captures
15 // the extra dependences through a common interface.
17 //===----------------------------------------------------------------------===//
19 #ifndef LLVM_CODEGEN_SCHEDGRAPH_H
20 #define LLVM_CODEGEN_SCHEDGRAPH_H
22 #include "llvm/CodeGen/SchedGraphCommon.h"
23 #include "llvm/CodeGen/MachineInstr.h"
24 #include "llvm/Transforms/Scalar.h"
25 #include "Support/hash_map"
26 #include "Support/GraphTraits.h"
29 class ValueToDefVecMap;
32 class SchedGraphNode : public SchedGraphNodeCommon {
34 MachineBasicBlock *MBB;
35 const MachineInstr *MI;
38 SchedGraphNode(unsigned nodeId, MachineBasicBlock *mbb, int indexInBB,
39 const TargetMachine& Target);
42 friend class SchedGraph; // give access for ctor and dtor
43 friend class SchedGraphEdge; // give access for adding edges
48 const MachineInstr* getMachineInstr() const { return MI; }
49 const MachineOpCode getOpCode() const { return MI->getOpCode(); }
50 bool isDummyNode() const { return (MI == NULL); }
51 MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
53 void print(std::ostream &os) const;
56 class SchedGraph : public SchedGraphCommon {
57 MachineBasicBlock &MBB;
58 hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
61 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
62 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
64 MachineBasicBlock& getBasicBlock() const{return MBB;}
65 const unsigned int getNumNodes() const { return GraphMap.size()+2; }
66 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
67 const_iterator onePair = find(MI);
68 return (onePair != end())? onePair->second : NULL;
75 SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
78 // Unordered iterators.
79 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
81 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
82 return GraphMap.begin();
84 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
85 return GraphMap.end();
88 unsigned size() { return GraphMap.size(); }
89 iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
91 SchedGraphNode *&operator[](const MachineInstr *MI) {
96 friend class SchedGraphSet; // give access to ctor
98 inline void noteGraphNodeForInstr (const MachineInstr* minstr,
99 SchedGraphNode* node) {
100 assert((*this)[minstr] == NULL);
101 (*this)[minstr] = node;
107 void buildGraph(const TargetMachine& target);
109 void buildNodesForBB(const TargetMachine& target,MachineBasicBlock &MBB,
110 std::vector<SchedGraphNode*>& memNV,
111 std::vector<SchedGraphNode*>& callNV,
112 RegToRefVecMap& regToRefVecMap,
113 ValueToDefVecMap& valueToDefVecMap);
116 void findDefUseInfoAtInstr(const TargetMachine& target, SchedGraphNode* node,
117 std::vector<SchedGraphNode*>& memNV,
118 std::vector<SchedGraphNode*>& callNV,
119 RegToRefVecMap& regToRefVecMap,
120 ValueToDefVecMap& valueToDefVecMap);
122 void addEdgesForInstruction(const MachineInstr& minstr,
123 const ValueToDefVecMap& valueToDefVecMap,
124 const TargetMachine& target);
126 void addCDEdges(const TerminatorInst* term, const TargetMachine& target);
128 void addMemEdges(const std::vector<SchedGraphNode*>& memNod,
129 const TargetMachine& target);
131 void addCallCCEdges(const std::vector<SchedGraphNode*>& memNod,
132 MachineBasicBlock& bbMvec,
133 const TargetMachine& target);
135 void addCallDepEdges(const std::vector<SchedGraphNode*>& callNV,
136 const TargetMachine& target);
138 void addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
139 const TargetMachine& target);
141 void addEdgesForValue(SchedGraphNode* refNode, const RefVec& defVec,
142 const Value* defValue, bool refNodeIsDef,
143 bool refNodeIsDefAndUse,
144 const TargetMachine& target);
146 void addDummyEdges();
152 class SchedGraphSet {
153 const Function* function;
154 std::vector<SchedGraph*> Graphs;
157 void buildGraphsForMethod(const Function *F, const TargetMachine& target);
159 inline void addGraph(SchedGraph* graph) {
160 assert(graph != NULL);
161 Graphs.push_back(graph);
165 SchedGraphSet(const Function *function, const TargetMachine& target);
169 typedef std::vector<SchedGraph*>::const_iterator iterator;
170 typedef std::vector<SchedGraph*>::const_iterator const_iterator;
172 std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
173 std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
181 //********************** Sched Graph Iterators *****************************/
183 // Ok to make it a template because it shd get instantiated at most twice:
184 // for <SchedGraphNode, SchedGraphNode::iterator> and
185 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
187 template <class _NodeType, class _EdgeType, class _EdgeIter>
188 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
192 typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
194 inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
196 inline bool operator==(const _Self& x) const { return oi == x.oi; }
197 inline bool operator!=(const _Self& x) const { return !operator==(x); }
199 // operator*() differs for pred or succ iterator
200 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
201 inline _NodeType* operator->() const { return operator*(); }
203 inline _EdgeType* getEdge() const { return *(oi); }
205 inline _Self &operator++() { ++oi; return *this; } // Preincrement
206 inline _Self operator++(int) { // Postincrement
207 _Self tmp(*this); ++*this; return tmp;
210 inline _Self &operator--() { --oi; return *this; } // Predecrement
211 inline _Self operator--(int) { // Postdecrement
212 _Self tmp = *this; --*this; return tmp;
216 template <class _NodeType, class _EdgeType, class _EdgeIter>
217 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
221 typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
223 inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
225 inline bool operator==(const _Self& x) const { return oi == x.oi; }
226 inline bool operator!=(const _Self& x) const { return !operator==(x); }
228 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
229 inline _NodeType* operator->() const { return operator*(); }
231 inline _EdgeType* getEdge() const { return *(oi); }
233 inline _Self &operator++() { ++oi; return *this; } // Preincrement
234 inline _Self operator++(int) { // Postincrement
235 _Self tmp(*this); ++*this; return tmp;
238 inline _Self &operator--() { --oi; return *this; } // Predecrement
239 inline _Self operator--(int) { // Postdecrement
240 _Self tmp = *this; --*this; return tmp;
246 // sg_pred_const_iterator
248 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
250 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
251 sg_pred_const_iterator;
253 inline sg_pred_iterator pred_begin(SchedGraphNode *N) {
254 return sg_pred_iterator(N->beginInEdges());
256 inline sg_pred_iterator pred_end(SchedGraphNode *N) {
257 return sg_pred_iterator(N->endInEdges());
259 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
260 return sg_pred_const_iterator(N->beginInEdges());
262 inline sg_pred_const_iterator pred_end(const SchedGraphNode *N) {
263 return sg_pred_const_iterator(N->endInEdges());
269 // sg_succ_const_iterator
271 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
273 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
274 sg_succ_const_iterator;
276 inline sg_succ_iterator succ_begin(SchedGraphNode *N) {
277 return sg_succ_iterator(N->beginOutEdges());
279 inline sg_succ_iterator succ_end(SchedGraphNode *N) {
280 return sg_succ_iterator(N->endOutEdges());
282 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
283 return sg_succ_const_iterator(N->beginOutEdges());
285 inline sg_succ_const_iterator succ_end(const SchedGraphNode *N) {
286 return sg_succ_const_iterator(N->endOutEdges());
289 // Provide specializations of GraphTraits to be able to use graph iterators on
290 // the scheduling graph!
292 template <> struct GraphTraits<SchedGraph*> {
293 typedef SchedGraphNode NodeType;
294 typedef sg_succ_iterator ChildIteratorType;
296 static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
297 static inline ChildIteratorType child_begin(NodeType *N) {
298 return succ_begin(N);
300 static inline ChildIteratorType child_end(NodeType *N) {
305 template <> struct GraphTraits<const SchedGraph*> {
306 typedef const SchedGraphNode NodeType;
307 typedef sg_succ_const_iterator ChildIteratorType;
309 static inline NodeType *getEntryNode(const SchedGraph *SG) {
310 return (NodeType*)SG->getRoot();
312 static inline ChildIteratorType child_begin(NodeType *N) {
313 return succ_begin(N);
315 static inline ChildIteratorType child_end(NodeType *N) {