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