bi_mode.cc revision 11434
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), 4111434Smitch.hayenga@arm.com globalHistoryReg(params->numThreads, 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 8011434Smitch.hayenga@arm.comBiModeBP::uncondBranch(ThreadID tid, Addr pc, void * &bpHistory) 8110244Satgutier@umich.edu{ 8210244Satgutier@umich.edu BPHistory *history = new BPHistory; 8311434Smitch.hayenga@arm.com history->globalHistoryReg = globalHistoryReg[tid]; 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); 8911434Smitch.hayenga@arm.com updateGlobalHistReg(tid, true); 9010244Satgutier@umich.edu} 9110244Satgutier@umich.edu 9210244Satgutier@umich.eduvoid 9311434Smitch.hayenga@arm.comBiModeBP::squash(ThreadID tid, void *bpHistory) 9410244Satgutier@umich.edu{ 9510244Satgutier@umich.edu BPHistory *history = static_cast<BPHistory*>(bpHistory); 9611434Smitch.hayenga@arm.com globalHistoryReg[tid] = 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 11111434Smitch.hayenga@arm.comBiModeBP::lookup(ThreadID tid, 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) 11611434Smitch.hayenga@arm.com ^ globalHistoryReg[tid]) 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; 13111434Smitch.hayenga@arm.com history->globalHistoryReg = globalHistoryReg[tid]; 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); 14411434Smitch.hayenga@arm.com updateGlobalHistReg(tid, finalPrediction); 14510244Satgutier@umich.edu 14610244Satgutier@umich.edu return finalPrediction; 14710244Satgutier@umich.edu} 14810244Satgutier@umich.edu 14910244Satgutier@umich.eduvoid 15011434Smitch.hayenga@arm.comBiModeBP::btbUpdate(ThreadID tid, Addr branchAddr, void * &bpHistory) 15110244Satgutier@umich.edu{ 15211434Smitch.hayenga@arm.com globalHistoryReg[tid] &= (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 16211434Smitch.hayenga@arm.comBiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory, 16311434Smitch.hayenga@arm.com bool squashed) 16410244Satgutier@umich.edu{ 16510244Satgutier@umich.edu if (bpHistory) { 16610244Satgutier@umich.edu BPHistory *history = static_cast<BPHistory*>(bpHistory); 16710244Satgutier@umich.edu 16810244Satgutier@umich.edu unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 16910244Satgutier@umich.edu & choiceHistoryMask); 17010244Satgutier@umich.edu unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 17110335Sdam.sunwoo@arm.com ^ history->globalHistoryReg) 17210244Satgutier@umich.edu & globalHistoryMask); 17310244Satgutier@umich.edu 17410244Satgutier@umich.edu assert(choiceHistoryIdx < choicePredictorSize); 17510244Satgutier@umich.edu assert(globalHistoryIdx < globalPredictorSize); 17610244Satgutier@umich.edu 17710244Satgutier@umich.edu if (history->takenUsed) { 17810244Satgutier@umich.edu // if the taken array's prediction was used, update it 17910244Satgutier@umich.edu if (taken) { 18010244Satgutier@umich.edu takenCounters[globalHistoryIdx].increment(); 18110244Satgutier@umich.edu } else { 18210244Satgutier@umich.edu takenCounters[globalHistoryIdx].decrement(); 18310244Satgutier@umich.edu } 18410244Satgutier@umich.edu } else { 18510244Satgutier@umich.edu // if the not-taken array's prediction was used, update it 18610244Satgutier@umich.edu if (taken) { 18710244Satgutier@umich.edu notTakenCounters[globalHistoryIdx].increment(); 18810244Satgutier@umich.edu } else { 18910244Satgutier@umich.edu notTakenCounters[globalHistoryIdx].decrement(); 19010244Satgutier@umich.edu } 19110244Satgutier@umich.edu } 19210244Satgutier@umich.edu 19310244Satgutier@umich.edu if (history->finalPred == taken) { 19410244Satgutier@umich.edu /* If the final prediction matches the actual branch's 19510244Satgutier@umich.edu * outcome and the choice predictor matches the final 19610244Satgutier@umich.edu * outcome, we update the choice predictor, otherwise it 19710244Satgutier@umich.edu * is not updated. While the designers of the bi-mode 19810244Satgutier@umich.edu * predictor don't explicity say why this is done, one 19910244Satgutier@umich.edu * can infer that it is to preserve the choice predictor's 20010244Satgutier@umich.edu * bias with respect to the branch being predicted; afterall, 20110244Satgutier@umich.edu * the whole point of the bi-mode predictor is to identify the 20210244Satgutier@umich.edu * atypical case when a branch deviates from its bias. 20310244Satgutier@umich.edu */ 20410244Satgutier@umich.edu if (history->finalPred == history->takenUsed) { 20510244Satgutier@umich.edu if (taken) { 20610244Satgutier@umich.edu choiceCounters[choiceHistoryIdx].increment(); 20710244Satgutier@umich.edu } else { 20810244Satgutier@umich.edu choiceCounters[choiceHistoryIdx].decrement(); 20910244Satgutier@umich.edu } 21010244Satgutier@umich.edu } 21110244Satgutier@umich.edu } else { 21210244Satgutier@umich.edu // always update the choice predictor on an incorrect prediction 21310244Satgutier@umich.edu if (taken) { 21410244Satgutier@umich.edu choiceCounters[choiceHistoryIdx].increment(); 21510244Satgutier@umich.edu } else { 21610244Satgutier@umich.edu choiceCounters[choiceHistoryIdx].decrement(); 21710244Satgutier@umich.edu } 21810244Satgutier@umich.edu } 21910244Satgutier@umich.edu 22010244Satgutier@umich.edu if (squashed) { 22110244Satgutier@umich.edu if (taken) { 22211434Smitch.hayenga@arm.com globalHistoryReg[tid] = (history->globalHistoryReg << 1) | 1; 22310244Satgutier@umich.edu } else { 22411434Smitch.hayenga@arm.com globalHistoryReg[tid] = (history->globalHistoryReg << 1); 22510244Satgutier@umich.edu } 22611434Smitch.hayenga@arm.com globalHistoryReg[tid] &= historyRegisterMask; 22710244Satgutier@umich.edu } else { 22810244Satgutier@umich.edu delete history; 22910244Satgutier@umich.edu } 23010244Satgutier@umich.edu } 23110244Satgutier@umich.edu} 23210244Satgutier@umich.edu 23310244Satgutier@umich.eduvoid 23411434Smitch.hayenga@arm.comBiModeBP::retireSquashed(ThreadID tid, void *bp_history) 23510244Satgutier@umich.edu{ 23610244Satgutier@umich.edu BPHistory *history = static_cast<BPHistory*>(bp_history); 23710244Satgutier@umich.edu delete history; 23810244Satgutier@umich.edu} 23910244Satgutier@umich.edu 24011433Smitch.hayenga@arm.comunsigned 24111434Smitch.hayenga@arm.comBiModeBP::getGHR(ThreadID tid, void *bp_history) const 24211433Smitch.hayenga@arm.com{ 24311433Smitch.hayenga@arm.com return static_cast<BPHistory*>(bp_history)->globalHistoryReg; 24411433Smitch.hayenga@arm.com} 24511433Smitch.hayenga@arm.com 24611429Sandreas.sandberg@arm.comvoid 24711434Smitch.hayenga@arm.comBiModeBP::updateGlobalHistReg(ThreadID tid, bool taken) 24811426Smitch.hayenga@arm.com{ 24911434Smitch.hayenga@arm.com globalHistoryReg[tid] = taken ? (globalHistoryReg[tid] << 1) | 1 : 25011434Smitch.hayenga@arm.com (globalHistoryReg[tid] << 1); 25111434Smitch.hayenga@arm.com globalHistoryReg[tid] &= historyRegisterMask; 25210244Satgutier@umich.edu} 25310785Sgope@wisc.edu 25410785Sgope@wisc.eduBiModeBP* 25510785Sgope@wisc.eduBiModeBPParams::create() 25610785Sgope@wisc.edu{ 25710785Sgope@wisc.edu return new BiModeBP(this); 25810785Sgope@wisc.edu} 259