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     : robPolicy(params->smtROBPolicy),
  60       cpu(_cpu),
  61       numEntries(params->numROBEntries),
  62       squashWidth(params->squashWidth),
  63       numInstsInROB(0),
  64       numThreads(params->numThreads)
  65 {
  66     //Figure out rob policy
  67     if (robPolicy == SMTQueuePolicy::Dynamic) {
  68         //Set Max Entries to Total ROB Capacity
  69         for (ThreadID tid = 0; tid < numThreads; tid++) {
  70             maxEntries[tid] = numEntries;
  71         }
  72
  73     } else if (robPolicy == SMTQueuePolicy::Partitioned) {
  74         DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");
  75
  76         //@todo:make work if part_amt doesnt divide evenly.
  77         int part_amt = numEntries / numThreads;
  78
  79         //Divide ROB up evenly
  80         for (ThreadID tid = 0; tid < numThreads; tid++) {
  81             maxEntries[tid] = part_amt;
  82         }
  83
  84     } else if (robPolicy == SMTQueuePolicy::Threshold) {
  85         DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");
  86
  87         int threshold =  params->smtROBThreshold;;
  88
  89         //Divide up by threshold amount
  90         for (ThreadID tid = 0; tid < numThreads; tid++) {
  91             maxEntries[tid] = threshold;
  92         }
  93     }
  94
  95     for (ThreadID tid = numThreads; tid < Impl::MaxThreads; tid++) {
  96         maxEntries[tid] = 0;
  97     }
  98
  99     resetState();
 100 }
 101
 102 template <class Impl>
 103 void
 104 ROB<Impl>::resetState()
 105 {
 106     for (ThreadID tid = 0; tid  < Impl::MaxThreads; tid++) {
 107         threadEntries[tid] = 0;
 108         squashIt[tid] = instList[tid].end();
 109         squashedSeqNum[tid] = 0;
 110         doneSquashing[tid] = true;
 111     }
 112     numInstsInROB = 0;
 113
 114     // Initialize the "universal" ROB head & tail point to invalid
 115     // pointers
 116     head = instList[0].end();
 117     tail = instList[0].end();
 118 }
 119
 120 template <class Impl>
 121 std::string
 122 ROB<Impl>::name() const
 123 {
 124     return cpu->name() + ".rob";
 125 }
 126
 127 template <class Impl>
 128 void
 129 ROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr)
 130 {
 131     DPRINTF(ROB, "Setting active threads list pointer.\n");
 132     activeThreads = at_ptr;
 133 }
 134
 135 template <class Impl>
 136 void
 137 ROB<Impl>::drainSanityCheck() const
 138 {
 139     for (ThreadID tid = 0; tid  < numThreads; tid++)
 140         assert(instList[tid].empty());
 141     assert(isEmpty());
 142 }
 143
 144 template <class Impl>
 145 void
 146 ROB<Impl>::takeOverFrom()
 147 {
 148     resetState();
 149 }
 150
 151 template <class Impl>
 152 void
 153 ROB<Impl>::resetEntries()
 154 {
 155     if (robPolicy != SMTQueuePolicy::Dynamic || numThreads > 1) {
 156         auto active_threads = activeThreads->size();
 157
 158         list<ThreadID>::iterator threads = activeThreads->begin();
 159         list<ThreadID>::iterator end = activeThreads->end();
 160
 161         while (threads != end) {
 162             ThreadID tid = *threads++;
 163
 164             if (robPolicy == SMTQueuePolicy::Partitioned) {
 165                 maxEntries[tid] = numEntries / active_threads;
 166             } else if (robPolicy == SMTQueuePolicy::Threshold &&
 167                        active_threads == 1) {
 168                 maxEntries[tid] = numEntries;
 169             }
 170         }
 171     }
 172 }
 173
 174 template <class Impl>
 175 int
 176 ROB<Impl>::entryAmount(ThreadID num_threads)
 177 {
 178     if (robPolicy == SMTQueuePolicy::Partitioned) {
 179         return numEntries / num_threads;
 180     } else {
 181         return 0;
 182     }
 183 }
 184
 185 template <class Impl>
 186 int
 187 ROB<Impl>::countInsts()
 188 {
 189     int total = 0;
 190
 191     for (ThreadID tid = 0; tid < numThreads; tid++)
 192         total += countInsts(tid);
 193
 194     return total;
 195 }
 196
 197 template <class Impl>
 198 size_t
 199 ROB<Impl>::countInsts(ThreadID tid)
 200 {
 201     return instList[tid].size();
 202 }
 203
 204 template <class Impl>
 205 void
 206 ROB<Impl>::insertInst(const DynInstPtr &inst)
 207 {
 208     assert(inst);
 209
 210     robWrites++;
 211
 212     DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState());
 213
 214     assert(numInstsInROB != numEntries);
 215
 216     ThreadID tid = inst->threadNumber;
 217
 218     instList[tid].push_back(inst);
 219
 220     //Set Up head iterator if this is the 1st instruction in the ROB
 221     if (numInstsInROB == 0) {
 222         head = instList[tid].begin();
 223         assert((*head) == inst);
 224     }
 225
 226     //Must Decrement for iterator to actually be valid  since __.end()
 227     //actually points to 1 after the last inst
 228     tail = instList[tid].end();
 229     tail--;
 230
 231     inst->setInROB();
 232
 233     ++numInstsInROB;
 234     ++threadEntries[tid];
 235
 236     assert((*tail) == inst);
 237
 238     DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
 239 }
 240
 241 template <class Impl>
 242 void
 243 ROB<Impl>::retireHead(ThreadID tid)
 244 {
 245     robWrites++;
 246
 247     assert(numInstsInROB > 0);
 248
 249     // Get the head ROB instruction by copying it and remove it from the list
 250     InstIt head_it = instList[tid].begin();
 251
 252     DynInstPtr head_inst = std::move(*head_it);
 253     instList[tid].erase(head_it);
 254
 255     assert(head_inst->readyToCommit());
 256
 257     DPRINTF(ROB, "[tid:%i] Retiring head instruction, "
 258             "instruction PC %s, [sn:%llu]\n", tid, head_inst->pcState(),
 259             head_inst->seqNum);
 260
 261     --numInstsInROB;
 262     --threadEntries[tid];
 263
 264     head_inst->clearInROB();
 265     head_inst->setCommitted();
 266
 267     //Update "Global" Head of ROB
 268     updateHead();
 269
 270     // @todo: A special case is needed if the instruction being
 271     // retired is the only instruction in the ROB; otherwise the tail
 272     // iterator will become invalidated.
 273     cpu->removeFrontInst(head_inst);
 274 }
 275
 276 template <class Impl>
 277 bool
 278 ROB<Impl>::isHeadReady(ThreadID tid)
 279 {
 280     robReads++;
 281     if (threadEntries[tid] != 0) {
 282         return instList[tid].front()->readyToCommit();
 283     }
 284
 285     return false;
 286 }
 287
 288 template <class Impl>
 289 bool
 290 ROB<Impl>::canCommit()
 291 {
 292     //@todo: set ActiveThreads through ROB or CPU
 293     list<ThreadID>::iterator threads = activeThreads->begin();
 294     list<ThreadID>::iterator end = activeThreads->end();
 295
 296     while (threads != end) {
 297         ThreadID tid = *threads++;
 298
 299         if (isHeadReady(tid)) {
 300             return true;
 301         }
 302     }
 303
 304     return false;
 305 }
 306
 307 template <class Impl>
 308 unsigned
 309 ROB<Impl>::numFreeEntries()
 310 {
 311     return numEntries - numInstsInROB;
 312 }
 313
 314 template <class Impl>
 315 unsigned
 316 ROB<Impl>::numFreeEntries(ThreadID tid)
 317 {
 318     return maxEntries[tid] - threadEntries[tid];
 319 }
 320
 321 template <class Impl>
 322 void
 323 ROB<Impl>::doSquash(ThreadID tid)
 324 {
 325     robWrites++;
 326     DPRINTF(ROB, "[tid:%i] Squashing instructions until [sn:%llu].\n",
 327             tid, squashedSeqNum[tid]);
 328
 329     assert(squashIt[tid] != instList[tid].end());
 330
 331     if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) {
 332         DPRINTF(ROB, "[tid:%i] Done squashing instructions.\n",
 333                 tid);
 334
 335         squashIt[tid] = instList[tid].end();
 336
 337         doneSquashing[tid] = true;
 338         return;
 339     }
 340
 341     bool robTailUpdate = false;
 342
 343     for (int numSquashed = 0;
 344          numSquashed < squashWidth &&
 345          squashIt[tid] != instList[tid].end() &&
 346          (*squashIt[tid])->seqNum > squashedSeqNum[tid];
 347          ++numSquashed)
 348     {
 349         DPRINTF(ROB, "[tid:%i] Squashing instruction PC %s, seq num %i.\n",
 350                 (*squashIt[tid])->threadNumber,
 351                 (*squashIt[tid])->pcState(),
 352                 (*squashIt[tid])->seqNum);
 353
 354         // Mark the instruction as squashed, and ready to commit so that
 355         // it can drain out of the pipeline.
 356         (*squashIt[tid])->setSquashed();
 357
 358         (*squashIt[tid])->setCanCommit();
 359
 360
 361         if (squashIt[tid] == instList[tid].begin()) {
 362             DPRINTF(ROB, "Reached head of instruction list while "
 363                     "squashing.\n");
 364
 365             squashIt[tid] = instList[tid].end();
 366
 367             doneSquashing[tid] = true;
 368
 369             return;
 370         }
 371
 372         InstIt tail_thread = instList[tid].end();
 373         tail_thread--;
 374
 375         if ((*squashIt[tid]) == (*tail_thread))
 376             robTailUpdate = true;
 377
 378         squashIt[tid]--;
 379     }
 380
 381
 382     // Check if ROB is done squashing.
 383     if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) {
 384         DPRINTF(ROB, "[tid:%i] Done squashing instructions.\n",
 385                 tid);
 386
 387         squashIt[tid] = instList[tid].end();
 388
 389         doneSquashing[tid] = true;
 390     }
 391
 392     if (robTailUpdate) {
 393         updateTail();
 394     }
 395 }
 396
 397
 398 template <class Impl>
 399 void
 400 ROB<Impl>::updateHead()
 401 {
 402     InstSeqNum lowest_num = 0;
 403     bool first_valid = true;
 404
 405     // @todo: set ActiveThreads through ROB or CPU
 406     list<ThreadID>::iterator threads = activeThreads->begin();
 407     list<ThreadID>::iterator end = activeThreads->end();
 408
 409     while (threads != end) {
 410         ThreadID tid = *threads++;
 411
 412         if (instList[tid].empty())
 413             continue;
 414
 415         if (first_valid) {
 416             head = instList[tid].begin();
 417             lowest_num = (*head)->seqNum;
 418             first_valid = false;
 419             continue;
 420         }
 421
 422         InstIt head_thread = instList[tid].begin();
 423
 424         DynInstPtr head_inst = (*head_thread);
 425
 426         assert(head_inst != 0);
 427
 428         if (head_inst->seqNum < lowest_num) {
 429             head = head_thread;
 430             lowest_num = head_inst->seqNum;
 431         }
 432     }
 433
 434     if (first_valid) {
 435         head = instList[0].end();
 436     }
 437
 438 }
 439
 440 template <class Impl>
 441 void
 442 ROB<Impl>::updateTail()
 443 {
 444     tail = instList[0].end();
 445     bool first_valid = true;
 446
 447     list<ThreadID>::iterator threads = activeThreads->begin();
 448     list<ThreadID>::iterator end = activeThreads->end();
 449
 450     while (threads != end) {
 451         ThreadID tid = *threads++;
 452
 453         if (instList[tid].empty()) {
 454             continue;
 455         }
 456
 457         // If this is the first valid then assign w/out
 458         // comparison
 459         if (first_valid) {
 460             tail = instList[tid].end();
 461             tail--;
 462             first_valid = false;
 463             continue;
 464         }
 465
 466         // Assign new tail if this thread's tail is younger
 467         // than our current "tail high"
 468         InstIt tail_thread = instList[tid].end();
 469         tail_thread--;
 470
 471         if ((*tail_thread)->seqNum > (*tail)->seqNum) {
 472             tail = tail_thread;
 473         }
 474     }
 475 }
 476
 477
 478 template <class Impl>
 479 void
 480 ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid)
 481 {
 482     if (isEmpty(tid)) {
 483         DPRINTF(ROB, "Does not need to squash due to being empty "
 484                 "[sn:%llu]\n",
 485                 squash_num);
 486
 487         return;
 488     }
 489
 490     DPRINTF(ROB, "Starting to squash within the ROB.\n");
 491
 492     robStatus[tid] = ROBSquashing;
 493
 494     doneSquashing[tid] = false;
 495
 496     squashedSeqNum[tid] = squash_num;
 497
 498     if (!instList[tid].empty()) {
 499         InstIt tail_thread = instList[tid].end();
 500         tail_thread--;
 501
 502         squashIt[tid] = tail_thread;
 503
 504         doSquash(tid);
 505     }
 506 }
 507
 508 template <class Impl>
 509 const typename Impl::DynInstPtr&
 510 ROB<Impl>::readHeadInst(ThreadID tid)
 511 {
 512     if (threadEntries[tid] != 0) {
 513         InstIt head_thread = instList[tid].begin();
 514
 515         assert((*head_thread)->isInROB());
 516
 517         return *head_thread;
 518     } else {
 519         return dummyInst;
 520     }
 521 }
 522
 523 template <class Impl>
 524 typename Impl::DynInstPtr
 525 ROB<Impl>::readTailInst(ThreadID tid)
 526 {
 527     InstIt tail_thread = instList[tid].end();
 528     tail_thread--;
 529
 530     return *tail_thread;
 531 }
 532
 533 template <class Impl>
 534 void
 535 ROB<Impl>::regStats()
 536 {
 537     using namespace Stats;
 538     robReads
 539         .name(name() + ".rob_reads")
 540         .desc("The number of ROB reads");
 541
 542     robWrites
 543         .name(name() + ".rob_writes")
 544         .desc("The number of ROB writes");
 545 }
 546
 547 template <class Impl>
 548 typename Impl::DynInstPtr
 549 ROB<Impl>::findInst(ThreadID tid, InstSeqNum squash_inst)
 550 {
 551     for (InstIt it = instList[tid].begin(); it != instList[tid].end(); it++) {
 552         if ((*it)->seqNum == squash_inst) {
 553             return *it;
 554         }
 555     }
 556     return NULL;
 557 }
 558
 559 #endif//__CPU_O3_ROB_IMPL_HH__