rob_impl.hh revision 13429
13536SN/A/* 211274Sshingarov@labware.com * Copyright (c) 2012 ARM Limited 310595Sgabeblack@google.com * All rights reserved 410037SARM gem5 Developers * 57752SWilliam.Wang@arm.com * The license below extends only to copyright in the software and shall 67752SWilliam.Wang@arm.com * not be construed as granting a license to any other intellectual 77752SWilliam.Wang@arm.com * property including but not limited to intellectual property relating 87752SWilliam.Wang@arm.com * to a hardware implementation of the functionality of the software 97752SWilliam.Wang@arm.com * licensed hereunder. You may use the software subject to the license 107752SWilliam.Wang@arm.com * terms below provided that you ensure that this notice is replicated 117752SWilliam.Wang@arm.com * unmodified and in its entirety in all distributions of the software, 127752SWilliam.Wang@arm.com * modified or unmodified, in source code or in binary form. 137752SWilliam.Wang@arm.com * 147752SWilliam.Wang@arm.com * Copyright (c) 2004-2006 The Regents of The University of Michigan 157752SWilliam.Wang@arm.com * All rights reserved. 163536SN/A * 173536SN/A * Redistribution and use in source and binary forms, with or without 183536SN/A * modification, are permitted provided that the following conditions are 193536SN/A * met: redistributions of source code must retain the above copyright 203536SN/A * notice, this list of conditions and the following disclaimer; 213536SN/A * redistributions in binary form must reproduce the above copyright 223536SN/A * notice, this list of conditions and the following disclaimer in the 233536SN/A * documentation and/or other materials provided with the distribution; 243536SN/A * neither the name of the copyright holders nor the names of its 253536SN/A * contributors may be used to endorse or promote products derived from 263536SN/A * this software without specific prior written permission. 273536SN/A * 283536SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 293536SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 303536SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 313536SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 323536SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 333536SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 343536SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 353536SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 363536SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 373536SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 383536SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 393536SN/A * 403536SN/A * Authors: Kevin Lim 413536SN/A * Korey Sewell 423536SN/A */ 437752SWilliam.Wang@arm.com 4411274Sshingarov@labware.com#ifndef __CPU_O3_ROB_IMPL_HH__ 453536SN/A#define __CPU_O3_ROB_IMPL_HH__ 463536SN/A 473536SN/A#include <list> 488332Snate@binkert.org 498332Snate@binkert.org#include "cpu/o3/rob.hh" 503536SN/A#include "debug/Fetch.hh" 513536SN/A#include "debug/ROB.hh" 523536SN/A#include "params/DerivO3CPU.hh" 533536SN/A 543536SN/Ausing namespace std; 553536SN/A 563536SN/Atemplate <class Impl> 575543SN/AROB<Impl>::ROB(O3CPU *_cpu, DerivO3CPUParams *params) 585543SN/A : cpu(_cpu), 593536SN/A numEntries(params->numROBEntries), 603536SN/A squashWidth(params->squashWidth), 613536SN/A numInstsInROB(0), 623536SN/A numThreads(params->numThreads) 633536SN/A{ 643536SN/A std::string policy = params->smtROBPolicy; 653536SN/A 663536SN/A //Convert string to lowercase 673536SN/A std::transform(policy.begin(), policy.end(), policy.begin(), 683536SN/A (int(*)(int)) tolower); 693536SN/A 705543SN/A //Figure out rob policy 715543SN/A if (policy == "dynamic") { 723536SN/A robPolicy = Dynamic; 733536SN/A 743536SN/A //Set Max Entries to Total ROB Capacity 753536SN/A for (ThreadID tid = 0; tid < numThreads; tid++) { 763536SN/A maxEntries[tid] = numEntries; 773536SN/A } 783536SN/A 793536SN/A } else if (policy == "partitioned") { 803536SN/A robPolicy = Partitioned; 813536SN/A DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n"); 823536SN/A 833536SN/A //@todo:make work if part_amt doesnt divide evenly. 843536SN/A int part_amt = numEntries / numThreads; 853536SN/A 863536SN/A //Divide ROB up evenly 873536SN/A for (ThreadID tid = 0; tid < numThreads; tid++) { 885543SN/A maxEntries[tid] = part_amt; 893536SN/A } 903536SN/A 913536SN/A } else if (policy == "threshold") { 923536SN/A robPolicy = Threshold; 933536SN/A DPRINTF(Fetch, "ROB sharing policy set to Threshold\n"); 943536SN/A 953536SN/A int threshold = params->smtROBThreshold;; 963536SN/A 973536SN/A //Divide up by threshold amount 983536SN/A for (ThreadID tid = 0; tid < numThreads; tid++) { 993536SN/A maxEntries[tid] = threshold; 1003536SN/A } 1013536SN/A } else { 1023536SN/A assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic," 1033536SN/A "Partitioned, Threshold}"); 1043536SN/A } 1053536SN/A 1063536SN/A resetState(); 1073536SN/A} 1085543SN/A 1095543SN/Atemplate <class Impl> 1103536SN/Avoid 1113536SN/AROB<Impl>::resetState() 1123536SN/A{ 1133536SN/A for (ThreadID tid = 0; tid < numThreads; tid++) { 1143536SN/A doneSquashing[tid] = true; 1153536SN/A threadEntries[tid] = 0; 1163536SN/A squashIt[tid] = instList[tid].end(); 1173536SN/A squashedSeqNum[tid] = 0; 1183536SN/A } 1193536SN/A numInstsInROB = 0; 1203536SN/A 1213536SN/A // Initialize the "universal" ROB head & tail point to invalid 1223536SN/A // pointers 1233536SN/A head = instList[0].end(); 1243536SN/A tail = instList[0].end(); 1253536SN/A} 1263536SN/A 1273536SN/Atemplate <class Impl> 1283536SN/Astd::string 1293536SN/AROB<Impl>::name() const 1303536SN/A{ 1313536SN/A return cpu->name() + ".rob"; 1323536SN/A} 1333536SN/A 1343536SN/Atemplate <class Impl> 13511793Sbrandon.potter@amd.comvoid 13611793Sbrandon.potter@amd.comROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr) 1373536SN/A{ 1385569SN/A DPRINTF(ROB, "Setting active threads list pointer.\n"); 1393536SN/A activeThreads = at_ptr; 1403536SN/A} 1413536SN/A 1429020Sgblack@eecs.umich.edutemplate <class Impl> 1438229Snate@binkert.orgvoid 1448229Snate@binkert.orgROB<Impl>::drainSanityCheck() const 14510037SARM gem5 Developers{ 1467752SWilliam.Wang@arm.com for (ThreadID tid = 0; tid < numThreads; tid++) 1477752SWilliam.Wang@arm.com assert(instList[tid].empty()); 14810707SAndreas.Sandberg@ARM.com assert(isEmpty()); 1493536SN/A} 1503536SN/A 1513536SN/Atemplate <class Impl> 1523536SN/Avoid 1538229Snate@binkert.orgROB<Impl>::takeOverFrom() 1543536SN/A{ 1557752SWilliam.Wang@arm.com resetState(); 1568232Snate@binkert.org} 1578232Snate@binkert.org 1588229Snate@binkert.orgtemplate <class Impl> 1593536SN/Avoid 1603536SN/AROB<Impl>::resetEntries() 1618782Sgblack@eecs.umich.edu{ 1623536SN/A if (robPolicy != Dynamic || numThreads > 1) { 1633536SN/A int active_threads = activeThreads->size(); 1643536SN/A 1657752SWilliam.Wang@arm.com list<ThreadID>::iterator threads = activeThreads->begin(); 1663536SN/A list<ThreadID>::iterator end = activeThreads->end(); 1675569SN/A 16812031Sgabeblack@google.com while (threads != end) { 1693536SN/A ThreadID tid = *threads++; 1703536SN/A 1713536SN/A if (robPolicy == Partitioned) { 1725569SN/A maxEntries[tid] = numEntries / active_threads; 1735569SN/A } else if (robPolicy == Threshold && active_threads == 1) { 1745569SN/A maxEntries[tid] = numEntries; 1753536SN/A } 1763536SN/A } 1773536SN/A } 1788782Sgblack@eecs.umich.edu} 17910707SAndreas.Sandberg@ARM.com 18010707SAndreas.Sandberg@ARM.comtemplate <class Impl> 18110707SAndreas.Sandberg@ARM.comint 18210707SAndreas.Sandberg@ARM.comROB<Impl>::entryAmount(ThreadID num_threads) 1838782Sgblack@eecs.umich.edu{ 18410707SAndreas.Sandberg@ARM.com if (robPolicy == Partitioned) { 1858782Sgblack@eecs.umich.edu return numEntries / num_threads; 1868782Sgblack@eecs.umich.edu } else { 1878782Sgblack@eecs.umich.edu return 0; 1888782Sgblack@eecs.umich.edu } 1898782Sgblack@eecs.umich.edu} 1908782Sgblack@eecs.umich.edu 1918782Sgblack@eecs.umich.edutemplate <class Impl> 1928782Sgblack@eecs.umich.eduint 1933536SN/AROB<Impl>::countInsts() 1948782Sgblack@eecs.umich.edu{ 1958782Sgblack@eecs.umich.edu int total = 0; 1963536SN/A 1973536SN/A for (ThreadID tid = 0; tid < numThreads; tid++) 1983536SN/A total += countInsts(tid); 19911274Sshingarov@labware.com 2003536SN/A return total; 20111274Sshingarov@labware.com} 2027752SWilliam.Wang@arm.com 20311274Sshingarov@labware.comtemplate <class Impl> 20411274Sshingarov@labware.comint 20511274Sshingarov@labware.comROB<Impl>::countInsts(ThreadID tid) 20611274Sshingarov@labware.com{ 20711274Sshingarov@labware.com return instList[tid].size(); 2083536SN/A} 20911274Sshingarov@labware.com 21011274Sshingarov@labware.comtemplate <class Impl> 21111274Sshingarov@labware.comvoid 21211274Sshingarov@labware.comROB<Impl>::insertInst(const DynInstPtr &inst) 21311274Sshingarov@labware.com{ 2143536SN/A assert(inst); 2153536SN/A 2163536SN/A robWrites++; 2173536SN/A 21811274Sshingarov@labware.com DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState()); 2193536SN/A 22011274Sshingarov@labware.com assert(numInstsInROB != numEntries); 2217752SWilliam.Wang@arm.com 22211274Sshingarov@labware.com ThreadID tid = inst->threadNumber; 22311274Sshingarov@labware.com 22411274Sshingarov@labware.com instList[tid].push_back(inst); 22511274Sshingarov@labware.com 22611274Sshingarov@labware.com //Set Up head iterator if this is the 1st instruction in the ROB 22711274Sshingarov@labware.com if (numInstsInROB == 0) { 22811274Sshingarov@labware.com head = instList[tid].begin(); 22911274Sshingarov@labware.com assert((*head) == inst); 2307752SWilliam.Wang@arm.com } 23111274Sshingarov@labware.com 23211274Sshingarov@labware.com //Must Decrement for iterator to actually be valid since __.end() 23311274Sshingarov@labware.com //actually points to 1 after the last inst 23411274Sshingarov@labware.com tail = instList[tid].end(); 23511274Sshingarov@labware.com tail--; 2363536SN/A 2373536SN/A inst->setInROB(); 2383536SN/A 23911274Sshingarov@labware.com ++numInstsInROB; 24011274Sshingarov@labware.com ++threadEntries[tid]; 2413536SN/A 24211274Sshingarov@labware.com assert((*tail) == inst); 24311274Sshingarov@labware.com 24411274Sshingarov@labware.com DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]); 24511274Sshingarov@labware.com} 24611274Sshingarov@labware.com 24711274Sshingarov@labware.comtemplate <class Impl> 24811274Sshingarov@labware.comvoid 24911274Sshingarov@labware.comROB<Impl>::retireHead(ThreadID tid) 25011274Sshingarov@labware.com{ 25111274Sshingarov@labware.com robWrites++; 25211274Sshingarov@labware.com 25311274Sshingarov@labware.com assert(numInstsInROB > 0); 25411274Sshingarov@labware.com 25511274Sshingarov@labware.com // Get the head ROB instruction by copying it and remove it from the list 25611274Sshingarov@labware.com InstIt head_it = instList[tid].begin(); 25711274Sshingarov@labware.com 25811274Sshingarov@labware.com DynInstPtr head_inst = std::move(*head_it); 25911274Sshingarov@labware.com instList[tid].erase(head_it); 26011274Sshingarov@labware.com 26111274Sshingarov@labware.com assert(head_inst->readyToCommit()); 26211274Sshingarov@labware.com 26311274Sshingarov@labware.com DPRINTF(ROB, "[tid:%u]: Retiring head instruction, " 26411274Sshingarov@labware.com "instruction PC %s, [sn:%lli]\n", tid, head_inst->pcState(), 26511274Sshingarov@labware.com head_inst->seqNum); 2663536SN/A 2673536SN/A --numInstsInROB; 26811274Sshingarov@labware.com --threadEntries[tid]; 26911274Sshingarov@labware.com 27011274Sshingarov@labware.com head_inst->clearInROB(); 27111274Sshingarov@labware.com head_inst->setCommitted(); 27211274Sshingarov@labware.com 27311274Sshingarov@labware.com //Update "Global" Head of ROB 27411274Sshingarov@labware.com updateHead(); 27511274Sshingarov@labware.com 27611274Sshingarov@labware.com // @todo: A special case is needed if the instruction being 27711274Sshingarov@labware.com // retired is the only instruction in the ROB; otherwise the tail 27811274Sshingarov@labware.com // iterator will become invalidated. 27911274Sshingarov@labware.com cpu->removeFrontInst(head_inst); 28011274Sshingarov@labware.com} 28111274Sshingarov@labware.com 28211274Sshingarov@labware.comtemplate <class Impl> 28311274Sshingarov@labware.combool 28411274Sshingarov@labware.comROB<Impl>::isHeadReady(ThreadID tid) 28511274Sshingarov@labware.com{ 28611274Sshingarov@labware.com robReads++; 28711274Sshingarov@labware.com if (threadEntries[tid] != 0) { 28811274Sshingarov@labware.com return instList[tid].front()->readyToCommit(); 28911274Sshingarov@labware.com } 29011274Sshingarov@labware.com 29111274Sshingarov@labware.com return false; 29211274Sshingarov@labware.com} 29311274Sshingarov@labware.com 29411274Sshingarov@labware.comtemplate <class Impl> 29511274Sshingarov@labware.combool 29611274Sshingarov@labware.comROB<Impl>::canCommit() 29711274Sshingarov@labware.com{ 29811274Sshingarov@labware.com //@todo: set ActiveThreads through ROB or CPU 29911274Sshingarov@labware.com list<ThreadID>::iterator threads = activeThreads->begin(); 30012031Sgabeblack@google.com list<ThreadID>::iterator end = activeThreads->end(); 30111274Sshingarov@labware.com 30212031Sgabeblack@google.com while (threads != end) { 30311274Sshingarov@labware.com ThreadID tid = *threads++; 304 305 if (isHeadReady(tid)) { 306 return true; 307 } 308 } 309 310 return false; 311} 312 313template <class Impl> 314unsigned 315ROB<Impl>::numFreeEntries() 316{ 317 return numEntries - numInstsInROB; 318} 319 320template <class Impl> 321unsigned 322ROB<Impl>::numFreeEntries(ThreadID tid) 323{ 324 return maxEntries[tid] - threadEntries[tid]; 325} 326 327template <class Impl> 328void 329ROB<Impl>::doSquash(ThreadID tid) 330{ 331 robWrites++; 332 DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n", 333 tid, squashedSeqNum[tid]); 334 335 assert(squashIt[tid] != instList[tid].end()); 336 337 if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) { 338 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n", 339 tid); 340 341 squashIt[tid] = instList[tid].end(); 342 343 doneSquashing[tid] = true; 344 return; 345 } 346 347 bool robTailUpdate = false; 348 349 for (int numSquashed = 0; 350 numSquashed < squashWidth && 351 squashIt[tid] != instList[tid].end() && 352 (*squashIt[tid])->seqNum > squashedSeqNum[tid]; 353 ++numSquashed) 354 { 355 DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %s, seq num %i.\n", 356 (*squashIt[tid])->threadNumber, 357 (*squashIt[tid])->pcState(), 358 (*squashIt[tid])->seqNum); 359 360 // Mark the instruction as squashed, and ready to commit so that 361 // it can drain out of the pipeline. 362 (*squashIt[tid])->setSquashed(); 363 364 (*squashIt[tid])->setCanCommit(); 365 366 367 if (squashIt[tid] == instList[tid].begin()) { 368 DPRINTF(ROB, "Reached head of instruction list while " 369 "squashing.\n"); 370 371 squashIt[tid] = instList[tid].end(); 372 373 doneSquashing[tid] = true; 374 375 return; 376 } 377 378 InstIt tail_thread = instList[tid].end(); 379 tail_thread--; 380 381 if ((*squashIt[tid]) == (*tail_thread)) 382 robTailUpdate = true; 383 384 squashIt[tid]--; 385 } 386 387 388 // Check if ROB is done squashing. 389 if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) { 390 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n", 391 tid); 392 393 squashIt[tid] = instList[tid].end(); 394 395 doneSquashing[tid] = true; 396 } 397 398 if (robTailUpdate) { 399 updateTail(); 400 } 401} 402 403 404template <class Impl> 405void 406ROB<Impl>::updateHead() 407{ 408 InstSeqNum lowest_num = 0; 409 bool first_valid = true; 410 411 // @todo: set ActiveThreads through ROB or CPU 412 list<ThreadID>::iterator threads = activeThreads->begin(); 413 list<ThreadID>::iterator end = activeThreads->end(); 414 415 while (threads != end) { 416 ThreadID tid = *threads++; 417 418 if (instList[tid].empty()) 419 continue; 420 421 if (first_valid) { 422 head = instList[tid].begin(); 423 lowest_num = (*head)->seqNum; 424 first_valid = false; 425 continue; 426 } 427 428 InstIt head_thread = instList[tid].begin(); 429 430 DynInstPtr head_inst = (*head_thread); 431 432 assert(head_inst != 0); 433 434 if (head_inst->seqNum < lowest_num) { 435 head = head_thread; 436 lowest_num = head_inst->seqNum; 437 } 438 } 439 440 if (first_valid) { 441 head = instList[0].end(); 442 } 443 444} 445 446template <class Impl> 447void 448ROB<Impl>::updateTail() 449{ 450 tail = instList[0].end(); 451 bool first_valid = true; 452 453 list<ThreadID>::iterator threads = activeThreads->begin(); 454 list<ThreadID>::iterator end = activeThreads->end(); 455 456 while (threads != end) { 457 ThreadID tid = *threads++; 458 459 if (instList[tid].empty()) { 460 continue; 461 } 462 463 // If this is the first valid then assign w/out 464 // comparison 465 if (first_valid) { 466 tail = instList[tid].end(); 467 tail--; 468 first_valid = false; 469 continue; 470 } 471 472 // Assign new tail if this thread's tail is younger 473 // than our current "tail high" 474 InstIt tail_thread = instList[tid].end(); 475 tail_thread--; 476 477 if ((*tail_thread)->seqNum > (*tail)->seqNum) { 478 tail = tail_thread; 479 } 480 } 481} 482 483 484template <class Impl> 485void 486ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid) 487{ 488 if (isEmpty(tid)) { 489 DPRINTF(ROB, "Does not need to squash due to being empty " 490 "[sn:%i]\n", 491 squash_num); 492 493 return; 494 } 495 496 DPRINTF(ROB, "Starting to squash within the ROB.\n"); 497 498 robStatus[tid] = ROBSquashing; 499 500 doneSquashing[tid] = false; 501 502 squashedSeqNum[tid] = squash_num; 503 504 if (!instList[tid].empty()) { 505 InstIt tail_thread = instList[tid].end(); 506 tail_thread--; 507 508 squashIt[tid] = tail_thread; 509 510 doSquash(tid); 511 } 512} 513 514template <class Impl> 515const typename Impl::DynInstPtr& 516ROB<Impl>::readHeadInst(ThreadID tid) 517{ 518 if (threadEntries[tid] != 0) { 519 InstIt head_thread = instList[tid].begin(); 520 521 assert((*head_thread)->isInROB()); 522 523 return *head_thread; 524 } else { 525 return dummyInst; 526 } 527} 528 529template <class Impl> 530typename Impl::DynInstPtr 531ROB<Impl>::readTailInst(ThreadID tid) 532{ 533 InstIt tail_thread = instList[tid].end(); 534 tail_thread--; 535 536 return *tail_thread; 537} 538 539template <class Impl> 540void 541ROB<Impl>::regStats() 542{ 543 using namespace Stats; 544 robReads 545 .name(name() + ".rob_reads") 546 .desc("The number of ROB reads"); 547 548 robWrites 549 .name(name() + ".rob_writes") 550 .desc("The number of ROB writes"); 551} 552 553template <class Impl> 554typename Impl::DynInstPtr 555ROB<Impl>::findInst(ThreadID tid, InstSeqNum squash_inst) 556{ 557 for (InstIt it = instList[tid].begin(); it != instList[tid].end(); it++) { 558 if ((*it)->seqNum == squash_inst) { 559 return *it; 560 } 561 } 562 return NULL; 563} 564 565#endif//__CPU_O3_ROB_IMPL_HH__ 566