1/*
2 * Copyright (c) 2018 Inria
3 * Copyright (c) 2012-2013, 2015 ARM Limited
4 * All rights reserved
5 *
6 * The license below extends only to copyright in the software and shall
7 * not be construed as granting a license to any other intellectual
8 * property including but not limited to intellectual property relating
9 * to a hardware implementation of the functionality of the software
10 * licensed hereunder.  You may use the software subject to the license
11 * terms below provided that you ensure that this notice is replicated
12 * unmodified and in its entirety in all distributions of the software,
13 * modified or unmodified, in source code or in binary form.
14 *
15 * Copyright (c) 2005 The Regents of The University of Michigan
16 * All rights reserved.
17 *
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions are
20 * met: redistributions of source code must retain the above copyright
21 * notice, this list of conditions and the following disclaimer;
22 * redistributions in binary form must reproduce the above copyright
23 * notice, this list of conditions and the following disclaimer in the
24 * documentation and/or other materials provided with the distribution;
25 * neither the name of the copyright holders nor the names of its
26 * contributors may be used to endorse or promote products derived from
27 * this software without specific prior written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
30 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
31 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
32 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
33 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
34 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
35 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
36 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
37 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
38 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
39 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
40 *
41 * Authors: Ron Dreslinski
42 *          Daniel Carvalho
43 */
44
45/**
46 * @file
47 * Describes a strided prefetcher.
48 */
49
50#ifndef __MEM_CACHE_PREFETCH_STRIDE_HH__
51#define __MEM_CACHE_PREFETCH_STRIDE_HH__
52
53#include <string>
54#include <unordered_map>
55#include <vector>
56
57#include "base/types.hh"
58#include "mem/cache/prefetch/queued.hh"
59#include "mem/cache/replacement_policies/replaceable_entry.hh"
60#include "mem/packet.hh"
61
62class BaseReplacementPolicy;
63struct StridePrefetcherParams;
64
65class StridePrefetcher : public QueuedPrefetcher
66{
67  protected:
68    const int maxConf;
69    const int threshConf;
70    const int minConf;
71    const int startConf;
72
73    const int pcTableAssoc;
74    const int pcTableSets;
75
76    const bool useMasterId;
77
78    const int degree;
79
80    /** Replacement policy used in the PC tables. */
81    BaseReplacementPolicy* replacementPolicy;
82
83    struct StrideEntry : public ReplaceableEntry
84    {
85        /** Default constructor */
86        StrideEntry();
87
88        /** Invalidate the entry */
89        void invalidate();
90
91        Addr instAddr;
92        Addr lastAddr;
93        bool isSecure;
94        int stride;
95        int confidence;
96    };
97
98    class PCTable
99    {
100      public:
101        /**
102         * Default constructor. Create a table with given parameters.
103         *
104         * @param assoc Associativity of the table.
105         * @param sets Number of sets in the table.
106         * @param name Name of the prefetcher.
107         * @param replacementPolicy Replacement policy used by the table.
108         */
109        PCTable(int assoc, int sets, const std::string name,
110                BaseReplacementPolicy* replacementPolicy);
111
112        /**
113         * Default destructor.
114         */
115        ~PCTable();
116
117        /**
118         * Search for an entry in the pc table.
119         *
120         * @param pc The PC to look for.
121         * @param is_secure True if the target memory space is secure.
122         * @return Pointer to the entry.
123         */
124        StrideEntry* findEntry(Addr pc, bool is_secure);
125
126        /**
127         * Find a replacement victim to make room for given PC.
128         *
129         * @param pc The PC value.
130         * @return The victimized entry.
131         */
132        StrideEntry* findVictim(Addr pc);
133
134      private:
135        const std::string name() {return _name; }
136        const int pcTableSets;
137        const std::string _name;
138        std::vector<std::vector<StrideEntry>> entries;
139
140        /**
141         * Replacement policy used by StridePrefetcher.
142         */
143        BaseReplacementPolicy* replacementPolicy;
144
145        /**
146         * PC hashing function to index sets in the table.
147         *
148         * @param pc The PC value.
149         * @return The set to which this PC maps.
150         */
151        Addr pcHash(Addr pc) const;
152    };
153    std::unordered_map<int, PCTable> pcTables;
154
155    /**
156     * Try to find a table of entries for the given context. If none is
157     * found, a new table is created.
158     *
159     * @param context The context to be searched for.
160     * @return The table corresponding to the given context.
161     */
162    PCTable* findTable(int context);
163
164    /**
165     * Create a PC table for the given context.
166     *
167     * @param context The context of the new PC table.
168     * @return The new PC table
169     */
170    PCTable* allocateNewContext(int context);
171
172  public:
173    StridePrefetcher(const StridePrefetcherParams *p);
174
175    void calculatePrefetch(const PrefetchInfo &pfi,
176                           std::vector<AddrPriority> &addresses) override;
177};
178
179#endif // __MEM_CACHE_PREFETCH_STRIDE_HH__
180