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/HashExtras.h"
19 #include "Support/GraphTraits.h"
31 class ValueToDefVecMap;
34 class MachineBasicBlock;
37 /******************** Exported Data Types and Constants ********************/
39 typedef int ResourceId;
40 const ResourceId InvalidRID = -1;
41 const ResourceId MachineCCRegsRID = -2; // use +ve numbers for actual regs
42 const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
43 const ResourceId MachineFPRegsRID = -4; // use +ve numbers for actual regs
46 //*********************** Public Class Declarations ************************/
48 class SchedGraphEdge: public NonCopyable {
50 enum SchedGraphEdgeDepType {
51 CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
53 enum DataDepOrderType {
54 TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
60 SchedGraphEdgeDepType depType;
61 unsigned int depOrderType;
62 int minDelay; // cached latency (assumes fixed target arch)
67 ResourceId resourceId;
71 // For all constructors, if minDelay is unspecified, minDelay is
72 // set to _src->getLatency().
73 // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
74 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
75 SchedGraphNode* _sink,
76 SchedGraphEdgeDepType _depType,
77 unsigned int _depOrderType,
80 // constructor for explicit value dependence (may be true/anti/output)
81 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
82 SchedGraphNode* _sink,
84 unsigned int _depOrderType,
87 // constructor for machine register dependence
88 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
89 SchedGraphNode* _sink,
91 unsigned int _depOrderType,
94 // constructor for any other machine resource dependences.
95 // DataDepOrderType is always NonDataDep. It it not an argument to
96 // avoid overloading ambiguity with previous constructor.
97 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
98 SchedGraphNode* _sink,
99 ResourceId _resourceId,
102 /*dtor*/ ~SchedGraphEdge();
104 SchedGraphNode* getSrc () const { return src; }
105 SchedGraphNode* getSink () const { return sink; }
106 int getMinDelay () const { return minDelay; }
107 SchedGraphEdgeDepType getDepType () const { return depType; }
109 const Value* getValue () const {
110 assert(depType == ValueDep); return val;
112 int getMachineReg () const {
113 assert(depType == MachineRegister); return machineRegNum;
115 int getResourceId () const {
116 assert(depType == MachineResource); return resourceId;
123 friend std::ostream& operator<<(std::ostream& os, const SchedGraphEdge& edge);
125 void dump (int indent=0) const;
128 // disable default ctor
129 /*ctor*/ SchedGraphEdge(); // DO NOT IMPLEMENT
134 class SchedGraphNode: public NonCopyable {
136 MachineBasicBlock *MBB;
137 const MachineInstr* minstr;
138 std::vector<SchedGraphEdge*> inEdges;
139 std::vector<SchedGraphEdge*> outEdges;
140 int origIndexInBB; // original position of machine instr in BB
144 typedef std::vector<SchedGraphEdge*>:: iterator iterator;
145 typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator;
146 typedef std::vector<SchedGraphEdge*>:: reverse_iterator reverse_iterator;
147 typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
153 unsigned getNodeId () const { return nodeId; }
154 const MachineInstr* getMachineInstr () const { return minstr; }
155 const MachineOpCode getOpCode () const { return minstr->getOpCode(); }
156 int getLatency () const { return latency; }
157 unsigned getNumInEdges () const { return inEdges.size(); }
158 unsigned getNumOutEdges () const { return outEdges.size(); }
159 bool isDummyNode () const { return (minstr == NULL); }
160 MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
161 int getOrigIndexInBB() const { return origIndexInBB; }
166 iterator beginInEdges () { return inEdges.begin(); }
167 iterator endInEdges () { return inEdges.end(); }
168 iterator beginOutEdges () { return outEdges.begin(); }
169 iterator endOutEdges () { return outEdges.end(); }
171 const_iterator beginInEdges () const { return inEdges.begin(); }
172 const_iterator endInEdges () const { return inEdges.end(); }
173 const_iterator beginOutEdges () const { return outEdges.begin(); }
174 const_iterator endOutEdges () const { return outEdges.end(); }
180 friend std::ostream& operator<<(std::ostream& os, const SchedGraphNode& node);
182 void dump (int indent=0) const;
185 friend class SchedGraph; // give access for ctor and dtor
186 friend class SchedGraphEdge; // give access for adding edges
188 void addInEdge (SchedGraphEdge* edge);
189 void addOutEdge (SchedGraphEdge* edge);
191 void removeInEdge (const SchedGraphEdge* edge);
192 void removeOutEdge (const SchedGraphEdge* edge);
194 // disable default constructor and provide a ctor for single-block graphs
195 /*ctor*/ SchedGraphNode(); // DO NOT IMPLEMENT
196 /*ctor*/ SchedGraphNode (unsigned nodeId,
197 MachineBasicBlock *mbb,
199 const TargetMachine& Target);
200 /*dtor*/ ~SchedGraphNode ();
207 private hash_map<const MachineInstr*, SchedGraphNode*>
209 MachineBasicBlock &MBB; // basic blocks for this graph
210 SchedGraphNode* graphRoot; // the root and leaf are not inserted
211 SchedGraphNode* graphLeaf; // in the hash_map (see getNumNodes())
213 typedef hash_map<const MachineInstr*, SchedGraphNode*> map_base;
215 using map_base::iterator;
216 using map_base::const_iterator;
222 MachineBasicBlock &getBasicBlock() const { return MBB; }
223 unsigned getNumNodes() const { return size()+2; }
224 SchedGraphNode* getRoot() const { return graphRoot; }
225 SchedGraphNode* getLeaf() const { return graphLeaf; }
227 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
228 const_iterator onePair = this->find(minstr);
229 return (onePair != this->end())? (*onePair).second : NULL;
233 // Delete nodes or edges from the graph.
235 void eraseNode (SchedGraphNode* node);
237 void eraseIncomingEdges (SchedGraphNode* node,
238 bool addDummyEdges = true);
240 void eraseOutgoingEdges (SchedGraphNode* node,
241 bool addDummyEdges = true);
243 void eraseIncidentEdges (SchedGraphNode* node,
244 bool addDummyEdges = true);
247 // Unordered iterators.
248 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
250 using map_base::begin;
254 // Ordered iterators.
255 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
257 // void postord_init();
258 // postorder_iterator postord_begin();
259 // postorder_iterator postord_end();
260 // const_postorder_iterator postord_begin() const;
261 // const_postorder_iterator postord_end() const;
269 friend class SchedGraphSet; // give access to ctor
271 // disable default constructor and provide a ctor for single-block graphs
272 /*ctor*/ SchedGraph (MachineBasicBlock &bb,
273 const TargetMachine& target);
274 /*dtor*/ ~SchedGraph ();
276 inline void noteGraphNodeForInstr (const MachineInstr* minstr,
277 SchedGraphNode* node)
279 assert((*this)[minstr] == NULL);
280 (*this)[minstr] = node;
286 void buildGraph (const TargetMachine& target);
288 void buildNodesForBB (const TargetMachine& target,
289 MachineBasicBlock &MBB,
290 std::vector<SchedGraphNode*>& memNod,
291 RegToRefVecMap& regToRefVecMap,
292 ValueToDefVecMap& valueToDefVecMap);
294 void findDefUseInfoAtInstr (const TargetMachine& target,
295 SchedGraphNode* node,
296 std::vector<SchedGraphNode*>& memNode,
297 RegToRefVecMap& regToRefVecMap,
298 ValueToDefVecMap& valueToDefVecMap);
300 void addEdgesForInstruction(const MachineInstr& minstr,
301 const ValueToDefVecMap& valueToDefVecMap,
302 const TargetMachine& target);
304 void addCDEdges (const TerminatorInst* term,
305 const TargetMachine& target);
307 void addMemEdges (const std::vector<SchedGraphNode*>& memNod,
308 const TargetMachine& target);
310 void addCallCCEdges (const std::vector<SchedGraphNode*>& memNod,
311 MachineBasicBlock& bbMvec,
312 const TargetMachine& target);
314 void addMachineRegEdges (RegToRefVecMap& regToRefVecMap,
315 const TargetMachine& target);
317 void addEdgesForValue (SchedGraphNode* refNode,
318 const RefVec& defVec,
319 const Value* defValue,
321 bool refNodeIsDefAndUse,
322 const TargetMachine& target);
324 void addDummyEdges ();
328 class SchedGraphSet :
330 private std::vector<SchedGraph*>
333 const Function* method;
336 typedef std::vector<SchedGraph*> baseVector;
337 using baseVector::iterator;
338 using baseVector::const_iterator;
341 /*ctor*/ SchedGraphSet (const Function * function,
342 const TargetMachine& target);
343 /*dtor*/ ~SchedGraphSet ();
346 using baseVector::begin;
347 using baseVector::end;
353 inline void addGraph(SchedGraph* graph) {
354 assert(graph != NULL);
355 this->push_back(graph);
359 void buildGraphsForMethod (const Function *F,
360 const TargetMachine& target);
364 //********************** Sched Graph Iterators *****************************/
366 // Ok to make it a template because it shd get instantiated at most twice:
367 // for <SchedGraphNode, SchedGraphNode::iterator> and
368 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
370 template <class _NodeType, class _EdgeType, class _EdgeIter>
371 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
375 typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
377 inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
379 inline bool operator==(const _Self& x) const { return oi == x.oi; }
380 inline bool operator!=(const _Self& x) const { return !operator==(x); }
382 // operator*() differs for pred or succ iterator
383 inline _NodeType* operator*() const { return (*oi)->getSrc(); }
384 inline _NodeType* operator->() const { return operator*(); }
386 inline _EdgeType* getEdge() const { return *(oi); }
388 inline _Self &operator++() { ++oi; return *this; } // Preincrement
389 inline _Self operator++(int) { // Postincrement
390 _Self tmp(*this); ++*this; return tmp;
393 inline _Self &operator--() { --oi; return *this; } // Predecrement
394 inline _Self operator--(int) { // Postdecrement
395 _Self tmp = *this; --*this; return tmp;
399 template <class _NodeType, class _EdgeType, class _EdgeIter>
400 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
404 typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
406 inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
408 inline bool operator==(const _Self& x) const { return oi == x.oi; }
409 inline bool operator!=(const _Self& x) const { return !operator==(x); }
411 inline _NodeType* operator*() const { return (*oi)->getSink(); }
412 inline _NodeType* operator->() const { return operator*(); }
414 inline _EdgeType* getEdge() const { return *(oi); }
416 inline _Self &operator++() { ++oi; return *this; } // Preincrement
417 inline _Self operator++(int) { // Postincrement
418 _Self tmp(*this); ++*this; return tmp;
421 inline _Self &operator--() { --oi; return *this; } // Predecrement
422 inline _Self operator--(int) { // Postdecrement
423 _Self tmp = *this; --*this; return tmp;
429 // sg_pred_const_iterator
431 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
433 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
434 sg_pred_const_iterator;
436 inline sg_pred_iterator pred_begin( SchedGraphNode *N) {
437 return sg_pred_iterator(N->beginInEdges());
439 inline sg_pred_iterator pred_end( SchedGraphNode *N) {
440 return sg_pred_iterator(N->endInEdges());
442 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
443 return sg_pred_const_iterator(N->beginInEdges());
445 inline sg_pred_const_iterator pred_end( const SchedGraphNode *N) {
446 return sg_pred_const_iterator(N->endInEdges());
452 // sg_succ_const_iterator
454 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
456 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
457 sg_succ_const_iterator;
459 inline sg_succ_iterator succ_begin( SchedGraphNode *N) {
460 return sg_succ_iterator(N->beginOutEdges());
462 inline sg_succ_iterator succ_end( SchedGraphNode *N) {
463 return sg_succ_iterator(N->endOutEdges());
465 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
466 return sg_succ_const_iterator(N->beginOutEdges());
468 inline sg_succ_const_iterator succ_end( const SchedGraphNode *N) {
469 return sg_succ_const_iterator(N->endOutEdges());
472 // Provide specializations of GraphTraits to be able to use graph iterators on
473 // the scheduling graph!
475 template <> struct GraphTraits<SchedGraph*> {
476 typedef SchedGraphNode NodeType;
477 typedef sg_succ_iterator ChildIteratorType;
479 static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
480 static inline ChildIteratorType child_begin(NodeType *N) {
481 return succ_begin(N);
483 static inline ChildIteratorType child_end(NodeType *N) {
488 template <> struct GraphTraits<const SchedGraph*> {
489 typedef const SchedGraphNode NodeType;
490 typedef sg_succ_const_iterator ChildIteratorType;
492 static inline NodeType *getEntryNode(const SchedGraph *SG) {
493 return SG->getRoot();
495 static inline ChildIteratorType child_begin(NodeType *N) {
496 return succ_begin(N);
498 static inline ChildIteratorType child_end(NodeType *N) {
504 std::ostream &operator<<(std::ostream& os, const SchedGraphEdge& edge);
505 std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node);