rob_impl.hh revision 7897:d9e8b1fd1a9f
16928SBrad.Beckmann@amd.com/* 26928SBrad.Beckmann@amd.com * Copyright (c) 2004-2006 The Regents of The University of Michigan 36928SBrad.Beckmann@amd.com * All rights reserved. 46928SBrad.Beckmann@amd.com * 56928SBrad.Beckmann@amd.com * Redistribution and use in source and binary forms, with or without 66928SBrad.Beckmann@amd.com * modification, are permitted provided that the following conditions are 76928SBrad.Beckmann@amd.com * met: redistributions of source code must retain the above copyright 86928SBrad.Beckmann@amd.com * notice, this list of conditions and the following disclaimer; 96928SBrad.Beckmann@amd.com * redistributions in binary form must reproduce the above copyright 106928SBrad.Beckmann@amd.com * notice, this list of conditions and the following disclaimer in the 116928SBrad.Beckmann@amd.com * documentation and/or other materials provided with the distribution; 126928SBrad.Beckmann@amd.com * neither the name of the copyright holders nor the names of its 136928SBrad.Beckmann@amd.com * contributors may be used to endorse or promote products derived from 146928SBrad.Beckmann@amd.com * this software without specific prior written permission. 156928SBrad.Beckmann@amd.com * 166928SBrad.Beckmann@amd.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 176928SBrad.Beckmann@amd.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 186928SBrad.Beckmann@amd.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 196928SBrad.Beckmann@amd.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 206928SBrad.Beckmann@amd.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 216928SBrad.Beckmann@amd.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 226928SBrad.Beckmann@amd.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 236928SBrad.Beckmann@amd.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 246928SBrad.Beckmann@amd.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 256928SBrad.Beckmann@amd.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 266928SBrad.Beckmann@amd.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 276928SBrad.Beckmann@amd.com * 286928SBrad.Beckmann@amd.com * Authors: Kevin Lim 296928SBrad.Beckmann@amd.com * Korey Sewell 306928SBrad.Beckmann@amd.com */ 316928SBrad.Beckmann@amd.com 326928SBrad.Beckmann@amd.com#include <list> 336928SBrad.Beckmann@amd.com 346928SBrad.Beckmann@amd.com#include "config/full_system.hh" 356928SBrad.Beckmann@amd.com#include "cpu/o3/rob.hh" 366928SBrad.Beckmann@amd.com 376928SBrad.Beckmann@amd.comusing namespace std; 386928SBrad.Beckmann@amd.com 396928SBrad.Beckmann@amd.comtemplate <class Impl> 406928SBrad.Beckmann@amd.comROB<Impl>::ROB(O3CPU *_cpu, unsigned _numEntries, unsigned _squashWidth, 416928SBrad.Beckmann@amd.com std::string _smtROBPolicy, unsigned _smtROBThreshold, 426928SBrad.Beckmann@amd.com ThreadID _numThreads) 439113SBrad.Beckmann@amd.com : cpu(_cpu), 446928SBrad.Beckmann@amd.com numEntries(_numEntries), 456928SBrad.Beckmann@amd.com squashWidth(_squashWidth), 468920Snilay@cs.wisc.edu numInstsInROB(0), 476928SBrad.Beckmann@amd.com numThreads(_numThreads) 486928SBrad.Beckmann@amd.com{ 498920Snilay@cs.wisc.edu for (ThreadID tid = 0; tid < numThreads; tid++) { 506928SBrad.Beckmann@amd.com squashedSeqNum[tid] = 0; 517570SBrad.Beckmann@amd.com doneSquashing[tid] = true; 527570SBrad.Beckmann@amd.com threadEntries[tid] = 0; 536928SBrad.Beckmann@amd.com } 546928SBrad.Beckmann@amd.com 556928SBrad.Beckmann@amd.com std::string policy = _smtROBPolicy; 566928SBrad.Beckmann@amd.com 577570SBrad.Beckmann@amd.com //Convert string to lowercase 587570SBrad.Beckmann@amd.com std::transform(policy.begin(), policy.end(), policy.begin(), 597570SBrad.Beckmann@amd.com (int(*)(int)) tolower); 607570SBrad.Beckmann@amd.com 617570SBrad.Beckmann@amd.com //Figure out rob policy 627570SBrad.Beckmann@amd.com if (policy == "dynamic") { 637570SBrad.Beckmann@amd.com robPolicy = Dynamic; 647570SBrad.Beckmann@amd.com 657570SBrad.Beckmann@amd.com //Set Max Entries to Total ROB Capacity 667570SBrad.Beckmann@amd.com for (ThreadID tid = 0; tid < numThreads; tid++) { 677570SBrad.Beckmann@amd.com maxEntries[tid] = numEntries; 689841Snilay@cs.wisc.edu } 697570SBrad.Beckmann@amd.com 708933SBrad.Beckmann@amd.com } else if (policy == "partitioned") { 718933SBrad.Beckmann@amd.com robPolicy = Partitioned; 728933SBrad.Beckmann@amd.com DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n"); 738933SBrad.Beckmann@amd.com 748933SBrad.Beckmann@amd.com //@todo:make work if part_amt doesnt divide evenly. 757570SBrad.Beckmann@amd.com int part_amt = numEntries / numThreads; 766928SBrad.Beckmann@amd.com 776928SBrad.Beckmann@amd.com //Divide ROB up evenly 788933SBrad.Beckmann@amd.com for (ThreadID tid = 0; tid < numThreads; tid++) { 798940SBrad.Beckmann@amd.com maxEntries[tid] = part_amt; 806928SBrad.Beckmann@amd.com } 8110300Scastilloe@unican.es 8210300Scastilloe@unican.es } else if (policy == "threshold") { 8310524Snilay@cs.wisc.edu robPolicy = Threshold; 8410300Scastilloe@unican.es DPRINTF(Fetch, "ROB sharing policy set to Threshold\n"); 859827Sakash.bagdia@arm.com 869827Sakash.bagdia@arm.com int threshold = _smtROBThreshold;; 879827Sakash.bagdia@arm.com 889827Sakash.bagdia@arm.com //Divide up by threshold amount 896928SBrad.Beckmann@amd.com for (ThreadID tid = 0; tid < numThreads; tid++) { 909826Sandreas.hansson@arm.com maxEntries[tid] = threshold; 919826Sandreas.hansson@arm.com } 9210519Snilay@cs.wisc.edu } else { 936928SBrad.Beckmann@amd.com assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic," 949793Sakash.bagdia@arm.com "Partitioned, Threshold}"); 959827Sakash.bagdia@arm.com } 969827Sakash.bagdia@arm.com 979793Sakash.bagdia@arm.com // Set the per-thread iterators to the end of the instruction list. 9810120Snilay@cs.wisc.edu for (ThreadID tid = 0; tid < numThreads; tid++) { 996928SBrad.Beckmann@amd.com squashIt[tid] = instList[tid].end(); 10011267SBrad.Beckmann@amd.com } 10111267SBrad.Beckmann@amd.com 1026928SBrad.Beckmann@amd.com // Initialize the "universal" ROB head & tail point to invalid 1036928SBrad.Beckmann@amd.com // pointers 1046928SBrad.Beckmann@amd.com head = instList[0].end(); 1056928SBrad.Beckmann@amd.com tail = instList[0].end(); 1066928SBrad.Beckmann@amd.com} 1076928SBrad.Beckmann@amd.com 10810120Snilay@cs.wisc.edutemplate <class Impl> 1096928SBrad.Beckmann@amd.comstd::string 1108940SBrad.Beckmann@amd.comROB<Impl>::name() const 1116928SBrad.Beckmann@amd.com{ 11211267SBrad.Beckmann@amd.com return cpu->name() + ".rob"; 11311267SBrad.Beckmann@amd.com} 11411267SBrad.Beckmann@amd.com 11511267SBrad.Beckmann@amd.comtemplate <class Impl> 11611267SBrad.Beckmann@amd.comvoid 11711267SBrad.Beckmann@amd.comROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr) 11811267SBrad.Beckmann@amd.com{ 11911267SBrad.Beckmann@amd.com DPRINTF(ROB, "Setting active threads list pointer.\n"); 12011267SBrad.Beckmann@amd.com activeThreads = at_ptr; 1216928SBrad.Beckmann@amd.com} 1226928SBrad.Beckmann@amd.com 1236928SBrad.Beckmann@amd.comtemplate <class Impl> 1246928SBrad.Beckmann@amd.comvoid 1256928SBrad.Beckmann@amd.comROB<Impl>::switchOut() 1266928SBrad.Beckmann@amd.com{ 1276928SBrad.Beckmann@amd.com for (ThreadID tid = 0; tid < numThreads; tid++) { 1286928SBrad.Beckmann@amd.com instList[tid].clear(); 1296928SBrad.Beckmann@amd.com } 1306928SBrad.Beckmann@amd.com} 1316928SBrad.Beckmann@amd.com 1328801Sgblack@eecs.umich.edutemplate <class Impl> 1336928SBrad.Beckmann@amd.comvoid 1346928SBrad.Beckmann@amd.comROB<Impl>::takeOverFrom() 1356928SBrad.Beckmann@amd.com{ 1366928SBrad.Beckmann@amd.com for (ThreadID tid = 0; tid < numThreads; tid++) { 137 doneSquashing[tid] = true; 138 threadEntries[tid] = 0; 139 squashIt[tid] = instList[tid].end(); 140 } 141 numInstsInROB = 0; 142 143 // Initialize the "universal" ROB head & tail point to invalid 144 // pointers 145 head = instList[0].end(); 146 tail = instList[0].end(); 147} 148 149template <class Impl> 150void 151ROB<Impl>::resetEntries() 152{ 153 if (robPolicy != Dynamic || numThreads > 1) { 154 int active_threads = activeThreads->size(); 155 156 list<ThreadID>::iterator threads = activeThreads->begin(); 157 list<ThreadID>::iterator end = activeThreads->end(); 158 159 while (threads != end) { 160 ThreadID tid = *threads++; 161 162 if (robPolicy == Partitioned) { 163 maxEntries[tid] = numEntries / active_threads; 164 } else if (robPolicy == Threshold && active_threads == 1) { 165 maxEntries[tid] = numEntries; 166 } 167 } 168 } 169} 170 171template <class Impl> 172int 173ROB<Impl>::entryAmount(ThreadID num_threads) 174{ 175 if (robPolicy == Partitioned) { 176 return numEntries / num_threads; 177 } else { 178 return 0; 179 } 180} 181 182template <class Impl> 183int 184ROB<Impl>::countInsts() 185{ 186 int total = 0; 187 188 for (ThreadID tid = 0; tid < numThreads; tid++) 189 total += countInsts(tid); 190 191 return total; 192} 193 194template <class Impl> 195int 196ROB<Impl>::countInsts(ThreadID tid) 197{ 198 return instList[tid].size(); 199} 200 201template <class Impl> 202void 203ROB<Impl>::insertInst(DynInstPtr &inst) 204{ 205 assert(inst); 206 207 robWrites++; 208 209 DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState()); 210 211 assert(numInstsInROB != numEntries); 212 213 ThreadID 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 238template <class Impl> 239void 240ROB<Impl>::retireHead(ThreadID tid) 241{ 242 robWrites++; 243 244 assert(numInstsInROB > 0); 245 246 // Get the head ROB instruction. 247 InstIt head_it = instList[tid].begin(); 248 249 DynInstPtr head_inst = (*head_it); 250 251 assert(head_inst->readyToCommit()); 252 253 DPRINTF(ROB, "[tid:%u]: Retiring head instruction, " 254 "instruction PC %s, [sn:%lli]\n", tid, head_inst->pcState(), 255 head_inst->seqNum); 256 257 --numInstsInROB; 258 --threadEntries[tid]; 259 260 head_inst->clearInROB(); 261 head_inst->setCommitted(); 262 263 instList[tid].erase(head_it); 264 265 //Update "Global" Head of ROB 266 updateHead(); 267 268 // @todo: A special case is needed if the instruction being 269 // retired is the only instruction in the ROB; otherwise the tail 270 // iterator will become invalidated. 271 cpu->removeFrontInst(head_inst); 272} 273 274template <class Impl> 275bool 276ROB<Impl>::isHeadReady(ThreadID tid) 277{ 278 robReads++; 279 if (threadEntries[tid] != 0) { 280 return instList[tid].front()->readyToCommit(); 281 } 282 283 return false; 284} 285 286template <class Impl> 287bool 288ROB<Impl>::canCommit() 289{ 290 //@todo: set ActiveThreads through ROB or CPU 291 list<ThreadID>::iterator threads = activeThreads->begin(); 292 list<ThreadID>::iterator end = activeThreads->end(); 293 294 while (threads != end) { 295 ThreadID tid = *threads++; 296 297 if (isHeadReady(tid)) { 298 return true; 299 } 300 } 301 302 return false; 303} 304 305template <class Impl> 306unsigned 307ROB<Impl>::numFreeEntries() 308{ 309 return numEntries - numInstsInROB; 310} 311 312template <class Impl> 313unsigned 314ROB<Impl>::numFreeEntries(ThreadID tid) 315{ 316 return maxEntries[tid] - threadEntries[tid]; 317} 318 319template <class Impl> 320void 321ROB<Impl>::doSquash(ThreadID tid) 322{ 323 robWrites++; 324 DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n", 325 tid, squashedSeqNum[tid]); 326 327 assert(squashIt[tid] != instList[tid].end()); 328 329 if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) { 330 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n", 331 tid); 332 333 squashIt[tid] = instList[tid].end(); 334 335 doneSquashing[tid] = true; 336 return; 337 } 338 339 bool robTailUpdate = false; 340 341 for (int numSquashed = 0; 342 numSquashed < squashWidth && 343 squashIt[tid] != instList[tid].end() && 344 (*squashIt[tid])->seqNum > squashedSeqNum[tid]; 345 ++numSquashed) 346 { 347 DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %s, seq num %i.\n", 348 (*squashIt[tid])->threadNumber, 349 (*squashIt[tid])->pcState(), 350 (*squashIt[tid])->seqNum); 351 352 // Mark the instruction as squashed, and ready to commit so that 353 // it can drain out of the pipeline. 354 (*squashIt[tid])->setSquashed(); 355 356 (*squashIt[tid])->setCanCommit(); 357 358 359 if (squashIt[tid] == instList[tid].begin()) { 360 DPRINTF(ROB, "Reached head of instruction list while " 361 "squashing.\n"); 362 363 squashIt[tid] = instList[tid].end(); 364 365 doneSquashing[tid] = true; 366 367 return; 368 } 369 370 InstIt tail_thread = instList[tid].end(); 371 tail_thread--; 372 373 if ((*squashIt[tid]) == (*tail_thread)) 374 robTailUpdate = true; 375 376 squashIt[tid]--; 377 } 378 379 380 // Check if ROB is done squashing. 381 if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) { 382 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n", 383 tid); 384 385 squashIt[tid] = instList[tid].end(); 386 387 doneSquashing[tid] = true; 388 } 389 390 if (robTailUpdate) { 391 updateTail(); 392 } 393} 394 395 396template <class Impl> 397void 398ROB<Impl>::updateHead() 399{ 400 DynInstPtr head_inst; 401 InstSeqNum lowest_num = 0; 402 bool first_valid = true; 403 404 // @todo: set ActiveThreads through ROB or CPU 405 list<ThreadID>::iterator threads = activeThreads->begin(); 406 list<ThreadID>::iterator end = activeThreads->end(); 407 408 while (threads != end) { 409 ThreadID tid = *threads++; 410 411 if (instList[tid].empty()) 412 continue; 413 414 if (first_valid) { 415 head = instList[tid].begin(); 416 lowest_num = (*head)->seqNum; 417 first_valid = false; 418 continue; 419 } 420 421 InstIt head_thread = instList[tid].begin(); 422 423 DynInstPtr head_inst = (*head_thread); 424 425 assert(head_inst != 0); 426 427 if (head_inst->seqNum < lowest_num) { 428 head = head_thread; 429 lowest_num = head_inst->seqNum; 430 } 431 } 432 433 if (first_valid) { 434 head = instList[0].end(); 435 } 436 437} 438 439template <class Impl> 440void 441ROB<Impl>::updateTail() 442{ 443 tail = instList[0].end(); 444 bool first_valid = true; 445 446 list<ThreadID>::iterator threads = activeThreads->begin(); 447 list<ThreadID>::iterator end = activeThreads->end(); 448 449 while (threads != end) { 450 ThreadID tid = *threads++; 451 452 if (instList[tid].empty()) { 453 continue; 454 } 455 456 // If this is the first valid then assign w/out 457 // comparison 458 if (first_valid) { 459 tail = instList[tid].end(); 460 tail--; 461 first_valid = false; 462 continue; 463 } 464 465 // Assign new tail if this thread's tail is younger 466 // than our current "tail high" 467 InstIt tail_thread = instList[tid].end(); 468 tail_thread--; 469 470 if ((*tail_thread)->seqNum > (*tail)->seqNum) { 471 tail = tail_thread; 472 } 473 } 474} 475 476 477template <class Impl> 478void 479ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid) 480{ 481 if (isEmpty()) { 482 DPRINTF(ROB, "Does not need to squash due to being empty " 483 "[sn:%i]\n", 484 squash_num); 485 486 return; 487 } 488 489 DPRINTF(ROB, "Starting to squash within the ROB.\n"); 490 491 robStatus[tid] = ROBSquashing; 492 493 doneSquashing[tid] = false; 494 495 squashedSeqNum[tid] = squash_num; 496 497 if (!instList[tid].empty()) { 498 InstIt tail_thread = instList[tid].end(); 499 tail_thread--; 500 501 squashIt[tid] = tail_thread; 502 503 doSquash(tid); 504 } 505} 506 507template <class Impl> 508typename Impl::DynInstPtr 509ROB<Impl>::readHeadInst(ThreadID tid) 510{ 511 if (threadEntries[tid] != 0) { 512 InstIt head_thread = instList[tid].begin(); 513 514 assert((*head_thread)->isInROB()==true); 515 516 return *head_thread; 517 } else { 518 return dummyInst; 519 } 520} 521 522template <class Impl> 523typename Impl::DynInstPtr 524ROB<Impl>::readTailInst(ThreadID tid) 525{ 526 InstIt tail_thread = instList[tid].end(); 527 tail_thread--; 528 529 return *tail_thread; 530} 531 532template <class Impl> 533void 534ROB<Impl>::regStats() 535{ 536 using namespace Stats; 537 robReads 538 .name(name() + ".rob_reads") 539 .desc("The number of ROB reads"); 540 541 robWrites 542 .name(name() + ".rob_writes") 543 .desc("The number of ROB writes"); 544} 545 546