16184SN/A/* 210330Smitch.hayenga@arm.com * Copyright (c) 2011, 2014 ARM Limited 38842Smrinmoy.ghosh@arm.com * All rights reserved 48842Smrinmoy.ghosh@arm.com * 58842Smrinmoy.ghosh@arm.com * The license below extends only to copyright in the software and shall 68842Smrinmoy.ghosh@arm.com * not be construed as granting a license to any other intellectual 78842Smrinmoy.ghosh@arm.com * property including but not limited to intellectual property relating 88842Smrinmoy.ghosh@arm.com * to a hardware implementation of the functionality of the software 98842Smrinmoy.ghosh@arm.com * licensed hereunder. You may use the software subject to the license 108842Smrinmoy.ghosh@arm.com * terms below provided that you ensure that this notice is replicated 118842Smrinmoy.ghosh@arm.com * unmodified and in its entirety in all distributions of the software, 128842Smrinmoy.ghosh@arm.com * modified or unmodified, in source code or in binary form. 138842Smrinmoy.ghosh@arm.com * 146184SN/A * Copyright (c) 2004-2006 The Regents of The University of Michigan 156184SN/A * All rights reserved. 166184SN/A * 176184SN/A * Redistribution and use in source and binary forms, with or without 186184SN/A * modification, are permitted provided that the following conditions are 196184SN/A * met: redistributions of source code must retain the above copyright 206184SN/A * notice, this list of conditions and the following disclaimer; 216184SN/A * redistributions in binary form must reproduce the above copyright 226184SN/A * notice, this list of conditions and the following disclaimer in the 236184SN/A * documentation and/or other materials provided with the distribution; 246184SN/A * neither the name of the copyright holders nor the names of its 256184SN/A * contributors may be used to endorse or promote products derived from 266184SN/A * this software without specific prior written permission. 276184SN/A * 286184SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 296184SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 306184SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 316184SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 326184SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 336184SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 346184SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 356184SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 366184SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 376184SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 386184SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 396184SN/A * 406184SN/A * Authors: Kevin Lim 416184SN/A */ 426184SN/A 4311793Sbrandon.potter@amd.com#include "cpu/pred/tournament.hh" 4411793Sbrandon.potter@amd.com 459360SE.Tomusk@sms.ed.ac.uk#include "base/bitfield.hh" 466184SN/A#include "base/intmath.hh" 476184SN/A 4810785Sgope@wisc.eduTournamentBP::TournamentBP(const TournamentBPParams *params) 499480Snilay@cs.wisc.edu : BPredUnit(params), 509691Satgutier@umich.edu localPredictorSize(params->localPredictorSize), 519480Snilay@cs.wisc.edu localCtrBits(params->localCtrBits), 5213959Sodanrc@yahoo.com.br localCtrs(localPredictorSize, SatCounter(localCtrBits)), 539480Snilay@cs.wisc.edu localHistoryTableSize(params->localHistoryTableSize), 549691Satgutier@umich.edu localHistoryBits(ceilLog2(params->localPredictorSize)), 559480Snilay@cs.wisc.edu globalPredictorSize(params->globalPredictorSize), 569480Snilay@cs.wisc.edu globalCtrBits(params->globalCtrBits), 5713959Sodanrc@yahoo.com.br globalCtrs(globalPredictorSize, SatCounter(globalCtrBits)), 5811434Smitch.hayenga@arm.com globalHistory(params->numThreads, 0), 599691Satgutier@umich.edu globalHistoryBits( 609691Satgutier@umich.edu ceilLog2(params->globalPredictorSize) > 619691Satgutier@umich.edu ceilLog2(params->choicePredictorSize) ? 629691Satgutier@umich.edu ceilLog2(params->globalPredictorSize) : 639691Satgutier@umich.edu ceilLog2(params->choicePredictorSize)), 649480Snilay@cs.wisc.edu choicePredictorSize(params->choicePredictorSize), 6513959Sodanrc@yahoo.com.br choiceCtrBits(params->choiceCtrBits), 6613959Sodanrc@yahoo.com.br choiceCtrs(choicePredictorSize, SatCounter(choiceCtrBits)) 676184SN/A{ 689691Satgutier@umich.edu if (!isPowerOf2(localPredictorSize)) { 699691Satgutier@umich.edu fatal("Invalid local predictor size!\n"); 709691Satgutier@umich.edu } 719691Satgutier@umich.edu 729691Satgutier@umich.edu if (!isPowerOf2(globalPredictorSize)) { 739691Satgutier@umich.edu fatal("Invalid global predictor size!\n"); 749691Satgutier@umich.edu } 756184SN/A 769360SE.Tomusk@sms.ed.ac.uk localPredictorMask = mask(localHistoryBits); 776184SN/A 786184SN/A if (!isPowerOf2(localHistoryTableSize)) { 796184SN/A fatal("Invalid local history table size!\n"); 806184SN/A } 816184SN/A 826184SN/A //Setup the history table for the local table 836184SN/A localHistoryTable.resize(localHistoryTableSize); 846184SN/A 856184SN/A for (int i = 0; i < localHistoryTableSize; ++i) 866184SN/A localHistoryTable[i] = 0; 876184SN/A 889360SE.Tomusk@sms.ed.ac.uk // Set up the global history mask 899360SE.Tomusk@sms.ed.ac.uk // this is equivalent to mask(log2(globalPredictorSize) 909360SE.Tomusk@sms.ed.ac.uk globalHistoryMask = globalPredictorSize - 1; 916184SN/A 926184SN/A if (!isPowerOf2(choicePredictorSize)) { 936184SN/A fatal("Invalid choice predictor size!\n"); 946184SN/A } 956184SN/A 969360SE.Tomusk@sms.ed.ac.uk // Set up choiceHistoryMask 979360SE.Tomusk@sms.ed.ac.uk // this is equivalent to mask(log2(choicePredictorSize) 989360SE.Tomusk@sms.ed.ac.uk choiceHistoryMask = choicePredictorSize - 1; 999360SE.Tomusk@sms.ed.ac.uk 1009360SE.Tomusk@sms.ed.ac.uk //Set up historyRegisterMask 1019360SE.Tomusk@sms.ed.ac.uk historyRegisterMask = mask(globalHistoryBits); 1029360SE.Tomusk@sms.ed.ac.uk 1039360SE.Tomusk@sms.ed.ac.uk //Check that predictors don't use more bits than they have available 1049360SE.Tomusk@sms.ed.ac.uk if (globalHistoryMask > historyRegisterMask) { 1059360SE.Tomusk@sms.ed.ac.uk fatal("Global predictor too large for global history bits!\n"); 1069360SE.Tomusk@sms.ed.ac.uk } 1079360SE.Tomusk@sms.ed.ac.uk if (choiceHistoryMask > historyRegisterMask) { 1089360SE.Tomusk@sms.ed.ac.uk fatal("Choice predictor too large for global history bits!\n"); 1099360SE.Tomusk@sms.ed.ac.uk } 1109360SE.Tomusk@sms.ed.ac.uk 1119360SE.Tomusk@sms.ed.ac.uk if (globalHistoryMask < historyRegisterMask && 1129360SE.Tomusk@sms.ed.ac.uk choiceHistoryMask < historyRegisterMask) { 1139360SE.Tomusk@sms.ed.ac.uk inform("More global history bits than required by predictors\n"); 1149360SE.Tomusk@sms.ed.ac.uk } 1159360SE.Tomusk@sms.ed.ac.uk 1169360SE.Tomusk@sms.ed.ac.uk // Set thresholds for the three predictors' counters 1179360SE.Tomusk@sms.ed.ac.uk // This is equivalent to (2^(Ctr))/2 - 1 1189360SE.Tomusk@sms.ed.ac.uk localThreshold = (ULL(1) << (localCtrBits - 1)) - 1; 1199360SE.Tomusk@sms.ed.ac.uk globalThreshold = (ULL(1) << (globalCtrBits - 1)) - 1; 1209360SE.Tomusk@sms.ed.ac.uk choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 1216184SN/A} 1226184SN/A 1236184SN/Ainline 1246184SN/Aunsigned 1256184SN/ATournamentBP::calcLocHistIdx(Addr &branch_addr) 1266184SN/A{ 1276184SN/A // Get low order bits after removing instruction offset. 1286184SN/A return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1); 1296184SN/A} 1306184SN/A 1316184SN/Ainline 1326184SN/Avoid 13311434Smitch.hayenga@arm.comTournamentBP::updateGlobalHistTaken(ThreadID tid) 1346184SN/A{ 13511434Smitch.hayenga@arm.com globalHistory[tid] = (globalHistory[tid] << 1) | 1; 13611434Smitch.hayenga@arm.com globalHistory[tid] = globalHistory[tid] & historyRegisterMask; 1376184SN/A} 1386184SN/A 1396184SN/Ainline 1406184SN/Avoid 14111434Smitch.hayenga@arm.comTournamentBP::updateGlobalHistNotTaken(ThreadID tid) 1426184SN/A{ 14311434Smitch.hayenga@arm.com globalHistory[tid] = (globalHistory[tid] << 1); 14411434Smitch.hayenga@arm.com globalHistory[tid] = globalHistory[tid] & historyRegisterMask; 1456184SN/A} 1466184SN/A 1476184SN/Ainline 1486184SN/Avoid 1496184SN/ATournamentBP::updateLocalHistTaken(unsigned local_history_idx) 1506184SN/A{ 1516184SN/A localHistoryTable[local_history_idx] = 1526184SN/A (localHistoryTable[local_history_idx] << 1) | 1; 1536184SN/A} 1546184SN/A 1556184SN/Ainline 1566184SN/Avoid 1576184SN/ATournamentBP::updateLocalHistNotTaken(unsigned local_history_idx) 1586184SN/A{ 1596184SN/A localHistoryTable[local_history_idx] = 1606184SN/A (localHistoryTable[local_history_idx] << 1); 1616184SN/A} 1626184SN/A 1638842Smrinmoy.ghosh@arm.com 1648842Smrinmoy.ghosh@arm.comvoid 16511434Smitch.hayenga@arm.comTournamentBP::btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history) 1668842Smrinmoy.ghosh@arm.com{ 1678842Smrinmoy.ghosh@arm.com unsigned local_history_idx = calcLocHistIdx(branch_addr); 1689360SE.Tomusk@sms.ed.ac.uk //Update Global History to Not Taken (clear LSB) 16911434Smitch.hayenga@arm.com globalHistory[tid] &= (historyRegisterMask & ~ULL(1)); 1708842Smrinmoy.ghosh@arm.com //Update Local History to Not Taken 1718842Smrinmoy.ghosh@arm.com localHistoryTable[local_history_idx] = 1729327Smrinmoy.ghosh@arm.com localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1)); 1738842Smrinmoy.ghosh@arm.com} 1748842Smrinmoy.ghosh@arm.com 1756184SN/Abool 17611434Smitch.hayenga@arm.comTournamentBP::lookup(ThreadID tid, Addr branch_addr, void * &bp_history) 1776184SN/A{ 1786184SN/A bool local_prediction; 1796184SN/A unsigned local_history_idx; 1806184SN/A unsigned local_predictor_idx; 1816184SN/A 1826184SN/A bool global_prediction; 1836184SN/A bool choice_prediction; 1846184SN/A 1856184SN/A //Lookup in the local predictor to get its branch prediction 1866184SN/A local_history_idx = calcLocHistIdx(branch_addr); 1876184SN/A local_predictor_idx = localHistoryTable[local_history_idx] 1886184SN/A & localPredictorMask; 18913959Sodanrc@yahoo.com.br local_prediction = localCtrs[local_predictor_idx] > localThreshold; 1906184SN/A 1916184SN/A //Lookup in the global predictor to get its branch prediction 19211434Smitch.hayenga@arm.com global_prediction = globalThreshold < 19313959Sodanrc@yahoo.com.br globalCtrs[globalHistory[tid] & globalHistoryMask]; 1946184SN/A 1956184SN/A //Lookup in the choice predictor to see which one to use 19611434Smitch.hayenga@arm.com choice_prediction = choiceThreshold < 19713959Sodanrc@yahoo.com.br choiceCtrs[globalHistory[tid] & choiceHistoryMask]; 1986184SN/A 1996184SN/A // Create BPHistory and pass it back to be recorded. 2006184SN/A BPHistory *history = new BPHistory; 20111434Smitch.hayenga@arm.com history->globalHistory = globalHistory[tid]; 2026184SN/A history->localPredTaken = local_prediction; 2036184SN/A history->globalPredTaken = global_prediction; 2046184SN/A history->globalUsed = choice_prediction; 20511098Slukefahr@umich.edu history->localHistoryIdx = local_history_idx; 2068842Smrinmoy.ghosh@arm.com history->localHistory = local_predictor_idx; 2076184SN/A bp_history = (void *)history; 2086184SN/A 2099360SE.Tomusk@sms.ed.ac.uk assert(local_history_idx < localHistoryTableSize); 2106184SN/A 21111782Sarthur.perais@inria.fr // Speculative update of the global history and the 21211782Sarthur.perais@inria.fr // selected local history. 2136184SN/A if (choice_prediction) { 2146184SN/A if (global_prediction) { 21511434Smitch.hayenga@arm.com updateGlobalHistTaken(tid); 2168842Smrinmoy.ghosh@arm.com updateLocalHistTaken(local_history_idx); 2176184SN/A return true; 2186184SN/A } else { 21911434Smitch.hayenga@arm.com updateGlobalHistNotTaken(tid); 2208842Smrinmoy.ghosh@arm.com updateLocalHistNotTaken(local_history_idx); 2216184SN/A return false; 2226184SN/A } 2236184SN/A } else { 2246184SN/A if (local_prediction) { 22511434Smitch.hayenga@arm.com updateGlobalHistTaken(tid); 2268842Smrinmoy.ghosh@arm.com updateLocalHistTaken(local_history_idx); 2276184SN/A return true; 2286184SN/A } else { 22911434Smitch.hayenga@arm.com updateGlobalHistNotTaken(tid); 2308842Smrinmoy.ghosh@arm.com updateLocalHistNotTaken(local_history_idx); 2316184SN/A return false; 2326184SN/A } 2336184SN/A } 2346184SN/A} 2356184SN/A 2366184SN/Avoid 23711434Smitch.hayenga@arm.comTournamentBP::uncondBranch(ThreadID tid, Addr pc, void * &bp_history) 2386184SN/A{ 2396184SN/A // Create BPHistory and pass it back to be recorded. 2406184SN/A BPHistory *history = new BPHistory; 24111434Smitch.hayenga@arm.com history->globalHistory = globalHistory[tid]; 2426184SN/A history->localPredTaken = true; 2436184SN/A history->globalPredTaken = true; 2448487SAli.Saidi@ARM.com history->globalUsed = true; 24511098Slukefahr@umich.edu history->localHistoryIdx = invalidPredictorIndex; 2468842Smrinmoy.ghosh@arm.com history->localHistory = invalidPredictorIndex; 2476184SN/A bp_history = static_cast<void *>(history); 2486184SN/A 24911434Smitch.hayenga@arm.com updateGlobalHistTaken(tid); 2506184SN/A} 2516184SN/A 2526184SN/Avoid 25311434Smitch.hayenga@arm.comTournamentBP::update(ThreadID tid, Addr branch_addr, bool taken, 25413626Sjairo.balart@metempsy.com void *bp_history, bool squashed, 25513626Sjairo.balart@metempsy.com const StaticInstPtr & inst, Addr corrTarget) 2566184SN/A{ 25711783Sarthur.perais@inria.fr assert(bp_history); 2586184SN/A 25911783Sarthur.perais@inria.fr BPHistory *history = static_cast<BPHistory *>(bp_history); 2606184SN/A 26111783Sarthur.perais@inria.fr unsigned local_history_idx = calcLocHistIdx(branch_addr); 2626184SN/A 2639360SE.Tomusk@sms.ed.ac.uk assert(local_history_idx < localHistoryTableSize); 2646184SN/A 26511783Sarthur.perais@inria.fr // Unconditional branches do not use local history. 26611783Sarthur.perais@inria.fr bool old_local_pred_valid = history->localHistory != 26711783Sarthur.perais@inria.fr invalidPredictorIndex; 2686184SN/A 26911783Sarthur.perais@inria.fr // If this is a misprediction, restore the speculatively 27011783Sarthur.perais@inria.fr // updated state (global history register and local history) 27111783Sarthur.perais@inria.fr // and update again. 27211783Sarthur.perais@inria.fr if (squashed) { 27311783Sarthur.perais@inria.fr // Global history restore and update 27411783Sarthur.perais@inria.fr globalHistory[tid] = (history->globalHistory << 1) | taken; 27511783Sarthur.perais@inria.fr globalHistory[tid] &= historyRegisterMask; 2766184SN/A 27711783Sarthur.perais@inria.fr // Local history restore and update. 27811783Sarthur.perais@inria.fr if (old_local_pred_valid) { 27911783Sarthur.perais@inria.fr localHistoryTable[local_history_idx] = 28011783Sarthur.perais@inria.fr (history->localHistory << 1) | taken; 28111783Sarthur.perais@inria.fr } 28211783Sarthur.perais@inria.fr 28311783Sarthur.perais@inria.fr return; 28411783Sarthur.perais@inria.fr } 28511783Sarthur.perais@inria.fr 28611783Sarthur.perais@inria.fr unsigned old_local_pred_index = history->localHistory & 28711783Sarthur.perais@inria.fr localPredictorMask; 28811783Sarthur.perais@inria.fr 28911783Sarthur.perais@inria.fr assert(old_local_pred_index < localPredictorSize); 29011783Sarthur.perais@inria.fr 29111783Sarthur.perais@inria.fr // Update the choice predictor to tell it which one was correct if 29211783Sarthur.perais@inria.fr // there was a prediction. 29311783Sarthur.perais@inria.fr if (history->localPredTaken != history->globalPredTaken && 29411783Sarthur.perais@inria.fr old_local_pred_valid) 29511783Sarthur.perais@inria.fr { 29613959Sodanrc@yahoo.com.br // If the local prediction matches the actual outcome, 29713959Sodanrc@yahoo.com.br // decrement the counter. Otherwise increment the 29813959Sodanrc@yahoo.com.br // counter. 29913959Sodanrc@yahoo.com.br unsigned choice_predictor_idx = 30013959Sodanrc@yahoo.com.br history->globalHistory & choiceHistoryMask; 30113959Sodanrc@yahoo.com.br if (history->localPredTaken == taken) { 30213959Sodanrc@yahoo.com.br choiceCtrs[choice_predictor_idx]--; 30313959Sodanrc@yahoo.com.br } else if (history->globalPredTaken == taken) { 30413959Sodanrc@yahoo.com.br choiceCtrs[choice_predictor_idx]++; 30513959Sodanrc@yahoo.com.br } 30611783Sarthur.perais@inria.fr } 30711783Sarthur.perais@inria.fr 30811783Sarthur.perais@inria.fr // Update the counters with the proper 30911783Sarthur.perais@inria.fr // resolution of the branch. Histories are updated 31011783Sarthur.perais@inria.fr // speculatively, restored upon squash() calls, and 31111783Sarthur.perais@inria.fr // recomputed upon update(squash = true) calls, 31211783Sarthur.perais@inria.fr // so they do not need to be updated. 31311783Sarthur.perais@inria.fr unsigned global_predictor_idx = 31411783Sarthur.perais@inria.fr history->globalHistory & globalHistoryMask; 31511783Sarthur.perais@inria.fr if (taken) { 31613959Sodanrc@yahoo.com.br globalCtrs[global_predictor_idx]++; 31713959Sodanrc@yahoo.com.br if (old_local_pred_valid) { 31813959Sodanrc@yahoo.com.br localCtrs[old_local_pred_index]++; 31913959Sodanrc@yahoo.com.br } 32011783Sarthur.perais@inria.fr } else { 32113959Sodanrc@yahoo.com.br globalCtrs[global_predictor_idx]--; 32213959Sodanrc@yahoo.com.br if (old_local_pred_valid) { 32313959Sodanrc@yahoo.com.br localCtrs[old_local_pred_index]--; 32413959Sodanrc@yahoo.com.br } 32511783Sarthur.perais@inria.fr } 32611783Sarthur.perais@inria.fr 32711783Sarthur.perais@inria.fr // We're done with this history, now delete it. 32810330Smitch.hayenga@arm.com delete history; 32910330Smitch.hayenga@arm.com} 33010330Smitch.hayenga@arm.com 33110330Smitch.hayenga@arm.comvoid 33211434Smitch.hayenga@arm.comTournamentBP::squash(ThreadID tid, void *bp_history) 3336184SN/A{ 3346184SN/A BPHistory *history = static_cast<BPHistory *>(bp_history); 3356184SN/A 3366184SN/A // Restore global history to state prior to this branch. 33711434Smitch.hayenga@arm.com globalHistory[tid] = history->globalHistory; 3386184SN/A 33911098Slukefahr@umich.edu // Restore local history 34011098Slukefahr@umich.edu if (history->localHistoryIdx != invalidPredictorIndex) { 34111098Slukefahr@umich.edu localHistoryTable[history->localHistoryIdx] = history->localHistory; 34211098Slukefahr@umich.edu } 34311098Slukefahr@umich.edu 3446184SN/A // Delete this BPHistory now that we're done with it. 3456184SN/A delete history; 3466184SN/A} 3476184SN/A 34810785Sgope@wisc.eduTournamentBP* 34910785Sgope@wisc.eduTournamentBPParams::create() 35010785Sgope@wisc.edu{ 35110785Sgope@wisc.edu return new TournamentBP(this); 35210785Sgope@wisc.edu} 35310785Sgope@wisc.edu 3546184SN/A#ifdef DEBUG 3556184SN/Aint 3566184SN/ATournamentBP::BPHistory::newCount = 0; 3576184SN/A#endif 358