1/* 2 * Copyright (c) 2018 Metempsy Technology Consulting 3 * All rights reserved. 4 * 5 * Copyright (c) 2006 INRIA (Institut National de Recherche en 6 * Informatique et en Automatique / French National Research Institute 7 * for Computer Science and Applied Mathematics) 8 * 9 * All rights reserved. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions are 13 * met: redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer; 15 * redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution; 18 * neither the name of the copyright holders nor the names of its 19 * contributors may be used to endorse or promote products derived from 20 * this software without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 23 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 25 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 26 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 27 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 28 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 29 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 30 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 32 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 33 * 34 * Author: André Seznec, Pau Cabre, Javier Bueno 35 * 36 */ 37 38/* 39 * Statistical corrector base class 40 */ 41 42 #include "cpu/pred/statistical_corrector.hh" 43 44 #include "params/StatisticalCorrector.hh" 45 46 StatisticalCorrector::StatisticalCorrector( 47 const StatisticalCorrectorParams *p) 48 : SimObject(p), 49 logBias(p->logBias), 50 logSizeUp(p->logSizeUp), 51 logSizeUps(logSizeUp / 2), 52 numEntriesFirstLocalHistories(p->numEntriesFirstLocalHistories), 53 bwnb(p->bwnb), 54 logBwnb(p->logBwnb), 55 bwm(p->bwm), 56 lnb(p->lnb), 57 logLnb(p->logLnb), 58 lm(p->lm), 59 inb(p->inb), 60 logInb(p->logInb), 61 im(p->im), 62 chooserConfWidth(p->chooserConfWidth), 63 updateThresholdWidth(p->updateThresholdWidth), 64 pUpdateThresholdWidth(p->pUpdateThresholdWidth), 65 extraWeightsWidth(p->extraWeightsWidth), 66 scCountersWidth(p->scCountersWidth), 67 firstH(0), 68 secondH(0) 69{ 70 wb.resize(1 << logSizeUps, 4); 71 72 initGEHLTable(lnb, lm, lgehl, logLnb, wl, p->lWeightInitValue); 73 initGEHLTable(bwnb, bwm, bwgehl, logBwnb, wbw, p->bwWeightInitValue); 74 initGEHLTable(inb, im, igehl, logInb, wi, p->iWeightInitValue); 75 76 updateThreshold = 35 << 3; 77 78 pUpdateThreshold.resize(1 << logSizeUp, p->initialUpdateThresholdValue); 79 80 bias.resize(1 << logBias); 81 biasSK.resize(1 << logBias); 82 biasBank.resize(1 << logBias); 83} 84 85StatisticalCorrector::BranchInfo* 86StatisticalCorrector::makeBranchInfo() 87{ 88 return new BranchInfo(); 89} 90 91StatisticalCorrector::SCThreadHistory* 92StatisticalCorrector::makeThreadHistory() 93{ 94 return new SCThreadHistory(); 95} 96 97void 98StatisticalCorrector::initBias() 99{ 100 for (int j = 0; j < (1 << logBias); j++) { 101 switch (j & 3) { 102 case 0: 103 bias[j] = -32; 104 biasSK[j] = -8; 105 biasBank[j] = -32; 106 break; 107 case 1: 108 bias[j] = 31; 109 biasSK[j] = 7; 110 biasBank[j] = 31; 111 break; 112 case 2: 113 bias[j] = -1; 114 biasSK[j] = -32; 115 biasBank[j] = -1; 116 break; 117 case 3: 118 bias[j] = 0; 119 biasSK[j] = 31; 120 biasBank[j] = 0; 121 break; 122 } 123 } 124} 125 126void 127StatisticalCorrector::initGEHLTable(unsigned numLenghts, 128 std::vector<int> lengths, std::vector<int8_t> * & table, 129 unsigned logNumEntries, std::vector<int8_t> & w, int8_t wInitValue) 130{ 131 assert(lengths.size() == numLenghts); 132 if (numLenghts == 0) { 133 return; 134 } 135 table = new std::vector<int8_t> [numLenghts]; 136 for (int i = 0; i < numLenghts; ++i) { 137 table[i].resize(1 << logNumEntries, 0); 138 for (int j = 0; j < ((1 << logNumEntries) - 1); ++j) { 139 if (! (j & 1)) { 140 table[i][j] = -1; 141 } 142 } 143 } 144 145 w.resize(1 << logSizeUps, wInitValue); 146} 147 148unsigned 149StatisticalCorrector::getIndBias(Addr branch_pc, BranchInfo* bi, 150 bool bias) const 151{ 152 return (((((branch_pc ^(branch_pc >>2))<<1) ^ (bi->lowConf & bias)) <<1) 153 + bi->predBeforeSC) & ((1<<logBias) -1); 154} 155 156unsigned 157StatisticalCorrector::getIndBiasSK(Addr branch_pc, BranchInfo* bi) const 158{ 159 return (((((branch_pc ^ (branch_pc >> (logBias-2)))<<1) ^ 160 (bi->highConf))<<1) + bi->predBeforeSC) & ((1<<logBias) -1); 161} 162 163unsigned 164StatisticalCorrector::getIndUpd(Addr branch_pc) const 165{ 166 return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUp)) - 1)); 167} 168 169unsigned 170StatisticalCorrector::getIndUpds(Addr branch_pc) const 171{ 172 return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUps)) - 1)); 173} 174 175int64_t 176StatisticalCorrector::gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr, 177 int i) 178{ 179 return (((int64_t) branch_pc) ^ bhist ^ (bhist >> (8 - i)) ^ 180 (bhist >> (16 - 2 * i)) ^ (bhist >> (24 - 3 * i)) ^ 181 (bhist >> (32 - 3 * i)) ^ (bhist >> (40 - 4 * i))) & 182 ((1 << (logs - gIndexLogsSubstr(nbr, i))) - 1); 183} 184 185int 186StatisticalCorrector::gPredict(Addr branch_pc, int64_t hist, 187 std::vector<int> & length, std::vector<int8_t> * tab, int nbr, 188 int logs, std::vector<int8_t> & w) 189{ 190 int percsum = 0; 191 for (int i = 0; i < nbr; i++) { 192 int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1)); 193 int64_t index = gIndex(branch_pc, bhist, logs, nbr, i); 194 int8_t ctr = tab[i][index]; 195 percsum += (2 * ctr + 1); 196 } 197 percsum = (1 + (w[getIndUpds(branch_pc)] >= 0)) * percsum; 198 return percsum; 199} 200 201void 202StatisticalCorrector::gUpdate(Addr branch_pc, bool taken, int64_t hist, 203 std::vector<int> & length, std::vector<int8_t> * tab, 204 int nbr, int logs, std::vector<int8_t> & w, 205 BranchInfo* bi) 206{ 207 int percsum = 0; 208 for (int i = 0; i < nbr; i++) { 209 int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1)); 210 int64_t index = gIndex(branch_pc, bhist, logs, nbr, i); 211 percsum += (2 * tab[i][index] + 1); 212 ctrUpdate(tab[i][index], taken, scCountersWidth); 213 } 214 215 int xsum = bi->lsum - ((w[getIndUpds(branch_pc)] >= 0)) * percsum; 216 if ((xsum + percsum >= 0) != (xsum >= 0)) { 217 ctrUpdate(w[getIndUpds(branch_pc)], ((percsum >= 0) == taken), 218 extraWeightsWidth); 219 } 220} 221 222bool 223StatisticalCorrector::scPredict(ThreadID tid, Addr branch_pc, bool cond_branch, 224 BranchInfo* bi, bool prev_pred_taken, bool bias_bit, 225 bool use_conf_ctr, int8_t conf_ctr, unsigned conf_bits, 226 int hitBank, int altBank, int64_t phist, int init_lsum) 227{ 228 bool pred_taken = prev_pred_taken; 229 if (cond_branch) { 230 231 bi->predBeforeSC = prev_pred_taken; 232 233 // first calc/update the confidences from the TAGE prediction 234 if (use_conf_ctr) { 235 bi->lowConf = (abs(2 * conf_ctr + 1) == 1); 236 bi->medConf = (abs(2 * conf_ctr + 1) == 5); 237 bi->highConf = (abs(2 * conf_ctr + 1) >= (1<<conf_bits) - 1); 238 } 239 240 int lsum = init_lsum; 241 242 int8_t ctr = bias[getIndBias(branch_pc, bi, bias_bit)]; 243 lsum += (2 * ctr + 1); 244 ctr = biasSK[getIndBiasSK(branch_pc, bi)]; 245 lsum += (2 * ctr + 1); 246 ctr = biasBank[getIndBiasBank(branch_pc, bi, hitBank, altBank)]; 247 lsum += (2 * ctr + 1); 248 249 lsum = (1 + (wb[getIndUpds(branch_pc)] >= 0)) * lsum; 250 251 int thres = gPredictions(tid, branch_pc, bi, lsum, phist); 252 253 // These will be needed at update time 254 bi->lsum = lsum; 255 bi->thres = thres; 256 257 bool scPred = (lsum >= 0); 258 259 if (pred_taken != scPred) { 260 bool useScPred = true; 261 //Choser uses TAGE confidence and |LSUM| 262 if (bi->highConf) { 263 if (abs (lsum) < (thres / 4)) { 264 useScPred = false; 265 } else if (abs (lsum) < (thres / 2)) { 266 useScPred = (secondH < 0); 267 } 268 } 269 270 if (bi->medConf) { 271 if (abs (lsum) < (thres / 4)) { 272 useScPred = (firstH < 0); 273 } 274 } 275 276 bi->usedScPred = useScPred; 277 if (useScPred) { 278 pred_taken = scPred; 279 bi->scPred = scPred; 280 } 281 } 282 } 283 284 return pred_taken; 285} 286 287void 288StatisticalCorrector::scHistoryUpdate(Addr branch_pc, 289 const StaticInstPtr &inst, bool taken, BranchInfo * tage_bi, 290 Addr corrTarget) 291{ 292 int brtype = inst->isDirectCtrl() ? 0 : 2; 293 if (! inst->isUncondCtrl()) { 294 ++brtype; 295 } 296 // Non speculative SC histories update 297 if (brtype & 1) { 298 if (corrTarget < branch_pc) { 299 //This branch corresponds to a loop 300 if (!taken) { 301 //exit of the "loop" 302 scHistory->imliCount = 0; 303 } else { 304 if (scHistory->imliCount < ((1 << im[0]) - 1)) { 305 scHistory->imliCount++; 306 } 307 } 308 } 309 310 scHistory->bwHist = (scHistory->bwHist << 1) + 311 (taken & (corrTarget < branch_pc)); 312 scHistory->updateLocalHistory(1, branch_pc, taken); 313 } 314} 315 316void 317StatisticalCorrector::condBranchUpdate(ThreadID tid, Addr branch_pc, 318 bool taken, BranchInfo *bi, Addr corrTarget, bool b, int hitBank, 319 int altBank, int64_t phist) 320{ 321 bool scPred = (bi->lsum >= 0); 322 323 if (bi->predBeforeSC != scPred) { 324 if (abs(bi->lsum) < bi->thres) { 325 if (bi->highConf) { 326 if ((abs(bi->lsum) < bi->thres / 2)) { 327 if ((abs(bi->lsum) >= bi->thres / 4)) { 328 ctrUpdate(secondH, (bi->predBeforeSC == taken), 329 chooserConfWidth); 330 } 331 } 332 } 333 } 334 if (bi->medConf) { 335 if ((abs(bi->lsum) < bi->thres / 4)) { 336 ctrUpdate(firstH, (bi->predBeforeSC == taken), 337 chooserConfWidth); 338 } 339 } 340 } 341 342 if ((scPred != taken) || ((abs(bi->lsum) < bi->thres))) { 343 ctrUpdate(updateThreshold, (scPred != taken), updateThresholdWidth); 344 ctrUpdate(pUpdateThreshold[getIndUpd(branch_pc)], (scPred != taken), 345 pUpdateThresholdWidth); 346 347 unsigned indUpds = getIndUpds(branch_pc); 348 unsigned indBias = getIndBias(branch_pc, bi, b); 349 unsigned indBiasSK = getIndBiasSK(branch_pc, bi); 350 unsigned indBiasBank = getIndBiasBank(branch_pc, bi, hitBank, altBank); 351 352 int xsum = bi->lsum - 353 ((wb[indUpds] >= 0) * ((2 * bias[indBias] + 1) + 354 (2 * biasSK[indBiasSK] + 1) + 355 (2 * biasBank[indBiasBank] + 1))); 356 357 if ((xsum + ((2 * bias[indBias] + 1) + (2 * biasSK[indBiasSK] + 1) + 358 (2 * biasBank[indBiasBank] + 1)) >= 0) != (xsum >= 0)) 359 { 360 ctrUpdate(wb[indUpds], 361 (((2 * bias[indBias] + 1) + 362 (2 * biasSK[indBiasSK] + 1) + 363 (2 * biasBank[indBiasBank] + 1) >= 0) == taken), 364 extraWeightsWidth); 365 } 366 367 ctrUpdate(bias[indBias], taken, scCountersWidth); 368 ctrUpdate(biasSK[indBiasSK], taken, scCountersWidth); 369 ctrUpdate(biasBank[indBiasBank], taken, scCountersWidth); 370 371 gUpdates(tid, branch_pc, taken, bi, phist); 372 } 373} 374 375void 376StatisticalCorrector::updateStats(bool taken, BranchInfo *bi) 377{ 378 if (taken == bi->scPred) { 379 scPredictorCorrect++; 380 } else { 381 scPredictorWrong++; 382 } 383} 384 385void 386StatisticalCorrector::init() 387{ 388 scHistory = makeThreadHistory(); 389 initBias(); 390} 391 392size_t 393StatisticalCorrector::getSizeInBits() const 394{ 395 // Not implemented 396 return 0; 397} 398 399void 400StatisticalCorrector::regStats() 401{ 402 scPredictorCorrect 403 .name(name() + ".scPredictorCorrect") 404 .desc("Number of time the SC predictor is the provider and " 405 "the prediction is correct"); 406 407 scPredictorWrong 408 .name(name() + ".scPredictorWrong") 409 .desc("Number of time the SC predictor is the provider and " 410 "the prediction is wrong"); 411} 412