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 "base/random.hh"
  50 #include "debug/HWPrefetch.hh"
  51 #include "mem/cache/prefetch/stride.hh"
  52
  53 StridePrefetcher::StridePrefetcher(const StridePrefetcherParams *p)
  54     : QueuedPrefetcher(p),
  55       maxConf(p->max_conf),
  56       threshConf(p->thresh_conf),
  57       minConf(p->min_conf),
  58       startConf(p->start_conf),
  59       pcTableAssoc(p->table_assoc),
  60       pcTableSets(p->table_sets),
  61       useMasterId(p->use_master_id),
  62       degree(p->degree),
  63       pcTable(pcTableAssoc, pcTableSets, name())
  64 {
  65     // Don't consult stride prefetcher on instruction accesses
  66     onInst = false;
  67
  68     assert(isPowerOf2(pcTableSets));
  69 }
  70
  71 StridePrefetcher::StrideEntry**
  72 StridePrefetcher::PCTable::allocateNewContext(int context)
  73 {
  74     auto res = entries.insert(std::make_pair(context,
  75                               new StrideEntry*[pcTableSets]));
  76     auto it = res.first;
  77     chatty_assert(res.second, "Allocating an already created context\n");
  78     assert(it->first == context);
  79
  80     DPRINTF(HWPrefetch, "Adding context %i with stride entries at %p\n",
  81             context, it->second);
  82
  83     StrideEntry** entry = it->second;
  84     for (int s = 0; s < pcTableSets; s++) {
  85         entry[s] = new StrideEntry[pcTableAssoc];
  86     }
  87     return entry;
  88 }
  89
  90 StridePrefetcher::PCTable::~PCTable() {
  91     for (auto entry : entries) {
  92         for (int s = 0; s < pcTableSets; s++) {
  93             delete[] entry.second[s];
  94         }
  95         delete[] entry.second;
  96     }
  97 }
  98
  99 void
 100 StridePrefetcher::calculatePrefetch(const PacketPtr &pkt,
 101                                     std::vector<Addr> &addresses)
 102 {
 103     if (!pkt->req->hasPC()) {
 104         DPRINTF(HWPrefetch, "Ignoring request with no PC.\n");
 105         return;
 106     }
 107
 108     // Get required packet info
 109     Addr pkt_addr = pkt->getAddr();
 110     Addr pc = pkt->req->getPC();
 111     bool is_secure = pkt->isSecure();
 112     MasterID master_id = useMasterId ? pkt->req->masterId() : 0;
 113
 114     // Lookup pc-based information
 115     StrideEntry *entry;
 116
 117     if(pcTableHit(pc, is_secure, master_id, entry)) {
 118         // Hit in table
 119         int new_stride = pkt_addr - entry->lastAddr;
 120         bool stride_match = (new_stride == entry->stride);
 121
 122         // Adjust confidence for stride entry
 123         if (stride_match && new_stride != 0) {
 124             if (entry->confidence < maxConf)
 125                 entry->confidence++;
 126         } else {
 127             if (entry->confidence > minConf)
 128                 entry->confidence--;
 129             // If confidence has dropped below the threshold, train new stride
 130             if (entry->confidence < threshConf)
 131                 entry->stride = new_stride;
 132         }
 133
 134         DPRINTF(HWPrefetch, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), "
 135                 "conf %d\n", pc, pkt_addr, is_secure ? "s" : "ns", new_stride,
 136                 stride_match ? "match" : "change",
 137                 entry->confidence);
 138
 139         entry->lastAddr = pkt_addr;
 140
 141         // Abort prefetch generation if below confidence threshold
 142         if (entry->confidence < threshConf)
 143             return;
 144
 145         // Generate up to degree prefetches
 146         for (int d = 1; d <= degree; d++) {
 147             // Round strides up to atleast 1 cacheline
 148             int prefetch_stride = new_stride;
 149             if (abs(new_stride) < blkSize) {
 150                 prefetch_stride = (new_stride < 0) ? -blkSize : blkSize;
 151             }
 152
 153             Addr new_addr = pkt_addr + d * prefetch_stride;
 154             if (samePage(pkt_addr, new_addr)) {
 155                 DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr);
 156                 addresses.push_back(new_addr);
 157             } else {
 158                 // Record the number of page crossing prefetches generated
 159                 pfSpanPage += degree - d + 1;
 160                 DPRINTF(HWPrefetch, "Ignoring page crossing prefetch.\n");
 161                 return;
 162             }
 163         }
 164     } else {
 165         // Miss in table
 166         DPRINTF(HWPrefetch, "Miss: PC %x pkt_addr %x (%s)\n", pc, pkt_addr,
 167                 is_secure ? "s" : "ns");
 168
 169         StrideEntry* entry = pcTableVictim(pc, master_id);
 170         entry->instAddr = pc;
 171         entry->lastAddr = pkt_addr;
 172         entry->isSecure= is_secure;
 173         entry->stride = 0;
 174         entry->confidence = startConf;
 175     }
 176 }
 177
 178 inline Addr
 179 StridePrefetcher::pcHash(Addr pc) const
 180 {
 181     Addr hash1 = pc >> 1;
 182     Addr hash2 = hash1 >> floorLog2(pcTableSets);
 183     return (hash1 ^ hash2) & (Addr)(pcTableSets - 1);
 184 }
 185
 186 inline StridePrefetcher::StrideEntry*
 187 StridePrefetcher::pcTableVictim(Addr pc, int master_id)
 188 {
 189     // Rand replacement for now
 190     int set = pcHash(pc);
 191     int way = random_mt.random<int>(0, pcTableAssoc - 1);
 192
 193     DPRINTF(HWPrefetch, "Victimizing lookup table[%d][%d].\n", set, way);
 194     return &pcTable[master_id][set][way];
 195 }
 196
 197 inline bool
 198 StridePrefetcher::pcTableHit(Addr pc, bool is_secure, int master_id,
 199                              StrideEntry* &entry)
 200 {
 201     int set = pcHash(pc);
 202     StrideEntry* set_entries = pcTable[master_id][set];
 203     for (int way = 0; way < pcTableAssoc; way++) {
 204         // Search ways for match
 205         if (set_entries[way].instAddr == pc &&
 206             set_entries[way].isSecure == is_secure) {
 207             DPRINTF(HWPrefetch, "Lookup hit table[%d][%d].\n", set, way);
 208             entry = &set_entries[way];
 209             return true;
 210         }
 211     }
 212     return false;
 213 }
 214
 215 StridePrefetcher*
 216 StridePrefetcherParams::create()
 217 {
 218     return new StridePrefetcher(this);
 219 }