statistical_corrector.cc revision 14081
110915Sandreas.sandberg@arm.com/* 211313Sandreas.sandberg@arm.com * Copyright (c) 2018 Metempsy Technology Consulting 310915Sandreas.sandberg@arm.com * All rights reserved. 410915Sandreas.sandberg@arm.com * 510915Sandreas.sandberg@arm.com * Copyright (c) 2006 INRIA (Institut National de Recherche en 610915Sandreas.sandberg@arm.com * Informatique et en Automatique / French National Research Institute 710915Sandreas.sandberg@arm.com * for Computer Science and Applied Mathematics) 810915Sandreas.sandberg@arm.com * 910915Sandreas.sandberg@arm.com * All rights reserved. 1010915Sandreas.sandberg@arm.com * 1110915Sandreas.sandberg@arm.com * Redistribution and use in source and binary forms, with or without 1210915Sandreas.sandberg@arm.com * modification, are permitted provided that the following conditions are 1310915Sandreas.sandberg@arm.com * met: redistributions of source code must retain the above copyright 1410915Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer; 1510915Sandreas.sandberg@arm.com * redistributions in binary form must reproduce the above copyright 1610915Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer in the 1710915Sandreas.sandberg@arm.com * documentation and/or other materials provided with the distribution; 1810915Sandreas.sandberg@arm.com * neither the name of the copyright holders nor the names of its 1910915Sandreas.sandberg@arm.com * contributors may be used to endorse or promote products derived from 2010915Sandreas.sandberg@arm.com * this software without specific prior written permission. 2110915Sandreas.sandberg@arm.com * 2210915Sandreas.sandberg@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2310915Sandreas.sandberg@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2410915Sandreas.sandberg@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2510915Sandreas.sandberg@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2610915Sandreas.sandberg@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2710915Sandreas.sandberg@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2810915Sandreas.sandberg@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2910915Sandreas.sandberg@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3010915Sandreas.sandberg@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3111313Sandreas.sandberg@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3211313Sandreas.sandberg@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3311313Sandreas.sandberg@arm.com * 3411313Sandreas.sandberg@arm.com * Author: André Seznec, Pau Cabre, Javier Bueno 3510915Sandreas.sandberg@arm.com * 3610915Sandreas.sandberg@arm.com */ 3710915Sandreas.sandberg@arm.com 3810915Sandreas.sandberg@arm.com/* 3910915Sandreas.sandberg@arm.com * Statistical corrector base class 4010915Sandreas.sandberg@arm.com */ 4110915Sandreas.sandberg@arm.com 4210915Sandreas.sandberg@arm.com #include "cpu/pred/statistical_corrector.hh" 4310915Sandreas.sandberg@arm.com 4410915Sandreas.sandberg@arm.com #include "params/StatisticalCorrector.hh" 4510915Sandreas.sandberg@arm.com 4610915Sandreas.sandberg@arm.com StatisticalCorrector::StatisticalCorrector( 4710915Sandreas.sandberg@arm.com const StatisticalCorrectorParams *p) 4810915Sandreas.sandberg@arm.com : SimObject(p), 4910915Sandreas.sandberg@arm.com logBias(p->logBias), 5010915Sandreas.sandberg@arm.com logSizeUp(p->logSizeUp), 5110915Sandreas.sandberg@arm.com logSizeUps(logSizeUp / 2), 5210915Sandreas.sandberg@arm.com numEntriesFirstLocalHistories(p->numEntriesFirstLocalHistories), 5310915Sandreas.sandberg@arm.com bwnb(p->bwnb), 5410915Sandreas.sandberg@arm.com logBwnb(p->logBwnb), 5510915Sandreas.sandberg@arm.com bwm(p->bwm), 5610915Sandreas.sandberg@arm.com lnb(p->lnb), 5710915Sandreas.sandberg@arm.com logLnb(p->logLnb), 5810915Sandreas.sandberg@arm.com lm(p->lm), 5910915Sandreas.sandberg@arm.com inb(p->inb), 6010915Sandreas.sandberg@arm.com logInb(p->logInb), 6110915Sandreas.sandberg@arm.com im(p->im), 6210915Sandreas.sandberg@arm.com chooserConfWidth(p->chooserConfWidth), 6310915Sandreas.sandberg@arm.com updateThresholdWidth(p->updateThresholdWidth), 6410915Sandreas.sandberg@arm.com pUpdateThresholdWidth(p->pUpdateThresholdWidth), 6510915Sandreas.sandberg@arm.com extraWeightsWidth(p->extraWeightsWidth), 6610915Sandreas.sandberg@arm.com scCountersWidth(p->scCountersWidth), 6710915Sandreas.sandberg@arm.com firstH(0), 6810915Sandreas.sandberg@arm.com secondH(0) 6910915Sandreas.sandberg@arm.com{ 7010915Sandreas.sandberg@arm.com wb.resize(1 << logSizeUps, 4); 7110915Sandreas.sandberg@arm.com 7210915Sandreas.sandberg@arm.com initGEHLTable(lnb, lm, lgehl, logLnb, wl, p->lWeightInitValue); 7310915Sandreas.sandberg@arm.com initGEHLTable(bwnb, bwm, bwgehl, logBwnb, wbw, p->bwWeightInitValue); 7410915Sandreas.sandberg@arm.com initGEHLTable(inb, im, igehl, logInb, wi, p->iWeightInitValue); 7510915Sandreas.sandberg@arm.com 7610915Sandreas.sandberg@arm.com updateThreshold = 35 << 3; 7710915Sandreas.sandberg@arm.com 7810915Sandreas.sandberg@arm.com pUpdateThreshold.resize(1 << logSizeUp, p->initialUpdateThresholdValue); 7910915Sandreas.sandberg@arm.com 8010915Sandreas.sandberg@arm.com bias.resize(1 << logBias); 8110915Sandreas.sandberg@arm.com biasSK.resize(1 << logBias); 8210915Sandreas.sandberg@arm.com biasBank.resize(1 << logBias); 8310915Sandreas.sandberg@arm.com} 8410915Sandreas.sandberg@arm.com 8510915Sandreas.sandberg@arm.comStatisticalCorrector::BranchInfo* 8610915Sandreas.sandberg@arm.comStatisticalCorrector::makeBranchInfo() 8710915Sandreas.sandberg@arm.com{ 8810915Sandreas.sandberg@arm.com return new BranchInfo(); 8910915Sandreas.sandberg@arm.com} 9010915Sandreas.sandberg@arm.com 9110915Sandreas.sandberg@arm.comStatisticalCorrector::SCThreadHistory* 9210915Sandreas.sandberg@arm.comStatisticalCorrector::makeThreadHistory() 9310915Sandreas.sandberg@arm.com{ 9410915Sandreas.sandberg@arm.com return new SCThreadHistory(); 9510915Sandreas.sandberg@arm.com} 9610915Sandreas.sandberg@arm.com 9710915Sandreas.sandberg@arm.comvoid 9810915Sandreas.sandberg@arm.comStatisticalCorrector::initBias() 9910915Sandreas.sandberg@arm.com{ 10010915Sandreas.sandberg@arm.com for (int j = 0; j < (1 << logBias); j++) { 10110915Sandreas.sandberg@arm.com switch (j & 3) { 10210915Sandreas.sandberg@arm.com case 0: 10310915Sandreas.sandberg@arm.com bias[j] = -32; 10410915Sandreas.sandberg@arm.com biasSK[j] = -8; 10510915Sandreas.sandberg@arm.com biasBank[j] = -32; 10610915Sandreas.sandberg@arm.com break; 10710915Sandreas.sandberg@arm.com case 1: 10810915Sandreas.sandberg@arm.com bias[j] = 31; 10910915Sandreas.sandberg@arm.com biasSK[j] = 7; 11010915Sandreas.sandberg@arm.com biasBank[j] = 31; 11111313Sandreas.sandberg@arm.com break; 11210915Sandreas.sandberg@arm.com case 2: 11310915Sandreas.sandberg@arm.com bias[j] = -1; 11410915Sandreas.sandberg@arm.com biasSK[j] = -32; 11510915Sandreas.sandberg@arm.com biasBank[j] = -1; 11610915Sandreas.sandberg@arm.com break; 11710915Sandreas.sandberg@arm.com case 3: 11810915Sandreas.sandberg@arm.com bias[j] = 0; 11910915Sandreas.sandberg@arm.com biasSK[j] = 31; 12010915Sandreas.sandberg@arm.com biasBank[j] = 0; 12110915Sandreas.sandberg@arm.com break; 12210915Sandreas.sandberg@arm.com } 12310915Sandreas.sandberg@arm.com } 12410915Sandreas.sandberg@arm.com} 12510915Sandreas.sandberg@arm.com 12610915Sandreas.sandberg@arm.comvoid 12710915Sandreas.sandberg@arm.comStatisticalCorrector::initGEHLTable(unsigned numLenghts, 12810915Sandreas.sandberg@arm.com std::vector<int> lengths, std::vector<int8_t> * & table, 12910915Sandreas.sandberg@arm.com unsigned logNumEntries, std::vector<int8_t> & w, int8_t wInitValue) 13010915Sandreas.sandberg@arm.com{ 13111313Sandreas.sandberg@arm.com assert(lengths.size() == numLenghts); 13210915Sandreas.sandberg@arm.com if (numLenghts == 0) { 13310915Sandreas.sandberg@arm.com return; 13410915Sandreas.sandberg@arm.com } 13510915Sandreas.sandberg@arm.com table = new std::vector<int8_t> [numLenghts]; 13610915Sandreas.sandberg@arm.com for (int i = 0; i < numLenghts; ++i) { 13710915Sandreas.sandberg@arm.com table[i].resize(1 << logNumEntries, 0); 13810915Sandreas.sandberg@arm.com for (int j = 0; j < ((1 << logNumEntries) - 1); ++j) { 13910915Sandreas.sandberg@arm.com if (! (j & 1)) { 14010915Sandreas.sandberg@arm.com table[i][j] = -1; 14110915Sandreas.sandberg@arm.com } 14210915Sandreas.sandberg@arm.com } 14310915Sandreas.sandberg@arm.com } 14410915Sandreas.sandberg@arm.com 14510915Sandreas.sandberg@arm.com w.resize(1 << logSizeUps, wInitValue); 14610915Sandreas.sandberg@arm.com} 14710915Sandreas.sandberg@arm.com 14810915Sandreas.sandberg@arm.comunsigned 14910915Sandreas.sandberg@arm.comStatisticalCorrector::getIndBias(Addr branch_pc, BranchInfo* bi, 15010915Sandreas.sandberg@arm.com bool bias) const 15110915Sandreas.sandberg@arm.com{ 15210915Sandreas.sandberg@arm.com return (((((branch_pc ^(branch_pc >>2))<<1) ^ (bi->lowConf & bias)) <<1) 15310915Sandreas.sandberg@arm.com + bi->predBeforeSC) & ((1<<logBias) -1); 15410915Sandreas.sandberg@arm.com} 15510915Sandreas.sandberg@arm.com 15610915Sandreas.sandberg@arm.comunsigned 15710915Sandreas.sandberg@arm.comStatisticalCorrector::getIndBiasSK(Addr branch_pc, BranchInfo* bi) const 15810915Sandreas.sandberg@arm.com{ 15910915Sandreas.sandberg@arm.com return (((((branch_pc ^ (branch_pc >> (logBias-2)))<<1) ^ 16010915Sandreas.sandberg@arm.com (bi->highConf))<<1) + bi->predBeforeSC) & ((1<<logBias) -1); 16110915Sandreas.sandberg@arm.com} 16210915Sandreas.sandberg@arm.com 16310915Sandreas.sandberg@arm.comunsigned 16410915Sandreas.sandberg@arm.comStatisticalCorrector::getIndUpd(Addr branch_pc) const 16510915Sandreas.sandberg@arm.com{ 16610915Sandreas.sandberg@arm.com return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUp)) - 1)); 16710915Sandreas.sandberg@arm.com} 16810915Sandreas.sandberg@arm.com 16910915Sandreas.sandberg@arm.comunsigned 17010915Sandreas.sandberg@arm.comStatisticalCorrector::getIndUpds(Addr branch_pc) const 17110915Sandreas.sandberg@arm.com{ 17210915Sandreas.sandberg@arm.com return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUps)) - 1)); 17310915Sandreas.sandberg@arm.com} 17410915Sandreas.sandberg@arm.com 17510915Sandreas.sandberg@arm.comint64_t 17610915Sandreas.sandberg@arm.comStatisticalCorrector::gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr, 17710915Sandreas.sandberg@arm.com int i) 17810915Sandreas.sandberg@arm.com{ 17910915Sandreas.sandberg@arm.com return (((int64_t) branch_pc) ^ bhist ^ (bhist >> (8 - i)) ^ 18010915Sandreas.sandberg@arm.com (bhist >> (16 - 2 * i)) ^ (bhist >> (24 - 3 * i)) ^ 18110915Sandreas.sandberg@arm.com (bhist >> (32 - 3 * i)) ^ (bhist >> (40 - 4 * i))) & 18210915Sandreas.sandberg@arm.com ((1 << (logs - gIndexLogsSubstr(nbr, i))) - 1); 18310915Sandreas.sandberg@arm.com} 18410915Sandreas.sandberg@arm.com 18510915Sandreas.sandberg@arm.comint 18610915Sandreas.sandberg@arm.comStatisticalCorrector::gPredict(Addr branch_pc, int64_t hist, 18710915Sandreas.sandberg@arm.com std::vector<int> & length, std::vector<int8_t> * tab, int nbr, 18810915Sandreas.sandberg@arm.com int logs, std::vector<int8_t> & w) 18910915Sandreas.sandberg@arm.com{ 19010915Sandreas.sandberg@arm.com int percsum = 0; 19110915Sandreas.sandberg@arm.com for (int i = 0; i < nbr; i++) { 19210915Sandreas.sandberg@arm.com int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1)); 19310915Sandreas.sandberg@arm.com int64_t index = gIndex(branch_pc, bhist, logs, nbr, i); 19410915Sandreas.sandberg@arm.com int8_t ctr = tab[i][index]; 19510915Sandreas.sandberg@arm.com percsum += (2 * ctr + 1); 19610915Sandreas.sandberg@arm.com } 19710915Sandreas.sandberg@arm.com percsum = (1 + (w[getIndUpds(branch_pc)] >= 0)) * percsum; 19810915Sandreas.sandberg@arm.com return percsum; 19910915Sandreas.sandberg@arm.com} 20010915Sandreas.sandberg@arm.com 20110915Sandreas.sandberg@arm.comvoid 20210915Sandreas.sandberg@arm.comStatisticalCorrector::gUpdate(Addr branch_pc, bool taken, int64_t hist, 20310915Sandreas.sandberg@arm.com std::vector<int> & length, std::vector<int8_t> * tab, 20410915Sandreas.sandberg@arm.com int nbr, int logs, std::vector<int8_t> & w, 20510915Sandreas.sandberg@arm.com BranchInfo* bi) 20610915Sandreas.sandberg@arm.com{ 20710915Sandreas.sandberg@arm.com int percsum = 0; 20810915Sandreas.sandberg@arm.com for (int i = 0; i < nbr; i++) { 20910915Sandreas.sandberg@arm.com int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1)); 21010915Sandreas.sandberg@arm.com int64_t index = gIndex(branch_pc, bhist, logs, nbr, i); 21110915Sandreas.sandberg@arm.com percsum += (2 * tab[i][index] + 1); 21210915Sandreas.sandberg@arm.com ctrUpdate(tab[i][index], taken, scCountersWidth); 21310915Sandreas.sandberg@arm.com } 21410915Sandreas.sandberg@arm.com 21510915Sandreas.sandberg@arm.com int xsum = bi->lsum - ((w[getIndUpds(branch_pc)] >= 0)) * percsum; 21610915Sandreas.sandberg@arm.com if ((xsum + percsum >= 0) != (xsum >= 0)) { 21710915Sandreas.sandberg@arm.com 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