bi_mode.cc revision 10335:1b627a6ddac0
1/* 2 * Copyright (c) 2014 The Regents of The University of Michigan 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Anthony Gutierrez 29 */ 30 31/* @file 32 * Implementation of a bi-mode branch predictor 33 */ 34 35#include "base/bitfield.hh" 36#include "base/intmath.hh" 37#include "cpu/pred/bi_mode.hh" 38 39BiModeBP::BiModeBP(const Params *params) 40 : BPredUnit(params), instShiftAmt(params->instShiftAmt), 41 globalHistoryReg(0), 42 globalHistoryBits(ceilLog2(params->globalPredictorSize)), 43 choicePredictorSize(params->choicePredictorSize), 44 choiceCtrBits(params->choiceCtrBits), 45 globalPredictorSize(params->globalPredictorSize), 46 globalCtrBits(params->globalCtrBits) 47{ 48 if (!isPowerOf2(choicePredictorSize)) 49 fatal("Invalid choice predictor size.\n"); 50 if (!isPowerOf2(globalPredictorSize)) 51 fatal("Invalid global history predictor size.\n"); 52 53 choiceCounters.resize(choicePredictorSize); 54 takenCounters.resize(globalPredictorSize); 55 notTakenCounters.resize(globalPredictorSize); 56 57 for (int i = 0; i < choicePredictorSize; ++i) { 58 choiceCounters[i].setBits(choiceCtrBits); 59 } 60 for (int i = 0; i < globalPredictorSize; ++i) { 61 takenCounters[i].setBits(globalCtrBits); 62 notTakenCounters[i].setBits(globalCtrBits); 63 } 64 65 historyRegisterMask = mask(globalHistoryBits); 66 choiceHistoryMask = choicePredictorSize - 1; 67 globalHistoryMask = globalPredictorSize - 1; 68 69 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(void * &bpHistory) 81{ 82 BPHistory *history = new BPHistory; 83 history->globalHistoryReg = globalHistoryReg; 84 history->takenUsed = true; 85 history->takenPred = true; 86 history->notTakenPred = true; 87 history->finalPred = true; 88 bpHistory = static_cast<void*>(history); 89 updateGlobalHistReg(true); 90} 91 92void 93BiModeBP::squash(void *bpHistory) 94{ 95 BPHistory *history = static_cast<BPHistory*>(bpHistory); 96 globalHistoryReg = 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(Addr branchAddr, void * &bpHistory) 112{ 113 unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 114 & choiceHistoryMask); 115 unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 116 ^ globalHistoryReg) 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; 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(finalPrediction); 145 146 return finalPrediction; 147} 148 149void 150BiModeBP::btbUpdate(Addr branchAddr, void * &bpHistory) 151{ 152 globalHistoryReg &= (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(Addr branchAddr, bool taken, void *bpHistory, bool squashed) 163{ 164 if (bpHistory) { 165 BPHistory *history = static_cast<BPHistory*>(bpHistory); 166 167 unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 168 & choiceHistoryMask); 169 unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 170 ^ history->globalHistoryReg) 171 & globalHistoryMask); 172 173 assert(choiceHistoryIdx < choicePredictorSize); 174 assert(globalHistoryIdx < globalPredictorSize); 175 176 if (history->takenUsed) { 177 // if the taken array's prediction was used, update it 178 if (taken) { 179 takenCounters[globalHistoryIdx].increment(); 180 } else { 181 takenCounters[globalHistoryIdx].decrement(); 182 } 183 } else { 184 // if the not-taken array's prediction was used, update it 185 if (taken) { 186 notTakenCounters[globalHistoryIdx].increment(); 187 } else { 188 notTakenCounters[globalHistoryIdx].decrement(); 189 } 190 } 191 192 if (history->finalPred == taken) { 193 /* If the final prediction matches the actual branch's 194 * outcome and the choice predictor matches the final 195 * outcome, we update the choice predictor, otherwise it 196 * is not updated. While the designers of the bi-mode 197 * predictor don't explicity say why this is done, one 198 * can infer that it is to preserve the choice predictor's 199 * bias with respect to the branch being predicted; afterall, 200 * the whole point of the bi-mode predictor is to identify the 201 * atypical case when a branch deviates from its bias. 202 */ 203 if (history->finalPred == history->takenUsed) { 204 if (taken) { 205 choiceCounters[choiceHistoryIdx].increment(); 206 } else { 207 choiceCounters[choiceHistoryIdx].decrement(); 208 } 209 } 210 } else { 211 // always update the choice predictor on an incorrect prediction 212 if (taken) { 213 choiceCounters[choiceHistoryIdx].increment(); 214 } else { 215 choiceCounters[choiceHistoryIdx].decrement(); 216 } 217 } 218 219 if (squashed) { 220 if (taken) { 221 globalHistoryReg = (history->globalHistoryReg << 1) | 1; 222 } else { 223 globalHistoryReg = (history->globalHistoryReg << 1); 224 } 225 globalHistoryReg &= historyRegisterMask; 226 } else { 227 delete history; 228 } 229 } 230} 231 232void 233BiModeBP::retireSquashed(void *bp_history) 234{ 235 BPHistory *history = static_cast<BPHistory*>(bp_history); 236 delete history; 237} 238 239void 240BiModeBP::updateGlobalHistReg(bool taken) 241{ 242 globalHistoryReg = taken ? (globalHistoryReg << 1) | 1 : 243 (globalHistoryReg << 1); 244 globalHistoryReg &= historyRegisterMask; 245} 246