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