2 * Copyright (c) 2004-2006 The Regents of The University of Michigan
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.
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.
29 #ifndef __CPU_O3_INST_QUEUE_HH__
30 #define __CPU_O3_INST_QUEUE_HH__
37 #include "base/statistics.hh"
38 #include "base/timebuf.hh"
39 #include "cpu/inst_seq.hh"
40 #include "cpu/o3/dep_graph.hh"
41 #include "encumbered/cpu/full/op_class.hh"
42 #include "sim/host.hh"
48 * A standard instruction queue class. It holds ready instructions, in
49 * order, in seperate priority queues to facilitate the scheduling of
50 * instructions. The IQ uses a separate linked list to track dependencies.
51 * Similar to the rename map and the free list, it expects that
52 * floating point registers have their indices start after the integer
53 * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
54 * and 96-191 are fp). This remains true even for both logical and
55 * physical register indices. The IQ depends on the memory dependence unit to
56 * track when memory operations are ready in terms of ordering; register
57 * dependencies are tracked normally. Right now the IQ also handles the
58 * execution timing; this is mainly to allow back-to-back scheduling without
59 * requiring IEW to be able to peek into the IQ. At the end of the execution
60 * latency, the instruction is put into the queue to execute, where it will
61 * have the execute() function called on it.
62 * @todo: Make IQ able to handle multiple FU pools.
65 class InstructionQueue
68 //Typedefs from the Impl.
69 typedef typename Impl::FullCPU FullCPU;
70 typedef typename Impl::DynInstPtr DynInstPtr;
71 typedef typename Impl::Params Params;
73 typedef typename Impl::CPUPol::IEW IEW;
74 typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
75 typedef typename Impl::CPUPol::IssueStruct IssueStruct;
76 typedef typename Impl::CPUPol::TimeStruct TimeStruct;
78 // Typedef of iterator through the list of instructions.
79 typedef typename std::list<DynInstPtr>::iterator ListIt;
81 friend class Impl::FullCPU;
83 /** FU completion event class. */
84 class FUCompletion : public Event {
86 /** Executing instruction. */
89 /** Index of the FU used for executing. */
92 /** Pointer back to the instruction queue. */
93 InstructionQueue<Impl> *iqPtr;
98 /** Construct a FU completion event. */
99 FUCompletion(DynInstPtr &_inst, int fu_idx,
100 InstructionQueue<Impl> *iq_ptr);
102 virtual void process();
103 virtual const char *description();
104 void setFreeFU() { freeFU = true; }
107 /** Constructs an IQ. */
108 InstructionQueue(Params *params);
110 /** Destructs the IQ. */
113 /** Returns the name of the IQ. */
114 std::string name() const;
116 /** Registers statistics. */
121 /** Sets CPU pointer. */
122 void setCPU(FullCPU *_cpu) { cpu = _cpu; }
124 /** Sets active threads list. */
125 void setActiveThreads(std::list<unsigned> *at_ptr);
127 /** Sets the IEW pointer. */
128 void setIEW(IEW *iew_ptr) { iewStage = iew_ptr; }
130 /** Sets the timer buffer between issue and execute. */
131 void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);
133 /** Sets the global time buffer. */
134 void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
140 bool isSwitchedOut() { return switchedOut; }
142 /** Number of entries needed for given amount of threads. */
143 int entryAmount(int num_threads);
145 /** Resets max entries for all threads. */
148 /** Returns total number of free entries. */
149 unsigned numFreeEntries();
151 /** Returns number of free entries for a thread. */
152 unsigned numFreeEntries(unsigned tid);
154 /** Returns whether or not the IQ is full. */
157 /** Returns whether or not the IQ is full for a specific thread. */
158 bool isFull(unsigned tid);
160 /** Returns if there are any ready instructions in the IQ. */
161 bool hasReadyInsts();
163 /** Inserts a new instruction into the IQ. */
164 void insert(DynInstPtr &new_inst);
166 /** Inserts a new, non-speculative instruction into the IQ. */
167 void insertNonSpec(DynInstPtr &new_inst);
169 /** Inserts a memory or write barrier into the IQ to make sure
170 * loads and stores are ordered properly.
172 void insertBarrier(DynInstPtr &barr_inst);
175 * Records the instruction as the producer of a register without
176 * adding it to the rest of the IQ.
178 void recordProducer(DynInstPtr &inst)
179 { addToProducers(inst); }
181 /** Process FU completion event. */
182 void processFUCompletion(DynInstPtr &inst, int fu_idx);
185 * Schedules ready instructions, adding the ready ones (oldest first) to
186 * the queue to execute.
188 void scheduleReadyInsts();
190 /** Schedules a single specific non-speculative instruction. */
191 void scheduleNonSpec(const InstSeqNum &inst);
194 * Commits all instructions up to and including the given sequence number,
195 * for a specific thread.
197 void commit(const InstSeqNum &inst, unsigned tid = 0);
199 /** Wakes all dependents of a completed instruction. */
200 int wakeDependents(DynInstPtr &completed_inst);
202 /** Adds a ready memory instruction to the ready list. */
203 void addReadyMemInst(DynInstPtr &ready_inst);
206 * Reschedules a memory instruction. It will be ready to issue once
207 * replayMemInst() is called.
209 void rescheduleMemInst(DynInstPtr &resched_inst);
211 /** Replays a memory instruction. It must be rescheduled first. */
212 void replayMemInst(DynInstPtr &replay_inst);
214 /** Completes a memory operation. */
215 void completeMemInst(DynInstPtr &completed_inst);
217 /** Indicates an ordering violation between a store and a load. */
218 void violation(DynInstPtr &store, DynInstPtr &faulting_load);
221 * Squashes instructions for a thread. Squashing information is obtained
222 * from the time buffer.
224 void squash(unsigned tid);
226 /** Returns the number of used entries for a thread. */
227 unsigned getCount(unsigned tid) { return count[tid]; };
229 /** Debug function to print all instructions. */
233 /** Does the actual squashing. */
234 void doSquash(unsigned tid);
236 /////////////////////////
238 /////////////////////////
240 /** Pointer to the CPU. */
243 /** Cache interface. */
244 MemInterface *dcacheInterface;
246 /** Pointer to IEW stage. */
249 /** The memory dependence unit, which tracks/predicts memory dependences
250 * between instructions.
252 MemDepUnit memDepUnit[Impl::MaxThreads];
254 /** The queue to the execute stage. Issued instructions will be written
257 TimeBuffer<IssueStruct> *issueToExecuteQueue;
259 /** The backwards time buffer. */
260 TimeBuffer<TimeStruct> *timeBuffer;
262 /** Wire to read information from timebuffer. */
263 typename TimeBuffer<TimeStruct>::wire fromCommit;
265 /** Function unit pool. */
268 //////////////////////////////////////
269 // Instruction lists, ready queues, and ordering
270 //////////////////////////////////////
272 /** List of all the instructions in the IQ (some of which may be issued). */
273 std::list<DynInstPtr> instList[Impl::MaxThreads];
276 * Struct for comparing entries to be added to the priority queue. This
277 * gives reverse ordering to the instructions in terms of sequence
278 * numbers: the instructions with smaller sequence numbers (and hence
279 * are older) will be at the top of the priority queue.
282 bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
284 return lhs->seqNum > rhs->seqNum;
288 typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
291 /** List of ready instructions, per op class. They are separated by op
292 * class to allow for easy mapping to FUs.
294 ReadyInstQueue readyInsts[Num_OpClasses];
296 /** List of non-speculative instructions that will be scheduled
297 * once the IQ gets a signal from commit. While it's redundant to
298 * have the key be a part of the value (the sequence number is stored
299 * inside of DynInst), when these instructions are woken up only
300 * the sequence number will be available. Thus it is most efficient to be
301 * able to search by the sequence number alone.
303 std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
305 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;
307 /** Entry for the list age ordering by op class. */
308 struct ListOrderEntry {
310 InstSeqNum oldestInst;
313 /** List that contains the age order of the oldest instruction of each
314 * ready queue. Used to select the oldest instruction available
316 * @todo: Might be better to just move these entries around instead
317 * of creating new ones every time the position changes due to an
318 * instruction issuing. Not sure std::list supports this.
320 std::list<ListOrderEntry> listOrder;
322 typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;
324 /** Tracks if each ready queue is on the age order list. */
325 bool queueOnList[Num_OpClasses];
327 /** Iterators of each ready queue. Points to their spot in the age order
330 ListOrderIt readyIt[Num_OpClasses];
332 /** Add an op class to the age order list. */
333 void addToOrderList(OpClass op_class);
336 * Called when the oldest instruction has been removed from a ready queue;
337 * this places that ready queue into the proper spot in the age order list.
339 void moveToYoungerInst(ListOrderIt age_order_it);
341 DependencyGraph<DynInstPtr> dependGraph;
343 //////////////////////////////////////
344 // Various parameters
345 //////////////////////////////////////
347 /** IQ Resource Sharing Policy */
354 /** IQ sharing policy for SMT. */
357 /** Number of Total Threads*/
360 /** Pointer to list of active threads. */
361 std::list<unsigned> *activeThreads;
363 /** Per Thread IQ count */
364 unsigned count[Impl::MaxThreads];
366 /** Max IQ Entries Per Thread */
367 unsigned maxEntries[Impl::MaxThreads];
369 /** Number of free IQ entries left. */
370 unsigned freeEntries;
372 /** The number of entries in the instruction queue. */
375 /** The total number of instructions that can be issued in one cycle. */
378 /** The number of physical registers in the CPU. */
379 unsigned numPhysRegs;
381 /** The number of physical integer registers in the CPU. */
382 unsigned numPhysIntRegs;
384 /** The number of floating point registers in the CPU. */
385 unsigned numPhysFloatRegs;
387 /** Delay between commit stage and the IQ.
388 * @todo: Make there be a distinction between the delays within IEW.
390 unsigned commitToIEWDelay;
394 /** The sequence number of the squashed instruction. */
395 InstSeqNum squashedSeqNum[Impl::MaxThreads];
397 /** A cache of the recently woken registers. It is 1 if the register
398 * has been woken up recently, and 0 if the register has been added
399 * to the dependency graph and has not yet received its value. It
400 * is basically a secondary scoreboard, and should pretty much mirror
401 * the scoreboard that exists in the rename map.
403 std::vector<bool> regScoreboard;
405 /** Adds an instruction to the dependency graph, as a consumer. */
406 bool addToDependents(DynInstPtr &new_inst);
408 /** Adds an instruction to the dependency graph, as a producer. */
409 void addToProducers(DynInstPtr &new_inst);
411 /** Moves an instruction to the ready queue if it is ready. */
412 void addIfReady(DynInstPtr &inst);
414 /** Debugging function to count how many entries are in the IQ. It does
415 * a linear walk through the instructions, so do not call this function
416 * during normal execution.
420 /** Debugging function to dump all the list sizes, as well as print
421 * out the list of nonspeculative instructions. Should not be used
422 * in any other capacity, but it has no harmful sideaffects.
426 /** Debugging function to dump out all instructions that are in the
431 /** Stat for number of instructions added. */
432 Stats::Scalar<> iqInstsAdded;
433 /** Stat for number of non-speculative instructions added. */
434 Stats::Scalar<> iqNonSpecInstsAdded;
436 Stats::Scalar<> iqInstsIssued;
437 /** Stat for number of integer instructions issued. */
438 Stats::Scalar<> iqIntInstsIssued;
439 /** Stat for number of floating point instructions issued. */
440 Stats::Scalar<> iqFloatInstsIssued;
441 /** Stat for number of branch instructions issued. */
442 Stats::Scalar<> iqBranchInstsIssued;
443 /** Stat for number of memory instructions issued. */
444 Stats::Scalar<> iqMemInstsIssued;
445 /** Stat for number of miscellaneous instructions issued. */
446 Stats::Scalar<> iqMiscInstsIssued;
447 /** Stat for number of squashed instructions that were ready to issue. */
448 Stats::Scalar<> iqSquashedInstsIssued;
449 /** Stat for number of squashed instructions examined when squashing. */
450 Stats::Scalar<> iqSquashedInstsExamined;
451 /** Stat for number of squashed instruction operands examined when
454 Stats::Scalar<> iqSquashedOperandsExamined;
455 /** Stat for number of non-speculative instructions removed due to a squash.
457 Stats::Scalar<> iqSquashedNonSpecRemoved;
459 Stats::VectorDistribution<> queueResDist;
460 Stats::Distribution<> numIssuedDist;
461 Stats::VectorDistribution<> issueDelayDist;
463 Stats::Vector<> statFuBusy;
464 // Stats::Vector<> dist_unissued;
465 Stats::Vector2d<> statIssuedInstType;
467 Stats::Formula issueRate;
468 // Stats::Formula issue_stores;
469 // Stats::Formula issue_op_rate;
470 Stats::Vector<> fuBusy; //cumulative fu busy
472 Stats::Formula fuBusyRate;
475 #endif //__CPU_O3_INST_QUEUE_HH__