queued.cc revision 11439
113531Sjairo.balart@metempsy.com/* 214167Sgiacomo.travaglini@arm.com * Copyright (c) 2014-2015 ARM Limited 314167Sgiacomo.travaglini@arm.com * All rights reserved 414167Sgiacomo.travaglini@arm.com * 514167Sgiacomo.travaglini@arm.com * The license below extends only to copyright in the software and shall 614167Sgiacomo.travaglini@arm.com * not be construed as granting a license to any other intellectual 714167Sgiacomo.travaglini@arm.com * property including but not limited to intellectual property relating 814167Sgiacomo.travaglini@arm.com * to a hardware implementation of the functionality of the software 914167Sgiacomo.travaglini@arm.com * licensed hereunder. You may use the software subject to the license 1014167Sgiacomo.travaglini@arm.com * terms below provided that you ensure that this notice is replicated 1114167Sgiacomo.travaglini@arm.com * unmodified and in its entirety in all distributions of the software, 1214167Sgiacomo.travaglini@arm.com * modified or unmodified, in source code or in binary form. 1314167Sgiacomo.travaglini@arm.com * 1413531Sjairo.balart@metempsy.com * Redistribution and use in source and binary forms, with or without 1513531Sjairo.balart@metempsy.com * modification, are permitted provided that the following conditions are 1613531Sjairo.balart@metempsy.com * met: redistributions of source code must retain the above copyright 1713531Sjairo.balart@metempsy.com * notice, this list of conditions and the following disclaimer; 1813531Sjairo.balart@metempsy.com * redistributions in binary form must reproduce the above copyright 1913531Sjairo.balart@metempsy.com * notice, this list of conditions and the following disclaimer in the 2013531Sjairo.balart@metempsy.com * documentation and/or other materials provided with the distribution; 2113531Sjairo.balart@metempsy.com * neither the name of the copyright holders nor the names of its 2213531Sjairo.balart@metempsy.com * contributors may be used to endorse or promote products derived from 2313531Sjairo.balart@metempsy.com * this software without specific prior written permission. 2413531Sjairo.balart@metempsy.com * 2513531Sjairo.balart@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2613531Sjairo.balart@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2713531Sjairo.balart@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2813531Sjairo.balart@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2913531Sjairo.balart@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3013531Sjairo.balart@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3113531Sjairo.balart@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3213531Sjairo.balart@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3313531Sjairo.balart@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3413531Sjairo.balart@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3513531Sjairo.balart@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3613531Sjairo.balart@metempsy.com * 3713531Sjairo.balart@metempsy.com * Authors: Mitch Hayenga 3813531Sjairo.balart@metempsy.com */ 3913531Sjairo.balart@metempsy.com 4013531Sjairo.balart@metempsy.com#include "debug/HWPrefetch.hh" 4113531Sjairo.balart@metempsy.com#include "mem/cache/prefetch/queued.hh" 4213756Sjairo.balart@metempsy.com#include "mem/cache/base.hh" 4313531Sjairo.balart@metempsy.com 4413531Sjairo.balart@metempsy.comQueuedPrefetcher::QueuedPrefetcher(const QueuedPrefetcherParams *p) 4513531Sjairo.balart@metempsy.com : BasePrefetcher(p), queueSize(p->queue_size), latency(p->latency), 4613531Sjairo.balart@metempsy.com queueSquash(p->queue_squash), queueFilter(p->queue_filter), 4714257Sgiacomo.travaglini@arm.com cacheSnoop(p->cache_snoop), tagPrefetch(p->tag_prefetch) 4813531Sjairo.balart@metempsy.com{ 4913531Sjairo.balart@metempsy.com 5013531Sjairo.balart@metempsy.com} 5113531Sjairo.balart@metempsy.com 5213531Sjairo.balart@metempsy.comQueuedPrefetcher::~QueuedPrefetcher() 5313756Sjairo.balart@metempsy.com{ 5413756Sjairo.balart@metempsy.com // Delete the queued prefetch packets 5513756Sjairo.balart@metempsy.com for (DeferredPacket &p : pfq) { 5613756Sjairo.balart@metempsy.com delete p.pkt->req; 5713756Sjairo.balart@metempsy.com delete p.pkt; 5813756Sjairo.balart@metempsy.com } 5913756Sjairo.balart@metempsy.com} 6013531Sjairo.balart@metempsy.com 6113756Sjairo.balart@metempsy.comTick 6213756Sjairo.balart@metempsy.comQueuedPrefetcher::notify(const PacketPtr &pkt) 6313756Sjairo.balart@metempsy.com{ 6413756Sjairo.balart@metempsy.com // Verify this access type is observed by prefetcher 6513756Sjairo.balart@metempsy.com if (observeAccess(pkt)) { 6613756Sjairo.balart@metempsy.com Addr blk_addr = pkt->getBlockAddr(blkSize); 6713756Sjairo.balart@metempsy.com bool is_secure = pkt->isSecure(); 6813531Sjairo.balart@metempsy.com 6913531Sjairo.balart@metempsy.com // Squash queued prefetches if demand miss to same line 7013531Sjairo.balart@metempsy.com if (queueSquash) { 7113531Sjairo.balart@metempsy.com auto itr = pfq.begin(); 7213531Sjairo.balart@metempsy.com while (itr != pfq.end()) { 7313531Sjairo.balart@metempsy.com if (itr->pkt->getAddr() == blk_addr && 7413531Sjairo.balart@metempsy.com itr->pkt->isSecure() == is_secure) { 7513531Sjairo.balart@metempsy.com delete itr->pkt->req; 7613531Sjairo.balart@metempsy.com delete itr->pkt; 7713531Sjairo.balart@metempsy.com itr = pfq.erase(itr); 7813531Sjairo.balart@metempsy.com } else { 7913531Sjairo.balart@metempsy.com ++itr; 8014167Sgiacomo.travaglini@arm.com } 8114257Sgiacomo.travaglini@arm.com } 8214167Sgiacomo.travaglini@arm.com } 8314167Sgiacomo.travaglini@arm.com 8414167Sgiacomo.travaglini@arm.com // Calculate prefetches given this access 8514167Sgiacomo.travaglini@arm.com std::vector<AddrPriority> addresses; 8614167Sgiacomo.travaglini@arm.com calculatePrefetch(pkt, addresses); 8713531Sjairo.balart@metempsy.com 8813531Sjairo.balart@metempsy.com // Queue up generated prefetches 8914257Sgiacomo.travaglini@arm.com for (AddrPriority& pf_info : addresses) { 9014257Sgiacomo.travaglini@arm.com 9114257Sgiacomo.travaglini@arm.com // Block align prefetch address 9214257Sgiacomo.travaglini@arm.com pf_info.first &= ~(Addr)(blkSize - 1); 9314257Sgiacomo.travaglini@arm.com 9414257Sgiacomo.travaglini@arm.com pfIdentified++; 9514257Sgiacomo.travaglini@arm.com DPRINTF(HWPrefetch, "Found a pf candidate addr: %#x, " 9614257Sgiacomo.travaglini@arm.com "inserting into prefetch queue.\n", pf_info.first); 9714257Sgiacomo.travaglini@arm.com 9814257Sgiacomo.travaglini@arm.com // Create and insert the request 9914257Sgiacomo.travaglini@arm.com PacketPtr pf_pkt = insert(pf_info, is_secure); 10014257Sgiacomo.travaglini@arm.com 10114257Sgiacomo.travaglini@arm.com if (pf_pkt != nullptr) { 10214257Sgiacomo.travaglini@arm.com if (tagPrefetch && pkt->req->hasPC()) { 10314257Sgiacomo.travaglini@arm.com // Tag prefetch packet with accessing pc 10414257Sgiacomo.travaglini@arm.com pf_pkt->req->setPC(pkt->req->getPC()); 10514257Sgiacomo.travaglini@arm.com } 10614257Sgiacomo.travaglini@arm.com } 10714257Sgiacomo.travaglini@arm.com } 10814257Sgiacomo.travaglini@arm.com } 10914257Sgiacomo.travaglini@arm.com 11014257Sgiacomo.travaglini@arm.com return pfq.empty() ? MaxTick : pfq.front().tick; 11114257Sgiacomo.travaglini@arm.com} 11214257Sgiacomo.travaglini@arm.com 11314257Sgiacomo.travaglini@arm.comPacketPtr 11414257Sgiacomo.travaglini@arm.comQueuedPrefetcher::getPacket() 11514257Sgiacomo.travaglini@arm.com{ 11614257Sgiacomo.travaglini@arm.com DPRINTF(HWPrefetch, "Requesting a prefetch to issue.\n"); 11714257Sgiacomo.travaglini@arm.com 11814257Sgiacomo.travaglini@arm.com if (pfq.empty()) { 11914257Sgiacomo.travaglini@arm.com DPRINTF(HWPrefetch, "No hardware prefetches available.\n"); 12013531Sjairo.balart@metempsy.com return NULL; 12113531Sjairo.balart@metempsy.com } 12213531Sjairo.balart@metempsy.com 12313531Sjairo.balart@metempsy.com PacketPtr pkt = pfq.begin()->pkt; 12413531Sjairo.balart@metempsy.com pfq.pop_front(); 12513531Sjairo.balart@metempsy.com 12613531Sjairo.balart@metempsy.com pfIssued++; 12713531Sjairo.balart@metempsy.com assert(pkt != NULL); 12813531Sjairo.balart@metempsy.com DPRINTF(HWPrefetch, "Generating prefetch for %#x.\n", pkt->getAddr()); 12913531Sjairo.balart@metempsy.com return pkt; 13013531Sjairo.balart@metempsy.com} 13113531Sjairo.balart@metempsy.com 13213531Sjairo.balart@metempsy.comstd::list<QueuedPrefetcher::DeferredPacket>::const_iterator 13313531Sjairo.balart@metempsy.comQueuedPrefetcher::inPrefetch(Addr address, bool is_secure) const 13413531Sjairo.balart@metempsy.com{ 13513531Sjairo.balart@metempsy.com for (const_iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 13613531Sjairo.balart@metempsy.com if ((*dp).pkt->getAddr() == address && 13713531Sjairo.balart@metempsy.com (*dp).pkt->isSecure() == is_secure) return dp; 13813531Sjairo.balart@metempsy.com } 13913531Sjairo.balart@metempsy.com 14013531Sjairo.balart@metempsy.com return pfq.end(); 14113531Sjairo.balart@metempsy.com} 14213531Sjairo.balart@metempsy.com 14313531Sjairo.balart@metempsy.comQueuedPrefetcher::iterator 14413531Sjairo.balart@metempsy.comQueuedPrefetcher::inPrefetch(Addr address, bool is_secure) 14513531Sjairo.balart@metempsy.com{ 14613531Sjairo.balart@metempsy.com for (iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 14713531Sjairo.balart@metempsy.com if (dp->pkt->getAddr() == address && 14813531Sjairo.balart@metempsy.com dp->pkt->isSecure() == is_secure) return dp; 14913531Sjairo.balart@metempsy.com } 15013531Sjairo.balart@metempsy.com 15113531Sjairo.balart@metempsy.com return pfq.end(); 15213531Sjairo.balart@metempsy.com} 15313531Sjairo.balart@metempsy.com 15413531Sjairo.balart@metempsy.comvoid 15513531Sjairo.balart@metempsy.comQueuedPrefetcher::regStats() 15613531Sjairo.balart@metempsy.com{ 15713531Sjairo.balart@metempsy.com BasePrefetcher::regStats(); 15813531Sjairo.balart@metempsy.com 15913531Sjairo.balart@metempsy.com pfIdentified 16013531Sjairo.balart@metempsy.com .name(name() + ".pfIdentified") 16113531Sjairo.balart@metempsy.com .desc("number of prefetch candidates identified"); 16213531Sjairo.balart@metempsy.com 16313531Sjairo.balart@metempsy.com pfBufferHit 16413531Sjairo.balart@metempsy.com .name(name() + ".pfBufferHit") 16513531Sjairo.balart@metempsy.com .desc("number of redundant prefetches already in prefetch queue"); 16613531Sjairo.balart@metempsy.com 16713531Sjairo.balart@metempsy.com pfInCache 16813531Sjairo.balart@metempsy.com .name(name() + ".pfInCache") 16913531Sjairo.balart@metempsy.com .desc("number of redundant prefetches already in cache/mshr dropped"); 17013531Sjairo.balart@metempsy.com 17113531Sjairo.balart@metempsy.com pfRemovedFull 17213531Sjairo.balart@metempsy.com .name(name() + ".pfRemovedFull") 17313531Sjairo.balart@metempsy.com .desc("number of prefetches dropped due to prefetch queue size"); 17413531Sjairo.balart@metempsy.com 17513531Sjairo.balart@metempsy.com pfSpanPage 17613531Sjairo.balart@metempsy.com .name(name() + ".pfSpanPage") 17713531Sjairo.balart@metempsy.com .desc("number of prefetches not generated due to page crossing"); 17813531Sjairo.balart@metempsy.com} 17913531Sjairo.balart@metempsy.com 18013531Sjairo.balart@metempsy.comPacketPtr 18113531Sjairo.balart@metempsy.comQueuedPrefetcher::insert(AddrPriority &pf_info, bool is_secure) 18213756Sjairo.balart@metempsy.com{ 18313531Sjairo.balart@metempsy.com if (queueFilter) { 18413531Sjairo.balart@metempsy.com iterator it = inPrefetch(pf_info.first, is_secure); 18513531Sjairo.balart@metempsy.com /* If the address is already in the queue, update priority and leave */ 18613531Sjairo.balart@metempsy.com if (it != pfq.end()) { 18713756Sjairo.balart@metempsy.com pfBufferHit++; 18813531Sjairo.balart@metempsy.com if (it->priority < pf_info.second) { 18913531Sjairo.balart@metempsy.com /* Update priority value and position in the queue */ 19013531Sjairo.balart@metempsy.com it->priority = pf_info.second; 19113531Sjairo.balart@metempsy.com iterator prev = it; 19213531Sjairo.balart@metempsy.com bool cont = true; 19313531Sjairo.balart@metempsy.com while (cont && prev != pfq.begin()) { 19413531Sjairo.balart@metempsy.com prev--; 19513531Sjairo.balart@metempsy.com /* If the packet has higher priority, swap */ 19613531Sjairo.balart@metempsy.com if (*it > *prev) { 19713756Sjairo.balart@metempsy.com std::swap(*it, *prev); 19813756Sjairo.balart@metempsy.com it = prev; 19913531Sjairo.balart@metempsy.com } 20013531Sjairo.balart@metempsy.com } 20113531Sjairo.balart@metempsy.com DPRINTF(HWPrefetch, "Prefetch addr already in " 20213531Sjairo.balart@metempsy.com "prefetch queue, priority updated\n"); 20313531Sjairo.balart@metempsy.com } else { 20413531Sjairo.balart@metempsy.com DPRINTF(HWPrefetch, "Prefetch addr already in " 20513531Sjairo.balart@metempsy.com "prefetch queue\n"); 20613531Sjairo.balart@metempsy.com } 20713531Sjairo.balart@metempsy.com return nullptr; 20813531Sjairo.balart@metempsy.com } 20913531Sjairo.balart@metempsy.com } 21013531Sjairo.balart@metempsy.com 21113531Sjairo.balart@metempsy.com if (cacheSnoop && (inCache(pf_info.first, is_secure) || 21213531Sjairo.balart@metempsy.com inMissQueue(pf_info.first, is_secure))) { 21313531Sjairo.balart@metempsy.com pfInCache++; 21413531Sjairo.balart@metempsy.com DPRINTF(HWPrefetch, "Dropping redundant in " 21513531Sjairo.balart@metempsy.com "cache/MSHR prefetch addr:%#x\n", pf_info.first); 21613531Sjairo.balart@metempsy.com return nullptr; 21713531Sjairo.balart@metempsy.com } 21813756Sjairo.balart@metempsy.com 21913756Sjairo.balart@metempsy.com /* Create a prefetch memory request */ 22013531Sjairo.balart@metempsy.com Request *pf_req = 22113531Sjairo.balart@metempsy.com new Request(pf_info.first, blkSize, 0, masterId); 22213531Sjairo.balart@metempsy.com 22313531Sjairo.balart@metempsy.com if (is_secure) { 22413531Sjairo.balart@metempsy.com pf_req->setFlags(Request::SECURE); 22513531Sjairo.balart@metempsy.com } 22613531Sjairo.balart@metempsy.com pf_req->taskId(ContextSwitchTaskId::Prefetcher); 22713531Sjairo.balart@metempsy.com PacketPtr pf_pkt = new Packet(pf_req, MemCmd::HardPFReq); 22813531Sjairo.balart@metempsy.com pf_pkt->allocate(); 22913531Sjairo.balart@metempsy.com 23013756Sjairo.balart@metempsy.com /* Verify prefetch buffer space for request */ 23113531Sjairo.balart@metempsy.com if (pfq.size() == queueSize) { 23213531Sjairo.balart@metempsy.com pfRemovedFull++; 23313531Sjairo.balart@metempsy.com /* Lowest priority packet */ 23413531Sjairo.balart@metempsy.com iterator it = pfq.end(); 23513531Sjairo.balart@metempsy.com panic_if (it == pfq.begin(), "Prefetch queue is both full and empty!"); 23613531Sjairo.balart@metempsy.com --it; 23713531Sjairo.balart@metempsy.com /* Look for oldest in that level of priority */ 23813531Sjairo.balart@metempsy.com panic_if (it == pfq.begin(), "Prefetch queue is full with 1 element!"); 23913756Sjairo.balart@metempsy.com iterator prev = it; 24013756Sjairo.balart@metempsy.com bool cont = true; 24113531Sjairo.balart@metempsy.com /* While not at the head of the queue */ 24213531Sjairo.balart@metempsy.com while (cont && prev != pfq.begin()) { 24313531Sjairo.balart@metempsy.com prev--; 24413531Sjairo.balart@metempsy.com /* While at the same level of priority */ 24513531Sjairo.balart@metempsy.com cont = (*prev).priority == (*it).priority; 24613531Sjairo.balart@metempsy.com if (cont) 24713531Sjairo.balart@metempsy.com /* update pointer */ 24813531Sjairo.balart@metempsy.com it = prev; 24913531Sjairo.balart@metempsy.com } 25013531Sjairo.balart@metempsy.com DPRINTF(HWPrefetch, "Prefetch queue full, removing lowest priority " 25113531Sjairo.balart@metempsy.com "oldest packet, addr: %#x", it->pkt->getAddr()); 25213531Sjairo.balart@metempsy.com delete it->pkt->req; 25313531Sjairo.balart@metempsy.com delete it->pkt; 25413756Sjairo.balart@metempsy.com pfq.erase(it); 25513531Sjairo.balart@metempsy.com } 25613531Sjairo.balart@metempsy.com 25713531Sjairo.balart@metempsy.com Tick pf_time = curTick() + clockPeriod() * latency; 25813531Sjairo.balart@metempsy.com DPRINTF(HWPrefetch, "Prefetch queued. " 25913531Sjairo.balart@metempsy.com "addr:%#x priority: %3d tick:%lld.\n", 26013531Sjairo.balart@metempsy.com pf_info.first, pf_info.second, pf_time); 26113531Sjairo.balart@metempsy.com 26213531Sjairo.balart@metempsy.com /* Create the packet and find the spot to insert it */ 26313756Sjairo.balart@metempsy.com DeferredPacket dpp(pf_time, pf_pkt, pf_info.second); 26413756Sjairo.balart@metempsy.com if (pfq.size() == 0) { 26513531Sjairo.balart@metempsy.com pfq.emplace_back(dpp); 26613531Sjairo.balart@metempsy.com } else { 26713531Sjairo.balart@metempsy.com iterator it = pfq.end(); 26813531Sjairo.balart@metempsy.com while (it != pfq.begin() && dpp > *it) 26913531Sjairo.balart@metempsy.com --it; 27013531Sjairo.balart@metempsy.com /* If we reach the head, we have to see if the new element is new head 27113531Sjairo.balart@metempsy.com * or not */ 27213531Sjairo.balart@metempsy.com if (it == pfq.begin() && dpp <= *it) 27313531Sjairo.balart@metempsy.com it++; 27413531Sjairo.balart@metempsy.com pfq.insert(it, dpp); 27513531Sjairo.balart@metempsy.com } 27613531Sjairo.balart@metempsy.com 27713756Sjairo.balart@metempsy.com return pf_pkt; 27813531Sjairo.balart@metempsy.com} 27913531Sjairo.balart@metempsy.com