tournament.cc revision 6226
1360SN/A/* 21458SN/A * Copyright (c) 2004-2006 The Regents of The University of Michigan 3360SN/A * All rights reserved. 4360SN/A * 5360SN/A * Redistribution and use in source and binary forms, with or without 6360SN/A * modification, are permitted provided that the following conditions are 7360SN/A * met: redistributions of source code must retain the above copyright 8360SN/A * notice, this list of conditions and the following disclaimer; 9360SN/A * redistributions in binary form must reproduce the above copyright 10360SN/A * notice, this list of conditions and the following disclaimer in the 11360SN/A * documentation and/or other materials provided with the distribution; 12360SN/A * neither the name of the copyright holders nor the names of its 13360SN/A * contributors may be used to endorse or promote products derived from 14360SN/A * this software without specific prior written permission. 15360SN/A * 16360SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17360SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18360SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19360SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20360SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21360SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22360SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23360SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24360SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25360SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26360SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272665Ssaidi@eecs.umich.edu * 282665Ssaidi@eecs.umich.edu * Authors: Kevin Lim 292665Ssaidi@eecs.umich.edu */ 30360SN/A 31360SN/A#include "base/intmath.hh" 322093SN/A#include "cpu/pred/tournament.hh" 33360SN/A 34360SN/ATournamentBP::TournamentBP(unsigned _localPredictorSize, 35360SN/A unsigned _localCtrBits, 36360SN/A unsigned _localHistoryTableSize, 37360SN/A unsigned _localHistoryBits, 38360SN/A unsigned _globalPredictorSize, 392474SN/A unsigned _globalCtrBits, 40360SN/A unsigned _globalHistoryBits, 412680Sktlim@umich.edu unsigned _choicePredictorSize, 421717SN/A unsigned _choiceCtrBits, 432474SN/A unsigned _instShiftAmt) 44360SN/A : localPredictorSize(_localPredictorSize), 456029Ssteve.reinhardt@amd.com localCtrBits(_localCtrBits), 46360SN/A localHistoryTableSize(_localHistoryTableSize), 472667Sstever@eecs.umich.edu localHistoryBits(_localHistoryBits), 48360SN/A globalPredictorSize(_globalPredictorSize), 49360SN/A globalCtrBits(_globalCtrBits), 502107SN/A globalHistoryBits(_globalHistoryBits), 51360SN/A choicePredictorSize(_globalPredictorSize), 52360SN/A choiceCtrBits(_choiceCtrBits), 533114Sgblack@eecs.umich.edu instShiftAmt(_instShiftAmt) 54360SN/A{ 556111Ssteve.reinhardt@amd.com if (!isPowerOf2(localPredictorSize)) { 566111Ssteve.reinhardt@amd.com fatal("Invalid local predictor size!\n"); 576111Ssteve.reinhardt@amd.com } 585958Sgblack@eecs.umich.edu 595958Sgblack@eecs.umich.edu //Setup the array of counters for the local predictor 60360SN/A localCtrs.resize(localPredictorSize); 612680Sktlim@umich.edu 62360SN/A for (int i = 0; i < localPredictorSize; ++i) 632495SN/A localCtrs[i].setBits(localCtrBits); 642680Sktlim@umich.edu 65360SN/A localPredictorMask = floorPow2(localPredictorSize) - 1; 661450SN/A 675958Sgblack@eecs.umich.edu if (!isPowerOf2(localHistoryTableSize)) { 68360SN/A fatal("Invalid local history table size!\n"); 69360SN/A } 70360SN/A 711450SN/A //Setup the history table for the local table 723114Sgblack@eecs.umich.edu localHistoryTable.resize(localHistoryTableSize); 732680Sktlim@umich.edu 74360SN/A for (int i = 0; i < localHistoryTableSize; ++i) 751969SN/A localHistoryTable[i] = 0; 762484SN/A 772484SN/A // Setup the local history mask 78360SN/A localHistoryMask = (1 << localHistoryBits) - 1; 79360SN/A 80360SN/A if (!isPowerOf2(globalPredictorSize)) { 811450SN/A fatal("Invalid global predictor size!\n"); 823114Sgblack@eecs.umich.edu } 832680Sktlim@umich.edu 84360SN/A //Setup the array of counters for the global predictor 851969SN/A globalCtrs.resize(globalPredictorSize); 865958Sgblack@eecs.umich.edu 87360SN/A for (int i = 0; i < globalPredictorSize; ++i) 881458SN/A globalCtrs[i].setBits(globalCtrBits); 89360SN/A 90360SN/A //Clear the global history 91360SN/A globalHistory = 0; 921450SN/A // Setup the global history mask 933114Sgblack@eecs.umich.edu globalHistoryMask = (1 << globalHistoryBits) - 1; 942680Sktlim@umich.edu 95360SN/A if (!isPowerOf2(choicePredictorSize)) { 966029Ssteve.reinhardt@amd.com fatal("Invalid choice predictor size!\n"); 976029Ssteve.reinhardt@amd.com } 985958Sgblack@eecs.umich.edu 996029Ssteve.reinhardt@amd.com //Setup the array of counters for the choice predictor 1006029Ssteve.reinhardt@amd.com choiceCtrs.resize(choicePredictorSize); 1016029Ssteve.reinhardt@amd.com 1026029Ssteve.reinhardt@amd.com for (int i = 0; i < choicePredictorSize; ++i) 1032834Sksewell@umich.edu choiceCtrs[i].setBits(choiceCtrBits); 104360SN/A 1051458SN/A // @todo: Allow for different thresholds between the predictors. 106360SN/A threshold = (1 << (localCtrBits - 1)) - 1; 107360SN/A threshold = threshold / 2; 108360SN/A} 1091450SN/A 1106109Ssanchezd@stanford.eduinline 1116109Ssanchezd@stanford.eduunsigned 1126109Ssanchezd@stanford.eduTournamentBP::calcLocHistIdx(Addr &branch_addr) 1136109Ssanchezd@stanford.edu{ 1146109Ssanchezd@stanford.edu // Get low order bits after removing instruction offset. 1156109Ssanchezd@stanford.edu return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1); 1166109Ssanchezd@stanford.edu} 1176109Ssanchezd@stanford.edu 1186109Ssanchezd@stanford.eduinline 1196109Ssanchezd@stanford.eduvoid 1206109Ssanchezd@stanford.eduTournamentBP::updateGlobalHistTaken() 1216109Ssanchezd@stanford.edu{ 1226109Ssanchezd@stanford.edu globalHistory = (globalHistory << 1) | 1; 1233114Sgblack@eecs.umich.edu globalHistory = globalHistory & globalHistoryMask; 124360SN/A} 1252107SN/A 126360SN/Ainline 127360SN/Avoid 128360SN/ATournamentBP::updateGlobalHistNotTaken() 1291450SN/A{ 1305748SSteve.Reinhardt@amd.com globalHistory = (globalHistory << 1); 131360SN/A globalHistory = globalHistory & globalHistoryMask; 132360SN/A} 1335958Sgblack@eecs.umich.edu 1345748SSteve.Reinhardt@amd.cominline 1355748SSteve.Reinhardt@amd.comvoid 1365748SSteve.Reinhardt@amd.comTournamentBP::updateLocalHistTaken(unsigned local_history_idx) 1375748SSteve.Reinhardt@amd.com{ 1385748SSteve.Reinhardt@amd.com localHistoryTable[local_history_idx] = 1395748SSteve.Reinhardt@amd.com (localHistoryTable[local_history_idx] << 1) | 1; 1405748SSteve.Reinhardt@amd.com} 1415748SSteve.Reinhardt@amd.com 1422474SN/Ainline 1432474SN/Avoid 1445748SSteve.Reinhardt@amd.comTournamentBP::updateLocalHistNotTaken(unsigned local_history_idx) 1452474SN/A{ 1462474SN/A localHistoryTable[local_history_idx] = 1472474SN/A (localHistoryTable[local_history_idx] << 1); 1481450SN/A} 1495748SSteve.Reinhardt@amd.com 1505748SSteve.Reinhardt@amd.combool 1511458SN/ATournamentBP::lookup(Addr &branch_addr, void * &bp_history) 1521458SN/A{ 153360SN/A bool local_prediction; 154360SN/A unsigned local_history_idx; 155360SN/A unsigned local_predictor_idx; 1561450SN/A 1573114Sgblack@eecs.umich.edu bool global_prediction; 158360SN/A bool choice_prediction; 1595958Sgblack@eecs.umich.edu 1601970SN/A //Lookup in the local predictor to get its branch prediction 1611970SN/A local_history_idx = calcLocHistIdx(branch_addr); 1621970SN/A local_predictor_idx = localHistoryTable[local_history_idx] 1631970SN/A & localPredictorMask; 164360SN/A local_prediction = localCtrs[local_predictor_idx].read() > threshold; 165360SN/A 166360SN/A //Lookup in the global predictor to get its branch prediction 1671450SN/A global_prediction = globalCtrs[globalHistory].read() > threshold; 1683114Sgblack@eecs.umich.edu 169360SN/A //Lookup in the choice predictor to see which one to use 1705958Sgblack@eecs.umich.edu choice_prediction = choiceCtrs[globalHistory].read() > threshold; 1715958Sgblack@eecs.umich.edu 1725958Sgblack@eecs.umich.edu // Create BPHistory and pass it back to be recorded. 173360SN/A BPHistory *history = new BPHistory; 174360SN/A history->globalHistory = globalHistory; 175360SN/A history->localPredTaken = local_prediction; 176360SN/A history->globalPredTaken = global_prediction; 1772680Sktlim@umich.edu history->globalUsed = choice_prediction; 178360SN/A bp_history = (void *)history; 1791458SN/A 180360SN/A assert(globalHistory < globalPredictorSize && 181360SN/A local_history_idx < localHistoryTableSize && 1821450SN/A local_predictor_idx < localPredictorSize); 1833114Sgblack@eecs.umich.edu 184360SN/A // Commented code is for doing speculative update of counters and 1855958Sgblack@eecs.umich.edu // all histories. 1865958Sgblack@eecs.umich.edu if (choice_prediction) { 1875958Sgblack@eecs.umich.edu if (global_prediction) { 188360SN/A// updateHistoriesTaken(local_history_idx); 1892680Sktlim@umich.edu// globalCtrs[globalHistory].increment(); 190360SN/A// localCtrs[local_history_idx].increment(); 191360SN/A updateGlobalHistTaken(); 192360SN/A return true; 193360SN/A } else { 194360SN/A// updateHistoriesNotTaken(local_history_idx); 1951458SN/A// globalCtrs[globalHistory].decrement(); 196360SN/A// localCtrs[local_history_idx].decrement(); 197360SN/A updateGlobalHistNotTaken(); 198360SN/A return false; 1991450SN/A } 2003114Sgblack@eecs.umich.edu } else { 201360SN/A if (local_prediction) { 2025958Sgblack@eecs.umich.edu// updateHistoriesTaken(local_history_idx); 2035958Sgblack@eecs.umich.edu// globalCtrs[globalHistory].increment(); 2045958Sgblack@eecs.umich.edu// localCtrs[local_history_idx].increment(); 205360SN/A updateGlobalHistTaken(); 206360SN/A return true; 207360SN/A } else { 2081458SN/A// updateHistoriesNotTaken(local_history_idx); 209360SN/A// globalCtrs[globalHistory].decrement(); 210360SN/A// localCtrs[local_history_idx].decrement(); 211360SN/A updateGlobalHistNotTaken(); 2121450SN/A return false; 2134118Sgblack@eecs.umich.edu } 2144118Sgblack@eecs.umich.edu } 2155958Sgblack@eecs.umich.edu} 2165958Sgblack@eecs.umich.edu 2175958Sgblack@eecs.umich.eduvoid 2185958Sgblack@eecs.umich.eduTournamentBP::uncondBr(void * &bp_history) 2195958Sgblack@eecs.umich.edu{ 2204118Sgblack@eecs.umich.edu // Create BPHistory and pass it back to be recorded. 2214118Sgblack@eecs.umich.edu BPHistory *history = new BPHistory; 2224118Sgblack@eecs.umich.edu history->globalHistory = globalHistory; 2234118Sgblack@eecs.umich.edu history->localPredTaken = true; 2244118Sgblack@eecs.umich.edu history->globalPredTaken = true; 2254118Sgblack@eecs.umich.edu bp_history = static_cast<void *>(history); 2264118Sgblack@eecs.umich.edu 2274118Sgblack@eecs.umich.edu updateGlobalHistTaken(); 2284118Sgblack@eecs.umich.edu} 2294118Sgblack@eecs.umich.edu 2306111Ssteve.reinhardt@amd.comvoid 2316111Ssteve.reinhardt@amd.comTournamentBP::update(Addr &branch_addr, bool taken, void *bp_history) 2326111Ssteve.reinhardt@amd.com{ 2336111Ssteve.reinhardt@amd.com unsigned local_history_idx; 2344118Sgblack@eecs.umich.edu unsigned local_predictor_idx; 2354118Sgblack@eecs.umich.edu unsigned local_predictor_hist; 2364118Sgblack@eecs.umich.edu 2374118Sgblack@eecs.umich.edu // Get the local predictor's current prediction 2384118Sgblack@eecs.umich.edu local_history_idx = calcLocHistIdx(branch_addr); 2394118Sgblack@eecs.umich.edu local_predictor_hist = localHistoryTable[local_history_idx]; 2404118Sgblack@eecs.umich.edu local_predictor_idx = local_predictor_hist & localPredictorMask; 2414118Sgblack@eecs.umich.edu 2424118Sgblack@eecs.umich.edu // Update the choice predictor to tell it which one was correct if 2434118Sgblack@eecs.umich.edu // there was a prediction. 2444118Sgblack@eecs.umich.edu if (bp_history) { 2454118Sgblack@eecs.umich.edu BPHistory *history = static_cast<BPHistory *>(bp_history); 2463114Sgblack@eecs.umich.edu if (history->localPredTaken != history->globalPredTaken) { 247360SN/A // If the local prediction matches the actual outcome, 248360SN/A // decerement the counter. Otherwise increment the 2491458SN/A // counter. 250360SN/A if (history->localPredTaken == taken) { 251360SN/A choiceCtrs[globalHistory].decrement(); 252360SN/A } else if (history->globalPredTaken == taken){ 253360SN/A choiceCtrs[globalHistory].increment(); 254360SN/A } 2551450SN/A } 2563114Sgblack@eecs.umich.edu 257360SN/A // We're done with this history, now delete it. 2585958Sgblack@eecs.umich.edu delete history; 2595958Sgblack@eecs.umich.edu } 260360SN/A 261360SN/A assert(globalHistory < globalPredictorSize && 262360SN/A local_history_idx < localHistoryTableSize && 2632680Sktlim@umich.edu local_predictor_idx < localPredictorSize); 264360SN/A 2651458SN/A // Update the counters and local history with the proper 266360SN/A // resolution of the branch. Global history is updated 267360SN/A // speculatively and restored upon squash() calls, so it does not 2681450SN/A // need to be updated. 2695513SMichael.Adler@intel.com if (taken) { 2705513SMichael.Adler@intel.com localCtrs[local_predictor_idx].increment(); 2715513SMichael.Adler@intel.com globalCtrs[globalHistory].increment(); 2725958Sgblack@eecs.umich.edu 2735958Sgblack@eecs.umich.edu updateLocalHistTaken(local_history_idx); 2745513SMichael.Adler@intel.com } else { 2755513SMichael.Adler@intel.com localCtrs[local_predictor_idx].decrement(); 2765513SMichael.Adler@intel.com globalCtrs[globalHistory].decrement(); 2775513SMichael.Adler@intel.com 2785513SMichael.Adler@intel.com updateLocalHistNotTaken(local_history_idx); 2795513SMichael.Adler@intel.com } 2805513SMichael.Adler@intel.com} 2815513SMichael.Adler@intel.com 2825513SMichael.Adler@intel.comvoid 2835513SMichael.Adler@intel.comTournamentBP::squash(void *bp_history) 2845513SMichael.Adler@intel.com{ 2855513SMichael.Adler@intel.com BPHistory *history = static_cast<BPHistory *>(bp_history); 2865513SMichael.Adler@intel.com 2875513SMichael.Adler@intel.com // Restore global history to state prior to this branch. 2885513SMichael.Adler@intel.com globalHistory = history->globalHistory; 2895513SMichael.Adler@intel.com 2905513SMichael.Adler@intel.com // Delete this BPHistory now that we're done with it. 2915513SMichael.Adler@intel.com delete history; 2925513SMichael.Adler@intel.com} 2935513SMichael.Adler@intel.com 2945513SMichael.Adler@intel.com#ifdef DEBUG 2955513SMichael.Adler@intel.comint 2965513SMichael.Adler@intel.comTournamentBP::BPHistory::newCount = 0; 2975513SMichael.Adler@intel.com#endif 2985513SMichael.Adler@intel.com