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