1/** 2 * Copyright (c) 2019 Metempsy Technology Consulting 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Ivan Pizarro 29 */ 30 31#include "mem/cache/prefetch/pif.hh" 32 33#include <utility> 34 35#include "debug/HWPrefetch.hh" 36#include "mem/cache/prefetch/associative_set_impl.hh" 37#include "params/PIFPrefetcher.hh" 38 39PIFPrefetcher::PIFPrefetcher(const PIFPrefetcherParams *p) 40 : QueuedPrefetcher(p), 41 precSize(p->prec_spatial_region_bits), 42 succSize(p->succ_spatial_region_bits), 43 maxCompactorEntries(p->compactor_entries), 44 maxStreamAddressBufferEntries(p->stream_address_buffer_entries), 45 historyBuffer(p->history_buffer_size), 46 historyBufferTail(0), 47 index(p->index_assoc, p->index_entries, p->index_indexing_policy, 48 p->index_replacement_policy), 49 streamAddressBuffer(), listenersPC() 50{ 51} 52 53PIFPrefetcher::CompactorEntry::CompactorEntry(Addr addr, 54 unsigned int prec_size, unsigned int succ_size) 55{ 56 trigger = addr; 57 prec.resize(prec_size, false); 58 succ.resize(succ_size, false); 59} 60 61Addr 62PIFPrefetcher::CompactorEntry::distanceFromTrigger(Addr target, 63 unsigned int log_blk_size) const 64{ 65 const Addr target_blk = target >> log_blk_size; 66 const Addr trigger_blk = trigger >> log_blk_size; 67 68 return target_blk > trigger_blk ? 69 target_blk - trigger_blk : trigger_blk - target_blk; 70} 71 72bool 73PIFPrefetcher::CompactorEntry::inSameSpatialRegion(Addr pc, 74 unsigned int log_blk_size, bool update) 75{ 76 Addr blk_distance = distanceFromTrigger(pc, log_blk_size); 77 78 bool hit = (pc > trigger) ? 79 (succ.size() >= blk_distance) : (prec.size() >= blk_distance); 80 if (hit && update) { 81 if (pc > trigger) { 82 succ[blk_distance - 1] = true; 83 } else if (pc < trigger) { 84 prec[blk_distance - 1] = true; 85 } 86 } 87 return hit; 88} 89 90bool 91PIFPrefetcher::CompactorEntry::hasAddress(Addr target, 92 unsigned int log_blk_size) const 93{ 94 Addr blk_distance = distanceFromTrigger(target, log_blk_size); 95 bool hit = false; 96 if (target > trigger) { 97 hit = blk_distance <= succ.size() && succ[blk_distance - 1]; 98 } else if (target < trigger) { 99 hit = blk_distance <= prec.size() && succ[blk_distance - 1]; 100 } else { 101 hit = true; 102 } 103 return hit; 104} 105 106void 107PIFPrefetcher::CompactorEntry::getPredictedAddresses(unsigned int log_blk_size, 108 std::vector<AddrPriority> &addresses) const 109{ 110 // Calculate the addresses of the instruction blocks that are encoded 111 // by the bit vector and issue prefetch requests for these addresses. 112 // Predictions are made by traversing the bit vector from left to right 113 // as this typically predicts the accesses in the order they will be 114 // issued in the core. 115 const Addr trigger_blk = trigger >> log_blk_size; 116 for (int i = prec.size()-1; i >= 0; i--) { 117 // Address from the preceding blocks to issue a prefetch 118 if (prec[i]) { 119 const Addr prec_addr = (trigger_blk - (i+1)) << log_blk_size; 120 addresses.push_back(AddrPriority(prec_addr, 0)); 121 } 122 } 123 for (int i = 0; i < succ.size(); i++) { 124 // Address from the succeding blocks to issue a prefetch 125 if (succ[i]) { 126 const Addr succ_addr = (trigger_blk + (i+1)) << log_blk_size; 127 addresses.push_back(AddrPriority(succ_addr, 0)); 128 } 129 } 130} 131 132void 133PIFPrefetcher::notifyRetiredInst(const Addr pc) 134{ 135 // First access to the prefetcher 136 if (temporalCompactor.size() == 0) { 137 spatialCompactor = CompactorEntry(pc, precSize, succSize); 138 } else { 139 // If the PC of the instruction retired is in the same spatial region 140 // than the last trigger address, update the bit vectors based on the 141 // distance between them 142 if (spatialCompactor.inSameSpatialRegion(pc, lBlkSize, true)) { 143 // If the PC of the instruction retired is outside the latest spatial 144 // region, check if it matches in any of the regions in the temporal 145 // compactor and update it to the MRU position 146 } else { 147 bool is_in_temporal_compactor = false; 148 149 // Check if the PC is in the temporal compactor 150 for (auto it = temporalCompactor.begin(); 151 it != temporalCompactor.end(); it++) 152 { 153 if (it->inSameSpatialRegion(pc, lBlkSize, false)) { 154 spatialCompactor = (*it); 155 temporalCompactor.erase(it); 156 is_in_temporal_compactor = true; 157 break; 158 } 159 } 160 161 if (temporalCompactor.size() == maxCompactorEntries) { 162 temporalCompactor.pop_front(); // Discard the LRU entry 163 } 164 165 temporalCompactor.push_back(spatialCompactor); 166 167 // If the compactor entry is neither the spatial or can't be 168 // found in the temporal compactor, reset the spatial compactor 169 // updating the trigger address and resetting the vector bits 170 if (!is_in_temporal_compactor) { 171 // Insert the spatial entry into the history buffer and update 172 // the 'index' table to point to the new entry 173 historyBuffer[historyBufferTail] = spatialCompactor; 174 175 IndexEntry *idx_entry = 176 index.findEntry(spatialCompactor.trigger, false); 177 if (idx_entry != nullptr) { 178 index.accessEntry(idx_entry); 179 } else { 180 idx_entry = index.findVictim(spatialCompactor.trigger); 181 assert(idx_entry != nullptr); 182 index.insertEntry(spatialCompactor.trigger, false, 183 idx_entry); 184 } 185 idx_entry->historyIndex = historyBufferTail; 186 187 historyBufferTail++; 188 if (historyBufferTail == historyBuffer.size()) { 189 historyBufferTail = 0; 190 } 191 192 // Reset the spatial compactor fields with the new address 193 spatialCompactor = CompactorEntry(pc, precSize, succSize); 194 } 195 } 196 } 197} 198 199void 200PIFPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 201 std::vector<AddrPriority> &addresses) 202{ 203 const Addr addr = pfi.getAddr(); 204 205 // First check if the access has been prefetched, this is done by 206 // comparing the access against the active Stream Address Buffers 207 for (auto &sabEntry : streamAddressBuffer) { 208 if (sabEntry->hasAddress(addr, lBlkSize)) { 209 // Advance to the next entry (first check if we have reached the 210 // end of the history buffer) 211 if (sabEntry == &(historyBuffer[historyBuffer.size() - 1])) { 212 sabEntry = &(historyBuffer[0]); 213 } else { 214 sabEntry++; 215 } 216 sabEntry->getPredictedAddresses(lBlkSize, addresses); 217 // We are done 218 return; 219 } 220 } 221 222 // Check if a valid entry in the 'index' table is found and allocate a new 223 // active prediction stream 224 IndexEntry *idx_entry = index.findEntry(addr, /* unused */ false); 225 226 if (idx_entry != nullptr) { 227 index.accessEntry(idx_entry); 228 // Trigger address from the 'index' table and index to the history 229 // buffer 230 const unsigned int hb_entry = idx_entry->historyIndex; 231 CompactorEntry *entry = &historyBuffer[hb_entry]; 232 233 // Track the block in the Stream Address Buffer 234 if (streamAddressBuffer.size() == maxStreamAddressBufferEntries) { 235 streamAddressBuffer.pop_front(); 236 } 237 streamAddressBuffer.push_back(entry); 238 239 entry->getPredictedAddresses(lBlkSize, addresses); 240 } 241} 242 243void 244PIFPrefetcher::PrefetchListenerPC::notify(const Addr& pc) 245{ 246 parent.notifyRetiredInst(pc); 247} 248 249void 250PIFPrefetcher::addEventProbeRetiredInsts(SimObject *obj, const char *name) 251{ 252 ProbeManager *pm(obj->getProbeManager()); 253 listenersPC.push_back(new PrefetchListenerPC(*this, pm, name)); 254} 255 256PIFPrefetcher* 257PIFPrefetcherParams::create() 258{ 259 return new PIFPrefetcher(this); 260} 261