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/CodeGen/MachineInstr.h"
23 #include "Support/HashExtras.h"
24 #include "Support/GraphTraits.h"
36 class ValueToDefVecMap;
39 class MachineCodeForBasicBlock;
42 /******************** Exported Data Types and Constants ********************/
44 typedef int ResourceId;
45 const ResourceId InvalidRID = -1;
46 const ResourceId MachineCCRegsRID = -2; // use +ve numbers for actual regs
47 const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
48 const ResourceId MachineFPRegsRID = -4; // use +ve numbers for actual regs
51 //*********************** Public Class Declarations ************************/
53 class SchedGraphEdge: public NonCopyable {
55 enum SchedGraphEdgeDepType {
56 CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
58 enum DataDepOrderType {
59 TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
65 SchedGraphEdgeDepType depType;
66 unsigned int depOrderType;
67 int minDelay; // cached latency (assumes fixed target arch)
72 ResourceId resourceId;
76 // For all constructors, if minDelay is unspecified, minDelay is
77 // set to _src->getLatency().
78 // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
79 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
80 SchedGraphNode* _sink,
81 SchedGraphEdgeDepType _depType,
82 unsigned int _depOrderType,
85 // constructor for explicit value dependence (may be true/anti/output)
86 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
87 SchedGraphNode* _sink,
89 unsigned int _depOrderType,
92 // constructor for machine register dependence
93 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
94 SchedGraphNode* _sink,
96 unsigned int _depOrderType,
99 // constructor for any other machine resource dependences.
100 // DataDepOrderType is always NonDataDep. It it not an argument to
101 // avoid overloading ambiguity with previous constructor.
102 /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
103 SchedGraphNode* _sink,
104 ResourceId _resourceId,
107 /*dtor*/ ~SchedGraphEdge();
109 SchedGraphNode* getSrc () const { return src; }
110 SchedGraphNode* getSink () const { return sink; }
111 int getMinDelay () const { return minDelay; }
112 SchedGraphEdgeDepType getDepType () const { return depType; }
114 const Value* getValue () const {
115 assert(depType == ValueDep); return val;
117 int getMachineReg () const {
118 assert(depType == MachineRegister); return machineRegNum;
120 int getResourceId () const {
121 assert(depType == MachineResource); return resourceId;
128 friend std::ostream& operator<<(std::ostream& os, const SchedGraphEdge& edge);
130 void dump (int indent=0) const;
133 // disable default ctor
134 /*ctor*/ SchedGraphEdge(); // DO NOT IMPLEMENT
139 class SchedGraphNode: public NonCopyable {
142 const BasicBlock* bb;
143 const MachineInstr* minstr;
144 std::vector<SchedGraphEdge*> inEdges;
145 std::vector<SchedGraphEdge*> outEdges;
146 int origIndexInBB; // original position of machine instr in BB
150 typedef std::vector<SchedGraphEdge*>:: iterator iterator;
151 typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator;
152 typedef std::vector<SchedGraphEdge*>:: reverse_iterator reverse_iterator;
153 typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
159 unsigned int getNodeId () const { return nodeId; }
160 const MachineInstr* getMachineInstr () const { return minstr; }
161 const MachineOpCode getOpCode () const { return minstr->getOpCode();}
162 int getLatency () const { return latency; }
163 unsigned int getNumInEdges () const { return inEdges.size(); }
164 unsigned int getNumOutEdges () const { return outEdges.size(); }
165 bool isDummyNode () const { return (minstr == NULL); }
166 const BasicBlock* getBB () const { return bb; }
167 int getOrigIndexInBB() const { return origIndexInBB; }
172 iterator beginInEdges () { return inEdges.begin(); }
173 iterator endInEdges () { return inEdges.end(); }
174 iterator beginOutEdges () { return outEdges.begin(); }
175 iterator endOutEdges () { return outEdges.end(); }
177 const_iterator beginInEdges () const { return inEdges.begin(); }
178 const_iterator endInEdges () const { return inEdges.end(); }
179 const_iterator beginOutEdges () const { return outEdges.begin(); }
180 const_iterator endOutEdges () const { return outEdges.end(); }
186 friend std::ostream& operator<<(std::ostream& os, const SchedGraphNode& node);
188 void dump (int indent=0) const;
191 friend class SchedGraph; // give access for ctor and dtor
192 friend class SchedGraphEdge; // give access for adding edges
194 void addInEdge (SchedGraphEdge* edge);
195 void addOutEdge (SchedGraphEdge* edge);
197 void removeInEdge (const SchedGraphEdge* edge);
198 void removeOutEdge (const SchedGraphEdge* edge);
200 // disable default constructor and provide a ctor for single-block graphs
201 /*ctor*/ SchedGraphNode(); // DO NOT IMPLEMENT
202 /*ctor*/ SchedGraphNode (unsigned int _nodeId,
203 const BasicBlock* _bb,
204 const MachineInstr* _minstr,
206 const TargetMachine& _target);
207 /*dtor*/ ~SchedGraphNode ();
214 private hash_map<const MachineInstr*, SchedGraphNode*>
217 std::vector<const BasicBlock*> bbVec; // basic blocks included in the graph
218 SchedGraphNode* graphRoot; // the root and leaf are not inserted
219 SchedGraphNode* graphLeaf; // in the hash_map (see getNumNodes())
221 typedef hash_map<const MachineInstr*, SchedGraphNode*> map_base;
223 using map_base::iterator;
224 using map_base::const_iterator;
230 const std::vector<const BasicBlock*>& getBasicBlocks() const { return bbVec; }
231 const unsigned int getNumNodes() const { return size()+2; }
232 SchedGraphNode* getRoot() const { return graphRoot; }
233 SchedGraphNode* getLeaf() const { return graphLeaf; }
235 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
236 const_iterator onePair = this->find(minstr);
237 return (onePair != this->end())? (*onePair).second : NULL;
241 // Delete nodes or edges from the graph.
243 void eraseNode (SchedGraphNode* node);
245 void eraseIncomingEdges (SchedGraphNode* node,
246 bool addDummyEdges = true);
248 void eraseOutgoingEdges (SchedGraphNode* node,
249 bool addDummyEdges = true);
251 void eraseIncidentEdges (SchedGraphNode* node,
252 bool addDummyEdges = true);
255 // Unordered iterators.
256 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
258 using map_base::begin;
262 // Ordered iterators.
263 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
265 // void postord_init();
266 // postorder_iterator postord_begin();
267 // postorder_iterator postord_end();
268 // const_postorder_iterator postord_begin() const;
269 // const_postorder_iterator postord_end() const;
277 friend class SchedGraphSet; // give access to ctor
279 // disable default constructor and provide a ctor for single-block graphs
280 /*ctor*/ SchedGraph (); // DO NOT IMPLEMENT
281 /*ctor*/ SchedGraph (const BasicBlock* bb,
282 const TargetMachine& target);
283 /*dtor*/ ~SchedGraph ();
285 inline void noteGraphNodeForInstr (const MachineInstr* minstr,
286 SchedGraphNode* node)
288 assert((*this)[minstr] == NULL);
289 (*this)[minstr] = node;
295 void buildGraph (const TargetMachine& target);
297 void buildNodesforBB (const TargetMachine& target,
298 const BasicBlock* bb,
299 std::vector<SchedGraphNode*>& memNod,
300 RegToRefVecMap& regToRefVecMap,
301 ValueToDefVecMap& valueToDefVecMap);
303 void findDefUseInfoAtInstr (const TargetMachine& target,
304 SchedGraphNode* node,
305 std::vector<SchedGraphNode*>& memNode,
306 RegToRefVecMap& regToRefVecMap,
307 ValueToDefVecMap& valueToDefVecMap);
309 void addEdgesForInstruction(const MachineInstr& minstr,
310 const ValueToDefVecMap& valueToDefVecMap,
311 const TargetMachine& target);
313 void addCDEdges (const TerminatorInst* term,
314 const TargetMachine& target);
316 void addMemEdges (const std::vector<SchedGraphNode*>& memNod,
317 const TargetMachine& target);
319 void addCallCCEdges (const std::vector<SchedGraphNode*>& memNod,
320 MachineCodeForBasicBlock& bbMvec,
321 const TargetMachine& target);
323 void addMachineRegEdges (RegToRefVecMap& regToRefVecMap,
324 const TargetMachine& target);
326 void addEdgesForValue (SchedGraphNode* refNode,
327 const RefVec& defVec,
328 const Value* defValue,
330 bool refNodeIsDefAndUse,
331 const TargetMachine& target);
333 void addDummyEdges ();
337 class SchedGraphSet :
339 private std::vector<SchedGraph*>
342 const Function* method;
345 typedef std::vector<SchedGraph*> baseVector;
346 using baseVector::iterator;
347 using baseVector::const_iterator;
350 /*ctor*/ SchedGraphSet (const Function * function,
351 const TargetMachine& target);
352 /*dtor*/ ~SchedGraphSet ();
355 using baseVector::begin;
356 using baseVector::end;
362 inline void addGraph(SchedGraph* graph) {
363 assert(graph != NULL);
364 this->push_back(graph);
368 void buildGraphsForMethod (const Function *F,
369 const TargetMachine& target);
373 //********************** Sched Graph Iterators *****************************/
375 // Ok to make it a template because it shd get instantiated at most twice:
376 // for <SchedGraphNode, SchedGraphNode::iterator> and
377 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
379 template <class _NodeType, class _EdgeType, class _EdgeIter>
380 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
384 typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
386 inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
388 inline bool operator==(const _Self& x) const { return oi == x.oi; }
389 inline bool operator!=(const _Self& x) const { return !operator==(x); }
391 // operator*() differs for pred or succ iterator
392 inline _NodeType* operator*() const { return (*oi)->getSrc(); }
393 inline _NodeType* operator->() const { return operator*(); }
395 inline _EdgeType* getEdge() const { return *(oi); }
397 inline _Self &operator++() { ++oi; return *this; } // Preincrement
398 inline _Self operator++(int) { // Postincrement
399 _Self tmp(*this); ++*this; return tmp;
402 inline _Self &operator--() { --oi; return *this; } // Predecrement
403 inline _Self operator--(int) { // Postdecrement
404 _Self tmp = *this; --*this; return tmp;
408 template <class _NodeType, class _EdgeType, class _EdgeIter>
409 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
413 typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
415 inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
417 inline bool operator==(const _Self& x) const { return oi == x.oi; }
418 inline bool operator!=(const _Self& x) const { return !operator==(x); }
420 inline _NodeType* operator*() const { return (*oi)->getSink(); }
421 inline _NodeType* operator->() const { return operator*(); }
423 inline _EdgeType* getEdge() const { return *(oi); }
425 inline _Self &operator++() { ++oi; return *this; } // Preincrement
426 inline _Self operator++(int) { // Postincrement
427 _Self tmp(*this); ++*this; return tmp;
430 inline _Self &operator--() { --oi; return *this; } // Predecrement
431 inline _Self operator--(int) { // Postdecrement
432 _Self tmp = *this; --*this; return tmp;
438 // sg_pred_const_iterator
440 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
442 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
443 sg_pred_const_iterator;
445 inline sg_pred_iterator pred_begin( SchedGraphNode *N) {
446 return sg_pred_iterator(N->beginInEdges());
448 inline sg_pred_iterator pred_end( SchedGraphNode *N) {
449 return sg_pred_iterator(N->endInEdges());
451 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
452 return sg_pred_const_iterator(N->beginInEdges());
454 inline sg_pred_const_iterator pred_end( const SchedGraphNode *N) {
455 return sg_pred_const_iterator(N->endInEdges());
461 // sg_succ_const_iterator
463 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
465 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
466 sg_succ_const_iterator;
468 inline sg_succ_iterator succ_begin( SchedGraphNode *N) {
469 return sg_succ_iterator(N->beginOutEdges());
471 inline sg_succ_iterator succ_end( SchedGraphNode *N) {
472 return sg_succ_iterator(N->endOutEdges());
474 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
475 return sg_succ_const_iterator(N->beginOutEdges());
477 inline sg_succ_const_iterator succ_end( const SchedGraphNode *N) {
478 return sg_succ_const_iterator(N->endOutEdges());
481 // Provide specializations of GraphTraits to be able to use graph iterators on
482 // the scheduling graph!
484 template <> struct GraphTraits<SchedGraph*> {
485 typedef SchedGraphNode NodeType;
486 typedef sg_succ_iterator ChildIteratorType;
488 static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
489 static inline ChildIteratorType child_begin(NodeType *N) {
490 return succ_begin(N);
492 static inline ChildIteratorType child_end(NodeType *N) {
497 template <> struct GraphTraits<const SchedGraph*> {
498 typedef const SchedGraphNode NodeType;
499 typedef sg_succ_const_iterator ChildIteratorType;
501 static inline NodeType *getEntryNode(const SchedGraph *SG) {
502 return SG->getRoot();
504 static inline ChildIteratorType child_begin(NodeType *N) {
505 return succ_begin(N);
507 static inline ChildIteratorType child_end(NodeType *N) {
513 std::ostream &operator<<(std::ostream& os, const SchedGraphEdge& edge);
514 std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node);