src/cpu/o3/tournament_pred.hh

   1 /*
   2  * Copyright (c) 2004-2006 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: Kevin Lim
  29  */
  30
  31 #ifndef __CPU_O3_TOURNAMENT_PRED_HH__
  32 #define __CPU_O3_TOURNAMENT_PRED_HH__
  33
  34 #include "cpu/o3/sat_counter.hh"
  35 #include "sim/host.hh"
  36 #include <vector>
  37
  38 /**
  39  * Implements a tournament branch predictor, hopefully identical to the one
  40  * used in the 21264.  It has a local predictor, which uses a local history
  41  * table to index into a table of counters, and a global predictor, which
  42  * uses a global history to index into a table of counters.  A choice
  43  * predictor chooses between the two.  Only the global history register
  44  * is speculatively updated, the rest are updated upon branches committing
  45  * or misspeculating.
  46  */
  47 class TournamentBP
  48 {
  49   public:
  50     /**
  51      * Default branch predictor constructor.
  52      */
  53     TournamentBP(unsigned localPredictorSize,
  54                  unsigned localCtrBits,
  55                  unsigned localHistoryTableSize,
  56                  unsigned localHistoryBits,
  57                  unsigned globalPredictorSize,
  58                  unsigned globalHistoryBits,
  59                  unsigned globalCtrBits,
  60                  unsigned choicePredictorSize,
  61                  unsigned choiceCtrBits,
  62                  unsigned instShiftAmt);
  63
  64     /**
  65      * Looks up the given address in the branch predictor and returns
  66      * a true/false value as to whether it is taken.  Also creates a
  67      * BPHistory object to store any state it will need on squash/update.
  68      * @param branch_addr The address of the branch to look up.
  69      * @param bp_history Pointer that will be set to the BPHistory object.
  70      * @return Whether or not the branch is taken.
  71      */
  72     bool lookup(Addr &branch_addr, void * &bp_history);
  73
  74     /**
  75      * Records that there was an unconditional branch, and modifies
  76      * the bp history to point to an object that has the previous
  77      * global history stored in it.
  78      * @param bp_history Pointer that will be set to the BPHistory object.
  79      */
  80     void uncondBr(void * &bp_history);
  81
  82     /**
  83      * Updates the branch predictor with the actual result of a branch.
  84      * @param branch_addr The address of the branch to update.
  85      * @param taken Whether or not the branch was taken.
  86      * @param bp_history Pointer to the BPHistory object that was created
  87      * when the branch was predicted.
  88      */
  89     void update(Addr &branch_addr, bool taken, void *bp_history);
  90
  91     /**
  92      * Restores the global branch history on a squash.
  93      * @param bp_history Pointer to the BPHistory object that has the
  94      * previous global branch history in it.
  95      */
  96     void squash(void *bp_history);
  97
  98     /** Returns the global history. */
  99     inline unsigned readGlobalHist() { return globalHistory; }
 100
 101   private:
 102     /**
 103      * Returns if the branch should be taken or not, given a counter
 104      * value.
 105      * @param count The counter value.
 106      */
 107     inline bool getPrediction(uint8_t &count);
 108
 109     /**
 110      * Returns the local history index, given a branch address.
 111      * @param branch_addr The branch's PC address.
 112      */
 113     inline unsigned calcLocHistIdx(Addr &branch_addr);
 114
 115     /** Updates global history as taken. */
 116     inline void updateGlobalHistTaken();
 117
 118     /** Updates global history as not taken. */
 119     inline void updateGlobalHistNotTaken();
 120
 121     /**
 122      * Updates local histories as taken.
 123      * @param local_history_idx The local history table entry that
 124      * will be updated.
 125      */
 126     inline void updateLocalHistTaken(unsigned local_history_idx);
 127
 128     /**
 129      * Updates local histories as not taken.
 130      * @param local_history_idx The local history table entry that
 131      * will be updated.
 132      */
 133     inline void updateLocalHistNotTaken(unsigned local_history_idx);
 134
 135     /**
 136      * The branch history information that is created upon predicting
 137      * a branch.  It will be passed back upon updating and squashing,
 138      * when the BP can use this information to update/restore its
 139      * state properly.
 140      */
 141     struct BPHistory {
 142 #ifdef DEBUG
 143         BPHistory()
 144         { newCount++; }
 145         ~BPHistory()
 146         { newCount--; }
 147
 148         static int newCount;
 149 #endif
 150         unsigned globalHistory;
 151         bool localPredTaken;
 152         bool globalPredTaken;
 153         bool globalUsed;
 154     };
 155
 156     /** Local counters. */
 157     std::vector<SatCounter> localCtrs;
 158
 159     /** Size of the local predictor. */
 160     unsigned localPredictorSize;
 161
 162     /** Mask to get the proper index bits into the predictor. */
 163     unsigned localPredictorMask;
 164
 165     /** Number of bits of the local predictor's counters. */
 166     unsigned localCtrBits;
 167
 168     /** Array of local history table entries. */
 169     std::vector<unsigned> localHistoryTable;
 170
 171     /** Size of the local history table. */
 172     unsigned localHistoryTableSize;
 173
 174     /** Number of bits for each entry of the local history table.
 175      *  @todo Doesn't this come from the size of the local predictor?
 176      */
 177     unsigned localHistoryBits;
 178
 179     /** Mask to get the proper local history. */
 180     unsigned localHistoryMask;
 181
 182     /** Array of counters that make up the global predictor. */
 183     std::vector<SatCounter> globalCtrs;
 184
 185     /** Size of the global predictor. */
 186     unsigned globalPredictorSize;
 187
 188     /** Number of bits of the global predictor's counters. */
 189     unsigned globalCtrBits;
 190
 191     /** Global history register. */
 192     unsigned globalHistory;
 193
 194     /** Number of bits for the global history. */
 195     unsigned globalHistoryBits;
 196
 197     /** Mask to get the proper global history. */
 198     unsigned globalHistoryMask;
 199
 200     /** Array of counters that make up the choice predictor. */
 201     std::vector<SatCounter> choiceCtrs;
 202
 203     /** Size of the choice predictor (identical to the global predictor). */
 204     unsigned choicePredictorSize;
 205
 206     /** Number of bits of the choice predictor's counters. */
 207     unsigned choiceCtrBits;
 208
 209     /** Number of bits to shift the instruction over to get rid of the word
 210      *  offset.
 211      */
 212     unsigned instShiftAmt;
 213
 214     /** Threshold for the counter value; above the threshold is taken,
 215      *  equal to or below the threshold is not taken.
 216      */
 217     unsigned threshold;
 218 };
 219
 220 #endif // __CPU_O3_TOURNAMENT_PRED_HH__