inst_queue.hh revision 2348
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 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 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 /** Should the FU be added to the list to be freed upon 96 * completing this event. 97 */ 98 bool freeFU; 99 100 public: 101 /** Construct a FU completion event. */ 102 FUCompletion(DynInstPtr &_inst, int fu_idx, 103 InstructionQueue<Impl> *iq_ptr); 104 105 virtual void process(); 106 virtual const char *description(); 107 void setFreeFU() { freeFU = true; } 108 }; 109 110 /** Constructs an IQ. */ 111 InstructionQueue(Params *params); 112 113 /** Destructs the IQ. */ 114 ~InstructionQueue(); 115 116 /** Returns the name of the IQ. */ 117 std::string name() const; 118 119 /** Registers statistics. */ 120 void regStats(); 121 122 /** Resets all instruction queue state. */ 123 void resetState(); 124 125 /** Sets CPU pointer. */ 126 void setCPU(FullCPU *_cpu) { cpu = _cpu; } 127 128 /** Sets active threads list. */ 129 void setActiveThreads(std::list<unsigned> *at_ptr); 130 131 /** Sets the IEW pointer. */ 132 void setIEW(IEW *iew_ptr) { iewStage = iew_ptr; } 133 134 /** Sets the timer buffer between issue and execute. */ 135 void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue); 136 137 /** Sets the global time buffer. */ 138 void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr); 139 140 /** Switches out the instruction queue. */ 141 void switchOut(); 142 143 /** Takes over execution from another CPU's thread. */ 144 void takeOverFrom(); 145 146 /** Returns if the IQ is switched out. */ 147 bool isSwitchedOut() { return switchedOut; } 148 149 /** Number of entries needed for given amount of threads. */ 150 int entryAmount(int num_threads); 151 152 /** Resets max entries for all threads. */ 153 void resetEntries(); 154 155 /** Returns total number of free entries. */ 156 unsigned numFreeEntries(); 157 158 /** Returns number of free entries for a thread. */ 159 unsigned numFreeEntries(unsigned tid); 160 161 /** Returns whether or not the IQ is full. */ 162 bool isFull(); 163 164 /** Returns whether or not the IQ is full for a specific thread. */ 165 bool isFull(unsigned tid); 166 167 /** Returns if there are any ready instructions in the IQ. */ 168 bool hasReadyInsts(); 169 170 /** Inserts a new instruction into the IQ. */ 171 void insert(DynInstPtr &new_inst); 172 173 /** Inserts a new, non-speculative instruction into the IQ. */ 174 void insertNonSpec(DynInstPtr &new_inst); 175 176 /** Inserts a memory or write barrier into the IQ to make sure 177 * loads and stores are ordered properly. 178 */ 179 void insertBarrier(DynInstPtr &barr_inst); 180 181 /** Returns the oldest scheduled instruction, and removes it from 182 * the list of instructions waiting to execute. 183 */ 184 DynInstPtr getInstToExecute(); 185 186 /** 187 * Records the instruction as the producer of a register without 188 * adding it to the rest of the IQ. 189 */ 190 void recordProducer(DynInstPtr &inst) 191 { addToProducers(inst); } 192 193 /** Process FU completion event. */ 194 void processFUCompletion(DynInstPtr &inst, int fu_idx); 195 196 /** 197 * Schedules ready instructions, adding the ready ones (oldest first) to 198 * the queue to execute. 199 */ 200 void scheduleReadyInsts(); 201 202 /** Schedules a single specific non-speculative instruction. */ 203 void scheduleNonSpec(const InstSeqNum &inst); 204 205 /** 206 * Commits all instructions up to and including the given sequence number, 207 * for a specific thread. 208 */ 209 void commit(const InstSeqNum &inst, unsigned tid = 0); 210 211 /** Wakes all dependents of a completed instruction. */ 212 int wakeDependents(DynInstPtr &completed_inst); 213 214 /** Adds a ready memory instruction to the ready list. */ 215 void addReadyMemInst(DynInstPtr &ready_inst); 216 217 /** 218 * Reschedules a memory instruction. It will be ready to issue once 219 * replayMemInst() is called. 220 */ 221 void rescheduleMemInst(DynInstPtr &resched_inst); 222 223 /** Replays a memory instruction. It must be rescheduled first. */ 224 void replayMemInst(DynInstPtr &replay_inst); 225 226 /** Completes a memory operation. */ 227 void completeMemInst(DynInstPtr &completed_inst); 228 229 /** Indicates an ordering violation between a store and a load. */ 230 void violation(DynInstPtr &store, DynInstPtr &faulting_load); 231 232 /** 233 * Squashes instructions for a thread. Squashing information is obtained 234 * from the time buffer. 235 */ 236 void squash(unsigned tid); 237 238 /** Returns the number of used entries for a thread. */ 239 unsigned getCount(unsigned tid) { return count[tid]; }; 240 241 /** Debug function to print all instructions. */ 242 void printInsts(); 243 244 private: 245 /** Does the actual squashing. */ 246 void doSquash(unsigned tid); 247 248 ///////////////////////// 249 // Various pointers 250 ///////////////////////// 251 252 /** Pointer to the CPU. */ 253 FullCPU *cpu; 254 255 /** Cache interface. */ 256 MemInterface *dcacheInterface; 257 258 /** Pointer to IEW stage. */ 259 IEW *iewStage; 260 261 /** The memory dependence unit, which tracks/predicts memory dependences 262 * between instructions. 263 */ 264 MemDepUnit memDepUnit[Impl::MaxThreads]; 265 266 /** The queue to the execute stage. Issued instructions will be written 267 * into it. 268 */ 269 TimeBuffer<IssueStruct> *issueToExecuteQueue; 270 271 /** The backwards time buffer. */ 272 TimeBuffer<TimeStruct> *timeBuffer; 273 274 /** Wire to read information from timebuffer. */ 275 typename TimeBuffer<TimeStruct>::wire fromCommit; 276 277 /** Function unit pool. */ 278 FUPool *fuPool; 279 280 ////////////////////////////////////// 281 // Instruction lists, ready queues, and ordering 282 ////////////////////////////////////// 283 284 /** List of all the instructions in the IQ (some of which may be issued). */ 285 std::list<DynInstPtr> instList[Impl::MaxThreads]; 286 287 /** List of instructions that are ready to be executed. */ 288 std::list<DynInstPtr> instsToExecute; 289 290 /** 291 * Struct for comparing entries to be added to the priority queue. 292 * This gives reverse ordering to the instructions in terms of 293 * sequence numbers: the instructions with smaller sequence 294 * numbers (and hence are older) will be at the top of the 295 * priority queue. 296 */ 297 struct pqCompare { 298 bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const 299 { 300 return lhs->seqNum > rhs->seqNum; 301 } 302 }; 303 304 typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare> 305 ReadyInstQueue; 306 307 /** List of ready instructions, per op class. They are separated by op 308 * class to allow for easy mapping to FUs. 309 */ 310 ReadyInstQueue readyInsts[Num_OpClasses]; 311 312 /** List of non-speculative instructions that will be scheduled 313 * once the IQ gets a signal from commit. While it's redundant to 314 * have the key be a part of the value (the sequence number is stored 315 * inside of DynInst), when these instructions are woken up only 316 * the sequence number will be available. Thus it is most efficient to be 317 * able to search by the sequence number alone. 318 */ 319 std::map<InstSeqNum, DynInstPtr> nonSpecInsts; 320 321 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt; 322 323 /** Entry for the list age ordering by op class. */ 324 struct ListOrderEntry { 325 OpClass queueType; 326 InstSeqNum oldestInst; 327 }; 328 329 /** List that contains the age order of the oldest instruction of each 330 * ready queue. Used to select the oldest instruction available 331 * among op classes. 332 * @todo: Might be better to just move these entries around instead 333 * of creating new ones every time the position changes due to an 334 * instruction issuing. Not sure std::list supports this. 335 */ 336 std::list<ListOrderEntry> listOrder; 337 338 typedef typename std::list<ListOrderEntry>::iterator ListOrderIt; 339 340 /** Tracks if each ready queue is on the age order list. */ 341 bool queueOnList[Num_OpClasses]; 342 343 /** Iterators of each ready queue. Points to their spot in the age order 344 * list. 345 */ 346 ListOrderIt readyIt[Num_OpClasses]; 347 348 /** Add an op class to the age order list. */ 349 void addToOrderList(OpClass op_class); 350 351 /** 352 * Called when the oldest instruction has been removed from a ready queue; 353 * this places that ready queue into the proper spot in the age order list. 354 */ 355 void moveToYoungerInst(ListOrderIt age_order_it); 356 357 DependencyGraph<DynInstPtr> dependGraph; 358 359 ////////////////////////////////////// 360 // Various parameters 361 ////////////////////////////////////// 362 363 /** IQ Resource Sharing Policy */ 364 enum IQPolicy { 365 Dynamic, 366 Partitioned, 367 Threshold 368 }; 369 370 /** IQ sharing policy for SMT. */ 371 IQPolicy iqPolicy; 372 373 /** Number of Total Threads*/ 374 unsigned numThreads; 375 376 /** Pointer to list of active threads. */ 377 std::list<unsigned> *activeThreads; 378 379 /** Per Thread IQ count */ 380 unsigned count[Impl::MaxThreads]; 381 382 /** Max IQ Entries Per Thread */ 383 unsigned maxEntries[Impl::MaxThreads]; 384 385 /** Number of free IQ entries left. */ 386 unsigned freeEntries; 387 388 /** The number of entries in the instruction queue. */ 389 unsigned numEntries; 390 391 /** The total number of instructions that can be issued in one cycle. */ 392 unsigned totalWidth; 393 394 /** The number of physical registers in the CPU. */ 395 unsigned numPhysRegs; 396 397 /** The number of physical integer registers in the CPU. */ 398 unsigned numPhysIntRegs; 399 400 /** The number of floating point registers in the CPU. */ 401 unsigned numPhysFloatRegs; 402 403 /** Delay between commit stage and the IQ. 404 * @todo: Make there be a distinction between the delays within IEW. 405 */ 406 unsigned commitToIEWDelay; 407 408 /** Is the IQ switched out. */ 409 bool switchedOut; 410 411 /** The sequence number of the squashed instruction. */ 412 InstSeqNum squashedSeqNum[Impl::MaxThreads]; 413 414 /** A cache of the recently woken registers. It is 1 if the register 415 * has been woken up recently, and 0 if the register has been added 416 * to the dependency graph and has not yet received its value. It 417 * is basically a secondary scoreboard, and should pretty much mirror 418 * the scoreboard that exists in the rename map. 419 */ 420 std::vector<bool> regScoreboard; 421 422 /** Adds an instruction to the dependency graph, as a consumer. */ 423 bool addToDependents(DynInstPtr &new_inst); 424 425 /** Adds an instruction to the dependency graph, as a producer. */ 426 void addToProducers(DynInstPtr &new_inst); 427 428 /** Moves an instruction to the ready queue if it is ready. */ 429 void addIfReady(DynInstPtr &inst); 430 431 /** Debugging function to count how many entries are in the IQ. It does 432 * a linear walk through the instructions, so do not call this function 433 * during normal execution. 434 */ 435 int countInsts(); 436 437 /** Debugging function to dump all the list sizes, as well as print 438 * out the list of nonspeculative instructions. Should not be used 439 * in any other capacity, but it has no harmful sideaffects. 440 */ 441 void dumpLists(); 442 443 /** Debugging function to dump out all instructions that are in the 444 * IQ. 445 */ 446 void dumpInsts(); 447 448 /** Stat for number of instructions added. */ 449 Stats::Scalar<> iqInstsAdded; 450 /** Stat for number of non-speculative instructions added. */ 451 Stats::Scalar<> iqNonSpecInstsAdded; 452 453 Stats::Scalar<> iqInstsIssued; 454 /** Stat for number of integer instructions issued. */ 455 Stats::Scalar<> iqIntInstsIssued; 456 /** Stat for number of floating point instructions issued. */ 457 Stats::Scalar<> iqFloatInstsIssued; 458 /** Stat for number of branch instructions issued. */ 459 Stats::Scalar<> iqBranchInstsIssued; 460 /** Stat for number of memory instructions issued. */ 461 Stats::Scalar<> iqMemInstsIssued; 462 /** Stat for number of miscellaneous instructions issued. */ 463 Stats::Scalar<> iqMiscInstsIssued; 464 /** Stat for number of squashed instructions that were ready to issue. */ 465 Stats::Scalar<> iqSquashedInstsIssued; 466 /** Stat for number of squashed instructions examined when squashing. */ 467 Stats::Scalar<> iqSquashedInstsExamined; 468 /** Stat for number of squashed instruction operands examined when 469 * squashing. 470 */ 471 Stats::Scalar<> iqSquashedOperandsExamined; 472 /** Stat for number of non-speculative instructions removed due to a squash. 473 */ 474 Stats::Scalar<> iqSquashedNonSpecRemoved; 475 476 /** Distribution of number of instructions in the queue. */ 477 Stats::VectorDistribution<> queueResDist; 478 /** Distribution of the number of instructions issued. */ 479 Stats::Distribution<> numIssuedDist; 480 /** Distribution of the cycles it takes to issue an instruction. */ 481 Stats::VectorDistribution<> issueDelayDist; 482 483 /** Number of times an instruction could not be issued because a 484 * FU was busy. 485 */ 486 Stats::Vector<> statFuBusy; 487// Stats::Vector<> dist_unissued; 488 /** Stat for total number issued for each instruction type. */ 489 Stats::Vector2d<> statIssuedInstType; 490 491 /** Number of instructions issued per cycle. */ 492 Stats::Formula issueRate; 493// Stats::Formula issue_stores; 494// Stats::Formula issue_op_rate; 495 /** Number of times the FU was busy. */ 496 Stats::Vector<> fuBusy; 497 /** Number of times the FU was busy per instruction issued. */ 498 Stats::Formula fuBusyRate; 499}; 500 501#endif //__CPU_O3_INST_QUEUE_HH__ 502