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 using namespace std;
  36
  37 template <class Impl>
  38 ROB<Impl>::ROB(unsigned _numEntries, unsigned _squashWidth,
  39                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     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(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         list<unsigned>::iterator threads  = (*activeThreads).begin();
 161         list<unsigned>::iterator list_end = (*activeThreads).end();
 162
 163         while (threads != list_end) {
 164             if (robPolicy == Partitioned) {
 165                 maxEntries[*threads++] = numEntries / active_threads;
 166             } else if (robPolicy == Threshold && active_threads == 1) {
 167                 maxEntries[*threads++] = numEntries;
 168             }
 169         }
 170     }
 171 }
 172
 173 template <class Impl>
 174 int
 175 ROB<Impl>::entryAmount(int num_threads)
 176 {
 177     if (robPolicy == Partitioned) {
 178         return numEntries / num_threads;
 179     } else {
 180         return 0;
 181     }
 182 }
 183
 184 template <class Impl>
 185 int
 186 ROB<Impl>::countInsts()
 187 {
 188     int total=0;
 189
 190     for (int i=0;i < numThreads;i++)
 191         total += countInsts(i);
 192
 193     return total;
 194 }
 195
 196 template <class Impl>
 197 int
 198 ROB<Impl>::countInsts(unsigned tid)
 199 {
 200     return instList[tid].size();
 201 }
 202
 203 template <class Impl>
 204 void
 205 ROB<Impl>::insertInst(DynInstPtr &inst)
 206 {
 207     //assert(numInstsInROB == countInsts());
 208     assert(inst);
 209
 210     DPRINTF(ROB, "Adding inst PC %#x to the ROB.\n", inst->readPC());
 211
 212     assert(numInstsInROB != numEntries);
 213
 214     int tid = inst->threadNumber;
 215
 216     instList[tid].push_back(inst);
 217
 218     //Set Up head iterator if this is the 1st instruction in the ROB
 219     if (numInstsInROB == 0) {
 220         head = instList[tid].begin();
 221         assert((*head) == inst);
 222     }
 223
 224     //Must Decrement for iterator to actually be valid  since __.end()
 225     //actually points to 1 after the last inst
 226     tail = instList[tid].end();
 227     tail--;
 228
 229     inst->setInROB();
 230
 231     ++numInstsInROB;
 232     ++threadEntries[tid];
 233
 234     assert((*tail) == inst);
 235
 236     DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
 237 }
 238
 239 // Whatever calls this function needs to ensure that it properly frees up
 240 // registers prior to this function.
 241 /*
 242 template <class Impl>
 243 void
 244 ROB<Impl>::retireHead()
 245 {
 246     //assert(numInstsInROB == countInsts());
 247     assert(numInstsInROB > 0);
 248
 249     int tid = (*head)->threadNumber;
 250
 251     retireHead(tid);
 252
 253     if (numInstsInROB == 0) {
 254         tail = instList[tid].end();
 255     }
 256 }
 257 */
 258
 259 template <class Impl>
 260 void
 261 ROB<Impl>::retireHead(unsigned tid)
 262 {
 263     //assert(numInstsInROB == countInsts());
 264     assert(numInstsInROB > 0);
 265
 266     // Get the head ROB instruction.
 267     InstIt head_it = instList[tid].begin();
 268
 269     DynInstPtr head_inst = (*head_it);
 270
 271     assert(head_inst->readyToCommit());
 272
 273     DPRINTF(ROB, "[tid:%u]: Retiring head instruction, "
 274             "instruction PC %#x,[sn:%lli]\n", tid, head_inst->readPC(),
 275             head_inst->seqNum);
 276
 277     --numInstsInROB;
 278     --threadEntries[tid];
 279
 280     head_inst->clearInROB();
 281     head_inst->setCommitted();
 282
 283     instList[tid].erase(head_it);
 284
 285     //Update "Global" Head of ROB
 286     updateHead();
 287
 288     // @todo: A special case is needed if the instruction being
 289     // retired is the only instruction in the ROB; otherwise the tail
 290     // iterator will become invalidated.
 291     cpu->removeFrontInst(head_inst);
 292 }
 293 /*
 294 template <class Impl>
 295 bool
 296 ROB<Impl>::isHeadReady()
 297 {
 298     if (numInstsInROB != 0) {
 299         return (*head)->readyToCommit();
 300     }
 301
 302     return false;
 303 }
 304 */
 305 template <class Impl>
 306 bool
 307 ROB<Impl>::isHeadReady(unsigned tid)
 308 {
 309     if (threadEntries[tid] != 0) {
 310         return instList[tid].front()->readyToCommit();
 311     }
 312
 313     return false;
 314 }
 315
 316 template <class Impl>
 317 bool
 318 ROB<Impl>::canCommit()
 319 {
 320     //@todo: set ActiveThreads through ROB or CPU
 321     list<unsigned>::iterator threads = (*activeThreads).begin();
 322
 323     while (threads != (*activeThreads).end()) {
 324         unsigned tid = *threads++;
 325
 326         if (isHeadReady(tid)) {
 327             return true;
 328         }
 329     }
 330
 331     return false;
 332 }
 333
 334 template <class Impl>
 335 unsigned
 336 ROB<Impl>::numFreeEntries()
 337 {
 338     //assert(numInstsInROB == countInsts());
 339
 340     return numEntries - numInstsInROB;
 341 }
 342
 343 template <class Impl>
 344 unsigned
 345 ROB<Impl>::numFreeEntries(unsigned tid)
 346 {
 347     return maxEntries[tid] - threadEntries[tid];
 348 }
 349
 350 template <class Impl>
 351 void
 352 ROB<Impl>::doSquash(unsigned tid)
 353 {
 354     DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n",
 355             tid, squashedSeqNum[tid]);
 356
 357     assert(squashIt[tid] != instList[tid].end());
 358
 359     if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) {
 360         DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
 361                 tid);
 362
 363         squashIt[tid] = instList[tid].end();
 364
 365         doneSquashing[tid] = true;
 366         return;
 367     }
 368
 369     bool robTailUpdate = false;
 370
 371     for (int numSquashed = 0;
 372          numSquashed < squashWidth &&
 373          squashIt[tid] != instList[tid].end() &&
 374          (*squashIt[tid])->seqNum > squashedSeqNum[tid];
 375          ++numSquashed)
 376     {
 377         DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %#x, seq num %i.\n",
 378                 (*squashIt[tid])->threadNumber,
 379                 (*squashIt[tid])->readPC(),
 380                 (*squashIt[tid])->seqNum);
 381
 382         // Mark the instruction as squashed, and ready to commit so that
 383         // it can drain out of the pipeline.
 384         (*squashIt[tid])->setSquashed();
 385
 386         (*squashIt[tid])->setCanCommit();
 387
 388
 389         if (squashIt[tid] == instList[tid].begin()) {
 390             DPRINTF(ROB, "Reached head of instruction list while "
 391                     "squashing.\n");
 392
 393             squashIt[tid] = instList[tid].end();
 394
 395             doneSquashing[tid] = true;
 396
 397             return;
 398         }
 399
 400         InstIt tail_thread = instList[tid].end();
 401         tail_thread--;
 402
 403         if ((*squashIt[tid]) == (*tail_thread))
 404             robTailUpdate = true;
 405
 406         squashIt[tid]--;
 407     }
 408
 409
 410     // Check if ROB is done squashing.
 411     if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) {
 412         DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
 413                 tid);
 414
 415         squashIt[tid] = instList[tid].end();
 416
 417         doneSquashing[tid] = true;
 418     }
 419
 420     if (robTailUpdate) {
 421         updateTail();
 422     }
 423 }
 424
 425
 426 template <class Impl>
 427 void
 428 ROB<Impl>::updateHead()
 429 {
 430     DynInstPtr head_inst;
 431     InstSeqNum lowest_num = 0;
 432     bool first_valid = true;
 433
 434     // @todo: set ActiveThreads through ROB or CPU
 435     list<unsigned>::iterator threads = (*activeThreads).begin();
 436
 437     while (threads != (*activeThreads).end()) {
 438         unsigned thread_num = *threads++;
 439
 440         if (instList[thread_num].empty())
 441             continue;
 442
 443         if (first_valid) {
 444             head = instList[thread_num].begin();
 445             lowest_num = (*head)->seqNum;
 446             first_valid = false;
 447             continue;
 448         }
 449
 450         InstIt head_thread = instList[thread_num].begin();
 451
 452         DynInstPtr head_inst = (*head_thread);
 453
 454         assert(head_inst != 0);
 455
 456         if (head_inst->seqNum < lowest_num) {
 457             head = head_thread;
 458             lowest_num = head_inst->seqNum;
 459         }
 460     }
 461
 462     if (first_valid) {
 463         head = instList[0].end();
 464     }
 465
 466 }
 467
 468 template <class Impl>
 469 void
 470 ROB<Impl>::updateTail()
 471 {
 472     tail = instList[0].end();
 473     bool first_valid = true;
 474
 475     list<unsigned>::iterator threads = (*activeThreads).begin();
 476
 477     while (threads != (*activeThreads).end()) {
 478         unsigned tid = *threads++;
 479
 480         if (instList[tid].empty()) {
 481             continue;
 482         }
 483
 484         // If this is the first valid then assign w/out
 485         // comparison
 486         if (first_valid) {
 487             tail = instList[tid].end();
 488             tail--;
 489             first_valid = false;
 490             continue;
 491         }
 492
 493         // Assign new tail if this thread's tail is younger
 494         // than our current "tail high"
 495         InstIt tail_thread = instList[tid].end();
 496         tail_thread--;
 497
 498         if ((*tail_thread)->seqNum > (*tail)->seqNum) {
 499             tail = tail_thread;
 500         }
 501     }
 502 }
 503
 504
 505 template <class Impl>
 506 void
 507 ROB<Impl>::squash(InstSeqNum squash_num,unsigned tid)
 508 {
 509     if (isEmpty()) {
 510         DPRINTF(ROB, "Does not need to squash due to being empty "
 511                 "[sn:%i]\n",
 512                 squash_num);
 513
 514         return;
 515     }
 516
 517     DPRINTF(ROB, "Starting to squash within the ROB.\n");
 518
 519     robStatus[tid] = ROBSquashing;
 520
 521     doneSquashing[tid] = false;
 522
 523     squashedSeqNum[tid] = squash_num;
 524
 525     if (!instList[tid].empty()) {
 526         InstIt tail_thread = instList[tid].end();
 527         tail_thread--;
 528
 529         squashIt[tid] = tail_thread;
 530
 531         doSquash(tid);
 532     }
 533 }
 534 /*
 535 template <class Impl>
 536 typename Impl::DynInstPtr
 537 ROB<Impl>::readHeadInst()
 538 {
 539     if (numInstsInROB != 0) {
 540         assert((*head)->isInROB()==true);
 541         return *head;
 542     } else {
 543         return dummyInst;
 544     }
 545 }
 546 */
 547
 548 template <class Impl>
 549 typename Impl::DynInstPtr
 550 ROB<Impl>::readHeadInst(unsigned tid)
 551 {
 552     if (threadEntries[tid] != 0) {
 553         InstIt head_thread = instList[tid].begin();
 554
 555         assert((*head_thread)->isInROB()==true);
 556
 557         return *head_thread;
 558     } else {
 559         return dummyInst;
 560     }
 561 }
 562
 563 /*
 564 template <class Impl>
 565 uint64_t
 566 ROB<Impl>::readHeadPC()
 567 {
 568     //assert(numInstsInROB == countInsts());
 569
 570     DynInstPtr head_inst = *head;
 571
 572     return head_inst->readPC();
 573 }
 574
 575 template <class Impl>
 576 uint64_t
 577 ROB<Impl>::readHeadPC(unsigned tid)
 578 {
 579     //assert(numInstsInROB == countInsts());
 580     InstIt head_thread = instList[tid].begin();
 581
 582     return (*head_thread)->readPC();
 583 }
 584
 585
 586 template <class Impl>
 587 uint64_t
 588 ROB<Impl>::readHeadNextPC()
 589 {
 590     //assert(numInstsInROB == countInsts());
 591
 592     DynInstPtr head_inst = *head;
 593
 594     return head_inst->readNextPC();
 595 }
 596
 597 template <class Impl>
 598 uint64_t
 599 ROB<Impl>::readHeadNextPC(unsigned tid)
 600 {
 601     //assert(numInstsInROB == countInsts());
 602     InstIt head_thread = instList[tid].begin();
 603
 604     return (*head_thread)->readNextPC();
 605 }
 606
 607 template <class Impl>
 608 InstSeqNum
 609 ROB<Impl>::readHeadSeqNum()
 610 {
 611     //assert(numInstsInROB == countInsts());
 612     DynInstPtr head_inst = *head;
 613
 614     return head_inst->seqNum;
 615 }
 616
 617 template <class Impl>
 618 InstSeqNum
 619 ROB<Impl>::readHeadSeqNum(unsigned tid)
 620 {
 621     InstIt head_thread = instList[tid].begin();
 622
 623     return ((*head_thread)->seqNum);
 624 }
 625
 626 template <class Impl>
 627 typename Impl::DynInstPtr
 628 ROB<Impl>::readTailInst()
 629 {
 630     //assert(numInstsInROB == countInsts());
 631     //assert(tail != instList[0].end());
 632
 633     return (*tail);
 634 }
 635 */
 636 template <class Impl>
 637 typename Impl::DynInstPtr
 638 ROB<Impl>::readTailInst(unsigned tid)
 639 {
 640     //assert(tail_thread[tid] != instList[tid].end());
 641
 642     InstIt tail_thread = instList[tid].end();
 643     tail_thread--;
 644
 645     return *tail_thread;
 646 }
 647
 648 /*
 649 template <class Impl>
 650 uint64_t
 651 ROB<Impl>::readTailPC()
 652 {
 653     //assert(numInstsInROB == countInsts());
 654
 655     //assert(tail != instList[0].end());
 656
 657     return (*tail)->readPC();
 658 }
 659
 660 template <class Impl>
 661 uint64_t
 662 ROB<Impl>::readTailPC(unsigned tid)
 663 {
 664     //assert(tail_thread[tid] != instList[tid].end());
 665
 666     InstIt tail_thread = instList[tid].end();
 667     tail_thread--;
 668
 669     return (*tail_thread)->readPC();
 670 }
 671
 672 template <class Impl>
 673 InstSeqNum
 674 ROB<Impl>::readTailSeqNum()
 675 {
 676     // Return the last sequence number that has not been squashed.  Other
 677     // stages can use it to squash any instructions younger than the current
 678     // tail.
 679     return (*tail)->seqNum;
 680 }
 681
 682 template <class Impl>
 683 InstSeqNum
 684 ROB<Impl>::readTailSeqNum(unsigned tid)
 685 {
 686     // Return the last sequence number that has not been squashed.  Other
 687     // stages can use it to squash any instructions younger than the current
 688     // tail.
 689     //    assert(tail_thread[tid] != instList[tid].end());
 690
 691     InstIt tail_thread = instList[tid].end();
 692     tail_thread--;
 693
 694     return (*tail_thread)->seqNum;
 695 }
 696 */