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/**
32 * Implementation of the Indirect Memory Prefetcher
33 *
34 * References:
35 * IMP: Indirect memory prefetcher.
36 * Yu, X., Hughes, C. J., Satish, N., & Devadas, S. (2015, December).
37 * In Proceedings of the 48th International Symposium on Microarchitecture
38 * (pp. 178-190). ACM.
39 */
40
41#ifndef __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
42#define __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
43
44#include <vector>
45
46#include "base/sat_counter.hh"
47#include "mem/cache/prefetch/associative_set.hh"
48#include "mem/cache/prefetch/queued.hh"
49
50struct IndirectMemoryPrefetcherParams;
51
52class IndirectMemoryPrefetcher : public QueuedPrefetcher
53{
54    /** Maximum number of prefetches generated per event */
55    const unsigned int maxPrefetchDistance;
56    /** Shift values considered */
57    const std::vector<int> shiftValues;
58    /** Counter threshold to start prefetching */
59    const unsigned int prefetchThreshold;
60    /** streamCounter value to trigger the streaming prefetcher */
61    const int streamCounterThreshold;
62    /** Number of prefetches generated when using the streaming prefetcher */
63    const int streamingDistance;
64
65    /** Prefetch Table Entry */
66    struct PrefetchTableEntry : public TaggedEntry
67    {
68        /* Stream table fields */
69
70        /** Accessed address */
71        Addr address;
72        /** Whether this address is in the secure region */
73        bool secure;
74        /** Confidence counter of the stream */
75        unsigned int streamCounter;
76
77        /* Indirect table fields */
78
79        /** Enable bit of the indirect fields */
80        bool enabled;
81        /** Current index value */
82        int64_t index;
83        /** BaseAddr detected */
84        Addr baseAddr;
85        /** Shift detected */
86        int shift;
87        /** Confidence counter of the indirect fields */
88        SatCounter indirectCounter;
89        /**
90         * This variable is set to indicate that there has been at least one
91         * match with the current index value. This information is later used
92         * when a new index is updated. If there were no increases in the
93         * indirectCounter, the counter is decremented.
94         */
95        bool increasedIndirectCounter;
96
97        PrefetchTableEntry(unsigned indirect_counter_bits)
98            : TaggedEntry(), address(0), secure(false), streamCounter(0),
99              enabled(false), index(0), baseAddr(0), shift(0),
100              indirectCounter(indirect_counter_bits),
101              increasedIndirectCounter(false)
102        {}
103
104        void reset() override {
105            address = 0;
106            secure = false;
107            streamCounter = 0;
108            enabled = false;
109            index = 0;
110            baseAddr = 0;
111            shift = 0;
112            indirectCounter.reset();
113            increasedIndirectCounter = false;
114        }
115    };
116    /** Prefetch table */
117    AssociativeSet<PrefetchTableEntry> prefetchTable;
118
119    /** Indirect Pattern Detector entrt */
120    struct IndirectPatternDetectorEntry : public TaggedEntry
121    {
122        /** First index */
123        int64_t idx1;
124        /** Second index */
125        int64_t idx2;
126        /** Valid bit for the second index */
127        bool secondIndexSet;
128        /** Number of misses currently recorded */
129        int numMisses;
130        /**
131         * Potential BaseAddr candidates for each recorded miss.
132         * The number of candidates per miss is determined by the number of
133         * elements in the shiftValues array.
134         */
135        std::vector<std::vector<Addr>> baseAddr;
136
137        IndirectPatternDetectorEntry(unsigned int num_addresses,
138                                     unsigned int num_shifts)
139          : idx1(0), idx2(0), secondIndexSet(false), numMisses(0),
140            baseAddr(num_addresses, std::vector<Addr>(num_shifts))
141        {}
142
143        void reset() override {
144            idx1 = 0;
145            idx2 = 0;
146            secondIndexSet = false;
147            numMisses = 0;
148            setInvalid();
149        }
150    };
151    /** Indirect Pattern Detector (IPD) table */
152    AssociativeSet<IndirectPatternDetectorEntry> ipd;
153
154    /** Entry currently tracking misses */
155    IndirectPatternDetectorEntry *ipdEntryTrackingMisses;
156
157    /** Byte order used to access the cache */
158    const ByteOrder byteOrder;
159
160    /**
161     * Allocate or update an entry in the IPD
162     * @param pt_entry Pointer to the associated page table entry
163     * @param index Detected first index value
164     */
165    void allocateOrUpdateIPDEntry(const PrefetchTableEntry *pt_entry,
166                                  int64_t index);
167    /**
168     * Update an IPD entry with a detected miss address, when the first index
169     * is being tracked
170     * @param miss_addr The address that caused the miss
171     */
172    void trackMissIndex1(Addr miss_addr);
173
174    /**
175     * Update an IPD entry with a detected miss address, when the second index
176     * is being tracked
177     * @param miss_addr The address that caused the miss
178     */
179    void trackMissIndex2(Addr miss_addr);
180
181    /**
182     * Checks if an access to the cache matches any active PT entry, if so,
183     * the indirect confidence counter is incremented
184     * @param addr address of the access
185     */
186    void checkAccessMatchOnActiveEntries(Addr addr);
187
188  public:
189    IndirectMemoryPrefetcher(const IndirectMemoryPrefetcherParams *p);
190    ~IndirectMemoryPrefetcher() {}
191
192    void calculatePrefetch(const PrefetchInfo &pfi,
193                           std::vector<AddrPriority> &addresses) override;
194};
195#endif//__MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
196