rob_impl.hh revision 7720:65d338a8dba4
1892SN/A/* 21762SN/A * Copyright (c) 2004-2006 The Regents of The University of Michigan 3892SN/A * All rights reserved. 4892SN/A * 5892SN/A * Redistribution and use in source and binary forms, with or without 6892SN/A * modification, are permitted provided that the following conditions are 7892SN/A * met: redistributions of source code must retain the above copyright 8892SN/A * notice, this list of conditions and the following disclaimer; 9892SN/A * redistributions in binary form must reproduce the above copyright 10892SN/A * notice, this list of conditions and the following disclaimer in the 11892SN/A * documentation and/or other materials provided with the distribution; 12892SN/A * neither the name of the copyright holders nor the names of its 13892SN/A * contributors may be used to endorse or promote products derived from 14892SN/A * this software without specific prior written permission. 15892SN/A * 16892SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17892SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18892SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19892SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20892SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21892SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22892SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23892SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24892SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25892SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26892SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272665SN/A * 282665SN/A * Authors: Kevin Lim 292665SN/A * Korey Sewell 30892SN/A */ 31768SN/A 321730SN/A#include <list> 33768SN/A 34768SN/A#include "config/full_system.hh" 35768SN/A#include "cpu/o3/rob.hh" 36768SN/A 37768SN/Ausing namespace std; 38768SN/A 39768SN/Atemplate <class Impl> 40768SN/AROB<Impl>::ROB(O3CPU *_cpu, unsigned _numEntries, unsigned _squashWidth, 413540Sgblack@eecs.umich.edu std::string _smtROBPolicy, unsigned _smtROBThreshold, 423540Sgblack@eecs.umich.edu ThreadID _numThreads) 433540Sgblack@eecs.umich.edu : cpu(_cpu), 442542SN/A numEntries(_numEntries), 453348SN/A squashWidth(_squashWidth), 46768SN/A numInstsInROB(0), 47768SN/A numThreads(_numThreads) 48768SN/A{ 49768SN/A for (ThreadID tid = 0; tid < numThreads; tid++) { 502107SN/A squashedSeqNum[tid] = 0; 512107SN/A doneSquashing[tid] = true; 52768SN/A threadEntries[tid] = 0; 532539SN/A } 542542SN/A 55768SN/A std::string policy = _smtROBPolicy; 562539SN/A 57809SN/A //Convert string to lowercase 58835SN/A std::transform(policy.begin(), policy.end(), policy.begin(), 59835SN/A (int(*)(int)) tolower); 60835SN/A 61835SN/A //Figure out rob policy 62835SN/A if (policy == "dynamic") { 63768SN/A robPolicy = Dynamic; 64896SN/A 65896SN/A //Set Max Entries to Total ROB Capacity 66896SN/A for (ThreadID tid = 0; tid < numThreads; tid++) { 67775SN/A maxEntries[tid] = numEntries; 682539SN/A } 692539SN/A 702539SN/A } else if (policy == "partitioned") { 712539SN/A robPolicy = Partitioned; 723349SN/A DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n"); 732539SN/A 742641SN/A //@todo:make work if part_amt doesnt divide evenly. 752641SN/A int part_amt = numEntries / numThreads; 762539SN/A 772630SN/A //Divide ROB up evenly 782641SN/A for (ThreadID tid = 0; tid < numThreads; tid++) { 792641SN/A maxEntries[tid] = part_amt; 802539SN/A } 812539SN/A 822641SN/A } else if (policy == "threshold") { 832539SN/A robPolicy = Threshold; 842539SN/A DPRINTF(Fetch, "ROB sharing policy set to Threshold\n"); 852539SN/A 862630SN/A int threshold = _smtROBThreshold;; 872539SN/A 882539SN/A //Divide up by threshold amount 892630SN/A for (ThreadID tid = 0; tid < numThreads; tid++) { 902539SN/A maxEntries[tid] = threshold; 912539SN/A } 922630SN/A } else { 932539SN/A assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic," 942539SN/A "Partitioned, Threshold}"); 952630SN/A } 962539SN/A 972539SN/A // Set the per-thread iterators to the end of the instruction list. 982630SN/A for (ThreadID tid = 0; tid < numThreads; tid++) { 992539SN/A squashIt[tid] = instList[tid].end(); 1002539SN/A } 1012630SN/A 1022539SN/A // Initialize the "universal" ROB head & tail point to invalid 1032539SN/A // pointers 1042630SN/A head = instList[0].end(); 1052539SN/A tail = instList[0].end(); 1062539SN/A} 1072630SN/A 1082539SN/Atemplate <class Impl> 1092539SN/Astd::string 1102630SN/AROB<Impl>::name() const 1112539SN/A{ 1122539SN/A return cpu->name() + ".rob"; 1132630SN/A} 1142539SN/A 1152539SN/Atemplate <class Impl> 1162630SN/Avoid 1172539SN/AROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr) 1182542SN/A{ 1192630SN/A DPRINTF(ROB, "Setting active threads list pointer.\n"); 1202539SN/A activeThreads = at_ptr; 1212539SN/A} 1222630SN/A 1232539SN/Atemplate <class Impl> 1242539SN/Avoid 1252539SN/AROB<Impl>::switchOut() 1262539SN/A{ 1272539SN/A for (ThreadID tid = 0; tid < numThreads; tid++) { 1282539SN/A instList[tid].clear(); 1292630SN/A } 1302539SN/A} 1312539SN/A 1322630SN/Atemplate <class Impl> 1332539SN/Avoid 1342539SN/AROB<Impl>::takeOverFrom() 1352539SN/A{ 1362539SN/A for (ThreadID tid = 0; tid < numThreads; tid++) { 1372539SN/A doneSquashing[tid] = true; 1382539SN/A threadEntries[tid] = 0; 1392630SN/A squashIt[tid] = instList[tid].end(); 1402539SN/A } 1412539SN/A numInstsInROB = 0; 1422539SN/A 1432539SN/A // Initialize the "universal" ROB head & tail point to invalid 1442539SN/A // pointers 1452539SN/A head = instList[0].end(); 1462539SN/A tail = instList[0].end(); 1472539SN/A} 1482641SN/A 1492539SN/Atemplate <class Impl> 1502539SN/Avoid 151768SN/AROB<Impl>::resetEntries() 152768SN/A{ 1532542SN/A if (robPolicy != Dynamic || numThreads > 1) { 1543349SN/A int active_threads = activeThreads->size(); 155768SN/A 1562641SN/A list<ThreadID>::iterator threads = activeThreads->begin(); 1572641SN/A list<ThreadID>::iterator end = activeThreads->end(); 1582641SN/A 159768SN/A while (threads != end) { 1602641SN/A ThreadID tid = *threads++; 161768SN/A 1622641SN/A if (robPolicy == Partitioned) { 163768SN/A maxEntries[tid] = numEntries / active_threads; 1642539SN/A } else if (robPolicy == Threshold && active_threads == 1) { 1652539SN/A maxEntries[tid] = numEntries; 1662630SN/A } 1672539SN/A } 1682539SN/A } 1692630SN/A} 1702539SN/A 1712539SN/Atemplate <class Impl> 1722630SN/Aint 1732539SN/AROB<Impl>::entryAmount(ThreadID num_threads) 1742539SN/A{ 1752630SN/A if (robPolicy == Partitioned) { 1762539SN/A return numEntries / num_threads; 1772539SN/A } else { 1782630SN/A return 0; 1792539SN/A } 1802539SN/A} 1812630SN/A 1822539SN/Atemplate <class Impl> 1832539SN/Aint 1842630SN/AROB<Impl>::countInsts() 1852539SN/A{ 1862539SN/A int total = 0; 1872630SN/A 1882539SN/A for (ThreadID tid = 0; tid < numThreads; tid++) 1892539SN/A total += countInsts(tid); 1902630SN/A 1912539SN/A return total; 1922539SN/A} 1932630SN/A 1942539SN/Atemplate <class Impl> 1952539SN/Aint 1962630SN/AROB<Impl>::countInsts(ThreadID tid) 1972539SN/A{ 1982539SN/A return instList[tid].size(); 1992630SN/A} 2002539SN/A 2012539SN/Atemplate <class Impl> 2022630SN/Avoid 2032539SN/AROB<Impl>::insertInst(DynInstPtr &inst) 2042539SN/A{ 2052539SN/A assert(inst); 2062539SN/A 2072539SN/A DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState()); 2082539SN/A 2092539SN/A assert(numInstsInROB != numEntries); 2102539SN/A 2112539SN/A ThreadID tid = inst->threadNumber; 2122539SN/A 2132539SN/A instList[tid].push_back(inst); 2142539SN/A 2152539SN/A //Set Up head iterator if this is the 1st instruction in the ROB 2162539SN/A if (numInstsInROB == 0) { 2172539SN/A head = instList[tid].begin(); 2182539SN/A assert((*head) == inst); 2192539SN/A } 2202539SN/A 2212539SN/A //Must Decrement for iterator to actually be valid since __.end() 2222539SN/A //actually points to 1 after the last inst 2232549SN/A tail = instList[tid].end(); 224768SN/A tail--; 2252539SN/A 226768SN/A inst->setInROB(); 2272641SN/A 2282539SN/A ++numInstsInROB; 229768SN/A ++threadEntries[tid]; 230768SN/A 231857SN/A assert((*tail) == inst); 232857SN/A 233835SN/A DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]); 234835SN/A} 235835SN/A 236835SN/Atemplate <class Impl> 237857SN/Avoid 238857SN/AROB<Impl>::retireHead(ThreadID tid) 239857SN/A{ 240835SN/A assert(numInstsInROB > 0); 241835SN/A 242857SN/A // Get the head ROB instruction. 243857SN/A InstIt head_it = instList[tid].begin(); 244857SN/A 245857SN/A DynInstPtr head_inst = (*head_it); 246835SN/A 247835SN/A assert(head_inst->readyToCommit()); 248896SN/A 249896SN/A DPRINTF(ROB, "[tid:%u]: Retiring head instruction, " 250835SN/A "instruction PC %s, [sn:%lli]\n", tid, head_inst->pcState(), 251896SN/A head_inst->seqNum); 252896SN/A 253896SN/A --numInstsInROB; 254835SN/A --threadEntries[tid]; 255896SN/A 256835SN/A head_inst->clearInROB(); 257835SN/A head_inst->setCommitted(); 258896SN/A 259896SN/A instList[tid].erase(head_it); 260896SN/A 261896SN/A //Update "Global" Head of ROB 262896SN/A updateHead(); 263896SN/A 264857SN/A // @todo: A special case is needed if the instruction being 265896SN/A // retired is the only instruction in the ROB; otherwise the tail 266896SN/A // iterator will become invalidated. 267896SN/A cpu->removeFrontInst(head_inst); 268896SN/A} 269896SN/A 270896SN/Atemplate <class Impl> 271835SN/Abool 272835SN/AROB<Impl>::isHeadReady(ThreadID tid) 273857SN/A{ 274857SN/A if (threadEntries[tid] != 0) { 275857SN/A return instList[tid].front()->readyToCommit(); 276857SN/A } 277857SN/A 278857SN/A return false; 279857SN/A} 280857SN/A 281857SN/Atemplate <class Impl> 282857SN/Abool 283835SN/AROB<Impl>::canCommit() 284896SN/A{ 285896SN/A //@todo: set ActiveThreads through ROB or CPU 286857SN/A list<ThreadID>::iterator threads = activeThreads->begin(); 287857SN/A list<ThreadID>::iterator end = activeThreads->end(); 2882542SN/A 289857SN/A while (threads != end) { 290896SN/A ThreadID tid = *threads++; 291857SN/A 292857SN/A if (isHeadReady(tid)) { 293896SN/A return true; 294857SN/A } 295857SN/A } 296857SN/A 297857SN/A return false; 298857SN/A} 299835SN/A 300835SN/Atemplate <class Impl> 301835SN/Aunsigned 302835SN/AROB<Impl>::numFreeEntries() 303896SN/A{ 304896SN/A return numEntries - numInstsInROB; 305835SN/A} 3062846SN/A 3072846SN/Atemplate <class Impl> 3082846SN/Aunsigned 3092846SN/AROB<Impl>::numFreeEntries(ThreadID tid) 3102846SN/A{ 3112846SN/A return maxEntries[tid] - threadEntries[tid]; 3122846SN/A} 3132846SN/A 3142846SN/Atemplate <class Impl> 3152846SN/Avoid 3162846SN/AROB<Impl>::doSquash(ThreadID tid) 317835SN/A{ 318768SN/A DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n", 319768SN/A tid, squashedSeqNum[tid]); 320768SN/A 321896SN/A assert(squashIt[tid] != instList[tid].end()); 322835SN/A 323835SN/A if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) { 324835SN/A DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n", 325768SN/A tid); 326768SN/A 327768SN/A squashIt[tid] = instList[tid].end(); 328768SN/A 329768SN/A doneSquashing[tid] = true; 330896SN/A return; 331835SN/A } 332835SN/A 333835SN/A bool robTailUpdate = false; 334768SN/A 335768SN/A for (int numSquashed = 0; 336909SN/A numSquashed < squashWidth && 337768SN/A squashIt[tid] != instList[tid].end() && 338768SN/A (*squashIt[tid])->seqNum > squashedSeqNum[tid]; 3392539SN/A ++numSquashed) 3402539SN/A { 3412539SN/A DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %s, seq num %i.\n", 3422539SN/A (*squashIt[tid])->threadNumber, 343775SN/A (*squashIt[tid])->pcState(), 344768SN/A (*squashIt[tid])->seqNum); 345768SN/A 346768SN/A // Mark the instruction as squashed, and ready to commit so that 347768SN/A // it can drain out of the pipeline. 348768SN/A (*squashIt[tid])->setSquashed(); 3492539SN/A 3502539SN/A (*squashIt[tid])->setCanCommit(); 3512539SN/A 3522539SN/A 3532539SN/A if (squashIt[tid] == instList[tid].begin()) { 354768SN/A DPRINTF(ROB, "Reached head of instruction list while " 355768SN/A "squashing.\n"); 356768SN/A 357768SN/A squashIt[tid] = instList[tid].end(); 358768SN/A 3592539SN/A doneSquashing[tid] = true; 3602539SN/A 3612539SN/A return; 3622539SN/A } 3632539SN/A 3642539SN/A InstIt tail_thread = instList[tid].end(); 3652539SN/A tail_thread--; 3662539SN/A 367768SN/A if ((*squashIt[tid]) == (*tail_thread)) 368768SN/A robTailUpdate = true; 369768SN/A 370 squashIt[tid]--; 371 } 372 373 374 // Check if ROB is done squashing. 375 if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) { 376 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n", 377 tid); 378 379 squashIt[tid] = instList[tid].end(); 380 381 doneSquashing[tid] = true; 382 } 383 384 if (robTailUpdate) { 385 updateTail(); 386 } 387} 388 389 390template <class Impl> 391void 392ROB<Impl>::updateHead() 393{ 394 DynInstPtr head_inst; 395 InstSeqNum lowest_num = 0; 396 bool first_valid = true; 397 398 // @todo: set ActiveThreads through ROB or CPU 399 list<ThreadID>::iterator threads = activeThreads->begin(); 400 list<ThreadID>::iterator end = activeThreads->end(); 401 402 while (threads != end) { 403 ThreadID tid = *threads++; 404 405 if (instList[tid].empty()) 406 continue; 407 408 if (first_valid) { 409 head = instList[tid].begin(); 410 lowest_num = (*head)->seqNum; 411 first_valid = false; 412 continue; 413 } 414 415 InstIt head_thread = instList[tid].begin(); 416 417 DynInstPtr head_inst = (*head_thread); 418 419 assert(head_inst != 0); 420 421 if (head_inst->seqNum < lowest_num) { 422 head = head_thread; 423 lowest_num = head_inst->seqNum; 424 } 425 } 426 427 if (first_valid) { 428 head = instList[0].end(); 429 } 430 431} 432 433template <class Impl> 434void 435ROB<Impl>::updateTail() 436{ 437 tail = instList[0].end(); 438 bool first_valid = true; 439 440 list<ThreadID>::iterator threads = activeThreads->begin(); 441 list<ThreadID>::iterator end = activeThreads->end(); 442 443 while (threads != end) { 444 ThreadID tid = *threads++; 445 446 if (instList[tid].empty()) { 447 continue; 448 } 449 450 // If this is the first valid then assign w/out 451 // comparison 452 if (first_valid) { 453 tail = instList[tid].end(); 454 tail--; 455 first_valid = false; 456 continue; 457 } 458 459 // Assign new tail if this thread's tail is younger 460 // than our current "tail high" 461 InstIt tail_thread = instList[tid].end(); 462 tail_thread--; 463 464 if ((*tail_thread)->seqNum > (*tail)->seqNum) { 465 tail = tail_thread; 466 } 467 } 468} 469 470 471template <class Impl> 472void 473ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid) 474{ 475 if (isEmpty()) { 476 DPRINTF(ROB, "Does not need to squash due to being empty " 477 "[sn:%i]\n", 478 squash_num); 479 480 return; 481 } 482 483 DPRINTF(ROB, "Starting to squash within the ROB.\n"); 484 485 robStatus[tid] = ROBSquashing; 486 487 doneSquashing[tid] = false; 488 489 squashedSeqNum[tid] = squash_num; 490 491 if (!instList[tid].empty()) { 492 InstIt tail_thread = instList[tid].end(); 493 tail_thread--; 494 495 squashIt[tid] = tail_thread; 496 497 doSquash(tid); 498 } 499} 500 501template <class Impl> 502typename Impl::DynInstPtr 503ROB<Impl>::readHeadInst(ThreadID tid) 504{ 505 if (threadEntries[tid] != 0) { 506 InstIt head_thread = instList[tid].begin(); 507 508 assert((*head_thread)->isInROB()==true); 509 510 return *head_thread; 511 } else { 512 return dummyInst; 513 } 514} 515 516template <class Impl> 517typename Impl::DynInstPtr 518ROB<Impl>::readTailInst(ThreadID tid) 519{ 520 InstIt tail_thread = instList[tid].end(); 521 tail_thread--; 522 523 return *tail_thread; 524} 525 526