mem_dep_unit_impl.hh revision 2665
11689SN/A/* 21689SN/A * Copyright (c) 2004-2005 The Regents of The University of Michigan 31689SN/A * All rights reserved. 41689SN/A * 51689SN/A * Redistribution and use in source and binary forms, with or without 61689SN/A * modification, are permitted provided that the following conditions are 71689SN/A * met: redistributions of source code must retain the above copyright 81689SN/A * notice, this list of conditions and the following disclaimer; 91689SN/A * redistributions in binary form must reproduce the above copyright 101689SN/A * notice, this list of conditions and the following disclaimer in the 111689SN/A * documentation and/or other materials provided with the distribution; 121689SN/A * neither the name of the copyright holders nor the names of its 131689SN/A * contributors may be used to endorse or promote products derived from 141689SN/A * this software without specific prior written permission. 151689SN/A * 161689SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 171689SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 181689SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 191689SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 201689SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 211689SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 221689SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 231689SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 241689SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 251689SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 261689SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272665Ssaidi@eecs.umich.edu * 282665Ssaidi@eecs.umich.edu * Authors: Kevin Lim 291689SN/A */ 301061SN/A 311061SN/A#include <map> 321061SN/A 331717SN/A#include "cpu/o3/mem_dep_unit.hh" 341061SN/A 351061SN/Atemplate <class MemDepPred, class Impl> 361061SN/AMemDepUnit<MemDepPred, Impl>::MemDepUnit(Params ¶ms) 371062SN/A : depPred(params.SSITSize, params.LFSTSize) 381061SN/A{ 391061SN/A DPRINTF(MemDepUnit, "MemDepUnit: Creating MemDepUnit object.\n"); 401061SN/A} 411061SN/A 421061SN/Atemplate <class MemDepPred, class Impl> 431061SN/Avoid 441062SN/AMemDepUnit<MemDepPred, Impl>::regStats() 451062SN/A{ 461062SN/A insertedLoads 471062SN/A .name(name() + ".memDep.insertedLoads") 481062SN/A .desc("Number of loads inserted to the mem dependence unit."); 491062SN/A 501062SN/A insertedStores 511062SN/A .name(name() + ".memDep.insertedStores") 521062SN/A .desc("Number of stores inserted to the mem dependence unit."); 531062SN/A 541062SN/A conflictingLoads 551062SN/A .name(name() + ".memDep.conflictingLoads") 561062SN/A .desc("Number of conflicting loads."); 571062SN/A 581062SN/A conflictingStores 591062SN/A .name(name() + ".memDep.conflictingStores") 601062SN/A .desc("Number of conflicting stores."); 611062SN/A} 621062SN/A 631062SN/Atemplate <class MemDepPred, class Impl> 641062SN/Avoid 651061SN/AMemDepUnit<MemDepPred, Impl>::insert(DynInstPtr &inst) 661061SN/A{ 671061SN/A InstSeqNum inst_seq_num = inst->seqNum; 681061SN/A 691062SN/A Dependency unresolved_dependencies(inst_seq_num); 701061SN/A 711061SN/A InstSeqNum producing_store = depPred.checkInst(inst->readPC()); 721061SN/A 731061SN/A if (producing_store == 0 || 741062SN/A storeDependents.find(producing_store) == storeDependents.end()) { 751062SN/A 761062SN/A DPRINTF(MemDepUnit, "MemDepUnit: No dependency for inst PC " 771062SN/A "%#x.\n", inst->readPC()); 781062SN/A 791062SN/A unresolved_dependencies.storeDep = storeDependents.end(); 801062SN/A 811062SN/A if (inst->readyToIssue()) { 821062SN/A readyInsts.insert(inst_seq_num); 831062SN/A } else { 841062SN/A unresolved_dependencies.memDepReady = true; 851062SN/A 861062SN/A waitingInsts.insert(unresolved_dependencies); 871062SN/A } 881061SN/A } else { 891062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Adding to dependency list; " 901062SN/A "inst PC %#x is dependent on seq num %i.\n", 911062SN/A inst->readPC(), producing_store); 921062SN/A 931062SN/A if (inst->readyToIssue()) { 941062SN/A unresolved_dependencies.regsReady = true; 951062SN/A } 961062SN/A 971062SN/A // Find the store that this instruction is dependent on. 981062SN/A sd_it_t store_loc = storeDependents.find(producing_store); 991062SN/A 1001062SN/A assert(store_loc != storeDependents.end()); 1011062SN/A 1021062SN/A // Record the location of the store that this instruction is 1031062SN/A // dependent on. 1041062SN/A unresolved_dependencies.storeDep = store_loc; 1051062SN/A 1061061SN/A // If it's not already ready, then add it to the renamed 1071061SN/A // list and the dependencies. 1081062SN/A dep_it_t inst_loc = 1091062SN/A (waitingInsts.insert(unresolved_dependencies)).first; 1101061SN/A 1111062SN/A // Add this instruction to the list of dependents. 1121062SN/A (*store_loc).second.push_back(inst_loc); 1131062SN/A 1141062SN/A assert(!(*store_loc).second.empty()); 1151062SN/A 1161062SN/A if (inst->isLoad()) { 1171062SN/A ++conflictingLoads; 1181062SN/A } else { 1191062SN/A ++conflictingStores; 1201062SN/A } 1211061SN/A } 1221061SN/A 1231061SN/A if (inst->isStore()) { 1241062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Inserting store PC %#x.\n", 1251062SN/A inst->readPC()); 1261062SN/A 1271061SN/A depPred.insertStore(inst->readPC(), inst_seq_num); 1281061SN/A 1291061SN/A // Make sure this store isn't already in this list. 1301062SN/A assert(storeDependents.find(inst_seq_num) == storeDependents.end()); 1311061SN/A 1321061SN/A // Put a dependency entry in at the store's sequence number. 1331061SN/A // Uh, not sure how this works...I want to create an entry but 1341061SN/A // I don't have anything to put into the value yet. 1351062SN/A storeDependents[inst_seq_num]; 1361062SN/A 1371062SN/A assert(storeDependents.size() != 0); 1381062SN/A 1391062SN/A ++insertedStores; 1401062SN/A 1411062SN/A } else if (inst->isLoad()) { 1421062SN/A ++insertedLoads; 1431062SN/A } else { 1441061SN/A panic("MemDepUnit: Unknown type! (most likely a barrier)."); 1451061SN/A } 1461062SN/A 1471062SN/A memInsts[inst_seq_num] = inst; 1481062SN/A} 1491062SN/A 1501062SN/Atemplate <class MemDepPred, class Impl> 1511062SN/Avoid 1521062SN/AMemDepUnit<MemDepPred, Impl>::insertNonSpec(DynInstPtr &inst) 1531062SN/A{ 1541062SN/A InstSeqNum inst_seq_num = inst->seqNum; 1551062SN/A 1561062SN/A Dependency non_spec_inst(inst_seq_num); 1571062SN/A 1581062SN/A non_spec_inst.storeDep = storeDependents.end(); 1591062SN/A 1601062SN/A waitingInsts.insert(non_spec_inst); 1611062SN/A 1621062SN/A // Might want to turn this part into an inline function or something. 1631062SN/A // It's shared between both insert functions. 1641062SN/A if (inst->isStore()) { 1651062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Inserting store PC %#x.\n", 1661062SN/A inst->readPC()); 1671062SN/A 1681062SN/A depPred.insertStore(inst->readPC(), inst_seq_num); 1691062SN/A 1701062SN/A // Make sure this store isn't already in this list. 1711062SN/A assert(storeDependents.find(inst_seq_num) == storeDependents.end()); 1721062SN/A 1731062SN/A // Put a dependency entry in at the store's sequence number. 1741062SN/A // Uh, not sure how this works...I want to create an entry but 1751062SN/A // I don't have anything to put into the value yet. 1761062SN/A storeDependents[inst_seq_num]; 1771062SN/A 1781062SN/A assert(storeDependents.size() != 0); 1791062SN/A 1801062SN/A ++insertedStores; 1811062SN/A 1821062SN/A } else if (inst->isLoad()) { 1831062SN/A ++insertedLoads; 1841062SN/A } else { 1851062SN/A panic("MemDepUnit: Unknown type! (most likely a barrier)."); 1861062SN/A } 1871062SN/A 1881062SN/A memInsts[inst_seq_num] = inst; 1891062SN/A} 1901062SN/A 1911062SN/Atemplate <class MemDepPred, class Impl> 1921062SN/Atypename Impl::DynInstPtr & 1931062SN/AMemDepUnit<MemDepPred, Impl>::top() 1941062SN/A{ 1951062SN/A topInst = memInsts.find( (*readyInsts.begin()) ); 1961062SN/A 1971062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Top instruction is PC %#x.\n", 1981062SN/A (*topInst).second->readPC()); 1991062SN/A 2001062SN/A return (*topInst).second; 2011062SN/A} 2021062SN/A 2031062SN/Atemplate <class MemDepPred, class Impl> 2041062SN/Avoid 2051062SN/AMemDepUnit<MemDepPred, Impl>::pop() 2061062SN/A{ 2071062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Removing instruction PC %#x.\n", 2081062SN/A (*topInst).second->readPC()); 2091062SN/A 2101062SN/A wakeDependents((*topInst).second); 2111062SN/A 2121062SN/A issue((*topInst).second); 2131062SN/A 2141062SN/A memInsts.erase(topInst); 2151062SN/A 2161062SN/A topInst = memInsts.end(); 2171062SN/A} 2181062SN/A 2191062SN/Atemplate <class MemDepPred, class Impl> 2201062SN/Avoid 2211062SN/AMemDepUnit<MemDepPred, Impl>::regsReady(DynInstPtr &inst) 2221062SN/A{ 2231062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Marking registers as ready for " 2241062SN/A "instruction PC %#x.\n", 2251062SN/A inst->readPC()); 2261062SN/A 2271062SN/A InstSeqNum inst_seq_num = inst->seqNum; 2281062SN/A 2291062SN/A Dependency inst_to_find(inst_seq_num); 2301062SN/A 2311062SN/A dep_it_t waiting_inst = waitingInsts.find(inst_to_find); 2321062SN/A 2331062SN/A assert(waiting_inst != waitingInsts.end()); 2341062SN/A 2351062SN/A if ((*waiting_inst).memDepReady) { 2361062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Instruction has its memory " 2371062SN/A "dependencies resolved, adding it to the ready list.\n"); 2381062SN/A 2391062SN/A moveToReady(waiting_inst); 2401062SN/A } else { 2411062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Instruction still waiting on " 2421062SN/A "memory dependency.\n"); 2431062SN/A 2441062SN/A (*waiting_inst).regsReady = true; 2451062SN/A } 2461061SN/A} 2471061SN/A 2481061SN/Atemplate <class MemDepPred, class Impl> 2491062SN/Avoid 2501062SN/AMemDepUnit<MemDepPred, Impl>::nonSpecInstReady(DynInstPtr &inst) 2511061SN/A{ 2521062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Marking non speculative " 2531062SN/A "instruction PC %#x as ready.\n", 2541062SN/A inst->readPC()); 2551062SN/A 2561061SN/A InstSeqNum inst_seq_num = inst->seqNum; 2571061SN/A 2581062SN/A Dependency inst_to_find(inst_seq_num); 2591062SN/A 2601062SN/A dep_it_t waiting_inst = waitingInsts.find(inst_to_find); 2611062SN/A 2621062SN/A assert(waiting_inst != waitingInsts.end()); 2631062SN/A 2641062SN/A moveToReady(waiting_inst); 2651061SN/A} 2661061SN/A 2671061SN/Atemplate <class MemDepPred, class Impl> 2681061SN/Avoid 2691061SN/AMemDepUnit<MemDepPred, Impl>::issue(DynInstPtr &inst) 2701061SN/A{ 2711061SN/A assert(readyInsts.find(inst->seqNum) != readyInsts.end()); 2721061SN/A 2731062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Issuing instruction PC %#x.\n", 2741062SN/A inst->readPC()); 2751062SN/A 2761061SN/A // Remove the instruction from the ready list. 2771061SN/A readyInsts.erase(inst->seqNum); 2781062SN/A 2791062SN/A depPred.issued(inst->readPC(), inst->seqNum, inst->isStore()); 2801061SN/A} 2811061SN/A 2821061SN/Atemplate <class MemDepPred, class Impl> 2831061SN/Avoid 2841061SN/AMemDepUnit<MemDepPred, Impl>::wakeDependents(DynInstPtr &inst) 2851061SN/A{ 2861062SN/A // Only stores have dependents. 2871062SN/A if (!inst->isStore()) { 2881062SN/A return; 2891062SN/A } 2901062SN/A 2911061SN/A // Wake any dependencies. 2921062SN/A sd_it_t sd_it = storeDependents.find(inst->seqNum); 2931061SN/A 2941061SN/A // If there's no entry, then return. Really there should only be 2951061SN/A // no entry if the instruction is a load. 2961062SN/A if (sd_it == storeDependents.end()) { 2971062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Instruction PC %#x, sequence " 2981062SN/A "number %i has no dependents.\n", 2991062SN/A inst->readPC(), inst->seqNum); 3001062SN/A 3011061SN/A return; 3021061SN/A } 3031061SN/A 3041062SN/A for (int i = 0; i < (*sd_it).second.size(); ++i ) { 3051062SN/A dep_it_t woken_inst = (*sd_it).second[i]; 3061061SN/A 3071062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Waking up a dependent inst, " 3081062SN/A "sequence number %i.\n", 3091062SN/A (*woken_inst).seqNum); 3101062SN/A#if 0 3111061SN/A // Should we have reached instructions that are actually squashed, 3121061SN/A // there will be no more useful instructions in this dependency 3131061SN/A // list. Break out early. 3141062SN/A if (waitingInsts.find(woken_inst) == waitingInsts.end()) { 3151061SN/A DPRINTF(MemDepUnit, "MemDepUnit: Dependents on inst PC %#x " 3161061SN/A "are squashed, starting at SN %i. Breaking early.\n", 3171061SN/A inst->readPC(), woken_inst); 3181061SN/A break; 3191061SN/A } 3201062SN/A#endif 3211061SN/A 3221062SN/A if ((*woken_inst).regsReady) { 3231062SN/A moveToReady(woken_inst); 3241062SN/A } else { 3251062SN/A (*woken_inst).memDepReady = true; 3261062SN/A } 3271061SN/A } 3281061SN/A 3291062SN/A storeDependents.erase(sd_it); 3301061SN/A} 3311061SN/A 3321061SN/Atemplate <class MemDepPred, class Impl> 3331061SN/Avoid 3341061SN/AMemDepUnit<MemDepPred, Impl>::squash(const InstSeqNum &squashed_num) 3351061SN/A{ 3361061SN/A 3371062SN/A if (!waitingInsts.empty()) { 3381062SN/A dep_it_t waiting_it = waitingInsts.end(); 3391061SN/A 3401062SN/A --waiting_it; 3411061SN/A 3421061SN/A // Remove entries from the renamed list as long as we haven't reached 3431061SN/A // the end and the entries continue to be younger than the squashed. 3441062SN/A while (!waitingInsts.empty() && 3451062SN/A (*waiting_it).seqNum > squashed_num) 3461061SN/A { 3471062SN/A if (!(*waiting_it).memDepReady && 3481062SN/A (*waiting_it).storeDep != storeDependents.end()) { 3491062SN/A sd_it_t sd_it = (*waiting_it).storeDep; 3501062SN/A 3511062SN/A // Make sure the iterator that the store has pointing 3521062SN/A // back is actually to this instruction. 3531062SN/A assert((*sd_it).second.back() == waiting_it); 3541062SN/A 3551062SN/A // Now remove this from the store's list of dependent 3561062SN/A // instructions. 3571062SN/A (*sd_it).second.pop_back(); 3581062SN/A } 3591062SN/A 3601062SN/A waitingInsts.erase(waiting_it--); 3611061SN/A } 3621061SN/A } 3631061SN/A 3641061SN/A if (!readyInsts.empty()) { 3651061SN/A sn_it_t ready_it = readyInsts.end(); 3661061SN/A 3671061SN/A --ready_it; 3681061SN/A 3691061SN/A // Same for the ready list. 3701061SN/A while (!readyInsts.empty() && 3711061SN/A (*ready_it) > squashed_num) 3721061SN/A { 3731061SN/A readyInsts.erase(ready_it--); 3741061SN/A } 3751061SN/A } 3761061SN/A 3771062SN/A if (!storeDependents.empty()) { 3781062SN/A sd_it_t dep_it = storeDependents.end(); 3791061SN/A 3801061SN/A --dep_it; 3811061SN/A 3821061SN/A // Same for the dependencies list. 3831062SN/A while (!storeDependents.empty() && 3841061SN/A (*dep_it).first > squashed_num) 3851061SN/A { 3861062SN/A // This store's list of dependent instructions should be empty. 3871062SN/A assert((*dep_it).second.empty()); 3881062SN/A 3891062SN/A storeDependents.erase(dep_it--); 3901061SN/A } 3911061SN/A } 3921061SN/A 3931061SN/A // Tell the dependency predictor to squash as well. 3941061SN/A depPred.squash(squashed_num); 3951061SN/A} 3961061SN/A 3971061SN/Atemplate <class MemDepPred, class Impl> 3981061SN/Avoid 3991061SN/AMemDepUnit<MemDepPred, Impl>::violation(DynInstPtr &store_inst, 4001061SN/A DynInstPtr &violating_load) 4011061SN/A{ 4021062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Passing violating PCs to store sets," 4031062SN/A " load: %#x, store: %#x\n", violating_load->readPC(), 4041062SN/A store_inst->readPC()); 4051061SN/A // Tell the memory dependence unit of the violation. 4061061SN/A depPred.violation(violating_load->readPC(), store_inst->readPC()); 4071061SN/A} 4081062SN/A 4091062SN/Atemplate <class MemDepPred, class Impl> 4101062SN/Ainline void 4111062SN/AMemDepUnit<MemDepPred, Impl>::moveToReady(dep_it_t &woken_inst) 4121062SN/A{ 4131062SN/A DPRINTF(MemDepUnit, "MemDepUnit: Adding instruction sequence number %i " 4141062SN/A "to the ready list.\n", (*woken_inst).seqNum); 4151062SN/A 4161062SN/A // Add it to the ready list. 4171062SN/A readyInsts.insert((*woken_inst).seqNum); 4181062SN/A 4191062SN/A // Remove it from the waiting instructions. 4201062SN/A waitingInsts.erase(woken_inst); 4211062SN/A} 422