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