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