src/cpu/pred/bi_mode.cc

   1 /*
   2  * Copyright (c) 2014 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Anthony Gutierrez
  29  */
  30
  31 /* @file
  32  * Implementation of a bi-mode branch predictor
  33  */
  34
  35 #include "cpu/pred/bi_mode.hh"
  36
  37 #include "base/bitfield.hh"
  38 #include "base/intmath.hh"
  39
  40 BiModeBP::BiModeBP(const BiModeBPParams *params)
  41     : BPredUnit(params),
  42       globalHistoryReg(params->numThreads, 0),
  43       globalHistoryBits(ceilLog2(params->globalPredictorSize)),
  44       choicePredictorSize(params->choicePredictorSize),
  45       choiceCtrBits(params->choiceCtrBits),
  46       globalPredictorSize(params->globalPredictorSize),
  47       globalCtrBits(params->globalCtrBits)
  48 {
  49     if (!isPowerOf2(choicePredictorSize))
  50         fatal("Invalid choice predictor size.\n");
  51     if (!isPowerOf2(globalPredictorSize))
  52         fatal("Invalid global history predictor size.\n");
  53
  54     choiceCounters.resize(choicePredictorSize);
  55     takenCounters.resize(globalPredictorSize);
  56     notTakenCounters.resize(globalPredictorSize);
  57
  58     for (int i = 0; i < choicePredictorSize; ++i) {
  59         choiceCounters[i].setBits(choiceCtrBits);
  60     }
  61     for (int i = 0; i < globalPredictorSize; ++i) {
  62         takenCounters[i].setBits(globalCtrBits);
  63         notTakenCounters[i].setBits(globalCtrBits);
  64     }
  65
  66     historyRegisterMask = mask(globalHistoryBits);
  67     choiceHistoryMask = choicePredictorSize - 1;
  68     globalHistoryMask = globalPredictorSize - 1;
  69
  70     choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
  71     takenThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
  72     notTakenThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
  73 }
  74
  75 /*
  76  * For an unconditional branch we set its history such that
  77  * everything is set to taken. I.e., its choice predictor
  78  * chooses the taken array and the taken array predicts taken.
  79  */
  80 void
  81 BiModeBP::uncondBranch(ThreadID tid, Addr pc, void * &bpHistory)
  82 {
  83     BPHistory *history = new BPHistory;
  84     history->globalHistoryReg = globalHistoryReg[tid];
  85     history->takenUsed = true;
  86     history->takenPred = true;
  87     history->notTakenPred = true;
  88     history->finalPred = true;
  89     bpHistory = static_cast<void*>(history);
  90     updateGlobalHistReg(tid, true);
  91 }
  92
  93 void
  94 BiModeBP::squash(ThreadID tid, void *bpHistory)
  95 {
  96     BPHistory *history = static_cast<BPHistory*>(bpHistory);
  97     globalHistoryReg[tid] = history->globalHistoryReg;
  98
  99     delete history;
 100 }
 101
 102 /*
 103  * Here we lookup the actual branch prediction. We use the PC to
 104  * identify the bias of a particular branch, which is based on the
 105  * prediction in the choice array. A hash of the global history
 106  * register and a branch's PC is used to index into both the taken
 107  * and not-taken predictors, which both present a prediction. The
 108  * choice array's prediction is used to select between the two
 109  * direction predictors for the final branch prediction.
 110  */
 111 bool
 112 BiModeBP::lookup(ThreadID tid, Addr branchAddr, void * &bpHistory)
 113 {
 114     unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
 115                                 & choiceHistoryMask);
 116     unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
 117                                 ^ globalHistoryReg[tid])
 118                                 & globalHistoryMask);
 119
 120     assert(choiceHistoryIdx < choicePredictorSize);
 121     assert(globalHistoryIdx < globalPredictorSize);
 122
 123     bool choicePrediction = choiceCounters[choiceHistoryIdx].read()
 124                             > choiceThreshold;
 125     bool takenGHBPrediction = takenCounters[globalHistoryIdx].read()
 126                               > takenThreshold;
 127     bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx].read()
 128                                  > notTakenThreshold;
 129     bool finalPrediction;
 130
 131     BPHistory *history = new BPHistory;
 132     history->globalHistoryReg = globalHistoryReg[tid];
 133     history->takenUsed = choicePrediction;
 134     history->takenPred = takenGHBPrediction;
 135     history->notTakenPred = notTakenGHBPrediction;
 136
 137     if (choicePrediction) {
 138         finalPrediction = takenGHBPrediction;
 139     } else {
 140         finalPrediction = notTakenGHBPrediction;
 141     }
 142
 143     history->finalPred = finalPrediction;
 144     bpHistory = static_cast<void*>(history);
 145     updateGlobalHistReg(tid, finalPrediction);
 146
 147     return finalPrediction;
 148 }
 149
 150 void
 151 BiModeBP::btbUpdate(ThreadID tid, Addr branchAddr, void * &bpHistory)
 152 {
 153     globalHistoryReg[tid] &= (historyRegisterMask & ~ULL(1));
 154 }
 155
 156 /* Only the selected direction predictor will be updated with the final
 157  * outcome; the status of the unselected one will not be altered. The choice
 158  * predictor is always updated with the branch outcome, except when the
 159  * choice is opposite to the branch outcome but the selected counter of
 160  * the direction predictors makes a correct final prediction.
 161  */
 162 void
 163 BiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory,
 164                  bool squashed)
 165 {
 166     assert(bpHistory);
 167
 168     BPHistory *history = static_cast<BPHistory*>(bpHistory);
 169
 170     // We do not update the counters speculatively on a squash.
 171     // We just restore the global history register.
 172     if (squashed) {
 173         globalHistoryReg[tid] = (history->globalHistoryReg << 1) | taken;
 174         return;
 175     }
 176
 177     unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
 178                                 & choiceHistoryMask);
 179     unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
 180                                 ^ history->globalHistoryReg)
 181                                 & globalHistoryMask);
 182
 183     assert(choiceHistoryIdx < choicePredictorSize);
 184     assert(globalHistoryIdx < globalPredictorSize);
 185
 186     if (history->takenUsed) {
 187         // if the taken array's prediction was used, update it
 188         if (taken) {
 189             takenCounters[globalHistoryIdx].increment();
 190         } else {
 191             takenCounters[globalHistoryIdx].decrement();
 192         }
 193     } else {
 194         // if the not-taken array's prediction was used, update it
 195         if (taken) {
 196             notTakenCounters[globalHistoryIdx].increment();
 197         } else {
 198             notTakenCounters[globalHistoryIdx].decrement();
 199         }
 200     }
 201
 202     if (history->finalPred == taken) {
 203        /* If the final prediction matches the actual branch's
 204         * outcome and the choice predictor matches the final
 205         * outcome, we update the choice predictor, otherwise it
 206         * is not updated. While the designers of the bi-mode
 207         * predictor don't explicity say why this is done, one
 208         * can infer that it is to preserve the choice predictor's
 209         * bias with respect to the branch being predicted; afterall,
 210         * the whole point of the bi-mode predictor is to identify the
 211         * atypical case when a branch deviates from its bias.
 212         */
 213         if (history->finalPred == history->takenUsed) {
 214             if (taken) {
 215                 choiceCounters[choiceHistoryIdx].increment();
 216             } else {
 217                 choiceCounters[choiceHistoryIdx].decrement();
 218             }
 219         }
 220     } else {
 221         // always update the choice predictor on an incorrect prediction
 222         if (taken) {
 223             choiceCounters[choiceHistoryIdx].increment();
 224         } else {
 225             choiceCounters[choiceHistoryIdx].decrement();
 226         }
 227     }
 228
 229     delete history;
 230 }
 231
 232 unsigned
 233 BiModeBP::getGHR(ThreadID tid, void *bp_history) const
 234 {
 235     return static_cast<BPHistory*>(bp_history)->globalHistoryReg;
 236 }
 237
 238 void
 239 BiModeBP::updateGlobalHistReg(ThreadID tid, bool taken)
 240 {
 241     globalHistoryReg[tid] = taken ? (globalHistoryReg[tid] << 1) | 1 :
 242                                (globalHistoryReg[tid] << 1);
 243     globalHistoryReg[tid] &= historyRegisterMask;
 244 }
 245
 246 BiModeBP*
 247 BiModeBPParams::create()
 248 {
 249     return new BiModeBP(this);
 250 }