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