2 ****************************************************************************
7 * Scheduling graph based on SSA graph plus extra dependence edges
8 * capturing dependences due to machine resources (machine registers,
9 * CC registers, and any others).
12 * This graph tries to leverage the SSA graph as much as possible,
13 * but captures the extra dependences through a common interface.
16 * 7/20/01 - Vikram Adve - Created
17 ***************************************************************************/
19 #ifndef LLVM_CODEGEN_SCHEDGRAPH_H
20 #define LLVM_CODEGEN_SCHEDGRAPH_H
22 #include "llvm/Support/NonCopyable.h"
23 #include "llvm/Support/HashExtras.h"
24 #include "llvm/Support/GraphTraits.h"
36 class NodeToRegRefMap;
39 /******************** Exported Data Types and Constants ********************/
41 typedef int ResourceId;
42 const ResourceId InvalidResourceId = -1;
45 //*********************** Public Class Declarations ************************/
47 class SchedGraphEdge: public NonCopyable {
49 enum SchedGraphEdgeDepType {
50 CtrlDep, MemoryDep, DefUseDep, MachineRegister, MachineResource
52 enum DataDepOrderType {
53 TrueDep, AntiDep, OutputDep, NonDataDep
59 SchedGraphEdgeDepType depType;
60 DataDepOrderType depOrderType;
61 int minDelay; // cached latency (assumes fixed target arch)
66 ResourceId resourceId;
70 // For all constructors, if minDelay is unspecified, minDelay is
71 // set to _src->getLatency().
72 // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
73 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
74 SchedGraphNode* _sink,
75 SchedGraphEdgeDepType _depType,
76 DataDepOrderType _depOrderType =TrueDep,
79 // constructor for explicit def-use or memory def-use edge
80 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
81 SchedGraphNode* _sink,
83 DataDepOrderType _depOrderType =TrueDep,
86 // constructor for machine register dependence
87 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
88 SchedGraphNode* _sink,
90 DataDepOrderType _depOrderType =TrueDep,
93 // constructor for any other machine resource dependences.
94 // DataDepOrderType is always NonDataDep. It it not an argument to
95 // avoid overloading ambiguity with previous constructor.
96 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
97 SchedGraphNode* _sink,
98 ResourceId _resourceId,
101 /*dtor*/ ~SchedGraphEdge();
103 SchedGraphNode* getSrc () const { return src; }
104 SchedGraphNode* getSink () const { return sink; }
105 int getMinDelay () const { return minDelay; }
106 SchedGraphEdgeDepType getDepType () const { return depType; }
108 const Value* getValue () const {
109 assert(depType == DefUseDep || depType == MemoryDep); return val;
111 int getMachineReg () const {
112 assert(depType == MachineRegister); return machineRegNum;
114 int getResourceId () const {
115 assert(depType == MachineResource); return resourceId;
122 friend ostream& operator<<(ostream& os, const SchedGraphEdge& edge);
124 void dump (int indent=0) const;
127 // disable default ctor
128 /*ctor*/ SchedGraphEdge(); // DO NOT IMPLEMENT
133 class SchedGraphNode: public NonCopyable {
136 const Instruction* instr;
137 const MachineInstr* minstr;
138 vector<SchedGraphEdge*> inEdges;
139 vector<SchedGraphEdge*> outEdges;
143 typedef vector<SchedGraphEdge*>:: iterator iterator;
144 typedef vector<SchedGraphEdge*>::const_iterator const_iterator;
145 typedef vector<SchedGraphEdge*>:: reverse_iterator reverse_iterator;
146 typedef vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
152 unsigned int getNodeId () const { return nodeId; }
153 const Instruction* getInstr () const { return instr; }
154 const MachineInstr* getMachineInstr () const { return minstr; }
155 int getLatency () const { return latency; }
156 unsigned int getNumInEdges () const { return inEdges.size(); }
157 unsigned int getNumOutEdges () const { return outEdges.size(); }
158 bool isDummyNode () const { return (minstr == NULL); }
163 iterator beginInEdges () { return inEdges.begin(); }
164 iterator endInEdges () { return inEdges.end(); }
165 iterator beginOutEdges () { return outEdges.begin(); }
166 iterator endOutEdges () { return outEdges.end(); }
168 const_iterator beginInEdges () const { return inEdges.begin(); }
169 const_iterator endInEdges () const { return inEdges.end(); }
170 const_iterator beginOutEdges () const { return outEdges.begin(); }
171 const_iterator endOutEdges () const { return outEdges.end(); }
177 friend ostream& operator<<(ostream& os, const SchedGraphNode& node);
179 void dump (int indent=0) const;
182 friend class SchedGraph; // give access for ctor and dtor
183 friend class SchedGraphEdge; // give access for adding edges
185 void addInEdge (SchedGraphEdge* edge);
186 void addOutEdge (SchedGraphEdge* edge);
188 void removeInEdge (const SchedGraphEdge* edge);
189 void removeOutEdge (const SchedGraphEdge* edge);
191 // disable default constructor and provide a ctor for single-block graphs
192 /*ctor*/ SchedGraphNode(); // DO NOT IMPLEMENT
193 /*ctor*/ SchedGraphNode (unsigned int _nodeId,
194 const Instruction* _instr,
195 const MachineInstr* _minstr,
196 const TargetMachine& _target);
197 /*dtor*/ ~SchedGraphNode ();
204 private hash_map<const MachineInstr*, SchedGraphNode*>
207 vector<const BasicBlock*> bbVec; // basic blocks included in the graph
208 SchedGraphNode* graphRoot; // the root and leaf are not inserted
209 SchedGraphNode* graphLeaf; // in the hash_map (see getNumNodes())
212 typedef hash_map<const MachineInstr*, SchedGraphNode*>::iterator iterator;
213 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
219 const vector<const BasicBlock*>& getBasicBlocks() const { return bbVec; }
220 const unsigned int getNumNodes() const { return size()+2; }
221 SchedGraphNode* getRoot() const { return graphRoot; }
222 SchedGraphNode* getLeaf() const { return graphLeaf; }
224 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
225 const_iterator onePair = this->find(minstr);
226 return (onePair != this->end())? (*onePair).second : NULL;
230 // Delete nodes or edges from the graph.
232 void eraseNode (SchedGraphNode* node);
234 void eraseIncomingEdges (SchedGraphNode* node,
235 bool addDummyEdges = true);
237 void eraseOutgoingEdges (SchedGraphNode* node,
238 bool addDummyEdges = true);
240 void eraseIncidentEdges (SchedGraphNode* node,
241 bool addDummyEdges = true);
244 // Unordered iterators.
245 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
248 return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
251 return hash_map<const MachineInstr*, SchedGraphNode*>::end();
253 const_iterator begin() const {
254 return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
256 const_iterator end() const {
257 return hash_map<const MachineInstr*, SchedGraphNode*>::end();
261 // Ordered iterators.
262 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
264 // void postord_init();
265 // postorder_iterator postord_begin();
266 // postorder_iterator postord_end();
267 // const_postorder_iterator postord_begin() const;
268 // const_postorder_iterator postord_end() const;
276 friend class SchedGraphSet; // give access to ctor
278 // disable default constructor and provide a ctor for single-block graphs
279 /*ctor*/ SchedGraph (); // DO NOT IMPLEMENT
280 /*ctor*/ SchedGraph (const BasicBlock* bb,
281 const TargetMachine& target);
282 /*dtor*/ ~SchedGraph ();
284 inline void noteGraphNodeForInstr (const MachineInstr* minstr,
285 SchedGraphNode* node)
287 assert((*this)[minstr] == NULL);
288 (*this)[minstr] = node;
294 void buildGraph (const TargetMachine& target);
296 void addEdgesForInstruction (SchedGraphNode* node,
297 NodeToRegRefMap& regToRefVecMap,
298 const TargetMachine& target);
300 void addCDEdges (const TerminatorInst* term,
301 const TargetMachine& target);
303 void addMemEdges (const vector<const Instruction*>& memVec,
304 const TargetMachine& target);
306 void addMachineRegEdges (NodeToRegRefMap& regToRefVecMap,
307 const TargetMachine& target);
309 void addSSAEdge (SchedGraphNode* node,
311 const TargetMachine& target);
313 void addDummyEdges ();
317 class SchedGraphSet :
319 private hash_map<const BasicBlock*, SchedGraph*>
322 const Method* method;
325 typedef hash_map<const BasicBlock*, SchedGraph*>::iterator iterator;
326 typedef hash_map<const BasicBlock*, SchedGraph*>::const_iterator const_iterator;
329 /*ctor*/ SchedGraphSet (const Method* _method,
330 const TargetMachine& target);
331 /*dtor*/ ~SchedGraphSet ();
336 SchedGraph* getGraphForBasicBlock (const BasicBlock* bb) const {
337 const_iterator onePair = this->find(bb);
338 return (onePair != this->end())? (*onePair).second : NULL;
345 return hash_map<const BasicBlock*, SchedGraph*>::begin();
348 return hash_map<const BasicBlock*, SchedGraph*>::end();
350 const_iterator begin() const {
351 return hash_map<const BasicBlock*, SchedGraph*>::begin();
353 const_iterator end() const {
354 return hash_map<const BasicBlock*, SchedGraph*>::end();
363 inline void noteGraphForBlock(const BasicBlock* bb, SchedGraph* graph) {
364 assert((*this)[bb] == NULL);
371 void buildGraphsForMethod (const Method *method,
372 const TargetMachine& target);
376 //********************** Sched Graph Iterators *****************************/
378 // Ok to make it a template because it shd get instantiated at most twice:
379 // for <SchedGraphNode, SchedGraphNode::iterator> and
380 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
382 template <class _NodeType, class _EdgeType, class _EdgeIter>
383 class PredIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
387 typedef PredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
389 inline PredIterator(_EdgeIter startEdge) : oi(startEdge) {}
391 inline bool operator==(const _Self& x) const { return oi == x.oi; }
392 inline bool operator!=(const _Self& x) const { return !operator==(x); }
394 // operator*() differs for pred or succ iterator
395 inline _NodeType* operator*() const { return (*oi)->getSrc(); }
396 inline _NodeType* operator->() const { return operator*(); }
398 inline _EdgeType* getEdge() const { return *(oi); }
400 inline _Self &operator++() { ++oi; return *this; } // Preincrement
401 inline _Self operator++(int) { // Postincrement
402 _Self tmp(*this); ++*this; return tmp;
405 inline _Self &operator--() { --oi; return *this; } // Predecrement
406 inline _Self operator--(int) { // Postdecrement
407 _Self tmp = *this; --*this; return tmp;
411 template <class _NodeType, class _EdgeType, class _EdgeIter>
412 class SuccIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
416 typedef SuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
418 inline SuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
420 inline bool operator==(const _Self& x) const { return oi == x.oi; }
421 inline bool operator!=(const _Self& x) const { return !operator==(x); }
423 inline _NodeType* operator*() const { return (*oi)->getSink(); }
424 inline _NodeType* operator->() const { return operator*(); }
426 inline _EdgeType* getEdge() const { return *(oi); }
428 inline _Self &operator++() { ++oi; return *this; } // Preincrement
429 inline _Self operator++(int) { // Postincrement
430 _Self tmp(*this); ++*this; return tmp;
433 inline _Self &operator--() { --oi; return *this; } // Predecrement
434 inline _Self operator--(int) { // Postdecrement
435 _Self tmp = *this; --*this; return tmp;
441 // sg_pred_const_iterator
443 typedef PredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
445 typedef PredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
446 sg_pred_const_iterator;
448 inline sg_pred_iterator pred_begin( SchedGraphNode *N) {
449 return sg_pred_iterator(N->beginInEdges());
451 inline sg_pred_iterator pred_end( SchedGraphNode *N) {
452 return sg_pred_iterator(N->endInEdges());
454 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
455 return sg_pred_const_iterator(N->beginInEdges());
457 inline sg_pred_const_iterator pred_end( const SchedGraphNode *N) {
458 return sg_pred_const_iterator(N->endInEdges());
464 // sg_succ_const_iterator
466 typedef SuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
468 typedef SuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
469 sg_succ_const_iterator;
471 inline sg_succ_iterator succ_begin( SchedGraphNode *N) {
472 return sg_succ_iterator(N->beginOutEdges());
474 inline sg_succ_iterator succ_end( SchedGraphNode *N) {
475 return sg_succ_iterator(N->endOutEdges());
477 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
478 return sg_succ_const_iterator(N->beginOutEdges());
480 inline sg_succ_const_iterator succ_end( const SchedGraphNode *N) {
481 return sg_succ_const_iterator(N->endOutEdges());
484 // Provide specializations of GraphTraits to be able to use graph iterators on
485 // the scheduling graph!
487 template <> struct GraphTraits<SchedGraph*> {
488 typedef SchedGraphNode NodeType;
489 typedef sg_succ_iterator ChildIteratorType;
491 static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
492 static inline ChildIteratorType child_begin(NodeType *N) {
493 return succ_begin(N);
495 static inline ChildIteratorType child_end(NodeType *N) {
500 template <> struct GraphTraits<const SchedGraph*> {
501 typedef const SchedGraphNode NodeType;
502 typedef sg_succ_const_iterator ChildIteratorType;
504 static inline NodeType *getEntryNode(const SchedGraph *SG) {
505 return SG->getRoot();
507 static inline ChildIteratorType child_begin(NodeType *N) {
508 return succ_begin(N);
510 static inline ChildIteratorType child_end(NodeType *N) {
516 //************************ External Functions *****************************/
519 ostream& operator<<(ostream& os, const SchedGraphEdge& edge);
521 ostream& operator<<(ostream& os, const SchedGraphNode& node);
524 /***************************************************************************/