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