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