bi_mode.cc revision 11783
112855Sgabeblack@google.com/* 212855Sgabeblack@google.com * Copyright (c) 2014 The Regents of The University of Michigan 312855Sgabeblack@google.com * All rights reserved. 412855Sgabeblack@google.com * 512855Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 612855Sgabeblack@google.com * modification, are permitted provided that the following conditions are 712855Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 812855Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 912855Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 1012855Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 1112855Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 1212855Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 1312855Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 1412855Sgabeblack@google.com * this software without specific prior written permission. 1512855Sgabeblack@google.com * 1612855Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1712855Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1812855Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1912855Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2012855Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2112855Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2212855Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2312855Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2412855Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2512855Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2612855Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2712855Sgabeblack@google.com * 2812855Sgabeblack@google.com * Authors: Anthony Gutierrez 2912855Sgabeblack@google.com */ 3012855Sgabeblack@google.com 3112855Sgabeblack@google.com/* @file 3212855Sgabeblack@google.com * Implementation of a bi-mode branch predictor 3312855Sgabeblack@google.com */ 3412855Sgabeblack@google.com 3512855Sgabeblack@google.com#include "base/bitfield.hh" 3612855Sgabeblack@google.com#include "base/intmath.hh" 3712855Sgabeblack@google.com#include "cpu/pred/bi_mode.hh" 3812855Sgabeblack@google.com 3912855Sgabeblack@google.comBiModeBP::BiModeBP(const BiModeBPParams *params) 4012855Sgabeblack@google.com : BPredUnit(params), 4112855Sgabeblack@google.com globalHistoryReg(params->numThreads, 0), 4212855Sgabeblack@google.com globalHistoryBits(ceilLog2(params->globalPredictorSize)), 4312855Sgabeblack@google.com choicePredictorSize(params->choicePredictorSize), 4412855Sgabeblack@google.com choiceCtrBits(params->choiceCtrBits), 4512855Sgabeblack@google.com globalPredictorSize(params->globalPredictorSize), 4612855Sgabeblack@google.com globalCtrBits(params->globalCtrBits) 4712855Sgabeblack@google.com{ 4812855Sgabeblack@google.com if (!isPowerOf2(choicePredictorSize)) 4912855Sgabeblack@google.com fatal("Invalid choice predictor size.\n"); 5012855Sgabeblack@google.com if (!isPowerOf2(globalPredictorSize)) 5112855Sgabeblack@google.com fatal("Invalid global history predictor size.\n"); 5212855Sgabeblack@google.com 5312855Sgabeblack@google.com choiceCounters.resize(choicePredictorSize); 5412855Sgabeblack@google.com takenCounters.resize(globalPredictorSize); 5512855Sgabeblack@google.com notTakenCounters.resize(globalPredictorSize); 5612855Sgabeblack@google.com 5712855Sgabeblack@google.com for (int i = 0; i < choicePredictorSize; ++i) { 5812855Sgabeblack@google.com choiceCounters[i].setBits(choiceCtrBits); 5912855Sgabeblack@google.com } 6012855Sgabeblack@google.com for (int i = 0; i < globalPredictorSize; ++i) { 6112855Sgabeblack@google.com takenCounters[i].setBits(globalCtrBits); 6212855Sgabeblack@google.com notTakenCounters[i].setBits(globalCtrBits); 6312855Sgabeblack@google.com } 6412855Sgabeblack@google.com 6512855Sgabeblack@google.com historyRegisterMask = mask(globalHistoryBits); 6612855Sgabeblack@google.com choiceHistoryMask = choicePredictorSize - 1; 6712855Sgabeblack@google.com globalHistoryMask = globalPredictorSize - 1; 6812855Sgabeblack@google.com 6912855Sgabeblack@google.com choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 70 takenThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 71 notTakenThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 72} 73 74/* 75 * For an unconditional branch we set its history such that 76 * everything is set to taken. I.e., its choice predictor 77 * chooses the taken array and the taken array predicts taken. 78 */ 79void 80BiModeBP::uncondBranch(ThreadID tid, Addr pc, void * &bpHistory) 81{ 82 BPHistory *history = new BPHistory; 83 history->globalHistoryReg = globalHistoryReg[tid]; 84 history->takenUsed = true; 85 history->takenPred = true; 86 history->notTakenPred = true; 87 history->finalPred = true; 88 bpHistory = static_cast<void*>(history); 89 updateGlobalHistReg(tid, true); 90} 91 92void 93BiModeBP::squash(ThreadID tid, void *bpHistory) 94{ 95 BPHistory *history = static_cast<BPHistory*>(bpHistory); 96 globalHistoryReg[tid] = history->globalHistoryReg; 97 98 delete history; 99} 100 101/* 102 * Here we lookup the actual branch prediction. We use the PC to 103 * identify the bias of a particular branch, which is based on the 104 * prediction in the choice array. A hash of the global history 105 * register and a branch's PC is used to index into both the taken 106 * and not-taken predictors, which both present a prediction. The 107 * choice array's prediction is used to select between the two 108 * direction predictors for the final branch prediction. 109 */ 110bool 111BiModeBP::lookup(ThreadID tid, Addr branchAddr, void * &bpHistory) 112{ 113 unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 114 & choiceHistoryMask); 115 unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 116 ^ globalHistoryReg[tid]) 117 & globalHistoryMask); 118 119 assert(choiceHistoryIdx < choicePredictorSize); 120 assert(globalHistoryIdx < globalPredictorSize); 121 122 bool choicePrediction = choiceCounters[choiceHistoryIdx].read() 123 > choiceThreshold; 124 bool takenGHBPrediction = takenCounters[globalHistoryIdx].read() 125 > takenThreshold; 126 bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx].read() 127 > notTakenThreshold; 128 bool finalPrediction; 129 130 BPHistory *history = new BPHistory; 131 history->globalHistoryReg = globalHistoryReg[tid]; 132 history->takenUsed = choicePrediction; 133 history->takenPred = takenGHBPrediction; 134 history->notTakenPred = notTakenGHBPrediction; 135 136 if (choicePrediction) { 137 finalPrediction = takenGHBPrediction; 138 } else { 139 finalPrediction = notTakenGHBPrediction; 140 } 141 142 history->finalPred = finalPrediction; 143 bpHistory = static_cast<void*>(history); 144 updateGlobalHistReg(tid, finalPrediction); 145 146 return finalPrediction; 147} 148 149void 150BiModeBP::btbUpdate(ThreadID tid, Addr branchAddr, void * &bpHistory) 151{ 152 globalHistoryReg[tid] &= (historyRegisterMask & ~ULL(1)); 153} 154 155/* Only the selected direction predictor will be updated with the final 156 * outcome; the status of the unselected one will not be altered. The choice 157 * predictor is always updated with the branch outcome, except when the 158 * choice is opposite to the branch outcome but the selected counter of 159 * the direction predictors makes a correct final prediction. 160 */ 161void 162BiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory, 163 bool squashed) 164{ 165 assert(bpHistory); 166 167 BPHistory *history = static_cast<BPHistory*>(bpHistory); 168 169 // We do not update the counters speculatively on a squash. 170 // We just restore the global history register. 171 if (squashed) { 172 globalHistoryReg[tid] = (history->globalHistoryReg << 1) | taken; 173 return; 174 } 175 176 unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 177 & choiceHistoryMask); 178 unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 179 ^ history->globalHistoryReg) 180 & globalHistoryMask); 181 182 assert(choiceHistoryIdx < choicePredictorSize); 183 assert(globalHistoryIdx < globalPredictorSize); 184 185 if (history->takenUsed) { 186 // if the taken array's prediction was used, update it 187 if (taken) { 188 takenCounters[globalHistoryIdx].increment(); 189 } else { 190 takenCounters[globalHistoryIdx].decrement(); 191 } 192 } else { 193 // if the not-taken array's prediction was used, update it 194 if (taken) { 195 notTakenCounters[globalHistoryIdx].increment(); 196 } else { 197 notTakenCounters[globalHistoryIdx].decrement(); 198 } 199 } 200 201 if (history->finalPred == taken) { 202 /* If the final prediction matches the actual branch's 203 * outcome and the choice predictor matches the final 204 * outcome, we update the choice predictor, otherwise it 205 * is not updated. While the designers of the bi-mode 206 * predictor don't explicity say why this is done, one 207 * can infer that it is to preserve the choice predictor's 208 * bias with respect to the branch being predicted; afterall, 209 * the whole point of the bi-mode predictor is to identify the 210 * atypical case when a branch deviates from its bias. 211 */ 212 if (history->finalPred == history->takenUsed) { 213 if (taken) { 214 choiceCounters[choiceHistoryIdx].increment(); 215 } else { 216 choiceCounters[choiceHistoryIdx].decrement(); 217 } 218 } 219 } else { 220 // always update the choice predictor on an incorrect prediction 221 if (taken) { 222 choiceCounters[choiceHistoryIdx].increment(); 223 } else { 224 choiceCounters[choiceHistoryIdx].decrement(); 225 } 226 } 227 228 delete history; 229} 230 231unsigned 232BiModeBP::getGHR(ThreadID tid, void *bp_history) const 233{ 234 return static_cast<BPHistory*>(bp_history)->globalHistoryReg; 235} 236 237void 238BiModeBP::updateGlobalHistReg(ThreadID tid, bool taken) 239{ 240 globalHistoryReg[tid] = taken ? (globalHistoryReg[tid] << 1) | 1 : 241 (globalHistoryReg[tid] << 1); 242 globalHistoryReg[tid] &= historyRegisterMask; 243} 244 245BiModeBP* 246BiModeBPParams::create() 247{ 248 return new BiModeBP(this); 249} 250