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 * Authors: Kevin Lim
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::O3CPU O3CPU;
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::O3CPU;
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 /** Should the FU be added to the list to be freed upon
98 * completing this event.
99 */
100 bool freeFU;
101
102 public:
103 /** Construct a FU completion event. */
104 FUCompletion(DynInstPtr &_inst, int fu_idx,
105 InstructionQueue<Impl> *iq_ptr);
106
107 virtual void process();
| 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 * Authors: Kevin Lim
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::O3CPU O3CPU;
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::O3CPU;
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 /** Should the FU be added to the list to be freed upon
98 * completing this event.
99 */
100 bool freeFU;
101
102 public:
103 /** Construct a FU completion event. */
104 FUCompletion(DynInstPtr &_inst, int fu_idx,
105 InstructionQueue<Impl> *iq_ptr);
106
107 virtual void process();
|
108 virtual const char *description();
| 108 virtual const char *description() const;
|
109 void setFreeFU() { freeFU = true; }
110 };
111
112 /** Constructs an IQ. */
113 InstructionQueue(O3CPU *cpu_ptr, IEW *iew_ptr, Params *params);
114
115 /** Destructs the IQ. */
116 ~InstructionQueue();
117
118 /** Returns the name of the IQ. */
119 std::string name() const;
120
121 /** Registers statistics. */
122 void regStats();
123
124 /** Resets all instruction queue state. */
125 void resetState();
126
127 /** Sets active threads list. */
128 void setActiveThreads(std::list<unsigned> *at_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 /** Switches out the instruction queue. */
137 void switchOut();
138
139 /** Takes over execution from another CPU's thread. */
140 void takeOverFrom();
141
142 /** Returns if the IQ is switched out. */
143 bool isSwitchedOut() { return switchedOut; }
144
145 /** Number of entries needed for given amount of threads. */
146 int entryAmount(int num_threads);
147
148 /** Resets max entries for all threads. */
149 void resetEntries();
150
151 /** Returns total number of free entries. */
152 unsigned numFreeEntries();
153
154 /** Returns number of free entries for a thread. */
155 unsigned numFreeEntries(unsigned tid);
156
157 /** Returns whether or not the IQ is full. */
158 bool isFull();
159
160 /** Returns whether or not the IQ is full for a specific thread. */
161 bool isFull(unsigned tid);
162
163 /** Returns if there are any ready instructions in the IQ. */
164 bool hasReadyInsts();
165
166 /** Inserts a new instruction into the IQ. */
167 void insert(DynInstPtr &new_inst);
168
169 /** Inserts a new, non-speculative instruction into the IQ. */
170 void insertNonSpec(DynInstPtr &new_inst);
171
172 /** Inserts a memory or write barrier into the IQ to make sure
173 * loads and stores are ordered properly.
174 */
175 void insertBarrier(DynInstPtr &barr_inst);
176
177 /** Returns the oldest scheduled instruction, and removes it from
178 * the list of instructions waiting to execute.
179 */
180 DynInstPtr getInstToExecute();
181
182 /**
183 * Records the instruction as the producer of a register without
184 * adding it to the rest of the IQ.
185 */
186 void recordProducer(DynInstPtr &inst)
187 { addToProducers(inst); }
188
189 /** Process FU completion event. */
190 void processFUCompletion(DynInstPtr &inst, int fu_idx);
191
192 /**
193 * Schedules ready instructions, adding the ready ones (oldest first) to
194 * the queue to execute.
195 */
196 void scheduleReadyInsts();
197
198 /** Schedules a single specific non-speculative instruction. */
199 void scheduleNonSpec(const InstSeqNum &inst);
200
201 /**
202 * Commits all instructions up to and including the given sequence number,
203 * for a specific thread.
204 */
205 void commit(const InstSeqNum &inst, unsigned tid = 0);
206
207 /** Wakes all dependents of a completed instruction. */
208 int wakeDependents(DynInstPtr &completed_inst);
209
210 /** Adds a ready memory instruction to the ready list. */
211 void addReadyMemInst(DynInstPtr &ready_inst);
212
213 /**
214 * Reschedules a memory instruction. It will be ready to issue once
215 * replayMemInst() is called.
216 */
217 void rescheduleMemInst(DynInstPtr &resched_inst);
218
219 /** Replays a memory instruction. It must be rescheduled first. */
220 void replayMemInst(DynInstPtr &replay_inst);
221
222 /** Completes a memory operation. */
223 void completeMemInst(DynInstPtr &completed_inst);
224
225 /** Indicates an ordering violation between a store and a load. */
226 void violation(DynInstPtr &store, DynInstPtr &faulting_load);
227
228 /**
229 * Squashes instructions for a thread. Squashing information is obtained
230 * from the time buffer.
231 */
232 void squash(unsigned tid);
233
234 /** Returns the number of used entries for a thread. */
235 unsigned getCount(unsigned tid) { return count[tid]; };
236
237 /** Debug function to print all instructions. */
238 void printInsts();
239
240 private:
241 /** Does the actual squashing. */
242 void doSquash(unsigned tid);
243
244 /////////////////////////
245 // Various pointers
246 /////////////////////////
247
248 /** Pointer to the CPU. */
249 O3CPU *cpu;
250
251 /** Cache interface. */
252 MemInterface *dcacheInterface;
253
254 /** Pointer to IEW stage. */
255 IEW *iewStage;
256
257 /** The memory dependence unit, which tracks/predicts memory dependences
258 * between instructions.
259 */
260 MemDepUnit memDepUnit[Impl::MaxThreads];
261
262 /** The queue to the execute stage. Issued instructions will be written
263 * into it.
264 */
265 TimeBuffer<IssueStruct> *issueToExecuteQueue;
266
267 /** The backwards time buffer. */
268 TimeBuffer<TimeStruct> *timeBuffer;
269
270 /** Wire to read information from timebuffer. */
271 typename TimeBuffer<TimeStruct>::wire fromCommit;
272
273 /** Function unit pool. */
274 FUPool *fuPool;
275
276 //////////////////////////////////////
277 // Instruction lists, ready queues, and ordering
278 //////////////////////////////////////
279
280 /** List of all the instructions in the IQ (some of which may be issued). */
281 std::list<DynInstPtr> instList[Impl::MaxThreads];
282
283 /** List of instructions that are ready to be executed. */
284 std::list<DynInstPtr> instsToExecute;
285
286 /**
287 * Struct for comparing entries to be added to the priority queue.
288 * This gives reverse ordering to the instructions in terms of
289 * sequence numbers: the instructions with smaller sequence
290 * numbers (and hence are older) will be at the top of the
291 * priority queue.
292 */
293 struct pqCompare {
294 bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
295 {
296 return lhs->seqNum > rhs->seqNum;
297 }
298 };
299
300 typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
301 ReadyInstQueue;
302
303 /** List of ready instructions, per op class. They are separated by op
304 * class to allow for easy mapping to FUs.
305 */
306 ReadyInstQueue readyInsts[Num_OpClasses];
307
308 /** List of non-speculative instructions that will be scheduled
309 * once the IQ gets a signal from commit. While it's redundant to
310 * have the key be a part of the value (the sequence number is stored
311 * inside of DynInst), when these instructions are woken up only
312 * the sequence number will be available. Thus it is most efficient to be
313 * able to search by the sequence number alone.
314 */
315 std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
316
317 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;
318
319 /** Entry for the list age ordering by op class. */
320 struct ListOrderEntry {
321 OpClass queueType;
322 InstSeqNum oldestInst;
323 };
324
325 /** List that contains the age order of the oldest instruction of each
326 * ready queue. Used to select the oldest instruction available
327 * among op classes.
328 * @todo: Might be better to just move these entries around instead
329 * of creating new ones every time the position changes due to an
330 * instruction issuing. Not sure std::list supports this.
331 */
332 std::list<ListOrderEntry> listOrder;
333
334 typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;
335
336 /** Tracks if each ready queue is on the age order list. */
337 bool queueOnList[Num_OpClasses];
338
339 /** Iterators of each ready queue. Points to their spot in the age order
340 * list.
341 */
342 ListOrderIt readyIt[Num_OpClasses];
343
344 /** Add an op class to the age order list. */
345 void addToOrderList(OpClass op_class);
346
347 /**
348 * Called when the oldest instruction has been removed from a ready queue;
349 * this places that ready queue into the proper spot in the age order list.
350 */
351 void moveToYoungerInst(ListOrderIt age_order_it);
352
353 DependencyGraph<DynInstPtr> dependGraph;
354
355 //////////////////////////////////////
356 // Various parameters
357 //////////////////////////////////////
358
359 /** IQ Resource Sharing Policy */
360 enum IQPolicy {
361 Dynamic,
362 Partitioned,
363 Threshold
364 };
365
366 /** IQ sharing policy for SMT. */
367 IQPolicy iqPolicy;
368
369 /** Number of Total Threads*/
370 unsigned numThreads;
371
372 /** Pointer to list of active threads. */
373 std::list<unsigned> *activeThreads;
374
375 /** Per Thread IQ count */
376 unsigned count[Impl::MaxThreads];
377
378 /** Max IQ Entries Per Thread */
379 unsigned maxEntries[Impl::MaxThreads];
380
381 /** Number of free IQ entries left. */
382 unsigned freeEntries;
383
384 /** The number of entries in the instruction queue. */
385 unsigned numEntries;
386
387 /** The total number of instructions that can be issued in one cycle. */
388 unsigned totalWidth;
389
390 /** The number of physical registers in the CPU. */
391 unsigned numPhysRegs;
392
393 /** The number of physical integer registers in the CPU. */
394 unsigned numPhysIntRegs;
395
396 /** The number of floating point registers in the CPU. */
397 unsigned numPhysFloatRegs;
398
399 /** Delay between commit stage and the IQ.
400 * @todo: Make there be a distinction between the delays within IEW.
401 */
402 unsigned commitToIEWDelay;
403
404 /** Is the IQ switched out. */
405 bool switchedOut;
406
407 /** The sequence number of the squashed instruction. */
408 InstSeqNum squashedSeqNum[Impl::MaxThreads];
409
410 /** A cache of the recently woken registers. It is 1 if the register
411 * has been woken up recently, and 0 if the register has been added
412 * to the dependency graph and has not yet received its value. It
413 * is basically a secondary scoreboard, and should pretty much mirror
414 * the scoreboard that exists in the rename map.
415 */
416 std::vector<bool> regScoreboard;
417
418 /** Adds an instruction to the dependency graph, as a consumer. */
419 bool addToDependents(DynInstPtr &new_inst);
420
421 /** Adds an instruction to the dependency graph, as a producer. */
422 void addToProducers(DynInstPtr &new_inst);
423
424 /** Moves an instruction to the ready queue if it is ready. */
425 void addIfReady(DynInstPtr &inst);
426
427 /** Debugging function to count how many entries are in the IQ. It does
428 * a linear walk through the instructions, so do not call this function
429 * during normal execution.
430 */
431 int countInsts();
432
433 /** Debugging function to dump all the list sizes, as well as print
434 * out the list of nonspeculative instructions. Should not be used
435 * in any other capacity, but it has no harmful sideaffects.
436 */
437 void dumpLists();
438
439 /** Debugging function to dump out all instructions that are in the
440 * IQ.
441 */
442 void dumpInsts();
443
444 /** Stat for number of instructions added. */
445 Stats::Scalar<> iqInstsAdded;
446 /** Stat for number of non-speculative instructions added. */
447 Stats::Scalar<> iqNonSpecInstsAdded;
448
449 Stats::Scalar<> iqInstsIssued;
450 /** Stat for number of integer instructions issued. */
451 Stats::Scalar<> iqIntInstsIssued;
452 /** Stat for number of floating point instructions issued. */
453 Stats::Scalar<> iqFloatInstsIssued;
454 /** Stat for number of branch instructions issued. */
455 Stats::Scalar<> iqBranchInstsIssued;
456 /** Stat for number of memory instructions issued. */
457 Stats::Scalar<> iqMemInstsIssued;
458 /** Stat for number of miscellaneous instructions issued. */
459 Stats::Scalar<> iqMiscInstsIssued;
460 /** Stat for number of squashed instructions that were ready to issue. */
461 Stats::Scalar<> iqSquashedInstsIssued;
462 /** Stat for number of squashed instructions examined when squashing. */
463 Stats::Scalar<> iqSquashedInstsExamined;
464 /** Stat for number of squashed instruction operands examined when
465 * squashing.
466 */
467 Stats::Scalar<> iqSquashedOperandsExamined;
468 /** Stat for number of non-speculative instructions removed due to a squash.
469 */
470 Stats::Scalar<> iqSquashedNonSpecRemoved;
471 // Also include number of instructions rescheduled and replayed.
472
473 /** Distribution of number of instructions in the queue.
474 * @todo: Need to create struct to track the entry time for each
475 * instruction. */
476// Stats::VectorDistribution<> queueResDist;
477 /** Distribution of the number of instructions issued. */
478 Stats::Distribution<> numIssuedDist;
479 /** Distribution of the cycles it takes to issue an instruction.
480 * @todo: Need to create struct to track the ready time for each
481 * instruction. */
482// Stats::VectorDistribution<> issueDelayDist;
483
484 /** Number of times an instruction could not be issued because a
485 * FU was busy.
486 */
487 Stats::Vector<> statFuBusy;
488// Stats::Vector<> dist_unissued;
489 /** Stat for total number issued for each instruction type. */
490 Stats::Vector2d<> statIssuedInstType;
491
492 /** Number of instructions issued per cycle. */
493 Stats::Formula issueRate;
494
495 /** Number of times the FU was busy. */
496 Stats::Vector<> fuBusy;
497 /** Number of times the FU was busy per instruction issued. */
498 Stats::Formula fuBusyRate;
499};
500
501#endif //__CPU_O3_INST_QUEUE_HH__
| 109 void setFreeFU() { freeFU = true; }
110 };
111
112 /** Constructs an IQ. */
113 InstructionQueue(O3CPU *cpu_ptr, IEW *iew_ptr, Params *params);
114
115 /** Destructs the IQ. */
116 ~InstructionQueue();
117
118 /** Returns the name of the IQ. */
119 std::string name() const;
120
121 /** Registers statistics. */
122 void regStats();
123
124 /** Resets all instruction queue state. */
125 void resetState();
126
127 /** Sets active threads list. */
128 void setActiveThreads(std::list<unsigned> *at_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 /** Switches out the instruction queue. */
137 void switchOut();
138
139 /** Takes over execution from another CPU's thread. */
140 void takeOverFrom();
141
142 /** Returns if the IQ is switched out. */
143 bool isSwitchedOut() { return switchedOut; }
144
145 /** Number of entries needed for given amount of threads. */
146 int entryAmount(int num_threads);
147
148 /** Resets max entries for all threads. */
149 void resetEntries();
150
151 /** Returns total number of free entries. */
152 unsigned numFreeEntries();
153
154 /** Returns number of free entries for a thread. */
155 unsigned numFreeEntries(unsigned tid);
156
157 /** Returns whether or not the IQ is full. */
158 bool isFull();
159
160 /** Returns whether or not the IQ is full for a specific thread. */
161 bool isFull(unsigned tid);
162
163 /** Returns if there are any ready instructions in the IQ. */
164 bool hasReadyInsts();
165
166 /** Inserts a new instruction into the IQ. */
167 void insert(DynInstPtr &new_inst);
168
169 /** Inserts a new, non-speculative instruction into the IQ. */
170 void insertNonSpec(DynInstPtr &new_inst);
171
172 /** Inserts a memory or write barrier into the IQ to make sure
173 * loads and stores are ordered properly.
174 */
175 void insertBarrier(DynInstPtr &barr_inst);
176
177 /** Returns the oldest scheduled instruction, and removes it from
178 * the list of instructions waiting to execute.
179 */
180 DynInstPtr getInstToExecute();
181
182 /**
183 * Records the instruction as the producer of a register without
184 * adding it to the rest of the IQ.
185 */
186 void recordProducer(DynInstPtr &inst)
187 { addToProducers(inst); }
188
189 /** Process FU completion event. */
190 void processFUCompletion(DynInstPtr &inst, int fu_idx);
191
192 /**
193 * Schedules ready instructions, adding the ready ones (oldest first) to
194 * the queue to execute.
195 */
196 void scheduleReadyInsts();
197
198 /** Schedules a single specific non-speculative instruction. */
199 void scheduleNonSpec(const InstSeqNum &inst);
200
201 /**
202 * Commits all instructions up to and including the given sequence number,
203 * for a specific thread.
204 */
205 void commit(const InstSeqNum &inst, unsigned tid = 0);
206
207 /** Wakes all dependents of a completed instruction. */
208 int wakeDependents(DynInstPtr &completed_inst);
209
210 /** Adds a ready memory instruction to the ready list. */
211 void addReadyMemInst(DynInstPtr &ready_inst);
212
213 /**
214 * Reschedules a memory instruction. It will be ready to issue once
215 * replayMemInst() is called.
216 */
217 void rescheduleMemInst(DynInstPtr &resched_inst);
218
219 /** Replays a memory instruction. It must be rescheduled first. */
220 void replayMemInst(DynInstPtr &replay_inst);
221
222 /** Completes a memory operation. */
223 void completeMemInst(DynInstPtr &completed_inst);
224
225 /** Indicates an ordering violation between a store and a load. */
226 void violation(DynInstPtr &store, DynInstPtr &faulting_load);
227
228 /**
229 * Squashes instructions for a thread. Squashing information is obtained
230 * from the time buffer.
231 */
232 void squash(unsigned tid);
233
234 /** Returns the number of used entries for a thread. */
235 unsigned getCount(unsigned tid) { return count[tid]; };
236
237 /** Debug function to print all instructions. */
238 void printInsts();
239
240 private:
241 /** Does the actual squashing. */
242 void doSquash(unsigned tid);
243
244 /////////////////////////
245 // Various pointers
246 /////////////////////////
247
248 /** Pointer to the CPU. */
249 O3CPU *cpu;
250
251 /** Cache interface. */
252 MemInterface *dcacheInterface;
253
254 /** Pointer to IEW stage. */
255 IEW *iewStage;
256
257 /** The memory dependence unit, which tracks/predicts memory dependences
258 * between instructions.
259 */
260 MemDepUnit memDepUnit[Impl::MaxThreads];
261
262 /** The queue to the execute stage. Issued instructions will be written
263 * into it.
264 */
265 TimeBuffer<IssueStruct> *issueToExecuteQueue;
266
267 /** The backwards time buffer. */
268 TimeBuffer<TimeStruct> *timeBuffer;
269
270 /** Wire to read information from timebuffer. */
271 typename TimeBuffer<TimeStruct>::wire fromCommit;
272
273 /** Function unit pool. */
274 FUPool *fuPool;
275
276 //////////////////////////////////////
277 // Instruction lists, ready queues, and ordering
278 //////////////////////////////////////
279
280 /** List of all the instructions in the IQ (some of which may be issued). */
281 std::list<DynInstPtr> instList[Impl::MaxThreads];
282
283 /** List of instructions that are ready to be executed. */
284 std::list<DynInstPtr> instsToExecute;
285
286 /**
287 * Struct for comparing entries to be added to the priority queue.
288 * This gives reverse ordering to the instructions in terms of
289 * sequence numbers: the instructions with smaller sequence
290 * numbers (and hence are older) will be at the top of the
291 * priority queue.
292 */
293 struct pqCompare {
294 bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
295 {
296 return lhs->seqNum > rhs->seqNum;
297 }
298 };
299
300 typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
301 ReadyInstQueue;
302
303 /** List of ready instructions, per op class. They are separated by op
304 * class to allow for easy mapping to FUs.
305 */
306 ReadyInstQueue readyInsts[Num_OpClasses];
307
308 /** List of non-speculative instructions that will be scheduled
309 * once the IQ gets a signal from commit. While it's redundant to
310 * have the key be a part of the value (the sequence number is stored
311 * inside of DynInst), when these instructions are woken up only
312 * the sequence number will be available. Thus it is most efficient to be
313 * able to search by the sequence number alone.
314 */
315 std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
316
317 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;
318
319 /** Entry for the list age ordering by op class. */
320 struct ListOrderEntry {
321 OpClass queueType;
322 InstSeqNum oldestInst;
323 };
324
325 /** List that contains the age order of the oldest instruction of each
326 * ready queue. Used to select the oldest instruction available
327 * among op classes.
328 * @todo: Might be better to just move these entries around instead
329 * of creating new ones every time the position changes due to an
330 * instruction issuing. Not sure std::list supports this.
331 */
332 std::list<ListOrderEntry> listOrder;
333
334 typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;
335
336 /** Tracks if each ready queue is on the age order list. */
337 bool queueOnList[Num_OpClasses];
338
339 /** Iterators of each ready queue. Points to their spot in the age order
340 * list.
341 */
342 ListOrderIt readyIt[Num_OpClasses];
343
344 /** Add an op class to the age order list. */
345 void addToOrderList(OpClass op_class);
346
347 /**
348 * Called when the oldest instruction has been removed from a ready queue;
349 * this places that ready queue into the proper spot in the age order list.
350 */
351 void moveToYoungerInst(ListOrderIt age_order_it);
352
353 DependencyGraph<DynInstPtr> dependGraph;
354
355 //////////////////////////////////////
356 // Various parameters
357 //////////////////////////////////////
358
359 /** IQ Resource Sharing Policy */
360 enum IQPolicy {
361 Dynamic,
362 Partitioned,
363 Threshold
364 };
365
366 /** IQ sharing policy for SMT. */
367 IQPolicy iqPolicy;
368
369 /** Number of Total Threads*/
370 unsigned numThreads;
371
372 /** Pointer to list of active threads. */
373 std::list<unsigned> *activeThreads;
374
375 /** Per Thread IQ count */
376 unsigned count[Impl::MaxThreads];
377
378 /** Max IQ Entries Per Thread */
379 unsigned maxEntries[Impl::MaxThreads];
380
381 /** Number of free IQ entries left. */
382 unsigned freeEntries;
383
384 /** The number of entries in the instruction queue. */
385 unsigned numEntries;
386
387 /** The total number of instructions that can be issued in one cycle. */
388 unsigned totalWidth;
389
390 /** The number of physical registers in the CPU. */
391 unsigned numPhysRegs;
392
393 /** The number of physical integer registers in the CPU. */
394 unsigned numPhysIntRegs;
395
396 /** The number of floating point registers in the CPU. */
397 unsigned numPhysFloatRegs;
398
399 /** Delay between commit stage and the IQ.
400 * @todo: Make there be a distinction between the delays within IEW.
401 */
402 unsigned commitToIEWDelay;
403
404 /** Is the IQ switched out. */
405 bool switchedOut;
406
407 /** The sequence number of the squashed instruction. */
408 InstSeqNum squashedSeqNum[Impl::MaxThreads];
409
410 /** A cache of the recently woken registers. It is 1 if the register
411 * has been woken up recently, and 0 if the register has been added
412 * to the dependency graph and has not yet received its value. It
413 * is basically a secondary scoreboard, and should pretty much mirror
414 * the scoreboard that exists in the rename map.
415 */
416 std::vector<bool> regScoreboard;
417
418 /** Adds an instruction to the dependency graph, as a consumer. */
419 bool addToDependents(DynInstPtr &new_inst);
420
421 /** Adds an instruction to the dependency graph, as a producer. */
422 void addToProducers(DynInstPtr &new_inst);
423
424 /** Moves an instruction to the ready queue if it is ready. */
425 void addIfReady(DynInstPtr &inst);
426
427 /** Debugging function to count how many entries are in the IQ. It does
428 * a linear walk through the instructions, so do not call this function
429 * during normal execution.
430 */
431 int countInsts();
432
433 /** Debugging function to dump all the list sizes, as well as print
434 * out the list of nonspeculative instructions. Should not be used
435 * in any other capacity, but it has no harmful sideaffects.
436 */
437 void dumpLists();
438
439 /** Debugging function to dump out all instructions that are in the
440 * IQ.
441 */
442 void dumpInsts();
443
444 /** Stat for number of instructions added. */
445 Stats::Scalar<> iqInstsAdded;
446 /** Stat for number of non-speculative instructions added. */
447 Stats::Scalar<> iqNonSpecInstsAdded;
448
449 Stats::Scalar<> iqInstsIssued;
450 /** Stat for number of integer instructions issued. */
451 Stats::Scalar<> iqIntInstsIssued;
452 /** Stat for number of floating point instructions issued. */
453 Stats::Scalar<> iqFloatInstsIssued;
454 /** Stat for number of branch instructions issued. */
455 Stats::Scalar<> iqBranchInstsIssued;
456 /** Stat for number of memory instructions issued. */
457 Stats::Scalar<> iqMemInstsIssued;
458 /** Stat for number of miscellaneous instructions issued. */
459 Stats::Scalar<> iqMiscInstsIssued;
460 /** Stat for number of squashed instructions that were ready to issue. */
461 Stats::Scalar<> iqSquashedInstsIssued;
462 /** Stat for number of squashed instructions examined when squashing. */
463 Stats::Scalar<> iqSquashedInstsExamined;
464 /** Stat for number of squashed instruction operands examined when
465 * squashing.
466 */
467 Stats::Scalar<> iqSquashedOperandsExamined;
468 /** Stat for number of non-speculative instructions removed due to a squash.
469 */
470 Stats::Scalar<> iqSquashedNonSpecRemoved;
471 // Also include number of instructions rescheduled and replayed.
472
473 /** Distribution of number of instructions in the queue.
474 * @todo: Need to create struct to track the entry time for each
475 * instruction. */
476// Stats::VectorDistribution<> queueResDist;
477 /** Distribution of the number of instructions issued. */
478 Stats::Distribution<> numIssuedDist;
479 /** Distribution of the cycles it takes to issue an instruction.
480 * @todo: Need to create struct to track the ready time for each
481 * instruction. */
482// Stats::VectorDistribution<> issueDelayDist;
483
484 /** Number of times an instruction could not be issued because a
485 * FU was busy.
486 */
487 Stats::Vector<> statFuBusy;
488// Stats::Vector<> dist_unissued;
489 /** Stat for total number issued for each instruction type. */
490 Stats::Vector2d<> statIssuedInstType;
491
492 /** Number of instructions issued per cycle. */
493 Stats::Formula issueRate;
494
495 /** Number of times the FU was busy. */
496 Stats::Vector<> fuBusy;
497 /** Number of times the FU was busy per instruction issued. */
498 Stats::Formula fuBusyRate;
499};
500
501#endif //__CPU_O3_INST_QUEUE_HH__
|