src/mem/cache/prefetch/stride.cc

   1 /*
   2  * Copyright (c) 2012-2013, 2015 ARM Limited
   3  * All rights reserved
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Copyright (c) 2005 The Regents of The University of Michigan
  15  * All rights reserved.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions are
  19  * met: redistributions of source code must retain the above copyright
  20  * notice, this list of conditions and the following disclaimer;
  21  * redistributions in binary form must reproduce the above copyright
  22  * notice, this list of conditions and the following disclaimer in the
  23  * documentation and/or other materials provided with the distribution;
  24  * neither the name of the copyright holders nor the names of its
  25  * contributors may be used to endorse or promote products derived from
  26  * this software without specific prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39  *
  40  * Authors: Ron Dreslinski
  41  *          Steve Reinhardt
  42  */
  43
  44 /**
  45  * @file
  46  * Stride Prefetcher template instantiations.
  47  */
  48
  49 #include "mem/cache/prefetch/stride.hh"
  50
  51 #include <cassert>
  52
  53 #include "base/intmath.hh"
  54 #include "base/logging.hh"
  55 #include "base/random.hh"
  56 #include "base/trace.hh"
  57 #include "debug/HWPrefetch.hh"
  58 #include "params/StridePrefetcher.hh"
  59
  60 StridePrefetcher::StridePrefetcher(const StridePrefetcherParams *p)
  61     : QueuedPrefetcher(p),
  62       maxConf(p->max_conf),
  63       threshConf(p->thresh_conf),
  64       minConf(p->min_conf),
  65       startConf(p->start_conf),
  66       pcTableAssoc(p->table_assoc),
  67       pcTableSets(p->table_sets),
  68       useMasterId(p->use_master_id),
  69       degree(p->degree),
  70       pcTable(pcTableAssoc, pcTableSets, name())
  71 {
  72     // Don't consult stride prefetcher on instruction accesses
  73     onInst = false;
  74
  75     assert(isPowerOf2(pcTableSets));
  76 }
  77
  78 StridePrefetcher::StrideEntry**
  79 StridePrefetcher::PCTable::allocateNewContext(int context)
  80 {
  81     auto res = entries.insert(std::make_pair(context,
  82                               new StrideEntry*[pcTableSets]));
  83     auto it = res.first;
  84     chatty_assert(res.second, "Allocating an already created context\n");
  85     assert(it->first == context);
  86
  87     DPRINTF(HWPrefetch, "Adding context %i with stride entries at %p\n",
  88             context, it->second);
  89
  90     StrideEntry** entry = it->second;
  91     for (int s = 0; s < pcTableSets; s++) {
  92         entry[s] = new StrideEntry[pcTableAssoc];
  93     }
  94     return entry;
  95 }
  96
  97 StridePrefetcher::PCTable::~PCTable() {
  98     for (auto entry : entries) {
  99         for (int s = 0; s < pcTableSets; s++) {
 100             delete[] entry.second[s];
 101         }
 102         delete[] entry.second;
 103     }
 104 }
 105
 106 void
 107 StridePrefetcher::calculatePrefetch(const PacketPtr &pkt,
 108                                     std::vector<AddrPriority> &addresses)
 109 {
 110     if (!pkt->req->hasPC()) {
 111         DPRINTF(HWPrefetch, "Ignoring request with no PC.\n");
 112         return;
 113     }
 114
 115     // Get required packet info
 116     Addr pkt_addr = pkt->getAddr();
 117     Addr pc = pkt->req->getPC();
 118     bool is_secure = pkt->isSecure();
 119     MasterID master_id = useMasterId ? pkt->req->masterId() : 0;
 120
 121     // Lookup pc-based information
 122     StrideEntry *entry;
 123
 124     if (pcTableHit(pc, is_secure, master_id, entry)) {
 125         // Hit in table
 126         int new_stride = pkt_addr - entry->lastAddr;
 127         bool stride_match = (new_stride == entry->stride);
 128
 129         // Adjust confidence for stride entry
 130         if (stride_match && new_stride != 0) {
 131             if (entry->confidence < maxConf)
 132                 entry->confidence++;
 133         } else {
 134             if (entry->confidence > minConf)
 135                 entry->confidence--;
 136             // If confidence has dropped below the threshold, train new stride
 137             if (entry->confidence < threshConf)
 138                 entry->stride = new_stride;
 139         }
 140
 141         DPRINTF(HWPrefetch, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), "
 142                 "conf %d\n", pc, pkt_addr, is_secure ? "s" : "ns", new_stride,
 143                 stride_match ? "match" : "change",
 144                 entry->confidence);
 145
 146         entry->lastAddr = pkt_addr;
 147
 148         // Abort prefetch generation if below confidence threshold
 149         if (entry->confidence < threshConf)
 150             return;
 151
 152         // Generate up to degree prefetches
 153         for (int d = 1; d <= degree; d++) {
 154             // Round strides up to atleast 1 cacheline
 155             int prefetch_stride = new_stride;
 156             if (abs(new_stride) < blkSize) {
 157                 prefetch_stride = (new_stride < 0) ? -blkSize : blkSize;
 158             }
 159
 160             Addr new_addr = pkt_addr + d * prefetch_stride;
 161             if (samePage(pkt_addr, new_addr)) {
 162                 DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr);
 163                 addresses.push_back(AddrPriority(new_addr, 0));
 164             } else {
 165                 // Record the number of page crossing prefetches generated
 166                 pfSpanPage += degree - d + 1;
 167                 DPRINTF(HWPrefetch, "Ignoring page crossing prefetch.\n");
 168                 return;
 169             }
 170         }
 171     } else {
 172         // Miss in table
 173         DPRINTF(HWPrefetch, "Miss: PC %x pkt_addr %x (%s)\n", pc, pkt_addr,
 174                 is_secure ? "s" : "ns");
 175
 176         StrideEntry* entry = pcTableVictim(pc, master_id);
 177         entry->instAddr = pc;
 178         entry->lastAddr = pkt_addr;
 179         entry->isSecure= is_secure;
 180         entry->stride = 0;
 181         entry->confidence = startConf;
 182     }
 183 }
 184
 185 inline Addr
 186 StridePrefetcher::pcHash(Addr pc) const
 187 {
 188     Addr hash1 = pc >> 1;
 189     Addr hash2 = hash1 >> floorLog2(pcTableSets);
 190     return (hash1 ^ hash2) & (Addr)(pcTableSets - 1);
 191 }
 192
 193 inline StridePrefetcher::StrideEntry*
 194 StridePrefetcher::pcTableVictim(Addr pc, int master_id)
 195 {
 196     // Rand replacement for now
 197     int set = pcHash(pc);
 198     int way = random_mt.random<int>(0, pcTableAssoc - 1);
 199
 200     DPRINTF(HWPrefetch, "Victimizing lookup table[%d][%d].\n", set, way);
 201     return &pcTable[master_id][set][way];
 202 }
 203
 204 inline bool
 205 StridePrefetcher::pcTableHit(Addr pc, bool is_secure, int master_id,
 206                              StrideEntry* &entry)
 207 {
 208     int set = pcHash(pc);
 209     StrideEntry* set_entries = pcTable[master_id][set];
 210     for (int way = 0; way < pcTableAssoc; way++) {
 211         // Search ways for match
 212         if (set_entries[way].instAddr == pc &&
 213             set_entries[way].isSecure == is_secure) {
 214             DPRINTF(HWPrefetch, "Lookup hit table[%d][%d].\n", set, way);
 215             entry = &set_entries[way];
 216             return true;
 217         }
 218     }
 219     return false;
 220 }
 221
 222 StridePrefetcher*
 223 StridePrefetcherParams::create()
 224 {
 225     return new StridePrefetcher(this);
 226 }