inst_queue.hh revision 1060 
1#ifndef __INST_QUEUE_HH__
2#define __INST_QUEUE_HH__
3
4#include <list>
5#include <queue>
6#include <stdint.h>
7
8#include "base/timebuf.hh"
9
10using namespace std;
11
12//Perhaps have a better separation between the data structure underlying
13//and the actual algorithm.
14//somewhat nasty to try to have a nice ordering.
15// Consider moving to STL list or slist for the LL stuff.
16
17/**
18 * A standard instruction queue class.  It holds instructions in an
19 * array, holds the ordering of the instructions within a linked list,
20 * and tracks producer/consumer dependencies within a separate linked
21 * list.  Similar to the rename map and the free list, it expects that
22 * floating point registers have their indices start after the integer
23 * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
24 * and 96-191 are fp).  This remains true even for both logical and
25 * physical register indices.
26 */
27template<class Impl>
28class InstructionQueue
29{
30  public:
31    //Typedefs from the Impl.
32    typedef typename Impl::FullCPU FullCPU;
33    typedef typename Impl::DynInst DynInst;
34    typedef typename Impl::Params Params;
35
36    typedef typename Impl::IssueStruct IssueStruct;
37    typedef typename Impl::TimeStruct TimeStruct;
38
39    // Typedef of iterator through the list of instructions.  Might be
40    // better to untie this from the FullCPU or pass its information to
41    // the stages.
42    typedef typename list<DynInst *>::iterator ListIt;
43
44    /**
45     * Class for priority queue entries.  Mainly made so that the < operator
46     * is defined.
47     */
48    struct ReadyEntry {
49        DynInst *inst;
50
51        ReadyEntry(DynInst *_inst)
52            : inst(_inst)
53        { }
54
55        /** Compare(lhs,rhs) checks if rhs is "bigger" than lhs.  If so, rhs
56         *  goes higher on the priority queue.  The oldest instruction should
57         *  be on the top of the instruction queue, so in this case "bigger"
58         *  has the reverse meaning; the instruction with the lowest
59         *  sequence number is on the top.
60         */
61        bool operator <(const ReadyEntry &rhs) const
62        {
63            if (this->inst->seqNum > rhs.inst->seqNum)
64                return true;
65            return false;
66        }
67    };
68
69    InstructionQueue(Params &params);
70
71    void setCPU(FullCPU *cpu);
72
73    void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);
74
75    void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
76
77    unsigned numFreeEntries();
78
79    bool isFull();
80
81    void insert(DynInst *new_inst);
82
83    void advanceTail(DynInst *inst);
84
85    void scheduleReadyInsts();
86
87    void wakeDependents(DynInst *completed_inst);
88
89    void doSquash();
90
91    void squash();
92
93    void stopSquash();
94
95  private:
96    /** Debugging function to count how many entries are in the IQ.  It does
97     *  a linear walk through the instructions, so do not call this function
98     *  during normal execution.
99     */
100    int countInsts();
101
102  private:
103    /** Pointer to the CPU. */
104    FullCPU *cpu;
105
106    /** The queue to the execute stage.  Issued instructions will be written
107     *  into it.
108     */
109    TimeBuffer<IssueStruct> *issueToExecuteQueue;
110
111    /** The backwards time buffer. */
112    TimeBuffer<TimeStruct> *timeBuffer;
113
114    /** Wire to read information from timebuffer. */
115    typename TimeBuffer<TimeStruct>::wire fromCommit;
116
117    enum InstList {
118        Int,
119        Float,
120        Branch,
121        Squashed,
122        None
123    };
124
125    /** List of ready int instructions.  Used to keep track of the order in
126     *  which */
127    priority_queue<ReadyEntry> readyIntInsts;
128
129    /** List of ready floating point instructions. */
130    priority_queue<ReadyEntry> readyFloatInsts;
131
132    /** List of ready branch instructions. */
133    priority_queue<ReadyEntry> readyBranchInsts;
134
135    /** List of squashed instructions (which are still valid and in IQ).
136     *  Implemented using a priority queue; the entries must contain both
137     *  the IQ index and sequence number of each instruction so that
138     *  ordering based on sequence numbers can be used.
139     */
140    priority_queue<ReadyEntry> squashedInsts;
141
142    /** Number of free IQ entries left. */
143    unsigned freeEntries;
144
145    /** The number of entries in the instruction queue. */
146    unsigned numEntries;
147
148    /** The number of integer instructions that can be issued in one
149     *  cycle.
150     */
151    unsigned intWidth;
152
153    /** The number of floating point instructions that can be issued
154     *  in one cycle.
155     */
156    unsigned floatWidth;
157
158    /** The number of branches that can be issued in one cycle. */
159    unsigned branchWidth;
160
161    /** The total number of instructions that can be issued in one cycle. */
162    unsigned totalWidth;
163
164    //The number of physical registers in the CPU.
165    unsigned numPhysRegs;
166
167    /** The number of physical integer registers in the CPU. */
168    unsigned numPhysIntRegs;
169
170    /** The number of floating point registers in the CPU. */
171    unsigned numPhysFloatRegs;
172
173    /** Delay between commit stage and the IQ.
174     *  @todo: Make there be a distinction between the delays within IEW.
175     */
176    unsigned commitToIEWDelay;
177
178    //////////////////////////////////
179    // Variables needed for squashing
180    //////////////////////////////////
181
182    /** The sequence number of the squashed instruction. */
183    InstSeqNum squashedSeqNum;
184
185    /** Iterator that points to the oldest instruction in the IQ. */
186    ListIt head;
187
188    /** Iterator that points to the youngest instruction in the IQ. */
189    ListIt tail;
190
191    /** Iterator that points to the last instruction that has been squashed.
192     *  This will not be valid unless the IQ is in the process of squashing.
193     */
194    ListIt squashIt;
195
196    ///////////////////////////////////
197    // Dependency graph stuff
198    ///////////////////////////////////
199
200    class DependencyEntry
201    {
202      public:
203        DynInst *inst;
204        //Might want to include data about what arch. register the
205        //dependence is waiting on.
206        DependencyEntry *next;
207
208        //This function, and perhaps this whole class, stand out a little
209        //bit as they don't fit a classification well.  I want access
210        //to the underlying structure of the linked list, yet at
211        //the same time it feels like this should be something abstracted
212        //away.  So for now it will sit here, within the IQ, until
213        //a better implementation is decided upon.
214        // This function probably shouldn't be within the entry...
215        void insert(DynInst *new_inst);
216
217        void remove(DynInst *inst_to_remove);
218    };
219
220    /** Array of linked lists.  Each linked list is a list of all the
221     *  instructions that depend upon a given register.  The actual
222     *  register's index is used to index into the graph; ie all
223     *  instructions in flight that are dependent upon r34 will be
224     *  in the linked list of dependGraph[34].
225     */
226    DependencyEntry *dependGraph;
227
228    /** A cache of the recently woken registers.  It is 1 if the register
229     *  has been woken up recently, and 0 if the register has been added
230     *  to the dependency graph and has not yet received its value.  It
231     *  is basically a secondary scoreboard, and should pretty much mirror
232     *  the scoreboard that exists in the rename map.
233     */
234    vector<bool> regScoreboard;
235
236    bool addToDependents(DynInst *new_inst);
237    void insertDependency(DynInst *new_inst);
238    void createDependency(DynInst *new_inst);
239
240    void addIfReady(DynInst *inst);
241};
242
243#endif //__INST_QUEUE_HH__
244