src/cpu/o3/rob_impl.hh

   1 /*
   2  * Copyright (c) 2004-2006 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Kevin Lim
  29  *          Korey Sewell
  30  */
  31
  32 #include "config/full_system.hh"
  33 #include "cpu/o3/rob.hh"
  34
  35 #include <list>
  36
  37 template <class Impl>
  38 ROB<Impl>::ROB(unsigned _numEntries, unsigned _squashWidth,
  39                std::string _smtROBPolicy, unsigned _smtROBThreshold,
  40                unsigned _numThreads)
  41     : numEntries(_numEntries),
  42       squashWidth(_squashWidth),
  43       numInstsInROB(0),
  44       numThreads(_numThreads)
  45 {
  46     for (int tid=0; tid  < numThreads; tid++) {
  47         squashedSeqNum[tid] = 0;
  48         doneSquashing[tid] = true;
  49         threadEntries[tid] = 0;
  50     }
  51
  52     std::string policy = _smtROBPolicy;
  53
  54     //Convert string to lowercase
  55     std::transform(policy.begin(), policy.end(), policy.begin(),
  56                    (int(*)(int)) tolower);
  57
  58     //Figure out rob policy
  59     if (policy == "dynamic") {
  60         robPolicy = Dynamic;
  61
  62         //Set Max Entries to Total ROB Capacity
  63         for (int i = 0; i < numThreads; i++) {
  64             maxEntries[i]=numEntries;
  65         }
  66
  67     } else if (policy == "partitioned") {
  68         robPolicy = Partitioned;
  69 //      DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");
  70
  71         //@todo:make work if part_amt doesnt divide evenly.
  72         int part_amt = numEntries / numThreads;
  73
  74         //Divide ROB up evenly
  75         for (int i = 0; i < numThreads; i++) {
  76             maxEntries[i]=part_amt;
  77         }
  78
  79     } else if (policy == "threshold") {
  80         robPolicy = Threshold;
  81 //      DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");
  82
  83         int threshold =  _smtROBThreshold;;
  84
  85         //Divide up by threshold amount
  86         for (int i = 0; i < numThreads; i++) {
  87             maxEntries[i]=threshold;
  88         }
  89     } else {
  90         assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic,"
  91                     "Partitioned, Threshold}");
  92     }
  93 }
  94
  95 template <class Impl>
  96 std::string
  97 ROB<Impl>::name() const
  98 {
  99     return cpu->name() + ".rob";
 100 }
 101
 102 template <class Impl>
 103 void
 104 ROB<Impl>::setCPU(O3CPU *cpu_ptr)
 105 {
 106     cpu = cpu_ptr;
 107
 108     // Set the per-thread iterators to the end of the instruction list.
 109     for (int i=0; i < numThreads;i++) {
 110         squashIt[i] = instList[i].end();
 111     }
 112
 113     // Initialize the "universal" ROB head & tail point to invalid
 114     // pointers
 115     head = instList[0].end();
 116     tail = instList[0].end();
 117 }
 118
 119 template <class Impl>
 120 void
 121 ROB<Impl>::setActiveThreads(std::list<unsigned> *at_ptr)
 122 {
 123     DPRINTF(ROB, "Setting active threads list pointer.\n");
 124     activeThreads = at_ptr;
 125 }
 126
 127 template <class Impl>
 128 void
 129 ROB<Impl>::switchOut()
 130 {
 131     for (int tid = 0; tid < numThreads; tid++) {
 132         instList[tid].clear();
 133     }
 134 }
 135
 136 template <class Impl>
 137 void
 138 ROB<Impl>::takeOverFrom()
 139 {
 140     for (int tid=0; tid  < numThreads; tid++) {
 141         doneSquashing[tid] = true;
 142         threadEntries[tid] = 0;
 143         squashIt[tid] = instList[tid].end();
 144     }
 145     numInstsInROB = 0;
 146
 147     // Initialize the "universal" ROB head & tail point to invalid
 148     // pointers
 149     head = instList[0].end();
 150     tail = instList[0].end();
 151 }
 152
 153 template <class Impl>
 154 void
 155 ROB<Impl>::resetEntries()
 156 {
 157     if (robPolicy != Dynamic || numThreads > 1) {
 158         int active_threads = activeThreads->size();
 159
 160         std::list<unsigned>::iterator threads = activeThreads->begin();
 161         std::list<unsigned>::iterator end = activeThreads->end();
 162
 163         while (threads != end) {
 164             unsigned tid = *threads++;
 165
 166             if (robPolicy == Partitioned) {
 167                 maxEntries[tid] = numEntries / active_threads;
 168             } else if (robPolicy == Threshold && active_threads == 1) {
 169                 maxEntries[tid] = numEntries;
 170             }
 171         }
 172     }
 173 }
 174
 175 template <class Impl>
 176 int
 177 ROB<Impl>::entryAmount(int num_threads)
 178 {
 179     if (robPolicy == Partitioned) {
 180         return numEntries / num_threads;
 181     } else {
 182         return 0;
 183     }
 184 }
 185
 186 template <class Impl>
 187 int
 188 ROB<Impl>::countInsts()
 189 {
 190     int total=0;
 191
 192     for (int i=0;i < numThreads;i++)
 193         total += countInsts(i);
 194
 195     return total;
 196 }
 197
 198 template <class Impl>
 199 int
 200 ROB<Impl>::countInsts(unsigned tid)
 201 {
 202     return instList[tid].size();
 203 }
 204
 205 template <class Impl>
 206 void
 207 ROB<Impl>::insertInst(DynInstPtr &inst)
 208 {
 209     //assert(numInstsInROB == countInsts());
 210     assert(inst);
 211
 212     DPRINTF(ROB, "Adding inst PC %#x to the ROB.\n", inst->readPC());
 213
 214     assert(numInstsInROB != numEntries);
 215
 216     int tid = inst->threadNumber;
 217
 218     instList[tid].push_back(inst);
 219
 220     //Set Up head iterator if this is the 1st instruction in the ROB
 221     if (numInstsInROB == 0) {
 222         head = instList[tid].begin();
 223         assert((*head) == inst);
 224     }
 225
 226     //Must Decrement for iterator to actually be valid  since __.end()
 227     //actually points to 1 after the last inst
 228     tail = instList[tid].end();
 229     tail--;
 230
 231     inst->setInROB();
 232
 233     ++numInstsInROB;
 234     ++threadEntries[tid];
 235
 236     assert((*tail) == inst);
 237
 238     DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
 239 }
 240
 241 // Whatever calls this function needs to ensure that it properly frees up
 242 // registers prior to this function.
 243 /*
 244 template <class Impl>
 245 void
 246 ROB<Impl>::retireHead()
 247 {
 248     //assert(numInstsInROB == countInsts());
 249     assert(numInstsInROB > 0);
 250
 251     int tid = (*head)->threadNumber;
 252
 253     retireHead(tid);
 254
 255     if (numInstsInROB == 0) {
 256         tail = instList[tid].end();
 257     }
 258 }
 259 */
 260
 261 template <class Impl>
 262 void
 263 ROB<Impl>::retireHead(unsigned tid)
 264 {
 265     //assert(numInstsInROB == countInsts());
 266     assert(numInstsInROB > 0);
 267
 268     // Get the head ROB instruction.
 269     InstIt head_it = instList[tid].begin();
 270
 271     DynInstPtr head_inst = (*head_it);
 272
 273     assert(head_inst->readyToCommit());
 274
 275     DPRINTF(ROB, "[tid:%u]: Retiring head instruction, "
 276             "instruction PC %#x,[sn:%lli]\n", tid, head_inst->readPC(),
 277             head_inst->seqNum);
 278
 279     --numInstsInROB;
 280     --threadEntries[tid];
 281
 282     head_inst->clearInROB();
 283     head_inst->setCommitted();
 284
 285     instList[tid].erase(head_it);
 286
 287     //Update "Global" Head of ROB
 288     updateHead();
 289
 290     // @todo: A special case is needed if the instruction being
 291     // retired is the only instruction in the ROB; otherwise the tail
 292     // iterator will become invalidated.
 293     cpu->removeFrontInst(head_inst);
 294 }
 295 /*
 296 template <class Impl>
 297 bool
 298 ROB<Impl>::isHeadReady()
 299 {
 300     if (numInstsInROB != 0) {
 301         return (*head)->readyToCommit();
 302     }
 303
 304     return false;
 305 }
 306 */
 307 template <class Impl>
 308 bool
 309 ROB<Impl>::isHeadReady(unsigned tid)
 310 {
 311     if (threadEntries[tid] != 0) {
 312         return instList[tid].front()->readyToCommit();
 313     }
 314
 315     return false;
 316 }
 317
 318 template <class Impl>
 319 bool
 320 ROB<Impl>::canCommit()
 321 {
 322     //@todo: set ActiveThreads through ROB or CPU
 323     std::list<unsigned>::iterator threads = activeThreads->begin();
 324     std::list<unsigned>::iterator end = activeThreads->end();
 325
 326     while (threads != end) {
 327         unsigned tid = *threads++;
 328
 329         if (isHeadReady(tid)) {
 330             return true;
 331         }
 332     }
 333
 334     return false;
 335 }
 336
 337 template <class Impl>
 338 unsigned
 339 ROB<Impl>::numFreeEntries()
 340 {
 341     //assert(numInstsInROB == countInsts());
 342
 343     return numEntries - numInstsInROB;
 344 }
 345
 346 template <class Impl>
 347 unsigned
 348 ROB<Impl>::numFreeEntries(unsigned tid)
 349 {
 350     return maxEntries[tid] - threadEntries[tid];
 351 }
 352
 353 template <class Impl>
 354 void
 355 ROB<Impl>::doSquash(unsigned tid)
 356 {
 357     DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n",
 358             tid, squashedSeqNum[tid]);
 359
 360     assert(squashIt[tid] != instList[tid].end());
 361
 362     if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) {
 363         DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
 364                 tid);
 365
 366         squashIt[tid] = instList[tid].end();
 367
 368         doneSquashing[tid] = true;
 369         return;
 370     }
 371
 372     bool robTailUpdate = false;
 373
 374     for (int numSquashed = 0;
 375          numSquashed < squashWidth &&
 376          squashIt[tid] != instList[tid].end() &&
 377          (*squashIt[tid])->seqNum > squashedSeqNum[tid];
 378          ++numSquashed)
 379     {
 380         DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %#x, seq num %i.\n",
 381                 (*squashIt[tid])->threadNumber,
 382                 (*squashIt[tid])->readPC(),
 383                 (*squashIt[tid])->seqNum);
 384
 385         // Mark the instruction as squashed, and ready to commit so that
 386         // it can drain out of the pipeline.
 387         (*squashIt[tid])->setSquashed();
 388
 389         (*squashIt[tid])->setCanCommit();
 390
 391
 392         if (squashIt[tid] == instList[tid].begin()) {
 393             DPRINTF(ROB, "Reached head of instruction list while "
 394                     "squashing.\n");
 395
 396             squashIt[tid] = instList[tid].end();
 397
 398             doneSquashing[tid] = true;
 399
 400             return;
 401         }
 402
 403         InstIt tail_thread = instList[tid].end();
 404         tail_thread--;
 405
 406         if ((*squashIt[tid]) == (*tail_thread))
 407             robTailUpdate = true;
 408
 409         squashIt[tid]--;
 410     }
 411
 412
 413     // Check if ROB is done squashing.
 414     if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) {
 415         DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
 416                 tid);
 417
 418         squashIt[tid] = instList[tid].end();
 419
 420         doneSquashing[tid] = true;
 421     }
 422
 423     if (robTailUpdate) {
 424         updateTail();
 425     }
 426 }
 427
 428
 429 template <class Impl>
 430 void
 431 ROB<Impl>::updateHead()
 432 {
 433     DynInstPtr head_inst;
 434     InstSeqNum lowest_num = 0;
 435     bool first_valid = true;
 436
 437     // @todo: set ActiveThreads through ROB or CPU
 438     std::list<unsigned>::iterator threads = activeThreads->begin();
 439     std::list<unsigned>::iterator end = activeThreads->end();
 440
 441     while (threads != end) {
 442         unsigned tid = *threads++;
 443
 444         if (instList[tid].empty())
 445             continue;
 446
 447         if (first_valid) {
 448             head = instList[tid].begin();
 449             lowest_num = (*head)->seqNum;
 450             first_valid = false;
 451             continue;
 452         }
 453
 454         InstIt head_thread = instList[tid].begin();
 455
 456         DynInstPtr head_inst = (*head_thread);
 457
 458         assert(head_inst != 0);
 459
 460         if (head_inst->seqNum < lowest_num) {
 461             head = head_thread;
 462             lowest_num = head_inst->seqNum;
 463         }
 464     }
 465
 466     if (first_valid) {
 467         head = instList[0].end();
 468     }
 469
 470 }
 471
 472 template <class Impl>
 473 void
 474 ROB<Impl>::updateTail()
 475 {
 476     tail = instList[0].end();
 477     bool first_valid = true;
 478
 479     std::list<unsigned>::iterator threads = activeThreads->begin();
 480     std::list<unsigned>::iterator end = activeThreads->end();
 481
 482     while (threads != end) {
 483         unsigned tid = *threads++;
 484
 485         if (instList[tid].empty()) {
 486             continue;
 487         }
 488
 489         // If this is the first valid then assign w/out
 490         // comparison
 491         if (first_valid) {
 492             tail = instList[tid].end();
 493             tail--;
 494             first_valid = false;
 495             continue;
 496         }
 497
 498         // Assign new tail if this thread's tail is younger
 499         // than our current "tail high"
 500         InstIt tail_thread = instList[tid].end();
 501         tail_thread--;
 502
 503         if ((*tail_thread)->seqNum > (*tail)->seqNum) {
 504             tail = tail_thread;
 505         }
 506     }
 507 }
 508
 509
 510 template <class Impl>
 511 void
 512 ROB<Impl>::squash(InstSeqNum squash_num,unsigned tid)
 513 {
 514     if (isEmpty()) {
 515         DPRINTF(ROB, "Does not need to squash due to being empty "
 516                 "[sn:%i]\n",
 517                 squash_num);
 518
 519         return;
 520     }
 521
 522     DPRINTF(ROB, "Starting to squash within the ROB.\n");
 523
 524     robStatus[tid] = ROBSquashing;
 525
 526     doneSquashing[tid] = false;
 527
 528     squashedSeqNum[tid] = squash_num;
 529
 530     if (!instList[tid].empty()) {
 531         InstIt tail_thread = instList[tid].end();
 532         tail_thread--;
 533
 534         squashIt[tid] = tail_thread;
 535
 536         doSquash(tid);
 537     }
 538 }
 539 /*
 540 template <class Impl>
 541 typename Impl::DynInstPtr
 542 ROB<Impl>::readHeadInst()
 543 {
 544     if (numInstsInROB != 0) {
 545         assert((*head)->isInROB()==true);
 546         return *head;
 547     } else {
 548         return dummyInst;
 549     }
 550 }
 551 */
 552
 553 template <class Impl>
 554 typename Impl::DynInstPtr
 555 ROB<Impl>::readHeadInst(unsigned tid)
 556 {
 557     if (threadEntries[tid] != 0) {
 558         InstIt head_thread = instList[tid].begin();
 559
 560         assert((*head_thread)->isInROB()==true);
 561
 562         return *head_thread;
 563     } else {
 564         return dummyInst;
 565     }
 566 }
 567
 568 /*
 569 template <class Impl>
 570 uint64_t
 571 ROB<Impl>::readHeadPC()
 572 {
 573     //assert(numInstsInROB == countInsts());
 574
 575     DynInstPtr head_inst = *head;
 576
 577     return head_inst->readPC();
 578 }
 579
 580 template <class Impl>
 581 uint64_t
 582 ROB<Impl>::readHeadPC(unsigned tid)
 583 {
 584     //assert(numInstsInROB == countInsts());
 585     InstIt head_thread = instList[tid].begin();
 586
 587     return (*head_thread)->readPC();
 588 }
 589
 590
 591 template <class Impl>
 592 uint64_t
 593 ROB<Impl>::readHeadNextPC()
 594 {
 595     //assert(numInstsInROB == countInsts());
 596
 597     DynInstPtr head_inst = *head;
 598
 599     return head_inst->readNextPC();
 600 }
 601
 602 template <class Impl>
 603 uint64_t
 604 ROB<Impl>::readHeadNextPC(unsigned tid)
 605 {
 606     //assert(numInstsInROB == countInsts());
 607     InstIt head_thread = instList[tid].begin();
 608
 609     return (*head_thread)->readNextPC();
 610 }
 611
 612 template <class Impl>
 613 InstSeqNum
 614 ROB<Impl>::readHeadSeqNum()
 615 {
 616     //assert(numInstsInROB == countInsts());
 617     DynInstPtr head_inst = *head;
 618
 619     return head_inst->seqNum;
 620 }
 621
 622 template <class Impl>
 623 InstSeqNum
 624 ROB<Impl>::readHeadSeqNum(unsigned tid)
 625 {
 626     InstIt head_thread = instList[tid].begin();
 627
 628     return ((*head_thread)->seqNum);
 629 }
 630
 631 template <class Impl>
 632 typename Impl::DynInstPtr
 633 ROB<Impl>::readTailInst()
 634 {
 635     //assert(numInstsInROB == countInsts());
 636     //assert(tail != instList[0].end());
 637
 638     return (*tail);
 639 }
 640 */
 641 template <class Impl>
 642 typename Impl::DynInstPtr
 643 ROB<Impl>::readTailInst(unsigned tid)
 644 {
 645     //assert(tail_thread[tid] != instList[tid].end());
 646
 647     InstIt tail_thread = instList[tid].end();
 648     tail_thread--;
 649
 650     return *tail_thread;
 651 }
 652
 653 /*
 654 template <class Impl>
 655 uint64_t
 656 ROB<Impl>::readTailPC()
 657 {
 658     //assert(numInstsInROB == countInsts());
 659
 660     //assert(tail != instList[0].end());
 661
 662     return (*tail)->readPC();
 663 }
 664
 665 template <class Impl>
 666 uint64_t
 667 ROB<Impl>::readTailPC(unsigned tid)
 668 {
 669     //assert(tail_thread[tid] != instList[tid].end());
 670
 671     InstIt tail_thread = instList[tid].end();
 672     tail_thread--;
 673
 674     return (*tail_thread)->readPC();
 675 }
 676
 677 template <class Impl>
 678 InstSeqNum
 679 ROB<Impl>::readTailSeqNum()
 680 {
 681     // Return the last sequence number that has not been squashed.  Other
 682     // stages can use it to squash any instructions younger than the current
 683     // tail.
 684     return (*tail)->seqNum;
 685 }
 686
 687 template <class Impl>
 688 InstSeqNum
 689 ROB<Impl>::readTailSeqNum(unsigned tid)
 690 {
 691     // Return the last sequence number that has not been squashed.  Other
 692     // stages can use it to squash any instructions younger than the current
 693     // tail.
 694     //    assert(tail_thread[tid] != instList[tid].end());
 695
 696     InstIt tail_thread = instList[tid].end();
 697     tail_thread--;
 698
 699     return (*tail_thread)->seqNum;
 700 }
 701 */