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