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