stride.cc revision 11793
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" 528232Snate@binkert.org#include "debug/HWPrefetch.hh" 532810SN/A 5410623Smitch.hayenga@arm.comStridePrefetcher::StridePrefetcher(const StridePrefetcherParams *p) 5510623Smitch.hayenga@arm.com : QueuedPrefetcher(p), 5610623Smitch.hayenga@arm.com maxConf(p->max_conf), 5710623Smitch.hayenga@arm.com threshConf(p->thresh_conf), 5810623Smitch.hayenga@arm.com minConf(p->min_conf), 5910623Smitch.hayenga@arm.com startConf(p->start_conf), 6010623Smitch.hayenga@arm.com pcTableAssoc(p->table_assoc), 6110623Smitch.hayenga@arm.com pcTableSets(p->table_sets), 6210623Smitch.hayenga@arm.com useMasterId(p->use_master_id), 6310771Sstephan.diestelhorst@arm.com degree(p->degree), 6410771Sstephan.diestelhorst@arm.com pcTable(pcTableAssoc, pcTableSets, name()) 6510623Smitch.hayenga@arm.com{ 6610623Smitch.hayenga@arm.com // Don't consult stride prefetcher on instruction accesses 6710623Smitch.hayenga@arm.com onInst = false; 6810623Smitch.hayenga@arm.com 6910623Smitch.hayenga@arm.com assert(isPowerOf2(pcTableSets)); 7010623Smitch.hayenga@arm.com} 7110623Smitch.hayenga@arm.com 7210771Sstephan.diestelhorst@arm.comStridePrefetcher::StrideEntry** 7310771Sstephan.diestelhorst@arm.comStridePrefetcher::PCTable::allocateNewContext(int context) 7410623Smitch.hayenga@arm.com{ 7510771Sstephan.diestelhorst@arm.com auto res = entries.insert(std::make_pair(context, 7610771Sstephan.diestelhorst@arm.com new StrideEntry*[pcTableSets])); 7710771Sstephan.diestelhorst@arm.com auto it = res.first; 7810771Sstephan.diestelhorst@arm.com chatty_assert(res.second, "Allocating an already created context\n"); 7910771Sstephan.diestelhorst@arm.com assert(it->first == context); 8010771Sstephan.diestelhorst@arm.com 8110771Sstephan.diestelhorst@arm.com DPRINTF(HWPrefetch, "Adding context %i with stride entries at %p\n", 8210771Sstephan.diestelhorst@arm.com context, it->second); 8310771Sstephan.diestelhorst@arm.com 8410771Sstephan.diestelhorst@arm.com StrideEntry** entry = it->second; 8510771Sstephan.diestelhorst@arm.com for (int s = 0; s < pcTableSets; s++) { 8610771Sstephan.diestelhorst@arm.com entry[s] = new StrideEntry[pcTableAssoc]; 8710771Sstephan.diestelhorst@arm.com } 8810771Sstephan.diestelhorst@arm.com return entry; 8910771Sstephan.diestelhorst@arm.com} 9010771Sstephan.diestelhorst@arm.com 9110771Sstephan.diestelhorst@arm.comStridePrefetcher::PCTable::~PCTable() { 9210771Sstephan.diestelhorst@arm.com for (auto entry : entries) { 9310623Smitch.hayenga@arm.com for (int s = 0; s < pcTableSets; s++) { 9410771Sstephan.diestelhorst@arm.com delete[] entry.second[s]; 9510623Smitch.hayenga@arm.com } 9610771Sstephan.diestelhorst@arm.com delete[] entry.second; 9710623Smitch.hayenga@arm.com } 9810623Smitch.hayenga@arm.com} 9910623Smitch.hayenga@arm.com 1003861SN/Avoid 10110623Smitch.hayenga@arm.comStridePrefetcher::calculatePrefetch(const PacketPtr &pkt, 10211439SRekai.GonzalezAlberquilla@arm.com std::vector<AddrPriority> &addresses) 1033861SN/A{ 1045875Ssteve.reinhardt@amd.com if (!pkt->req->hasPC()) { 10510623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Ignoring request with no PC.\n"); 1065875Ssteve.reinhardt@amd.com return; 1075875Ssteve.reinhardt@amd.com } 1082810SN/A 10910623Smitch.hayenga@arm.com // Get required packet info 11010623Smitch.hayenga@arm.com Addr pkt_addr = pkt->getAddr(); 11110623Smitch.hayenga@arm.com Addr pc = pkt->req->getPC(); 11210028SGiacomo.Gabrielli@arm.com bool is_secure = pkt->isSecure(); 1138832SAli.Saidi@ARM.com MasterID master_id = useMasterId ? pkt->req->masterId() : 0; 1142810SN/A 11510623Smitch.hayenga@arm.com // Lookup pc-based information 11610623Smitch.hayenga@arm.com StrideEntry *entry; 1173861SN/A 11811321Ssteve.reinhardt@amd.com if (pcTableHit(pc, is_secure, master_id, entry)) { 1195875Ssteve.reinhardt@amd.com // Hit in table 12010623Smitch.hayenga@arm.com int new_stride = pkt_addr - entry->lastAddr; 12110623Smitch.hayenga@arm.com bool stride_match = (new_stride == entry->stride); 1223861SN/A 12310623Smitch.hayenga@arm.com // Adjust confidence for stride entry 1245875Ssteve.reinhardt@amd.com if (stride_match && new_stride != 0) { 12510623Smitch.hayenga@arm.com if (entry->confidence < maxConf) 12610623Smitch.hayenga@arm.com entry->confidence++; 1275875Ssteve.reinhardt@amd.com } else { 12810623Smitch.hayenga@arm.com if (entry->confidence > minConf) 12910623Smitch.hayenga@arm.com entry->confidence--; 13010623Smitch.hayenga@arm.com // If confidence has dropped below the threshold, train new stride 13110623Smitch.hayenga@arm.com if (entry->confidence < threshConf) 13210623Smitch.hayenga@arm.com entry->stride = new_stride; 1335875Ssteve.reinhardt@amd.com } 1343861SN/A 13510623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), " 13610623Smitch.hayenga@arm.com "conf %d\n", pc, pkt_addr, is_secure ? "s" : "ns", new_stride, 13710028SGiacomo.Gabrielli@arm.com stride_match ? "match" : "change", 13810623Smitch.hayenga@arm.com entry->confidence); 1395875Ssteve.reinhardt@amd.com 14010623Smitch.hayenga@arm.com entry->lastAddr = pkt_addr; 1415875Ssteve.reinhardt@amd.com 14210623Smitch.hayenga@arm.com // Abort prefetch generation if below confidence threshold 14310623Smitch.hayenga@arm.com if (entry->confidence < threshConf) 1445875Ssteve.reinhardt@amd.com return; 1455875Ssteve.reinhardt@amd.com 14610623Smitch.hayenga@arm.com // Generate up to degree prefetches 1475875Ssteve.reinhardt@amd.com for (int d = 1; d <= degree; d++) { 14810623Smitch.hayenga@arm.com // Round strides up to atleast 1 cacheline 14910623Smitch.hayenga@arm.com int prefetch_stride = new_stride; 15010623Smitch.hayenga@arm.com if (abs(new_stride) < blkSize) { 15110623Smitch.hayenga@arm.com prefetch_stride = (new_stride < 0) ? -blkSize : blkSize; 15210623Smitch.hayenga@arm.com } 15310623Smitch.hayenga@arm.com 15410623Smitch.hayenga@arm.com Addr new_addr = pkt_addr + d * prefetch_stride; 15510623Smitch.hayenga@arm.com if (samePage(pkt_addr, new_addr)) { 15610623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr); 15711439SRekai.GonzalezAlberquilla@arm.com addresses.push_back(AddrPriority(new_addr, 0)); 15810623Smitch.hayenga@arm.com } else { 15910623Smitch.hayenga@arm.com // Record the number of page crossing prefetches generated 1605875Ssteve.reinhardt@amd.com pfSpanPage += degree - d + 1; 16110623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Ignoring page crossing prefetch.\n"); 1625875Ssteve.reinhardt@amd.com return; 1635875Ssteve.reinhardt@amd.com } 1645875Ssteve.reinhardt@amd.com } 1655875Ssteve.reinhardt@amd.com } else { 1665875Ssteve.reinhardt@amd.com // Miss in table 16710623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Miss: PC %x pkt_addr %x (%s)\n", pc, pkt_addr, 16810028SGiacomo.Gabrielli@arm.com is_secure ? "s" : "ns"); 1695875Ssteve.reinhardt@amd.com 17010623Smitch.hayenga@arm.com StrideEntry* entry = pcTableVictim(pc, master_id); 17110623Smitch.hayenga@arm.com entry->instAddr = pc; 17210623Smitch.hayenga@arm.com entry->lastAddr = pkt_addr; 17310623Smitch.hayenga@arm.com entry->isSecure= is_secure; 17410623Smitch.hayenga@arm.com entry->stride = 0; 17510623Smitch.hayenga@arm.com entry->confidence = startConf; 1765875Ssteve.reinhardt@amd.com } 1773861SN/A} 1788831Smrinmoy.ghosh@arm.com 17910623Smitch.hayenga@arm.cominline Addr 18010623Smitch.hayenga@arm.comStridePrefetcher::pcHash(Addr pc) const 18110623Smitch.hayenga@arm.com{ 18210623Smitch.hayenga@arm.com Addr hash1 = pc >> 1; 18310623Smitch.hayenga@arm.com Addr hash2 = hash1 >> floorLog2(pcTableSets); 18410623Smitch.hayenga@arm.com return (hash1 ^ hash2) & (Addr)(pcTableSets - 1); 18510623Smitch.hayenga@arm.com} 18610623Smitch.hayenga@arm.com 18710623Smitch.hayenga@arm.cominline StridePrefetcher::StrideEntry* 18810623Smitch.hayenga@arm.comStridePrefetcher::pcTableVictim(Addr pc, int master_id) 18910623Smitch.hayenga@arm.com{ 19010623Smitch.hayenga@arm.com // Rand replacement for now 19110623Smitch.hayenga@arm.com int set = pcHash(pc); 19210627Smitch.hayenga@arm.com int way = random_mt.random<int>(0, pcTableAssoc - 1); 19310623Smitch.hayenga@arm.com 19410623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Victimizing lookup table[%d][%d].\n", set, way); 19510623Smitch.hayenga@arm.com return &pcTable[master_id][set][way]; 19610623Smitch.hayenga@arm.com} 19710623Smitch.hayenga@arm.com 19810623Smitch.hayenga@arm.cominline bool 19910623Smitch.hayenga@arm.comStridePrefetcher::pcTableHit(Addr pc, bool is_secure, int master_id, 20010623Smitch.hayenga@arm.com StrideEntry* &entry) 20110623Smitch.hayenga@arm.com{ 20210623Smitch.hayenga@arm.com int set = pcHash(pc); 20310623Smitch.hayenga@arm.com StrideEntry* set_entries = pcTable[master_id][set]; 20410623Smitch.hayenga@arm.com for (int way = 0; way < pcTableAssoc; way++) { 20510623Smitch.hayenga@arm.com // Search ways for match 20610623Smitch.hayenga@arm.com if (set_entries[way].instAddr == pc && 20710623Smitch.hayenga@arm.com set_entries[way].isSecure == is_secure) { 20810623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Lookup hit table[%d][%d].\n", set, way); 20910623Smitch.hayenga@arm.com entry = &set_entries[way]; 21010623Smitch.hayenga@arm.com return true; 21110623Smitch.hayenga@arm.com } 21210623Smitch.hayenga@arm.com } 21310623Smitch.hayenga@arm.com return false; 21410623Smitch.hayenga@arm.com} 2158831Smrinmoy.ghosh@arm.com 2168831Smrinmoy.ghosh@arm.comStridePrefetcher* 2178831Smrinmoy.ghosh@arm.comStridePrefetcherParams::create() 2188831Smrinmoy.ghosh@arm.com{ 21910623Smitch.hayenga@arm.com return new StridePrefetcher(this); 2208831Smrinmoy.ghosh@arm.com} 221