tournament.cc revision 8843
16184SN/A/* 28842Smrinmoy.ghosh@arm.com * Copyright (c) 2011 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 436184SN/A#include "base/intmath.hh" 446226Snate@binkert.org#include "cpu/pred/tournament.hh" 456184SN/A 466184SN/ATournamentBP::TournamentBP(unsigned _localPredictorSize, 476184SN/A unsigned _localCtrBits, 486184SN/A unsigned _localHistoryTableSize, 496184SN/A unsigned _localHistoryBits, 506184SN/A unsigned _globalPredictorSize, 518463SMrinmoy.Ghosh@arm.com unsigned _globalHistoryBits, 526184SN/A unsigned _globalCtrBits, 536184SN/A unsigned _choicePredictorSize, 546184SN/A unsigned _choiceCtrBits, 556184SN/A unsigned _instShiftAmt) 566184SN/A : localPredictorSize(_localPredictorSize), 576184SN/A localCtrBits(_localCtrBits), 586184SN/A localHistoryTableSize(_localHistoryTableSize), 596184SN/A localHistoryBits(_localHistoryBits), 606184SN/A globalPredictorSize(_globalPredictorSize), 616184SN/A globalCtrBits(_globalCtrBits), 626184SN/A globalHistoryBits(_globalHistoryBits), 636184SN/A choicePredictorSize(_globalPredictorSize), 646184SN/A choiceCtrBits(_choiceCtrBits), 656184SN/A instShiftAmt(_instShiftAmt) 666184SN/A{ 676184SN/A if (!isPowerOf2(localPredictorSize)) { 686184SN/A fatal("Invalid local predictor size!\n"); 696184SN/A } 706184SN/A 716184SN/A //Setup 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 776184SN/A localPredictorMask = floorPow2(localPredictorSize) - 1; 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 local history mask 906184SN/A localHistoryMask = (1 << localHistoryBits) - 1; 916184SN/A 926184SN/A if (!isPowerOf2(globalPredictorSize)) { 936184SN/A fatal("Invalid global predictor size!\n"); 946184SN/A } 956184SN/A 966184SN/A //Setup the array of counters for the global predictor 976184SN/A globalCtrs.resize(globalPredictorSize); 986184SN/A 996184SN/A for (int i = 0; i < globalPredictorSize; ++i) 1006184SN/A globalCtrs[i].setBits(globalCtrBits); 1016184SN/A 1026184SN/A //Clear the global history 1036184SN/A globalHistory = 0; 1046184SN/A // Setup the global history mask 1056184SN/A globalHistoryMask = (1 << globalHistoryBits) - 1; 1066184SN/A 1076184SN/A if (!isPowerOf2(choicePredictorSize)) { 1086184SN/A fatal("Invalid choice predictor size!\n"); 1096184SN/A } 1106184SN/A 1116184SN/A //Setup the array of counters for the choice predictor 1126184SN/A choiceCtrs.resize(choicePredictorSize); 1136184SN/A 1146184SN/A for (int i = 0; i < choicePredictorSize; ++i) 1156184SN/A choiceCtrs[i].setBits(choiceCtrBits); 1166184SN/A 1176184SN/A // @todo: Allow for different thresholds between the predictors. 1186184SN/A threshold = (1 << (localCtrBits - 1)) - 1; 1196184SN/A} 1206184SN/A 1216184SN/Ainline 1226184SN/Aunsigned 1236184SN/ATournamentBP::calcLocHistIdx(Addr &branch_addr) 1246184SN/A{ 1256184SN/A // Get low order bits after removing instruction offset. 1266184SN/A return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1); 1276184SN/A} 1286184SN/A 1296184SN/Ainline 1306184SN/Avoid 1316184SN/ATournamentBP::updateGlobalHistTaken() 1326184SN/A{ 1336184SN/A globalHistory = (globalHistory << 1) | 1; 1346184SN/A globalHistory = globalHistory & globalHistoryMask; 1356184SN/A} 1366184SN/A 1376184SN/Ainline 1386184SN/Avoid 1396184SN/ATournamentBP::updateGlobalHistNotTaken() 1406184SN/A{ 1416184SN/A globalHistory = (globalHistory << 1); 1426184SN/A globalHistory = globalHistory & globalHistoryMask; 1436184SN/A} 1446184SN/A 1456184SN/Ainline 1466184SN/Avoid 1476184SN/ATournamentBP::updateLocalHistTaken(unsigned local_history_idx) 1486184SN/A{ 1496184SN/A localHistoryTable[local_history_idx] = 1506184SN/A (localHistoryTable[local_history_idx] << 1) | 1; 1516184SN/A} 1526184SN/A 1536184SN/Ainline 1546184SN/Avoid 1556184SN/ATournamentBP::updateLocalHistNotTaken(unsigned local_history_idx) 1566184SN/A{ 1576184SN/A localHistoryTable[local_history_idx] = 1586184SN/A (localHistoryTable[local_history_idx] << 1); 1596184SN/A} 1606184SN/A 1618842Smrinmoy.ghosh@arm.com 1628842Smrinmoy.ghosh@arm.comvoid 1638842Smrinmoy.ghosh@arm.comTournamentBP::BTBUpdate(Addr &branch_addr, void * &bp_history) 1648842Smrinmoy.ghosh@arm.com{ 1658842Smrinmoy.ghosh@arm.com unsigned local_history_idx = calcLocHistIdx(branch_addr); 1668842Smrinmoy.ghosh@arm.com //Update Global History to Not Taken 1678842Smrinmoy.ghosh@arm.com globalHistory = globalHistory & (globalHistoryMask - 1); 1688842Smrinmoy.ghosh@arm.com //Update Local History to Not Taken 1698842Smrinmoy.ghosh@arm.com localHistoryTable[local_history_idx] = 1708842Smrinmoy.ghosh@arm.com localHistoryTable[local_history_idx] & (localPredictorMask - 1); 1718842Smrinmoy.ghosh@arm.com} 1728842Smrinmoy.ghosh@arm.com 1736184SN/Abool 1746184SN/ATournamentBP::lookup(Addr &branch_addr, void * &bp_history) 1756184SN/A{ 1766184SN/A bool local_prediction; 1776184SN/A unsigned local_history_idx; 1786184SN/A unsigned local_predictor_idx; 1796184SN/A 1806184SN/A bool global_prediction; 1816184SN/A bool choice_prediction; 1826184SN/A 1836184SN/A //Lookup in the local predictor to get its branch prediction 1846184SN/A local_history_idx = calcLocHistIdx(branch_addr); 1856184SN/A local_predictor_idx = localHistoryTable[local_history_idx] 1866184SN/A & localPredictorMask; 1876184SN/A local_prediction = localCtrs[local_predictor_idx].read() > threshold; 1886184SN/A 1896184SN/A //Lookup in the global predictor to get its branch prediction 1906184SN/A global_prediction = globalCtrs[globalHistory].read() > threshold; 1916184SN/A 1926184SN/A //Lookup in the choice predictor to see which one to use 1936184SN/A choice_prediction = choiceCtrs[globalHistory].read() > threshold; 1946184SN/A 1956184SN/A // Create BPHistory and pass it back to be recorded. 1966184SN/A BPHistory *history = new BPHistory; 1976184SN/A history->globalHistory = globalHistory; 1986184SN/A history->localPredTaken = local_prediction; 1996184SN/A history->globalPredTaken = global_prediction; 2006184SN/A history->globalUsed = choice_prediction; 2018842Smrinmoy.ghosh@arm.com history->localHistory = local_predictor_idx; 2026184SN/A bp_history = (void *)history; 2036184SN/A 2046184SN/A assert(globalHistory < globalPredictorSize && 2056184SN/A local_history_idx < localHistoryTableSize && 2066184SN/A local_predictor_idx < localPredictorSize); 2076184SN/A 2086184SN/A // Commented code is for doing speculative update of counters and 2096184SN/A // all histories. 2106184SN/A if (choice_prediction) { 2116184SN/A if (global_prediction) { 2126184SN/A updateGlobalHistTaken(); 2138842Smrinmoy.ghosh@arm.com updateLocalHistTaken(local_history_idx); 2146184SN/A return true; 2156184SN/A } else { 2166184SN/A updateGlobalHistNotTaken(); 2178842Smrinmoy.ghosh@arm.com updateLocalHistNotTaken(local_history_idx); 2186184SN/A return false; 2196184SN/A } 2206184SN/A } else { 2216184SN/A if (local_prediction) { 2226184SN/A updateGlobalHistTaken(); 2238842Smrinmoy.ghosh@arm.com updateLocalHistTaken(local_history_idx); 2246184SN/A return true; 2256184SN/A } else { 2266184SN/A updateGlobalHistNotTaken(); 2278842Smrinmoy.ghosh@arm.com updateLocalHistNotTaken(local_history_idx); 2286184SN/A return false; 2296184SN/A } 2306184SN/A } 2316184SN/A} 2326184SN/A 2336184SN/Avoid 2346184SN/ATournamentBP::uncondBr(void * &bp_history) 2356184SN/A{ 2366184SN/A // Create BPHistory and pass it back to be recorded. 2376184SN/A BPHistory *history = new BPHistory; 2386184SN/A history->globalHistory = globalHistory; 2396184SN/A history->localPredTaken = true; 2406184SN/A history->globalPredTaken = true; 2418487SAli.Saidi@ARM.com history->globalUsed = true; 2428842Smrinmoy.ghosh@arm.com history->localHistory = invalidPredictorIndex; 2436184SN/A bp_history = static_cast<void *>(history); 2446184SN/A 2456184SN/A updateGlobalHistTaken(); 2466184SN/A} 2476184SN/A 2486184SN/Avoid 2498842Smrinmoy.ghosh@arm.comTournamentBP::update(Addr &branch_addr, bool taken, void *bp_history, 2508842Smrinmoy.ghosh@arm.com bool squashed) 2516184SN/A{ 2526184SN/A unsigned local_history_idx; 2538842Smrinmoy.ghosh@arm.com unsigned local_predictor_idx M5_VAR_USED; 2546184SN/A unsigned local_predictor_hist; 2556184SN/A 2566184SN/A // Get the local predictor's current prediction 2576184SN/A local_history_idx = calcLocHistIdx(branch_addr); 2586184SN/A local_predictor_hist = localHistoryTable[local_history_idx]; 2596184SN/A local_predictor_idx = local_predictor_hist & localPredictorMask; 2606184SN/A 2616184SN/A if (bp_history) { 2626184SN/A BPHistory *history = static_cast<BPHistory *>(bp_history); 2638843Smrinmoy.ghosh@arm.com // Update may also be called if the Branch target is incorrect even if 2648843Smrinmoy.ghosh@arm.com // the prediction is correct. In that case do not update the counters. 2658843Smrinmoy.ghosh@arm.com bool historyPred = false; 2668843Smrinmoy.ghosh@arm.com unsigned old_local_pred_index = history->localHistory 2678843Smrinmoy.ghosh@arm.com & localPredictorMask; 2688843Smrinmoy.ghosh@arm.com if (history->globalUsed) { 2698843Smrinmoy.ghosh@arm.com historyPred = history->globalPredTaken; 2708843Smrinmoy.ghosh@arm.com } else { 2718843Smrinmoy.ghosh@arm.com historyPred = history->localPredTaken; 2728843Smrinmoy.ghosh@arm.com } 2738843Smrinmoy.ghosh@arm.com if (historyPred != taken || !squashed) { 2748843Smrinmoy.ghosh@arm.com // Update the choice predictor to tell it which one was correct if 2758843Smrinmoy.ghosh@arm.com // there was a prediction. 2768843Smrinmoy.ghosh@arm.com if (history->localPredTaken != history->globalPredTaken) { 2778843Smrinmoy.ghosh@arm.com // If the local prediction matches the actual outcome, 2788843Smrinmoy.ghosh@arm.com // decerement the counter. Otherwise increment the 2798843Smrinmoy.ghosh@arm.com // counter. 2808843Smrinmoy.ghosh@arm.com if (history->localPredTaken == taken) { 2818843Smrinmoy.ghosh@arm.com choiceCtrs[history->globalHistory].decrement(); 2828843Smrinmoy.ghosh@arm.com } else if (history->globalPredTaken == taken) { 2838843Smrinmoy.ghosh@arm.com choiceCtrs[history->globalHistory].increment(); 2848843Smrinmoy.ghosh@arm.com } 2858463SMrinmoy.Ghosh@arm.com 2868843Smrinmoy.ghosh@arm.com } 2878843Smrinmoy.ghosh@arm.com 2888843Smrinmoy.ghosh@arm.com // Update the counters and local history with the proper 2898843Smrinmoy.ghosh@arm.com // resolution of the branch. Global history is updated 2908843Smrinmoy.ghosh@arm.com // speculatively and restored upon squash() calls, so it does not 2918843Smrinmoy.ghosh@arm.com // need to be updated. 2928843Smrinmoy.ghosh@arm.com if (taken) { 2938843Smrinmoy.ghosh@arm.com globalCtrs[history->globalHistory].increment(); 2948843Smrinmoy.ghosh@arm.com if (old_local_pred_index != invalidPredictorIndex) { 2958843Smrinmoy.ghosh@arm.com localCtrs[old_local_pred_index].increment(); 2968843Smrinmoy.ghosh@arm.com } 2978843Smrinmoy.ghosh@arm.com } else { 2988843Smrinmoy.ghosh@arm.com globalCtrs[history->globalHistory].decrement(); 2998843Smrinmoy.ghosh@arm.com if (old_local_pred_index != invalidPredictorIndex) { 3008843Smrinmoy.ghosh@arm.com localCtrs[old_local_pred_index].decrement(); 3018843Smrinmoy.ghosh@arm.com } 3028843Smrinmoy.ghosh@arm.com } 3036184SN/A } 3048843Smrinmoy.ghosh@arm.com if (squashed) { 3058843Smrinmoy.ghosh@arm.com if (taken) { 3068843Smrinmoy.ghosh@arm.com globalHistory = (history->globalHistory << 1) | 1; 3078843Smrinmoy.ghosh@arm.com globalHistory = globalHistory & globalHistoryMask; 3088843Smrinmoy.ghosh@arm.com if (old_local_pred_index != invalidPredictorIndex) { 3098843Smrinmoy.ghosh@arm.com localHistoryTable[old_local_pred_index] = 3108842Smrinmoy.ghosh@arm.com (history->localHistory << 1) | 1; 3118843Smrinmoy.ghosh@arm.com } 3128843Smrinmoy.ghosh@arm.com } else { 3138843Smrinmoy.ghosh@arm.com globalHistory = (history->globalHistory << 1); 3148843Smrinmoy.ghosh@arm.com globalHistory = globalHistory & globalHistoryMask; 3158843Smrinmoy.ghosh@arm.com if (old_local_pred_index != invalidPredictorIndex) { 3168843Smrinmoy.ghosh@arm.com localHistoryTable[old_local_pred_index] = 3178842Smrinmoy.ghosh@arm.com history->localHistory << 1; 3188843Smrinmoy.ghosh@arm.com } 3198843Smrinmoy.ghosh@arm.com } 3208463SMrinmoy.Ghosh@arm.com 3218463SMrinmoy.Ghosh@arm.com } 3226184SN/A // We're done with this history, now delete it. 3236184SN/A delete history; 3248843Smrinmoy.ghosh@arm.com 3256184SN/A } 3266184SN/A 3276184SN/A assert(globalHistory < globalPredictorSize && 3286184SN/A local_history_idx < localHistoryTableSize && 3296184SN/A local_predictor_idx < localPredictorSize); 3306184SN/A 3316184SN/A 3326184SN/A} 3336184SN/A 3346184SN/Avoid 3356184SN/ATournamentBP::squash(void *bp_history) 3366184SN/A{ 3376184SN/A BPHistory *history = static_cast<BPHistory *>(bp_history); 3386184SN/A 3396184SN/A // Restore global history to state prior to this branch. 3406184SN/A globalHistory = history->globalHistory; 3416184SN/A 3426184SN/A // Delete this BPHistory now that we're done with it. 3436184SN/A delete history; 3446184SN/A} 3456184SN/A 3466184SN/A#ifdef DEBUG 3476184SN/Aint 3486184SN/ATournamentBP::BPHistory::newCount = 0; 3496184SN/A#endif 350