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