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