indirect_memory.cc revision 13963
112852Sgabeblack@google.com/** 212852Sgabeblack@google.com * Copyright (c) 2018 Metempsy Technology Consulting 312852Sgabeblack@google.com * All rights reserved. 412852Sgabeblack@google.com * 512852Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 612852Sgabeblack@google.com * modification, are permitted provided that the following conditions are 712852Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 812852Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 912852Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 1012852Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 1112852Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 1212852Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 1312852Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 1412852Sgabeblack@google.com * this software without specific prior written permission. 1512852Sgabeblack@google.com * 1612852Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1712852Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1812852Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1912852Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2012852Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2112852Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2212852Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2312852Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2412852Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2512852Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2612852Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2712852Sgabeblack@google.com * 2812852Sgabeblack@google.com * Authors: Javier Bueno 2912852Sgabeblack@google.com */ 3012997Sgabeblack@google.com 3112997Sgabeblack@google.com #include "mem/cache/prefetch/indirect_memory.hh" 3212997Sgabeblack@google.com 3312997Sgabeblack@google.com #include "mem/cache/base.hh" 3412997Sgabeblack@google.com #include "mem/cache/prefetch/associative_set_impl.hh" 3513335Sgabeblack@google.com #include "params/IndirectMemoryPrefetcher.hh" 3612997Sgabeblack@google.com 3712997Sgabeblack@google.comIndirectMemoryPrefetcher::IndirectMemoryPrefetcher( 3812997Sgabeblack@google.com const IndirectMemoryPrefetcherParams *p) : QueuedPrefetcher(p), 3913324Sgabeblack@google.com maxPrefetchDistance(p->max_prefetch_distance), 4012852Sgabeblack@google.com shiftValues(p->shift_values), prefetchThreshold(p->prefetch_threshold), 4113312Sgabeblack@google.com streamCounterThreshold(p->stream_counter_threshold), 4212852Sgabeblack@google.com streamingDistance(p->streaming_distance), 4312852Sgabeblack@google.com prefetchTable(p->pt_table_assoc, p->pt_table_entries, 4412852Sgabeblack@google.com p->pt_table_indexing_policy, p->pt_table_replacement_policy, 4512852Sgabeblack@google.com PrefetchTableEntry(p->num_indirect_counter_bits)), 4612997Sgabeblack@google.com ipd(p->ipd_table_assoc, p->ipd_table_entries, p->ipd_table_indexing_policy, 4712997Sgabeblack@google.com p->ipd_table_replacement_policy, 4812997Sgabeblack@google.com IndirectPatternDetectorEntry(p->addr_array_len, shiftValues.size())), 4912997Sgabeblack@google.com ipdEntryTrackingMisses(nullptr), 5012997Sgabeblack@google.com#if THE_ISA != NULL_ISA 5112997Sgabeblack@google.com byteOrder(TheISA::GuestByteOrder) 5212997Sgabeblack@google.com#else 5312997Sgabeblack@google.com byteOrder((ByteOrder) -1) 5412852Sgabeblack@google.com#endif 5512997Sgabeblack@google.com{ 5612997Sgabeblack@google.com fatal_if(byteOrder == static_cast<ByteOrder>(-1), 5712852Sgabeblack@google.com "This prefetcher requires a defined ISA\n"); 5812997Sgabeblack@google.com} 5912852Sgabeblack@google.com 6012852Sgabeblack@google.comvoid 6112852Sgabeblack@google.comIndirectMemoryPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 6212997Sgabeblack@google.com std::vector<AddrPriority> &addresses) 6312997Sgabeblack@google.com{ 6412997Sgabeblack@google.com // This prefetcher requires a PC 6512852Sgabeblack@google.com if (!pfi.hasPC()) { 6613324Sgabeblack@google.com return; 6713324Sgabeblack@google.com } 6813324Sgabeblack@google.com 6913312Sgabeblack@google.com bool is_secure = pfi.isSecure(); 7012997Sgabeblack@google.com Addr pc = pfi.getPC(); 7112997Sgabeblack@google.com Addr addr = pfi.getAddr(); 7213312Sgabeblack@google.com bool miss = pfi.isCacheMiss(); 7313401Sgabeblack@google.com 7412997Sgabeblack@google.com checkAccessMatchOnActiveEntries(addr); 7512997Sgabeblack@google.com 7612997Sgabeblack@google.com // First check if this is a miss, if the prefetcher is tracking misses 7713312Sgabeblack@google.com if (ipdEntryTrackingMisses != nullptr && miss) { 7812997Sgabeblack@google.com // Check if the entry tracking misses has already set its second index 7912997Sgabeblack@google.com if (!ipdEntryTrackingMisses->secondIndexSet) { 8013312Sgabeblack@google.com trackMissIndex1(addr); 8113312Sgabeblack@google.com } else { 8212997Sgabeblack@google.com trackMissIndex2(addr); 8312997Sgabeblack@google.com } 8412997Sgabeblack@google.com } else { 8512997Sgabeblack@google.com // if misses are not being tracked, attempt to detect stream accesses 8612997Sgabeblack@google.com PrefetchTableEntry *pt_entry = 8713312Sgabeblack@google.com prefetchTable.findEntry(pc, false /* unused */); 8813312Sgabeblack@google.com if (pt_entry != nullptr) { 8912997Sgabeblack@google.com prefetchTable.accessEntry(pt_entry); 9013312Sgabeblack@google.com 9113312Sgabeblack@google.com if (pt_entry->address != addr) { 9212997Sgabeblack@google.com // Streaming access found 9312997Sgabeblack@google.com pt_entry->streamCounter += 1; 9412997Sgabeblack@google.com if (pt_entry->streamCounter >= streamCounterThreshold) { 9512997Sgabeblack@google.com int64_t delta = addr - pt_entry->address; 9613313Sgabeblack@google.com for (unsigned int i = 1; i <= streamingDistance; i += 1) { 9712997Sgabeblack@google.com addresses.push_back(AddrPriority(addr + delta * i, 0)); 9812997Sgabeblack@google.com } 9912997Sgabeblack@google.com } 10012997Sgabeblack@google.com pt_entry->address = addr; 10112997Sgabeblack@google.com pt_entry->secure = is_secure; 10213312Sgabeblack@google.com 10312997Sgabeblack@google.com 10412997Sgabeblack@google.com // if this is a read, read the data from the cache and assume 10512997Sgabeblack@google.com // it is an index (this is only possible if the data is already 10612997Sgabeblack@google.com // in the cache), also, only indexes up to 8 bytes are 10713312Sgabeblack@google.com // considered 10812852Sgabeblack@google.com 10912852Sgabeblack@google.com if (!miss && !pfi.isWrite() && pfi.getSize() <= 8) { 11012902Sgabeblack@google.com int64_t index = 0; 11113313Sgabeblack@google.com bool read_index = true; 11212902Sgabeblack@google.com switch(pfi.getSize()) { 11312902Sgabeblack@google.com case sizeof(uint8_t): 11413401Sgabeblack@google.com index = pfi.get<uint8_t>(byteOrder); 11513313Sgabeblack@google.com break; 11613313Sgabeblack@google.com case sizeof(uint16_t): 11713313Sgabeblack@google.com index = pfi.get<uint16_t>(byteOrder); 11813313Sgabeblack@google.com break; 11913313Sgabeblack@google.com case sizeof(uint32_t): 12012902Sgabeblack@google.com index = pfi.get<uint32_t>(byteOrder); 12112902Sgabeblack@google.com break; 12212852Sgabeblack@google.com case sizeof(uint64_t): 12312997Sgabeblack@google.com index = pfi.get<uint64_t>(byteOrder); 12412852Sgabeblack@google.com break; 12513312Sgabeblack@google.com default: 12612997Sgabeblack@google.com // Ignore non-power-of-two sizes 12712997Sgabeblack@google.com read_index = false; 12812997Sgabeblack@google.com } 12912852Sgabeblack@google.com if (read_index && !pt_entry->enabled) { 13012852Sgabeblack@google.com // Not enabled (no pattern detected in this stream), 13112852Sgabeblack@google.com // add or update an entry in the pattern detector and 13212997Sgabeblack@google.com // start tracking misses 13312852Sgabeblack@google.com allocateOrUpdateIPDEntry(pt_entry, index); 13413324Sgabeblack@google.com } else if (read_index) { 13513324Sgabeblack@google.com // Enabled entry, update the index 13613324Sgabeblack@google.com pt_entry->index = index; 13713401Sgabeblack@google.com if (!pt_entry->increasedIndirectCounter) { 13812997Sgabeblack@google.com pt_entry->indirectCounter--; 13912997Sgabeblack@google.com } else { 14012997Sgabeblack@google.com // Set this to false, to see if the new index 14112852Sgabeblack@google.com // has any match 14212852Sgabeblack@google.com pt_entry->increasedIndirectCounter = false; 14312852Sgabeblack@google.com } 14412997Sgabeblack@google.com 14512997Sgabeblack@google.com // If the counter is high enough, start prefetching 14612852Sgabeblack@google.com if (pt_entry->indirectCounter > prefetchThreshold) { 14713324Sgabeblack@google.com unsigned distance = maxPrefetchDistance * 14813324Sgabeblack@google.com pt_entry->indirectCounter.calcSaturation(); 14913324Sgabeblack@google.com for (int delta = 1; delta < distance; delta += 1) { 15013401Sgabeblack@google.com Addr pf_addr = pt_entry->baseAddr + 15113312Sgabeblack@google.com (pt_entry->index << pt_entry->shift); 15213312Sgabeblack@google.com addresses.push_back(AddrPriority(pf_addr, 0)); 15312997Sgabeblack@google.com } 15412852Sgabeblack@google.com } 15512852Sgabeblack@google.com } 15612852Sgabeblack@google.com } 15712997Sgabeblack@google.com } 15812852Sgabeblack@google.com } else { 15913312Sgabeblack@google.com pt_entry = prefetchTable.findVictim(pc); 16012997Sgabeblack@google.com assert(pt_entry != nullptr); 16112997Sgabeblack@google.com prefetchTable.insertEntry(pc, false /* unused */, pt_entry); 16212997Sgabeblack@google.com pt_entry->address = addr; 16312852Sgabeblack@google.com pt_entry->secure = is_secure; 16412852Sgabeblack@google.com } 16512852Sgabeblack@google.com } 16612852Sgabeblack@google.com} 16712852Sgabeblack@google.com 16813324Sgabeblack@google.comvoid 16913324Sgabeblack@google.comIndirectMemoryPrefetcher::allocateOrUpdateIPDEntry( 17013324Sgabeblack@google.com const PrefetchTableEntry *pt_entry, int64_t index) 17113401Sgabeblack@google.com{ 17212997Sgabeblack@google.com // The address of the pt_entry is used to index the IPD 17312997Sgabeblack@google.com Addr ipd_entry_addr = (Addr) pt_entry; 17412997Sgabeblack@google.com IndirectPatternDetectorEntry *ipd_entry = ipd.findEntry(ipd_entry_addr, 17512852Sgabeblack@google.com false/* unused */); 17612852Sgabeblack@google.com if (ipd_entry != nullptr) { 17712852Sgabeblack@google.com ipd.accessEntry(ipd_entry); 17812997Sgabeblack@google.com if (!ipd_entry->secondIndexSet) { 17912997Sgabeblack@google.com // Second time we see an index, fill idx2 18012852Sgabeblack@google.com ipd_entry->idx2 = index; 18113324Sgabeblack@google.com ipd_entry->secondIndexSet = true; 18213324Sgabeblack@google.com ipdEntryTrackingMisses = ipd_entry; 18313324Sgabeblack@google.com } else { 18413401Sgabeblack@google.com // Third access! no pattern has been found so far, 18513312Sgabeblack@google.com // release the IPD entry 18613312Sgabeblack@google.com ipd_entry->reset(); 18712997Sgabeblack@google.com ipdEntryTrackingMisses = nullptr; 18812852Sgabeblack@google.com } 18912852Sgabeblack@google.com } else { 19012852Sgabeblack@google.com ipd_entry = ipd.findVictim(ipd_entry_addr); 19112997Sgabeblack@google.com assert(ipd_entry != nullptr); 19212852Sgabeblack@google.com ipd.insertEntry(ipd_entry_addr, false /* unused */, ipd_entry); 19313312Sgabeblack@google.com ipd_entry->idx1 = index; 19412852Sgabeblack@google.com ipdEntryTrackingMisses = ipd_entry; 19512852Sgabeblack@google.com } 19612852Sgabeblack@google.com} 19712852Sgabeblack@google.com 19812852Sgabeblack@google.comvoid 19913324Sgabeblack@google.comIndirectMemoryPrefetcher::trackMissIndex1(Addr miss_addr) 20013324Sgabeblack@google.com{ 20113324Sgabeblack@google.com IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; 20213401Sgabeblack@google.com // If the second index is not set, we are just filling the baseAddr 20312852Sgabeblack@google.com // vector 20412852Sgabeblack@google.com assert(entry->numMisses < entry->baseAddr.size()); 20512852Sgabeblack@google.com std::vector<Addr> &ba_array = entry->baseAddr[entry->numMisses]; 20612997Sgabeblack@google.com int idx = 0; 20712852Sgabeblack@google.com for (int shift : shiftValues) { 20813324Sgabeblack@google.com ba_array[idx] = miss_addr - (entry->idx1 << shift); 20913324Sgabeblack@google.com idx += 1; 21013324Sgabeblack@google.com } 21113401Sgabeblack@google.com entry->numMisses += 1; 21212852Sgabeblack@google.com if (entry->numMisses == entry->baseAddr.size()) { 21312852Sgabeblack@google.com // stop tracking misses once we have tracked enough 21412852Sgabeblack@google.com ipdEntryTrackingMisses = nullptr; 21512997Sgabeblack@google.com } 21612852Sgabeblack@google.com} 21713312Sgabeblack@google.comvoid 21813312Sgabeblack@google.comIndirectMemoryPrefetcher::trackMissIndex2(Addr miss_addr) 21912997Sgabeblack@google.com{ 22012852Sgabeblack@google.com IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; 22112852Sgabeblack@google.com // Second index is filled, compare the addresses generated during 22212852Sgabeblack@google.com // the previous misses (using idx1) against newly generated values 22312852Sgabeblack@google.com // using idx2, if a match is found, fill the additional fields 22412852Sgabeblack@google.com // of the PT entry 22513312Sgabeblack@google.com for (int midx = 0; midx < entry->numMisses; midx += 1) 22612852Sgabeblack@google.com { 22712852Sgabeblack@google.com std::vector<Addr> &ba_array = entry->baseAddr[midx]; 22812852Sgabeblack@google.com int idx = 0; 22912852Sgabeblack@google.com for (int shift : shiftValues) { 23012997Sgabeblack@google.com if (ba_array[idx] == (miss_addr - (entry->idx2 << shift))) { 23112852Sgabeblack@google.com // Match found! 23213312Sgabeblack@google.com // Fill the corresponding pt_entry 23313312Sgabeblack@google.com PrefetchTableEntry *pt_entry = 23412997Sgabeblack@google.com (PrefetchTableEntry *) entry->getTag(); 23512852Sgabeblack@google.com pt_entry->baseAddr = ba_array[idx]; 23612852Sgabeblack@google.com pt_entry->shift = shift; 23712852Sgabeblack@google.com pt_entry->enabled = true; 23812852Sgabeblack@google.com pt_entry->indirectCounter.reset(); 23912852Sgabeblack@google.com // Release the current IPD Entry 24012997Sgabeblack@google.com entry->reset(); 24112852Sgabeblack@google.com // Do not track more misses 24212852Sgabeblack@google.com ipdEntryTrackingMisses = nullptr; 24312852Sgabeblack@google.com return; 24412997Sgabeblack@google.com } 24512852Sgabeblack@google.com idx += 1; 24613312Sgabeblack@google.com } 24713312Sgabeblack@google.com } 24812997Sgabeblack@google.com} 24912852Sgabeblack@google.com 25012852Sgabeblack@google.comvoid 25112852Sgabeblack@google.comIndirectMemoryPrefetcher::checkAccessMatchOnActiveEntries(Addr addr) 25212852Sgabeblack@google.com{ 25312852Sgabeblack@google.com for (auto &pt_entry : prefetchTable) { 25412997Sgabeblack@google.com if (pt_entry.enabled) { 25512852Sgabeblack@google.com if (addr == pt_entry.baseAddr + 25612852Sgabeblack@google.com (pt_entry.index << pt_entry.shift)) { 25712852Sgabeblack@google.com pt_entry.indirectCounter++; 25812911Sgabeblack@google.com pt_entry.increasedIndirectCounter = true; 25912997Sgabeblack@google.com } 26012911Sgabeblack@google.com } 26113312Sgabeblack@google.com } 26213312Sgabeblack@google.com} 26312997Sgabeblack@google.com 26412911Sgabeblack@google.comIndirectMemoryPrefetcher* 26512911Sgabeblack@google.comIndirectMemoryPrefetcherParams::create() 26612911Sgabeblack@google.com{ 26712911Sgabeblack@google.com return new IndirectMemoryPrefetcher(this); 26812911Sgabeblack@google.com} 26913312Sgabeblack@google.com