1/* |
2 * Copyright (c) 2004-2006 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_INST_QUEUE_HH__ 30#define __CPU_O3_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 "cpu/o3/dep_graph.hh" 41#include "encumbered/cpu/full/op_class.hh" |
42#include "sim/host.hh" 43 |
44class FUPool; 45class MemInterface; 46 |
47/** 48 * A standard instruction queue class. It holds ready instructions, in 49 * order, in seperate priority queues to facilitate the scheduling of 50 * instructions. The IQ uses a separate linked list to track dependencies. 51 * Similar to the rename map and the free list, it expects that 52 * floating point registers have their indices start after the integer 53 * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer 54 * and 96-191 are fp). This remains true even for both logical and |
55 * physical register indices. The IQ depends on the memory dependence unit to 56 * track when memory operations are ready in terms of ordering; register 57 * dependencies are tracked normally. Right now the IQ also handles the 58 * execution timing; this is mainly to allow back-to-back scheduling without 59 * requiring IEW to be able to peek into the IQ. At the end of the execution 60 * latency, the instruction is put into the queue to execute, where it will 61 * have the execute() function called on it. 62 * @todo: Make IQ able to handle multiple FU pools. |
63 */ 64template <class Impl> 65class InstructionQueue 66{ 67 public: 68 //Typedefs from the Impl. 69 typedef typename Impl::FullCPU FullCPU; 70 typedef typename Impl::DynInstPtr DynInstPtr; 71 typedef typename Impl::Params Params; 72 |
73 typedef typename Impl::CPUPol::IEW IEW; |
74 typedef typename Impl::CPUPol::MemDepUnit MemDepUnit; 75 typedef typename Impl::CPUPol::IssueStruct IssueStruct; 76 typedef typename Impl::CPUPol::TimeStruct TimeStruct; 77 |
78 // Typedef of iterator through the list of instructions. |
79 typedef typename std::list<DynInstPtr>::iterator ListIt; 80 |
81 friend class Impl::FullCPU; |
82 |
83 /** FU completion event class. */ 84 class FUCompletion : public Event { 85 private: 86 /** Executing instruction. */ 87 DynInstPtr inst; 88 89 /** Index of the FU used for executing. */ 90 int fuIdx; 91 92 /** Pointer back to the instruction queue. */ 93 InstructionQueue<Impl> *iqPtr; 94 95 bool freeFU; 96 97 public: 98 /** Construct a FU completion event. */ 99 FUCompletion(DynInstPtr &_inst, int fu_idx, 100 InstructionQueue<Impl> *iq_ptr); 101 102 virtual void process(); 103 virtual const char *description(); 104 void setFreeFU() { freeFU = true; } |
105 }; 106 |
107 /** Constructs an IQ. */ 108 InstructionQueue(Params *params); |
109 |
110 /** Destructs the IQ. */ 111 ~InstructionQueue(); |
112 |
113 /** Returns the name of the IQ. */ 114 std::string name() const; 115 116 /** Registers statistics. */ |
117 void regStats(); 118 |
119 void resetState(); |
120 |
121 /** Sets CPU pointer. */ 122 void setCPU(FullCPU *_cpu) { cpu = _cpu; } 123 124 /** Sets active threads list. */ 125 void setActiveThreads(std::list<unsigned> *at_ptr); 126 127 /** Sets the IEW pointer. */ 128 void setIEW(IEW *iew_ptr) { iewStage = iew_ptr; } 129 130 /** Sets the timer buffer between issue and execute. */ |
131 void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue); 132 |
133 /** Sets the global time buffer. */ |
134 void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr); 135 |
136 void switchOut(); 137 138 void takeOverFrom(); 139 140 bool isSwitchedOut() { return switchedOut; } 141 142 /** Number of entries needed for given amount of threads. */ 143 int entryAmount(int num_threads); 144 145 /** Resets max entries for all threads. */ 146 void resetEntries(); 147 148 /** Returns total number of free entries. */ |
149 unsigned numFreeEntries(); 150 |
151 /** Returns number of free entries for a thread. */ 152 unsigned numFreeEntries(unsigned tid); 153 154 /** Returns whether or not the IQ is full. */ |
155 bool isFull(); 156 |
157 /** Returns whether or not the IQ is full for a specific thread. */ 158 bool isFull(unsigned tid); 159 160 /** Returns if there are any ready instructions in the IQ. */ 161 bool hasReadyInsts(); 162 163 /** Inserts a new instruction into the IQ. */ |
164 void insert(DynInstPtr &new_inst); 165 |
166 /** Inserts a new, non-speculative instruction into the IQ. */ |
167 void insertNonSpec(DynInstPtr &new_inst); 168 |
169 /** Inserts a memory or write barrier into the IQ to make sure 170 * loads and stores are ordered properly. 171 */ 172 void insertBarrier(DynInstPtr &barr_inst); |
173 |
174 DynInstPtr getInstToExecute(); 175 176 /** 177 * Records the instruction as the producer of a register without 178 * adding it to the rest of the IQ. 179 */ 180 void recordProducer(DynInstPtr &inst) 181 { addToProducers(inst); } 182 183 /** Process FU completion event. */ 184 void processFUCompletion(DynInstPtr &inst, int fu_idx); 185 186 /** 187 * Schedules ready instructions, adding the ready ones (oldest first) to 188 * the queue to execute. 189 */ |
190 void scheduleReadyInsts(); 191 |
192 /** Schedules a single specific non-speculative instruction. */ |
193 void scheduleNonSpec(const InstSeqNum &inst); 194 |
195 /** 196 * Commits all instructions up to and including the given sequence number, 197 * for a specific thread. 198 */ 199 void commit(const InstSeqNum &inst, unsigned tid = 0); |
200 |
201 /** Wakes all dependents of a completed instruction. */ 202 int wakeDependents(DynInstPtr &completed_inst); 203 204 /** Adds a ready memory instruction to the ready list. */ 205 void addReadyMemInst(DynInstPtr &ready_inst); 206 207 /** 208 * Reschedules a memory instruction. It will be ready to issue once 209 * replayMemInst() is called. 210 */ 211 void rescheduleMemInst(DynInstPtr &resched_inst); 212 213 /** Replays a memory instruction. It must be rescheduled first. */ 214 void replayMemInst(DynInstPtr &replay_inst); 215 216 /** Completes a memory operation. */ 217 void completeMemInst(DynInstPtr &completed_inst); 218 219 /** Indicates an ordering violation between a store and a load. */ |
220 void violation(DynInstPtr &store, DynInstPtr &faulting_load); 221 |
222 /** 223 * Squashes instructions for a thread. Squashing information is obtained 224 * from the time buffer. 225 */ 226 void squash(unsigned tid); |
227 |
228 /** Returns the number of used entries for a thread. */ 229 unsigned getCount(unsigned tid) { return count[tid]; }; |
230 |
231 /** Debug function to print all instructions. */ 232 void printInsts(); |
233 234 private: |
235 /** Does the actual squashing. */ 236 void doSquash(unsigned tid); 237 238 ///////////////////////// 239 // Various pointers 240 ///////////////////////// 241 |
242 /** Pointer to the CPU. */ 243 FullCPU *cpu; 244 |
245 /** Cache interface. */ 246 MemInterface *dcacheInterface; 247 248 /** Pointer to IEW stage. */ 249 IEW *iewStage; 250 |
251 /** The memory dependence unit, which tracks/predicts memory dependences 252 * between instructions. 253 */ |
254 MemDepUnit memDepUnit[Impl::MaxThreads]; |
255 256 /** The queue to the execute stage. Issued instructions will be written 257 * into it. 258 */ 259 TimeBuffer<IssueStruct> *issueToExecuteQueue; 260 261 /** The backwards time buffer. */ 262 TimeBuffer<TimeStruct> *timeBuffer; 263 264 /** Wire to read information from timebuffer. */ 265 typename TimeBuffer<TimeStruct>::wire fromCommit; 266 |
267 /** Function unit pool. */ 268 FUPool *fuPool; |
269 |
270 ////////////////////////////////////// 271 // Instruction lists, ready queues, and ordering 272 ////////////////////////////////////// |
273 |
274 /** List of all the instructions in the IQ (some of which may be issued). */ 275 std::list<DynInstPtr> instList[Impl::MaxThreads]; |
276 |
277 std::list<DynInstPtr> instsToExecute; |
278 |
279 /** 280 * Struct for comparing entries to be added to the priority queue. This 281 * gives reverse ordering to the instructions in terms of sequence 282 * numbers: the instructions with smaller sequence numbers (and hence 283 * are older) will be at the top of the priority queue. 284 */ 285 struct pqCompare { 286 bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const 287 { 288 return lhs->seqNum > rhs->seqNum; 289 } 290 }; |
291 |
292 typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare> 293 ReadyInstQueue; 294 295 /** List of ready instructions, per op class. They are separated by op 296 * class to allow for easy mapping to FUs. |
297 */ |
298 ReadyInstQueue readyInsts[Num_OpClasses]; |
299 300 /** List of non-speculative instructions that will be scheduled 301 * once the IQ gets a signal from commit. While it's redundant to 302 * have the key be a part of the value (the sequence number is stored 303 * inside of DynInst), when these instructions are woken up only 304 * the sequence number will be available. Thus it is most efficient to be 305 * able to search by the sequence number alone. 306 */ 307 std::map<InstSeqNum, DynInstPtr> nonSpecInsts; 308 |
309 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt; |
310 |
311 /** Entry for the list age ordering by op class. */ 312 struct ListOrderEntry { 313 OpClass queueType; 314 InstSeqNum oldestInst; 315 }; |
316 |
317 /** List that contains the age order of the oldest instruction of each 318 * ready queue. Used to select the oldest instruction available 319 * among op classes. 320 * @todo: Might be better to just move these entries around instead 321 * of creating new ones every time the position changes due to an 322 * instruction issuing. Not sure std::list supports this. 323 */ 324 std::list<ListOrderEntry> listOrder; |
325 |
326 typedef typename std::list<ListOrderEntry>::iterator ListOrderIt; 327 328 /** Tracks if each ready queue is on the age order list. */ 329 bool queueOnList[Num_OpClasses]; 330 331 /** Iterators of each ready queue. Points to their spot in the age order 332 * list. |
333 */ |
334 ListOrderIt readyIt[Num_OpClasses]; |
335 |
336 /** Add an op class to the age order list. */ 337 void addToOrderList(OpClass op_class); 338 339 /** 340 * Called when the oldest instruction has been removed from a ready queue; 341 * this places that ready queue into the proper spot in the age order list. |
342 */ |
343 void moveToYoungerInst(ListOrderIt age_order_it); |
344 |
345 DependencyGraph<DynInstPtr> dependGraph; |
346 |
347 ////////////////////////////////////// 348 // Various parameters 349 ////////////////////////////////////// |
350 |
351 /** IQ Resource Sharing Policy */ 352 enum IQPolicy { 353 Dynamic, 354 Partitioned, 355 Threshold 356 }; 357 358 /** IQ sharing policy for SMT. */ 359 IQPolicy iqPolicy; 360 361 /** Number of Total Threads*/ 362 unsigned numThreads; 363 364 /** Pointer to list of active threads. */ 365 std::list<unsigned> *activeThreads; 366 367 /** Per Thread IQ count */ 368 unsigned count[Impl::MaxThreads]; 369 370 /** Max IQ Entries Per Thread */ 371 unsigned maxEntries[Impl::MaxThreads]; 372 373 /** Number of free IQ entries left. */ 374 unsigned freeEntries; 375 376 /** The number of entries in the instruction queue. */ 377 unsigned numEntries; 378 |
379 /** The total number of instructions that can be issued in one cycle. */ 380 unsigned totalWidth; 381 |
382 /** The number of physical registers in the CPU. */ |
383 unsigned numPhysRegs; 384 385 /** The number of physical integer registers in the CPU. */ 386 unsigned numPhysIntRegs; 387 388 /** The number of floating point registers in the CPU. */ 389 unsigned numPhysFloatRegs; 390 391 /** Delay between commit stage and the IQ. 392 * @todo: Make there be a distinction between the delays within IEW. 393 */ 394 unsigned commitToIEWDelay; 395 |
396 bool switchedOut; |
397 398 /** The sequence number of the squashed instruction. */ |
399 InstSeqNum squashedSeqNum[Impl::MaxThreads]; |
400 |
401 /** A cache of the recently woken registers. It is 1 if the register 402 * has been woken up recently, and 0 if the register has been added 403 * to the dependency graph and has not yet received its value. It 404 * is basically a secondary scoreboard, and should pretty much mirror 405 * the scoreboard that exists in the rename map. 406 */ |
407 std::vector<bool> regScoreboard; |
408 |
409 /** Adds an instruction to the dependency graph, as a consumer. */ |
410 bool addToDependents(DynInstPtr &new_inst); |
411 |
412 /** Adds an instruction to the dependency graph, as a producer. */ 413 void addToProducers(DynInstPtr &new_inst); 414 415 /** Moves an instruction to the ready queue if it is ready. */ |
416 void addIfReady(DynInstPtr &inst); 417 |
418 /** Debugging function to count how many entries are in the IQ. It does 419 * a linear walk through the instructions, so do not call this function 420 * during normal execution. 421 */ 422 int countInsts(); 423 |
424 /** Debugging function to dump all the list sizes, as well as print 425 * out the list of nonspeculative instructions. Should not be used 426 * in any other capacity, but it has no harmful sideaffects. 427 */ 428 void dumpLists(); 429 |
430 /** Debugging function to dump out all instructions that are in the 431 * IQ. 432 */ 433 void dumpInsts(); 434 435 /** Stat for number of instructions added. */ |
436 Stats::Scalar<> iqInstsAdded; |
437 /** Stat for number of non-speculative instructions added. */ |
438 Stats::Scalar<> iqNonSpecInstsAdded; |
439 440 Stats::Scalar<> iqInstsIssued; 441 /** Stat for number of integer instructions issued. */ |
442 Stats::Scalar<> iqIntInstsIssued; |
443 /** Stat for number of floating point instructions issued. */ |
444 Stats::Scalar<> iqFloatInstsIssued; |
445 /** Stat for number of branch instructions issued. */ |
446 Stats::Scalar<> iqBranchInstsIssued; |
447 /** Stat for number of memory instructions issued. */ |
448 Stats::Scalar<> iqMemInstsIssued; |
449 /** Stat for number of miscellaneous instructions issued. */ |
450 Stats::Scalar<> iqMiscInstsIssued; |
451 /** Stat for number of squashed instructions that were ready to issue. */ |
452 Stats::Scalar<> iqSquashedInstsIssued; |
453 /** Stat for number of squashed instructions examined when squashing. */ |
454 Stats::Scalar<> iqSquashedInstsExamined; |
455 /** Stat for number of squashed instruction operands examined when 456 * squashing. 457 */ |
458 Stats::Scalar<> iqSquashedOperandsExamined; |
459 /** Stat for number of non-speculative instructions removed due to a squash. 460 */ |
461 Stats::Scalar<> iqSquashedNonSpecRemoved; 462 |
463 Stats::VectorDistribution<> queueResDist; 464 Stats::Distribution<> numIssuedDist; 465 Stats::VectorDistribution<> issueDelayDist; 466 467 Stats::Vector<> statFuBusy; 468// Stats::Vector<> dist_unissued; 469 Stats::Vector2d<> statIssuedInstType; 470 471 Stats::Formula issueRate; 472// Stats::Formula issue_stores; 473// Stats::Formula issue_op_rate; 474 Stats::Vector<> fuBusy; //cumulative fu busy 475 476 Stats::Formula fuBusyRate; |
477}; 478 |
479#endif //__CPU_O3_INST_QUEUE_HH__ |