cpu/o3/inst_queue_impl.hh

   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.
  46 const InstSeqNum MaxInstSeqNum = std::numeric_limits<InstSeqNum>::max();
  47
  48 template <class Impl>
  49 InstructionQueue<Impl>::InstructionQueue(Params &params)
  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
  92 template <class Impl>
  93 void
  94 InstructionQueue<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
 173 template <class Impl>
 174 void
 175 InstructionQueue<Impl>::setCPU(FullCPU *cpu_ptr)
 176 {
 177     cpu = cpu_ptr;
 178
 179     tail = cpu->instList.begin();
 180 }
 181
 182 template <class Impl>
 183 void
 184 InstructionQueue<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
 191 template <class Impl>
 192 void
 193 InstructionQueue<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
 201 template <class Impl>
 202 unsigned
 203 InstructionQueue<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.
 210 template <class Impl>
 211 bool
 212 InstructionQueue<Impl>::isFull()
 213 {
 214     if (freeEntries == 0) {
 215         return(true);
 216     } else {
 217         return(false);
 218     }
 219 }
 220
 221 template <class Impl>
 222 void
 223 InstructionQueue<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
 280 template <class Impl>
 281 void
 282 InstructionQueue<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.
 336 template <class Impl>
 337 void
 338 InstructionQueue<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.
 379 template <class Impl>
 380 void
 381 InstructionQueue<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
 624 template <class Impl>
 625 void
 626 InstructionQueue<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
 648 template <class Impl>
 649 void
 650 InstructionQueue<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
 719 template <class Impl>
 720 void
 721 InstructionQueue<Impl>::violation(DynInstPtr &store,
 722                                   DynInstPtr &faulting_load)
 723 {
 724     memDepUnit.violation(store, faulting_load);
 725 }
 726
 727 template <class Impl>
 728 void
 729 InstructionQueue<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
 749 template <class Impl>
 750 void
 751 InstructionQueue<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
 834 template <class Impl>
 835 void
 836 InstructionQueue<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
 845 template <class Impl>
 846 void
 847 InstructionQueue<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
 864 template <class Impl>
 865 void
 866 InstructionQueue<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
 899 template <class Impl>
 900 bool
 901 InstructionQueue<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
 945 template <class Impl>
 946 void
 947 InstructionQueue<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
 981 template <class Impl>
 982 void
 983 InstructionQueue<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  */
1052 template <class Impl>
1053 int
1054 InstructionQueue<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
1082 template <class Impl>
1083 void
1084 InstructionQueue<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
1109 template <class Impl>
1110 void
1111 InstructionQueue<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 }