1/* 2 * Copyright (c) 2014-2015 ARM Limited 3 * All rights reserved 4 * 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. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions are 16 * met: redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer; 18 * redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution; 21 * neither the name of the copyright holders nor the names of its 22 * contributors may be used to endorse or promote products derived from 23 * this software without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 * 37 * Authors: Mitch Hayenga 38 */ 39 40#include "mem/cache/prefetch/queued.hh" 41 42#include <cassert> 43 44#include "base/logging.hh" 45#include "base/trace.hh" 46#include "debug/HWPrefetch.hh" 47#include "mem/request.hh" 48#include "params/QueuedPrefetcher.hh" 49 50QueuedPrefetcher::QueuedPrefetcher(const QueuedPrefetcherParams *p) 51 : BasePrefetcher(p), queueSize(p->queue_size), latency(p->latency), 52 queueSquash(p->queue_squash), queueFilter(p->queue_filter), 53 cacheSnoop(p->cache_snoop), tagPrefetch(p->tag_prefetch) 54{ 55 56} 57 58QueuedPrefetcher::~QueuedPrefetcher() 59{ 60 // Delete the queued prefetch packets 61 for (DeferredPacket &p : pfq) { 62 delete p.pkt; 63 } 64} 65 66void 67QueuedPrefetcher::notify(const PacketPtr &pkt) 68{ 69 // Verify this access type is observed by prefetcher 70 if (observeAccess(pkt)) { 71 Addr blk_addr = pkt->getBlockAddr(blkSize); 72 bool is_secure = pkt->isSecure(); 73 74 // Squash queued prefetches if demand miss to same line 75 if (queueSquash) { 76 auto itr = pfq.begin(); 77 while (itr != pfq.end()) { 78 if (itr->pkt->getAddr() == blk_addr && 79 itr->pkt->isSecure() == is_secure) { 80 delete itr->pkt; 81 itr = pfq.erase(itr); 82 } else { 83 ++itr; 84 } 85 } 86 } 87 88 // Calculate prefetches given this access 89 std::vector<AddrPriority> addresses; 90 calculatePrefetch(pkt, addresses); 91 92 // Queue up generated prefetches 93 for (AddrPriority& pf_info : addresses) {
| 1/* 2 * Copyright (c) 2014-2015 ARM Limited 3 * All rights reserved 4 * 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. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions are 16 * met: redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer; 18 * redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution; 21 * neither the name of the copyright holders nor the names of its 22 * contributors may be used to endorse or promote products derived from 23 * this software without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 * 37 * Authors: Mitch Hayenga 38 */ 39 40#include "mem/cache/prefetch/queued.hh" 41 42#include <cassert> 43 44#include "base/logging.hh" 45#include "base/trace.hh" 46#include "debug/HWPrefetch.hh" 47#include "mem/request.hh" 48#include "params/QueuedPrefetcher.hh" 49 50QueuedPrefetcher::QueuedPrefetcher(const QueuedPrefetcherParams *p) 51 : BasePrefetcher(p), queueSize(p->queue_size), latency(p->latency), 52 queueSquash(p->queue_squash), queueFilter(p->queue_filter), 53 cacheSnoop(p->cache_snoop), tagPrefetch(p->tag_prefetch) 54{ 55 56} 57 58QueuedPrefetcher::~QueuedPrefetcher() 59{ 60 // Delete the queued prefetch packets 61 for (DeferredPacket &p : pfq) { 62 delete p.pkt; 63 } 64} 65 66void 67QueuedPrefetcher::notify(const PacketPtr &pkt) 68{ 69 // Verify this access type is observed by prefetcher 70 if (observeAccess(pkt)) { 71 Addr blk_addr = pkt->getBlockAddr(blkSize); 72 bool is_secure = pkt->isSecure(); 73 74 // Squash queued prefetches if demand miss to same line 75 if (queueSquash) { 76 auto itr = pfq.begin(); 77 while (itr != pfq.end()) { 78 if (itr->pkt->getAddr() == blk_addr && 79 itr->pkt->isSecure() == is_secure) { 80 delete itr->pkt; 81 itr = pfq.erase(itr); 82 } else { 83 ++itr; 84 } 85 } 86 } 87 88 // Calculate prefetches given this access 89 std::vector<AddrPriority> addresses; 90 calculatePrefetch(pkt, addresses); 91 92 // Queue up generated prefetches 93 for (AddrPriority& pf_info : addresses) {
|
94
| |
95 // Block align prefetch address
| 94 // Block align prefetch address
|
96 pf_info.first &= ~(Addr)(blkSize - 1);
| 95 pf_info.first = blockAddress(pf_info.first);
|
97 98 pfIdentified++; 99 DPRINTF(HWPrefetch, "Found a pf candidate addr: %#x, " 100 "inserting into prefetch queue.\n", pf_info.first); 101 102 // Create and insert the request 103 PacketPtr pf_pkt = insert(pf_info, is_secure); 104 105 if (pf_pkt != nullptr) { 106 if (tagPrefetch && pkt->req->hasPC()) { 107 // Tag prefetch packet with accessing pc 108 pf_pkt->req->setPC(pkt->req->getPC()); 109 } 110 } 111 } 112 } 113} 114 115PacketPtr 116QueuedPrefetcher::getPacket() 117{ 118 DPRINTF(HWPrefetch, "Requesting a prefetch to issue.\n"); 119 120 if (pfq.empty()) { 121 DPRINTF(HWPrefetch, "No hardware prefetches available.\n"); 122 return nullptr; 123 } 124 125 PacketPtr pkt = pfq.begin()->pkt; 126 pfq.pop_front(); 127 128 pfIssued++; 129 assert(pkt != nullptr); 130 DPRINTF(HWPrefetch, "Generating prefetch for %#x.\n", pkt->getAddr()); 131 return pkt; 132} 133
| 96 97 pfIdentified++; 98 DPRINTF(HWPrefetch, "Found a pf candidate addr: %#x, " 99 "inserting into prefetch queue.\n", pf_info.first); 100 101 // Create and insert the request 102 PacketPtr pf_pkt = insert(pf_info, is_secure); 103 104 if (pf_pkt != nullptr) { 105 if (tagPrefetch && pkt->req->hasPC()) { 106 // Tag prefetch packet with accessing pc 107 pf_pkt->req->setPC(pkt->req->getPC()); 108 } 109 } 110 } 111 } 112} 113 114PacketPtr 115QueuedPrefetcher::getPacket() 116{ 117 DPRINTF(HWPrefetch, "Requesting a prefetch to issue.\n"); 118 119 if (pfq.empty()) { 120 DPRINTF(HWPrefetch, "No hardware prefetches available.\n"); 121 return nullptr; 122 } 123 124 PacketPtr pkt = pfq.begin()->pkt; 125 pfq.pop_front(); 126 127 pfIssued++; 128 assert(pkt != nullptr); 129 DPRINTF(HWPrefetch, "Generating prefetch for %#x.\n", pkt->getAddr()); 130 return pkt; 131} 132
|
134std::list<QueuedPrefetcher::DeferredPacket>::const_iterator
| 133QueuedPrefetcher::const_iterator
|
135QueuedPrefetcher::inPrefetch(Addr address, bool is_secure) const 136{ 137 for (const_iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 138 if ((*dp).pkt->getAddr() == address && 139 (*dp).pkt->isSecure() == is_secure) return dp; 140 } 141 142 return pfq.end(); 143} 144 145QueuedPrefetcher::iterator 146QueuedPrefetcher::inPrefetch(Addr address, bool is_secure) 147{ 148 for (iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 149 if (dp->pkt->getAddr() == address && 150 dp->pkt->isSecure() == is_secure) return dp; 151 } 152 153 return pfq.end(); 154} 155 156void 157QueuedPrefetcher::regStats() 158{ 159 BasePrefetcher::regStats(); 160 161 pfIdentified 162 .name(name() + ".pfIdentified") 163 .desc("number of prefetch candidates identified"); 164 165 pfBufferHit 166 .name(name() + ".pfBufferHit") 167 .desc("number of redundant prefetches already in prefetch queue"); 168 169 pfInCache 170 .name(name() + ".pfInCache") 171 .desc("number of redundant prefetches already in cache/mshr dropped"); 172 173 pfRemovedFull 174 .name(name() + ".pfRemovedFull") 175 .desc("number of prefetches dropped due to prefetch queue size"); 176 177 pfSpanPage 178 .name(name() + ".pfSpanPage") 179 .desc("number of prefetches not generated due to page crossing"); 180} 181 182PacketPtr 183QueuedPrefetcher::insert(AddrPriority &pf_info, bool is_secure) 184{ 185 if (queueFilter) { 186 iterator it = inPrefetch(pf_info.first, is_secure); 187 /* If the address is already in the queue, update priority and leave */ 188 if (it != pfq.end()) { 189 pfBufferHit++; 190 if (it->priority < pf_info.second) { 191 /* Update priority value and position in the queue */ 192 it->priority = pf_info.second; 193 iterator prev = it; 194 bool cont = true; 195 while (cont && prev != pfq.begin()) { 196 prev--; 197 /* If the packet has higher priority, swap */ 198 if (*it > *prev) { 199 std::swap(*it, *prev); 200 it = prev; 201 } 202 } 203 DPRINTF(HWPrefetch, "Prefetch addr already in " 204 "prefetch queue, priority updated\n"); 205 } else { 206 DPRINTF(HWPrefetch, "Prefetch addr already in " 207 "prefetch queue\n"); 208 } 209 return nullptr; 210 } 211 } 212 213 if (cacheSnoop && (inCache(pf_info.first, is_secure) || 214 inMissQueue(pf_info.first, is_secure))) { 215 pfInCache++; 216 DPRINTF(HWPrefetch, "Dropping redundant in " 217 "cache/MSHR prefetch addr:%#x\n", pf_info.first); 218 return nullptr; 219 } 220 221 /* Create a prefetch memory request */ 222 RequestPtr pf_req = 223 std::make_shared<Request>(pf_info.first, blkSize, 0, masterId); 224 225 if (is_secure) { 226 pf_req->setFlags(Request::SECURE); 227 } 228 pf_req->taskId(ContextSwitchTaskId::Prefetcher); 229 PacketPtr pf_pkt = new Packet(pf_req, MemCmd::HardPFReq); 230 pf_pkt->allocate(); 231 232 /* Verify prefetch buffer space for request */ 233 if (pfq.size() == queueSize) { 234 pfRemovedFull++; 235 /* Lowest priority packet */ 236 iterator it = pfq.end(); 237 panic_if (it == pfq.begin(), "Prefetch queue is both full and empty!"); 238 --it; 239 /* Look for oldest in that level of priority */ 240 panic_if (it == pfq.begin(), "Prefetch queue is full with 1 element!"); 241 iterator prev = it; 242 bool cont = true; 243 /* While not at the head of the queue */ 244 while (cont && prev != pfq.begin()) { 245 prev--; 246 /* While at the same level of priority */ 247 cont = (*prev).priority == (*it).priority; 248 if (cont) 249 /* update pointer */ 250 it = prev; 251 } 252 DPRINTF(HWPrefetch, "Prefetch queue full, removing lowest priority " 253 "oldest packet, addr: %#x", it->pkt->getAddr()); 254 delete it->pkt; 255 pfq.erase(it); 256 } 257 258 Tick pf_time = curTick() + clockPeriod() * latency; 259 DPRINTF(HWPrefetch, "Prefetch queued. " 260 "addr:%#x priority: %3d tick:%lld.\n", 261 pf_info.first, pf_info.second, pf_time); 262 263 /* Create the packet and find the spot to insert it */ 264 DeferredPacket dpp(pf_time, pf_pkt, pf_info.second); 265 if (pfq.size() == 0) { 266 pfq.emplace_back(dpp); 267 } else { 268 iterator it = pfq.end(); 269 while (it != pfq.begin() && dpp > *it) 270 --it; 271 /* If we reach the head, we have to see if the new element is new head 272 * or not */ 273 if (it == pfq.begin() && dpp <= *it) 274 it++; 275 pfq.insert(it, dpp); 276 } 277 278 return pf_pkt; 279}
| 134QueuedPrefetcher::inPrefetch(Addr address, bool is_secure) const 135{ 136 for (const_iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 137 if ((*dp).pkt->getAddr() == address && 138 (*dp).pkt->isSecure() == is_secure) return dp; 139 } 140 141 return pfq.end(); 142} 143 144QueuedPrefetcher::iterator 145QueuedPrefetcher::inPrefetch(Addr address, bool is_secure) 146{ 147 for (iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 148 if (dp->pkt->getAddr() == address && 149 dp->pkt->isSecure() == is_secure) return dp; 150 } 151 152 return pfq.end(); 153} 154 155void 156QueuedPrefetcher::regStats() 157{ 158 BasePrefetcher::regStats(); 159 160 pfIdentified 161 .name(name() + ".pfIdentified") 162 .desc("number of prefetch candidates identified"); 163 164 pfBufferHit 165 .name(name() + ".pfBufferHit") 166 .desc("number of redundant prefetches already in prefetch queue"); 167 168 pfInCache 169 .name(name() + ".pfInCache") 170 .desc("number of redundant prefetches already in cache/mshr dropped"); 171 172 pfRemovedFull 173 .name(name() + ".pfRemovedFull") 174 .desc("number of prefetches dropped due to prefetch queue size"); 175 176 pfSpanPage 177 .name(name() + ".pfSpanPage") 178 .desc("number of prefetches not generated due to page crossing"); 179} 180 181PacketPtr 182QueuedPrefetcher::insert(AddrPriority &pf_info, bool is_secure) 183{ 184 if (queueFilter) { 185 iterator it = inPrefetch(pf_info.first, is_secure); 186 /* If the address is already in the queue, update priority and leave */ 187 if (it != pfq.end()) { 188 pfBufferHit++; 189 if (it->priority < pf_info.second) { 190 /* Update priority value and position in the queue */ 191 it->priority = pf_info.second; 192 iterator prev = it; 193 bool cont = true; 194 while (cont && prev != pfq.begin()) { 195 prev--; 196 /* If the packet has higher priority, swap */ 197 if (*it > *prev) { 198 std::swap(*it, *prev); 199 it = prev; 200 } 201 } 202 DPRINTF(HWPrefetch, "Prefetch addr already in " 203 "prefetch queue, priority updated\n"); 204 } else { 205 DPRINTF(HWPrefetch, "Prefetch addr already in " 206 "prefetch queue\n"); 207 } 208 return nullptr; 209 } 210 } 211 212 if (cacheSnoop && (inCache(pf_info.first, is_secure) || 213 inMissQueue(pf_info.first, is_secure))) { 214 pfInCache++; 215 DPRINTF(HWPrefetch, "Dropping redundant in " 216 "cache/MSHR prefetch addr:%#x\n", pf_info.first); 217 return nullptr; 218 } 219 220 /* Create a prefetch memory request */ 221 RequestPtr pf_req = 222 std::make_shared<Request>(pf_info.first, blkSize, 0, masterId); 223 224 if (is_secure) { 225 pf_req->setFlags(Request::SECURE); 226 } 227 pf_req->taskId(ContextSwitchTaskId::Prefetcher); 228 PacketPtr pf_pkt = new Packet(pf_req, MemCmd::HardPFReq); 229 pf_pkt->allocate(); 230 231 /* Verify prefetch buffer space for request */ 232 if (pfq.size() == queueSize) { 233 pfRemovedFull++; 234 /* Lowest priority packet */ 235 iterator it = pfq.end(); 236 panic_if (it == pfq.begin(), "Prefetch queue is both full and empty!"); 237 --it; 238 /* Look for oldest in that level of priority */ 239 panic_if (it == pfq.begin(), "Prefetch queue is full with 1 element!"); 240 iterator prev = it; 241 bool cont = true; 242 /* While not at the head of the queue */ 243 while (cont && prev != pfq.begin()) { 244 prev--; 245 /* While at the same level of priority */ 246 cont = (*prev).priority == (*it).priority; 247 if (cont) 248 /* update pointer */ 249 it = prev; 250 } 251 DPRINTF(HWPrefetch, "Prefetch queue full, removing lowest priority " 252 "oldest packet, addr: %#x", it->pkt->getAddr()); 253 delete it->pkt; 254 pfq.erase(it); 255 } 256 257 Tick pf_time = curTick() + clockPeriod() * latency; 258 DPRINTF(HWPrefetch, "Prefetch queued. " 259 "addr:%#x priority: %3d tick:%lld.\n", 260 pf_info.first, pf_info.second, pf_time); 261 262 /* Create the packet and find the spot to insert it */ 263 DeferredPacket dpp(pf_time, pf_pkt, pf_info.second); 264 if (pfq.size() == 0) { 265 pfq.emplace_back(dpp); 266 } else { 267 iterator it = pfq.end(); 268 while (it != pfq.begin() && dpp > *it) 269 --it; 270 /* If we reach the head, we have to see if the new element is new head 271 * or not */ 272 if (it == pfq.begin() && dpp <= *it) 273 it++; 274 pfq.insert(it, dpp); 275 } 276 277 return pf_pkt; 278}
|