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/CFGdecls.h" // just for graph iterators
23 #include "llvm/Support/NonCopyable.h"
24 #include "llvm/Support/HashExtras.h"
35 class NodeToRegRefMap;
37 /******************** Exported Data Types and Constants ********************/
39 typedef int ResourceId;
40 const ResourceId InvalidResourceId = -1;
43 //*********************** Public Class Declarations ************************/
45 class SchedGraphEdge: public NonCopyable {
47 enum SchedGraphEdgeDepType {
48 CtrlDep, MemoryDep, DefUseDep, MachineRegister, MachineResource
50 enum DataDepOrderType {
51 TrueDep, AntiDep, OutputDep, NonDataDep
57 SchedGraphEdgeDepType depType;
58 DataDepOrderType depOrderType;
59 int minDelay; // cached latency (assumes fixed target arch)
64 ResourceId resourceId;
68 // For all constructors, if minDelay is unspecified, minDelay is
69 // set to _src->getLatency().
70 // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
71 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
72 SchedGraphNode* _sink,
73 SchedGraphEdgeDepType _depType,
74 DataDepOrderType _depOrderType =TrueDep,
77 // constructor for explicit def-use or memory def-use edge
78 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
79 SchedGraphNode* _sink,
81 DataDepOrderType _depOrderType =TrueDep,
84 // constructor for machine register dependence
85 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
86 SchedGraphNode* _sink,
88 DataDepOrderType _depOrderType =TrueDep,
91 // constructor for any other machine resource dependences.
92 // DataDepOrderType is always NonDataDep. It it not an argument to
93 // avoid overloading ambiguity with previous constructor.
94 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
95 SchedGraphNode* _sink,
96 ResourceId _resourceId,
99 /*dtor*/ ~SchedGraphEdge() {}
101 SchedGraphNode* getSrc () const { return src; }
102 SchedGraphNode* getSink () const { return sink; }
103 int getMinDelay () const { return minDelay; }
104 SchedGraphEdgeDepType getDepType () const { return depType; }
106 const Value* getValue () const {
107 assert(depType == DefUseDep || depType == MemoryDep); return val;
109 int getMachineReg () const {
110 assert(depType == MachineRegister); return machineRegNum;
112 int getResourceId () const {
113 assert(depType == MachineResource); return resourceId;
120 friend ostream& operator<<(ostream& os, const SchedGraphEdge& edge);
122 void dump (int indent=0) const;
125 // disable default ctor
126 /*ctor*/ SchedGraphEdge(); // DO NOT IMPLEMENT
131 class SchedGraphNode: public NonCopyable {
134 const Instruction* instr;
135 const MachineInstr* minstr;
136 vector<SchedGraphEdge*> inEdges;
137 vector<SchedGraphEdge*> outEdges;
141 typedef vector<SchedGraphEdge*>::iterator iterator;
142 typedef vector<SchedGraphEdge*>::const_iterator const_iterator;
148 unsigned int getNodeId () const { return nodeId; }
149 const Instruction* getInstr () const { return instr; }
150 const MachineInstr* getMachineInstr () const { return minstr; }
151 int getLatency () const { return latency; }
152 unsigned int getNumInEdges () const { return inEdges.size(); }
153 unsigned int getNumOutEdges () const { return outEdges.size(); }
154 bool isDummyNode () const { return (minstr == NULL); }
159 iterator beginInEdges () { return inEdges.begin(); }
160 iterator endInEdges () { return inEdges.end(); }
161 iterator beginOutEdges () { return outEdges.begin(); }
162 iterator endOutEdges () { return outEdges.end(); }
164 const_iterator beginInEdges () const { return inEdges.begin(); }
165 const_iterator endInEdges () const { return inEdges.end(); }
166 const_iterator beginOutEdges () const { return outEdges.begin(); }
167 const_iterator endOutEdges () const { return outEdges.end(); }
170 // Limited modifier methods
172 void eraseAllEdges ();
178 friend ostream& operator<<(ostream& os, const SchedGraphNode& node);
180 void dump (int indent=0) const;
183 friend class SchedGraph; // give access for ctor and dtor
184 friend class SchedGraphEdge; // give access for adding edges
186 void addInEdge (SchedGraphEdge* edge);
187 void addOutEdge (SchedGraphEdge* edge);
189 void removeInEdge (const SchedGraphEdge* edge);
190 void removeOutEdge (const SchedGraphEdge* edge);
192 // disable default constructor and provide a ctor for single-block graphs
193 /*ctor*/ SchedGraphNode(); // DO NOT IMPLEMENT
194 /*ctor*/ SchedGraphNode (unsigned int _nodeId,
195 const Instruction* _instr,
196 const MachineInstr* _minstr,
197 const TargetMachine& _target);
198 /*dtor*/ ~SchedGraphNode ();
205 private hash_map<const MachineInstr*, SchedGraphNode*>
208 vector<const BasicBlock*> bbVec; // basic blocks included in the graph
209 SchedGraphNode* graphRoot; // the root and leaf are not inserted
210 SchedGraphNode* graphLeaf; // in the hash_map (see getNumNodes())
213 typedef hash_map<const MachineInstr*, SchedGraphNode*>::iterator iterator;
214 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
220 const vector<const BasicBlock*>& getBasicBlocks() const { return bbVec; }
221 const unsigned int getNumNodes() const { return size()+2; }
222 SchedGraphNode* getRoot() const { return graphRoot; }
223 SchedGraphNode* getLeaf() const { return graphLeaf; }
225 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
226 const_iterator onePair = this->find(minstr);
227 return (onePair != this->end())? (*onePair).second : NULL;
231 // Delete a node from the graph.
233 void eraseNode(SchedGraphNode* node);
236 // Unordered iterators.
237 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
240 return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
243 return hash_map<const MachineInstr*, SchedGraphNode*>::end();
245 const_iterator begin() const {
246 return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
248 const_iterator end() const {
249 return hash_map<const MachineInstr*, SchedGraphNode*>::end();
253 // Ordered iterators.
254 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
256 // void postord_init();
257 // postorder_iterator postord_begin();
258 // postorder_iterator postord_end();
259 // const_postorder_iterator postord_begin() const;
260 // const_postorder_iterator postord_end() const;
268 friend class SchedGraphSet; // give access to ctor
270 // disable default constructor and provide a ctor for single-block graphs
271 /*ctor*/ SchedGraph (); // DO NOT IMPLEMENT
272 /*ctor*/ SchedGraph (const BasicBlock* 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 addEdgesForInstruction (SchedGraphNode* node,
289 NodeToRegRefMap& regToRefVecMap,
290 const TargetMachine& target);
292 void addCDEdges (const TerminatorInst* term,
293 const TargetMachine& target);
295 void addMemEdges (const vector<const Instruction*>& memVec,
296 const TargetMachine& target);
298 void addMachineRegEdges (NodeToRegRefMap& regToRefVecMap,
299 const TargetMachine& target);
301 void addSSAEdge (SchedGraphNode* node,
303 const TargetMachine& target);
305 void addDummyEdges ();
309 class SchedGraphSet :
311 private hash_map<const BasicBlock*, SchedGraph*>
314 const Method* method;
317 typedef hash_map<const BasicBlock*, SchedGraph*>::iterator iterator;
318 typedef hash_map<const BasicBlock*, SchedGraph*>::const_iterator const_iterator;
321 /*ctor*/ SchedGraphSet (const Method* _method,
322 const TargetMachine& target);
323 /*dtor*/ ~SchedGraphSet ();
328 SchedGraph* getGraphForBasicBlock (const BasicBlock* bb) const {
329 const_iterator onePair = this->find(bb);
330 return (onePair != this->end())? (*onePair).second : NULL;
337 return hash_map<const BasicBlock*, SchedGraph*>::begin();
340 return hash_map<const BasicBlock*, SchedGraph*>::end();
342 const_iterator begin() const {
343 return hash_map<const BasicBlock*, SchedGraph*>::begin();
345 const_iterator end() const {
346 return hash_map<const BasicBlock*, SchedGraph*>::end();
355 inline void noteGraphForBlock(const BasicBlock* bb, SchedGraph* graph) {
356 assert((*this)[bb] == NULL);
363 void buildGraphsForMethod (const Method *method,
364 const TargetMachine& target);
368 //********************** Sched Graph Iterators *****************************/
370 // Ok to make it a template because it shd get instantiated at most twice:
371 // for <SchedGraphNode, SchedGraphNode::iterator> and
372 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
374 template <class _NodeType, class _EdgeType, class _EdgeIter>
375 class PredIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
379 typedef PredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
381 inline PredIterator(_EdgeIter startEdge) : oi(startEdge) {}
383 inline bool operator==(const _Self& x) const { return oi == x.oi; }
384 inline bool operator!=(const _Self& x) const { return !operator==(x); }
386 // operator*() differs for pred or succ iterator
387 inline _NodeType* operator*() const { return (*oi)->getSrc(); }
388 inline _NodeType* operator->() const { return operator*(); }
390 inline _EdgeType* getEdge() const { return *(oi); }
392 inline _Self &operator++() { ++oi; return *this; } // Preincrement
393 inline _Self operator++(int) { // Postincrement
394 _Self tmp(*this); ++*this; return tmp;
397 inline _Self &operator--() { --oi; return *this; } // Predecrement
398 inline _Self operator--(int) { // Postdecrement
399 _Self tmp = *this; --*this; return tmp;
403 template <class _NodeType, class _EdgeType, class _EdgeIter>
404 class SuccIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
408 typedef SuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
410 inline SuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
412 inline bool operator==(const _Self& x) const { return oi == x.oi; }
413 inline bool operator!=(const _Self& x) const { return !operator==(x); }
415 inline _NodeType* operator*() const { return (*oi)->getSink(); }
416 inline _NodeType* operator->() const { return operator*(); }
418 inline _EdgeType* getEdge() const { return *(oi); }
420 inline _Self &operator++() { ++oi; return *this; } // Preincrement
421 inline _Self operator++(int) { // Postincrement
422 _Self tmp(*this); ++*this; return tmp;
425 inline _Self &operator--() { --oi; return *this; } // Predecrement
426 inline _Self operator--(int) { // Postdecrement
427 _Self tmp = *this; --*this; return tmp;
433 // sg_pred_const_iterator
435 typedef PredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
437 typedef PredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
438 sg_pred_const_iterator;
440 inline sg_pred_iterator pred_begin( SchedGraphNode *N) {
441 return sg_pred_iterator(N->beginInEdges());
443 inline sg_pred_iterator pred_end( SchedGraphNode *N) {
444 return sg_pred_iterator(N->endInEdges());
446 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
447 return sg_pred_const_iterator(N->beginInEdges());
449 inline sg_pred_const_iterator pred_end( const SchedGraphNode *N) {
450 return sg_pred_const_iterator(N->endInEdges());
456 // sg_succ_const_iterator
458 typedef SuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
460 typedef SuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
461 sg_succ_const_iterator;
463 inline sg_succ_iterator succ_begin( SchedGraphNode *N) {
464 return sg_succ_iterator(N->beginOutEdges());
466 inline sg_succ_iterator succ_end( SchedGraphNode *N) {
467 return sg_succ_iterator(N->endOutEdges());
469 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
470 return sg_succ_const_iterator(N->beginOutEdges());
472 inline sg_succ_const_iterator succ_end( const SchedGraphNode *N) {
473 return sg_succ_const_iterator(N->endOutEdges());
480 typedef cfg::POIterator<SchedGraphNode, sg_succ_iterator> sg_po_iterator;
481 typedef cfg::POIterator<const SchedGraphNode,
482 sg_succ_const_iterator> sg_po_const_iterator;
485 //************************ External Functions *****************************/
488 ostream& operator<<(ostream& os, const SchedGraphEdge& edge);
490 ostream& operator<<(ostream& os, const SchedGraphNode& node);
493 /***************************************************************************/