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