ltage.cc revision 12334
113511Sgabeblack@google.com/* 213511Sgabeblack@google.com * Copyright (c) 2014 The University of Wisconsin 313511Sgabeblack@google.com * 413511Sgabeblack@google.com * Copyright (c) 2006 INRIA (Institut National de Recherche en 513511Sgabeblack@google.com * Informatique et en Automatique / French National Research Institute 613511Sgabeblack@google.com * for Computer Science and Applied Mathematics) 713511Sgabeblack@google.com * 813511Sgabeblack@google.com * All rights reserved. 913511Sgabeblack@google.com * 1013511Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 1113511Sgabeblack@google.com * modification, are permitted provided that the following conditions are 1213511Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 1313511Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 1413511Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 1513511Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 1613511Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 1713511Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 1813511Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 1913511Sgabeblack@google.com * this software without specific prior written permission. 2013511Sgabeblack@google.com * 2113511Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2213511Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2313511Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2413511Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2513511Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2613511Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2713511Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2813511Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2913511Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3013511Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3113511Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3213511Sgabeblack@google.com * 3313511Sgabeblack@google.com * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais, 3413511Sgabeblack@google.com * from André Seznec's code. 3513511Sgabeblack@google.com */ 3613511Sgabeblack@google.com 3713511Sgabeblack@google.com/* @file 3813511Sgabeblack@google.com * Implementation of a L-TAGE branch predictor 3913511Sgabeblack@google.com */ 4013511Sgabeblack@google.com 4113511Sgabeblack@google.com#include "cpu/pred/ltage.hh" 4213511Sgabeblack@google.com 4313511Sgabeblack@google.com#include "base/intmath.hh" 4413511Sgabeblack@google.com#include "base/logging.hh" 4513511Sgabeblack@google.com#include "base/random.hh" 4613511Sgabeblack@google.com#include "base/trace.hh" 4713511Sgabeblack@google.com#include "debug/Fetch.hh" 4813511Sgabeblack@google.com#include "debug/LTage.hh" 4913511Sgabeblack@google.com 5013511Sgabeblack@google.comLTAGE::LTAGE(const LTAGEParams *params) 5113511Sgabeblack@google.com : BPredUnit(params), 5213511Sgabeblack@google.com logSizeBiMP(params->logSizeBiMP), 5313511Sgabeblack@google.com logSizeTagTables(params->logSizeTagTables), 5413511Sgabeblack@google.com logSizeLoopPred(params->logSizeLoopPred), 5513511Sgabeblack@google.com nHistoryTables(params->nHistoryTables), 5613511Sgabeblack@google.com tagTableCounterBits(params->tagTableCounterBits), 5713511Sgabeblack@google.com histBufferSize(params->histBufferSize), 5813511Sgabeblack@google.com minHist(params->minHist), 5913511Sgabeblack@google.com maxHist(params->maxHist), 6013511Sgabeblack@google.com minTagWidth(params->minTagWidth), 6113511Sgabeblack@google.com threadHistory(params->numThreads) 6213511Sgabeblack@google.com{ 6313511Sgabeblack@google.com assert(params->histBufferSize > params->maxHist * 2); 6413511Sgabeblack@google.com useAltPredForNewlyAllocated = 0; 6513511Sgabeblack@google.com logTick = 19; 6613511Sgabeblack@google.com tCounter = ULL(1) << (logTick - 1); 6713511Sgabeblack@google.com 6813511Sgabeblack@google.com for (auto& history : threadHistory) { 6913511Sgabeblack@google.com history.pathHist = 0; 7013511Sgabeblack@google.com history.globalHistory = new uint8_t[histBufferSize]; 7113511Sgabeblack@google.com history.gHist = history.globalHistory; 7213511Sgabeblack@google.com memset(history.gHist, 0, histBufferSize); 7313511Sgabeblack@google.com history.ptGhist = 0; 7413511Sgabeblack@google.com } 7513511Sgabeblack@google.com 7613511Sgabeblack@google.com histLengths = new int [nHistoryTables+1]; 7713511Sgabeblack@google.com histLengths[1] = minHist; 7813511Sgabeblack@google.com histLengths[nHistoryTables] = maxHist; 7913511Sgabeblack@google.com 8013511Sgabeblack@google.com for (int i = 2; i <= nHistoryTables; i++) { 8113511Sgabeblack@google.com histLengths[i] = (int) (((double) minHist * 8213511Sgabeblack@google.com pow ((double) (maxHist) / (double) minHist, 8313511Sgabeblack@google.com (double) (i - 1) / (double) ((nHistoryTables- 1)))) 8413511Sgabeblack@google.com + 0.5); 8513511Sgabeblack@google.com } 8613511Sgabeblack@google.com 8713511Sgabeblack@google.com tagWidths[1] = minTagWidth; 8813511Sgabeblack@google.com tagWidths[2] = minTagWidth; 8913511Sgabeblack@google.com tagWidths[3] = minTagWidth + 1; 9013511Sgabeblack@google.com tagWidths[4] = minTagWidth + 1; 9113511Sgabeblack@google.com tagWidths[5] = minTagWidth + 2; 9213511Sgabeblack@google.com tagWidths[6] = minTagWidth + 3; 9313511Sgabeblack@google.com tagWidths[7] = minTagWidth + 4; 9413511Sgabeblack@google.com tagWidths[8] = minTagWidth + 5; 9513511Sgabeblack@google.com tagWidths[9] = minTagWidth + 5; 9613511Sgabeblack@google.com tagWidths[10] = minTagWidth + 6; 9713511Sgabeblack@google.com tagWidths[11] = minTagWidth + 7; 9813511Sgabeblack@google.com tagWidths[12] = minTagWidth + 8; 9913511Sgabeblack@google.com 10013511Sgabeblack@google.com for (int i = 1; i <= 2; i++) 10113511Sgabeblack@google.com tagTableSizes[i] = logSizeTagTables - 1; 10213511Sgabeblack@google.com for (int i = 3; i <= 6; i++) 10313511Sgabeblack@google.com tagTableSizes[i] = logSizeTagTables; 10413511Sgabeblack@google.com for (int i = 7; i <= 10; i++) 10513511Sgabeblack@google.com tagTableSizes[i] = logSizeTagTables - 1; 10613511Sgabeblack@google.com for (int i = 11; i <= 12; i++) 10713511Sgabeblack@google.com tagTableSizes[i] = logSizeTagTables - 2; 10813511Sgabeblack@google.com 10913511Sgabeblack@google.com for (auto& history : threadHistory) { 11013511Sgabeblack@google.com history.computeIndices = new FoldedHistory[nHistoryTables+1]; 11113511Sgabeblack@google.com history.computeTags[0] = new FoldedHistory[nHistoryTables+1]; 11213511Sgabeblack@google.com history.computeTags[1] = new FoldedHistory[nHistoryTables+1]; 11313511Sgabeblack@google.com 11413511Sgabeblack@google.com for (int i = 1; i <= nHistoryTables; i++) { 11513511Sgabeblack@google.com history.computeIndices[i].init(histLengths[i], (tagTableSizes[i])); 11613511Sgabeblack@google.com history.computeTags[0][i].init( 11713511Sgabeblack@google.com history.computeIndices[i].origLength, tagWidths[i]); 11813511Sgabeblack@google.com history.computeTags[1][i].init( 11913511Sgabeblack@google.com history.computeIndices[i].origLength, tagWidths[i] - 1); 12013511Sgabeblack@google.com DPRINTF(LTage, "HistLength:%d, TTSize:%d, TTTWidth:%d\n", 12113511Sgabeblack@google.com histLengths[i], tagTableSizes[i], tagWidths[i]); 12213511Sgabeblack@google.com } 12313511Sgabeblack@google.com } 12413511Sgabeblack@google.com 12513511Sgabeblack@google.com btable = new BimodalEntry[ULL(1) << logSizeBiMP]; 12613511Sgabeblack@google.com ltable = new LoopEntry[ULL(1) << logSizeLoopPred]; 12713511Sgabeblack@google.com gtable = new TageEntry*[nHistoryTables + 1]; 12813511Sgabeblack@google.com for (int i = 1; i <= nHistoryTables; i++) { 12913511Sgabeblack@google.com gtable[i] = new TageEntry[1<<(tagTableSizes[i])]; 13013511Sgabeblack@google.com } 13113511Sgabeblack@google.com 13213511Sgabeblack@google.com tableIndices = new int [nHistoryTables+1]; 13313511Sgabeblack@google.com tableTags = new int [nHistoryTables+1]; 13413511Sgabeblack@google.com 13513511Sgabeblack@google.com loopUseCounter = 0; 13613511Sgabeblack@google.com} 13713511Sgabeblack@google.com 13813511Sgabeblack@google.comint 13913511Sgabeblack@google.comLTAGE::bindex(Addr pc_in) const 14013511Sgabeblack@google.com{ 14113511Sgabeblack@google.com return ((pc_in) & ((ULL(1) << (logSizeBiMP)) - 1)); 14213511Sgabeblack@google.com} 14313511Sgabeblack@google.com 14413511Sgabeblack@google.comint 14513511Sgabeblack@google.comLTAGE::lindex(Addr pc_in) const 14613511Sgabeblack@google.com{ 14713511Sgabeblack@google.com return (((pc_in) & ((ULL(1) << (logSizeLoopPred - 2)) - 1)) << 2); 14813511Sgabeblack@google.com} 14913511Sgabeblack@google.com 15013511Sgabeblack@google.comint 15113511Sgabeblack@google.comLTAGE::F(int A, int size, int bank) const 15213511Sgabeblack@google.com{ 15313511Sgabeblack@google.com int A1, A2; 15413511Sgabeblack@google.com 15513511Sgabeblack@google.com A = A & ((ULL(1) << size) - 1); 15613511Sgabeblack@google.com A1 = (A & ((ULL(1) << tagTableSizes[bank]) - 1)); 15713511Sgabeblack@google.com A2 = (A >> tagTableSizes[bank]); 15813511Sgabeblack@google.com A2 = ((A2 << bank) & ((ULL(1) << tagTableSizes[bank]) - 1)) 15913511Sgabeblack@google.com + (A2 >> (tagTableSizes[bank] - bank)); 16013511Sgabeblack@google.com A = A1 ^ A2; 16113511Sgabeblack@google.com A = ((A << bank) & ((ULL(1) << tagTableSizes[bank]) - 1)) 16213511Sgabeblack@google.com + (A >> (tagTableSizes[bank] - bank)); 16313511Sgabeblack@google.com return (A); 16413511Sgabeblack@google.com} 16513511Sgabeblack@google.com 16613511Sgabeblack@google.com 16713511Sgabeblack@google.com// gindex computes a full hash of pc, ghist and pathHist 16813511Sgabeblack@google.comint 16913511Sgabeblack@google.comLTAGE::gindex(ThreadID tid, Addr pc, int bank) const 17013511Sgabeblack@google.com{ 17113511Sgabeblack@google.com int index; 17213511Sgabeblack@google.com int hlen = (histLengths[bank] > 16) ? 16 : histLengths[bank]; 17313511Sgabeblack@google.com index = 17413511Sgabeblack@google.com (pc) ^ ((pc) >> ((int) abs(tagTableSizes[bank] - bank) + 1)) ^ 17513511Sgabeblack@google.com threadHistory[tid].computeIndices[bank].comp ^ 17613511Sgabeblack@google.com F(threadHistory[tid].pathHist, hlen, bank); 17713511Sgabeblack@google.com 17813511Sgabeblack@google.com return (index & ((ULL(1) << (tagTableSizes[bank])) - 1)); 17913511Sgabeblack@google.com} 18013511Sgabeblack@google.com 18113511Sgabeblack@google.com 18213511Sgabeblack@google.com// Tag computation 18313511Sgabeblack@google.comuint16_t 18413511Sgabeblack@google.comLTAGE::gtag(ThreadID tid, Addr pc, int bank) const 18513511Sgabeblack@google.com{ 18613511Sgabeblack@google.com int tag = (pc) ^ threadHistory[tid].computeTags[0][bank].comp 18713511Sgabeblack@google.com ^ (threadHistory[tid].computeTags[1][bank].comp << 1); 18813511Sgabeblack@google.com 18913511Sgabeblack@google.com return (tag & ((ULL(1) << tagWidths[bank]) - 1)); 19013511Sgabeblack@google.com} 19113511Sgabeblack@google.com 19213511Sgabeblack@google.com 19313511Sgabeblack@google.com// Up-down saturating counter 19413511Sgabeblack@google.comvoid 19513511Sgabeblack@google.comLTAGE::ctrUpdate(int8_t & ctr, bool taken, int nbits) 19613511Sgabeblack@google.com{ 19713511Sgabeblack@google.com assert(nbits <= sizeof(int8_t) << 3); 19813511Sgabeblack@google.com if (taken) { 19913511Sgabeblack@google.com if (ctr < ((1 << (nbits - 1)) - 1)) 20013511Sgabeblack@google.com ctr++; 20113511Sgabeblack@google.com } else { 20213511Sgabeblack@google.com if (ctr > -(1 << (nbits - 1))) 20313511Sgabeblack@google.com ctr--; 20413511Sgabeblack@google.com } 20513511Sgabeblack@google.com} 20613511Sgabeblack@google.com 20713511Sgabeblack@google.com// Bimodal prediction 20813511Sgabeblack@google.combool 20913511Sgabeblack@google.comLTAGE::getBimodePred(Addr pc, BranchInfo* bi) const 21013511Sgabeblack@google.com{ 21113511Sgabeblack@google.com return (btable[bi->bimodalIndex].pred > 0); 21213511Sgabeblack@google.com} 21313511Sgabeblack@google.com 21413511Sgabeblack@google.com 21513511Sgabeblack@google.com// Update the bimodal predictor: a hysteresis bit is shared among 4 prediction 21613511Sgabeblack@google.com// bits 21713511Sgabeblack@google.comvoid 21813511Sgabeblack@google.comLTAGE::baseUpdate(Addr pc, bool taken, BranchInfo* bi) 21913511Sgabeblack@google.com{ 22013511Sgabeblack@google.com int inter = (btable[bi->bimodalIndex].pred << 1) 22113511Sgabeblack@google.com + btable[bi->bimodalIndex ].hyst; 22213511Sgabeblack@google.com if (taken) { 22313511Sgabeblack@google.com if (inter < 3) 22413511Sgabeblack@google.com inter++; 22513511Sgabeblack@google.com } else if (inter > 0) { 22613511Sgabeblack@google.com inter--; 22713511Sgabeblack@google.com } 22813511Sgabeblack@google.com btable[bi->bimodalIndex].pred = inter >> 1; 22913511Sgabeblack@google.com btable[bi->bimodalIndex].hyst = (inter & 1); 23013511Sgabeblack@google.com DPRINTF(LTage, "Updating branch %lx, pred:%d, hyst:%d\n", 23113511Sgabeblack@google.com pc, btable[bi->bimodalIndex].pred,btable[bi->bimodalIndex].hyst); 23213511Sgabeblack@google.com} 23313511Sgabeblack@google.com 23413511Sgabeblack@google.com 23513511Sgabeblack@google.com//loop prediction: only used if high confidence 23613511Sgabeblack@google.combool 23713511Sgabeblack@google.comLTAGE::getLoop(Addr pc, BranchInfo* bi) const 23813511Sgabeblack@google.com{ 23913511Sgabeblack@google.com bi->loopHit = -1; 24013511Sgabeblack@google.com bi->loopPredValid = false; 24113511Sgabeblack@google.com bi->loopIndex = lindex(pc); 24213511Sgabeblack@google.com bi->loopTag = ((pc) >> (logSizeLoopPred - 2)); 24313511Sgabeblack@google.com 24413511Sgabeblack@google.com for (int i = 0; i < 4; i++) { 24513511Sgabeblack@google.com if (ltable[bi->loopIndex + i].tag == bi->loopTag) { 24613511Sgabeblack@google.com bi->loopHit = i; 24713511Sgabeblack@google.com bi->loopPredValid = (ltable[bi->loopIndex + i].confidence >= 3); 24813511Sgabeblack@google.com bi->currentIter = ltable[bi->loopIndex + i].currentIterSpec; 24913511Sgabeblack@google.com if (ltable[bi->loopIndex + i].currentIterSpec + 1 == 25013511Sgabeblack@google.com ltable[bi->loopIndex + i].numIter) { 25113511Sgabeblack@google.com return !(ltable[bi->loopIndex + i].dir); 25213511Sgabeblack@google.com }else { 25313511Sgabeblack@google.com return (ltable[bi->loopIndex + i].dir); 25413511Sgabeblack@google.com } 25513511Sgabeblack@google.com } 25613511Sgabeblack@google.com } 25713511Sgabeblack@google.com return false; 25813511Sgabeblack@google.com} 25913511Sgabeblack@google.com 26013511Sgabeblack@google.comvoid 26113511Sgabeblack@google.comLTAGE::specLoopUpdate(Addr pc, bool taken, BranchInfo* bi) 26213511Sgabeblack@google.com{ 26313511Sgabeblack@google.com if (bi->loopHit>=0) { 26413511Sgabeblack@google.com int index = lindex(pc); 26513511Sgabeblack@google.com if (taken != ltable[index].dir) { 26613511Sgabeblack@google.com ltable[index].currentIterSpec = 0; 26713511Sgabeblack@google.com } else { 26813511Sgabeblack@google.com ltable[index].currentIterSpec++; 26913511Sgabeblack@google.com } 27013511Sgabeblack@google.com } 27113511Sgabeblack@google.com} 27213511Sgabeblack@google.com 27313511Sgabeblack@google.comvoid 27413511Sgabeblack@google.comLTAGE::loopUpdate(Addr pc, bool taken, BranchInfo* bi) 27513511Sgabeblack@google.com{ 27613511Sgabeblack@google.com int idx = bi->loopIndex + bi->loopHit; 27713511Sgabeblack@google.com if (bi->loopHit >= 0) { 27813511Sgabeblack@google.com //already a hit 27913511Sgabeblack@google.com if (bi->loopPredValid) { 28013511Sgabeblack@google.com if (taken != bi->loopPred) { 28113511Sgabeblack@google.com // free the entry 28213511Sgabeblack@google.com ltable[idx].numIter = 0; 28313511Sgabeblack@google.com ltable[idx].age = 0; 28413511Sgabeblack@google.com ltable[idx].confidence = 0; 28513511Sgabeblack@google.com ltable[idx].currentIter = 0; 28613511Sgabeblack@google.com return; 28713511Sgabeblack@google.com } else if (bi->loopPred != bi->tagePred) { 28813511Sgabeblack@google.com DPRINTF(LTage, "Loop Prediction success:%lx\n",pc); 28913511Sgabeblack@google.com if (ltable[idx].age < 7) 29013511Sgabeblack@google.com ltable[idx].age++; 29113511Sgabeblack@google.com } 29213511Sgabeblack@google.com } 29313511Sgabeblack@google.com 29413511Sgabeblack@google.com ltable[idx].currentIter++; 29513511Sgabeblack@google.com if (ltable[idx].currentIter > ltable[idx].numIter) { 29613511Sgabeblack@google.com ltable[idx].confidence = 0; 29713511Sgabeblack@google.com if (ltable[idx].numIter != 0) { 29813511Sgabeblack@google.com // free the entry 29913511Sgabeblack@google.com ltable[idx].numIter = 0; 30013511Sgabeblack@google.com ltable[idx].age = 0; 30113511Sgabeblack@google.com ltable[idx].confidence = 0; 30213511Sgabeblack@google.com } 30313511Sgabeblack@google.com } 30413511Sgabeblack@google.com 30513511Sgabeblack@google.com if (taken != ltable[idx].dir) { 30613511Sgabeblack@google.com if (ltable[idx].currentIter == ltable[idx].numIter) { 30713511Sgabeblack@google.com DPRINTF(LTage, "Loop End predicted successfully:%lx\n", pc); 30813511Sgabeblack@google.com 30913511Sgabeblack@google.com if (ltable[idx].confidence < 7) { 31013511Sgabeblack@google.com ltable[idx].confidence++; 31113511Sgabeblack@google.com } 31213511Sgabeblack@google.com //just do not predict when the loop count is 1 or 2 31313511Sgabeblack@google.com if (ltable[idx].numIter < 3) { 31413511Sgabeblack@google.com // free the entry 31513511Sgabeblack@google.com ltable[idx].dir = taken; 31613511Sgabeblack@google.com ltable[idx].numIter = 0; 31713511Sgabeblack@google.com ltable[idx].age = 0; 31813511Sgabeblack@google.com ltable[idx].confidence = 0; 31913511Sgabeblack@google.com } 32013511Sgabeblack@google.com } else { 32113511Sgabeblack@google.com DPRINTF(LTage, "Loop End predicted incorrectly:%lx\n", pc); 32213511Sgabeblack@google.com if (ltable[idx].numIter == 0) { 32313511Sgabeblack@google.com // first complete nest; 32413511Sgabeblack@google.com ltable[idx].confidence = 0; 32513511Sgabeblack@google.com ltable[idx].numIter = ltable[idx].currentIter; 32613511Sgabeblack@google.com } else { 32713511Sgabeblack@google.com //not the same number of iterations as last time: free the 32813511Sgabeblack@google.com //entry 329 ltable[idx].numIter = 0; 330 ltable[idx].age = 0; 331 ltable[idx].confidence = 0; 332 } 333 } 334 ltable[idx].currentIter = 0; 335 } 336 337 } else if (taken) { 338 //try to allocate an entry on taken branch 339 int nrand = random_mt.random<int>(); 340 for (int i = 0; i < 4; i++) { 341 int loop_hit = (nrand + i) & 3; 342 idx = bi->loopIndex + loop_hit; 343 if (ltable[idx].age == 0) { 344 DPRINTF(LTage, "Allocating loop pred entry for branch %lx\n", 345 pc); 346 ltable[idx].dir = !taken; 347 ltable[idx].tag = bi->loopTag; 348 ltable[idx].numIter = 0; 349 ltable[idx].age = 7; 350 ltable[idx].confidence = 0; 351 ltable[idx].currentIter = 1; 352 break; 353 354 } 355 else 356 ltable[idx].age--; 357 } 358 } 359 360} 361 362// shifting the global history: we manage the history in a big table in order 363// to reduce simulation time 364void 365LTAGE::updateGHist(uint8_t * &h, bool dir, uint8_t * tab, int &pt) 366{ 367 if (pt == 0) { 368 DPRINTF(LTage, "Rolling over the histories\n"); 369 // Copy beginning of globalHistoryBuffer to end, such that 370 // the last maxHist outcomes are still reachable 371 // through pt[0 .. maxHist - 1]. 372 for (int i = 0; i < maxHist; i++) 373 tab[histBufferSize - maxHist + i] = tab[i]; 374 pt = histBufferSize - maxHist; 375 h = &tab[pt]; 376 } 377 pt--; 378 h--; 379 h[0] = (dir) ? 1 : 0; 380} 381 382// Get GHR for hashing indirect predictor 383// Build history backwards from pointer in 384// bp_history. 385unsigned 386LTAGE::getGHR(ThreadID tid, void *bp_history) const 387{ 388 BranchInfo* bi = static_cast<BranchInfo*>(bp_history); 389 unsigned val = 0; 390 for (unsigned i = 0; i < 32; i++) { 391 // Make sure we don't go out of bounds 392 int gh_offset = bi->ptGhist + i; 393 assert(&(threadHistory[tid].globalHistory[gh_offset]) < 394 threadHistory[tid].globalHistory + histBufferSize); 395 val |= ((threadHistory[tid].globalHistory[gh_offset] & 0x1) << i); 396 } 397 398 return val; 399} 400 401//prediction 402bool 403LTAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) 404{ 405 BranchInfo *bi = new BranchInfo(nHistoryTables+1); 406 b = (void*)(bi); 407 Addr pc = branch_pc; 408 bool pred_taken = true; 409 bi->loopHit = -1; 410 411 if (cond_branch) { 412 // TAGE prediction 413 414 // computes the table addresses and the partial tags 415 for (int i = 1; i <= nHistoryTables; i++) { 416 tableIndices[i] = gindex(tid, pc, i); 417 bi->tableIndices[i] = tableIndices[i]; 418 tableTags[i] = gtag(tid, pc, i); 419 bi->tableTags[i] = tableTags[i]; 420 } 421 422 bi->bimodalIndex = bindex(pc); 423 424 bi->hitBank = 0; 425 bi->altBank = 0; 426 //Look for the bank with longest matching history 427 for (int i = nHistoryTables; i > 0; i--) { 428 if (gtable[i][tableIndices[i]].tag == tableTags[i]) { 429 bi->hitBank = i; 430 bi->hitBankIndex = tableIndices[bi->hitBank]; 431 break; 432 } 433 } 434 //Look for the alternate bank 435 for (int i = bi->hitBank - 1; i > 0; i--) { 436 if (gtable[i][tableIndices[i]].tag == tableTags[i]) { 437 bi->altBank = i; 438 bi->altBankIndex = tableIndices[bi->altBank]; 439 break; 440 } 441 } 442 //computes the prediction and the alternate prediction 443 if (bi->hitBank > 0) { 444 if (bi->altBank > 0) { 445 bi->altTaken = 446 gtable[bi->altBank][tableIndices[bi->altBank]].ctr >= 0; 447 }else { 448 bi->altTaken = getBimodePred(pc, bi); 449 } 450 451 bi->longestMatchPred = 452 gtable[bi->hitBank][tableIndices[bi->hitBank]].ctr >= 0; 453 bi->pseudoNewAlloc = 454 abs(2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) <= 1; 455 456 //if the entry is recognized as a newly allocated entry and 457 //useAltPredForNewlyAllocated is positive use the alternate 458 //prediction 459 if ((useAltPredForNewlyAllocated < 0) 460 || abs(2 * 461 gtable[bi->hitBank][tableIndices[bi->hitBank]].ctr + 1) > 1) 462 bi->tagePred = bi->longestMatchPred; 463 else 464 bi->tagePred = bi->altTaken; 465 } else { 466 bi->altTaken = getBimodePred(pc, bi); 467 bi->tagePred = bi->altTaken; 468 bi->longestMatchPred = bi->altTaken; 469 } 470 //end TAGE prediction 471 472 bi->loopPred = getLoop(pc, bi); // loop prediction 473 474 pred_taken = (((loopUseCounter >= 0) && bi->loopPredValid)) ? 475 (bi->loopPred): (bi->tagePred); 476 DPRINTF(LTage, "Predict for %lx: taken?:%d, loopTaken?:%d, " 477 "loopValid?:%d, loopUseCounter:%d, tagePred:%d, altPred:%d\n", 478 branch_pc, pred_taken, bi->loopPred, bi->loopPredValid, 479 loopUseCounter, bi->tagePred, bi->altTaken); 480 } 481 bi->branchPC = branch_pc; 482 bi->condBranch = cond_branch; 483 specLoopUpdate(branch_pc, pred_taken, bi); 484 return pred_taken; 485} 486 487// PREDICTOR UPDATE 488void 489LTAGE::update(ThreadID tid, Addr branch_pc, bool taken, void* bp_history, 490 bool squashed) 491{ 492 assert(bp_history); 493 494 BranchInfo *bi = static_cast<BranchInfo*>(bp_history); 495 496 if (squashed) { 497 // This restores the global history, then update it 498 // and recomputes the folded histories. 499 squash(tid, taken, bp_history); 500 return; 501 } 502 503 int nrand = random_mt.random<int>(0,3); 504 Addr pc = branch_pc; 505 if (bi->condBranch) { 506 DPRINTF(LTage, "Updating tables for branch:%lx; taken?:%d\n", 507 branch_pc, taken); 508 // first update the loop predictor 509 loopUpdate(pc, taken, bi); 510 511 if (bi->loopPredValid) { 512 if (bi->tagePred != bi->loopPred) { 513 ctrUpdate(loopUseCounter, (bi->loopPred== taken), 7); 514 } 515 } 516 517 // TAGE UPDATE 518 // try to allocate a new entries only if prediction was wrong 519 bool longest_match_pred = false; 520 bool alloc = (bi->tagePred != taken) && (bi->hitBank < nHistoryTables); 521 if (bi->hitBank > 0) { 522 // Manage the selection between longest matching and alternate 523 // matching for "pseudo"-newly allocated longest matching entry 524 longest_match_pred = bi->longestMatchPred; 525 bool PseudoNewAlloc = bi->pseudoNewAlloc; 526 // an entry is considered as newly allocated if its prediction 527 // counter is weak 528 if (PseudoNewAlloc) { 529 if (longest_match_pred == taken) { 530 alloc = false; 531 } 532 // if it was delivering the correct prediction, no need to 533 // allocate new entry even if the overall prediction was false 534 if (longest_match_pred != bi->altTaken) { 535 ctrUpdate(useAltPredForNewlyAllocated, 536 bi->altTaken == taken, 4); 537 } 538 } 539 } 540 541 if (alloc) { 542 // is there some "unuseful" entry to allocate 543 int8_t min = 1; 544 for (int i = nHistoryTables; i > bi->hitBank; i--) { 545 if (gtable[i][bi->tableIndices[i]].u < min) { 546 min = gtable[i][bi->tableIndices[i]].u; 547 } 548 } 549 550 // we allocate an entry with a longer history 551 // to avoid ping-pong, we do not choose systematically the next 552 // entry, but among the 3 next entries 553 int Y = nrand & 554 ((ULL(1) << (nHistoryTables - bi->hitBank - 1)) - 1); 555 int X = bi->hitBank + 1; 556 if (Y & 1) { 557 X++; 558 if (Y & 2) 559 X++; 560 } 561 // No entry available, forces one to be available 562 if (min > 0) { 563 gtable[X][bi->tableIndices[X]].u = 0; 564 } 565 566 567 //Allocate only one entry 568 for (int i = X; i <= nHistoryTables; i++) { 569 if ((gtable[i][bi->tableIndices[i]].u == 0)) { 570 gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i]; 571 gtable[i][bi->tableIndices[i]].ctr = (taken) ? 0 : -1; 572 gtable[i][bi->tableIndices[i]].u = 0; //? 573 } 574 } 575 } 576 //periodic reset of u: reset is not complete but bit by bit 577 tCounter++; 578 if ((tCounter & ((ULL(1) << logTick) - 1)) == 0) { 579 // reset least significant bit 580 // most significant bit becomes least significant bit 581 for (int i = 1; i <= nHistoryTables; i++) { 582 for (int j = 0; j < (ULL(1) << tagTableSizes[i]); j++) { 583 gtable[i][j].u = gtable[i][j].u >> 1; 584 } 585 } 586 } 587 588 if (bi->hitBank > 0) { 589 DPRINTF(LTage, "Updating tag table entry (%d,%d) for branch %lx\n", 590 bi->hitBank, bi->hitBankIndex, branch_pc); 591 ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken, 592 tagTableCounterBits); 593 // if the provider entry is not certified to be useful also update 594 // the alternate prediction 595 if (gtable[bi->hitBank][bi->hitBankIndex].u == 0) { 596 if (bi->altBank > 0) { 597 ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken, 598 tagTableCounterBits); 599 DPRINTF(LTage, "Updating tag table entry (%d,%d) for" 600 " branch %lx\n", bi->hitBank, bi->hitBankIndex, 601 branch_pc); 602 } 603 if (bi->altBank == 0) { 604 baseUpdate(pc, taken, bi); 605 } 606 } 607 608 // update the u counter 609 if (longest_match_pred != bi->altTaken) { 610 if (longest_match_pred == taken) { 611 if (gtable[bi->hitBank][bi->hitBankIndex].u < 1) { 612 gtable[bi->hitBank][bi->hitBankIndex].u++; 613 } 614 } 615 } 616 } else { 617 baseUpdate(pc, taken, bi); 618 } 619 620 //END PREDICTOR UPDATE 621 } 622 if (!squashed) { 623 delete bi; 624 } 625} 626 627void 628LTAGE::updateHistories(ThreadID tid, Addr branch_pc, bool taken, void* b) 629{ 630 BranchInfo* bi = (BranchInfo*)(b); 631 ThreadHistory& tHist = threadHistory[tid]; 632 // UPDATE HISTORIES 633 bool pathbit = ((branch_pc) & 1); 634 //on a squash, return pointers to this and recompute indices. 635 //update user history 636 updateGHist(tHist.gHist, taken, tHist.globalHistory, tHist.ptGhist); 637 tHist.pathHist = (tHist.pathHist << 1) + pathbit; 638 tHist.pathHist = (tHist.pathHist & ((ULL(1) << 16) - 1)); 639 640 bi->ptGhist = tHist.ptGhist; 641 bi->pathHist = tHist.pathHist; 642 //prepare next index and tag computations for user branchs 643 for (int i = 1; i <= nHistoryTables; i++) 644 { 645 bi->ci[i] = tHist.computeIndices[i].comp; 646 bi->ct0[i] = tHist.computeTags[0][i].comp; 647 bi->ct1[i] = tHist.computeTags[1][i].comp; 648 tHist.computeIndices[i].update(tHist.gHist); 649 tHist.computeTags[0][i].update(tHist.gHist); 650 tHist.computeTags[1][i].update(tHist.gHist); 651 } 652 DPRINTF(LTage, "Updating global histories with branch:%lx; taken?:%d, " 653 "path Hist: %x; pointer:%d\n", branch_pc, taken, tHist.pathHist, 654 tHist.ptGhist); 655} 656 657void 658LTAGE::squash(ThreadID tid, bool taken, void *bp_history) 659{ 660 BranchInfo* bi = (BranchInfo*)(bp_history); 661 ThreadHistory& tHist = threadHistory[tid]; 662 DPRINTF(LTage, "Restoring branch info: %lx; taken? %d; PathHistory:%x, " 663 "pointer:%d\n", bi->branchPC,taken, bi->pathHist, bi->ptGhist); 664 tHist.pathHist = bi->pathHist; 665 tHist.ptGhist = bi->ptGhist; 666 tHist.gHist = &(tHist.globalHistory[tHist.ptGhist]); 667 tHist.gHist[0] = (taken ? 1 : 0); 668 for (int i = 1; i <= nHistoryTables; i++) { 669 tHist.computeIndices[i].comp = bi->ci[i]; 670 tHist.computeTags[0][i].comp = bi->ct0[i]; 671 tHist.computeTags[1][i].comp = bi->ct1[i]; 672 tHist.computeIndices[i].update(tHist.gHist); 673 tHist.computeTags[0][i].update(tHist.gHist); 674 tHist.computeTags[1][i].update(tHist.gHist); 675 } 676 677 if (bi->condBranch) { 678 if (bi->loopHit >= 0) { 679 int idx = bi->loopIndex + bi->loopHit; 680 ltable[idx].currentIterSpec = bi->currentIter; 681 } 682 } 683 684} 685 686void 687LTAGE::squash(ThreadID tid, void *bp_history) 688{ 689 BranchInfo* bi = (BranchInfo*)(bp_history); 690 DPRINTF(LTage, "Deleting branch info: %lx\n", bi->branchPC); 691 if (bi->condBranch) { 692 if (bi->loopHit >= 0) { 693 int idx = bi->loopIndex + bi->loopHit; 694 ltable[idx].currentIterSpec = bi->currentIter; 695 } 696 } 697 698 delete bi; 699} 700 701bool 702LTAGE::lookup(ThreadID tid, Addr branch_pc, void* &bp_history) 703{ 704 bool retval = predict(tid, branch_pc, true, bp_history); 705 706 DPRINTF(LTage, "Lookup branch: %lx; predict:%d\n", branch_pc, retval); 707 updateHistories(tid, branch_pc, retval, bp_history); 708 assert(threadHistory[tid].gHist == 709 &threadHistory[tid].globalHistory[threadHistory[tid].ptGhist]); 710 711 return retval; 712} 713 714void 715LTAGE::btbUpdate(ThreadID tid, Addr branch_pc, void* &bp_history) 716{ 717 BranchInfo* bi = (BranchInfo*) bp_history; 718 ThreadHistory& tHist = threadHistory[tid]; 719 DPRINTF(LTage, "BTB miss resets prediction: %lx\n", branch_pc); 720 assert(tHist.gHist == &tHist.globalHistory[tHist.ptGhist]); 721 tHist.gHist[0] = 0; 722 for (int i = 1; i <= nHistoryTables; i++) { 723 tHist.computeIndices[i].comp = bi->ci[i]; 724 tHist.computeTags[0][i].comp = bi->ct0[i]; 725 tHist.computeTags[1][i].comp = bi->ct1[i]; 726 tHist.computeIndices[i].update(tHist.gHist); 727 tHist.computeTags[0][i].update(tHist.gHist); 728 tHist.computeTags[1][i].update(tHist.gHist); 729 } 730} 731 732void 733LTAGE::uncondBranch(ThreadID tid, Addr br_pc, void* &bp_history) 734{ 735 DPRINTF(LTage, "UnConditionalBranch: %lx\n", br_pc); 736 predict(tid, br_pc, false, bp_history); 737 updateHistories(tid, br_pc, true, bp_history); 738 assert(threadHistory[tid].gHist == 739 &threadHistory[tid].globalHistory[threadHistory[tid].ptGhist]); 740} 741 742LTAGE* 743LTAGEParams::create() 744{ 745 return new LTAGE(this); 746} 747