inst_queue.hh revision 1684 
1#ifndef __CPU_BETA_CPU_INST_QUEUE_HH__
2#define __CPU_BETA_CPU_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  private:
107    /** Pointer to the CPU. */
108    FullCPU *cpu;
109
110    /** The memory dependence unit, which tracks/predicts memory dependences
111     *  between instructions.
112     */
113    MemDepUnit memDepUnit;
114
115    /** The queue to the execute stage.  Issued instructions will be written
116     *  into it.
117     */
118    TimeBuffer<IssueStruct> *issueToExecuteQueue;
119
120    /** The backwards time buffer. */
121    TimeBuffer<TimeStruct> *timeBuffer;
122
123    /** Wire to read information from timebuffer. */
124    typename TimeBuffer<TimeStruct>::wire fromCommit;
125
126    enum InstList {
127        Int,
128        Float,
129        Branch,
130        Memory,
131        Misc,
132        Squashed,
133        None
134    };
135
136    /** List of ready int instructions.  Used to keep track of the order in
137     *  which instructions should issue.
138     */
139    ReadyInstQueue readyIntInsts;
140
141    /** List of ready floating point instructions. */
142    ReadyInstQueue readyFloatInsts;
143
144    /** List of ready branch instructions. */
145    ReadyInstQueue readyBranchInsts;
146
147    /** List of ready miscellaneous instructions. */
148    ReadyInstQueue readyMiscInsts;
149
150    /** List of squashed instructions (which are still valid and in IQ).
151     *  Implemented using a priority queue; the entries must contain both
152     *  the IQ index and sequence number of each instruction so that
153     *  ordering based on sequence numbers can be used.
154     */
155    ReadyInstQueue squashedInsts;
156
157    /** List of non-speculative instructions that will be scheduled
158     *  once the IQ gets a signal from commit.  While it's redundant to
159     *  have the key be a part of the value (the sequence number is stored
160     *  inside of DynInst), when these instructions are woken up only
161     *  the sequence number will be available.  Thus it is most efficient to be
162     *  able to search by the sequence number alone.
163     */
164    std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
165
166    typedef typename std::map<InstSeqNum, DynInstPtr>::iterator non_spec_it_t;
167
168    /** Number of free IQ entries left. */
169    unsigned freeEntries;
170
171    /** The number of entries in the instruction queue. */
172    unsigned numEntries;
173
174    /** The number of integer instructions that can be issued in one
175     *  cycle.
176     */
177    unsigned intWidth;
178
179    /** The number of floating point instructions that can be issued
180     *  in one cycle.
181     */
182    unsigned floatWidth;
183
184    /** The number of branches that can be issued in one cycle. */
185    unsigned branchWidth;
186
187    /** The number of memory instructions that can be issued in one cycle. */
188    unsigned memoryWidth;
189
190    /** The total number of instructions that can be issued in one cycle. */
191    unsigned totalWidth;
192
193    //The number of physical registers in the CPU.
194    unsigned numPhysRegs;
195
196    /** The number of physical integer registers in the CPU. */
197    unsigned numPhysIntRegs;
198
199    /** The number of floating point registers in the CPU. */
200    unsigned numPhysFloatRegs;
201
202    /** Delay between commit stage and the IQ.
203     *  @todo: Make there be a distinction between the delays within IEW.
204     */
205    unsigned commitToIEWDelay;
206
207    //////////////////////////////////
208    // Variables needed for squashing
209    //////////////////////////////////
210
211    /** The sequence number of the squashed instruction. */
212    InstSeqNum squashedSeqNum;
213
214    /** Iterator that points to the youngest instruction in the IQ. */
215    ListIt tail;
216
217    /** Iterator that points to the last instruction that has been squashed.
218     *  This will not be valid unless the IQ is in the process of squashing.
219     */
220    ListIt squashIt;
221
222    ///////////////////////////////////
223    // Dependency graph stuff
224    ///////////////////////////////////
225
226    class DependencyEntry
227    {
228      public:
229        DynInstPtr inst;
230        //Might want to include data about what arch. register the
231        //dependence is waiting on.
232        DependencyEntry *next;
233
234        //This function, and perhaps this whole class, stand out a little
235        //bit as they don't fit a classification well.  I want access
236        //to the underlying structure of the linked list, yet at
237        //the same time it feels like this should be something abstracted
238        //away.  So for now it will sit here, within the IQ, until
239        //a better implementation is decided upon.
240        // This function probably shouldn't be within the entry...
241        void insert(DynInstPtr &new_inst);
242
243        void remove(DynInstPtr &inst_to_remove);
244
245        // Debug variable, remove when done testing.
246        static unsigned mem_alloc_counter;
247    };
248
249    /** Array of linked lists.  Each linked list is a list of all the
250     *  instructions that depend upon a given register.  The actual
251     *  register's index is used to index into the graph; ie all
252     *  instructions in flight that are dependent upon r34 will be
253     *  in the linked list of dependGraph[34].
254     */
255    DependencyEntry *dependGraph;
256
257    /** A cache of the recently woken registers.  It is 1 if the register
258     *  has been woken up recently, and 0 if the register has been added
259     *  to the dependency graph and has not yet received its value.  It
260     *  is basically a secondary scoreboard, and should pretty much mirror
261     *  the scoreboard that exists in the rename map.
262     */
263    vector<bool> regScoreboard;
264
265    bool addToDependents(DynInstPtr &new_inst);
266    void insertDependency(DynInstPtr &new_inst);
267    void createDependency(DynInstPtr &new_inst);
268
269    void addIfReady(DynInstPtr &inst);
270
271  private:
272    /** Debugging function to count how many entries are in the IQ.  It does
273     *  a linear walk through the instructions, so do not call this function
274     *  during normal execution.
275     */
276    int countInsts();
277
278    /** Debugging function to dump out the dependency graph.
279     */
280    void dumpDependGraph();
281
282    /** Debugging function to dump all the list sizes, as well as print
283     *  out the list of nonspeculative instructions.  Should not be used
284     *  in any other capacity, but it has no harmful sideaffects.
285     */
286    void dumpLists();
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 //__CPU_BETA_CPU_INST_QUEUE_HH__
309