tage_sc_l_64KB.cc revision 14081:f99ed78e5263
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 * 64KB TAGE-SC-L branch predictor (devised by Andre Seznec) 40 */ 41 42#include "cpu/pred/tage_sc_l_64KB.hh" 43 44TAGE_SC_L_64KB_StatisticalCorrector::TAGE_SC_L_64KB_StatisticalCorrector( 45 TAGE_SC_L_64KB_StatisticalCorrectorParams *p) 46 : StatisticalCorrector(p), 47 numEntriesSecondLocalHistories(p->numEntriesSecondLocalHistories), 48 numEntriesThirdLocalHistories(p->numEntriesThirdLocalHistories), 49 pnb(p->pnb), 50 logPnb(p->logPnb), 51 pm(p->pm), 52 snb(p->snb), 53 logSnb(p->logSnb), 54 sm(p->sm), 55 tnb(p->tnb), 56 logTnb(p->logTnb), 57 tm(p->tm), 58 imnb(p->imnb), 59 logImnb(p->logImnb), 60 imm(p->imm) 61{ 62 initGEHLTable(pnb, pm, pgehl, logPnb, wp, 7); 63 initGEHLTable(snb, sm, sgehl, logSnb, ws, 7); 64 initGEHLTable(tnb, tm, tgehl, logTnb, wt, 7); 65 initGEHLTable(imnb, imm, imgehl, logImnb, wim, 0); 66 67} 68 69TAGE_SC_L_64KB_StatisticalCorrector::SCThreadHistory* 70TAGE_SC_L_64KB_StatisticalCorrector::makeThreadHistory() 71{ 72 SC_64KB_ThreadHistory *sh = new SC_64KB_ThreadHistory(); 73 74 sh->setNumOrdinalHistories(3); 75 sh->initLocalHistory(1, numEntriesFirstLocalHistories, 2); 76 sh->initLocalHistory(2, numEntriesSecondLocalHistories, 5); 77 sh->initLocalHistory(3, numEntriesThirdLocalHistories, logTnb); 78 79 sh->imHist.resize(1 << im[0]); 80 return sh; 81} 82 83unsigned 84TAGE_SC_L_64KB_StatisticalCorrector::getIndBiasBank(Addr branch_pc, 85 BranchInfo* bi, int hitBank, int altBank) const 86{ 87 return (bi->predBeforeSC + (((hitBank+1)/4)<<4) + (bi->highConf<<1) + 88 (bi->lowConf <<2) + ((altBank!=0)<<3) + 89 ((branch_pc^(branch_pc>>2))<<7)) & ((1<<logBias) -1); 90} 91 92int 93TAGE_SC_L_64KB_StatisticalCorrector::gPredictions(ThreadID tid, Addr branch_pc, 94 BranchInfo* bi, int & lsum, int64_t pathHist) 95{ 96 SC_64KB_ThreadHistory *sh = 97 static_cast<SC_64KB_ThreadHistory *>(scHistory); 98 99 lsum += gPredict( 100 (branch_pc << 1) + bi->predBeforeSC, sh->bwHist, bwm, 101 bwgehl, bwnb, logBwnb, wbw); 102 103 lsum += gPredict( 104 branch_pc, pathHist, pm, pgehl, pnb, logPnb, wp); 105 106 lsum += gPredict( 107 branch_pc, sh->getLocalHistory(1, branch_pc), lm, 108 lgehl, lnb, logLnb, wl); 109 110 lsum += gPredict( 111 branch_pc, sh->getLocalHistory(2, branch_pc), sm, 112 sgehl, snb, logSnb, ws); 113 114 lsum += gPredict( 115 branch_pc, sh->getLocalHistory(3, branch_pc), tm, 116 tgehl, tnb, logTnb, wt); 117 118 lsum += gPredict( 119 branch_pc, sh->imHist[scHistory->imliCount], imm, 120 imgehl, imnb, logImnb, wim); 121 122 lsum += gPredict( 123 branch_pc, sh->imliCount, im, igehl, inb, logInb, wi); 124 125 int thres = (updateThreshold>>3) + pUpdateThreshold[getIndUpd(branch_pc)] 126 + 12*((wb[getIndUpds(branch_pc)] >= 0) + (wp[getIndUpds(branch_pc)] >= 0) 127 + (ws[getIndUpds(branch_pc)] >= 0) + (wt[getIndUpds(branch_pc)] >= 0) 128 + (wl[getIndUpds(branch_pc)] >= 0) + (wbw[getIndUpds(branch_pc)] >= 0) 129 + (wi[getIndUpds(branch_pc)] >= 0)); 130 131 return thres; 132} 133 134int 135TAGE_SC_L_64KB_StatisticalCorrector::gIndexLogsSubstr(int nbr, int i) 136{ 137 return (i >= (nbr - 2)) ? 1 : 0; 138} 139 140void 141TAGE_SC_L_64KB_StatisticalCorrector::scHistoryUpdate(Addr branch_pc, 142 const StaticInstPtr &inst, bool taken, BranchInfo* tage_bi, 143 Addr corrTarget) 144{ 145 int brtype = inst->isDirectCtrl() ? 0 : 2; 146 if (! inst->isUncondCtrl()) { 147 ++brtype; 148 } 149 // Non speculative SC histories update 150 if (brtype & 1) { 151 SC_64KB_ThreadHistory *sh = 152 static_cast<SC_64KB_ThreadHistory *>(scHistory); 153 int64_t imliCount = sh->imliCount; 154 sh->imHist[imliCount] = (sh->imHist[imliCount] << 1) 155 + taken; 156 sh->updateLocalHistory(2, branch_pc, taken, branch_pc & 15); 157 sh->updateLocalHistory(3, branch_pc, taken); 158 } 159 160 StatisticalCorrector::scHistoryUpdate(branch_pc, inst, taken, tage_bi, 161 corrTarget); 162} 163 164void 165TAGE_SC_L_64KB_StatisticalCorrector::gUpdates(ThreadID tid, Addr pc, 166 bool taken, BranchInfo* bi, int64_t phist) 167{ 168 SC_64KB_ThreadHistory *sh = 169 static_cast<SC_64KB_ThreadHistory *>(scHistory); 170 171 gUpdate((pc << 1) + bi->predBeforeSC, taken, sh->bwHist, bwm, 172 bwgehl, bwnb, logBwnb, wbw, bi); 173 174 gUpdate(pc, taken, phist, pm, 175 pgehl, pnb, logPnb, wp, bi); 176 177 gUpdate(pc, taken, sh->getLocalHistory(1, pc), lm, 178 lgehl, lnb, logLnb, wl, bi); 179 180 gUpdate(pc, taken, sh->getLocalHistory(2, pc), sm, 181 sgehl, snb, logSnb, ws, bi); 182 183 gUpdate(pc, taken, sh->getLocalHistory(3, pc), tm, 184 tgehl, tnb, logTnb, wt, bi); 185 186 gUpdate(pc, taken, sh->imHist[scHistory->imliCount], imm, 187 imgehl, imnb, logImnb, wim, bi); 188 189 gUpdate(pc, taken, sh->imliCount, im, 190 igehl, inb, logInb, wi, bi); 191} 192 193TAGE_SC_L_64KB_StatisticalCorrector* 194TAGE_SC_L_64KB_StatisticalCorrectorParams::create() 195{ 196 return new TAGE_SC_L_64KB_StatisticalCorrector(this); 197} 198 199int 200TAGE_SC_L_TAGE_64KB::gindex_ext(int index, int bank) const 201{ 202 return index; 203} 204 205uint16_t 206TAGE_SC_L_TAGE_64KB::gtag(ThreadID tid, Addr pc, int bank) const 207{ 208 // very similar to the TAGE implementation, but w/o shifting the pc 209 int tag = pc ^ threadHistory[tid].computeTags[0][bank].comp ^ 210 (threadHistory[tid].computeTags[1][bank].comp << 1); 211 212 return (tag & ((ULL(1) << tagTableTagWidths[bank]) - 1)); 213} 214 215void 216TAGE_SC_L_TAGE_64KB::handleAllocAndUReset( 217 bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand) 218{ 219 if (! alloc) { 220 return; 221 } 222 223 int penalty = 0; 224 int numAllocated = 0; 225 bool maxAllocReached = false; 226 227 for (int I = calcDep(bi); I < nHistoryTables; I += 2) { 228 // Handle the 2-way associativity for allocation 229 for (int j = 0; j < 2; ++j) { 230 int i = ((j == 0) ? I : (I ^ 1)) + 1; 231 if (noSkip[i]) { 232 if (gtable[i][bi->tableIndices[i]].u == 0) { 233 int8_t ctr = gtable[i][bi->tableIndices[i]].ctr; 234 if (abs (2 * ctr + 1) <= 3) { 235 gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i]; 236 gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1; 237 numAllocated++; 238 maxAllocReached = (numAllocated == maxNumAlloc); 239 I += 2; 240 break; 241 } else { 242 if (gtable[i][bi->tableIndices[i]].ctr > 0) { 243 gtable[i][bi->tableIndices[i]].ctr--; 244 } else { 245 gtable[i][bi->tableIndices[i]].ctr++; 246 } 247 } 248 } else { 249 penalty++; 250 } 251 } 252 } 253 if (maxAllocReached) { 254 break; 255 } 256 } 257 258 tCounter += (penalty - 2 * numAllocated); 259 260 handleUReset(); 261} 262 263void 264TAGE_SC_L_TAGE_64KB::handleTAGEUpdate(Addr branch_pc, bool taken, 265 TAGEBase::BranchInfo* bi) 266{ 267 if (bi->hitBank > 0) { 268 if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { 269 if (bi->longestMatchPred != taken) { 270 // acts as a protection 271 if (bi->altBank > 0) { 272 ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken, 273 tagTableCounterBits); 274 } 275 if (bi->altBank == 0){ 276 baseUpdate(branch_pc, taken, bi); 277 } 278 } 279 } 280 281 ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken, 282 tagTableCounterBits); 283 284 //sign changes: no way it can have been useful 285 if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { 286 gtable[bi->hitBank][bi->hitBankIndex].u = 0; 287 } 288 289 if (bi->altTaken == taken) { 290 if (bi->altBank > 0) { 291 int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr; 292 if (abs (2 * ctr + 1) == 7) { 293 if (gtable[bi->hitBank][bi->hitBankIndex].u == 1) { 294 if (bi->longestMatchPred == taken) { 295 gtable[bi->hitBank][bi->hitBankIndex].u = 0; 296 } 297 } 298 } 299 } 300 } 301 } else { 302 baseUpdate(branch_pc, taken, bi); 303 } 304 305 if ((bi->longestMatchPred != bi->altTaken) && 306 (bi->longestMatchPred == taken) && 307 (gtable[bi->hitBank][bi->hitBankIndex].u < (1 << tagTableUBits) -1)) { 308 gtable[bi->hitBank][bi->hitBankIndex].u++; 309 } 310} 311 312TAGE_SC_L_TAGE_64KB* 313TAGE_SC_L_TAGE_64KBParams::create() 314{ 315 return new TAGE_SC_L_TAGE_64KB(this); 316} 317 318TAGE_SC_L_64KB::TAGE_SC_L_64KB(const TAGE_SC_L_64KBParams *params) 319 : TAGE_SC_L(params) 320{ 321} 322 323TAGE_SC_L_64KB* 324TAGE_SC_L_64KBParams::create() 325{ 326 return new TAGE_SC_L_64KB(this); 327} 328