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