bi_mode.cc revision 11427:fb512311295e
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 BiModeBPParams *params) 40 : BPredUnit(params), 41 globalHistoryReg(params->numThreads, 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(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 if (bpHistory) { 166 BPHistory *history = static_cast<BPHistory*>(bpHistory); 167 168 unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 169 & choiceHistoryMask); 170 unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 171 ^ history->globalHistoryReg) 172 & globalHistoryMask); 173 174 assert(choiceHistoryIdx < choicePredictorSize); 175 assert(globalHistoryIdx < globalPredictorSize); 176 177 if (history->takenUsed) { 178 // if the taken array's prediction was used, update it 179 if (taken) { 180 takenCounters[globalHistoryIdx].increment(); 181 } else { 182 takenCounters[globalHistoryIdx].decrement(); 183 } 184 } else { 185 // if the not-taken array's prediction was used, update it 186 if (taken) { 187 notTakenCounters[globalHistoryIdx].increment(); 188 } else { 189 notTakenCounters[globalHistoryIdx].decrement(); 190 } 191 } 192 193 if (history->finalPred == taken) { 194 /* If the final prediction matches the actual branch's 195 * outcome and the choice predictor matches the final 196 * outcome, we update the choice predictor, otherwise it 197 * is not updated. While the designers of the bi-mode 198 * predictor don't explicity say why this is done, one 199 * can infer that it is to preserve the choice predictor's 200 * bias with respect to the branch being predicted; afterall, 201 * the whole point of the bi-mode predictor is to identify the 202 * atypical case when a branch deviates from its bias. 203 */ 204 if (history->finalPred == history->takenUsed) { 205 if (taken) { 206 choiceCounters[choiceHistoryIdx].increment(); 207 } else { 208 choiceCounters[choiceHistoryIdx].decrement(); 209 } 210 } 211 } else { 212 // always update the choice predictor on an incorrect prediction 213 if (taken) { 214 choiceCounters[choiceHistoryIdx].increment(); 215 } else { 216 choiceCounters[choiceHistoryIdx].decrement(); 217 } 218 } 219 220 if (squashed) { 221 if (taken) { 222 globalHistoryReg[tid] = (history->globalHistoryReg << 1) | 1; 223 } else { 224 globalHistoryReg[tid] = (history->globalHistoryReg << 1); 225 } 226 globalHistoryReg[tid] &= historyRegisterMask; 227 } else { 228 delete history; 229 } 230 } 231} 232 233void 234BiModeBP::retireSquashed(ThreadID tid, void *bp_history) 235{ 236 BPHistory *history = static_cast<BPHistory*>(bp_history); 237 delete history; 238} 239 240unsigned 241BiModeBP::getGHR(ThreadID tid, void *bp_history) const 242{ 243 return static_cast<BPHistory*>(bp_history)->globalHistoryReg; 244} 245 246void 247BiModeBP::updateGlobalHistReg(ThreadID tid, bool taken) 248{ 249 globalHistoryReg[tid] = taken ? (globalHistoryReg[tid] << 1) | 1 : 250 (globalHistoryReg[tid] << 1); 251 globalHistoryReg[tid] &= historyRegisterMask; 252} 253 254BiModeBP* 255BiModeBPParams::create() 256{ 257 return new BiModeBP(this); 258} 259