src/cpu/o3/rob_impl.hh

   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
  55 using namespace std;
  56
  57 template <class Impl>
  58 ROB<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
 113 template <class Impl>
 114 void
 115 ROB<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
 131 template <class Impl>
 132 std::string
 133 ROB<Impl>::name() const
 134 {
 135     return cpu->name() + ".rob";
 136 }
 137
 138 template <class Impl>
 139 void
 140 ROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr)
 141 {
 142     DPRINTF(ROB, "Setting active threads list pointer.\n");
 143     activeThreads = at_ptr;
 144 }
 145
 146 template <class Impl>
 147 void
 148 ROB<Impl>::drainSanityCheck() const
 149 {
 150     for (ThreadID tid = 0; tid  < numThreads; tid++)
 151         assert(instList[tid].empty());
 152     assert(isEmpty());
 153 }
 154
 155 template <class Impl>
 156 void
 157 ROB<Impl>::takeOverFrom()
 158 {
 159     resetState();
 160 }
 161
 162 template <class Impl>
 163 void
 164 ROB<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
 184 template <class Impl>
 185 int
 186 ROB<Impl>::entryAmount(ThreadID num_threads)
 187 {
 188     if (robPolicy == Partitioned) {
 189         return numEntries / num_threads;
 190     } else {
 191         return 0;
 192     }
 193 }
 194
 195 template <class Impl>
 196 int
 197 ROB<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
 207 template <class Impl>
 208 int
 209 ROB<Impl>::countInsts(ThreadID tid)
 210 {
 211     return instList[tid].size();
 212 }
 213
 214 template <class Impl>
 215 void
 216 ROB<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
 251 template <class Impl>
 252 void
 253 ROB<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
 286 template <class Impl>
 287 bool
 288 ROB<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
 298 template <class Impl>
 299 bool
 300 ROB<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
 317 template <class Impl>
 318 unsigned
 319 ROB<Impl>::numFreeEntries()
 320 {
 321     return numEntries - numInstsInROB;
 322 }
 323
 324 template <class Impl>
 325 unsigned
 326 ROB<Impl>::numFreeEntries(ThreadID tid)
 327 {
 328     return maxEntries[tid] - threadEntries[tid];
 329 }
 330
 331 template <class Impl>
 332 void
 333 ROB<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
 408 template <class Impl>
 409 void
 410 ROB<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
 450 template <class Impl>
 451 void
 452 ROB<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
 488 template <class Impl>
 489 void
 490 ROB<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
 518 template <class Impl>
 519 const typename Impl::DynInstPtr&
 520 ROB<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
 533 template <class Impl>
 534 typename Impl::DynInstPtr
 535 ROB<Impl>::readTailInst(ThreadID tid)
 536 {
 537     InstIt tail_thread = instList[tid].end();
 538     tail_thread--;
 539
 540     return *tail_thread;
 541 }
 542
 543 template <class Impl>
 544 void
 545 ROB<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
 557 template <class Impl>
 558 typename Impl::DynInstPtr
 559 ROB<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__