pif.cc revision 13825:90e5b4dfeaff 
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 <cmath>
34#include <utility>
35
36#include "debug/HWPrefetch.hh"
37#include "mem/cache/prefetch/associative_set_impl.hh"
38#include "params/PIFPrefetcher.hh"
39
40PIFPrefetcher::PIFPrefetcher(const PIFPrefetcherParams *p)
41    : QueuedPrefetcher(p),
42      precSize(p->prec_spatial_region_bits),
43      succSize(p->succ_spatial_region_bits),
44      maxCompactorEntries(p->compactor_entries),
45      maxStreamAddressBufferEntries(p->stream_address_buffer_entries),
46      historyBuffer(p->history_buffer_size),
47      historyBufferTail(0),
48      index(p->index_assoc, p->index_entries, p->index_indexing_policy,
49            p->index_replacement_policy),
50      streamAddressBuffer(), listenersPC()
51{
52}
53
54PIFPrefetcher::CompactorEntry::CompactorEntry(Addr addr,
55    unsigned int prec_size, unsigned int succ_size)
56{
57    trigger = addr;
58    prec.resize(prec_size, false);
59    succ.resize(succ_size, false);
60}
61
62unsigned int
63PIFPrefetcher::CompactorEntry::distanceFromTrigger(Addr target,
64        unsigned int log_blk_size) const {
65    const Addr target_blk = target >> log_blk_size;
66    const Addr trigger_blk = trigger >> log_blk_size;
67
68    return std::abs(target_blk - trigger_blk);
69}
70
71bool
72PIFPrefetcher::CompactorEntry::inSameSpatialRegion(Addr pc,
73        unsigned int log_blk_size, bool update)
74{
75    unsigned int 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 - 1] = true;
82        } else if (pc < trigger) {
83            prec[blk_distance - 1] = true;
84        }
85    }
86    return hit;
87}
88
89bool
90PIFPrefetcher::CompactorEntry::hasAddress(Addr target,
91                                          unsigned int log_blk_size) const
92{
93    unsigned int blk_distance = distanceFromTrigger(target, log_blk_size);
94    bool hit = false;
95    if (target > trigger) {
96        hit = blk_distance <= succ.size() && succ[blk_distance - 1];
97    } else if (target < trigger) {
98        hit = blk_distance <= prec.size() && succ[blk_distance - 1];
99    } else {
100        hit = true;
101    }
102    return hit;
103}
104
105void
106PIFPrefetcher::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
131void
132PIFPrefetcher::notifyRetiredInst(const Addr pc)
133{
134    // First access to the prefetcher
135    if (temporalCompactor.size() == 0) {
136        spatialCompactor = CompactorEntry(pc, precSize, succSize);
137    } else {
138        // If the PC of the instruction retired is in the same spatial region
139        // than the last trigger address, update the bit vectors based on the
140        // distance between them
141        if (spatialCompactor.inSameSpatialRegion(pc, lBlkSize, true)) {
142        // If the PC of the instruction retired is outside the latest spatial
143        // region, check if it matches in any of the regions in the temporal
144        // compactor and update it to the MRU position
145        } else {
146            bool is_in_temporal_compactor = false;
147
148            // Check if the PC is in the temporal compactor
149            for (auto it = temporalCompactor.begin();
150                    it != temporalCompactor.end(); it++)
151            {
152                if (it->inSameSpatialRegion(pc, lBlkSize, false)) {
153                    spatialCompactor = (*it);
154                    temporalCompactor.erase(it);
155                    is_in_temporal_compactor = true;
156                    break;
157                }
158            }
159
160            if (temporalCompactor.size() == maxCompactorEntries) {
161                temporalCompactor.pop_front(); // Discard the LRU entry
162            }
163
164            temporalCompactor.push_back(spatialCompactor);
165
166            // If the compactor entry is neither the spatial or can't be
167            // found in the temporal compactor, reset the spatial compactor
168            // updating the trigger address and resetting the vector bits
169            if (!is_in_temporal_compactor) {
170                // Insert the spatial entry into the history buffer and update
171                // the 'index' table to point to the new entry
172                historyBuffer[historyBufferTail] = spatialCompactor;
173
174                IndexEntry *idx_entry =
175                    index.findEntry(spatialCompactor.trigger, false);
176                if (idx_entry != nullptr) {
177                    index.accessEntry(idx_entry);
178                } else {
179                    idx_entry = index.findVictim(spatialCompactor.trigger);
180                    assert(idx_entry != nullptr);
181                    index.insertEntry(spatialCompactor.trigger, false,
182                                      idx_entry);
183                }
184                idx_entry->historyIndex = historyBufferTail;
185
186                historyBufferTail++;
187                if (historyBufferTail == historyBuffer.size()) {
188                    historyBufferTail = 0;
189                }
190
191                // Reset the spatial compactor fields with the new address
192                spatialCompactor = CompactorEntry(pc, precSize, succSize);
193            }
194        }
195    }
196}
197
198void
199PIFPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
200    std::vector<AddrPriority> &addresses)
201{
202    const Addr addr = pfi.getAddr();
203
204    // First check if the access has been prefetched, this is done by
205    // comparing the access against the active Stream Address Buffers
206    for (auto &sabEntry : streamAddressBuffer) {
207        if (sabEntry->hasAddress(addr, lBlkSize)) {
208            // Advance to the next entry (first check if we have reached the
209            // end of the history buffer)
210            if (sabEntry == &(historyBuffer[historyBuffer.size() - 1])) {
211                sabEntry = &(historyBuffer[0]);
212            } else {
213                sabEntry++;
214            }
215            sabEntry->getPredictedAddresses(lBlkSize, addresses);
216            // We are done
217            return;
218        }
219    }
220
221    // Check if a valid entry in the 'index' table is found and allocate a new
222    // active prediction stream
223    IndexEntry *idx_entry = index.findEntry(addr, /* unused */ false);
224
225    if (idx_entry != nullptr) {
226        index.accessEntry(idx_entry);
227        // Trigger address from the 'index' table and index to the history
228        // buffer
229        const unsigned int hb_entry = idx_entry->historyIndex;
230        CompactorEntry *entry = &historyBuffer[hb_entry];
231
232        // Track the block in the Stream Address Buffer
233        if (streamAddressBuffer.size() == maxStreamAddressBufferEntries) {
234            streamAddressBuffer.pop_front();
235        }
236        streamAddressBuffer.push_back(entry);
237
238        entry->getPredictedAddresses(lBlkSize, addresses);
239    }
240}
241
242void
243PIFPrefetcher::PrefetchListenerPC::notify(const Addr& pc)
244{
245    parent.notifyRetiredInst(pc);
246}
247
248void
249PIFPrefetcher::addEventProbeRetiredInsts(SimObject *obj, const char *name)
250{
251    ProbeManager *pm(obj->getProbeManager());
252    listenersPC.push_back(new PrefetchListenerPC(*this, pm, name));
253}
254
255PIFPrefetcher*
256PIFPrefetcherParams::create()
257{
258    return new PIFPrefetcher(this);
259}
260