rob_impl.hh revision 13453:4a7a060ea26e
1/* 2 * Copyright (c) 2012 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Copyright (c) 2004-2006 The Regents of The University of Michigan 15 * All rights reserved. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions are 19 * met: redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer; 21 * redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution; 24 * neither the name of the copyright holders nor the names of its 25 * contributors may be used to endorse or promote products derived from 26 * this software without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 39 * 40 * Authors: Kevin Lim 41 * Korey Sewell 42 */ 43 44#ifndef __CPU_O3_ROB_IMPL_HH__ 45#define __CPU_O3_ROB_IMPL_HH__ 46 47#include <list> 48 49#include "base/logging.hh" 50#include "cpu/o3/rob.hh" 51#include "debug/Fetch.hh" 52#include "debug/ROB.hh" 53#include "params/DerivO3CPU.hh" 54 55using namespace std; 56 57template <class Impl> 58ROB<Impl>::ROB(O3CPU *_cpu, DerivO3CPUParams *params) 59 : cpu(_cpu), 60 numEntries(params->numROBEntries), 61 squashWidth(params->squashWidth), 62 numInstsInROB(0), 63 numThreads(params->numThreads) 64{ 65 std::string policy = params->smtROBPolicy; 66 67 //Convert string to lowercase 68 std::transform(policy.begin(), policy.end(), policy.begin(), 69 (int(*)(int)) tolower); 70 71 //Figure out rob policy 72 if (policy == "dynamic") { 73 robPolicy = Dynamic; 74 75 //Set Max Entries to Total ROB Capacity 76 for (ThreadID tid = 0; tid < numThreads; tid++) { 77 maxEntries[tid] = numEntries; 78 } 79 80 } else if (policy == "partitioned") { 81 robPolicy = Partitioned; 82 DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n"); 83 84 //@todo:make work if part_amt doesnt divide evenly. 85 int part_amt = numEntries / numThreads; 86 87 //Divide ROB up evenly 88 for (ThreadID tid = 0; tid < numThreads; tid++) { 89 maxEntries[tid] = part_amt; 90 } 91 92 } else if (policy == "threshold") { 93 robPolicy = Threshold; 94 DPRINTF(Fetch, "ROB sharing policy set to Threshold\n"); 95 96 int threshold = params->smtROBThreshold;; 97 98 //Divide up by threshold amount 99 for (ThreadID tid = 0; tid < numThreads; tid++) { 100 maxEntries[tid] = threshold; 101 } 102 } else { 103 panic("Invalid ROB sharing policy. Options are: Dynamic, " 104 "Partitioned, Threshold"); 105 } 106 for (ThreadID tid = numThreads; tid < Impl::MaxThreads; tid++) { 107 maxEntries[tid] = 0; 108 } 109 110 resetState(); 111} 112 113template <class Impl> 114void 115ROB<Impl>::resetState() 116{ 117 for (ThreadID tid = 0; tid < Impl::MaxThreads; tid++) { 118 threadEntries[tid] = 0; 119 squashIt[tid] = instList[tid].end(); 120 squashedSeqNum[tid] = 0; 121 doneSquashing[tid] = true; 122 } 123 numInstsInROB = 0; 124 125 // Initialize the "universal" ROB head & tail point to invalid 126 // pointers 127 head = instList[0].end(); 128 tail = instList[0].end(); 129} 130 131template <class Impl> 132std::string 133ROB<Impl>::name() const 134{ 135 return cpu->name() + ".rob"; 136} 137 138template <class Impl> 139void 140ROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr) 141{ 142 DPRINTF(ROB, "Setting active threads list pointer.\n"); 143 activeThreads = at_ptr; 144} 145 146template <class Impl> 147void 148ROB<Impl>::drainSanityCheck() const 149{ 150 for (ThreadID tid = 0; tid < numThreads; tid++) 151 assert(instList[tid].empty()); 152 assert(isEmpty()); 153} 154 155template <class Impl> 156void 157ROB<Impl>::takeOverFrom() 158{ 159 resetState(); 160} 161 162template <class Impl> 163void 164ROB<Impl>::resetEntries() 165{ 166 if (robPolicy != Dynamic || numThreads > 1) { 167 int active_threads = activeThreads->size(); 168 169 list<ThreadID>::iterator threads = activeThreads->begin(); 170 list<ThreadID>::iterator end = activeThreads->end(); 171 172 while (threads != end) { 173 ThreadID tid = *threads++; 174 175 if (robPolicy == Partitioned) { 176 maxEntries[tid] = numEntries / active_threads; 177 } else if (robPolicy == Threshold && active_threads == 1) { 178 maxEntries[tid] = numEntries; 179 } 180 } 181 } 182} 183 184template <class Impl> 185int 186ROB<Impl>::entryAmount(ThreadID num_threads) 187{ 188 if (robPolicy == Partitioned) { 189 return numEntries / num_threads; 190 } else { 191 return 0; 192 } 193} 194 195template <class Impl> 196int 197ROB<Impl>::countInsts() 198{ 199 int total = 0; 200 201 for (ThreadID tid = 0; tid < numThreads; tid++) 202 total += countInsts(tid); 203 204 return total; 205} 206 207template <class Impl> 208int 209ROB<Impl>::countInsts(ThreadID tid) 210{ 211 return instList[tid].size(); 212} 213 214template <class Impl> 215void 216ROB<Impl>::insertInst(const DynInstPtr &inst) 217{ 218 assert(inst); 219 220 robWrites++; 221 222 DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState()); 223 224 assert(numInstsInROB != numEntries); 225 226 ThreadID tid = inst->threadNumber; 227 228 instList[tid].push_back(inst); 229 230 //Set Up head iterator if this is the 1st instruction in the ROB 231 if (numInstsInROB == 0) { 232 head = instList[tid].begin(); 233 assert((*head) == inst); 234 } 235 236 //Must Decrement for iterator to actually be valid since __.end() 237 //actually points to 1 after the last inst 238 tail = instList[tid].end(); 239 tail--; 240 241 inst->setInROB(); 242 243 ++numInstsInROB; 244 ++threadEntries[tid]; 245 246 assert((*tail) == inst); 247 248 DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]); 249} 250 251template <class Impl> 252void 253ROB<Impl>::retireHead(ThreadID tid) 254{ 255 robWrites++; 256 257 assert(numInstsInROB > 0); 258 259 // Get the head ROB instruction by copying it and remove it from the list 260 InstIt head_it = instList[tid].begin(); 261 262 DynInstPtr head_inst = std::move(*head_it); 263 instList[tid].erase(head_it); 264 265 assert(head_inst->readyToCommit()); 266 267 DPRINTF(ROB, "[tid:%u]: Retiring head instruction, " 268 "instruction PC %s, [sn:%lli]\n", tid, head_inst->pcState(), 269 head_inst->seqNum); 270 271 --numInstsInROB; 272 --threadEntries[tid]; 273 274 head_inst->clearInROB(); 275 head_inst->setCommitted(); 276 277 //Update "Global" Head of ROB 278 updateHead(); 279 280 // @todo: A special case is needed if the instruction being 281 // retired is the only instruction in the ROB; otherwise the tail 282 // iterator will become invalidated. 283 cpu->removeFrontInst(head_inst); 284} 285 286template <class Impl> 287bool 288ROB<Impl>::isHeadReady(ThreadID tid) 289{ 290 robReads++; 291 if (threadEntries[tid] != 0) { 292 return instList[tid].front()->readyToCommit(); 293 } 294 295 return false; 296} 297 298template <class Impl> 299bool 300ROB<Impl>::canCommit() 301{ 302 //@todo: set ActiveThreads through ROB or CPU 303 list<ThreadID>::iterator threads = activeThreads->begin(); 304 list<ThreadID>::iterator end = activeThreads->end(); 305 306 while (threads != end) { 307 ThreadID tid = *threads++; 308 309 if (isHeadReady(tid)) { 310 return true; 311 } 312 } 313 314 return false; 315} 316 317template <class Impl> 318unsigned 319ROB<Impl>::numFreeEntries() 320{ 321 return numEntries - numInstsInROB; 322} 323 324template <class Impl> 325unsigned 326ROB<Impl>::numFreeEntries(ThreadID tid) 327{ 328 return maxEntries[tid] - threadEntries[tid]; 329} 330 331template <class Impl> 332void 333ROB<Impl>::doSquash(ThreadID tid) 334{ 335 robWrites++; 336 DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n", 337 tid, squashedSeqNum[tid]); 338 339 assert(squashIt[tid] != instList[tid].end()); 340 341 if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) { 342 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n", 343 tid); 344 345 squashIt[tid] = instList[tid].end(); 346 347 doneSquashing[tid] = true; 348 return; 349 } 350 351 bool robTailUpdate = false; 352 353 for (int numSquashed = 0; 354 numSquashed < squashWidth && 355 squashIt[tid] != instList[tid].end() && 356 (*squashIt[tid])->seqNum > squashedSeqNum[tid]; 357 ++numSquashed) 358 { 359 DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %s, seq num %i.\n", 360 (*squashIt[tid])->threadNumber, 361 (*squashIt[tid])->pcState(), 362 (*squashIt[tid])->seqNum); 363 364 // Mark the instruction as squashed, and ready to commit so that 365 // it can drain out of the pipeline. 366 (*squashIt[tid])->setSquashed(); 367 368 (*squashIt[tid])->setCanCommit(); 369 370 371 if (squashIt[tid] == instList[tid].begin()) { 372 DPRINTF(ROB, "Reached head of instruction list while " 373 "squashing.\n"); 374 375 squashIt[tid] = instList[tid].end(); 376 377 doneSquashing[tid] = true; 378 379 return; 380 } 381 382 InstIt tail_thread = instList[tid].end(); 383 tail_thread--; 384 385 if ((*squashIt[tid]) == (*tail_thread)) 386 robTailUpdate = true; 387 388 squashIt[tid]--; 389 } 390 391 392 // Check if ROB is done squashing. 393 if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) { 394 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n", 395 tid); 396 397 squashIt[tid] = instList[tid].end(); 398 399 doneSquashing[tid] = true; 400 } 401 402 if (robTailUpdate) { 403 updateTail(); 404 } 405} 406 407 408template <class Impl> 409void 410ROB<Impl>::updateHead() 411{ 412 InstSeqNum lowest_num = 0; 413 bool first_valid = true; 414 415 // @todo: set ActiveThreads through ROB or CPU 416 list<ThreadID>::iterator threads = activeThreads->begin(); 417 list<ThreadID>::iterator end = activeThreads->end(); 418 419 while (threads != end) { 420 ThreadID tid = *threads++; 421 422 if (instList[tid].empty()) 423 continue; 424 425 if (first_valid) { 426 head = instList[tid].begin(); 427 lowest_num = (*head)->seqNum; 428 first_valid = false; 429 continue; 430 } 431 432 InstIt head_thread = instList[tid].begin(); 433 434 DynInstPtr head_inst = (*head_thread); 435 436 assert(head_inst != 0); 437 438 if (head_inst->seqNum < lowest_num) { 439 head = head_thread; 440 lowest_num = head_inst->seqNum; 441 } 442 } 443 444 if (first_valid) { 445 head = instList[0].end(); 446 } 447 448} 449 450template <class Impl> 451void 452ROB<Impl>::updateTail() 453{ 454 tail = instList[0].end(); 455 bool first_valid = true; 456 457 list<ThreadID>::iterator threads = activeThreads->begin(); 458 list<ThreadID>::iterator end = activeThreads->end(); 459 460 while (threads != end) { 461 ThreadID tid = *threads++; 462 463 if (instList[tid].empty()) { 464 continue; 465 } 466 467 // If this is the first valid then assign w/out 468 // comparison 469 if (first_valid) { 470 tail = instList[tid].end(); 471 tail--; 472 first_valid = false; 473 continue; 474 } 475 476 // Assign new tail if this thread's tail is younger 477 // than our current "tail high" 478 InstIt tail_thread = instList[tid].end(); 479 tail_thread--; 480 481 if ((*tail_thread)->seqNum > (*tail)->seqNum) { 482 tail = tail_thread; 483 } 484 } 485} 486 487 488template <class Impl> 489void 490ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid) 491{ 492 if (isEmpty(tid)) { 493 DPRINTF(ROB, "Does not need to squash due to being empty " 494 "[sn:%i]\n", 495 squash_num); 496 497 return; 498 } 499 500 DPRINTF(ROB, "Starting to squash within the ROB.\n"); 501 502 robStatus[tid] = ROBSquashing; 503 504 doneSquashing[tid] = false; 505 506 squashedSeqNum[tid] = squash_num; 507 508 if (!instList[tid].empty()) { 509 InstIt tail_thread = instList[tid].end(); 510 tail_thread--; 511 512 squashIt[tid] = tail_thread; 513 514 doSquash(tid); 515 } 516} 517 518template <class Impl> 519const typename Impl::DynInstPtr& 520ROB<Impl>::readHeadInst(ThreadID tid) 521{ 522 if (threadEntries[tid] != 0) { 523 InstIt head_thread = instList[tid].begin(); 524 525 assert((*head_thread)->isInROB()); 526 527 return *head_thread; 528 } else { 529 return dummyInst; 530 } 531} 532 533template <class Impl> 534typename Impl::DynInstPtr 535ROB<Impl>::readTailInst(ThreadID tid) 536{ 537 InstIt tail_thread = instList[tid].end(); 538 tail_thread--; 539 540 return *tail_thread; 541} 542 543template <class Impl> 544void 545ROB<Impl>::regStats() 546{ 547 using namespace Stats; 548 robReads 549 .name(name() + ".rob_reads") 550 .desc("The number of ROB reads"); 551 552 robWrites 553 .name(name() + ".rob_writes") 554 .desc("The number of ROB writes"); 555} 556 557template <class Impl> 558typename Impl::DynInstPtr 559ROB<Impl>::findInst(ThreadID tid, InstSeqNum squash_inst) 560{ 561 for (InstIt it = instList[tid].begin(); it != instList[tid].end(); it++) { 562 if ((*it)->seqNum == squash_inst) { 563 return *it; 564 } 565 } 566 return NULL; 567} 568 569#endif//__CPU_O3_ROB_IMPL_HH__ 570