2 * Copyright (c) 2012-2013, 2015 ARM Limited
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
14 * Copyright (c) 2005 The Regents of The University of Michigan
15 * All rights reserved.
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions are
19 * met: redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer;
21 * redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution;
24 * neither the name of the copyright holders nor the names of its
25 * contributors may be used to endorse or promote products derived from
26 * this software without specific prior written permission.
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
40 * Authors: Ron Dreslinski
46 * Stride Prefetcher template instantiations.
49 #include "mem/cache/prefetch/stride.hh"
53 #include "base/intmath.hh"
54 #include "base/logging.hh"
55 #include "base/random.hh"
56 #include "base/trace.hh"
57 #include "debug/HWPrefetch.hh"
58 #include "params/StridePrefetcher.hh"
60 StridePrefetcher::StridePrefetcher(const StridePrefetcherParams
*p
)
61 : QueuedPrefetcher(p
),
63 threshConf(p
->thresh_conf
),
65 startConf(p
->start_conf
),
66 pcTableAssoc(p
->table_assoc
),
67 pcTableSets(p
->table_sets
),
68 useMasterId(p
->use_master_id
),
70 pcTable(pcTableAssoc
, pcTableSets
, name())
72 // Don't consult stride prefetcher on instruction accesses
75 assert(isPowerOf2(pcTableSets
));
78 StridePrefetcher::StrideEntry
**
79 StridePrefetcher::PCTable::allocateNewContext(int context
)
81 auto res
= entries
.insert(std::make_pair(context
,
82 new StrideEntry
*[pcTableSets
]));
84 chatty_assert(res
.second
, "Allocating an already created context\n");
85 assert(it
->first
== context
);
87 DPRINTF(HWPrefetch
, "Adding context %i with stride entries at %p\n",
90 StrideEntry
** entry
= it
->second
;
91 for (int s
= 0; s
< pcTableSets
; s
++) {
92 entry
[s
] = new StrideEntry
[pcTableAssoc
];
97 StridePrefetcher::PCTable::~PCTable() {
98 for (auto entry
: entries
) {
99 for (int s
= 0; s
< pcTableSets
; s
++) {
100 delete[] entry
.second
[s
];
102 delete[] entry
.second
;
107 StridePrefetcher::calculatePrefetch(const PacketPtr
&pkt
,
108 std::vector
<AddrPriority
> &addresses
)
110 if (!pkt
->req
->hasPC()) {
111 DPRINTF(HWPrefetch
, "Ignoring request with no PC.\n");
115 // Get required packet info
116 Addr pkt_addr
= pkt
->getAddr();
117 Addr pc
= pkt
->req
->getPC();
118 bool is_secure
= pkt
->isSecure();
119 MasterID master_id
= useMasterId
? pkt
->req
->masterId() : 0;
121 // Lookup pc-based information
124 if (pcTableHit(pc
, is_secure
, master_id
, entry
)) {
126 int new_stride
= pkt_addr
- entry
->lastAddr
;
127 bool stride_match
= (new_stride
== entry
->stride
);
129 // Adjust confidence for stride entry
130 if (stride_match
&& new_stride
!= 0) {
131 if (entry
->confidence
< maxConf
)
134 if (entry
->confidence
> minConf
)
136 // If confidence has dropped below the threshold, train new stride
137 if (entry
->confidence
< threshConf
)
138 entry
->stride
= new_stride
;
141 DPRINTF(HWPrefetch
, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), "
142 "conf %d\n", pc
, pkt_addr
, is_secure
? "s" : "ns", new_stride
,
143 stride_match
? "match" : "change",
146 entry
->lastAddr
= pkt_addr
;
148 // Abort prefetch generation if below confidence threshold
149 if (entry
->confidence
< threshConf
)
152 // Generate up to degree prefetches
153 for (int d
= 1; d
<= degree
; d
++) {
154 // Round strides up to atleast 1 cacheline
155 int prefetch_stride
= new_stride
;
156 if (abs(new_stride
) < blkSize
) {
157 prefetch_stride
= (new_stride
< 0) ? -blkSize
: blkSize
;
160 Addr new_addr
= pkt_addr
+ d
* prefetch_stride
;
161 if (samePage(pkt_addr
, new_addr
)) {
162 DPRINTF(HWPrefetch
, "Queuing prefetch to %#x.\n", new_addr
);
163 addresses
.push_back(AddrPriority(new_addr
, 0));
165 // Record the number of page crossing prefetches generated
166 pfSpanPage
+= degree
- d
+ 1;
167 DPRINTF(HWPrefetch
, "Ignoring page crossing prefetch.\n");
173 DPRINTF(HWPrefetch
, "Miss: PC %x pkt_addr %x (%s)\n", pc
, pkt_addr
,
174 is_secure
? "s" : "ns");
176 StrideEntry
* entry
= pcTableVictim(pc
, master_id
);
177 entry
->instAddr
= pc
;
178 entry
->lastAddr
= pkt_addr
;
179 entry
->isSecure
= is_secure
;
181 entry
->confidence
= startConf
;
186 StridePrefetcher::pcHash(Addr pc
) const
188 Addr hash1
= pc
>> 1;
189 Addr hash2
= hash1
>> floorLog2(pcTableSets
);
190 return (hash1
^ hash2
) & (Addr
)(pcTableSets
- 1);
193 inline StridePrefetcher::StrideEntry
*
194 StridePrefetcher::pcTableVictim(Addr pc
, int master_id
)
196 // Rand replacement for now
197 int set
= pcHash(pc
);
198 int way
= random_mt
.random
<int>(0, pcTableAssoc
- 1);
200 DPRINTF(HWPrefetch
, "Victimizing lookup table[%d][%d].\n", set
, way
);
201 return &pcTable
[master_id
][set
][way
];
205 StridePrefetcher::pcTableHit(Addr pc
, bool is_secure
, int master_id
,
208 int set
= pcHash(pc
);
209 StrideEntry
* set_entries
= pcTable
[master_id
][set
];
210 for (int way
= 0; way
< pcTableAssoc
; way
++) {
211 // Search ways for match
212 if (set_entries
[way
].instAddr
== pc
&&
213 set_entries
[way
].isSecure
== is_secure
) {
214 DPRINTF(HWPrefetch
, "Lookup hit table[%d][%d].\n", set
, way
);
215 entry
= &set_entries
[way
];
223 StridePrefetcherParams::create()
225 return new StridePrefetcher(this);