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