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 {
49 SchedGraphEdge(const SchedGraphEdge &); // DO NOT IMPLEMENT
50 void operator=(const SchedGraphEdge &); // DO NOT IMPLEMENT
52 enum SchedGraphEdgeDepType {
53 CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
55 enum DataDepOrderType {
56 TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
62 SchedGraphEdgeDepType depType;
63 unsigned int depOrderType;
64 int minDelay; // cached latency (assumes fixed target arch)
69 ResourceId resourceId;
73 // For all constructors, if minDelay is unspecified, minDelay is
74 // set to _src->getLatency().
75 // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
76 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
77 SchedGraphNode* _sink,
78 SchedGraphEdgeDepType _depType,
79 unsigned int _depOrderType,
82 // constructor for explicit value dependence (may be true/anti/output)
83 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
84 SchedGraphNode* _sink,
86 unsigned int _depOrderType,
89 // constructor for machine register dependence
90 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
91 SchedGraphNode* _sink,
93 unsigned int _depOrderType,
96 // constructor for any other machine resource dependences.
97 // DataDepOrderType is always NonDataDep. It it not an argument to
98 // avoid overloading ambiguity with previous constructor.
99 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
100 SchedGraphNode* _sink,
101 ResourceId _resourceId,
104 /*dtor*/ ~SchedGraphEdge();
106 SchedGraphNode* getSrc () const { return src; }
107 SchedGraphNode* getSink () const { return sink; }
108 int getMinDelay () const { return minDelay; }
109 SchedGraphEdgeDepType getDepType () const { return depType; }
111 const Value* getValue () const {
112 assert(depType == ValueDep); return val;
114 int getMachineReg () const {
115 assert(depType == MachineRegister); return machineRegNum;
117 int getResourceId () const {
118 assert(depType == MachineResource); return resourceId;
125 friend std::ostream& operator<<(std::ostream& os, const SchedGraphEdge& edge);
127 void dump (int indent=0) const;
130 // disable default ctor
131 /*ctor*/ SchedGraphEdge(); // DO NOT IMPLEMENT
136 class SchedGraphNode {
138 MachineBasicBlock *MBB;
139 const MachineInstr* minstr;
140 std::vector<SchedGraphEdge*> inEdges;
141 std::vector<SchedGraphEdge*> outEdges;
142 int origIndexInBB; // original position of machine instr in BB
145 SchedGraphNode(const SchedGraphNode &); // DO NOT IMPLEMENT
146 void operator=(const SchedGraphNode &); // DO NOT IMPLEMENT
148 typedef std::vector<SchedGraphEdge*>:: iterator iterator;
149 typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator;
150 typedef std::vector<SchedGraphEdge*>:: reverse_iterator reverse_iterator;
151 typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
157 unsigned getNodeId () const { return nodeId; }
158 const MachineInstr* getMachineInstr () const { return minstr; }
159 const MachineOpCode getOpCode () const { return minstr->getOpCode(); }
160 int getLatency () const { return latency; }
161 unsigned getNumInEdges () const { return inEdges.size(); }
162 unsigned getNumOutEdges () const { return outEdges.size(); }
163 bool isDummyNode () const { return (minstr == NULL); }
164 MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
165 int getOrigIndexInBB() const { return origIndexInBB; }
170 iterator beginInEdges () { return inEdges.begin(); }
171 iterator endInEdges () { return inEdges.end(); }
172 iterator beginOutEdges () { return outEdges.begin(); }
173 iterator endOutEdges () { return outEdges.end(); }
175 const_iterator beginInEdges () const { return inEdges.begin(); }
176 const_iterator endInEdges () const { return inEdges.end(); }
177 const_iterator beginOutEdges () const { return outEdges.begin(); }
178 const_iterator endOutEdges () const { return outEdges.end(); }
184 friend std::ostream& operator<<(std::ostream& os, const SchedGraphNode& node);
186 void dump (int indent=0) const;
189 friend class SchedGraph; // give access for ctor and dtor
190 friend class SchedGraphEdge; // give access for adding edges
192 void addInEdge (SchedGraphEdge* edge);
193 void addOutEdge (SchedGraphEdge* edge);
195 void removeInEdge (const SchedGraphEdge* edge);
196 void removeOutEdge (const SchedGraphEdge* edge);
198 // disable default constructor and provide a ctor for single-block graphs
199 /*ctor*/ SchedGraphNode(); // DO NOT IMPLEMENT
200 /*ctor*/ SchedGraphNode (unsigned nodeId,
201 MachineBasicBlock *mbb,
203 const TargetMachine& Target);
204 /*dtor*/ ~SchedGraphNode ();
209 class SchedGraph : private hash_map<const MachineInstr*, SchedGraphNode*> {
210 MachineBasicBlock &MBB; // basic blocks for this graph
211 SchedGraphNode* graphRoot; // the root and leaf are not inserted
212 SchedGraphNode* graphLeaf; // in the hash_map (see getNumNodes())
214 typedef hash_map<const MachineInstr*, SchedGraphNode*> map_base;
215 SchedGraph(const SchedGraph &); // DO NOT IMPLEMENT
216 void operator=(const SchedGraph &); // DO NOT IMPLEMENT
218 using map_base::iterator;
219 using map_base::const_iterator;
225 MachineBasicBlock &getBasicBlock() const { return MBB; }
226 unsigned getNumNodes() const { return size()+2; }
227 SchedGraphNode* getRoot() const { return graphRoot; }
228 SchedGraphNode* getLeaf() const { return graphLeaf; }
230 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
231 const_iterator onePair = this->find(minstr);
232 return (onePair != this->end())? (*onePair).second : NULL;
236 // Delete nodes or edges from the graph.
238 void eraseNode (SchedGraphNode* node);
240 void eraseIncomingEdges (SchedGraphNode* node,
241 bool addDummyEdges = true);
243 void eraseOutgoingEdges (SchedGraphNode* node,
244 bool addDummyEdges = true);
246 void eraseIncidentEdges (SchedGraphNode* node,
247 bool addDummyEdges = true);
250 // Unordered iterators.
251 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
253 using map_base::begin;
257 // Ordered iterators.
258 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
260 // void postord_init();
261 // postorder_iterator postord_begin();
262 // postorder_iterator postord_end();
263 // const_postorder_iterator postord_begin() const;
264 // const_postorder_iterator postord_end() const;
272 friend class SchedGraphSet; // give access to ctor
274 // disable default constructor and provide a ctor for single-block graphs
275 /*ctor*/ SchedGraph (MachineBasicBlock &bb,
276 const TargetMachine& target);
277 /*dtor*/ ~SchedGraph ();
279 inline void noteGraphNodeForInstr (const MachineInstr* minstr,
280 SchedGraphNode* node)
282 assert((*this)[minstr] == NULL);
283 (*this)[minstr] = node;
289 void buildGraph (const TargetMachine& target);
291 void buildNodesForBB (const TargetMachine& target,
292 MachineBasicBlock &MBB,
293 std::vector<SchedGraphNode*>& memNV,
294 std::vector<SchedGraphNode*>& callNV,
295 RegToRefVecMap& regToRefVecMap,
296 ValueToDefVecMap& valueToDefVecMap);
298 void findDefUseInfoAtInstr (const TargetMachine& target,
299 SchedGraphNode* node,
300 std::vector<SchedGraphNode*>& memNV,
301 std::vector<SchedGraphNode*>& callNV,
302 RegToRefVecMap& regToRefVecMap,
303 ValueToDefVecMap& valueToDefVecMap);
305 void addEdgesForInstruction(const MachineInstr& minstr,
306 const ValueToDefVecMap& valueToDefVecMap,
307 const TargetMachine& target);
309 void addCDEdges (const TerminatorInst* term,
310 const TargetMachine& target);
312 void addMemEdges (const std::vector<SchedGraphNode*>& memNV,
313 const TargetMachine& target);
315 void addCallDepEdges (const std::vector<SchedGraphNode*>& callNV,
316 const TargetMachine& target);
318 void addMachineRegEdges (RegToRefVecMap& regToRefVecMap,
319 const TargetMachine& target);
321 void addEdgesForValue (SchedGraphNode* refNode,
322 const RefVec& defVec,
323 const Value* defValue,
325 bool refNodeIsDefAndUse,
326 const TargetMachine& target);
328 void addDummyEdges ();
332 class SchedGraphSet : private std::vector<SchedGraph*> {
334 const Function* method;
336 SchedGraphSet(const SchedGraphSet&); // DO NOT IMPLEMENT
337 void operator=(const SchedGraphSet&); // DO NOT IMPLEMENT
339 typedef std::vector<SchedGraph*> baseVector;
340 using baseVector::iterator;
341 using baseVector::const_iterator;
344 SchedGraphSet(const Function *F, const TargetMachine &TM);
348 using baseVector::begin;
349 using baseVector::end;
355 inline void addGraph(SchedGraph* graph) {
356 assert(graph != NULL);
357 this->push_back(graph);
361 void buildGraphsForMethod(const Function *F, const TargetMachine &TM);
365 //********************** Sched Graph Iterators *****************************/
367 // Ok to make it a template because it shd get instantiated at most twice:
368 // for <SchedGraphNode, SchedGraphNode::iterator> and
369 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
371 template <class _NodeType, class _EdgeType, class _EdgeIter>
372 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
376 typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
378 inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
380 inline bool operator==(const _Self& x) const { return oi == x.oi; }
381 inline bool operator!=(const _Self& x) const { return !operator==(x); }
383 // operator*() differs for pred or succ iterator
384 inline _NodeType* operator*() const { return (*oi)->getSrc(); }
385 inline _NodeType* operator->() const { return operator*(); }
387 inline _EdgeType* getEdge() const { return *(oi); }
389 inline _Self &operator++() { ++oi; return *this; } // Preincrement
390 inline _Self operator++(int) { // Postincrement
391 _Self tmp(*this); ++*this; return tmp;
394 inline _Self &operator--() { --oi; return *this; } // Predecrement
395 inline _Self operator--(int) { // Postdecrement
396 _Self tmp = *this; --*this; return tmp;
400 template <class _NodeType, class _EdgeType, class _EdgeIter>
401 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
405 typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
407 inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
409 inline bool operator==(const _Self& x) const { return oi == x.oi; }
410 inline bool operator!=(const _Self& x) const { return !operator==(x); }
412 inline _NodeType* operator*() const { return (*oi)->getSink(); }
413 inline _NodeType* operator->() const { return operator*(); }
415 inline _EdgeType* getEdge() const { return *(oi); }
417 inline _Self &operator++() { ++oi; return *this; } // Preincrement
418 inline _Self operator++(int) { // Postincrement
419 _Self tmp(*this); ++*this; return tmp;
422 inline _Self &operator--() { --oi; return *this; } // Predecrement
423 inline _Self operator--(int) { // Postdecrement
424 _Self tmp = *this; --*this; return tmp;
430 // sg_pred_const_iterator
432 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
434 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
435 sg_pred_const_iterator;
437 inline sg_pred_iterator pred_begin( SchedGraphNode *N) {
438 return sg_pred_iterator(N->beginInEdges());
440 inline sg_pred_iterator pred_end( SchedGraphNode *N) {
441 return sg_pred_iterator(N->endInEdges());
443 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
444 return sg_pred_const_iterator(N->beginInEdges());
446 inline sg_pred_const_iterator pred_end( const SchedGraphNode *N) {
447 return sg_pred_const_iterator(N->endInEdges());
453 // sg_succ_const_iterator
455 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
457 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
458 sg_succ_const_iterator;
460 inline sg_succ_iterator succ_begin( SchedGraphNode *N) {
461 return sg_succ_iterator(N->beginOutEdges());
463 inline sg_succ_iterator succ_end( SchedGraphNode *N) {
464 return sg_succ_iterator(N->endOutEdges());
466 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
467 return sg_succ_const_iterator(N->beginOutEdges());
469 inline sg_succ_const_iterator succ_end( const SchedGraphNode *N) {
470 return sg_succ_const_iterator(N->endOutEdges());
473 // Provide specializations of GraphTraits to be able to use graph iterators on
474 // the scheduling graph!
476 template <> struct GraphTraits<SchedGraph*> {
477 typedef SchedGraphNode NodeType;
478 typedef sg_succ_iterator ChildIteratorType;
480 static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
481 static inline ChildIteratorType child_begin(NodeType *N) {
482 return succ_begin(N);
484 static inline ChildIteratorType child_end(NodeType *N) {
489 template <> struct GraphTraits<const SchedGraph*> {
490 typedef const SchedGraphNode NodeType;
491 typedef sg_succ_const_iterator ChildIteratorType;
493 static inline NodeType *getEntryNode(const SchedGraph *SG) {
494 return SG->getRoot();
496 static inline ChildIteratorType child_begin(NodeType *N) {
497 return succ_begin(N);
499 static inline ChildIteratorType child_end(NodeType *N) {
505 std::ostream &operator<<(std::ostream& os, const SchedGraphEdge& edge);
506 std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node);