bi_mode.cc revision 11783
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 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