| /* |
| * Copyright (c) 2014 The University of Wisconsin |
| * |
| * Copyright (c) 2006 INRIA (Institut National de Recherche en |
| * Informatique et en Automatique / French National Research Institute |
| * for Computer Science and Applied Mathematics) |
| * |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions are |
| * met: redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer; |
| * redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution; |
| * neither the name of the copyright holders nor the names of its |
| * contributors may be used to endorse or promote products derived from |
| * this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| * |
| * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais, |
| * from André Seznec's code. |
| */ |
| |
| /* @file |
| * Implementation of a L-TAGE branch predictor |
| */ |
| |
| #include "cpu/pred/ltage.hh" |
| |
| #include "base/intmath.hh" |
| #include "base/logging.hh" |
| #include "base/random.hh" |
| #include "base/trace.hh" |
| #include "debug/Fetch.hh" |
| #include "debug/LTage.hh" |
| |
| LTAGE::LTAGE(const LTAGEParams *params) |
| : TAGE(params), |
| logSizeLoopPred(params->logSizeLoopPred), |
| loopTableAgeBits(params->loopTableAgeBits), |
| loopTableConfidenceBits(params->loopTableConfidenceBits), |
| loopTableTagBits(params->loopTableTagBits), |
| loopTableIterBits(params->loopTableIterBits), |
| logLoopTableAssoc(params->logLoopTableAssoc), |
| confidenceThreshold((1 << loopTableConfidenceBits) - 1), |
| loopTagMask((1 << loopTableTagBits) - 1), |
| loopNumIterMask((1 << loopTableIterBits) - 1), |
| loopSetMask((1 << (logSizeLoopPred - logLoopTableAssoc)) - 1), |
| loopUseCounter(0), |
| withLoopBits(params->withLoopBits), |
| useDirectionBit(params->useDirectionBit), |
| useSpeculation(params->useSpeculation), |
| useHashing(params->useHashing) |
| { |
| // we use uint16_t type for these vales, so they cannot be more than |
| // 16 bits |
| assert(loopTableTagBits <= 16); |
| assert(loopTableIterBits <= 16); |
| |
| assert(logSizeLoopPred >= logLoopTableAssoc); |
| |
| ltable = new LoopEntry[ULL(1) << logSizeLoopPred]; |
| } |
| |
| int |
| LTAGE::lindex(Addr pc_in) const |
| { |
| // The loop table is implemented as a linear table |
| // If associativity is N (N being 1 << logLoopTableAssoc), |
| // the first N entries are for set 0, the next N entries are for set 1, |
| // and so on. |
| // Thus, this function calculates the set and then it gets left shifted |
| // by logLoopTableAssoc in order to return the index of the first of the |
| // N entries of the set |
| Addr mask = (ULL(1) << (logSizeLoopPred - logLoopTableAssoc)) - 1; |
| Addr pc = pc_in >> instShiftAmt; |
| if (useHashing) { |
| // copied from TAGE-SC-L |
| // (http://www.jilp.org/cbp2016/code/AndreSeznecLimited.tar.gz) |
| pc ^= (pc_in >> (instShiftAmt + logLoopTableAssoc)); |
| } |
| return ((pc & mask) << logLoopTableAssoc); |
| } |
| |
| int |
| LTAGE::finallindex(int index, int lowPcBits, int way) const |
| { |
| // copied from TAGE-SC-L |
| // (http://www.jilp.org/cbp2016/code/AndreSeznecLimited.tar.gz) |
| return (useHashing ? (index ^ ((lowPcBits >> way) << logLoopTableAssoc)) : |
| (index)) |
| + way; |
| } |
| |
| //loop prediction: only used if high confidence |
| bool |
| LTAGE::getLoop(Addr pc, LTageBranchInfo* bi, bool speculative) const |
| { |
| bi->loopHit = -1; |
| bi->loopPredValid = false; |
| bi->loopIndex = lindex(pc); |
| unsigned pcShift = instShiftAmt + logSizeLoopPred - logLoopTableAssoc; |
| bi->loopTag = ((pc) >> pcShift) & loopTagMask; |
| |
| if (useHashing) { |
| bi->loopTag ^= ((pc >> (pcShift + logSizeLoopPred)) & loopTagMask); |
| bi->loopLowPcBits = (pc >> pcShift) & loopSetMask; |
| } |
| |
| for (int i = 0; i < (1 << logLoopTableAssoc); i++) { |
| int idx = finallindex(bi->loopIndex, bi->loopLowPcBits, i); |
| if (ltable[idx].tag == bi->loopTag) { |
| bi->loopHit = i; |
| bi->loopPredValid = |
| ltable[idx].confidence == confidenceThreshold; |
| |
| uint16_t iter = speculative ? ltable[idx].currentIterSpec |
| : ltable[idx].currentIter; |
| |
| if ((iter + 1) == ltable[idx].numIter) { |
| return useDirectionBit ? !(ltable[idx].dir) : false; |
| } else { |
| return useDirectionBit ? (ltable[idx].dir) : true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| void |
| LTAGE::specLoopUpdate(bool taken, LTageBranchInfo* bi) |
| { |
| if (bi->loopHit>=0) { |
| int index = finallindex(bi->loopIndex, bi->loopLowPcBits, bi->loopHit); |
| if (taken != ltable[index].dir) { |
| ltable[index].currentIterSpec = 0; |
| } else { |
| ltable[index].currentIterSpec = |
| (ltable[index].currentIterSpec + 1) & loopNumIterMask; |
| } |
| } |
| } |
| |
| void |
| LTAGE::loopUpdate(Addr pc, bool taken, LTageBranchInfo* bi) |
| { |
| int idx = finallindex(bi->loopIndex, bi->loopLowPcBits, bi->loopHit); |
| if (bi->loopHit >= 0) { |
| //already a hit |
| if (bi->loopPredValid) { |
| if (taken != bi->loopPred) { |
| // free the entry |
| ltable[idx].numIter = 0; |
| ltable[idx].age = 0; |
| ltable[idx].confidence = 0; |
| ltable[idx].currentIter = 0; |
| return; |
| } else if (bi->loopPred != bi->tageBranchInfo->tagePred) { |
| DPRINTF(LTage, "Loop Prediction success:%lx\n",pc); |
| TAGEBase::unsignedCtrUpdate(ltable[idx].age, true, |
| loopTableAgeBits); |
| } |
| } |
| |
| ltable[idx].currentIter = |
| (ltable[idx].currentIter + 1) & loopNumIterMask; |
| if (ltable[idx].currentIter > ltable[idx].numIter) { |
| ltable[idx].confidence = 0; |
| if (ltable[idx].numIter != 0) { |
| // free the entry |
| ltable[idx].numIter = 0; |
| ltable[idx].age = 0; |
| ltable[idx].confidence = 0; |
| } |
| } |
| |
| if (taken != (useDirectionBit ? ltable[idx].dir : true)) { |
| if (ltable[idx].currentIter == ltable[idx].numIter) { |
| DPRINTF(LTage, "Loop End predicted successfully:%lx\n", pc); |
| |
| TAGEBase::unsignedCtrUpdate(ltable[idx].confidence, true, |
| loopTableConfidenceBits); |
| //just do not predict when the loop count is 1 or 2 |
| if (ltable[idx].numIter < 3) { |
| // free the entry |
| ltable[idx].dir = taken; // ignored if no useDirectionBit |
| ltable[idx].numIter = 0; |
| ltable[idx].age = 0; |
| ltable[idx].confidence = 0; |
| } |
| } else { |
| DPRINTF(LTage, "Loop End predicted incorrectly:%lx\n", pc); |
| if (ltable[idx].numIter == 0) { |
| // first complete nest; |
| ltable[idx].confidence = 0; |
| ltable[idx].numIter = ltable[idx].currentIter; |
| } else { |
| //not the same number of iterations as last time: free the |
| //entry |
| ltable[idx].numIter = 0; |
| ltable[idx].age = 0; |
| ltable[idx].confidence = 0; |
| } |
| } |
| ltable[idx].currentIter = 0; |
| } |
| |
| } else if (useDirectionBit ? |
| ((bi->loopPredValid ? |
| bi->loopPred : bi->tageBranchInfo->tagePred) != taken) : |
| taken) { |
| //try to allocate an entry on taken branch |
| int nrand = TAGEBase::getRandom(); |
| for (int i = 0; i < (1 << logLoopTableAssoc); i++) { |
| int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) - 1); |
| idx = bi->loopIndex + loop_hit; |
| if (ltable[idx].age == 0) { |
| DPRINTF(LTage, "Allocating loop pred entry for branch %lx\n", |
| pc); |
| ltable[idx].dir = !taken; // ignored if no useDirectionBit |
| ltable[idx].tag = bi->loopTag; |
| ltable[idx].numIter = 0; |
| ltable[idx].age = (1 << loopTableAgeBits) - 1; |
| ltable[idx].confidence = 0; |
| ltable[idx].currentIter = 1; |
| break; |
| |
| } |
| else |
| ltable[idx].age--; |
| } |
| } |
| |
| } |
| |
| //prediction |
| bool |
| LTAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) |
| { |
| LTageBranchInfo *bi = new LTageBranchInfo(*tage); |
| b = (void*)(bi); |
| |
| bool pred_taken = tage->tagePredict(tid, branch_pc, cond_branch, |
| bi->tageBranchInfo); |
| |
| if (cond_branch) { |
| // loop prediction |
| bi->loopPred = getLoop(branch_pc, bi, useSpeculation); |
| |
| if ((loopUseCounter >= 0) && bi->loopPredValid) { |
| pred_taken = bi->loopPred; |
| bi->tageBranchInfo->provider = LOOP; |
| } |
| DPRINTF(LTage, "Predict for %lx: taken?:%d, loopTaken?:%d, " |
| "loopValid?:%d, loopUseCounter:%d, tagePred:%d, altPred:%d\n", |
| branch_pc, pred_taken, bi->loopPred, bi->loopPredValid, |
| loopUseCounter, bi->tageBranchInfo->tagePred, |
| bi->tageBranchInfo->altTaken); |
| |
| if (useSpeculation) { |
| specLoopUpdate(pred_taken, bi); |
| } |
| } |
| |
| return pred_taken; |
| } |
| |
| void |
| LTAGE::update(ThreadID tid, Addr branch_pc, bool taken, void* bp_history, |
| bool squashed, const StaticInstPtr & inst, Addr corrTarget) |
| { |
| assert(bp_history); |
| |
| LTageBranchInfo* bi = static_cast<LTageBranchInfo*>(bp_history); |
| |
| if (squashed) { |
| if (tage->isSpeculativeUpdateEnabled()) { |
| // This restores the global history, then update it |
| // and recomputes the folded histories. |
| tage->squash(tid, taken, bi->tageBranchInfo, corrTarget); |
| squashLoop(bi); |
| } |
| return; |
| } |
| |
| int nrand = TAGEBase::getRandom() & 3; |
| if (bi->tageBranchInfo->condBranch) { |
| DPRINTF(LTage, "Updating tables for branch:%lx; taken?:%d\n", |
| branch_pc, taken); |
| tage->updateStats(taken, bi->tageBranchInfo); |
| // update stats |
| if (bi->tageBranchInfo->provider == LOOP) { |
| if (taken == bi->loopPred) { |
| loopPredictorCorrect++; |
| } else { |
| loopPredictorWrong++; |
| } |
| } |
| // cond Branch Update |
| if (useSpeculation) { |
| // recalculate loop prediction without speculation |
| // It is ok to overwrite the loop prediction fields in bi |
| // as the stats have already been updated with the previous |
| // values |
| bi->loopPred = getLoop(branch_pc, bi, false); |
| } |
| if (bi->loopPredValid) { |
| if (bi->tageBranchInfo->tagePred != bi->loopPred) { |
| TAGEBase::ctrUpdate(loopUseCounter, |
| (bi->loopPred == taken), |
| withLoopBits); |
| } |
| } |
| |
| loopUpdate(branch_pc, taken, bi); |
| |
| tage->condBranchUpdate(tid, branch_pc, taken, bi->tageBranchInfo, |
| nrand, corrTarget); |
| } |
| |
| tage->updateHistories(tid, branch_pc, taken, bi->tageBranchInfo, false, |
| inst, corrTarget); |
| |
| delete bi; |
| } |
| |
| void |
| LTAGE::squashLoop(LTageBranchInfo* bi) |
| { |
| if (bi->tageBranchInfo->condBranch) { |
| if (bi->loopHit >= 0) { |
| int idx = finallindex(bi->loopIndex, |
| bi->loopLowPcBits, |
| bi->loopHit); |
| ltable[idx].currentIterSpec = bi->currentIter; |
| } |
| } |
| } |
| |
| void |
| LTAGE::squash(ThreadID tid, void *bp_history) |
| { |
| LTageBranchInfo* bi = (LTageBranchInfo*)(bp_history); |
| |
| if (bi->tageBranchInfo->condBranch) { |
| squashLoop(bi); |
| } |
| |
| TAGE::squash(tid, bp_history); |
| } |
| |
| void |
| LTAGE::regStats() |
| { |
| TAGE::regStats(); |
| |
| loopPredictorCorrect |
| .name(name() + ".loopPredictorCorrect") |
| .desc("Number of times the loop predictor is the provider and " |
| "the prediction is correct"); |
| |
| loopPredictorWrong |
| .name(name() + ".loopPredictorWrong") |
| .desc("Number of times the loop predictor is the provider and " |
| "the prediction is wrong"); |
| } |
| |
| |
| |
| LTAGE* |
| LTAGEParams::create() |
| { |
| return new LTAGE(this); |
| } |
