rob_impl.hh revision 7720
11689SN/A/* 22329SN/A * Copyright (c) 2004-2006 The Regents of The University of Michigan 31689SN/A * All rights reserved. 41689SN/A * 51689SN/A * Redistribution and use in source and binary forms, with or without 61689SN/A * modification, are permitted provided that the following conditions are 71689SN/A * met: redistributions of source code must retain the above copyright 81689SN/A * notice, this list of conditions and the following disclaimer; 91689SN/A * redistributions in binary form must reproduce the above copyright 101689SN/A * notice, this list of conditions and the following disclaimer in the 111689SN/A * documentation and/or other materials provided with the distribution; 121689SN/A * neither the name of the copyright holders nor the names of its 131689SN/A * contributors may be used to endorse or promote products derived from 141689SN/A * this software without specific prior written permission. 151689SN/A * 161689SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 171689SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 181689SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 191689SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 201689SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 211689SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 221689SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 231689SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 241689SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 251689SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 261689SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272665Ssaidi@eecs.umich.edu * 282665Ssaidi@eecs.umich.edu * Authors: Kevin Lim 292831Sksewell@umich.edu * Korey Sewell 301689SN/A */ 311689SN/A 326221Snate@binkert.org#include <list> 336221Snate@binkert.org 341858SN/A#include "config/full_system.hh" 351717SN/A#include "cpu/o3/rob.hh" 361060SN/A 376221Snate@binkert.orgusing namespace std; 382292SN/A 391061SN/Atemplate <class Impl> 404329Sktlim@umich.eduROB<Impl>::ROB(O3CPU *_cpu, unsigned _numEntries, unsigned _squashWidth, 412980Sgblack@eecs.umich.edu std::string _smtROBPolicy, unsigned _smtROBThreshold, 426221Snate@binkert.org ThreadID _numThreads) 434329Sktlim@umich.edu : cpu(_cpu), 444329Sktlim@umich.edu numEntries(_numEntries), 451060SN/A squashWidth(_squashWidth), 461060SN/A numInstsInROB(0), 472292SN/A numThreads(_numThreads) 481060SN/A{ 496221Snate@binkert.org for (ThreadID tid = 0; tid < numThreads; tid++) { 502877Sksewell@umich.edu squashedSeqNum[tid] = 0; 512292SN/A doneSquashing[tid] = true; 522292SN/A threadEntries[tid] = 0; 532292SN/A } 542292SN/A 552980Sgblack@eecs.umich.edu std::string policy = _smtROBPolicy; 562292SN/A 572292SN/A //Convert string to lowercase 582292SN/A std::transform(policy.begin(), policy.end(), policy.begin(), 592292SN/A (int(*)(int)) tolower); 602292SN/A 612292SN/A //Figure out rob policy 622292SN/A if (policy == "dynamic") { 632292SN/A robPolicy = Dynamic; 642292SN/A 652292SN/A //Set Max Entries to Total ROB Capacity 666221Snate@binkert.org for (ThreadID tid = 0; tid < numThreads; tid++) { 676221Snate@binkert.org maxEntries[tid] = numEntries; 682292SN/A } 692292SN/A 702292SN/A } else if (policy == "partitioned") { 712292SN/A robPolicy = Partitioned; 724329Sktlim@umich.edu DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n"); 732292SN/A 742292SN/A //@todo:make work if part_amt doesnt divide evenly. 752292SN/A int part_amt = numEntries / numThreads; 762292SN/A 772292SN/A //Divide ROB up evenly 786221Snate@binkert.org for (ThreadID tid = 0; tid < numThreads; tid++) { 796221Snate@binkert.org maxEntries[tid] = part_amt; 802292SN/A } 812292SN/A 822292SN/A } else if (policy == "threshold") { 832292SN/A robPolicy = Threshold; 844329Sktlim@umich.edu DPRINTF(Fetch, "ROB sharing policy set to Threshold\n"); 852292SN/A 862292SN/A int threshold = _smtROBThreshold;; 872292SN/A 882292SN/A //Divide up by threshold amount 896221Snate@binkert.org for (ThreadID tid = 0; tid < numThreads; tid++) { 906221Snate@binkert.org maxEntries[tid] = threshold; 912292SN/A } 922292SN/A } else { 932292SN/A assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic," 942292SN/A "Partitioned, Threshold}"); 952292SN/A } 961060SN/A 972292SN/A // Set the per-thread iterators to the end of the instruction list. 986221Snate@binkert.org for (ThreadID tid = 0; tid < numThreads; tid++) { 996221Snate@binkert.org squashIt[tid] = instList[tid].end(); 1002292SN/A } 1011060SN/A 1022292SN/A // Initialize the "universal" ROB head & tail point to invalid 1032292SN/A // pointers 1042292SN/A head = instList[0].end(); 1052292SN/A tail = instList[0].end(); 1062292SN/A} 1072292SN/A 1082292SN/Atemplate <class Impl> 1094329Sktlim@umich.edustd::string 1104329Sktlim@umich.eduROB<Impl>::name() const 1114329Sktlim@umich.edu{ 1124329Sktlim@umich.edu return cpu->name() + ".rob"; 1134329Sktlim@umich.edu} 1144329Sktlim@umich.edu 1154329Sktlim@umich.edutemplate <class Impl> 1162292SN/Avoid 1176221Snate@binkert.orgROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr) 1182292SN/A{ 1192292SN/A DPRINTF(ROB, "Setting active threads list pointer.\n"); 1202292SN/A activeThreads = at_ptr; 1212292SN/A} 1222292SN/A 1232307SN/Atemplate <class Impl> 1242307SN/Avoid 1252307SN/AROB<Impl>::switchOut() 1262307SN/A{ 1276221Snate@binkert.org for (ThreadID tid = 0; tid < numThreads; tid++) { 1282307SN/A instList[tid].clear(); 1292307SN/A } 1302307SN/A} 1312307SN/A 1322307SN/Atemplate <class Impl> 1332307SN/Avoid 1342307SN/AROB<Impl>::takeOverFrom() 1352307SN/A{ 1366221Snate@binkert.org for (ThreadID tid = 0; tid < numThreads; tid++) { 1372307SN/A doneSquashing[tid] = true; 1382307SN/A threadEntries[tid] = 0; 1392307SN/A squashIt[tid] = instList[tid].end(); 1402307SN/A } 1412307SN/A numInstsInROB = 0; 1422307SN/A 1432307SN/A // Initialize the "universal" ROB head & tail point to invalid 1442307SN/A // pointers 1452307SN/A head = instList[0].end(); 1462307SN/A tail = instList[0].end(); 1472307SN/A} 1482292SN/A 1492292SN/Atemplate <class Impl> 1502292SN/Avoid 1512292SN/AROB<Impl>::resetEntries() 1522292SN/A{ 1532292SN/A if (robPolicy != Dynamic || numThreads > 1) { 1543867Sbinkertn@umich.edu int active_threads = activeThreads->size(); 1552292SN/A 1566221Snate@binkert.org list<ThreadID>::iterator threads = activeThreads->begin(); 1576221Snate@binkert.org list<ThreadID>::iterator end = activeThreads->end(); 1582292SN/A 1593867Sbinkertn@umich.edu while (threads != end) { 1606221Snate@binkert.org ThreadID tid = *threads++; 1613867Sbinkertn@umich.edu 1622292SN/A if (robPolicy == Partitioned) { 1633867Sbinkertn@umich.edu maxEntries[tid] = numEntries / active_threads; 1642292SN/A } else if (robPolicy == Threshold && active_threads == 1) { 1653867Sbinkertn@umich.edu maxEntries[tid] = numEntries; 1662292SN/A } 1672292SN/A } 1682292SN/A } 1692292SN/A} 1702292SN/A 1712292SN/Atemplate <class Impl> 1722292SN/Aint 1736221Snate@binkert.orgROB<Impl>::entryAmount(ThreadID num_threads) 1742292SN/A{ 1752292SN/A if (robPolicy == Partitioned) { 1762292SN/A return numEntries / num_threads; 1772292SN/A } else { 1782292SN/A return 0; 1792292SN/A } 1801060SN/A} 1811060SN/A 1821061SN/Atemplate <class Impl> 1831060SN/Aint 1841060SN/AROB<Impl>::countInsts() 1851060SN/A{ 1866221Snate@binkert.org int total = 0; 1871061SN/A 1886221Snate@binkert.org for (ThreadID tid = 0; tid < numThreads; tid++) 1896221Snate@binkert.org total += countInsts(tid); 1901060SN/A 1912292SN/A return total; 1922292SN/A} 1931060SN/A 1942292SN/Atemplate <class Impl> 1952292SN/Aint 1966221Snate@binkert.orgROB<Impl>::countInsts(ThreadID tid) 1972292SN/A{ 1982292SN/A return instList[tid].size(); 1991060SN/A} 2001060SN/A 2011061SN/Atemplate <class Impl> 2021060SN/Avoid 2031061SN/AROB<Impl>::insertInst(DynInstPtr &inst) 2041060SN/A{ 2051060SN/A assert(inst); 2061060SN/A 2077720Sgblack@eecs.umich.edu DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState()); 2081060SN/A 2091060SN/A assert(numInstsInROB != numEntries); 2101060SN/A 2116221Snate@binkert.org ThreadID tid = inst->threadNumber; 2121060SN/A 2132292SN/A instList[tid].push_back(inst); 2142292SN/A 2152292SN/A //Set Up head iterator if this is the 1st instruction in the ROB 2162292SN/A if (numInstsInROB == 0) { 2172292SN/A head = instList[tid].begin(); 2182292SN/A assert((*head) == inst); 2191060SN/A } 2201060SN/A 2212292SN/A //Must Decrement for iterator to actually be valid since __.end() 2222292SN/A //actually points to 1 after the last inst 2232292SN/A tail = instList[tid].end(); 2242292SN/A tail--; 2252292SN/A 2262292SN/A inst->setInROB(); 2272292SN/A 2282292SN/A ++numInstsInROB; 2292292SN/A ++threadEntries[tid]; 2302292SN/A 2311060SN/A assert((*tail) == inst); 2321060SN/A 2332292SN/A DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]); 2341060SN/A} 2351060SN/A 2362292SN/Atemplate <class Impl> 2372292SN/Avoid 2386221Snate@binkert.orgROB<Impl>::retireHead(ThreadID tid) 2392292SN/A{ 2401061SN/A assert(numInstsInROB > 0); 2411060SN/A 2421060SN/A // Get the head ROB instruction. 2432292SN/A InstIt head_it = instList[tid].begin(); 2441060SN/A 2452292SN/A DynInstPtr head_inst = (*head_it); 2461858SN/A 2471060SN/A assert(head_inst->readyToCommit()); 2481060SN/A 2492292SN/A DPRINTF(ROB, "[tid:%u]: Retiring head instruction, " 2507720Sgblack@eecs.umich.edu "instruction PC %s, [sn:%lli]\n", tid, head_inst->pcState(), 2511060SN/A head_inst->seqNum); 2521060SN/A 2531060SN/A --numInstsInROB; 2542292SN/A --threadEntries[tid]; 2551060SN/A 2562731Sktlim@umich.edu head_inst->clearInROB(); 2572292SN/A head_inst->setCommitted(); 2582292SN/A 2592292SN/A instList[tid].erase(head_it); 2602292SN/A 2612292SN/A //Update "Global" Head of ROB 2622292SN/A updateHead(); 2632292SN/A 2642329SN/A // @todo: A special case is needed if the instruction being 2652329SN/A // retired is the only instruction in the ROB; otherwise the tail 2662329SN/A // iterator will become invalidated. 2671681SN/A cpu->removeFrontInst(head_inst); 2681060SN/A} 2692292SN/A 2702292SN/Atemplate <class Impl> 2712292SN/Abool 2726221Snate@binkert.orgROB<Impl>::isHeadReady(ThreadID tid) 2732292SN/A{ 2742292SN/A if (threadEntries[tid] != 0) { 2752292SN/A return instList[tid].front()->readyToCommit(); 2762292SN/A } 2772292SN/A 2782292SN/A return false; 2792292SN/A} 2802292SN/A 2812292SN/Atemplate <class Impl> 2822292SN/Abool 2832292SN/AROB<Impl>::canCommit() 2842292SN/A{ 2852292SN/A //@todo: set ActiveThreads through ROB or CPU 2866221Snate@binkert.org list<ThreadID>::iterator threads = activeThreads->begin(); 2876221Snate@binkert.org list<ThreadID>::iterator end = activeThreads->end(); 2882292SN/A 2893867Sbinkertn@umich.edu while (threads != end) { 2906221Snate@binkert.org ThreadID tid = *threads++; 2912292SN/A 2922292SN/A if (isHeadReady(tid)) { 2932292SN/A return true; 2942292SN/A } 2951060SN/A } 2961060SN/A 2971060SN/A return false; 2981060SN/A} 2991060SN/A 3001061SN/Atemplate <class Impl> 3011060SN/Aunsigned 3021060SN/AROB<Impl>::numFreeEntries() 3031060SN/A{ 3041060SN/A return numEntries - numInstsInROB; 3051060SN/A} 3061060SN/A 3071061SN/Atemplate <class Impl> 3082292SN/Aunsigned 3096221Snate@binkert.orgROB<Impl>::numFreeEntries(ThreadID tid) 3101060SN/A{ 3112292SN/A return maxEntries[tid] - threadEntries[tid]; 3121060SN/A} 3131060SN/A 3141061SN/Atemplate <class Impl> 3151060SN/Avoid 3166221Snate@binkert.orgROB<Impl>::doSquash(ThreadID tid) 3171060SN/A{ 3182292SN/A DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n", 3192877Sksewell@umich.edu tid, squashedSeqNum[tid]); 3201858SN/A 3212292SN/A assert(squashIt[tid] != instList[tid].end()); 3222292SN/A 3232877Sksewell@umich.edu if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) { 3242292SN/A DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n", 3252292SN/A tid); 3262292SN/A 3272292SN/A squashIt[tid] = instList[tid].end(); 3282292SN/A 3292292SN/A doneSquashing[tid] = true; 3302292SN/A return; 3312292SN/A } 3322292SN/A 3332292SN/A bool robTailUpdate = false; 3341858SN/A 3351858SN/A for (int numSquashed = 0; 3362292SN/A numSquashed < squashWidth && 3372292SN/A squashIt[tid] != instList[tid].end() && 3382877Sksewell@umich.edu (*squashIt[tid])->seqNum > squashedSeqNum[tid]; 3391858SN/A ++numSquashed) 3401858SN/A { 3417720Sgblack@eecs.umich.edu DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %s, seq num %i.\n", 3422292SN/A (*squashIt[tid])->threadNumber, 3437720Sgblack@eecs.umich.edu (*squashIt[tid])->pcState(), 3442292SN/A (*squashIt[tid])->seqNum); 3451858SN/A 3461858SN/A // Mark the instruction as squashed, and ready to commit so that 3471858SN/A // it can drain out of the pipeline. 3482292SN/A (*squashIt[tid])->setSquashed(); 3491858SN/A 3502292SN/A (*squashIt[tid])->setCanCommit(); 3511858SN/A 3522292SN/A 3532292SN/A if (squashIt[tid] == instList[tid].begin()) { 3542292SN/A DPRINTF(ROB, "Reached head of instruction list while " 3551858SN/A "squashing.\n"); 3561858SN/A 3572292SN/A squashIt[tid] = instList[tid].end(); 3581858SN/A 3592292SN/A doneSquashing[tid] = true; 3601858SN/A 3611858SN/A return; 3621858SN/A } 3631858SN/A 3642292SN/A InstIt tail_thread = instList[tid].end(); 3652292SN/A tail_thread--; 3662292SN/A 3672292SN/A if ((*squashIt[tid]) == (*tail_thread)) 3682292SN/A robTailUpdate = true; 3692292SN/A 3702292SN/A squashIt[tid]--; 3711858SN/A } 3721858SN/A 3731858SN/A 3741858SN/A // Check if ROB is done squashing. 3752877Sksewell@umich.edu if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) { 3762292SN/A DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n", 3772292SN/A tid); 3781858SN/A 3792292SN/A squashIt[tid] = instList[tid].end(); 3801858SN/A 3812292SN/A doneSquashing[tid] = true; 3822292SN/A } 3832292SN/A 3842292SN/A if (robTailUpdate) { 3852292SN/A updateTail(); 3862292SN/A } 3872292SN/A} 3882292SN/A 3892292SN/A 3902292SN/Atemplate <class Impl> 3912292SN/Avoid 3922292SN/AROB<Impl>::updateHead() 3932292SN/A{ 3942292SN/A DynInstPtr head_inst; 3952292SN/A InstSeqNum lowest_num = 0; 3962292SN/A bool first_valid = true; 3972292SN/A 3982292SN/A // @todo: set ActiveThreads through ROB or CPU 3996221Snate@binkert.org list<ThreadID>::iterator threads = activeThreads->begin(); 4006221Snate@binkert.org list<ThreadID>::iterator end = activeThreads->end(); 4012292SN/A 4023867Sbinkertn@umich.edu while (threads != end) { 4036221Snate@binkert.org ThreadID tid = *threads++; 4042292SN/A 4053867Sbinkertn@umich.edu if (instList[tid].empty()) 4062292SN/A continue; 4072292SN/A 4082292SN/A if (first_valid) { 4093867Sbinkertn@umich.edu head = instList[tid].begin(); 4102292SN/A lowest_num = (*head)->seqNum; 4112292SN/A first_valid = false; 4122292SN/A continue; 4132292SN/A } 4142292SN/A 4153867Sbinkertn@umich.edu InstIt head_thread = instList[tid].begin(); 4162292SN/A 4172292SN/A DynInstPtr head_inst = (*head_thread); 4182292SN/A 4192292SN/A assert(head_inst != 0); 4202292SN/A 4212292SN/A if (head_inst->seqNum < lowest_num) { 4222292SN/A head = head_thread; 4232292SN/A lowest_num = head_inst->seqNum; 4242292SN/A } 4252292SN/A } 4262292SN/A 4272292SN/A if (first_valid) { 4282292SN/A head = instList[0].end(); 4292292SN/A } 4302292SN/A 4312292SN/A} 4322292SN/A 4332292SN/Atemplate <class Impl> 4342292SN/Avoid 4352292SN/AROB<Impl>::updateTail() 4362292SN/A{ 4372292SN/A tail = instList[0].end(); 4382292SN/A bool first_valid = true; 4392292SN/A 4406221Snate@binkert.org list<ThreadID>::iterator threads = activeThreads->begin(); 4416221Snate@binkert.org list<ThreadID>::iterator end = activeThreads->end(); 4422292SN/A 4433867Sbinkertn@umich.edu while (threads != end) { 4446221Snate@binkert.org ThreadID tid = *threads++; 4452292SN/A 4462292SN/A if (instList[tid].empty()) { 4472292SN/A continue; 4482292SN/A } 4492292SN/A 4502292SN/A // If this is the first valid then assign w/out 4512292SN/A // comparison 4522292SN/A if (first_valid) { 4532292SN/A tail = instList[tid].end(); 4542292SN/A tail--; 4552292SN/A first_valid = false; 4562292SN/A continue; 4572292SN/A } 4582292SN/A 4592292SN/A // Assign new tail if this thread's tail is younger 4602292SN/A // than our current "tail high" 4612292SN/A InstIt tail_thread = instList[tid].end(); 4622292SN/A tail_thread--; 4632292SN/A 4642292SN/A if ((*tail_thread)->seqNum > (*tail)->seqNum) { 4652292SN/A tail = tail_thread; 4662292SN/A } 4672292SN/A } 4682292SN/A} 4692292SN/A 4702292SN/A 4712292SN/Atemplate <class Impl> 4722292SN/Avoid 4736221Snate@binkert.orgROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid) 4742292SN/A{ 4752292SN/A if (isEmpty()) { 4762292SN/A DPRINTF(ROB, "Does not need to squash due to being empty " 4772292SN/A "[sn:%i]\n", 4782292SN/A squash_num); 4792292SN/A 4802292SN/A return; 4812292SN/A } 4822292SN/A 4832292SN/A DPRINTF(ROB, "Starting to squash within the ROB.\n"); 4842292SN/A 4852292SN/A robStatus[tid] = ROBSquashing; 4862292SN/A 4872292SN/A doneSquashing[tid] = false; 4881060SN/A 4892877Sksewell@umich.edu squashedSeqNum[tid] = squash_num; 4901060SN/A 4912292SN/A if (!instList[tid].empty()) { 4922292SN/A InstIt tail_thread = instList[tid].end(); 4932292SN/A tail_thread--; 4941060SN/A 4952292SN/A squashIt[tid] = tail_thread; 4961060SN/A 4972292SN/A doSquash(tid); 4981858SN/A } 4991060SN/A} 5002877Sksewell@umich.edu 5012292SN/Atemplate <class Impl> 5022292SN/Atypename Impl::DynInstPtr 5036221Snate@binkert.orgROB<Impl>::readHeadInst(ThreadID tid) 5042292SN/A{ 5052292SN/A if (threadEntries[tid] != 0) { 5062292SN/A InstIt head_thread = instList[tid].begin(); 5071060SN/A 5082292SN/A assert((*head_thread)->isInROB()==true); 5091858SN/A 5102292SN/A return *head_thread; 5112292SN/A } else { 5122292SN/A return dummyInst; 5132292SN/A } 5141858SN/A} 5152877Sksewell@umich.edu 5162292SN/Atemplate <class Impl> 5172292SN/Atypename Impl::DynInstPtr 5186221Snate@binkert.orgROB<Impl>::readTailInst(ThreadID tid) 5192292SN/A{ 5202292SN/A InstIt tail_thread = instList[tid].end(); 5212292SN/A tail_thread--; 5222292SN/A 5232292SN/A return *tail_thread; 5242292SN/A} 5252292SN/A 526