1/*
2 * Copyright (c) 2005 The Regents of The University of Michigan
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: Ron Dreslinski
29 */
30
31/**
32 * @file
33 * Hardware Prefetcher Definition.
34 */
35
36#include "arch/isa_traits.hh"
37#include "base/trace.hh"
38#include "mem/cache/base.hh"
39#include "mem/cache/prefetch/base.hh"
40#include "mem/request.hh"
41#include <list>
42
43BasePrefetcher::BasePrefetcher(const BaseCacheParams *p)
44 : size(p->prefetcher_size), pageStop(!p->prefetch_past_page),
45 serialSquash(p->prefetch_serial_squash),
46 cacheCheckPush(p->prefetch_cache_check_push),
46 only_data(p->prefetch_data_accesses_only)
47 onlyData(p->prefetch_data_accesses_only)
48{
49}
50
51void
52BasePrefetcher::setCache(BaseCache *_cache)
53{
54 cache = _cache;
55 blkSize = cache->getBlockSize();
56 _name = cache->name() + "-pf";
57}
58
59void
60BasePrefetcher::regStats(const std::string &name)
61{
62 pfIdentified
63 .name(name + ".prefetcher.num_hwpf_identified")
64 .desc("number of hwpf identified")
65 ;
66
67 pfMSHRHit
68 .name(name + ".prefetcher.num_hwpf_already_in_mshr")
69 .desc("number of hwpf that were already in mshr")
70 ;
71
72 pfCacheHit
73 .name(name + ".prefetcher.num_hwpf_already_in_cache")
74 .desc("number of hwpf that were already in the cache")
75 ;
76
77 pfBufferHit
78 .name(name + ".prefetcher.num_hwpf_already_in_prefetcher")
79 .desc("number of hwpf that were already in the prefetch queue")
80 ;
81
82 pfRemovedFull
83 .name(name + ".prefetcher.num_hwpf_evicted")
84 .desc("number of hwpf removed due to no buffer left")
85 ;
86
87 pfRemovedMSHR
88 .name(name + ".prefetcher.num_hwpf_removed_MSHR_hit")
89 .desc("number of hwpf removed because MSHR allocated")
90 ;
91
92 pfIssued
93 .name(name + ".prefetcher.num_hwpf_issued")
94 .desc("number of hwpf issued")
95 ;
96
97 pfSpanPage
98 .name(name + ".prefetcher.num_hwpf_span_page")
99 .desc("number of hwpf spanning a virtual page")
100 ;
101
102 pfSquashed
103 .name(name + ".prefetcher.num_hwpf_squashed_from_miss")
102 .desc("number of hwpf that got squashed due to a miss aborting calculation time")
104 .desc("number of hwpf that got squashed due to a miss "
105 "aborting calculation time")
106 ;
107}
108
109inline bool
110BasePrefetcher::inCache(Addr addr)
111{
112 if (cache->inCache(addr)) {
113 pfCacheHit++;
114 return true;
115 }
116 return false;
117}
118
119inline bool
120BasePrefetcher::inMissQueue(Addr addr)
121{
122 if (cache->inMissQueue(addr)) {
123 pfMSHRHit++;
124 return true;
125 }
126 return false;
127}
128
129PacketPtr
130BasePrefetcher::getPacket()
131{
129 DPRINTF(HWPrefetch, "%s:Requesting a hw_pf to issue\n", cache->name());
132 DPRINTF(HWPrefetch, "Requesting a hw_pf to issue\n");
133
134 if (pf.empty()) {
132 DPRINTF(HWPrefetch, "%s:No HW_PF found\n", cache->name());
135 DPRINTF(HWPrefetch, "No HW_PF found\n");
136 return NULL;
137 }
138
139 PacketPtr pkt;
137 bool keepTrying = false;
140 bool keep_trying = false;
141 do {
142 pkt = *pf.begin();
143 pf.pop_front();
144 if (!cacheCheckPush) {
142 keepTrying = cache->inCache(pkt->getAddr());
145 keep_trying = cache->inCache(pkt->getAddr());
146 }
147
148 if (keep_trying) {
149 DPRINTF(HWPrefetch, "addr 0x%x in cache, skipping\n",
150 pkt->getAddr());
151 delete pkt->req;
152 delete pkt;
153 }
154
155 if (pf.empty()) {
156 cache->deassertMemSideBusRequest(BaseCache::Request_PF);
146 if (keepTrying) return NULL; //None left, all were in cache
157 if (keep_trying) {
158 return NULL; // None left, all were in cache
159 }
160 }
148 } while (keepTrying);
161 } while (keep_trying);
162
163 pfIssued++;
164 assert(pkt != NULL);
165 DPRINTF(HWPrefetch, "returning 0x%x\n", pkt->getAddr());
166 return pkt;
167}
168
154void
155BasePrefetcher::handleMiss(PacketPtr &pkt, Tick time)
169
170Tick
171BasePrefetcher::notify(PacketPtr &pkt, Tick time)
172{
157 if (!pkt->req->isUncacheable() && !(pkt->req->isInstRead() && only_data))
158 {
159 //Calculate the blk address
160 Addr blkAddr = pkt->getAddr() & ~(Addr)(blkSize-1);
173 if (!pkt->req->isUncacheable() && !(pkt->req->isInstRead() && onlyData)) {
174 // Calculate the blk address
175 Addr blk_addr = pkt->getAddr() & ~(Addr)(blkSize-1);
176
162 //Check if miss is in pfq, if so remove it
163 std::list<PacketPtr>::iterator iter = inPrefetch(blkAddr);
177 // Check if miss is in pfq, if so remove it
178 std::list<PacketPtr>::iterator iter = inPrefetch(blk_addr);
179 if (iter != pf.end()) {
165 DPRINTF(HWPrefetch, "%s:Saw a miss to a queued prefetch, removing it\n", cache->name());
180 DPRINTF(HWPrefetch, "Saw a miss to a queued prefetch addr: "
181 "0x%x, removing it\n", blk_addr);
182 pfRemovedMSHR++;
183 delete (*iter)->req;
184 delete (*iter);
185 pf.erase(iter);
186 if (pf.empty())
187 cache->deassertMemSideBusRequest(BaseCache::Request_PF);
188 }
189
172 //Remove anything in queue with delay older than time
173 //since everything is inserted in time order, start from end
174 //and work until pf.empty() or time is earlier
175 //This is done to emulate Aborting the previous work on a new miss
176 //Needed for serial calculators like GHB
190 // Remove anything in queue with delay older than time
191 // since everything is inserted in time order, start from end
192 // and work until pf.empty() or time is earlier
193 // This is done to emulate Aborting the previous work on a new miss
194 // Needed for serial calculators like GHB
195 if (serialSquash) {
196 iter = pf.end();
197 iter--;
198 while (!pf.empty() && ((*iter)->time >= time)) {
199 pfSquashed++;
182 pf.pop_back();
200 DPRINTF(HWPrefetch, "Squashing old prefetch addr: 0x%x\n",
201 (*iter)->getAddr());
202 delete (*iter)->req;
203 delete (*iter);
204 pf.erase(iter);
205 iter--;
206 }
207 if (pf.empty())
208 cache->deassertMemSideBusRequest(BaseCache::Request_PF);
209 }
210
211
212 std::list<Addr> addresses;
213 std::list<Tick> delays;
214 calculatePrefetch(pkt, addresses, delays);
215
194 std::list::iterator addr = addresses.begin();
195 std::list::iterator delay = delays.begin();
196 while (addr != addresses.end())
197 {
198 DPRINTF(HWPrefetch, "%s:Found a pf canidate, inserting into prefetch queue\n", cache->name());
199 //temp calc this here...
216 std::list<Addr>::iterator addrIter = addresses.begin();
217 std::list<Tick>::iterator delayIter = delays.begin();
218 for (; addrIter != addresses.end(); ++addrIter, ++delayIter) {
219 Addr addr = *addrIter;
220
221 pfIdentified++;
201 //create a prefetch memreq
202 Request * prefetchReq = new Request(*addr, blkSize, 0);
203 PacketPtr prefetch;
204 prefetch = new Packet(prefetchReq, MemCmd::HardPFReq, -1);
205 prefetch->allocate();
206 prefetch->req->setThreadContext(pkt->req->contextId(),
207 pkt->req->threadId());
222
209 prefetch->time = time + (*delay); //@todo ADD LATENCY HERE
210 //... initialize
223 DPRINTF(HWPrefetch, "Found a pf candidate addr: 0x%x, "
224 "inserting into prefetch queue with delay %d time %d\n",
225 addr, *delayIter, time);
226
212 //Check if it is already in the cache
213 if (cacheCheckPush) {
214 if (cache->inCache(prefetch->getAddr())) {
215 addr++;
216 delay++;
217 continue;
218 }
227 // Check if it is already in the cache
228 if (cacheCheckPush && cache->inCache(addr)) {
229 DPRINTF(HWPrefetch, "Prefetch addr already in cache\n");
230 continue;
231 }
232
221 //Check if it is already in the miss_queue
222 if (cache->inMissQueue(prefetch->getAddr())) {
223 addr++;
224 delay++;
233 // Check if it is already in the miss_queue
234 if (cache->inMissQueue(addr)) {
235 DPRINTF(HWPrefetch, "Prefetch addr already in miss queue\n");
236 continue;
237 }
238
228 //Check if it is already in the pf buffer
229 if (inPrefetch(prefetch->getAddr()) != pf.end()) {
239 // Check if it is already in the pf buffer
240 if (inPrefetch(addr) != pf.end()) {
241 pfBufferHit++;
231 addr++;
232 delay++;
242 DPRINTF(HWPrefetch, "Prefetch addr already in pf buffer\n");
243 continue;
244 }
245
236 //We just remove the head if we are full
237 if (pf.size() == size)
238 {
239 DPRINTF(HWPrefetch, "%s:Inserting into prefetch queue, it was full removing oldest\n", cache->name());
246 // create a prefetch memreq
247 Request *prefetchReq = new Request(*addrIter, blkSize, 0);
248 PacketPtr prefetch =
249 new Packet(prefetchReq, MemCmd::HardPFReq, Packet::Broadcast);
250 prefetch->allocate();
251 prefetch->req->setThreadContext(pkt->req->contextId(),
252 pkt->req->threadId());
253
254 prefetch->time = time + (*delayIter); // @todo ADD LATENCY HERE
255
256 // We just remove the head if we are full
257 if (pf.size() == size) {
258 pfRemovedFull++;
259 PacketPtr old_pkt = *pf.begin();
260 DPRINTF(HWPrefetch, "Prefetch queue full, "
261 "removing oldest 0x%x\n", old_pkt->getAddr());
262 delete old_pkt->req;
263 delete old_pkt;
264 pf.pop_front();
265 }
266
267 pf.push_back(prefetch);
245
246 //Make sure to request the bus, with proper delay
247 cache->requestMemSideBus(BaseCache::Request_PF, prefetch->time);
248
249 //Increment through the list
250 addr++;
251 delay++;
268 }
269 }
270
271 return pf.empty() ? 0 : pf.front()->time;
272}
273
274std::list<PacketPtr>::iterator
275BasePrefetcher::inPrefetch(Addr address)
276{
259 //Guaranteed to only be one match, we always check before inserting
277 // Guaranteed to only be one match, we always check before inserting
278 std::list<PacketPtr>::iterator iter;
261 for (iter=pf.begin(); iter != pf.end(); iter++) {
279 for (iter = pf.begin(); iter != pf.end(); iter++) {
280 if (((*iter)->getAddr() & ~(Addr)(blkSize-1)) == address) {
281 return iter;
282 }
283 }
284 return pf.end();
285}
286
269
287bool
288BasePrefetcher::samePage(Addr a, Addr b)
289{
290 return roundDown(a, TheISA::VMPageSize) == roundDown(b, TheISA::VMPageSize);
291}