stride.cc revision 13423
12810SN/A/* 210771Sstephan.diestelhorst@arm.com * Copyright (c) 2012-2013, 2015 ARM Limited 310028SGiacomo.Gabrielli@arm.com * All rights reserved 410028SGiacomo.Gabrielli@arm.com * 510028SGiacomo.Gabrielli@arm.com * The license below extends only to copyright in the software and shall 610028SGiacomo.Gabrielli@arm.com * not be construed as granting a license to any other intellectual 710028SGiacomo.Gabrielli@arm.com * property including but not limited to intellectual property relating 810028SGiacomo.Gabrielli@arm.com * to a hardware implementation of the functionality of the software 910028SGiacomo.Gabrielli@arm.com * licensed hereunder. You may use the software subject to the license 1010028SGiacomo.Gabrielli@arm.com * terms below provided that you ensure that this notice is replicated 1110028SGiacomo.Gabrielli@arm.com * unmodified and in its entirety in all distributions of the software, 1210028SGiacomo.Gabrielli@arm.com * modified or unmodified, in source code or in binary form. 1310028SGiacomo.Gabrielli@arm.com * 142810SN/A * Copyright (c) 2005 The Regents of The University of Michigan 152810SN/A * All rights reserved. 162810SN/A * 172810SN/A * Redistribution and use in source and binary forms, with or without 182810SN/A * modification, are permitted provided that the following conditions are 192810SN/A * met: redistributions of source code must retain the above copyright 202810SN/A * notice, this list of conditions and the following disclaimer; 212810SN/A * redistributions in binary form must reproduce the above copyright 222810SN/A * notice, this list of conditions and the following disclaimer in the 232810SN/A * documentation and/or other materials provided with the distribution; 242810SN/A * neither the name of the copyright holders nor the names of its 252810SN/A * contributors may be used to endorse or promote products derived from 262810SN/A * this software without specific prior written permission. 272810SN/A * 282810SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 292810SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 302810SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 312810SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 322810SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 332810SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 342810SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 352810SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 362810SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 372810SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 382810SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 392810SN/A * 402810SN/A * Authors: Ron Dreslinski 412810SN/A * Steve Reinhardt 422810SN/A */ 432810SN/A 442810SN/A/** 452810SN/A * @file 462810SN/A * Stride Prefetcher template instantiations. 472810SN/A */ 482810SN/A 4911793Sbrandon.potter@amd.com#include "mem/cache/prefetch/stride.hh" 5011793Sbrandon.potter@amd.com 5112727Snikos.nikoleris@arm.com#include <cassert> 5212727Snikos.nikoleris@arm.com 5312727Snikos.nikoleris@arm.com#include "base/intmath.hh" 5412727Snikos.nikoleris@arm.com#include "base/logging.hh" 5510627Smitch.hayenga@arm.com#include "base/random.hh" 5611800Sbrandon.potter@amd.com#include "base/trace.hh" 578232Snate@binkert.org#include "debug/HWPrefetch.hh" 5812727Snikos.nikoleris@arm.com#include "params/StridePrefetcher.hh" 592810SN/A 6010623Smitch.hayenga@arm.comStridePrefetcher::StridePrefetcher(const StridePrefetcherParams *p) 6110623Smitch.hayenga@arm.com : QueuedPrefetcher(p), 6210623Smitch.hayenga@arm.com maxConf(p->max_conf), 6310623Smitch.hayenga@arm.com threshConf(p->thresh_conf), 6410623Smitch.hayenga@arm.com minConf(p->min_conf), 6510623Smitch.hayenga@arm.com startConf(p->start_conf), 6610623Smitch.hayenga@arm.com pcTableAssoc(p->table_assoc), 6710623Smitch.hayenga@arm.com pcTableSets(p->table_sets), 6810623Smitch.hayenga@arm.com useMasterId(p->use_master_id), 6910771Sstephan.diestelhorst@arm.com degree(p->degree), 7010771Sstephan.diestelhorst@arm.com pcTable(pcTableAssoc, pcTableSets, name()) 7110623Smitch.hayenga@arm.com{ 7210623Smitch.hayenga@arm.com assert(isPowerOf2(pcTableSets)); 7310623Smitch.hayenga@arm.com} 7410623Smitch.hayenga@arm.com 7510771Sstephan.diestelhorst@arm.comStridePrefetcher::StrideEntry** 7610771Sstephan.diestelhorst@arm.comStridePrefetcher::PCTable::allocateNewContext(int context) 7710623Smitch.hayenga@arm.com{ 7810771Sstephan.diestelhorst@arm.com auto res = entries.insert(std::make_pair(context, 7910771Sstephan.diestelhorst@arm.com new StrideEntry*[pcTableSets])); 8010771Sstephan.diestelhorst@arm.com auto it = res.first; 8110771Sstephan.diestelhorst@arm.com chatty_assert(res.second, "Allocating an already created context\n"); 8210771Sstephan.diestelhorst@arm.com assert(it->first == context); 8310771Sstephan.diestelhorst@arm.com 8410771Sstephan.diestelhorst@arm.com DPRINTF(HWPrefetch, "Adding context %i with stride entries at %p\n", 8510771Sstephan.diestelhorst@arm.com context, it->second); 8610771Sstephan.diestelhorst@arm.com 8710771Sstephan.diestelhorst@arm.com StrideEntry** entry = it->second; 8810771Sstephan.diestelhorst@arm.com for (int s = 0; s < pcTableSets; s++) { 8910771Sstephan.diestelhorst@arm.com entry[s] = new StrideEntry[pcTableAssoc]; 9010771Sstephan.diestelhorst@arm.com } 9110771Sstephan.diestelhorst@arm.com return entry; 9210771Sstephan.diestelhorst@arm.com} 9310771Sstephan.diestelhorst@arm.com 9410771Sstephan.diestelhorst@arm.comStridePrefetcher::PCTable::~PCTable() { 9510771Sstephan.diestelhorst@arm.com for (auto entry : entries) { 9610623Smitch.hayenga@arm.com for (int s = 0; s < pcTableSets; s++) { 9710771Sstephan.diestelhorst@arm.com delete[] entry.second[s]; 9810623Smitch.hayenga@arm.com } 9910771Sstephan.diestelhorst@arm.com delete[] entry.second; 10010623Smitch.hayenga@arm.com } 10110623Smitch.hayenga@arm.com} 10210623Smitch.hayenga@arm.com 1033861SN/Avoid 10410623Smitch.hayenga@arm.comStridePrefetcher::calculatePrefetch(const PacketPtr &pkt, 10511439SRekai.GonzalezAlberquilla@arm.com std::vector<AddrPriority> &addresses) 1063861SN/A{ 1075875Ssteve.reinhardt@amd.com if (!pkt->req->hasPC()) { 10810623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Ignoring request with no PC.\n"); 1095875Ssteve.reinhardt@amd.com return; 1105875Ssteve.reinhardt@amd.com } 1112810SN/A 11210623Smitch.hayenga@arm.com // Get required packet info 11310623Smitch.hayenga@arm.com Addr pkt_addr = pkt->getAddr(); 11410623Smitch.hayenga@arm.com Addr pc = pkt->req->getPC(); 11510028SGiacomo.Gabrielli@arm.com bool is_secure = pkt->isSecure(); 1168832SAli.Saidi@ARM.com MasterID master_id = useMasterId ? pkt->req->masterId() : 0; 1172810SN/A 11813423Sodanrc@yahoo.com.br // Search for entry in the pc table 11913423Sodanrc@yahoo.com.br StrideEntry *entry = findEntry(pc, is_secure, master_id); 1203861SN/A 12113423Sodanrc@yahoo.com.br if (entry != nullptr) { 1225875Ssteve.reinhardt@amd.com // Hit in table 12310623Smitch.hayenga@arm.com int new_stride = pkt_addr - entry->lastAddr; 12410623Smitch.hayenga@arm.com bool stride_match = (new_stride == entry->stride); 1253861SN/A 12610623Smitch.hayenga@arm.com // Adjust confidence for stride entry 1275875Ssteve.reinhardt@amd.com if (stride_match && new_stride != 0) { 12810623Smitch.hayenga@arm.com if (entry->confidence < maxConf) 12910623Smitch.hayenga@arm.com entry->confidence++; 1305875Ssteve.reinhardt@amd.com } else { 13110623Smitch.hayenga@arm.com if (entry->confidence > minConf) 13210623Smitch.hayenga@arm.com entry->confidence--; 13310623Smitch.hayenga@arm.com // If confidence has dropped below the threshold, train new stride 13410623Smitch.hayenga@arm.com if (entry->confidence < threshConf) 13510623Smitch.hayenga@arm.com entry->stride = new_stride; 1365875Ssteve.reinhardt@amd.com } 1373861SN/A 13810623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), " 13910623Smitch.hayenga@arm.com "conf %d\n", pc, pkt_addr, is_secure ? "s" : "ns", new_stride, 14010028SGiacomo.Gabrielli@arm.com stride_match ? "match" : "change", 14110623Smitch.hayenga@arm.com entry->confidence); 1425875Ssteve.reinhardt@amd.com 14310623Smitch.hayenga@arm.com entry->lastAddr = pkt_addr; 1445875Ssteve.reinhardt@amd.com 14510623Smitch.hayenga@arm.com // Abort prefetch generation if below confidence threshold 14610623Smitch.hayenga@arm.com if (entry->confidence < threshConf) 1475875Ssteve.reinhardt@amd.com return; 1485875Ssteve.reinhardt@amd.com 14910623Smitch.hayenga@arm.com // Generate up to degree prefetches 1505875Ssteve.reinhardt@amd.com for (int d = 1; d <= degree; d++) { 15110623Smitch.hayenga@arm.com // Round strides up to atleast 1 cacheline 15210623Smitch.hayenga@arm.com int prefetch_stride = new_stride; 15310623Smitch.hayenga@arm.com if (abs(new_stride) < blkSize) { 15410623Smitch.hayenga@arm.com prefetch_stride = (new_stride < 0) ? -blkSize : blkSize; 15510623Smitch.hayenga@arm.com } 15610623Smitch.hayenga@arm.com 15710623Smitch.hayenga@arm.com Addr new_addr = pkt_addr + d * prefetch_stride; 15810623Smitch.hayenga@arm.com if (samePage(pkt_addr, new_addr)) { 15910623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr); 16011439SRekai.GonzalezAlberquilla@arm.com addresses.push_back(AddrPriority(new_addr, 0)); 16110623Smitch.hayenga@arm.com } else { 16210623Smitch.hayenga@arm.com // Record the number of page crossing prefetches generated 1635875Ssteve.reinhardt@amd.com pfSpanPage += degree - d + 1; 16410623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Ignoring page crossing prefetch.\n"); 1655875Ssteve.reinhardt@amd.com return; 1665875Ssteve.reinhardt@amd.com } 1675875Ssteve.reinhardt@amd.com } 1685875Ssteve.reinhardt@amd.com } else { 1695875Ssteve.reinhardt@amd.com // Miss in table 17010623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Miss: PC %x pkt_addr %x (%s)\n", pc, pkt_addr, 17110028SGiacomo.Gabrielli@arm.com is_secure ? "s" : "ns"); 1725875Ssteve.reinhardt@amd.com 17310623Smitch.hayenga@arm.com StrideEntry* entry = pcTableVictim(pc, master_id); 17410623Smitch.hayenga@arm.com entry->instAddr = pc; 17510623Smitch.hayenga@arm.com entry->lastAddr = pkt_addr; 17610623Smitch.hayenga@arm.com entry->isSecure= is_secure; 17710623Smitch.hayenga@arm.com entry->stride = 0; 17810623Smitch.hayenga@arm.com entry->confidence = startConf; 1795875Ssteve.reinhardt@amd.com } 1803861SN/A} 1818831Smrinmoy.ghosh@arm.com 18210623Smitch.hayenga@arm.cominline Addr 18310623Smitch.hayenga@arm.comStridePrefetcher::pcHash(Addr pc) const 18410623Smitch.hayenga@arm.com{ 18510623Smitch.hayenga@arm.com Addr hash1 = pc >> 1; 18610623Smitch.hayenga@arm.com Addr hash2 = hash1 >> floorLog2(pcTableSets); 18710623Smitch.hayenga@arm.com return (hash1 ^ hash2) & (Addr)(pcTableSets - 1); 18810623Smitch.hayenga@arm.com} 18910623Smitch.hayenga@arm.com 19010623Smitch.hayenga@arm.cominline StridePrefetcher::StrideEntry* 19110623Smitch.hayenga@arm.comStridePrefetcher::pcTableVictim(Addr pc, int master_id) 19210623Smitch.hayenga@arm.com{ 19310623Smitch.hayenga@arm.com // Rand replacement for now 19410623Smitch.hayenga@arm.com int set = pcHash(pc); 19510627Smitch.hayenga@arm.com int way = random_mt.random<int>(0, pcTableAssoc - 1); 19610623Smitch.hayenga@arm.com 19710623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Victimizing lookup table[%d][%d].\n", set, way); 19810623Smitch.hayenga@arm.com return &pcTable[master_id][set][way]; 19910623Smitch.hayenga@arm.com} 20010623Smitch.hayenga@arm.com 20113423Sodanrc@yahoo.com.brinline StridePrefetcher::StrideEntry* 20213423Sodanrc@yahoo.com.brStridePrefetcher::findEntry(Addr pc, bool is_secure, int master_id) 20310623Smitch.hayenga@arm.com{ 20410623Smitch.hayenga@arm.com int set = pcHash(pc); 20510623Smitch.hayenga@arm.com StrideEntry* set_entries = pcTable[master_id][set]; 20610623Smitch.hayenga@arm.com for (int way = 0; way < pcTableAssoc; way++) { 20713423Sodanrc@yahoo.com.br StrideEntry* entry = &set_entries[way]; 20810623Smitch.hayenga@arm.com // Search ways for match 20913423Sodanrc@yahoo.com.br if ((entry->instAddr == pc) && (entry->isSecure == is_secure)) { 21010623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Lookup hit table[%d][%d].\n", set, way); 21113423Sodanrc@yahoo.com.br return entry; 21210623Smitch.hayenga@arm.com } 21310623Smitch.hayenga@arm.com } 21413423Sodanrc@yahoo.com.br return nullptr; 21510623Smitch.hayenga@arm.com} 2168831Smrinmoy.ghosh@arm.com 2178831Smrinmoy.ghosh@arm.comStridePrefetcher* 2188831Smrinmoy.ghosh@arm.comStridePrefetcherParams::create() 2198831Smrinmoy.ghosh@arm.com{ 22010623Smitch.hayenga@arm.com return new StridePrefetcher(this); 2218831Smrinmoy.ghosh@arm.com} 222