12810SN/A/* 213427Sodanrc@yahoo.com.br * Copyright (c) 2018 Inria 310771Sstephan.diestelhorst@arm.com * Copyright (c) 2012-2013, 2015 ARM Limited 410028SGiacomo.Gabrielli@arm.com * All rights reserved 510028SGiacomo.Gabrielli@arm.com * 610028SGiacomo.Gabrielli@arm.com * The license below extends only to copyright in the software and shall 710028SGiacomo.Gabrielli@arm.com * not be construed as granting a license to any other intellectual 810028SGiacomo.Gabrielli@arm.com * property including but not limited to intellectual property relating 910028SGiacomo.Gabrielli@arm.com * to a hardware implementation of the functionality of the software 1010028SGiacomo.Gabrielli@arm.com * licensed hereunder. You may use the software subject to the license 1110028SGiacomo.Gabrielli@arm.com * terms below provided that you ensure that this notice is replicated 1210028SGiacomo.Gabrielli@arm.com * unmodified and in its entirety in all distributions of the software, 1310028SGiacomo.Gabrielli@arm.com * modified or unmodified, in source code or in binary form. 1410028SGiacomo.Gabrielli@arm.com * 152810SN/A * Copyright (c) 2005 The Regents of The University of Michigan 162810SN/A * All rights reserved. 172810SN/A * 182810SN/A * Redistribution and use in source and binary forms, with or without 192810SN/A * modification, are permitted provided that the following conditions are 202810SN/A * met: redistributions of source code must retain the above copyright 212810SN/A * notice, this list of conditions and the following disclaimer; 222810SN/A * redistributions in binary form must reproduce the above copyright 232810SN/A * notice, this list of conditions and the following disclaimer in the 242810SN/A * documentation and/or other materials provided with the distribution; 252810SN/A * neither the name of the copyright holders nor the names of its 262810SN/A * contributors may be used to endorse or promote products derived from 272810SN/A * this software without specific prior written permission. 282810SN/A * 292810SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 302810SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 312810SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 322810SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 332810SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 342810SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 352810SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 362810SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 372810SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 382810SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 392810SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 402810SN/A * 412810SN/A * Authors: Ron Dreslinski 422810SN/A * Steve Reinhardt 4313427Sodanrc@yahoo.com.br * Daniel Carvalho 442810SN/A */ 452810SN/A 462810SN/A/** 472810SN/A * @file 482810SN/A * Stride Prefetcher template instantiations. 492810SN/A */ 502810SN/A 5111793Sbrandon.potter@amd.com#include "mem/cache/prefetch/stride.hh" 5211793Sbrandon.potter@amd.com 5312727Snikos.nikoleris@arm.com#include <cassert> 5412727Snikos.nikoleris@arm.com 5512727Snikos.nikoleris@arm.com#include "base/intmath.hh" 5612727Snikos.nikoleris@arm.com#include "base/logging.hh" 5710627Smitch.hayenga@arm.com#include "base/random.hh" 5811800Sbrandon.potter@amd.com#include "base/trace.hh" 598232Snate@binkert.org#include "debug/HWPrefetch.hh" 6013427Sodanrc@yahoo.com.br#include "mem/cache/replacement_policies/base.hh" 6112727Snikos.nikoleris@arm.com#include "params/StridePrefetcher.hh" 622810SN/A 6313426Sodanrc@yahoo.com.brStridePrefetcher::StrideEntry::StrideEntry() 6413426Sodanrc@yahoo.com.br{ 6513426Sodanrc@yahoo.com.br invalidate(); 6613426Sodanrc@yahoo.com.br} 6713426Sodanrc@yahoo.com.br 6813426Sodanrc@yahoo.com.brvoid 6913426Sodanrc@yahoo.com.brStridePrefetcher::StrideEntry::invalidate() 7013426Sodanrc@yahoo.com.br{ 7113426Sodanrc@yahoo.com.br instAddr = 0; 7213426Sodanrc@yahoo.com.br lastAddr = 0; 7313426Sodanrc@yahoo.com.br isSecure = false; 7413426Sodanrc@yahoo.com.br stride = 0; 7513426Sodanrc@yahoo.com.br confidence = 0; 7613426Sodanrc@yahoo.com.br} 7713426Sodanrc@yahoo.com.br 7810623Smitch.hayenga@arm.comStridePrefetcher::StridePrefetcher(const StridePrefetcherParams *p) 7910623Smitch.hayenga@arm.com : QueuedPrefetcher(p), 8010623Smitch.hayenga@arm.com maxConf(p->max_conf), 8110623Smitch.hayenga@arm.com threshConf(p->thresh_conf), 8210623Smitch.hayenga@arm.com minConf(p->min_conf), 8310623Smitch.hayenga@arm.com startConf(p->start_conf), 8410623Smitch.hayenga@arm.com pcTableAssoc(p->table_assoc), 8510623Smitch.hayenga@arm.com pcTableSets(p->table_sets), 8610623Smitch.hayenga@arm.com useMasterId(p->use_master_id), 8713427Sodanrc@yahoo.com.br degree(p->degree), 8813427Sodanrc@yahoo.com.br replacementPolicy(p->replacement_policy) 8910623Smitch.hayenga@arm.com{ 9010623Smitch.hayenga@arm.com assert(isPowerOf2(pcTableSets)); 9110623Smitch.hayenga@arm.com} 9210623Smitch.hayenga@arm.com 9313425Sodanrc@yahoo.com.brStridePrefetcher::PCTable* 9413425Sodanrc@yahoo.com.brStridePrefetcher::findTable(int context) 9510623Smitch.hayenga@arm.com{ 9613425Sodanrc@yahoo.com.br // Check if table for given context exists 9713425Sodanrc@yahoo.com.br auto it = pcTables.find(context); 9813425Sodanrc@yahoo.com.br if (it != pcTables.end()) 9913425Sodanrc@yahoo.com.br return &it->second; 10013425Sodanrc@yahoo.com.br 10113425Sodanrc@yahoo.com.br // If table does not exist yet, create one 10213425Sodanrc@yahoo.com.br return allocateNewContext(context); 10313425Sodanrc@yahoo.com.br} 10413425Sodanrc@yahoo.com.br 10513425Sodanrc@yahoo.com.brStridePrefetcher::PCTable* 10613425Sodanrc@yahoo.com.brStridePrefetcher::allocateNewContext(int context) 10713425Sodanrc@yahoo.com.br{ 10813425Sodanrc@yahoo.com.br // Create new table 10913425Sodanrc@yahoo.com.br auto insertion_result = pcTables.insert(std::make_pair(context, 11013427Sodanrc@yahoo.com.br PCTable(pcTableAssoc, pcTableSets, name(), replacementPolicy))); 11110771Sstephan.diestelhorst@arm.com 11213424Sodanrc@yahoo.com.br DPRINTF(HWPrefetch, "Adding context %i with stride entries\n", context); 11310771Sstephan.diestelhorst@arm.com 11413425Sodanrc@yahoo.com.br // Get iterator to new pc table, and then return a pointer to the new table 11513425Sodanrc@yahoo.com.br return &(insertion_result.first->second); 11613425Sodanrc@yahoo.com.br} 11713425Sodanrc@yahoo.com.br 11813427Sodanrc@yahoo.com.brStridePrefetcher::PCTable::PCTable(int assoc, int sets, const std::string name, 11913427Sodanrc@yahoo.com.br BaseReplacementPolicy* replacementPolicy) 12013427Sodanrc@yahoo.com.br : pcTableSets(sets), _name(name), entries(pcTableSets), 12113427Sodanrc@yahoo.com.br replacementPolicy(replacementPolicy) 12213425Sodanrc@yahoo.com.br{ 12313427Sodanrc@yahoo.com.br for (int set = 0; set < sets; set++) { 12413427Sodanrc@yahoo.com.br entries[set].resize(assoc); 12513427Sodanrc@yahoo.com.br for (int way = 0; way < assoc; way++) { 12613427Sodanrc@yahoo.com.br // Inform the entry its position 12713427Sodanrc@yahoo.com.br entries[set][way].setPosition(set, way); 12813427Sodanrc@yahoo.com.br 12913427Sodanrc@yahoo.com.br // Initialize replacement policy data 13013427Sodanrc@yahoo.com.br entries[set][way].replacementData = 13113427Sodanrc@yahoo.com.br replacementPolicy->instantiateEntry(); 13213427Sodanrc@yahoo.com.br } 13310771Sstephan.diestelhorst@arm.com } 13410771Sstephan.diestelhorst@arm.com} 13510771Sstephan.diestelhorst@arm.com 13613424Sodanrc@yahoo.com.brStridePrefetcher::PCTable::~PCTable() 13713424Sodanrc@yahoo.com.br{ 13810623Smitch.hayenga@arm.com} 13910623Smitch.hayenga@arm.com 1403861SN/Avoid 14113551Sjavier.bueno@metempsy.comStridePrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 14211439SRekai.GonzalezAlberquilla@arm.com std::vector<AddrPriority> &addresses) 1433861SN/A{ 14413551Sjavier.bueno@metempsy.com if (!pfi.hasPC()) { 14510623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Ignoring request with no PC.\n"); 1465875Ssteve.reinhardt@amd.com return; 1475875Ssteve.reinhardt@amd.com } 1482810SN/A 14910623Smitch.hayenga@arm.com // Get required packet info 15013551Sjavier.bueno@metempsy.com Addr pf_addr = pfi.getAddr(); 15113551Sjavier.bueno@metempsy.com Addr pc = pfi.getPC(); 15213551Sjavier.bueno@metempsy.com bool is_secure = pfi.isSecure(); 15313551Sjavier.bueno@metempsy.com MasterID master_id = useMasterId ? pfi.getMasterId() : 0; 1542810SN/A 15513425Sodanrc@yahoo.com.br // Get corresponding pc table 15613425Sodanrc@yahoo.com.br PCTable* pcTable = findTable(master_id); 15713425Sodanrc@yahoo.com.br 15813423Sodanrc@yahoo.com.br // Search for entry in the pc table 15913425Sodanrc@yahoo.com.br StrideEntry *entry = pcTable->findEntry(pc, is_secure); 1603861SN/A 16113423Sodanrc@yahoo.com.br if (entry != nullptr) { 1625875Ssteve.reinhardt@amd.com // Hit in table 16313551Sjavier.bueno@metempsy.com int new_stride = pf_addr - entry->lastAddr; 16410623Smitch.hayenga@arm.com bool stride_match = (new_stride == entry->stride); 1653861SN/A 16610623Smitch.hayenga@arm.com // Adjust confidence for stride entry 1675875Ssteve.reinhardt@amd.com if (stride_match && new_stride != 0) { 16810623Smitch.hayenga@arm.com if (entry->confidence < maxConf) 16910623Smitch.hayenga@arm.com entry->confidence++; 1705875Ssteve.reinhardt@amd.com } else { 17110623Smitch.hayenga@arm.com if (entry->confidence > minConf) 17210623Smitch.hayenga@arm.com entry->confidence--; 17310623Smitch.hayenga@arm.com // If confidence has dropped below the threshold, train new stride 17410623Smitch.hayenga@arm.com if (entry->confidence < threshConf) 17510623Smitch.hayenga@arm.com entry->stride = new_stride; 1765875Ssteve.reinhardt@amd.com } 1773861SN/A 17810623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), " 17913551Sjavier.bueno@metempsy.com "conf %d\n", pc, pf_addr, is_secure ? "s" : "ns", 18013551Sjavier.bueno@metempsy.com new_stride, stride_match ? "match" : "change", 18110623Smitch.hayenga@arm.com entry->confidence); 1825875Ssteve.reinhardt@amd.com 18313551Sjavier.bueno@metempsy.com entry->lastAddr = pf_addr; 1845875Ssteve.reinhardt@amd.com 18510623Smitch.hayenga@arm.com // Abort prefetch generation if below confidence threshold 18610623Smitch.hayenga@arm.com if (entry->confidence < threshConf) 1875875Ssteve.reinhardt@amd.com return; 1885875Ssteve.reinhardt@amd.com 18910623Smitch.hayenga@arm.com // Generate up to degree prefetches 1905875Ssteve.reinhardt@amd.com for (int d = 1; d <= degree; d++) { 19110623Smitch.hayenga@arm.com // Round strides up to atleast 1 cacheline 19210623Smitch.hayenga@arm.com int prefetch_stride = new_stride; 19310623Smitch.hayenga@arm.com if (abs(new_stride) < blkSize) { 19410623Smitch.hayenga@arm.com prefetch_stride = (new_stride < 0) ? -blkSize : blkSize; 19510623Smitch.hayenga@arm.com } 19610623Smitch.hayenga@arm.com 19713551Sjavier.bueno@metempsy.com Addr new_addr = pf_addr + d * prefetch_stride; 19813552Sjavier.bueno@metempsy.com addresses.push_back(AddrPriority(new_addr, 0)); 1995875Ssteve.reinhardt@amd.com } 2005875Ssteve.reinhardt@amd.com } else { 2015875Ssteve.reinhardt@amd.com // Miss in table 20213551Sjavier.bueno@metempsy.com DPRINTF(HWPrefetch, "Miss: PC %x pkt_addr %x (%s)\n", pc, pf_addr, 20310028SGiacomo.Gabrielli@arm.com is_secure ? "s" : "ns"); 2045875Ssteve.reinhardt@amd.com 20513425Sodanrc@yahoo.com.br StrideEntry* entry = pcTable->findVictim(pc); 20613426Sodanrc@yahoo.com.br 20713426Sodanrc@yahoo.com.br // Invalidate victim 20813426Sodanrc@yahoo.com.br entry->invalidate(); 20913427Sodanrc@yahoo.com.br replacementPolicy->invalidate(entry->replacementData); 21013426Sodanrc@yahoo.com.br 21113426Sodanrc@yahoo.com.br // Insert new entry's data 21210623Smitch.hayenga@arm.com entry->instAddr = pc; 21313551Sjavier.bueno@metempsy.com entry->lastAddr = pf_addr; 21413427Sodanrc@yahoo.com.br entry->isSecure = is_secure; 21510623Smitch.hayenga@arm.com entry->confidence = startConf; 21613427Sodanrc@yahoo.com.br replacementPolicy->reset(entry->replacementData); 2175875Ssteve.reinhardt@amd.com } 2183861SN/A} 2198831Smrinmoy.ghosh@arm.com 22010623Smitch.hayenga@arm.cominline Addr 22113425Sodanrc@yahoo.com.brStridePrefetcher::PCTable::pcHash(Addr pc) const 22210623Smitch.hayenga@arm.com{ 22310623Smitch.hayenga@arm.com Addr hash1 = pc >> 1; 22410623Smitch.hayenga@arm.com Addr hash2 = hash1 >> floorLog2(pcTableSets); 22510623Smitch.hayenga@arm.com return (hash1 ^ hash2) & (Addr)(pcTableSets - 1); 22610623Smitch.hayenga@arm.com} 22710623Smitch.hayenga@arm.com 22810623Smitch.hayenga@arm.cominline StridePrefetcher::StrideEntry* 22913425Sodanrc@yahoo.com.brStridePrefetcher::PCTable::findVictim(Addr pc) 23010623Smitch.hayenga@arm.com{ 23110623Smitch.hayenga@arm.com // Rand replacement for now 23210623Smitch.hayenga@arm.com int set = pcHash(pc); 23310623Smitch.hayenga@arm.com 23413427Sodanrc@yahoo.com.br // Get possible entries to be victimized 23513427Sodanrc@yahoo.com.br std::vector<ReplaceableEntry*> possible_entries; 23613427Sodanrc@yahoo.com.br for (auto& entry : entries[set]) { 23713427Sodanrc@yahoo.com.br possible_entries.push_back(&entry); 23813427Sodanrc@yahoo.com.br } 23913427Sodanrc@yahoo.com.br 24013427Sodanrc@yahoo.com.br // Choose victim based on replacement policy 24113427Sodanrc@yahoo.com.br StrideEntry* victim = static_cast<StrideEntry*>( 24213427Sodanrc@yahoo.com.br replacementPolicy->getVictim(possible_entries)); 24313427Sodanrc@yahoo.com.br 24413427Sodanrc@yahoo.com.br DPRINTF(HWPrefetch, "Victimizing lookup table[%d][%d].\n", 24513427Sodanrc@yahoo.com.br victim->getSet(), victim->getWay()); 24613427Sodanrc@yahoo.com.br 24713427Sodanrc@yahoo.com.br return victim; 24810623Smitch.hayenga@arm.com} 24910623Smitch.hayenga@arm.com 25013423Sodanrc@yahoo.com.brinline StridePrefetcher::StrideEntry* 25113425Sodanrc@yahoo.com.brStridePrefetcher::PCTable::findEntry(Addr pc, bool is_secure) 25210623Smitch.hayenga@arm.com{ 25310623Smitch.hayenga@arm.com int set = pcHash(pc); 25413427Sodanrc@yahoo.com.br for (auto& entry : entries[set]) { 25510623Smitch.hayenga@arm.com // Search ways for match 25613427Sodanrc@yahoo.com.br if ((entry.instAddr == pc) && (entry.isSecure == is_secure)) { 25713427Sodanrc@yahoo.com.br DPRINTF(HWPrefetch, "Lookup hit table[%d][%d].\n", entry.getSet(), 25813427Sodanrc@yahoo.com.br entry.getWay()); 25913427Sodanrc@yahoo.com.br replacementPolicy->touch(entry.replacementData); 26013427Sodanrc@yahoo.com.br return &entry; 26110623Smitch.hayenga@arm.com } 26210623Smitch.hayenga@arm.com } 26313423Sodanrc@yahoo.com.br return nullptr; 26410623Smitch.hayenga@arm.com} 2658831Smrinmoy.ghosh@arm.com 2668831Smrinmoy.ghosh@arm.comStridePrefetcher* 2678831Smrinmoy.ghosh@arm.comStridePrefetcherParams::create() 2688831Smrinmoy.ghosh@arm.com{ 26910623Smitch.hayenga@arm.com return new StridePrefetcher(this); 2708831Smrinmoy.ghosh@arm.com} 271