tage_sc_l_8KB.cc revision 14081
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 * 8KB TAGE-SC-L branch predictor (devised by Andre Seznec) 40 */ 41 42#include "cpu/pred/tage_sc_l_8KB.hh" 43 44#include "base/random.hh" 45#include "debug/TageSCL.hh" 46 47TAGE_SC_L_8KB_StatisticalCorrector::TAGE_SC_L_8KB_StatisticalCorrector( 48 TAGE_SC_L_8KB_StatisticalCorrectorParams *p) 49 : StatisticalCorrector(p), 50 gnb(p->gnb), 51 logGnb(p->logGnb), 52 gm(p->gm) 53{ 54 initGEHLTable(gnb, gm, ggehl, logGnb, wg, 7); 55} 56 57TAGE_SC_L_8KB_StatisticalCorrector::SCThreadHistory * 58TAGE_SC_L_8KB_StatisticalCorrector::makeThreadHistory() 59{ 60 SC_8KB_ThreadHistory *sh = new SC_8KB_ThreadHistory(); 61 sh->setNumOrdinalHistories(1); 62 sh->initLocalHistory(1, numEntriesFirstLocalHistories, 2); 63 return sh; 64} 65 66unsigned 67TAGE_SC_L_8KB_StatisticalCorrector::getIndBiasBank(Addr branch_pc, 68 BranchInfo* bi, int hitBank, int altBank) const 69{ 70 return (bi->predBeforeSC + (((hitBank+1)/4)<<4) + (bi->highConf<<1) + 71 (bi->lowConf <<2) +((altBank!=0)<<3)) & ((1<<logBias) -1); 72} 73 74int 75TAGE_SC_L_8KB_StatisticalCorrector::gPredictions( 76 ThreadID tid, Addr branch_pc, BranchInfo* bi, int & lsum, int64_t phist) 77{ 78 SC_8KB_ThreadHistory *sh = static_cast<SC_8KB_ThreadHistory *>(scHistory); 79 lsum += gPredict( 80 branch_pc, sh->globalHist, gm, ggehl, gnb, logGnb, wg); 81 82 lsum += gPredict( 83 branch_pc, sh->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw); 84 85 // only 1 local history here 86 lsum += gPredict( 87 branch_pc, sh->getLocalHistory(1, branch_pc), lm, 88 lgehl, lnb, logLnb, wl); 89 90 lsum += gPredict( 91 branch_pc, sh->imliCount, im, igehl, inb, logInb, wi); 92 93 int thres = (updateThreshold>>3)+pUpdateThreshold[getIndUpd(branch_pc)]; 94 95 return thres; 96} 97 98int TAGE_SC_L_8KB_StatisticalCorrector::gIndexLogsSubstr(int nbr, int i) 99{ 100 return 0; 101} 102 103void 104TAGE_SC_L_8KB_StatisticalCorrector::scHistoryUpdate(Addr branch_pc, 105 const StaticInstPtr &inst, bool taken, BranchInfo *tage_bi, 106 Addr corrTarget) 107{ 108 int brtype = inst->isDirectCtrl() ? 0 : 2; 109 if (! inst->isUncondCtrl()) { 110 ++brtype; 111 } 112 // Non speculative SC histories update 113 if (brtype & 1) { 114 SC_8KB_ThreadHistory *sh = 115 static_cast<SC_8KB_ThreadHistory *>(scHistory); 116 sh->globalHist = (sh->globalHist << 1) + taken; 117 } 118 119 StatisticalCorrector::scHistoryUpdate(branch_pc, inst, taken, tage_bi, 120 corrTarget); 121} 122 123void 124TAGE_SC_L_8KB_StatisticalCorrector::gUpdates(ThreadID tid, Addr pc, bool taken, 125 BranchInfo* bi, int64_t phist) 126{ 127 SC_8KB_ThreadHistory *sh = static_cast<SC_8KB_ThreadHistory *>(scHistory); 128 gUpdate(pc, taken, sh->globalHist, gm, ggehl, gnb, logGnb, wg, bi); 129 gUpdate(pc, taken, sh->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw, bi); 130 gUpdate(pc, taken, sh->getLocalHistory(1, pc), lm, lgehl, lnb, logLnb, wl, 131 bi); 132 gUpdate(pc, taken, sh->imliCount, im, igehl, inb, logInb, wi, bi); 133} 134 135TAGE_SC_L_8KB_StatisticalCorrector* 136TAGE_SC_L_8KB_StatisticalCorrectorParams::create() 137{ 138 return new TAGE_SC_L_8KB_StatisticalCorrector(this); 139} 140 141TAGE_SC_L_8KB::TAGE_SC_L_8KB(const TAGE_SC_L_8KBParams *params) 142 : TAGE_SC_L(params) 143{ 144} 145 146void 147TAGE_SC_L_TAGE_8KB::initFoldedHistories(ThreadHistory & history) 148{ 149 // Some hardcoded values are used here 150 // (they do not seem to depend on any parameter) 151 for (int i = 1; i <= nHistoryTables; i++) { 152 history.computeIndices[i].init( 153 histLengths[i], 17 + (2 * ((i - 1) / 2) % 4)); 154 history.computeTags[0][i].init( 155 history.computeIndices[i].origLength, 13); 156 history.computeTags[1][i].init( 157 history.computeIndices[i].origLength, 11); 158 DPRINTF(TageSCL, "HistLength:%d, TTSize:%d, TTTWidth:%d\n", 159 histLengths[i], logTagTableSizes[i], tagTableTagWidths[i]); 160 } 161} 162 163int 164TAGE_SC_L_TAGE_8KB::gindex_ext(int index, int bank) const 165{ 166 return (index ^ (index >> logTagTableSizes[bank]) 167 ^ (index >> 2 * logTagTableSizes[bank])); 168} 169 170uint16_t 171TAGE_SC_L_TAGE_8KB::gtag(ThreadID tid, Addr pc, int bank) const 172{ 173 int tag = (threadHistory[tid].computeIndices[bank - 1].comp << 2) ^ pc ^ 174 (pc >> instShiftAmt) ^ 175 threadHistory[tid].computeIndices[bank].comp; 176 int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits : 177 histLengths[bank]; 178 179 tag = (tag >> 1) ^ ((tag & 1) << 10) ^ 180 F(threadHistory[tid].pathHist, hlen, bank); 181 tag ^= threadHistory[tid].computeTags[0][bank].comp ^ 182 (threadHistory[tid].computeTags[1][bank].comp << 1); 183 184 return ((tag ^ (tag >> tagTableTagWidths[bank])) 185 & ((ULL(1) << tagTableTagWidths[bank]) - 1)); 186} 187 188void 189TAGE_SC_L_TAGE_8KB::handleAllocAndUReset( 190 bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand) 191{ 192 if (!alloc) { 193 return; 194 } 195 196 int penalty = 0; 197 int truePen = 0; 198 int numAllocated = 0; 199 bool maxAllocReached = false; 200 201 for (int I = calcDep(bi); I < nHistoryTables; I += 2) { 202 // Handle the 2-way associativity for allocation 203 for (int j = 0; j < 2; ++j) { 204 int i = ((j == 0) ? I : (I ^ 1)) + 1; 205 if (i > nHistoryTables) { 206 break; 207 } 208 if (noSkip[i]) { 209 if (gtable[i][bi->tableIndices[i]].u == 0) { 210 gtable[i][bi->tableIndices[i]].u = 211 ((random_mt.random<int>() & 31) == 0); 212 // protect randomly from fast replacement 213 gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i]; 214 gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1; 215 numAllocated++; 216 217 if (numAllocated == maxNumAlloc) { 218 maxAllocReached = true; 219 break; 220 } 221 I += 2; 222 } else { 223 int8_t ctr = gtable[i][bi->tableIndices[i]].ctr; 224 if ((gtable[i][bi->tableIndices[i]].u == 1) & 225 (abs (2 * ctr + 1) == 1)) { 226 if ((random_mt.random<int>() & 7) == 0) { 227 gtable[i][bi->tableIndices[i]].u = 0; 228 } 229 } else { 230 truePen++; 231 } 232 penalty++; 233 } 234 } else { 235 break; 236 } 237 } 238 if (maxAllocReached) { 239 break; 240 } 241 } 242 243 tCounter += (truePen + penalty - 5 * numAllocated); 244 245 handleUReset(); 246} 247 248void 249TAGE_SC_L_TAGE_8KB::resetUctr(uint8_t & u) 250{ 251 // On real HW it should be u >>= 1 instead of if > 0 then u-- 252 if (u > 0) { 253 u--; 254 } 255} 256 257void 258TAGE_SC_L_TAGE_8KB::handleTAGEUpdate(Addr branch_pc, bool taken, 259 TAGEBase::BranchInfo* bi) 260{ 261 if (bi->hitBank > 0) { 262 if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { 263 if (bi->longestMatchPred != taken) { // acts as a protection 264 if (bi->altBank > 0) { 265 int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr; 266 if (abs (2 * ctr + 1) == 1) { 267 gtable[bi->altBank][bi->altBankIndex].u = 0; 268 } 269 270 //just mute from protected to unprotected 271 ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken, 272 tagTableCounterBits); 273 ctr = gtable[bi->altBank][bi->altBankIndex].ctr; 274 if (abs (2 * ctr + 1) == 1) { 275 gtable[bi->altBank][bi->altBankIndex].u = 0; 276 } 277 } 278 if (bi->altBank == 0) { 279 baseUpdate(branch_pc, taken, bi); 280 } 281 } 282 } 283 284 //just mute from protected to unprotected 285 if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { 286 gtable[bi->hitBank][bi->hitBankIndex].u = 0; 287 } 288 289 ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken, 290 tagTableCounterBits); 291 292 //sign changes: no way it can have been useful 293 if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { 294 gtable[bi->hitBank][bi->hitBankIndex].u = 0; 295 } 296 297 if (bi->altTaken == taken) { 298 if (bi->altBank > 0) { 299 int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr; 300 if (abs (2*ctr + 1) == 7) { 301 if (gtable[bi->hitBank][bi->hitBankIndex].u == 1) { 302 if (bi->longestMatchPred == taken) { 303 gtable[bi->hitBank][bi->hitBankIndex].u = 0; 304 } 305 } 306 } 307 } 308 } 309 } else { 310 baseUpdate(branch_pc, taken, bi); 311 } 312 313 if ((bi->longestMatchPred != bi->altTaken) && 314 (bi->longestMatchPred == taken) && 315 (gtable[bi->hitBank][bi->hitBankIndex].u < (1 << tagTableUBits) -1)) { 316 gtable[bi->hitBank][bi->hitBankIndex].u++; 317 } 318} 319 320TAGE_SC_L_TAGE_8KB* 321TAGE_SC_L_TAGE_8KBParams::create() 322{ 323 return new TAGE_SC_L_TAGE_8KB(this); 324} 325 326TAGE_SC_L_8KB* 327TAGE_SC_L_8KBParams::create() 328{ 329 return new TAGE_SC_L_8KB(this); 330} 331