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