2 * Copyright (c) 2004-2005 The Regents of The University of Michigan
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.
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.
31 #include "cpu/o3/mem_dep_unit.hh"
33 template <class MemDepPred, class Impl>
34 MemDepUnit<MemDepPred, Impl>::MemDepUnit(Params ¶ms)
35 : depPred(params.SSITSize, params.LFSTSize)
37 DPRINTF(MemDepUnit, "MemDepUnit: Creating MemDepUnit object.\n");
40 template <class MemDepPred, class Impl>
42 MemDepUnit<MemDepPred, Impl>::regStats()
45 .name(name() + ".memDep.insertedLoads")
46 .desc("Number of loads inserted to the mem dependence unit.");
49 .name(name() + ".memDep.insertedStores")
50 .desc("Number of stores inserted to the mem dependence unit.");
53 .name(name() + ".memDep.conflictingLoads")
54 .desc("Number of conflicting loads.");
57 .name(name() + ".memDep.conflictingStores")
58 .desc("Number of conflicting stores.");
61 template <class MemDepPred, class Impl>
63 MemDepUnit<MemDepPred, Impl>::insert(DynInstPtr &inst)
65 InstSeqNum inst_seq_num = inst->seqNum;
67 Dependency unresolved_dependencies(inst_seq_num);
69 InstSeqNum producing_store = depPred.checkInst(inst->readPC());
71 if (producing_store == 0 ||
72 storeDependents.find(producing_store) == storeDependents.end()) {
74 DPRINTF(MemDepUnit, "MemDepUnit: No dependency for inst PC "
75 "%#x.\n", inst->readPC());
77 unresolved_dependencies.storeDep = storeDependents.end();
79 if (inst->readyToIssue()) {
80 readyInsts.insert(inst_seq_num);
82 unresolved_dependencies.memDepReady = true;
84 waitingInsts.insert(unresolved_dependencies);
87 DPRINTF(MemDepUnit, "MemDepUnit: Adding to dependency list; "
88 "inst PC %#x is dependent on seq num %i.\n",
89 inst->readPC(), producing_store);
91 if (inst->readyToIssue()) {
92 unresolved_dependencies.regsReady = true;
95 // Find the store that this instruction is dependent on.
96 sd_it_t store_loc = storeDependents.find(producing_store);
98 assert(store_loc != storeDependents.end());
100 // Record the location of the store that this instruction is
102 unresolved_dependencies.storeDep = store_loc;
104 // If it's not already ready, then add it to the renamed
105 // list and the dependencies.
107 (waitingInsts.insert(unresolved_dependencies)).first;
109 // Add this instruction to the list of dependents.
110 (*store_loc).second.push_back(inst_loc);
112 assert(!(*store_loc).second.empty());
114 if (inst->isLoad()) {
121 if (inst->isStore()) {
122 DPRINTF(MemDepUnit, "MemDepUnit: Inserting store PC %#x.\n",
125 depPred.insertStore(inst->readPC(), inst_seq_num);
127 // Make sure this store isn't already in this list.
128 assert(storeDependents.find(inst_seq_num) == storeDependents.end());
130 // Put a dependency entry in at the store's sequence number.
131 // Uh, not sure how this works...I want to create an entry but
132 // I don't have anything to put into the value yet.
133 storeDependents[inst_seq_num];
135 assert(storeDependents.size() != 0);
139 } else if (inst->isLoad()) {
142 panic("MemDepUnit: Unknown type! (most likely a barrier).");
145 memInsts[inst_seq_num] = inst;
148 template <class MemDepPred, class Impl>
150 MemDepUnit<MemDepPred, Impl>::insertNonSpec(DynInstPtr &inst)
152 InstSeqNum inst_seq_num = inst->seqNum;
154 Dependency non_spec_inst(inst_seq_num);
156 non_spec_inst.storeDep = storeDependents.end();
158 waitingInsts.insert(non_spec_inst);
160 // Might want to turn this part into an inline function or something.
161 // It's shared between both insert functions.
162 if (inst->isStore()) {
163 DPRINTF(MemDepUnit, "MemDepUnit: Inserting store PC %#x.\n",
166 depPred.insertStore(inst->readPC(), inst_seq_num);
168 // Make sure this store isn't already in this list.
169 assert(storeDependents.find(inst_seq_num) == storeDependents.end());
171 // Put a dependency entry in at the store's sequence number.
172 // Uh, not sure how this works...I want to create an entry but
173 // I don't have anything to put into the value yet.
174 storeDependents[inst_seq_num];
176 assert(storeDependents.size() != 0);
180 } else if (inst->isLoad()) {
183 panic("MemDepUnit: Unknown type! (most likely a barrier).");
186 memInsts[inst_seq_num] = inst;
189 template <class MemDepPred, class Impl>
190 typename Impl::DynInstPtr &
191 MemDepUnit<MemDepPred, Impl>::top()
193 topInst = memInsts.find( (*readyInsts.begin()) );
195 DPRINTF(MemDepUnit, "MemDepUnit: Top instruction is PC %#x.\n",
196 (*topInst).second->readPC());
198 return (*topInst).second;
201 template <class MemDepPred, class Impl>
203 MemDepUnit<MemDepPred, Impl>::pop()
205 DPRINTF(MemDepUnit, "MemDepUnit: Removing instruction PC %#x.\n",
206 (*topInst).second->readPC());
208 wakeDependents((*topInst).second);
210 issue((*topInst).second);
212 memInsts.erase(topInst);
214 topInst = memInsts.end();
217 template <class MemDepPred, class Impl>
219 MemDepUnit<MemDepPred, Impl>::regsReady(DynInstPtr &inst)
221 DPRINTF(MemDepUnit, "MemDepUnit: Marking registers as ready for "
222 "instruction PC %#x.\n",
225 InstSeqNum inst_seq_num = inst->seqNum;
227 Dependency inst_to_find(inst_seq_num);
229 dep_it_t waiting_inst = waitingInsts.find(inst_to_find);
231 assert(waiting_inst != waitingInsts.end());
233 if ((*waiting_inst).memDepReady) {
234 DPRINTF(MemDepUnit, "MemDepUnit: Instruction has its memory "
235 "dependencies resolved, adding it to the ready list.\n");
237 moveToReady(waiting_inst);
239 DPRINTF(MemDepUnit, "MemDepUnit: Instruction still waiting on "
240 "memory dependency.\n");
242 (*waiting_inst).regsReady = true;
246 template <class MemDepPred, class Impl>
248 MemDepUnit<MemDepPred, Impl>::nonSpecInstReady(DynInstPtr &inst)
250 DPRINTF(MemDepUnit, "MemDepUnit: Marking non speculative "
251 "instruction PC %#x as ready.\n",
254 InstSeqNum inst_seq_num = inst->seqNum;
256 Dependency inst_to_find(inst_seq_num);
258 dep_it_t waiting_inst = waitingInsts.find(inst_to_find);
260 assert(waiting_inst != waitingInsts.end());
262 moveToReady(waiting_inst);
265 template <class MemDepPred, class Impl>
267 MemDepUnit<MemDepPred, Impl>::issue(DynInstPtr &inst)
269 assert(readyInsts.find(inst->seqNum) != readyInsts.end());
271 DPRINTF(MemDepUnit, "MemDepUnit: Issuing instruction PC %#x.\n",
274 // Remove the instruction from the ready list.
275 readyInsts.erase(inst->seqNum);
277 depPred.issued(inst->readPC(), inst->seqNum, inst->isStore());
280 template <class MemDepPred, class Impl>
282 MemDepUnit<MemDepPred, Impl>::wakeDependents(DynInstPtr &inst)
284 // Only stores have dependents.
285 if (!inst->isStore()) {
289 // Wake any dependencies.
290 sd_it_t sd_it = storeDependents.find(inst->seqNum);
292 // If there's no entry, then return. Really there should only be
293 // no entry if the instruction is a load.
294 if (sd_it == storeDependents.end()) {
295 DPRINTF(MemDepUnit, "MemDepUnit: Instruction PC %#x, sequence "
296 "number %i has no dependents.\n",
297 inst->readPC(), inst->seqNum);
302 for (int i = 0; i < (*sd_it).second.size(); ++i ) {
303 dep_it_t woken_inst = (*sd_it).second[i];
305 DPRINTF(MemDepUnit, "MemDepUnit: Waking up a dependent inst, "
306 "sequence number %i.\n",
307 (*woken_inst).seqNum);
309 // Should we have reached instructions that are actually squashed,
310 // there will be no more useful instructions in this dependency
311 // list. Break out early.
312 if (waitingInsts.find(woken_inst) == waitingInsts.end()) {
313 DPRINTF(MemDepUnit, "MemDepUnit: Dependents on inst PC %#x "
314 "are squashed, starting at SN %i. Breaking early.\n",
315 inst->readPC(), woken_inst);
320 if ((*woken_inst).regsReady) {
321 moveToReady(woken_inst);
323 (*woken_inst).memDepReady = true;
327 storeDependents.erase(sd_it);
330 template <class MemDepPred, class Impl>
332 MemDepUnit<MemDepPred, Impl>::squash(const InstSeqNum &squashed_num)
335 if (!waitingInsts.empty()) {
336 dep_it_t waiting_it = waitingInsts.end();
340 // Remove entries from the renamed list as long as we haven't reached
341 // the end and the entries continue to be younger than the squashed.
342 while (!waitingInsts.empty() &&
343 (*waiting_it).seqNum > squashed_num)
345 if (!(*waiting_it).memDepReady &&
346 (*waiting_it).storeDep != storeDependents.end()) {
347 sd_it_t sd_it = (*waiting_it).storeDep;
349 // Make sure the iterator that the store has pointing
350 // back is actually to this instruction.
351 assert((*sd_it).second.back() == waiting_it);
353 // Now remove this from the store's list of dependent
355 (*sd_it).second.pop_back();
358 waitingInsts.erase(waiting_it--);
362 if (!readyInsts.empty()) {
363 sn_it_t ready_it = readyInsts.end();
367 // Same for the ready list.
368 while (!readyInsts.empty() &&
369 (*ready_it) > squashed_num)
371 readyInsts.erase(ready_it--);
375 if (!storeDependents.empty()) {
376 sd_it_t dep_it = storeDependents.end();
380 // Same for the dependencies list.
381 while (!storeDependents.empty() &&
382 (*dep_it).first > squashed_num)
384 // This store's list of dependent instructions should be empty.
385 assert((*dep_it).second.empty());
387 storeDependents.erase(dep_it--);
391 // Tell the dependency predictor to squash as well.
392 depPred.squash(squashed_num);
395 template <class MemDepPred, class Impl>
397 MemDepUnit<MemDepPred, Impl>::violation(DynInstPtr &store_inst,
398 DynInstPtr &violating_load)
400 DPRINTF(MemDepUnit, "MemDepUnit: Passing violating PCs to store sets,"
401 " load: %#x, store: %#x\n", violating_load->readPC(),
402 store_inst->readPC());
403 // Tell the memory dependence unit of the violation.
404 depPred.violation(violating_load->readPC(), store_inst->readPC());
407 template <class MemDepPred, class Impl>
409 MemDepUnit<MemDepPred, Impl>::moveToReady(dep_it_t &woken_inst)
411 DPRINTF(MemDepUnit, "MemDepUnit: Adding instruction sequence number %i "
412 "to the ready list.\n", (*woken_inst).seqNum);
414 // Add it to the ready list.
415 readyInsts.insert((*woken_inst).seqNum);
417 // Remove it from the waiting instructions.
418 waitingInsts.erase(woken_inst);