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