src/cpu/o3/rob_impl.hh

   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
  37 using namespace std;
  38
  39 template <class Impl>
  40 ROB<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
 108 template <class Impl>
 109 std::string
 110 ROB<Impl>::name() const
 111 {
 112     return cpu->name() + ".rob";
 113 }
 114
 115 template <class Impl>
 116 void
 117 ROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr)
 118 {
 119     DPRINTF(ROB, "Setting active threads list pointer.\n");
 120     activeThreads = at_ptr;
 121 }
 122
 123 template <class Impl>
 124 void
 125 ROB<Impl>::switchOut()
 126 {
 127     for (ThreadID tid = 0; tid < numThreads; tid++) {
 128         instList[tid].clear();
 129     }
 130 }
 131
 132 template <class Impl>
 133 void
 134 ROB<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
 149 template <class Impl>
 150 void
 151 ROB<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
 171 template <class Impl>
 172 int
 173 ROB<Impl>::entryAmount(ThreadID num_threads)
 174 {
 175     if (robPolicy == Partitioned) {
 176         return numEntries / num_threads;
 177     } else {
 178         return 0;
 179     }
 180 }
 181
 182 template <class Impl>
 183 int
 184 ROB<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
 194 template <class Impl>
 195 int
 196 ROB<Impl>::countInsts(ThreadID tid)
 197 {
 198     return instList[tid].size();
 199 }
 200
 201 template <class Impl>
 202 void
 203 ROB<Impl>::insertInst(DynInstPtr &inst)
 204 {
 205     assert(inst);
 206
 207     DPRINTF(ROB, "Adding inst PC %#x to the ROB.\n", inst->readPC());
 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
 236 template <class Impl>
 237 void
 238 ROB<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 %#x,[sn:%lli]\n", tid, head_inst->readPC(),
 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
 270 template <class Impl>
 271 bool
 272 ROB<Impl>::isHeadReady(ThreadID tid)
 273 {
 274     if (threadEntries[tid] != 0) {
 275         return instList[tid].front()->readyToCommit();
 276     }
 277
 278     return false;
 279 }
 280
 281 template <class Impl>
 282 bool
 283 ROB<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
 300 template <class Impl>
 301 unsigned
 302 ROB<Impl>::numFreeEntries()
 303 {
 304     return numEntries - numInstsInROB;
 305 }
 306
 307 template <class Impl>
 308 unsigned
 309 ROB<Impl>::numFreeEntries(ThreadID tid)
 310 {
 311     return maxEntries[tid] - threadEntries[tid];
 312 }
 313
 314 template <class Impl>
 315 void
 316 ROB<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 %#x, seq num %i.\n",
 342                 (*squashIt[tid])->threadNumber,
 343                 (*squashIt[tid])->readPC(),
 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
 390 template <class Impl>
 391 void
 392 ROB<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
 433 template <class Impl>
 434 void
 435 ROB<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
 471 template <class Impl>
 472 void
 473 ROB<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
 501 template <class Impl>
 502 typename Impl::DynInstPtr
 503 ROB<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
 516 template <class Impl>
 517 typename Impl::DynInstPtr
 518 ROB<Impl>::readTailInst(ThreadID tid)
 519 {
 520     InstIt tail_thread = instList[tid].end();
 521     tail_thread--;
 522
 523     return *tail_thread;
 524 }
 525