inst_queue.hh revision 2665:a124942bacb8
1/*
2 * Copyright (c) 2004-2005 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_CPU_INST_QUEUE_HH__
32#define __CPU_O3_CPU_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 "sim/host.hh"
43
44/**
45 * A standard instruction queue class.  It holds ready instructions, in
46 * order, in seperate priority queues to facilitate the scheduling of
47 * instructions.  The IQ uses a separate linked list to track dependencies.
48 * Similar to the rename map and the free list, it expects that
49 * floating point registers have their indices start after the integer
50 * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
51 * and 96-191 are fp).  This remains true even for both logical and
52 * physical register indices.
53 */
54template <class Impl>
55class InstructionQueue
56{
57  public:
58    //Typedefs from the Impl.
59    typedef typename Impl::FullCPU FullCPU;
60    typedef typename Impl::DynInstPtr DynInstPtr;
61    typedef typename Impl::Params Params;
62
63    typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
64    typedef typename Impl::CPUPol::IssueStruct IssueStruct;
65    typedef typename Impl::CPUPol::TimeStruct TimeStruct;
66
67    // Typedef of iterator through the list of instructions.  Might be
68    // better to untie this from the FullCPU or pass its information to
69    // the stages.
70    typedef typename std::list<DynInstPtr>::iterator ListIt;
71
72    /**
73     * Struct for comparing entries to be added to the priority queue.  This
74     * gives reverse ordering to the instructions in terms of sequence
75     * numbers: the instructions with smaller sequence numbers (and hence
76     * are older) will be at the top of the priority queue.
77     */
78    struct pqCompare
79    {
80        bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
81        {
82            return lhs->seqNum > rhs->seqNum;
83        }
84    };
85
86    /**
87     * Struct for comparing entries to be added to the set.  This gives
88     * standard ordering in terms of sequence numbers.
89     */
90    struct setCompare
91    {
92        bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
93        {
94            return lhs->seqNum < rhs->seqNum;
95        }
96    };
97
98    typedef std::priority_queue<DynInstPtr, vector<DynInstPtr>, pqCompare>
99    ReadyInstQueue;
100
101    InstructionQueue(Params &params);
102
103    void regStats();
104
105    void setCPU(FullCPU *cpu);
106
107    void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);
108
109    void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
110
111    unsigned numFreeEntries();
112
113    bool isFull();
114
115    void insert(DynInstPtr &new_inst);
116
117    void insertNonSpec(DynInstPtr &new_inst);
118
119    void advanceTail(DynInstPtr &inst);
120
121    void scheduleReadyInsts();
122
123    void scheduleNonSpec(const InstSeqNum &inst);
124
125    void wakeDependents(DynInstPtr &completed_inst);
126
127    void violation(DynInstPtr &store, DynInstPtr &faulting_load);
128
129    // Change this to take in the sequence number
130    void squash();
131
132    void doSquash();
133
134    void stopSquash();
135
136  private:
137    /** Pointer to the CPU. */
138    FullCPU *cpu;
139
140    /** The memory dependence unit, which tracks/predicts memory dependences
141     *  between instructions.
142     */
143    MemDepUnit memDepUnit;
144
145    /** The queue to the execute stage.  Issued instructions will be written
146     *  into it.
147     */
148    TimeBuffer<IssueStruct> *issueToExecuteQueue;
149
150    /** The backwards time buffer. */
151    TimeBuffer<TimeStruct> *timeBuffer;
152
153    /** Wire to read information from timebuffer. */
154    typename TimeBuffer<TimeStruct>::wire fromCommit;
155
156    enum InstList {
157        Int,
158        Float,
159        Branch,
160        Memory,
161        Misc,
162        Squashed,
163        None
164    };
165
166    /** List of ready int instructions.  Used to keep track of the order in
167     *  which instructions should issue.
168     */
169    ReadyInstQueue readyIntInsts;
170
171    /** List of ready floating point instructions. */
172    ReadyInstQueue readyFloatInsts;
173
174    /** List of ready branch instructions. */
175    ReadyInstQueue readyBranchInsts;
176
177    /** List of ready miscellaneous instructions. */
178    ReadyInstQueue readyMiscInsts;
179
180    /** List of squashed instructions (which are still valid and in IQ).
181     *  Implemented using a priority queue; the entries must contain both
182     *  the IQ index and sequence number of each instruction so that
183     *  ordering based on sequence numbers can be used.
184     */
185    ReadyInstQueue squashedInsts;
186
187    /** List of non-speculative instructions that will be scheduled
188     *  once the IQ gets a signal from commit.  While it's redundant to
189     *  have the key be a part of the value (the sequence number is stored
190     *  inside of DynInst), when these instructions are woken up only
191     *  the sequence number will be available.  Thus it is most efficient to be
192     *  able to search by the sequence number alone.
193     */
194    std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
195
196    typedef typename std::map<InstSeqNum, DynInstPtr>::iterator non_spec_it_t;
197
198    /** Number of free IQ entries left. */
199    unsigned freeEntries;
200
201    /** The number of entries in the instruction queue. */
202    unsigned numEntries;
203
204    /** The number of integer instructions that can be issued in one
205     *  cycle.
206     */
207    unsigned intWidth;
208
209    /** The number of floating point instructions that can be issued
210     *  in one cycle.
211     */
212    unsigned floatWidth;
213
214    /** The number of branches that can be issued in one cycle. */
215    unsigned branchWidth;
216
217    /** The number of memory instructions that can be issued in one cycle. */
218    unsigned memoryWidth;
219
220    /** The total number of instructions that can be issued in one cycle. */
221    unsigned totalWidth;
222
223    //The number of physical registers in the CPU.
224    unsigned numPhysRegs;
225
226    /** The number of physical integer registers in the CPU. */
227    unsigned numPhysIntRegs;
228
229    /** The number of floating point registers in the CPU. */
230    unsigned numPhysFloatRegs;
231
232    /** Delay between commit stage and the IQ.
233     *  @todo: Make there be a distinction between the delays within IEW.
234     */
235    unsigned commitToIEWDelay;
236
237    //////////////////////////////////
238    // Variables needed for squashing
239    //////////////////////////////////
240
241    /** The sequence number of the squashed instruction. */
242    InstSeqNum squashedSeqNum;
243
244    /** Iterator that points to the youngest instruction in the IQ. */
245    ListIt tail;
246
247    /** Iterator that points to the last instruction that has been squashed.
248     *  This will not be valid unless the IQ is in the process of squashing.
249     */
250    ListIt squashIt;
251
252    ///////////////////////////////////
253    // Dependency graph stuff
254    ///////////////////////////////////
255
256    class DependencyEntry
257    {
258      public:
259        DynInstPtr inst;
260        //Might want to include data about what arch. register the
261        //dependence is waiting on.
262        DependencyEntry *next;
263
264        //This function, and perhaps this whole class, stand out a little
265        //bit as they don't fit a classification well.  I want access
266        //to the underlying structure of the linked list, yet at
267        //the same time it feels like this should be something abstracted
268        //away.  So for now it will sit here, within the IQ, until
269        //a better implementation is decided upon.
270        // This function probably shouldn't be within the entry...
271        void insert(DynInstPtr &new_inst);
272
273        void remove(DynInstPtr &inst_to_remove);
274
275        // Debug variable, remove when done testing.
276        static unsigned mem_alloc_counter;
277    };
278
279    /** Array of linked lists.  Each linked list is a list of all the
280     *  instructions that depend upon a given register.  The actual
281     *  register's index is used to index into the graph; ie all
282     *  instructions in flight that are dependent upon r34 will be
283     *  in the linked list of dependGraph[34].
284     */
285    DependencyEntry *dependGraph;
286
287    /** A cache of the recently woken registers.  It is 1 if the register
288     *  has been woken up recently, and 0 if the register has been added
289     *  to the dependency graph and has not yet received its value.  It
290     *  is basically a secondary scoreboard, and should pretty much mirror
291     *  the scoreboard that exists in the rename map.
292     */
293    vector<bool> regScoreboard;
294
295    bool addToDependents(DynInstPtr &new_inst);
296    void insertDependency(DynInstPtr &new_inst);
297    void createDependency(DynInstPtr &new_inst);
298
299    void addIfReady(DynInstPtr &inst);
300
301  private:
302    /** Debugging function to count how many entries are in the IQ.  It does
303     *  a linear walk through the instructions, so do not call this function
304     *  during normal execution.
305     */
306    int countInsts();
307
308    /** Debugging function to dump out the dependency graph.
309     */
310    void dumpDependGraph();
311
312    /** Debugging function to dump all the list sizes, as well as print
313     *  out the list of nonspeculative instructions.  Should not be used
314     *  in any other capacity, but it has no harmful sideaffects.
315     */
316    void dumpLists();
317
318    Stats::Scalar<> iqInstsAdded;
319    Stats::Scalar<> iqNonSpecInstsAdded;
320//    Stats::Scalar<> iqIntInstsAdded;
321    Stats::Scalar<> iqIntInstsIssued;
322//    Stats::Scalar<> iqFloatInstsAdded;
323    Stats::Scalar<> iqFloatInstsIssued;
324//    Stats::Scalar<> iqBranchInstsAdded;
325    Stats::Scalar<> iqBranchInstsIssued;
326//    Stats::Scalar<> iqMemInstsAdded;
327    Stats::Scalar<> iqMemInstsIssued;
328//    Stats::Scalar<> iqMiscInstsAdded;
329    Stats::Scalar<> iqMiscInstsIssued;
330    Stats::Scalar<> iqSquashedInstsIssued;
331    Stats::Scalar<> iqLoopSquashStalls;
332    Stats::Scalar<> iqSquashedInstsExamined;
333    Stats::Scalar<> iqSquashedOperandsExamined;
334    Stats::Scalar<> iqSquashedNonSpecRemoved;
335
336};
337
338#endif //__CPU_O3_CPU_INST_QUEUE_HH__
339