tage_sc_l_8KB.cc revision 13685:bb3377c81303
112953Sgabeblack@google.com/* 212953Sgabeblack@google.com * Copyright (c) 2018 Metempsy Technology Consulting 312953Sgabeblack@google.com * All rights reserved. 412953Sgabeblack@google.com * 512953Sgabeblack@google.com * Copyright (c) 2006 INRIA (Institut National de Recherche en 612953Sgabeblack@google.com * Informatique et en Automatique / French National Research Institute 712953Sgabeblack@google.com * for Computer Science and Applied Mathematics) 812953Sgabeblack@google.com * 912953Sgabeblack@google.com * All rights reserved. 1012953Sgabeblack@google.com * 1112953Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 1212953Sgabeblack@google.com * modification, are permitted provided that the following conditions are 1312953Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 1412953Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 1512953Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 1612953Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 1712953Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 1812953Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 1912953Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 2012953Sgabeblack@google.com * this software without specific prior written permission. 2112953Sgabeblack@google.com * 2212953Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2312953Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2412953Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2512953Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2612953Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2712953Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2812953Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2912953Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3012953Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3112953Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3212953Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3312957Sgabeblack@google.com * 3412957Sgabeblack@google.com * Author: André Seznec, Pau Cabre, Javier Bueno 3512961Sgabeblack@google.com * 3612954Sgabeblack@google.com */ 3712954Sgabeblack@google.com 3812953Sgabeblack@google.com/* 3912953Sgabeblack@google.com * 8KB TAGE-SC-L branch predictor (devised by Andre Seznec) 4012953Sgabeblack@google.com */ 4112961Sgabeblack@google.com 4212961Sgabeblack@google.com#include "cpu/pred/tage_sc_l_8KB.hh" 4312953Sgabeblack@google.com 4412953Sgabeblack@google.com#include "base/random.hh" 4512953Sgabeblack@google.com#include "debug/TageSCL.hh" 4612953Sgabeblack@google.com 4712954Sgabeblack@google.comTAGE_SC_L_8KB_StatisticalCorrector::TAGE_SC_L_8KB_StatisticalCorrector( 4812954Sgabeblack@google.com TAGE_SC_L_8KB_StatisticalCorrectorParams *p) 4912954Sgabeblack@google.com : StatisticalCorrector(p), 5012954Sgabeblack@google.com gnb(p->gnb), 5112954Sgabeblack@google.com logGnb(p->logGnb), 5212954Sgabeblack@google.com gm(p->gm) 5312954Sgabeblack@google.com{ 5412954Sgabeblack@google.com initGEHLTable(gnb, gm, ggehl, logGnb, wg, 7); 5512954Sgabeblack@google.com} 5612954Sgabeblack@google.com 5712954Sgabeblack@google.comTAGE_SC_L_8KB_StatisticalCorrector::SCThreadHistory * 5812954Sgabeblack@google.comTAGE_SC_L_8KB_StatisticalCorrector::makeThreadHistory() 5912954Sgabeblack@google.com{ 6012954Sgabeblack@google.com SC_8KB_ThreadHistory *sh = new SC_8KB_ThreadHistory(); 6112954Sgabeblack@google.com sh->setNumOrdinalHistories(1); 6212954Sgabeblack@google.com sh->initLocalHistory(1, numEntriesFirstLocalHistories, 2); 6312954Sgabeblack@google.com return sh; 6412954Sgabeblack@google.com} 6512954Sgabeblack@google.com 6612957Sgabeblack@google.comunsigned 6712954Sgabeblack@google.comTAGE_SC_L_8KB_StatisticalCorrector::getIndBiasBank(Addr branch_pc, 6812954Sgabeblack@google.com BranchInfo* bi, int hitBank, int altBank) const 6912954Sgabeblack@google.com{ 7012954Sgabeblack@google.com return (bi->predBeforeSC + (((hitBank+1)/4)<<4) + (bi->highConf<<1) + 7112954Sgabeblack@google.com (bi->lowConf <<2) +((altBank!=0)<<3)) & ((1<<logBias) -1); 7212954Sgabeblack@google.com} 7312954Sgabeblack@google.com 7412954Sgabeblack@google.comint 7512954Sgabeblack@google.comTAGE_SC_L_8KB_StatisticalCorrector::gPredictions( 7612954Sgabeblack@google.com ThreadID tid, Addr branch_pc, BranchInfo* bi, int & lsum, int64_t phist) 7712954Sgabeblack@google.com{ 7812954Sgabeblack@google.com SC_8KB_ThreadHistory *sh = static_cast<SC_8KB_ThreadHistory *>(scHistory); 7912954Sgabeblack@google.com lsum += gPredict( 8012954Sgabeblack@google.com branch_pc, sh->globalHist, gm, ggehl, gnb, logGnb, wg); 8112954Sgabeblack@google.com 8212954Sgabeblack@google.com lsum += gPredict( 8312954Sgabeblack@google.com branch_pc, sh->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw); 8412954Sgabeblack@google.com 8512954Sgabeblack@google.com // only 1 local history here 8612954Sgabeblack@google.com lsum += gPredict( 8712954Sgabeblack@google.com branch_pc, sh->getLocalHistory(1, branch_pc), lm, 8812954Sgabeblack@google.com lgehl, lnb, logLnb, wl); 8912954Sgabeblack@google.com 9012954Sgabeblack@google.com lsum += gPredict( 9112954Sgabeblack@google.com branch_pc, sh->imliCount, im, igehl, inb, logInb, wi); 9212954Sgabeblack@google.com 9312954Sgabeblack@google.com int thres = (updateThreshold>>3)+pUpdateThreshold[getIndUpd(branch_pc)]; 9412954Sgabeblack@google.com 9512954Sgabeblack@google.com return thres; 9612954Sgabeblack@google.com} 9712954Sgabeblack@google.com 9812954Sgabeblack@google.comint TAGE_SC_L_8KB_StatisticalCorrector::gIndexLogsSubstr(int nbr, int i) 9912954Sgabeblack@google.com{ 10012954Sgabeblack@google.com return 0; 10112954Sgabeblack@google.com} 10212954Sgabeblack@google.com 10312954Sgabeblack@google.comvoid 10412954Sgabeblack@google.comTAGE_SC_L_8KB_StatisticalCorrector::scHistoryUpdate(Addr branch_pc, int brtype, 10512954Sgabeblack@google.com bool taken, BranchInfo * tage_bi, Addr corrTarget) 10612954Sgabeblack@google.com{ 10712954Sgabeblack@google.com // Non speculative SC histories update 10812954Sgabeblack@google.com if (brtype & 1) { 10912954Sgabeblack@google.com SC_8KB_ThreadHistory *sh = 11012954Sgabeblack@google.com static_cast<SC_8KB_ThreadHistory *>(scHistory); 11112961Sgabeblack@google.com sh->globalHist = (sh->globalHist << 1) + taken; 11212961Sgabeblack@google.com } 11312961Sgabeblack@google.com 11412961Sgabeblack@google.com StatisticalCorrector::scHistoryUpdate(branch_pc, brtype, taken, tage_bi, 11512961Sgabeblack@google.com corrTarget); 11612961Sgabeblack@google.com} 11712961Sgabeblack@google.com 11812961Sgabeblack@google.comvoid 11912961Sgabeblack@google.comTAGE_SC_L_8KB_StatisticalCorrector::gUpdates(ThreadID tid, Addr pc, bool taken, 12012961Sgabeblack@google.com BranchInfo* bi, int64_t phist) 12112961Sgabeblack@google.com{ 12212961Sgabeblack@google.com SC_8KB_ThreadHistory *sh = static_cast<SC_8KB_ThreadHistory *>(scHistory); 12312961Sgabeblack@google.com gUpdate(pc, taken, sh->globalHist, gm, ggehl, gnb, logGnb, wg, bi); 12412961Sgabeblack@google.com gUpdate(pc, taken, sh->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw, bi); 12512961Sgabeblack@google.com gUpdate(pc, taken, sh->getLocalHistory(1, pc), lm, lgehl, lnb, logLnb, wl, 12612961Sgabeblack@google.com bi); 12712961Sgabeblack@google.com gUpdate(pc, taken, sh->imliCount, im, igehl, inb, logInb, wi, bi); 12812961Sgabeblack@google.com} 12912961Sgabeblack@google.com 13012961Sgabeblack@google.comTAGE_SC_L_8KB_StatisticalCorrector* 13112961Sgabeblack@google.comTAGE_SC_L_8KB_StatisticalCorrectorParams::create() 13212961Sgabeblack@google.com{ 13312961Sgabeblack@google.com return new TAGE_SC_L_8KB_StatisticalCorrector(this); 13412961Sgabeblack@google.com} 13512961Sgabeblack@google.com 13612961Sgabeblack@google.comTAGE_SC_L_8KB::TAGE_SC_L_8KB(const TAGE_SC_L_8KBParams *params) 13712954Sgabeblack@google.com : TAGE_SC_L(params) 13812953Sgabeblack@google.com{ 13912953Sgabeblack@google.com} 14012953Sgabeblack@google.com 14112953Sgabeblack@google.comvoid 14212953Sgabeblack@google.comTAGE_SC_L_TAGE_8KB::initFoldedHistories(ThreadHistory & history) 14312953Sgabeblack@google.com{ 14412954Sgabeblack@google.com // Some hardcoded values are used here 14512954Sgabeblack@google.com // (they do not seem to depend on any parameter) 14612953Sgabeblack@google.com for (int i = 1; i <= nHistoryTables; i++) { 14712953Sgabeblack@google.com history.computeIndices[i].init( 14812953Sgabeblack@google.com histLengths[i], 17 + (2 * ((i - 1) / 2) % 4)); 14912957Sgabeblack@google.com history.computeTags[0][i].init( 15012957Sgabeblack@google.com history.computeIndices[i].origLength, 13); 15112953Sgabeblack@google.com history.computeTags[1][i].init( 15212957Sgabeblack@google.com history.computeIndices[i].origLength, 11); 15312957Sgabeblack@google.com DPRINTF(TageSCL, "HistLength:%d, TTSize:%d, TTTWidth:%d\n", 15412957Sgabeblack@google.com histLengths[i], logTagTableSizes[i], tagTableTagWidths[i]); 15512957Sgabeblack@google.com } 15612957Sgabeblack@google.com} 15712953Sgabeblack@google.com 15812953Sgabeblack@google.comint 15912953Sgabeblack@google.comTAGE_SC_L_TAGE_8KB::gindex_ext(int index, int bank) const 16012953Sgabeblack@google.com{ 16112953Sgabeblack@google.com return (index ^ (index >> logTagTableSizes[bank]) 16212954Sgabeblack@google.com ^ (index >> 2 * logTagTableSizes[bank])); 16312954Sgabeblack@google.com} 16412954Sgabeblack@google.com 16512954Sgabeblack@google.comuint16_t 16612953Sgabeblack@google.comTAGE_SC_L_TAGE_8KB::gtag(ThreadID tid, Addr pc, int bank) const 16712953Sgabeblack@google.com{ 16812953Sgabeblack@google.com int tag = (threadHistory[tid].computeIndices[bank - 1].comp << 2) ^ pc ^ 16912953Sgabeblack@google.com (pc >> instShiftAmt) ^ 17012953Sgabeblack@google.com threadHistory[tid].computeIndices[bank].comp; 17112953Sgabeblack@google.com int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits : 17212953Sgabeblack@google.com histLengths[bank]; 17312953Sgabeblack@google.com 17412953Sgabeblack@google.com tag = (tag >> 1) ^ ((tag & 1) << 10) ^ 17512953Sgabeblack@google.com F(threadHistory[tid].pathHist, hlen, bank); 17612953Sgabeblack@google.com tag ^= threadHistory[tid].computeTags[0][bank].comp ^ 17712953Sgabeblack@google.com (threadHistory[tid].computeTags[1][bank].comp << 1); 17812953Sgabeblack@google.com 17912954Sgabeblack@google.com return ((tag ^ (tag >> tagTableTagWidths[bank])) 18012954Sgabeblack@google.com & ((ULL(1) << tagTableTagWidths[bank]) - 1)); 18112954Sgabeblack@google.com} 18212962Sgabeblack@google.com 18312962Sgabeblack@google.comvoid 18412962Sgabeblack@google.comTAGE_SC_L_TAGE_8KB::handleAllocAndUReset( 18512962Sgabeblack@google.com bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand) 18612962Sgabeblack@google.com{ 18712962Sgabeblack@google.com if (!alloc) { 18812962Sgabeblack@google.com return; 18912962Sgabeblack@google.com } 19012962Sgabeblack@google.com 19112962Sgabeblack@google.com int penalty = 0; 19212962Sgabeblack@google.com int truePen = 0; 19312962Sgabeblack@google.com int numAllocated = 0; 19412962Sgabeblack@google.com bool maxAllocReached = false; 19512962Sgabeblack@google.com 19612962Sgabeblack@google.com for (int I = calcDep(bi); I < nHistoryTables; I += 2) { 19712962Sgabeblack@google.com // Handle the 2-way associativity for allocation 19812962Sgabeblack@google.com for (int j = 0; j < 2; ++j) { 19912962Sgabeblack@google.com int i = ((j == 0) ? I : (I ^ 1)) + 1; 20012962Sgabeblack@google.com if (i > nHistoryTables) { 20112962Sgabeblack@google.com break; 20212962Sgabeblack@google.com } 20312962Sgabeblack@google.com if (noSkip[i]) { 20412962Sgabeblack@google.com if (gtable[i][bi->tableIndices[i]].u == 0) { 20512962Sgabeblack@google.com gtable[i][bi->tableIndices[i]].u = 20612962Sgabeblack@google.com ((random_mt.random<int>() & 31) == 0); 20712962Sgabeblack@google.com // protect randomly from fast replacement 20812962Sgabeblack@google.com gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i]; 20912962Sgabeblack@google.com gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1; 21012962Sgabeblack@google.com numAllocated++; 21112962Sgabeblack@google.com 21212962Sgabeblack@google.com if (numAllocated == maxNumAlloc) { 21312962Sgabeblack@google.com maxAllocReached = true; 21412962Sgabeblack@google.com break; 21512962Sgabeblack@google.com } 21612962Sgabeblack@google.com I += 2; 21712962Sgabeblack@google.com } else { 21812962Sgabeblack@google.com int8_t ctr = gtable[i][bi->tableIndices[i]].ctr; 21912962Sgabeblack@google.com if ((gtable[i][bi->tableIndices[i]].u == 1) & 22012962Sgabeblack@google.com (abs (2 * ctr + 1) == 1)) { 22112962Sgabeblack@google.com if ((random_mt.random<int>() & 7) == 0) { 22212962Sgabeblack@google.com gtable[i][bi->tableIndices[i]].u = 0; 22312962Sgabeblack@google.com } 22412962Sgabeblack@google.com } else { 22512962Sgabeblack@google.com truePen++; 22612962Sgabeblack@google.com } 22712962Sgabeblack@google.com penalty++; 22812962Sgabeblack@google.com } 22912962Sgabeblack@google.com } else { 23012962Sgabeblack@google.com break; 23112962Sgabeblack@google.com } 23212962Sgabeblack@google.com } 23312962Sgabeblack@google.com if (maxAllocReached) { 23412962Sgabeblack@google.com break; 23512962Sgabeblack@google.com } 23612962Sgabeblack@google.com } 23712962Sgabeblack@google.com 23812962Sgabeblack@google.com tCounter += (truePen + penalty - 5 * numAllocated); 23912962Sgabeblack@google.com 24012962Sgabeblack@google.com handleUReset(); 24112962Sgabeblack@google.com} 24212962Sgabeblack@google.com 24312962Sgabeblack@google.comvoid 24412962Sgabeblack@google.comTAGE_SC_L_TAGE_8KB::resetUctr(uint8_t & u) 24512962Sgabeblack@google.com{ 24612962Sgabeblack@google.com // On real HW it should be u >>= 1 instead of if > 0 then u-- 24712962Sgabeblack@google.com if (u > 0) { 24812962Sgabeblack@google.com u--; 24912962Sgabeblack@google.com } 25012962Sgabeblack@google.com} 25112954Sgabeblack@google.com 25212954Sgabeblack@google.comvoid 25312954Sgabeblack@google.comTAGE_SC_L_TAGE_8KB::handleTAGEUpdate(Addr branch_pc, bool taken, 25412954Sgabeblack@google.com TAGEBase::BranchInfo* bi) 25512961Sgabeblack@google.com{ 25612961Sgabeblack@google.com if (bi->hitBank > 0) { 25712961Sgabeblack@google.com if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { 25812961Sgabeblack@google.com if (bi->longestMatchPred != taken) { // acts as a protection 25912961Sgabeblack@google.com if (bi->altBank > 0) { 26012961Sgabeblack@google.com int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr; 26112961Sgabeblack@google.com if (abs (2 * ctr + 1) == 1) { 26212961Sgabeblack@google.com gtable[bi->altBank][bi->altBankIndex].u = 0; 26312961Sgabeblack@google.com } 26412961Sgabeblack@google.com 26512953Sgabeblack@google.com //just mute from protected to unprotected 26612961Sgabeblack@google.com ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken, 26712961Sgabeblack@google.com tagTableCounterBits); 26812961Sgabeblack@google.com ctr = gtable[bi->altBank][bi->altBankIndex].ctr; 26912961Sgabeblack@google.com if (abs (2 * ctr + 1) == 1) { 27012961Sgabeblack@google.com gtable[bi->altBank][bi->altBankIndex].u = 0; 27112961Sgabeblack@google.com } 27212961Sgabeblack@google.com } 27312961Sgabeblack@google.com if (bi->altBank == 0) { 27412954Sgabeblack@google.com baseUpdate(branch_pc, taken, bi); 27512962Sgabeblack@google.com } 27612954Sgabeblack@google.com } 27712954Sgabeblack@google.com } 27812954Sgabeblack@google.com 27912954Sgabeblack@google.com //just mute from protected to unprotected 28012954Sgabeblack@google.com if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { 28112961Sgabeblack@google.com gtable[bi->hitBank][bi->hitBankIndex].u = 0; 28212961Sgabeblack@google.com } 28312961Sgabeblack@google.com 28412961Sgabeblack@google.com ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken, 28512961Sgabeblack@google.com tagTableCounterBits); 28612961Sgabeblack@google.com 28712961Sgabeblack@google.com //sign changes: no way it can have been useful 28812961Sgabeblack@google.com if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { 28912961Sgabeblack@google.com gtable[bi->hitBank][bi->hitBankIndex].u = 0; 29012961Sgabeblack@google.com } 29112961Sgabeblack@google.com 29212961Sgabeblack@google.com if (bi->altTaken == taken) { 29312961Sgabeblack@google.com if (bi->altBank > 0) { 29412953Sgabeblack@google.com int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr; 29512953Sgabeblack@google.com if (abs (2*ctr + 1) == 7) { 29612953Sgabeblack@google.com if (gtable[bi->hitBank][bi->hitBankIndex].u == 1) { 29712953Sgabeblack@google.com if (bi->longestMatchPred == taken) { 29812957Sgabeblack@google.com gtable[bi->hitBank][bi->hitBankIndex].u = 0; 29912957Sgabeblack@google.com } 30012953Sgabeblack@google.com } 30112957Sgabeblack@google.com } 30212953Sgabeblack@google.com } 30312953Sgabeblack@google.com } 30412954Sgabeblack@google.com } else { 30512953Sgabeblack@google.com baseUpdate(branch_pc, taken, bi); 30612953Sgabeblack@google.com } 30712953Sgabeblack@google.com 30812953Sgabeblack@google.com if ((bi->longestMatchPred != bi->altTaken) && 30912953Sgabeblack@google.com (bi->longestMatchPred == taken) && 31012953Sgabeblack@google.com (gtable[bi->hitBank][bi->hitBankIndex].u < (1 << tagTableUBits) -1)) { 31112953Sgabeblack@google.com gtable[bi->hitBank][bi->hitBankIndex].u++; 312 } 313} 314 315TAGE_SC_L_TAGE_8KB* 316TAGE_SC_L_TAGE_8KBParams::create() 317{ 318 return new TAGE_SC_L_TAGE_8KB(this); 319} 320 321TAGE_SC_L_8KB* 322TAGE_SC_L_8KBParams::create() 323{ 324 return new TAGE_SC_L_8KB(this); 325} 326