1/*
2 * Copyright (c) 2012 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Copyright (c) 2006 The Regents of The University of Michigan
15 * All rights reserved.
16 *
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions are
19 * met: redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer;
21 * redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution;
24 * neither the name of the copyright holders nor the names of its
25 * contributors may be used to endorse or promote products derived from
26 * this software without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 *
40 * Authors: Kevin Lim
41 */
42
43#ifndef __CPU_O3_DEP_GRAPH_HH__
44#define __CPU_O3_DEP_GRAPH_HH__
45
46#include "cpu/o3/comm.hh"
47
48/** Node in a linked list. */
49template <class DynInstPtr>
50class DependencyEntry
51{
52 public:
53 DependencyEntry()
54 : inst(NULL), next(NULL)
55 { }
56
57 DynInstPtr inst;
58 //Might want to include data about what arch. register the
59 //dependence is waiting on.
60 DependencyEntry<DynInstPtr> *next;
61};
62
63/** Array of linked list that maintains the dependencies between
64 * producing instructions and consuming instructions. Each linked
65 * list represents a single physical register, having the future
66 * producer of the register's value, and all consumers waiting on that
67 * value on the list. The head node of each linked list represents
68 * the producing instruction of that register. Instructions are put
69 * on the list upon reaching the IQ, and are removed from the list
70 * either when the producer completes, or the instruction is squashed.
71*/
72template <class DynInstPtr>
73class DependencyGraph
74{
75 public:
76 typedef DependencyEntry<DynInstPtr> DepEntry;
77
78 /** Default construction. Must call resize() prior to use. */
79 DependencyGraph()
80 : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0)
81 { }
82
83 ~DependencyGraph();
84
85 /** Resize the dependency graph to have num_entries registers. */
86 void resize(int num_entries);
87
88 /** Clears all of the linked lists. */
89 void reset();
90
91 /** Inserts an instruction to be dependent on the given index. */
92 void insert(PhysRegIndex idx, const DynInstPtr &new_inst);
93
94 /** Sets the producing instruction of a given register. */
95 void setInst(PhysRegIndex idx, const DynInstPtr &new_inst)
96 { dependGraph[idx].inst = new_inst; }
97
98 /** Clears the producing instruction. */
99 void clearInst(PhysRegIndex idx)
100 { dependGraph[idx].inst = NULL; }
101
102 /** Removes an instruction from a single linked list. */
103 void remove(PhysRegIndex idx, const DynInstPtr &inst_to_remove);
104
105 /** Removes and returns the newest dependent of a specific register. */
106 DynInstPtr pop(PhysRegIndex idx);
107
108 /** Checks if the entire dependency graph is empty. */
109 bool empty() const;
110
111 /** Checks if there are any dependents on a specific register. */
112 bool empty(PhysRegIndex idx) const { return !dependGraph[idx].next; }
113
114 /** Debugging function to dump out the dependency graph.
115 */
116 void dump();
117
118 private:
119 /** Array of linked lists. Each linked list is a list of all the
120 * instructions that depend upon a given register. The actual
121 * register's index is used to index into the graph; ie all
122 * instructions in flight that are dependent upon r34 will be
123 * in the linked list of dependGraph[34].
124 */
| 1/*
2 * Copyright (c) 2012 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Copyright (c) 2006 The Regents of The University of Michigan
15 * All rights reserved.
16 *
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions are
19 * met: redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer;
21 * redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution;
24 * neither the name of the copyright holders nor the names of its
25 * contributors may be used to endorse or promote products derived from
26 * this software without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 *
40 * Authors: Kevin Lim
41 */
42
43#ifndef __CPU_O3_DEP_GRAPH_HH__
44#define __CPU_O3_DEP_GRAPH_HH__
45
46#include "cpu/o3/comm.hh"
47
48/** Node in a linked list. */
49template <class DynInstPtr>
50class DependencyEntry
51{
52 public:
53 DependencyEntry()
54 : inst(NULL), next(NULL)
55 { }
56
57 DynInstPtr inst;
58 //Might want to include data about what arch. register the
59 //dependence is waiting on.
60 DependencyEntry<DynInstPtr> *next;
61};
62
63/** Array of linked list that maintains the dependencies between
64 * producing instructions and consuming instructions. Each linked
65 * list represents a single physical register, having the future
66 * producer of the register's value, and all consumers waiting on that
67 * value on the list. The head node of each linked list represents
68 * the producing instruction of that register. Instructions are put
69 * on the list upon reaching the IQ, and are removed from the list
70 * either when the producer completes, or the instruction is squashed.
71*/
72template <class DynInstPtr>
73class DependencyGraph
74{
75 public:
76 typedef DependencyEntry<DynInstPtr> DepEntry;
77
78 /** Default construction. Must call resize() prior to use. */
79 DependencyGraph()
80 : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0)
81 { }
82
83 ~DependencyGraph();
84
85 /** Resize the dependency graph to have num_entries registers. */
86 void resize(int num_entries);
87
88 /** Clears all of the linked lists. */
89 void reset();
90
91 /** Inserts an instruction to be dependent on the given index. */
92 void insert(PhysRegIndex idx, const DynInstPtr &new_inst);
93
94 /** Sets the producing instruction of a given register. */
95 void setInst(PhysRegIndex idx, const DynInstPtr &new_inst)
96 { dependGraph[idx].inst = new_inst; }
97
98 /** Clears the producing instruction. */
99 void clearInst(PhysRegIndex idx)
100 { dependGraph[idx].inst = NULL; }
101
102 /** Removes an instruction from a single linked list. */
103 void remove(PhysRegIndex idx, const DynInstPtr &inst_to_remove);
104
105 /** Removes and returns the newest dependent of a specific register. */
106 DynInstPtr pop(PhysRegIndex idx);
107
108 /** Checks if the entire dependency graph is empty. */
109 bool empty() const;
110
111 /** Checks if there are any dependents on a specific register. */
112 bool empty(PhysRegIndex idx) const { return !dependGraph[idx].next; }
113
114 /** Debugging function to dump out the dependency graph.
115 */
116 void dump();
117
118 private:
119 /** Array of linked lists. Each linked list is a list of all the
120 * instructions that depend upon a given register. The actual
121 * register's index is used to index into the graph; ie all
122 * instructions in flight that are dependent upon r34 will be
123 * in the linked list of dependGraph[34].
124 */
|
126
127 /** Number of linked lists; identical to the number of registers. */
128 int numEntries;
129
130 // Debug variable, remove when done testing.
131 unsigned memAllocCounter;
132
133 public:
134 // Debug variable, remove when done testing.
135 uint64_t nodesTraversed;
136 // Debug variable, remove when done testing.
137 uint64_t nodesRemoved;
138};
139
140template <class DynInstPtr>
141DependencyGraph<DynInstPtr>::~DependencyGraph()
142{
| 126
127 /** Number of linked lists; identical to the number of registers. */
128 int numEntries;
129
130 // Debug variable, remove when done testing.
131 unsigned memAllocCounter;
132
133 public:
134 // Debug variable, remove when done testing.
135 uint64_t nodesTraversed;
136 // Debug variable, remove when done testing.
137 uint64_t nodesRemoved;
138};
139
140template <class DynInstPtr>
141DependencyGraph<DynInstPtr>::~DependencyGraph()
142{
|
152}
153
154template <class DynInstPtr>
155void
156DependencyGraph<DynInstPtr>::reset()
157{
158 // Clear the dependency graph
159 DepEntry *curr;
160 DepEntry *prev;
161
162 for (int i = 0; i < numEntries; ++i) {
163 curr = dependGraph[i].next;
164
165 while (curr) {
166 memAllocCounter--;
167
168 prev = curr;
169 curr = prev->next;
170 prev->inst = NULL;
171
172 delete prev;
173 }
174
175 if (dependGraph[i].inst) {
176 dependGraph[i].inst = NULL;
177 }
178
179 dependGraph[i].next = NULL;
180 }
181}
182
183template <class DynInstPtr>
184void
185DependencyGraph<DynInstPtr>::insert(PhysRegIndex idx,
186 const DynInstPtr &new_inst)
187{
188 //Add this new, dependent instruction at the head of the dependency
189 //chain.
190
191 // First create the entry that will be added to the head of the
192 // dependency chain.
193 DepEntry *new_entry = new DepEntry;
194 new_entry->next = dependGraph[idx].next;
195 new_entry->inst = new_inst;
196
197 // Then actually add it to the chain.
198 dependGraph[idx].next = new_entry;
199
200 ++memAllocCounter;
201}
202
203
204template <class DynInstPtr>
205void
206DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx,
207 const DynInstPtr &inst_to_remove)
208{
209 DepEntry *prev = &dependGraph[idx];
210 DepEntry *curr = dependGraph[idx].next;
211
212 // Make sure curr isn't NULL. Because this instruction is being
213 // removed from a dependency list, it must have been placed there at
214 // an earlier time. The dependency chain should not be empty,
215 // unless the instruction dependent upon it is already ready.
216 if (curr == NULL) {
217 return;
218 }
219
220 nodesRemoved++;
221
222 // Find the instruction to remove within the dependency linked list.
223 while (curr->inst != inst_to_remove) {
224 prev = curr;
225 curr = curr->next;
226 nodesTraversed++;
227
228 assert(curr != NULL);
229 }
230
231 // Now remove this instruction from the list.
232 prev->next = curr->next;
233
234 --memAllocCounter;
235
236 // Could push this off to the destructor of DependencyEntry
237 curr->inst = NULL;
238
239 delete curr;
240}
241
242template <class DynInstPtr>
243DynInstPtr
244DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx)
245{
246 DepEntry *node;
247 node = dependGraph[idx].next;
248 DynInstPtr inst = NULL;
249 if (node) {
250 inst = node->inst;
251 dependGraph[idx].next = node->next;
252 node->inst = NULL;
253 memAllocCounter--;
254 delete node;
255 }
256 return inst;
257}
258
259template <class DynInstPtr>
260bool
261DependencyGraph<DynInstPtr>::empty() const
262{
263 for (int i = 0; i < numEntries; ++i) {
264 if (!empty(i))
265 return false;
266 }
267 return true;
268}
269
270template <class DynInstPtr>
271void
272DependencyGraph<DynInstPtr>::dump()
273{
274 DepEntry *curr;
275
276 for (int i = 0; i < numEntries; ++i)
277 {
278 curr = &dependGraph[i];
279
280 if (curr->inst) {
281 cprintf("dependGraph[%i]: producer: %s [sn:%lli] consumer: ",
282 i, curr->inst->pcState(), curr->inst->seqNum);
283 } else {
284 cprintf("dependGraph[%i]: No producer. consumer: ", i);
285 }
286
287 while (curr->next != NULL) {
288 curr = curr->next;
289
290 cprintf("%s [sn:%lli] ",
291 curr->inst->pcState(), curr->inst->seqNum);
292 }
293
294 cprintf("\n");
295 }
296 cprintf("memAllocCounter: %i\n", memAllocCounter);
297}
298
299#endif // __CPU_O3_DEP_GRAPH_HH__
| 151}
152
153template <class DynInstPtr>
154void
155DependencyGraph<DynInstPtr>::reset()
156{
157 // Clear the dependency graph
158 DepEntry *curr;
159 DepEntry *prev;
160
161 for (int i = 0; i < numEntries; ++i) {
162 curr = dependGraph[i].next;
163
164 while (curr) {
165 memAllocCounter--;
166
167 prev = curr;
168 curr = prev->next;
169 prev->inst = NULL;
170
171 delete prev;
172 }
173
174 if (dependGraph[i].inst) {
175 dependGraph[i].inst = NULL;
176 }
177
178 dependGraph[i].next = NULL;
179 }
180}
181
182template <class DynInstPtr>
183void
184DependencyGraph<DynInstPtr>::insert(PhysRegIndex idx,
185 const DynInstPtr &new_inst)
186{
187 //Add this new, dependent instruction at the head of the dependency
188 //chain.
189
190 // First create the entry that will be added to the head of the
191 // dependency chain.
192 DepEntry *new_entry = new DepEntry;
193 new_entry->next = dependGraph[idx].next;
194 new_entry->inst = new_inst;
195
196 // Then actually add it to the chain.
197 dependGraph[idx].next = new_entry;
198
199 ++memAllocCounter;
200}
201
202
203template <class DynInstPtr>
204void
205DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx,
206 const DynInstPtr &inst_to_remove)
207{
208 DepEntry *prev = &dependGraph[idx];
209 DepEntry *curr = dependGraph[idx].next;
210
211 // Make sure curr isn't NULL. Because this instruction is being
212 // removed from a dependency list, it must have been placed there at
213 // an earlier time. The dependency chain should not be empty,
214 // unless the instruction dependent upon it is already ready.
215 if (curr == NULL) {
216 return;
217 }
218
219 nodesRemoved++;
220
221 // Find the instruction to remove within the dependency linked list.
222 while (curr->inst != inst_to_remove) {
223 prev = curr;
224 curr = curr->next;
225 nodesTraversed++;
226
227 assert(curr != NULL);
228 }
229
230 // Now remove this instruction from the list.
231 prev->next = curr->next;
232
233 --memAllocCounter;
234
235 // Could push this off to the destructor of DependencyEntry
236 curr->inst = NULL;
237
238 delete curr;
239}
240
241template <class DynInstPtr>
242DynInstPtr
243DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx)
244{
245 DepEntry *node;
246 node = dependGraph[idx].next;
247 DynInstPtr inst = NULL;
248 if (node) {
249 inst = node->inst;
250 dependGraph[idx].next = node->next;
251 node->inst = NULL;
252 memAllocCounter--;
253 delete node;
254 }
255 return inst;
256}
257
258template <class DynInstPtr>
259bool
260DependencyGraph<DynInstPtr>::empty() const
261{
262 for (int i = 0; i < numEntries; ++i) {
263 if (!empty(i))
264 return false;
265 }
266 return true;
267}
268
269template <class DynInstPtr>
270void
271DependencyGraph<DynInstPtr>::dump()
272{
273 DepEntry *curr;
274
275 for (int i = 0; i < numEntries; ++i)
276 {
277 curr = &dependGraph[i];
278
279 if (curr->inst) {
280 cprintf("dependGraph[%i]: producer: %s [sn:%lli] consumer: ",
281 i, curr->inst->pcState(), curr->inst->seqNum);
282 } else {
283 cprintf("dependGraph[%i]: No producer. consumer: ", i);
284 }
285
286 while (curr->next != NULL) {
287 curr = curr->next;
288
289 cprintf("%s [sn:%lli] ",
290 curr->inst->pcState(), curr->inst->seqNum);
291 }
292
293 cprintf("\n");
294 }
295 cprintf("memAllocCounter: %i\n", memAllocCounter);
296}
297
298#endif // __CPU_O3_DEP_GRAPH_HH__
|