indirect_memory.cc revision 13772:31b71dadc472 
1/**
2 * Copyright (c) 2018 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: Javier Bueno
29 */
30
31 #include "mem/cache/prefetch/indirect_memory.hh"
32
33 #include "mem/cache/base.hh"
34 #include "mem/cache/prefetch/associative_set_impl.hh"
35 #include "params/IndirectMemoryPrefetcher.hh"
36
37IndirectMemoryPrefetcher::IndirectMemoryPrefetcher(
38    const IndirectMemoryPrefetcherParams *p) : QueuedPrefetcher(p),
39    maxPrefetchDistance(p->max_prefetch_distance),
40    shiftValues(p->shift_values), prefetchThreshold(p->prefetch_threshold),
41    maxIndirectCounterValue(p->max_indirect_counter_value),
42    streamCounterThreshold(p->stream_counter_threshold),
43    streamingDistance(p->streaming_distance),
44    prefetchTable(p->pt_table_assoc, p->pt_table_entries,
45                  p->pt_table_indexing_policy, p->pt_table_replacement_policy),
46    ipd(p->ipd_table_assoc, p->ipd_table_entries, p->ipd_table_indexing_policy,
47        p->ipd_table_replacement_policy,
48        IndirectPatternDetectorEntry(p->addr_array_len, shiftValues.size())),
49    ipdEntryTrackingMisses(nullptr),
50#if THE_ISA != NULL_ISA
51    byteOrder(TheISA::GuestByteOrder)
52#else
53    byteOrder((ByteOrder) -1)
54#endif
55{
56    fatal_if(byteOrder == -1, "This prefetcher requires a defined ISA\n");
57}
58
59void
60IndirectMemoryPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
61    std::vector<AddrPriority> &addresses)
62{
63    // This prefetcher requires a PC
64    if (!pfi.hasPC()) {
65        return;
66    }
67
68    bool is_secure = pfi.isSecure();
69    Addr pc = pfi.getPC();
70    Addr addr = pfi.getAddr();
71    bool miss = pfi.isCacheMiss();
72
73    checkAccessMatchOnActiveEntries(addr);
74
75    // First check if this is a miss, if the prefetcher is tracking misses
76    if (ipdEntryTrackingMisses != nullptr && miss) {
77        // Check if the entry tracking misses has already set its second index
78        if (!ipdEntryTrackingMisses->secondIndexSet) {
79            trackMissIndex1(addr);
80        } else {
81            trackMissIndex2(addr);
82        }
83    } else {
84        // if misses are not being tracked, attempt to detect stream accesses
85        PrefetchTableEntry *pt_entry =
86            prefetchTable.findEntry(pc, false /* unused */);
87        if (pt_entry != nullptr) {
88            prefetchTable.accessEntry(pt_entry);
89
90            if (pt_entry->address != addr) {
91                // Streaming access found
92                pt_entry->streamCounter += 1;
93                if (pt_entry->streamCounter >= streamCounterThreshold) {
94                    int64_t delta = addr - pt_entry->address;
95                    for (unsigned int i = 1; i <= streamingDistance; i += 1) {
96                        addresses.push_back(AddrPriority(addr + delta * i, 0));
97                    }
98                }
99                pt_entry->address = addr;
100                pt_entry->secure = is_secure;
101
102
103                // if this is a read, read the data from the cache and assume
104                // it is an index (this is only possible if the data is already
105                // in the cache), also, only indexes up to 8 bytes are
106                // considered
107
108                if (!miss && !pfi.isWrite() && pfi.getSize() <= 8) {
109                    int64_t index = 0;
110                    switch(pfi.getSize()) {
111                        case sizeof(uint8_t):
112                            index = pfi.get<uint8_t>(byteOrder);
113                            break;
114                        case sizeof(uint16_t):
115                            index = pfi.get<uint16_t>(byteOrder);
116                            break;
117                        case sizeof(uint32_t):
118                            index = pfi.get<uint32_t>(byteOrder);
119                            break;
120                        case sizeof(uint64_t):
121                            index = pfi.get<uint64_t>(byteOrder);
122                            break;
123                        default:
124                            panic("Invalid access size\n");
125                    }
126                    if (!pt_entry->enabled) {
127                        // Not enabled (no pattern detected in this stream),
128                        // add or update an entry in the pattern detector and
129                        // start tracking misses
130                        allocateOrUpdateIPDEntry(pt_entry, index);
131                    } else {
132                        // Enabled entry, update the index
133                        pt_entry->index = index;
134                        if (!pt_entry->increasedIndirectCounter) {
135                            if (pt_entry->indirectCounter > 0) {
136                                pt_entry->indirectCounter -= 1;
137                            }
138                        } else {
139                            // Set this to false, to see if the new index
140                            // has any match
141                            pt_entry->increasedIndirectCounter = false;
142                        }
143
144                        // If the counter is high enough, start prefetching
145                        if (pt_entry->indirectCounter > prefetchThreshold) {
146                            unsigned distance = pt_entry->indirectCounter *
147                                maxPrefetchDistance / maxIndirectCounterValue;
148                            for (int delta = 1; delta < distance; delta += 1) {
149                                Addr pf_addr = pt_entry->baseAddr +
150                                    (pt_entry->index << pt_entry->shift);
151                                addresses.push_back(AddrPriority(pf_addr, 0));
152                            }
153                        }
154                    }
155                }
156            }
157        } else {
158            pt_entry = prefetchTable.findVictim(pc);
159            assert(pt_entry != nullptr);
160            prefetchTable.insertEntry(pc, false /* unused */, pt_entry);
161            pt_entry->address = addr;
162            pt_entry->secure = is_secure;
163        }
164    }
165}
166
167void
168IndirectMemoryPrefetcher::allocateOrUpdateIPDEntry(
169    const PrefetchTableEntry *pt_entry, int64_t index)
170{
171    // The address of the pt_entry is used to index the IPD
172    Addr ipd_entry_addr = (Addr) pt_entry;
173    IndirectPatternDetectorEntry *ipd_entry = ipd.findEntry(ipd_entry_addr,
174                                                            false/* unused */);
175    if (ipd_entry != nullptr) {
176        ipd.accessEntry(ipd_entry);
177        if (!ipd_entry->secondIndexSet) {
178            // Second time we see an index, fill idx2
179            ipd_entry->idx2 = index;
180            ipd_entry->secondIndexSet = true;
181            ipdEntryTrackingMisses = ipd_entry;
182        } else {
183            // Third access! no pattern has been found so far,
184            // release the IPD entry
185            ipd_entry->reset();
186            ipdEntryTrackingMisses = nullptr;
187        }
188    } else {
189        ipd_entry = ipd.findVictim(ipd_entry_addr);
190        assert(ipd_entry != nullptr);
191        ipd.insertEntry(ipd_entry_addr, false /* unused */, ipd_entry);
192        ipd_entry->idx1 = index;
193        ipdEntryTrackingMisses = ipd_entry;
194    }
195}
196
197void
198IndirectMemoryPrefetcher::trackMissIndex1(Addr miss_addr)
199{
200    IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses;
201    // If the second index is not set, we are just filling the baseAddr
202    // vector
203    assert(entry->numMisses < entry->baseAddr.size());
204    std::vector<Addr> &ba_array = entry->baseAddr[entry->numMisses];
205    int idx = 0;
206    for (int shift : shiftValues) {
207        ba_array[idx] = miss_addr - (entry->idx1 << shift);
208        idx += 1;
209    }
210    entry->numMisses += 1;
211    if (entry->numMisses == entry->baseAddr.size()) {
212        // stop tracking misses once we have tracked enough
213        ipdEntryTrackingMisses = nullptr;
214    }
215}
216void
217IndirectMemoryPrefetcher::trackMissIndex2(Addr miss_addr)
218{
219    IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses;
220    // Second index is filled, compare the addresses generated during
221    // the previous misses (using idx1) against newly generated values
222    // using idx2, if a match is found, fill the additional fields
223    // of the PT entry
224    for (int midx = 0; midx < entry->numMisses; midx += 1)
225    {
226        std::vector<Addr> &ba_array = entry->baseAddr[midx];
227        int idx = 0;
228        for (int shift : shiftValues) {
229            if (ba_array[idx] == (miss_addr - (entry->idx2 << shift))) {
230                // Match found!
231                // Fill the corresponding pt_entry
232                PrefetchTableEntry *pt_entry =
233                    (PrefetchTableEntry *) entry->getTag();
234                pt_entry->baseAddr = ba_array[idx];
235                pt_entry->shift = shift;
236                pt_entry->enabled = true;
237                pt_entry->indirectCounter = 0;
238                // Release the current IPD Entry
239                entry->reset();
240                // Do not track more misses
241                ipdEntryTrackingMisses = nullptr;
242                return;
243            }
244            idx += 1;
245        }
246    }
247}
248
249void
250IndirectMemoryPrefetcher::checkAccessMatchOnActiveEntries(Addr addr)
251{
252    for (auto &pt_entry : prefetchTable) {
253        if (pt_entry.enabled) {
254            if (addr == pt_entry.baseAddr +
255                       (pt_entry.index << pt_entry.shift)) {
256                if (pt_entry.indirectCounter < maxIndirectCounterValue) {
257                    pt_entry.indirectCounter += 1;
258                    pt_entry.increasedIndirectCounter = true;
259                }
260            }
261        }
262    }
263}
264
265IndirectMemoryPrefetcher*
266IndirectMemoryPrefetcherParams::create()
267{
268    return new IndirectMemoryPrefetcher(this);
269}
270