inst_queue_impl.hh revision 2064
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 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// Todo: 30// Current ordering allows for 0 cycle added-to-scheduled. Could maybe fake 31// it; either do in reverse order, or have added instructions put into a 32// different ready queue that, in scheduleRreadyInsts(), gets put onto the 33// normal ready queue. This would however give only a one cycle delay, 34// but probably is more flexible to actually add in a delay parameter than 35// just running it backwards. 36 37#include <limits> 38#include <vector> 39 40#include "sim/root.hh" 41 42#include "cpu/o3/inst_queue.hh" 43 44// Either compile error or max int due to sign extension. 45// Hack to avoid compile warnings. 46const InstSeqNum MaxInstSeqNum = std::numeric_limits<InstSeqNum>::max(); 47 48template <class Impl> 49InstructionQueue<Impl>::InstructionQueue(Params ¶ms) 50 : memDepUnit(params), 51 numEntries(params.numIQEntries), 52 intWidth(params.executeIntWidth), 53 floatWidth(params.executeFloatWidth), 54 branchWidth(params.executeBranchWidth), 55 memoryWidth(params.executeMemoryWidth), 56 totalWidth(params.issueWidth), 57 numPhysIntRegs(params.numPhysIntRegs), 58 numPhysFloatRegs(params.numPhysFloatRegs), 59 commitToIEWDelay(params.commitToIEWDelay) 60{ 61 // Initialize the number of free IQ entries. 62 freeEntries = numEntries; 63 64 // Set the number of physical registers as the number of int + float 65 numPhysRegs = numPhysIntRegs + numPhysFloatRegs; 66 67 DPRINTF(IQ, "IQ: There are %i physical registers.\n", numPhysRegs); 68 69 //Create an entry for each physical register within the 70 //dependency graph. 71 dependGraph = new DependencyEntry[numPhysRegs]; 72 73 // Resize the register scoreboard. 74 regScoreboard.resize(numPhysRegs); 75 76 // Initialize all the head pointers to point to NULL, and all the 77 // entries as unready. 78 // Note that in actuality, the registers corresponding to the logical 79 // registers start off as ready. However this doesn't matter for the 80 // IQ as the instruction should have been correctly told if those 81 // registers are ready in rename. Thus it can all be initialized as 82 // unready. 83 for (int i = 0; i < numPhysRegs; ++i) 84 { 85 dependGraph[i].next = NULL; 86 dependGraph[i].inst = NULL; 87 regScoreboard[i] = false; 88 } 89 90} 91 92template <class Impl> 93void 94InstructionQueue<Impl>::regStats() 95{ 96 iqInstsAdded 97 .name(name() + ".iqInstsAdded") 98 .desc("Number of instructions added to the IQ (excludes non-spec)") 99 .prereq(iqInstsAdded); 100 101 iqNonSpecInstsAdded 102 .name(name() + ".iqNonSpecInstsAdded") 103 .desc("Number of non-speculative instructions added to the IQ") 104 .prereq(iqNonSpecInstsAdded); 105 106// iqIntInstsAdded; 107 108 iqIntInstsIssued 109 .name(name() + ".iqIntInstsIssued") 110 .desc("Number of integer instructions issued") 111 .prereq(iqIntInstsIssued); 112 113// iqFloatInstsAdded; 114 115 iqFloatInstsIssued 116 .name(name() + ".iqFloatInstsIssued") 117 .desc("Number of float instructions issued") 118 .prereq(iqFloatInstsIssued); 119 120// iqBranchInstsAdded; 121 122 iqBranchInstsIssued 123 .name(name() + ".iqBranchInstsIssued") 124 .desc("Number of branch instructions issued") 125 .prereq(iqBranchInstsIssued); 126 127// iqMemInstsAdded; 128 129 iqMemInstsIssued 130 .name(name() + ".iqMemInstsIssued") 131 .desc("Number of memory instructions issued") 132 .prereq(iqMemInstsIssued); 133 134// iqMiscInstsAdded; 135 136 iqMiscInstsIssued 137 .name(name() + ".iqMiscInstsIssued") 138 .desc("Number of miscellaneous instructions issued") 139 .prereq(iqMiscInstsIssued); 140 141 iqSquashedInstsIssued 142 .name(name() + ".iqSquashedInstsIssued") 143 .desc("Number of squashed instructions issued") 144 .prereq(iqSquashedInstsIssued); 145 146 iqLoopSquashStalls 147 .name(name() + ".iqLoopSquashStalls") 148 .desc("Number of times issue loop had to restart due to squashed " 149 "inst; mainly for profiling") 150 .prereq(iqLoopSquashStalls); 151 152 iqSquashedInstsExamined 153 .name(name() + ".iqSquashedInstsExamined") 154 .desc("Number of squashed instructions iterated over during squash;" 155 " mainly for profiling") 156 .prereq(iqSquashedInstsExamined); 157 158 iqSquashedOperandsExamined 159 .name(name() + ".iqSquashedOperandsExamined") 160 .desc("Number of squashed operands that are examined and possibly " 161 "removed from graph") 162 .prereq(iqSquashedOperandsExamined); 163 164 iqSquashedNonSpecRemoved 165 .name(name() + ".iqSquashedNonSpecRemoved") 166 .desc("Number of squashed non-spec instructions that were removed") 167 .prereq(iqSquashedNonSpecRemoved); 168 169 // Tell mem dependence unit to reg stats as well. 170 memDepUnit.regStats(); 171} 172 173template <class Impl> 174void 175InstructionQueue<Impl>::setCPU(FullCPU *cpu_ptr) 176{ 177 cpu = cpu_ptr; 178 179 tail = cpu->instList.begin(); 180} 181 182template <class Impl> 183void 184InstructionQueue<Impl>::setIssueToExecuteQueue( 185 TimeBuffer<IssueStruct> *i2e_ptr) 186{ 187 DPRINTF(IQ, "IQ: Set the issue to execute queue.\n"); 188 issueToExecuteQueue = i2e_ptr; 189} 190 191template <class Impl> 192void 193InstructionQueue<Impl>::setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr) 194{ 195 DPRINTF(IQ, "IQ: Set the time buffer.\n"); 196 timeBuffer = tb_ptr; 197 198 fromCommit = timeBuffer->getWire(-commitToIEWDelay); 199} 200 201template <class Impl> 202unsigned 203InstructionQueue<Impl>::numFreeEntries() 204{ 205 return freeEntries; 206} 207 208// Might want to do something more complex if it knows how many instructions 209// will be issued this cycle. 210template <class Impl> 211bool 212InstructionQueue<Impl>::isFull() 213{ 214 if (freeEntries == 0) { 215 return(true); 216 } else { 217 return(false); 218 } 219} 220 221template <class Impl> 222void 223InstructionQueue<Impl>::insert(DynInstPtr &new_inst) 224{ 225 // Make sure the instruction is valid 226 assert(new_inst); 227 228 DPRINTF(IQ, "IQ: Adding instruction PC %#x to the IQ.\n", 229 new_inst->readPC()); 230 231 // Check if there are any free entries. Panic if there are none. 232 // Might want to have this return a fault in the future instead of 233 // panicing. 234 assert(freeEntries != 0); 235 236 // If the IQ currently has nothing in it, then there's a possibility 237 // that the tail iterator is invalid (might have been pointing at an 238 // instruction that was retired). Reset the tail iterator. 239 if (freeEntries == numEntries) { 240 tail = cpu->instList.begin(); 241 } 242 243 // Move the tail iterator. Instructions may not have been issued 244 // to the IQ, so we may have to increment the iterator more than once. 245 while ((*tail) != new_inst) { 246 tail++; 247 248 // Make sure the tail iterator points at something legal. 249 assert(tail != cpu->instList.end()); 250 } 251 252 253 // Decrease the number of free entries. 254 --freeEntries; 255 256 // Look through its source registers (physical regs), and mark any 257 // dependencies. 258 addToDependents(new_inst); 259 260 // Have this instruction set itself as the producer of its destination 261 // register(s). 262 createDependency(new_inst); 263 264 // If it's a memory instruction, add it to the memory dependency 265 // unit. 266 if (new_inst->isMemRef()) { 267 memDepUnit.insert(new_inst); 268 // Uh..forgot to look it up and put it on the proper dependency list 269 // if the instruction should not go yet. 270 } else { 271 // If the instruction is ready then add it to the ready list. 272 addIfReady(new_inst); 273 } 274 275 ++iqInstsAdded; 276 277 assert(freeEntries == (numEntries - countInsts())); 278} 279 280template <class Impl> 281void 282InstructionQueue<Impl>::insertNonSpec(DynInstPtr &inst) 283{ 284 nonSpecInsts[inst->seqNum] = inst; 285 286 // @todo: Clean up this code; can do it by setting inst as unable 287 // to issue, then calling normal insert on the inst. 288 289 // Make sure the instruction is valid 290 assert(inst); 291 292 DPRINTF(IQ, "IQ: Adding instruction PC %#x to the IQ.\n", 293 inst->readPC()); 294 295 // Check if there are any free entries. Panic if there are none. 296 // Might want to have this return a fault in the future instead of 297 // panicing. 298 assert(freeEntries != 0); 299 300 // If the IQ currently has nothing in it, then there's a possibility 301 // that the tail iterator is invalid (might have been pointing at an 302 // instruction that was retired). Reset the tail iterator. 303 if (freeEntries == numEntries) { 304 tail = cpu->instList.begin(); 305 } 306 307 // Move the tail iterator. Instructions may not have been issued 308 // to the IQ, so we may have to increment the iterator more than once. 309 while ((*tail) != inst) { 310 tail++; 311 312 // Make sure the tail iterator points at something legal. 313 assert(tail != cpu->instList.end()); 314 } 315 316 // Decrease the number of free entries. 317 --freeEntries; 318 319 // Have this instruction set itself as the producer of its destination 320 // register(s). 321 createDependency(inst); 322 323 // If it's a memory instruction, add it to the memory dependency 324 // unit. 325 if (inst->isMemRef()) { 326 memDepUnit.insertNonSpec(inst); 327 } 328 329 ++iqNonSpecInstsAdded; 330} 331 332// Slightly hack function to advance the tail iterator in the case that 333// the IEW stage issues an instruction that is not added to the IQ. This 334// is needed in case a long chain of such instructions occurs. 335// I don't think this is used anymore. 336template <class Impl> 337void 338InstructionQueue<Impl>::advanceTail(DynInstPtr &inst) 339{ 340 // Make sure the instruction is valid 341 assert(inst); 342 343 DPRINTF(IQ, "IQ: Adding instruction PC %#x to the IQ.\n", 344 inst->readPC()); 345 346 // Check if there are any free entries. Panic if there are none. 347 // Might want to have this return a fault in the future instead of 348 // panicing. 349 assert(freeEntries != 0); 350 351 // If the IQ currently has nothing in it, then there's a possibility 352 // that the tail iterator is invalid (might have been pointing at an 353 // instruction that was retired). Reset the tail iterator. 354 if (freeEntries == numEntries) { 355 tail = cpu->instList.begin(); 356 } 357 358 // Move the tail iterator. Instructions may not have been issued 359 // to the IQ, so we may have to increment the iterator more than once. 360 while ((*tail) != inst) { 361 tail++; 362 363 // Make sure the tail iterator points at something legal. 364 assert(tail != cpu->instList.end()); 365 } 366 367 assert(freeEntries <= numEntries); 368 369 // Have this instruction set itself as the producer of its destination 370 // register(s). 371 createDependency(inst); 372} 373 374// Need to make sure the number of float and integer instructions 375// issued does not exceed the total issue bandwidth. 376// @todo: Figure out a better way to remove the squashed items from the 377// lists. Checking the top item of each list to see if it's squashed 378// wastes time and forces jumps. 379template <class Impl> 380void 381InstructionQueue<Impl>::scheduleReadyInsts() 382{ 383 DPRINTF(IQ, "IQ: Attempting to schedule ready instructions from " 384 "the IQ.\n"); 385 386 int int_issued = 0; 387 int float_issued = 0; 388 int branch_issued = 0; 389 int memory_issued = 0; 390 int squashed_issued = 0; 391 int total_issued = 0; 392 393 IssueStruct *i2e_info = issueToExecuteQueue->access(0); 394 395 bool insts_available = !readyBranchInsts.empty() || 396 !readyIntInsts.empty() || 397 !readyFloatInsts.empty() || 398 !memDepUnit.empty() || 399 !readyMiscInsts.empty() || 400 !squashedInsts.empty(); 401 402 // Note: Requires a globally defined constant. 403 InstSeqNum oldest_inst = MaxInstSeqNum; 404 InstList list_with_oldest = None; 405 406 // Temporary values. 407 DynInstPtr int_head_inst; 408 DynInstPtr float_head_inst; 409 DynInstPtr branch_head_inst; 410 DynInstPtr mem_head_inst; 411 DynInstPtr misc_head_inst; 412 DynInstPtr squashed_head_inst; 413 414 // Somewhat nasty code to look at all of the lists where issuable 415 // instructions are located, and choose the oldest instruction among 416 // those lists. Consider a rewrite in the future. 417 while (insts_available && total_issued < totalWidth) 418 { 419 // Set this to false. Each if-block is required to set it to true 420 // if there were instructions available this check. This will cause 421 // this loop to run once more than necessary, but avoids extra calls. 422 insts_available = false; 423 424 oldest_inst = MaxInstSeqNum; 425 426 list_with_oldest = None; 427 428 if (!readyIntInsts.empty() && 429 int_issued < intWidth) { 430 431 insts_available = true; 432 433 int_head_inst = readyIntInsts.top(); 434 435 if (int_head_inst->isSquashed()) { 436 readyIntInsts.pop(); 437 438 ++iqLoopSquashStalls; 439 440 continue; 441 } 442 443 oldest_inst = int_head_inst->seqNum; 444 445 list_with_oldest = Int; 446 } 447 448 if (!readyFloatInsts.empty() && 449 float_issued < floatWidth) { 450 451 insts_available = true; 452 453 float_head_inst = readyFloatInsts.top(); 454 455 if (float_head_inst->isSquashed()) { 456 readyFloatInsts.pop(); 457 458 ++iqLoopSquashStalls; 459 460 continue; 461 } else if (float_head_inst->seqNum < oldest_inst) { 462 oldest_inst = float_head_inst->seqNum; 463 464 list_with_oldest = Float; 465 } 466 } 467 468 if (!readyBranchInsts.empty() && 469 branch_issued < branchWidth) { 470 471 insts_available = true; 472 473 branch_head_inst = readyBranchInsts.top(); 474 475 if (branch_head_inst->isSquashed()) { 476 readyBranchInsts.pop(); 477 478 ++iqLoopSquashStalls; 479 480 continue; 481 } else if (branch_head_inst->seqNum < oldest_inst) { 482 oldest_inst = branch_head_inst->seqNum; 483 484 list_with_oldest = Branch; 485 } 486 487 } 488 489 if (!memDepUnit.empty() && 490 memory_issued < memoryWidth) { 491 492 insts_available = true; 493 494 mem_head_inst = memDepUnit.top(); 495 496 if (mem_head_inst->isSquashed()) { 497 memDepUnit.pop(); 498 499 ++iqLoopSquashStalls; 500 501 continue; 502 } else if (mem_head_inst->seqNum < oldest_inst) { 503 oldest_inst = mem_head_inst->seqNum; 504 505 list_with_oldest = Memory; 506 } 507 } 508 509 if (!readyMiscInsts.empty()) { 510 511 insts_available = true; 512 513 misc_head_inst = readyMiscInsts.top(); 514 515 if (misc_head_inst->isSquashed()) { 516 readyMiscInsts.pop(); 517 518 ++iqLoopSquashStalls; 519 520 continue; 521 } else if (misc_head_inst->seqNum < oldest_inst) { 522 oldest_inst = misc_head_inst->seqNum; 523 524 list_with_oldest = Misc; 525 } 526 } 527 528 if (!squashedInsts.empty()) { 529 530 insts_available = true; 531 532 squashed_head_inst = squashedInsts.top(); 533 534 if (squashed_head_inst->seqNum < oldest_inst) { 535 list_with_oldest = Squashed; 536 } 537 538 } 539 540 DynInstPtr issuing_inst = NULL; 541 542 switch (list_with_oldest) { 543 case None: 544 DPRINTF(IQ, "IQ: Not able to schedule any instructions. Issuing " 545 "inst is %#x.\n", issuing_inst); 546 break; 547 548 case Int: 549 issuing_inst = int_head_inst; 550 readyIntInsts.pop(); 551 ++int_issued; 552 DPRINTF(IQ, "IQ: Issuing integer instruction PC %#x.\n", 553 issuing_inst->readPC()); 554 break; 555 556 case Float: 557 issuing_inst = float_head_inst; 558 readyFloatInsts.pop(); 559 ++float_issued; 560 DPRINTF(IQ, "IQ: Issuing float instruction PC %#x.\n", 561 issuing_inst->readPC()); 562 break; 563 564 case Branch: 565 issuing_inst = branch_head_inst; 566 readyBranchInsts.pop(); 567 ++branch_issued; 568 DPRINTF(IQ, "IQ: Issuing branch instruction PC %#x.\n", 569 issuing_inst->readPC()); 570 break; 571 572 case Memory: 573 issuing_inst = mem_head_inst; 574 575 memDepUnit.pop(); 576 ++memory_issued; 577 DPRINTF(IQ, "IQ: Issuing memory instruction PC %#x.\n", 578 issuing_inst->readPC()); 579 break; 580 581 case Misc: 582 issuing_inst = misc_head_inst; 583 readyMiscInsts.pop(); 584 585 ++iqMiscInstsIssued; 586 587 DPRINTF(IQ, "IQ: Issuing a miscellaneous instruction PC %#x.\n", 588 issuing_inst->readPC()); 589 break; 590 591 case Squashed: 592 assert(0 && "Squashed insts should not issue any more!"); 593 squashedInsts.pop(); 594 // Set the squashed instruction as able to commit so that commit 595 // can just drop it from the ROB. This is a bit faked. 596 ++squashed_issued; 597 ++freeEntries; 598 599 DPRINTF(IQ, "IQ: Issuing squashed instruction PC %#x.\n", 600 squashed_head_inst->readPC()); 601 break; 602 } 603 604 if (list_with_oldest != None && list_with_oldest != Squashed) { 605 i2e_info->insts[total_issued] = issuing_inst; 606 i2e_info->size++; 607 608 issuing_inst->setIssued(); 609 610 ++freeEntries; 611 ++total_issued; 612 } 613 614 assert(freeEntries == (numEntries - countInsts())); 615 } 616 617 iqIntInstsIssued += int_issued; 618 iqFloatInstsIssued += float_issued; 619 iqBranchInstsIssued += branch_issued; 620 iqMemInstsIssued += memory_issued; 621 iqSquashedInstsIssued += squashed_issued; 622} 623 624template <class Impl> 625void 626InstructionQueue<Impl>::scheduleNonSpec(const InstSeqNum &inst) 627{ 628 DPRINTF(IQ, "IQ: Marking nonspeculative instruction with sequence " 629 "number %i as ready to execute.\n", inst); 630 631 non_spec_it_t inst_it = nonSpecInsts.find(inst); 632 633 assert(inst_it != nonSpecInsts.end()); 634 635 // Mark this instruction as ready to issue. 636 (*inst_it).second->setCanIssue(); 637 638 // Now schedule the instruction. 639 if (!(*inst_it).second->isMemRef()) { 640 addIfReady((*inst_it).second); 641 } else { 642 memDepUnit.nonSpecInstReady((*inst_it).second); 643 } 644 645 nonSpecInsts.erase(inst_it); 646} 647 648template <class Impl> 649void 650InstructionQueue<Impl>::wakeDependents(DynInstPtr &completed_inst) 651{ 652 DPRINTF(IQ, "IQ: Waking dependents of completed instruction.\n"); 653 //Look at the physical destination register of the DynInst 654 //and look it up on the dependency graph. Then mark as ready 655 //any instructions within the instruction queue. 656 DependencyEntry *curr; 657 658 // Tell the memory dependence unit to wake any dependents on this 659 // instruction if it is a memory instruction. 660 661 if (completed_inst->isMemRef()) { 662 memDepUnit.wakeDependents(completed_inst); 663 } 664 665 for (int dest_reg_idx = 0; 666 dest_reg_idx < completed_inst->numDestRegs(); 667 dest_reg_idx++) 668 { 669 PhysRegIndex dest_reg = 670 completed_inst->renamedDestRegIdx(dest_reg_idx); 671 672 // Special case of uniq or control registers. They are not 673 // handled by the IQ and thus have no dependency graph entry. 674 // @todo Figure out a cleaner way to handle this. 675 if (dest_reg >= numPhysRegs) { 676 continue; 677 } 678 679 DPRINTF(IQ, "IQ: Waking any dependents on register %i.\n", 680 (int) dest_reg); 681 682 //Maybe abstract this part into a function. 683 //Go through the dependency chain, marking the registers as ready 684 //within the waiting instructions. 685 while (dependGraph[dest_reg].next) { 686 687 curr = dependGraph[dest_reg].next; 688 689 DPRINTF(IQ, "IQ: Waking up a dependent instruction, PC%#x.\n", 690 curr->inst->readPC()); 691 692 // Might want to give more information to the instruction 693 // so that it knows which of its source registers is ready. 694 // However that would mean that the dependency graph entries 695 // would need to hold the src_reg_idx. 696 curr->inst->markSrcRegReady(); 697 698 addIfReady(curr->inst); 699 700 dependGraph[dest_reg].next = curr->next; 701 702 DependencyEntry::mem_alloc_counter--; 703 704 curr->inst = NULL; 705 706 delete curr; 707 } 708 709 // Reset the head node now that all of its dependents have been woken 710 // up. 711 dependGraph[dest_reg].next = NULL; 712 dependGraph[dest_reg].inst = NULL; 713 714 // Mark the scoreboard as having that register ready. 715 regScoreboard[dest_reg] = true; 716 } 717} 718 719template <class Impl> 720void 721InstructionQueue<Impl>::violation(DynInstPtr &store, 722 DynInstPtr &faulting_load) 723{ 724 memDepUnit.violation(store, faulting_load); 725} 726 727template <class Impl> 728void 729InstructionQueue<Impl>::squash() 730{ 731 DPRINTF(IQ, "IQ: Starting to squash instructions in the IQ.\n"); 732 733 // Read instruction sequence number of last instruction out of the 734 // time buffer. 735 squashedSeqNum = fromCommit->commitInfo.doneSeqNum; 736 737 // Setup the squash iterator to point to the tail. 738 squashIt = tail; 739 740 // Call doSquash if there are insts in the IQ 741 if (freeEntries != numEntries) { 742 doSquash(); 743 } 744 745 // Also tell the memory dependence unit to squash. 746 memDepUnit.squash(squashedSeqNum); 747} 748 749template <class Impl> 750void 751InstructionQueue<Impl>::doSquash() 752{ 753 // Make sure the squash iterator isn't pointing to nothing. 754 assert(squashIt != cpu->instList.end()); 755 // Make sure the squashed sequence number is valid. 756 assert(squashedSeqNum != 0); 757 758 DPRINTF(IQ, "IQ: Squashing instructions in the IQ.\n"); 759 760 // Squash any instructions younger than the squashed sequence number 761 // given. 762 while ((*squashIt)->seqNum > squashedSeqNum) { 763 DynInstPtr squashed_inst = (*squashIt); 764 765 // Only handle the instruction if it actually is in the IQ and 766 // hasn't already been squashed in the IQ. 767 if (!squashed_inst->isIssued() && 768 !squashed_inst->isSquashedInIQ()) { 769 770 // Remove the instruction from the dependency list. 771 // Hack for now: These below don't add themselves to the 772 // dependency list, so don't try to remove them. 773 if (!squashed_inst->isNonSpeculative()/* && 774 !squashed_inst->isStore()*/ 775 ) { 776 777 for (int src_reg_idx = 0; 778 src_reg_idx < squashed_inst->numSrcRegs(); 779 src_reg_idx++) 780 { 781 PhysRegIndex src_reg = 782 squashed_inst->renamedSrcRegIdx(src_reg_idx); 783 784 // Only remove it from the dependency graph if it was 785 // placed there in the first place. 786 // HACK: This assumes that instructions woken up from the 787 // dependency chain aren't informed that a specific src 788 // register has become ready. This may not always be true 789 // in the future. 790 if (!squashed_inst->isReadySrcRegIdx(src_reg_idx) && 791 src_reg < numPhysRegs) { 792 dependGraph[src_reg].remove(squashed_inst); 793 } 794 795 ++iqSquashedOperandsExamined; 796 } 797 798 // Might want to remove producers as well. 799 } else { 800 nonSpecInsts[squashed_inst->seqNum] = NULL; 801 802 nonSpecInsts.erase(squashed_inst->seqNum); 803 804 ++iqSquashedNonSpecRemoved; 805 } 806 807 // Might want to also clear out the head of the dependency graph. 808 809 // Mark it as squashed within the IQ. 810 squashed_inst->setSquashedInIQ(); 811 812// squashedInsts.push(squashed_inst); 813 squashed_inst->setIssued(); 814 squashed_inst->setCanCommit(); 815 816 ++freeEntries; 817 818 DPRINTF(IQ, "IQ: Instruction PC %#x squashed.\n", 819 squashed_inst->readPC()); 820 } 821 822 --squashIt; 823 ++iqSquashedInstsExamined; 824 } 825 826 assert(freeEntries <= numEntries); 827 828 if (freeEntries == numEntries) { 829 tail = cpu->instList.end(); 830 } 831 832} 833 834template <class Impl> 835void 836InstructionQueue<Impl>::stopSquash() 837{ 838 // Clear up the squash variables to ensure that squashing doesn't 839 // get called improperly. 840 squashedSeqNum = 0; 841 842 squashIt = cpu->instList.end(); 843} 844 845template <class Impl> 846void 847InstructionQueue<Impl>::DependencyEntry::insert(DynInstPtr &new_inst) 848{ 849 //Add this new, dependent instruction at the head of the dependency 850 //chain. 851 852 // First create the entry that will be added to the head of the 853 // dependency chain. 854 DependencyEntry *new_entry = new DependencyEntry; 855 new_entry->next = this->next; 856 new_entry->inst = new_inst; 857 858 // Then actually add it to the chain. 859 this->next = new_entry; 860 861 ++mem_alloc_counter; 862} 863 864template <class Impl> 865void 866InstructionQueue<Impl>::DependencyEntry::remove(DynInstPtr &inst_to_remove) 867{ 868 DependencyEntry *prev = this; 869 DependencyEntry *curr = this->next; 870 871 // Make sure curr isn't NULL. Because this instruction is being 872 // removed from a dependency list, it must have been placed there at 873 // an earlier time. The dependency chain should not be empty, 874 // unless the instruction dependent upon it is already ready. 875 if (curr == NULL) { 876 return; 877 } 878 879 // Find the instruction to remove within the dependency linked list. 880 while(curr->inst != inst_to_remove) 881 { 882 prev = curr; 883 curr = curr->next; 884 885 assert(curr != NULL); 886 } 887 888 // Now remove this instruction from the list. 889 prev->next = curr->next; 890 891 --mem_alloc_counter; 892 893 // Could push this off to the destructor of DependencyEntry 894 curr->inst = NULL; 895 896 delete curr; 897} 898 899template <class Impl> 900bool 901InstructionQueue<Impl>::addToDependents(DynInstPtr &new_inst) 902{ 903 // Loop through the instruction's source registers, adding 904 // them to the dependency list if they are not ready. 905 int8_t total_src_regs = new_inst->numSrcRegs(); 906 bool return_val = false; 907 908 for (int src_reg_idx = 0; 909 src_reg_idx < total_src_regs; 910 src_reg_idx++) 911 { 912 // Only add it to the dependency graph if it's not ready. 913 if (!new_inst->isReadySrcRegIdx(src_reg_idx)) { 914 PhysRegIndex src_reg = new_inst->renamedSrcRegIdx(src_reg_idx); 915 916 // Check the IQ's scoreboard to make sure the register 917 // hasn't become ready while the instruction was in flight 918 // between stages. Only if it really isn't ready should 919 // it be added to the dependency graph. 920 if (src_reg >= numPhysRegs) { 921 continue; 922 } else if (regScoreboard[src_reg] == false) { 923 DPRINTF(IQ, "IQ: Instruction PC %#x has src reg %i that " 924 "is being added to the dependency chain.\n", 925 new_inst->readPC(), src_reg); 926 927 dependGraph[src_reg].insert(new_inst); 928 929 // Change the return value to indicate that something 930 // was added to the dependency graph. 931 return_val = true; 932 } else { 933 DPRINTF(IQ, "IQ: Instruction PC %#x has src reg %i that " 934 "became ready before it reached the IQ.\n", 935 new_inst->readPC(), src_reg); 936 // Mark a register ready within the instruction. 937 new_inst->markSrcRegReady(); 938 } 939 } 940 } 941 942 return return_val; 943} 944 945template <class Impl> 946void 947InstructionQueue<Impl>::createDependency(DynInstPtr &new_inst) 948{ 949 //Actually nothing really needs to be marked when an 950 //instruction becomes the producer of a register's value, 951 //but for convenience a ptr to the producing instruction will 952 //be placed in the head node of the dependency links. 953 int8_t total_dest_regs = new_inst->numDestRegs(); 954 955 for (int dest_reg_idx = 0; 956 dest_reg_idx < total_dest_regs; 957 dest_reg_idx++) 958 { 959 PhysRegIndex dest_reg = new_inst->renamedDestRegIdx(dest_reg_idx); 960 961 // Instructions that use the misc regs will have a reg number 962 // higher than the normal physical registers. In this case these 963 // registers are not renamed, and there is no need to track 964 // dependencies as these instructions must be executed at commit. 965 if (dest_reg >= numPhysRegs) { 966 continue; 967 } 968 969 dependGraph[dest_reg].inst = new_inst; 970 971 if (dependGraph[dest_reg].next) { 972 dumpDependGraph(); 973 panic("IQ: Dependency graph not empty!"); 974 } 975 976 // Mark the scoreboard to say it's not yet ready. 977 regScoreboard[dest_reg] = false; 978 } 979} 980 981template <class Impl> 982void 983InstructionQueue<Impl>::addIfReady(DynInstPtr &inst) 984{ 985 //If the instruction now has all of its source registers 986 // available, then add it to the list of ready instructions. 987 if (inst->readyToIssue()) { 988 989 //Add the instruction to the proper ready list. 990 if (inst->isControl()) { 991 992 DPRINTF(IQ, "IQ: Branch instruction is ready to issue, " 993 "putting it onto the ready list, PC %#x.\n", 994 inst->readPC()); 995 readyBranchInsts.push(inst); 996 997 } else if (inst->isMemRef()) { 998 999 DPRINTF(IQ, "IQ: Checking if memory instruction can issue.\n"); 1000 1001 // Message to the mem dependence unit that this instruction has 1002 // its registers ready. 1003 1004 memDepUnit.regsReady(inst); 1005 1006#if 0 1007 if (memDepUnit.readyToIssue(inst)) { 1008 DPRINTF(IQ, "IQ: Memory instruction is ready to issue, " 1009 "putting it onto the ready list, PC %#x.\n", 1010 inst->readPC()); 1011 readyMemInsts.push(inst); 1012 } else { 1013 // Make dependent on the store. 1014 // Will need some way to get the store instruction it should 1015 // be dependent upon; then when the store issues it can 1016 // put the instruction on the ready list. 1017 // Yet another tree? 1018 assert(0 && "Instruction has no way to actually issue"); 1019 } 1020#endif 1021 1022 } else if (inst->isInteger()) { 1023 1024 DPRINTF(IQ, "IQ: Integer instruction is ready to issue, " 1025 "putting it onto the ready list, PC %#x.\n", 1026 inst->readPC()); 1027 readyIntInsts.push(inst); 1028 1029 } else if (inst->isFloating()) { 1030 1031 DPRINTF(IQ, "IQ: Floating instruction is ready to issue, " 1032 "putting it onto the ready list, PC %#x.\n", 1033 inst->readPC()); 1034 readyFloatInsts.push(inst); 1035 1036 } else { 1037 DPRINTF(IQ, "IQ: Miscellaneous instruction is ready to issue, " 1038 "putting it onto the ready list, PC %#x..\n", 1039 inst->readPC()); 1040 1041 readyMiscInsts.push(inst); 1042 } 1043 } 1044} 1045 1046/* 1047 * Caution, this function must not be called prior to tail being updated at 1048 * least once, otherwise it will fail the assertion. This is because 1049 * instList.begin() actually changes upon the insertion of an element into the 1050 * list when the list is empty. 1051 */ 1052template <class Impl> 1053int 1054InstructionQueue<Impl>::countInsts() 1055{ 1056 ListIt count_it = cpu->instList.begin(); 1057 int total_insts = 0; 1058 1059 if (tail == cpu->instList.end()) 1060 return 0; 1061 1062 while (count_it != tail) { 1063 if (!(*count_it)->isIssued()) { 1064 ++total_insts; 1065 } 1066 1067 ++count_it; 1068 1069 assert(count_it != cpu->instList.end()); 1070 } 1071 1072 // Need to count the tail iterator as well. 1073 if (count_it != cpu->instList.end() && 1074 (*count_it) && 1075 !(*count_it)->isIssued()) { 1076 ++total_insts; 1077 } 1078 1079 return total_insts; 1080} 1081 1082template <class Impl> 1083void 1084InstructionQueue<Impl>::dumpDependGraph() 1085{ 1086 DependencyEntry *curr; 1087 1088 for (int i = 0; i < numPhysRegs; ++i) 1089 { 1090 curr = &dependGraph[i]; 1091 1092 if (curr->inst) { 1093 cprintf("dependGraph[%i]: producer: %#x consumer: ", i, 1094 curr->inst->readPC()); 1095 } else { 1096 cprintf("dependGraph[%i]: No producer. consumer: ", i); 1097 } 1098 1099 while (curr->next != NULL) { 1100 curr = curr->next; 1101 1102 cprintf("%#x ", curr->inst->readPC()); 1103 } 1104 1105 cprintf("\n"); 1106 } 1107} 1108 1109template <class Impl> 1110void 1111InstructionQueue<Impl>::dumpLists() 1112{ 1113 cprintf("Ready integer list size: %i\n", readyIntInsts.size()); 1114 1115 cprintf("Ready float list size: %i\n", readyFloatInsts.size()); 1116 1117 cprintf("Ready branch list size: %i\n", readyBranchInsts.size()); 1118 1119 cprintf("Ready misc list size: %i\n", readyMiscInsts.size()); 1120 1121 cprintf("Squashed list size: %i\n", squashedInsts.size()); 1122 1123 cprintf("Non speculative list size: %i\n", nonSpecInsts.size()); 1124 1125 non_spec_it_t non_spec_it = nonSpecInsts.begin(); 1126 1127 cprintf("Non speculative list: "); 1128 1129 while (non_spec_it != nonSpecInsts.end()) { 1130 cprintf("%#x ", (*non_spec_it).second->readPC()); 1131 ++non_spec_it; 1132 } 1133 1134 cprintf("\n"); 1135 1136} 1137