bi_mode.cc revision 11429
12810Srdreslin@umich.edu/* 212665Snikos.nikoleris@arm.com * Copyright (c) 2014 The Regents of The University of Michigan 39796Sprakash.ramrakhyani@arm.com * All rights reserved. 49796Sprakash.ramrakhyani@arm.com * 59796Sprakash.ramrakhyani@arm.com * Redistribution and use in source and binary forms, with or without 69796Sprakash.ramrakhyani@arm.com * modification, are permitted provided that the following conditions are 79796Sprakash.ramrakhyani@arm.com * met: redistributions of source code must retain the above copyright 89796Sprakash.ramrakhyani@arm.com * notice, this list of conditions and the following disclaimer; 99796Sprakash.ramrakhyani@arm.com * redistributions in binary form must reproduce the above copyright 109796Sprakash.ramrakhyani@arm.com * notice, this list of conditions and the following disclaimer in the 119796Sprakash.ramrakhyani@arm.com * documentation and/or other materials provided with the distribution; 129796Sprakash.ramrakhyani@arm.com * neither the name of the copyright holders nor the names of its 139796Sprakash.ramrakhyani@arm.com * contributors may be used to endorse or promote products derived from 142810Srdreslin@umich.edu * this software without specific prior written permission. 152810Srdreslin@umich.edu * 162810Srdreslin@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172810Srdreslin@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182810Srdreslin@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192810Srdreslin@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202810Srdreslin@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212810Srdreslin@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222810Srdreslin@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232810Srdreslin@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242810Srdreslin@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252810Srdreslin@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262810Srdreslin@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272810Srdreslin@umich.edu * 282810Srdreslin@umich.edu * Authors: Anthony Gutierrez 292810Srdreslin@umich.edu */ 302810Srdreslin@umich.edu 312810Srdreslin@umich.edu/* @file 322810Srdreslin@umich.edu * Implementation of a bi-mode branch predictor 332810Srdreslin@umich.edu */ 342810Srdreslin@umich.edu 352810Srdreslin@umich.edu#include "base/bitfield.hh" 362810Srdreslin@umich.edu#include "base/intmath.hh" 372810Srdreslin@umich.edu#include "cpu/pred/bi_mode.hh" 382810Srdreslin@umich.edu 392810Srdreslin@umich.eduBiModeBP::BiModeBP(const BiModeBPParams *params) 402810Srdreslin@umich.edu : BPredUnit(params), 4112665Snikos.nikoleris@arm.com globalHistoryReg(0), 422810Srdreslin@umich.edu globalHistoryBits(ceilLog2(params->globalPredictorSize)), 432810Srdreslin@umich.edu choicePredictorSize(params->choicePredictorSize), 442810Srdreslin@umich.edu choiceCtrBits(params->choiceCtrBits), 452810Srdreslin@umich.edu globalPredictorSize(params->globalPredictorSize), 462810Srdreslin@umich.edu globalCtrBits(params->globalCtrBits) 472810Srdreslin@umich.edu{ 482810Srdreslin@umich.edu if (!isPowerOf2(choicePredictorSize)) 4911486Snikos.nikoleris@arm.com fatal("Invalid choice predictor size.\n"); 5011486Snikos.nikoleris@arm.com if (!isPowerOf2(globalPredictorSize)) 516216Snate@binkert.org fatal("Invalid global history predictor size.\n"); 522810Srdreslin@umich.edu 532810Srdreslin@umich.edu choiceCounters.resize(choicePredictorSize); 542810Srdreslin@umich.edu takenCounters.resize(globalPredictorSize); 5512334Sgabeblack@google.com notTakenCounters.resize(globalPredictorSize); 562810Srdreslin@umich.edu 579796Sprakash.ramrakhyani@arm.com for (int i = 0; i < choicePredictorSize; ++i) { 5812665Snikos.nikoleris@arm.com choiceCounters[i].setBits(choiceCtrBits); 5912665Snikos.nikoleris@arm.com } 6012665Snikos.nikoleris@arm.com for (int i = 0; i < globalPredictorSize; ++i) { 612810Srdreslin@umich.edu takenCounters[i].setBits(globalCtrBits); 622810Srdreslin@umich.edu notTakenCounters[i].setBits(globalCtrBits); 632810Srdreslin@umich.edu } 642810Srdreslin@umich.edu 652810Srdreslin@umich.edu historyRegisterMask = mask(globalHistoryBits); 662810Srdreslin@umich.edu choiceHistoryMask = choicePredictorSize - 1; 672810Srdreslin@umich.edu globalHistoryMask = globalPredictorSize - 1; 6812665Snikos.nikoleris@arm.com 692810Srdreslin@umich.edu choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 702810Srdreslin@umich.edu takenThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 7111484Snikos.nikoleris@arm.com notTakenThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 722810Srdreslin@umich.edu} 7312665Snikos.nikoleris@arm.com 7412665Snikos.nikoleris@arm.com/* 7512629Sodanrc@yahoo.com.br * For an unconditional branch we set its history such that 762810Srdreslin@umich.edu * everything is set to taken. I.e., its choice predictor 776978SLisa.Hsu@amd.com * chooses the taken array and the taken array predicts taken. 782810Srdreslin@umich.edu */ 792810Srdreslin@umich.eduvoid 8010941Sdavid.guillen@arm.comBiModeBP::uncondBranch(Addr pc, void * &bpHistory) 8110941Sdavid.guillen@arm.com{ 8212629Sodanrc@yahoo.com.br BPHistory *history = new BPHistory; 8312629Sodanrc@yahoo.com.br history->globalHistoryReg = globalHistoryReg; 8412629Sodanrc@yahoo.com.br history->takenUsed = true; 852810Srdreslin@umich.edu history->takenPred = true; 8612665Snikos.nikoleris@arm.com history->notTakenPred = true; 8712665Snikos.nikoleris@arm.com history->finalPred = true; 8812665Snikos.nikoleris@arm.com bpHistory = static_cast<void*>(history); 8912665Snikos.nikoleris@arm.com updateGlobalHistReg(true); 9012665Snikos.nikoleris@arm.com} 9112665Snikos.nikoleris@arm.com 9212665Snikos.nikoleris@arm.comvoid 9312665Snikos.nikoleris@arm.comBiModeBP::squash(void *bpHistory) 9412665Snikos.nikoleris@arm.com{ 952810Srdreslin@umich.edu BPHistory *history = static_cast<BPHistory*>(bpHistory); 962810Srdreslin@umich.edu globalHistoryReg = history->globalHistoryReg; 979086Sandreas.hansson@arm.com 989086Sandreas.hansson@arm.com delete history; 999086Sandreas.hansson@arm.com} 1009086Sandreas.hansson@arm.com 1019086Sandreas.hansson@arm.com/* 1022810Srdreslin@umich.edu * Here we lookup the actual branch prediction. We use the PC to 1039796Sprakash.ramrakhyani@arm.com * identify the bias of a particular branch, which is based on the 1042810Srdreslin@umich.edu * prediction in the choice array. A hash of the global history 1059796Sprakash.ramrakhyani@arm.com * register and a branch's PC is used to index into both the taken 10612665Snikos.nikoleris@arm.com * and not-taken predictors, which both present a prediction. The 1072810Srdreslin@umich.edu * choice array's prediction is used to select between the two 1082810Srdreslin@umich.edu * direction predictors for the final branch prediction. 1092810Srdreslin@umich.edu */ 1102810Srdreslin@umich.edubool 1112810Srdreslin@umich.eduBiModeBP::lookup(Addr branchAddr, void * &bpHistory) 1122810Srdreslin@umich.edu{ 1132810Srdreslin@umich.edu unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 1142810Srdreslin@umich.edu & choiceHistoryMask); 1152810Srdreslin@umich.edu unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 11611484Snikos.nikoleris@arm.com ^ globalHistoryReg) 1172810Srdreslin@umich.edu & globalHistoryMask); 1182810Srdreslin@umich.edu 1192810Srdreslin@umich.edu assert(choiceHistoryIdx < choicePredictorSize); 12010815Sdavid.guillen@arm.com assert(globalHistoryIdx < globalPredictorSize); 1212810Srdreslin@umich.edu 12212566Snikos.nikoleris@arm.com bool choicePrediction = choiceCounters[choiceHistoryIdx].read() 12312636Sodanrc@yahoo.com.br > choiceThreshold; 12412648Sodanrc@yahoo.com.br bool takenGHBPrediction = takenCounters[globalHistoryIdx].read() 12512648Sodanrc@yahoo.com.br > takenThreshold; 12612648Sodanrc@yahoo.com.br bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx].read() 12712636Sodanrc@yahoo.com.br > notTakenThreshold; 12812636Sodanrc@yahoo.com.br bool finalPrediction; 1292810Srdreslin@umich.edu 1302810Srdreslin@umich.edu BPHistory *history = new BPHistory; 13110815Sdavid.guillen@arm.com history->globalHistoryReg = globalHistoryReg; 13211870Snikos.nikoleris@arm.com history->takenUsed = choicePrediction; 13310815Sdavid.guillen@arm.com history->takenPred = takenGHBPrediction; 13411870Snikos.nikoleris@arm.com history->notTakenPred = notTakenGHBPrediction; 13510815Sdavid.guillen@arm.com 13610815Sdavid.guillen@arm.com if (choicePrediction) { 13710815Sdavid.guillen@arm.com finalPrediction = takenGHBPrediction; 13812665Snikos.nikoleris@arm.com } else { 13912665Snikos.nikoleris@arm.com finalPrediction = notTakenGHBPrediction; 1402810Srdreslin@umich.edu } 14112665Snikos.nikoleris@arm.com 1422810Srdreslin@umich.edu history->finalPred = finalPrediction; 1432810Srdreslin@umich.edu bpHistory = static_cast<void*>(history); 1442810Srdreslin@umich.edu updateGlobalHistReg(finalPrediction); 1452810Srdreslin@umich.edu 14611722Ssophiane.senni@gmail.com return finalPrediction; 14711722Ssophiane.senni@gmail.com} 14811722Ssophiane.senni@gmail.com 14911722Ssophiane.senni@gmail.comvoid 15011722Ssophiane.senni@gmail.comBiModeBP::btbUpdate(Addr branchAddr, void * &bpHistory) 15111722Ssophiane.senni@gmail.com{ 15211722Ssophiane.senni@gmail.com globalHistoryReg &= (historyRegisterMask & ~ULL(1)); 15311722Ssophiane.senni@gmail.com} 15411722Ssophiane.senni@gmail.com 15511722Ssophiane.senni@gmail.com/* Only the selected direction predictor will be updated with the final 1562810Srdreslin@umich.edu * outcome; the status of the unselected one will not be altered. The choice 15712665Snikos.nikoleris@arm.com * predictor is always updated with the branch outcome, except when the 15812665Snikos.nikoleris@arm.com * choice is opposite to the branch outcome but the selected counter of 1592810Srdreslin@umich.edu * the direction predictors makes a correct final prediction. 16011722Ssophiane.senni@gmail.com */ 16111722Ssophiane.senni@gmail.comvoid 16211484Snikos.nikoleris@arm.comBiModeBP::update(Addr branchAddr, bool taken, void *bpHistory, bool squashed) 1632810Srdreslin@umich.edu{ 16412665Snikos.nikoleris@arm.com if (bpHistory) { 16512665Snikos.nikoleris@arm.com BPHistory *history = static_cast<BPHistory*>(bpHistory); 1662810Srdreslin@umich.edu 1672810Srdreslin@umich.edu unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 16812665Snikos.nikoleris@arm.com & choiceHistoryMask); 16912665Snikos.nikoleris@arm.com unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 1702810Srdreslin@umich.edu ^ history->globalHistoryReg) 1712810Srdreslin@umich.edu & globalHistoryMask); 1722810Srdreslin@umich.edu 1732810Srdreslin@umich.edu assert(choiceHistoryIdx < choicePredictorSize); 17410815Sdavid.guillen@arm.com assert(globalHistoryIdx < globalPredictorSize); 17510028SGiacomo.Gabrielli@arm.com 1762810Srdreslin@umich.edu if (history->takenUsed) { 1772810Srdreslin@umich.edu // if the taken array's prediction was used, update it 1782810Srdreslin@umich.edu if (taken) { 1792810Srdreslin@umich.edu takenCounters[globalHistoryIdx].increment(); 1802810Srdreslin@umich.edu } else { 1812810Srdreslin@umich.edu takenCounters[globalHistoryIdx].decrement(); 18212676Sodanrc@yahoo.com.br } 1832810Srdreslin@umich.edu } else { 18411484Snikos.nikoleris@arm.com // if the not-taken array's prediction was used, update it 1852810Srdreslin@umich.edu if (taken) { 1862810Srdreslin@umich.edu notTakenCounters[globalHistoryIdx].increment(); 1872810Srdreslin@umich.edu } else { 1882810Srdreslin@umich.edu notTakenCounters[globalHistoryIdx].decrement(); 18910815Sdavid.guillen@arm.com } 19010941Sdavid.guillen@arm.com } 19110941Sdavid.guillen@arm.com 19210941Sdavid.guillen@arm.com if (history->finalPred == taken) { 19310941Sdavid.guillen@arm.com /* If the final prediction matches the actual branch's 19410941Sdavid.guillen@arm.com * outcome and the choice predictor matches the final 19510941Sdavid.guillen@arm.com * outcome, we update the choice predictor, otherwise it 19610941Sdavid.guillen@arm.com * is not updated. While the designers of the bi-mode 19710048Saminfar@gmail.com * predictor don't explicity say why this is done, one 1982810Srdreslin@umich.edu * can infer that it is to preserve the choice predictor's 19912636Sodanrc@yahoo.com.br * bias with respect to the branch being predicted; afterall, 2002810Srdreslin@umich.edu * the whole point of the bi-mode predictor is to identify the 2012810Srdreslin@umich.edu * atypical case when a branch deviates from its bias. 2022810Srdreslin@umich.edu */ 20310815Sdavid.guillen@arm.com if (history->finalPred == history->takenUsed) { 2045717Shsul@eecs.umich.edu if (taken) { 20512636Sodanrc@yahoo.com.br choiceCounters[choiceHistoryIdx].increment(); 20612636Sodanrc@yahoo.com.br } else { 20712636Sodanrc@yahoo.com.br choiceCounters[choiceHistoryIdx].decrement(); 20812665Snikos.nikoleris@arm.com } 20912636Sodanrc@yahoo.com.br } 21012636Sodanrc@yahoo.com.br } else { 21112636Sodanrc@yahoo.com.br // always update the choice predictor on an incorrect prediction 21212636Sodanrc@yahoo.com.br if (taken) { 21312636Sodanrc@yahoo.com.br choiceCounters[choiceHistoryIdx].increment(); 21412636Sodanrc@yahoo.com.br } else { 21512636Sodanrc@yahoo.com.br choiceCounters[choiceHistoryIdx].decrement(); 21612636Sodanrc@yahoo.com.br } 21712636Sodanrc@yahoo.com.br } 2185717Shsul@eecs.umich.edu 2195717Shsul@eecs.umich.edu if (squashed) { 2205717Shsul@eecs.umich.edu if (taken) { 2212810Srdreslin@umich.edu globalHistoryReg = (history->globalHistoryReg << 1) | 1; 2222810Srdreslin@umich.edu } else { 22312648Sodanrc@yahoo.com.br globalHistoryReg = (history->globalHistoryReg << 1); 22412648Sodanrc@yahoo.com.br } 22512665Snikos.nikoleris@arm.com globalHistoryReg &= historyRegisterMask; 22612648Sodanrc@yahoo.com.br } else { 2272810Srdreslin@umich.edu delete history; 22811484Snikos.nikoleris@arm.com } 2292810Srdreslin@umich.edu } 23011484Snikos.nikoleris@arm.com} 23112648Sodanrc@yahoo.com.br 2322810Srdreslin@umich.eduvoid 2332810Srdreslin@umich.eduBiModeBP::retireSquashed(void *bp_history) 2342810Srdreslin@umich.edu{ 2352810Srdreslin@umich.edu BPHistory *history = static_cast<BPHistory*>(bp_history); 23612648Sodanrc@yahoo.com.br delete history; 23712648Sodanrc@yahoo.com.br} 2382810Srdreslin@umich.edu 23911484Snikos.nikoleris@arm.comvoid 2402810Srdreslin@umich.eduBiModeBP::updateGlobalHistReg(bool taken) 2412810Srdreslin@umich.edu{ 24212665Snikos.nikoleris@arm.com globalHistoryReg = taken ? (globalHistoryReg << 1) | 1 : 24312665Snikos.nikoleris@arm.com (globalHistoryReg << 1); 2442810Srdreslin@umich.edu globalHistoryReg &= historyRegisterMask; 2452810Srdreslin@umich.edu} 2462810Srdreslin@umich.edu 24712648Sodanrc@yahoo.com.brBiModeBP* 24812648Sodanrc@yahoo.com.brBiModeBPParams::create() 24912648Sodanrc@yahoo.com.br{ 25012648Sodanrc@yahoo.com.br return new BiModeBP(this); 25112648Sodanrc@yahoo.com.br} 25212665Snikos.nikoleris@arm.com