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