1/*
2 * Copyright (c) 2004-2006 The Regents of The University of Michigan
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
| 1/*
2 * Copyright (c) 2004-2006 The Regents of The University of Michigan
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
27 */
28
29#ifndef __CPU_O3_INST_QUEUE_HH__
30#define __CPU_O3_INST_QUEUE_HH__
31
32#include <list>
33#include <map>
34#include <queue>
35#include <vector>
36
37#include "base/statistics.hh"
38#include "base/timebuf.hh"
39#include "cpu/inst_seq.hh"
40#include "cpu/o3/dep_graph.hh"
41#include "cpu/op_class.hh"
42#include "sim/host.hh"
43
44class FUPool;
45class MemInterface;
46
47/**
48 * A standard instruction queue class. It holds ready instructions, in
49 * order, in seperate priority queues to facilitate the scheduling of
50 * instructions. The IQ uses a separate linked list to track dependencies.
51 * Similar to the rename map and the free list, it expects that
52 * floating point registers have their indices start after the integer
53 * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
54 * and 96-191 are fp). This remains true even for both logical and
55 * physical register indices. The IQ depends on the memory dependence unit to
56 * track when memory operations are ready in terms of ordering; register
57 * dependencies are tracked normally. Right now the IQ also handles the
58 * execution timing; this is mainly to allow back-to-back scheduling without
59 * requiring IEW to be able to peek into the IQ. At the end of the execution
60 * latency, the instruction is put into the queue to execute, where it will
61 * have the execute() function called on it.
62 * @todo: Make IQ able to handle multiple FU pools.
63 */
64template <class Impl>
65class InstructionQueue
66{
67 public:
68 //Typedefs from the Impl.
69 typedef typename Impl::FullCPU FullCPU;
70 typedef typename Impl::DynInstPtr DynInstPtr;
71 typedef typename Impl::Params Params;
72
73 typedef typename Impl::CPUPol::IEW IEW;
74 typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
75 typedef typename Impl::CPUPol::IssueStruct IssueStruct;
76 typedef typename Impl::CPUPol::TimeStruct TimeStruct;
77
78 // Typedef of iterator through the list of instructions.
79 typedef typename std::list<DynInstPtr>::iterator ListIt;
80
81 friend class Impl::FullCPU;
82
83 /** FU completion event class. */
84 class FUCompletion : public Event {
85 private:
86 /** Executing instruction. */
87 DynInstPtr inst;
88
89 /** Index of the FU used for executing. */
90 int fuIdx;
91
92 /** Pointer back to the instruction queue. */
93 InstructionQueue<Impl> *iqPtr;
94
95 bool freeFU;
96
97 public:
98 /** Construct a FU completion event. */
99 FUCompletion(DynInstPtr &_inst, int fu_idx,
100 InstructionQueue<Impl> *iq_ptr);
101
102 virtual void process();
103 virtual const char *description();
104 void setFreeFU() { freeFU = true; }
105 };
106
107 /** Constructs an IQ. */
108 InstructionQueue(Params *params);
109
110 /** Destructs the IQ. */
111 ~InstructionQueue();
112
113 /** Returns the name of the IQ. */
114 std::string name() const;
115
116 /** Registers statistics. */
117 void regStats();
118
119 void resetState();
120
121 /** Sets CPU pointer. */
122 void setCPU(FullCPU *_cpu) { cpu = _cpu; }
123
124 /** Sets active threads list. */
125 void setActiveThreads(std::list<unsigned> *at_ptr);
126
127 /** Sets the IEW pointer. */
128 void setIEW(IEW *iew_ptr) { iewStage = iew_ptr; }
129
130 /** Sets the timer buffer between issue and execute. */
131 void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);
132
133 /** Sets the global time buffer. */
134 void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
135
136 void switchOut();
137
138 void takeOverFrom();
139
140 bool isSwitchedOut() { return switchedOut; }
141
142 /** Number of entries needed for given amount of threads. */
143 int entryAmount(int num_threads);
144
145 /** Resets max entries for all threads. */
146 void resetEntries();
147
148 /** Returns total number of free entries. */
149 unsigned numFreeEntries();
150
151 /** Returns number of free entries for a thread. */
152 unsigned numFreeEntries(unsigned tid);
153
154 /** Returns whether or not the IQ is full. */
155 bool isFull();
156
157 /** Returns whether or not the IQ is full for a specific thread. */
158 bool isFull(unsigned tid);
159
160 /** Returns if there are any ready instructions in the IQ. */
161 bool hasReadyInsts();
162
163 /** Inserts a new instruction into the IQ. */
164 void insert(DynInstPtr &new_inst);
165
166 /** Inserts a new, non-speculative instruction into the IQ. */
167 void insertNonSpec(DynInstPtr &new_inst);
168
169 /** Inserts a memory or write barrier into the IQ to make sure
170 * loads and stores are ordered properly.
171 */
172 void insertBarrier(DynInstPtr &barr_inst);
173
174 DynInstPtr getInstToExecute();
175
176 /**
177 * Records the instruction as the producer of a register without
178 * adding it to the rest of the IQ.
179 */
180 void recordProducer(DynInstPtr &inst)
181 { addToProducers(inst); }
182
183 /** Process FU completion event. */
184 void processFUCompletion(DynInstPtr &inst, int fu_idx);
185
186 /**
187 * Schedules ready instructions, adding the ready ones (oldest first) to
188 * the queue to execute.
189 */
190 void scheduleReadyInsts();
191
192 /** Schedules a single specific non-speculative instruction. */
193 void scheduleNonSpec(const InstSeqNum &inst);
194
195 /**
196 * Commits all instructions up to and including the given sequence number,
197 * for a specific thread.
198 */
199 void commit(const InstSeqNum &inst, unsigned tid = 0);
200
201 /** Wakes all dependents of a completed instruction. */
202 int wakeDependents(DynInstPtr &completed_inst);
203
204 /** Adds a ready memory instruction to the ready list. */
205 void addReadyMemInst(DynInstPtr &ready_inst);
206
207 /**
208 * Reschedules a memory instruction. It will be ready to issue once
209 * replayMemInst() is called.
210 */
211 void rescheduleMemInst(DynInstPtr &resched_inst);
212
213 /** Replays a memory instruction. It must be rescheduled first. */
214 void replayMemInst(DynInstPtr &replay_inst);
215
216 /** Completes a memory operation. */
217 void completeMemInst(DynInstPtr &completed_inst);
218
219 /** Indicates an ordering violation between a store and a load. */
220 void violation(DynInstPtr &store, DynInstPtr &faulting_load);
221
222 /**
223 * Squashes instructions for a thread. Squashing information is obtained
224 * from the time buffer.
225 */
226 void squash(unsigned tid);
227
228 /** Returns the number of used entries for a thread. */
229 unsigned getCount(unsigned tid) { return count[tid]; };
230
231 /** Debug function to print all instructions. */
232 void printInsts();
233
234 private:
235 /** Does the actual squashing. */
236 void doSquash(unsigned tid);
237
238 /////////////////////////
239 // Various pointers
240 /////////////////////////
241
242 /** Pointer to the CPU. */
243 FullCPU *cpu;
244
245 /** Cache interface. */
246 MemInterface *dcacheInterface;
247
248 /** Pointer to IEW stage. */
249 IEW *iewStage;
250
251 /** The memory dependence unit, which tracks/predicts memory dependences
252 * between instructions.
253 */
254 MemDepUnit memDepUnit[Impl::MaxThreads];
255
256 /** The queue to the execute stage. Issued instructions will be written
257 * into it.
258 */
259 TimeBuffer<IssueStruct> *issueToExecuteQueue;
260
261 /** The backwards time buffer. */
262 TimeBuffer<TimeStruct> *timeBuffer;
263
264 /** Wire to read information from timebuffer. */
265 typename TimeBuffer<TimeStruct>::wire fromCommit;
266
267 /** Function unit pool. */
268 FUPool *fuPool;
269
270 //////////////////////////////////////
271 // Instruction lists, ready queues, and ordering
272 //////////////////////////////////////
273
274 /** List of all the instructions in the IQ (some of which may be issued). */
275 std::list<DynInstPtr> instList[Impl::MaxThreads];
276
277 std::list<DynInstPtr> instsToExecute;
278
279 /**
280 * Struct for comparing entries to be added to the priority queue. This
281 * gives reverse ordering to the instructions in terms of sequence
282 * numbers: the instructions with smaller sequence numbers (and hence
283 * are older) will be at the top of the priority queue.
284 */
285 struct pqCompare {
286 bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
287 {
288 return lhs->seqNum > rhs->seqNum;
289 }
290 };
291
292 typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
293 ReadyInstQueue;
294
295 /** List of ready instructions, per op class. They are separated by op
296 * class to allow for easy mapping to FUs.
297 */
298 ReadyInstQueue readyInsts[Num_OpClasses];
299
300 /** List of non-speculative instructions that will be scheduled
301 * once the IQ gets a signal from commit. While it's redundant to
302 * have the key be a part of the value (the sequence number is stored
303 * inside of DynInst), when these instructions are woken up only
304 * the sequence number will be available. Thus it is most efficient to be
305 * able to search by the sequence number alone.
306 */
307 std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
308
309 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;
310
311 /** Entry for the list age ordering by op class. */
312 struct ListOrderEntry {
313 OpClass queueType;
314 InstSeqNum oldestInst;
315 };
316
317 /** List that contains the age order of the oldest instruction of each
318 * ready queue. Used to select the oldest instruction available
319 * among op classes.
320 * @todo: Might be better to just move these entries around instead
321 * of creating new ones every time the position changes due to an
322 * instruction issuing. Not sure std::list supports this.
323 */
324 std::list<ListOrderEntry> listOrder;
325
326 typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;
327
328 /** Tracks if each ready queue is on the age order list. */
329 bool queueOnList[Num_OpClasses];
330
331 /** Iterators of each ready queue. Points to their spot in the age order
332 * list.
333 */
334 ListOrderIt readyIt[Num_OpClasses];
335
336 /** Add an op class to the age order list. */
337 void addToOrderList(OpClass op_class);
338
339 /**
340 * Called when the oldest instruction has been removed from a ready queue;
341 * this places that ready queue into the proper spot in the age order list.
342 */
343 void moveToYoungerInst(ListOrderIt age_order_it);
344
345 DependencyGraph<DynInstPtr> dependGraph;
346
347 //////////////////////////////////////
348 // Various parameters
349 //////////////////////////////////////
350
351 /** IQ Resource Sharing Policy */
352 enum IQPolicy {
353 Dynamic,
354 Partitioned,
355 Threshold
356 };
357
358 /** IQ sharing policy for SMT. */
359 IQPolicy iqPolicy;
360
361 /** Number of Total Threads*/
362 unsigned numThreads;
363
364 /** Pointer to list of active threads. */
365 std::list<unsigned> *activeThreads;
366
367 /** Per Thread IQ count */
368 unsigned count[Impl::MaxThreads];
369
370 /** Max IQ Entries Per Thread */
371 unsigned maxEntries[Impl::MaxThreads];
372
373 /** Number of free IQ entries left. */
374 unsigned freeEntries;
375
376 /** The number of entries in the instruction queue. */
377 unsigned numEntries;
378
379 /** The total number of instructions that can be issued in one cycle. */
380 unsigned totalWidth;
381
382 /** The number of physical registers in the CPU. */
383 unsigned numPhysRegs;
384
385 /** The number of physical integer registers in the CPU. */
386 unsigned numPhysIntRegs;
387
388 /** The number of floating point registers in the CPU. */
389 unsigned numPhysFloatRegs;
390
391 /** Delay between commit stage and the IQ.
392 * @todo: Make there be a distinction between the delays within IEW.
393 */
394 unsigned commitToIEWDelay;
395
396 bool switchedOut;
397
398 /** The sequence number of the squashed instruction. */
399 InstSeqNum squashedSeqNum[Impl::MaxThreads];
400
401 /** A cache of the recently woken registers. It is 1 if the register
402 * has been woken up recently, and 0 if the register has been added
403 * to the dependency graph and has not yet received its value. It
404 * is basically a secondary scoreboard, and should pretty much mirror
405 * the scoreboard that exists in the rename map.
406 */
407 std::vector<bool> regScoreboard;
408
409 /** Adds an instruction to the dependency graph, as a consumer. */
410 bool addToDependents(DynInstPtr &new_inst);
411
412 /** Adds an instruction to the dependency graph, as a producer. */
413 void addToProducers(DynInstPtr &new_inst);
414
415 /** Moves an instruction to the ready queue if it is ready. */
416 void addIfReady(DynInstPtr &inst);
417
418 /** Debugging function to count how many entries are in the IQ. It does
419 * a linear walk through the instructions, so do not call this function
420 * during normal execution.
421 */
422 int countInsts();
423
424 /** Debugging function to dump all the list sizes, as well as print
425 * out the list of nonspeculative instructions. Should not be used
426 * in any other capacity, but it has no harmful sideaffects.
427 */
428 void dumpLists();
429
430 /** Debugging function to dump out all instructions that are in the
431 * IQ.
432 */
433 void dumpInsts();
434
435 /** Stat for number of instructions added. */
436 Stats::Scalar<> iqInstsAdded;
437 /** Stat for number of non-speculative instructions added. */
438 Stats::Scalar<> iqNonSpecInstsAdded;
439
440 Stats::Scalar<> iqInstsIssued;
441 /** Stat for number of integer instructions issued. */
442 Stats::Scalar<> iqIntInstsIssued;
443 /** Stat for number of floating point instructions issued. */
444 Stats::Scalar<> iqFloatInstsIssued;
445 /** Stat for number of branch instructions issued. */
446 Stats::Scalar<> iqBranchInstsIssued;
447 /** Stat for number of memory instructions issued. */
448 Stats::Scalar<> iqMemInstsIssued;
449 /** Stat for number of miscellaneous instructions issued. */
450 Stats::Scalar<> iqMiscInstsIssued;
451 /** Stat for number of squashed instructions that were ready to issue. */
452 Stats::Scalar<> iqSquashedInstsIssued;
453 /** Stat for number of squashed instructions examined when squashing. */
454 Stats::Scalar<> iqSquashedInstsExamined;
455 /** Stat for number of squashed instruction operands examined when
456 * squashing.
457 */
458 Stats::Scalar<> iqSquashedOperandsExamined;
459 /** Stat for number of non-speculative instructions removed due to a squash.
460 */
461 Stats::Scalar<> iqSquashedNonSpecRemoved;
462
463 Stats::VectorDistribution<> queueResDist;
464 Stats::Distribution<> numIssuedDist;
465 Stats::VectorDistribution<> issueDelayDist;
466
467 Stats::Vector<> statFuBusy;
468// Stats::Vector<> dist_unissued;
469 Stats::Vector2d<> statIssuedInstType;
470
471 Stats::Formula issueRate;
472// Stats::Formula issue_stores;
473// Stats::Formula issue_op_rate;
474 Stats::Vector<> fuBusy; //cumulative fu busy
475
476 Stats::Formula fuBusyRate;
477};
478
479#endif //__CPU_O3_INST_QUEUE_HH__
| 29 */
30
31#ifndef __CPU_O3_INST_QUEUE_HH__
32#define __CPU_O3_INST_QUEUE_HH__
33
34#include <list>
35#include <map>
36#include <queue>
37#include <vector>
38
39#include "base/statistics.hh"
40#include "base/timebuf.hh"
41#include "cpu/inst_seq.hh"
42#include "cpu/o3/dep_graph.hh"
43#include "cpu/op_class.hh"
44#include "sim/host.hh"
45
46class FUPool;
47class MemInterface;
48
49/**
50 * A standard instruction queue class. It holds ready instructions, in
51 * order, in seperate priority queues to facilitate the scheduling of
52 * instructions. The IQ uses a separate linked list to track dependencies.
53 * Similar to the rename map and the free list, it expects that
54 * floating point registers have their indices start after the integer
55 * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
56 * and 96-191 are fp). This remains true even for both logical and
57 * physical register indices. The IQ depends on the memory dependence unit to
58 * track when memory operations are ready in terms of ordering; register
59 * dependencies are tracked normally. Right now the IQ also handles the
60 * execution timing; this is mainly to allow back-to-back scheduling without
61 * requiring IEW to be able to peek into the IQ. At the end of the execution
62 * latency, the instruction is put into the queue to execute, where it will
63 * have the execute() function called on it.
64 * @todo: Make IQ able to handle multiple FU pools.
65 */
66template <class Impl>
67class InstructionQueue
68{
69 public:
70 //Typedefs from the Impl.
71 typedef typename Impl::FullCPU FullCPU;
72 typedef typename Impl::DynInstPtr DynInstPtr;
73 typedef typename Impl::Params Params;
74
75 typedef typename Impl::CPUPol::IEW IEW;
76 typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
77 typedef typename Impl::CPUPol::IssueStruct IssueStruct;
78 typedef typename Impl::CPUPol::TimeStruct TimeStruct;
79
80 // Typedef of iterator through the list of instructions.
81 typedef typename std::list<DynInstPtr>::iterator ListIt;
82
83 friend class Impl::FullCPU;
84
85 /** FU completion event class. */
86 class FUCompletion : public Event {
87 private:
88 /** Executing instruction. */
89 DynInstPtr inst;
90
91 /** Index of the FU used for executing. */
92 int fuIdx;
93
94 /** Pointer back to the instruction queue. */
95 InstructionQueue<Impl> *iqPtr;
96
97 bool freeFU;
98
99 public:
100 /** Construct a FU completion event. */
101 FUCompletion(DynInstPtr &_inst, int fu_idx,
102 InstructionQueue<Impl> *iq_ptr);
103
104 virtual void process();
105 virtual const char *description();
106 void setFreeFU() { freeFU = true; }
107 };
108
109 /** Constructs an IQ. */
110 InstructionQueue(Params *params);
111
112 /** Destructs the IQ. */
113 ~InstructionQueue();
114
115 /** Returns the name of the IQ. */
116 std::string name() const;
117
118 /** Registers statistics. */
119 void regStats();
120
121 void resetState();
122
123 /** Sets CPU pointer. */
124 void setCPU(FullCPU *_cpu) { cpu = _cpu; }
125
126 /** Sets active threads list. */
127 void setActiveThreads(std::list<unsigned> *at_ptr);
128
129 /** Sets the IEW pointer. */
130 void setIEW(IEW *iew_ptr) { iewStage = iew_ptr; }
131
132 /** Sets the timer buffer between issue and execute. */
133 void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);
134
135 /** Sets the global time buffer. */
136 void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
137
138 void switchOut();
139
140 void takeOverFrom();
141
142 bool isSwitchedOut() { return switchedOut; }
143
144 /** Number of entries needed for given amount of threads. */
145 int entryAmount(int num_threads);
146
147 /** Resets max entries for all threads. */
148 void resetEntries();
149
150 /** Returns total number of free entries. */
151 unsigned numFreeEntries();
152
153 /** Returns number of free entries for a thread. */
154 unsigned numFreeEntries(unsigned tid);
155
156 /** Returns whether or not the IQ is full. */
157 bool isFull();
158
159 /** Returns whether or not the IQ is full for a specific thread. */
160 bool isFull(unsigned tid);
161
162 /** Returns if there are any ready instructions in the IQ. */
163 bool hasReadyInsts();
164
165 /** Inserts a new instruction into the IQ. */
166 void insert(DynInstPtr &new_inst);
167
168 /** Inserts a new, non-speculative instruction into the IQ. */
169 void insertNonSpec(DynInstPtr &new_inst);
170
171 /** Inserts a memory or write barrier into the IQ to make sure
172 * loads and stores are ordered properly.
173 */
174 void insertBarrier(DynInstPtr &barr_inst);
175
176 DynInstPtr getInstToExecute();
177
178 /**
179 * Records the instruction as the producer of a register without
180 * adding it to the rest of the IQ.
181 */
182 void recordProducer(DynInstPtr &inst)
183 { addToProducers(inst); }
184
185 /** Process FU completion event. */
186 void processFUCompletion(DynInstPtr &inst, int fu_idx);
187
188 /**
189 * Schedules ready instructions, adding the ready ones (oldest first) to
190 * the queue to execute.
191 */
192 void scheduleReadyInsts();
193
194 /** Schedules a single specific non-speculative instruction. */
195 void scheduleNonSpec(const InstSeqNum &inst);
196
197 /**
198 * Commits all instructions up to and including the given sequence number,
199 * for a specific thread.
200 */
201 void commit(const InstSeqNum &inst, unsigned tid = 0);
202
203 /** Wakes all dependents of a completed instruction. */
204 int wakeDependents(DynInstPtr &completed_inst);
205
206 /** Adds a ready memory instruction to the ready list. */
207 void addReadyMemInst(DynInstPtr &ready_inst);
208
209 /**
210 * Reschedules a memory instruction. It will be ready to issue once
211 * replayMemInst() is called.
212 */
213 void rescheduleMemInst(DynInstPtr &resched_inst);
214
215 /** Replays a memory instruction. It must be rescheduled first. */
216 void replayMemInst(DynInstPtr &replay_inst);
217
218 /** Completes a memory operation. */
219 void completeMemInst(DynInstPtr &completed_inst);
220
221 /** Indicates an ordering violation between a store and a load. */
222 void violation(DynInstPtr &store, DynInstPtr &faulting_load);
223
224 /**
225 * Squashes instructions for a thread. Squashing information is obtained
226 * from the time buffer.
227 */
228 void squash(unsigned tid);
229
230 /** Returns the number of used entries for a thread. */
231 unsigned getCount(unsigned tid) { return count[tid]; };
232
233 /** Debug function to print all instructions. */
234 void printInsts();
235
236 private:
237 /** Does the actual squashing. */
238 void doSquash(unsigned tid);
239
240 /////////////////////////
241 // Various pointers
242 /////////////////////////
243
244 /** Pointer to the CPU. */
245 FullCPU *cpu;
246
247 /** Cache interface. */
248 MemInterface *dcacheInterface;
249
250 /** Pointer to IEW stage. */
251 IEW *iewStage;
252
253 /** The memory dependence unit, which tracks/predicts memory dependences
254 * between instructions.
255 */
256 MemDepUnit memDepUnit[Impl::MaxThreads];
257
258 /** The queue to the execute stage. Issued instructions will be written
259 * into it.
260 */
261 TimeBuffer<IssueStruct> *issueToExecuteQueue;
262
263 /** The backwards time buffer. */
264 TimeBuffer<TimeStruct> *timeBuffer;
265
266 /** Wire to read information from timebuffer. */
267 typename TimeBuffer<TimeStruct>::wire fromCommit;
268
269 /** Function unit pool. */
270 FUPool *fuPool;
271
272 //////////////////////////////////////
273 // Instruction lists, ready queues, and ordering
274 //////////////////////////////////////
275
276 /** List of all the instructions in the IQ (some of which may be issued). */
277 std::list<DynInstPtr> instList[Impl::MaxThreads];
278
279 std::list<DynInstPtr> instsToExecute;
280
281 /**
282 * Struct for comparing entries to be added to the priority queue. This
283 * gives reverse ordering to the instructions in terms of sequence
284 * numbers: the instructions with smaller sequence numbers (and hence
285 * are older) will be at the top of the priority queue.
286 */
287 struct pqCompare {
288 bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
289 {
290 return lhs->seqNum > rhs->seqNum;
291 }
292 };
293
294 typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
295 ReadyInstQueue;
296
297 /** List of ready instructions, per op class. They are separated by op
298 * class to allow for easy mapping to FUs.
299 */
300 ReadyInstQueue readyInsts[Num_OpClasses];
301
302 /** List of non-speculative instructions that will be scheduled
303 * once the IQ gets a signal from commit. While it's redundant to
304 * have the key be a part of the value (the sequence number is stored
305 * inside of DynInst), when these instructions are woken up only
306 * the sequence number will be available. Thus it is most efficient to be
307 * able to search by the sequence number alone.
308 */
309 std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
310
311 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;
312
313 /** Entry for the list age ordering by op class. */
314 struct ListOrderEntry {
315 OpClass queueType;
316 InstSeqNum oldestInst;
317 };
318
319 /** List that contains the age order of the oldest instruction of each
320 * ready queue. Used to select the oldest instruction available
321 * among op classes.
322 * @todo: Might be better to just move these entries around instead
323 * of creating new ones every time the position changes due to an
324 * instruction issuing. Not sure std::list supports this.
325 */
326 std::list<ListOrderEntry> listOrder;
327
328 typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;
329
330 /** Tracks if each ready queue is on the age order list. */
331 bool queueOnList[Num_OpClasses];
332
333 /** Iterators of each ready queue. Points to their spot in the age order
334 * list.
335 */
336 ListOrderIt readyIt[Num_OpClasses];
337
338 /** Add an op class to the age order list. */
339 void addToOrderList(OpClass op_class);
340
341 /**
342 * Called when the oldest instruction has been removed from a ready queue;
343 * this places that ready queue into the proper spot in the age order list.
344 */
345 void moveToYoungerInst(ListOrderIt age_order_it);
346
347 DependencyGraph<DynInstPtr> dependGraph;
348
349 //////////////////////////////////////
350 // Various parameters
351 //////////////////////////////////////
352
353 /** IQ Resource Sharing Policy */
354 enum IQPolicy {
355 Dynamic,
356 Partitioned,
357 Threshold
358 };
359
360 /** IQ sharing policy for SMT. */
361 IQPolicy iqPolicy;
362
363 /** Number of Total Threads*/
364 unsigned numThreads;
365
366 /** Pointer to list of active threads. */
367 std::list<unsigned> *activeThreads;
368
369 /** Per Thread IQ count */
370 unsigned count[Impl::MaxThreads];
371
372 /** Max IQ Entries Per Thread */
373 unsigned maxEntries[Impl::MaxThreads];
374
375 /** Number of free IQ entries left. */
376 unsigned freeEntries;
377
378 /** The number of entries in the instruction queue. */
379 unsigned numEntries;
380
381 /** The total number of instructions that can be issued in one cycle. */
382 unsigned totalWidth;
383
384 /** The number of physical registers in the CPU. */
385 unsigned numPhysRegs;
386
387 /** The number of physical integer registers in the CPU. */
388 unsigned numPhysIntRegs;
389
390 /** The number of floating point registers in the CPU. */
391 unsigned numPhysFloatRegs;
392
393 /** Delay between commit stage and the IQ.
394 * @todo: Make there be a distinction between the delays within IEW.
395 */
396 unsigned commitToIEWDelay;
397
398 bool switchedOut;
399
400 /** The sequence number of the squashed instruction. */
401 InstSeqNum squashedSeqNum[Impl::MaxThreads];
402
403 /** A cache of the recently woken registers. It is 1 if the register
404 * has been woken up recently, and 0 if the register has been added
405 * to the dependency graph and has not yet received its value. It
406 * is basically a secondary scoreboard, and should pretty much mirror
407 * the scoreboard that exists in the rename map.
408 */
409 std::vector<bool> regScoreboard;
410
411 /** Adds an instruction to the dependency graph, as a consumer. */
412 bool addToDependents(DynInstPtr &new_inst);
413
414 /** Adds an instruction to the dependency graph, as a producer. */
415 void addToProducers(DynInstPtr &new_inst);
416
417 /** Moves an instruction to the ready queue if it is ready. */
418 void addIfReady(DynInstPtr &inst);
419
420 /** Debugging function to count how many entries are in the IQ. It does
421 * a linear walk through the instructions, so do not call this function
422 * during normal execution.
423 */
424 int countInsts();
425
426 /** Debugging function to dump all the list sizes, as well as print
427 * out the list of nonspeculative instructions. Should not be used
428 * in any other capacity, but it has no harmful sideaffects.
429 */
430 void dumpLists();
431
432 /** Debugging function to dump out all instructions that are in the
433 * IQ.
434 */
435 void dumpInsts();
436
437 /** Stat for number of instructions added. */
438 Stats::Scalar<> iqInstsAdded;
439 /** Stat for number of non-speculative instructions added. */
440 Stats::Scalar<> iqNonSpecInstsAdded;
441
442 Stats::Scalar<> iqInstsIssued;
443 /** Stat for number of integer instructions issued. */
444 Stats::Scalar<> iqIntInstsIssued;
445 /** Stat for number of floating point instructions issued. */
446 Stats::Scalar<> iqFloatInstsIssued;
447 /** Stat for number of branch instructions issued. */
448 Stats::Scalar<> iqBranchInstsIssued;
449 /** Stat for number of memory instructions issued. */
450 Stats::Scalar<> iqMemInstsIssued;
451 /** Stat for number of miscellaneous instructions issued. */
452 Stats::Scalar<> iqMiscInstsIssued;
453 /** Stat for number of squashed instructions that were ready to issue. */
454 Stats::Scalar<> iqSquashedInstsIssued;
455 /** Stat for number of squashed instructions examined when squashing. */
456 Stats::Scalar<> iqSquashedInstsExamined;
457 /** Stat for number of squashed instruction operands examined when
458 * squashing.
459 */
460 Stats::Scalar<> iqSquashedOperandsExamined;
461 /** Stat for number of non-speculative instructions removed due to a squash.
462 */
463 Stats::Scalar<> iqSquashedNonSpecRemoved;
464
465 Stats::VectorDistribution<> queueResDist;
466 Stats::Distribution<> numIssuedDist;
467 Stats::VectorDistribution<> issueDelayDist;
468
469 Stats::Vector<> statFuBusy;
470// Stats::Vector<> dist_unissued;
471 Stats::Vector2d<> statIssuedInstType;
472
473 Stats::Formula issueRate;
474// Stats::Formula issue_stores;
475// Stats::Formula issue_op_rate;
476 Stats::Vector<> fuBusy; //cumulative fu busy
477
478 Stats::Formula fuBusyRate;
479};
480
481#endif //__CPU_O3_INST_QUEUE_HH__
|