tournament.cc revision 10785
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 439360SE.Tomusk@sms.ed.ac.uk#include "base/bitfield.hh" 446184SN/A#include "base/intmath.hh" 456226Snate@binkert.org#include "cpu/pred/tournament.hh" 466184SN/A 4710785Sgope@wisc.eduTournamentBP::TournamentBP(const TournamentBPParams *params) 489480Snilay@cs.wisc.edu : BPredUnit(params), 499691Satgutier@umich.edu localPredictorSize(params->localPredictorSize), 509480Snilay@cs.wisc.edu localCtrBits(params->localCtrBits), 519480Snilay@cs.wisc.edu localHistoryTableSize(params->localHistoryTableSize), 529691Satgutier@umich.edu localHistoryBits(ceilLog2(params->localPredictorSize)), 539480Snilay@cs.wisc.edu globalPredictorSize(params->globalPredictorSize), 549480Snilay@cs.wisc.edu globalCtrBits(params->globalCtrBits), 559691Satgutier@umich.edu globalHistoryBits( 569691Satgutier@umich.edu ceilLog2(params->globalPredictorSize) > 579691Satgutier@umich.edu ceilLog2(params->choicePredictorSize) ? 589691Satgutier@umich.edu ceilLog2(params->globalPredictorSize) : 599691Satgutier@umich.edu ceilLog2(params->choicePredictorSize)), 609480Snilay@cs.wisc.edu choicePredictorSize(params->choicePredictorSize), 6110785Sgope@wisc.edu choiceCtrBits(params->choiceCtrBits) 626184SN/A{ 639691Satgutier@umich.edu if (!isPowerOf2(localPredictorSize)) { 649691Satgutier@umich.edu fatal("Invalid local predictor size!\n"); 659691Satgutier@umich.edu } 669691Satgutier@umich.edu 679691Satgutier@umich.edu if (!isPowerOf2(globalPredictorSize)) { 689691Satgutier@umich.edu fatal("Invalid global predictor size!\n"); 699691Satgutier@umich.edu } 706184SN/A 719360SE.Tomusk@sms.ed.ac.uk //Set up the array of counters for the local predictor 726184SN/A localCtrs.resize(localPredictorSize); 736184SN/A 746184SN/A for (int i = 0; i < localPredictorSize; ++i) 756184SN/A localCtrs[i].setBits(localCtrBits); 766184SN/A 779360SE.Tomusk@sms.ed.ac.uk localPredictorMask = mask(localHistoryBits); 786184SN/A 796184SN/A if (!isPowerOf2(localHistoryTableSize)) { 806184SN/A fatal("Invalid local history table size!\n"); 816184SN/A } 826184SN/A 836184SN/A //Setup the history table for the local table 846184SN/A localHistoryTable.resize(localHistoryTableSize); 856184SN/A 866184SN/A for (int i = 0; i < localHistoryTableSize; ++i) 876184SN/A localHistoryTable[i] = 0; 886184SN/A 896184SN/A //Setup the array of counters for the global predictor 906184SN/A globalCtrs.resize(globalPredictorSize); 916184SN/A 926184SN/A for (int i = 0; i < globalPredictorSize; ++i) 936184SN/A globalCtrs[i].setBits(globalCtrBits); 946184SN/A 956184SN/A //Clear the global history 966184SN/A globalHistory = 0; 979360SE.Tomusk@sms.ed.ac.uk // Set up the global history mask 989360SE.Tomusk@sms.ed.ac.uk // this is equivalent to mask(log2(globalPredictorSize) 999360SE.Tomusk@sms.ed.ac.uk globalHistoryMask = globalPredictorSize - 1; 1006184SN/A 1016184SN/A if (!isPowerOf2(choicePredictorSize)) { 1026184SN/A fatal("Invalid choice predictor size!\n"); 1036184SN/A } 1046184SN/A 1059360SE.Tomusk@sms.ed.ac.uk // Set up choiceHistoryMask 1069360SE.Tomusk@sms.ed.ac.uk // this is equivalent to mask(log2(choicePredictorSize) 1079360SE.Tomusk@sms.ed.ac.uk choiceHistoryMask = choicePredictorSize - 1; 1089360SE.Tomusk@sms.ed.ac.uk 1096184SN/A //Setup the array of counters for the choice predictor 1106184SN/A choiceCtrs.resize(choicePredictorSize); 1116184SN/A 1126184SN/A for (int i = 0; i < choicePredictorSize; ++i) 1136184SN/A choiceCtrs[i].setBits(choiceCtrBits); 1146184SN/A 1159360SE.Tomusk@sms.ed.ac.uk //Set up historyRegisterMask 1169360SE.Tomusk@sms.ed.ac.uk historyRegisterMask = mask(globalHistoryBits); 1179360SE.Tomusk@sms.ed.ac.uk 1189360SE.Tomusk@sms.ed.ac.uk //Check that predictors don't use more bits than they have available 1199360SE.Tomusk@sms.ed.ac.uk if (globalHistoryMask > historyRegisterMask) { 1209360SE.Tomusk@sms.ed.ac.uk fatal("Global predictor too large for global history bits!\n"); 1219360SE.Tomusk@sms.ed.ac.uk } 1229360SE.Tomusk@sms.ed.ac.uk if (choiceHistoryMask > historyRegisterMask) { 1239360SE.Tomusk@sms.ed.ac.uk fatal("Choice predictor too large for global history bits!\n"); 1249360SE.Tomusk@sms.ed.ac.uk } 1259360SE.Tomusk@sms.ed.ac.uk 1269360SE.Tomusk@sms.ed.ac.uk if (globalHistoryMask < historyRegisterMask && 1279360SE.Tomusk@sms.ed.ac.uk choiceHistoryMask < historyRegisterMask) { 1289360SE.Tomusk@sms.ed.ac.uk inform("More global history bits than required by predictors\n"); 1299360SE.Tomusk@sms.ed.ac.uk } 1309360SE.Tomusk@sms.ed.ac.uk 1319360SE.Tomusk@sms.ed.ac.uk // Set thresholds for the three predictors' counters 1329360SE.Tomusk@sms.ed.ac.uk // This is equivalent to (2^(Ctr))/2 - 1 1339360SE.Tomusk@sms.ed.ac.uk localThreshold = (ULL(1) << (localCtrBits - 1)) - 1; 1349360SE.Tomusk@sms.ed.ac.uk globalThreshold = (ULL(1) << (globalCtrBits - 1)) - 1; 1359360SE.Tomusk@sms.ed.ac.uk choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 1366184SN/A} 1376184SN/A 1386184SN/Ainline 1396184SN/Aunsigned 1406184SN/ATournamentBP::calcLocHistIdx(Addr &branch_addr) 1416184SN/A{ 1426184SN/A // Get low order bits after removing instruction offset. 1436184SN/A return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1); 1446184SN/A} 1456184SN/A 1466184SN/Ainline 1476184SN/Avoid 1486184SN/ATournamentBP::updateGlobalHistTaken() 1496184SN/A{ 1506184SN/A globalHistory = (globalHistory << 1) | 1; 1519360SE.Tomusk@sms.ed.ac.uk globalHistory = globalHistory & historyRegisterMask; 1526184SN/A} 1536184SN/A 1546184SN/Ainline 1556184SN/Avoid 1566184SN/ATournamentBP::updateGlobalHistNotTaken() 1576184SN/A{ 1586184SN/A globalHistory = (globalHistory << 1); 1599360SE.Tomusk@sms.ed.ac.uk globalHistory = globalHistory & historyRegisterMask; 1606184SN/A} 1616184SN/A 1626184SN/Ainline 1636184SN/Avoid 1646184SN/ATournamentBP::updateLocalHistTaken(unsigned local_history_idx) 1656184SN/A{ 1666184SN/A localHistoryTable[local_history_idx] = 1676184SN/A (localHistoryTable[local_history_idx] << 1) | 1; 1686184SN/A} 1696184SN/A 1706184SN/Ainline 1716184SN/Avoid 1726184SN/ATournamentBP::updateLocalHistNotTaken(unsigned local_history_idx) 1736184SN/A{ 1746184SN/A localHistoryTable[local_history_idx] = 1756184SN/A (localHistoryTable[local_history_idx] << 1); 1766184SN/A} 1776184SN/A 1788842Smrinmoy.ghosh@arm.com 1798842Smrinmoy.ghosh@arm.comvoid 1809480Snilay@cs.wisc.eduTournamentBP::btbUpdate(Addr branch_addr, void * &bp_history) 1818842Smrinmoy.ghosh@arm.com{ 1828842Smrinmoy.ghosh@arm.com unsigned local_history_idx = calcLocHistIdx(branch_addr); 1839360SE.Tomusk@sms.ed.ac.uk //Update Global History to Not Taken (clear LSB) 1849360SE.Tomusk@sms.ed.ac.uk globalHistory &= (historyRegisterMask & ~ULL(1)); 1858842Smrinmoy.ghosh@arm.com //Update Local History to Not Taken 1868842Smrinmoy.ghosh@arm.com localHistoryTable[local_history_idx] = 1879327Smrinmoy.ghosh@arm.com localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1)); 1888842Smrinmoy.ghosh@arm.com} 1898842Smrinmoy.ghosh@arm.com 1906184SN/Abool 1919480Snilay@cs.wisc.eduTournamentBP::lookup(Addr branch_addr, void * &bp_history) 1926184SN/A{ 1936184SN/A bool local_prediction; 1946184SN/A unsigned local_history_idx; 1956184SN/A unsigned local_predictor_idx; 1966184SN/A 1976184SN/A bool global_prediction; 1986184SN/A bool choice_prediction; 1996184SN/A 2006184SN/A //Lookup in the local predictor to get its branch prediction 2016184SN/A local_history_idx = calcLocHistIdx(branch_addr); 2026184SN/A local_predictor_idx = localHistoryTable[local_history_idx] 2036184SN/A & localPredictorMask; 2049360SE.Tomusk@sms.ed.ac.uk local_prediction = localCtrs[local_predictor_idx].read() > localThreshold; 2056184SN/A 2066184SN/A //Lookup in the global predictor to get its branch prediction 2079360SE.Tomusk@sms.ed.ac.uk global_prediction = 2089360SE.Tomusk@sms.ed.ac.uk globalCtrs[globalHistory & globalHistoryMask].read() > globalThreshold; 2096184SN/A 2106184SN/A //Lookup in the choice predictor to see which one to use 2119360SE.Tomusk@sms.ed.ac.uk choice_prediction = 2129360SE.Tomusk@sms.ed.ac.uk choiceCtrs[globalHistory & choiceHistoryMask].read() > choiceThreshold; 2136184SN/A 2146184SN/A // Create BPHistory and pass it back to be recorded. 2156184SN/A BPHistory *history = new BPHistory; 2166184SN/A history->globalHistory = globalHistory; 2176184SN/A history->localPredTaken = local_prediction; 2186184SN/A history->globalPredTaken = global_prediction; 2196184SN/A history->globalUsed = choice_prediction; 2208842Smrinmoy.ghosh@arm.com history->localHistory = local_predictor_idx; 2216184SN/A bp_history = (void *)history; 2226184SN/A 2239360SE.Tomusk@sms.ed.ac.uk assert(local_history_idx < localHistoryTableSize); 2246184SN/A 2256184SN/A // Commented code is for doing speculative update of counters and 2266184SN/A // all histories. 2276184SN/A if (choice_prediction) { 2286184SN/A if (global_prediction) { 2296184SN/A updateGlobalHistTaken(); 2308842Smrinmoy.ghosh@arm.com updateLocalHistTaken(local_history_idx); 2316184SN/A return true; 2326184SN/A } else { 2336184SN/A updateGlobalHistNotTaken(); 2348842Smrinmoy.ghosh@arm.com updateLocalHistNotTaken(local_history_idx); 2356184SN/A return false; 2366184SN/A } 2376184SN/A } else { 2386184SN/A if (local_prediction) { 2396184SN/A updateGlobalHistTaken(); 2408842Smrinmoy.ghosh@arm.com updateLocalHistTaken(local_history_idx); 2416184SN/A return true; 2426184SN/A } else { 2436184SN/A updateGlobalHistNotTaken(); 2448842Smrinmoy.ghosh@arm.com updateLocalHistNotTaken(local_history_idx); 2456184SN/A return false; 2466184SN/A } 2476184SN/A } 2486184SN/A} 2496184SN/A 2506184SN/Avoid 25110785Sgope@wisc.eduTournamentBP::uncondBranch(Addr pc, void * &bp_history) 2526184SN/A{ 2536184SN/A // Create BPHistory and pass it back to be recorded. 2546184SN/A BPHistory *history = new BPHistory; 2556184SN/A history->globalHistory = globalHistory; 2566184SN/A history->localPredTaken = true; 2576184SN/A history->globalPredTaken = true; 2588487SAli.Saidi@ARM.com history->globalUsed = true; 2598842Smrinmoy.ghosh@arm.com history->localHistory = invalidPredictorIndex; 2606184SN/A bp_history = static_cast<void *>(history); 2616184SN/A 2626184SN/A updateGlobalHistTaken(); 2636184SN/A} 2646184SN/A 2656184SN/Avoid 2669480Snilay@cs.wisc.eduTournamentBP::update(Addr branch_addr, bool taken, void *bp_history, 2678842Smrinmoy.ghosh@arm.com bool squashed) 2686184SN/A{ 2696184SN/A unsigned local_history_idx; 2708842Smrinmoy.ghosh@arm.com unsigned local_predictor_idx M5_VAR_USED; 2716184SN/A unsigned local_predictor_hist; 2726184SN/A 2736184SN/A // Get the local predictor's current prediction 2746184SN/A local_history_idx = calcLocHistIdx(branch_addr); 2756184SN/A local_predictor_hist = localHistoryTable[local_history_idx]; 2766184SN/A local_predictor_idx = local_predictor_hist & localPredictorMask; 2776184SN/A 2786184SN/A if (bp_history) { 2796184SN/A BPHistory *history = static_cast<BPHistory *>(bp_history); 2808843Smrinmoy.ghosh@arm.com // Update may also be called if the Branch target is incorrect even if 2818843Smrinmoy.ghosh@arm.com // the prediction is correct. In that case do not update the counters. 2828843Smrinmoy.ghosh@arm.com bool historyPred = false; 2839327Smrinmoy.ghosh@arm.com unsigned old_local_pred_index = history->localHistory & 2849327Smrinmoy.ghosh@arm.com localPredictorMask; 2859327Smrinmoy.ghosh@arm.com 2869327Smrinmoy.ghosh@arm.com bool old_local_pred_valid = history->localHistory != 2879327Smrinmoy.ghosh@arm.com invalidPredictorIndex; 2889327Smrinmoy.ghosh@arm.com 2899327Smrinmoy.ghosh@arm.com assert(old_local_pred_index < localPredictorSize); 2909327Smrinmoy.ghosh@arm.com 2918843Smrinmoy.ghosh@arm.com if (history->globalUsed) { 2928843Smrinmoy.ghosh@arm.com historyPred = history->globalPredTaken; 2938843Smrinmoy.ghosh@arm.com } else { 2948843Smrinmoy.ghosh@arm.com historyPred = history->localPredTaken; 2958843Smrinmoy.ghosh@arm.com } 2968843Smrinmoy.ghosh@arm.com if (historyPred != taken || !squashed) { 2978843Smrinmoy.ghosh@arm.com // Update the choice predictor to tell it which one was correct if 2988843Smrinmoy.ghosh@arm.com // there was a prediction. 2998843Smrinmoy.ghosh@arm.com if (history->localPredTaken != history->globalPredTaken) { 3008843Smrinmoy.ghosh@arm.com // If the local prediction matches the actual outcome, 3018843Smrinmoy.ghosh@arm.com // decerement the counter. Otherwise increment the 3028843Smrinmoy.ghosh@arm.com // counter. 3039360SE.Tomusk@sms.ed.ac.uk unsigned choice_predictor_idx = 3049360SE.Tomusk@sms.ed.ac.uk history->globalHistory & choiceHistoryMask; 3058843Smrinmoy.ghosh@arm.com if (history->localPredTaken == taken) { 3069360SE.Tomusk@sms.ed.ac.uk choiceCtrs[choice_predictor_idx].decrement(); 3078843Smrinmoy.ghosh@arm.com } else if (history->globalPredTaken == taken) { 3089360SE.Tomusk@sms.ed.ac.uk choiceCtrs[choice_predictor_idx].increment(); 3098843Smrinmoy.ghosh@arm.com } 3108463SMrinmoy.Ghosh@arm.com 3118843Smrinmoy.ghosh@arm.com } 3128843Smrinmoy.ghosh@arm.com 3138843Smrinmoy.ghosh@arm.com // Update the counters and local history with the proper 3148843Smrinmoy.ghosh@arm.com // resolution of the branch. Global history is updated 3158843Smrinmoy.ghosh@arm.com // speculatively and restored upon squash() calls, so it does not 3168843Smrinmoy.ghosh@arm.com // need to be updated. 3179360SE.Tomusk@sms.ed.ac.uk unsigned global_predictor_idx = 3189360SE.Tomusk@sms.ed.ac.uk history->globalHistory & globalHistoryMask; 3198843Smrinmoy.ghosh@arm.com if (taken) { 3209360SE.Tomusk@sms.ed.ac.uk globalCtrs[global_predictor_idx].increment(); 3219327Smrinmoy.ghosh@arm.com if (old_local_pred_valid) { 3228843Smrinmoy.ghosh@arm.com localCtrs[old_local_pred_index].increment(); 3238843Smrinmoy.ghosh@arm.com } 3248843Smrinmoy.ghosh@arm.com } else { 3259360SE.Tomusk@sms.ed.ac.uk globalCtrs[global_predictor_idx].decrement(); 3269327Smrinmoy.ghosh@arm.com if (old_local_pred_valid) { 3278843Smrinmoy.ghosh@arm.com localCtrs[old_local_pred_index].decrement(); 3288843Smrinmoy.ghosh@arm.com } 3298843Smrinmoy.ghosh@arm.com } 3306184SN/A } 3318843Smrinmoy.ghosh@arm.com if (squashed) { 3328843Smrinmoy.ghosh@arm.com if (taken) { 3338843Smrinmoy.ghosh@arm.com globalHistory = (history->globalHistory << 1) | 1; 3349360SE.Tomusk@sms.ed.ac.uk globalHistory = globalHistory & historyRegisterMask; 3359327Smrinmoy.ghosh@arm.com if (old_local_pred_valid) { 3369327Smrinmoy.ghosh@arm.com localHistoryTable[local_history_idx] = 3378842Smrinmoy.ghosh@arm.com (history->localHistory << 1) | 1; 3388843Smrinmoy.ghosh@arm.com } 3398843Smrinmoy.ghosh@arm.com } else { 3408843Smrinmoy.ghosh@arm.com globalHistory = (history->globalHistory << 1); 3419360SE.Tomusk@sms.ed.ac.uk globalHistory = globalHistory & historyRegisterMask; 3429327Smrinmoy.ghosh@arm.com if (old_local_pred_valid) { 3439327Smrinmoy.ghosh@arm.com localHistoryTable[local_history_idx] = 3448842Smrinmoy.ghosh@arm.com history->localHistory << 1; 3458843Smrinmoy.ghosh@arm.com } 3468843Smrinmoy.ghosh@arm.com } 3478463SMrinmoy.Ghosh@arm.com 34810330Smitch.hayenga@arm.com } else { 34910330Smitch.hayenga@arm.com // We're done with this history, now delete it. 35010330Smitch.hayenga@arm.com delete history; 3518463SMrinmoy.Ghosh@arm.com } 3526184SN/A } 3536184SN/A 3549360SE.Tomusk@sms.ed.ac.uk assert(local_history_idx < localHistoryTableSize); 3556184SN/A 3566184SN/A 3576184SN/A} 3586184SN/A 3596184SN/Avoid 36010330Smitch.hayenga@arm.comTournamentBP::retireSquashed(void *bp_history) 36110330Smitch.hayenga@arm.com{ 36210330Smitch.hayenga@arm.com BPHistory *history = static_cast<BPHistory *>(bp_history); 36310330Smitch.hayenga@arm.com delete history; 36410330Smitch.hayenga@arm.com} 36510330Smitch.hayenga@arm.com 36610330Smitch.hayenga@arm.comvoid 3676184SN/ATournamentBP::squash(void *bp_history) 3686184SN/A{ 3696184SN/A BPHistory *history = static_cast<BPHistory *>(bp_history); 3706184SN/A 3716184SN/A // Restore global history to state prior to this branch. 3726184SN/A globalHistory = history->globalHistory; 3736184SN/A 3746184SN/A // Delete this BPHistory now that we're done with it. 3756184SN/A delete history; 3766184SN/A} 3776184SN/A 37810785Sgope@wisc.eduTournamentBP* 37910785Sgope@wisc.eduTournamentBPParams::create() 38010785Sgope@wisc.edu{ 38110785Sgope@wisc.edu return new TournamentBP(this); 38210785Sgope@wisc.edu} 38310785Sgope@wisc.edu 3846184SN/A#ifdef DEBUG 3856184SN/Aint 3866184SN/ATournamentBP::BPHistory::newCount = 0; 3876184SN/A#endif 388