inst_queue.hh revision 10511
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    /** Determine if we are drained. */
149    bool isDrained() const;
150
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    /** Number of instructions currently in flight to FUs */
441    int wbOutstanding;
442
443    /** Delay between commit stage and the IQ.
444     *  @todo: Make there be a distinction between the delays within IEW.
445     */
446    Cycles commitToIEWDelay;
447
448    /** The sequence number of the squashed instruction. */
449    InstSeqNum squashedSeqNum[Impl::MaxThreads];
450
451    /** A cache of the recently woken registers.  It is 1 if the register
452     *  has been woken up recently, and 0 if the register has been added
453     *  to the dependency graph and has not yet received its value.  It
454     *  is basically a secondary scoreboard, and should pretty much mirror
455     *  the scoreboard that exists in the rename map.
456     */
457    std::vector<bool> regScoreboard;
458
459    /** Adds an instruction to the dependency graph, as a consumer. */
460    bool addToDependents(DynInstPtr &new_inst);
461
462    /** Adds an instruction to the dependency graph, as a producer. */
463    void addToProducers(DynInstPtr &new_inst);
464
465    /** Moves an instruction to the ready queue if it is ready. */
466    void addIfReady(DynInstPtr &inst);
467
468    /** Debugging function to count how many entries are in the IQ.  It does
469     *  a linear walk through the instructions, so do not call this function
470     *  during normal execution.
471     */
472    int countInsts();
473
474    /** Debugging function to dump all the list sizes, as well as print
475     *  out the list of nonspeculative instructions.  Should not be used
476     *  in any other capacity, but it has no harmful sideaffects.
477     */
478    void dumpLists();
479
480    /** Debugging function to dump out all instructions that are in the
481     *  IQ.
482     */
483    void dumpInsts();
484
485    /** Stat for number of instructions added. */
486    Stats::Scalar iqInstsAdded;
487    /** Stat for number of non-speculative instructions added. */
488    Stats::Scalar iqNonSpecInstsAdded;
489
490    Stats::Scalar iqInstsIssued;
491    /** Stat for number of integer instructions issued. */
492    Stats::Scalar iqIntInstsIssued;
493    /** Stat for number of floating point instructions issued. */
494    Stats::Scalar iqFloatInstsIssued;
495    /** Stat for number of branch instructions issued. */
496    Stats::Scalar iqBranchInstsIssued;
497    /** Stat for number of memory instructions issued. */
498    Stats::Scalar iqMemInstsIssued;
499    /** Stat for number of miscellaneous instructions issued. */
500    Stats::Scalar iqMiscInstsIssued;
501    /** Stat for number of squashed instructions that were ready to issue. */
502    Stats::Scalar iqSquashedInstsIssued;
503    /** Stat for number of squashed instructions examined when squashing. */
504    Stats::Scalar iqSquashedInstsExamined;
505    /** Stat for number of squashed instruction operands examined when
506     * squashing.
507     */
508    Stats::Scalar iqSquashedOperandsExamined;
509    /** Stat for number of non-speculative instructions removed due to a squash.
510     */
511    Stats::Scalar iqSquashedNonSpecRemoved;
512    // Also include number of instructions rescheduled and replayed.
513
514    /** Distribution of number of instructions in the queue.
515     * @todo: Need to create struct to track the entry time for each
516     * instruction. */
517//    Stats::VectorDistribution queueResDist;
518    /** Distribution of the number of instructions issued. */
519    Stats::Distribution numIssuedDist;
520    /** Distribution of the cycles it takes to issue an instruction.
521     * @todo: Need to create struct to track the ready time for each
522     * instruction. */
523//    Stats::VectorDistribution issueDelayDist;
524
525    /** Number of times an instruction could not be issued because a
526     * FU was busy.
527     */
528    Stats::Vector statFuBusy;
529//    Stats::Vector dist_unissued;
530    /** Stat for total number issued for each instruction type. */
531    Stats::Vector2d statIssuedInstType;
532
533    /** Number of instructions issued per cycle. */
534    Stats::Formula issueRate;
535
536    /** Number of times the FU was busy. */
537    Stats::Vector fuBusy;
538    /** Number of times the FU was busy per instruction issued. */
539    Stats::Formula fuBusyRate;
540   public:
541    Stats::Scalar intInstQueueReads;
542    Stats::Scalar intInstQueueWrites;
543    Stats::Scalar intInstQueueWakeupAccesses;
544    Stats::Scalar fpInstQueueReads;
545    Stats::Scalar fpInstQueueWrites;
546    Stats::Scalar fpInstQueueWakeupQccesses;
547
548    Stats::Scalar intAluAccesses;
549    Stats::Scalar fpAluAccesses;
550};
551
552#endif //__CPU_O3_INST_QUEUE_HH__
553