rob_impl.hh revision 7720
1/* 2 * Copyright (c) 2004-2006 The Regents of The University of Michigan 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Kevin Lim 29 * Korey Sewell 30 */ 31 32#include <list> 33 34#include "config/full_system.hh" 35#include "cpu/o3/rob.hh" 36 37using namespace std; 38 39template <class Impl> 40ROB<Impl>::ROB(O3CPU *_cpu, unsigned _numEntries, unsigned _squashWidth, 41 std::string _smtROBPolicy, unsigned _smtROBThreshold, 42 ThreadID _numThreads) 43 : cpu(_cpu), 44 numEntries(_numEntries), 45 squashWidth(_squashWidth), 46 numInstsInROB(0), 47 numThreads(_numThreads) 48{ 49 for (ThreadID tid = 0; tid < numThreads; tid++) { 50 squashedSeqNum[tid] = 0; 51 doneSquashing[tid] = true; 52 threadEntries[tid] = 0; 53 } 54 55 std::string policy = _smtROBPolicy; 56 57 //Convert string to lowercase 58 std::transform(policy.begin(), policy.end(), policy.begin(), 59 (int(*)(int)) tolower); 60 61 //Figure out rob policy 62 if (policy == "dynamic") { 63 robPolicy = Dynamic; 64 65 //Set Max Entries to Total ROB Capacity 66 for (ThreadID tid = 0; tid < numThreads; tid++) { 67 maxEntries[tid] = numEntries; 68 } 69 70 } else if (policy == "partitioned") { 71 robPolicy = Partitioned; 72 DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n"); 73 74 //@todo:make work if part_amt doesnt divide evenly. 75 int part_amt = numEntries / numThreads; 76 77 //Divide ROB up evenly 78 for (ThreadID tid = 0; tid < numThreads; tid++) { 79 maxEntries[tid] = part_amt; 80 } 81 82 } else if (policy == "threshold") { 83 robPolicy = Threshold; 84 DPRINTF(Fetch, "ROB sharing policy set to Threshold\n"); 85 86 int threshold = _smtROBThreshold;; 87 88 //Divide up by threshold amount 89 for (ThreadID tid = 0; tid < numThreads; tid++) { 90 maxEntries[tid] = threshold; 91 } 92 } else { 93 assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic," 94 "Partitioned, Threshold}"); 95 } 96 97 // Set the per-thread iterators to the end of the instruction list. 98 for (ThreadID tid = 0; tid < numThreads; tid++) { 99 squashIt[tid] = instList[tid].end(); 100 } 101 102 // Initialize the "universal" ROB head & tail point to invalid 103 // pointers 104 head = instList[0].end(); 105 tail = instList[0].end(); 106} 107 108template <class Impl> 109std::string 110ROB<Impl>::name() const 111{ 112 return cpu->name() + ".rob"; 113} 114 115template <class Impl> 116void 117ROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr) 118{ 119 DPRINTF(ROB, "Setting active threads list pointer.\n"); 120 activeThreads = at_ptr; 121} 122 123template <class Impl> 124void 125ROB<Impl>::switchOut() 126{ 127 for (ThreadID tid = 0; tid < numThreads; tid++) { 128 instList[tid].clear(); 129 } 130} 131 132template <class Impl> 133void 134ROB<Impl>::takeOverFrom() 135{ 136 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 DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState()); 208 209 assert(numInstsInROB != numEntries); 210 211 ThreadID tid = inst->threadNumber; 212 213 instList[tid].push_back(inst); 214 215 //Set Up head iterator if this is the 1st instruction in the ROB 216 if (numInstsInROB == 0) { 217 head = instList[tid].begin(); 218 assert((*head) == inst); 219 } 220 221 //Must Decrement for iterator to actually be valid since __.end() 222 //actually points to 1 after the last inst 223 tail = instList[tid].end(); 224 tail--; 225 226 inst->setInROB(); 227 228 ++numInstsInROB; 229 ++threadEntries[tid]; 230 231 assert((*tail) == inst); 232 233 DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]); 234} 235 236template <class Impl> 237void 238ROB<Impl>::retireHead(ThreadID tid) 239{ 240 assert(numInstsInROB > 0); 241 242 // Get the head ROB instruction. 243 InstIt head_it = instList[tid].begin(); 244 245 DynInstPtr head_inst = (*head_it); 246 247 assert(head_inst->readyToCommit()); 248 249 DPRINTF(ROB, "[tid:%u]: Retiring head instruction, " 250 "instruction PC %s, [sn:%lli]\n", tid, head_inst->pcState(), 251 head_inst->seqNum); 252 253 --numInstsInROB; 254 --threadEntries[tid]; 255 256 head_inst->clearInROB(); 257 head_inst->setCommitted(); 258 259 instList[tid].erase(head_it); 260 261 //Update "Global" Head of ROB 262 updateHead(); 263 264 // @todo: A special case is needed if the instruction being 265 // retired is the only instruction in the ROB; otherwise the tail 266 // iterator will become invalidated. 267 cpu->removeFrontInst(head_inst); 268} 269 270template <class Impl> 271bool 272ROB<Impl>::isHeadReady(ThreadID tid) 273{ 274 if (threadEntries[tid] != 0) { 275 return instList[tid].front()->readyToCommit(); 276 } 277 278 return false; 279} 280 281template <class Impl> 282bool 283ROB<Impl>::canCommit() 284{ 285 //@todo: set ActiveThreads through ROB or CPU 286 list<ThreadID>::iterator threads = activeThreads->begin(); 287 list<ThreadID>::iterator end = activeThreads->end(); 288 289 while (threads != end) { 290 ThreadID tid = *threads++; 291 292 if (isHeadReady(tid)) { 293 return true; 294 } 295 } 296 297 return false; 298} 299 300template <class Impl> 301unsigned 302ROB<Impl>::numFreeEntries() 303{ 304 return numEntries - numInstsInROB; 305} 306 307template <class Impl> 308unsigned 309ROB<Impl>::numFreeEntries(ThreadID tid) 310{ 311 return maxEntries[tid] - threadEntries[tid]; 312} 313 314template <class Impl> 315void 316ROB<Impl>::doSquash(ThreadID tid) 317{ 318 DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n", 319 tid, squashedSeqNum[tid]); 320 321 assert(squashIt[tid] != instList[tid].end()); 322 323 if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) { 324 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n", 325 tid); 326 327 squashIt[tid] = instList[tid].end(); 328 329 doneSquashing[tid] = true; 330 return; 331 } 332 333 bool robTailUpdate = false; 334 335 for (int numSquashed = 0; 336 numSquashed < squashWidth && 337 squashIt[tid] != instList[tid].end() && 338 (*squashIt[tid])->seqNum > squashedSeqNum[tid]; 339 ++numSquashed) 340 { 341 DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %s, seq num %i.\n", 342 (*squashIt[tid])->threadNumber, 343 (*squashIt[tid])->pcState(), 344 (*squashIt[tid])->seqNum); 345 346 // Mark the instruction as squashed, and ready to commit so that 347 // it can drain out of the pipeline. 348 (*squashIt[tid])->setSquashed(); 349 350 (*squashIt[tid])->setCanCommit(); 351 352 353 if (squashIt[tid] == instList[tid].begin()) { 354 DPRINTF(ROB, "Reached head of instruction list while " 355 "squashing.\n"); 356 357 squashIt[tid] = instList[tid].end(); 358 359 doneSquashing[tid] = true; 360 361 return; 362 } 363 364 InstIt tail_thread = instList[tid].end(); 365 tail_thread--; 366 367 if ((*squashIt[tid]) == (*tail_thread)) 368 robTailUpdate = true; 369 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