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
  29 /* @file
  30  * Implementation of a bi-mode branch predictor
  31  */
  32
  33 #include "cpu/pred/bi_mode.hh"
  34
  35 #include "base/bitfield.hh"
  36 #include "base/intmath.hh"
  37
  38 BiModeBP::BiModeBP(const BiModeBPParams &params)
  39     : BPredUnit(params),
  40       globalHistoryReg(params.numThreads, 0),
  41       globalHistoryBits(ceilLog2(params.globalPredictorSize)),
  42       choicePredictorSize(params.choicePredictorSize),
  43       choiceCtrBits(params.choiceCtrBits),
  44       globalPredictorSize(params.globalPredictorSize),
  45       globalCtrBits(params.globalCtrBits),
  46       choiceCounters(choicePredictorSize, SatCounter8(choiceCtrBits)),
  47       takenCounters(globalPredictorSize, SatCounter8(globalCtrBits)),
  48       notTakenCounters(globalPredictorSize, SatCounter8(globalCtrBits))
  49 {
  50     if (!isPowerOf2(choicePredictorSize))
  51         fatal("Invalid choice predictor size.\n");
  52     if (!isPowerOf2(globalPredictorSize))
  53         fatal("Invalid global history predictor size.\n");
  54
  55     historyRegisterMask = mask(globalHistoryBits);
  56     choiceHistoryMask = choicePredictorSize - 1;
  57     globalHistoryMask = globalPredictorSize - 1;
  58
  59     choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
  60     takenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1;
  61     notTakenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1;
  62 }
  63
  64 /*
  65  * For an unconditional branch we set its history such that
  66  * everything is set to taken. I.e., its choice predictor
  67  * chooses the taken array and the taken array predicts taken.
  68  */
  69 void
  70 BiModeBP::uncondBranch(ThreadID tid, Addr pc, void * &bpHistory)
  71 {
  72     BPHistory *history = new BPHistory;
  73     history->globalHistoryReg = globalHistoryReg[tid];
  74     history->takenUsed = true;
  75     history->takenPred = true;
  76     history->notTakenPred = true;
  77     history->finalPred = true;
  78     bpHistory = static_cast<void*>(history);
  79     updateGlobalHistReg(tid, true);
  80 }
  81
  82 void
  83 BiModeBP::squash(ThreadID tid, void *bpHistory)
  84 {
  85     BPHistory *history = static_cast<BPHistory*>(bpHistory);
  86     globalHistoryReg[tid] = history->globalHistoryReg;
  87
  88     delete history;
  89 }
  90
  91 /*
  92  * Here we lookup the actual branch prediction. We use the PC to
  93  * identify the bias of a particular branch, which is based on the
  94  * prediction in the choice array. A hash of the global history
  95  * register and a branch's PC is used to index into both the taken
  96  * and not-taken predictors, which both present a prediction. The
  97  * choice array's prediction is used to select between the two
  98  * direction predictors for the final branch prediction.
  99  */
 100 bool
 101 BiModeBP::lookup(ThreadID tid, Addr branchAddr, void * &bpHistory)
 102 {
 103     unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
 104                                 & choiceHistoryMask);
 105     unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
 106                                 ^ globalHistoryReg[tid])
 107                                 & globalHistoryMask);
 108
 109     assert(choiceHistoryIdx < choicePredictorSize);
 110     assert(globalHistoryIdx < globalPredictorSize);
 111
 112     bool choicePrediction = choiceCounters[choiceHistoryIdx]
 113                             > choiceThreshold;
 114     bool takenGHBPrediction = takenCounters[globalHistoryIdx]
 115                               > takenThreshold;
 116     bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx]
 117                                  > notTakenThreshold;
 118     bool finalPrediction;
 119
 120     BPHistory *history = new BPHistory;
 121     history->globalHistoryReg = globalHistoryReg[tid];
 122     history->takenUsed = choicePrediction;
 123     history->takenPred = takenGHBPrediction;
 124     history->notTakenPred = notTakenGHBPrediction;
 125
 126     if (choicePrediction) {
 127         finalPrediction = takenGHBPrediction;
 128     } else {
 129         finalPrediction = notTakenGHBPrediction;
 130     }
 131
 132     history->finalPred = finalPrediction;
 133     bpHistory = static_cast<void*>(history);
 134     updateGlobalHistReg(tid, finalPrediction);
 135
 136     return finalPrediction;
 137 }
 138
 139 void
 140 BiModeBP::btbUpdate(ThreadID tid, Addr branchAddr, void * &bpHistory)
 141 {
 142     globalHistoryReg[tid] &= (historyRegisterMask & ~ULL(1));
 143 }
 144
 145 /* Only the selected direction predictor will be updated with the final
 146  * outcome; the status of the unselected one will not be altered. The choice
 147  * predictor is always updated with the branch outcome, except when the
 148  * choice is opposite to the branch outcome but the selected counter of
 149  * the direction predictors makes a correct final prediction.
 150  */
 151 void
 152 BiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory,
 153                  bool squashed, const StaticInstPtr & inst, Addr corrTarget)
 154 {
 155     assert(bpHistory);
 156
 157     BPHistory *history = static_cast<BPHistory*>(bpHistory);
 158
 159     // We do not update the counters speculatively on a squash.
 160     // We just restore the global history register.
 161     if (squashed) {
 162         globalHistoryReg[tid] = (history->globalHistoryReg << 1) | taken;
 163         return;
 164     }
 165
 166     unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
 167                                 & choiceHistoryMask);
 168     unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
 169                                 ^ history->globalHistoryReg)
 170                                 & globalHistoryMask);
 171
 172     assert(choiceHistoryIdx < choicePredictorSize);
 173     assert(globalHistoryIdx < globalPredictorSize);
 174
 175     if (history->takenUsed) {
 176         // if the taken array's prediction was used, update it
 177         if (taken) {
 178             takenCounters[globalHistoryIdx]++;
 179         } else {
 180             takenCounters[globalHistoryIdx]--;
 181         }
 182     } else {
 183         // if the not-taken array's prediction was used, update it
 184         if (taken) {
 185             notTakenCounters[globalHistoryIdx]++;
 186         } else {
 187             notTakenCounters[globalHistoryIdx]--;
 188         }
 189     }
 190
 191     if (history->finalPred == taken) {
 192        /* If the final prediction matches the actual branch's
 193         * outcome and the choice predictor matches the final
 194         * outcome, we update the choice predictor, otherwise it
 195         * is not updated. While the designers of the bi-mode
 196         * predictor don't explicity say why this is done, one
 197         * can infer that it is to preserve the choice predictor's
 198         * bias with respect to the branch being predicted; afterall,
 199         * the whole point of the bi-mode predictor is to identify the
 200         * atypical case when a branch deviates from its bias.
 201         */
 202         if (history->finalPred == history->takenUsed) {
 203             if (taken) {
 204                 choiceCounters[choiceHistoryIdx]++;
 205             } else {
 206                 choiceCounters[choiceHistoryIdx]--;
 207             }
 208         }
 209     } else {
 210         // always update the choice predictor on an incorrect prediction
 211         if (taken) {
 212             choiceCounters[choiceHistoryIdx]++;
 213         } else {
 214             choiceCounters[choiceHistoryIdx]--;
 215         }
 216     }
 217
 218     delete history;
 219 }
 220
 221 void
 222 BiModeBP::updateGlobalHistReg(ThreadID tid, bool taken)
 223 {
 224     globalHistoryReg[tid] = taken ? (globalHistoryReg[tid] << 1) | 1 :
 225                                (globalHistoryReg[tid] << 1);
 226     globalHistoryReg[tid] &= historyRegisterMask;
 227 }