1
2#ifndef __CPU_O3_DEP_GRAPH_HH__
3#define __CPU_O3_DEP_GRAPH_HH__
4
5#include "cpu/o3/comm.hh"
6
| 1
2#ifndef __CPU_O3_DEP_GRAPH_HH__
3#define __CPU_O3_DEP_GRAPH_HH__
4
5#include "cpu/o3/comm.hh"
6
|
| 7/** Node in a linked list. */
|
7template <class DynInstPtr>
8class DependencyEntry
9{
10 public:
11 DependencyEntry()
12 : inst(NULL), next(NULL)
13 { }
14
15 DynInstPtr inst;
16 //Might want to include data about what arch. register the
17 //dependence is waiting on.
18 DependencyEntry<DynInstPtr> *next;
19};
20
| 8template <class DynInstPtr>
9class DependencyEntry
10{
11 public:
12 DependencyEntry()
13 : inst(NULL), next(NULL)
14 { }
15
16 DynInstPtr inst;
17 //Might want to include data about what arch. register the
18 //dependence is waiting on.
19 DependencyEntry<DynInstPtr> *next;
20};
21
|
| 22/** Array of linked list that maintains the dependencies between
23 * producing instructions and consuming instructions. Each linked
24 * list represents a single physical register, having the future
25 * producer of the register's value, and all consumers waiting on that
26 * value on the list. The head node of each linked list represents
27 * the producing instruction of that register. Instructions are put
28 * on the list upon reaching the IQ, and are removed from the list
29 * either when the producer completes, or the instruction is squashed.
30*/
|
21template <class DynInstPtr>
22class DependencyGraph
23{
24 public:
25 typedef DependencyEntry<DynInstPtr> DepEntry;
26
| 31template <class DynInstPtr>
32class DependencyGraph
33{
34 public:
35 typedef DependencyEntry<DynInstPtr> DepEntry;
36
|
| 37 /** Default construction. Must call resize() prior to use. */
|
27 DependencyGraph()
28 : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0)
29 { }
30
| 38 DependencyGraph()
39 : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0)
40 { }
41
|
| 42 /** Resize the dependency graph to have num_entries registers. */
|
31 void resize(int num_entries);
32
| 43 void resize(int num_entries);
44
|
| 45 /** Clears all of the linked lists. */
|
33 void reset();
34
| 46 void reset();
47
|
| 48 /** Inserts an instruction to be dependent on the given index. */
|
35 void insert(PhysRegIndex idx, DynInstPtr &new_inst);
36
| 49 void insert(PhysRegIndex idx, DynInstPtr &new_inst);
50
|
| 51 /** Sets the producing instruction of a given register. */
|
37 void setInst(PhysRegIndex idx, DynInstPtr &new_inst)
38 { dependGraph[idx].inst = new_inst; }
39
| 52 void setInst(PhysRegIndex idx, DynInstPtr &new_inst)
53 { dependGraph[idx].inst = new_inst; }
54
|
| 55 /** Clears the producing instruction. */
|
40 void clearInst(PhysRegIndex idx)
41 { dependGraph[idx].inst = NULL; }
42
| 56 void clearInst(PhysRegIndex idx)
57 { dependGraph[idx].inst = NULL; }
58
|
| 59 /** Removes an instruction from a single linked list. */
|
43 void remove(PhysRegIndex idx, DynInstPtr &inst_to_remove);
44
| 60 void remove(PhysRegIndex idx, DynInstPtr &inst_to_remove);
61
|
| 62 /** Removes and returns the newest dependent of a specific register. */
|
45 DynInstPtr pop(PhysRegIndex idx);
46
| 63 DynInstPtr pop(PhysRegIndex idx);
64
|
| 65 /** Checks if there are any dependents on a specific register. */
|
47 bool empty(PhysRegIndex idx) { return !dependGraph[idx].next; }
48
49 /** Debugging function to dump out the dependency graph.
50 */
51 void dump();
52
53 private:
54 /** Array of linked lists. Each linked list is a list of all the
55 * instructions that depend upon a given register. The actual
56 * register's index is used to index into the graph; ie all
57 * instructions in flight that are dependent upon r34 will be
58 * in the linked list of dependGraph[34].
59 */
60 DepEntry *dependGraph;
61
| 66 bool empty(PhysRegIndex idx) { return !dependGraph[idx].next; }
67
68 /** Debugging function to dump out the dependency graph.
69 */
70 void dump();
71
72 private:
73 /** Array of linked lists. Each linked list is a list of all the
74 * instructions that depend upon a given register. The actual
75 * register's index is used to index into the graph; ie all
76 * instructions in flight that are dependent upon r34 will be
77 * in the linked list of dependGraph[34].
78 */
79 DepEntry *dependGraph;
80
|
| 81 /** Number of linked lists; identical to the number of registers. */
|
62 int numEntries;
63
64 // Debug variable, remove when done testing.
65 unsigned memAllocCounter;
66
67 public:
| 82 int numEntries;
83
84 // Debug variable, remove when done testing.
85 unsigned memAllocCounter;
86
87 public:
|
| 88 // Debug variable, remove when done testing.
|
68 uint64_t nodesTraversed;
| 89 uint64_t nodesTraversed;
|
| 90 // Debug variable, remove when done testing.
|
69 uint64_t nodesRemoved;
70};
71
72template <class DynInstPtr>
73void
74DependencyGraph<DynInstPtr>::resize(int num_entries)
75{
76 numEntries = num_entries;
77 dependGraph = new DepEntry[numEntries];
78}
79
80template <class DynInstPtr>
81void
82DependencyGraph<DynInstPtr>::reset()
83{
84 // Clear the dependency graph
85 DepEntry *curr;
86 DepEntry *prev;
87
88 for (int i = 0; i < numEntries; ++i) {
89 curr = dependGraph[i].next;
90
91 while (curr) {
92 memAllocCounter--;
93
94 prev = curr;
95 curr = prev->next;
96 prev->inst = NULL;
97
98 delete prev;
99 }
100
101 if (dependGraph[i].inst) {
102 dependGraph[i].inst = NULL;
103 }
104
105 dependGraph[i].next = NULL;
106 }
107}
108
109template <class DynInstPtr>
110void
111DependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, DynInstPtr &new_inst)
112{
113 //Add this new, dependent instruction at the head of the dependency
114 //chain.
115
116 // First create the entry that will be added to the head of the
117 // dependency chain.
118 DepEntry *new_entry = new DepEntry;
119 new_entry->next = dependGraph[idx].next;
120 new_entry->inst = new_inst;
121
122 // Then actually add it to the chain.
123 dependGraph[idx].next = new_entry;
124
125 ++memAllocCounter;
126}
127
128
129template <class DynInstPtr>
130void
131DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx,
132 DynInstPtr &inst_to_remove)
133{
134 DepEntry *prev = &dependGraph[idx];
135 DepEntry *curr = dependGraph[idx].next;
136
137 // Make sure curr isn't NULL. Because this instruction is being
138 // removed from a dependency list, it must have been placed there at
139 // an earlier time. The dependency chain should not be empty,
140 // unless the instruction dependent upon it is already ready.
141 if (curr == NULL) {
142 return;
143 }
144
145 nodesRemoved++;
146
147 // Find the instruction to remove within the dependency linked list.
148 while (curr->inst != inst_to_remove) {
149 prev = curr;
150 curr = curr->next;
151 nodesTraversed++;
152
153 assert(curr != NULL);
154 }
155
156 // Now remove this instruction from the list.
157 prev->next = curr->next;
158
159 --memAllocCounter;
160
161 // Could push this off to the destructor of DependencyEntry
162 curr->inst = NULL;
163
164 delete curr;
165}
166
167template <class DynInstPtr>
168DynInstPtr
169DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx)
170{
171 DepEntry *node;
172 node = dependGraph[idx].next;
173 DynInstPtr inst = NULL;
174 if (node) {
175 inst = node->inst;
176 dependGraph[idx].next = node->next;
177 node->inst = NULL;
178 memAllocCounter--;
179 delete node;
180 }
181 return inst;
182}
183
184template <class DynInstPtr>
185void
186DependencyGraph<DynInstPtr>::dump()
187{
188 DepEntry *curr;
189
190 for (int i = 0; i < numEntries; ++i)
191 {
192 curr = &dependGraph[i];
193
194 if (curr->inst) {
195 cprintf("dependGraph[%i]: producer: %#x [sn:%lli] consumer: ",
196 i, curr->inst->readPC(), curr->inst->seqNum);
197 } else {
198 cprintf("dependGraph[%i]: No producer. consumer: ", i);
199 }
200
201 while (curr->next != NULL) {
202 curr = curr->next;
203
204 cprintf("%#x [sn:%lli] ",
205 curr->inst->readPC(), curr->inst->seqNum);
206 }
207
208 cprintf("\n");
209 }
210 cprintf("memAllocCounter: %i\n", memAllocCounter);
211}
212
213#endif // __CPU_O3_DEP_GRAPH_HH__
| 91 uint64_t nodesRemoved;
92};
93
94template <class DynInstPtr>
95void
96DependencyGraph<DynInstPtr>::resize(int num_entries)
97{
98 numEntries = num_entries;
99 dependGraph = new DepEntry[numEntries];
100}
101
102template <class DynInstPtr>
103void
104DependencyGraph<DynInstPtr>::reset()
105{
106 // Clear the dependency graph
107 DepEntry *curr;
108 DepEntry *prev;
109
110 for (int i = 0; i < numEntries; ++i) {
111 curr = dependGraph[i].next;
112
113 while (curr) {
114 memAllocCounter--;
115
116 prev = curr;
117 curr = prev->next;
118 prev->inst = NULL;
119
120 delete prev;
121 }
122
123 if (dependGraph[i].inst) {
124 dependGraph[i].inst = NULL;
125 }
126
127 dependGraph[i].next = NULL;
128 }
129}
130
131template <class DynInstPtr>
132void
133DependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, DynInstPtr &new_inst)
134{
135 //Add this new, dependent instruction at the head of the dependency
136 //chain.
137
138 // First create the entry that will be added to the head of the
139 // dependency chain.
140 DepEntry *new_entry = new DepEntry;
141 new_entry->next = dependGraph[idx].next;
142 new_entry->inst = new_inst;
143
144 // Then actually add it to the chain.
145 dependGraph[idx].next = new_entry;
146
147 ++memAllocCounter;
148}
149
150
151template <class DynInstPtr>
152void
153DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx,
154 DynInstPtr &inst_to_remove)
155{
156 DepEntry *prev = &dependGraph[idx];
157 DepEntry *curr = dependGraph[idx].next;
158
159 // Make sure curr isn't NULL. Because this instruction is being
160 // removed from a dependency list, it must have been placed there at
161 // an earlier time. The dependency chain should not be empty,
162 // unless the instruction dependent upon it is already ready.
163 if (curr == NULL) {
164 return;
165 }
166
167 nodesRemoved++;
168
169 // Find the instruction to remove within the dependency linked list.
170 while (curr->inst != inst_to_remove) {
171 prev = curr;
172 curr = curr->next;
173 nodesTraversed++;
174
175 assert(curr != NULL);
176 }
177
178 // Now remove this instruction from the list.
179 prev->next = curr->next;
180
181 --memAllocCounter;
182
183 // Could push this off to the destructor of DependencyEntry
184 curr->inst = NULL;
185
186 delete curr;
187}
188
189template <class DynInstPtr>
190DynInstPtr
191DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx)
192{
193 DepEntry *node;
194 node = dependGraph[idx].next;
195 DynInstPtr inst = NULL;
196 if (node) {
197 inst = node->inst;
198 dependGraph[idx].next = node->next;
199 node->inst = NULL;
200 memAllocCounter--;
201 delete node;
202 }
203 return inst;
204}
205
206template <class DynInstPtr>
207void
208DependencyGraph<DynInstPtr>::dump()
209{
210 DepEntry *curr;
211
212 for (int i = 0; i < numEntries; ++i)
213 {
214 curr = &dependGraph[i];
215
216 if (curr->inst) {
217 cprintf("dependGraph[%i]: producer: %#x [sn:%lli] consumer: ",
218 i, curr->inst->readPC(), curr->inst->seqNum);
219 } else {
220 cprintf("dependGraph[%i]: No producer. consumer: ", i);
221 }
222
223 while (curr->next != NULL) {
224 curr = curr->next;
225
226 cprintf("%#x [sn:%lli] ",
227 curr->inst->readPC(), curr->inst->seqNum);
228 }
229
230 cprintf("\n");
231 }
232 cprintf("memAllocCounter: %i\n", memAllocCounter);
233}
234
235#endif // __CPU_O3_DEP_GRAPH_HH__
|