pif.cc revision 13825
12391SN/A/** 28931Sandreas.hansson@arm.com * Copyright (c) 2019 Metempsy Technology Consulting 37733SN/A * All rights reserved. 47733SN/A * 57733SN/A * Redistribution and use in source and binary forms, with or without 67733SN/A * modification, are permitted provided that the following conditions are 77733SN/A * met: redistributions of source code must retain the above copyright 87733SN/A * notice, this list of conditions and the following disclaimer; 97733SN/A * redistributions in binary form must reproduce the above copyright 107733SN/A * notice, this list of conditions and the following disclaimer in the 117733SN/A * documentation and/or other materials provided with the distribution; 127733SN/A * neither the name of the copyright holders nor the names of its 137733SN/A * contributors may be used to endorse or promote products derived from 142391SN/A * this software without specific prior written permission. 152391SN/A * 162391SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172391SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182391SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192391SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202391SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212391SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222391SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232391SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242391SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252391SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262391SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272391SN/A * 282391SN/A * Authors: Ivan Pizarro 292391SN/A */ 302391SN/A 312391SN/A#include "mem/cache/prefetch/pif.hh" 322391SN/A 332391SN/A#include <cmath> 342391SN/A#include <utility> 352391SN/A 362391SN/A#include "debug/HWPrefetch.hh" 372391SN/A#include "mem/cache/prefetch/associative_set_impl.hh" 382391SN/A#include "params/PIFPrefetcher.hh" 392665SN/A 402665SN/APIFPrefetcher::PIFPrefetcher(const PIFPrefetcherParams *p) 412914SN/A : QueuedPrefetcher(p), 428931Sandreas.hansson@arm.com precSize(p->prec_spatial_region_bits), 432391SN/A succSize(p->succ_spatial_region_bits), 442391SN/A maxCompactorEntries(p->compactor_entries), 455399SN/A maxStreamAddressBufferEntries(p->stream_address_buffer_entries), 468931Sandreas.hansson@arm.com historyBuffer(p->history_buffer_size), 472394SN/A historyBufferTail(0), 482391SN/A index(p->index_assoc, p->index_entries, p->index_indexing_policy, 492391SN/A p->index_replacement_policy), 509228Sandreas.hansson@arm.com streamAddressBuffer(), listenersPC() 518931Sandreas.hansson@arm.com{ 529228Sandreas.hansson@arm.com} 539228Sandreas.hansson@arm.com 549228Sandreas.hansson@arm.comPIFPrefetcher::CompactorEntry::CompactorEntry(Addr addr, 552391SN/A unsigned int prec_size, unsigned int succ_size) 562391SN/A{ 572391SN/A trigger = addr; 582541SN/A prec.resize(prec_size, false); 598931Sandreas.hansson@arm.com succ.resize(succ_size, false); 602541SN/A} 619120Sandreas.hansson@arm.com 629120Sandreas.hansson@arm.comunsigned int 639120Sandreas.hansson@arm.comPIFPrefetcher::CompactorEntry::distanceFromTrigger(Addr target, 649120Sandreas.hansson@arm.com unsigned int log_blk_size) const { 654467SN/A const Addr target_blk = target >> log_blk_size; 662541SN/A const Addr trigger_blk = trigger >> log_blk_size; 672541SN/A 688931Sandreas.hansson@arm.com return std::abs(target_blk - trigger_blk); 698931Sandreas.hansson@arm.com} 702391SN/A 718931Sandreas.hansson@arm.combool 728931Sandreas.hansson@arm.comPIFPrefetcher::CompactorEntry::inSameSpatialRegion(Addr pc, 738931Sandreas.hansson@arm.com unsigned int log_blk_size, bool update) 748931Sandreas.hansson@arm.com{ 758931Sandreas.hansson@arm.com unsigned int blk_distance = distanceFromTrigger(pc, log_blk_size); 768931Sandreas.hansson@arm.com 778931Sandreas.hansson@arm.com bool hit = (pc > trigger) ? 788931Sandreas.hansson@arm.com (succ.size() >= blk_distance) : (prec.size() >= blk_distance); 798931Sandreas.hansson@arm.com if (hit && update) { 808931Sandreas.hansson@arm.com if (pc > trigger) { 818931Sandreas.hansson@arm.com succ[blk_distance - 1] = true; 828931Sandreas.hansson@arm.com } else if (pc < trigger) { 838931Sandreas.hansson@arm.com prec[blk_distance - 1] = true; 848931Sandreas.hansson@arm.com } 858931Sandreas.hansson@arm.com } 862391SN/A return hit; 872391SN/A} 888719SN/A 898931Sandreas.hansson@arm.combool 908719SN/APIFPrefetcher::CompactorEntry::hasAddress(Addr target, 918931Sandreas.hansson@arm.com unsigned int log_blk_size) const 928719SN/A{ 938719SN/A unsigned int blk_distance = distanceFromTrigger(target, log_blk_size); 949228Sandreas.hansson@arm.com bool hit = false; 959228Sandreas.hansson@arm.com if (target > trigger) { 969228Sandreas.hansson@arm.com hit = blk_distance <= succ.size() && succ[blk_distance - 1]; 979349SAli.Saidi@ARM.com } else if (target < trigger) { 989349SAli.Saidi@ARM.com hit = blk_distance <= prec.size() && succ[blk_distance - 1]; 999349SAli.Saidi@ARM.com } else { 1009349SAli.Saidi@ARM.com hit = true; 1019349SAli.Saidi@ARM.com } 1029349SAli.Saidi@ARM.com return hit; 1039228Sandreas.hansson@arm.com} 1049228Sandreas.hansson@arm.com 1059228Sandreas.hansson@arm.comvoid 1069349SAli.Saidi@ARM.comPIFPrefetcher::CompactorEntry::getPredictedAddresses(unsigned int log_blk_size, 1079228Sandreas.hansson@arm.com std::vector<AddrPriority> &addresses) const 1089228Sandreas.hansson@arm.com{ 1099228Sandreas.hansson@arm.com // Calculate the addresses of the instruction blocks that are encoded 1109228Sandreas.hansson@arm.com // by the bit vector and issue prefetch requests for these addresses. 1119228Sandreas.hansson@arm.com // Predictions are made by traversing the bit vector from left to right 1129228Sandreas.hansson@arm.com // as this typically predicts the accesses in the order they will be 1139228Sandreas.hansson@arm.com // issued in the core. 1149228Sandreas.hansson@arm.com const Addr trigger_blk = trigger >> log_blk_size; 1159228Sandreas.hansson@arm.com for (int i = prec.size()-1; i >= 0; i--) { 1169228Sandreas.hansson@arm.com // Address from the preceding blocks to issue a prefetch 1179228Sandreas.hansson@arm.com if (prec[i]) { 1189228Sandreas.hansson@arm.com const Addr prec_addr = (trigger_blk - (i+1)) << log_blk_size; 1199228Sandreas.hansson@arm.com addresses.push_back(AddrPriority(prec_addr, 0)); 1209228Sandreas.hansson@arm.com } 1219228Sandreas.hansson@arm.com } 1229228Sandreas.hansson@arm.com for (int i = 0; i < succ.size(); i++) { 1239228Sandreas.hansson@arm.com // Address from the succeding blocks to issue a prefetch 1249228Sandreas.hansson@arm.com if (succ[i]) { 1259228Sandreas.hansson@arm.com const Addr succ_addr = (trigger_blk + (i+1)) << log_blk_size; 1269228Sandreas.hansson@arm.com addresses.push_back(AddrPriority(succ_addr, 0)); 1279228Sandreas.hansson@arm.com } 1289228Sandreas.hansson@arm.com } 1299228Sandreas.hansson@arm.com} 1309228Sandreas.hansson@arm.com 1319228Sandreas.hansson@arm.comvoid 1329228Sandreas.hansson@arm.comPIFPrefetcher::notifyRetiredInst(const Addr pc) 1339228Sandreas.hansson@arm.com{ 1349228Sandreas.hansson@arm.com // First access to the prefetcher 1359228Sandreas.hansson@arm.com if (temporalCompactor.size() == 0) { 1369228Sandreas.hansson@arm.com spatialCompactor = CompactorEntry(pc, precSize, succSize); 1379228Sandreas.hansson@arm.com } else { 1389228Sandreas.hansson@arm.com // If the PC of the instruction retired is in the same spatial region 1399228Sandreas.hansson@arm.com // than the last trigger address, update the bit vectors based on the 1409228Sandreas.hansson@arm.com // distance between them 1419228Sandreas.hansson@arm.com if (spatialCompactor.inSameSpatialRegion(pc, lBlkSize, true)) { 1429228Sandreas.hansson@arm.com // If the PC of the instruction retired is outside the latest spatial 1439228Sandreas.hansson@arm.com // region, check if it matches in any of the regions in the temporal 1449228Sandreas.hansson@arm.com // compactor and update it to the MRU position 1459228Sandreas.hansson@arm.com } else { 1469228Sandreas.hansson@arm.com bool is_in_temporal_compactor = false; 1479228Sandreas.hansson@arm.com 1489228Sandreas.hansson@arm.com // Check if the PC is in the temporal compactor 1499228Sandreas.hansson@arm.com for (auto it = temporalCompactor.begin(); 1509228Sandreas.hansson@arm.com it != temporalCompactor.end(); it++) 1519228Sandreas.hansson@arm.com { 1529228Sandreas.hansson@arm.com if (it->inSameSpatialRegion(pc, lBlkSize, false)) { 1539228Sandreas.hansson@arm.com spatialCompactor = (*it); 1549228Sandreas.hansson@arm.com temporalCompactor.erase(it); 1559228Sandreas.hansson@arm.com is_in_temporal_compactor = true; 1569228Sandreas.hansson@arm.com break; 1579228Sandreas.hansson@arm.com } 1589228Sandreas.hansson@arm.com } 1599228Sandreas.hansson@arm.com 1609228Sandreas.hansson@arm.com if (temporalCompactor.size() == maxCompactorEntries) { 1619228Sandreas.hansson@arm.com temporalCompactor.pop_front(); // Discard the LRU entry 1629228Sandreas.hansson@arm.com } 1639228Sandreas.hansson@arm.com 1649228Sandreas.hansson@arm.com temporalCompactor.push_back(spatialCompactor); 1659228Sandreas.hansson@arm.com 1669228Sandreas.hansson@arm.com // If the compactor entry is neither the spatial or can't be 1679228Sandreas.hansson@arm.com // found in the temporal compactor, reset the spatial compactor 1689228Sandreas.hansson@arm.com // updating the trigger address and resetting the vector bits 1699228Sandreas.hansson@arm.com if (!is_in_temporal_compactor) { 1709228Sandreas.hansson@arm.com // Insert the spatial entry into the history buffer and update 1719228Sandreas.hansson@arm.com // the 'index' table to point to the new entry 1729228Sandreas.hansson@arm.com historyBuffer[historyBufferTail] = spatialCompactor; 1739228Sandreas.hansson@arm.com 1749294Sandreas.hansson@arm.com IndexEntry *idx_entry = 1759294Sandreas.hansson@arm.com index.findEntry(spatialCompactor.trigger, false); 1762413SN/A if (idx_entry != nullptr) { 1774467SN/A index.accessEntry(idx_entry); 1788922SN/A } else { 1798922SN/A idx_entry = index.findVictim(spatialCompactor.trigger); 1809120Sandreas.hansson@arm.com assert(idx_entry != nullptr); 1812462SN/A index.insertEntry(spatialCompactor.trigger, false, 1822413SN/A idx_entry); 1832413SN/A } 1842914SN/A idx_entry->historyIndex = historyBufferTail; 1859342SAndreas.Sandberg@arm.com 1862914SN/A historyBufferTail++; 1879342SAndreas.Sandberg@arm.com if (historyBufferTail == historyBuffer.size()) { 1884467SN/A historyBufferTail = 0; 1892914SN/A } 1909342SAndreas.Sandberg@arm.com 1912914SN/A // Reset the spatial compactor fields with the new address 1929342SAndreas.Sandberg@arm.com spatialCompactor = CompactorEntry(pc, precSize, succSize); 1932914SN/A } 1942914SN/A } 1952413SN/A } 1968931Sandreas.hansson@arm.com} 1978931Sandreas.hansson@arm.com 1989228Sandreas.hansson@arm.comvoid 1999228Sandreas.hansson@arm.comPIFPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 2008931Sandreas.hansson@arm.com std::vector<AddrPriority> &addresses) 2018931Sandreas.hansson@arm.com{ 2028931Sandreas.hansson@arm.com const Addr addr = pfi.getAddr(); 2039090Sandreas.hansson@arm.com 2042391SN/A // First check if the access has been prefetched, this is done by 2058931Sandreas.hansson@arm.com // comparing the access against the active Stream Address Buffers 2068931Sandreas.hansson@arm.com for (auto &sabEntry : streamAddressBuffer) { 2078931Sandreas.hansson@arm.com if (sabEntry->hasAddress(addr, lBlkSize)) { 2088931Sandreas.hansson@arm.com // Advance to the next entry (first check if we have reached the 2095477SN/A // end of the history buffer) 2108931Sandreas.hansson@arm.com if (sabEntry == &(historyBuffer[historyBuffer.size() - 1])) { 2118931Sandreas.hansson@arm.com sabEntry = &(historyBuffer[0]); 2128931Sandreas.hansson@arm.com } else { 2138931Sandreas.hansson@arm.com sabEntry++; 2142391SN/A } 2152391SN/A sabEntry->getPredictedAddresses(lBlkSize, addresses); 2162391SN/A // We are done 2178931Sandreas.hansson@arm.com return; 2182391SN/A } 2198931Sandreas.hansson@arm.com } 2205477SN/A 2218931Sandreas.hansson@arm.com // Check if a valid entry in the 'index' table is found and allocate a new 2228931Sandreas.hansson@arm.com // active prediction stream 2238931Sandreas.hansson@arm.com IndexEntry *idx_entry = index.findEntry(addr, /* unused */ false); 2248931Sandreas.hansson@arm.com 2258931Sandreas.hansson@arm.com if (idx_entry != nullptr) { 2262391SN/A index.accessEntry(idx_entry); 2272391SN/A // Trigger address from the 'index' table and index to the history 2288931Sandreas.hansson@arm.com // buffer 2292391SN/A const unsigned int hb_entry = idx_entry->historyIndex; 2302391SN/A CompactorEntry *entry = &historyBuffer[hb_entry]; 2319228Sandreas.hansson@arm.com 2329228Sandreas.hansson@arm.com // Track the block in the Stream Address Buffer 2339228Sandreas.hansson@arm.com if (streamAddressBuffer.size() == maxStreamAddressBufferEntries) { 2349228Sandreas.hansson@arm.com streamAddressBuffer.pop_front(); 2359228Sandreas.hansson@arm.com } 2369228Sandreas.hansson@arm.com streamAddressBuffer.push_back(entry); 2378931Sandreas.hansson@arm.com 2388931Sandreas.hansson@arm.com entry->getPredictedAddresses(lBlkSize, addresses); 2392391SN/A } 2408931Sandreas.hansson@arm.com} 2412391SN/A 242void 243PIFPrefetcher::PrefetchListenerPC::notify(const Addr& pc) 244{ 245 parent.notifyRetiredInst(pc); 246} 247 248void 249PIFPrefetcher::addEventProbeRetiredInsts(SimObject *obj, const char *name) 250{ 251 ProbeManager *pm(obj->getProbeManager()); 252 listenersPC.push_back(new PrefetchListenerPC(*this, pm, name)); 253} 254 255PIFPrefetcher* 256PIFPrefetcherParams::create() 257{ 258 return new PIFPrefetcher(this); 259} 260