ltage.cc revision 13444
111784Sarthur.perais@inria.fr/* 211784Sarthur.perais@inria.fr * Copyright (c) 2014 The University of Wisconsin 311784Sarthur.perais@inria.fr * 411784Sarthur.perais@inria.fr * Copyright (c) 2006 INRIA (Institut National de Recherche en 511784Sarthur.perais@inria.fr * Informatique et en Automatique / French National Research Institute 611784Sarthur.perais@inria.fr * for Computer Science and Applied Mathematics) 711784Sarthur.perais@inria.fr * 811784Sarthur.perais@inria.fr * All rights reserved. 911784Sarthur.perais@inria.fr * 1011784Sarthur.perais@inria.fr * Redistribution and use in source and binary forms, with or without 1111784Sarthur.perais@inria.fr * modification, are permitted provided that the following conditions are 1211784Sarthur.perais@inria.fr * met: redistributions of source code must retain the above copyright 1311784Sarthur.perais@inria.fr * notice, this list of conditions and the following disclaimer; 1411784Sarthur.perais@inria.fr * redistributions in binary form must reproduce the above copyright 1511784Sarthur.perais@inria.fr * notice, this list of conditions and the following disclaimer in the 1611784Sarthur.perais@inria.fr * documentation and/or other materials provided with the distribution; 1711784Sarthur.perais@inria.fr * neither the name of the copyright holders nor the names of its 1811784Sarthur.perais@inria.fr * contributors may be used to endorse or promote products derived from 1911784Sarthur.perais@inria.fr * this software without specific prior written permission. 2011784Sarthur.perais@inria.fr * 2111784Sarthur.perais@inria.fr * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2211784Sarthur.perais@inria.fr * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2311784Sarthur.perais@inria.fr * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2411784Sarthur.perais@inria.fr * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2511784Sarthur.perais@inria.fr * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2611784Sarthur.perais@inria.fr * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2711784Sarthur.perais@inria.fr * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2811784Sarthur.perais@inria.fr * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2911784Sarthur.perais@inria.fr * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3011784Sarthur.perais@inria.fr * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3111784Sarthur.perais@inria.fr * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3211784Sarthur.perais@inria.fr * 3311784Sarthur.perais@inria.fr * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais, 3411784Sarthur.perais@inria.fr * from André Seznec's code. 3511784Sarthur.perais@inria.fr */ 3611784Sarthur.perais@inria.fr 3711784Sarthur.perais@inria.fr/* @file 3811784Sarthur.perais@inria.fr * Implementation of a L-TAGE branch predictor 3911784Sarthur.perais@inria.fr */ 4011784Sarthur.perais@inria.fr 4111784Sarthur.perais@inria.fr#include "cpu/pred/ltage.hh" 4211784Sarthur.perais@inria.fr 4311784Sarthur.perais@inria.fr#include "base/intmath.hh" 4412334Sgabeblack@google.com#include "base/logging.hh" 4511784Sarthur.perais@inria.fr#include "base/random.hh" 4611784Sarthur.perais@inria.fr#include "base/trace.hh" 4711784Sarthur.perais@inria.fr#include "debug/Fetch.hh" 4811784Sarthur.perais@inria.fr#include "debug/LTage.hh" 4911784Sarthur.perais@inria.fr 5011784Sarthur.perais@inria.frLTAGE::LTAGE(const LTAGEParams *params) 5111784Sarthur.perais@inria.fr : BPredUnit(params), 5213420Spau.cabre@metempsy.com logRatioBiModalHystEntries(params->logRatioBiModalHystEntries), 5311784Sarthur.perais@inria.fr logSizeLoopPred(params->logSizeLoopPred), 5411784Sarthur.perais@inria.fr nHistoryTables(params->nHistoryTables), 5511784Sarthur.perais@inria.fr tagTableCounterBits(params->tagTableCounterBits), 5613443Spau.cabre@metempsy.com tagTableUBits(params->tagTableUBits), 5711784Sarthur.perais@inria.fr histBufferSize(params->histBufferSize), 5811784Sarthur.perais@inria.fr minHist(params->minHist), 5911784Sarthur.perais@inria.fr maxHist(params->maxHist), 6013444Spau.cabre@metempsy.com pathHistBits(params->pathHistBits), 6113442Spau.cabre@metempsy.com loopTableAgeBits(params->loopTableAgeBits), 6213442Spau.cabre@metempsy.com loopTableConfidenceBits(params->loopTableConfidenceBits), 6313442Spau.cabre@metempsy.com loopTableTagBits(params->loopTableTagBits), 6413442Spau.cabre@metempsy.com loopTableIterBits(params->loopTableIterBits), 6513444Spau.cabre@metempsy.com logLoopTableAssoc(params->logLoopTableAssoc), 6613442Spau.cabre@metempsy.com confidenceThreshold((1 << loopTableConfidenceBits) - 1), 6713442Spau.cabre@metempsy.com loopTagMask((1 << loopTableTagBits) - 1), 6813442Spau.cabre@metempsy.com loopNumIterMask((1 << loopTableIterBits) - 1), 6913444Spau.cabre@metempsy.com tagTableTagWidths(params->tagTableTagWidths), 7013444Spau.cabre@metempsy.com logTagTableSizes(params->logTagTableSizes), 7113444Spau.cabre@metempsy.com threadHistory(params->numThreads), 7213444Spau.cabre@metempsy.com logUResetPeriod(params->logUResetPeriod), 7313444Spau.cabre@metempsy.com useAltOnNaBits(params->useAltOnNaBits), 7413444Spau.cabre@metempsy.com withLoopBits(params->withLoopBits) 7511784Sarthur.perais@inria.fr{ 7613443Spau.cabre@metempsy.com // Current method for periodically resetting the u counter bits only 7713443Spau.cabre@metempsy.com // works for 1 or 2 bits 7813443Spau.cabre@metempsy.com // Also make sure that it is not 0 7913443Spau.cabre@metempsy.com assert(tagTableUBits <= 2 && (tagTableUBits > 0)); 8013443Spau.cabre@metempsy.com 8113442Spau.cabre@metempsy.com // we use uint16_t type for these vales, so they cannot be more than 8213442Spau.cabre@metempsy.com // 16 bits 8313442Spau.cabre@metempsy.com assert(loopTableTagBits <= 16); 8413442Spau.cabre@metempsy.com assert(loopTableIterBits <= 16); 8513442Spau.cabre@metempsy.com 8613444Spau.cabre@metempsy.com assert(logSizeLoopPred >= logLoopTableAssoc); 8713444Spau.cabre@metempsy.com 8813444Spau.cabre@metempsy.com // we use int type for the path history, so it cannot be more than 8913444Spau.cabre@metempsy.com // its size 9013444Spau.cabre@metempsy.com assert(pathHistBits <= (sizeof(int)*8)); 9113444Spau.cabre@metempsy.com 9213444Spau.cabre@metempsy.com // initialize the counter to half of the period 9313444Spau.cabre@metempsy.com assert(logUResetPeriod != 0); 9413444Spau.cabre@metempsy.com tCounter = ULL(1) << (logUResetPeriod - 1); 9513444Spau.cabre@metempsy.com 9611784Sarthur.perais@inria.fr assert(params->histBufferSize > params->maxHist * 2); 9711784Sarthur.perais@inria.fr useAltPredForNewlyAllocated = 0; 9811784Sarthur.perais@inria.fr 9911784Sarthur.perais@inria.fr for (auto& history : threadHistory) { 10011784Sarthur.perais@inria.fr history.pathHist = 0; 10111784Sarthur.perais@inria.fr history.globalHistory = new uint8_t[histBufferSize]; 10211784Sarthur.perais@inria.fr history.gHist = history.globalHistory; 10311784Sarthur.perais@inria.fr memset(history.gHist, 0, histBufferSize); 10411784Sarthur.perais@inria.fr history.ptGhist = 0; 10511784Sarthur.perais@inria.fr } 10611784Sarthur.perais@inria.fr 10711784Sarthur.perais@inria.fr histLengths = new int [nHistoryTables+1]; 10811784Sarthur.perais@inria.fr histLengths[1] = minHist; 10911784Sarthur.perais@inria.fr histLengths[nHistoryTables] = maxHist; 11011784Sarthur.perais@inria.fr 11111784Sarthur.perais@inria.fr for (int i = 2; i <= nHistoryTables; i++) { 11211784Sarthur.perais@inria.fr histLengths[i] = (int) (((double) minHist * 11311784Sarthur.perais@inria.fr pow ((double) (maxHist) / (double) minHist, 11411784Sarthur.perais@inria.fr (double) (i - 1) / (double) ((nHistoryTables- 1)))) 11511784Sarthur.perais@inria.fr + 0.5); 11611784Sarthur.perais@inria.fr } 11711784Sarthur.perais@inria.fr 11813444Spau.cabre@metempsy.com assert(tagTableTagWidths.size() == (nHistoryTables+1)); 11913444Spau.cabre@metempsy.com assert(logTagTableSizes.size() == (nHistoryTables+1)); 12011784Sarthur.perais@inria.fr 12113444Spau.cabre@metempsy.com // First entry is for the Bimodal table and it is untagged in this 12213444Spau.cabre@metempsy.com // implementation 12313444Spau.cabre@metempsy.com assert(tagTableTagWidths[0] == 0); 12411784Sarthur.perais@inria.fr 12511784Sarthur.perais@inria.fr for (auto& history : threadHistory) { 12611784Sarthur.perais@inria.fr history.computeIndices = new FoldedHistory[nHistoryTables+1]; 12711784Sarthur.perais@inria.fr history.computeTags[0] = new FoldedHistory[nHistoryTables+1]; 12811784Sarthur.perais@inria.fr history.computeTags[1] = new FoldedHistory[nHistoryTables+1]; 12911784Sarthur.perais@inria.fr 13011784Sarthur.perais@inria.fr for (int i = 1; i <= nHistoryTables; i++) { 13113444Spau.cabre@metempsy.com history.computeIndices[i].init( 13213444Spau.cabre@metempsy.com histLengths[i], (logTagTableSizes[i])); 13311784Sarthur.perais@inria.fr history.computeTags[0][i].init( 13413444Spau.cabre@metempsy.com history.computeIndices[i].origLength, tagTableTagWidths[i]); 13511784Sarthur.perais@inria.fr history.computeTags[1][i].init( 13613444Spau.cabre@metempsy.com history.computeIndices[i].origLength, tagTableTagWidths[i]-1); 13711784Sarthur.perais@inria.fr DPRINTF(LTage, "HistLength:%d, TTSize:%d, TTTWidth:%d\n", 13813444Spau.cabre@metempsy.com histLengths[i], logTagTableSizes[i], tagTableTagWidths[i]); 13911784Sarthur.perais@inria.fr } 14011784Sarthur.perais@inria.fr } 14111784Sarthur.perais@inria.fr 14213444Spau.cabre@metempsy.com const uint64_t bimodalTableSize = ULL(1) << logTagTableSizes[0]; 14313420Spau.cabre@metempsy.com btablePrediction.resize(bimodalTableSize, false); 14413420Spau.cabre@metempsy.com btableHysteresis.resize(bimodalTableSize >> logRatioBiModalHystEntries, 14513420Spau.cabre@metempsy.com true); 14613420Spau.cabre@metempsy.com 14711784Sarthur.perais@inria.fr ltable = new LoopEntry[ULL(1) << logSizeLoopPred]; 14811784Sarthur.perais@inria.fr gtable = new TageEntry*[nHistoryTables + 1]; 14911784Sarthur.perais@inria.fr for (int i = 1; i <= nHistoryTables; i++) { 15013444Spau.cabre@metempsy.com gtable[i] = new TageEntry[1<<(logTagTableSizes[i])]; 15111784Sarthur.perais@inria.fr } 15211784Sarthur.perais@inria.fr 15311784Sarthur.perais@inria.fr tableIndices = new int [nHistoryTables+1]; 15411784Sarthur.perais@inria.fr tableTags = new int [nHistoryTables+1]; 15511784Sarthur.perais@inria.fr 15611784Sarthur.perais@inria.fr loopUseCounter = 0; 15711784Sarthur.perais@inria.fr} 15811784Sarthur.perais@inria.fr 15911784Sarthur.perais@inria.frint 16011784Sarthur.perais@inria.frLTAGE::bindex(Addr pc_in) const 16111784Sarthur.perais@inria.fr{ 16213444Spau.cabre@metempsy.com return ((pc_in >> instShiftAmt) & ((ULL(1) << (logTagTableSizes[0])) - 1)); 16311784Sarthur.perais@inria.fr} 16411784Sarthur.perais@inria.fr 16511784Sarthur.perais@inria.frint 16611784Sarthur.perais@inria.frLTAGE::lindex(Addr pc_in) const 16711784Sarthur.perais@inria.fr{ 16813444Spau.cabre@metempsy.com // The loop table is implemented as a linear table 16913444Spau.cabre@metempsy.com // If associativity is N (N being 1 << logLoopTableAssoc), 17013444Spau.cabre@metempsy.com // the first N entries are for set 0, the next N entries are for set 1, 17113444Spau.cabre@metempsy.com // and so on. 17213444Spau.cabre@metempsy.com // Thus, this function calculates the set and then it gets left shifted 17313444Spau.cabre@metempsy.com // by logLoopTableAssoc in order to return the index of the first of the 17413444Spau.cabre@metempsy.com // N entries of the set 17513444Spau.cabre@metempsy.com Addr mask = (ULL(1) << (logSizeLoopPred - logLoopTableAssoc)) - 1; 17613444Spau.cabre@metempsy.com return (((pc_in >> instShiftAmt) & mask) << logLoopTableAssoc); 17711784Sarthur.perais@inria.fr} 17811784Sarthur.perais@inria.fr 17911784Sarthur.perais@inria.frint 18011784Sarthur.perais@inria.frLTAGE::F(int A, int size, int bank) const 18111784Sarthur.perais@inria.fr{ 18211784Sarthur.perais@inria.fr int A1, A2; 18311784Sarthur.perais@inria.fr 18411784Sarthur.perais@inria.fr A = A & ((ULL(1) << size) - 1); 18513444Spau.cabre@metempsy.com A1 = (A & ((ULL(1) << logTagTableSizes[bank]) - 1)); 18613444Spau.cabre@metempsy.com A2 = (A >> logTagTableSizes[bank]); 18713444Spau.cabre@metempsy.com A2 = ((A2 << bank) & ((ULL(1) << logTagTableSizes[bank]) - 1)) 18813444Spau.cabre@metempsy.com + (A2 >> (logTagTableSizes[bank] - bank)); 18911784Sarthur.perais@inria.fr A = A1 ^ A2; 19013444Spau.cabre@metempsy.com A = ((A << bank) & ((ULL(1) << logTagTableSizes[bank]) - 1)) 19113444Spau.cabre@metempsy.com + (A >> (logTagTableSizes[bank] - bank)); 19211784Sarthur.perais@inria.fr return (A); 19311784Sarthur.perais@inria.fr} 19411784Sarthur.perais@inria.fr 19511784Sarthur.perais@inria.fr 19611784Sarthur.perais@inria.fr// gindex computes a full hash of pc, ghist and pathHist 19711784Sarthur.perais@inria.frint 19811784Sarthur.perais@inria.frLTAGE::gindex(ThreadID tid, Addr pc, int bank) const 19911784Sarthur.perais@inria.fr{ 20011784Sarthur.perais@inria.fr int index; 20113444Spau.cabre@metempsy.com int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits : 20213444Spau.cabre@metempsy.com histLengths[bank]; 20313444Spau.cabre@metempsy.com const Addr shiftedPc = pc >> instShiftAmt; 20411784Sarthur.perais@inria.fr index = 20513444Spau.cabre@metempsy.com shiftedPc ^ 20613444Spau.cabre@metempsy.com (shiftedPc >> ((int) abs(logTagTableSizes[bank] - bank) + 1)) ^ 20711784Sarthur.perais@inria.fr threadHistory[tid].computeIndices[bank].comp ^ 20811784Sarthur.perais@inria.fr F(threadHistory[tid].pathHist, hlen, bank); 20911784Sarthur.perais@inria.fr 21013444Spau.cabre@metempsy.com return (index & ((ULL(1) << (logTagTableSizes[bank])) - 1)); 21111784Sarthur.perais@inria.fr} 21211784Sarthur.perais@inria.fr 21311784Sarthur.perais@inria.fr 21411784Sarthur.perais@inria.fr// Tag computation 21511784Sarthur.perais@inria.fruint16_t 21611784Sarthur.perais@inria.frLTAGE::gtag(ThreadID tid, Addr pc, int bank) const 21711784Sarthur.perais@inria.fr{ 21813413Spau.cabre@metempsy.com int tag = (pc >> instShiftAmt) ^ 21913413Spau.cabre@metempsy.com threadHistory[tid].computeTags[0][bank].comp ^ 22013413Spau.cabre@metempsy.com (threadHistory[tid].computeTags[1][bank].comp << 1); 22111784Sarthur.perais@inria.fr 22213444Spau.cabre@metempsy.com return (tag & ((ULL(1) << tagTableTagWidths[bank]) - 1)); 22311784Sarthur.perais@inria.fr} 22411784Sarthur.perais@inria.fr 22511784Sarthur.perais@inria.fr 22611784Sarthur.perais@inria.fr// Up-down saturating counter 22711784Sarthur.perais@inria.frvoid 22811784Sarthur.perais@inria.frLTAGE::ctrUpdate(int8_t & ctr, bool taken, int nbits) 22911784Sarthur.perais@inria.fr{ 23011784Sarthur.perais@inria.fr assert(nbits <= sizeof(int8_t) << 3); 23111784Sarthur.perais@inria.fr if (taken) { 23211784Sarthur.perais@inria.fr if (ctr < ((1 << (nbits - 1)) - 1)) 23311784Sarthur.perais@inria.fr ctr++; 23411784Sarthur.perais@inria.fr } else { 23511784Sarthur.perais@inria.fr if (ctr > -(1 << (nbits - 1))) 23611784Sarthur.perais@inria.fr ctr--; 23711784Sarthur.perais@inria.fr } 23811784Sarthur.perais@inria.fr} 23911784Sarthur.perais@inria.fr 24013442Spau.cabre@metempsy.com// Up-down unsigned saturating counter 24113442Spau.cabre@metempsy.comvoid 24213442Spau.cabre@metempsy.comLTAGE::unsignedCtrUpdate(uint8_t & ctr, bool up, unsigned nbits) 24313442Spau.cabre@metempsy.com{ 24413442Spau.cabre@metempsy.com assert(nbits <= sizeof(uint8_t) << 3); 24513442Spau.cabre@metempsy.com if (up) { 24613442Spau.cabre@metempsy.com if (ctr < ((1 << nbits) - 1)) 24713442Spau.cabre@metempsy.com ctr++; 24813442Spau.cabre@metempsy.com } else { 24913442Spau.cabre@metempsy.com if (ctr) 25013442Spau.cabre@metempsy.com ctr--; 25113442Spau.cabre@metempsy.com } 25213442Spau.cabre@metempsy.com} 25313442Spau.cabre@metempsy.com 25411784Sarthur.perais@inria.fr// Bimodal prediction 25511784Sarthur.perais@inria.frbool 25611784Sarthur.perais@inria.frLTAGE::getBimodePred(Addr pc, BranchInfo* bi) const 25711784Sarthur.perais@inria.fr{ 25813420Spau.cabre@metempsy.com return btablePrediction[bi->bimodalIndex]; 25911784Sarthur.perais@inria.fr} 26011784Sarthur.perais@inria.fr 26111784Sarthur.perais@inria.fr 26213420Spau.cabre@metempsy.com// Update the bimodal predictor: a hysteresis bit is shared among N prediction 26313420Spau.cabre@metempsy.com// bits (N = 2 ^ logRatioBiModalHystEntries) 26411784Sarthur.perais@inria.frvoid 26511784Sarthur.perais@inria.frLTAGE::baseUpdate(Addr pc, bool taken, BranchInfo* bi) 26611784Sarthur.perais@inria.fr{ 26713420Spau.cabre@metempsy.com int inter = (btablePrediction[bi->bimodalIndex] << 1) 26813420Spau.cabre@metempsy.com + btableHysteresis[bi->bimodalIndex >> logRatioBiModalHystEntries]; 26911784Sarthur.perais@inria.fr if (taken) { 27011784Sarthur.perais@inria.fr if (inter < 3) 27111784Sarthur.perais@inria.fr inter++; 27211784Sarthur.perais@inria.fr } else if (inter > 0) { 27311784Sarthur.perais@inria.fr inter--; 27411784Sarthur.perais@inria.fr } 27513420Spau.cabre@metempsy.com const bool pred = inter >> 1; 27613420Spau.cabre@metempsy.com const bool hyst = inter & 1; 27713420Spau.cabre@metempsy.com btablePrediction[bi->bimodalIndex] = pred; 27813420Spau.cabre@metempsy.com btableHysteresis[bi->bimodalIndex >> logRatioBiModalHystEntries] = hyst; 27913420Spau.cabre@metempsy.com DPRINTF(LTage, "Updating branch %lx, pred:%d, hyst:%d\n", pc, pred, hyst); 28011784Sarthur.perais@inria.fr} 28111784Sarthur.perais@inria.fr 28211784Sarthur.perais@inria.fr 28311784Sarthur.perais@inria.fr//loop prediction: only used if high confidence 28411784Sarthur.perais@inria.frbool 28511784Sarthur.perais@inria.frLTAGE::getLoop(Addr pc, BranchInfo* bi) const 28611784Sarthur.perais@inria.fr{ 28711784Sarthur.perais@inria.fr bi->loopHit = -1; 28811784Sarthur.perais@inria.fr bi->loopPredValid = false; 28911784Sarthur.perais@inria.fr bi->loopIndex = lindex(pc); 29013444Spau.cabre@metempsy.com unsigned pcShift = instShiftAmt + logSizeLoopPred - logLoopTableAssoc; 29113444Spau.cabre@metempsy.com bi->loopTag = ((pc) >> pcShift) & loopTagMask; 29211784Sarthur.perais@inria.fr 29313444Spau.cabre@metempsy.com for (int i = 0; i < (1 << logLoopTableAssoc); i++) { 29411784Sarthur.perais@inria.fr if (ltable[bi->loopIndex + i].tag == bi->loopTag) { 29511784Sarthur.perais@inria.fr bi->loopHit = i; 29613442Spau.cabre@metempsy.com bi->loopPredValid = 29713442Spau.cabre@metempsy.com ltable[bi->loopIndex + i].confidence == confidenceThreshold; 29811784Sarthur.perais@inria.fr bi->currentIter = ltable[bi->loopIndex + i].currentIterSpec; 29911784Sarthur.perais@inria.fr if (ltable[bi->loopIndex + i].currentIterSpec + 1 == 30011784Sarthur.perais@inria.fr ltable[bi->loopIndex + i].numIter) { 30111784Sarthur.perais@inria.fr return !(ltable[bi->loopIndex + i].dir); 30211784Sarthur.perais@inria.fr }else { 30311784Sarthur.perais@inria.fr return (ltable[bi->loopIndex + i].dir); 30411784Sarthur.perais@inria.fr } 30511784Sarthur.perais@inria.fr } 30611784Sarthur.perais@inria.fr } 30711784Sarthur.perais@inria.fr return false; 30811784Sarthur.perais@inria.fr} 30911784Sarthur.perais@inria.fr 31011784Sarthur.perais@inria.frvoid 31111784Sarthur.perais@inria.frLTAGE::specLoopUpdate(Addr pc, bool taken, BranchInfo* bi) 31211784Sarthur.perais@inria.fr{ 31311784Sarthur.perais@inria.fr if (bi->loopHit>=0) { 31411784Sarthur.perais@inria.fr int index = lindex(pc); 31511784Sarthur.perais@inria.fr if (taken != ltable[index].dir) { 31611784Sarthur.perais@inria.fr ltable[index].currentIterSpec = 0; 31711784Sarthur.perais@inria.fr } else { 31813442Spau.cabre@metempsy.com ltable[index].currentIterSpec = 31913442Spau.cabre@metempsy.com (ltable[index].currentIterSpec + 1) & loopNumIterMask; 32011784Sarthur.perais@inria.fr } 32111784Sarthur.perais@inria.fr } 32211784Sarthur.perais@inria.fr} 32311784Sarthur.perais@inria.fr 32411784Sarthur.perais@inria.frvoid 32511784Sarthur.perais@inria.frLTAGE::loopUpdate(Addr pc, bool taken, BranchInfo* bi) 32611784Sarthur.perais@inria.fr{ 32711784Sarthur.perais@inria.fr int idx = bi->loopIndex + bi->loopHit; 32811784Sarthur.perais@inria.fr if (bi->loopHit >= 0) { 32911784Sarthur.perais@inria.fr //already a hit 33011784Sarthur.perais@inria.fr if (bi->loopPredValid) { 33111784Sarthur.perais@inria.fr if (taken != bi->loopPred) { 33211784Sarthur.perais@inria.fr // free the entry 33311784Sarthur.perais@inria.fr ltable[idx].numIter = 0; 33411784Sarthur.perais@inria.fr ltable[idx].age = 0; 33511784Sarthur.perais@inria.fr ltable[idx].confidence = 0; 33611784Sarthur.perais@inria.fr ltable[idx].currentIter = 0; 33711784Sarthur.perais@inria.fr return; 33811784Sarthur.perais@inria.fr } else if (bi->loopPred != bi->tagePred) { 33911784Sarthur.perais@inria.fr DPRINTF(LTage, "Loop Prediction success:%lx\n",pc); 34013442Spau.cabre@metempsy.com unsignedCtrUpdate(ltable[idx].age, true, loopTableAgeBits); 34111784Sarthur.perais@inria.fr } 34211784Sarthur.perais@inria.fr } 34311784Sarthur.perais@inria.fr 34413442Spau.cabre@metempsy.com ltable[idx].currentIter = 34513442Spau.cabre@metempsy.com (ltable[idx].currentIter + 1) & loopNumIterMask; 34611784Sarthur.perais@inria.fr if (ltable[idx].currentIter > ltable[idx].numIter) { 34711784Sarthur.perais@inria.fr ltable[idx].confidence = 0; 34811784Sarthur.perais@inria.fr if (ltable[idx].numIter != 0) { 34911784Sarthur.perais@inria.fr // free the entry 35011784Sarthur.perais@inria.fr ltable[idx].numIter = 0; 35111784Sarthur.perais@inria.fr ltable[idx].age = 0; 35211784Sarthur.perais@inria.fr ltable[idx].confidence = 0; 35311784Sarthur.perais@inria.fr } 35411784Sarthur.perais@inria.fr } 35511784Sarthur.perais@inria.fr 35611784Sarthur.perais@inria.fr if (taken != ltable[idx].dir) { 35711784Sarthur.perais@inria.fr if (ltable[idx].currentIter == ltable[idx].numIter) { 35811784Sarthur.perais@inria.fr DPRINTF(LTage, "Loop End predicted successfully:%lx\n", pc); 35911784Sarthur.perais@inria.fr 36013442Spau.cabre@metempsy.com unsignedCtrUpdate(ltable[idx].confidence, true, 36113442Spau.cabre@metempsy.com loopTableConfidenceBits); 36211784Sarthur.perais@inria.fr //just do not predict when the loop count is 1 or 2 36311784Sarthur.perais@inria.fr if (ltable[idx].numIter < 3) { 36411784Sarthur.perais@inria.fr // free the entry 36511784Sarthur.perais@inria.fr ltable[idx].dir = taken; 36611784Sarthur.perais@inria.fr ltable[idx].numIter = 0; 36711784Sarthur.perais@inria.fr ltable[idx].age = 0; 36811784Sarthur.perais@inria.fr ltable[idx].confidence = 0; 36911784Sarthur.perais@inria.fr } 37011784Sarthur.perais@inria.fr } else { 37111784Sarthur.perais@inria.fr DPRINTF(LTage, "Loop End predicted incorrectly:%lx\n", pc); 37211784Sarthur.perais@inria.fr if (ltable[idx].numIter == 0) { 37311784Sarthur.perais@inria.fr // first complete nest; 37411784Sarthur.perais@inria.fr ltable[idx].confidence = 0; 37511784Sarthur.perais@inria.fr ltable[idx].numIter = ltable[idx].currentIter; 37611784Sarthur.perais@inria.fr } else { 37711784Sarthur.perais@inria.fr //not the same number of iterations as last time: free the 37811784Sarthur.perais@inria.fr //entry 37911784Sarthur.perais@inria.fr ltable[idx].numIter = 0; 38011784Sarthur.perais@inria.fr ltable[idx].age = 0; 38111784Sarthur.perais@inria.fr ltable[idx].confidence = 0; 38211784Sarthur.perais@inria.fr } 38311784Sarthur.perais@inria.fr } 38411784Sarthur.perais@inria.fr ltable[idx].currentIter = 0; 38511784Sarthur.perais@inria.fr } 38611784Sarthur.perais@inria.fr 38711784Sarthur.perais@inria.fr } else if (taken) { 38811784Sarthur.perais@inria.fr //try to allocate an entry on taken branch 38911784Sarthur.perais@inria.fr int nrand = random_mt.random<int>(); 39013444Spau.cabre@metempsy.com for (int i = 0; i < (1 << logLoopTableAssoc); i++) { 39113444Spau.cabre@metempsy.com int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) - 1); 39211784Sarthur.perais@inria.fr idx = bi->loopIndex + loop_hit; 39311784Sarthur.perais@inria.fr if (ltable[idx].age == 0) { 39411784Sarthur.perais@inria.fr DPRINTF(LTage, "Allocating loop pred entry for branch %lx\n", 39511784Sarthur.perais@inria.fr pc); 39611784Sarthur.perais@inria.fr ltable[idx].dir = !taken; 39711784Sarthur.perais@inria.fr ltable[idx].tag = bi->loopTag; 39811784Sarthur.perais@inria.fr ltable[idx].numIter = 0; 39913442Spau.cabre@metempsy.com ltable[idx].age = (1 << loopTableAgeBits) - 1; 40011784Sarthur.perais@inria.fr ltable[idx].confidence = 0; 40111784Sarthur.perais@inria.fr ltable[idx].currentIter = 1; 40211784Sarthur.perais@inria.fr break; 40311784Sarthur.perais@inria.fr 40411784Sarthur.perais@inria.fr } 40511784Sarthur.perais@inria.fr else 40611784Sarthur.perais@inria.fr ltable[idx].age--; 40711784Sarthur.perais@inria.fr } 40811784Sarthur.perais@inria.fr } 40911784Sarthur.perais@inria.fr 41011784Sarthur.perais@inria.fr} 41111784Sarthur.perais@inria.fr 41211784Sarthur.perais@inria.fr// shifting the global history: we manage the history in a big table in order 41311784Sarthur.perais@inria.fr// to reduce simulation time 41411784Sarthur.perais@inria.frvoid 41511784Sarthur.perais@inria.frLTAGE::updateGHist(uint8_t * &h, bool dir, uint8_t * tab, int &pt) 41611784Sarthur.perais@inria.fr{ 41711784Sarthur.perais@inria.fr if (pt == 0) { 41811784Sarthur.perais@inria.fr DPRINTF(LTage, "Rolling over the histories\n"); 41911784Sarthur.perais@inria.fr // Copy beginning of globalHistoryBuffer to end, such that 42011784Sarthur.perais@inria.fr // the last maxHist outcomes are still reachable 42111784Sarthur.perais@inria.fr // through pt[0 .. maxHist - 1]. 42211784Sarthur.perais@inria.fr for (int i = 0; i < maxHist; i++) 42311784Sarthur.perais@inria.fr tab[histBufferSize - maxHist + i] = tab[i]; 42411784Sarthur.perais@inria.fr pt = histBufferSize - maxHist; 42511784Sarthur.perais@inria.fr h = &tab[pt]; 42611784Sarthur.perais@inria.fr } 42711784Sarthur.perais@inria.fr pt--; 42811784Sarthur.perais@inria.fr h--; 42911784Sarthur.perais@inria.fr h[0] = (dir) ? 1 : 0; 43011784Sarthur.perais@inria.fr} 43111784Sarthur.perais@inria.fr 43211784Sarthur.perais@inria.fr// Get GHR for hashing indirect predictor 43311784Sarthur.perais@inria.fr// Build history backwards from pointer in 43411784Sarthur.perais@inria.fr// bp_history. 43511784Sarthur.perais@inria.frunsigned 43611784Sarthur.perais@inria.frLTAGE::getGHR(ThreadID tid, void *bp_history) const 43711784Sarthur.perais@inria.fr{ 43811784Sarthur.perais@inria.fr BranchInfo* bi = static_cast<BranchInfo*>(bp_history); 43911784Sarthur.perais@inria.fr unsigned val = 0; 44011784Sarthur.perais@inria.fr for (unsigned i = 0; i < 32; i++) { 44111784Sarthur.perais@inria.fr // Make sure we don't go out of bounds 44211784Sarthur.perais@inria.fr int gh_offset = bi->ptGhist + i; 44311784Sarthur.perais@inria.fr assert(&(threadHistory[tid].globalHistory[gh_offset]) < 44411784Sarthur.perais@inria.fr threadHistory[tid].globalHistory + histBufferSize); 44511784Sarthur.perais@inria.fr val |= ((threadHistory[tid].globalHistory[gh_offset] & 0x1) << i); 44611784Sarthur.perais@inria.fr } 44711784Sarthur.perais@inria.fr 44811784Sarthur.perais@inria.fr return val; 44911784Sarthur.perais@inria.fr} 45011784Sarthur.perais@inria.fr 45111784Sarthur.perais@inria.fr//prediction 45211784Sarthur.perais@inria.frbool 45311784Sarthur.perais@inria.frLTAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) 45411784Sarthur.perais@inria.fr{ 45511784Sarthur.perais@inria.fr BranchInfo *bi = new BranchInfo(nHistoryTables+1); 45611784Sarthur.perais@inria.fr b = (void*)(bi); 45711784Sarthur.perais@inria.fr Addr pc = branch_pc; 45811784Sarthur.perais@inria.fr bool pred_taken = true; 45911784Sarthur.perais@inria.fr bi->loopHit = -1; 46011784Sarthur.perais@inria.fr 46111784Sarthur.perais@inria.fr if (cond_branch) { 46211784Sarthur.perais@inria.fr // TAGE prediction 46311784Sarthur.perais@inria.fr 46411784Sarthur.perais@inria.fr // computes the table addresses and the partial tags 46511784Sarthur.perais@inria.fr for (int i = 1; i <= nHistoryTables; i++) { 46611784Sarthur.perais@inria.fr tableIndices[i] = gindex(tid, pc, i); 46711784Sarthur.perais@inria.fr bi->tableIndices[i] = tableIndices[i]; 46811784Sarthur.perais@inria.fr tableTags[i] = gtag(tid, pc, i); 46911784Sarthur.perais@inria.fr bi->tableTags[i] = tableTags[i]; 47011784Sarthur.perais@inria.fr } 47111784Sarthur.perais@inria.fr 47211784Sarthur.perais@inria.fr bi->bimodalIndex = bindex(pc); 47311784Sarthur.perais@inria.fr 47411784Sarthur.perais@inria.fr bi->hitBank = 0; 47511784Sarthur.perais@inria.fr bi->altBank = 0; 47611784Sarthur.perais@inria.fr //Look for the bank with longest matching history 47711784Sarthur.perais@inria.fr for (int i = nHistoryTables; i > 0; i--) { 47811784Sarthur.perais@inria.fr if (gtable[i][tableIndices[i]].tag == tableTags[i]) { 47911784Sarthur.perais@inria.fr bi->hitBank = i; 48011784Sarthur.perais@inria.fr bi->hitBankIndex = tableIndices[bi->hitBank]; 48111784Sarthur.perais@inria.fr break; 48211784Sarthur.perais@inria.fr } 48311784Sarthur.perais@inria.fr } 48411784Sarthur.perais@inria.fr //Look for the alternate bank 48511784Sarthur.perais@inria.fr for (int i = bi->hitBank - 1; i > 0; i--) { 48611784Sarthur.perais@inria.fr if (gtable[i][tableIndices[i]].tag == tableTags[i]) { 48711784Sarthur.perais@inria.fr bi->altBank = i; 48811784Sarthur.perais@inria.fr bi->altBankIndex = tableIndices[bi->altBank]; 48911784Sarthur.perais@inria.fr break; 49011784Sarthur.perais@inria.fr } 49111784Sarthur.perais@inria.fr } 49211784Sarthur.perais@inria.fr //computes the prediction and the alternate prediction 49311784Sarthur.perais@inria.fr if (bi->hitBank > 0) { 49411784Sarthur.perais@inria.fr if (bi->altBank > 0) { 49511784Sarthur.perais@inria.fr bi->altTaken = 49611784Sarthur.perais@inria.fr gtable[bi->altBank][tableIndices[bi->altBank]].ctr >= 0; 49711784Sarthur.perais@inria.fr }else { 49811784Sarthur.perais@inria.fr bi->altTaken = getBimodePred(pc, bi); 49911784Sarthur.perais@inria.fr } 50011784Sarthur.perais@inria.fr 50111784Sarthur.perais@inria.fr bi->longestMatchPred = 50211784Sarthur.perais@inria.fr gtable[bi->hitBank][tableIndices[bi->hitBank]].ctr >= 0; 50311784Sarthur.perais@inria.fr bi->pseudoNewAlloc = 50411784Sarthur.perais@inria.fr abs(2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) <= 1; 50511784Sarthur.perais@inria.fr 50611784Sarthur.perais@inria.fr //if the entry is recognized as a newly allocated entry and 50711784Sarthur.perais@inria.fr //useAltPredForNewlyAllocated is positive use the alternate 50811784Sarthur.perais@inria.fr //prediction 50911784Sarthur.perais@inria.fr if ((useAltPredForNewlyAllocated < 0) 51011784Sarthur.perais@inria.fr || abs(2 * 51111784Sarthur.perais@inria.fr gtable[bi->hitBank][tableIndices[bi->hitBank]].ctr + 1) > 1) 51211784Sarthur.perais@inria.fr bi->tagePred = bi->longestMatchPred; 51311784Sarthur.perais@inria.fr else 51411784Sarthur.perais@inria.fr bi->tagePred = bi->altTaken; 51511784Sarthur.perais@inria.fr } else { 51611784Sarthur.perais@inria.fr bi->altTaken = getBimodePred(pc, bi); 51711784Sarthur.perais@inria.fr bi->tagePred = bi->altTaken; 51811784Sarthur.perais@inria.fr bi->longestMatchPred = bi->altTaken; 51911784Sarthur.perais@inria.fr } 52011784Sarthur.perais@inria.fr //end TAGE prediction 52111784Sarthur.perais@inria.fr 52211784Sarthur.perais@inria.fr bi->loopPred = getLoop(pc, bi); // loop prediction 52311784Sarthur.perais@inria.fr 52411784Sarthur.perais@inria.fr pred_taken = (((loopUseCounter >= 0) && bi->loopPredValid)) ? 52511784Sarthur.perais@inria.fr (bi->loopPred): (bi->tagePred); 52611784Sarthur.perais@inria.fr DPRINTF(LTage, "Predict for %lx: taken?:%d, loopTaken?:%d, " 52711784Sarthur.perais@inria.fr "loopValid?:%d, loopUseCounter:%d, tagePred:%d, altPred:%d\n", 52811784Sarthur.perais@inria.fr branch_pc, pred_taken, bi->loopPred, bi->loopPredValid, 52911784Sarthur.perais@inria.fr loopUseCounter, bi->tagePred, bi->altTaken); 53011784Sarthur.perais@inria.fr } 53111784Sarthur.perais@inria.fr bi->branchPC = branch_pc; 53211784Sarthur.perais@inria.fr bi->condBranch = cond_branch; 53311784Sarthur.perais@inria.fr specLoopUpdate(branch_pc, pred_taken, bi); 53411784Sarthur.perais@inria.fr return pred_taken; 53511784Sarthur.perais@inria.fr} 53611784Sarthur.perais@inria.fr 53711784Sarthur.perais@inria.fr// PREDICTOR UPDATE 53811784Sarthur.perais@inria.frvoid 53911784Sarthur.perais@inria.frLTAGE::update(ThreadID tid, Addr branch_pc, bool taken, void* bp_history, 54011784Sarthur.perais@inria.fr bool squashed) 54111784Sarthur.perais@inria.fr{ 54211784Sarthur.perais@inria.fr assert(bp_history); 54311784Sarthur.perais@inria.fr 54411784Sarthur.perais@inria.fr BranchInfo *bi = static_cast<BranchInfo*>(bp_history); 54511784Sarthur.perais@inria.fr 54611784Sarthur.perais@inria.fr if (squashed) { 54711784Sarthur.perais@inria.fr // This restores the global history, then update it 54811784Sarthur.perais@inria.fr // and recomputes the folded histories. 54911784Sarthur.perais@inria.fr squash(tid, taken, bp_history); 55011784Sarthur.perais@inria.fr return; 55111784Sarthur.perais@inria.fr } 55211784Sarthur.perais@inria.fr 55311784Sarthur.perais@inria.fr int nrand = random_mt.random<int>(0,3); 55411784Sarthur.perais@inria.fr Addr pc = branch_pc; 55511784Sarthur.perais@inria.fr if (bi->condBranch) { 55611784Sarthur.perais@inria.fr DPRINTF(LTage, "Updating tables for branch:%lx; taken?:%d\n", 55711784Sarthur.perais@inria.fr branch_pc, taken); 55811784Sarthur.perais@inria.fr // first update the loop predictor 55911784Sarthur.perais@inria.fr loopUpdate(pc, taken, bi); 56011784Sarthur.perais@inria.fr 56111784Sarthur.perais@inria.fr if (bi->loopPredValid) { 56211784Sarthur.perais@inria.fr if (bi->tagePred != bi->loopPred) { 56313444Spau.cabre@metempsy.com ctrUpdate(loopUseCounter, 56413444Spau.cabre@metempsy.com (bi->loopPred == taken), 56513444Spau.cabre@metempsy.com withLoopBits); 56611784Sarthur.perais@inria.fr } 56711784Sarthur.perais@inria.fr } 56811784Sarthur.perais@inria.fr 56911784Sarthur.perais@inria.fr // TAGE UPDATE 57011784Sarthur.perais@inria.fr // try to allocate a new entries only if prediction was wrong 57111784Sarthur.perais@inria.fr bool longest_match_pred = false; 57211784Sarthur.perais@inria.fr bool alloc = (bi->tagePred != taken) && (bi->hitBank < nHistoryTables); 57311784Sarthur.perais@inria.fr if (bi->hitBank > 0) { 57411784Sarthur.perais@inria.fr // Manage the selection between longest matching and alternate 57511784Sarthur.perais@inria.fr // matching for "pseudo"-newly allocated longest matching entry 57611784Sarthur.perais@inria.fr longest_match_pred = bi->longestMatchPred; 57711784Sarthur.perais@inria.fr bool PseudoNewAlloc = bi->pseudoNewAlloc; 57811784Sarthur.perais@inria.fr // an entry is considered as newly allocated if its prediction 57911784Sarthur.perais@inria.fr // counter is weak 58011784Sarthur.perais@inria.fr if (PseudoNewAlloc) { 58111784Sarthur.perais@inria.fr if (longest_match_pred == taken) { 58211784Sarthur.perais@inria.fr alloc = false; 58311784Sarthur.perais@inria.fr } 58411784Sarthur.perais@inria.fr // if it was delivering the correct prediction, no need to 58511784Sarthur.perais@inria.fr // allocate new entry even if the overall prediction was false 58611784Sarthur.perais@inria.fr if (longest_match_pred != bi->altTaken) { 58711784Sarthur.perais@inria.fr ctrUpdate(useAltPredForNewlyAllocated, 58813444Spau.cabre@metempsy.com bi->altTaken == taken, useAltOnNaBits); 58911784Sarthur.perais@inria.fr } 59011784Sarthur.perais@inria.fr } 59111784Sarthur.perais@inria.fr } 59211784Sarthur.perais@inria.fr 59311784Sarthur.perais@inria.fr if (alloc) { 59411784Sarthur.perais@inria.fr // is there some "unuseful" entry to allocate 59513443Spau.cabre@metempsy.com uint8_t min = 1; 59611784Sarthur.perais@inria.fr for (int i = nHistoryTables; i > bi->hitBank; i--) { 59711784Sarthur.perais@inria.fr if (gtable[i][bi->tableIndices[i]].u < min) { 59811784Sarthur.perais@inria.fr min = gtable[i][bi->tableIndices[i]].u; 59911784Sarthur.perais@inria.fr } 60011784Sarthur.perais@inria.fr } 60111784Sarthur.perais@inria.fr 60211784Sarthur.perais@inria.fr // we allocate an entry with a longer history 60311784Sarthur.perais@inria.fr // to avoid ping-pong, we do not choose systematically the next 60411784Sarthur.perais@inria.fr // entry, but among the 3 next entries 60511784Sarthur.perais@inria.fr int Y = nrand & 60611784Sarthur.perais@inria.fr ((ULL(1) << (nHistoryTables - bi->hitBank - 1)) - 1); 60711784Sarthur.perais@inria.fr int X = bi->hitBank + 1; 60811784Sarthur.perais@inria.fr if (Y & 1) { 60911784Sarthur.perais@inria.fr X++; 61011784Sarthur.perais@inria.fr if (Y & 2) 61111784Sarthur.perais@inria.fr X++; 61211784Sarthur.perais@inria.fr } 61311784Sarthur.perais@inria.fr // No entry available, forces one to be available 61411784Sarthur.perais@inria.fr if (min > 0) { 61511784Sarthur.perais@inria.fr gtable[X][bi->tableIndices[X]].u = 0; 61611784Sarthur.perais@inria.fr } 61711784Sarthur.perais@inria.fr 61811784Sarthur.perais@inria.fr 61911784Sarthur.perais@inria.fr //Allocate only one entry 62011784Sarthur.perais@inria.fr for (int i = X; i <= nHistoryTables; i++) { 62111784Sarthur.perais@inria.fr if ((gtable[i][bi->tableIndices[i]].u == 0)) { 62211784Sarthur.perais@inria.fr gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i]; 62311784Sarthur.perais@inria.fr gtable[i][bi->tableIndices[i]].ctr = (taken) ? 0 : -1; 62413433Spau.cabre@metempsy.com break; 62511784Sarthur.perais@inria.fr } 62611784Sarthur.perais@inria.fr } 62711784Sarthur.perais@inria.fr } 62811784Sarthur.perais@inria.fr //periodic reset of u: reset is not complete but bit by bit 62911784Sarthur.perais@inria.fr tCounter++; 63013444Spau.cabre@metempsy.com if ((tCounter & ((ULL(1) << logUResetPeriod) - 1)) == 0) { 63111784Sarthur.perais@inria.fr // reset least significant bit 63211784Sarthur.perais@inria.fr // most significant bit becomes least significant bit 63311784Sarthur.perais@inria.fr for (int i = 1; i <= nHistoryTables; i++) { 63413444Spau.cabre@metempsy.com for (int j = 0; j < (ULL(1) << logTagTableSizes[i]); j++) { 63511784Sarthur.perais@inria.fr gtable[i][j].u = gtable[i][j].u >> 1; 63611784Sarthur.perais@inria.fr } 63711784Sarthur.perais@inria.fr } 63811784Sarthur.perais@inria.fr } 63911784Sarthur.perais@inria.fr 64011784Sarthur.perais@inria.fr if (bi->hitBank > 0) { 64111784Sarthur.perais@inria.fr DPRINTF(LTage, "Updating tag table entry (%d,%d) for branch %lx\n", 64211784Sarthur.perais@inria.fr bi->hitBank, bi->hitBankIndex, branch_pc); 64311784Sarthur.perais@inria.fr ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken, 64411784Sarthur.perais@inria.fr tagTableCounterBits); 64511784Sarthur.perais@inria.fr // if the provider entry is not certified to be useful also update 64611784Sarthur.perais@inria.fr // the alternate prediction 64711784Sarthur.perais@inria.fr if (gtable[bi->hitBank][bi->hitBankIndex].u == 0) { 64811784Sarthur.perais@inria.fr if (bi->altBank > 0) { 64911784Sarthur.perais@inria.fr ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken, 65011784Sarthur.perais@inria.fr tagTableCounterBits); 65111784Sarthur.perais@inria.fr DPRINTF(LTage, "Updating tag table entry (%d,%d) for" 65211784Sarthur.perais@inria.fr " branch %lx\n", bi->hitBank, bi->hitBankIndex, 65311784Sarthur.perais@inria.fr branch_pc); 65411784Sarthur.perais@inria.fr } 65511784Sarthur.perais@inria.fr if (bi->altBank == 0) { 65611784Sarthur.perais@inria.fr baseUpdate(pc, taken, bi); 65711784Sarthur.perais@inria.fr } 65811784Sarthur.perais@inria.fr } 65911784Sarthur.perais@inria.fr 66011784Sarthur.perais@inria.fr // update the u counter 66113443Spau.cabre@metempsy.com if (bi->tagePred != bi->altTaken) { 66213443Spau.cabre@metempsy.com unsignedCtrUpdate(gtable[bi->hitBank][bi->hitBankIndex].u, 66313443Spau.cabre@metempsy.com bi->tagePred == taken, tagTableUBits); 66411784Sarthur.perais@inria.fr } 66511784Sarthur.perais@inria.fr } else { 66611784Sarthur.perais@inria.fr baseUpdate(pc, taken, bi); 66711784Sarthur.perais@inria.fr } 66811784Sarthur.perais@inria.fr 66911784Sarthur.perais@inria.fr //END PREDICTOR UPDATE 67011784Sarthur.perais@inria.fr } 67111784Sarthur.perais@inria.fr if (!squashed) { 67211784Sarthur.perais@inria.fr delete bi; 67311784Sarthur.perais@inria.fr } 67411784Sarthur.perais@inria.fr} 67511784Sarthur.perais@inria.fr 67611784Sarthur.perais@inria.frvoid 67711784Sarthur.perais@inria.frLTAGE::updateHistories(ThreadID tid, Addr branch_pc, bool taken, void* b) 67811784Sarthur.perais@inria.fr{ 67911784Sarthur.perais@inria.fr BranchInfo* bi = (BranchInfo*)(b); 68011784Sarthur.perais@inria.fr ThreadHistory& tHist = threadHistory[tid]; 68111784Sarthur.perais@inria.fr // UPDATE HISTORIES 68213413Spau.cabre@metempsy.com bool pathbit = ((branch_pc >> instShiftAmt) & 1); 68311784Sarthur.perais@inria.fr //on a squash, return pointers to this and recompute indices. 68411784Sarthur.perais@inria.fr //update user history 68511784Sarthur.perais@inria.fr updateGHist(tHist.gHist, taken, tHist.globalHistory, tHist.ptGhist); 68611784Sarthur.perais@inria.fr tHist.pathHist = (tHist.pathHist << 1) + pathbit; 68713444Spau.cabre@metempsy.com tHist.pathHist = (tHist.pathHist & ((ULL(1) << pathHistBits) - 1)); 68811784Sarthur.perais@inria.fr 68911784Sarthur.perais@inria.fr bi->ptGhist = tHist.ptGhist; 69011784Sarthur.perais@inria.fr bi->pathHist = tHist.pathHist; 69111784Sarthur.perais@inria.fr //prepare next index and tag computations for user branchs 69211784Sarthur.perais@inria.fr for (int i = 1; i <= nHistoryTables; i++) 69311784Sarthur.perais@inria.fr { 69411784Sarthur.perais@inria.fr bi->ci[i] = tHist.computeIndices[i].comp; 69511784Sarthur.perais@inria.fr bi->ct0[i] = tHist.computeTags[0][i].comp; 69611784Sarthur.perais@inria.fr bi->ct1[i] = tHist.computeTags[1][i].comp; 69711784Sarthur.perais@inria.fr tHist.computeIndices[i].update(tHist.gHist); 69811784Sarthur.perais@inria.fr tHist.computeTags[0][i].update(tHist.gHist); 69911784Sarthur.perais@inria.fr tHist.computeTags[1][i].update(tHist.gHist); 70011784Sarthur.perais@inria.fr } 70111784Sarthur.perais@inria.fr DPRINTF(LTage, "Updating global histories with branch:%lx; taken?:%d, " 70211784Sarthur.perais@inria.fr "path Hist: %x; pointer:%d\n", branch_pc, taken, tHist.pathHist, 70311784Sarthur.perais@inria.fr tHist.ptGhist); 70411784Sarthur.perais@inria.fr} 70511784Sarthur.perais@inria.fr 70611784Sarthur.perais@inria.frvoid 70711784Sarthur.perais@inria.frLTAGE::squash(ThreadID tid, bool taken, void *bp_history) 70811784Sarthur.perais@inria.fr{ 70911784Sarthur.perais@inria.fr BranchInfo* bi = (BranchInfo*)(bp_history); 71011784Sarthur.perais@inria.fr ThreadHistory& tHist = threadHistory[tid]; 71111784Sarthur.perais@inria.fr DPRINTF(LTage, "Restoring branch info: %lx; taken? %d; PathHistory:%x, " 71211784Sarthur.perais@inria.fr "pointer:%d\n", bi->branchPC,taken, bi->pathHist, bi->ptGhist); 71311784Sarthur.perais@inria.fr tHist.pathHist = bi->pathHist; 71411784Sarthur.perais@inria.fr tHist.ptGhist = bi->ptGhist; 71511784Sarthur.perais@inria.fr tHist.gHist = &(tHist.globalHistory[tHist.ptGhist]); 71611784Sarthur.perais@inria.fr tHist.gHist[0] = (taken ? 1 : 0); 71711784Sarthur.perais@inria.fr for (int i = 1; i <= nHistoryTables; i++) { 71811784Sarthur.perais@inria.fr tHist.computeIndices[i].comp = bi->ci[i]; 71911784Sarthur.perais@inria.fr tHist.computeTags[0][i].comp = bi->ct0[i]; 72011784Sarthur.perais@inria.fr tHist.computeTags[1][i].comp = bi->ct1[i]; 72111784Sarthur.perais@inria.fr tHist.computeIndices[i].update(tHist.gHist); 72211784Sarthur.perais@inria.fr tHist.computeTags[0][i].update(tHist.gHist); 72311784Sarthur.perais@inria.fr tHist.computeTags[1][i].update(tHist.gHist); 72411784Sarthur.perais@inria.fr } 72511784Sarthur.perais@inria.fr 72611784Sarthur.perais@inria.fr if (bi->condBranch) { 72711784Sarthur.perais@inria.fr if (bi->loopHit >= 0) { 72811784Sarthur.perais@inria.fr int idx = bi->loopIndex + bi->loopHit; 72911784Sarthur.perais@inria.fr ltable[idx].currentIterSpec = bi->currentIter; 73011784Sarthur.perais@inria.fr } 73111784Sarthur.perais@inria.fr } 73211784Sarthur.perais@inria.fr 73311784Sarthur.perais@inria.fr} 73411784Sarthur.perais@inria.fr 73511784Sarthur.perais@inria.frvoid 73611784Sarthur.perais@inria.frLTAGE::squash(ThreadID tid, void *bp_history) 73711784Sarthur.perais@inria.fr{ 73811784Sarthur.perais@inria.fr BranchInfo* bi = (BranchInfo*)(bp_history); 73911784Sarthur.perais@inria.fr DPRINTF(LTage, "Deleting branch info: %lx\n", bi->branchPC); 74011784Sarthur.perais@inria.fr if (bi->condBranch) { 74111784Sarthur.perais@inria.fr if (bi->loopHit >= 0) { 74211784Sarthur.perais@inria.fr int idx = bi->loopIndex + bi->loopHit; 74311784Sarthur.perais@inria.fr ltable[idx].currentIterSpec = bi->currentIter; 74411784Sarthur.perais@inria.fr } 74511784Sarthur.perais@inria.fr } 74611784Sarthur.perais@inria.fr 74711784Sarthur.perais@inria.fr delete bi; 74811784Sarthur.perais@inria.fr} 74911784Sarthur.perais@inria.fr 75011784Sarthur.perais@inria.frbool 75111784Sarthur.perais@inria.frLTAGE::lookup(ThreadID tid, Addr branch_pc, void* &bp_history) 75211784Sarthur.perais@inria.fr{ 75311784Sarthur.perais@inria.fr bool retval = predict(tid, branch_pc, true, bp_history); 75411784Sarthur.perais@inria.fr 75511784Sarthur.perais@inria.fr DPRINTF(LTage, "Lookup branch: %lx; predict:%d\n", branch_pc, retval); 75611784Sarthur.perais@inria.fr updateHistories(tid, branch_pc, retval, bp_history); 75711784Sarthur.perais@inria.fr assert(threadHistory[tid].gHist == 75811784Sarthur.perais@inria.fr &threadHistory[tid].globalHistory[threadHistory[tid].ptGhist]); 75911784Sarthur.perais@inria.fr 76011784Sarthur.perais@inria.fr return retval; 76111784Sarthur.perais@inria.fr} 76211784Sarthur.perais@inria.fr 76311784Sarthur.perais@inria.frvoid 76411784Sarthur.perais@inria.frLTAGE::btbUpdate(ThreadID tid, Addr branch_pc, void* &bp_history) 76511784Sarthur.perais@inria.fr{ 76611784Sarthur.perais@inria.fr BranchInfo* bi = (BranchInfo*) bp_history; 76711784Sarthur.perais@inria.fr ThreadHistory& tHist = threadHistory[tid]; 76811784Sarthur.perais@inria.fr DPRINTF(LTage, "BTB miss resets prediction: %lx\n", branch_pc); 76911784Sarthur.perais@inria.fr assert(tHist.gHist == &tHist.globalHistory[tHist.ptGhist]); 77011784Sarthur.perais@inria.fr tHist.gHist[0] = 0; 77111784Sarthur.perais@inria.fr for (int i = 1; i <= nHistoryTables; i++) { 77211784Sarthur.perais@inria.fr tHist.computeIndices[i].comp = bi->ci[i]; 77311784Sarthur.perais@inria.fr tHist.computeTags[0][i].comp = bi->ct0[i]; 77411784Sarthur.perais@inria.fr tHist.computeTags[1][i].comp = bi->ct1[i]; 77511784Sarthur.perais@inria.fr tHist.computeIndices[i].update(tHist.gHist); 77611784Sarthur.perais@inria.fr tHist.computeTags[0][i].update(tHist.gHist); 77711784Sarthur.perais@inria.fr tHist.computeTags[1][i].update(tHist.gHist); 77811784Sarthur.perais@inria.fr } 77911784Sarthur.perais@inria.fr} 78011784Sarthur.perais@inria.fr 78111784Sarthur.perais@inria.frvoid 78211784Sarthur.perais@inria.frLTAGE::uncondBranch(ThreadID tid, Addr br_pc, void* &bp_history) 78311784Sarthur.perais@inria.fr{ 78411784Sarthur.perais@inria.fr DPRINTF(LTage, "UnConditionalBranch: %lx\n", br_pc); 78511784Sarthur.perais@inria.fr predict(tid, br_pc, false, bp_history); 78611784Sarthur.perais@inria.fr updateHistories(tid, br_pc, true, bp_history); 78711784Sarthur.perais@inria.fr assert(threadHistory[tid].gHist == 78811784Sarthur.perais@inria.fr &threadHistory[tid].globalHistory[threadHistory[tid].ptGhist]); 78911784Sarthur.perais@inria.fr} 79011784Sarthur.perais@inria.fr 79111784Sarthur.perais@inria.frLTAGE* 79211784Sarthur.perais@inria.frLTAGEParams::create() 79311784Sarthur.perais@inria.fr{ 79411784Sarthur.perais@inria.fr return new LTAGE(this); 79511784Sarthur.perais@inria.fr} 796