mem_dep_unit_impl.hh revision 13429 
1/*
2 * Copyright (c) 2012, 2014 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder.  You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Copyright (c) 2004-2006 The Regents of The University of Michigan
15 * All rights reserved.
16 *
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions are
19 * met: redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer;
21 * redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution;
24 * neither the name of the copyright holders nor the names of its
25 * contributors may be used to endorse or promote products derived from
26 * this software without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 *
40 * Authors: Kevin Lim
41 */
42
43#ifndef __CPU_O3_MEM_DEP_UNIT_IMPL_HH__
44#define __CPU_O3_MEM_DEP_UNIT_IMPL_HH__
45
46#include <map>
47
48#include "cpu/o3/inst_queue.hh"
49#include "cpu/o3/mem_dep_unit.hh"
50#include "debug/MemDepUnit.hh"
51#include "params/DerivO3CPU.hh"
52
53template <class MemDepPred, class Impl>
54MemDepUnit<MemDepPred, Impl>::MemDepUnit()
55    : loadBarrier(false), loadBarrierSN(0), storeBarrier(false),
56      storeBarrierSN(0), iqPtr(NULL)
57{
58}
59
60template <class MemDepPred, class Impl>
61MemDepUnit<MemDepPred, Impl>::MemDepUnit(DerivO3CPUParams *params)
62    : _name(params->name + ".memdepunit"),
63      depPred(params->store_set_clear_period, params->SSITSize,
64              params->LFSTSize),
65      loadBarrier(false), loadBarrierSN(0), storeBarrier(false),
66      storeBarrierSN(0), iqPtr(NULL)
67{
68    DPRINTF(MemDepUnit, "Creating MemDepUnit object.\n");
69}
70
71template <class MemDepPred, class Impl>
72MemDepUnit<MemDepPred, Impl>::~MemDepUnit()
73{
74    for (ThreadID tid = 0; tid < Impl::MaxThreads; tid++) {
75
76        ListIt inst_list_it = instList[tid].begin();
77
78        MemDepHashIt hash_it;
79
80        while (!instList[tid].empty()) {
81            hash_it = memDepHash.find((*inst_list_it)->seqNum);
82
83            assert(hash_it != memDepHash.end());
84
85            memDepHash.erase(hash_it);
86
87            instList[tid].erase(inst_list_it++);
88        }
89    }
90
91#ifdef DEBUG
92    assert(MemDepEntry::memdep_count == 0);
93#endif
94}
95
96template <class MemDepPred, class Impl>
97void
98MemDepUnit<MemDepPred, Impl>::init(DerivO3CPUParams *params, ThreadID tid)
99{
100    DPRINTF(MemDepUnit, "Creating MemDepUnit %i object.\n",tid);
101
102    _name = csprintf("%s.memDep%d", params->name, tid);
103    id = tid;
104
105    depPred.init(params->store_set_clear_period, params->SSITSize,
106            params->LFSTSize);
107}
108
109template <class MemDepPred, class Impl>
110void
111MemDepUnit<MemDepPred, Impl>::regStats()
112{
113    insertedLoads
114        .name(name() + ".insertedLoads")
115        .desc("Number of loads inserted to the mem dependence unit.");
116
117    insertedStores
118        .name(name() + ".insertedStores")
119        .desc("Number of stores inserted to the mem dependence unit.");
120
121    conflictingLoads
122        .name(name() + ".conflictingLoads")
123        .desc("Number of conflicting loads.");
124
125    conflictingStores
126        .name(name() + ".conflictingStores")
127        .desc("Number of conflicting stores.");
128}
129
130template <class MemDepPred, class Impl>
131bool
132MemDepUnit<MemDepPred, Impl>::isDrained() const
133{
134    bool drained = instsToReplay.empty()
135                 && memDepHash.empty()
136                 && instsToReplay.empty();
137    for (int i = 0; i < Impl::MaxThreads; ++i)
138        drained = drained && instList[i].empty();
139
140    return drained;
141}
142
143template <class MemDepPred, class Impl>
144void
145MemDepUnit<MemDepPred, Impl>::drainSanityCheck() const
146{
147    assert(instsToReplay.empty());
148    assert(memDepHash.empty());
149    for (int i = 0; i < Impl::MaxThreads; ++i)
150        assert(instList[i].empty());
151    assert(instsToReplay.empty());
152    assert(memDepHash.empty());
153}
154
155template <class MemDepPred, class Impl>
156void
157MemDepUnit<MemDepPred, Impl>::takeOverFrom()
158{
159    // Be sure to reset all state.
160    loadBarrier = storeBarrier = false;
161    loadBarrierSN = storeBarrierSN = 0;
162    depPred.clear();
163}
164
165template <class MemDepPred, class Impl>
166void
167MemDepUnit<MemDepPred, Impl>::setIQ(InstructionQueue<Impl> *iq_ptr)
168{
169    iqPtr = iq_ptr;
170}
171
172template <class MemDepPred, class Impl>
173void
174MemDepUnit<MemDepPred, Impl>::insert(const DynInstPtr &inst)
175{
176    ThreadID tid = inst->threadNumber;
177
178    MemDepEntryPtr inst_entry = std::make_shared<MemDepEntry>(inst);
179
180    // Add the MemDepEntry to the hash.
181    memDepHash.insert(
182        std::pair<InstSeqNum, MemDepEntryPtr>(inst->seqNum, inst_entry));
183#ifdef DEBUG
184    MemDepEntry::memdep_insert++;
185#endif
186
187    instList[tid].push_back(inst);
188
189    inst_entry->listIt = --(instList[tid].end());
190
191    // Check any barriers and the dependence predictor for any
192    // producing memrefs/stores.
193    InstSeqNum producing_store;
194    if (inst->isLoad() && loadBarrier) {
195        DPRINTF(MemDepUnit, "Load barrier [sn:%lli] in flight\n",
196                loadBarrierSN);
197        producing_store = loadBarrierSN;
198    } else if (inst->isStore() && storeBarrier) {
199        DPRINTF(MemDepUnit, "Store barrier [sn:%lli] in flight\n",
200                storeBarrierSN);
201        producing_store = storeBarrierSN;
202    } else {
203        producing_store = depPred.checkInst(inst->instAddr());
204    }
205
206    MemDepEntryPtr store_entry = NULL;
207
208    // If there is a producing store, try to find the entry.
209    if (producing_store != 0) {
210        DPRINTF(MemDepUnit, "Searching for producer\n");
211        MemDepHashIt hash_it = memDepHash.find(producing_store);
212
213        if (hash_it != memDepHash.end()) {
214            store_entry = (*hash_it).second;
215            DPRINTF(MemDepUnit, "Proucer found\n");
216        }
217    }
218
219    // If no store entry, then instruction can issue as soon as the registers
220    // are ready.
221    if (!store_entry) {
222        DPRINTF(MemDepUnit, "No dependency for inst PC "
223                "%s [sn:%lli].\n", inst->pcState(), inst->seqNum);
224
225        inst_entry->memDepReady = true;
226
227        if (inst->readyToIssue()) {
228            inst_entry->regsReady = true;
229
230            moveToReady(inst_entry);
231        }
232    } else {
233        // Otherwise make the instruction dependent on the store/barrier.
234        DPRINTF(MemDepUnit, "Adding to dependency list; "
235                "inst PC %s is dependent on [sn:%lli].\n",
236                inst->pcState(), producing_store);
237
238        if (inst->readyToIssue()) {
239            inst_entry->regsReady = true;
240        }
241
242        // Clear the bit saying this instruction can issue.
243        inst->clearCanIssue();
244
245        // Add this instruction to the list of dependents.
246        store_entry->dependInsts.push_back(inst_entry);
247
248        if (inst->isLoad()) {
249            ++conflictingLoads;
250        } else {
251            ++conflictingStores;
252        }
253    }
254
255    if (inst->isStore()) {
256        DPRINTF(MemDepUnit, "Inserting store PC %s [sn:%lli].\n",
257                inst->pcState(), inst->seqNum);
258
259        depPred.insertStore(inst->instAddr(), inst->seqNum, inst->threadNumber);
260
261        ++insertedStores;
262    } else if (inst->isLoad()) {
263        ++insertedLoads;
264    } else {
265        panic("Unknown type! (most likely a barrier).");
266    }
267}
268
269template <class MemDepPred, class Impl>
270void
271MemDepUnit<MemDepPred, Impl>::insertNonSpec(const DynInstPtr &inst)
272{
273    ThreadID tid = inst->threadNumber;
274
275    MemDepEntryPtr inst_entry = std::make_shared<MemDepEntry>(inst);
276
277    // Insert the MemDepEntry into the hash.
278    memDepHash.insert(
279        std::pair<InstSeqNum, MemDepEntryPtr>(inst->seqNum, inst_entry));
280#ifdef DEBUG
281    MemDepEntry::memdep_insert++;
282#endif
283
284    // Add the instruction to the list.
285    instList[tid].push_back(inst);
286
287    inst_entry->listIt = --(instList[tid].end());
288
289    // Might want to turn this part into an inline function or something.
290    // It's shared between both insert functions.
291    if (inst->isStore()) {
292        DPRINTF(MemDepUnit, "Inserting store PC %s [sn:%lli].\n",
293                inst->pcState(), inst->seqNum);
294
295        depPred.insertStore(inst->instAddr(), inst->seqNum, inst->threadNumber);
296
297        ++insertedStores;
298    } else if (inst->isLoad()) {
299        ++insertedLoads;
300    } else {
301        panic("Unknown type! (most likely a barrier).");
302    }
303}
304
305template <class MemDepPred, class Impl>
306void
307MemDepUnit<MemDepPred, Impl>::insertBarrier(const DynInstPtr &barr_inst)
308{
309    InstSeqNum barr_sn = barr_inst->seqNum;
310    // Memory barriers block loads and stores, write barriers only stores.
311    if (barr_inst->isMemBarrier()) {
312        loadBarrier = true;
313        loadBarrierSN = barr_sn;
314        storeBarrier = true;
315        storeBarrierSN = barr_sn;
316        DPRINTF(MemDepUnit, "Inserted a memory barrier %s SN:%lli\n",
317                barr_inst->pcState(),barr_sn);
318    } else if (barr_inst->isWriteBarrier()) {
319        storeBarrier = true;
320        storeBarrierSN = barr_sn;
321        DPRINTF(MemDepUnit, "Inserted a write barrier\n");
322    }
323
324    ThreadID tid = barr_inst->threadNumber;
325
326    MemDepEntryPtr inst_entry = std::make_shared<MemDepEntry>(barr_inst);
327
328    // Add the MemDepEntry to the hash.
329    memDepHash.insert(
330        std::pair<InstSeqNum, MemDepEntryPtr>(barr_sn, inst_entry));
331#ifdef DEBUG
332    MemDepEntry::memdep_insert++;
333#endif
334
335    // Add the instruction to the instruction list.
336    instList[tid].push_back(barr_inst);
337
338    inst_entry->listIt = --(instList[tid].end());
339}
340
341template <class MemDepPred, class Impl>
342void
343MemDepUnit<MemDepPred, Impl>::regsReady(const DynInstPtr &inst)
344{
345    DPRINTF(MemDepUnit, "Marking registers as ready for "
346            "instruction PC %s [sn:%lli].\n",
347            inst->pcState(), inst->seqNum);
348
349    MemDepEntryPtr inst_entry = findInHash(inst);
350
351    inst_entry->regsReady = true;
352
353    if (inst_entry->memDepReady) {
354        DPRINTF(MemDepUnit, "Instruction has its memory "
355                "dependencies resolved, adding it to the ready list.\n");
356
357        moveToReady(inst_entry);
358    } else {
359        DPRINTF(MemDepUnit, "Instruction still waiting on "
360                "memory dependency.\n");
361    }
362}
363
364template <class MemDepPred, class Impl>
365void
366MemDepUnit<MemDepPred, Impl>::nonSpecInstReady(const DynInstPtr &inst)
367{
368    DPRINTF(MemDepUnit, "Marking non speculative "
369            "instruction PC %s as ready [sn:%lli].\n",
370            inst->pcState(), inst->seqNum);
371
372    MemDepEntryPtr inst_entry = findInHash(inst);
373
374    moveToReady(inst_entry);
375}
376
377template <class MemDepPred, class Impl>
378void
379MemDepUnit<MemDepPred, Impl>::reschedule(const DynInstPtr &inst)
380{
381    instsToReplay.push_back(inst);
382}
383
384template <class MemDepPred, class Impl>
385void
386MemDepUnit<MemDepPred, Impl>::replay()
387{
388    DynInstPtr temp_inst;
389
390    // For now this replay function replays all waiting memory ops.
391    while (!instsToReplay.empty()) {
392        temp_inst = instsToReplay.front();
393
394        MemDepEntryPtr inst_entry = findInHash(temp_inst);
395
396        DPRINTF(MemDepUnit, "Replaying mem instruction PC %s [sn:%lli].\n",
397                temp_inst->pcState(), temp_inst->seqNum);
398
399        moveToReady(inst_entry);
400
401        instsToReplay.pop_front();
402    }
403}
404
405template <class MemDepPred, class Impl>
406void
407MemDepUnit<MemDepPred, Impl>::completed(const DynInstPtr &inst)
408{
409    DPRINTF(MemDepUnit, "Completed mem instruction PC %s [sn:%lli].\n",
410            inst->pcState(), inst->seqNum);
411
412    ThreadID tid = inst->threadNumber;
413
414    // Remove the instruction from the hash and the list.
415    MemDepHashIt hash_it = memDepHash.find(inst->seqNum);
416
417    assert(hash_it != memDepHash.end());
418
419    instList[tid].erase((*hash_it).second->listIt);
420
421    (*hash_it).second = NULL;
422
423    memDepHash.erase(hash_it);
424#ifdef DEBUG
425    MemDepEntry::memdep_erase++;
426#endif
427}
428
429template <class MemDepPred, class Impl>
430void
431MemDepUnit<MemDepPred, Impl>::completeBarrier(const DynInstPtr &inst)
432{
433    wakeDependents(inst);
434    completed(inst);
435
436    InstSeqNum barr_sn = inst->seqNum;
437    DPRINTF(MemDepUnit, "barrier completed: %s SN:%lli\n", inst->pcState(),
438            inst->seqNum);
439    if (inst->isMemBarrier()) {
440        if (loadBarrierSN == barr_sn)
441            loadBarrier = false;
442        if (storeBarrierSN == barr_sn)
443            storeBarrier = false;
444    } else if (inst->isWriteBarrier()) {
445        if (storeBarrierSN == barr_sn)
446            storeBarrier = false;
447    }
448}
449
450template <class MemDepPred, class Impl>
451void
452MemDepUnit<MemDepPred, Impl>::wakeDependents(const DynInstPtr &inst)
453{
454    // Only stores and barriers have dependents.
455    if (!inst->isStore() && !inst->isMemBarrier() && !inst->isWriteBarrier()) {
456        return;
457    }
458
459    MemDepEntryPtr inst_entry = findInHash(inst);
460
461    for (int i = 0; i < inst_entry->dependInsts.size(); ++i ) {
462        MemDepEntryPtr woken_inst = inst_entry->dependInsts[i];
463
464        if (!woken_inst->inst) {
465            // Potentially removed mem dep entries could be on this list
466            continue;
467        }
468
469        DPRINTF(MemDepUnit, "Waking up a dependent inst, "
470                "[sn:%lli].\n",
471                woken_inst->inst->seqNum);
472
473        if (woken_inst->regsReady && !woken_inst->squashed) {
474            moveToReady(woken_inst);
475        } else {
476            woken_inst->memDepReady = true;
477        }
478    }
479
480    inst_entry->dependInsts.clear();
481}
482
483template <class MemDepPred, class Impl>
484void
485MemDepUnit<MemDepPred, Impl>::squash(const InstSeqNum &squashed_num,
486                                     ThreadID tid)
487{
488    if (!instsToReplay.empty()) {
489        ListIt replay_it = instsToReplay.begin();
490        while (replay_it != instsToReplay.end()) {
491            if ((*replay_it)->threadNumber == tid &&
492                (*replay_it)->seqNum > squashed_num) {
493                instsToReplay.erase(replay_it++);
494            } else {
495                ++replay_it;
496            }
497        }
498    }
499
500    ListIt squash_it = instList[tid].end();
501    --squash_it;
502
503    MemDepHashIt hash_it;
504
505    while (!instList[tid].empty() &&
506           (*squash_it)->seqNum > squashed_num) {
507
508        DPRINTF(MemDepUnit, "Squashing inst [sn:%lli]\n",
509                (*squash_it)->seqNum);
510
511        if ((*squash_it)->seqNum == loadBarrierSN)
512              loadBarrier = false;
513
514        if ((*squash_it)->seqNum == storeBarrierSN)
515              storeBarrier = false;
516
517        hash_it = memDepHash.find((*squash_it)->seqNum);
518
519        assert(hash_it != memDepHash.end());
520
521        (*hash_it).second->squashed = true;
522
523        (*hash_it).second = NULL;
524
525        memDepHash.erase(hash_it);
526#ifdef DEBUG
527        MemDepEntry::memdep_erase++;
528#endif
529
530        instList[tid].erase(squash_it--);
531    }
532
533    // Tell the dependency predictor to squash as well.
534    depPred.squash(squashed_num, tid);
535}
536
537template <class MemDepPred, class Impl>
538void
539MemDepUnit<MemDepPred, Impl>::violation(const DynInstPtr &store_inst,
540                                        const DynInstPtr &violating_load)
541{
542    DPRINTF(MemDepUnit, "Passing violating PCs to store sets,"
543            " load: %#x, store: %#x\n", violating_load->instAddr(),
544            store_inst->instAddr());
545    // Tell the memory dependence unit of the violation.
546    depPred.violation(store_inst->instAddr(), violating_load->instAddr());
547}
548
549template <class MemDepPred, class Impl>
550void
551MemDepUnit<MemDepPred, Impl>::issue(const DynInstPtr &inst)
552{
553    DPRINTF(MemDepUnit, "Issuing instruction PC %#x [sn:%lli].\n",
554            inst->instAddr(), inst->seqNum);
555
556    depPred.issued(inst->instAddr(), inst->seqNum, inst->isStore());
557}
558
559template <class MemDepPred, class Impl>
560inline typename MemDepUnit<MemDepPred,Impl>::MemDepEntryPtr &
561MemDepUnit<MemDepPred, Impl>::findInHash(const DynInstConstPtr &inst)
562{
563    MemDepHashIt hash_it = memDepHash.find(inst->seqNum);
564
565    assert(hash_it != memDepHash.end());
566
567    return (*hash_it).second;
568}
569
570template <class MemDepPred, class Impl>
571inline void
572MemDepUnit<MemDepPred, Impl>::moveToReady(MemDepEntryPtr &woken_inst_entry)
573{
574    DPRINTF(MemDepUnit, "Adding instruction [sn:%lli] "
575            "to the ready list.\n", woken_inst_entry->inst->seqNum);
576
577    assert(!woken_inst_entry->squashed);
578
579    iqPtr->addReadyMemInst(woken_inst_entry->inst);
580}
581
582
583template <class MemDepPred, class Impl>
584void
585MemDepUnit<MemDepPred, Impl>::dumpLists()
586{
587    for (ThreadID tid = 0; tid < Impl::MaxThreads; tid++) {
588        cprintf("Instruction list %i size: %i\n",
589                tid, instList[tid].size());
590
591        ListIt inst_list_it = instList[tid].begin();
592        int num = 0;
593
594        while (inst_list_it != instList[tid].end()) {
595            cprintf("Instruction:%i\nPC: %s\n[sn:%i]\n[tid:%i]\nIssued:%i\n"
596                    "Squashed:%i\n\n",
597                    num, (*inst_list_it)->pcState(),
598                    (*inst_list_it)->seqNum,
599                    (*inst_list_it)->threadNumber,
600                    (*inst_list_it)->isIssued(),
601                    (*inst_list_it)->isSquashed());
602            inst_list_it++;
603            ++num;
604        }
605    }
606
607    cprintf("Memory dependence hash size: %i\n", memDepHash.size());
608
609#ifdef DEBUG
610    cprintf("Memory dependence entries: %i\n", MemDepEntry::memdep_count);
611#endif
612}
613
614#endif//__CPU_O3_MEM_DEP_UNIT_IMPL_HH__
615