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