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

--- 10 unchanged lines hidden (view full) ---

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 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__