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 <utility> 3413825Sivan.pizarro@metempsy.com 3513825Sivan.pizarro@metempsy.com#include "debug/HWPrefetch.hh" 3613825Sivan.pizarro@metempsy.com#include "mem/cache/prefetch/associative_set_impl.hh" 3713825Sivan.pizarro@metempsy.com#include "params/PIFPrefetcher.hh" 3813825Sivan.pizarro@metempsy.com 3913825Sivan.pizarro@metempsy.comPIFPrefetcher::PIFPrefetcher(const PIFPrefetcherParams *p) 4013825Sivan.pizarro@metempsy.com : QueuedPrefetcher(p), 4113825Sivan.pizarro@metempsy.com precSize(p->prec_spatial_region_bits), 4213825Sivan.pizarro@metempsy.com succSize(p->succ_spatial_region_bits), 4313825Sivan.pizarro@metempsy.com maxCompactorEntries(p->compactor_entries), 4413825Sivan.pizarro@metempsy.com maxStreamAddressBufferEntries(p->stream_address_buffer_entries), 4513825Sivan.pizarro@metempsy.com historyBuffer(p->history_buffer_size), 4613825Sivan.pizarro@metempsy.com historyBufferTail(0), 4713825Sivan.pizarro@metempsy.com index(p->index_assoc, p->index_entries, p->index_indexing_policy, 4813825Sivan.pizarro@metempsy.com p->index_replacement_policy), 4913825Sivan.pizarro@metempsy.com streamAddressBuffer(), listenersPC() 5013825Sivan.pizarro@metempsy.com{ 5113825Sivan.pizarro@metempsy.com} 5213825Sivan.pizarro@metempsy.com 5313825Sivan.pizarro@metempsy.comPIFPrefetcher::CompactorEntry::CompactorEntry(Addr addr, 5413825Sivan.pizarro@metempsy.com unsigned int prec_size, unsigned int succ_size) 5513825Sivan.pizarro@metempsy.com{ 5613825Sivan.pizarro@metempsy.com trigger = addr; 5713825Sivan.pizarro@metempsy.com prec.resize(prec_size, false); 5813825Sivan.pizarro@metempsy.com succ.resize(succ_size, false); 5913825Sivan.pizarro@metempsy.com} 6013825Sivan.pizarro@metempsy.com 6113835Sgambordr@oregonstate.eduAddr 6213825Sivan.pizarro@metempsy.comPIFPrefetcher::CompactorEntry::distanceFromTrigger(Addr target, 6313835Sgambordr@oregonstate.edu unsigned int log_blk_size) const 6413835Sgambordr@oregonstate.edu{ 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 6813835Sgambordr@oregonstate.edu return target_blk > trigger_blk ? 6913835Sgambordr@oregonstate.edu target_blk - trigger_blk : trigger_blk - target_blk; 7013825Sivan.pizarro@metempsy.com} 7113825Sivan.pizarro@metempsy.com 7213825Sivan.pizarro@metempsy.combool 7313825Sivan.pizarro@metempsy.comPIFPrefetcher::CompactorEntry::inSameSpatialRegion(Addr pc, 7413825Sivan.pizarro@metempsy.com unsigned int log_blk_size, bool update) 7513825Sivan.pizarro@metempsy.com{ 7613835Sgambordr@oregonstate.edu Addr blk_distance = distanceFromTrigger(pc, log_blk_size); 7713825Sivan.pizarro@metempsy.com 7813825Sivan.pizarro@metempsy.com bool hit = (pc > trigger) ? 7913825Sivan.pizarro@metempsy.com (succ.size() >= blk_distance) : (prec.size() >= blk_distance); 8013825Sivan.pizarro@metempsy.com if (hit && update) { 8113825Sivan.pizarro@metempsy.com if (pc > trigger) { 8213825Sivan.pizarro@metempsy.com succ[blk_distance - 1] = true; 8313825Sivan.pizarro@metempsy.com } else if (pc < trigger) { 8413825Sivan.pizarro@metempsy.com prec[blk_distance - 1] = true; 8513825Sivan.pizarro@metempsy.com } 8613825Sivan.pizarro@metempsy.com } 8713825Sivan.pizarro@metempsy.com return hit; 8813825Sivan.pizarro@metempsy.com} 8913825Sivan.pizarro@metempsy.com 9013825Sivan.pizarro@metempsy.combool 9113825Sivan.pizarro@metempsy.comPIFPrefetcher::CompactorEntry::hasAddress(Addr target, 9213825Sivan.pizarro@metempsy.com unsigned int log_blk_size) const 9313825Sivan.pizarro@metempsy.com{ 9413835Sgambordr@oregonstate.edu Addr blk_distance = distanceFromTrigger(target, log_blk_size); 9513825Sivan.pizarro@metempsy.com bool hit = false; 9613825Sivan.pizarro@metempsy.com if (target > trigger) { 9713825Sivan.pizarro@metempsy.com hit = blk_distance <= succ.size() && succ[blk_distance - 1]; 9813825Sivan.pizarro@metempsy.com } else if (target < trigger) { 9913825Sivan.pizarro@metempsy.com hit = blk_distance <= prec.size() && succ[blk_distance - 1]; 10013825Sivan.pizarro@metempsy.com } else { 10113825Sivan.pizarro@metempsy.com hit = true; 10213825Sivan.pizarro@metempsy.com } 10313825Sivan.pizarro@metempsy.com return hit; 10413825Sivan.pizarro@metempsy.com} 10513825Sivan.pizarro@metempsy.com 10613825Sivan.pizarro@metempsy.comvoid 10713825Sivan.pizarro@metempsy.comPIFPrefetcher::CompactorEntry::getPredictedAddresses(unsigned int log_blk_size, 10813825Sivan.pizarro@metempsy.com std::vector<AddrPriority> &addresses) const 10913825Sivan.pizarro@metempsy.com{ 11013825Sivan.pizarro@metempsy.com // Calculate the addresses of the instruction blocks that are encoded 11113825Sivan.pizarro@metempsy.com // by the bit vector and issue prefetch requests for these addresses. 11213825Sivan.pizarro@metempsy.com // Predictions are made by traversing the bit vector from left to right 11313825Sivan.pizarro@metempsy.com // as this typically predicts the accesses in the order they will be 11413825Sivan.pizarro@metempsy.com // issued in the core. 11513825Sivan.pizarro@metempsy.com const Addr trigger_blk = trigger >> log_blk_size; 11613825Sivan.pizarro@metempsy.com for (int i = prec.size()-1; i >= 0; i--) { 11713825Sivan.pizarro@metempsy.com // Address from the preceding blocks to issue a prefetch 11813825Sivan.pizarro@metempsy.com if (prec[i]) { 11913825Sivan.pizarro@metempsy.com const Addr prec_addr = (trigger_blk - (i+1)) << log_blk_size; 12013825Sivan.pizarro@metempsy.com addresses.push_back(AddrPriority(prec_addr, 0)); 12113825Sivan.pizarro@metempsy.com } 12213825Sivan.pizarro@metempsy.com } 12313825Sivan.pizarro@metempsy.com for (int i = 0; i < succ.size(); i++) { 12413825Sivan.pizarro@metempsy.com // Address from the succeding blocks to issue a prefetch 12513825Sivan.pizarro@metempsy.com if (succ[i]) { 12613825Sivan.pizarro@metempsy.com const Addr succ_addr = (trigger_blk + (i+1)) << log_blk_size; 12713825Sivan.pizarro@metempsy.com addresses.push_back(AddrPriority(succ_addr, 0)); 12813825Sivan.pizarro@metempsy.com } 12913825Sivan.pizarro@metempsy.com } 13013825Sivan.pizarro@metempsy.com} 13113825Sivan.pizarro@metempsy.com 13213825Sivan.pizarro@metempsy.comvoid 13313825Sivan.pizarro@metempsy.comPIFPrefetcher::notifyRetiredInst(const Addr pc) 13413825Sivan.pizarro@metempsy.com{ 13513825Sivan.pizarro@metempsy.com // First access to the prefetcher 13613825Sivan.pizarro@metempsy.com if (temporalCompactor.size() == 0) { 13713825Sivan.pizarro@metempsy.com spatialCompactor = CompactorEntry(pc, precSize, succSize); 13813825Sivan.pizarro@metempsy.com } else { 13913825Sivan.pizarro@metempsy.com // If the PC of the instruction retired is in the same spatial region 14013825Sivan.pizarro@metempsy.com // than the last trigger address, update the bit vectors based on the 14113825Sivan.pizarro@metempsy.com // distance between them 14213825Sivan.pizarro@metempsy.com if (spatialCompactor.inSameSpatialRegion(pc, lBlkSize, true)) { 14313825Sivan.pizarro@metempsy.com // If the PC of the instruction retired is outside the latest spatial 14413825Sivan.pizarro@metempsy.com // region, check if it matches in any of the regions in the temporal 14513825Sivan.pizarro@metempsy.com // compactor and update it to the MRU position 14613825Sivan.pizarro@metempsy.com } else { 14713825Sivan.pizarro@metempsy.com bool is_in_temporal_compactor = false; 14813825Sivan.pizarro@metempsy.com 14913825Sivan.pizarro@metempsy.com // Check if the PC is in the temporal compactor 15013825Sivan.pizarro@metempsy.com for (auto it = temporalCompactor.begin(); 15113825Sivan.pizarro@metempsy.com it != temporalCompactor.end(); it++) 15213825Sivan.pizarro@metempsy.com { 15313825Sivan.pizarro@metempsy.com if (it->inSameSpatialRegion(pc, lBlkSize, false)) { 15413825Sivan.pizarro@metempsy.com spatialCompactor = (*it); 15513825Sivan.pizarro@metempsy.com temporalCompactor.erase(it); 15613825Sivan.pizarro@metempsy.com is_in_temporal_compactor = true; 15713825Sivan.pizarro@metempsy.com break; 15813825Sivan.pizarro@metempsy.com } 15913825Sivan.pizarro@metempsy.com } 16013825Sivan.pizarro@metempsy.com 16113825Sivan.pizarro@metempsy.com if (temporalCompactor.size() == maxCompactorEntries) { 16213825Sivan.pizarro@metempsy.com temporalCompactor.pop_front(); // Discard the LRU entry 16313825Sivan.pizarro@metempsy.com } 16413825Sivan.pizarro@metempsy.com 16513825Sivan.pizarro@metempsy.com temporalCompactor.push_back(spatialCompactor); 16613825Sivan.pizarro@metempsy.com 16713825Sivan.pizarro@metempsy.com // If the compactor entry is neither the spatial or can't be 16813825Sivan.pizarro@metempsy.com // found in the temporal compactor, reset the spatial compactor 16913825Sivan.pizarro@metempsy.com // updating the trigger address and resetting the vector bits 17013825Sivan.pizarro@metempsy.com if (!is_in_temporal_compactor) { 17113825Sivan.pizarro@metempsy.com // Insert the spatial entry into the history buffer and update 17213825Sivan.pizarro@metempsy.com // the 'index' table to point to the new entry 17313825Sivan.pizarro@metempsy.com historyBuffer[historyBufferTail] = spatialCompactor; 17413825Sivan.pizarro@metempsy.com 17513825Sivan.pizarro@metempsy.com IndexEntry *idx_entry = 17613825Sivan.pizarro@metempsy.com index.findEntry(spatialCompactor.trigger, false); 17713825Sivan.pizarro@metempsy.com if (idx_entry != nullptr) { 17813825Sivan.pizarro@metempsy.com index.accessEntry(idx_entry); 17913825Sivan.pizarro@metempsy.com } else { 18013825Sivan.pizarro@metempsy.com idx_entry = index.findVictim(spatialCompactor.trigger); 18113825Sivan.pizarro@metempsy.com assert(idx_entry != nullptr); 18213825Sivan.pizarro@metempsy.com index.insertEntry(spatialCompactor.trigger, false, 18313825Sivan.pizarro@metempsy.com idx_entry); 18413825Sivan.pizarro@metempsy.com } 18513825Sivan.pizarro@metempsy.com idx_entry->historyIndex = historyBufferTail; 18613825Sivan.pizarro@metempsy.com 18713825Sivan.pizarro@metempsy.com historyBufferTail++; 18813825Sivan.pizarro@metempsy.com if (historyBufferTail == historyBuffer.size()) { 18913825Sivan.pizarro@metempsy.com historyBufferTail = 0; 19013825Sivan.pizarro@metempsy.com } 19113825Sivan.pizarro@metempsy.com 19213825Sivan.pizarro@metempsy.com // Reset the spatial compactor fields with the new address 19313825Sivan.pizarro@metempsy.com spatialCompactor = CompactorEntry(pc, precSize, succSize); 19413825Sivan.pizarro@metempsy.com } 19513825Sivan.pizarro@metempsy.com } 19613825Sivan.pizarro@metempsy.com } 19713825Sivan.pizarro@metempsy.com} 19813825Sivan.pizarro@metempsy.com 19913825Sivan.pizarro@metempsy.comvoid 20013825Sivan.pizarro@metempsy.comPIFPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 20113825Sivan.pizarro@metempsy.com std::vector<AddrPriority> &addresses) 20213825Sivan.pizarro@metempsy.com{ 20313825Sivan.pizarro@metempsy.com const Addr addr = pfi.getAddr(); 20413825Sivan.pizarro@metempsy.com 20513825Sivan.pizarro@metempsy.com // First check if the access has been prefetched, this is done by 20613825Sivan.pizarro@metempsy.com // comparing the access against the active Stream Address Buffers 20713825Sivan.pizarro@metempsy.com for (auto &sabEntry : streamAddressBuffer) { 20813825Sivan.pizarro@metempsy.com if (sabEntry->hasAddress(addr, lBlkSize)) { 20913825Sivan.pizarro@metempsy.com // Advance to the next entry (first check if we have reached the 21013825Sivan.pizarro@metempsy.com // end of the history buffer) 21113825Sivan.pizarro@metempsy.com if (sabEntry == &(historyBuffer[historyBuffer.size() - 1])) { 21213825Sivan.pizarro@metempsy.com sabEntry = &(historyBuffer[0]); 21313825Sivan.pizarro@metempsy.com } else { 21413825Sivan.pizarro@metempsy.com sabEntry++; 21513825Sivan.pizarro@metempsy.com } 21613825Sivan.pizarro@metempsy.com sabEntry->getPredictedAddresses(lBlkSize, addresses); 21713825Sivan.pizarro@metempsy.com // We are done 21813825Sivan.pizarro@metempsy.com return; 21913825Sivan.pizarro@metempsy.com } 22013825Sivan.pizarro@metempsy.com } 22113825Sivan.pizarro@metempsy.com 22213825Sivan.pizarro@metempsy.com // Check if a valid entry in the 'index' table is found and allocate a new 22313825Sivan.pizarro@metempsy.com // active prediction stream 22413825Sivan.pizarro@metempsy.com IndexEntry *idx_entry = index.findEntry(addr, /* unused */ false); 22513825Sivan.pizarro@metempsy.com 22613825Sivan.pizarro@metempsy.com if (idx_entry != nullptr) { 22713825Sivan.pizarro@metempsy.com index.accessEntry(idx_entry); 22813825Sivan.pizarro@metempsy.com // Trigger address from the 'index' table and index to the history 22913825Sivan.pizarro@metempsy.com // buffer 23013825Sivan.pizarro@metempsy.com const unsigned int hb_entry = idx_entry->historyIndex; 23113825Sivan.pizarro@metempsy.com CompactorEntry *entry = &historyBuffer[hb_entry]; 23213825Sivan.pizarro@metempsy.com 23313825Sivan.pizarro@metempsy.com // Track the block in the Stream Address Buffer 23413825Sivan.pizarro@metempsy.com if (streamAddressBuffer.size() == maxStreamAddressBufferEntries) { 23513825Sivan.pizarro@metempsy.com streamAddressBuffer.pop_front(); 23613825Sivan.pizarro@metempsy.com } 23713825Sivan.pizarro@metempsy.com streamAddressBuffer.push_back(entry); 23813825Sivan.pizarro@metempsy.com 23913825Sivan.pizarro@metempsy.com entry->getPredictedAddresses(lBlkSize, addresses); 24013825Sivan.pizarro@metempsy.com } 24113825Sivan.pizarro@metempsy.com} 24213825Sivan.pizarro@metempsy.com 24313825Sivan.pizarro@metempsy.comvoid 24413825Sivan.pizarro@metempsy.comPIFPrefetcher::PrefetchListenerPC::notify(const Addr& pc) 24513825Sivan.pizarro@metempsy.com{ 24613825Sivan.pizarro@metempsy.com parent.notifyRetiredInst(pc); 24713825Sivan.pizarro@metempsy.com} 24813825Sivan.pizarro@metempsy.com 24913825Sivan.pizarro@metempsy.comvoid 25013825Sivan.pizarro@metempsy.comPIFPrefetcher::addEventProbeRetiredInsts(SimObject *obj, const char *name) 25113825Sivan.pizarro@metempsy.com{ 25213825Sivan.pizarro@metempsy.com ProbeManager *pm(obj->getProbeManager()); 25313825Sivan.pizarro@metempsy.com listenersPC.push_back(new PrefetchListenerPC(*this, pm, name)); 25413825Sivan.pizarro@metempsy.com} 25513825Sivan.pizarro@metempsy.com 25613825Sivan.pizarro@metempsy.comPIFPrefetcher* 25713825Sivan.pizarro@metempsy.comPIFPrefetcherParams::create() 25813825Sivan.pizarro@metempsy.com{ 25913825Sivan.pizarro@metempsy.com return new PIFPrefetcher(this); 26013825Sivan.pizarro@metempsy.com} 261