stride.cc revision 11800
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 5110627Smitch.hayenga@arm.com#include "base/random.hh" 5211800Sbrandon.potter@amd.com#include "base/trace.hh" 538232Snate@binkert.org#include "debug/HWPrefetch.hh" 542810SN/A 5510623Smitch.hayenga@arm.comStridePrefetcher::StridePrefetcher(const StridePrefetcherParams *p) 5610623Smitch.hayenga@arm.com : QueuedPrefetcher(p), 5710623Smitch.hayenga@arm.com maxConf(p->max_conf), 5810623Smitch.hayenga@arm.com threshConf(p->thresh_conf), 5910623Smitch.hayenga@arm.com minConf(p->min_conf), 6010623Smitch.hayenga@arm.com startConf(p->start_conf), 6110623Smitch.hayenga@arm.com pcTableAssoc(p->table_assoc), 6210623Smitch.hayenga@arm.com pcTableSets(p->table_sets), 6310623Smitch.hayenga@arm.com useMasterId(p->use_master_id), 6410771Sstephan.diestelhorst@arm.com degree(p->degree), 6510771Sstephan.diestelhorst@arm.com pcTable(pcTableAssoc, pcTableSets, name()) 6610623Smitch.hayenga@arm.com{ 6710623Smitch.hayenga@arm.com // Don't consult stride prefetcher on instruction accesses 6810623Smitch.hayenga@arm.com onInst = false; 6910623Smitch.hayenga@arm.com 7010623Smitch.hayenga@arm.com assert(isPowerOf2(pcTableSets)); 7110623Smitch.hayenga@arm.com} 7210623Smitch.hayenga@arm.com 7310771Sstephan.diestelhorst@arm.comStridePrefetcher::StrideEntry** 7410771Sstephan.diestelhorst@arm.comStridePrefetcher::PCTable::allocateNewContext(int context) 7510623Smitch.hayenga@arm.com{ 7610771Sstephan.diestelhorst@arm.com auto res = entries.insert(std::make_pair(context, 7710771Sstephan.diestelhorst@arm.com new StrideEntry*[pcTableSets])); 7810771Sstephan.diestelhorst@arm.com auto it = res.first; 7910771Sstephan.diestelhorst@arm.com chatty_assert(res.second, "Allocating an already created context\n"); 8010771Sstephan.diestelhorst@arm.com assert(it->first == context); 8110771Sstephan.diestelhorst@arm.com 8210771Sstephan.diestelhorst@arm.com DPRINTF(HWPrefetch, "Adding context %i with stride entries at %p\n", 8310771Sstephan.diestelhorst@arm.com context, it->second); 8410771Sstephan.diestelhorst@arm.com 8510771Sstephan.diestelhorst@arm.com StrideEntry** entry = it->second; 8610771Sstephan.diestelhorst@arm.com for (int s = 0; s < pcTableSets; s++) { 8710771Sstephan.diestelhorst@arm.com entry[s] = new StrideEntry[pcTableAssoc]; 8810771Sstephan.diestelhorst@arm.com } 8910771Sstephan.diestelhorst@arm.com return entry; 9010771Sstephan.diestelhorst@arm.com} 9110771Sstephan.diestelhorst@arm.com 9210771Sstephan.diestelhorst@arm.comStridePrefetcher::PCTable::~PCTable() { 9310771Sstephan.diestelhorst@arm.com for (auto entry : entries) { 9410623Smitch.hayenga@arm.com for (int s = 0; s < pcTableSets; s++) { 9510771Sstephan.diestelhorst@arm.com delete[] entry.second[s]; 9610623Smitch.hayenga@arm.com } 9710771Sstephan.diestelhorst@arm.com delete[] entry.second; 9810623Smitch.hayenga@arm.com } 9910623Smitch.hayenga@arm.com} 10010623Smitch.hayenga@arm.com 1013861SN/Avoid 10210623Smitch.hayenga@arm.comStridePrefetcher::calculatePrefetch(const PacketPtr &pkt, 10311439SRekai.GonzalezAlberquilla@arm.com std::vector<AddrPriority> &addresses) 1043861SN/A{ 1055875Ssteve.reinhardt@amd.com if (!pkt->req->hasPC()) { 10610623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Ignoring request with no PC.\n"); 1075875Ssteve.reinhardt@amd.com return; 1085875Ssteve.reinhardt@amd.com } 1092810SN/A 11010623Smitch.hayenga@arm.com // Get required packet info 11110623Smitch.hayenga@arm.com Addr pkt_addr = pkt->getAddr(); 11210623Smitch.hayenga@arm.com Addr pc = pkt->req->getPC(); 11310028SGiacomo.Gabrielli@arm.com bool is_secure = pkt->isSecure(); 1148832SAli.Saidi@ARM.com MasterID master_id = useMasterId ? pkt->req->masterId() : 0; 1152810SN/A 11610623Smitch.hayenga@arm.com // Lookup pc-based information 11710623Smitch.hayenga@arm.com StrideEntry *entry; 1183861SN/A 11911321Ssteve.reinhardt@amd.com if (pcTableHit(pc, is_secure, master_id, entry)) { 1205875Ssteve.reinhardt@amd.com // Hit in table 12110623Smitch.hayenga@arm.com int new_stride = pkt_addr - entry->lastAddr; 12210623Smitch.hayenga@arm.com bool stride_match = (new_stride == entry->stride); 1233861SN/A 12410623Smitch.hayenga@arm.com // Adjust confidence for stride entry 1255875Ssteve.reinhardt@amd.com if (stride_match && new_stride != 0) { 12610623Smitch.hayenga@arm.com if (entry->confidence < maxConf) 12710623Smitch.hayenga@arm.com entry->confidence++; 1285875Ssteve.reinhardt@amd.com } else { 12910623Smitch.hayenga@arm.com if (entry->confidence > minConf) 13010623Smitch.hayenga@arm.com entry->confidence--; 13110623Smitch.hayenga@arm.com // If confidence has dropped below the threshold, train new stride 13210623Smitch.hayenga@arm.com if (entry->confidence < threshConf) 13310623Smitch.hayenga@arm.com entry->stride = new_stride; 1345875Ssteve.reinhardt@amd.com } 1353861SN/A 13610623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), " 13710623Smitch.hayenga@arm.com "conf %d\n", pc, pkt_addr, is_secure ? "s" : "ns", new_stride, 13810028SGiacomo.Gabrielli@arm.com stride_match ? "match" : "change", 13910623Smitch.hayenga@arm.com entry->confidence); 1405875Ssteve.reinhardt@amd.com 14110623Smitch.hayenga@arm.com entry->lastAddr = pkt_addr; 1425875Ssteve.reinhardt@amd.com 14310623Smitch.hayenga@arm.com // Abort prefetch generation if below confidence threshold 14410623Smitch.hayenga@arm.com if (entry->confidence < threshConf) 1455875Ssteve.reinhardt@amd.com return; 1465875Ssteve.reinhardt@amd.com 14710623Smitch.hayenga@arm.com // Generate up to degree prefetches 1485875Ssteve.reinhardt@amd.com for (int d = 1; d <= degree; d++) { 14910623Smitch.hayenga@arm.com // Round strides up to atleast 1 cacheline 15010623Smitch.hayenga@arm.com int prefetch_stride = new_stride; 15110623Smitch.hayenga@arm.com if (abs(new_stride) < blkSize) { 15210623Smitch.hayenga@arm.com prefetch_stride = (new_stride < 0) ? -blkSize : blkSize; 15310623Smitch.hayenga@arm.com } 15410623Smitch.hayenga@arm.com 15510623Smitch.hayenga@arm.com Addr new_addr = pkt_addr + d * prefetch_stride; 15610623Smitch.hayenga@arm.com if (samePage(pkt_addr, new_addr)) { 15710623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr); 15811439SRekai.GonzalezAlberquilla@arm.com addresses.push_back(AddrPriority(new_addr, 0)); 15910623Smitch.hayenga@arm.com } else { 16010623Smitch.hayenga@arm.com // Record the number of page crossing prefetches generated 1615875Ssteve.reinhardt@amd.com pfSpanPage += degree - d + 1; 16210623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Ignoring page crossing prefetch.\n"); 1635875Ssteve.reinhardt@amd.com return; 1645875Ssteve.reinhardt@amd.com } 1655875Ssteve.reinhardt@amd.com } 1665875Ssteve.reinhardt@amd.com } else { 1675875Ssteve.reinhardt@amd.com // Miss in table 16810623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Miss: PC %x pkt_addr %x (%s)\n", pc, pkt_addr, 16910028SGiacomo.Gabrielli@arm.com is_secure ? "s" : "ns"); 1705875Ssteve.reinhardt@amd.com 17110623Smitch.hayenga@arm.com StrideEntry* entry = pcTableVictim(pc, master_id); 17210623Smitch.hayenga@arm.com entry->instAddr = pc; 17310623Smitch.hayenga@arm.com entry->lastAddr = pkt_addr; 17410623Smitch.hayenga@arm.com entry->isSecure= is_secure; 17510623Smitch.hayenga@arm.com entry->stride = 0; 17610623Smitch.hayenga@arm.com entry->confidence = startConf; 1775875Ssteve.reinhardt@amd.com } 1783861SN/A} 1798831Smrinmoy.ghosh@arm.com 18010623Smitch.hayenga@arm.cominline Addr 18110623Smitch.hayenga@arm.comStridePrefetcher::pcHash(Addr pc) const 18210623Smitch.hayenga@arm.com{ 18310623Smitch.hayenga@arm.com Addr hash1 = pc >> 1; 18410623Smitch.hayenga@arm.com Addr hash2 = hash1 >> floorLog2(pcTableSets); 18510623Smitch.hayenga@arm.com return (hash1 ^ hash2) & (Addr)(pcTableSets - 1); 18610623Smitch.hayenga@arm.com} 18710623Smitch.hayenga@arm.com 18810623Smitch.hayenga@arm.cominline StridePrefetcher::StrideEntry* 18910623Smitch.hayenga@arm.comStridePrefetcher::pcTableVictim(Addr pc, int master_id) 19010623Smitch.hayenga@arm.com{ 19110623Smitch.hayenga@arm.com // Rand replacement for now 19210623Smitch.hayenga@arm.com int set = pcHash(pc); 19310627Smitch.hayenga@arm.com int way = random_mt.random<int>(0, pcTableAssoc - 1); 19410623Smitch.hayenga@arm.com 19510623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Victimizing lookup table[%d][%d].\n", set, way); 19610623Smitch.hayenga@arm.com return &pcTable[master_id][set][way]; 19710623Smitch.hayenga@arm.com} 19810623Smitch.hayenga@arm.com 19910623Smitch.hayenga@arm.cominline bool 20010623Smitch.hayenga@arm.comStridePrefetcher::pcTableHit(Addr pc, bool is_secure, int master_id, 20110623Smitch.hayenga@arm.com StrideEntry* &entry) 20210623Smitch.hayenga@arm.com{ 20310623Smitch.hayenga@arm.com int set = pcHash(pc); 20410623Smitch.hayenga@arm.com StrideEntry* set_entries = pcTable[master_id][set]; 20510623Smitch.hayenga@arm.com for (int way = 0; way < pcTableAssoc; way++) { 20610623Smitch.hayenga@arm.com // Search ways for match 20710623Smitch.hayenga@arm.com if (set_entries[way].instAddr == pc && 20810623Smitch.hayenga@arm.com set_entries[way].isSecure == is_secure) { 20910623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Lookup hit table[%d][%d].\n", set, way); 21010623Smitch.hayenga@arm.com entry = &set_entries[way]; 21110623Smitch.hayenga@arm.com return true; 21210623Smitch.hayenga@arm.com } 21310623Smitch.hayenga@arm.com } 21410623Smitch.hayenga@arm.com return false; 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