tournament.hh revision 10785
19651SAndreas.Sandberg@ARM.com/* 29651SAndreas.Sandberg@ARM.com * Copyright (c) 2011, 2014 ARM Limited 39651SAndreas.Sandberg@ARM.com * All rights reserved 49651SAndreas.Sandberg@ARM.com * 59651SAndreas.Sandberg@ARM.com * The license below extends only to copyright in the software and shall 69651SAndreas.Sandberg@ARM.com * not be construed as granting a license to any other intellectual 79651SAndreas.Sandberg@ARM.com * property including but not limited to intellectual property relating 89651SAndreas.Sandberg@ARM.com * to a hardware implementation of the functionality of the software 99651SAndreas.Sandberg@ARM.com * licensed hereunder. You may use the software subject to the license 109651SAndreas.Sandberg@ARM.com * terms below provided that you ensure that this notice is replicated 119651SAndreas.Sandberg@ARM.com * unmodified and in its entirety in all distributions of the software, 129651SAndreas.Sandberg@ARM.com * modified or unmodified, in source code or in binary form. 139651SAndreas.Sandberg@ARM.com * 149651SAndreas.Sandberg@ARM.com * Copyright (c) 2004-2006 The Regents of The University of Michigan 159651SAndreas.Sandberg@ARM.com * All rights reserved. 169651SAndreas.Sandberg@ARM.com * 179651SAndreas.Sandberg@ARM.com * Redistribution and use in source and binary forms, with or without 189651SAndreas.Sandberg@ARM.com * modification, are permitted provided that the following conditions are 199651SAndreas.Sandberg@ARM.com * met: redistributions of source code must retain the above copyright 209651SAndreas.Sandberg@ARM.com * notice, this list of conditions and the following disclaimer; 219651SAndreas.Sandberg@ARM.com * redistributions in binary form must reproduce the above copyright 229651SAndreas.Sandberg@ARM.com * notice, this list of conditions and the following disclaimer in the 239651SAndreas.Sandberg@ARM.com * documentation and/or other materials provided with the distribution; 249651SAndreas.Sandberg@ARM.com * neither the name of the copyright holders nor the names of its 259651SAndreas.Sandberg@ARM.com * contributors may be used to endorse or promote products derived from 269651SAndreas.Sandberg@ARM.com * this software without specific prior written permission. 279651SAndreas.Sandberg@ARM.com * 289651SAndreas.Sandberg@ARM.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 299651SAndreas.Sandberg@ARM.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 309651SAndreas.Sandberg@ARM.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 319651SAndreas.Sandberg@ARM.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 329651SAndreas.Sandberg@ARM.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 339651SAndreas.Sandberg@ARM.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 349651SAndreas.Sandberg@ARM.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 359651SAndreas.Sandberg@ARM.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 369651SAndreas.Sandberg@ARM.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 379651SAndreas.Sandberg@ARM.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3811988Sandreas.sandberg@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 399651SAndreas.Sandberg@ARM.com * 409651SAndreas.Sandberg@ARM.com * Authors: Kevin Lim 419651SAndreas.Sandberg@ARM.com * Timothy M. Jones 4213665Sandreas.sandberg@arm.com * Nilay Vaish 4313665Sandreas.sandberg@arm.com */ 449651SAndreas.Sandberg@ARM.com 459651SAndreas.Sandberg@ARM.com#ifndef __CPU_PRED_TOURNAMENT_PRED_HH__ 469651SAndreas.Sandberg@ARM.com#define __CPU_PRED_TOURNAMENT_PRED_HH__ 479651SAndreas.Sandberg@ARM.com 489651SAndreas.Sandberg@ARM.com#include <vector> 499651SAndreas.Sandberg@ARM.com 5011988Sandreas.sandberg@arm.com#include "base/types.hh" 5111988Sandreas.sandberg@arm.com#include "cpu/pred/bpred_unit.hh" 5211988Sandreas.sandberg@arm.com#include "cpu/pred/sat_counter.hh" 5311988Sandreas.sandberg@arm.com#include "params/TournamentBP.hh" 549651SAndreas.Sandberg@ARM.com 559651SAndreas.Sandberg@ARM.com/** 569651SAndreas.Sandberg@ARM.com * Implements a tournament branch predictor, hopefully identical to the one 579651SAndreas.Sandberg@ARM.com * used in the 21264. It has a local predictor, which uses a local history 589651SAndreas.Sandberg@ARM.com * table to index into a table of counters, and a global predictor, which 599651SAndreas.Sandberg@ARM.com * uses a global history to index into a table of counters. A choice 609651SAndreas.Sandberg@ARM.com * predictor chooses between the two. Only the global history register 619651SAndreas.Sandberg@ARM.com * is speculatively updated, the rest are updated upon branches committing 629651SAndreas.Sandberg@ARM.com * or misspeculating. 639651SAndreas.Sandberg@ARM.com */ 649651SAndreas.Sandberg@ARM.comclass TournamentBP : public BPredUnit 659651SAndreas.Sandberg@ARM.com{ 669651SAndreas.Sandberg@ARM.com public: 679690Sandreas@sandberg.pp.se /** 689655SAndreas.Sandberg@ARM.com * Default branch predictor constructor. 6911399Sandreas.sandberg@arm.com */ 7011399Sandreas.sandberg@arm.com TournamentBP(const TournamentBPParams *params); 719754Sandreas@sandberg.pp.se 729754Sandreas@sandberg.pp.se /** 739651SAndreas.Sandberg@ARM.com * 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