113957Sjairo.balart@metempsy.com/* 213957Sjairo.balart@metempsy.com * Copyright (c) 2014 ARM Limited 313957Sjairo.balart@metempsy.com * All rights reserved. 413957Sjairo.balart@metempsy.com * 513957Sjairo.balart@metempsy.com * Redistribution and use in source and binary forms, with or without 613957Sjairo.balart@metempsy.com * modification, are permitted provided that the following conditions are 713957Sjairo.balart@metempsy.com * met: redistributions of source code must retain the above copyright 813957Sjairo.balart@metempsy.com * notice, this list of conditions and the following disclaimer; 913957Sjairo.balart@metempsy.com * redistributions in binary form must reproduce the above copyright 1013957Sjairo.balart@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113957Sjairo.balart@metempsy.com * documentation and/or other materials provided with the distribution; 1213957Sjairo.balart@metempsy.com * neither the name of the copyright holders nor the names of its 1313957Sjairo.balart@metempsy.com * contributors may be used to endorse or promote products derived from 1413957Sjairo.balart@metempsy.com * this software without specific prior written permission. 1513957Sjairo.balart@metempsy.com * 1613957Sjairo.balart@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713957Sjairo.balart@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813957Sjairo.balart@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913957Sjairo.balart@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013957Sjairo.balart@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113957Sjairo.balart@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213957Sjairo.balart@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313957Sjairo.balart@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413957Sjairo.balart@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513957Sjairo.balart@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613957Sjairo.balart@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713957Sjairo.balart@metempsy.com * 2813957Sjairo.balart@metempsy.com * Authors: Mitch Hayenga 2913957Sjairo.balart@metempsy.com */ 3013957Sjairo.balart@metempsy.com 3113957Sjairo.balart@metempsy.com#include "cpu/pred/simple_indirect.hh" 3213957Sjairo.balart@metempsy.com 3313957Sjairo.balart@metempsy.com#include "base/intmath.hh" 3413957Sjairo.balart@metempsy.com#include "debug/Indirect.hh" 3513957Sjairo.balart@metempsy.com 3613957Sjairo.balart@metempsy.comSimpleIndirectPredictor::SimpleIndirectPredictor( 3713957Sjairo.balart@metempsy.com const SimpleIndirectPredictorParams * params) 3813957Sjairo.balart@metempsy.com : IndirectPredictor(params), 3913957Sjairo.balart@metempsy.com hashGHR(params->indirectHashGHR), 4013957Sjairo.balart@metempsy.com hashTargets(params->indirectHashTargets), 4113957Sjairo.balart@metempsy.com numSets(params->indirectSets), 4213957Sjairo.balart@metempsy.com numWays(params->indirectWays), 4313957Sjairo.balart@metempsy.com tagBits(params->indirectTagSize), 4413957Sjairo.balart@metempsy.com pathLength(params->indirectPathLength), 4513957Sjairo.balart@metempsy.com instShift(params->instShiftAmt), 4613957Sjairo.balart@metempsy.com ghrNumBits(params->indirectGHRBits), 4713957Sjairo.balart@metempsy.com ghrMask((1 << params->indirectGHRBits)-1) 4813957Sjairo.balart@metempsy.com{ 4913957Sjairo.balart@metempsy.com if (!isPowerOf2(numSets)) { 5013957Sjairo.balart@metempsy.com panic("Indirect predictor requires power of 2 number of sets"); 5113957Sjairo.balart@metempsy.com } 5213957Sjairo.balart@metempsy.com 5313957Sjairo.balart@metempsy.com threadInfo.resize(params->numThreads); 5413957Sjairo.balart@metempsy.com 5513957Sjairo.balart@metempsy.com targetCache.resize(numSets); 5613957Sjairo.balart@metempsy.com for (unsigned i = 0; i < numSets; i++) { 5713957Sjairo.balart@metempsy.com targetCache[i].resize(numWays); 5813957Sjairo.balart@metempsy.com } 5913957Sjairo.balart@metempsy.com 6013957Sjairo.balart@metempsy.com fatal_if(ghrNumBits > (sizeof(ThreadInfo::ghr)*8), "ghr_size is too big"); 6113957Sjairo.balart@metempsy.com} 6213957Sjairo.balart@metempsy.com 6313957Sjairo.balart@metempsy.comvoid 6413957Sjairo.balart@metempsy.comSimpleIndirectPredictor::genIndirectInfo(ThreadID tid, 6513957Sjairo.balart@metempsy.com void* & indirect_history) 6613957Sjairo.balart@metempsy.com{ 6713957Sjairo.balart@metempsy.com // record the GHR as it was before this prediction 6813957Sjairo.balart@metempsy.com // It will be used to recover the history in case this prediction is 6913957Sjairo.balart@metempsy.com // wrong or belongs to bad path 7013957Sjairo.balart@metempsy.com indirect_history = new unsigned(threadInfo[tid].ghr); 7113957Sjairo.balart@metempsy.com} 7213957Sjairo.balart@metempsy.com 7313957Sjairo.balart@metempsy.comvoid 7413957Sjairo.balart@metempsy.comSimpleIndirectPredictor::updateDirectionInfo( 7513957Sjairo.balart@metempsy.com ThreadID tid, bool actually_taken) 7613957Sjairo.balart@metempsy.com{ 7713957Sjairo.balart@metempsy.com threadInfo[tid].ghr <<= 1; 7813957Sjairo.balart@metempsy.com threadInfo[tid].ghr |= actually_taken; 7913957Sjairo.balart@metempsy.com threadInfo[tid].ghr &= ghrMask; 8013957Sjairo.balart@metempsy.com} 8113957Sjairo.balart@metempsy.com 8213957Sjairo.balart@metempsy.comvoid 8313957Sjairo.balart@metempsy.comSimpleIndirectPredictor::changeDirectionPrediction(ThreadID tid, 8413957Sjairo.balart@metempsy.com void * indirect_history, bool actually_taken) 8513957Sjairo.balart@metempsy.com{ 8613957Sjairo.balart@metempsy.com unsigned * previousGhr = static_cast<unsigned *>(indirect_history); 8713957Sjairo.balart@metempsy.com threadInfo[tid].ghr = ((*previousGhr) << 1) + actually_taken; 8813957Sjairo.balart@metempsy.com threadInfo[tid].ghr &= ghrMask; 8913957Sjairo.balart@metempsy.com} 9013957Sjairo.balart@metempsy.com 9113957Sjairo.balart@metempsy.combool 9213957Sjairo.balart@metempsy.comSimpleIndirectPredictor::lookup(Addr br_addr, TheISA::PCState& target, 9313957Sjairo.balart@metempsy.com ThreadID tid) 9413957Sjairo.balart@metempsy.com{ 9513957Sjairo.balart@metempsy.com Addr set_index = getSetIndex(br_addr, threadInfo[tid].ghr, tid); 9613957Sjairo.balart@metempsy.com Addr tag = getTag(br_addr); 9713957Sjairo.balart@metempsy.com 9813957Sjairo.balart@metempsy.com assert(set_index < numSets); 9913957Sjairo.balart@metempsy.com 10013957Sjairo.balart@metempsy.com DPRINTF(Indirect, "Looking up %x (set:%d)\n", br_addr, set_index); 10113957Sjairo.balart@metempsy.com const auto &iset = targetCache[set_index]; 10213957Sjairo.balart@metempsy.com for (auto way = iset.begin(); way != iset.end(); ++way) { 10313957Sjairo.balart@metempsy.com if (way->tag == tag) { 10413957Sjairo.balart@metempsy.com DPRINTF(Indirect, "Hit %x (target:%s)\n", br_addr, way->target); 10513957Sjairo.balart@metempsy.com target = way->target; 10613957Sjairo.balart@metempsy.com return true; 10713957Sjairo.balart@metempsy.com } 10813957Sjairo.balart@metempsy.com } 10913957Sjairo.balart@metempsy.com DPRINTF(Indirect, "Miss %x\n", br_addr); 11013957Sjairo.balart@metempsy.com return false; 11113957Sjairo.balart@metempsy.com} 11213957Sjairo.balart@metempsy.com 11313957Sjairo.balart@metempsy.comvoid 11413957Sjairo.balart@metempsy.comSimpleIndirectPredictor::recordIndirect(Addr br_addr, Addr tgt_addr, 11513957Sjairo.balart@metempsy.com InstSeqNum seq_num, ThreadID tid) 11613957Sjairo.balart@metempsy.com{ 11713957Sjairo.balart@metempsy.com DPRINTF(Indirect, "Recording %x seq:%d\n", br_addr, seq_num); 11813957Sjairo.balart@metempsy.com HistoryEntry entry(br_addr, tgt_addr, seq_num); 11913957Sjairo.balart@metempsy.com threadInfo[tid].pathHist.push_back(entry); 12013957Sjairo.balart@metempsy.com} 12113957Sjairo.balart@metempsy.com 12213957Sjairo.balart@metempsy.comvoid 12313957Sjairo.balart@metempsy.comSimpleIndirectPredictor::commit(InstSeqNum seq_num, ThreadID tid, 12413957Sjairo.balart@metempsy.com void * indirect_history) 12513957Sjairo.balart@metempsy.com{ 12613957Sjairo.balart@metempsy.com DPRINTF(Indirect, "Committing seq:%d\n", seq_num); 12713957Sjairo.balart@metempsy.com ThreadInfo &t_info = threadInfo[tid]; 12813957Sjairo.balart@metempsy.com 12913957Sjairo.balart@metempsy.com // we do not need to recover the GHR, so delete the information 13013957Sjairo.balart@metempsy.com unsigned * previousGhr = static_cast<unsigned *>(indirect_history); 13113957Sjairo.balart@metempsy.com delete previousGhr; 13213957Sjairo.balart@metempsy.com 13313957Sjairo.balart@metempsy.com if (t_info.pathHist.empty()) return; 13413957Sjairo.balart@metempsy.com 13513957Sjairo.balart@metempsy.com if (t_info.headHistEntry < t_info.pathHist.size() && 13613957Sjairo.balart@metempsy.com t_info.pathHist[t_info.headHistEntry].seqNum <= seq_num) { 13713957Sjairo.balart@metempsy.com if (t_info.headHistEntry >= pathLength) { 13813957Sjairo.balart@metempsy.com t_info.pathHist.pop_front(); 13913957Sjairo.balart@metempsy.com } else { 14013957Sjairo.balart@metempsy.com ++t_info.headHistEntry; 14113957Sjairo.balart@metempsy.com } 14213957Sjairo.balart@metempsy.com } 14313957Sjairo.balart@metempsy.com} 14413957Sjairo.balart@metempsy.com 14513957Sjairo.balart@metempsy.comvoid 14613957Sjairo.balart@metempsy.comSimpleIndirectPredictor::squash(InstSeqNum seq_num, ThreadID tid) 14713957Sjairo.balart@metempsy.com{ 14813957Sjairo.balart@metempsy.com DPRINTF(Indirect, "Squashing seq:%d\n", seq_num); 14913957Sjairo.balart@metempsy.com ThreadInfo &t_info = threadInfo[tid]; 15013957Sjairo.balart@metempsy.com auto squash_itr = t_info.pathHist.begin(); 15113957Sjairo.balart@metempsy.com while (squash_itr != t_info.pathHist.end()) { 15213957Sjairo.balart@metempsy.com if (squash_itr->seqNum > seq_num) { 15313957Sjairo.balart@metempsy.com break; 15413957Sjairo.balart@metempsy.com } 15513957Sjairo.balart@metempsy.com ++squash_itr; 15613957Sjairo.balart@metempsy.com } 15713957Sjairo.balart@metempsy.com if (squash_itr != t_info.pathHist.end()) { 15813957Sjairo.balart@metempsy.com DPRINTF(Indirect, "Squashing series starting with sn:%d\n", 15913957Sjairo.balart@metempsy.com squash_itr->seqNum); 16013957Sjairo.balart@metempsy.com } 16113957Sjairo.balart@metempsy.com t_info.pathHist.erase(squash_itr, t_info.pathHist.end()); 16213957Sjairo.balart@metempsy.com} 16313957Sjairo.balart@metempsy.com 16413957Sjairo.balart@metempsy.comvoid 16513957Sjairo.balart@metempsy.comSimpleIndirectPredictor::deleteIndirectInfo(ThreadID tid, 16613957Sjairo.balart@metempsy.com void * indirect_history) 16713957Sjairo.balart@metempsy.com{ 16813957Sjairo.balart@metempsy.com unsigned * previousGhr = static_cast<unsigned *>(indirect_history); 16913957Sjairo.balart@metempsy.com threadInfo[tid].ghr = *previousGhr; 17013957Sjairo.balart@metempsy.com 17113957Sjairo.balart@metempsy.com delete previousGhr; 17213957Sjairo.balart@metempsy.com} 17313957Sjairo.balart@metempsy.com 17413957Sjairo.balart@metempsy.comvoid 17513957Sjairo.balart@metempsy.comSimpleIndirectPredictor::recordTarget( 17613957Sjairo.balart@metempsy.com InstSeqNum seq_num, void * indirect_history, const TheISA::PCState& target, 17713957Sjairo.balart@metempsy.com ThreadID tid) 17813957Sjairo.balart@metempsy.com{ 17913957Sjairo.balart@metempsy.com ThreadInfo &t_info = threadInfo[tid]; 18013957Sjairo.balart@metempsy.com 18113957Sjairo.balart@metempsy.com unsigned * ghr = static_cast<unsigned *>(indirect_history); 18213957Sjairo.balart@metempsy.com 18313957Sjairo.balart@metempsy.com // Should have just squashed so this branch should be the oldest 18413957Sjairo.balart@metempsy.com auto hist_entry = *(t_info.pathHist.rbegin()); 18513957Sjairo.balart@metempsy.com // Temporarily pop it off the history so we can calculate the set 18613957Sjairo.balart@metempsy.com t_info.pathHist.pop_back(); 18713957Sjairo.balart@metempsy.com Addr set_index = getSetIndex(hist_entry.pcAddr, *ghr, tid); 18813957Sjairo.balart@metempsy.com Addr tag = getTag(hist_entry.pcAddr); 18913957Sjairo.balart@metempsy.com hist_entry.targetAddr = target.instAddr(); 19013957Sjairo.balart@metempsy.com t_info.pathHist.push_back(hist_entry); 19113957Sjairo.balart@metempsy.com 19213957Sjairo.balart@metempsy.com assert(set_index < numSets); 19313957Sjairo.balart@metempsy.com 19413957Sjairo.balart@metempsy.com auto &iset = targetCache[set_index]; 19513957Sjairo.balart@metempsy.com for (auto way = iset.begin(); way != iset.end(); ++way) { 19613957Sjairo.balart@metempsy.com if (way->tag == tag) { 19713957Sjairo.balart@metempsy.com DPRINTF(Indirect, "Updating Target (seq: %d br:%x set:%d target:" 19813957Sjairo.balart@metempsy.com "%s)\n", seq_num, hist_entry.pcAddr, set_index, target); 19913957Sjairo.balart@metempsy.com way->target = target; 20013957Sjairo.balart@metempsy.com return; 20113957Sjairo.balart@metempsy.com } 20213957Sjairo.balart@metempsy.com } 20313957Sjairo.balart@metempsy.com 20413957Sjairo.balart@metempsy.com DPRINTF(Indirect, "Allocating Target (seq: %d br:%x set:%d target:%s)\n", 20513957Sjairo.balart@metempsy.com seq_num, hist_entry.pcAddr, set_index, target); 20613957Sjairo.balart@metempsy.com // Did not find entry, random replacement 20713957Sjairo.balart@metempsy.com auto &way = iset[rand() % numWays]; 20813957Sjairo.balart@metempsy.com way.tag = tag; 20913957Sjairo.balart@metempsy.com way.target = target; 21013957Sjairo.balart@metempsy.com} 21113957Sjairo.balart@metempsy.com 21213957Sjairo.balart@metempsy.com 21313957Sjairo.balart@metempsy.cominline Addr 21413957Sjairo.balart@metempsy.comSimpleIndirectPredictor::getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid) 21513957Sjairo.balart@metempsy.com{ 21613957Sjairo.balart@metempsy.com ThreadInfo &t_info = threadInfo[tid]; 21713957Sjairo.balart@metempsy.com 21813957Sjairo.balart@metempsy.com Addr hash = br_addr >> instShift; 21913957Sjairo.balart@metempsy.com if (hashGHR) { 22013957Sjairo.balart@metempsy.com hash ^= ghr; 22113957Sjairo.balart@metempsy.com } 22213957Sjairo.balart@metempsy.com if (hashTargets) { 22313957Sjairo.balart@metempsy.com unsigned hash_shift = floorLog2(numSets) / pathLength; 22413957Sjairo.balart@metempsy.com for (int i = t_info.pathHist.size()-1, p = 0; 22513957Sjairo.balart@metempsy.com i >= 0 && p < pathLength; i--, p++) { 22613957Sjairo.balart@metempsy.com hash ^= (t_info.pathHist[i].targetAddr >> 22713957Sjairo.balart@metempsy.com (instShift + p*hash_shift)); 22813957Sjairo.balart@metempsy.com } 22913957Sjairo.balart@metempsy.com } 23013957Sjairo.balart@metempsy.com return hash & (numSets-1); 23113957Sjairo.balart@metempsy.com} 23213957Sjairo.balart@metempsy.com 23313957Sjairo.balart@metempsy.cominline Addr 23413957Sjairo.balart@metempsy.comSimpleIndirectPredictor::getTag(Addr br_addr) 23513957Sjairo.balart@metempsy.com{ 23613957Sjairo.balart@metempsy.com return (br_addr >> instShift) & ((0x1<<tagBits)-1); 23713957Sjairo.balart@metempsy.com} 23813957Sjairo.balart@metempsy.com 23913957Sjairo.balart@metempsy.comSimpleIndirectPredictor * 24013957Sjairo.balart@metempsy.comSimpleIndirectPredictorParams::create() 24113957Sjairo.balart@metempsy.com{ 24213957Sjairo.balart@metempsy.com return new SimpleIndirectPredictor(this); 24313957Sjairo.balart@metempsy.com} 244