mem_dep_unit_impl.hh revision 1689
1545SN/A/*
21762SN/A * Copyright (c) 2004-2005 The Regents of The University of Michigan
3545SN/A * All rights reserved.
4545SN/A *
5545SN/A * Redistribution and use in source and binary forms, with or without
6545SN/A * modification, are permitted provided that the following conditions are
7545SN/A * met: redistributions of source code must retain the above copyright
8545SN/A * notice, this list of conditions and the following disclaimer;
9545SN/A * redistributions in binary form must reproduce the above copyright
10545SN/A * notice, this list of conditions and the following disclaimer in the
11545SN/A * documentation and/or other materials provided with the distribution;
12545SN/A * neither the name of the copyright holders nor the names of its
13545SN/A * contributors may be used to endorse or promote products derived from
14545SN/A * this software without specific prior written permission.
15545SN/A *
16545SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17545SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18545SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19545SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20545SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21545SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22545SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23545SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24545SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25545SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26545SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
272665Ssaidi@eecs.umich.edu */
282665Ssaidi@eecs.umich.edu
292665Ssaidi@eecs.umich.edu#include <map>
30545SN/A
31545SN/A#include "cpu/beta_cpu/mem_dep_unit.hh"
321310SN/A
331310SN/Atemplate <class MemDepPred, class Impl>
34545SN/AMemDepUnit<MemDepPred, Impl>::MemDepUnit(Params &params)
355386Sstever@gmail.com    : depPred(params.SSITSize, params.LFSTSize)
362542SN/A{
373348Sbinkertn@umich.edu    DPRINTF(MemDepUnit, "MemDepUnit: Creating MemDepUnit object.\n");
383348Sbinkertn@umich.edu}
394762Snate@binkert.org
404762Snate@binkert.orgtemplate <class MemDepPred, class Impl>
414762Snate@binkert.orgvoid
422489SN/AMemDepUnit<MemDepPred, Impl>::regStats()
43545SN/A{
443090Sstever@eecs.umich.edu    insertedLoads
452384SN/A        .name(name() + ".memDep.insertedLoads")
462489SN/A        .desc("Number of loads inserted to the mem dependence unit.");
472522SN/A
48545SN/A    insertedStores
492489SN/A        .name(name() + ".memDep.insertedStores")
502489SN/A        .desc("Number of stores inserted to the mem dependence unit.");
512489SN/A
522489SN/A    conflictingLoads
538711Sandreas.hansson@arm.com        .name(name() + ".memDep.conflictingLoads")
543090Sstever@eecs.umich.edu        .desc("Number of conflicting loads.");
553090Sstever@eecs.umich.edu
562914Ssaidi@eecs.umich.edu    conflictingStores
57545SN/A        .name(name() + ".memDep.conflictingStores")
58545SN/A        .desc("Number of conflicting stores.");
592489SN/A}
602384SN/A
612384SN/Atemplate <class MemDepPred, class Impl>
623349Sbinkertn@umich.eduvoid
632384SN/AMemDepUnit<MemDepPred, Impl>::insert(DynInstPtr &inst)
648711Sandreas.hansson@arm.com{
652384SN/A    InstSeqNum inst_seq_num = inst->seqNum;
662384SN/A
673091Sstever@eecs.umich.edu    Dependency unresolved_dependencies(inst_seq_num);
688914Sandreas.hansson@arm.com
692384SN/A    InstSeqNum producing_store = depPred.checkInst(inst->readPC());
702384SN/A
712565SN/A    if (producing_store == 0 ||
728922Swilliam.wang@arm.com        storeDependents.find(producing_store) == storeDependents.end()) {
732384SN/A
742384SN/A        DPRINTF(MemDepUnit, "MemDepUnit: No dependency for inst PC "
755386Sstever@gmail.com                "%#x.\n", inst->readPC());
762784Ssaidi@eecs.umich.edu
772784Ssaidi@eecs.umich.edu        unresolved_dependencies.storeDep = storeDependents.end();
782784Ssaidi@eecs.umich.edu
792784Ssaidi@eecs.umich.edu        if (inst->readyToIssue()) {
802784Ssaidi@eecs.umich.edu            readyInsts.insert(inst_seq_num);
812784Ssaidi@eecs.umich.edu        } else {
822784Ssaidi@eecs.umich.edu            unresolved_dependencies.memDepReady = true;
832784Ssaidi@eecs.umich.edu
842784Ssaidi@eecs.umich.edu            waitingInsts.insert(unresolved_dependencies);
852784Ssaidi@eecs.umich.edu        }
862784Ssaidi@eecs.umich.edu    } else {
872784Ssaidi@eecs.umich.edu        DPRINTF(MemDepUnit, "MemDepUnit: Adding to dependency list; "
882784Ssaidi@eecs.umich.edu                "inst PC %#x is dependent on seq num %i.\n",
892784Ssaidi@eecs.umich.edu                inst->readPC(), producing_store);
905534Ssaidi@eecs.umich.edu
915534Ssaidi@eecs.umich.edu        if (inst->readyToIssue()) {
925534Ssaidi@eecs.umich.edu            unresolved_dependencies.regsReady = true;
937403SAli.Saidi@ARM.com        }
945534Ssaidi@eecs.umich.edu
955534Ssaidi@eecs.umich.edu        // Find the store that this instruction is dependent on.
965534Ssaidi@eecs.umich.edu        sd_it_t store_loc = storeDependents.find(producing_store);
972784Ssaidi@eecs.umich.edu
982784Ssaidi@eecs.umich.edu        assert(store_loc != storeDependents.end());
992784Ssaidi@eecs.umich.edu
1007403SAli.Saidi@ARM.com        // Record the location of the store that this instruction is
1013349Sbinkertn@umich.edu        // dependent on.
1022384SN/A        unresolved_dependencies.storeDep = store_loc;
1032901Ssaidi@eecs.umich.edu
1042565SN/A        // If it's not already ready, then add it to the renamed
1052901Ssaidi@eecs.umich.edu        // list and the dependencies.
1062565SN/A        dep_it_t inst_loc =
1078832SAli.Saidi@ARM.com            (waitingInsts.insert(unresolved_dependencies)).first;
1088832SAli.Saidi@ARM.com
1098832SAli.Saidi@ARM.com        // Add this instruction to the list of dependents.
1102565SN/A        (*store_loc).second.push_back(inst_loc);
1112565SN/A
1122384SN/A        assert(!(*store_loc).second.empty());
1132901Ssaidi@eecs.umich.edu
1142901Ssaidi@eecs.umich.edu        if (inst->isLoad()) {
1152901Ssaidi@eecs.umich.edu            ++conflictingLoads;
1162901Ssaidi@eecs.umich.edu        } else {
1172901Ssaidi@eecs.umich.edu            ++conflictingStores;
1182901Ssaidi@eecs.umich.edu        }
1192901Ssaidi@eecs.umich.edu    }
1204435Ssaidi@eecs.umich.edu
1214435Ssaidi@eecs.umich.edu    if (inst->isStore()) {
1224435Ssaidi@eecs.umich.edu        DPRINTF(MemDepUnit, "MemDepUnit: Inserting store PC %#x.\n",
1234435Ssaidi@eecs.umich.edu                inst->readPC());
1247403SAli.Saidi@ARM.com
1257403SAli.Saidi@ARM.com        depPred.insertStore(inst->readPC(), inst_seq_num);
1267403SAli.Saidi@ARM.com
1277403SAli.Saidi@ARM.com        // Make sure this store isn't already in this list.
1287403SAli.Saidi@ARM.com        assert(storeDependents.find(inst_seq_num) == storeDependents.end());
1297403SAli.Saidi@ARM.com
1304435Ssaidi@eecs.umich.edu        // Put a dependency entry in at the store's sequence number.
1314435Ssaidi@eecs.umich.edu        // Uh, not sure how this works...I want to create an entry but
1324435Ssaidi@eecs.umich.edu        // I don't have anything to put into the value yet.
1334435Ssaidi@eecs.umich.edu        storeDependents[inst_seq_num];
1348630SMitchell.Hayenga@ARM.com
1358630SMitchell.Hayenga@ARM.com        assert(storeDependents.size() != 0);
1368630SMitchell.Hayenga@ARM.com
1373349Sbinkertn@umich.edu        ++insertedStores;
1383349Sbinkertn@umich.edu
1398630SMitchell.Hayenga@ARM.com    } else if (inst->isLoad()) {
1408630SMitchell.Hayenga@ARM.com        ++insertedLoads;
1418630SMitchell.Hayenga@ARM.com    } else {
1428630SMitchell.Hayenga@ARM.com        panic("MemDepUnit: Unknown type! (most likely a barrier).");
1438630SMitchell.Hayenga@ARM.com    }
1443349Sbinkertn@umich.edu
1458630SMitchell.Hayenga@ARM.com    memInsts[inst_seq_num] = inst;
1468630SMitchell.Hayenga@ARM.com}
1478630SMitchell.Hayenga@ARM.com
1488630SMitchell.Hayenga@ARM.comtemplate <class MemDepPred, class Impl>
1498630SMitchell.Hayenga@ARM.comvoid
1502384SN/AMemDepUnit<MemDepPred, Impl>::insertNonSpec(DynInstPtr &inst)
1512657Ssaidi@eecs.umich.edu{
1522384SN/A    InstSeqNum inst_seq_num = inst->seqNum;
1538922Swilliam.wang@arm.com
1542384SN/A    Dependency non_spec_inst(inst_seq_num);
1554435Ssaidi@eecs.umich.edu
1564435Ssaidi@eecs.umich.edu    non_spec_inst.storeDep = storeDependents.end();
1574435Ssaidi@eecs.umich.edu
1584435Ssaidi@eecs.umich.edu    waitingInsts.insert(non_spec_inst);
1594435Ssaidi@eecs.umich.edu
1602489SN/A    // Might want to turn this part into an inline function or something.
1612384SN/A    // It's shared between both insert functions.
1628630SMitchell.Hayenga@ARM.com    if (inst->isStore()) {
1638630SMitchell.Hayenga@ARM.com        DPRINTF(MemDepUnit, "MemDepUnit: Inserting store PC %#x.\n",
1642565SN/A                inst->readPC());
1652641Sstever@eecs.umich.edu
1667607SGene.Wu@arm.com        depPred.insertStore(inst->readPC(), inst_seq_num);
1672565SN/A
1682565SN/A        // Make sure this store isn't already in this list.
1692384SN/A        assert(storeDependents.find(inst_seq_num) == storeDependents.end());
1706227Snate@binkert.org
1712901Ssaidi@eecs.umich.edu        // Put a dependency entry in at the store's sequence number.
1722384SN/A        // Uh, not sure how this works...I want to create an entry but
1732384SN/A        // I don't have anything to put into the value yet.
1742489SN/A        storeDependents[inst_seq_num];
1752489SN/A
1762489SN/A        assert(storeDependents.size() != 0);
1778711Sandreas.hansson@arm.com
1782489SN/A        ++insertedStores;
1792489SN/A
1802489SN/A    } else if (inst->isLoad()) {
1812542SN/A        ++insertedLoads;
1822384SN/A    } else {
1832384SN/A        panic("MemDepUnit: Unknown type! (most likely a barrier).");
1842901Ssaidi@eecs.umich.edu    }
1852901Ssaidi@eecs.umich.edu
1862489SN/A    memInsts[inst_seq_num] = inst;
1872489SN/A}
1888851Sandreas.hansson@arm.com
1892384SN/Atemplate <class MemDepPred, class Impl>
1908711Sandreas.hansson@arm.comtypename Impl::DynInstPtr &
1918711Sandreas.hansson@arm.comMemDepUnit<MemDepPred, Impl>::top()
1928711Sandreas.hansson@arm.com{
1938711Sandreas.hansson@arm.com    topInst = memInsts.find( (*readyInsts.begin()) );
1948711Sandreas.hansson@arm.com
1958711Sandreas.hansson@arm.com    DPRINTF(MemDepUnit, "MemDepUnit: Top instruction is PC %#x.\n",
1968711Sandreas.hansson@arm.com            (*topInst).second->readPC());
1972384SN/A
1983090Sstever@eecs.umich.edu    return (*topInst).second;
1993090Sstever@eecs.umich.edu}
2002523SN/A
2012523SN/Atemplate <class MemDepPred, class Impl>
2022523SN/Avoid
2033349Sbinkertn@umich.eduMemDepUnit<MemDepPred, Impl>::pop()
2042384SN/A{
2052489SN/A    DPRINTF(MemDepUnit, "MemDepUnit: Removing instruction PC %#x.\n",
2062523SN/A            (*topInst).second->readPC());
2072523SN/A
2082523SN/A    wakeDependents((*topInst).second);
2092523SN/A
2103349Sbinkertn@umich.edu    issue((*topInst).second);
211545SN/A
212545SN/A    memInsts.erase(topInst);
2134762Snate@binkert.org
2144762Snate@binkert.org    topInst = memInsts.end();
2154762Snate@binkert.org}
2164762Snate@binkert.org
2174762Snate@binkert.orgtemplate <class MemDepPred, class Impl>
2184762Snate@binkert.orgvoid
2192512SN/AMemDepUnit<MemDepPred, Impl>::regsReady(DynInstPtr &inst)
2204762Snate@binkert.org{
2214762Snate@binkert.org    DPRINTF(MemDepUnit, "MemDepUnit: Marking registers as ready for "
2222384SN/A            "instruction PC %#x.\n",
2232541SN/A            inst->readPC());
2242541SN/A
2252901Ssaidi@eecs.umich.edu    InstSeqNum inst_seq_num = inst->seqNum;
2262901Ssaidi@eecs.umich.edu
2278922Swilliam.wang@arm.com    Dependency inst_to_find(inst_seq_num);
2288598Ssteve.reinhardt@amd.com
2292489SN/A    dep_it_t waiting_inst = waitingInsts.find(inst_to_find);
2302489SN/A
231545SN/A    assert(waiting_inst != waitingInsts.end());
232545SN/A
2332512SN/A    if ((*waiting_inst).memDepReady) {
2342512SN/A        DPRINTF(MemDepUnit, "MemDepUnit: Instruction has its memory "
2352512SN/A                "dependencies resolved, adding it to the ready list.\n");
2362512SN/A
2372512SN/A        moveToReady(waiting_inst);
2382512SN/A    } else {
2392512SN/A        DPRINTF(MemDepUnit, "MemDepUnit: Instruction still waiting on "
2402521SN/A                "memory dependency.\n");
2412512SN/A
2422512SN/A        (*waiting_inst).regsReady = true;
2432512SN/A    }
2442512SN/A}
2452512SN/A
2464762Snate@binkert.orgtemplate <class MemDepPred, class Impl>
2474762Snate@binkert.orgvoid
2484762Snate@binkert.orgMemDepUnit<MemDepPred, Impl>::nonSpecInstReady(DynInstPtr &inst)
2494762Snate@binkert.org{
2504762Snate@binkert.org    DPRINTF(MemDepUnit, "MemDepUnit: Marking non speculative "
2514762Snate@binkert.org            "instruction PC %#x as ready.\n",
2524762Snate@binkert.org            inst->readPC());
2534762Snate@binkert.org
2542512SN/A    InstSeqNum inst_seq_num = inst->seqNum;
2558711Sandreas.hansson@arm.com
2568711Sandreas.hansson@arm.com    Dependency inst_to_find(inst_seq_num);
2578711Sandreas.hansson@arm.com
2588711Sandreas.hansson@arm.com    dep_it_t waiting_inst = waitingInsts.find(inst_to_find);
2592539SN/A
2608711Sandreas.hansson@arm.com    assert(waiting_inst != waitingInsts.end());
2612539SN/A
2622512SN/A    moveToReady(waiting_inst);
2632512SN/A}
264545SN/A
265545SN/Atemplate <class MemDepPred, class Impl>
2664435Ssaidi@eecs.umich.eduvoid
2678851Sandreas.hansson@arm.comMemDepUnit<MemDepPred, Impl>::issue(DynInstPtr &inst)
268545SN/A{
269545SN/A    assert(readyInsts.find(inst->seqNum) != readyInsts.end());
2704762Snate@binkert.org
2714762Snate@binkert.org    DPRINTF(MemDepUnit, "MemDepUnit: Issuing instruction PC %#x.\n",
272545SN/A            inst->readPC());
2732384SN/A
2744762Snate@binkert.org    // Remove the instruction from the ready list.
2754762Snate@binkert.org    readyInsts.erase(inst->seqNum);
2764762Snate@binkert.org
2774762Snate@binkert.org    depPred.issued(inst->readPC(), inst->seqNum, inst->isStore());
2784762Snate@binkert.org}
2794762Snate@binkert.org
2808851Sandreas.hansson@arm.comtemplate <class MemDepPred, class Impl>
2818851Sandreas.hansson@arm.comvoid
2824022Sstever@eecs.umich.eduMemDepUnit<MemDepPred, Impl>::wakeDependents(DynInstPtr &inst)
2838851Sandreas.hansson@arm.com{
2844022Sstever@eecs.umich.edu    // Only stores have dependents.
2852565SN/A    if (!inst->isStore()) {
2868851Sandreas.hansson@arm.com        return;
2878851Sandreas.hansson@arm.com    }
2884263Ssaidi@eecs.umich.edu
2898851Sandreas.hansson@arm.com    // Wake any dependencies.
2904263Ssaidi@eecs.umich.edu    sd_it_t sd_it = storeDependents.find(inst->seqNum);
2912565SN/A
2928851Sandreas.hansson@arm.com    // If there's no entry, then return.  Really there should only be
2938851Sandreas.hansson@arm.com    // no entry if the instruction is a load.
2948851Sandreas.hansson@arm.com    if (sd_it == storeDependents.end()) {
2952565SN/A        DPRINTF(MemDepUnit, "MemDepUnit: Instruction PC %#x, sequence "
2962901Ssaidi@eecs.umich.edu                "number %i has no dependents.\n",
2972901Ssaidi@eecs.umich.edu                inst->readPC(), inst->seqNum);
2988851Sandreas.hansson@arm.com
2994263Ssaidi@eecs.umich.edu        return;
3008922Swilliam.wang@arm.com    }
3018922Swilliam.wang@arm.com
3022489SN/A    for (int i = 0; i < (*sd_it).second.size(); ++i ) {
3032489SN/A        dep_it_t woken_inst = (*sd_it).second[i];
304545SN/A
305545SN/A        DPRINTF(MemDepUnit, "MemDepUnit: Waking up a dependent inst, "
3062384SN/A                "sequence number %i.\n",
3071310SN/A                (*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