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