src/cpu/pred/tournament.hh

   1 /*
   2  * Copyright (c) 2011, 2014 ARM Limited
   3  * All rights reserved
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Copyright (c) 2004-2006 The Regents of The University of Michigan
  15  * All rights reserved.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions are
  19  * met: redistributions of source code must retain the above copyright
  20  * notice, this list of conditions and the following disclaimer;
  21  * redistributions in binary form must reproduce the above copyright
  22  * notice, this list of conditions and the following disclaimer in the
  23  * documentation and/or other materials provided with the distribution;
  24  * neither the name of the copyright holders nor the names of its
  25  * contributors may be used to endorse or promote products derived from
  26  * this software without specific prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39  */
  40
  41 #ifndef __CPU_PRED_TOURNAMENT_PRED_HH__
  42 #define __CPU_PRED_TOURNAMENT_PRED_HH__
  43
  44 #include <vector>
  45
  46 #include "base/sat_counter.hh"
  47 #include "base/types.hh"
  48 #include "cpu/pred/bpred_unit.hh"
  49 #include "params/TournamentBP.hh"
  50
  51 /**
  52  * Implements a tournament branch predictor, hopefully identical to the one
  53  * used in the 21264.  It has a local predictor, which uses a local history
  54  * table to index into a table of counters, and a global predictor, which
  55  * uses a global history to index into a table of counters.  A choice
  56  * predictor chooses between the two.  Both the global history register
  57  * and the selected local history are speculatively updated.
  58  */
  59 class TournamentBP : public BPredUnit
  60 {
  61   public:
  62     /**
  63      * Default branch predictor constructor.
  64      */
  65     TournamentBP(const TournamentBPParams *params);
  66
  67     /**
  68      * Looks up the given address in the branch predictor and returns
  69      * a true/false value as to whether it is taken.  Also creates a
  70      * BPHistory object to store any state it will need on squash/update.
  71      * @param branch_addr The address of the branch to look up.
  72      * @param bp_history Pointer that will be set to the BPHistory object.
  73      * @return Whether or not the branch is taken.
  74      */
  75     bool lookup(ThreadID tid, Addr branch_addr, void * &bp_history);
  76
  77     /**
  78      * Records that there was an unconditional branch, and modifies
  79      * the bp history to point to an object that has the previous
  80      * global history stored in it.
  81      * @param bp_history Pointer that will be set to the BPHistory object.
  82      */
  83     void uncondBranch(ThreadID tid, Addr pc, void * &bp_history);
  84     /**
  85      * Updates the branch predictor to Not Taken if a BTB entry is
  86      * invalid or not found.
  87      * @param branch_addr The address of the branch to look up.
  88      * @param bp_history Pointer to any bp history state.
  89      * @return Whether or not the branch is taken.
  90      */
  91     void btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history);
  92     /**
  93      * Updates the branch predictor with the actual result of a branch.
  94      * @param branch_addr The address of the branch to update.
  95      * @param taken Whether or not the branch was taken.
  96      * @param bp_history Pointer to the BPHistory object that was created
  97      * when the branch was predicted.
  98      * @param squashed is set when this function is called during a squash
  99      * operation.
 100      * @param inst Static instruction information
 101      * @param corrTarget Resolved target of the branch (only needed if
 102      * squashed)
 103      */
 104     void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history,
 105                 bool squashed, const StaticInstPtr & inst, Addr corrTarget);
 106
 107     /**
 108      * Restores the global branch history on a squash.
 109      * @param bp_history Pointer to the BPHistory object that has the
 110      * previous global branch history in it.
 111      */
 112     void squash(ThreadID tid, void *bp_history);
 113
 114   private:
 115     /**
 116      * Returns if the branch should be taken or not, given a counter
 117      * value.
 118      * @param count The counter value.
 119      */
 120     inline bool getPrediction(uint8_t &count);
 121
 122     /**
 123      * Returns the local history index, given a branch address.
 124      * @param branch_addr The branch's PC address.
 125      */
 126     inline unsigned calcLocHistIdx(Addr &branch_addr);
 127
 128     /** Updates global history as taken. */
 129     inline void updateGlobalHistTaken(ThreadID tid);
 130
 131     /** Updates global history as not taken. */
 132     inline void updateGlobalHistNotTaken(ThreadID tid);
 133
 134     /**
 135      * Updates local histories as taken.
 136      * @param local_history_idx The local history table entry that
 137      * will be updated.
 138      */
 139     inline void updateLocalHistTaken(unsigned local_history_idx);
 140
 141     /**
 142      * Updates local histories as not taken.
 143      * @param local_history_idx The local history table entry that
 144      * will be updated.
 145      */
 146     inline void updateLocalHistNotTaken(unsigned local_history_idx);
 147
 148     /**
 149      * The branch history information that is created upon predicting
 150      * a branch.  It will be passed back upon updating and squashing,
 151      * when the BP can use this information to update/restore its
 152      * state properly.
 153      */
 154     struct BPHistory {
 155 #ifdef DEBUG
 156         BPHistory()
 157         { newCount++; }
 158         ~BPHistory()
 159         { newCount--; }
 160
 161         static int newCount;
 162 #endif
 163         unsigned globalHistory;
 164         unsigned localHistoryIdx;
 165         unsigned localHistory;
 166         bool localPredTaken;
 167         bool globalPredTaken;
 168         bool globalUsed;
 169     };
 170
 171     /** Flag for invalid predictor index */
 172     static const int invalidPredictorIndex = -1;
 173     /** Number of counters in the local predictor. */
 174     unsigned localPredictorSize;
 175
 176     /** Mask to truncate values stored in the local history table. */
 177     unsigned localPredictorMask;
 178
 179     /** Number of bits of the local predictor's counters. */
 180     unsigned localCtrBits;
 181
 182     /** Local counters. */
 183     std::vector<SatCounter> localCtrs;
 184
 185     /** Array of local history table entries. */
 186     std::vector<unsigned> localHistoryTable;
 187
 188     /** Number of entries in the local history table. */
 189     unsigned localHistoryTableSize;
 190
 191     /** Number of bits for each entry of the local history table. */
 192     unsigned localHistoryBits;
 193
 194     /** Number of entries in the global predictor. */
 195     unsigned globalPredictorSize;
 196
 197     /** Number of bits of the global predictor's counters. */
 198     unsigned globalCtrBits;
 199
 200     /** Array of counters that make up the global predictor. */
 201     std::vector<SatCounter> globalCtrs;
 202
 203     /** Global history register. Contains as much history as specified by
 204      *  globalHistoryBits. Actual number of bits used is determined by
 205      *  globalHistoryMask and choiceHistoryMask. */
 206     std::vector<unsigned> globalHistory;
 207
 208     /** Number of bits for the global history. Determines maximum number of
 209         entries in global and choice predictor tables. */
 210     unsigned globalHistoryBits;
 211
 212     /** Mask to apply to globalHistory to access global history table.
 213      *  Based on globalPredictorSize.*/
 214     unsigned globalHistoryMask;
 215
 216     /** Mask to apply to globalHistory to access choice history table.
 217      *  Based on choicePredictorSize.*/
 218     unsigned choiceHistoryMask;
 219
 220     /** Mask to control how much history is stored. All of it might not be
 221      *  used. */
 222     unsigned historyRegisterMask;
 223
 224     /** Number of entries in the choice predictor. */
 225     unsigned choicePredictorSize;
 226
 227     /** Number of bits in the choice predictor's counters. */
 228     unsigned choiceCtrBits;
 229
 230     /** Array of counters that make up the choice predictor. */
 231     std::vector<SatCounter> choiceCtrs;
 232
 233     /** Thresholds for the counter value; above the threshold is taken,
 234      *  equal to or below the threshold is not taken.
 235      */
 236     unsigned localThreshold;
 237     unsigned globalThreshold;
 238     unsigned choiceThreshold;
 239 };
 240
 241 #endif // __CPU_PRED_TOURNAMENT_PRED_HH__