inst_queue.hh revision 13561
1/* 2 * Copyright (c) 2011-2012, 2014 ARM Limited 3 * Copyright (c) 2013 Advanced Micro Devices, Inc. 4 * All rights reserved. 5 * 6 * The license below extends only to copyright in the software and shall 7 * not be construed as granting a license to any other intellectual 8 * property including but not limited to intellectual property relating 9 * to a hardware implementation of the functionality of the software 10 * licensed hereunder. You may use the software subject to the license 11 * terms below provided that you ensure that this notice is replicated 12 * unmodified and in its entirety in all distributions of the software, 13 * modified or unmodified, in source code or in binary form. 14 * 15 * Copyright (c) 2004-2006 The Regents of The University of Michigan 16 * All rights reserved. 17 * 18 * Redistribution and use in source and binary forms, with or without 19 * modification, are permitted provided that the following conditions are 20 * met: redistributions of source code must retain the above copyright 21 * notice, this list of conditions and the following disclaimer; 22 * redistributions in binary form must reproduce the above copyright 23 * notice, this list of conditions and the following disclaimer in the 24 * documentation and/or other materials provided with the distribution; 25 * neither the name of the copyright holders nor the names of its 26 * contributors may be used to endorse or promote products derived from 27 * this software without specific prior written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 30 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 31 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 32 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 33 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 34 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 35 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 36 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 37 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 38 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 39 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 40 * 41 * Authors: Kevin Lim 42 */ 43 44#ifndef __CPU_O3_INST_QUEUE_HH__ 45#define __CPU_O3_INST_QUEUE_HH__ 46 47#include <list> 48#include <map> 49#include <queue> 50#include <vector> 51 52#include "base/statistics.hh" 53#include "base/types.hh" 54#include "cpu/o3/dep_graph.hh" 55#include "cpu/inst_seq.hh" 56#include "cpu/op_class.hh" 57#include "cpu/timebuf.hh" 58#include "enums/SMTQueuePolicy.hh" 59#include "sim/eventq.hh" 60 61struct DerivO3CPUParams; 62class FUPool; 63class MemInterface; 64 65/** 66 * A standard instruction queue class. It holds ready instructions, in 67 * order, in seperate priority queues to facilitate the scheduling of 68 * instructions. The IQ uses a separate linked list to track dependencies. 69 * Similar to the rename map and the free list, it expects that 70 * floating point registers have their indices start after the integer 71 * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer 72 * and 96-191 are fp). This remains true even for both logical and 73 * physical register indices. The IQ depends on the memory dependence unit to 74 * track when memory operations are ready in terms of ordering; register 75 * dependencies are tracked normally. Right now the IQ also handles the 76 * execution timing; this is mainly to allow back-to-back scheduling without 77 * requiring IEW to be able to peek into the IQ. At the end of the execution 78 * latency, the instruction is put into the queue to execute, where it will 79 * have the execute() function called on it. 80 * @todo: Make IQ able to handle multiple FU pools. 81 */ 82template <class Impl> 83class InstructionQueue 84{ 85 public: 86 //Typedefs from the Impl. 87 typedef typename Impl::O3CPU O3CPU; 88 typedef typename Impl::DynInstPtr DynInstPtr; 89 90 typedef typename Impl::CPUPol::IEW IEW; 91 typedef typename Impl::CPUPol::MemDepUnit MemDepUnit; 92 typedef typename Impl::CPUPol::IssueStruct IssueStruct; 93 typedef typename Impl::CPUPol::TimeStruct TimeStruct; 94 95 // Typedef of iterator through the list of instructions. 96 typedef typename std::list<DynInstPtr>::iterator ListIt; 97 98 /** FU completion event class. */ 99 class FUCompletion : public Event { 100 private: 101 /** Executing instruction. */ 102 DynInstPtr inst; 103 104 /** Index of the FU used for executing. */ 105 int fuIdx; 106 107 /** Pointer back to the instruction queue. */ 108 InstructionQueue<Impl> *iqPtr; 109 110 /** Should the FU be added to the list to be freed upon 111 * completing this event. 112 */ 113 bool freeFU; 114 115 public: 116 /** Construct a FU completion event. */ 117 FUCompletion(const DynInstPtr &_inst, int fu_idx, 118 InstructionQueue<Impl> *iq_ptr); 119 120 virtual void process(); 121 virtual const char *description() const; 122 void setFreeFU() { freeFU = true; } 123 }; 124 125 /** Constructs an IQ. */ 126 InstructionQueue(O3CPU *cpu_ptr, IEW *iew_ptr, DerivO3CPUParams *params); 127 128 /** Destructs the IQ. */ 129 ~InstructionQueue(); 130 131 /** Returns the name of the IQ. */ 132 std::string name() const; 133 134 /** Registers statistics. */ 135 void regStats(); 136 137 /** Resets all instruction queue state. */ 138 void resetState(); 139 140 /** Sets active threads list. */ 141 void setActiveThreads(std::list<ThreadID> *at_ptr); 142 143 /** Sets the timer buffer between issue and execute. */ 144 void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue); 145 146 /** Sets the global time buffer. */ 147 void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr); 148 149 /** Determine if we are drained. */ 150 bool isDrained() const; 151 152 /** Perform sanity checks after a drain. */ 153 void drainSanityCheck() const; 154 155 /** Takes over execution from another CPU's thread. */ 156 void takeOverFrom(); 157 158 /** Number of entries needed for given amount of threads. */ 159 int entryAmount(ThreadID num_threads); 160 161 /** Resets max entries for all threads. */ 162 void resetEntries(); 163 164 /** Returns total number of free entries. */ 165 unsigned numFreeEntries(); 166 167 /** Returns number of free entries for a thread. */ 168 unsigned numFreeEntries(ThreadID tid); 169 170 /** Returns whether or not the IQ is full. */ 171 bool isFull(); 172 173 /** Returns whether or not the IQ is full for a specific thread. */ 174 bool isFull(ThreadID tid); 175 176 /** Returns if there are any ready instructions in the IQ. */ 177 bool hasReadyInsts(); 178 179 /** Inserts a new instruction into the IQ. */ 180 void insert(const DynInstPtr &new_inst); 181 182 /** Inserts a new, non-speculative instruction into the IQ. */ 183 void insertNonSpec(const DynInstPtr &new_inst); 184 185 /** Inserts a memory or write barrier into the IQ to make sure 186 * loads and stores are ordered properly. 187 */ 188 void insertBarrier(const DynInstPtr &barr_inst); 189 190 /** Returns the oldest scheduled instruction, and removes it from 191 * the list of instructions waiting to execute. 192 */ 193 DynInstPtr getInstToExecute(); 194 195 /** Gets a memory instruction that was referred due to a delayed DTB 196 * translation if it is now ready to execute. NULL if none available. 197 */ 198 DynInstPtr getDeferredMemInstToExecute(); 199 200 /** Gets a memory instruction that was blocked on the cache. NULL if none 201 * available. 202 */ 203 DynInstPtr getBlockedMemInstToExecute(); 204 205 /** 206 * Records the instruction as the producer of a register without 207 * adding it to the rest of the IQ. 208 */ 209 void recordProducer(const DynInstPtr &inst) 210 { addToProducers(inst); } 211 212 /** Process FU completion event. */ 213 void processFUCompletion(const DynInstPtr &inst, int fu_idx); 214 215 /** 216 * Schedules ready instructions, adding the ready ones (oldest first) to 217 * the queue to execute. 218 */ 219 void scheduleReadyInsts(); 220 221 /** Schedules a single specific non-speculative instruction. */ 222 void scheduleNonSpec(const InstSeqNum &inst); 223 224 /** 225 * Commits all instructions up to and including the given sequence number, 226 * for a specific thread. 227 */ 228 void commit(const InstSeqNum &inst, ThreadID tid = 0); 229 230 /** Wakes all dependents of a completed instruction. */ 231 int wakeDependents(const DynInstPtr &completed_inst); 232 233 /** Adds a ready memory instruction to the ready list. */ 234 void addReadyMemInst(const DynInstPtr &ready_inst); 235 236 /** 237 * Reschedules a memory instruction. It will be ready to issue once 238 * replayMemInst() is called. 239 */ 240 void rescheduleMemInst(const DynInstPtr &resched_inst); 241 242 /** Replays a memory instruction. It must be rescheduled first. */ 243 void replayMemInst(const DynInstPtr &replay_inst); 244 245 /** Completes a memory operation. */ 246 void completeMemInst(const DynInstPtr &completed_inst); 247 248 /** 249 * Defers a memory instruction when its DTB translation incurs a hw 250 * page table walk. 251 */ 252 void deferMemInst(const DynInstPtr &deferred_inst); 253 254 /** Defers a memory instruction when it is cache blocked. */ 255 void blockMemInst(const DynInstPtr &blocked_inst); 256 257 /** Notify instruction queue that a previous blockage has resolved */ 258 void cacheUnblocked(); 259 260 /** Indicates an ordering violation between a store and a load. */ 261 void violation(const DynInstPtr &store, const DynInstPtr &faulting_load); 262 263 /** 264 * Squashes instructions for a thread. Squashing information is obtained 265 * from the time buffer. 266 */ 267 void squash(ThreadID tid); 268 269 /** Returns the number of used entries for a thread. */ 270 unsigned getCount(ThreadID tid) { return count[tid]; }; 271 272 /** Debug function to print all instructions. */ 273 void printInsts(); 274 275 private: 276 /** Does the actual squashing. */ 277 void doSquash(ThreadID tid); 278 279 ///////////////////////// 280 // Various pointers 281 ///////////////////////// 282 283 /** Pointer to the CPU. */ 284 O3CPU *cpu; 285 286 /** Cache interface. */ 287 MemInterface *dcacheInterface; 288 289 /** Pointer to IEW stage. */ 290 IEW *iewStage; 291 292 /** The memory dependence unit, which tracks/predicts memory dependences 293 * between instructions. 294 */ 295 MemDepUnit memDepUnit[Impl::MaxThreads]; 296 297 /** The queue to the execute stage. Issued instructions will be written 298 * into it. 299 */ 300 TimeBuffer<IssueStruct> *issueToExecuteQueue; 301 302 /** The backwards time buffer. */ 303 TimeBuffer<TimeStruct> *timeBuffer; 304 305 /** Wire to read information from timebuffer. */ 306 typename TimeBuffer<TimeStruct>::wire fromCommit; 307 308 /** Function unit pool. */ 309 FUPool *fuPool; 310 311 ////////////////////////////////////// 312 // Instruction lists, ready queues, and ordering 313 ////////////////////////////////////// 314 315 /** List of all the instructions in the IQ (some of which may be issued). */ 316 std::list<DynInstPtr> instList[Impl::MaxThreads]; 317 318 /** List of instructions that are ready to be executed. */ 319 std::list<DynInstPtr> instsToExecute; 320 321 /** List of instructions waiting for their DTB translation to 322 * complete (hw page table walk in progress). 323 */ 324 std::list<DynInstPtr> deferredMemInsts; 325 326 /** List of instructions that have been cache blocked. */ 327 std::list<DynInstPtr> blockedMemInsts; 328 329 /** List of instructions that were cache blocked, but a retry has been seen 330 * since, so they can now be retried. May fail again go on the blocked list. 331 */ 332 std::list<DynInstPtr> retryMemInsts; 333 334 /** 335 * Struct for comparing entries to be added to the priority queue. 336 * This gives reverse ordering to the instructions in terms of 337 * sequence numbers: the instructions with smaller sequence 338 * numbers (and hence are older) will be at the top of the 339 * priority queue. 340 */ 341 struct pqCompare { 342 bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const 343 { 344 return lhs->seqNum > rhs->seqNum; 345 } 346 }; 347 348 typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare> 349 ReadyInstQueue; 350 351 /** List of ready instructions, per op class. They are separated by op 352 * class to allow for easy mapping to FUs. 353 */ 354 ReadyInstQueue readyInsts[Num_OpClasses]; 355 356 /** List of non-speculative instructions that will be scheduled 357 * once the IQ gets a signal from commit. While it's redundant to 358 * have the key be a part of the value (the sequence number is stored 359 * inside of DynInst), when these instructions are woken up only 360 * the sequence number will be available. Thus it is most efficient to be 361 * able to search by the sequence number alone. 362 */ 363 std::map<InstSeqNum, DynInstPtr> nonSpecInsts; 364 365 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt; 366 367 /** Entry for the list age ordering by op class. */ 368 struct ListOrderEntry { 369 OpClass queueType; 370 InstSeqNum oldestInst; 371 }; 372 373 /** List that contains the age order of the oldest instruction of each 374 * ready queue. Used to select the oldest instruction available 375 * among op classes. 376 * @todo: Might be better to just move these entries around instead 377 * of creating new ones every time the position changes due to an 378 * instruction issuing. Not sure std::list supports this. 379 */ 380 std::list<ListOrderEntry> listOrder; 381 382 typedef typename std::list<ListOrderEntry>::iterator ListOrderIt; 383 384 /** Tracks if each ready queue is on the age order list. */ 385 bool queueOnList[Num_OpClasses]; 386 387 /** Iterators of each ready queue. Points to their spot in the age order 388 * list. 389 */ 390 ListOrderIt readyIt[Num_OpClasses]; 391 392 /** Add an op class to the age order list. */ 393 void addToOrderList(OpClass op_class); 394 395 /** 396 * Called when the oldest instruction has been removed from a ready queue; 397 * this places that ready queue into the proper spot in the age order list. 398 */ 399 void moveToYoungerInst(ListOrderIt age_order_it); 400 401 DependencyGraph<DynInstPtr> dependGraph; 402 403 ////////////////////////////////////// 404 // Various parameters 405 ////////////////////////////////////// 406 407 /** IQ sharing policy for SMT. */ 408 SMTQueuePolicy iqPolicy; 409 410 /** Number of Total Threads*/ 411 ThreadID numThreads; 412 413 /** Pointer to list of active threads. */ 414 std::list<ThreadID> *activeThreads; 415 416 /** Per Thread IQ count */ 417 unsigned count[Impl::MaxThreads]; 418 419 /** Max IQ Entries Per Thread */ 420 unsigned maxEntries[Impl::MaxThreads]; 421 422 /** Number of free IQ entries left. */ 423 unsigned freeEntries; 424 425 /** The number of entries in the instruction queue. */ 426 unsigned numEntries; 427 428 /** The total number of instructions that can be issued in one cycle. */ 429 unsigned totalWidth; 430 431 /** The number of physical registers in the CPU. */ 432 unsigned numPhysRegs; 433 434 /** Number of instructions currently in flight to FUs */ 435 int wbOutstanding; 436 437 /** Delay between commit stage and the IQ. 438 * @todo: Make there be a distinction between the delays within IEW. 439 */ 440 Cycles commitToIEWDelay; 441 442 /** The sequence number of the squashed instruction. */ 443 InstSeqNum squashedSeqNum[Impl::MaxThreads]; 444 445 /** A cache of the recently woken registers. It is 1 if the register 446 * has been woken up recently, and 0 if the register has been added 447 * to the dependency graph and has not yet received its value. It 448 * is basically a secondary scoreboard, and should pretty much mirror 449 * the scoreboard that exists in the rename map. 450 */ 451 std::vector<bool> regScoreboard; 452 453 /** Adds an instruction to the dependency graph, as a consumer. */ 454 bool addToDependents(const DynInstPtr &new_inst); 455 456 /** Adds an instruction to the dependency graph, as a producer. */ 457 void addToProducers(const DynInstPtr &new_inst); 458 459 /** Moves an instruction to the ready queue if it is ready. */ 460 void addIfReady(const DynInstPtr &inst); 461 462 /** Debugging function to count how many entries are in the IQ. It does 463 * a linear walk through the instructions, so do not call this function 464 * during normal execution. 465 */ 466 int countInsts(); 467 468 /** Debugging function to dump all the list sizes, as well as print 469 * out the list of nonspeculative instructions. Should not be used 470 * in any other capacity, but it has no harmful sideaffects. 471 */ 472 void dumpLists(); 473 474 /** Debugging function to dump out all instructions that are in the 475 * IQ. 476 */ 477 void dumpInsts(); 478 479 /** Stat for number of instructions added. */ 480 Stats::Scalar iqInstsAdded; 481 /** Stat for number of non-speculative instructions added. */ 482 Stats::Scalar iqNonSpecInstsAdded; 483 484 Stats::Scalar iqInstsIssued; 485 /** Stat for number of integer instructions issued. */ 486 Stats::Scalar iqIntInstsIssued; 487 /** Stat for number of floating point instructions issued. */ 488 Stats::Scalar iqFloatInstsIssued; 489 /** Stat for number of branch instructions issued. */ 490 Stats::Scalar iqBranchInstsIssued; 491 /** Stat for number of memory instructions issued. */ 492 Stats::Scalar iqMemInstsIssued; 493 /** Stat for number of miscellaneous instructions issued. */ 494 Stats::Scalar iqMiscInstsIssued; 495 /** Stat for number of squashed instructions that were ready to issue. */ 496 Stats::Scalar iqSquashedInstsIssued; 497 /** Stat for number of squashed instructions examined when squashing. */ 498 Stats::Scalar iqSquashedInstsExamined; 499 /** Stat for number of squashed instruction operands examined when 500 * squashing. 501 */ 502 Stats::Scalar iqSquashedOperandsExamined; 503 /** Stat for number of non-speculative instructions removed due to a squash. 504 */ 505 Stats::Scalar iqSquashedNonSpecRemoved; 506 // Also include number of instructions rescheduled and replayed. 507 508 /** Distribution of number of instructions in the queue. 509 * @todo: Need to create struct to track the entry time for each 510 * instruction. */ 511// Stats::VectorDistribution queueResDist; 512 /** Distribution of the number of instructions issued. */ 513 Stats::Distribution numIssuedDist; 514 /** Distribution of the cycles it takes to issue an instruction. 515 * @todo: Need to create struct to track the ready time for each 516 * instruction. */ 517// Stats::VectorDistribution issueDelayDist; 518 519 /** Number of times an instruction could not be issued because a 520 * FU was busy. 521 */ 522 Stats::Vector statFuBusy; 523// Stats::Vector dist_unissued; 524 /** Stat for total number issued for each instruction type. */ 525 Stats::Vector2d statIssuedInstType; 526 527 /** Number of instructions issued per cycle. */ 528 Stats::Formula issueRate; 529 530 /** Number of times the FU was busy. */ 531 Stats::Vector fuBusy; 532 /** Number of times the FU was busy per instruction issued. */ 533 Stats::Formula fuBusyRate; 534 public: 535 Stats::Scalar intInstQueueReads; 536 Stats::Scalar intInstQueueWrites; 537 Stats::Scalar intInstQueueWakeupAccesses; 538 Stats::Scalar fpInstQueueReads; 539 Stats::Scalar fpInstQueueWrites; 540 Stats::Scalar fpInstQueueWakeupAccesses; 541 Stats::Scalar vecInstQueueReads; 542 Stats::Scalar vecInstQueueWrites; 543 Stats::Scalar vecInstQueueWakeupAccesses; 544 545 Stats::Scalar intAluAccesses; 546 Stats::Scalar fpAluAccesses; 547 Stats::Scalar vecAluAccesses; 548}; 549 550#endif //__CPU_O3_INST_QUEUE_HH__ 551