src/mem/cache/prefetch/pif.cc

   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
  29 #include "mem/cache/prefetch/pif.hh"
  30
  31 #include <utility>
  32
  33 #include "debug/HWPrefetch.hh"
  34 #include "mem/cache/prefetch/associative_set_impl.hh"
  35 #include "params/PIFPrefetcher.hh"
  36
  37 namespace Prefetcher {
  38
  39 PIF::PIF(const PIFPrefetcherParams &p)
  40     : Queued(p),
  41       precSize(p.prec_spatial_region_bits),
  42       succSize(p.succ_spatial_region_bits),
  43       maxCompactorEntries(p.compactor_entries),
  44       historyBuffer(p.history_buffer_size),
  45       index(p.index_assoc, p.index_entries, p.index_indexing_policy,
  46             p.index_replacement_policy),
  47       streamAddressBuffer(p.stream_address_buffer_entries),
  48       listenersPC()
  49 {
  50 }
  51
  52 PIF::CompactorEntry::CompactorEntry(Addr addr,
  53     unsigned int prec_size, unsigned int succ_size)
  54 {
  55     trigger = addr;
  56     prec.resize(prec_size, false);
  57     succ.resize(succ_size, false);
  58 }
  59
  60 Addr
  61 PIF::CompactorEntry::distanceFromTrigger(Addr target,
  62         unsigned int log_blk_size) const
  63 {
  64     const Addr target_blk = target >> log_blk_size;
  65     const Addr trigger_blk = trigger >> log_blk_size;
  66
  67     return target_blk > trigger_blk ?
  68               target_blk - trigger_blk : trigger_blk - target_blk;
  69 }
  70
  71 bool
  72 PIF::CompactorEntry::inSameSpatialRegion(Addr pc,
  73         unsigned int log_blk_size, bool update)
  74 {
  75     Addr blk_distance = distanceFromTrigger(pc, log_blk_size);
  76
  77     bool hit = (pc > trigger) ?
  78         (succ.size() > blk_distance) : (prec.size() > blk_distance);
  79     if (hit && update) {
  80         if (pc > trigger) {
  81             succ[blk_distance] = true;
  82         } else if (pc < trigger) {
  83             prec[blk_distance] = true;
  84         }
  85     }
  86     return hit;
  87 }
  88
  89 bool
  90 PIF::CompactorEntry::hasAddress(Addr target,
  91                                           unsigned int log_blk_size) const
  92 {
  93     Addr blk_distance = distanceFromTrigger(target, log_blk_size);
  94     bool hit = false;
  95     if (target > trigger) {
  96         hit = blk_distance < succ.size() && succ[blk_distance];
  97     } else if (target < trigger) {
  98         hit = blk_distance < prec.size() && prec[blk_distance];
  99     } else {
 100         hit = true;
 101     }
 102     return hit;
 103 }
 104
 105 void
 106 PIF::CompactorEntry::getPredictedAddresses(unsigned int log_blk_size,
 107     std::vector<AddrPriority> &addresses) const
 108 {
 109     // Calculate the addresses of the instruction blocks that are encoded
 110     // by the bit vector and issue prefetch requests for these addresses.
 111     // Predictions are made by traversing the bit vector from left to right
 112     // as this typically predicts the accesses in the order they will be
 113     // issued in the core.
 114     const Addr trigger_blk = trigger >> log_blk_size;
 115     for (int i = prec.size()-1; i >= 0; i--) {
 116         // Address from the preceding blocks to issue a prefetch
 117         if (prec[i]) {
 118             const Addr prec_addr = (trigger_blk - (i+1)) << log_blk_size;
 119             addresses.push_back(AddrPriority(prec_addr, 0));
 120         }
 121     }
 122     for (int i = 0; i < succ.size(); i++) {
 123         // Address from the succeding blocks to issue a prefetch
 124         if (succ[i]) {
 125             const Addr succ_addr = (trigger_blk + (i+1)) << log_blk_size;
 126             addresses.push_back(AddrPriority(succ_addr, 0));
 127         }
 128     }
 129 }
 130
 131 void
 132 PIF::notifyRetiredInst(const Addr pc)
 133 {
 134     // First access to the prefetcher
 135     if (temporalCompactor.size() == 0) {
 136         spatialCompactor = CompactorEntry(pc, precSize, succSize);
 137         temporalCompactor.push_back(spatialCompactor);
 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 'iterator' table to point to the new entry
 173                 historyBuffer.push_back(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->historyIt =
 186                     historyBuffer.getIterator(historyBuffer.tail());
 187
 188                 // Reset the spatial compactor fields with the new address
 189                 spatialCompactor = CompactorEntry(pc, precSize, succSize);
 190             }
 191         }
 192     }
 193 }
 194
 195 void
 196 PIF::calculatePrefetch(const PrefetchInfo &pfi,
 197     std::vector<AddrPriority> &addresses)
 198 {
 199     if (!pfi.hasPC()) {
 200         return;
 201     }
 202
 203     const Addr pc = pfi.getPC();
 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(pc, lBlkSize)) {
 209             sabEntry++;
 210             sabEntry->getPredictedAddresses(lBlkSize, addresses);
 211             // We are done
 212             return;
 213         }
 214     }
 215
 216     // Check if a valid entry in the 'index' table is found and allocate a new
 217     // active prediction stream
 218     IndexEntry *idx_entry = index.findEntry(pc, /* unused */ false);
 219
 220     if (idx_entry != nullptr) {
 221         index.accessEntry(idx_entry);
 222         // Trigger address from the 'index' table and index to the history
 223         // buffer
 224         auto entry = idx_entry->historyIt;
 225
 226         // Track the block in the Stream Address Buffer
 227         streamAddressBuffer.push_back(entry);
 228
 229         entry->getPredictedAddresses(lBlkSize, addresses);
 230     }
 231 }
 232
 233 void
 234 PIF::PrefetchListenerPC::notify(const Addr& pc)
 235 {
 236     parent.notifyRetiredInst(pc);
 237 }
 238
 239 void
 240 PIF::addEventProbeRetiredInsts(SimObject *obj, const char *name)
 241 {
 242     ProbeManager *pm(obj->getProbeManager());
 243     listenersPC.push_back(new PrefetchListenerPC(*this, pm, name));
 244 }
 245
 246 } // namespace Prefetcher
 247
 248 Prefetcher::PIF*
 249 PIFPrefetcherParams::create() const
 250 {
 251     return new Prefetcher::PIF(*this);
 252 }