indirect.cc revision 11426
111426Smitch.hayenga@arm.com/* 211426Smitch.hayenga@arm.com * Copyright (c) 2014 ARM Limited 311426Smitch.hayenga@arm.com * All rights reserved. 411426Smitch.hayenga@arm.com * 511426Smitch.hayenga@arm.com * Redistribution and use in source and binary forms, with or without 611426Smitch.hayenga@arm.com * modification, are permitted provided that the following conditions are 711426Smitch.hayenga@arm.com * met: redistributions of source code must retain the above copyright 811426Smitch.hayenga@arm.com * notice, this list of conditions and the following disclaimer; 911426Smitch.hayenga@arm.com * redistributions in binary form must reproduce the above copyright 1011426Smitch.hayenga@arm.com * notice, this list of conditions and the following disclaimer in the 1111426Smitch.hayenga@arm.com * documentation and/or other materials provided with the distribution; 1211426Smitch.hayenga@arm.com * neither the name of the copyright holders nor the names of its 1311426Smitch.hayenga@arm.com * contributors may be used to endorse or promote products derived from 1411426Smitch.hayenga@arm.com * this software without specific prior written permission. 1511426Smitch.hayenga@arm.com * 1611426Smitch.hayenga@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1711426Smitch.hayenga@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1811426Smitch.hayenga@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1911426Smitch.hayenga@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2011426Smitch.hayenga@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2111426Smitch.hayenga@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2211426Smitch.hayenga@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2311426Smitch.hayenga@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2411426Smitch.hayenga@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2511426Smitch.hayenga@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2611426Smitch.hayenga@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2711426Smitch.hayenga@arm.com * 2811426Smitch.hayenga@arm.com * Authors: Mitch Hayenga 2911426Smitch.hayenga@arm.com */ 3011426Smitch.hayenga@arm.com 3111426Smitch.hayenga@arm.com#include "cpu/pred/indirect.hh" 3211426Smitch.hayenga@arm.com 3311426Smitch.hayenga@arm.com#include "base/intmath.hh" 3411426Smitch.hayenga@arm.com#include "debug/Indirect.hh" 3511426Smitch.hayenga@arm.com 3611426Smitch.hayenga@arm.comIndirectPredictor::IndirectPredictor(bool hash_ghr, bool hash_targets, 3711426Smitch.hayenga@arm.com unsigned num_sets, unsigned num_ways, 3811426Smitch.hayenga@arm.com unsigned tag_bits, unsigned path_len, unsigned inst_shift, 3911426Smitch.hayenga@arm.com unsigned num_threads) 4011426Smitch.hayenga@arm.com : hashGHR(hash_ghr), hashTargets(hash_targets), 4111426Smitch.hayenga@arm.com numSets(num_sets), numWays(num_ways), tagBits(tag_bits), 4211426Smitch.hayenga@arm.com pathLength(path_len), instShift(inst_shift) 4311426Smitch.hayenga@arm.com{ 4411426Smitch.hayenga@arm.com if (!isPowerOf2(numSets)) { 4511426Smitch.hayenga@arm.com panic("Indirect predictor requires power of 2 number of sets"); 4611426Smitch.hayenga@arm.com } 4711426Smitch.hayenga@arm.com 4811426Smitch.hayenga@arm.com threadInfo.resize(num_threads); 4911426Smitch.hayenga@arm.com 5011426Smitch.hayenga@arm.com targetCache.resize(numSets); 5111426Smitch.hayenga@arm.com for (unsigned i = 0; i < numSets; i++) { 5211426Smitch.hayenga@arm.com targetCache[i].resize(numWays); 5311426Smitch.hayenga@arm.com } 5411426Smitch.hayenga@arm.com} 5511426Smitch.hayenga@arm.com 5611426Smitch.hayenga@arm.combool 5711426Smitch.hayenga@arm.comIndirectPredictor::lookup(Addr br_addr, unsigned ghr, TheISA::PCState& target, 5811426Smitch.hayenga@arm.com ThreadID tid) 5911426Smitch.hayenga@arm.com{ 6011426Smitch.hayenga@arm.com Addr set_index = getSetIndex(br_addr, ghr, tid); 6111426Smitch.hayenga@arm.com Addr tag = getTag(br_addr); 6211426Smitch.hayenga@arm.com 6311426Smitch.hayenga@arm.com assert(set_index < numSets); 6411426Smitch.hayenga@arm.com 6511426Smitch.hayenga@arm.com DPRINTF(Indirect, "Looking up %x (set:%d)\n", br_addr, set_index); 6611426Smitch.hayenga@arm.com const auto &iset = targetCache[set_index]; 6711426Smitch.hayenga@arm.com for (auto way = iset.begin(); way != iset.end(); ++way) { 6811426Smitch.hayenga@arm.com if (way->tag == tag) { 6911426Smitch.hayenga@arm.com DPRINTF(Indirect, "Hit %x (target:%s)\n", br_addr, way->target); 7011426Smitch.hayenga@arm.com target = way->target; 7111426Smitch.hayenga@arm.com return true; 7211426Smitch.hayenga@arm.com } 7311426Smitch.hayenga@arm.com } 7411426Smitch.hayenga@arm.com DPRINTF(Indirect, "Miss %x\n", br_addr); 7511426Smitch.hayenga@arm.com return false; 7611426Smitch.hayenga@arm.com} 7711426Smitch.hayenga@arm.com 7811426Smitch.hayenga@arm.comvoid 7911426Smitch.hayenga@arm.comIndirectPredictor::recordIndirect(Addr br_addr, Addr tgt_addr, 8011426Smitch.hayenga@arm.com InstSeqNum seq_num, ThreadID tid) 8111426Smitch.hayenga@arm.com{ 8211426Smitch.hayenga@arm.com DPRINTF(Indirect, "Recording %x seq:%d\n", br_addr, seq_num); 8311426Smitch.hayenga@arm.com HistoryEntry entry(br_addr, tgt_addr, seq_num); 8411426Smitch.hayenga@arm.com threadInfo[tid].pathHist.push_back(entry); 8511426Smitch.hayenga@arm.com} 8611426Smitch.hayenga@arm.com 8711426Smitch.hayenga@arm.comvoid 8811426Smitch.hayenga@arm.comIndirectPredictor::commit(InstSeqNum seq_num, ThreadID tid) 8911426Smitch.hayenga@arm.com{ 9011426Smitch.hayenga@arm.com DPRINTF(Indirect, "Committing seq:%d\n", seq_num); 9111426Smitch.hayenga@arm.com ThreadInfo &t_info = threadInfo[tid]; 9211426Smitch.hayenga@arm.com 9311426Smitch.hayenga@arm.com if (t_info.pathHist.empty()) return; 9411426Smitch.hayenga@arm.com 9511426Smitch.hayenga@arm.com if (t_info.headHistEntry < t_info.pathHist.size() && 9611426Smitch.hayenga@arm.com t_info.pathHist[t_info.headHistEntry].seqNum <= seq_num) { 9711426Smitch.hayenga@arm.com if (t_info.headHistEntry >= pathLength) { 9811426Smitch.hayenga@arm.com t_info.pathHist.pop_front(); 9911426Smitch.hayenga@arm.com } else { 10011426Smitch.hayenga@arm.com ++t_info.headHistEntry; 10111426Smitch.hayenga@arm.com } 10211426Smitch.hayenga@arm.com } 10311426Smitch.hayenga@arm.com} 10411426Smitch.hayenga@arm.com 10511426Smitch.hayenga@arm.comvoid 10611426Smitch.hayenga@arm.comIndirectPredictor::squash(InstSeqNum seq_num, ThreadID tid) 10711426Smitch.hayenga@arm.com{ 10811426Smitch.hayenga@arm.com DPRINTF(Indirect, "Squashing seq:%d\n", seq_num); 10911426Smitch.hayenga@arm.com ThreadInfo &t_info = threadInfo[tid]; 11011426Smitch.hayenga@arm.com auto squash_itr = t_info.pathHist.begin(); 11111426Smitch.hayenga@arm.com while (squash_itr != t_info.pathHist.end()) { 11211426Smitch.hayenga@arm.com if (squash_itr->seqNum > seq_num) { 11311426Smitch.hayenga@arm.com break; 11411426Smitch.hayenga@arm.com } 11511426Smitch.hayenga@arm.com ++squash_itr; 11611426Smitch.hayenga@arm.com } 11711426Smitch.hayenga@arm.com if (squash_itr != t_info.pathHist.end()) { 11811426Smitch.hayenga@arm.com DPRINTF(Indirect, "Squashing series starting with sn:%d\n", 11911426Smitch.hayenga@arm.com squash_itr->seqNum); 12011426Smitch.hayenga@arm.com } 12111426Smitch.hayenga@arm.com t_info.pathHist.erase(squash_itr, t_info.pathHist.end()); 12211426Smitch.hayenga@arm.com} 12311426Smitch.hayenga@arm.com 12411426Smitch.hayenga@arm.com 12511426Smitch.hayenga@arm.comvoid 12611426Smitch.hayenga@arm.comIndirectPredictor::recordTarget(InstSeqNum seq_num, unsigned ghr, 12711426Smitch.hayenga@arm.com const TheISA::PCState& target, ThreadID tid) 12811426Smitch.hayenga@arm.com{ 12911426Smitch.hayenga@arm.com ThreadInfo &t_info = threadInfo[tid]; 13011426Smitch.hayenga@arm.com 13111426Smitch.hayenga@arm.com // Should have just squashed so this branch should be the oldest 13211426Smitch.hayenga@arm.com auto hist_entry = *(t_info.pathHist.rbegin()); 13311426Smitch.hayenga@arm.com // Temporarily pop it off the history so we can calculate the set 13411426Smitch.hayenga@arm.com t_info.pathHist.pop_back(); 13511426Smitch.hayenga@arm.com Addr set_index = getSetIndex(hist_entry.pcAddr, ghr, tid); 13611426Smitch.hayenga@arm.com Addr tag = getTag(hist_entry.pcAddr); 13711426Smitch.hayenga@arm.com hist_entry.targetAddr = target.instAddr(); 13811426Smitch.hayenga@arm.com t_info.pathHist.push_back(hist_entry); 13911426Smitch.hayenga@arm.com 14011426Smitch.hayenga@arm.com assert(set_index < numSets); 14111426Smitch.hayenga@arm.com 14211426Smitch.hayenga@arm.com auto &iset = targetCache[set_index]; 14311426Smitch.hayenga@arm.com for (auto way = iset.begin(); way != iset.end(); ++way) { 14411426Smitch.hayenga@arm.com if (way->tag == tag) { 14511426Smitch.hayenga@arm.com DPRINTF(Indirect, "Updating Target (seq: %d br:%x set:%d target:" 14611426Smitch.hayenga@arm.com "%s)\n", seq_num, hist_entry.pcAddr, set_index, target); 14711426Smitch.hayenga@arm.com way->target = target; 14811426Smitch.hayenga@arm.com return; 14911426Smitch.hayenga@arm.com } 15011426Smitch.hayenga@arm.com } 15111426Smitch.hayenga@arm.com 15211426Smitch.hayenga@arm.com DPRINTF(Indirect, "Allocating Target (seq: %d br:%x set:%d target:%s)\n", 15311426Smitch.hayenga@arm.com seq_num, hist_entry.pcAddr, set_index, target); 15411426Smitch.hayenga@arm.com // Did not find entry, random replacement 15511426Smitch.hayenga@arm.com auto &way = iset[rand() % numWays]; 15611426Smitch.hayenga@arm.com way.tag = tag; 15711426Smitch.hayenga@arm.com way.target = target; 15811426Smitch.hayenga@arm.com} 15911426Smitch.hayenga@arm.com 16011426Smitch.hayenga@arm.com 16111426Smitch.hayenga@arm.cominline Addr 16211426Smitch.hayenga@arm.comIndirectPredictor::getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid) 16311426Smitch.hayenga@arm.com{ 16411426Smitch.hayenga@arm.com ThreadInfo &t_info = threadInfo[tid]; 16511426Smitch.hayenga@arm.com 16611426Smitch.hayenga@arm.com Addr hash = br_addr >> instShift; 16711426Smitch.hayenga@arm.com if (hashGHR) { 16811426Smitch.hayenga@arm.com hash ^= ghr; 16911426Smitch.hayenga@arm.com } 17011426Smitch.hayenga@arm.com if (hashTargets) { 17111426Smitch.hayenga@arm.com unsigned hash_shift = floorLog2(numSets) / pathLength; 17211426Smitch.hayenga@arm.com for (int i = t_info.pathHist.size()-1, p = 0; 17311426Smitch.hayenga@arm.com i >= 0 && p < pathLength; i--, p++) { 17411426Smitch.hayenga@arm.com hash ^= (t_info.pathHist[i].targetAddr >> 17511426Smitch.hayenga@arm.com (instShift + p*hash_shift)); 17611426Smitch.hayenga@arm.com } 17711426Smitch.hayenga@arm.com } 17811426Smitch.hayenga@arm.com return hash & (numSets-1); 17911426Smitch.hayenga@arm.com} 18011426Smitch.hayenga@arm.com 18111426Smitch.hayenga@arm.cominline Addr 18211426Smitch.hayenga@arm.comIndirectPredictor::getTag(Addr br_addr) 18311426Smitch.hayenga@arm.com{ 18411426Smitch.hayenga@arm.com return (br_addr >> instShift) & ((0x1<<tagBits)-1); 18511426Smitch.hayenga@arm.com} 186