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