2 * Copyright (c) 2011-2012, 2014 ARM Limited
3 * Copyright (c) 2013 Advanced Micro Devices, Inc.
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.
15 * Copyright (c) 2004-2006 The Regents of The University of Michigan
16 * All rights reserved.
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.
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.
42 #ifndef __CPU_O3_INST_QUEUE_HH__
43 #define __CPU_O3_INST_QUEUE_HH__
50 #include "base/statistics.hh"
51 #include "base/types.hh"
52 #include "cpu/o3/dep_graph.hh"
53 #include "cpu/inst_seq.hh"
54 #include "cpu/op_class.hh"
55 #include "cpu/timebuf.hh"
56 #include "enums/SMTQueuePolicy.hh"
57 #include "sim/eventq.hh"
59 struct DerivO3CPUParams;
64 * A standard instruction queue class. It holds ready instructions, in
65 * order, in seperate priority queues to facilitate the scheduling of
66 * instructions. The IQ uses a separate linked list to track dependencies.
67 * Similar to the rename map and the free list, it expects that
68 * floating point registers have their indices start after the integer
69 * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
70 * and 96-191 are fp). This remains true even for both logical and
71 * physical register indices. The IQ depends on the memory dependence unit to
72 * track when memory operations are ready in terms of ordering; register
73 * dependencies are tracked normally. Right now the IQ also handles the
74 * execution timing; this is mainly to allow back-to-back scheduling without
75 * requiring IEW to be able to peek into the IQ. At the end of the execution
76 * latency, the instruction is put into the queue to execute, where it will
77 * have the execute() function called on it.
78 * @todo: Make IQ able to handle multiple FU pools.
81 class InstructionQueue
84 //Typedefs from the Impl.
85 typedef typename Impl::O3CPU O3CPU;
86 typedef typename Impl::DynInstPtr DynInstPtr;
88 typedef typename Impl::CPUPol::IEW IEW;
89 typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
90 typedef typename Impl::CPUPol::IssueStruct IssueStruct;
91 typedef typename Impl::CPUPol::TimeStruct TimeStruct;
93 // Typedef of iterator through the list of instructions.
94 typedef typename std::list<DynInstPtr>::iterator ListIt;
96 /** FU completion event class. */
97 class FUCompletion : public Event {
99 /** Executing instruction. */
102 /** Index of the FU used for executing. */
105 /** Pointer back to the instruction queue. */
106 InstructionQueue<Impl> *iqPtr;
108 /** Should the FU be added to the list to be freed upon
109 * completing this event.
114 /** Construct a FU completion event. */
115 FUCompletion(const DynInstPtr &_inst, int fu_idx,
116 InstructionQueue<Impl> *iq_ptr);
118 virtual void process();
119 virtual const char *description() const;
120 void setFreeFU() { freeFU = true; }
123 /** Constructs an IQ. */
124 InstructionQueue(O3CPU *cpu_ptr, IEW *iew_ptr, DerivO3CPUParams *params);
126 /** Destructs the IQ. */
129 /** Returns the name of the IQ. */
130 std::string name() const;
132 /** Registers statistics. */
135 /** Resets all instruction queue state. */
138 /** Sets active threads list. */
139 void setActiveThreads(std::list<ThreadID> *at_ptr);
141 /** Sets the timer buffer between issue and execute. */
142 void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);
144 /** Sets the global time buffer. */
145 void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
147 /** Determine if we are drained. */
148 bool isDrained() const;
150 /** Perform sanity checks after a drain. */
151 void drainSanityCheck() const;
153 /** Takes over execution from another CPU's thread. */
156 /** Number of entries needed for given amount of threads. */
157 int entryAmount(ThreadID num_threads);
159 /** Resets max entries for all threads. */
162 /** Returns total number of free entries. */
163 unsigned numFreeEntries();
165 /** Returns number of free entries for a thread. */
166 unsigned numFreeEntries(ThreadID tid);
168 /** Returns whether or not the IQ is full. */
171 /** Returns whether or not the IQ is full for a specific thread. */
172 bool isFull(ThreadID tid);
174 /** Returns if there are any ready instructions in the IQ. */
175 bool hasReadyInsts();
177 /** Inserts a new instruction into the IQ. */
178 void insert(const DynInstPtr &new_inst);
180 /** Inserts a new, non-speculative instruction into the IQ. */
181 void insertNonSpec(const DynInstPtr &new_inst);
183 /** Inserts a memory or write barrier into the IQ to make sure
184 * loads and stores are ordered properly.
186 void insertBarrier(const DynInstPtr &barr_inst);
188 /** Returns the oldest scheduled instruction, and removes it from
189 * the list of instructions waiting to execute.
191 DynInstPtr getInstToExecute();
193 /** Gets a memory instruction that was referred due to a delayed DTB
194 * translation if it is now ready to execute. NULL if none available.
196 DynInstPtr getDeferredMemInstToExecute();
198 /** Gets a memory instruction that was blocked on the cache. NULL if none
201 DynInstPtr getBlockedMemInstToExecute();
204 * Records the instruction as the producer of a register without
205 * adding it to the rest of the IQ.
207 void recordProducer(const DynInstPtr &inst)
208 { addToProducers(inst); }
210 /** Process FU completion event. */
211 void processFUCompletion(const DynInstPtr &inst, int fu_idx);
214 * Schedules ready instructions, adding the ready ones (oldest first) to
215 * the queue to execute.
217 void scheduleReadyInsts();
219 /** Schedules a single specific non-speculative instruction. */
220 void scheduleNonSpec(const InstSeqNum &inst);
223 * Commits all instructions up to and including the given sequence number,
224 * for a specific thread.
226 void commit(const InstSeqNum &inst, ThreadID tid = 0);
228 /** Wakes all dependents of a completed instruction. */
229 int wakeDependents(const DynInstPtr &completed_inst);
231 /** Adds a ready memory instruction to the ready list. */
232 void addReadyMemInst(const DynInstPtr &ready_inst);
235 * Reschedules a memory instruction. It will be ready to issue once
236 * replayMemInst() is called.
238 void rescheduleMemInst(const DynInstPtr &resched_inst);
240 /** Replays a memory instruction. It must be rescheduled first. */
241 void replayMemInst(const DynInstPtr &replay_inst);
244 * Defers a memory instruction when its DTB translation incurs a hw
247 void deferMemInst(const DynInstPtr &deferred_inst);
249 /** Defers a memory instruction when it is cache blocked. */
250 void blockMemInst(const DynInstPtr &blocked_inst);
252 /** Notify instruction queue that a previous blockage has resolved */
253 void cacheUnblocked();
255 /** Indicates an ordering violation between a store and a load. */
256 void violation(const DynInstPtr &store, const DynInstPtr &faulting_load);
259 * Squashes instructions for a thread. Squashing information is obtained
260 * from the time buffer.
262 void squash(ThreadID tid);
264 /** Returns the number of used entries for a thread. */
265 unsigned getCount(ThreadID tid) { return count[tid]; };
267 /** Debug function to print all instructions. */
271 /** Does the actual squashing. */
272 void doSquash(ThreadID tid);
274 /////////////////////////
276 /////////////////////////
278 /** Pointer to the CPU. */
281 /** Cache interface. */
282 MemInterface *dcacheInterface;
284 /** Pointer to IEW stage. */
287 /** The memory dependence unit, which tracks/predicts memory dependences
288 * between instructions.
290 MemDepUnit memDepUnit[Impl::MaxThreads];
292 /** The queue to the execute stage. Issued instructions will be written
295 TimeBuffer<IssueStruct> *issueToExecuteQueue;
297 /** The backwards time buffer. */
298 TimeBuffer<TimeStruct> *timeBuffer;
300 /** Wire to read information from timebuffer. */
301 typename TimeBuffer<TimeStruct>::wire fromCommit;
303 /** Function unit pool. */
306 //////////////////////////////////////
307 // Instruction lists, ready queues, and ordering
308 //////////////////////////////////////
310 /** List of all the instructions in the IQ (some of which may be issued). */
311 std::list<DynInstPtr> instList[Impl::MaxThreads];
313 /** List of instructions that are ready to be executed. */
314 std::list<DynInstPtr> instsToExecute;
316 /** List of instructions waiting for their DTB translation to
317 * complete (hw page table walk in progress).
319 std::list<DynInstPtr> deferredMemInsts;
321 /** List of instructions that have been cache blocked. */
322 std::list<DynInstPtr> blockedMemInsts;
324 /** List of instructions that were cache blocked, but a retry has been seen
325 * since, so they can now be retried. May fail again go on the blocked list.
327 std::list<DynInstPtr> retryMemInsts;
330 * Struct for comparing entries to be added to the priority queue.
331 * This gives reverse ordering to the instructions in terms of
332 * sequence numbers: the instructions with smaller sequence
333 * numbers (and hence are older) will be at the top of the
337 bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
339 return lhs->seqNum > rhs->seqNum;
343 typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
346 /** List of ready instructions, per op class. They are separated by op
347 * class to allow for easy mapping to FUs.
349 ReadyInstQueue readyInsts[Num_OpClasses];
351 /** List of non-speculative instructions that will be scheduled
352 * once the IQ gets a signal from commit. While it's redundant to
353 * have the key be a part of the value (the sequence number is stored
354 * inside of DynInst), when these instructions are woken up only
355 * the sequence number will be available. Thus it is most efficient to be
356 * able to search by the sequence number alone.
358 std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
360 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;
362 /** Entry for the list age ordering by op class. */
363 struct ListOrderEntry {
365 InstSeqNum oldestInst;
368 /** List that contains the age order of the oldest instruction of each
369 * ready queue. Used to select the oldest instruction available
371 * @todo: Might be better to just move these entries around instead
372 * of creating new ones every time the position changes due to an
373 * instruction issuing. Not sure std::list supports this.
375 std::list<ListOrderEntry> listOrder;
377 typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;
379 /** Tracks if each ready queue is on the age order list. */
380 bool queueOnList[Num_OpClasses];
382 /** Iterators of each ready queue. Points to their spot in the age order
385 ListOrderIt readyIt[Num_OpClasses];
387 /** Add an op class to the age order list. */
388 void addToOrderList(OpClass op_class);
391 * Called when the oldest instruction has been removed from a ready queue;
392 * this places that ready queue into the proper spot in the age order list.
394 void moveToYoungerInst(ListOrderIt age_order_it);
396 DependencyGraph<DynInstPtr> dependGraph;
398 //////////////////////////////////////
399 // Various parameters
400 //////////////////////////////////////
402 /** IQ sharing policy for SMT. */
403 SMTQueuePolicy iqPolicy;
405 /** Number of Total Threads*/
408 /** Pointer to list of active threads. */
409 std::list<ThreadID> *activeThreads;
411 /** Per Thread IQ count */
412 unsigned count[Impl::MaxThreads];
414 /** Max IQ Entries Per Thread */
415 unsigned maxEntries[Impl::MaxThreads];
417 /** Number of free IQ entries left. */
418 unsigned freeEntries;
420 /** The number of entries in the instruction queue. */
423 /** The total number of instructions that can be issued in one cycle. */
426 /** The number of physical registers in the CPU. */
427 unsigned numPhysRegs;
429 /** Number of instructions currently in flight to FUs */
432 /** Delay between commit stage and the IQ.
433 * @todo: Make there be a distinction between the delays within IEW.
435 Cycles commitToIEWDelay;
437 /** The sequence number of the squashed instruction. */
438 InstSeqNum squashedSeqNum[Impl::MaxThreads];
440 /** A cache of the recently woken registers. It is 1 if the register
441 * has been woken up recently, and 0 if the register has been added
442 * to the dependency graph and has not yet received its value. It
443 * is basically a secondary scoreboard, and should pretty much mirror
444 * the scoreboard that exists in the rename map.
446 std::vector<bool> regScoreboard;
448 /** Adds an instruction to the dependency graph, as a consumer. */
449 bool addToDependents(const DynInstPtr &new_inst);
451 /** Adds an instruction to the dependency graph, as a producer. */
452 void addToProducers(const DynInstPtr &new_inst);
454 /** Moves an instruction to the ready queue if it is ready. */
455 void addIfReady(const DynInstPtr &inst);
457 /** Debugging function to count how many entries are in the IQ. It does
458 * a linear walk through the instructions, so do not call this function
459 * during normal execution.
463 /** Debugging function to dump all the list sizes, as well as print
464 * out the list of nonspeculative instructions. Should not be used
465 * in any other capacity, but it has no harmful sideaffects.
469 /** Debugging function to dump out all instructions that are in the
474 /** Stat for number of instructions added. */
475 Stats::Scalar iqInstsAdded;
476 /** Stat for number of non-speculative instructions added. */
477 Stats::Scalar iqNonSpecInstsAdded;
479 Stats::Scalar iqInstsIssued;
480 /** Stat for number of integer instructions issued. */
481 Stats::Scalar iqIntInstsIssued;
482 /** Stat for number of floating point instructions issued. */
483 Stats::Scalar iqFloatInstsIssued;
484 /** Stat for number of branch instructions issued. */
485 Stats::Scalar iqBranchInstsIssued;
486 /** Stat for number of memory instructions issued. */
487 Stats::Scalar iqMemInstsIssued;
488 /** Stat for number of miscellaneous instructions issued. */
489 Stats::Scalar iqMiscInstsIssued;
490 /** Stat for number of squashed instructions that were ready to issue. */
491 Stats::Scalar iqSquashedInstsIssued;
492 /** Stat for number of squashed instructions examined when squashing. */
493 Stats::Scalar iqSquashedInstsExamined;
494 /** Stat for number of squashed instruction operands examined when
497 Stats::Scalar iqSquashedOperandsExamined;
498 /** Stat for number of non-speculative instructions removed due to a squash.
500 Stats::Scalar iqSquashedNonSpecRemoved;
501 // Also include number of instructions rescheduled and replayed.
503 /** Distribution of number of instructions in the queue.
504 * @todo: Need to create struct to track the entry time for each
506 // Stats::VectorDistribution queueResDist;
507 /** Distribution of the number of instructions issued. */
508 Stats::Distribution numIssuedDist;
509 /** Distribution of the cycles it takes to issue an instruction.
510 * @todo: Need to create struct to track the ready time for each
512 // Stats::VectorDistribution issueDelayDist;
514 /** Number of times an instruction could not be issued because a
517 Stats::Vector statFuBusy;
518 // Stats::Vector dist_unissued;
519 /** Stat for total number issued for each instruction type. */
520 Stats::Vector2d statIssuedInstType;
522 /** Number of instructions issued per cycle. */
523 Stats::Formula issueRate;
525 /** Number of times the FU was busy. */
526 Stats::Vector fuBusy;
527 /** Number of times the FU was busy per instruction issued. */
528 Stats::Formula fuBusyRate;
530 Stats::Scalar intInstQueueReads;
531 Stats::Scalar intInstQueueWrites;
532 Stats::Scalar intInstQueueWakeupAccesses;
533 Stats::Scalar fpInstQueueReads;
534 Stats::Scalar fpInstQueueWrites;
535 Stats::Scalar fpInstQueueWakeupAccesses;
536 Stats::Scalar vecInstQueueReads;
537 Stats::Scalar vecInstQueueWrites;
538 Stats::Scalar vecInstQueueWakeupAccesses;
540 Stats::Scalar intAluAccesses;
541 Stats::Scalar fpAluAccesses;
542 Stats::Scalar vecAluAccesses;
545 #endif //__CPU_O3_INST_QUEUE_HH__