src/cpu/o3/mem_dep_unit_impl.hh

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