/**
* 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
*/
/** Implementation of the 'Proactive Instruction Fetch' prefetcher
* Reference:
* Ferdman, M., Kaynak, C., & Falsafi, B. (2011, December).
* Proactive instruction fetch.
* In Proceedings of the 44th Annual IEEE/ACM International Symposium
* on Microarchitecture (pp. 152-162). ACM.
*/
#ifndef __MEM_CACHE_PREFETCH_PIF_HH__
#define __MEM_CACHE_PREFETCH_PIF_HH__
#include <deque>
#include <vector>
#include "mem/cache/prefetch/associative_set.hh"
#include "mem/cache/prefetch/queued.hh"
struct PIFPrefetcherParams;
class PIFPrefetcher : public QueuedPrefetcher
{
private:
/** Number of preceding and subsequent spatial addresses to compact */
const unsigned int precSize;
const unsigned int succSize;
/** Number of entries used for the temporal compactor */
const unsigned int maxCompactorEntries;
/** Max number of entries to be used in the Stream Address Buffer */
const unsigned int maxStreamAddressBufferEntries;
/**
* The compactor tracks retired instructions addresses, leveraging the
* spatial and temporal locality among instructions for compaction. It
*comprises the spatial and temporal compaction mechanisms.
*
* Taking advantage of the spatial locality across instruction blocks,
* the spatial compactor combines instruction-block addresses that fall
* within a 'spatial region', a group of adjacent instruction blocks.
* When an instruction outside the current spatial region retires, the
* existing spatial region is sent to the temporal compactor.
*
* The temporal compactor tracks a small number of the
* most-recently-observed spatial region records.
*/
struct CompactorEntry {
Addr trigger;
std::vector<bool> prec;
std::vector<bool> succ;
CompactorEntry() {}
CompactorEntry(Addr, unsigned int, unsigned int);
/**
* Checks if a given address is in the same defined spatial region
* as the compactor entry.
* @param addr Address to check if it's inside the spatial region
* @param log_blk_distance log_2(block size of the cache)
* @param update if true, set the corresponding succ/prec entry
* @return TRUE if they are in the same spatial region, FALSE
* otherwise
*/
bool inSameSpatialRegion(Addr addr, unsigned int log_blk_size,
bool update);
/**
* Checks if the provided address is contained in this spatial
* region and if its corresponding bit vector entry is set
* @param target address to check
* @param log_blk_distance log_2(block size of the cache)
* @return TRUE if target has its bit set
*/
bool hasAddress(Addr target, unsigned int log_blk_size) const;
/**
* Fills the provided vector with the predicted addresses using the
* recorded bit vectors of the entry
* @param log_blk_distance log_2(block size of the cache)
* @param addresses reference to a vector to add the generated
* addresses
*/
void getPredictedAddresses(unsigned int log_blk_size,
std::vector<AddrPriority> &addresses) const;
private:
/**
* Computes the distance, in cache blocks, from an address to the
* trigger of the entry.
* @param addr address to compute the distance from the trigger
* @param log_blk_distance log_2(block size of the cache)
* @result distance in cache blocks from the address to the trigger
*/
Addr distanceFromTrigger(Addr addr,
unsigned int log_blk_size) const;
};
CompactorEntry spatialCompactor;
std::deque<CompactorEntry> temporalCompactor;
/**
* History buffer is a circular buffer that stores the sequence of
* retired instructions in FIFO order.
*/
std::vector<CompactorEntry> historyBuffer;
unsigned int historyBufferTail;
struct IndexEntry : public TaggedEntry
{
unsigned int historyIndex;
};
/**
* The index table is a small cache-like structure that facilitates
* fast search of the history buffer.
*/
AssociativeSet<IndexEntry> index;
/**
* A Stream Address Buffer (SAB) tracks a window of consecutive
* spatial regions. The SAB mantains a pointer to the sequence in the
* history buffer, initiallly set to the pointer taken from the index
* table
*/
std::deque<CompactorEntry*> streamAddressBuffer;
/**
* Updates the prefetcher structures upon an instruction retired
* @param pc PC of the instruction being retired
*/
void notifyRetiredInst(const Addr pc);
/**
* Probe Listener to handle probe events from the CPU
*/
class PrefetchListenerPC : public ProbeListenerArgBase<Addr>
{
public:
PrefetchListenerPC(PIFPrefetcher &_parent, ProbeManager *pm,
const std::string &name)
: ProbeListenerArgBase(pm, name),
parent(_parent) {}
void notify(const Addr& pc) override;
protected:
PIFPrefetcher &parent;
};
/** Array of probe listeners */
std::vector<PrefetchListenerPC *> listenersPC;
public:
PIFPrefetcher(const PIFPrefetcherParams *p);
~PIFPrefetcher() {}
void calculatePrefetch(const PrefetchInfo &pfi,
std::vector<AddrPriority> &addresses);
/**
* Add a SimObject and a probe name to monitor the retired instructions
* @param obj The SimObject pointer to listen from
* @param name The probe name
*/
void addEventProbeRetiredInsts(SimObject *obj, const char *name);
};
#endif // __MEM_CACHE_PREFETCH_PIF_HH__