src/cpu/pred/tage_sc_l_8KB.cc

   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
  47 TAGE_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
  57 TAGE_SC_L_8KB_StatisticalCorrector::SCThreadHistory *
  58 TAGE_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
  66 unsigned
  67 TAGE_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
  74 int
  75 TAGE_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
  98 int TAGE_SC_L_8KB_StatisticalCorrector::gIndexLogsSubstr(int nbr, int i)
  99 {
 100     return 0;
 101 }
 102
 103 void
 104 TAGE_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
 123 void
 124 TAGE_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
 135 TAGE_SC_L_8KB_StatisticalCorrector*
 136 TAGE_SC_L_8KB_StatisticalCorrectorParams::create()
 137 {
 138     return new TAGE_SC_L_8KB_StatisticalCorrector(this);
 139 }
 140
 141 TAGE_SC_L_8KB::TAGE_SC_L_8KB(const TAGE_SC_L_8KBParams *params)
 142   : TAGE_SC_L(params)
 143 {
 144 }
 145
 146 void
 147 TAGE_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
 163 int
 164 TAGE_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
 170 uint16_t
 171 TAGE_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
 188 void
 189 TAGE_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
 248 void
 249 TAGE_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
 257 void
 258 TAGE_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
 320 TAGE_SC_L_TAGE_8KB*
 321 TAGE_SC_L_TAGE_8KBParams::create()
 322 {
 323     return new TAGE_SC_L_TAGE_8KB(this);
 324 }
 325
 326 TAGE_SC_L_8KB*
 327 TAGE_SC_L_8KBParams::create()
 328 {
 329     return new TAGE_SC_L_8KB(this);
 330 }