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 3511793Sbrandon.potter@amd.com#include "cpu/pred/bi_mode.hh" 3611793Sbrandon.potter@amd.com 3710244Satgutier@umich.edu#include "base/bitfield.hh" 3810244Satgutier@umich.edu#include "base/intmath.hh" 3910244Satgutier@umich.edu 4010785Sgope@wisc.eduBiModeBP::BiModeBP(const BiModeBPParams *params) 4110785Sgope@wisc.edu : BPredUnit(params), 4211434Smitch.hayenga@arm.com globalHistoryReg(params->numThreads, 0), 4310244Satgutier@umich.edu globalHistoryBits(ceilLog2(params->globalPredictorSize)), 4410244Satgutier@umich.edu choicePredictorSize(params->choicePredictorSize), 4510244Satgutier@umich.edu choiceCtrBits(params->choiceCtrBits), 4610244Satgutier@umich.edu globalPredictorSize(params->globalPredictorSize), 4713959Sodanrc@yahoo.com.br globalCtrBits(params->globalCtrBits), 4813959Sodanrc@yahoo.com.br choiceCounters(choicePredictorSize, SatCounter(choiceCtrBits)), 4913959Sodanrc@yahoo.com.br takenCounters(globalPredictorSize, SatCounter(globalCtrBits)), 5013959Sodanrc@yahoo.com.br notTakenCounters(globalPredictorSize, SatCounter(globalCtrBits)) 5110244Satgutier@umich.edu{ 5210244Satgutier@umich.edu if (!isPowerOf2(choicePredictorSize)) 5310244Satgutier@umich.edu fatal("Invalid choice predictor size.\n"); 5410244Satgutier@umich.edu if (!isPowerOf2(globalPredictorSize)) 5510244Satgutier@umich.edu fatal("Invalid global history predictor size.\n"); 5610244Satgutier@umich.edu 5710244Satgutier@umich.edu historyRegisterMask = mask(globalHistoryBits); 5810244Satgutier@umich.edu choiceHistoryMask = choicePredictorSize - 1; 5910244Satgutier@umich.edu globalHistoryMask = globalPredictorSize - 1; 6010244Satgutier@umich.edu 6110244Satgutier@umich.edu choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 6212180Srico.amslinger@informatik.uni-augsburg.de takenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1; 6312180Srico.amslinger@informatik.uni-augsburg.de notTakenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1; 6410244Satgutier@umich.edu} 6510244Satgutier@umich.edu 6610244Satgutier@umich.edu/* 6710244Satgutier@umich.edu * For an unconditional branch we set its history such that 6810244Satgutier@umich.edu * everything is set to taken. I.e., its choice predictor 6910244Satgutier@umich.edu * chooses the taken array and the taken array predicts taken. 7010244Satgutier@umich.edu */ 7110244Satgutier@umich.eduvoid 7211434Smitch.hayenga@arm.comBiModeBP::uncondBranch(ThreadID tid, Addr pc, void * &bpHistory) 7310244Satgutier@umich.edu{ 7410244Satgutier@umich.edu BPHistory *history = new BPHistory; 7511434Smitch.hayenga@arm.com history->globalHistoryReg = globalHistoryReg[tid]; 7610244Satgutier@umich.edu history->takenUsed = true; 7710244Satgutier@umich.edu history->takenPred = true; 7810244Satgutier@umich.edu history->notTakenPred = true; 7910244Satgutier@umich.edu history->finalPred = true; 8010244Satgutier@umich.edu bpHistory = static_cast<void*>(history); 8111434Smitch.hayenga@arm.com updateGlobalHistReg(tid, true); 8210244Satgutier@umich.edu} 8310244Satgutier@umich.edu 8410244Satgutier@umich.eduvoid 8511434Smitch.hayenga@arm.comBiModeBP::squash(ThreadID tid, void *bpHistory) 8610244Satgutier@umich.edu{ 8710244Satgutier@umich.edu BPHistory *history = static_cast<BPHistory*>(bpHistory); 8811434Smitch.hayenga@arm.com globalHistoryReg[tid] = history->globalHistoryReg; 8910244Satgutier@umich.edu 9010244Satgutier@umich.edu delete history; 9110244Satgutier@umich.edu} 9210244Satgutier@umich.edu 9310244Satgutier@umich.edu/* 9410244Satgutier@umich.edu * Here we lookup the actual branch prediction. We use the PC to 9510244Satgutier@umich.edu * identify the bias of a particular branch, which is based on the 9610244Satgutier@umich.edu * prediction in the choice array. A hash of the global history 9710244Satgutier@umich.edu * register and a branch's PC is used to index into both the taken 9810244Satgutier@umich.edu * and not-taken predictors, which both present a prediction. The 9910244Satgutier@umich.edu * choice array's prediction is used to select between the two 10010244Satgutier@umich.edu * direction predictors for the final branch prediction. 10110244Satgutier@umich.edu */ 10210244Satgutier@umich.edubool 10311434Smitch.hayenga@arm.comBiModeBP::lookup(ThreadID tid, Addr branchAddr, void * &bpHistory) 10410244Satgutier@umich.edu{ 10510244Satgutier@umich.edu unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 10610244Satgutier@umich.edu & choiceHistoryMask); 10710244Satgutier@umich.edu unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 10811434Smitch.hayenga@arm.com ^ globalHistoryReg[tid]) 10910244Satgutier@umich.edu & globalHistoryMask); 11010244Satgutier@umich.edu 11110244Satgutier@umich.edu assert(choiceHistoryIdx < choicePredictorSize); 11210244Satgutier@umich.edu assert(globalHistoryIdx < globalPredictorSize); 11310244Satgutier@umich.edu 11413959Sodanrc@yahoo.com.br bool choicePrediction = choiceCounters[choiceHistoryIdx] 11510244Satgutier@umich.edu > choiceThreshold; 11613959Sodanrc@yahoo.com.br bool takenGHBPrediction = takenCounters[globalHistoryIdx] 11710244Satgutier@umich.edu > takenThreshold; 11813959Sodanrc@yahoo.com.br bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx] 11910244Satgutier@umich.edu > notTakenThreshold; 12010244Satgutier@umich.edu bool finalPrediction; 12110244Satgutier@umich.edu 12210244Satgutier@umich.edu BPHistory *history = new BPHistory; 12311434Smitch.hayenga@arm.com history->globalHistoryReg = globalHistoryReg[tid]; 12410244Satgutier@umich.edu history->takenUsed = choicePrediction; 12510244Satgutier@umich.edu history->takenPred = takenGHBPrediction; 12610244Satgutier@umich.edu history->notTakenPred = notTakenGHBPrediction; 12710244Satgutier@umich.edu 12810244Satgutier@umich.edu if (choicePrediction) { 12910244Satgutier@umich.edu finalPrediction = takenGHBPrediction; 13010244Satgutier@umich.edu } else { 13110244Satgutier@umich.edu finalPrediction = notTakenGHBPrediction; 13210244Satgutier@umich.edu } 13310244Satgutier@umich.edu 13410244Satgutier@umich.edu history->finalPred = finalPrediction; 13510244Satgutier@umich.edu bpHistory = static_cast<void*>(history); 13611434Smitch.hayenga@arm.com updateGlobalHistReg(tid, finalPrediction); 13710244Satgutier@umich.edu 13810244Satgutier@umich.edu return finalPrediction; 13910244Satgutier@umich.edu} 14010244Satgutier@umich.edu 14110244Satgutier@umich.eduvoid 14211434Smitch.hayenga@arm.comBiModeBP::btbUpdate(ThreadID tid, Addr branchAddr, void * &bpHistory) 14310244Satgutier@umich.edu{ 14411434Smitch.hayenga@arm.com globalHistoryReg[tid] &= (historyRegisterMask & ~ULL(1)); 14510244Satgutier@umich.edu} 14610244Satgutier@umich.edu 14710244Satgutier@umich.edu/* Only the selected direction predictor will be updated with the final 14810244Satgutier@umich.edu * outcome; the status of the unselected one will not be altered. The choice 14910244Satgutier@umich.edu * predictor is always updated with the branch outcome, except when the 15010244Satgutier@umich.edu * choice is opposite to the branch outcome but the selected counter of 15110244Satgutier@umich.edu * the direction predictors makes a correct final prediction. 15210244Satgutier@umich.edu */ 15310244Satgutier@umich.eduvoid 15411434Smitch.hayenga@arm.comBiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory, 15513626Sjairo.balart@metempsy.com bool squashed, const StaticInstPtr & inst, Addr corrTarget) 15610244Satgutier@umich.edu{ 15711783Sarthur.perais@inria.fr assert(bpHistory); 15810244Satgutier@umich.edu 15911783Sarthur.perais@inria.fr BPHistory *history = static_cast<BPHistory*>(bpHistory); 16010244Satgutier@umich.edu 16111783Sarthur.perais@inria.fr // We do not update the counters speculatively on a squash. 16211783Sarthur.perais@inria.fr // We just restore the global history register. 16311783Sarthur.perais@inria.fr if (squashed) { 16411783Sarthur.perais@inria.fr globalHistoryReg[tid] = (history->globalHistoryReg << 1) | taken; 16511783Sarthur.perais@inria.fr return; 16611783Sarthur.perais@inria.fr } 16710244Satgutier@umich.edu 16811783Sarthur.perais@inria.fr unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 16911783Sarthur.perais@inria.fr & choiceHistoryMask); 17011783Sarthur.perais@inria.fr unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 17111783Sarthur.perais@inria.fr ^ history->globalHistoryReg) 17211783Sarthur.perais@inria.fr & globalHistoryMask); 17311783Sarthur.perais@inria.fr 17411783Sarthur.perais@inria.fr assert(choiceHistoryIdx < choicePredictorSize); 17511783Sarthur.perais@inria.fr assert(globalHistoryIdx < globalPredictorSize); 17611783Sarthur.perais@inria.fr 17711783Sarthur.perais@inria.fr if (history->takenUsed) { 17811783Sarthur.perais@inria.fr // if the taken array's prediction was used, update it 17911783Sarthur.perais@inria.fr if (taken) { 18013959Sodanrc@yahoo.com.br takenCounters[globalHistoryIdx]++; 18110244Satgutier@umich.edu } else { 18213959Sodanrc@yahoo.com.br takenCounters[globalHistoryIdx]--; 18310244Satgutier@umich.edu } 18411783Sarthur.perais@inria.fr } else { 18511783Sarthur.perais@inria.fr // if the not-taken array's prediction was used, update it 18611783Sarthur.perais@inria.fr if (taken) { 18713959Sodanrc@yahoo.com.br notTakenCounters[globalHistoryIdx]++; 18811783Sarthur.perais@inria.fr } else { 18913959Sodanrc@yahoo.com.br notTakenCounters[globalHistoryIdx]--; 19011783Sarthur.perais@inria.fr } 19111783Sarthur.perais@inria.fr } 19210244Satgutier@umich.edu 19311783Sarthur.perais@inria.fr if (history->finalPred == taken) { 19411783Sarthur.perais@inria.fr /* If the final prediction matches the actual branch's 19511783Sarthur.perais@inria.fr * outcome and the choice predictor matches the final 19611783Sarthur.perais@inria.fr * outcome, we update the choice predictor, otherwise it 19711783Sarthur.perais@inria.fr * is not updated. While the designers of the bi-mode 19811783Sarthur.perais@inria.fr * predictor don't explicity say why this is done, one 19911783Sarthur.perais@inria.fr * can infer that it is to preserve the choice predictor's 20011783Sarthur.perais@inria.fr * bias with respect to the branch being predicted; afterall, 20111783Sarthur.perais@inria.fr * the whole point of the bi-mode predictor is to identify the 20211783Sarthur.perais@inria.fr * atypical case when a branch deviates from its bias. 20311783Sarthur.perais@inria.fr */ 20411783Sarthur.perais@inria.fr if (history->finalPred == history->takenUsed) { 20510244Satgutier@umich.edu if (taken) { 20613959Sodanrc@yahoo.com.br choiceCounters[choiceHistoryIdx]++; 20710244Satgutier@umich.edu } else { 20813959Sodanrc@yahoo.com.br choiceCounters[choiceHistoryIdx]--; 20910244Satgutier@umich.edu } 21010244Satgutier@umich.edu } 21111783Sarthur.perais@inria.fr } else { 21211783Sarthur.perais@inria.fr // always update the choice predictor on an incorrect prediction 21311783Sarthur.perais@inria.fr if (taken) { 21413959Sodanrc@yahoo.com.br choiceCounters[choiceHistoryIdx]++; 21510244Satgutier@umich.edu } else { 21613959Sodanrc@yahoo.com.br choiceCounters[choiceHistoryIdx]--; 21710244Satgutier@umich.edu } 21810244Satgutier@umich.edu } 21910244Satgutier@umich.edu 22010244Satgutier@umich.edu delete history; 22110244Satgutier@umich.edu} 22210244Satgutier@umich.edu 22311429Sandreas.sandberg@arm.comvoid 22411434Smitch.hayenga@arm.comBiModeBP::updateGlobalHistReg(ThreadID tid, bool taken) 22511426Smitch.hayenga@arm.com{ 22611434Smitch.hayenga@arm.com globalHistoryReg[tid] = taken ? (globalHistoryReg[tid] << 1) | 1 : 22711434Smitch.hayenga@arm.com (globalHistoryReg[tid] << 1); 22811434Smitch.hayenga@arm.com globalHistoryReg[tid] &= historyRegisterMask; 22910244Satgutier@umich.edu} 23010785Sgope@wisc.edu 23110785Sgope@wisc.eduBiModeBP* 23210785Sgope@wisc.eduBiModeBPParams::create() 23310785Sgope@wisc.edu{ 23410785Sgope@wisc.edu return new BiModeBP(this); 23510785Sgope@wisc.edu} 236