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