/**
 * 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.
 */

#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);
}