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     const 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::TAGE_SC_L_8KB(const TAGE_SC_L_8KBParams &params)
 136   : TAGE_SC_L(params)
 137 {
 138 }
 139
 140 void
 141 TAGE_SC_L_TAGE_8KB::initFoldedHistories(ThreadHistory & history)
 142 {
 143     // Some hardcoded values are used here
 144     // (they do not seem to depend on any parameter)
 145     for (int i = 1; i <= nHistoryTables; i++) {
 146         history.computeIndices[i].init(
 147             histLengths[i], 17 + (2 * ((i - 1) / 2) % 4));
 148         history.computeTags[0][i].init(
 149             history.computeIndices[i].origLength, 13);
 150         history.computeTags[1][i].init(
 151             history.computeIndices[i].origLength, 11);
 152         DPRINTF(TageSCL, "HistLength:%d, TTSize:%d, TTTWidth:%d\n",
 153                 histLengths[i], logTagTableSizes[i], tagTableTagWidths[i]);
 154     }
 155 }
 156
 157 int
 158 TAGE_SC_L_TAGE_8KB::gindex_ext(int index, int bank) const
 159 {
 160     return (index ^ (index >> logTagTableSizes[bank])
 161                   ^ (index >> 2 * logTagTableSizes[bank]));
 162 }
 163
 164 uint16_t
 165 TAGE_SC_L_TAGE_8KB::gtag(ThreadID tid, Addr pc, int bank) const
 166 {
 167     int tag = (threadHistory[tid].computeIndices[bank - 1].comp << 2) ^ pc ^
 168               (pc >> instShiftAmt) ^
 169               threadHistory[tid].computeIndices[bank].comp;
 170     int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits :
 171                                                     histLengths[bank];
 172
 173     tag = (tag >> 1) ^ ((tag & 1) << 10) ^
 174            F(threadHistory[tid].pathHist, hlen, bank);
 175     tag ^= threadHistory[tid].computeTags[0][bank].comp ^
 176            (threadHistory[tid].computeTags[1][bank].comp << 1);
 177
 178     return ((tag ^ (tag >> tagTableTagWidths[bank]))
 179             & ((ULL(1) << tagTableTagWidths[bank]) - 1));
 180 }
 181
 182 void
 183 TAGE_SC_L_TAGE_8KB::handleAllocAndUReset(
 184     bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand)
 185 {
 186     if (!alloc) {
 187         return;
 188     }
 189
 190     int penalty = 0;
 191     int truePen = 0;
 192     int numAllocated = 0;
 193     bool maxAllocReached = false;
 194
 195     for (int I = calcDep(bi); I < nHistoryTables; I += 2) {
 196         // Handle the 2-way associativity for allocation
 197         for (int j = 0; j < 2; ++j) {
 198             int i = ((j == 0) ? I : (I ^ 1)) + 1;
 199             if (i > nHistoryTables) {
 200                 break;
 201             }
 202             if (noSkip[i]) {
 203                 if (gtable[i][bi->tableIndices[i]].u == 0) {
 204                     gtable[i][bi->tableIndices[i]].u =
 205                         ((random_mt.random<int>() & 31) == 0);
 206                     // protect randomly from fast replacement
 207                     gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i];
 208                     gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1;
 209                     numAllocated++;
 210
 211                     if (numAllocated == maxNumAlloc) {
 212                         maxAllocReached = true;
 213                         break;
 214                     }
 215                     I += 2;
 216                 } else {
 217                     int8_t ctr = gtable[i][bi->tableIndices[i]].ctr;
 218                     if ((gtable[i][bi->tableIndices[i]].u == 1) &
 219                         (abs (2 * ctr + 1) == 1)) {
 220                         if ((random_mt.random<int>() & 7) == 0) {
 221                             gtable[i][bi->tableIndices[i]].u = 0;
 222                         }
 223                     } else {
 224                         truePen++;
 225                     }
 226                     penalty++;
 227                 }
 228             } else {
 229                 break;
 230             }
 231         }
 232         if (maxAllocReached) {
 233             break;
 234         }
 235     }
 236
 237     tCounter += (truePen + penalty - 5 * numAllocated);
 238
 239     handleUReset();
 240 }
 241
 242 void
 243 TAGE_SC_L_TAGE_8KB::resetUctr(uint8_t & u)
 244 {
 245     // On real HW it should be u >>= 1 instead of if > 0 then u--
 246     if (u > 0) {
 247         u--;
 248     }
 249 }
 250
 251 void
 252 TAGE_SC_L_TAGE_8KB::handleTAGEUpdate(Addr branch_pc, bool taken,
 253                                      TAGEBase::BranchInfo* bi)
 254 {
 255     if (bi->hitBank > 0) {
 256         if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
 257             if (bi->longestMatchPred != taken) { // acts as a protection
 258                 if (bi->altBank > 0) {
 259                     int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
 260                     if (abs (2 * ctr + 1) == 1) {
 261                         gtable[bi->altBank][bi->altBankIndex].u = 0;
 262                     }
 263
 264                     //just mute from protected to unprotected
 265                     ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken,
 266                               tagTableCounterBits);
 267                     ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
 268                     if (abs (2 * ctr + 1) == 1) {
 269                         gtable[bi->altBank][bi->altBankIndex].u = 0;
 270                     }
 271                 }
 272                 if (bi->altBank == 0) {
 273                     baseUpdate(branch_pc, taken, bi);
 274                 }
 275             }
 276         }
 277
 278         //just mute from protected to unprotected
 279         if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
 280             gtable[bi->hitBank][bi->hitBankIndex].u = 0;
 281         }
 282
 283         ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken,
 284                   tagTableCounterBits);
 285
 286         //sign changes: no way it can have been useful
 287         if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
 288             gtable[bi->hitBank][bi->hitBankIndex].u = 0;
 289         }
 290
 291         if (bi->altTaken == taken) {
 292             if (bi->altBank > 0) {
 293                 int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
 294                 if (abs (2*ctr + 1) == 7) {
 295                     if (gtable[bi->hitBank][bi->hitBankIndex].u == 1) {
 296                         if (bi->longestMatchPred == taken) {
 297                             gtable[bi->hitBank][bi->hitBankIndex].u = 0;
 298                         }
 299                     }
 300                 }
 301             }
 302         }
 303     } else {
 304         baseUpdate(branch_pc, taken, bi);
 305     }
 306
 307     if ((bi->longestMatchPred != bi->altTaken) &&
 308         (bi->longestMatchPred == taken) &&
 309         (gtable[bi->hitBank][bi->hitBankIndex].u < (1 << tagTableUBits) -1)) {
 310             gtable[bi->hitBank][bi->hitBankIndex].u++;
 311     }
 312 }