bi_mode.cc revision 13654:dc3878f03a0c
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 "cpu/pred/bi_mode.hh" 36 37#include "base/bitfield.hh" 38#include "base/intmath.hh" 39 40BiModeBP::BiModeBP(const BiModeBPParams *params) 41 : BPredUnit(params), 42 globalHistoryReg(params->numThreads, 0), 43 globalHistoryBits(ceilLog2(params->globalPredictorSize)), 44 choicePredictorSize(params->choicePredictorSize), 45 choiceCtrBits(params->choiceCtrBits), 46 globalPredictorSize(params->globalPredictorSize), 47 globalCtrBits(params->globalCtrBits) 48{ 49 if (!isPowerOf2(choicePredictorSize)) 50 fatal("Invalid choice predictor size.\n"); 51 if (!isPowerOf2(globalPredictorSize)) 52 fatal("Invalid global history predictor size.\n"); 53 54 choiceCounters.resize(choicePredictorSize); 55 takenCounters.resize(globalPredictorSize); 56 notTakenCounters.resize(globalPredictorSize); 57 58 for (int i = 0; i < choicePredictorSize; ++i) { 59 choiceCounters[i].setBits(choiceCtrBits); 60 } 61 for (int i = 0; i < globalPredictorSize; ++i) { 62 takenCounters[i].setBits(globalCtrBits); 63 notTakenCounters[i].setBits(globalCtrBits); 64 } 65 66 historyRegisterMask = mask(globalHistoryBits); 67 choiceHistoryMask = choicePredictorSize - 1; 68 globalHistoryMask = globalPredictorSize - 1; 69 70 choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 71 takenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1; 72 notTakenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1; 73} 74 75/* 76 * For an unconditional branch we set its history such that 77 * everything is set to taken. I.e., its choice predictor 78 * chooses the taken array and the taken array predicts taken. 79 */ 80void 81BiModeBP::uncondBranch(ThreadID tid, Addr pc, void * &bpHistory) 82{ 83 BPHistory *history = new BPHistory; 84 history->globalHistoryReg = globalHistoryReg[tid]; 85 history->takenUsed = true; 86 history->takenPred = true; 87 history->notTakenPred = true; 88 history->finalPred = true; 89 bpHistory = static_cast<void*>(history); 90 updateGlobalHistReg(tid, true); 91} 92 93void 94BiModeBP::squash(ThreadID tid, void *bpHistory) 95{ 96 BPHistory *history = static_cast<BPHistory*>(bpHistory); 97 globalHistoryReg[tid] = history->globalHistoryReg; 98 99 delete history; 100} 101 102/* 103 * Here we lookup the actual branch prediction. We use the PC to 104 * identify the bias of a particular branch, which is based on the 105 * prediction in the choice array. A hash of the global history 106 * register and a branch's PC is used to index into both the taken 107 * and not-taken predictors, which both present a prediction. The 108 * choice array's prediction is used to select between the two 109 * direction predictors for the final branch prediction. 110 */ 111bool 112BiModeBP::lookup(ThreadID tid, Addr branchAddr, void * &bpHistory) 113{ 114 unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 115 & choiceHistoryMask); 116 unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 117 ^ globalHistoryReg[tid]) 118 & globalHistoryMask); 119 120 assert(choiceHistoryIdx < choicePredictorSize); 121 assert(globalHistoryIdx < globalPredictorSize); 122 123 bool choicePrediction = choiceCounters[choiceHistoryIdx].read() 124 > choiceThreshold; 125 bool takenGHBPrediction = takenCounters[globalHistoryIdx].read() 126 > takenThreshold; 127 bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx].read() 128 > notTakenThreshold; 129 bool finalPrediction; 130 131 BPHistory *history = new BPHistory; 132 history->globalHistoryReg = globalHistoryReg[tid]; 133 history->takenUsed = choicePrediction; 134 history->takenPred = takenGHBPrediction; 135 history->notTakenPred = notTakenGHBPrediction; 136 137 if (choicePrediction) { 138 finalPrediction = takenGHBPrediction; 139 } else { 140 finalPrediction = notTakenGHBPrediction; 141 } 142 143 history->finalPred = finalPrediction; 144 bpHistory = static_cast<void*>(history); 145 updateGlobalHistReg(tid, finalPrediction); 146 147 return finalPrediction; 148} 149 150void 151BiModeBP::btbUpdate(ThreadID tid, Addr branchAddr, void * &bpHistory) 152{ 153 globalHistoryReg[tid] &= (historyRegisterMask & ~ULL(1)); 154} 155 156/* Only the selected direction predictor will be updated with the final 157 * outcome; the status of the unselected one will not be altered. The choice 158 * predictor is always updated with the branch outcome, except when the 159 * choice is opposite to the branch outcome but the selected counter of 160 * the direction predictors makes a correct final prediction. 161 */ 162void 163BiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory, 164 bool squashed, const StaticInstPtr & inst, Addr corrTarget) 165{ 166 assert(bpHistory); 167 168 BPHistory *history = static_cast<BPHistory*>(bpHistory); 169 170 // We do not update the counters speculatively on a squash. 171 // We just restore the global history register. 172 if (squashed) { 173 globalHistoryReg[tid] = (history->globalHistoryReg << 1) | taken; 174 return; 175 } 176 177 unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt) 178 & choiceHistoryMask); 179 unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt) 180 ^ history->globalHistoryReg) 181 & globalHistoryMask); 182 183 assert(choiceHistoryIdx < choicePredictorSize); 184 assert(globalHistoryIdx < globalPredictorSize); 185 186 if (history->takenUsed) { 187 // if the taken array's prediction was used, update it 188 if (taken) { 189 takenCounters[globalHistoryIdx].increment(); 190 } else { 191 takenCounters[globalHistoryIdx].decrement(); 192 } 193 } else { 194 // if the not-taken array's prediction was used, update it 195 if (taken) { 196 notTakenCounters[globalHistoryIdx].increment(); 197 } else { 198 notTakenCounters[globalHistoryIdx].decrement(); 199 } 200 } 201 202 if (history->finalPred == taken) { 203 /* If the final prediction matches the actual branch's 204 * outcome and the choice predictor matches the final 205 * outcome, we update the choice predictor, otherwise it 206 * is not updated. While the designers of the bi-mode 207 * predictor don't explicity say why this is done, one 208 * can infer that it is to preserve the choice predictor's 209 * bias with respect to the branch being predicted; afterall, 210 * the whole point of the bi-mode predictor is to identify the 211 * atypical case when a branch deviates from its bias. 212 */ 213 if (history->finalPred == history->takenUsed) { 214 if (taken) { 215 choiceCounters[choiceHistoryIdx].increment(); 216 } else { 217 choiceCounters[choiceHistoryIdx].decrement(); 218 } 219 } 220 } else { 221 // always update the choice predictor on an incorrect prediction 222 if (taken) { 223 choiceCounters[choiceHistoryIdx].increment(); 224 } else { 225 choiceCounters[choiceHistoryIdx].decrement(); 226 } 227 } 228 229 delete history; 230} 231 232void 233BiModeBP::updateGlobalHistReg(ThreadID tid, bool taken) 234{ 235 globalHistoryReg[tid] = taken ? (globalHistoryReg[tid] << 1) | 1 : 236 (globalHistoryReg[tid] << 1); 237 globalHistoryReg[tid] &= historyRegisterMask; 238} 239 240BiModeBP* 241BiModeBPParams::create() 242{ 243 return new BiModeBP(this); 244} 245