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