1 //===-- SchedGraphCommon.h - Scheduling Base Graph --------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // A common graph class that is based on the SSA graph. It includes
11 // extra dependencies that are caused by machine resources.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
16 #define LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
18 #include "llvm/Value.h"
19 #include "llvm/ADT/iterator"
20 #include "llvm/Support/Streams.h"
28 /******************** Exported Data Types and Constants ********************/
30 typedef int ResourceId;
31 const ResourceId InvalidRID = -1;
32 const ResourceId MachineCCRegsRID = -2; // use +ve numbers for actual regs
33 const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
34 const ResourceId MachineFPRegsRID = -4; // use +ve numbers for actual regs
37 //*********************** Public Class Declarations ************************/
38 class SchedGraphNodeCommon {
41 std::vector<SchedGraphEdge*> inEdges;
42 std::vector<SchedGraphEdge*> outEdges;
44 int origIndexInBB; // original position of instr in BB
47 typedef std::vector<SchedGraphEdge*>::iterator iterator;
48 typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator;
49 typedef std::vector<SchedGraphEdge*>::reverse_iterator reverse_iterator;
50 typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
53 unsigned getNodeId() const { return ID; }
54 int getLatency() const { return latency; }
55 unsigned getNumInEdges() const { return inEdges.size(); }
56 unsigned getNumOutEdges() const { return outEdges.size(); }
57 int getOrigIndexInBB() const { return origIndexInBB; }
60 iterator beginInEdges() { return inEdges.begin(); }
61 iterator endInEdges() { return inEdges.end(); }
62 iterator beginOutEdges() { return outEdges.begin(); }
63 iterator endOutEdges() { return outEdges.end(); }
65 const_iterator beginInEdges() const { return inEdges.begin(); }
66 const_iterator endInEdges() const { return inEdges.end(); }
67 const_iterator beginOutEdges() const { return outEdges.begin(); }
68 const_iterator endOutEdges() const { return outEdges.end(); }
70 void dump(int indent=0) const;
73 void print(OStream &os) const {
74 if (os.stream()) print(*os.stream());
76 virtual void print(std::ostream &os) const = 0;
79 friend class SchedGraphCommon;
80 friend class SchedGraphEdge; // give access for adding edges
83 // disable default constructor and provide a ctor for single-block graphs
84 SchedGraphNodeCommon(); // DO NOT IMPLEMENT
86 inline SchedGraphNodeCommon(unsigned Id, int index, int late=0) : ID(Id), latency(late), origIndexInBB(index) {}
88 virtual ~SchedGraphNodeCommon();
90 //Functions to add and remove edges
91 inline void addInEdge(SchedGraphEdge* edge) { inEdges.push_back(edge); }
92 inline void addOutEdge(SchedGraphEdge* edge) { outEdges.push_back(edge); }
93 void removeInEdge(const SchedGraphEdge* edge);
94 void removeOutEdge(const SchedGraphEdge* edge);
98 // ostream << operator for SchedGraphNode class
99 inline OStream &operator<<(OStream &os,
100 const SchedGraphNodeCommon &node) {
104 inline std::ostream &operator<<(std::ostream &os,
105 const SchedGraphNodeCommon &node) {
111 // SchedGraphEdge - Edge class to represent dependencies
113 class SchedGraphEdge {
115 enum SchedGraphEdgeDepType {
116 CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
118 enum DataDepOrderType {
119 TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
123 SchedGraphNodeCommon* src;
124 SchedGraphNodeCommon* sink;
125 SchedGraphEdgeDepType depType;
126 unsigned int depOrderType;
127 int minDelay; // cached latency (assumes fixed target arch)
133 ResourceId resourceId;
137 // For all constructors, if minDelay is unspecified, minDelay is
138 // set to _src->getLatency().
140 // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
141 SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
142 SchedGraphEdgeDepType _depType, unsigned int _depOrderType,
145 // constructor for explicit value dependence (may be true/anti/output)
146 SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
147 const Value* _val, unsigned int _depOrderType,
150 // constructor for machine register dependence
151 SchedGraphEdge(SchedGraphNodeCommon* _src,SchedGraphNodeCommon* _sink,
152 unsigned int _regNum, unsigned int _depOrderType,
155 // constructor for any other machine resource dependences.
156 // DataDepOrderType is always NonDataDep. It it not an argument to
157 // avoid overloading ambiguity with previous constructor.
158 SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
159 ResourceId _resourceId, int _minDelay = -1);
163 SchedGraphNodeCommon* getSrc() const { return src; }
164 SchedGraphNodeCommon* getSink() const { return sink; }
165 int getMinDelay() const { return minDelay; }
166 SchedGraphEdgeDepType getDepType() const { return depType; }
167 unsigned int getDepOrderType() const { return depOrderType; }
169 const Value* getValue() const {
170 assert(depType == ValueDep); return val;
173 int getMachineReg() const {
174 assert(depType == MachineRegister); return machineRegNum;
177 int getResourceId() const {
178 assert(depType == MachineResource); return resourceId;
181 void setIteDiff(int _iteDiff) {
191 void print(OStream &os) const {
192 if (os.stream()) print(*os.stream());
194 void print(std::ostream &os) const;
195 void dump(int indent=0) const;
198 // disable default ctor
199 SchedGraphEdge(); // DO NOT IMPLEMENT
202 // ostream << operator for SchedGraphNode class
203 inline OStream &operator<<(OStream &os, const SchedGraphEdge &edge) {
207 inline std::ostream &operator<<(std::ostream &os, const SchedGraphEdge &edge) {
212 class SchedGraphCommon {
215 SchedGraphNodeCommon* graphRoot; // the root and leaf are not inserted
216 SchedGraphNodeCommon* graphLeaf; // in the hash_map (see getNumNodes())
222 SchedGraphNodeCommon* getRoot() const { return graphRoot; }
223 SchedGraphNodeCommon* getLeaf() const { return graphLeaf; }
226 // Delete nodes or edges from the graph.
228 void eraseNode(SchedGraphNodeCommon* node);
229 void eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
230 void eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
231 void eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
233 SchedGraphCommon() {}
238 //********************** Sched Graph Iterators *****************************/
240 // Ok to make it a template because it shd get instantiated at most twice:
241 // for <SchedGraphNode, SchedGraphNode::iterator> and
242 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
244 template <class _NodeType, class _EdgeType, class _EdgeIter>
245 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
249 typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
251 inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
253 inline bool operator==(const _Self& x) const { return oi == x.oi; }
254 inline bool operator!=(const _Self& x) const { return !operator==(x); }
256 // operator*() differs for pred or succ iterator
257 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
258 inline _NodeType* operator->() const { return operator*(); }
260 inline _EdgeType* getEdge() const { return *(oi); }
262 inline _Self &operator++() { ++oi; return *this; } // Preincrement
263 inline _Self operator++(int) { // Postincrement
264 _Self tmp(*this); ++*this; return tmp;
267 inline _Self &operator--() { --oi; return *this; } // Predecrement
268 inline _Self operator--(int) { // Postdecrement
269 _Self tmp = *this; --*this; return tmp;
273 template <class _NodeType, class _EdgeType, class _EdgeIter>
274 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
278 typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
280 inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
282 inline bool operator==(const _Self& x) const { return oi == x.oi; }
283 inline bool operator!=(const _Self& x) const { return !operator==(x); }
285 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
286 inline _NodeType* operator->() const { return operator*(); }
288 inline _EdgeType* getEdge() const { return *(oi); }
290 inline _Self &operator++() { ++oi; return *this; } // Preincrement
291 inline _Self operator++(int) { // Postincrement
292 _Self tmp(*this); ++*this; return tmp;
295 inline _Self &operator--() { --oi; return *this; } // Predecrement
296 inline _Self operator--(int) { // Postdecrement
297 _Self tmp = *this; --*this; return tmp;
300 } // End llvm namespace