indirect_memory.cc revision 13772
113772Sjavier.bueno@metempsy.com/** 213772Sjavier.bueno@metempsy.com * Copyright (c) 2018 Metempsy Technology Consulting 313772Sjavier.bueno@metempsy.com * All rights reserved. 413772Sjavier.bueno@metempsy.com * 513772Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without 613772Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are 713772Sjavier.bueno@metempsy.com * met: redistributions of source code must retain the above copyright 813772Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer; 913772Sjavier.bueno@metempsy.com * redistributions in binary form must reproduce the above copyright 1013772Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113772Sjavier.bueno@metempsy.com * documentation and/or other materials provided with the distribution; 1213772Sjavier.bueno@metempsy.com * neither the name of the copyright holders nor the names of its 1313772Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from 1413772Sjavier.bueno@metempsy.com * this software without specific prior written permission. 1513772Sjavier.bueno@metempsy.com * 1613772Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713772Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813772Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913772Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013772Sjavier.bueno@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113772Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213772Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313772Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413772Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513772Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613772Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713772Sjavier.bueno@metempsy.com * 2813772Sjavier.bueno@metempsy.com * Authors: Javier Bueno 2913772Sjavier.bueno@metempsy.com */ 3013772Sjavier.bueno@metempsy.com 3113772Sjavier.bueno@metempsy.com #include "mem/cache/prefetch/indirect_memory.hh" 3213772Sjavier.bueno@metempsy.com 3313772Sjavier.bueno@metempsy.com #include "mem/cache/base.hh" 3413772Sjavier.bueno@metempsy.com #include "mem/cache/prefetch/associative_set_impl.hh" 3513772Sjavier.bueno@metempsy.com #include "params/IndirectMemoryPrefetcher.hh" 3613772Sjavier.bueno@metempsy.com 3713772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::IndirectMemoryPrefetcher( 3813772Sjavier.bueno@metempsy.com const IndirectMemoryPrefetcherParams *p) : QueuedPrefetcher(p), 3913772Sjavier.bueno@metempsy.com maxPrefetchDistance(p->max_prefetch_distance), 4013772Sjavier.bueno@metempsy.com shiftValues(p->shift_values), prefetchThreshold(p->prefetch_threshold), 4113772Sjavier.bueno@metempsy.com maxIndirectCounterValue(p->max_indirect_counter_value), 4213772Sjavier.bueno@metempsy.com streamCounterThreshold(p->stream_counter_threshold), 4313772Sjavier.bueno@metempsy.com streamingDistance(p->streaming_distance), 4413772Sjavier.bueno@metempsy.com prefetchTable(p->pt_table_assoc, p->pt_table_entries, 4513772Sjavier.bueno@metempsy.com p->pt_table_indexing_policy, p->pt_table_replacement_policy), 4613772Sjavier.bueno@metempsy.com ipd(p->ipd_table_assoc, p->ipd_table_entries, p->ipd_table_indexing_policy, 4713772Sjavier.bueno@metempsy.com p->ipd_table_replacement_policy, 4813772Sjavier.bueno@metempsy.com IndirectPatternDetectorEntry(p->addr_array_len, shiftValues.size())), 4913772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses(nullptr), 5013772Sjavier.bueno@metempsy.com#if THE_ISA != NULL_ISA 5113772Sjavier.bueno@metempsy.com byteOrder(TheISA::GuestByteOrder) 5213772Sjavier.bueno@metempsy.com#else 5313772Sjavier.bueno@metempsy.com byteOrder((ByteOrder) -1) 5413772Sjavier.bueno@metempsy.com#endif 5513772Sjavier.bueno@metempsy.com{ 5613772Sjavier.bueno@metempsy.com fatal_if(byteOrder == -1, "This prefetcher requires a defined ISA\n"); 5713772Sjavier.bueno@metempsy.com} 5813772Sjavier.bueno@metempsy.com 5913772Sjavier.bueno@metempsy.comvoid 6013772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 6113772Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) 6213772Sjavier.bueno@metempsy.com{ 6313772Sjavier.bueno@metempsy.com // This prefetcher requires a PC 6413772Sjavier.bueno@metempsy.com if (!pfi.hasPC()) { 6513772Sjavier.bueno@metempsy.com return; 6613772Sjavier.bueno@metempsy.com } 6713772Sjavier.bueno@metempsy.com 6813772Sjavier.bueno@metempsy.com bool is_secure = pfi.isSecure(); 6913772Sjavier.bueno@metempsy.com Addr pc = pfi.getPC(); 7013772Sjavier.bueno@metempsy.com Addr addr = pfi.getAddr(); 7113772Sjavier.bueno@metempsy.com bool miss = pfi.isCacheMiss(); 7213772Sjavier.bueno@metempsy.com 7313772Sjavier.bueno@metempsy.com checkAccessMatchOnActiveEntries(addr); 7413772Sjavier.bueno@metempsy.com 7513772Sjavier.bueno@metempsy.com // First check if this is a miss, if the prefetcher is tracking misses 7613772Sjavier.bueno@metempsy.com if (ipdEntryTrackingMisses != nullptr && miss) { 7713772Sjavier.bueno@metempsy.com // Check if the entry tracking misses has already set its second index 7813772Sjavier.bueno@metempsy.com if (!ipdEntryTrackingMisses->secondIndexSet) { 7913772Sjavier.bueno@metempsy.com trackMissIndex1(addr); 8013772Sjavier.bueno@metempsy.com } else { 8113772Sjavier.bueno@metempsy.com trackMissIndex2(addr); 8213772Sjavier.bueno@metempsy.com } 8313772Sjavier.bueno@metempsy.com } else { 8413772Sjavier.bueno@metempsy.com // if misses are not being tracked, attempt to detect stream accesses 8513772Sjavier.bueno@metempsy.com PrefetchTableEntry *pt_entry = 8613772Sjavier.bueno@metempsy.com prefetchTable.findEntry(pc, false /* unused */); 8713772Sjavier.bueno@metempsy.com if (pt_entry != nullptr) { 8813772Sjavier.bueno@metempsy.com prefetchTable.accessEntry(pt_entry); 8913772Sjavier.bueno@metempsy.com 9013772Sjavier.bueno@metempsy.com if (pt_entry->address != addr) { 9113772Sjavier.bueno@metempsy.com // Streaming access found 9213772Sjavier.bueno@metempsy.com pt_entry->streamCounter += 1; 9313772Sjavier.bueno@metempsy.com if (pt_entry->streamCounter >= streamCounterThreshold) { 9413772Sjavier.bueno@metempsy.com int64_t delta = addr - pt_entry->address; 9513772Sjavier.bueno@metempsy.com for (unsigned int i = 1; i <= streamingDistance; i += 1) { 9613772Sjavier.bueno@metempsy.com addresses.push_back(AddrPriority(addr + delta * i, 0)); 9713772Sjavier.bueno@metempsy.com } 9813772Sjavier.bueno@metempsy.com } 9913772Sjavier.bueno@metempsy.com pt_entry->address = addr; 10013772Sjavier.bueno@metempsy.com pt_entry->secure = is_secure; 10113772Sjavier.bueno@metempsy.com 10213772Sjavier.bueno@metempsy.com 10313772Sjavier.bueno@metempsy.com // if this is a read, read the data from the cache and assume 10413772Sjavier.bueno@metempsy.com // it is an index (this is only possible if the data is already 10513772Sjavier.bueno@metempsy.com // in the cache), also, only indexes up to 8 bytes are 10613772Sjavier.bueno@metempsy.com // considered 10713772Sjavier.bueno@metempsy.com 10813772Sjavier.bueno@metempsy.com if (!miss && !pfi.isWrite() && pfi.getSize() <= 8) { 10913772Sjavier.bueno@metempsy.com int64_t index = 0; 11013772Sjavier.bueno@metempsy.com switch(pfi.getSize()) { 11113772Sjavier.bueno@metempsy.com case sizeof(uint8_t): 11213772Sjavier.bueno@metempsy.com index = pfi.get<uint8_t>(byteOrder); 11313772Sjavier.bueno@metempsy.com break; 11413772Sjavier.bueno@metempsy.com case sizeof(uint16_t): 11513772Sjavier.bueno@metempsy.com index = pfi.get<uint16_t>(byteOrder); 11613772Sjavier.bueno@metempsy.com break; 11713772Sjavier.bueno@metempsy.com case sizeof(uint32_t): 11813772Sjavier.bueno@metempsy.com index = pfi.get<uint32_t>(byteOrder); 11913772Sjavier.bueno@metempsy.com break; 12013772Sjavier.bueno@metempsy.com case sizeof(uint64_t): 12113772Sjavier.bueno@metempsy.com index = pfi.get<uint64_t>(byteOrder); 12213772Sjavier.bueno@metempsy.com break; 12313772Sjavier.bueno@metempsy.com default: 12413772Sjavier.bueno@metempsy.com panic("Invalid access size\n"); 12513772Sjavier.bueno@metempsy.com } 12613772Sjavier.bueno@metempsy.com if (!pt_entry->enabled) { 12713772Sjavier.bueno@metempsy.com // Not enabled (no pattern detected in this stream), 12813772Sjavier.bueno@metempsy.com // add or update an entry in the pattern detector and 12913772Sjavier.bueno@metempsy.com // start tracking misses 13013772Sjavier.bueno@metempsy.com allocateOrUpdateIPDEntry(pt_entry, index); 13113772Sjavier.bueno@metempsy.com } else { 13213772Sjavier.bueno@metempsy.com // Enabled entry, update the index 13313772Sjavier.bueno@metempsy.com pt_entry->index = index; 13413772Sjavier.bueno@metempsy.com if (!pt_entry->increasedIndirectCounter) { 13513772Sjavier.bueno@metempsy.com if (pt_entry->indirectCounter > 0) { 13613772Sjavier.bueno@metempsy.com pt_entry->indirectCounter -= 1; 13713772Sjavier.bueno@metempsy.com } 13813772Sjavier.bueno@metempsy.com } else { 13913772Sjavier.bueno@metempsy.com // Set this to false, to see if the new index 14013772Sjavier.bueno@metempsy.com // has any match 14113772Sjavier.bueno@metempsy.com pt_entry->increasedIndirectCounter = false; 14213772Sjavier.bueno@metempsy.com } 14313772Sjavier.bueno@metempsy.com 14413772Sjavier.bueno@metempsy.com // If the counter is high enough, start prefetching 14513772Sjavier.bueno@metempsy.com if (pt_entry->indirectCounter > prefetchThreshold) { 14613772Sjavier.bueno@metempsy.com unsigned distance = pt_entry->indirectCounter * 14713772Sjavier.bueno@metempsy.com maxPrefetchDistance / maxIndirectCounterValue; 14813772Sjavier.bueno@metempsy.com for (int delta = 1; delta < distance; delta += 1) { 14913772Sjavier.bueno@metempsy.com Addr pf_addr = pt_entry->baseAddr + 15013772Sjavier.bueno@metempsy.com (pt_entry->index << pt_entry->shift); 15113772Sjavier.bueno@metempsy.com addresses.push_back(AddrPriority(pf_addr, 0)); 15213772Sjavier.bueno@metempsy.com } 15313772Sjavier.bueno@metempsy.com } 15413772Sjavier.bueno@metempsy.com } 15513772Sjavier.bueno@metempsy.com } 15613772Sjavier.bueno@metempsy.com } 15713772Sjavier.bueno@metempsy.com } else { 15813772Sjavier.bueno@metempsy.com pt_entry = prefetchTable.findVictim(pc); 15913772Sjavier.bueno@metempsy.com assert(pt_entry != nullptr); 16013772Sjavier.bueno@metempsy.com prefetchTable.insertEntry(pc, false /* unused */, pt_entry); 16113772Sjavier.bueno@metempsy.com pt_entry->address = addr; 16213772Sjavier.bueno@metempsy.com pt_entry->secure = is_secure; 16313772Sjavier.bueno@metempsy.com } 16413772Sjavier.bueno@metempsy.com } 16513772Sjavier.bueno@metempsy.com} 16613772Sjavier.bueno@metempsy.com 16713772Sjavier.bueno@metempsy.comvoid 16813772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::allocateOrUpdateIPDEntry( 16913772Sjavier.bueno@metempsy.com const PrefetchTableEntry *pt_entry, int64_t index) 17013772Sjavier.bueno@metempsy.com{ 17113772Sjavier.bueno@metempsy.com // The address of the pt_entry is used to index the IPD 17213772Sjavier.bueno@metempsy.com Addr ipd_entry_addr = (Addr) pt_entry; 17313772Sjavier.bueno@metempsy.com IndirectPatternDetectorEntry *ipd_entry = ipd.findEntry(ipd_entry_addr, 17413772Sjavier.bueno@metempsy.com false/* unused */); 17513772Sjavier.bueno@metempsy.com if (ipd_entry != nullptr) { 17613772Sjavier.bueno@metempsy.com ipd.accessEntry(ipd_entry); 17713772Sjavier.bueno@metempsy.com if (!ipd_entry->secondIndexSet) { 17813772Sjavier.bueno@metempsy.com // Second time we see an index, fill idx2 17913772Sjavier.bueno@metempsy.com ipd_entry->idx2 = index; 18013772Sjavier.bueno@metempsy.com ipd_entry->secondIndexSet = true; 18113772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses = ipd_entry; 18213772Sjavier.bueno@metempsy.com } else { 18313772Sjavier.bueno@metempsy.com // Third access! no pattern has been found so far, 18413772Sjavier.bueno@metempsy.com // release the IPD entry 18513772Sjavier.bueno@metempsy.com ipd_entry->reset(); 18613772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses = nullptr; 18713772Sjavier.bueno@metempsy.com } 18813772Sjavier.bueno@metempsy.com } else { 18913772Sjavier.bueno@metempsy.com ipd_entry = ipd.findVictim(ipd_entry_addr); 19013772Sjavier.bueno@metempsy.com assert(ipd_entry != nullptr); 19113772Sjavier.bueno@metempsy.com ipd.insertEntry(ipd_entry_addr, false /* unused */, ipd_entry); 19213772Sjavier.bueno@metempsy.com ipd_entry->idx1 = index; 19313772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses = ipd_entry; 19413772Sjavier.bueno@metempsy.com } 19513772Sjavier.bueno@metempsy.com} 19613772Sjavier.bueno@metempsy.com 19713772Sjavier.bueno@metempsy.comvoid 19813772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::trackMissIndex1(Addr miss_addr) 19913772Sjavier.bueno@metempsy.com{ 20013772Sjavier.bueno@metempsy.com IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; 20113772Sjavier.bueno@metempsy.com // If the second index is not set, we are just filling the baseAddr 20213772Sjavier.bueno@metempsy.com // vector 20313772Sjavier.bueno@metempsy.com assert(entry->numMisses < entry->baseAddr.size()); 20413772Sjavier.bueno@metempsy.com std::vector<Addr> &ba_array = entry->baseAddr[entry->numMisses]; 20513772Sjavier.bueno@metempsy.com int idx = 0; 20613772Sjavier.bueno@metempsy.com for (int shift : shiftValues) { 20713772Sjavier.bueno@metempsy.com ba_array[idx] = miss_addr - (entry->idx1 << shift); 20813772Sjavier.bueno@metempsy.com idx += 1; 20913772Sjavier.bueno@metempsy.com } 21013772Sjavier.bueno@metempsy.com entry->numMisses += 1; 21113772Sjavier.bueno@metempsy.com if (entry->numMisses == entry->baseAddr.size()) { 21213772Sjavier.bueno@metempsy.com // stop tracking misses once we have tracked enough 21313772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses = nullptr; 21413772Sjavier.bueno@metempsy.com } 21513772Sjavier.bueno@metempsy.com} 21613772Sjavier.bueno@metempsy.comvoid 21713772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::trackMissIndex2(Addr miss_addr) 21813772Sjavier.bueno@metempsy.com{ 21913772Sjavier.bueno@metempsy.com IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; 22013772Sjavier.bueno@metempsy.com // Second index is filled, compare the addresses generated during 22113772Sjavier.bueno@metempsy.com // the previous misses (using idx1) against newly generated values 22213772Sjavier.bueno@metempsy.com // using idx2, if a match is found, fill the additional fields 22313772Sjavier.bueno@metempsy.com // of the PT entry 22413772Sjavier.bueno@metempsy.com for (int midx = 0; midx < entry->numMisses; midx += 1) 22513772Sjavier.bueno@metempsy.com { 22613772Sjavier.bueno@metempsy.com std::vector<Addr> &ba_array = entry->baseAddr[midx]; 22713772Sjavier.bueno@metempsy.com int idx = 0; 22813772Sjavier.bueno@metempsy.com for (int shift : shiftValues) { 22913772Sjavier.bueno@metempsy.com if (ba_array[idx] == (miss_addr - (entry->idx2 << shift))) { 23013772Sjavier.bueno@metempsy.com // Match found! 23113772Sjavier.bueno@metempsy.com // Fill the corresponding pt_entry 23213772Sjavier.bueno@metempsy.com PrefetchTableEntry *pt_entry = 23313772Sjavier.bueno@metempsy.com (PrefetchTableEntry *) entry->getTag(); 23413772Sjavier.bueno@metempsy.com pt_entry->baseAddr = ba_array[idx]; 23513772Sjavier.bueno@metempsy.com pt_entry->shift = shift; 23613772Sjavier.bueno@metempsy.com pt_entry->enabled = true; 23713772Sjavier.bueno@metempsy.com pt_entry->indirectCounter = 0; 23813772Sjavier.bueno@metempsy.com // Release the current IPD Entry 23913772Sjavier.bueno@metempsy.com entry->reset(); 24013772Sjavier.bueno@metempsy.com // Do not track more misses 24113772Sjavier.bueno@metempsy.com ipdEntryTrackingMisses = nullptr; 24213772Sjavier.bueno@metempsy.com return; 24313772Sjavier.bueno@metempsy.com } 24413772Sjavier.bueno@metempsy.com idx += 1; 24513772Sjavier.bueno@metempsy.com } 24613772Sjavier.bueno@metempsy.com } 24713772Sjavier.bueno@metempsy.com} 24813772Sjavier.bueno@metempsy.com 24913772Sjavier.bueno@metempsy.comvoid 25013772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher::checkAccessMatchOnActiveEntries(Addr addr) 25113772Sjavier.bueno@metempsy.com{ 25213772Sjavier.bueno@metempsy.com for (auto &pt_entry : prefetchTable) { 25313772Sjavier.bueno@metempsy.com if (pt_entry.enabled) { 25413772Sjavier.bueno@metempsy.com if (addr == pt_entry.baseAddr + 25513772Sjavier.bueno@metempsy.com (pt_entry.index << pt_entry.shift)) { 25613772Sjavier.bueno@metempsy.com if (pt_entry.indirectCounter < maxIndirectCounterValue) { 25713772Sjavier.bueno@metempsy.com pt_entry.indirectCounter += 1; 25813772Sjavier.bueno@metempsy.com pt_entry.increasedIndirectCounter = true; 25913772Sjavier.bueno@metempsy.com } 26013772Sjavier.bueno@metempsy.com } 26113772Sjavier.bueno@metempsy.com } 26213772Sjavier.bueno@metempsy.com } 26313772Sjavier.bueno@metempsy.com} 26413772Sjavier.bueno@metempsy.com 26513772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcher* 26613772Sjavier.bueno@metempsy.comIndirectMemoryPrefetcherParams::create() 26713772Sjavier.bueno@metempsy.com{ 26813772Sjavier.bueno@metempsy.com return new IndirectMemoryPrefetcher(this); 26913772Sjavier.bueno@metempsy.com} 270