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