bi_mode.cc revision 11433
110244Satgutier@umich.edu/* 210244Satgutier@umich.edu * Copyright (c) 2014 The Regents of The University of Michigan 310244Satgutier@umich.edu * All rights reserved. 410244Satgutier@umich.edu * 510244Satgutier@umich.edu * Redistribution and use in source and binary forms, with or without 610244Satgutier@umich.edu * modification, are permitted provided that the following conditions are 710244Satgutier@umich.edu * met: redistributions of source code must retain the above copyright 810244Satgutier@umich.edu * notice, this list of conditions and the following disclaimer; 910244Satgutier@umich.edu * redistributions in binary form must reproduce the above copyright 1010244Satgutier@umich.edu * notice, this list of conditions and the following disclaimer in the 1110244Satgutier@umich.edu * documentation and/or other materials provided with the distribution; 1210244Satgutier@umich.edu * neither the name of the copyright holders nor the names of its 1310244Satgutier@umich.edu * contributors may be used to endorse or promote products derived from 1410244Satgutier@umich.edu * this software without specific prior written permission. 1510244Satgutier@umich.edu * 1610244Satgutier@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1710244Satgutier@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1810244Satgutier@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1910244Satgutier@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2010244Satgutier@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2110244Satgutier@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2210244Satgutier@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2310244Satgutier@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2410244Satgutier@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2510244Satgutier@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2610244Satgutier@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2710244Satgutier@umich.edu * 2810244Satgutier@umich.edu * Authors: Anthony Gutierrez 2910244Satgutier@umich.edu */ 3010244Satgutier@umich.edu 3110244Satgutier@umich.edu/* @file 3210244Satgutier@umich.edu * Implementation of a bi-mode branch predictor 3310244Satgutier@umich.edu */ 3410244Satgutier@umich.edu 3510244Satgutier@umich.edu#include "base/bitfield.hh" 3610244Satgutier@umich.edu#include "base/intmath.hh" 3710244Satgutier@umich.edu#include "cpu/pred/bi_mode.hh" 3810244Satgutier@umich.edu 3910785Sgope@wisc.eduBiModeBP::BiModeBP(const BiModeBPParams *params) 4010785Sgope@wisc.edu : BPredUnit(params), 4111429Sandreas.sandberg@arm.com globalHistoryReg(0), 4210244Satgutier@umich.edu globalHistoryBits(ceilLog2(params->globalPredictorSize)), 4310244Satgutier@umich.edu choicePredictorSize(params->choicePredictorSize), 4410244Satgutier@umich.edu choiceCtrBits(params->choiceCtrBits), 4510244Satgutier@umich.edu globalPredictorSize(params->globalPredictorSize), 4610244Satgutier@umich.edu globalCtrBits(params->globalCtrBits) 4710244Satgutier@umich.edu{ 4810244Satgutier@umich.edu if (!isPowerOf2(choicePredictorSize)) 4910244Satgutier@umich.edu fatal("Invalid choice predictor size.\n"); 5010244Satgutier@umich.edu if (!isPowerOf2(globalPredictorSize)) 5110244Satgutier@umich.edu fatal("Invalid global history predictor size.\n"); 5210244Satgutier@umich.edu 5310244Satgutier@umich.edu choiceCounters.resize(choicePredictorSize); 5410244Satgutier@umich.edu takenCounters.resize(globalPredictorSize); 5510244Satgutier@umich.edu notTakenCounters.resize(globalPredictorSize); 5610244Satgutier@umich.edu 5710244Satgutier@umich.edu for (int i = 0; i < choicePredictorSize; ++i) { 5810244Satgutier@umich.edu choiceCounters[i].setBits(choiceCtrBits); 5910244Satgutier@umich.edu } 6010244Satgutier@umich.edu for (int i = 0; i < globalPredictorSize; ++i) { 6110244Satgutier@umich.edu takenCounters[i].setBits(globalCtrBits); 6210244Satgutier@umich.edu notTakenCounters[i].setBits(globalCtrBits); 6310244Satgutier@umich.edu } 6410244Satgutier@umich.edu 6510244Satgutier@umich.edu historyRegisterMask = mask(globalHistoryBits); 6610244Satgutier@umich.edu choiceHistoryMask = choicePredictorSize - 1; 6710244Satgutier@umich.edu globalHistoryMask = globalPredictorSize - 1; 6810244Satgutier@umich.edu 6910244Satgutier@umich.edu choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 7010244Satgutier@umich.edu takenThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 7110244Satgutier@umich.edu notTakenThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 7210244Satgutier@umich.edu} 7310244Satgutier@umich.edu 7410244Satgutier@umich.edu/* 7510244Satgutier@umich.edu * For an unconditional branch we set its history such that 7610244Satgutier@umich.edu * everything is set to taken. I.e., its choice predictor 7710244Satgutier@umich.edu * chooses the taken array and the taken array predicts taken. 7810244Satgutier@umich.edu */ 7910244Satgutier@umich.eduvoid 8011429Sandreas.sandberg@arm.comBiModeBP::uncondBranch(Addr pc, void * &bpHistory) 8110244Satgutier@umich.edu{ 8210244Satgutier@umich.edu BPHistory *history = new BPHistory; 8311429Sandreas.sandberg@arm.com history->globalHistoryReg = globalHistoryReg; 8410244Satgutier@umich.edu history->takenUsed = true; 8510244Satgutier@umich.edu history->takenPred = true; 8610244Satgutier@umich.edu history->notTakenPred = true; 8710244Satgutier@umich.edu history->finalPred = true; 8810244Satgutier@umich.edu bpHistory = static_cast<void*>(history); 8911429Sandreas.sandberg@arm.com updateGlobalHistReg(true); 9010244Satgutier@umich.edu} 9110244Satgutier@umich.edu 9210244Satgutier@umich.eduvoid 9311429Sandreas.sandberg@arm.comBiModeBP::squash(void *bpHistory) 9410244Satgutier@umich.edu{ 9510244Satgutier@umich.edu BPHistory *history = static_cast<BPHistory*>(bpHistory); 9611429Sandreas.sandberg@arm.com globalHistoryReg = history->globalHistoryReg; 9710244Satgutier@umich.edu 9810244Satgutier@umich.edu delete history; 9910244Satgutier@umich.edu} 10010244Satgutier@umich.edu 10110244Satgutier@umich.edu/* 10210244Satgutier@umich.edu * Here we lookup the actual branch prediction. We use the PC to 10310244Satgutier@umich.edu * identify the bias of a particular branch, which is based on the 10410244Satgutier@umich.edu * prediction in the choice array. A hash of the global history 10510244Satgutier@umich.edu * register and a branch's PC is used to index into both the taken 10610244Satgutier@umich.edu * and not-taken predictors, which both present a prediction. The 10710244Satgutier@umich.edu * choice array's prediction is used to select between the two 10810244Satgutier@umich.edu * direction predictors for the final branch prediction. 10910244Satgutier@umich.edu */ 11010244Satgutier@umich.edubool 11111429Sandreas.sandberg@arm.comBiModeBP::lookup(Addr branchAddr, void * &bpHistory) 11210244Satgutier@umich.edu{ 11310244Satgutier@umich.edu unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 11410244Satgutier@umich.edu & choiceHistoryMask); 11510244Satgutier@umich.edu unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 11611429Sandreas.sandberg@arm.com ^ globalHistoryReg) 11710244Satgutier@umich.edu & globalHistoryMask); 11810244Satgutier@umich.edu 11910244Satgutier@umich.edu assert(choiceHistoryIdx < choicePredictorSize); 12010244Satgutier@umich.edu assert(globalHistoryIdx < globalPredictorSize); 12110244Satgutier@umich.edu 12210244Satgutier@umich.edu bool choicePrediction = choiceCounters[choiceHistoryIdx].read() 12310244Satgutier@umich.edu > choiceThreshold; 12410244Satgutier@umich.edu bool takenGHBPrediction = takenCounters[globalHistoryIdx].read() 12510244Satgutier@umich.edu > takenThreshold; 12610244Satgutier@umich.edu bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx].read() 12710244Satgutier@umich.edu > notTakenThreshold; 12810244Satgutier@umich.edu bool finalPrediction; 12910244Satgutier@umich.edu 13010244Satgutier@umich.edu BPHistory *history = new BPHistory; 13111429Sandreas.sandberg@arm.com history->globalHistoryReg = globalHistoryReg; 13210244Satgutier@umich.edu history->takenUsed = choicePrediction; 13310244Satgutier@umich.edu history->takenPred = takenGHBPrediction; 13410244Satgutier@umich.edu history->notTakenPred = notTakenGHBPrediction; 13510244Satgutier@umich.edu 13610244Satgutier@umich.edu if (choicePrediction) { 13710244Satgutier@umich.edu finalPrediction = takenGHBPrediction; 13810244Satgutier@umich.edu } else { 13910244Satgutier@umich.edu finalPrediction = notTakenGHBPrediction; 14010244Satgutier@umich.edu } 14110244Satgutier@umich.edu 14210244Satgutier@umich.edu history->finalPred = finalPrediction; 14310244Satgutier@umich.edu bpHistory = static_cast<void*>(history); 14411429Sandreas.sandberg@arm.com updateGlobalHistReg(finalPrediction); 14510244Satgutier@umich.edu 14610244Satgutier@umich.edu return finalPrediction; 14710244Satgutier@umich.edu} 14810244Satgutier@umich.edu 14910244Satgutier@umich.eduvoid 15011429Sandreas.sandberg@arm.comBiModeBP::btbUpdate(Addr branchAddr, void * &bpHistory) 15110244Satgutier@umich.edu{ 15211429Sandreas.sandberg@arm.com globalHistoryReg &= (historyRegisterMask & ~ULL(1)); 15310244Satgutier@umich.edu} 15410244Satgutier@umich.edu 15510244Satgutier@umich.edu/* Only the selected direction predictor will be updated with the final 15610244Satgutier@umich.edu * outcome; the status of the unselected one will not be altered. The choice 15710244Satgutier@umich.edu * predictor is always updated with the branch outcome, except when the 15810244Satgutier@umich.edu * choice is opposite to the branch outcome but the selected counter of 15910244Satgutier@umich.edu * the direction predictors makes a correct final prediction. 16010244Satgutier@umich.edu */ 16110244Satgutier@umich.eduvoid 16211429Sandreas.sandberg@arm.comBiModeBP::update(Addr branchAddr, bool taken, void *bpHistory, bool squashed) 16310244Satgutier@umich.edu{ 16410244Satgutier@umich.edu if (bpHistory) { 16510244Satgutier@umich.edu BPHistory *history = static_cast<BPHistory*>(bpHistory); 16610244Satgutier@umich.edu 16710244Satgutier@umich.edu unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 16810244Satgutier@umich.edu & choiceHistoryMask); 16910244Satgutier@umich.edu unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 17010335Sdam.sunwoo@arm.com ^ history->globalHistoryReg) 17110244Satgutier@umich.edu & globalHistoryMask); 17210244Satgutier@umich.edu 17310244Satgutier@umich.edu assert(choiceHistoryIdx < choicePredictorSize); 17410244Satgutier@umich.edu assert(globalHistoryIdx < globalPredictorSize); 17510244Satgutier@umich.edu 17610244Satgutier@umich.edu if (history->takenUsed) { 17710244Satgutier@umich.edu // if the taken array's prediction was used, update it 17810244Satgutier@umich.edu if (taken) { 17910244Satgutier@umich.edu takenCounters[globalHistoryIdx].increment(); 18010244Satgutier@umich.edu } else { 18110244Satgutier@umich.edu takenCounters[globalHistoryIdx].decrement(); 18210244Satgutier@umich.edu } 18310244Satgutier@umich.edu } else { 18410244Satgutier@umich.edu // if the not-taken array's prediction was used, update it 18510244Satgutier@umich.edu if (taken) { 18610244Satgutier@umich.edu notTakenCounters[globalHistoryIdx].increment(); 18710244Satgutier@umich.edu } else { 18810244Satgutier@umich.edu notTakenCounters[globalHistoryIdx].decrement(); 18910244Satgutier@umich.edu } 19010244Satgutier@umich.edu } 19110244Satgutier@umich.edu 19210244Satgutier@umich.edu if (history->finalPred == taken) { 19310244Satgutier@umich.edu /* If the final prediction matches the actual branch's 19410244Satgutier@umich.edu * outcome and the choice predictor matches the final 19510244Satgutier@umich.edu * outcome, we update the choice predictor, otherwise it 19610244Satgutier@umich.edu * is not updated. While the designers of the bi-mode 19710244Satgutier@umich.edu * predictor don't explicity say why this is done, one 19810244Satgutier@umich.edu * can infer that it is to preserve the choice predictor's 19910244Satgutier@umich.edu * bias with respect to the branch being predicted; afterall, 20010244Satgutier@umich.edu * the whole point of the bi-mode predictor is to identify the 20110244Satgutier@umich.edu * atypical case when a branch deviates from its bias. 20210244Satgutier@umich.edu */ 20310244Satgutier@umich.edu if (history->finalPred == history->takenUsed) { 20410244Satgutier@umich.edu if (taken) { 20510244Satgutier@umich.edu choiceCounters[choiceHistoryIdx].increment(); 20610244Satgutier@umich.edu } else { 20710244Satgutier@umich.edu choiceCounters[choiceHistoryIdx].decrement(); 20810244Satgutier@umich.edu } 20910244Satgutier@umich.edu } 21010244Satgutier@umich.edu } else { 21110244Satgutier@umich.edu // always update the choice predictor on an incorrect prediction 21210244Satgutier@umich.edu if (taken) { 21310244Satgutier@umich.edu choiceCounters[choiceHistoryIdx].increment(); 21410244Satgutier@umich.edu } else { 21510244Satgutier@umich.edu choiceCounters[choiceHistoryIdx].decrement(); 21610244Satgutier@umich.edu } 21710244Satgutier@umich.edu } 21810244Satgutier@umich.edu 21910244Satgutier@umich.edu if (squashed) { 22010244Satgutier@umich.edu if (taken) { 22111429Sandreas.sandberg@arm.com globalHistoryReg = (history->globalHistoryReg << 1) | 1; 22210244Satgutier@umich.edu } else { 22311429Sandreas.sandberg@arm.com globalHistoryReg = (history->globalHistoryReg << 1); 22410244Satgutier@umich.edu } 22511429Sandreas.sandberg@arm.com globalHistoryReg &= historyRegisterMask; 22610244Satgutier@umich.edu } else { 22710244Satgutier@umich.edu delete history; 22810244Satgutier@umich.edu } 22910244Satgutier@umich.edu } 23010244Satgutier@umich.edu} 23110244Satgutier@umich.edu 23210244Satgutier@umich.eduvoid 23311429Sandreas.sandberg@arm.comBiModeBP::retireSquashed(void *bp_history) 23410244Satgutier@umich.edu{ 23510244Satgutier@umich.edu BPHistory *history = static_cast<BPHistory*>(bp_history); 23610244Satgutier@umich.edu delete history; 23710244Satgutier@umich.edu} 23810244Satgutier@umich.edu 23911433Smitch.hayenga@arm.comunsigned 24011433Smitch.hayenga@arm.comBiModeBP::getGHR(void *bp_history) const 24111433Smitch.hayenga@arm.com{ 24211433Smitch.hayenga@arm.com return static_cast<BPHistory*>(bp_history)->globalHistoryReg; 24311433Smitch.hayenga@arm.com} 24411433Smitch.hayenga@arm.com 24511429Sandreas.sandberg@arm.comvoid 24611429Sandreas.sandberg@arm.comBiModeBP::updateGlobalHistReg(bool taken) 24711426Smitch.hayenga@arm.com{ 24811429Sandreas.sandberg@arm.com globalHistoryReg = taken ? (globalHistoryReg << 1) | 1 : 24911429Sandreas.sandberg@arm.com (globalHistoryReg << 1); 25011429Sandreas.sandberg@arm.com globalHistoryReg &= historyRegisterMask; 25110244Satgutier@umich.edu} 25210785Sgope@wisc.edu 25310785Sgope@wisc.eduBiModeBP* 25410785Sgope@wisc.eduBiModeBPParams::create() 25510785Sgope@wisc.edu{ 25610785Sgope@wisc.edu return new BiModeBP(this); 25710785Sgope@wisc.edu} 258