bi_mode.cc revision 13959:ea907b02c800
1451SN/A/* 22212SN/A * Copyright (c) 2014 The Regents of The University of Michigan 3451SN/A * All rights reserved. 4451SN/A * 5451SN/A * Redistribution and use in source and binary forms, with or without 6451SN/A * modification, are permitted provided that the following conditions are 7451SN/A * met: redistributions of source code must retain the above copyright 8451SN/A * notice, this list of conditions and the following disclaimer; 9451SN/A * redistributions in binary form must reproduce the above copyright 10451SN/A * notice, this list of conditions and the following disclaimer in the 11451SN/A * documentation and/or other materials provided with the distribution; 12451SN/A * neither the name of the copyright holders nor the names of its 13451SN/A * contributors may be used to endorse or promote products derived from 14451SN/A * this software without specific prior written permission. 15451SN/A * 16451SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17451SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18451SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19451SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20451SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21451SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22451SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23451SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24451SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25451SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26451SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272665Ssaidi@eecs.umich.edu * 282665Ssaidi@eecs.umich.edu * Authors: Anthony Gutierrez 292665Ssaidi@eecs.umich.edu */ 302665Ssaidi@eecs.umich.edu 31451SN/A/* @file 32451SN/A * Implementation of a bi-mode branch predictor 332212SN/A */ 342212SN/A 35451SN/A#include "cpu/pred/bi_mode.hh" 362680Sktlim@umich.edu 371070SN/A#include "base/bitfield.hh" 381070SN/A#include "base/intmath.hh" 391070SN/A 402212SN/ABiModeBP::BiModeBP(const BiModeBPParams *params) 413565Sgblack@eecs.umich.edu : BPredUnit(params), 422212SN/A globalHistoryReg(params->numThreads, 0), 432212SN/A globalHistoryBits(ceilLog2(params->globalPredictorSize)), 444762Snate@binkert.org choicePredictorSize(params->choicePredictorSize), 452212SN/A choiceCtrBits(params->choiceCtrBits), 46885SN/A globalPredictorSize(params->globalPredictorSize), 472343SN/A globalCtrBits(params->globalCtrBits), 48885SN/A choiceCounters(choicePredictorSize, SatCounter(choiceCtrBits)), 49885SN/A takenCounters(globalPredictorSize, SatCounter(globalCtrBits)), 50885SN/A notTakenCounters(globalPredictorSize, SatCounter(globalCtrBits)) 512212SN/A{ 52451SN/A if (!isPowerOf2(choicePredictorSize)) 53451SN/A fatal("Invalid choice predictor size.\n"); 545569Snate@binkert.org if (!isPowerOf2(globalPredictorSize)) 551885SN/A fatal("Invalid global history predictor size.\n"); 561885SN/A 571885SN/A historyRegisterMask = mask(globalHistoryBits); 582680Sktlim@umich.edu choiceHistoryMask = choicePredictorSize - 1; 591885SN/A globalHistoryMask = globalPredictorSize - 1; 601885SN/A 615569Snate@binkert.org choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 621885SN/A takenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1; 631885SN/A notTakenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1; 641885SN/A} 652680Sktlim@umich.edu 661885SN/A/* 671885SN/A * For an unconditional branch we set its history such that 681855SN/A * everything is set to taken. I.e., its choice predictor 691855SN/A * chooses the taken array and the taken array predicts taken. 701855SN/A */ 711855SN/Avoid 721855SN/ABiModeBP::uncondBranch(ThreadID tid, Addr pc, void * &bpHistory) 731855SN/A{ 741855SN/A BPHistory *history = new BPHistory; 751855SN/A history->globalHistoryReg = globalHistoryReg[tid]; 761855SN/A history->takenUsed = true; 771855SN/A history->takenPred = true; 781855SN/A history->notTakenPred = true; 791855SN/A history->finalPred = true; 801855SN/A bpHistory = static_cast<void*>(history); 811855SN/A updateGlobalHistReg(tid, true); 821855SN/A} 831855SN/A 841855SN/Avoid 851855SN/ABiModeBP::squash(ThreadID tid, void *bpHistory) 861855SN/A{ 871855SN/A BPHistory *history = static_cast<BPHistory*>(bpHistory); 881492SN/A globalHistoryReg[tid] = history->globalHistoryReg; 89887SN/A 90451SN/A delete history; 911492SN/A} 929557Sandreas.hansson@arm.com 931492SN/A/* 941492SN/A * Here we lookup the actual branch prediction. We use the PC to 951070SN/A * identify the bias of a particular branch, which is based on the 96887SN/A * prediction in the choice array. A hash of the global history 979557Sandreas.hansson@arm.com * register and a branch's PC is used to index into both the taken 989557Sandreas.hansson@arm.com * and not-taken predictors, which both present a prediction. The 991070SN/A * choice array's prediction is used to select between the two 1001070SN/A * direction predictors for the final branch prediction. 1011070SN/A */ 102887SN/Abool 103885SN/ABiModeBP::lookup(ThreadID tid, Addr branchAddr, void * &bpHistory) 104887SN/A{ 105887SN/A unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 106885SN/A & choiceHistoryMask); 107887SN/A unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 1081070SN/A ^ globalHistoryReg[tid]) 1091070SN/A & globalHistoryMask); 1101070SN/A 1111070SN/A assert(choiceHistoryIdx < choicePredictorSize); 1125991Ssteve.reinhardt@amd.com assert(globalHistoryIdx < globalPredictorSize); 1131039SN/A 1141070SN/A bool choicePrediction = choiceCounters[choiceHistoryIdx] 1151070SN/A > choiceThreshold; 116887SN/A bool takenGHBPrediction = takenCounters[globalHistoryIdx] 117887SN/A > takenThreshold; 1181885SN/A bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx] 119841SN/A > notTakenThreshold; 1201082SN/A bool finalPrediction; 1211082SN/A 1221082SN/A BPHistory *history = new BPHistory; 1231082SN/A history->globalHistoryReg = globalHistoryReg[tid]; 1241067SN/A history->takenUsed = choicePrediction; 1251067SN/A history->takenPred = takenGHBPrediction; 1261070SN/A history->notTakenPred = notTakenGHBPrediction; 1271070SN/A 128451SN/A if (choicePrediction) { 1298885SAli.Saidi@ARM.com finalPrediction = takenGHBPrediction; 1308885SAli.Saidi@ARM.com } else { 1318885SAli.Saidi@ARM.com finalPrediction = notTakenGHBPrediction; 1328885SAli.Saidi@ARM.com } 1338885SAli.Saidi@ARM.com 1348885SAli.Saidi@ARM.com history->finalPred = finalPrediction; 135451SN/A bpHistory = static_cast<void*>(history); 1364762Snate@binkert.org updateGlobalHistReg(tid, finalPrediction); 1372212SN/A 1382212SN/A return finalPrediction; 139451SN/A} 1408706Sandreas.hansson@arm.com 1418706Sandreas.hansson@arm.comvoid 1428706Sandreas.hansson@arm.comBiModeBP::btbUpdate(ThreadID tid, Addr branchAddr, void * &bpHistory) 1438706Sandreas.hansson@arm.com{ 1448706Sandreas.hansson@arm.com globalHistoryReg[tid] &= (historyRegisterMask & ~ULL(1)); 1452680Sktlim@umich.edu} 1468799Sgblack@eecs.umich.edu 1478799Sgblack@eecs.umich.edu/* Only the selected direction predictor will be updated with the final 148451SN/A * outcome; the status of the unselected one will not be altered. The choice 149451SN/A * predictor is always updated with the branch outcome, except when the 1502212SN/A * choice is opposite to the branch outcome but the selected counter of 151 * the direction predictors makes a correct final prediction. 152 */ 153void 154BiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory, 155 bool squashed, const StaticInstPtr & inst, Addr corrTarget) 156{ 157 assert(bpHistory); 158 159 BPHistory *history = static_cast<BPHistory*>(bpHistory); 160 161 // We do not update the counters speculatively on a squash. 162 // We just restore the global history register. 163 if (squashed) { 164 globalHistoryReg[tid] = (history->globalHistoryReg << 1) | taken; 165 return; 166 } 167 168 unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 169 & choiceHistoryMask); 170 unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 171 ^ history->globalHistoryReg) 172 & globalHistoryMask); 173 174 assert(choiceHistoryIdx < choicePredictorSize); 175 assert(globalHistoryIdx < globalPredictorSize); 176 177 if (history->takenUsed) { 178 // if the taken array's prediction was used, update it 179 if (taken) { 180 takenCounters[globalHistoryIdx]++; 181 } else { 182 takenCounters[globalHistoryIdx]--; 183 } 184 } else { 185 // if the not-taken array's prediction was used, update it 186 if (taken) { 187 notTakenCounters[globalHistoryIdx]++; 188 } else { 189 notTakenCounters[globalHistoryIdx]--; 190 } 191 } 192 193 if (history->finalPred == taken) { 194 /* If the final prediction matches the actual branch's 195 * outcome and the choice predictor matches the final 196 * outcome, we update the choice predictor, otherwise it 197 * is not updated. While the designers of the bi-mode 198 * predictor don't explicity say why this is done, one 199 * can infer that it is to preserve the choice predictor's 200 * bias with respect to the branch being predicted; afterall, 201 * the whole point of the bi-mode predictor is to identify the 202 * atypical case when a branch deviates from its bias. 203 */ 204 if (history->finalPred == history->takenUsed) { 205 if (taken) { 206 choiceCounters[choiceHistoryIdx]++; 207 } else { 208 choiceCounters[choiceHistoryIdx]--; 209 } 210 } 211 } else { 212 // always update the choice predictor on an incorrect prediction 213 if (taken) { 214 choiceCounters[choiceHistoryIdx]++; 215 } else { 216 choiceCounters[choiceHistoryIdx]--; 217 } 218 } 219 220 delete history; 221} 222 223void 224BiModeBP::updateGlobalHistReg(ThreadID tid, bool taken) 225{ 226 globalHistoryReg[tid] = taken ? (globalHistoryReg[tid] << 1) | 1 : 227 (globalHistoryReg[tid] << 1); 228 globalHistoryReg[tid] &= historyRegisterMask; 229} 230 231BiModeBP* 232BiModeBPParams::create() 233{ 234 return new BiModeBP(this); 235} 236