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