rob_impl.hh revision 2731
12623SN/A/* 22623SN/A * Copyright (c) 2004-2006 The Regents of The University of Michigan 32623SN/A * All rights reserved. 42623SN/A * 52623SN/A * Redistribution and use in source and binary forms, with or without 62623SN/A * modification, are permitted provided that the following conditions are 72623SN/A * met: redistributions of source code must retain the above copyright 82623SN/A * notice, this list of conditions and the following disclaimer; 92623SN/A * redistributions in binary form must reproduce the above copyright 102623SN/A * notice, this list of conditions and the following disclaimer in the 112623SN/A * documentation and/or other materials provided with the distribution; 122623SN/A * neither the name of the copyright holders nor the names of its 132623SN/A * contributors may be used to endorse or promote products derived from 142623SN/A * this software without specific prior written permission. 152623SN/A * 162623SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172623SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182623SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192623SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202623SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212623SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222623SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232623SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242623SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252623SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262623SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272665Ssaidi@eecs.umich.edu * 282665Ssaidi@eecs.umich.edu * Authors: Kevin Lim 292623SN/A */ 302623SN/A 312623SN/A#include "config/full_system.hh" 322623SN/A#include "cpu/o3/rob.hh" 332623SN/A 342623SN/Ausing namespace std; 352623SN/A 362623SN/Atemplate <class Impl> 372623SN/AROB<Impl>::ROB(unsigned _numEntries, unsigned _squashWidth, 382623SN/A string _smtROBPolicy, unsigned _smtROBThreshold, 392623SN/A unsigned _numThreads) 402623SN/A : numEntries(_numEntries), 412623SN/A squashWidth(_squashWidth), 422623SN/A numInstsInROB(0), 432623SN/A squashedSeqNum(0), 442623SN/A numThreads(_numThreads) 452623SN/A{ 462623SN/A for (int tid=0; tid < numThreads; tid++) { 472623SN/A doneSquashing[tid] = true; 482623SN/A threadEntries[tid] = 0; 492623SN/A } 502623SN/A 512623SN/A string policy = _smtROBPolicy; 522623SN/A 532623SN/A //Convert string to lowercase 542623SN/A std::transform(policy.begin(), policy.end(), policy.begin(), 552623SN/A (int(*)(int)) tolower); 562623SN/A 572623SN/A //Figure out rob policy 582623SN/A if (policy == "dynamic") { 592623SN/A robPolicy = Dynamic; 602623SN/A 612623SN/A //Set Max Entries to Total ROB Capacity 622623SN/A for (int i = 0; i < numThreads; i++) { 632623SN/A maxEntries[i]=numEntries; 642623SN/A } 652623SN/A 662623SN/A } else if (policy == "partitioned") { 672839Sktlim@umich.edu robPolicy = Partitioned; 682798Sktlim@umich.edu DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n"); 692867Sktlim@umich.edu 702867Sktlim@umich.edu //@todo:make work if part_amt doesnt divide evenly. 712623SN/A int part_amt = numEntries / numThreads; 722623SN/A 732623SN/A //Divide ROB up evenly 742623SN/A for (int i = 0; i < numThreads; i++) { 752623SN/A maxEntries[i]=part_amt; 762623SN/A } 772948Ssaidi@eecs.umich.edu 782623SN/A } else if (policy == "threshold") { 792623SN/A robPolicy = Threshold; 802623SN/A DPRINTF(Fetch, "ROB sharing policy set to Threshold\n"); 812948Ssaidi@eecs.umich.edu 822948Ssaidi@eecs.umich.edu int threshold = _smtROBThreshold;; 832623SN/A 842623SN/A //Divide up by threshold amount 852623SN/A for (int i = 0; i < numThreads; i++) { 862623SN/A maxEntries[i]=threshold; 872630SN/A } 882623SN/A } else { 892630SN/A assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic," 902623SN/A "Partitioned, Threshold}"); 912623SN/A } 922623SN/A} 932623SN/A 942623SN/Atemplate <class Impl> 952623SN/Astd::string 962948Ssaidi@eecs.umich.eduROB<Impl>::name() const 972948Ssaidi@eecs.umich.edu{ 982948Ssaidi@eecs.umich.edu return cpu->name() + ".rob"; 992948Ssaidi@eecs.umich.edu} 1002948Ssaidi@eecs.umich.edu 1012948Ssaidi@eecs.umich.edutemplate <class Impl> 1022948Ssaidi@eecs.umich.eduvoid 1032948Ssaidi@eecs.umich.eduROB<Impl>::setCPU(FullCPU *cpu_ptr) 1042948Ssaidi@eecs.umich.edu{ 1052948Ssaidi@eecs.umich.edu cpu = cpu_ptr; 1062948Ssaidi@eecs.umich.edu 1072948Ssaidi@eecs.umich.edu // Set the per-thread iterators to the end of the instruction list. 1082623SN/A for (int i=0; i < numThreads;i++) { 1092623SN/A squashIt[i] = instList[i].end(); 1102623SN/A } 1112623SN/A 1122623SN/A // Initialize the "universal" ROB head & tail point to invalid 1132623SN/A // pointers 1142948Ssaidi@eecs.umich.edu head = instList[0].end(); 1152948Ssaidi@eecs.umich.edu tail = instList[0].end(); 1162623SN/A} 1172623SN/A 1182623SN/Atemplate <class Impl> 1192623SN/Avoid 1202630SN/AROB<Impl>::setActiveThreads(list<unsigned> *at_ptr) 1212623SN/A{ 1222657Ssaidi@eecs.umich.edu DPRINTF(ROB, "Setting active threads list pointer.\n"); 1232948Ssaidi@eecs.umich.edu activeThreads = at_ptr; 1242948Ssaidi@eecs.umich.edu} 1252948Ssaidi@eecs.umich.edu 1262948Ssaidi@eecs.umich.edutemplate <class Impl> 1272948Ssaidi@eecs.umich.eduvoid 1282948Ssaidi@eecs.umich.eduROB<Impl>::switchOut() 1292948Ssaidi@eecs.umich.edu{ 1302948Ssaidi@eecs.umich.edu for (int tid = 0; tid < numThreads; tid++) { 1312948Ssaidi@eecs.umich.edu instList[tid].clear(); 1322948Ssaidi@eecs.umich.edu } 1332948Ssaidi@eecs.umich.edu} 1342948Ssaidi@eecs.umich.edu 1352623SN/Atemplate <class Impl> 1362623SN/Avoid 1372623SN/AROB<Impl>::takeOverFrom() 1382623SN/A{ 1392623SN/A for (int tid=0; tid < numThreads; tid++) { 1402623SN/A doneSquashing[tid] = true; 1412948Ssaidi@eecs.umich.edu threadEntries[tid] = 0; 1422948Ssaidi@eecs.umich.edu squashIt[tid] = instList[tid].end(); 1432623SN/A } 1442623SN/A numInstsInROB = 0; 1452623SN/A 1462623SN/A // Initialize the "universal" ROB head & tail point to invalid 1472630SN/A // pointers 1482623SN/A head = instList[0].end(); 1492657Ssaidi@eecs.umich.edu tail = instList[0].end(); 1502948Ssaidi@eecs.umich.edu} 1512948Ssaidi@eecs.umich.edu 1522948Ssaidi@eecs.umich.edutemplate <class Impl> 1532948Ssaidi@eecs.umich.eduvoid 1542948Ssaidi@eecs.umich.eduROB<Impl>::resetEntries() 1552948Ssaidi@eecs.umich.edu{ 1562948Ssaidi@eecs.umich.edu if (robPolicy != Dynamic || numThreads > 1) { 1572948Ssaidi@eecs.umich.edu int active_threads = (*activeThreads).size(); 1582948Ssaidi@eecs.umich.edu 1592948Ssaidi@eecs.umich.edu list<unsigned>::iterator threads = (*activeThreads).begin(); 1602948Ssaidi@eecs.umich.edu list<unsigned>::iterator list_end = (*activeThreads).end(); 1612623SN/A 1622623SN/A while (threads != list_end) { 1632623SN/A if (robPolicy == Partitioned) { 1642623SN/A maxEntries[*threads++] = numEntries / active_threads; 1652623SN/A } else if (robPolicy == Threshold && active_threads == 1) { 1662623SN/A maxEntries[*threads++] = numEntries; 1672623SN/A } 1682623SN/A } 1692623SN/A } 1702623SN/A} 1712856Srdreslin@umich.edu 1722856Srdreslin@umich.edutemplate <class Impl> 1732623SN/Aint 1742623SN/AROB<Impl>::entryAmount(int num_threads) 1752623SN/A{ 1762901Ssaidi@eecs.umich.edu if (robPolicy == Partitioned) { 1772798Sktlim@umich.edu return numEntries / num_threads; 1782798Sktlim@umich.edu } else { 1792798Sktlim@umich.edu return 0; 1802623SN/A } 1812623SN/A} 1822623SN/A 1832623SN/Atemplate <class Impl> 1842623SN/Aint 1852623SN/AROB<Impl>::countInsts() 1862623SN/A{ 1872623SN/A int total=0; 1882623SN/A 1892623SN/A for (int i=0;i < numThreads;i++) 1902623SN/A total += countInsts(i); 1912623SN/A 1922644Sstever@eecs.umich.edu return total; 1932623SN/A} 1942644Sstever@eecs.umich.edu 1952798Sktlim@umich.edutemplate <class Impl> 1962839Sktlim@umich.eduint 1972623SN/AROB<Impl>::countInsts(unsigned tid) 1982623SN/A{ 1992623SN/A return instList[tid].size(); 200} 201 202template <class Impl> 203void 204ROB<Impl>::insertInst(DynInstPtr &inst) 205{ 206 //assert(numInstsInROB == countInsts()); 207 assert(inst); 208 209 DPRINTF(ROB, "Adding inst PC %#x to the ROB.\n", inst->readPC()); 210 211 assert(numInstsInROB != numEntries); 212 213 int tid = inst->threadNumber; 214 215 instList[tid].push_back(inst); 216 217 //Set Up head iterator if this is the 1st instruction in the ROB 218 if (numInstsInROB == 0) { 219 head = instList[tid].begin(); 220 assert((*head) == inst); 221 } 222 223 //Must Decrement for iterator to actually be valid since __.end() 224 //actually points to 1 after the last inst 225 tail = instList[tid].end(); 226 tail--; 227 228 inst->setInROB(); 229 230 ++numInstsInROB; 231 ++threadEntries[tid]; 232 233 assert((*tail) == inst); 234 235 DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]); 236} 237 238// Whatever calls this function needs to ensure that it properly frees up 239// registers prior to this function. 240/* 241template <class Impl> 242void 243ROB<Impl>::retireHead() 244{ 245 //assert(numInstsInROB == countInsts()); 246 assert(numInstsInROB > 0); 247 248 int tid = (*head)->threadNumber; 249 250 retireHead(tid); 251 252 if (numInstsInROB == 0) { 253 tail = instList[tid].end(); 254 } 255} 256*/ 257 258template <class Impl> 259void 260ROB<Impl>::retireHead(unsigned tid) 261{ 262 //assert(numInstsInROB == countInsts()); 263 assert(numInstsInROB > 0); 264 265 // Get the head ROB instruction. 266 InstIt head_it = instList[tid].begin(); 267 268 DynInstPtr head_inst = (*head_it); 269 270 assert(head_inst->readyToCommit()); 271 272 DPRINTF(ROB, "[tid:%u]: Retiring head instruction, " 273 "instruction PC %#x,[sn:%lli]\n", tid, head_inst->readPC(), 274 head_inst->seqNum); 275 276 --numInstsInROB; 277 --threadEntries[tid]; 278 279 head_inst->clearInROB(); 280 head_inst->setCommitted(); 281 282 instList[tid].erase(head_it); 283 284 //Update "Global" Head of ROB 285 updateHead(); 286 287 // @todo: A special case is needed if the instruction being 288 // retired is the only instruction in the ROB; otherwise the tail 289 // iterator will become invalidated. 290 cpu->removeFrontInst(head_inst); 291} 292/* 293template <class Impl> 294bool 295ROB<Impl>::isHeadReady() 296{ 297 if (numInstsInROB != 0) { 298 return (*head)->readyToCommit(); 299 } 300 301 return false; 302} 303*/ 304template <class Impl> 305bool 306ROB<Impl>::isHeadReady(unsigned tid) 307{ 308 if (threadEntries[tid] != 0) { 309 return instList[tid].front()->readyToCommit(); 310 } 311 312 return false; 313} 314 315template <class Impl> 316bool 317ROB<Impl>::canCommit() 318{ 319 //@todo: set ActiveThreads through ROB or CPU 320 list<unsigned>::iterator threads = (*activeThreads).begin(); 321 322 while (threads != (*activeThreads).end()) { 323 unsigned 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(unsigned tid) 345{ 346 return maxEntries[tid] - threadEntries[tid]; 347} 348 349template <class Impl> 350void 351ROB<Impl>::doSquash(unsigned tid) 352{ 353 DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n", 354 tid, squashedSeqNum); 355 356 assert(squashIt[tid] != instList[tid].end()); 357 358 if ((*squashIt[tid])->seqNum < squashedSeqNum) { 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; 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) { 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<unsigned>::iterator threads = (*activeThreads).begin(); 435 436 while (threads != (*activeThreads).end()) { 437 unsigned thread_num = *threads++; 438 439 if (instList[thread_num].empty()) 440 continue; 441 442 if (first_valid) { 443 head = instList[thread_num].begin(); 444 lowest_num = (*head)->seqNum; 445 first_valid = false; 446 continue; 447 } 448 449 InstIt head_thread = instList[thread_num].begin(); 450 451 DynInstPtr head_inst = (*head_thread); 452 453 assert(head_inst != 0); 454 455 if (head_inst->seqNum < lowest_num) { 456 head = head_thread; 457 lowest_num = head_inst->seqNum; 458 } 459 } 460 461 if (first_valid) { 462 head = instList[0].end(); 463 } 464 465} 466 467template <class Impl> 468void 469ROB<Impl>::updateTail() 470{ 471 tail = instList[0].end(); 472 bool first_valid = true; 473 474 list<unsigned>::iterator threads = (*activeThreads).begin(); 475 476 while (threads != (*activeThreads).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 504template <class Impl> 505void 506ROB<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 = 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/* 534template <class Impl> 535typename Impl::DynInstPtr 536ROB<Impl>::readHeadInst() 537{ 538 if (numInstsInROB != 0) { 539 assert((*head)->isInROB()==true); 540 return *head; 541 } else { 542 return dummyInst; 543 } 544} 545*/ 546template <class Impl> 547typename Impl::DynInstPtr 548ROB<Impl>::readHeadInst(unsigned tid) 549{ 550 if (threadEntries[tid] != 0) { 551 InstIt head_thread = instList[tid].begin(); 552 553 assert((*head_thread)->isInROB()==true); 554 555 return *head_thread; 556 } else { 557 return dummyInst; 558 } 559} 560/* 561template <class Impl> 562uint64_t 563ROB<Impl>::readHeadPC() 564{ 565 //assert(numInstsInROB == countInsts()); 566 567 DynInstPtr head_inst = *head; 568 569 return head_inst->readPC(); 570} 571 572template <class Impl> 573uint64_t 574ROB<Impl>::readHeadPC(unsigned tid) 575{ 576 //assert(numInstsInROB == countInsts()); 577 InstIt head_thread = instList[tid].begin(); 578 579 return (*head_thread)->readPC(); 580} 581 582 583template <class Impl> 584uint64_t 585ROB<Impl>::readHeadNextPC() 586{ 587 //assert(numInstsInROB == countInsts()); 588 589 DynInstPtr head_inst = *head; 590 591 return head_inst->readNextPC(); 592} 593 594template <class Impl> 595uint64_t 596ROB<Impl>::readHeadNextPC(unsigned tid) 597{ 598 //assert(numInstsInROB == countInsts()); 599 InstIt head_thread = instList[tid].begin(); 600 601 return (*head_thread)->readNextPC(); 602} 603 604template <class Impl> 605InstSeqNum 606ROB<Impl>::readHeadSeqNum() 607{ 608 //assert(numInstsInROB == countInsts()); 609 DynInstPtr head_inst = *head; 610 611 return head_inst->seqNum; 612} 613 614template <class Impl> 615InstSeqNum 616ROB<Impl>::readHeadSeqNum(unsigned tid) 617{ 618 InstIt head_thread = instList[tid].begin(); 619 620 return ((*head_thread)->seqNum); 621} 622 623template <class Impl> 624typename Impl::DynInstPtr 625ROB<Impl>::readTailInst() 626{ 627 //assert(numInstsInROB == countInsts()); 628 //assert(tail != instList[0].end()); 629 630 return (*tail); 631} 632*/ 633template <class Impl> 634typename Impl::DynInstPtr 635ROB<Impl>::readTailInst(unsigned tid) 636{ 637 //assert(tail_thread[tid] != instList[tid].end()); 638 639 InstIt tail_thread = instList[tid].end(); 640 tail_thread--; 641 642 return *tail_thread; 643} 644 645/* 646template <class Impl> 647uint64_t 648ROB<Impl>::readTailPC() 649{ 650 //assert(numInstsInROB == countInsts()); 651 652 //assert(tail != instList[0].end()); 653 654 return (*tail)->readPC(); 655} 656 657template <class Impl> 658uint64_t 659ROB<Impl>::readTailPC(unsigned tid) 660{ 661 //assert(tail_thread[tid] != instList[tid].end()); 662 663 InstIt tail_thread = instList[tid].end(); 664 tail_thread--; 665 666 return (*tail_thread)->readPC(); 667} 668 669template <class Impl> 670InstSeqNum 671ROB<Impl>::readTailSeqNum() 672{ 673 // Return the last sequence number that has not been squashed. Other 674 // stages can use it to squash any instructions younger than the current 675 // tail. 676 return (*tail)->seqNum; 677} 678 679template <class Impl> 680InstSeqNum 681ROB<Impl>::readTailSeqNum(unsigned tid) 682{ 683 // Return the last sequence number that has not been squashed. Other 684 // stages can use it to squash any instructions younger than the current 685 // tail. 686 // assert(tail_thread[tid] != instList[tid].end()); 687 688 InstIt tail_thread = instList[tid].end(); 689 tail_thread--; 690 691 return (*tail_thread)->seqNum; 692} 693*/ 694