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