diff options
Diffstat (limited to 'src/cpu/pred/loop_predictor.cc')
| -rw-r--r-- | src/cpu/pred/loop_predictor.cc | 361 |
1 files changed, 361 insertions, 0 deletions
diff --git a/src/cpu/pred/loop_predictor.cc b/src/cpu/pred/loop_predictor.cc new file mode 100644 index 000000000..2e709f392 --- /dev/null +++ b/src/cpu/pred/loop_predictor.cc @@ -0,0 +1,361 @@ +/* + * 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. + */ + +#include "cpu/pred/loop_predictor.hh" + +#include "params/LoopPredictor.hh" + +LoopPredictor::LoopPredictor(LoopPredictorParams *p) + : SimObject(p), logSizeLoopPred(p->logSizeLoopPred), + loopTableAgeBits(p->loopTableAgeBits), + loopTableConfidenceBits(p->loopTableConfidenceBits), + loopTableTagBits(p->loopTableTagBits), + loopTableIterBits(p->loopTableIterBits), + logLoopTableAssoc(p->logLoopTableAssoc), + confidenceThreshold((1 << loopTableConfidenceBits) - 1), + loopTagMask((1 << loopTableTagBits) - 1), + loopNumIterMask((1 << loopTableIterBits) - 1), + loopSetMask((1 << (logSizeLoopPred - logLoopTableAssoc)) - 1), + loopUseCounter(-1), + withLoopBits(p->withLoopBits), + useDirectionBit(p->useDirectionBit), + useSpeculation(p->useSpeculation), + useHashing(p->useHashing), + restrictAllocation(p->restrictAllocation), + initialLoopIter(p->initialLoopIter), + initialLoopAge(p->initialLoopAge), + optionalAgeReset(p->optionalAgeReset) +{ + assert(initialLoopAge <= ((1 << loopTableAgeBits) - 1)); +} + +void +LoopPredictor::init() +{ + // 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]; +} + +LoopPredictor::BranchInfo* +LoopPredictor::makeBranchInfo() +{ + return new BranchInfo(); +} + +int +LoopPredictor::lindex(Addr pc_in, unsigned instShiftAmt) 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 pc = pc_in >> instShiftAmt; + if (useHashing) { + pc ^= pc_in; + } + return ((pc & loopSetMask) << logLoopTableAssoc); +} + +int +LoopPredictor::finallindex(int index, int lowPcBits, int way) const +{ + return (useHashing ? (index ^ ((lowPcBits >> way) << logLoopTableAssoc)) : + (index)) + + way; +} + +//loop prediction: only used if high confidence +bool +LoopPredictor::getLoop(Addr pc, BranchInfo* bi, bool speculative, + unsigned instShiftAmt) const +{ + bi->loopHit = -1; + bi->loopPredValid = false; + bi->loopIndex = lindex(pc, instShiftAmt); + + if (useHashing) { + unsigned pcShift = logSizeLoopPred - logLoopTableAssoc; + bi->loopIndexB = (pc >> pcShift) & loopSetMask; + bi->loopTag = (pc >> pcShift) ^ (pc >> (pcShift + loopTableTagBits)); + bi->loopTag &= loopTagMask; + } else { + unsigned pcShift = instShiftAmt + logSizeLoopPred - logLoopTableAssoc; + bi->loopTag = (pc >> pcShift) & loopTagMask; + // bi->loopIndexB is not used without hash + } + + for (int i = 0; i < (1 << logLoopTableAssoc); i++) { + int idx = finallindex(bi->loopIndex, bi->loopIndexB, i); + if (ltable[idx].tag == bi->loopTag) { + bi->loopHit = i; + bi->loopPredValid = calcConf(idx); + + 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; +} + +bool +LoopPredictor::calcConf(int index) const +{ + return ltable[index].confidence == confidenceThreshold; +} + +void +LoopPredictor::specLoopUpdate(bool taken, BranchInfo* bi) +{ + if (bi->loopHit>=0) { + int index = finallindex(bi->loopIndex, bi->loopIndexB, bi->loopHit); + if (taken != ltable[index].dir) { + ltable[index].currentIterSpec = 0; + } else { + ltable[index].currentIterSpec = + (ltable[index].currentIterSpec + 1) & loopNumIterMask; + } + } +} + +bool +LoopPredictor::optionalAgeInc(int nrand) const +{ + return false; +} + +void +LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred, + int random0, int random1, int random2) +{ + int idx = finallindex(bi->loopIndex, bi->loopIndexB, 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 != tage_pred || optionalAgeInc(random0)) { + 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; + if (optionalAgeReset) { + ltable[idx].age = 0; + } + } + } + + if (taken != (useDirectionBit ? ltable[idx].dir : true)) { + if (ltable[idx].currentIter == ltable[idx].numIter) { + 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 { + 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; + if (optionalAgeReset) { + ltable[idx].age = 0; + } + ltable[idx].confidence = 0; + } + } + ltable[idx].currentIter = 0; + } + + } else if (useDirectionBit ? (bi->predTaken != taken) : taken) { + if ((random2 & 3) == 0 || !restrictAllocation) { + //try to allocate an entry on taken branch + int nrand = random1; + for (int i = 0; i < (1 << logLoopTableAssoc); i++) { + int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) - 1); + idx = finallindex(bi->loopIndex, bi->loopIndexB, loop_hit); + if (ltable[idx].age == 0) { + ltable[idx].dir = !taken; // ignored if no useDirectionBit + ltable[idx].tag = bi->loopTag; + ltable[idx].numIter = 0; + ltable[idx].age = initialLoopAge; + ltable[idx].confidence = 0; + ltable[idx].currentIter = initialLoopIter; + break; + + } else { + ltable[idx].age--; + } + if (restrictAllocation) { + break; + } + } + } + } +} + +bool +LoopPredictor::loopPredict(ThreadID tid, Addr branch_pc, bool cond_branch, + BranchInfo* bi, bool prev_pred_taken, unsigned instShiftAmt) +{ + bool pred_taken = prev_pred_taken; + if (cond_branch) { + // loop prediction + bi->loopPred = getLoop(branch_pc, bi, useSpeculation, instShiftAmt); + + if ((loopUseCounter >= 0) && bi->loopPredValid) { + pred_taken = bi->loopPred; + bi->loopPredUsed = true; + } + + if (useSpeculation) { + specLoopUpdate(pred_taken, bi); + } + } + + return pred_taken; +} + +void +LoopPredictor::squash(ThreadID tid, BranchInfo *bi) +{ + if (bi->loopHit >= 0) { + int idx = finallindex(bi->loopIndex, + bi->loopIndexB, + bi->loopHit); + ltable[idx].currentIterSpec = bi->currentIter; + } +} + +void +LoopPredictor::squashLoop(BranchInfo* bi) +{ + if (bi->loopHit >= 0) { + int idx = finallindex(bi->loopIndex, + bi->loopIndexB, + bi->loopHit); + ltable[idx].currentIterSpec = bi->currentIter; + } +} + +void +LoopPredictor::updateStats(bool taken, BranchInfo* bi) +{ + if (taken == bi->loopPred) { + loopPredictorCorrect++; + } else { + loopPredictorWrong++; + } +} + +void +LoopPredictor::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, + bool tage_pred, BranchInfo* bi, + unsigned instShiftAmt, int rand0, int rand1, + int rand2) +{ + 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, instShiftAmt); + } + + if (bi->loopPredValid) { + if (bi->predTaken != bi->loopPred) { + signedCtrUpdate(loopUseCounter, + (bi->loopPred == taken), + withLoopBits); + } + } + + loopUpdate(branch_pc, taken, bi, tage_pred, rand0, rand1, rand2); +} + +void +LoopPredictor::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"); +} + +LoopPredictor * +LoopPredictorParams::create() +{ + return new LoopPredictor(this); +} |