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