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