tournament.hh revision 10785:f56c10663a01
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 * Authors: Kevin Lim 41 * Timothy M. Jones 42 * Nilay Vaish 43 */ 44 45#ifndef __CPU_PRED_TOURNAMENT_PRED_HH__ 46#define __CPU_PRED_TOURNAMENT_PRED_HH__ 47 48#include <vector> 49 50#include "base/types.hh" 51#include "cpu/pred/bpred_unit.hh" 52#include "cpu/pred/sat_counter.hh" 53#include "params/TournamentBP.hh" 54 55/** 56 * Implements a tournament branch predictor, hopefully identical to the one 57 * used in the 21264. It has a local predictor, which uses a local history 58 * table to index into a table of counters, and a global predictor, which 59 * uses a global history to index into a table of counters. A choice 60 * predictor chooses between the two. Only the global history register 61 * is speculatively updated, the rest are updated upon branches committing 62 * or misspeculating. 63 */ 64class TournamentBP : public BPredUnit 65{ 66 public: 67 /** 68 * Default branch predictor constructor. 69 */ 70 TournamentBP(const TournamentBPParams *params); 71 72 /** 73 * Looks up the given address in the branch predictor and returns 74 * a true/false value as to whether it is taken. Also creates a 75 * BPHistory object to store any state it will need on squash/update. 76 * @param branch_addr The address of the branch to look up. 77 * @param bp_history Pointer that will be set to the BPHistory object. 78 * @return Whether or not the branch is taken. 79 */ 80 bool lookup(Addr branch_addr, void * &bp_history); 81 82 /** 83 * Records that there was an unconditional branch, and modifies 84 * the bp history to point to an object that has the previous 85 * global history stored in it. 86 * @param bp_history Pointer that will be set to the BPHistory object. 87 */ 88 void uncondBranch(Addr pc, void * &bp_history); 89 /** 90 * Updates the branch predictor to Not Taken if a BTB entry is 91 * invalid or not found. 92 * @param branch_addr The address of the branch to look up. 93 * @param bp_history Pointer to any bp history state. 94 * @return Whether or not the branch is taken. 95 */ 96 void btbUpdate(Addr branch_addr, void * &bp_history); 97 /** 98 * Updates the branch predictor with the actual result of a branch. 99 * @param branch_addr The address of the branch to update. 100 * @param taken Whether or not the branch was taken. 101 * @param bp_history Pointer to the BPHistory object that was created 102 * when the branch was predicted. 103 * @param squashed is set when this function is called during a squash 104 * operation. 105 */ 106 void update(Addr branch_addr, bool taken, void *bp_history, bool squashed); 107 108 void retireSquashed(void *bp_history); 109 110 /** 111 * Restores the global branch history on a squash. 112 * @param bp_history Pointer to the BPHistory object that has the 113 * previous global branch history in it. 114 */ 115 void squash(void *bp_history); 116 117 /** Returns the global history. */ 118 inline unsigned readGlobalHist() { return globalHistory; } 119 120 private: 121 /** 122 * Returns if the branch should be taken or not, given a counter 123 * value. 124 * @param count The counter value. 125 */ 126 inline bool getPrediction(uint8_t &count); 127 128 /** 129 * Returns the local history index, given a branch address. 130 * @param branch_addr The branch's PC address. 131 */ 132 inline unsigned calcLocHistIdx(Addr &branch_addr); 133 134 /** Updates global history as taken. */ 135 inline void updateGlobalHistTaken(); 136 137 /** Updates global history as not taken. */ 138 inline void updateGlobalHistNotTaken(); 139 140 /** 141 * Updates local histories as taken. 142 * @param local_history_idx The local history table entry that 143 * will be updated. 144 */ 145 inline void updateLocalHistTaken(unsigned local_history_idx); 146 147 /** 148 * Updates local histories as not taken. 149 * @param local_history_idx The local history table entry that 150 * will be updated. 151 */ 152 inline void updateLocalHistNotTaken(unsigned local_history_idx); 153 154 /** 155 * The branch history information that is created upon predicting 156 * a branch. It will be passed back upon updating and squashing, 157 * when the BP can use this information to update/restore its 158 * state properly. 159 */ 160 struct BPHistory { 161#ifdef DEBUG 162 BPHistory() 163 { newCount++; } 164 ~BPHistory() 165 { newCount--; } 166 167 static int newCount; 168#endif 169 unsigned globalHistory; 170 unsigned localHistory; 171 bool localPredTaken; 172 bool globalPredTaken; 173 bool globalUsed; 174 }; 175 176 /** Flag for invalid predictor index */ 177 static const int invalidPredictorIndex = -1; 178 /** Local counters. */ 179 std::vector<SatCounter> localCtrs; 180 181 /** Number of counters in the local predictor. */ 182 unsigned localPredictorSize; 183 184 /** Mask to truncate values stored in the local history table. */ 185 unsigned localPredictorMask; 186 187 /** Number of bits of the local predictor's counters. */ 188 unsigned localCtrBits; 189 190 /** Array of local history table entries. */ 191 std::vector<unsigned> localHistoryTable; 192 193 /** Number of entries in the local history table. */ 194 unsigned localHistoryTableSize; 195 196 /** Number of bits for each entry of the local history table. */ 197 unsigned localHistoryBits; 198 199 /** Array of counters that make up the global predictor. */ 200 std::vector<SatCounter> globalCtrs; 201 202 /** Number of entries in the global predictor. */ 203 unsigned globalPredictorSize; 204 205 /** Number of bits of the global predictor's counters. */ 206 unsigned globalCtrBits; 207 208 /** Global history register. Contains as much history as specified by 209 * globalHistoryBits. Actual number of bits used is determined by 210 * globalHistoryMask and choiceHistoryMask. */ 211 unsigned globalHistory; 212 213 /** Number of bits for the global history. Determines maximum number of 214 entries in global and choice predictor tables. */ 215 unsigned globalHistoryBits; 216 217 /** Mask to apply to globalHistory to access global history table. 218 * Based on globalPredictorSize.*/ 219 unsigned globalHistoryMask; 220 221 /** Mask to apply to globalHistory to access choice history table. 222 * Based on choicePredictorSize.*/ 223 unsigned choiceHistoryMask; 224 225 /** Mask to control how much history is stored. All of it might not be 226 * used. */ 227 unsigned historyRegisterMask; 228 229 /** Array of counters that make up the choice predictor. */ 230 std::vector<SatCounter> choiceCtrs; 231 232 /** Number of entries in the choice predictor. */ 233 unsigned choicePredictorSize; 234 235 /** Number of bits in the choice predictor's counters. */ 236 unsigned choiceCtrBits; 237 238 /** Thresholds for the counter value; above the threshold is taken, 239 * equal to or below the threshold is not taken. 240 */ 241 unsigned localThreshold; 242 unsigned globalThreshold; 243 unsigned choiceThreshold; 244}; 245 246#endif // __CPU_PRED_TOURNAMENT_PRED_HH__ 247