pif.cc revision 13825
113825Sivan.pizarro@metempsy.com/** 213825Sivan.pizarro@metempsy.com * Copyright (c) 2019 Metempsy Technology Consulting 313825Sivan.pizarro@metempsy.com * All rights reserved. 413825Sivan.pizarro@metempsy.com * 513825Sivan.pizarro@metempsy.com * Redistribution and use in source and binary forms, with or without 613825Sivan.pizarro@metempsy.com * modification, are permitted provided that the following conditions are 713825Sivan.pizarro@metempsy.com * met: redistributions of source code must retain the above copyright 813825Sivan.pizarro@metempsy.com * notice, this list of conditions and the following disclaimer; 913825Sivan.pizarro@metempsy.com * redistributions in binary form must reproduce the above copyright 1013825Sivan.pizarro@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113825Sivan.pizarro@metempsy.com * documentation and/or other materials provided with the distribution; 1213825Sivan.pizarro@metempsy.com * neither the name of the copyright holders nor the names of its 1313825Sivan.pizarro@metempsy.com * contributors may be used to endorse or promote products derived from 1413825Sivan.pizarro@metempsy.com * this software without specific prior written permission. 1513825Sivan.pizarro@metempsy.com * 1613825Sivan.pizarro@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713825Sivan.pizarro@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813825Sivan.pizarro@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913825Sivan.pizarro@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013825Sivan.pizarro@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113825Sivan.pizarro@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213825Sivan.pizarro@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313825Sivan.pizarro@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413825Sivan.pizarro@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513825Sivan.pizarro@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613825Sivan.pizarro@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713825Sivan.pizarro@metempsy.com * 2813825Sivan.pizarro@metempsy.com * Authors: Ivan Pizarro 2913825Sivan.pizarro@metempsy.com */ 3013825Sivan.pizarro@metempsy.com 3113825Sivan.pizarro@metempsy.com#include "mem/cache/prefetch/pif.hh" 3213825Sivan.pizarro@metempsy.com 3313825Sivan.pizarro@metempsy.com#include <cmath> 3413825Sivan.pizarro@metempsy.com#include <utility> 3513825Sivan.pizarro@metempsy.com 3613825Sivan.pizarro@metempsy.com#include "debug/HWPrefetch.hh" 3713825Sivan.pizarro@metempsy.com#include "mem/cache/prefetch/associative_set_impl.hh" 3813825Sivan.pizarro@metempsy.com#include "params/PIFPrefetcher.hh" 3913825Sivan.pizarro@metempsy.com 4013825Sivan.pizarro@metempsy.comPIFPrefetcher::PIFPrefetcher(const PIFPrefetcherParams *p) 4113825Sivan.pizarro@metempsy.com : QueuedPrefetcher(p), 4213825Sivan.pizarro@metempsy.com precSize(p->prec_spatial_region_bits), 4313825Sivan.pizarro@metempsy.com succSize(p->succ_spatial_region_bits), 4413825Sivan.pizarro@metempsy.com maxCompactorEntries(p->compactor_entries), 4513825Sivan.pizarro@metempsy.com maxStreamAddressBufferEntries(p->stream_address_buffer_entries), 4613825Sivan.pizarro@metempsy.com historyBuffer(p->history_buffer_size), 4713825Sivan.pizarro@metempsy.com historyBufferTail(0), 4813825Sivan.pizarro@metempsy.com index(p->index_assoc, p->index_entries, p->index_indexing_policy, 4913825Sivan.pizarro@metempsy.com p->index_replacement_policy), 5013825Sivan.pizarro@metempsy.com streamAddressBuffer(), listenersPC() 5113825Sivan.pizarro@metempsy.com{ 5213825Sivan.pizarro@metempsy.com} 5313825Sivan.pizarro@metempsy.com 5413825Sivan.pizarro@metempsy.comPIFPrefetcher::CompactorEntry::CompactorEntry(Addr addr, 5513825Sivan.pizarro@metempsy.com unsigned int prec_size, unsigned int succ_size) 5613825Sivan.pizarro@metempsy.com{ 5713825Sivan.pizarro@metempsy.com trigger = addr; 5813825Sivan.pizarro@metempsy.com prec.resize(prec_size, false); 5913825Sivan.pizarro@metempsy.com succ.resize(succ_size, false); 6013825Sivan.pizarro@metempsy.com} 6113825Sivan.pizarro@metempsy.com 6213825Sivan.pizarro@metempsy.comunsigned int 6313825Sivan.pizarro@metempsy.comPIFPrefetcher::CompactorEntry::distanceFromTrigger(Addr target, 6413825Sivan.pizarro@metempsy.com unsigned int log_blk_size) const { 6513825Sivan.pizarro@metempsy.com const Addr target_blk = target >> log_blk_size; 6613825Sivan.pizarro@metempsy.com const Addr trigger_blk = trigger >> log_blk_size; 6713825Sivan.pizarro@metempsy.com 6813825Sivan.pizarro@metempsy.com return std::abs(target_blk - trigger_blk); 6913825Sivan.pizarro@metempsy.com} 7013825Sivan.pizarro@metempsy.com 7113825Sivan.pizarro@metempsy.combool 7213825Sivan.pizarro@metempsy.comPIFPrefetcher::CompactorEntry::inSameSpatialRegion(Addr pc, 7313825Sivan.pizarro@metempsy.com unsigned int log_blk_size, bool update) 7413825Sivan.pizarro@metempsy.com{ 7513825Sivan.pizarro@metempsy.com unsigned int blk_distance = distanceFromTrigger(pc, log_blk_size); 7613825Sivan.pizarro@metempsy.com 7713825Sivan.pizarro@metempsy.com bool hit = (pc > trigger) ? 7813825Sivan.pizarro@metempsy.com (succ.size() >= blk_distance) : (prec.size() >= blk_distance); 7913825Sivan.pizarro@metempsy.com if (hit && update) { 8013825Sivan.pizarro@metempsy.com if (pc > trigger) { 8113825Sivan.pizarro@metempsy.com succ[blk_distance - 1] = true; 8213825Sivan.pizarro@metempsy.com } else if (pc < trigger) { 8313825Sivan.pizarro@metempsy.com prec[blk_distance - 1] = true; 8413825Sivan.pizarro@metempsy.com } 8513825Sivan.pizarro@metempsy.com } 8613825Sivan.pizarro@metempsy.com return hit; 8713825Sivan.pizarro@metempsy.com} 8813825Sivan.pizarro@metempsy.com 8913825Sivan.pizarro@metempsy.combool 9013825Sivan.pizarro@metempsy.comPIFPrefetcher::CompactorEntry::hasAddress(Addr target, 9113825Sivan.pizarro@metempsy.com unsigned int log_blk_size) const 9213825Sivan.pizarro@metempsy.com{ 9313825Sivan.pizarro@metempsy.com unsigned int blk_distance = distanceFromTrigger(target, log_blk_size); 9413825Sivan.pizarro@metempsy.com bool hit = false; 9513825Sivan.pizarro@metempsy.com if (target > trigger) { 9613825Sivan.pizarro@metempsy.com hit = blk_distance <= succ.size() && succ[blk_distance - 1]; 9713825Sivan.pizarro@metempsy.com } else if (target < trigger) { 9813825Sivan.pizarro@metempsy.com hit = blk_distance <= prec.size() && succ[blk_distance - 1]; 9913825Sivan.pizarro@metempsy.com } else { 10013825Sivan.pizarro@metempsy.com hit = true; 10113825Sivan.pizarro@metempsy.com } 10213825Sivan.pizarro@metempsy.com return hit; 10313825Sivan.pizarro@metempsy.com} 10413825Sivan.pizarro@metempsy.com 10513825Sivan.pizarro@metempsy.comvoid 10613825Sivan.pizarro@metempsy.comPIFPrefetcher::CompactorEntry::getPredictedAddresses(unsigned int log_blk_size, 10713825Sivan.pizarro@metempsy.com std::vector<AddrPriority> &addresses) const 10813825Sivan.pizarro@metempsy.com{ 10913825Sivan.pizarro@metempsy.com // Calculate the addresses of the instruction blocks that are encoded 11013825Sivan.pizarro@metempsy.com // by the bit vector and issue prefetch requests for these addresses. 11113825Sivan.pizarro@metempsy.com // Predictions are made by traversing the bit vector from left to right 11213825Sivan.pizarro@metempsy.com // as this typically predicts the accesses in the order they will be 11313825Sivan.pizarro@metempsy.com // issued in the core. 11413825Sivan.pizarro@metempsy.com const Addr trigger_blk = trigger >> log_blk_size; 11513825Sivan.pizarro@metempsy.com for (int i = prec.size()-1; i >= 0; i--) { 11613825Sivan.pizarro@metempsy.com // Address from the preceding blocks to issue a prefetch 11713825Sivan.pizarro@metempsy.com if (prec[i]) { 11813825Sivan.pizarro@metempsy.com const Addr prec_addr = (trigger_blk - (i+1)) << log_blk_size; 11913825Sivan.pizarro@metempsy.com addresses.push_back(AddrPriority(prec_addr, 0)); 12013825Sivan.pizarro@metempsy.com } 12113825Sivan.pizarro@metempsy.com } 12213825Sivan.pizarro@metempsy.com for (int i = 0; i < succ.size(); i++) { 12313825Sivan.pizarro@metempsy.com // Address from the succeding blocks to issue a prefetch 12413825Sivan.pizarro@metempsy.com if (succ[i]) { 12513825Sivan.pizarro@metempsy.com const Addr succ_addr = (trigger_blk + (i+1)) << log_blk_size; 12613825Sivan.pizarro@metempsy.com addresses.push_back(AddrPriority(succ_addr, 0)); 12713825Sivan.pizarro@metempsy.com } 12813825Sivan.pizarro@metempsy.com } 12913825Sivan.pizarro@metempsy.com} 13013825Sivan.pizarro@metempsy.com 13113825Sivan.pizarro@metempsy.comvoid 13213825Sivan.pizarro@metempsy.comPIFPrefetcher::notifyRetiredInst(const Addr pc) 13313825Sivan.pizarro@metempsy.com{ 13413825Sivan.pizarro@metempsy.com // First access to the prefetcher 13513825Sivan.pizarro@metempsy.com if (temporalCompactor.size() == 0) { 13613825Sivan.pizarro@metempsy.com spatialCompactor = CompactorEntry(pc, precSize, succSize); 13713825Sivan.pizarro@metempsy.com } else { 13813825Sivan.pizarro@metempsy.com // If the PC of the instruction retired is in the same spatial region 13913825Sivan.pizarro@metempsy.com // than the last trigger address, update the bit vectors based on the 14013825Sivan.pizarro@metempsy.com // distance between them 14113825Sivan.pizarro@metempsy.com if (spatialCompactor.inSameSpatialRegion(pc, lBlkSize, true)) { 14213825Sivan.pizarro@metempsy.com // If the PC of the instruction retired is outside the latest spatial 14313825Sivan.pizarro@metempsy.com // region, check if it matches in any of the regions in the temporal 14413825Sivan.pizarro@metempsy.com // compactor and update it to the MRU position 14513825Sivan.pizarro@metempsy.com } else { 14613825Sivan.pizarro@metempsy.com bool is_in_temporal_compactor = false; 14713825Sivan.pizarro@metempsy.com 14813825Sivan.pizarro@metempsy.com // Check if the PC is in the temporal compactor 14913825Sivan.pizarro@metempsy.com for (auto it = temporalCompactor.begin(); 15013825Sivan.pizarro@metempsy.com it != temporalCompactor.end(); it++) 15113825Sivan.pizarro@metempsy.com { 15213825Sivan.pizarro@metempsy.com if (it->inSameSpatialRegion(pc, lBlkSize, false)) { 15313825Sivan.pizarro@metempsy.com spatialCompactor = (*it); 15413825Sivan.pizarro@metempsy.com temporalCompactor.erase(it); 15513825Sivan.pizarro@metempsy.com is_in_temporal_compactor = true; 15613825Sivan.pizarro@metempsy.com break; 15713825Sivan.pizarro@metempsy.com } 15813825Sivan.pizarro@metempsy.com } 15913825Sivan.pizarro@metempsy.com 16013825Sivan.pizarro@metempsy.com if (temporalCompactor.size() == maxCompactorEntries) { 16113825Sivan.pizarro@metempsy.com temporalCompactor.pop_front(); // Discard the LRU entry 16213825Sivan.pizarro@metempsy.com } 16313825Sivan.pizarro@metempsy.com 16413825Sivan.pizarro@metempsy.com temporalCompactor.push_back(spatialCompactor); 16513825Sivan.pizarro@metempsy.com 16613825Sivan.pizarro@metempsy.com // If the compactor entry is neither the spatial or can't be 16713825Sivan.pizarro@metempsy.com // found in the temporal compactor, reset the spatial compactor 16813825Sivan.pizarro@metempsy.com // updating the trigger address and resetting the vector bits 16913825Sivan.pizarro@metempsy.com if (!is_in_temporal_compactor) { 17013825Sivan.pizarro@metempsy.com // Insert the spatial entry into the history buffer and update 17113825Sivan.pizarro@metempsy.com // the 'index' table to point to the new entry 17213825Sivan.pizarro@metempsy.com historyBuffer[historyBufferTail] = spatialCompactor; 17313825Sivan.pizarro@metempsy.com 17413825Sivan.pizarro@metempsy.com IndexEntry *idx_entry = 17513825Sivan.pizarro@metempsy.com index.findEntry(spatialCompactor.trigger, false); 17613825Sivan.pizarro@metempsy.com if (idx_entry != nullptr) { 17713825Sivan.pizarro@metempsy.com index.accessEntry(idx_entry); 17813825Sivan.pizarro@metempsy.com } else { 17913825Sivan.pizarro@metempsy.com idx_entry = index.findVictim(spatialCompactor.trigger); 18013825Sivan.pizarro@metempsy.com assert(idx_entry != nullptr); 18113825Sivan.pizarro@metempsy.com index.insertEntry(spatialCompactor.trigger, false, 18213825Sivan.pizarro@metempsy.com idx_entry); 18313825Sivan.pizarro@metempsy.com } 18413825Sivan.pizarro@metempsy.com idx_entry->historyIndex = historyBufferTail; 18513825Sivan.pizarro@metempsy.com 18613825Sivan.pizarro@metempsy.com historyBufferTail++; 18713825Sivan.pizarro@metempsy.com if (historyBufferTail == historyBuffer.size()) { 18813825Sivan.pizarro@metempsy.com historyBufferTail = 0; 18913825Sivan.pizarro@metempsy.com } 19013825Sivan.pizarro@metempsy.com 19113825Sivan.pizarro@metempsy.com // Reset the spatial compactor fields with the new address 19213825Sivan.pizarro@metempsy.com spatialCompactor = CompactorEntry(pc, precSize, succSize); 19313825Sivan.pizarro@metempsy.com } 19413825Sivan.pizarro@metempsy.com } 19513825Sivan.pizarro@metempsy.com } 19613825Sivan.pizarro@metempsy.com} 19713825Sivan.pizarro@metempsy.com 19813825Sivan.pizarro@metempsy.comvoid 19913825Sivan.pizarro@metempsy.comPIFPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 20013825Sivan.pizarro@metempsy.com std::vector<AddrPriority> &addresses) 20113825Sivan.pizarro@metempsy.com{ 20213825Sivan.pizarro@metempsy.com const Addr addr = pfi.getAddr(); 20313825Sivan.pizarro@metempsy.com 20413825Sivan.pizarro@metempsy.com // First check if the access has been prefetched, this is done by 20513825Sivan.pizarro@metempsy.com // comparing the access against the active Stream Address Buffers 20613825Sivan.pizarro@metempsy.com for (auto &sabEntry : streamAddressBuffer) { 20713825Sivan.pizarro@metempsy.com if (sabEntry->hasAddress(addr, lBlkSize)) { 20813825Sivan.pizarro@metempsy.com // Advance to the next entry (first check if we have reached the 20913825Sivan.pizarro@metempsy.com // end of the history buffer) 21013825Sivan.pizarro@metempsy.com if (sabEntry == &(historyBuffer[historyBuffer.size() - 1])) { 21113825Sivan.pizarro@metempsy.com sabEntry = &(historyBuffer[0]); 21213825Sivan.pizarro@metempsy.com } else { 21313825Sivan.pizarro@metempsy.com sabEntry++; 21413825Sivan.pizarro@metempsy.com } 21513825Sivan.pizarro@metempsy.com sabEntry->getPredictedAddresses(lBlkSize, addresses); 21613825Sivan.pizarro@metempsy.com // We are done 21713825Sivan.pizarro@metempsy.com return; 21813825Sivan.pizarro@metempsy.com } 21913825Sivan.pizarro@metempsy.com } 22013825Sivan.pizarro@metempsy.com 22113825Sivan.pizarro@metempsy.com // Check if a valid entry in the 'index' table is found and allocate a new 22213825Sivan.pizarro@metempsy.com // active prediction stream 22313825Sivan.pizarro@metempsy.com IndexEntry *idx_entry = index.findEntry(addr, /* unused */ false); 22413825Sivan.pizarro@metempsy.com 22513825Sivan.pizarro@metempsy.com if (idx_entry != nullptr) { 22613825Sivan.pizarro@metempsy.com index.accessEntry(idx_entry); 22713825Sivan.pizarro@metempsy.com // Trigger address from the 'index' table and index to the history 22813825Sivan.pizarro@metempsy.com // buffer 22913825Sivan.pizarro@metempsy.com const unsigned int hb_entry = idx_entry->historyIndex; 23013825Sivan.pizarro@metempsy.com CompactorEntry *entry = &historyBuffer[hb_entry]; 23113825Sivan.pizarro@metempsy.com 23213825Sivan.pizarro@metempsy.com // Track the block in the Stream Address Buffer 23313825Sivan.pizarro@metempsy.com if (streamAddressBuffer.size() == maxStreamAddressBufferEntries) { 23413825Sivan.pizarro@metempsy.com streamAddressBuffer.pop_front(); 23513825Sivan.pizarro@metempsy.com } 23613825Sivan.pizarro@metempsy.com streamAddressBuffer.push_back(entry); 23713825Sivan.pizarro@metempsy.com 23813825Sivan.pizarro@metempsy.com entry->getPredictedAddresses(lBlkSize, addresses); 23913825Sivan.pizarro@metempsy.com } 24013825Sivan.pizarro@metempsy.com} 24113825Sivan.pizarro@metempsy.com 24213825Sivan.pizarro@metempsy.comvoid 24313825Sivan.pizarro@metempsy.comPIFPrefetcher::PrefetchListenerPC::notify(const Addr& pc) 24413825Sivan.pizarro@metempsy.com{ 24513825Sivan.pizarro@metempsy.com parent.notifyRetiredInst(pc); 24613825Sivan.pizarro@metempsy.com} 24713825Sivan.pizarro@metempsy.com 24813825Sivan.pizarro@metempsy.comvoid 24913825Sivan.pizarro@metempsy.comPIFPrefetcher::addEventProbeRetiredInsts(SimObject *obj, const char *name) 25013825Sivan.pizarro@metempsy.com{ 25113825Sivan.pizarro@metempsy.com ProbeManager *pm(obj->getProbeManager()); 25213825Sivan.pizarro@metempsy.com listenersPC.push_back(new PrefetchListenerPC(*this, pm, name)); 25313825Sivan.pizarro@metempsy.com} 25413825Sivan.pizarro@metempsy.com 25513825Sivan.pizarro@metempsy.comPIFPrefetcher* 25613825Sivan.pizarro@metempsy.comPIFPrefetcherParams::create() 25713825Sivan.pizarro@metempsy.com{ 25813825Sivan.pizarro@metempsy.com return new PIFPrefetcher(this); 25913825Sivan.pizarro@metempsy.com} 260