| /** | |
| * Copyright (c) 2018 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. | |
| * | |
| * Authors: Javier Bueno | |
| */ | |
| #include "mem/cache/prefetch/indirect_memory.hh" | |
| #include "mem/cache/base.hh" | |
| #include "mem/cache/prefetch/associative_set_impl.hh" | |
| #include "params/IndirectMemoryPrefetcher.hh" | |
| IndirectMemoryPrefetcher::IndirectMemoryPrefetcher( | |
| const IndirectMemoryPrefetcherParams *p) : QueuedPrefetcher(p), | |
| maxPrefetchDistance(p->max_prefetch_distance), | |
| shiftValues(p->shift_values), prefetchThreshold(p->prefetch_threshold), | |
| streamCounterThreshold(p->stream_counter_threshold), | |
| streamingDistance(p->streaming_distance), | |
| prefetchTable(p->pt_table_assoc, p->pt_table_entries, | |
| p->pt_table_indexing_policy, p->pt_table_replacement_policy, | |
| PrefetchTableEntry(p->num_indirect_counter_bits)), | |
| ipd(p->ipd_table_assoc, p->ipd_table_entries, p->ipd_table_indexing_policy, | |
| p->ipd_table_replacement_policy, | |
| IndirectPatternDetectorEntry(p->addr_array_len, shiftValues.size())), | |
| ipdEntryTrackingMisses(nullptr), | |
| #if THE_ISA != NULL_ISA | |
| byteOrder(TheISA::GuestByteOrder) | |
| #else | |
| byteOrder((ByteOrder) -1) | |
| #endif | |
| { | |
| fatal_if(byteOrder == static_cast<ByteOrder>(-1), | |
| "This prefetcher requires a defined ISA\n"); | |
| } | |
| void | |
| IndirectMemoryPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, | |
| std::vector<AddrPriority> &addresses) | |
| { | |
| // This prefetcher requires a PC | |
| if (!pfi.hasPC()) { | |
| return; | |
| } | |
| bool is_secure = pfi.isSecure(); | |
| Addr pc = pfi.getPC(); | |
| Addr addr = pfi.getAddr(); | |
| bool miss = pfi.isCacheMiss(); | |
| checkAccessMatchOnActiveEntries(addr); | |
| // First check if this is a miss, if the prefetcher is tracking misses | |
| if (ipdEntryTrackingMisses != nullptr && miss) { | |
| // Check if the entry tracking misses has already set its second index | |
| if (!ipdEntryTrackingMisses->secondIndexSet) { | |
| trackMissIndex1(addr); | |
| } else { | |
| trackMissIndex2(addr); | |
| } | |
| } else { | |
| // if misses are not being tracked, attempt to detect stream accesses | |
| PrefetchTableEntry *pt_entry = | |
| prefetchTable.findEntry(pc, false /* unused */); | |
| if (pt_entry != nullptr) { | |
| prefetchTable.accessEntry(pt_entry); | |
| if (pt_entry->address != addr) { | |
| // Streaming access found | |
| pt_entry->streamCounter += 1; | |
| if (pt_entry->streamCounter >= streamCounterThreshold) { | |
| int64_t delta = addr - pt_entry->address; | |
| for (unsigned int i = 1; i <= streamingDistance; i += 1) { | |
| addresses.push_back(AddrPriority(addr + delta * i, 0)); | |
| } | |
| } | |
| pt_entry->address = addr; | |
| pt_entry->secure = is_secure; | |
| // if this is a read, read the data from the cache and assume | |
| // it is an index (this is only possible if the data is already | |
| // in the cache), also, only indexes up to 8 bytes are | |
| // considered | |
| if (!miss && !pfi.isWrite() && pfi.getSize() <= 8) { | |
| int64_t index = 0; | |
| bool read_index = true; | |
| switch(pfi.getSize()) { | |
| case sizeof(uint8_t): | |
| index = pfi.get<uint8_t>(byteOrder); | |
| break; | |
| case sizeof(uint16_t): | |
| index = pfi.get<uint16_t>(byteOrder); | |
| break; | |
| case sizeof(uint32_t): | |
| index = pfi.get<uint32_t>(byteOrder); | |
| break; | |
| case sizeof(uint64_t): | |
| index = pfi.get<uint64_t>(byteOrder); | |
| break; | |
| default: | |
| // Ignore non-power-of-two sizes | |
| read_index = false; | |
| } | |
| if (read_index && !pt_entry->enabled) { | |
| // Not enabled (no pattern detected in this stream), | |
| // add or update an entry in the pattern detector and | |
| // start tracking misses | |
| allocateOrUpdateIPDEntry(pt_entry, index); | |
| } else if (read_index) { | |
| // Enabled entry, update the index | |
| pt_entry->index = index; | |
| if (!pt_entry->increasedIndirectCounter) { | |
| pt_entry->indirectCounter--; | |
| } else { | |
| // Set this to false, to see if the new index | |
| // has any match | |
| pt_entry->increasedIndirectCounter = false; | |
| } | |
| // If the counter is high enough, start prefetching | |
| if (pt_entry->indirectCounter > prefetchThreshold) { | |
| unsigned distance = maxPrefetchDistance * | |
| pt_entry->indirectCounter.calcSaturation(); | |
| for (int delta = 1; delta < distance; delta += 1) { | |
| Addr pf_addr = pt_entry->baseAddr + | |
| (pt_entry->index << pt_entry->shift); | |
| addresses.push_back(AddrPriority(pf_addr, 0)); | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } else { | |
| pt_entry = prefetchTable.findVictim(pc); | |
| assert(pt_entry != nullptr); | |
| prefetchTable.insertEntry(pc, false /* unused */, pt_entry); | |
| pt_entry->address = addr; | |
| pt_entry->secure = is_secure; | |
| } | |
| } | |
| } | |
| void | |
| IndirectMemoryPrefetcher::allocateOrUpdateIPDEntry( | |
| const PrefetchTableEntry *pt_entry, int64_t index) | |
| { | |
| // The address of the pt_entry is used to index the IPD | |
| Addr ipd_entry_addr = (Addr) pt_entry; | |
| IndirectPatternDetectorEntry *ipd_entry = ipd.findEntry(ipd_entry_addr, | |
| false/* unused */); | |
| if (ipd_entry != nullptr) { | |
| ipd.accessEntry(ipd_entry); | |
| if (!ipd_entry->secondIndexSet) { | |
| // Second time we see an index, fill idx2 | |
| ipd_entry->idx2 = index; | |
| ipd_entry->secondIndexSet = true; | |
| ipdEntryTrackingMisses = ipd_entry; | |
| } else { | |
| // Third access! no pattern has been found so far, | |
| // release the IPD entry | |
| ipd_entry->reset(); | |
| ipdEntryTrackingMisses = nullptr; | |
| } | |
| } else { | |
| ipd_entry = ipd.findVictim(ipd_entry_addr); | |
| assert(ipd_entry != nullptr); | |
| ipd.insertEntry(ipd_entry_addr, false /* unused */, ipd_entry); | |
| ipd_entry->idx1 = index; | |
| ipdEntryTrackingMisses = ipd_entry; | |
| } | |
| } | |
| void | |
| IndirectMemoryPrefetcher::trackMissIndex1(Addr miss_addr) | |
| { | |
| IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; | |
| // If the second index is not set, we are just filling the baseAddr | |
| // vector | |
| assert(entry->numMisses < entry->baseAddr.size()); | |
| std::vector<Addr> &ba_array = entry->baseAddr[entry->numMisses]; | |
| int idx = 0; | |
| for (int shift : shiftValues) { | |
| ba_array[idx] = miss_addr - (entry->idx1 << shift); | |
| idx += 1; | |
| } | |
| entry->numMisses += 1; | |
| if (entry->numMisses == entry->baseAddr.size()) { | |
| // stop tracking misses once we have tracked enough | |
| ipdEntryTrackingMisses = nullptr; | |
| } | |
| } | |
| void | |
| IndirectMemoryPrefetcher::trackMissIndex2(Addr miss_addr) | |
| { | |
| IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses; | |
| // Second index is filled, compare the addresses generated during | |
| // the previous misses (using idx1) against newly generated values | |
| // using idx2, if a match is found, fill the additional fields | |
| // of the PT entry | |
| for (int midx = 0; midx < entry->numMisses; midx += 1) | |
| { | |
| std::vector<Addr> &ba_array = entry->baseAddr[midx]; | |
| int idx = 0; | |
| for (int shift : shiftValues) { | |
| if (ba_array[idx] == (miss_addr - (entry->idx2 << shift))) { | |
| // Match found! | |
| // Fill the corresponding pt_entry | |
| PrefetchTableEntry *pt_entry = | |
| (PrefetchTableEntry *) entry->getTag(); | |
| pt_entry->baseAddr = ba_array[idx]; | |
| pt_entry->shift = shift; | |
| pt_entry->enabled = true; | |
| pt_entry->indirectCounter.reset(); | |
| // Release the current IPD Entry | |
| entry->reset(); | |
| // Do not track more misses | |
| ipdEntryTrackingMisses = nullptr; | |
| return; | |
| } | |
| idx += 1; | |
| } | |
| } | |
| } | |
| void | |
| IndirectMemoryPrefetcher::checkAccessMatchOnActiveEntries(Addr addr) | |
| { | |
| for (auto &pt_entry : prefetchTable) { | |
| if (pt_entry.enabled) { | |
| if (addr == pt_entry.baseAddr + | |
| (pt_entry.index << pt_entry.shift)) { | |
| pt_entry.indirectCounter++; | |
| pt_entry.increasedIndirectCounter = true; | |
| } | |
| } | |
| } | |
| } | |
| IndirectMemoryPrefetcher* | |
| IndirectMemoryPrefetcherParams::create() | |
| { | |
| return new IndirectMemoryPrefetcher(this); | |
| } |