113667Sjavier.bueno@metempsy.com/** 213667Sjavier.bueno@metempsy.com * Copyright (c) 2018 Metempsy Technology Consulting 313667Sjavier.bueno@metempsy.com * All rights reserved. 413667Sjavier.bueno@metempsy.com * 513667Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without 613667Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are 713667Sjavier.bueno@metempsy.com * met: redistributions of source code must retain the above copyright 813667Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer; 913667Sjavier.bueno@metempsy.com * redistributions in binary form must reproduce the above copyright 1013667Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113667Sjavier.bueno@metempsy.com * documentation and/or other materials provided with the distribution; 1213667Sjavier.bueno@metempsy.com * neither the name of the copyright holders nor the names of its 1313667Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from 1413667Sjavier.bueno@metempsy.com * this software without specific prior written permission. 1513667Sjavier.bueno@metempsy.com * 1613667Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713667Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813667Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913667Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013667Sjavier.bueno@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113667Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213667Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313667Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413667Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513667Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613667Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713667Sjavier.bueno@metempsy.com * 2813667Sjavier.bueno@metempsy.com * Authors: Javier Bueno 2913667Sjavier.bueno@metempsy.com */ 3013667Sjavier.bueno@metempsy.com 3113667Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/delta_correlating_prediction_tables.hh" 3213667Sjavier.bueno@metempsy.com 3313667Sjavier.bueno@metempsy.com#include "debug/HWPrefetch.hh" 3413667Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/associative_set_impl.hh" 3513667Sjavier.bueno@metempsy.com#include "params/DCPTPrefetcher.hh" 3613667Sjavier.bueno@metempsy.com#include "params/DeltaCorrelatingPredictionTables.hh" 3713667Sjavier.bueno@metempsy.com 3813667Sjavier.bueno@metempsy.comDeltaCorrelatingPredictionTables::DeltaCorrelatingPredictionTables( 3913667Sjavier.bueno@metempsy.com DeltaCorrelatingPredictionTablesParams *p) : SimObject(p), 4013667Sjavier.bueno@metempsy.com deltaBits(p->delta_bits), deltaMaskBits(p->delta_mask_bits), 4113667Sjavier.bueno@metempsy.com table(p->table_assoc, p->table_entries, p->table_indexing_policy, 4213667Sjavier.bueno@metempsy.com p->table_replacement_policy, DCPTEntry(p->deltas_per_entry)) 4313667Sjavier.bueno@metempsy.com{ 4413667Sjavier.bueno@metempsy.com} 4513667Sjavier.bueno@metempsy.com 4613667Sjavier.bueno@metempsy.comvoid 4713667Sjavier.bueno@metempsy.comDeltaCorrelatingPredictionTables::DCPTEntry::reset() 4813667Sjavier.bueno@metempsy.com{ 4913667Sjavier.bueno@metempsy.com for (auto &delta : deltas) { 5013667Sjavier.bueno@metempsy.com delta = 0; 5113667Sjavier.bueno@metempsy.com } 5213667Sjavier.bueno@metempsy.com lastAddress = 0; 5313667Sjavier.bueno@metempsy.com deltaPointer = 0; 5413667Sjavier.bueno@metempsy.com} 5513667Sjavier.bueno@metempsy.com 5613667Sjavier.bueno@metempsy.comvoid 5713667Sjavier.bueno@metempsy.comDeltaCorrelatingPredictionTables::DCPTEntry::addAddress(Addr address, 5813667Sjavier.bueno@metempsy.com unsigned int delta_bits) 5913667Sjavier.bueno@metempsy.com{ 6013667Sjavier.bueno@metempsy.com if ((address - lastAddress) != 0) { 6113667Sjavier.bueno@metempsy.com Addr delta = address - lastAddress; 6213667Sjavier.bueno@metempsy.com // Account for the sign bit 6313667Sjavier.bueno@metempsy.com Addr max_positive_delta = (1 << (delta_bits-1)) - 1; 6413667Sjavier.bueno@metempsy.com if (address > lastAddress) { 6513667Sjavier.bueno@metempsy.com // check positive delta overflow 6613667Sjavier.bueno@metempsy.com if (delta > max_positive_delta) { 6713667Sjavier.bueno@metempsy.com delta = 0; 6813667Sjavier.bueno@metempsy.com } 6913667Sjavier.bueno@metempsy.com } else { 7013667Sjavier.bueno@metempsy.com // check negative delta overflow 7113667Sjavier.bueno@metempsy.com if (lastAddress - address > (max_positive_delta + 1)) { 7213667Sjavier.bueno@metempsy.com delta = 0; 7313667Sjavier.bueno@metempsy.com } 7413667Sjavier.bueno@metempsy.com } 7513667Sjavier.bueno@metempsy.com deltas[deltaPointer] = delta; 7613667Sjavier.bueno@metempsy.com deltaPointer = (deltaPointer + 1) % deltas.size(); 7713667Sjavier.bueno@metempsy.com lastAddress = address; 7813667Sjavier.bueno@metempsy.com } 7913667Sjavier.bueno@metempsy.com} 8013667Sjavier.bueno@metempsy.com 8113667Sjavier.bueno@metempsy.comvoid 8213667Sjavier.bueno@metempsy.comDeltaCorrelatingPredictionTables::DCPTEntry::getCandidates( 8313667Sjavier.bueno@metempsy.com std::vector<QueuedPrefetcher::AddrPriority> &pfs, unsigned int mask) const 8413667Sjavier.bueno@metempsy.com{ 8513667Sjavier.bueno@metempsy.com // most recent index 8613667Sjavier.bueno@metempsy.com unsigned int last = (deltaPointer - 1) % deltas.size(); 8713667Sjavier.bueno@metempsy.com // second most recent index 8813667Sjavier.bueno@metempsy.com unsigned int last_prev = (deltaPointer - 2) % deltas.size(); 8913667Sjavier.bueno@metempsy.com int delta_0 = deltas[last_prev]; 9013667Sjavier.bueno@metempsy.com int delta_1 = deltas[last]; 9113667Sjavier.bueno@metempsy.com 9213667Sjavier.bueno@metempsy.com // a delta 0 means that it overflowed, we can not match it 9313667Sjavier.bueno@metempsy.com if (delta_0 == 0 || delta_1 == 0) { 9413667Sjavier.bueno@metempsy.com return; 9513667Sjavier.bueno@metempsy.com } 9613667Sjavier.bueno@metempsy.com 9713667Sjavier.bueno@metempsy.com // Try to find the two most recent deltas in a previous position on the 9813667Sjavier.bueno@metempsy.com // delta circular array, if found, start issuing prefetches using the 9913667Sjavier.bueno@metempsy.com // remaining deltas (adding each delta to the last Addr to generate the 10013667Sjavier.bueno@metempsy.com // prefetched address. 10113667Sjavier.bueno@metempsy.com 10213667Sjavier.bueno@metempsy.com // oldest index 10313667Sjavier.bueno@metempsy.com int idx_0 = deltaPointer + 1; 10413667Sjavier.bueno@metempsy.com // second oldest index 10513667Sjavier.bueno@metempsy.com int idx_1 = deltaPointer + 2; 10613667Sjavier.bueno@metempsy.com for (int i = 0; i < deltas.size() - 2; i += 1) { 10713667Sjavier.bueno@metempsy.com int this_delta_0 = deltas[(idx_0 + i) % deltas.size()]; 10813667Sjavier.bueno@metempsy.com int this_delta_1 = deltas[(idx_1 + i) % deltas.size()]; 10913667Sjavier.bueno@metempsy.com if ((this_delta_0 >> mask) == (delta_0 >> mask) && 11013667Sjavier.bueno@metempsy.com (this_delta_1 >> mask) == (delta_1 >> mask)) { 11113667Sjavier.bueno@metempsy.com Addr addr = lastAddress; 11213667Sjavier.bueno@metempsy.com // Pattern found, issue prefetches with the remaining deltas after 11313667Sjavier.bueno@metempsy.com // this pair 11413667Sjavier.bueno@metempsy.com i += 2; // skip the matching pair 11513667Sjavier.bueno@metempsy.com do { 11613667Sjavier.bueno@metempsy.com int pf_delta = deltas[(idx_0 + i) % deltas.size()]; 11713667Sjavier.bueno@metempsy.com addr += pf_delta; 11813667Sjavier.bueno@metempsy.com pfs.push_back(QueuedPrefetcher::AddrPriority(addr, 0)); 11913667Sjavier.bueno@metempsy.com i += 1; 12013667Sjavier.bueno@metempsy.com } while (i < deltas.size() - 2); 12113667Sjavier.bueno@metempsy.com } 12213667Sjavier.bueno@metempsy.com } 12313667Sjavier.bueno@metempsy.com} 12413667Sjavier.bueno@metempsy.com 12513667Sjavier.bueno@metempsy.comvoid 12613667Sjavier.bueno@metempsy.comDeltaCorrelatingPredictionTables::calculatePrefetch( 12713667Sjavier.bueno@metempsy.com const BasePrefetcher::PrefetchInfo &pfi, 12813667Sjavier.bueno@metempsy.com std::vector<QueuedPrefetcher::AddrPriority> &addresses) 12913667Sjavier.bueno@metempsy.com{ 13013667Sjavier.bueno@metempsy.com if (!pfi.hasPC()) { 13113667Sjavier.bueno@metempsy.com DPRINTF(HWPrefetch, "Ignoring request with no PC.\n"); 13213667Sjavier.bueno@metempsy.com return; 13313667Sjavier.bueno@metempsy.com } 13413667Sjavier.bueno@metempsy.com Addr address = pfi.getAddr(); 13513667Sjavier.bueno@metempsy.com Addr pc = pfi.getPC(); 13613667Sjavier.bueno@metempsy.com // Look up table entry, is_secure is unused in findEntry because we 13713667Sjavier.bueno@metempsy.com // index using the pc 13813667Sjavier.bueno@metempsy.com DCPTEntry *entry = table.findEntry(pc, false /* unused */); 13913667Sjavier.bueno@metempsy.com if (entry != nullptr) { 14013667Sjavier.bueno@metempsy.com entry->addAddress(address, deltaBits); 14113667Sjavier.bueno@metempsy.com //Delta correlating 14213667Sjavier.bueno@metempsy.com entry->getCandidates(addresses, deltaMaskBits); 14313667Sjavier.bueno@metempsy.com } else { 14413667Sjavier.bueno@metempsy.com entry = table.findVictim(pc); 14513667Sjavier.bueno@metempsy.com 14613667Sjavier.bueno@metempsy.com table.insertEntry(pc, false /* unused */, entry); 14713667Sjavier.bueno@metempsy.com 14813667Sjavier.bueno@metempsy.com entry->lastAddress = address; 14913667Sjavier.bueno@metempsy.com } 15013667Sjavier.bueno@metempsy.com} 15113667Sjavier.bueno@metempsy.com 15213667Sjavier.bueno@metempsy.comDeltaCorrelatingPredictionTables * 15313667Sjavier.bueno@metempsy.comDeltaCorrelatingPredictionTablesParams::create() 15413667Sjavier.bueno@metempsy.com{ 15513667Sjavier.bueno@metempsy.com return new DeltaCorrelatingPredictionTables(this); 15613667Sjavier.bueno@metempsy.com} 15713667Sjavier.bueno@metempsy.com 15813667Sjavier.bueno@metempsy.comDCPTPrefetcher::DCPTPrefetcher(const DCPTPrefetcherParams *p) 15913667Sjavier.bueno@metempsy.com : QueuedPrefetcher(p), dcpt(*p->dcpt) 16013667Sjavier.bueno@metempsy.com{ 16113667Sjavier.bueno@metempsy.com} 16213667Sjavier.bueno@metempsy.com 16313667Sjavier.bueno@metempsy.comvoid 16413667Sjavier.bueno@metempsy.comDCPTPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 16513667Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) 16613667Sjavier.bueno@metempsy.com{ 16713667Sjavier.bueno@metempsy.com dcpt.calculatePrefetch(pfi, addresses); 16813667Sjavier.bueno@metempsy.com} 16913667Sjavier.bueno@metempsy.com 17013667Sjavier.bueno@metempsy.comDCPTPrefetcher* 17113667Sjavier.bueno@metempsy.comDCPTPrefetcherParams::create() 17213667Sjavier.bueno@metempsy.com{ 17313667Sjavier.bueno@metempsy.com return new DCPTPrefetcher(this); 17413667Sjavier.bueno@metempsy.com} 175