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"
25 #include "llvm/Target/MachineInstrInfo.h"
26 #include "llvm/CodeGen/MachineInstr.h"
39 class ValueToDefVecMap;
42 class MachineCodeForBasicBlock;
45 /******************** Exported Data Types and Constants ********************/
47 typedef int ResourceId;
48 const ResourceId InvalidRID = -1;
49 const ResourceId MachineCCRegsRID = -2; // use +ve numbers for actual regs
50 const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
51 const ResourceId MachineFPRegsRID = -4; // use +ve numbers for actual regs
54 //*********************** Public Class Declarations ************************/
56 class SchedGraphEdge: public NonCopyable {
58 enum SchedGraphEdgeDepType {
59 CtrlDep, MemoryDep, DefUseDep, MachineRegister, MachineResource
61 enum DataDepOrderType {
62 TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
68 SchedGraphEdgeDepType depType;
69 unsigned int depOrderType;
70 int minDelay; // cached latency (assumes fixed target arch)
75 ResourceId resourceId;
79 // For all constructors, if minDelay is unspecified, minDelay is
80 // set to _src->getLatency().
81 // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
82 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
83 SchedGraphNode* _sink,
84 SchedGraphEdgeDepType _depType,
85 unsigned int _depOrderType =TrueDep,
88 // constructor for explicit def-use or memory def-use edge
89 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
90 SchedGraphNode* _sink,
92 unsigned int _depOrderType =TrueDep,
95 // constructor for machine register dependence
96 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
97 SchedGraphNode* _sink,
99 unsigned int _depOrderType =TrueDep,
102 // constructor for any other machine resource dependences.
103 // DataDepOrderType is always NonDataDep. It it not an argument to
104 // avoid overloading ambiguity with previous constructor.
105 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
106 SchedGraphNode* _sink,
107 ResourceId _resourceId,
110 /*dtor*/ ~SchedGraphEdge();
112 SchedGraphNode* getSrc () const { return src; }
113 SchedGraphNode* getSink () const { return sink; }
114 int getMinDelay () const { return minDelay; }
115 SchedGraphEdgeDepType getDepType () const { return depType; }
117 const Value* getValue () const {
118 assert(depType == DefUseDep || depType == MemoryDep); return val;
120 int getMachineReg () const {
121 assert(depType == MachineRegister); return machineRegNum;
123 int getResourceId () const {
124 assert(depType == MachineResource); return resourceId;
131 friend ostream& operator<<(ostream& os, const SchedGraphEdge& edge);
133 void dump (int indent=0) const;
136 // disable default ctor
137 /*ctor*/ SchedGraphEdge(); // DO NOT IMPLEMENT
142 class SchedGraphNode: public NonCopyable {
145 const Instruction* instr;
146 const MachineInstr* minstr;
147 vector<SchedGraphEdge*> inEdges;
148 vector<SchedGraphEdge*> outEdges;
149 int origIndexInBB; // original position of machine instr in BB
153 typedef vector<SchedGraphEdge*>:: iterator iterator;
154 typedef vector<SchedGraphEdge*>::const_iterator const_iterator;
155 typedef vector<SchedGraphEdge*>:: reverse_iterator reverse_iterator;
156 typedef vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
162 unsigned int getNodeId () const { return nodeId; }
163 const Instruction* getInstr () const { return instr; }
164 const MachineInstr* getMachineInstr () const { return minstr; }
165 const MachineOpCode getOpCode () const { return minstr->getOpCode();}
166 int getLatency () const { return latency; }
167 unsigned int getNumInEdges () const { return inEdges.size(); }
168 unsigned int getNumOutEdges () const { return outEdges.size(); }
169 bool isDummyNode () const { return (minstr == NULL); }
170 int getOrigIndexInBB() const { return origIndexInBB; }
175 iterator beginInEdges () { return inEdges.begin(); }
176 iterator endInEdges () { return inEdges.end(); }
177 iterator beginOutEdges () { return outEdges.begin(); }
178 iterator endOutEdges () { return outEdges.end(); }
180 const_iterator beginInEdges () const { return inEdges.begin(); }
181 const_iterator endInEdges () const { return inEdges.end(); }
182 const_iterator beginOutEdges () const { return outEdges.begin(); }
183 const_iterator endOutEdges () const { return outEdges.end(); }
189 friend ostream& operator<<(ostream& os, const SchedGraphNode& node);
191 void dump (int indent=0) const;
194 friend class SchedGraph; // give access for ctor and dtor
195 friend class SchedGraphEdge; // give access for adding edges
197 void addInEdge (SchedGraphEdge* edge);
198 void addOutEdge (SchedGraphEdge* edge);
200 void removeInEdge (const SchedGraphEdge* edge);
201 void removeOutEdge (const SchedGraphEdge* edge);
203 // disable default constructor and provide a ctor for single-block graphs
204 /*ctor*/ SchedGraphNode(); // DO NOT IMPLEMENT
205 /*ctor*/ SchedGraphNode (unsigned int _nodeId,
206 const Instruction* _instr,
207 const MachineInstr* _minstr,
209 const TargetMachine& _target);
210 /*dtor*/ ~SchedGraphNode ();
217 private hash_map<const MachineInstr*, SchedGraphNode*>
220 vector<const BasicBlock*> bbVec; // basic blocks included in the graph
221 SchedGraphNode* graphRoot; // the root and leaf are not inserted
222 SchedGraphNode* graphLeaf; // in the hash_map (see getNumNodes())
225 typedef hash_map<const MachineInstr*, SchedGraphNode*>::iterator iterator;
226 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
232 const vector<const BasicBlock*>& getBasicBlocks() const { return bbVec; }
233 const unsigned int getNumNodes() const { return size()+2; }
234 SchedGraphNode* getRoot() const { return graphRoot; }
235 SchedGraphNode* getLeaf() const { return graphLeaf; }
237 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
238 const_iterator onePair = this->find(minstr);
239 return (onePair != this->end())? (*onePair).second : NULL;
243 // Delete nodes or edges from the graph.
245 void eraseNode (SchedGraphNode* node);
247 void eraseIncomingEdges (SchedGraphNode* node,
248 bool addDummyEdges = true);
250 void eraseOutgoingEdges (SchedGraphNode* node,
251 bool addDummyEdges = true);
253 void eraseIncidentEdges (SchedGraphNode* node,
254 bool addDummyEdges = true);
257 // Unordered iterators.
258 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
261 return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
264 return hash_map<const MachineInstr*, SchedGraphNode*>::end();
266 const_iterator begin() const {
267 return hash_map<const MachineInstr*, SchedGraphNode*>::begin();
269 const_iterator end() const {
270 return hash_map<const MachineInstr*, SchedGraphNode*>::end();
274 // Ordered iterators.
275 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
277 // void postord_init();
278 // postorder_iterator postord_begin();
279 // postorder_iterator postord_end();
280 // const_postorder_iterator postord_begin() const;
281 // const_postorder_iterator postord_end() const;
289 friend class SchedGraphSet; // give access to ctor
291 // disable default constructor and provide a ctor for single-block graphs
292 /*ctor*/ SchedGraph (); // DO NOT IMPLEMENT
293 /*ctor*/ SchedGraph (const BasicBlock* bb,
294 const TargetMachine& target);
295 /*dtor*/ ~SchedGraph ();
297 inline void noteGraphNodeForInstr (const MachineInstr* minstr,
298 SchedGraphNode* node)
300 assert((*this)[minstr] == NULL);
301 (*this)[minstr] = node;
307 void buildGraph (const TargetMachine& target);
309 void buildNodesforBB (const TargetMachine& target,
310 const BasicBlock* bb,
311 vector<SchedGraphNode*>& memNodeVec,
312 RegToRefVecMap& regToRefVecMap,
313 ValueToDefVecMap& valueToDefVecMap);
315 void findDefUseInfoAtInstr (const TargetMachine& target,
316 SchedGraphNode* node,
317 vector<SchedGraphNode*>& memNodeVec,
318 RegToRefVecMap& regToRefVecMap,
319 ValueToDefVecMap& valueToDefVecMap);
321 void addEdgesForInstruction(const MachineInstr& minstr,
322 const ValueToDefVecMap& valueToDefVecMap,
323 const TargetMachine& target);
325 void addCDEdges (const TerminatorInst* term,
326 const TargetMachine& target);
328 void addMemEdges (const vector<SchedGraphNode*>& memNodeVec,
329 const TargetMachine& target);
331 void addCallCCEdges (const vector<SchedGraphNode*>& memNodeVec,
332 MachineCodeForBasicBlock& bbMvec,
333 const TargetMachine& target);
335 void addMachineRegEdges (RegToRefVecMap& regToRefVecMap,
336 const TargetMachine& target);
338 void addSSAEdge (SchedGraphNode* node,
339 const RefVec& defVec,
340 const Value* defValue,
341 const TargetMachine& target);
343 void addNonSSAEdgesForValue (const Instruction* instr,
344 const TargetMachine& target);
346 void addDummyEdges ();
350 class SchedGraphSet :
352 private hash_map<const BasicBlock*, SchedGraph*>
355 const Method* method;
358 typedef hash_map<const BasicBlock*, SchedGraph*>::iterator iterator;
359 typedef hash_map<const BasicBlock*, SchedGraph*>::const_iterator const_iterator;
362 /*ctor*/ SchedGraphSet (const Method* _method,
363 const TargetMachine& target);
364 /*dtor*/ ~SchedGraphSet ();
369 SchedGraph* getGraphForBasicBlock (const BasicBlock* bb) const {
370 const_iterator onePair = this->find(bb);
371 return (onePair != this->end())? (*onePair).second : NULL;
378 return hash_map<const BasicBlock*, SchedGraph*>::begin();
381 return hash_map<const BasicBlock*, SchedGraph*>::end();
383 const_iterator begin() const {
384 return hash_map<const BasicBlock*, SchedGraph*>::begin();
386 const_iterator end() const {
387 return hash_map<const BasicBlock*, SchedGraph*>::end();
396 inline void noteGraphForBlock(const BasicBlock* bb, SchedGraph* graph) {
397 assert((*this)[bb] == NULL);
404 void buildGraphsForMethod (const Method *method,
405 const TargetMachine& target);
409 //********************** Sched Graph Iterators *****************************/
411 // Ok to make it a template because it shd get instantiated at most twice:
412 // for <SchedGraphNode, SchedGraphNode::iterator> and
413 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
415 template <class _NodeType, class _EdgeType, class _EdgeIter>
416 class PredIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
420 typedef PredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
422 inline PredIterator(_EdgeIter startEdge) : oi(startEdge) {}
424 inline bool operator==(const _Self& x) const { return oi == x.oi; }
425 inline bool operator!=(const _Self& x) const { return !operator==(x); }
427 // operator*() differs for pred or succ iterator
428 inline _NodeType* operator*() const { return (*oi)->getSrc(); }
429 inline _NodeType* operator->() const { return operator*(); }
431 inline _EdgeType* getEdge() const { return *(oi); }
433 inline _Self &operator++() { ++oi; return *this; } // Preincrement
434 inline _Self operator++(int) { // Postincrement
435 _Self tmp(*this); ++*this; return tmp;
438 inline _Self &operator--() { --oi; return *this; } // Predecrement
439 inline _Self operator--(int) { // Postdecrement
440 _Self tmp = *this; --*this; return tmp;
444 template <class _NodeType, class _EdgeType, class _EdgeIter>
445 class SuccIterator: public std::bidirectional_iterator<_NodeType, ptrdiff_t> {
449 typedef SuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
451 inline SuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
453 inline bool operator==(const _Self& x) const { return oi == x.oi; }
454 inline bool operator!=(const _Self& x) const { return !operator==(x); }
456 inline _NodeType* operator*() const { return (*oi)->getSink(); }
457 inline _NodeType* operator->() const { return operator*(); }
459 inline _EdgeType* getEdge() const { return *(oi); }
461 inline _Self &operator++() { ++oi; return *this; } // Preincrement
462 inline _Self operator++(int) { // Postincrement
463 _Self tmp(*this); ++*this; return tmp;
466 inline _Self &operator--() { --oi; return *this; } // Predecrement
467 inline _Self operator--(int) { // Postdecrement
468 _Self tmp = *this; --*this; return tmp;
474 // sg_pred_const_iterator
476 typedef PredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
478 typedef PredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
479 sg_pred_const_iterator;
481 inline sg_pred_iterator pred_begin( SchedGraphNode *N) {
482 return sg_pred_iterator(N->beginInEdges());
484 inline sg_pred_iterator pred_end( SchedGraphNode *N) {
485 return sg_pred_iterator(N->endInEdges());
487 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
488 return sg_pred_const_iterator(N->beginInEdges());
490 inline sg_pred_const_iterator pred_end( const SchedGraphNode *N) {
491 return sg_pred_const_iterator(N->endInEdges());
497 // sg_succ_const_iterator
499 typedef SuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
501 typedef SuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
502 sg_succ_const_iterator;
504 inline sg_succ_iterator succ_begin( SchedGraphNode *N) {
505 return sg_succ_iterator(N->beginOutEdges());
507 inline sg_succ_iterator succ_end( SchedGraphNode *N) {
508 return sg_succ_iterator(N->endOutEdges());
510 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
511 return sg_succ_const_iterator(N->beginOutEdges());
513 inline sg_succ_const_iterator succ_end( const SchedGraphNode *N) {
514 return sg_succ_const_iterator(N->endOutEdges());
517 // Provide specializations of GraphTraits to be able to use graph iterators on
518 // the scheduling graph!
520 template <> struct GraphTraits<SchedGraph*> {
521 typedef SchedGraphNode NodeType;
522 typedef sg_succ_iterator ChildIteratorType;
524 static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
525 static inline ChildIteratorType child_begin(NodeType *N) {
526 return succ_begin(N);
528 static inline ChildIteratorType child_end(NodeType *N) {
533 template <> struct GraphTraits<const SchedGraph*> {
534 typedef const SchedGraphNode NodeType;
535 typedef sg_succ_const_iterator ChildIteratorType;
537 static inline NodeType *getEntryNode(const SchedGraph *SG) {
538 return SG->getRoot();
540 static inline ChildIteratorType child_begin(NodeType *N) {
541 return succ_begin(N);
543 static inline ChildIteratorType child_end(NodeType *N) {
549 //************************ External Functions *****************************/
552 ostream& operator<<(ostream& os, const SchedGraphEdge& edge);
554 ostream& operator<<(ostream& os, const SchedGraphNode& node);
557 /***************************************************************************/