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