mem_dep_unit_impl.hh revision 2665:a124942bacb8
1/* 2 * Copyright (c) 2004-2005 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/mem_dep_unit.hh" 34 35template <class MemDepPred, class Impl> 36MemDepUnit<MemDepPred, Impl>::MemDepUnit(Params ¶ms) 37 : depPred(params.SSITSize, params.LFSTSize) 38{ 39 DPRINTF(MemDepUnit, "MemDepUnit: Creating MemDepUnit object.\n"); 40} 41 42template <class MemDepPred, class Impl> 43void 44MemDepUnit<MemDepPred, Impl>::regStats() 45{ 46 insertedLoads 47 .name(name() + ".memDep.insertedLoads") 48 .desc("Number of loads inserted to the mem dependence unit."); 49 50 insertedStores 51 .name(name() + ".memDep.insertedStores") 52 .desc("Number of stores inserted to the mem dependence unit."); 53 54 conflictingLoads 55 .name(name() + ".memDep.conflictingLoads") 56 .desc("Number of conflicting loads."); 57 58 conflictingStores 59 .name(name() + ".memDep.conflictingStores") 60 .desc("Number of conflicting stores."); 61} 62 63template <class MemDepPred, class Impl> 64void 65MemDepUnit<MemDepPred, Impl>::insert(DynInstPtr &inst) 66{ 67 InstSeqNum inst_seq_num = inst->seqNum; 68 69 Dependency unresolved_dependencies(inst_seq_num); 70 71 InstSeqNum producing_store = depPred.checkInst(inst->readPC()); 72 73 if (producing_store == 0 || 74 storeDependents.find(producing_store) == storeDependents.end()) { 75 76 DPRINTF(MemDepUnit, "MemDepUnit: No dependency for inst PC " 77 "%#x.\n", inst->readPC()); 78 79 unresolved_dependencies.storeDep = storeDependents.end(); 80 81 if (inst->readyToIssue()) { 82 readyInsts.insert(inst_seq_num); 83 } else { 84 unresolved_dependencies.memDepReady = true; 85 86 waitingInsts.insert(unresolved_dependencies); 87 } 88 } else { 89 DPRINTF(MemDepUnit, "MemDepUnit: Adding to dependency list; " 90 "inst PC %#x is dependent on seq num %i.\n", 91 inst->readPC(), producing_store); 92 93 if (inst->readyToIssue()) { 94 unresolved_dependencies.regsReady = true; 95 } 96 97 // Find the store that this instruction is dependent on. 98 sd_it_t store_loc = storeDependents.find(producing_store); 99 100 assert(store_loc != storeDependents.end()); 101 102 // Record the location of the store that this instruction is 103 // dependent on. 104 unresolved_dependencies.storeDep = store_loc; 105 106 // If it's not already ready, then add it to the renamed 107 // list and the dependencies. 108 dep_it_t inst_loc = 109 (waitingInsts.insert(unresolved_dependencies)).first; 110 111 // Add this instruction to the list of dependents. 112 (*store_loc).second.push_back(inst_loc); 113 114 assert(!(*store_loc).second.empty()); 115 116 if (inst->isLoad()) { 117 ++conflictingLoads; 118 } else { 119 ++conflictingStores; 120 } 121 } 122 123 if (inst->isStore()) { 124 DPRINTF(MemDepUnit, "MemDepUnit: Inserting store PC %#x.\n", 125 inst->readPC()); 126 127 depPred.insertStore(inst->readPC(), inst_seq_num); 128 129 // Make sure this store isn't already in this list. 130 assert(storeDependents.find(inst_seq_num) == storeDependents.end()); 131 132 // Put a dependency entry in at the store's sequence number. 133 // Uh, not sure how this works...I want to create an entry but 134 // I don't have anything to put into the value yet. 135 storeDependents[inst_seq_num]; 136 137 assert(storeDependents.size() != 0); 138 139 ++insertedStores; 140 141 } else if (inst->isLoad()) { 142 ++insertedLoads; 143 } else { 144 panic("MemDepUnit: Unknown type! (most likely a barrier)."); 145 } 146 147 memInsts[inst_seq_num] = inst; 148} 149 150template <class MemDepPred, class Impl> 151void 152MemDepUnit<MemDepPred, Impl>::insertNonSpec(DynInstPtr &inst) 153{ 154 InstSeqNum inst_seq_num = inst->seqNum; 155 156 Dependency non_spec_inst(inst_seq_num); 157 158 non_spec_inst.storeDep = storeDependents.end(); 159 160 waitingInsts.insert(non_spec_inst); 161 162 // Might want to turn this part into an inline function or something. 163 // It's shared between both insert functions. 164 if (inst->isStore()) { 165 DPRINTF(MemDepUnit, "MemDepUnit: Inserting store PC %#x.\n", 166 inst->readPC()); 167 168 depPred.insertStore(inst->readPC(), inst_seq_num); 169 170 // Make sure this store isn't already in this list. 171 assert(storeDependents.find(inst_seq_num) == storeDependents.end()); 172 173 // Put a dependency entry in at the store's sequence number. 174 // Uh, not sure how this works...I want to create an entry but 175 // I don't have anything to put into the value yet. 176 storeDependents[inst_seq_num]; 177 178 assert(storeDependents.size() != 0); 179 180 ++insertedStores; 181 182 } else if (inst->isLoad()) { 183 ++insertedLoads; 184 } else { 185 panic("MemDepUnit: Unknown type! (most likely a barrier)."); 186 } 187 188 memInsts[inst_seq_num] = inst; 189} 190 191template <class MemDepPred, class Impl> 192typename Impl::DynInstPtr & 193MemDepUnit<MemDepPred, Impl>::top() 194{ 195 topInst = memInsts.find( (*readyInsts.begin()) ); 196 197 DPRINTF(MemDepUnit, "MemDepUnit: Top instruction is PC %#x.\n", 198 (*topInst).second->readPC()); 199 200 return (*topInst).second; 201} 202 203template <class MemDepPred, class Impl> 204void 205MemDepUnit<MemDepPred, Impl>::pop() 206{ 207 DPRINTF(MemDepUnit, "MemDepUnit: Removing instruction PC %#x.\n", 208 (*topInst).second->readPC()); 209 210 wakeDependents((*topInst).second); 211 212 issue((*topInst).second); 213 214 memInsts.erase(topInst); 215 216 topInst = memInsts.end(); 217} 218 219template <class MemDepPred, class Impl> 220void 221MemDepUnit<MemDepPred, Impl>::regsReady(DynInstPtr &inst) 222{ 223 DPRINTF(MemDepUnit, "MemDepUnit: Marking registers as ready for " 224 "instruction PC %#x.\n", 225 inst->readPC()); 226 227 InstSeqNum inst_seq_num = inst->seqNum; 228 229 Dependency inst_to_find(inst_seq_num); 230 231 dep_it_t waiting_inst = waitingInsts.find(inst_to_find); 232 233 assert(waiting_inst != waitingInsts.end()); 234 235 if ((*waiting_inst).memDepReady) { 236 DPRINTF(MemDepUnit, "MemDepUnit: Instruction has its memory " 237 "dependencies resolved, adding it to the ready list.\n"); 238 239 moveToReady(waiting_inst); 240 } else { 241 DPRINTF(MemDepUnit, "MemDepUnit: Instruction still waiting on " 242 "memory dependency.\n"); 243 244 (*waiting_inst).regsReady = true; 245 } 246} 247 248template <class MemDepPred, class Impl> 249void 250MemDepUnit<MemDepPred, Impl>::nonSpecInstReady(DynInstPtr &inst) 251{ 252 DPRINTF(MemDepUnit, "MemDepUnit: Marking non speculative " 253 "instruction PC %#x as ready.\n", 254 inst->readPC()); 255 256 InstSeqNum inst_seq_num = inst->seqNum; 257 258 Dependency inst_to_find(inst_seq_num); 259 260 dep_it_t waiting_inst = waitingInsts.find(inst_to_find); 261 262 assert(waiting_inst != waitingInsts.end()); 263 264 moveToReady(waiting_inst); 265} 266 267template <class MemDepPred, class Impl> 268void 269MemDepUnit<MemDepPred, Impl>::issue(DynInstPtr &inst) 270{ 271 assert(readyInsts.find(inst->seqNum) != readyInsts.end()); 272 273 DPRINTF(MemDepUnit, "MemDepUnit: Issuing instruction PC %#x.\n", 274 inst->readPC()); 275 276 // Remove the instruction from the ready list. 277 readyInsts.erase(inst->seqNum); 278 279 depPred.issued(inst->readPC(), inst->seqNum, inst->isStore()); 280} 281 282template <class MemDepPred, class Impl> 283void 284MemDepUnit<MemDepPred, Impl>::wakeDependents(DynInstPtr &inst) 285{ 286 // Only stores have dependents. 287 if (!inst->isStore()) { 288 return; 289 } 290 291 // Wake any dependencies. 292 sd_it_t sd_it = storeDependents.find(inst->seqNum); 293 294 // If there's no entry, then return. Really there should only be 295 // no entry if the instruction is a load. 296 if (sd_it == storeDependents.end()) { 297 DPRINTF(MemDepUnit, "MemDepUnit: Instruction PC %#x, sequence " 298 "number %i has no dependents.\n", 299 inst->readPC(), inst->seqNum); 300 301 return; 302 } 303 304 for (int i = 0; i < (*sd_it).second.size(); ++i ) { 305 dep_it_t woken_inst = (*sd_it).second[i]; 306 307 DPRINTF(MemDepUnit, "MemDepUnit: Waking up a dependent inst, " 308 "sequence number %i.\n", 309 (*woken_inst).seqNum); 310#if 0 311 // Should we have reached instructions that are actually squashed, 312 // there will be no more useful instructions in this dependency 313 // list. Break out early. 314 if (waitingInsts.find(woken_inst) == waitingInsts.end()) { 315 DPRINTF(MemDepUnit, "MemDepUnit: Dependents on inst PC %#x " 316 "are squashed, starting at SN %i. Breaking early.\n", 317 inst->readPC(), woken_inst); 318 break; 319 } 320#endif 321 322 if ((*woken_inst).regsReady) { 323 moveToReady(woken_inst); 324 } else { 325 (*woken_inst).memDepReady = true; 326 } 327 } 328 329 storeDependents.erase(sd_it); 330} 331 332template <class MemDepPred, class Impl> 333void 334MemDepUnit<MemDepPred, Impl>::squash(const InstSeqNum &squashed_num) 335{ 336 337 if (!waitingInsts.empty()) { 338 dep_it_t waiting_it = waitingInsts.end(); 339 340 --waiting_it; 341 342 // Remove entries from the renamed list as long as we haven't reached 343 // the end and the entries continue to be younger than the squashed. 344 while (!waitingInsts.empty() && 345 (*waiting_it).seqNum > squashed_num) 346 { 347 if (!(*waiting_it).memDepReady && 348 (*waiting_it).storeDep != storeDependents.end()) { 349 sd_it_t sd_it = (*waiting_it).storeDep; 350 351 // Make sure the iterator that the store has pointing 352 // back is actually to this instruction. 353 assert((*sd_it).second.back() == waiting_it); 354 355 // Now remove this from the store's list of dependent 356 // instructions. 357 (*sd_it).second.pop_back(); 358 } 359 360 waitingInsts.erase(waiting_it--); 361 } 362 } 363 364 if (!readyInsts.empty()) { 365 sn_it_t ready_it = readyInsts.end(); 366 367 --ready_it; 368 369 // Same for the ready list. 370 while (!readyInsts.empty() && 371 (*ready_it) > squashed_num) 372 { 373 readyInsts.erase(ready_it--); 374 } 375 } 376 377 if (!storeDependents.empty()) { 378 sd_it_t dep_it = storeDependents.end(); 379 380 --dep_it; 381 382 // Same for the dependencies list. 383 while (!storeDependents.empty() && 384 (*dep_it).first > squashed_num) 385 { 386 // This store's list of dependent instructions should be empty. 387 assert((*dep_it).second.empty()); 388 389 storeDependents.erase(dep_it--); 390 } 391 } 392 393 // Tell the dependency predictor to squash as well. 394 depPred.squash(squashed_num); 395} 396 397template <class MemDepPred, class Impl> 398void 399MemDepUnit<MemDepPred, Impl>::violation(DynInstPtr &store_inst, 400 DynInstPtr &violating_load) 401{ 402 DPRINTF(MemDepUnit, "MemDepUnit: Passing violating PCs to store sets," 403 " load: %#x, store: %#x\n", violating_load->readPC(), 404 store_inst->readPC()); 405 // Tell the memory dependence unit of the violation. 406 depPred.violation(violating_load->readPC(), store_inst->readPC()); 407} 408 409template <class MemDepPred, class Impl> 410inline void 411MemDepUnit<MemDepPred, Impl>::moveToReady(dep_it_t &woken_inst) 412{ 413 DPRINTF(MemDepUnit, "MemDepUnit: Adding instruction sequence number %i " 414 "to the ready list.\n", (*woken_inst).seqNum); 415 416 // Add it to the ready list. 417 readyInsts.insert((*woken_inst).seqNum); 418 419 // Remove it from the waiting instructions. 420 waitingInsts.erase(woken_inst); 421} 422