1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
|
//===-- SchedGraphCommon.h - Scheduling Base Graph ---------------*- C++ -*---=//
//
// A common graph class that is based on the SSA graph. It includes
// extra dependencies that are caused by machine resources.
//
//===-------------------------------------------------------------------------=//
#ifndef LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
#define LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
#include "llvm/Value.h"
class SchedGraphEdge;
class SchedGraphNode;
/******************** Exported Data Types and Constants ********************/
typedef int ResourceId;
const ResourceId InvalidRID = -1;
const ResourceId MachineCCRegsRID = -2; // use +ve numbers for actual regs
const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
const ResourceId MachineFPRegsRID = -4; // use +ve numbers for actual regs
//*********************** Public Class Declarations ************************/
class SchedGraphNodeCommon {
protected:
unsigned ID;
std::vector<SchedGraphEdge*> inEdges;
std::vector<SchedGraphEdge*> outEdges;
int latency;
int origIndexInBB; // original position of instr in BB
public:
typedef std::vector<SchedGraphEdge*>::iterator iterator;
typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator;
typedef std::vector<SchedGraphEdge*>::reverse_iterator reverse_iterator;
typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
// Accessor methods
unsigned getNodeId() const { return ID; }
int getLatency() const { return latency; }
unsigned getNumInEdges() const { return inEdges.size(); }
unsigned getNumOutEdges() const { return outEdges.size(); }
int getOrigIndexInBB() const { return origIndexInBB; }
// Iterators
iterator beginInEdges() { return inEdges.begin(); }
iterator endInEdges() { return inEdges.end(); }
iterator beginOutEdges() { return outEdges.begin(); }
iterator endOutEdges() { return outEdges.end(); }
const_iterator beginInEdges() const { return inEdges.begin(); }
const_iterator endInEdges() const { return inEdges.end(); }
const_iterator beginOutEdges() const { return outEdges.begin(); }
const_iterator endOutEdges() const { return outEdges.end(); }
void dump(int indent=0) const;
// Debugging support
virtual void print(std::ostream &os) const = 0;
protected:
friend class SchedGraph;
friend class SchedGraphCommon;
friend class SchedGraphEdge; // give access for adding edges
// disable default constructor and provide a ctor for single-block graphs
SchedGraphNodeCommon(); // DO NOT IMPLEMENT
inline SchedGraphNodeCommon(unsigned Id, int index) : ID(Id), latency(0),
origIndexInBB(index) {}
virtual ~SchedGraphNodeCommon();
//Functions to add and remove edges
inline void addInEdge(SchedGraphEdge* edge) { inEdges.push_back(edge); }
inline void addOutEdge(SchedGraphEdge* edge) { outEdges.push_back(edge); }
void removeInEdge(const SchedGraphEdge* edge);
void removeOutEdge(const SchedGraphEdge* edge);
};
// ostream << operator for SchedGraphNode class
inline std::ostream &operator<<(std::ostream &os,
const SchedGraphNodeCommon &node) {
node.print(os);
return os;
}
//
// SchedGraphEdge - Edge class to represent dependencies
//
class SchedGraphEdge {
public:
enum SchedGraphEdgeDepType {
CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
};
enum DataDepOrderType {
TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
};
protected:
SchedGraphNodeCommon* src;
SchedGraphNodeCommon* sink;
SchedGraphEdgeDepType depType;
unsigned int depOrderType;
int minDelay; // cached latency (assumes fixed target arch)
int iteDiff;
union {
const Value* val;
int machineRegNum;
ResourceId resourceId;
};
public:
// For all constructors, if minDelay is unspecified, minDelay is
// set to _src->getLatency().
// constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
SchedGraphEdgeDepType _depType, unsigned int _depOrderType,
int _minDelay = -1);
// constructor for explicit value dependence (may be true/anti/output)
SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
const Value* _val, unsigned int _depOrderType,
int _minDelay = -1);
// constructor for machine register dependence
SchedGraphEdge(SchedGraphNodeCommon* _src,SchedGraphNodeCommon* _sink,
unsigned int _regNum, unsigned int _depOrderType,
int _minDelay = -1);
// constructor for any other machine resource dependences.
// DataDepOrderType is always NonDataDep. It it not an argument to
// avoid overloading ambiguity with previous constructor.
SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
ResourceId _resourceId, int _minDelay = -1);
~SchedGraphEdge() {}
SchedGraphNodeCommon* getSrc() const { return src; }
SchedGraphNodeCommon* getSink() const { return sink; }
int getMinDelay() const { return minDelay; }
SchedGraphEdgeDepType getDepType() const { return depType; }
const Value* getValue() const {
assert(depType == ValueDep); return val;
}
int getMachineReg() const {
assert(depType == MachineRegister); return machineRegNum;
}
int getResourceId() const {
assert(depType == MachineResource); return resourceId;
}
void setIteDiff(int _iteDiff) {
iteDiff = _iteDiff;
}
int getIteDiff() {
return iteDiff;
}
public:
// Debugging support
void print(std::ostream &os) const;
void dump(int indent=0) const;
private:
// disable default ctor
SchedGraphEdge(); // DO NOT IMPLEMENT
};
// ostream << operator for SchedGraphNode class
inline std::ostream &operator<<(std::ostream &os, const SchedGraphEdge &edge) {
edge.print(os);
return os;
}
class SchedGraphCommon {
protected:
SchedGraphNodeCommon* graphRoot; // the root and leaf are not inserted
SchedGraphNodeCommon* graphLeaf; // in the hash_map (see getNumNodes())
public:
//
// Accessor methods
//
SchedGraphNodeCommon* getRoot() const { return graphRoot; }
SchedGraphNodeCommon* getLeaf() const { return graphLeaf; }
//
// Delete nodes or edges from the graph.
//
void eraseNode(SchedGraphNodeCommon* node);
void eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
void eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
void eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
SchedGraphCommon() {}
~SchedGraphCommon();
};
#endif
|
