blob: c8cc109fd1a605ab84b6ae8831e230413bbddb17 [file] [log] [blame]
/**
* Copyright (c) 2019 Metempsy Technology Consulting
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met: redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer;
* redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution;
* neither the name of the copyright holders nor the names of its
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* Authors: Ivan Pizarro
*/
#include "mem/cache/prefetch/pif.hh"
#include <utility>
#include "debug/HWPrefetch.hh"
#include "mem/cache/prefetch/associative_set_impl.hh"
#include "params/PIFPrefetcher.hh"
PIFPrefetcher::PIFPrefetcher(const PIFPrefetcherParams *p)
: QueuedPrefetcher(p),
precSize(p->prec_spatial_region_bits),
succSize(p->succ_spatial_region_bits),
maxCompactorEntries(p->compactor_entries),
maxStreamAddressBufferEntries(p->stream_address_buffer_entries),
historyBuffer(p->history_buffer_size),
historyBufferTail(0),
index(p->index_assoc, p->index_entries, p->index_indexing_policy,
p->index_replacement_policy),
streamAddressBuffer(), listenersPC()
{
}
PIFPrefetcher::CompactorEntry::CompactorEntry(Addr addr,
unsigned int prec_size, unsigned int succ_size)
{
trigger = addr;
prec.resize(prec_size, false);
succ.resize(succ_size, false);
}
Addr
PIFPrefetcher::CompactorEntry::distanceFromTrigger(Addr target,
unsigned int log_blk_size) const
{
const Addr target_blk = target >> log_blk_size;
const Addr trigger_blk = trigger >> log_blk_size;
return target_blk > trigger_blk ?
target_blk - trigger_blk : trigger_blk - target_blk;
}
bool
PIFPrefetcher::CompactorEntry::inSameSpatialRegion(Addr pc,
unsigned int log_blk_size, bool update)
{
Addr blk_distance = distanceFromTrigger(pc, log_blk_size);
bool hit = (pc > trigger) ?
(succ.size() >= blk_distance) : (prec.size() >= blk_distance);
if (hit && update) {
if (pc > trigger) {
succ[blk_distance - 1] = true;
} else if (pc < trigger) {
prec[blk_distance - 1] = true;
}
}
return hit;
}
bool
PIFPrefetcher::CompactorEntry::hasAddress(Addr target,
unsigned int log_blk_size) const
{
Addr blk_distance = distanceFromTrigger(target, log_blk_size);
bool hit = false;
if (target > trigger) {
hit = blk_distance <= succ.size() && succ[blk_distance - 1];
} else if (target < trigger) {
hit = blk_distance <= prec.size() && succ[blk_distance - 1];
} else {
hit = true;
}
return hit;
}
void
PIFPrefetcher::CompactorEntry::getPredictedAddresses(unsigned int log_blk_size,
std::vector<AddrPriority> &addresses) const
{
// Calculate the addresses of the instruction blocks that are encoded
// by the bit vector and issue prefetch requests for these addresses.
// Predictions are made by traversing the bit vector from left to right
// as this typically predicts the accesses in the order they will be
// issued in the core.
const Addr trigger_blk = trigger >> log_blk_size;
for (int i = prec.size()-1; i >= 0; i--) {
// Address from the preceding blocks to issue a prefetch
if (prec[i]) {
const Addr prec_addr = (trigger_blk - (i+1)) << log_blk_size;
addresses.push_back(AddrPriority(prec_addr, 0));
}
}
for (int i = 0; i < succ.size(); i++) {
// Address from the succeding blocks to issue a prefetch
if (succ[i]) {
const Addr succ_addr = (trigger_blk + (i+1)) << log_blk_size;
addresses.push_back(AddrPriority(succ_addr, 0));
}
}
}
void
PIFPrefetcher::notifyRetiredInst(const Addr pc)
{
// First access to the prefetcher
if (temporalCompactor.size() == 0) {
spatialCompactor = CompactorEntry(pc, precSize, succSize);
} else {
// If the PC of the instruction retired is in the same spatial region
// than the last trigger address, update the bit vectors based on the
// distance between them
if (spatialCompactor.inSameSpatialRegion(pc, lBlkSize, true)) {
// If the PC of the instruction retired is outside the latest spatial
// region, check if it matches in any of the regions in the temporal
// compactor and update it to the MRU position
} else {
bool is_in_temporal_compactor = false;
// Check if the PC is in the temporal compactor
for (auto it = temporalCompactor.begin();
it != temporalCompactor.end(); it++)
{
if (it->inSameSpatialRegion(pc, lBlkSize, false)) {
spatialCompactor = (*it);
temporalCompactor.erase(it);
is_in_temporal_compactor = true;
break;
}
}
if (temporalCompactor.size() == maxCompactorEntries) {
temporalCompactor.pop_front(); // Discard the LRU entry
}
temporalCompactor.push_back(spatialCompactor);
// If the compactor entry is neither the spatial or can't be
// found in the temporal compactor, reset the spatial compactor
// updating the trigger address and resetting the vector bits
if (!is_in_temporal_compactor) {
// Insert the spatial entry into the history buffer and update
// the 'index' table to point to the new entry
historyBuffer[historyBufferTail] = spatialCompactor;
IndexEntry *idx_entry =
index.findEntry(spatialCompactor.trigger, false);
if (idx_entry != nullptr) {
index.accessEntry(idx_entry);
} else {
idx_entry = index.findVictim(spatialCompactor.trigger);
assert(idx_entry != nullptr);
index.insertEntry(spatialCompactor.trigger, false,
idx_entry);
}
idx_entry->historyIndex = historyBufferTail;
historyBufferTail++;
if (historyBufferTail == historyBuffer.size()) {
historyBufferTail = 0;
}
// Reset the spatial compactor fields with the new address
spatialCompactor = CompactorEntry(pc, precSize, succSize);
}
}
}
}
void
PIFPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
std::vector<AddrPriority> &addresses)
{
const Addr addr = pfi.getAddr();
// First check if the access has been prefetched, this is done by
// comparing the access against the active Stream Address Buffers
for (auto &sabEntry : streamAddressBuffer) {
if (sabEntry->hasAddress(addr, lBlkSize)) {
// Advance to the next entry (first check if we have reached the
// end of the history buffer)
if (sabEntry == &(historyBuffer[historyBuffer.size() - 1])) {
sabEntry = &(historyBuffer[0]);
} else {
sabEntry++;
}
sabEntry->getPredictedAddresses(lBlkSize, addresses);
// We are done
return;
}
}
// Check if a valid entry in the 'index' table is found and allocate a new
// active prediction stream
IndexEntry *idx_entry = index.findEntry(addr, /* unused */ false);
if (idx_entry != nullptr) {
index.accessEntry(idx_entry);
// Trigger address from the 'index' table and index to the history
// buffer
const unsigned int hb_entry = idx_entry->historyIndex;
CompactorEntry *entry = &historyBuffer[hb_entry];
// Track the block in the Stream Address Buffer
if (streamAddressBuffer.size() == maxStreamAddressBufferEntries) {
streamAddressBuffer.pop_front();
}
streamAddressBuffer.push_back(entry);
entry->getPredictedAddresses(lBlkSize, addresses);
}
}
void
PIFPrefetcher::PrefetchListenerPC::notify(const Addr& pc)
{
parent.notifyRetiredInst(pc);
}
void
PIFPrefetcher::addEventProbeRetiredInsts(SimObject *obj, const char *name)
{
ProbeManager *pm(obj->getProbeManager());
listenersPC.push_back(new PrefetchListenerPC(*this, pm, name));
}
PIFPrefetcher*
PIFPrefetcherParams::create()
{
return new PIFPrefetcher(this);
}