queued.cc revision 11793
110623Smitch.hayenga@arm.com/* 211439SRekai.GonzalezAlberquilla@arm.com * Copyright (c) 2014-2015 ARM Limited 310623Smitch.hayenga@arm.com * All rights reserved 410623Smitch.hayenga@arm.com * 510623Smitch.hayenga@arm.com * The license below extends only to copyright in the software and shall 610623Smitch.hayenga@arm.com * not be construed as granting a license to any other intellectual 710623Smitch.hayenga@arm.com * property including but not limited to intellectual property relating 810623Smitch.hayenga@arm.com * to a hardware implementation of the functionality of the software 910623Smitch.hayenga@arm.com * licensed hereunder. You may use the software subject to the license 1010623Smitch.hayenga@arm.com * terms below provided that you ensure that this notice is replicated 1110623Smitch.hayenga@arm.com * unmodified and in its entirety in all distributions of the software, 1210623Smitch.hayenga@arm.com * modified or unmodified, in source code or in binary form. 1310623Smitch.hayenga@arm.com * 1410623Smitch.hayenga@arm.com * Redistribution and use in source and binary forms, with or without 1510623Smitch.hayenga@arm.com * modification, are permitted provided that the following conditions are 1610623Smitch.hayenga@arm.com * met: redistributions of source code must retain the above copyright 1710623Smitch.hayenga@arm.com * notice, this list of conditions and the following disclaimer; 1810623Smitch.hayenga@arm.com * redistributions in binary form must reproduce the above copyright 1910623Smitch.hayenga@arm.com * notice, this list of conditions and the following disclaimer in the 2010623Smitch.hayenga@arm.com * documentation and/or other materials provided with the distribution; 2110623Smitch.hayenga@arm.com * neither the name of the copyright holders nor the names of its 2210623Smitch.hayenga@arm.com * contributors may be used to endorse or promote products derived from 2310623Smitch.hayenga@arm.com * this software without specific prior written permission. 2410623Smitch.hayenga@arm.com * 2510623Smitch.hayenga@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2610623Smitch.hayenga@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2710623Smitch.hayenga@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2810623Smitch.hayenga@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2910623Smitch.hayenga@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3010623Smitch.hayenga@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3110623Smitch.hayenga@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3210623Smitch.hayenga@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3310623Smitch.hayenga@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3410623Smitch.hayenga@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3510623Smitch.hayenga@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3610623Smitch.hayenga@arm.com * 3710623Smitch.hayenga@arm.com * Authors: Mitch Hayenga 3810623Smitch.hayenga@arm.com */ 3910623Smitch.hayenga@arm.com 4011793Sbrandon.potter@amd.com#include "mem/cache/prefetch/queued.hh" 4111793Sbrandon.potter@amd.com 4210623Smitch.hayenga@arm.com#include "debug/HWPrefetch.hh" 4310623Smitch.hayenga@arm.com#include "mem/cache/base.hh" 4410623Smitch.hayenga@arm.com 4510623Smitch.hayenga@arm.comQueuedPrefetcher::QueuedPrefetcher(const QueuedPrefetcherParams *p) 4610623Smitch.hayenga@arm.com : BasePrefetcher(p), queueSize(p->queue_size), latency(p->latency), 4710623Smitch.hayenga@arm.com queueSquash(p->queue_squash), queueFilter(p->queue_filter), 4810623Smitch.hayenga@arm.com cacheSnoop(p->cache_snoop), tagPrefetch(p->tag_prefetch) 4910623Smitch.hayenga@arm.com{ 5010623Smitch.hayenga@arm.com 5110623Smitch.hayenga@arm.com} 5210623Smitch.hayenga@arm.com 5310623Smitch.hayenga@arm.comQueuedPrefetcher::~QueuedPrefetcher() 5410623Smitch.hayenga@arm.com{ 5510623Smitch.hayenga@arm.com // Delete the queued prefetch packets 5610623Smitch.hayenga@arm.com for (DeferredPacket &p : pfq) { 5710623Smitch.hayenga@arm.com delete p.pkt->req; 5810623Smitch.hayenga@arm.com delete p.pkt; 5910623Smitch.hayenga@arm.com } 6010623Smitch.hayenga@arm.com} 6110623Smitch.hayenga@arm.com 6210623Smitch.hayenga@arm.comTick 6310623Smitch.hayenga@arm.comQueuedPrefetcher::notify(const PacketPtr &pkt) 6410623Smitch.hayenga@arm.com{ 6510623Smitch.hayenga@arm.com // Verify this access type is observed by prefetcher 6610623Smitch.hayenga@arm.com if (observeAccess(pkt)) { 6711439SRekai.GonzalezAlberquilla@arm.com Addr blk_addr = pkt->getBlockAddr(blkSize); 6810623Smitch.hayenga@arm.com bool is_secure = pkt->isSecure(); 6910623Smitch.hayenga@arm.com 7010623Smitch.hayenga@arm.com // Squash queued prefetches if demand miss to same line 7110623Smitch.hayenga@arm.com if (queueSquash) { 7210623Smitch.hayenga@arm.com auto itr = pfq.begin(); 7310623Smitch.hayenga@arm.com while (itr != pfq.end()) { 7410623Smitch.hayenga@arm.com if (itr->pkt->getAddr() == blk_addr && 7510623Smitch.hayenga@arm.com itr->pkt->isSecure() == is_secure) { 7610623Smitch.hayenga@arm.com delete itr->pkt->req; 7710623Smitch.hayenga@arm.com delete itr->pkt; 7810623Smitch.hayenga@arm.com itr = pfq.erase(itr); 7910623Smitch.hayenga@arm.com } else { 8010623Smitch.hayenga@arm.com ++itr; 8110623Smitch.hayenga@arm.com } 8210623Smitch.hayenga@arm.com } 8310623Smitch.hayenga@arm.com } 8410623Smitch.hayenga@arm.com 8510623Smitch.hayenga@arm.com // Calculate prefetches given this access 8611439SRekai.GonzalezAlberquilla@arm.com std::vector<AddrPriority> addresses; 8710623Smitch.hayenga@arm.com calculatePrefetch(pkt, addresses); 8810623Smitch.hayenga@arm.com 8910623Smitch.hayenga@arm.com // Queue up generated prefetches 9011439SRekai.GonzalezAlberquilla@arm.com for (AddrPriority& pf_info : addresses) { 9110623Smitch.hayenga@arm.com 9210623Smitch.hayenga@arm.com // Block align prefetch address 9311439SRekai.GonzalezAlberquilla@arm.com pf_info.first &= ~(Addr)(blkSize - 1); 9410623Smitch.hayenga@arm.com 9510623Smitch.hayenga@arm.com pfIdentified++; 9610623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Found a pf candidate addr: %#x, " 9711439SRekai.GonzalezAlberquilla@arm.com "inserting into prefetch queue.\n", pf_info.first); 9810623Smitch.hayenga@arm.com 9911439SRekai.GonzalezAlberquilla@arm.com // Create and insert the request 10011439SRekai.GonzalezAlberquilla@arm.com PacketPtr pf_pkt = insert(pf_info, is_secure); 10111439SRekai.GonzalezAlberquilla@arm.com 10211439SRekai.GonzalezAlberquilla@arm.com if (pf_pkt != nullptr) { 10311439SRekai.GonzalezAlberquilla@arm.com if (tagPrefetch && pkt->req->hasPC()) { 10411439SRekai.GonzalezAlberquilla@arm.com // Tag prefetch packet with accessing pc 10511439SRekai.GonzalezAlberquilla@arm.com pf_pkt->req->setPC(pkt->req->getPC()); 10611439SRekai.GonzalezAlberquilla@arm.com } 10710623Smitch.hayenga@arm.com } 10810623Smitch.hayenga@arm.com } 10910623Smitch.hayenga@arm.com } 11010623Smitch.hayenga@arm.com 11110623Smitch.hayenga@arm.com return pfq.empty() ? MaxTick : pfq.front().tick; 11210623Smitch.hayenga@arm.com} 11310623Smitch.hayenga@arm.com 11410623Smitch.hayenga@arm.comPacketPtr 11510623Smitch.hayenga@arm.comQueuedPrefetcher::getPacket() 11610623Smitch.hayenga@arm.com{ 11710623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Requesting a prefetch to issue.\n"); 11810623Smitch.hayenga@arm.com 11910623Smitch.hayenga@arm.com if (pfq.empty()) { 12010623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "No hardware prefetches available.\n"); 12111484Snikos.nikoleris@arm.com return nullptr; 12210623Smitch.hayenga@arm.com } 12310623Smitch.hayenga@arm.com 12410623Smitch.hayenga@arm.com PacketPtr pkt = pfq.begin()->pkt; 12510623Smitch.hayenga@arm.com pfq.pop_front(); 12610623Smitch.hayenga@arm.com 12710623Smitch.hayenga@arm.com pfIssued++; 12811484Snikos.nikoleris@arm.com assert(pkt != nullptr); 12910623Smitch.hayenga@arm.com DPRINTF(HWPrefetch, "Generating prefetch for %#x.\n", pkt->getAddr()); 13010623Smitch.hayenga@arm.com return pkt; 13110623Smitch.hayenga@arm.com} 13210623Smitch.hayenga@arm.com 13311439SRekai.GonzalezAlberquilla@arm.comstd::list<QueuedPrefetcher::DeferredPacket>::const_iterator 13410623Smitch.hayenga@arm.comQueuedPrefetcher::inPrefetch(Addr address, bool is_secure) const 13510623Smitch.hayenga@arm.com{ 13611439SRekai.GonzalezAlberquilla@arm.com for (const_iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 13711439SRekai.GonzalezAlberquilla@arm.com if ((*dp).pkt->getAddr() == address && 13811439SRekai.GonzalezAlberquilla@arm.com (*dp).pkt->isSecure() == is_secure) return dp; 13910623Smitch.hayenga@arm.com } 14010623Smitch.hayenga@arm.com 14111439SRekai.GonzalezAlberquilla@arm.com return pfq.end(); 14211439SRekai.GonzalezAlberquilla@arm.com} 14311439SRekai.GonzalezAlberquilla@arm.com 14411439SRekai.GonzalezAlberquilla@arm.comQueuedPrefetcher::iterator 14511439SRekai.GonzalezAlberquilla@arm.comQueuedPrefetcher::inPrefetch(Addr address, bool is_secure) 14611439SRekai.GonzalezAlberquilla@arm.com{ 14711439SRekai.GonzalezAlberquilla@arm.com for (iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 14811439SRekai.GonzalezAlberquilla@arm.com if (dp->pkt->getAddr() == address && 14911439SRekai.GonzalezAlberquilla@arm.com dp->pkt->isSecure() == is_secure) return dp; 15011439SRekai.GonzalezAlberquilla@arm.com } 15111439SRekai.GonzalezAlberquilla@arm.com 15211439SRekai.GonzalezAlberquilla@arm.com return pfq.end(); 15310623Smitch.hayenga@arm.com} 15410623Smitch.hayenga@arm.com 15510623Smitch.hayenga@arm.comvoid 15610623Smitch.hayenga@arm.comQueuedPrefetcher::regStats() 15710623Smitch.hayenga@arm.com{ 15810623Smitch.hayenga@arm.com BasePrefetcher::regStats(); 15910623Smitch.hayenga@arm.com 16010623Smitch.hayenga@arm.com pfIdentified 16110623Smitch.hayenga@arm.com .name(name() + ".pfIdentified") 16210623Smitch.hayenga@arm.com .desc("number of prefetch candidates identified"); 16310623Smitch.hayenga@arm.com 16410623Smitch.hayenga@arm.com pfBufferHit 16510623Smitch.hayenga@arm.com .name(name() + ".pfBufferHit") 16610623Smitch.hayenga@arm.com .desc("number of redundant prefetches already in prefetch queue"); 16710623Smitch.hayenga@arm.com 16810623Smitch.hayenga@arm.com pfInCache 16910623Smitch.hayenga@arm.com .name(name() + ".pfInCache") 17010623Smitch.hayenga@arm.com .desc("number of redundant prefetches already in cache/mshr dropped"); 17110623Smitch.hayenga@arm.com 17210623Smitch.hayenga@arm.com pfRemovedFull 17310623Smitch.hayenga@arm.com .name(name() + ".pfRemovedFull") 17410623Smitch.hayenga@arm.com .desc("number of prefetches dropped due to prefetch queue size"); 17510623Smitch.hayenga@arm.com 17610623Smitch.hayenga@arm.com pfSpanPage 17710623Smitch.hayenga@arm.com .name(name() + ".pfSpanPage") 17810623Smitch.hayenga@arm.com .desc("number of prefetches not generated due to page crossing"); 17910623Smitch.hayenga@arm.com} 18011439SRekai.GonzalezAlberquilla@arm.com 18111439SRekai.GonzalezAlberquilla@arm.comPacketPtr 18211439SRekai.GonzalezAlberquilla@arm.comQueuedPrefetcher::insert(AddrPriority &pf_info, bool is_secure) 18311439SRekai.GonzalezAlberquilla@arm.com{ 18411439SRekai.GonzalezAlberquilla@arm.com if (queueFilter) { 18511439SRekai.GonzalezAlberquilla@arm.com iterator it = inPrefetch(pf_info.first, is_secure); 18611439SRekai.GonzalezAlberquilla@arm.com /* If the address is already in the queue, update priority and leave */ 18711439SRekai.GonzalezAlberquilla@arm.com if (it != pfq.end()) { 18811439SRekai.GonzalezAlberquilla@arm.com pfBufferHit++; 18911439SRekai.GonzalezAlberquilla@arm.com if (it->priority < pf_info.second) { 19011439SRekai.GonzalezAlberquilla@arm.com /* Update priority value and position in the queue */ 19111439SRekai.GonzalezAlberquilla@arm.com it->priority = pf_info.second; 19211439SRekai.GonzalezAlberquilla@arm.com iterator prev = it; 19311439SRekai.GonzalezAlberquilla@arm.com bool cont = true; 19411439SRekai.GonzalezAlberquilla@arm.com while (cont && prev != pfq.begin()) { 19511439SRekai.GonzalezAlberquilla@arm.com prev--; 19611439SRekai.GonzalezAlberquilla@arm.com /* If the packet has higher priority, swap */ 19711439SRekai.GonzalezAlberquilla@arm.com if (*it > *prev) { 19811439SRekai.GonzalezAlberquilla@arm.com std::swap(*it, *prev); 19911439SRekai.GonzalezAlberquilla@arm.com it = prev; 20011439SRekai.GonzalezAlberquilla@arm.com } 20111439SRekai.GonzalezAlberquilla@arm.com } 20211439SRekai.GonzalezAlberquilla@arm.com DPRINTF(HWPrefetch, "Prefetch addr already in " 20311439SRekai.GonzalezAlberquilla@arm.com "prefetch queue, priority updated\n"); 20411439SRekai.GonzalezAlberquilla@arm.com } else { 20511439SRekai.GonzalezAlberquilla@arm.com DPRINTF(HWPrefetch, "Prefetch addr already in " 20611439SRekai.GonzalezAlberquilla@arm.com "prefetch queue\n"); 20711439SRekai.GonzalezAlberquilla@arm.com } 20811439SRekai.GonzalezAlberquilla@arm.com return nullptr; 20911439SRekai.GonzalezAlberquilla@arm.com } 21011439SRekai.GonzalezAlberquilla@arm.com } 21111439SRekai.GonzalezAlberquilla@arm.com 21211439SRekai.GonzalezAlberquilla@arm.com if (cacheSnoop && (inCache(pf_info.first, is_secure) || 21311439SRekai.GonzalezAlberquilla@arm.com inMissQueue(pf_info.first, is_secure))) { 21411439SRekai.GonzalezAlberquilla@arm.com pfInCache++; 21511439SRekai.GonzalezAlberquilla@arm.com DPRINTF(HWPrefetch, "Dropping redundant in " 21611439SRekai.GonzalezAlberquilla@arm.com "cache/MSHR prefetch addr:%#x\n", pf_info.first); 21711439SRekai.GonzalezAlberquilla@arm.com return nullptr; 21811439SRekai.GonzalezAlberquilla@arm.com } 21911439SRekai.GonzalezAlberquilla@arm.com 22011439SRekai.GonzalezAlberquilla@arm.com /* Create a prefetch memory request */ 22111439SRekai.GonzalezAlberquilla@arm.com Request *pf_req = 22211439SRekai.GonzalezAlberquilla@arm.com new Request(pf_info.first, blkSize, 0, masterId); 22311439SRekai.GonzalezAlberquilla@arm.com 22411439SRekai.GonzalezAlberquilla@arm.com if (is_secure) { 22511439SRekai.GonzalezAlberquilla@arm.com pf_req->setFlags(Request::SECURE); 22611439SRekai.GonzalezAlberquilla@arm.com } 22711439SRekai.GonzalezAlberquilla@arm.com pf_req->taskId(ContextSwitchTaskId::Prefetcher); 22811439SRekai.GonzalezAlberquilla@arm.com PacketPtr pf_pkt = new Packet(pf_req, MemCmd::HardPFReq); 22911439SRekai.GonzalezAlberquilla@arm.com pf_pkt->allocate(); 23011439SRekai.GonzalezAlberquilla@arm.com 23111439SRekai.GonzalezAlberquilla@arm.com /* Verify prefetch buffer space for request */ 23211439SRekai.GonzalezAlberquilla@arm.com if (pfq.size() == queueSize) { 23311439SRekai.GonzalezAlberquilla@arm.com pfRemovedFull++; 23411439SRekai.GonzalezAlberquilla@arm.com /* Lowest priority packet */ 23511439SRekai.GonzalezAlberquilla@arm.com iterator it = pfq.end(); 23611439SRekai.GonzalezAlberquilla@arm.com panic_if (it == pfq.begin(), "Prefetch queue is both full and empty!"); 23711439SRekai.GonzalezAlberquilla@arm.com --it; 23811439SRekai.GonzalezAlberquilla@arm.com /* Look for oldest in that level of priority */ 23911439SRekai.GonzalezAlberquilla@arm.com panic_if (it == pfq.begin(), "Prefetch queue is full with 1 element!"); 24011439SRekai.GonzalezAlberquilla@arm.com iterator prev = it; 24111439SRekai.GonzalezAlberquilla@arm.com bool cont = true; 24211439SRekai.GonzalezAlberquilla@arm.com /* While not at the head of the queue */ 24311439SRekai.GonzalezAlberquilla@arm.com while (cont && prev != pfq.begin()) { 24411439SRekai.GonzalezAlberquilla@arm.com prev--; 24511439SRekai.GonzalezAlberquilla@arm.com /* While at the same level of priority */ 24611439SRekai.GonzalezAlberquilla@arm.com cont = (*prev).priority == (*it).priority; 24711439SRekai.GonzalezAlberquilla@arm.com if (cont) 24811439SRekai.GonzalezAlberquilla@arm.com /* update pointer */ 24911439SRekai.GonzalezAlberquilla@arm.com it = prev; 25011439SRekai.GonzalezAlberquilla@arm.com } 25111439SRekai.GonzalezAlberquilla@arm.com DPRINTF(HWPrefetch, "Prefetch queue full, removing lowest priority " 25211439SRekai.GonzalezAlberquilla@arm.com "oldest packet, addr: %#x", it->pkt->getAddr()); 25311439SRekai.GonzalezAlberquilla@arm.com delete it->pkt->req; 25411439SRekai.GonzalezAlberquilla@arm.com delete it->pkt; 25511439SRekai.GonzalezAlberquilla@arm.com pfq.erase(it); 25611439SRekai.GonzalezAlberquilla@arm.com } 25711439SRekai.GonzalezAlberquilla@arm.com 25811439SRekai.GonzalezAlberquilla@arm.com Tick pf_time = curTick() + clockPeriod() * latency; 25911439SRekai.GonzalezAlberquilla@arm.com DPRINTF(HWPrefetch, "Prefetch queued. " 26011439SRekai.GonzalezAlberquilla@arm.com "addr:%#x priority: %3d tick:%lld.\n", 26111439SRekai.GonzalezAlberquilla@arm.com pf_info.first, pf_info.second, pf_time); 26211439SRekai.GonzalezAlberquilla@arm.com 26311439SRekai.GonzalezAlberquilla@arm.com /* Create the packet and find the spot to insert it */ 26411439SRekai.GonzalezAlberquilla@arm.com DeferredPacket dpp(pf_time, pf_pkt, pf_info.second); 26511439SRekai.GonzalezAlberquilla@arm.com if (pfq.size() == 0) { 26611439SRekai.GonzalezAlberquilla@arm.com pfq.emplace_back(dpp); 26711439SRekai.GonzalezAlberquilla@arm.com } else { 26811439SRekai.GonzalezAlberquilla@arm.com iterator it = pfq.end(); 26911439SRekai.GonzalezAlberquilla@arm.com while (it != pfq.begin() && dpp > *it) 27011439SRekai.GonzalezAlberquilla@arm.com --it; 27111439SRekai.GonzalezAlberquilla@arm.com /* If we reach the head, we have to see if the new element is new head 27211439SRekai.GonzalezAlberquilla@arm.com * or not */ 27311439SRekai.GonzalezAlberquilla@arm.com if (it == pfq.begin() && dpp <= *it) 27411439SRekai.GonzalezAlberquilla@arm.com it++; 27511439SRekai.GonzalezAlberquilla@arm.com pfq.insert(it, dpp); 27611439SRekai.GonzalezAlberquilla@arm.com } 27711439SRekai.GonzalezAlberquilla@arm.com 27811439SRekai.GonzalezAlberquilla@arm.com return pf_pkt; 27911439SRekai.GonzalezAlberquilla@arm.com} 280