2 * Copyright (c) 2018 Inria
3 * Copyright (c) 2012-2013, 2015 ARM Limited
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.
15 * Copyright (c) 2005 The Regents of The University of Michigan
16 * All rights reserved.
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.
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.
41 * Authors: Ron Dreslinski
48 * Stride Prefetcher template instantiations.
51 #include "mem/cache/prefetch/stride.hh"
55 #include "base/intmath.hh"
56 #include "base/logging.hh"
57 #include "base/random.hh"
58 #include "base/trace.hh"
59 #include "debug/HWPrefetch.hh"
60 #include "mem/cache/replacement_policies/base.hh"
61 #include "params/StridePrefetcher.hh"
63 StridePrefetcher::StrideEntry::StrideEntry()
69 StridePrefetcher::StrideEntry::invalidate()
78 StridePrefetcher::StridePrefetcher(const StridePrefetcherParams
*p
)
79 : QueuedPrefetcher(p
),
81 threshConf(p
->thresh_conf
),
83 startConf(p
->start_conf
),
84 pcTableAssoc(p
->table_assoc
),
85 pcTableSets(p
->table_sets
),
86 useMasterId(p
->use_master_id
),
88 replacementPolicy(p
->replacement_policy
)
90 assert(isPowerOf2(pcTableSets
));
93 StridePrefetcher::PCTable
*
94 StridePrefetcher::findTable(int context
)
96 // Check if table for given context exists
97 auto it
= pcTables
.find(context
);
98 if (it
!= pcTables
.end())
101 // If table does not exist yet, create one
102 return allocateNewContext(context
);
105 StridePrefetcher::PCTable
*
106 StridePrefetcher::allocateNewContext(int context
)
109 auto insertion_result
= pcTables
.insert(std::make_pair(context
,
110 PCTable(pcTableAssoc
, pcTableSets
, name(), replacementPolicy
)));
112 DPRINTF(HWPrefetch
, "Adding context %i with stride entries\n", context
);
114 // Get iterator to new pc table, and then return a pointer to the new table
115 return &(insertion_result
.first
->second
);
118 StridePrefetcher::PCTable::PCTable(int assoc
, int sets
, const std::string name
,
119 BaseReplacementPolicy
* replacementPolicy
)
120 : pcTableSets(sets
), _name(name
), entries(pcTableSets
),
121 replacementPolicy(replacementPolicy
)
123 for (int set
= 0; set
< sets
; set
++) {
124 entries
[set
].resize(assoc
);
125 for (int way
= 0; way
< assoc
; way
++) {
126 // Inform the entry its position
127 entries
[set
][way
].setPosition(set
, way
);
129 // Initialize replacement policy data
130 entries
[set
][way
].replacementData
=
131 replacementPolicy
->instantiateEntry();
136 StridePrefetcher::PCTable::~PCTable()
141 StridePrefetcher::calculatePrefetch(const PrefetchInfo
&pfi
,
142 std::vector
<AddrPriority
> &addresses
)
145 DPRINTF(HWPrefetch
, "Ignoring request with no PC.\n");
149 // Get required packet info
150 Addr pf_addr
= pfi
.getAddr();
151 Addr pc
= pfi
.getPC();
152 bool is_secure
= pfi
.isSecure();
153 MasterID master_id
= useMasterId
? pfi
.getMasterId() : 0;
155 // Get corresponding pc table
156 PCTable
* pcTable
= findTable(master_id
);
158 // Search for entry in the pc table
159 StrideEntry
*entry
= pcTable
->findEntry(pc
, is_secure
);
161 if (entry
!= nullptr) {
163 int new_stride
= pf_addr
- entry
->lastAddr
;
164 bool stride_match
= (new_stride
== entry
->stride
);
166 // Adjust confidence for stride entry
167 if (stride_match
&& new_stride
!= 0) {
168 if (entry
->confidence
< maxConf
)
171 if (entry
->confidence
> minConf
)
173 // If confidence has dropped below the threshold, train new stride
174 if (entry
->confidence
< threshConf
)
175 entry
->stride
= new_stride
;
178 DPRINTF(HWPrefetch
, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), "
179 "conf %d\n", pc
, pf_addr
, is_secure
? "s" : "ns",
180 new_stride
, stride_match
? "match" : "change",
183 entry
->lastAddr
= pf_addr
;
185 // Abort prefetch generation if below confidence threshold
186 if (entry
->confidence
< threshConf
)
189 // Generate up to degree prefetches
190 for (int d
= 1; d
<= degree
; d
++) {
191 // Round strides up to atleast 1 cacheline
192 int prefetch_stride
= new_stride
;
193 if (abs(new_stride
) < blkSize
) {
194 prefetch_stride
= (new_stride
< 0) ? -blkSize
: blkSize
;
197 Addr new_addr
= pf_addr
+ d
* prefetch_stride
;
198 if (samePage(pf_addr
, new_addr
)) {
199 DPRINTF(HWPrefetch
, "Queuing prefetch to %#x.\n", new_addr
);
200 addresses
.push_back(AddrPriority(new_addr
, 0));
202 // Record the number of page crossing prefetches generated
203 pfSpanPage
+= degree
- d
+ 1;
204 DPRINTF(HWPrefetch
, "Ignoring page crossing prefetch.\n");
210 DPRINTF(HWPrefetch
, "Miss: PC %x pkt_addr %x (%s)\n", pc
, pf_addr
,
211 is_secure
? "s" : "ns");
213 StrideEntry
* entry
= pcTable
->findVictim(pc
);
217 replacementPolicy
->invalidate(entry
->replacementData
);
219 // Insert new entry's data
220 entry
->instAddr
= pc
;
221 entry
->lastAddr
= pf_addr
;
222 entry
->isSecure
= is_secure
;
223 entry
->confidence
= startConf
;
224 replacementPolicy
->reset(entry
->replacementData
);
229 StridePrefetcher::PCTable::pcHash(Addr pc
) const
231 Addr hash1
= pc
>> 1;
232 Addr hash2
= hash1
>> floorLog2(pcTableSets
);
233 return (hash1
^ hash2
) & (Addr
)(pcTableSets
- 1);
236 inline StridePrefetcher::StrideEntry
*
237 StridePrefetcher::PCTable::findVictim(Addr pc
)
239 // Rand replacement for now
240 int set
= pcHash(pc
);
242 // Get possible entries to be victimized
243 std::vector
<ReplaceableEntry
*> possible_entries
;
244 for (auto& entry
: entries
[set
]) {
245 possible_entries
.push_back(&entry
);
248 // Choose victim based on replacement policy
249 StrideEntry
* victim
= static_cast<StrideEntry
*>(
250 replacementPolicy
->getVictim(possible_entries
));
252 DPRINTF(HWPrefetch
, "Victimizing lookup table[%d][%d].\n",
253 victim
->getSet(), victim
->getWay());
258 inline StridePrefetcher::StrideEntry
*
259 StridePrefetcher::PCTable::findEntry(Addr pc
, bool is_secure
)
261 int set
= pcHash(pc
);
262 for (auto& entry
: entries
[set
]) {
263 // Search ways for match
264 if ((entry
.instAddr
== pc
) && (entry
.isSecure
== is_secure
)) {
265 DPRINTF(HWPrefetch
, "Lookup hit table[%d][%d].\n", entry
.getSet(),
267 replacementPolicy
->touch(entry
.replacementData
);
275 StridePrefetcherParams::create()
277 return new StridePrefetcher(this);