src/cpu/o3/mem_dep_unit_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  */
  30
  31 #include <map>
  32
  33 #include "cpu/o3/inst_queue.hh"
  34 #include "cpu/o3/mem_dep_unit.hh"
  35
  36 template <class MemDepPred, class Impl>
  37 MemDepUnit<MemDepPred, Impl>::MemDepUnit()
  38     : loadBarrier(false), loadBarrierSN(0), storeBarrier(false),
  39       storeBarrierSN(0), iqPtr(NULL)
  40 {
  41 }
  42
  43 template <class MemDepPred, class Impl>
  44 MemDepUnit<MemDepPred, Impl>::MemDepUnit(Params *params)
  45     : depPred(params->SSITSize, params->LFSTSize), loadBarrier(false),
  46       loadBarrierSN(0), storeBarrier(false), storeBarrierSN(0), iqPtr(NULL)
  47 {
  48     DPRINTF(MemDepUnit, "Creating MemDepUnit object.\n");
  49 }
  50
  51 template <class MemDepPred, class Impl>
  52 MemDepUnit<MemDepPred, Impl>::~MemDepUnit()
  53 {
  54     for (int tid=0; tid < Impl::MaxThreads; tid++) {
  55
  56         ListIt inst_list_it = instList[tid].begin();
  57
  58         MemDepHashIt hash_it;
  59
  60         while (!instList[tid].empty()) {
  61             hash_it = memDepHash.find((*inst_list_it)->seqNum);
  62
  63             assert(hash_it != memDepHash.end());
  64
  65             memDepHash.erase(hash_it);
  66
  67             instList[tid].erase(inst_list_it++);
  68         }
  69     }
  70
  71 #ifdef DEBUG
  72     assert(MemDepEntry::memdep_count == 0);
  73 #endif
  74 }
  75
  76 template <class MemDepPred, class Impl>
  77 std::string
  78 MemDepUnit<MemDepPred, Impl>::name() const
  79 {
  80     return "memdepunit";
  81 }
  82
  83 template <class MemDepPred, class Impl>
  84 void
  85 MemDepUnit<MemDepPred, Impl>::init(Params *params, int tid)
  86 {
  87     DPRINTF(MemDepUnit, "Creating MemDepUnit %i object.\n",tid);
  88
  89     id = tid;
  90
  91     depPred.init(params->SSITSize, params->LFSTSize);
  92 }
  93
  94 template <class MemDepPred, class Impl>
  95 void
  96 MemDepUnit<MemDepPred, Impl>::regStats()
  97 {
  98     insertedLoads
  99         .name(name() + ".memDep.insertedLoads")
 100         .desc("Number of loads inserted to the mem dependence unit.");
 101
 102     insertedStores
 103         .name(name() + ".memDep.insertedStores")
 104         .desc("Number of stores inserted to the mem dependence unit.");
 105
 106     conflictingLoads
 107         .name(name() + ".memDep.conflictingLoads")
 108         .desc("Number of conflicting loads.");
 109
 110     conflictingStores
 111         .name(name() + ".memDep.conflictingStores")
 112         .desc("Number of conflicting stores.");
 113 }
 114
 115 template <class MemDepPred, class Impl>
 116 void
 117 MemDepUnit<MemDepPred, Impl>::switchOut()
 118 {
 119     assert(instList[0].empty());
 120     assert(instsToReplay.empty());
 121     assert(memDepHash.empty());
 122     // Clear any state.
 123     for (int i = 0; i < Impl::MaxThreads; ++i) {
 124         instList[i].clear();
 125     }
 126     instsToReplay.clear();
 127     memDepHash.clear();
 128 }
 129
 130 template <class MemDepPred, class Impl>
 131 void
 132 MemDepUnit<MemDepPred, Impl>::takeOverFrom()
 133 {
 134     // Be sure to reset all state.
 135     loadBarrier = storeBarrier = false;
 136     loadBarrierSN = storeBarrierSN = 0;
 137     depPred.clear();
 138 }
 139
 140 template <class MemDepPred, class Impl>
 141 void
 142 MemDepUnit<MemDepPred, Impl>::setIQ(InstructionQueue<Impl> *iq_ptr)
 143 {
 144     iqPtr = iq_ptr;
 145 }
 146
 147 template <class MemDepPred, class Impl>
 148 void
 149 MemDepUnit<MemDepPred, Impl>::insert(DynInstPtr &inst)
 150 {
 151     unsigned tid = inst->threadNumber;
 152
 153     MemDepEntryPtr inst_entry = new MemDepEntry(inst);
 154
 155     // Add the MemDepEntry to the hash.
 156     memDepHash.insert(
 157         std::pair<InstSeqNum, MemDepEntryPtr>(inst->seqNum, inst_entry));
 158 #ifdef DEBUG
 159     MemDepEntry::memdep_insert++;
 160 #endif
 161
 162     instList[tid].push_back(inst);
 163
 164     inst_entry->listIt = --(instList[tid].end());
 165
 166     // Check any barriers and the dependence predictor for any
 167     // producing memrefs/stores.
 168     InstSeqNum producing_store;
 169     if (inst->isLoad() && loadBarrier) {
 170         DPRINTF(MemDepUnit, "Load barrier [sn:%lli] in flight\n",
 171                 loadBarrierSN);
 172         producing_store = loadBarrierSN;
 173     } else if (inst->isStore() && storeBarrier) {
 174         DPRINTF(MemDepUnit, "Store barrier [sn:%lli] in flight\n",
 175                 storeBarrierSN);
 176         producing_store = storeBarrierSN;
 177     } else {
 178         producing_store = depPred.checkInst(inst->readPC());
 179     }
 180
 181     MemDepEntryPtr store_entry = NULL;
 182
 183     // If there is a producing store, try to find the entry.
 184     if (producing_store != 0) {
 185         DPRINTF(MemDepUnit, "Searching for producer\n");
 186         MemDepHashIt hash_it = memDepHash.find(producing_store);
 187
 188         if (hash_it != memDepHash.end()) {
 189             store_entry = (*hash_it).second;
 190             DPRINTF(MemDepUnit, "Proucer found\n");
 191         }
 192     }
 193
 194     // If no store entry, then instruction can issue as soon as the registers
 195     // are ready.
 196     if (!store_entry) {
 197         DPRINTF(MemDepUnit, "No dependency for inst PC "
 198                 "%#x [sn:%lli].\n", inst->readPC(), inst->seqNum);
 199
 200         inst_entry->memDepReady = true;
 201
 202         if (inst->readyToIssue()) {
 203             inst_entry->regsReady = true;
 204
 205             moveToReady(inst_entry);
 206         }
 207     } else {
 208         // Otherwise make the instruction dependent on the store/barrier.
 209         DPRINTF(MemDepUnit, "Adding to dependency list; "
 210                 "inst PC %#x is dependent on [sn:%lli].\n",
 211                 inst->readPC(), producing_store);
 212
 213         if (inst->readyToIssue()) {
 214             inst_entry->regsReady = true;
 215         }
 216
 217         // Clear the bit saying this instruction can issue.
 218         inst->clearCanIssue();
 219
 220         // Add this instruction to the list of dependents.
 221         store_entry->dependInsts.push_back(inst_entry);
 222
 223         if (inst->isLoad()) {
 224             ++conflictingLoads;
 225         } else {
 226             ++conflictingStores;
 227         }
 228     }
 229
 230     if (inst->isStore()) {
 231         DPRINTF(MemDepUnit, "Inserting store PC %#x [sn:%lli].\n",
 232                 inst->readPC(), inst->seqNum);
 233
 234         depPred.insertStore(inst->readPC(), inst->seqNum, inst->threadNumber);
 235
 236         ++insertedStores;
 237     } else if (inst->isLoad()) {
 238         ++insertedLoads;
 239     } else {
 240         panic("Unknown type! (most likely a barrier).");
 241     }
 242 }
 243
 244 template <class MemDepPred, class Impl>
 245 void
 246 MemDepUnit<MemDepPred, Impl>::insertNonSpec(DynInstPtr &inst)
 247 {
 248     unsigned tid = inst->threadNumber;
 249
 250     MemDepEntryPtr inst_entry = new MemDepEntry(inst);
 251
 252     // Insert the MemDepEntry into the hash.
 253     memDepHash.insert(
 254         std::pair<InstSeqNum, MemDepEntryPtr>(inst->seqNum, inst_entry));
 255 #ifdef DEBUG
 256     MemDepEntry::memdep_insert++;
 257 #endif
 258
 259     // Add the instruction to the list.
 260     instList[tid].push_back(inst);
 261
 262     inst_entry->listIt = --(instList[tid].end());
 263
 264     // Might want to turn this part into an inline function or something.
 265     // It's shared between both insert functions.
 266     if (inst->isStore()) {
 267         DPRINTF(MemDepUnit, "Inserting store PC %#x [sn:%lli].\n",
 268                 inst->readPC(), inst->seqNum);
 269
 270         depPred.insertStore(inst->readPC(), inst->seqNum, inst->threadNumber);
 271
 272         ++insertedStores;
 273     } else if (inst->isLoad()) {
 274         ++insertedLoads;
 275     } else {
 276         panic("Unknown type! (most likely a barrier).");
 277     }
 278 }
 279
 280 template <class MemDepPred, class Impl>
 281 void
 282 MemDepUnit<MemDepPred, Impl>::insertBarrier(DynInstPtr &barr_inst)
 283 {
 284     InstSeqNum barr_sn = barr_inst->seqNum;
 285     // Memory barriers block loads and stores, write barriers only stores.
 286     if (barr_inst->isMemBarrier()) {
 287         loadBarrier = true;
 288         loadBarrierSN = barr_sn;
 289         storeBarrier = true;
 290         storeBarrierSN = barr_sn;
 291         DPRINTF(MemDepUnit, "Inserted a memory barrier\n");
 292     } else if (barr_inst->isWriteBarrier()) {
 293         storeBarrier = true;
 294         storeBarrierSN = barr_sn;
 295         DPRINTF(MemDepUnit, "Inserted a write barrier\n");
 296     }
 297
 298     unsigned tid = barr_inst->threadNumber;
 299
 300     MemDepEntryPtr inst_entry = new MemDepEntry(barr_inst);
 301
 302     // Add the MemDepEntry to the hash.
 303     memDepHash.insert(
 304         std::pair<InstSeqNum, MemDepEntryPtr>(barr_sn, inst_entry));
 305 #ifdef DEBUG
 306     MemDepEntry::memdep_insert++;
 307 #endif
 308
 309     // Add the instruction to the instruction list.
 310     instList[tid].push_back(barr_inst);
 311
 312     inst_entry->listIt = --(instList[tid].end());
 313 }
 314
 315 template <class MemDepPred, class Impl>
 316 void
 317 MemDepUnit<MemDepPred, Impl>::regsReady(DynInstPtr &inst)
 318 {
 319     DPRINTF(MemDepUnit, "Marking registers as ready for "
 320             "instruction PC %#x [sn:%lli].\n",
 321             inst->readPC(), inst->seqNum);
 322
 323     MemDepEntryPtr inst_entry = findInHash(inst);
 324
 325     inst_entry->regsReady = true;
 326
 327     if (inst_entry->memDepReady) {
 328         DPRINTF(MemDepUnit, "Instruction has its memory "
 329                 "dependencies resolved, adding it to the ready list.\n");
 330
 331         moveToReady(inst_entry);
 332     } else {
 333         DPRINTF(MemDepUnit, "Instruction still waiting on "
 334                 "memory dependency.\n");
 335     }
 336 }
 337
 338 template <class MemDepPred, class Impl>
 339 void
 340 MemDepUnit<MemDepPred, Impl>::nonSpecInstReady(DynInstPtr &inst)
 341 {
 342     DPRINTF(MemDepUnit, "Marking non speculative "
 343             "instruction PC %#x as ready [sn:%lli].\n",
 344             inst->readPC(), inst->seqNum);
 345
 346     MemDepEntryPtr inst_entry = findInHash(inst);
 347
 348     moveToReady(inst_entry);
 349 }
 350
 351 template <class MemDepPred, class Impl>
 352 void
 353 MemDepUnit<MemDepPred, Impl>::reschedule(DynInstPtr &inst)
 354 {
 355     instsToReplay.push_back(inst);
 356 }
 357
 358 template <class MemDepPred, class Impl>
 359 void
 360 MemDepUnit<MemDepPred, Impl>::replay(DynInstPtr &inst)
 361 {
 362     DynInstPtr temp_inst;
 363
 364     // For now this replay function replays all waiting memory ops.
 365     while (!instsToReplay.empty()) {
 366         temp_inst = instsToReplay.front();
 367
 368         MemDepEntryPtr inst_entry = findInHash(temp_inst);
 369
 370         DPRINTF(MemDepUnit, "Replaying mem instruction PC %#x "
 371                 "[sn:%lli].\n",
 372                 temp_inst->readPC(), temp_inst->seqNum);
 373
 374         moveToReady(inst_entry);
 375
 376         instsToReplay.pop_front();
 377     }
 378 }
 379
 380 template <class MemDepPred, class Impl>
 381 void
 382 MemDepUnit<MemDepPred, Impl>::completed(DynInstPtr &inst)
 383 {
 384     DPRINTF(MemDepUnit, "Completed mem instruction PC %#x "
 385             "[sn:%lli].\n",
 386             inst->readPC(), inst->seqNum);
 387
 388     unsigned tid = inst->threadNumber;
 389
 390     // Remove the instruction from the hash and the list.
 391     MemDepHashIt hash_it = memDepHash.find(inst->seqNum);
 392
 393     assert(hash_it != memDepHash.end());
 394
 395     instList[tid].erase((*hash_it).second->listIt);
 396
 397     (*hash_it).second = NULL;
 398
 399     memDepHash.erase(hash_it);
 400 #ifdef DEBUG
 401     MemDepEntry::memdep_erase++;
 402 #endif
 403 }
 404
 405 template <class MemDepPred, class Impl>
 406 void
 407 MemDepUnit<MemDepPred, Impl>::completeBarrier(DynInstPtr &inst)
 408 {
 409     wakeDependents(inst);
 410     completed(inst);
 411
 412     InstSeqNum barr_sn = inst->seqNum;
 413
 414     if (inst->isMemBarrier()) {
 415         assert(loadBarrier && storeBarrier);
 416         if (loadBarrierSN == barr_sn)
 417             loadBarrier = false;
 418         if (storeBarrierSN == barr_sn)
 419             storeBarrier = false;
 420     } else if (inst->isWriteBarrier()) {
 421         assert(storeBarrier);
 422         if (storeBarrierSN == barr_sn)
 423             storeBarrier = false;
 424     }
 425 }
 426
 427 template <class MemDepPred, class Impl>
 428 void
 429 MemDepUnit<MemDepPred, Impl>::wakeDependents(DynInstPtr &inst)
 430 {
 431     // Only stores and barriers have dependents.
 432     if (!inst->isStore() && !inst->isMemBarrier() && !inst->isWriteBarrier()) {
 433         return;
 434     }
 435
 436     MemDepEntryPtr inst_entry = findInHash(inst);
 437
 438     for (int i = 0; i < inst_entry->dependInsts.size(); ++i ) {
 439         MemDepEntryPtr woken_inst = inst_entry->dependInsts[i];
 440
 441         if (!woken_inst->inst) {
 442             // Potentially removed mem dep entries could be on this list
 443             continue;
 444         }
 445
 446         DPRINTF(MemDepUnit, "Waking up a dependent inst, "
 447                 "[sn:%lli].\n",
 448                 woken_inst->inst->seqNum);
 449
 450         if (woken_inst->regsReady && !woken_inst->squashed) {
 451             moveToReady(woken_inst);
 452         } else {
 453             woken_inst->memDepReady = true;
 454         }
 455     }
 456
 457     inst_entry->dependInsts.clear();
 458 }
 459
 460 template <class MemDepPred, class Impl>
 461 void
 462 MemDepUnit<MemDepPred, Impl>::squash(const InstSeqNum &squashed_num,
 463                                      unsigned tid)
 464 {
 465     if (!instsToReplay.empty()) {
 466         ListIt replay_it = instsToReplay.begin();
 467         while (replay_it != instsToReplay.end()) {
 468             if ((*replay_it)->threadNumber == tid &&
 469                 (*replay_it)->seqNum > squashed_num) {
 470                 instsToReplay.erase(replay_it++);
 471             } else {
 472                 ++replay_it;
 473             }
 474         }
 475     }
 476
 477     ListIt squash_it = instList[tid].end();
 478     --squash_it;
 479
 480     MemDepHashIt hash_it;
 481
 482     while (!instList[tid].empty() &&
 483            (*squash_it)->seqNum > squashed_num) {
 484
 485         DPRINTF(MemDepUnit, "Squashing inst [sn:%lli]\n",
 486                 (*squash_it)->seqNum);
 487
 488         hash_it = memDepHash.find((*squash_it)->seqNum);
 489
 490         assert(hash_it != memDepHash.end());
 491
 492         (*hash_it).second->squashed = true;
 493
 494         (*hash_it).second = NULL;
 495
 496         memDepHash.erase(hash_it);
 497 #ifdef DEBUG
 498         MemDepEntry::memdep_erase++;
 499 #endif
 500
 501         instList[tid].erase(squash_it--);
 502     }
 503
 504     // Tell the dependency predictor to squash as well.
 505     depPred.squash(squashed_num, tid);
 506 }
 507
 508 template <class MemDepPred, class Impl>
 509 void
 510 MemDepUnit<MemDepPred, Impl>::violation(DynInstPtr &store_inst,
 511                                         DynInstPtr &violating_load)
 512 {
 513     DPRINTF(MemDepUnit, "Passing violating PCs to store sets,"
 514             " load: %#x, store: %#x\n", violating_load->readPC(),
 515             store_inst->readPC());
 516     // Tell the memory dependence unit of the violation.
 517     depPred.violation(violating_load->readPC(), store_inst->readPC());
 518 }
 519
 520 template <class MemDepPred, class Impl>
 521 void
 522 MemDepUnit<MemDepPred, Impl>::issue(DynInstPtr &inst)
 523 {
 524     DPRINTF(MemDepUnit, "Issuing instruction PC %#x [sn:%lli].\n",
 525             inst->readPC(), inst->seqNum);
 526
 527     depPred.issued(inst->readPC(), inst->seqNum, inst->isStore());
 528 }
 529
 530 template <class MemDepPred, class Impl>
 531 inline typename MemDepUnit<MemDepPred,Impl>::MemDepEntryPtr &
 532 MemDepUnit<MemDepPred, Impl>::findInHash(const DynInstPtr &inst)
 533 {
 534     MemDepHashIt hash_it = memDepHash.find(inst->seqNum);
 535
 536     assert(hash_it != memDepHash.end());
 537
 538     return (*hash_it).second;
 539 }
 540
 541 template <class MemDepPred, class Impl>
 542 inline void
 543 MemDepUnit<MemDepPred, Impl>::moveToReady(MemDepEntryPtr &woken_inst_entry)
 544 {
 545     DPRINTF(MemDepUnit, "Adding instruction [sn:%lli] "
 546             "to the ready list.\n", woken_inst_entry->inst->seqNum);
 547
 548     assert(!woken_inst_entry->squashed);
 549
 550     iqPtr->addReadyMemInst(woken_inst_entry->inst);
 551 }
 552
 553
 554 template <class MemDepPred, class Impl>
 555 void
 556 MemDepUnit<MemDepPred, Impl>::dumpLists()
 557 {
 558     for (unsigned tid=0; tid < Impl::MaxThreads; tid++) {
 559         cprintf("Instruction list %i size: %i\n",
 560                 tid, instList[tid].size());
 561
 562         ListIt inst_list_it = instList[tid].begin();
 563         int num = 0;
 564
 565         while (inst_list_it != instList[tid].end()) {
 566             cprintf("Instruction:%i\nPC:%#x\n[sn:%i]\n[tid:%i]\nIssued:%i\n"
 567                     "Squashed:%i\n\n",
 568                     num, (*inst_list_it)->readPC(),
 569                     (*inst_list_it)->seqNum,
 570                     (*inst_list_it)->threadNumber,
 571                     (*inst_list_it)->isIssued(),
 572                     (*inst_list_it)->isSquashed());
 573             inst_list_it++;
 574             ++num;
 575         }
 576     }
 577
 578     cprintf("Memory dependence hash size: %i\n", memDepHash.size());
 579
 580 #ifdef DEBUG
 581     cprintf("Memory dependence entries: %i\n", MemDepEntry::memdep_count);
 582 #endif
 583 }